diff options
Diffstat (limited to 'source/blender/blenlib/intern/BLI_kdopbvh.c')
| -rw-r--r-- | source/blender/blenlib/intern/BLI_kdopbvh.c | 89 |
1 files changed, 81 insertions, 8 deletions
diff --git a/source/blender/blenlib/intern/BLI_kdopbvh.c b/source/blender/blenlib/intern/BLI_kdopbvh.c index da67baf0ead..a3f93ccc753 100644 --- a/source/blender/blenlib/intern/BLI_kdopbvh.c +++ b/source/blender/blenlib/intern/BLI_kdopbvh.c @@ -94,7 +94,7 @@ typedef struct BVHNode { struct BVHTree { BVHNode **nodes; BVHNode *nodearray; /* pre-alloc branch nodes */ - BVHNode **nodechild; /* pre-alloc childs for nodes */ + BVHNode **nodechild; /* pre-alloc children for nodes */ float *nodebv; /* pre-alloc bounding-volumes for nodes */ float epsilon; /* epslion is used for inflation of the k-dop */ int totleaf; /* leafs */ @@ -169,6 +169,12 @@ typedef struct BVHNearestProjectedData { } BVHNearestProjectedData; +typedef struct BVHIntersectPlaneData { + const BVHTree *tree; + float plane[4]; + struct BLI_Stack *intersect; /* Store indexes. */ +} BVHIntersectPlaneData; + /** \} */ /** @@ -769,7 +775,7 @@ static void non_recursive_bvh_div_nodes_task_cb(void *__restrict userdata, * This functions builds an optimal implicit tree from the given leafs. * Where optimal stands for: * - The resulting tree will have the smallest number of branches; - * - At most only one branch will have NULL childs; + * - At most only one branch will have NULL children; * - All leafs will be stored at level N or N+1. * * This function creates an implicit tree on branches_array, @@ -777,7 +783,7 @@ static void non_recursive_bvh_div_nodes_task_cb(void *__restrict userdata, * * The tree is built per depth levels. First branches at depth 1.. then branches at depth 2.. etc.. * The reason is that we can build level N+1 from level N without any data dependencies.. - * thus it allows to use multithread building. + * thus it allows to use multi-thread building. * * To archive this is necessary to find how much leafs are accessible from a certain branch, * #BVHBuildHelper, #implicit_needed_branches and #implicit_leafs_index @@ -1032,12 +1038,14 @@ bool BLI_bvhtree_update_node( return true; } -/* call BLI_bvhtree_update_node() first for every node/point/triangle */ +/** + * Call #BLI_bvhtree_update_node() first for every node/point/triangle. + */ void BLI_bvhtree_update_tree(BVHTree *tree) { /* Update bottom=>top - * TRICKY: the way we build the tree all the childs have an index greater than the parent - * This allows us todo a bottom up update by starting on the bigger numbered branch */ + * TRICKY: the way we build the tree all the children have an index greater than the parent + * This allows us todo a bottom up update by starting on the bigger numbered branch. */ BVHNode **root = tree->nodes + tree->totleaf; BVHNode **index = tree->nodes + tree->totleaf + tree->totbranch - 1; @@ -1391,6 +1399,71 @@ BVHTreeOverlap *BLI_bvhtree_overlap( /** \} */ /* -------------------------------------------------------------------- */ +/** \name BLI_bvhtree_intersect_plane + * \{ */ + +static bool tree_intersect_plane_test(const float *bv, const float plane[4]) +{ + /* TODO(germano): Support other kdop geometries. */ + const float bb_min[3] = {bv[0], bv[2], bv[4]}; + const float bb_max[3] = {bv[1], bv[3], bv[5]}; + float bb_near[3], bb_far[3]; + aabb_get_near_far_from_plane(plane, bb_min, bb_max, bb_near, bb_far); + if ((plane_point_side_v3(plane, bb_near) > 0.0f) != + (plane_point_side_v3(plane, bb_far) > 0.0f)) { + return true; + } + + return false; +} + +static void bvhtree_intersect_plane_dfs_recursive(BVHIntersectPlaneData *__restrict data, + const BVHNode *node) +{ + if (tree_intersect_plane_test(node->bv, data->plane)) { + /* check if node is a leaf */ + if (!node->totnode) { + int *intersect = BLI_stack_push_r(data->intersect); + *intersect = node->index; + } + else { + for (int j = 0; j < data->tree->tree_type; j++) { + if (node->children[j]) { + bvhtree_intersect_plane_dfs_recursive(data, node->children[j]); + } + } + } + } +} + +int *BLI_bvhtree_intersect_plane(BVHTree *tree, float plane[4], uint *r_intersect_tot) +{ + int *intersect = NULL; + size_t total = 0; + + if (tree->totleaf) { + BVHIntersectPlaneData data; + data.tree = tree; + copy_v4_v4(data.plane, plane); + data.intersect = BLI_stack_new(sizeof(int), __func__); + + BVHNode *root = tree->nodes[tree->totleaf]; + bvhtree_intersect_plane_dfs_recursive(&data, root); + + total = BLI_stack_count(data.intersect); + if (total) { + intersect = MEM_mallocN(sizeof(int) * total, __func__); + BLI_stack_pop_n(data.intersect, intersect, (uint)total); + } + BLI_stack_free(data.intersect); + } + *r_intersect_tot = (uint)total; + return intersect; +} + +/** \} */ + +/* -------------------------------------------------------------------- */ /** \name BLI_bvhtree_find_nearest * \{ */ @@ -2309,7 +2382,7 @@ static bool bvhtree_walk_dfs_recursive(BVHTree_WalkData *walk_data, const BVHNod } /** - * This is a generic function to perform a depth first search on the BVHTree + * This is a generic function to perform a depth first search on the #BVHTree * where the search order and nodes traversed depend on callbacks passed in. * * \param tree: Tree to walk. @@ -2317,7 +2390,7 @@ static bool bvhtree_walk_dfs_recursive(BVHTree_WalkData *walk_data, const BVHNod * \param walk_leaf_cb: Callback to test leaf nodes, callback must store its own result, * returning false exits early. * \param walk_order_cb: Callback that indicates which direction to search, - * either from the node with the lower or higher k-dop axis value. + * either from the node with the lower or higher K-DOP axis value. * \param userdata: Argument passed to all callbacks. */ void BLI_bvhtree_walk_dfs(BVHTree *tree, |