[Bf-blender-cvs] [744f81c936c] master: Weld Modifier: Use KD Tree in detecting the geometry to be welded
Henrik Dick
noreply at git.blender.org
Thu Sep 24 20:22:03 CEST 2020
Commit: 744f81c936cbd946d2eb8035b9714b5f6bfbdc8c
Author: Henrik Dick
Date: Thu Sep 24 15:16:50 2020 -0300
Branches: master
https://developer.blender.org/rB744f81c936cbd946d2eb8035b9714b5f6bfbdc8c
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
===================================================================
M source/blender/makesdna/DNA_modifier_types.h
M source/blender/makesrna/intern/rna_modifier.c
M source/blender/modifiers/intern/MOD_weld.c
===================================================================
diff --git a/source/blender/makesdna/DNA_modifier_types.h b/source/blender/makesdna/DNA_modifier_types.h
index 9a5b5b8c2ca..c0716388f28 100644
--- a/source/blender/makesdna/DNA_modifier_types.h
+++ b/source/blender/makesdna/DNA_modifier_types.h
@@ -1978,12 +1978,11 @@ typedef struct WeldModifierData {
/* The limit below which to merge vertices. */
float merge_dist;
- unsigned int max_interactions;
/* Name of vertex group to use to mask, MAX_VGROUP_NAME. */
char defgrp_name[64];
short flag;
- char _pad[6];
+ char _pad[2];
} WeldModifierData;
/* WeldModifierData->flag */
diff --git a/source/blender/makesrna/intern/rna_modifier.c b/source/blender/makesrna/intern/rna_modifier.c
index 2463f3c409f..8a82b37a1a8 100644
--- a/source/blender/makesrna/intern/rna_modifier.c
+++ b/source/blender/makesrna/intern/rna_modifier.c
@@ -6332,15 +6332,6 @@ static void rna_def_modifier_weld(BlenderRNA *brna)
RNA_def_property_ui_text(prop, "Merge Distance", "Limit below which to merge vertices");
RNA_def_property_update(prop, 0, "rna_Modifier_update");
- prop = RNA_def_property(srna, "max_interactions", PROP_INT, PROP_UNSIGNED);
- RNA_def_property_int_sdna(prop, NULL, "max_interactions");
- RNA_def_property_ui_text(
- prop,
- "Duplicate Limit",
- "For a better performance, limits the number of elements found per vertex. "
- "(0 makes it infinite)");
- RNA_def_property_update(prop, 0, "rna_Modifier_update");
-
prop = RNA_def_property(srna, "vertex_group", PROP_STRING, PROP_NONE);
RNA_def_property_string_sdna(prop, NULL, "defgrp_name");
RNA_def_property_ui_text(
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,
+
@@ Diff output truncated at 10240 characters. @@
More information about the Bf-blender-cvs
mailing list