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; } _______________________________________________ Bf-blender-cvs mailing list Bf-blender-cvs@blender.org http://lists.blender.org/mailman/listinfo/bf-blender-cvs