[Bf-blender-cvs] SVN commit: /data/svn/bf-blender [15295] branches/soc-2008-unclezeiv/source /blender/render/intern/source/lightcuts.c: code reorganization: now each tree has its own structure (LightcutsTree)

Davide Vercelli davide.vercelli at gmail.com
Sat Jun 21 14:23:16 CEST 2008


Revision: 15295
          http://projects.blender.org/plugins/scmsvn/viewcvs.php?view=rev&root=bf-blender&revision=15295
Author:   unclezeiv
Date:     2008-06-21 14:23:04 +0200 (Sat, 21 Jun 2008)

Log Message:
-----------
code reorganization: now each tree has its own structure (LightcutsTree)

(sorry, my editor changed a lot of whitespace as well)

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-06-21 10:33:12 UTC (rev 15294)
+++ branches/soc-2008-unclezeiv/source/blender/render/intern/source/lightcuts.c	2008-06-21 12:23:04 UTC (rev 15295)
@@ -53,6 +53,17 @@
 
 #define LA_TYPE_TO_CLUSTER_TYPE(c) ((c)+1)
 
+/* = LA_X */
+#define TREE_LOCAL 0
+#define TREE_SUN   1
+#define TREE_SPOT  2
+#define _TREES_SIZE 3
+
+#define CLUSTER_TYPE_TO_ARRAY_IDX(c) ((c)-1)
+
+/* strings for guarded alloc */
+char *array_names[]= {"lc_array_local", "lc_array_sun", "lc_array_spot"};
+
 /* node of the lightcuts tree */
 typedef struct LightcutsCluster
 {
@@ -89,28 +100,28 @@
 	float f_clus_noshad;
 } CutNode;
 
+typedef struct LightcutsTree {
+	LightcutsCluster *array;
+	int free; /* location of first empty slot */
+	int root; /* id of root node */
+	int counter; /* number of available lights for this type */
+} LightcutsTree;
+
 typedef struct LightcutsData {
 	/* NOTE: conservative space estimation */
 	/* TODO: equivalent data structures for sun and spot */
 	ListBase pointlights;
-	LightcutsCluster *array_local;
-	int free_local; /* location of first empty slot */
-	int root_local; /* id of root node */
-	int counter_local;
 
+	LightcutsTree trees[_TREES_SIZE];
+
 	float max_local_dist; /* maximum distance for local lights */
 
-	LightcutsCluster *array_sun;
-	int free_sun; /* location of first empty slot */
-	int root_sun; /* id of root node */
-	int counter_sun;
-
 	int light_counter;
-	
+
 	float error_rate;
 	int max_lights;
 	int max_cut;
-	
+
 	CutNode *cut_nodes;
 	int cut_nodes_size;
 #ifdef LIGHTCUTS_DEBUG
@@ -133,15 +144,15 @@
 {
 	/* TODO: compute metric also for oriented lights */
 	float diff[3], min[3], max[3];
-	
+
 	VECCOPY(min, one->min);
 	VECCOPY(max, one->max);
-	
+
 	DO_MINMAX(two->min, min, max);
 	DO_MINMAX(two->max, min, max);
-	
+
 	VECSUB(diff, max, min);
-	
+
 	return (one->luminance + two->luminance) * VEC_LEN_SQ(diff);
 }
 
@@ -150,11 +161,11 @@
 	LightcutsCluster *one = &array[minpair->first];
 	LightcutsCluster *two = &array[minpair->second];
 	LightcutsCluster *dest = &array[*root];
-	
+
 	/* mark children elements as already in tree */
 	one->in_tree = 1;
 	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->id = *root;
@@ -165,14 +176,14 @@
 #ifdef LIGHTCUTS_DEBUG
 	dest->dbg_parent = -1;
 	one->dbg_parent = two->dbg_parent = dest->id;
-#endif 
-	
+#endif
+
 	/* compute new bounding box */
 	VECCOPY(dest->min, one->min);
 	VECCOPY(dest->max, one->max);
 	DO_MINMAX(two->min, dest->min, dest->max);
 	DO_MINMAX(two->max, dest->min, dest->max);
-	
+
 	/* the representative light is chosen randomly among children */
 	if (BLI_frand() * (one->luminance + two->luminance) < one->luminance) {
 		dest->lar= one->lar;
@@ -183,7 +194,7 @@
 		VECCOPY(dest->col, two->col);
 	}
 	dest->intensity= dest->luminance / LC_LUMINOSITY(dest->col);
-	
+
 	(*root)++;
 }
 
@@ -195,19 +206,19 @@
 	float pair_metric;
 	int other = -1;
 	int i;
-	
+
 	for (i = from; i < size; i++)
 	{
 		if (i == id)
 			continue;
-		
+
 		el2 = &array[i];
-		
+
 		if (el2->type == CLUSTER_EMPTY)
 			break;
 		if (el2->in_tree)
 			continue;
-		
+
 		pair_metric = lightcuts_compute_metric(el, el2);
 		if (pair_metric < metric)
 		{
@@ -215,37 +226,37 @@
 			other = i;
 		}
 	}
-	
+
 	if (other != -1)
 	{
 		pair->first = id;
 		pair->second = other;
-	
+
 		BLI_heap_insert(heap, metric, pair);
 	}
 }
 
-static void lightcuts_fill_array(ListBase * pointlights, LightcutsCluster **array, int *n_free, int max_lights, char * name, int cur_type)
+static void lightcuts_fill_array(ListBase *pointlights, LightcutsTree *tree, int cur_type)
 {
 	GroupObject *go;
 	LampRen *lar;
 	LightcutsCluster *clus;
-	
-	*array= MEM_callocN(sizeof(LightcutsCluster) * max_lights * 2, name);
-	*n_free= 0;
 
-	clus= *array;
-		
+	tree->array= MEM_callocN(sizeof(LightcutsCluster) * tree->counter * 2, array_names[cur_type]);
+	tree->free= 0;
+
+	clus= tree->array;
+
 	for(go = pointlights->first; go; go = go->next) {
 		lar = go->lampren;
 		if (lar==NULL) continue;
-		
+
 		if (lar->type!=cur_type)
 			continue;
-		
+
 		clus->type = LA_TYPE_TO_CLUSTER_TYPE(cur_type);
 		clus->in_tree = 0;
-		clus->id = *n_free;
+		clus->id = tree->free;
 		clus->intensity = lar->energy;
 
 		switch (lar->type) {
@@ -265,16 +276,16 @@
 			break;
 		}
 		clus->lar = lar;
-		
+
 		/* we need the original lamp color, not the premultiplied one */
 		/* TODO: maybe we could directly preserve this value when creating the render database? */
 		clus->col[0]= lar->r / lar->energy;
 		clus->col[1]= lar->g / lar->energy;
 		clus->col[2]= lar->b / lar->energy;
 		clus->luminance= LC_LUMINOSITY(clus->col) * lar->energy;
-		
+
 		clus++;
-		(*n_free)++;
+		tree->free++;
 	}
 }
 
@@ -286,85 +297,86 @@
 	for (i = 0; i < lev; i++)
 		printf("-");
 	printf(" id %d, int %f, lum %f\n", el->id, el->intensity, el->luminance);
-	
+
 	if (el->child1 == 0 && el->child2 == 0)
 		return;
-		
+
 	dbg_print_tree(array, el->child1, lev + 1);
-	dbg_print_tree(array, el->child2, lev + 1);		
+	dbg_print_tree(array, el->child2, lev + 1);
 }
 
 static void dbg_check_tree(LightcutsCluster *array, int n_root)
 {
 	LightcutsCluster *el= &array[n_root];
-	
+
 	if (el->child1 == 0 && el->child2 == 0)
 		return;
-		
+
 	if ((el->id != array[el->child1].dbg_parent) ||
 		(el->id != array[el->child2].dbg_parent))
 		printf("id %d wrong!\n", el->id);
-	
+
 	dbg_check_tree(array, el->child1);
-	dbg_check_tree(array, el->child2);		
+	dbg_check_tree(array, el->child2);
 }
 #endif
 
-static void lightcuts_build_tree(int max_lights, LightcutsCluster *array, int *n_free, int *n_root)
-{	
+static void lightcuts_build_tree(LightcutsTree *tree)
+{
 	int i, cluster_id = 0;
-	
+	LightcutsCluster *array= tree->array;
+
 	Heap * heap = BLI_heap_new();
 	/* TODO: taylor size: done. current TODO is "check if it works" */
-	LightcutsClusterPair *pair_array= MEM_callocN(sizeof(LightcutsClusterPair) * max_lights * 2, "pair_array");
-	
-	for (i = 0; i < max_lights; i++)
+	LightcutsClusterPair *pair_array= MEM_callocN(sizeof(LightcutsClusterPair) * tree->counter * 2, "pair_array");
+
+	for (i = 0; i < tree->counter; i++)
 	{
 		if (array[i].type == CLUSTER_EMPTY)
 			break;
-				
-		find_and_insert_new_min(heap, array, max_lights * 2, &pair_array[i], i, i + 1);
+
+		find_and_insert_new_min(heap, array, tree->counter * 2, &pair_array[i], i, i + 1);
 	}
-	
+
 	/* 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 */		
+
+		/* we look for another minimum */
 		if (in_tree2)
 		{
-			find_and_insert_new_min(heap, array, max_lights * 2, minpair, minpair->first, 0);
+			find_and_insert_new_min(heap, array, tree->counter * 2, minpair, minpair->first, 0);
 			continue;
 		}
-		
+
 		/* valid pair: build cluster out of it, mark children as used */
-		cluster_id = *n_free;
-		add_new_cluster(array, minpair, n_free);
-		
+		cluster_id = tree->free;
+		add_new_cluster(array, minpair, &tree->free);
+
 		/* new search, avoid considering in_tree children */
-		find_and_insert_new_min(heap, array, max_lights * 2, minpair, cluster_id, 0);
+		find_and_insert_new_min(heap, array, tree->counter * 2, minpair, cluster_id, 0);
 	}
-	
+
 	BLI_heap_free(heap, 0);
-	
-	/* the last cluster added is the root of the tree */	
-	*n_root = cluster_id;
 
+	/* the last cluster added is the root of the tree */
+	tree->root = cluster_id;
+
 #ifdef LIGHTCUTS_DEBUG
-	dbg_check_tree(array, *n_root);
-	dbg_print_tree(array, *n_root, 0);
+	dbg_check_tree(array, tree->root);
+	dbg_print_tree(array, tree->root, 0);
 #endif
-	printf(" %d nodes used.\n", *n_root + 1);
-	
+	printf(" %d nodes used.\n", tree->root + 1);
+
 	MEM_freeN(pair_array);
 }
 
@@ -376,11 +388,11 @@
 static void init_lamp_data(Render * re, LampRen * lar)
 {
 	if(re->r.mode & R_SHADOW) {
-		
+
 		if(lar->type==LA_AREA && (lar->mode & LA_SHAD_RAY) && (lar->ray_samp_method == LA_SAMP_CONSTANT)) {
 			init_jitter_plane(lar);
 		}
-		
+
 		else if (lar->type==LA_SPOT && (lar->mode & LA_SHAD_BUF) ) {
 			/* Per lamp, one shadow buffer is made. */
 #if 0
@@ -390,7 +402,7 @@
 			initshadowbuf(re, lar, mat);	/* mat is altered */
 #endif
 		}
-		
+
 		/* this is the way used all over to check for shadow */
 		if(lar->shb || (lar->mode & LA_SHAD_RAY)) {
 			LampShadowSample *ls;
@@ -398,7 +410,7 @@
 			int a, b;
 
 			memset(re->shadowsamplenr, 0, sizeof(re->shadowsamplenr));
-			
+
 			lar->shadsamp= MEM_mallocN(re->r.threads*sizeof(LampShadowSample), "lamp shadow sample");
 			ls= lar->shadsamp;
 
@@ -430,49 +442,49 @@
 	LampRen *larnew;
 	float r, g, b, n;
 #endif
-	
+
 	re->lcdata = lcd = MEM_callocN(sizeof(LightcutsData), "LightcutsData");
 	pointlights= &lcd->pointlights;
 	lcd->max_local_dist = MAXFLOAT;
 	lcd->light_counter= 0;
-	
+
 	for(go=lights->first; go; go= go->next) {
 		lar= go->lampren;
 		if(lar==NULL) continue;
-		
+
 		/* first copy the initial light */
 		gonew= MEM_callocN(sizeof(GroupObject), "groupobject");
 		BLI_addtail(pointlights, gonew);
 		gonew->lampren= lar;
 		gonew->ob= 0;
 		gonew->recalc= go->recalc;
-		
+
 		switch (lar->type) {
 		case LA_LOCAL:
-			lcd->counter_local++;
-			
+			lcd->trees[TREE_LOCAL].counter++;
+
 			/* TODO: handle other attenuation models */
 
 			if (lar->dist < lcd->max_local_dist)
 				lcd->max_local_dist = lar->dist;
-			
+
 			break;
 		case LA_SUN:
-			lcd->counter_sun++;
+			lcd->trees[TREE_SUN].counter++;
 			break;
 		default:
 			continue;
 		}
-		
+
 		lcd->light_counter++;
-		
-		/* 
+
+		/*
 		 * each light will contribute only marginally to the shadowing
 		 * that's why here I set a simpler sampling method
 		 * TODO: QMC may be restored for stronger lights
 		 */
 		lar->ray_samp_method = LA_SAMP_CONSTANT;
-		
+
 #ifdef LIGHTCUTS_CURRENTLY_UNUSED
 		/*
 		 * proof-of-concept functionality:
@@ -490,54 +502,54 @@
 		 * objects... do we need objects there?
 		 */
 		gonew->ob= 0;
-		
+
 		larnew = (LampRen *)MEM_callocN(sizeof(LampRen), "lampren");

@@ Diff output truncated at 10240 characters. @@




More information about the Bf-blender-cvs mailing list