diff options
Diffstat (limited to 'source/blender/blenlib/intern/BLI_kdopbvh.c')
-rw-r--r-- | source/blender/blenlib/intern/BLI_kdopbvh.c | 60 |
1 files changed, 30 insertions, 30 deletions
diff --git a/source/blender/blenlib/intern/BLI_kdopbvh.c b/source/blender/blenlib/intern/BLI_kdopbvh.c index 027c6e084f5..1676bf5d779 100644 --- a/source/blender/blenlib/intern/BLI_kdopbvh.c +++ b/source/blender/blenlib/intern/BLI_kdopbvh.c @@ -458,10 +458,10 @@ static void partition_nth_element(BVHNode **a, int begin, int end, const int n, static void build_skip_links(BVHTree *tree, BVHNode *node, BVHNode *left, BVHNode *right) { int i; - + node->skip[0] = left; node->skip[1] = right; - + for (i = 0; i < node->totnode; i++) { if (i + 1 < node->totnode) build_skip_links(tree, node->children[i], left, node->children[i + 1]); @@ -482,7 +482,7 @@ static void create_kdop_hull(const BVHTree *tree, BVHNode *node, const float *co float *bv = node->bv; int k; axis_t axis_iter; - + /* don't init boudings for the moving case */ if (!moving) { node_minmax_init(tree, node); @@ -560,7 +560,7 @@ static void node_join(BVHTree *tree, BVHNode *node) axis_t axis_iter; node_minmax_init(tree, node); - + for (i = 0; i < tree->tree_type; i++) { if (node->children[i]) { for (axis_iter = tree->start_axis; axis_iter < tree->stop_axis; axis_iter++) { @@ -631,7 +631,7 @@ static void bvhtree_info(BVHTree *tree) static void bvhtree_verify(BVHTree *tree) { int i, j, check = 0; - + /* check the pointer list */ for (i = 0; i < tree->totleaf; i++) { if (tree->nodes[i]->parent == NULL) { @@ -648,7 +648,7 @@ static void bvhtree_verify(BVHTree *tree) check = 0; } } - + /* check the leaf list */ for (i = 0; i < tree->totleaf; i++) { if (tree->nodearray[i].parent == NULL) { @@ -665,7 +665,7 @@ static void bvhtree_verify(BVHTree *tree) check = 0; } } - + printf("branches: %d, leafs: %d, total: %d\n", tree->totbranch, tree->totleaf, tree->totbranch + tree->totleaf); } @@ -1008,7 +1008,7 @@ BVHTree *BLI_bvhtree_new(int maxsize, float epsilon, char tree_type, char axis) tree->nodebv = MEM_callocN(sizeof(float) * (size_t)(axis * numnodes), "BVHNodeBV"); tree->nodechild = MEM_callocN(sizeof(BVHNode *) * (size_t)(tree_type * numnodes), "BVHNodeBV"); tree->nodearray = MEM_callocN(sizeof(BVHNode) * (size_t)numnodes, "BVHNodeArray"); - + if (UNLIKELY((!tree->nodes) || (!tree->nodebv) || (!tree->nodechild) || @@ -1022,7 +1022,7 @@ 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; @@ -1108,18 +1108,18 @@ bool BLI_bvhtree_update_node(BVHTree *tree, int index, const float co[3], const { BVHNode *node = NULL; axis_t axis_iter; - + /* check if index exists */ if (index > tree->totleaf) return false; - + 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 (axis_iter = tree->start_axis; axis_iter < tree->stop_axis; axis_iter++) { node->bv[(2 * axis_iter)] -= tree->epsilon; /* minimum */ @@ -1180,7 +1180,7 @@ static bool tree_overlap_test(const BVHNode *node1, const BVHNode *node2, axis_t const float *bv1 = node1->bv + (start_axis << 1); const float *bv2 = node2->bv + (start_axis << 1); const float *bv1_end = node1->bv + (stop_axis << 1); - + /* test all axis if min + max overlap */ for (; bv1 != bv1_end; bv1 += 2, bv2 += 2) { if ((bv1[0] > bv2[1]) || (bv2[0] > bv1[1])) { @@ -1321,7 +1321,7 @@ BVHTreeOverlap *BLI_bvhtree_overlap( BVHOverlapData_Shared data_shared; BVHOverlapData_Thread *data = BLI_array_alloca(data, (size_t)thread_num); axis_t start_axis, stop_axis; - + /* check for compatibility of both trees (can't compare 14-DOP with 18-DOP) */ if (UNLIKELY((tree1->axis != tree2->axis) && (tree1->axis == 14 || tree2->axis == 14) && @@ -1333,7 +1333,7 @@ BVHTreeOverlap *BLI_bvhtree_overlap( start_axis = min_axis(tree1->start_axis, tree2->start_axis); stop_axis = min_axis(tree1->stop_axis, tree2->stop_axis); - + /* fast check root nodes for collision before doing big splitting + traversal */ if (!tree_overlap_test(tree1->nodes[tree1->totleaf], tree2->nodes[tree2->totleaf], start_axis, stop_axis)) { return NULL; @@ -1365,12 +1365,12 @@ BVHTreeOverlap *BLI_bvhtree_overlap( data, bvhtree_overlap_task_cb, &settings); - + for (j = 0; j < thread_num; j++) total += BLI_stack_count(data[j].overlap); - + to = overlap = MEM_mallocN(sizeof(BVHTreeOverlap) * total, "BVHTreeOverlap"); - + for (j = 0; j < thread_num; j++) { uint count = (uint)BLI_stack_count(data[j].overlap); BLI_stack_pop_n(data[j].overlap, to, count); @@ -1403,7 +1403,7 @@ static float calc_nearest_point_squared(const float proj[3], BVHNode *node, floa else if (bv[1] < proj[i]) nearest[i] = bv[1]; else - nearest[i] = proj[i]; + nearest[i] = proj[i]; } #if 0 @@ -1548,7 +1548,7 @@ static void bfs_find_nearest(BVHNearestData *data, BVHNode *node) push_heaps++; } } - + if (heap_size == 0) break; current = heap[0]; @@ -1645,7 +1645,7 @@ static float ray_nearest_hit(const BVHRayCastData *data, const float bv[6]) if (lu > low) low = lu; if (ll < upper) upper = ll; } - + if (low > upper) return FLT_MAX; } } @@ -1661,7 +1661,7 @@ static float ray_nearest_hit(const BVHRayCastData *data, const float bv[6]) static float fast_ray_nearest_hit(const BVHRayCastData *data, const BVHNode *node) { const float *bv = node->bv; - + float t1x = (bv[data->index[0]] - data->ray.origin[0]) * data->idot_axis[0]; float t2x = (bv[data->index[1]] - data->ray.origin[0]) * data->idot_axis[0]; float t1y = (bv[data->index[2]] - data->ray.origin[1]) * data->idot_axis[1]; @@ -1773,7 +1773,7 @@ static void iterative_raycast(BVHRayCastData *data, BVHNode *node) data->hit.dist = dist; madd_v3_v3v3fl(data->hit.co, data->ray.origin, data->ray.direction, dist); } - + node = node->skip[1]; } else { @@ -1867,23 +1867,23 @@ float BLI_bvhtree_bb_raycast(const float bv[6], const float light_start[3], cons float dist; data.hit.dist = BVH_RAYCAST_DIST_MAX; - + /* get light direction */ sub_v3_v3v3(data.ray.direction, light_end, light_start); - + data.ray.radius = 0.0; - + copy_v3_v3(data.ray.origin, light_start); normalize_v3(data.ray.direction); copy_v3_v3(data.ray_dot_axis, data.ray.direction); - + dist = ray_nearest_hit(&data, bv); madd_v3_v3v3fl(pos, light_start, data.ray.direction, dist); return dist; - + } /** |