[Bf-blender-cvs] SVN commit: /data/svn/bf-blender [15993] branches/soc-2008-unclezeiv/source /blender/render/intern/source/lightcuts.c: Changed tree building to use BLI_kdtree_find_callback.

[Davide Vercelli]

Revision: 15993
          http://projects.blender.org/plugins/scmsvn/viewcvs.php?view=rev&root=bf-blender&revision=15993
Author:   unclezeiv
Date:     2008-08-06 22:52:15 +0200 (Wed, 06 Aug 2008)

Log Message:
-----------
Changed tree building to use BLI_kdtree_find_callback. This seems to cut building times roughly by an additional 33%.

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-06 20:37:15 UTC (rev 15992)
+++ branches/soc-2008-unclezeiv/source/blender/render/intern/source/lightcuts.c	2008-08-06 20:52:15 UTC (rev 15993)
@@ -179,6 +179,12 @@
 	short do_phongcorr;
 } SampleCoordInfo;
 
+typedef struct KDSearchCallbackData {
+	float c;
+	LightcutsCluster *one;
+	LightcutsCluster *array;
+} KDSearchCallbackData;
+
 #define VEC_LEN_SQ(v) (v[0]*v[0] + v[1]*v[1] + v[2]*v[2])
 #define VECCOPYMUL(v1,v2,aS) {*(v1)= *(v2)*aS; *(v1+1)= *(v2+1)*aS; *(v1+2)= *(v2+2)*aS;}
 #define VECNEG(v) {*(v)=-*(v); *(v+1)=-*(v+1); *(v+2)=-*(v+2);}
@@ -331,70 +337,24 @@
 	}
 }
 
+static void cb_update_metric_max_dist(void *data, int index, float *val, float *dist)
+{
+	KDSearchCallbackData *p = (KDSearchCallbackData*) data;
+	*val= lightcuts_compute_metric(p->c, p->one, &p->array[index]);
+	*dist= *val / p->one->luminance;
+}
+
 /* 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;
+	KDSearchCallbackData data= {c, one, array};
 	
-	/* find nearest light in kdtree */
-	found= BLI_kdtree_find_n_nearest(tree, 2, one->lar->co, NULL, nearest);
+	int other= BLI_kdtree_find_callback(tree, one->lar->co, NULL, one->id, cb_update_metric_max_dist, &data, 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)
 	{
+		float metric= lightcuts_compute_metric(c, one, &array[other]);
 		pair->first = id;
 		pair->second = other;