[Bf-blender-cvs] SVN commit: /data/svn/bf-blender [15971] branches/soc-2008-unclezeiv/source /blender/render/intern/source/lightcuts.c: Faster tree creation time.
Davide Vercelli
davide.vercelli at gmail.com
Tue Aug 5 14:50:46 CEST 2008
Revision: 15971
http://projects.blender.org/plugins/scmsvn/viewcvs.php?view=rev&root=bf-blender&revision=15971
Author: unclezeiv
Date: 2008-08-05 14:50:46 +0200 (Tue, 05 Aug 2008)
Log Message:
-----------
Faster tree creation time. The improvement is already pretty tangible but more optimizations are on the way.
Also changed the intensity conversion formula for area lights: now it should do a better (but still not perfect) job in matching the default (Blender internal) intensity of area lights. Attention testers: this means that existing blend files will render differently from this revision on.
Modified Paths:
--------------
branches/soc-2008-unclezeiv/source/blender/render/intern/source/lightcuts.c
Modified: branches/soc-2008-unclezeiv/source/blender/render/intern/source/lightcuts.c
===================================================================
--- branches/soc-2008-unclezeiv/source/blender/render/intern/source/lightcuts.c 2008-08-05 12:41:53 UTC (rev 15970)
+++ branches/soc-2008-unclezeiv/source/blender/render/intern/source/lightcuts.c 2008-08-05 12:50:46 UTC (rev 15971)
@@ -33,6 +33,7 @@
#include "BLI_arithb.h"
#include "BLI_blenlib.h"
#include "BLI_heap.h"
+#include "BLI_kdtree.h"
#include "BLI_rand.h"
#include "DNA_group_types.h"
#include "DNA_lamp_types.h"
@@ -233,11 +234,13 @@
return (one->luminance + two->luminance) * VEC_LEN_SQ(diff);
}
-static void add_new_cluster(LightcutsCluster * array, LightcutsClusterPair * minpair, int * root)
+/* returns 0 if the new cluster uses the first child as representative, 1 otherwise */
+static int add_new_cluster(LightcutsCluster * array, LightcutsClusterPair * minpair, int * root)
{
LightcutsCluster *one = &array[minpair->first];
LightcutsCluster *two = &array[minpair->second];
LightcutsCluster *dest = &array[*root];
+ int rep;
/* mark children elements as already in tree */
one->in_tree = 1;
@@ -269,10 +272,12 @@
if (BLI_frand() * (one->luminance + two->luminance) < one->luminance) {
dest->lar= one->lar;
VECCOPY(dest->col, one->col);
+ rep= 0;
}
else {
dest->lar= two->lar;
VECCOPY(dest->col, two->col);
+ rep= 1;
}
dest->intensity= dest->luminance / LC_LUMINOSITY(dest->col);
@@ -284,6 +289,8 @@
dest->sphere_dist= MAX2(one->sphere_dist, two->sphere_dist);
(*root)++;
+
+ return rep;
}
static void find_and_insert_new_min(Heap * heap, LightcutsCluster * array, int size, LightcutsClusterPair * pair, int id, int from, float c)
@@ -324,6 +331,77 @@
}
}
+/* this one uses kd tree */
+static void find_and_insert_new_min2(Heap * heap, KDTree * tree, KDTreeNearest *nearest, LightcutsCluster * array, LightcutsClusterPair * pair, int id, float c)
+{
+ LightcutsCluster *one= &array[id];
+ int near_idx= -1;
+ float pair_metric, metric;
+ float max_dist;
+ int found, j, other= -1;
+
+ /* find nearest light in kdtree */
+ found= BLI_kdtree_find_n_nearest(tree, 2, one->lar->co, NULL, nearest);
+
+ /*
+ * TODO: XXX: a bit hackish way to exclude the current element:
+ * we look for the 2 nearest elements and discard the current one
+ */
+ for (j= 0; j < found; j++)
+ if (nearest[j].index!= id)
+ near_idx= nearest[j].index;
+
+ /* when a single element is remaining, the search fails */
+ if (near_idx== -1)
+ return;
+
+ /* compute metric w.r.t. the nearest element */
+ pair_metric= lightcuts_compute_metric(c, one, &array[near_idx]);
+ metric= pair_metric;
+ other= near_idx;
+
+ /*
+ * compute maximum interesting distance:
+ * we are sure that elements further away have a greater metric value
+ */
+ max_dist= sqrtf(pair_metric / one->luminance);
+
+ /* get all lights within that distance */
+ found= BLI_kdtree_find_in_sphere(tree, max_dist, one->lar->co, NULL, nearest);
+
+ /* for each light compute metric and maximum distance */
+ /*
+ * TODO: better yet would be to take advantage of such knowledge
+ * while traversing the kdtree
+ */
+ for (j= 0; j < found; j++) {
+ LightcutsCluster *two= &array[nearest[j].index];
+
+ if (nearest[j].index== id)
+ continue;
+
+ /* note: elements in "nearest" are sorted by distance */
+ if (nearest[j].dist > max_dist)
+ break;
+
+ pair_metric= lightcuts_compute_metric(c, one, two);
+ max_dist= sqrtf(pair_metric / one->luminance);
+
+ if (pair_metric < metric) {
+ other= two->id;
+ metric= pair_metric;
+ }
+ }
+
+ if (other != -1)
+ {
+ pair->first = id;
+ pair->second = other;
+
+ BLI_heap_insert(heap, metric, pair);
+ }
+}
+
static void lightcuts_fill_array(ListBase *pointlights, LightcutsTree *tree, int cur_type)
{
GroupObject *go;
@@ -526,6 +604,117 @@
MEM_freeN(pair_array);
}
+/* this one uses kdtree */
+static void lightcuts_build_tree2(LightcutsTree *tree, float c)
+{
+ int i, rep, cluster_id= 0;
+ LightcutsCluster *array= tree->array;
+#ifdef LIGHTCUTS_DEBUG
+ double p1, p2;
+ char timestr[256];
+#endif
+
+ Heap * heap = BLI_heap_new();
+ LightcutsClusterPair *pair_array= MEM_callocN(sizeof(LightcutsClusterPair) * tree->counter * 2, "pair_array");
+
+ KDTree* kdtree = BLI_kdtree_new(tree->counter);
+ KDTreeNearest *nearest= MEM_callocN(sizeof(KDTreeNearest) * tree->counter, "kdtreenearest");
+
+#ifdef LIGHTCUTS_DEBUG
+ p1= PIL_check_seconds_timer();
+#endif
+
+ /* kdtree construction */
+ for (i= 0; i < tree->counter; i++)
+ BLI_kdtree_insert(kdtree, i, array[i].lar->co, NULL);
+
+#ifdef LIGHTCUTS_DEBUG
+ p2 = PIL_check_seconds_timer();
+ BLI_timestr(p2 - p1, timestr);
+ printf("add nodes: %s\n", timestr);
+ p1=p2;
+#endif
+
+ BLI_kdtree_balance(kdtree);
+
+#ifdef LIGHTCUTS_DEBUG
+ p2 = PIL_check_seconds_timer();
+ BLI_timestr(p2 - p1, timestr);
+ printf("balance: %s\n", timestr);
+ p1=p2;
+#endif
+
+ BLI_kdtree_build_correspondence(kdtree, 2);
+
+#ifdef LIGHTCUTS_DEBUG
+ p2 = PIL_check_seconds_timer();
+ BLI_timestr(p2 - p1, timestr);
+ printf("corr: %s\n", timestr);
+ p1=p2;
+#endif
+
+ for (i = 0; i < tree->counter; i++)
+ if (array[i].type != CLUSTER_EMPTY)
+ find_and_insert_new_min2(heap, kdtree, nearest, array, &pair_array[i], i, c);
+
+ /* now we have a nice heap with shortest metric for each element */
+ /* heap size = N (number of lights) - 1, and it doesn't grow */
+
+ /* go through heap building the tree */
+ while (!BLI_heap_empty(heap)) {
+ LightcutsClusterPair * minpair = (LightcutsClusterPair *)BLI_heap_popmin(heap);
+ short in_tree1 = array[minpair->first].in_tree;
+ short in_tree2 = array[minpair->second].in_tree;
+
+ if (in_tree1)
+ continue;
+
+ /* we look for another minimum */
+ if (in_tree2) {
+ find_and_insert_new_min2(heap, kdtree, nearest, array, minpair, minpair->first, c);
+ continue;
+ }
+
+ /* valid pair: build cluster out of it, mark children as used */
+ cluster_id = tree->free;
+ rep= add_new_cluster(array, minpair, &tree->free);
+
+ if (rep==0) {
+ BLI_kdtree_weak_delete(kdtree, minpair->second);
+ BLI_kdtree_change_index(kdtree, minpair->first, tree->free -1);
+ }
+ else {
+ BLI_kdtree_weak_delete(kdtree, minpair->first);
+ BLI_kdtree_change_index(kdtree, minpair->second, tree->free -1);
+ }
+
+ /* new search, avoid considering in_tree children */
+ find_and_insert_new_min2(heap, kdtree, nearest, array, minpair, cluster_id, c);
+ }
+
+ BLI_heap_free(heap, 0);
+ BLI_kdtree_free(kdtree);
+
+#ifdef LIGHTCUTS_DEBUG
+ p2 = PIL_check_seconds_timer();
+ BLI_timestr(p2 - p1, timestr);
+ printf("finally do stuff: %s\n", timestr);
+ p1=p2;
+#endif
+
+ /* the last cluster added is the root of the tree */
+ tree->root = cluster_id;
+
+#ifdef LIGHTCUTS_DEBUG
+ dbg_check_tree(array, tree->root);
+ dbg_print_tree(array, tree->root, 0);
+#endif
+ printf(" %d nodes used.\n", tree->root + 1);
+
+ MEM_freeN(pair_array);
+ MEM_freeN(nearest);
+}
+
static void init_lamp(Render * re, LampRen * lar)
{
/* float xs, ys, dist, distkw; */
@@ -875,8 +1064,8 @@
realw= sqrtf(VEC_LEN_SQ(orig->mat[0])) * orig->area_size;
realh= sqrtf(VEC_LEN_SQ(orig->mat[1])) * orig->area_sizey;
- n= MAX2((int)(density * realw), 1) * MAX2((int)(density * realh), 1);
- factor= 0.5f * sqrtf(orig->dist) * realw * realh / n;
+ n= MAX2((int)(density * realw), 1) * MAX2((int)(density * realh), 1);
+ factor= 2.0 * M_PI * orig->dist / (4.0 * realw * realh * n);
/* XXX: TODO: temporary check just to avoid freezing on undue densities */
if (lcd->light_counter + n > re->r.lightcuts_max_lights) {
@@ -1041,7 +1230,7 @@
if (lcd->trees[i].counter > 0) {
lightcuts_fill_array(pointlights, &lcd->trees[i], i);
printf("Lightcuts: building %s tree - ", tree_names[i]);
- lightcuts_build_tree(&lcd->trees[i], lcd->bb_diag_sq);
+ lightcuts_build_tree2(&lcd->trees[i], lcd->bb_diag_sq);
}
}
More information about the Bf-blender-cvs
mailing list