diff options
author | Matt Ebb <matt@mke3.net> | 2009-08-18 02:09:36 +0400 |
---|---|---|
committer | Matt Ebb <matt@mke3.net> | 2009-08-18 02:09:36 +0400 |
commit | 6412fe4b92f136fd7b9bdb7592476df26c8e46ce (patch) | |
tree | 9f7d0e3afdd19bef37a5c431e02b9c6c89d3c160 /source/blender/blenlib/intern | |
parent | fe984a6e6ca9de9cb358fea0f4f3cf42742a1667 (diff) |
* Point density texture works again
Diffstat (limited to 'source/blender/blenlib/intern')
-rw-r--r-- | source/blender/blenlib/intern/BLI_kdopbvh.c | 188 |
1 files changed, 94 insertions, 94 deletions
diff --git a/source/blender/blenlib/intern/BLI_kdopbvh.c b/source/blender/blenlib/intern/BLI_kdopbvh.c index 014c3d52cda..08e8a5871cd 100644 --- a/source/blender/blenlib/intern/BLI_kdopbvh.c +++ b/source/blender/blenlib/intern/BLI_kdopbvh.c @@ -72,10 +72,10 @@ struct BVHTree char start_axis, stop_axis; // KDOP_AXES array indices according to axis }; -typedef struct BVHOverlapData -{ - BVHTree *tree1, *tree2; - BVHTreeOverlap *overlap; +typedef struct BVHOverlapData +{ + BVHTree *tree1, *tree2; + BVHTreeOverlap *overlap; int i, max_overlap; /* i is number of overlaps */ int start_axis, stop_axis; } BVHOverlapData; @@ -109,7 +109,7 @@ typedef struct BVHRayCastData //////////////////////////////////////////////////////////////////////// // Bounding Volume Hierarchy Definition -// +// // Notes: From OBB until 26-DOP --> all bounding volumes possible, just choose type below // Notes: You have to choose the type at compile time ITM // Notes: You can choose the tree type --> binary, quad, octree, choose below @@ -188,10 +188,10 @@ int ADJUST_MEMORY(void *local_memblock, void **memblock, int new_size, int *max_ ////////////////////////////////////////////////////////////////////////////////////////////////////// -// Introsort +// Introsort // with permission deriven from the following Java code: // http://ralphunden.net/content/tutorials/a-guide-to-introsort/ -// and he derived it from the SUN STL +// and he derived it from the SUN STL ////////////////////////////////////////////////////////////////////////////////////////////////////// static int size_threshold = 16; /* @@ -362,7 +362,7 @@ static void create_kdop_hull(BVHTree *tree, BVHNode *node, float *co, int numpoi float newminmax; float *bv = node->bv; int i, k; - + // don't init boudings for the moving case if(!moving) { @@ -372,7 +372,7 @@ static void create_kdop_hull(BVHTree *tree, BVHNode *node, float *co, int numpoi bv[2*i + 1] = -FLT_MAX; } } - + for(k = 0; k < numpoints; k++) { // for all Axes. @@ -394,7 +394,7 @@ static void refit_kdop_hull(BVHTree *tree, BVHNode *node, int start, int end) int i, j; float *bv = node->bv; - + for (i = tree->start_axis; i < tree->stop_axis; i++) { bv[2*i] = FLT_MAX; @@ -406,10 +406,10 @@ static void refit_kdop_hull(BVHTree *tree, BVHNode *node, int start, int end) // for all Axes. for (i = tree->start_axis; i < tree->stop_axis; i++) { - newmin = tree->nodes[j]->bv[(2 * i)]; + newmin = tree->nodes[j]->bv[(2 * i)]; if ((newmin < bv[(2 * i)])) bv[(2 * i)] = newmin; - + newmax = tree->nodes[j]->bv[(2 * i) + 1]; if ((newmax > bv[(2 * i) + 1])) bv[(2 * i) + 1] = newmax; @@ -427,14 +427,14 @@ static char get_largest_axis(float *bv) middle_point[0] = (bv[1]) - (bv[0]); // x axis middle_point[1] = (bv[3]) - (bv[2]); // y axis middle_point[2] = (bv[5]) - (bv[4]); // z axis - if (middle_point[0] > middle_point[1]) + if (middle_point[0] > middle_point[1]) { if (middle_point[0] > middle_point[2]) return 1; // max x axis else return 5; // max z axis } - else + else { if (middle_point[1] > middle_point[2]) return 3; // max y axis @@ -448,24 +448,24 @@ static char get_largest_axis(float *bv) static void node_join(BVHTree *tree, BVHNode *node) { int i, j; - + for (i = tree->start_axis; i < tree->stop_axis; i++) { node->bv[2*i] = FLT_MAX; node->bv[2*i + 1] = -FLT_MAX; } - + for (i = 0; i < tree->tree_type; i++) { - if (node->children[i]) + if (node->children[i]) { for (j = tree->start_axis; j < tree->stop_axis; j++) { - // update minimum - if (node->children[i]->bv[(2 * j)] < node->bv[(2 * j)]) + // update minimum + if (node->children[i]->bv[(2 * j)] < node->bv[(2 * j)]) node->bv[(2 * j)] = node->children[i]->bv[(2 * j)]; - - // update maximum + + // update maximum if (node->children[i]->bv[(2 * j) + 1] > node->bv[(2 * j) + 1]) node->bv[(2 * j) + 1] = node->children[i]->bv[(2 * j) + 1]; } @@ -518,7 +518,7 @@ static void bvhtree_info(BVHTree *tree) static void verify_tree(BVHTree *tree) { int i, j, check = 0; - + // check the pointer list for(i = 0; i < tree->totleaf; i++) { @@ -538,7 +538,7 @@ static void verify_tree(BVHTree *tree) check = 0; } } - + // check the leaf list for(i = 0; i < tree->totleaf; i++) { @@ -558,7 +558,7 @@ static void verify_tree(BVHTree *tree) check = 0; } } - + printf("branches: %d, leafs: %d, total: %d\n", tree->totbranch, tree->totleaf, tree->totbranch + tree->totleaf); } #endif @@ -703,7 +703,7 @@ static void non_recursive_bvh_div_nodes(BVHTree *tree, BVHNode *branches_array, BVHBuildHelper data; int depth; - + // set parent from root node to NULL BVHNode *tmp = branches_array+0; tmp->parent = NULL; @@ -722,7 +722,7 @@ static void non_recursive_bvh_div_nodes(BVHTree *tree, BVHNode *branches_array, } branches_array--; //Implicit trees use 1-based indexs - + build_implicit_tree_helper(tree, &data); //Loop tree levels (log N) loops @@ -806,11 +806,11 @@ BVHTree *BLI_bvhtree_new(int maxsize, float epsilon, char tree_type, char axis) { BVHTree *tree; int numnodes, i; - + // theres not support for trees below binary-trees :P if(tree_type < 2) return NULL; - + if(tree_type > MAX_TREETYPE) return NULL; @@ -820,13 +820,13 @@ BVHTree *BLI_bvhtree_new(int maxsize, float epsilon, char tree_type, char axis) //so that tangent rays can still hit a bounding volume.. //this bug would show up when casting a ray aligned with a kdop-axis and with an edge of 2 faces epsilon = MAX2(FLT_EPSILON, epsilon); - + if(tree) { tree->epsilon = epsilon; - tree->tree_type = tree_type; + tree->tree_type = tree_type; tree->axis = axis; - + if(axis == 26) { tree->start_axis = 0; @@ -863,13 +863,13 @@ BVHTree *BLI_bvhtree_new(int maxsize, float epsilon, char tree_type, char axis) numnodes = maxsize + implicit_needed_branches(tree_type, maxsize) + tree_type; tree->nodes = (BVHNode **)MEM_callocN(sizeof(BVHNode *)*numnodes, "BVHNodes"); - + if(!tree->nodes) { MEM_freeN(tree); return NULL; } - + tree->nodebv = (float*)MEM_callocN(sizeof(float)* axis * numnodes, "BVHNodeBV"); if(!tree->nodebv) { @@ -886,7 +886,7 @@ BVHTree *BLI_bvhtree_new(int maxsize, float epsilon, char tree_type, char axis) } tree->nodearray = (BVHNode *)MEM_callocN(sizeof(BVHNode)* numnodes, "BVHNodeArray"); - + if(!tree->nodearray) { MEM_freeN(tree->nodechild); @@ -902,14 +902,14 @@ BVHTree *BLI_bvhtree_new(int maxsize, float epsilon, char tree_type, char axis) tree->nodearray[i].bv = tree->nodebv + i * axis; tree->nodearray[i].children = tree->nodechild + i * tree_type; } - + } return tree; } void BLI_bvhtree_free(BVHTree *tree) -{ +{ if(tree) { MEM_freeN(tree->nodes); @@ -946,27 +946,27 @@ int BLI_bvhtree_insert(BVHTree *tree, int index, float *co, int numpoints) { int i; BVHNode *node = NULL; - + // insert should only possible as long as tree->totbranch is 0 if(tree->totbranch > 0) return 0; - + if(tree->totleaf+1 >= MEM_allocN_len(tree->nodes)/sizeof(*(tree->nodes))) return 0; - + // TODO check if have enough nodes in array - + node = tree->nodes[tree->totleaf] = &(tree->nodearray[tree->totleaf]); tree->totleaf++; - + create_kdop_hull(tree, node, co, numpoints, 0); node->index= index; - + // inflate the bv with some epsilon for (i = tree->start_axis; i < tree->stop_axis; i++) { - node->bv[(2 * i)] -= tree->epsilon; // minimum - node->bv[(2 * i) + 1] += tree->epsilon; // maximum + node->bv[(2 * i)] -= tree->epsilon; // minimum + node->bv[(2 * i) + 1] += tree->epsilon; // maximum } return 1; @@ -978,23 +978,23 @@ int BLI_bvhtree_update_node(BVHTree *tree, int index, float *co, float *co_movin { int i; BVHNode *node= NULL; - + // check if index exists if(index > tree->totleaf) return 0; - + node = tree->nodearray + index; - + create_kdop_hull(tree, node, co, numpoints, 0); - + if(co_moving) create_kdop_hull(tree, node, co_moving, numpoints, 1); - + // inflate the bv with some epsilon for (i = tree->start_axis; i < tree->stop_axis; i++) { - node->bv[(2 * i)] -= tree->epsilon; // minimum - node->bv[(2 * i) + 1] += tree->epsilon; // maximum + node->bv[(2 * i)] -= tree->epsilon; // minimum + node->bv[(2 * i) + 1] += tree->epsilon; // maximum } return 1; @@ -1030,24 +1030,24 @@ static int tree_overlap(BVHNode *node1, BVHNode *node2, int start_axis, int stop float *bv2 = node2->bv; float *bv1_end = bv1 + (stop_axis<<1); - + bv1 += start_axis<<1; bv2 += start_axis<<1; - + // test all axis if min + max overlap for (; bv1 != bv1_end; bv1+=2, bv2+=2) { - if ((*(bv1) > *(bv2 + 1)) || (*(bv2) > *(bv1 + 1))) + if ((*(bv1) > *(bv2 + 1)) || (*(bv2) > *(bv1 + 1))) return 0; } - + return 1; } static void traverse(BVHOverlapData *data, BVHNode *node1, BVHNode *node2) { int j; - + if(tree_overlap(node1, node2, data->start_axis, data->stop_axis)) { // check if node1 is a leaf @@ -1056,17 +1056,17 @@ static void traverse(BVHOverlapData *data, BVHNode *node1, BVHNode *node2) // check if node2 is a leaf if(!node2->totnode) { - + if(node1 == node2) { return; } - + if(data->i >= data->max_overlap) - { + { // try to make alloc'ed memory bigger data->overlap = realloc(data->overlap, sizeof(BVHTreeOverlap)*data->max_overlap*2); - + if(!data->overlap) { printf("Out of Memory in traverse\n"); @@ -1074,7 +1074,7 @@ static void traverse(BVHOverlapData *data, BVHNode *node1, BVHNode *node2) } data->max_overlap *= 2; } - + // both leafs, insert overlap! data->overlap[data->i].indexA = node1->index; data->overlap[data->i].indexB = node2->index; @@ -1092,7 +1092,7 @@ static void traverse(BVHOverlapData *data, BVHNode *node1, BVHNode *node2) } else { - + for(j = 0; j < data->tree2->tree_type; j++) { if(node1->children[j]) @@ -1108,21 +1108,21 @@ BVHTreeOverlap *BLI_bvhtree_overlap(BVHTree *tree1, BVHTree *tree2, int *result) int j, total = 0; BVHTreeOverlap *overlap = NULL, *to = NULL; BVHOverlapData **data; - + // check for compatibility of both trees (can't compare 14-DOP with 18-DOP) if((tree1->axis != tree2->axis) && (tree1->axis == 14 || tree2->axis == 14) && (tree1->axis == 18 || tree2->axis == 18)) return 0; - + // fast check root nodes for collision before doing big splitting + traversal if(!tree_overlap(tree1->nodes[tree1->totleaf], tree2->nodes[tree2->totleaf], MIN2(tree1->start_axis, tree2->start_axis), MIN2(tree1->stop_axis, tree2->stop_axis))) return 0; data = MEM_callocN(sizeof(BVHOverlapData *)* tree1->tree_type, "BVHOverlapData_star"); - + for(j = 0; j < tree1->tree_type; j++) { data[j] = (BVHOverlapData *)MEM_callocN(sizeof(BVHOverlapData), "BVHOverlapData"); - + // init BVHOverlapData data[j]->overlap = (BVHTreeOverlap *)malloc(sizeof(BVHTreeOverlap)*MAX2(tree1->totleaf, tree2->totleaf)); data[j]->tree1 = tree1; @@ -1138,25 +1138,25 @@ BVHTreeOverlap *BLI_bvhtree_overlap(BVHTree *tree1, BVHTree *tree2, int *result) { traverse(data[j], tree1->nodes[tree1->totleaf]->children[j], tree2->nodes[tree2->totleaf]); } - + for(j = 0; j < tree1->tree_type; j++) total += data[j]->i; - + to = overlap = (BVHTreeOverlap *)MEM_callocN(sizeof(BVHTreeOverlap)*total, "BVHTreeOverlap"); - + for(j = 0; j < tree1->tree_type; j++) { memcpy(to, data[j]->overlap, data[j]->i*sizeof(BVHTreeOverlap)); to+=data[j]->i; } - + for(j = 0; j < tree1->tree_type; j++) { free(data[j]->overlap); MEM_freeN(data[j]); } MEM_freeN(data); - + (*result) = total; return overlap; } @@ -1173,7 +1173,7 @@ static float squared_dist(const float *a, const float *b) } //Determines the nearest point of the given node BV. Returns the squared distance to that point. -static float calc_nearest_point(BVHNearestData *data, BVHNode *node, float *nearest) +static float calc_nearest_point(const float *proj, BVHNode *node, float *nearest) { int i; const float *bv = node->bv; @@ -1181,12 +1181,12 @@ static float calc_nearest_point(BVHNearestData *data, BVHNode *node, float *near //nearest on AABB hull for(i=0; i != 3; i++, bv += 2) { - if(bv[0] > data->proj[i]) + if(bv[0] > proj[i]) nearest[i] = bv[0]; - else if(bv[1] < data->proj[i]) + else if(bv[1] < proj[i]) nearest[i] = bv[1]; else - nearest[i] = data->proj[i]; + nearest[i] = proj[i]; } /* @@ -1208,7 +1208,7 @@ static float calc_nearest_point(BVHNearestData *data, BVHNode *node, float *near } } */ - return squared_dist(data->co, nearest); + return squared_dist(proj, nearest); } @@ -1231,7 +1231,7 @@ static void dfs_find_nearest_dfs(BVHNearestData *data, BVHNode *node) else { data->nearest.index = node->index; - data->nearest.dist = calc_nearest_point(data, node, data->nearest.co); + data->nearest.dist = calc_nearest_point(data->proj, node, data->nearest.co); } } else @@ -1240,12 +1240,12 @@ static void dfs_find_nearest_dfs(BVHNearestData *data, BVHNode *node) int i; float nearest[3]; - if(data->proj[ (int)node->main_axis ] <= node->children[0]->bv[(int)node->main_axis*2+1]) + if(data->proj[ node->main_axis ] <= node->children[0]->bv[node->main_axis*2+1]) { for(i=0; i != node->totnode; i++) { - if( calc_nearest_point(data, node->children[i], nearest) >= data->nearest.dist) continue; + if( calc_nearest_point(data->proj, node->children[i], nearest) >= data->nearest.dist) continue; dfs_find_nearest_dfs(data, node->children[i]); } } @@ -1253,7 +1253,7 @@ static void dfs_find_nearest_dfs(BVHNearestData *data, BVHNode *node) { for(i=node->totnode-1; i >= 0 ; i--) { - if( calc_nearest_point(data, node->children[i], nearest) >= data->nearest.dist) continue; + if( calc_nearest_point(data->proj, node->children[i], nearest) >= data->nearest.dist) continue; dfs_find_nearest_dfs(data, node->children[i]); } } @@ -1263,7 +1263,7 @@ static void dfs_find_nearest_dfs(BVHNearestData *data, BVHNode *node) static void dfs_find_nearest_begin(BVHNearestData *data, BVHNode *node) { float nearest[3], sdist; - sdist = calc_nearest_point(data, node, nearest); + sdist = calc_nearest_point(data->proj, node, nearest); if(sdist >= data->nearest.dist) return; dfs_find_nearest_dfs(data, node); } @@ -1301,7 +1301,7 @@ static void bfs_find_nearest(BVHNearestData *data, BVHNode *node) } current.node = node; - current.dist = calc_nearest_point(data, node, nearest); + current.dist = calc_nearest_point(data->proj, node, nearest); while(current.dist < data->nearest.dist) { @@ -1329,7 +1329,7 @@ static void bfs_find_nearest(BVHNearestData *data, BVHNode *node) } heap[heap_size].node = current.node->children[i]; - heap[heap_size].dist = calc_nearest_point(data, current.node->children[i], nearest); + heap[heap_size].dist = calc_nearest_point(data->proj, current.node->children[i], nearest); if(heap[heap_size].dist >= data->nearest.dist) continue; heap_size++; @@ -1339,7 +1339,7 @@ static void bfs_find_nearest(BVHNearestData *data, BVHNode *node) push_heaps++; } } - + if(heap_size == 0) break; current = heap[0]; @@ -1355,6 +1355,7 @@ static void bfs_find_nearest(BVHNearestData *data, BVHNode *node) } #endif + int BLI_bvhtree_find_nearest(BVHTree *tree, const float *co, BVHTreeNearest *nearest, BVHTree_NearestPointCallback callback, void *userdata) { int i; @@ -1435,7 +1436,7 @@ static float ray_nearest_hit(BVHRayCastData *data, float *bv) if(lu > low) low = lu; if(ll < upper) upper = ll; } - + if(low > upper) return FLT_MAX; } } @@ -1530,32 +1531,31 @@ float BLI_bvhtree_bb_raycast(float *bv, float *light_start, float *light_end, fl { BVHRayCastData data; float dist = 0.0; - int i; - + data.hit.dist = FLT_MAX; - + // get light direction data.ray.direction[0] = light_end[0] - light_start[0]; data.ray.direction[1] = light_end[1] - light_start[1]; data.ray.direction[2] = light_end[2] - light_start[2]; - + data.ray.radius = 0.0; - + data.ray.origin[0] = light_start[0]; data.ray.origin[1] = light_start[1]; data.ray.origin[2] = light_start[2]; - + Normalize(data.ray.direction); VECCOPY(data.ray_dot_axis, data.ray.direction); - + dist = ray_nearest_hit(&data, bv); - + if(dist > 0.0) { VECADDFAC(pos, light_start, data.ray.direction, dist); } return dist; - + } /* |