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