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