diff options
author | Germano Cavalcante <germano.costa@ig.com.br> | 2020-07-07 15:45:53 +0300 |
---|---|---|
committer | Germano Cavalcante <germano.costa@ig.com.br> | 2020-07-07 16:55:57 +0300 |
commit | 20558848d311ac0be35d01ab8331f1330a9ad450 (patch) | |
tree | 20bf6dc7e17a10df106fd7a3796ab870d3c0ad86 /source | |
parent | 630c6226e29444113950d1073175fdf1723fbe34 (diff) |
Optimization: use `BLI_bvhtree_intersect_plane` to detect faces that will be affected by the knife tool
The knife code currently calls the `BLI_bvhtree_overlap` function that
tests the overlap between the mesh tree and an AABB that encompasses the
points projected in the clip_start, clip_end and or clip_planes of the
view.
This resulted in many false positives since the AABB is very large.
Often all the triangles "overlapped".
The solution was to create a new function that actually tests the
intersection of AABB with a plane.
Even not considering the clip_planes of the view, this solution is more
appropriate than using overlap.
Differential Revision: https://developer.blender.org/D8229
Diffstat (limited to 'source')
-rw-r--r-- | source/blender/blenlib/BLI_kdopbvh.h | 2 | ||||
-rw-r--r-- | source/blender/blenlib/intern/BLI_kdopbvh.c | 71 | ||||
-rw-r--r-- | source/blender/editors/mesh/editmesh_knife.c | 32 |
3 files changed, 89 insertions, 16 deletions
diff --git a/source/blender/blenlib/BLI_kdopbvh.h b/source/blender/blenlib/BLI_kdopbvh.h index 70fa633eeac..9e4e30181b9 100644 --- a/source/blender/blenlib/BLI_kdopbvh.h +++ b/source/blender/blenlib/BLI_kdopbvh.h @@ -174,6 +174,8 @@ BVHTreeOverlap *BLI_bvhtree_overlap(const BVHTree *tree1, BVHTree_OverlapCallback callback, void *userdata); +int *BLI_bvhtree_intersect_plane(BVHTree *tree, float plane[4], uint *r_intersect_tot); + int BLI_bvhtree_get_len(const BVHTree *tree); int BLI_bvhtree_get_tree_type(const BVHTree *tree); float BLI_bvhtree_get_epsilon(const BVHTree *tree); diff --git a/source/blender/blenlib/intern/BLI_kdopbvh.c b/source/blender/blenlib/intern/BLI_kdopbvh.c index 0707e4c1d2a..e9946d81f75 100644 --- a/source/blender/blenlib/intern/BLI_kdopbvh.c +++ b/source/blender/blenlib/intern/BLI_kdopbvh.c @@ -169,6 +169,12 @@ typedef struct BVHNearestProjectedData { } BVHNearestProjectedData; +typedef struct BVHIntersectPlaneData { + const BVHTree *tree; + float plane[4]; + struct BLI_Stack *intersect; /* Store indexes. */ +} BVHIntersectPlaneData; + /** \} */ /** @@ -1393,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; + + BVHNode *root = tree->nodes[tree->totleaf]; + if (root != NULL) { + BVHIntersectPlaneData data; + data.tree = tree; + copy_v4_v4(data.plane, plane); + data.intersect = BLI_stack_new(sizeof(int), __func__); + + 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 * \{ */ diff --git a/source/blender/editors/mesh/editmesh_knife.c b/source/blender/editors/mesh/editmesh_knife.c index d95985a5515..ae407b7b84b 100644 --- a/source/blender/editors/mesh/editmesh_knife.c +++ b/source/blender/editors/mesh/editmesh_knife.c @@ -1548,8 +1548,8 @@ static void knife_find_line_hits(KnifeTool_OpData *kcd) { SmallHash faces, kfes, kfvs; float v1[3], v2[3], v3[3], v4[3], s1[2], s2[2]; - BVHTree *planetree, *tree; - BVHTreeOverlap *results, *result; + BVHTree *tree; + int *results, *result; BMLoop **ls; BMFace *f; KnifeEdge *kfe; @@ -1562,7 +1562,6 @@ static void knife_find_line_hits(KnifeTool_OpData *kcd) KnifeLineHit hit; void *val; void **val_p; - float plane_cos[12]; float s[2], se1[2], se2[2], sint[2]; float r1[3], r2[3]; float d, d1, d2, lambda; @@ -1623,22 +1622,24 @@ static void knife_find_line_hits(KnifeTool_OpData *kcd) clip_to_ortho_planes(v2, v4, kcd->ortho_extent_center, kcd->ortho_extent + 10.0f); } + float plane[4]; + { + float v1_v2[3], v1_v3[3]; + copy_v3_v3(v1, kcd->prev.cage); + copy_v3_v3(v2, kcd->curr.cage); + sub_v3_v3v3(v1_v2, v2, v1); + sub_v3_v3v3(v1_v3, v3, v1); + cross_v3_v3v3(plane, v1_v2, v1_v3); + plane_from_point_normal_v3(plane, v1, plane); + } + /* First use bvh tree to find faces, knife edges, and knife verts that might * intersect the cut plane with rays v1-v3 and v2-v4. * This deduplicates the candidates before doing more expensive intersection tests. */ tree = BKE_bmbvh_tree_get(kcd->bmbvh); - planetree = BLI_bvhtree_new(4, FLT_EPSILON * 4, 8, 8); - copy_v3_v3(plane_cos + 0, v1); - copy_v3_v3(plane_cos + 3, v2); - copy_v3_v3(plane_cos + 6, v3); - copy_v3_v3(plane_cos + 9, v4); - BLI_bvhtree_insert(planetree, 0, plane_cos, 4); - BLI_bvhtree_balance(planetree); - - results = BLI_bvhtree_overlap(tree, planetree, &tot, NULL, NULL); + results = BLI_bvhtree_intersect_plane(tree, plane, &tot); if (!results) { - BLI_bvhtree_free(planetree); return; } @@ -1647,9 +1648,9 @@ static void knife_find_line_hits(KnifeTool_OpData *kcd) BLI_smallhash_init(&kfvs); for (i = 0, result = results; i < tot; i++, result++) { - ls = (BMLoop **)kcd->em->looptris[result->indexA]; + ls = (BMLoop **)kcd->em->looptris[*result]; f = ls[0]->f; - set_lowest_face_tri(kcd, f, result->indexA); + set_lowest_face_tri(kcd, f, *result); /* occlude but never cut unselected faces (when only_select is used) */ if (kcd->only_select && !BM_elem_flag_test(f, BM_ELEM_SELECT)) { @@ -1834,7 +1835,6 @@ static void knife_find_line_hits(KnifeTool_OpData *kcd) BLI_smallhash_release(&faces); BLI_smallhash_release(&kfes); BLI_smallhash_release(&kfvs); - BLI_bvhtree_free(planetree); if (results) { MEM_freeN(results); } |