Use KD Tree for Weld Modifier for better performance
ClosedPublic
Actions

Authored by Henrik Dick (weasel) on Sep 23 2020, 7:56 PM.

Details

Reviewers

Germano Cavalcante (mano-wii)
Campbell Barton (campbellbarton)

Group Reviewers

Modifiers

Commits

rB744f81c936cb: Weld Modifier: Use KD Tree in detecting the geometry to be welded

Summary

This patch 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.

Additionally to the quality improvement there is also a big performance advantage.
Try this blend file with and without the patch. With the patch it's 4x faster when played in comparison with current master with Duplicate Limit set to 1. If all subsurf modifiers are applied then this patch will be 14x faster than master.

weldkdtest2.blend691 KBDownload

I also tested models that would not have merged vertices and even there the KD Tree is 17% faster.

Here is an overview

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

Diff Detail

Repository: rB Blender

Event Timeline

Henrik Dick (weasel) requested review of this revision.Sep 23 2020, 7:56 PM

Henrik Dick (weasel) created this revision.

Woow 0.12s vs 0.029s! The difference is really noticeable!

But I'm not sure if there is really a "quality improvement" here.
As the name says BLI_kdtree_3d_calc_duplicates_fast focuses more on speed than quality.

Perhaps instead of removing the solution with BVHTree, as a first step it would be better to use the preprocessing directive (like #if USE_BVH_SOLUTION) to disable the BVH code on compilation.
From what I can see, the purpose of this patch, in addition to the performance, is to remove the need for overlapping vertices chains correction.
This also makes the result very dependent on the order in which the vertices are tested.

It might be a good idea to leave both solutions, and add a bool for the modifier ("Merge in groups").

The improvement in performance is really a gain, but I don't know if the quality and the result dependent on the order is really this improvement.

I will be more confident in accepting the patch with the preprocessing directive.

@Campbell Barton (campbellbarton), what do you think?

@Germano Cavalcante (mano-wii) is the current solution order independent?

If not, then this seems a reasonable change.

If we want a higher quality weld calculation we could do this as a separate task, one that groups clusters of vertices and welds them into their median location (although I don't think this is very urgent/important).

No strong opinion on if'defing the existing code out or removing it.

Accepting, but leave the final choice to @Germano Cavalcante (mano-wii).

This revision is now accepted and ready to land.Sep 24 2020, 2:52 AM