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
This commit is contained in:
parent
6877a7b3ff
commit
744f81c936
|
@ -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 */
|
||||
|
|
|
@ -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(
|
||||
|
|
|
@ -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;
|
||||
}
|
||||
|
||||
/* 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;
|
||||
}
|
||||
}
|
||||
|
||||
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;
|
||||
}
|
||||
|
||||
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
|
||||
|
||||
if (v_mask) {
|
||||
MEM_freeN(v_mask);
|
||||
}
|
||||
|
||||
if (bvhtree == NULL) {
|
||||
return result;
|
||||
}
|
||||
|
||||
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);
|
||||
|
||||
free_bvhtree_from_mesh(&treedata);
|
||||
|
||||
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);
|
||||
|
|
Loading…
Reference in New Issue