From 58c88bcf7636abce291168af189284181f2f7033 Mon Sep 17 00:00:00 2001 From: Daniel Genrich Date: Thu, 30 Jul 2009 15:00:26 +0000 Subject: BF2.5: First commit of smoke code. Not working: a) rendering (since volumterics branch is not merged yet) b) moving collision objects of any kind c) saving of collision objects (because that's what I am working on) d) pointcache e) A bunch of other things I already know of So please do not report any bugs on this one yet :-) --- source/blender/blenlib/BLI_kdopbvh.h | 2 + source/blender/blenlib/intern/BLI_kdopbvh.c | 183 ++++++++++++++++------------ 2 files changed, 109 insertions(+), 76 deletions(-) (limited to 'source/blender/blenlib') diff --git a/source/blender/blenlib/BLI_kdopbvh.h b/source/blender/blenlib/BLI_kdopbvh.h index e3591a84e98..50462d531ef 100644 --- a/source/blender/blenlib/BLI_kdopbvh.h +++ b/source/blender/blenlib/BLI_kdopbvh.h @@ -93,5 +93,7 @@ int BLI_bvhtree_find_nearest(BVHTree *tree, const float *co, BVHTreeNearest *nea int BLI_bvhtree_ray_cast(BVHTree *tree, const float *co, const float *dir, float radius, BVHTreeRayHit *hit, BVHTree_RayCastCallback callback, void *userdata); +float BLI_bvhtree_bb_raycast(float *bv, float *light_start, float *light_end, float *pos); + #endif // BLI_KDOPBVH_H diff --git a/source/blender/blenlib/intern/BLI_kdopbvh.c b/source/blender/blenlib/intern/BLI_kdopbvh.c index 0f8194362c9..84de9f9d862 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; } @@ -1339,7 +1339,7 @@ static void bfs_find_nearest(BVHNearestData *data, BVHNode *node) push_heaps++; } } - + if(heap_size == 0) break; current = heap[0]; @@ -1405,10 +1405,9 @@ int BLI_bvhtree_find_nearest(BVHTree *tree, const float *co, BVHTreeNearest *nea */ //Determines the distance that the ray must travel to hit the bounding volume of the given node -static float ray_nearest_hit(BVHRayCastData *data, BVHNode *node) +static float ray_nearest_hit(BVHRayCastData *data, float *bv) { int i; - const float *bv = node->bv; float low = 0, upper = data->hit.dist; @@ -1436,7 +1435,7 @@ static float ray_nearest_hit(BVHRayCastData *data, BVHNode *node) if(lu > low) low = lu; if(ll < upper) upper = ll; } - + if(low > upper) return FLT_MAX; } } @@ -1449,7 +1448,7 @@ static void dfs_raycast(BVHRayCastData *data, BVHNode *node) //ray-bv is really fast.. and simple tests revealed its worth to test it //before calling the ray-primitive functions - float dist = ray_nearest_hit(data, node); + float dist = ray_nearest_hit(data, node->bv); if(dist >= data->hit.dist) return; if(node->totnode == 0) @@ -1527,3 +1526,35 @@ int BLI_bvhtree_ray_cast(BVHTree *tree, const float *co, const float *dir, float return data.hit.index; } +float BLI_bvhtree_bb_raycast(float *bv, float *light_start, float *light_end, float *pos) +{ + 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; + +} + -- cgit v1.2.3