[Bf-blender-cvs] SVN commit: /data/svn/bf-blender [17154] branches/soc-2008-unclezeiv/source /blender: - building light trees with heap-less variant of the previous algorithm ( fast agglomerative clustering)
Davide Vercelli
davide.vercelli at gmail.com
Wed Oct 22 00:48:11 CEST 2008
Revision: 17154
http://projects.blender.org/plugins/scmsvn/viewcvs.php?view=rev&root=bf-blender&revision=17154
Author: unclezeiv
Date: 2008-10-22 00:48:11 +0200 (Wed, 22 Oct 2008)
Log Message:
-----------
- building light trees with heap-less variant of the previous algorithm (fast agglomerative clustering)
- tweaked the lightcuts metric function
Both implementation hints were found in the previously mentioned paper "Fast Agglomerative Clustering". Other minor optimizations are possible.
Modified Paths:
--------------
branches/soc-2008-unclezeiv/source/blender/blenlib/BLI_kdtree.h
branches/soc-2008-unclezeiv/source/blender/blenlib/intern/BLI_kdtree.c
branches/soc-2008-unclezeiv/source/blender/render/intern/source/lightcuts.c
Modified: branches/soc-2008-unclezeiv/source/blender/blenlib/BLI_kdtree.h
===================================================================
--- branches/soc-2008-unclezeiv/source/blender/blenlib/BLI_kdtree.h 2008-10-21 22:38:32 UTC (rev 17153)
+++ branches/soc-2008-unclezeiv/source/blender/blenlib/BLI_kdtree.h 2008-10-21 22:48:11 UTC (rev 17154)
@@ -83,5 +83,8 @@
* Please note: a correspondence table must be built (once) before using this feature */
int BLI_kdtree_change_index(KDTree *tree, int old_index, int new_index);
+/* gets the number of nodes currently part of the tree, minus the number of "weakly" deleted ones */
+int BLI_kdtree_valid_nodes(KDTree *tree);
+
#endif
Modified: branches/soc-2008-unclezeiv/source/blender/blenlib/intern/BLI_kdtree.c
===================================================================
--- branches/soc-2008-unclezeiv/source/blender/blenlib/intern/BLI_kdtree.c 2008-10-21 22:38:32 UTC (rev 17153)
+++ branches/soc-2008-unclezeiv/source/blender/blenlib/intern/BLI_kdtree.c 2008-10-21 22:48:11 UTC (rev 17154)
@@ -603,3 +603,8 @@
tree->correspondence[new_index]= tree->correspondence[old_index];
return 1;
}
+
+int BLI_kdtree_valid_nodes(KDTree *tree)
+{
+ return tree->totnode - tree->totdeleted;
+}
Modified: branches/soc-2008-unclezeiv/source/blender/render/intern/source/lightcuts.c
===================================================================
--- branches/soc-2008-unclezeiv/source/blender/render/intern/source/lightcuts.c 2008-10-21 22:38:32 UTC (rev 17153)
+++ branches/soc-2008-unclezeiv/source/blender/render/intern/source/lightcuts.c 2008-10-21 22:48:11 UTC (rev 17154)
@@ -347,7 +347,8 @@
if (one->type == CLUSTER_SPOT) {
float cos_a= get_bounding_cone_cos(NULL, one, two);
- float term = (1 - cos_a) * (1 - cos_a);
+ /* TODO: maybe export sine directly ? */
+ float term = cos_a < 0.0f ? 1.0 : (1.0f - cos_a * cos_a);
return (one->luminance + two->luminance) * (VEC_LEN_SQ(diff) + csq * term);
}
@@ -368,10 +369,10 @@
}
/* returns 0 if the new cluster uses the first child as representative, 1 otherwise */
-static int add_new_cluster(LightcutsData *lcd, LightcutsCluster *array, LightcutsClusterPair *minpair, int *root)
+static int add_new_cluster(LightcutsData *lcd, LightcutsCluster *array, int first, int second, int *root)
{
- LightcutsCluster *one = &array[minpair->first];
- LightcutsCluster *two = &array[minpair->second];
+ LightcutsCluster *one = &array[first];
+ LightcutsCluster *two = &array[second];
LightcutsCluster *dest = &array[*root];
int rep, use_one_as_repr;
@@ -380,10 +381,10 @@
two->in_tree = 1;
/* fill in the new cluster: please note that it is not yet in tree */
- dest->type = array[minpair->first].type;
+ dest->type = array[first].type;
dest->id = *root;
- dest->child1 = minpair->first;
- dest->child2 = minpair->second;
+ dest->child1 = first;
+ dest->child2 = second;
dest->luminance = one->luminance + two->luminance;
#ifdef LIGHTCUTS_DEBUG
@@ -554,6 +555,7 @@
*dist= MAXFLOAT;
}
+#if 0
/* this one uses kd tree */
static void find_and_insert_new_min2(Heap * heap, KDTree * tree, KDTreeNearest *nearest, KDSearchCallbackData *data, LightcutsClusterPair * pair, int id)
{
@@ -584,7 +586,36 @@
BLI_heap_insert(heap, metric, pair);
}
}
+#endif
+static int find_new_min(KDTree * tree, KDTreeNearest *nearest, KDSearchCallbackData *data, int id)
+{
+ LightcutsCluster *one= &data->array[id];
+ int other;
+
+ data->one= one;
+
+ if (one->type == CLUSTER_SPOT) {
+ float cos_a= cosf(one->cone_angle);
+ cos_a= MAX2(0.0f, cos_a);
+ data->mindir= (1 - cos_a) * (1 - cos_a) * data->c;
+ }
+ else
+ data->mindir= 0.0f;
+
+#ifdef LIGHTCUTS_DEBUG
+ printf("id %d, type %d, energy %10.7f, intensity %10.7f, luminance %10.7f ", one->id, one->type, one->lar->energy, one->intensity, one->luminance);
+#endif
+ other= BLI_kdtree_find_callback(tree, one->mrep_list[0].lar->co, NULL, one->id, cb_update_metric_max_dist, data, nearest);
+
+ if (other == -1) {
+ printf("BUG: it should always return a valid index! %d\n", id);
+ return 0;
+ }
+
+ return other;
+}
+
static void lightcuts_fill_array(LightcutsData *lcd, int cur_type)
{
LampRen *lar;
@@ -773,7 +804,7 @@
/* valid pair: build cluster out of it, mark children as used */
cluster_id = tree->free;
- add_new_cluster(array, minpair, &tree->free);
+ add_new_cluster(array, minpair->first, minpair->second, &tree->free);
/* new search, avoid considering in_tree children */
find_and_insert_new_min(heap, array, tree->counter * 2, minpair, cluster_id, 0, c);
@@ -794,6 +825,94 @@
}
#endif
+/* this one uses "fast agglomerative clustering" */
+static int lightcuts_build_tree3(LightcutsData *lcd, int tree_index)
+{
+ float c= lcd->scene_diag * lcd->scene_diag;
+ LightcutsTree *tree= &lcd->trees[tree_index];
+ LightcutsCluster *array= tree->array;
+ int clus_a, clus_b, clus_c, rep, stop= 0, cluster_id= 0, remaining;
+ KDTree* kdtree = BLI_kdtree_new(tree->counter);
+ KDTreeNearest *nearest= MEM_callocN(sizeof(KDTreeNearest) * tree->counter, "kdtreenearest");
+ KDSearchCallbackData data= {c, 0.0f, NULL, array};
+ int i;
+
+ /* kdtree construction */
+ for (i= 0; i < tree->counter; i++)
+ BLI_kdtree_insert(kdtree, i, array[i].mrep_list[0].lar->co, NULL);
+
+ BLI_kdtree_balance(kdtree);
+ BLI_kdtree_build_correspondence(kdtree, 2);
+
+ clus_a= 0;
+ if (tree->counter > 1)
+ clus_b= find_new_min(kdtree, nearest, &data, clus_a);
+
+ while (1) {
+
+ remaining= BLI_kdtree_valid_nodes(kdtree);
+
+ if (remaining <= 1)
+ break;
+
+ if (lcd->test_break()) {
+ stop= 1;
+ break;
+ }
+
+ clus_c = find_new_min(kdtree, nearest, &data, clus_b);
+
+ if (clus_a == clus_c
+ || (lightcuts_compute_metric(c, &array[clus_a], &array[clus_b]) == lightcuts_compute_metric(c, &array[clus_a], &array[clus_c])))
+ /* temporary code */
+ {
+ cluster_id= tree->free;
+ rep= add_new_cluster(lcd, array, clus_a, clus_b, &tree->free);
+
+ /* TODO: we always put it in more intense lamp, is this correct? */
+ if (rep==0) {
+ BLI_kdtree_weak_delete(kdtree, clus_b);
+ BLI_kdtree_change_index(kdtree, clus_a, cluster_id);
+ }
+ else {
+ BLI_kdtree_weak_delete(kdtree, clus_a);
+ BLI_kdtree_change_index(kdtree, clus_b, cluster_id);
+ }
+
+ if (remaining > 2) {
+ clus_a= cluster_id;
+ clus_b= find_new_min(kdtree, nearest, &data, clus_a);
+ }
+ }
+ else
+ {
+ clus_a= clus_b;
+ clus_b= clus_c;
+ }
+ }
+
+ /* the last cluster added is the root of the tree */
+ tree->root = cluster_id;
+
+#ifdef LIGHTCUTS_DEBUG
+ if (lcd->dbg_options & LC_DBG_TREE_PRINT) {
+ dbg_check_tree(array, tree->root);
+ dbg_print_tree(array, tree->root, 0);
+ }
+#endif
+
+ if (stop)
+ printf(" aborted.\n");
+ else
+ printf(" %d nodes used.\n", tree->root + 1);
+
+ BLI_kdtree_free(kdtree);
+ MEM_freeN(nearest);
+
+ return -stop;
+}
+
+#if 0
/* this one uses kdtree */
static int lightcuts_build_tree2(LightcutsData *lcd, int tree_index)
{
@@ -890,7 +1009,7 @@
/* valid pair: build cluster out of it, mark children as used */
cluster_id = tree->free;
- rep= add_new_cluster(lcd, array, minpair, &tree->free);
+ rep= add_new_cluster(lcd, array, minpair->first, minpair->second, &tree->free);
if (rep==0) {
BLI_kdtree_weak_delete(kdtree, minpair->second);
@@ -936,6 +1055,7 @@
return -stop;
}
+#endif
static void lamp_init(Render * re, LampRen * lar)
{
@@ -1785,7 +1905,7 @@
lcd->do_indir= re->r.lightcuts_indirect;
lcd->options= re->r.lightcuts_options;
lcd->error_rate= re->r.lightcuts_max_error;
- lcd->scene_diag= RE_ray_tree_max_size(re->raytree);
+ lcd->scene_diag= RE_ray_tree_max_size(re->raytree) / 16;
lcd->test_break= re->test_break;
#ifdef LIGHTCUTS_DEBUG
lcd->dbg_options= re->r.lightcuts_debug_options;
@@ -1937,7 +2057,7 @@
if (lcd->trees[i].counter > 0) {
lightcuts_fill_array(lcd, i);
printf("Lightcuts: building %s tree - ", tree_names[i]);
- if (lightcuts_build_tree2(lcd, i) == -1) {
+ if (lightcuts_build_tree3(lcd, i) == -1) {
stop= 1;
break;
}
More information about the Bf-blender-cvs
mailing list