diff options
author | Henrik Dick <weasel> | 2020-09-24 21:16:50 +0300 |
---|---|---|
committer | Germano Cavalcante <germano.costa@ig.com.br> | 2020-09-24 21:18:34 +0300 |
commit | 744f81c936cbd946d2eb8035b9714b5f6bfbdc8c (patch) | |
tree | 6e11b9dafb6435e39ebbfec5621cad39aa2fd13a /source/blender/modifiers | |
parent | 6877a7b3ff6acc94b572dfab6c581ef6ed74e4f0 (diff) |
Weld Modifier: Use KD Tree in detecting the geometry to be welded
This commit replaces the BVH Tree currently used by the Weld Modifier
with the KD Tree used by `Merge > By Distance`.
This changes the result of the Weld Modifier to more closely match
`Merge > By Distance`.
There is also a big performance advantage.
Here is an overview (models in D8995):
| 2.90 (Duplicate Limit = 0) | 2.90 (Duplicate Limit = 1) | master (BVH) (Duplicate Limit = 1) | patch (KD) |
| 1.69s| 0.17s | 0.12s | 0.029s |
Differential Revision: https://developer.blender.org/D8995
Diffstat (limited to 'source/blender/modifiers')
-rw-r--r-- | source/blender/modifiers/intern/MOD_weld.c | 246 |
1 files changed, 120 insertions, 126 deletions
diff --git a/source/blender/modifiers/intern/MOD_weld.c b/source/blender/modifiers/intern/MOD_weld.c index d7d24062fc5..0932e54a7cf 100644 --- a/source/blender/modifiers/intern/MOD_weld.c +++ b/source/blender/modifiers/intern/MOD_weld.c @@ -27,12 +27,17 @@ * - Review weight and vertex color interpolation.; */ +//#define USE_WELD_DEBUG +//#define USE_WELD_NORMALS +//#define USE_BVHTREEKDOP + #include "MEM_guardedalloc.h" #include "BLI_utildefines.h" #include "BLI_alloca.h" -#include "BLI_kdopbvh.h" +#include "BLI_bitmap.h" +#include "BLI_kdtree.h" #include "BLI_math.h" #include "BLT_translation.h" @@ -43,7 +48,10 @@ #include "DNA_object_types.h" #include "DNA_screen_types.h" -#include "BKE_bvhutils.h" +#ifdef USE_BVHTREEKDOP +# include "BKE_bvhutils.h" +#endif + #include "BKE_context.h" #include "BKE_deform.h" #include "BKE_mesh.h" @@ -60,9 +68,6 @@ #include "MOD_modifiertypes.h" #include "MOD_ui_common.h" -//#define USE_WELD_DEBUG -//#define USE_WELD_NORMALS - /* Indicates when the element was not computed. */ #define OUT_OF_CONTEXT (uint)(-1) /* Indicates if the edge or face will be collapsed. */ @@ -136,9 +141,6 @@ typedef struct WeldMesh { /* Group of vertices to be merged. */ struct WeldGroup *vert_groups; uint *vert_groups_buffer; - /* From the original index of the vertex, this indicates which group it is or is going to be - * merged. */ - uint *vert_groups_map; /* Group of edges to be merged. */ struct WeldGroupEdge *edge_groups; @@ -202,21 +204,6 @@ static bool weld_iter_loop_of_poly_begin(WeldLoopOfPolyIter *iter, static bool weld_iter_loop_of_poly_next(WeldLoopOfPolyIter *iter); -static void weld_assert_vert_dest_map_setup(const BVHTreeOverlap *overlap, - const uint overlap_len, - const uint *vert_dest_map) -{ - const BVHTreeOverlap *overlap_iter = &overlap[0]; - for (uint i = overlap_len; i--; overlap_iter++) { - uint indexA = overlap_iter->indexA; - uint indexB = overlap_iter->indexB; - uint va_dst = vert_dest_map[indexA]; - uint vb_dst = vert_dest_map[indexB]; - - BLI_assert(va_dst == vb_dst); - } -} - static void weld_assert_edge_kill_len(const WeldEdge *wedge, const uint wedge_len, const uint supposed_kill_len) @@ -383,56 +370,10 @@ static void weld_assert_poly_len(const WeldPoly *wp, const WeldLoop *wloop) * \{ */ static void weld_vert_ctx_alloc_and_setup(const uint mvert_len, - const BVHTreeOverlap *overlap, - const uint overlap_len, uint *r_vert_dest_map, WeldVert **r_wvert, - uint *r_wvert_len, - uint *r_vert_kill_len) + uint *r_wvert_len) { - range_vn_u(r_vert_dest_map, mvert_len, 0); - - uint vert_kill_len = 0; - const BVHTreeOverlap *overlap_iter = &overlap[0]; - for (uint i = 0; i < overlap_len; i++, overlap_iter++) { - uint indexA = overlap_iter->indexA; - uint indexB = overlap_iter->indexB; - - BLI_assert(indexA < indexB); - - uint va_dst = r_vert_dest_map[indexA]; - while (va_dst != r_vert_dest_map[va_dst]) { - va_dst = r_vert_dest_map[va_dst]; - } - uint vb_dst = r_vert_dest_map[indexB]; - while (vb_dst != r_vert_dest_map[vb_dst]) { - vb_dst = r_vert_dest_map[vb_dst]; - } - if (va_dst == vb_dst) { - continue; - } - if (va_dst > vb_dst) { - SWAP(uint, va_dst, vb_dst); - } - vert_kill_len++; - r_vert_dest_map[vb_dst] = va_dst; - } - - /* Fix #r_vert_dest_map for next step. */ - for (uint i = 0; i < mvert_len; i++) { - if (i == r_vert_dest_map[i]) { - r_vert_dest_map[i] = OUT_OF_CONTEXT; - continue; - } - - uint v = i; - while (v != r_vert_dest_map[v] && r_vert_dest_map[v] != OUT_OF_CONTEXT) { - v = r_vert_dest_map[v]; - } - r_vert_dest_map[v] = v; - r_vert_dest_map[i] = v; - } - /* Vert Context. */ uint wvert_len = 0; @@ -450,13 +391,8 @@ static void weld_vert_ctx_alloc_and_setup(const uint mvert_len, } } -#ifdef USE_WELD_DEBUG - weld_assert_vert_dest_map_setup(overlap, overlap_len, r_vert_dest_map); -#endif - *r_wvert = MEM_reallocN(wvert, sizeof(*wvert) * wvert_len); *r_wvert_len = wvert_len; - *r_vert_kill_len = vert_kill_len; } static void weld_vert_groups_setup(const uint mvert_len, @@ -1382,8 +1318,8 @@ static void weld_poly_loop_ctx_setup(const MLoop *mloop, * \{ */ static void weld_mesh_context_create(const Mesh *mesh, - BVHTreeOverlap *overlap, - const uint overlap_len, + uint *vert_dest_map, + const uint vert_kill_len, WeldMesh *r_weld_mesh) { const MEdge *medge = mesh->medge; @@ -1394,19 +1330,13 @@ static void weld_mesh_context_create(const Mesh *mesh, const uint mloop_len = mesh->totloop; const uint mpoly_len = mesh->totpoly; - uint *vert_dest_map = MEM_mallocN(sizeof(*vert_dest_map) * mvert_len, __func__); uint *edge_dest_map = MEM_mallocN(sizeof(*edge_dest_map) * medge_len, __func__); struct WeldGroup *v_links = MEM_callocN(sizeof(*v_links) * mvert_len, __func__); WeldVert *wvert; uint wvert_len; - weld_vert_ctx_alloc_and_setup(mvert_len, - overlap, - overlap_len, - vert_dest_map, - &wvert, - &wvert_len, - &r_weld_mesh->vert_kill_len); + r_weld_mesh->vert_kill_len = vert_kill_len; + weld_vert_ctx_alloc_and_setup(mvert_len, vert_dest_map, &wvert, &wvert_len); uint *edge_ctx_map; WeldEdge *wedge; @@ -1449,7 +1379,6 @@ static void weld_mesh_context_create(const Mesh *mesh, &r_weld_mesh->edge_groups_buffer, &r_weld_mesh->edge_groups); - r_weld_mesh->vert_groups_map = vert_dest_map; r_weld_mesh->edge_groups_map = edge_dest_map; MEM_freeN(v_links); MEM_freeN(wvert); @@ -1461,7 +1390,6 @@ static void weld_mesh_context_free(WeldMesh *weld_mesh) { MEM_freeN(weld_mesh->vert_groups); MEM_freeN(weld_mesh->vert_groups_buffer); - MEM_freeN(weld_mesh->vert_groups_map); MEM_freeN(weld_mesh->edge_groups); MEM_freeN(weld_mesh->edge_groups_buffer); @@ -1620,6 +1548,7 @@ static void customdata_weld( /** \name Weld Modifier Main * \{ */ +#ifdef USE_BVHTREEKDOP struct WeldOverlapData { const MVert *mvert; float merge_dist_sq; @@ -1635,6 +1564,7 @@ static bool bvhtree_weld_overlap_cb(void *userdata, int index_a, int index_b, in } return false; } +#endif static Mesh *weldModifier_doWeld(WeldModifierData *wmd, const ModifierEvalContext *ctx, Mesh *mesh) { @@ -1672,48 +1602,114 @@ static Mesh *weldModifier_doWeld(WeldModifierData *wmd, const ModifierEvalContex } } - /* Get overlap map. */ - /* TODO: For a better performanse use KD-Tree. */ - struct BVHTreeFromMesh treedata; - BVHTree *bvhtree = bvhtree_from_mesh_verts_ex(&treedata, - mvert, - totvert, - false, - v_mask, - v_mask_act, - wmd->merge_dist / 2, - 2, - 6, - 0, - NULL, - NULL); + /* From the original index of the vertex. + * This indicates which vert it is or is going to be merged. */ + uint *vert_dest_map = MEM_malloc_arrayN(totvert, sizeof(*vert_dest_map), __func__); + uint vert_kill_len = 0; +#ifdef USE_BVHTREEKDOP + { + /* Get overlap map. */ + struct BVHTreeFromMesh treedata; + BVHTree *bvhtree = bvhtree_from_mesh_verts_ex(&treedata, + mvert, + totvert, + false, + v_mask, + v_mask_act, + wmd->merge_dist / 2, + 2, + 6, + 0, + NULL, + NULL); + + if (bvhtree) { + struct WeldOverlapData data; + data.mvert = mvert; + data.merge_dist_sq = square_f(wmd->merge_dist); + + uint overlap_len; + BVHTreeOverlap *overlap = BLI_bvhtree_overlap_ex(bvhtree, + bvhtree, + &overlap_len, + bvhtree_weld_overlap_cb, + &data, + 1, + BVH_OVERLAP_RETURN_PAIRS); + + free_bvhtree_from_mesh(&treedata); + if (overlap) { + range_vn_u(vert_dest_map, totvert, 0); + + const BVHTreeOverlap *overlap_iter = &overlap[0]; + for (uint i = 0; i < overlap_len; i++, overlap_iter++) { + uint indexA = overlap_iter->indexA; + uint indexB = overlap_iter->indexB; + + BLI_assert(indexA < indexB); + + uint va_dst = vert_dest_map[indexA]; + while (va_dst != vert_dest_map[va_dst]) { + va_dst = vert_dest_map[va_dst]; + } + uint vb_dst = vert_dest_map[indexB]; + while (vb_dst != vert_dest_map[vb_dst]) { + vb_dst = vert_dest_map[vb_dst]; + } + if (va_dst == vb_dst) { + continue; + } + if (va_dst > vb_dst) { + SWAP(uint, va_dst, vb_dst); + } + vert_kill_len++; + vert_dest_map[vb_dst] = va_dst; + } - if (v_mask) { - MEM_freeN(v_mask); - } + /* Fix #r_vert_dest_map for next step. */ + for (uint i = 0; i < totvert; i++) { + if (i == vert_dest_map[i]) { + vert_dest_map[i] = OUT_OF_CONTEXT; + } + else { + uint v = i; + while (v != vert_dest_map[v] && vert_dest_map[v] != OUT_OF_CONTEXT) { + v = vert_dest_map[v]; + } + vert_dest_map[v] = v; + vert_dest_map[i] = v; + } + } - if (bvhtree == NULL) { - return result; + MEM_freeN(overlap); + } + } } +#else + { + vert_dest_map = MEM_malloc_arrayN(totvert, sizeof(*vert_dest_map), __func__); + KDTree_3d *tree = BLI_kdtree_3d_new(totvert); + for (i = 0; i < totvert; i++) { + if (!(v_mask && !BLI_BITMAP_TEST(v_mask, i))) { + BLI_kdtree_3d_insert(tree, i, mvert[i].co); + } + vert_dest_map[i] = OUT_OF_CONTEXT; + } - struct WeldOverlapData data; - data.mvert = mvert; - data.merge_dist_sq = square_f(wmd->merge_dist); - - uint overlap_len; - BVHTreeOverlap *overlap = BLI_bvhtree_overlap_ex(bvhtree, - bvhtree, - &overlap_len, - bvhtree_weld_overlap_cb, - &data, - wmd->max_interactions, - BVH_OVERLAP_RETURN_PAIRS); + BLI_kdtree_3d_balance(tree); + vert_kill_len = BLI_kdtree_3d_calc_duplicates_fast( + tree, wmd->merge_dist, false, (int *)vert_dest_map); + BLI_kdtree_3d_free(tree); + } +#endif - free_bvhtree_from_mesh(&treedata); + if (v_mask) { + MEM_freeN(v_mask); + } - if (overlap_len) { + if (vert_kill_len) { WeldMesh weld_mesh; - weld_mesh_context_create(mesh, overlap, overlap_len, &weld_mesh); + weld_mesh_context_create(mesh, vert_dest_map, vert_kill_len, &weld_mesh); mloop = mesh->mloop; mpoly = mesh->mpoly; @@ -1732,7 +1728,7 @@ static Mesh *weldModifier_doWeld(WeldModifierData *wmd, const ModifierEvalContex /* Vertices */ - uint *vert_final = weld_mesh.vert_groups_map; + uint *vert_final = vert_dest_map; uint *index_iter = &vert_final[0]; int dest_index = 0; for (i = 0; i < totvert; i++, index_iter++) { @@ -1905,7 +1901,7 @@ static Mesh *weldModifier_doWeld(WeldModifierData *wmd, const ModifierEvalContex weld_mesh_context_free(&weld_mesh); } - MEM_freeN(overlap); + MEM_freeN(vert_dest_map); return result; } @@ -1920,7 +1916,6 @@ static void initData(ModifierData *md) WeldModifierData *wmd = (WeldModifierData *)md; wmd->merge_dist = 0.001f; - wmd->max_interactions = 1; wmd->defgrp_name[0] = '\0'; } @@ -1946,7 +1941,6 @@ static void panel_draw(const bContext *UNUSED(C), Panel *panel) uiLayoutSetPropSep(layout, true); uiItemR(layout, ptr, "merge_threshold", 0, IFACE_("Distance"), ICON_NONE); - uiItemR(layout, ptr, "max_interactions", 0, NULL, ICON_NONE); modifier_vgroup_ui(layout, ptr, &ob_ptr, "vertex_group", "invert_vertex_group", NULL); modifier_panel_end(layout, ptr); |