[Bf-blender-cvs] SVN commit: /data/svn/bf-blender [14900] branches/soc-2008-unclezeiv/source /blender/render/intern/source/lightcuts.c: Added code to build light tree from available lights.
Davide Vercelli
davide.vercelli at gmail.com
Tue May 20 02:01:14 CEST 2008
Revision: 14900
http://projects.blender.org/plugins/scmsvn/viewcvs.php?view=rev&root=bf-blender&revision=14900
Author: unclezeiv
Date: 2008-05-20 02:01:14 +0200 (Tue, 20 May 2008)
Log Message:
-----------
Added code to build light tree from available lights.
Please note that this is work in progress:
- algorithmic complexity is O(n^2): it can be lowered to O(n*logn), but I prefer to code the other parts of the algorithm first
- only omnidirectional lights (LA_LOCAL) are considered right now
- the tree is only built, it's not used yet (but at least it's possible to get a grasp of tree building times)
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-05-19 18:41:13 UTC (rev 14899)
+++ branches/soc-2008-unclezeiv/source/blender/render/intern/source/lightcuts.c 2008-05-20 00:01:14 UTC (rev 14900)
@@ -32,6 +32,7 @@
#include "BLI_arithb.h"
#include "BLI_blenlib.h"
+#include "BLI_heap.h"
#include "BLI_rand.h"
#include "DNA_group_types.h"
#include "DNA_lamp_types.h"
@@ -41,8 +42,224 @@
#include "render_types.h"
-#define max(a,b) ((a)>(b)?(a):(b))
+/* = LA_X + 1 */
+#define CLUSTER_EMPTY 0
+#define CLUSTER_LOCAL 1
+#define CLUSTER_SUN 2
+#define CLUSTER_SPOT 3
+/* TODO: these are WIP values */
+#define LIGHTCUTS_MAX_METRIC (10e38)
+#define LIGHTCUTS_MAX_LIGHTS (10000)
+
+/* node of the lightcuts tree */
+typedef struct LightcutsCluster
+{
+ short type;
+ short in_tree;
+ int id; /* must be able to accomodate millions of lights */
+ int child1;
+ int child2;
+ float intensity;
+ float min[3];
+ float max[3];
+} LightcutsCluster;
+
+typedef struct LightcutsClusterPair
+{
+ int first;
+ int second;
+} LightcutsClusterPair;
+
+#define VEC_LEN_SQ(v) (v[0]*v[0] + v[1]*v[1] + v[2]*v[2])
+
+static float lightcuts_compute_metric(LightcutsCluster * one, LightcutsCluster * two)
+{
+ /* 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->intensity + two->intensity) * VEC_LEN_SQ(diff);
+}
+
+static void add_new_cluster(LightcutsCluster * array, LightcutsClusterPair * minpair, int * root)
+{
+ 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;
+ dest->child1 = minpair->first;
+ dest->child2 = minpair->second;
+ dest->intensity = one->intensity + two->intensity;
+
+ /* 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);
+
+ (*root)++;
+}
+
+static void find_and_insert_new_min(Heap * heap, LightcutsCluster * array, LightcutsClusterPair * pair, int id, int from)
+{
+ LightcutsCluster * el = &array[id];
+ LightcutsCluster * el2;
+ float metric = LIGHTCUTS_MAX_METRIC + 1.0;
+ float pair_metric;
+ int other = -1;
+ int i;
+
+ for (i = from; i < LIGHTCUTS_MAX_LIGHTS * 2; 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)
+ {
+ metric = pair_metric;
+ other = i;
+ }
+ }
+
+ if (other != -1)
+ {
+ pair->first = id;
+ pair->second = other;
+
+ BLI_heap_insert(heap, metric, pair);
+ }
+}
+
+/* NOTE: conservative space estimation */
+/* TODO: dynamic allocation required of course */
+LightcutsCluster array_local[LIGHTCUTS_MAX_LIGHTS * 2];
+/* location of first empty slot */
+int free_local;
+/* id of root node */
+int root_local;
+/* TODO: equivalent data structures for sun and spot */
+
+static void lightcuts_fill_array(ListBase * pointlights)
+{
+ GroupObject *go;
+ LampRen *lar;
+ LightcutsCluster *clus = array_local;
+
+ /* TODO: check if not already filled in ? */
+ memset(array_local, 0, sizeof(LightcutsCluster) * (LIGHTCUTS_MAX_LIGHTS * 2));
+ free_local = 0;
+ root_local = 0;
+
+ for(go = pointlights->first; go; go = go->next) {
+ lar = go->lampren;
+ if (lar==NULL) continue;
+
+ if (lar->type!=LA_LOCAL)
+ continue;
+
+ clus->type = CLUSTER_LOCAL;
+ clus->in_tree = 0;
+ clus->id = free_local;
+ clus->intensity = lar->energy;
+ VECCOPY(clus->min, lar->co);
+ VECCOPY(clus->max, lar->co);
+
+ clus++;
+ free_local++;
+ }
+}
+
+static void debug_print_tree(int root_local, int lev)
+{
+ LightcutsCluster * el = &array_local[root_local];
+ int i;
+ for (i = 0; i < lev; i++)
+ printf("-");
+ printf(" id %d, int %f\n", el->id, el->intensity);
+
+ if (el->child1 == 0 && el->child2 == 0)
+ return;
+
+ debug_print_tree(el->child1, lev + 1);
+ debug_print_tree(el->child2, lev + 1);
+}
+
+static void lightcuts_build_tree()
+{
+ int i, cluster_id = 0;
+
+ Heap * heap = BLI_heap_new();
+ /* TODO: taylor size */
+ LightcutsClusterPair pair_array[LIGHTCUTS_MAX_LIGHTS];
+
+ for (i = 0; i < LIGHTCUTS_MAX_LIGHTS; i++)
+ {
+ if (array_local[i].type == CLUSTER_EMPTY)
+ break;
+
+ find_and_insert_new_min(heap, array_local, &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_local[minpair->first].in_tree;
+ short in_tree2 = array_local[minpair->second].in_tree;
+
+ if (in_tree1)
+ continue;
+
+ /* we look for another minimum */
+ if (in_tree2)
+ {
+ find_and_insert_new_min(heap, array_local, minpair, minpair->first, 0);
+ continue;
+ }
+
+ /* valid pair: build cluster out of it, mark children as used */
+ cluster_id = free_local;
+ add_new_cluster(array_local, minpair, &free_local);
+
+ /* new search, avoid considering in_tree children */
+ find_and_insert_new_min(heap, array_local, minpair, cluster_id, 0);
+ }
+
+ BLI_heap_free(heap, 0);
+
+ /* the last cluster added is the root of the tree */
+ root_local = cluster_id;
+
+ printf("Lightcuts tree built: %d\n", root_local);
+ debug_print_tree(root_local, 0);
+}
+
/*
* TODO: this is a temporary function, I need a proper initializer
* right now this code is partly copied from add_render_lamp()
@@ -58,10 +275,10 @@
else if (lar->type==LA_SPOT && (lar->mode & LA_SHAD_BUF) ) {
/* Per lamp, one shadow buffer is made. */
#if 0
-// TODO: matrix mat is not available here
+/* TODO: matrix mat is not available here */
lar->bufflag= la->bufflag;
Mat4CpyMat4(mat, ob->obmat);
- initshadowbuf(re, lar, mat); // mat is altered
+ initshadowbuf(re, lar, mat); /* mat is altered */
#endif
}
@@ -119,7 +336,7 @@
gonew->ob= 0;
gonew->recalc= go->recalc;
- if (lar->type!=LA_LOCAL && lar->type!=LA_SUN)
+ if (lar->type!=LA_LOCAL)
continue;
/* then create a new one */
@@ -160,6 +377,12 @@
BLI_addtail(&re->lampren, larnew);
gonew->lampren= larnew;
}
+
+ if (pointlights->first)
+ {
+ lightcuts_fill_array(pointlights);
+ lightcuts_build_tree();
+ }
}
/*
More information about the Bf-blender-cvs
mailing list