Page MenuHome

Transform: approximate geodesic distances for proportional edit connected mode
ClosedPublic

Authored by Brecht Van Lommel (brecht) on Jan 11 2021, 9:40 AM.
Tokens
"Love" token, awarded by gritche."Love" token, awarded by Lumpengnom."Love" token, awarded by hadrien."Love" token, awarded by gilberto_rodrigues."Like" token, awarded by Torrent."Like" token, awarded by TheRedWaxPolice."Party Time" token, awarded by lichtwerk."Love" token, awarded by kioku.

Details

Summary

Use approximate geodesic distance computatiom that crosses through triangles
rather than only along edges. Using only edges would give artifacts already
on a simple grid.

The initial distance computation is about 1.5x slower in my tests. The first
naive implementation was about 8x slower. It was optimized by switching to an
edge based queue, adding early out tests and always propagating using latest
distance estimates. The only remaining big optimization I can think of would
be multithreading, but that's fairly difficult.

The same algorithm should be useful for sculpt mode falloff and instance/hair
distribution as well, so the core math function was added in blenlib.

The algorithm can be further improved for the case where a region is selected
rather than a single vertex. The boundary of the region is not smooth since it
zigzags along the topology, and that leads to non-smooth distances as well.
Less so for geodesic distances but still visible. Some type of blurring of the
boundary before propagation would help, but I consider that outside the scope
of this patch.

Diff Detail

Repository
rB Blender

Event Timeline

Brecht Van Lommel (brecht) requested review of this revision.Jan 11 2021, 9:40 AM
Brecht Van Lommel (brecht) created this revision.

Comparison of new and old, with various mesh topologies.

Good to see an improvement in this area.
While in the examples shown it worked very well, I tested it in a simpler geometry and the result does not seem to be as expected:


(I may be talking nonsense, but I suspect the problem may be in the order of the edges of the loop BM_ITER_MESH (e, &eiter, bm, BM_EDGES_OF_MESH))

source/blender/blenlib/intern/math_geom.c
6254

Are these "two vertices" v1 and v2?

6281

Why not put this condition before computing n, u, v and v0_? (I don't know if it contributes in any way to the performance, but it simplifies the code a little in my opinion).
Btw, if I'm not mistaken, normalize_v3_v3(u, v12); already returns the value of d12.

Brecht Van Lommel (brecht) marked 2 inline comments as done.

Address comments, fix bugs with loose edges.

That .blend file and more complex cases with mixed loose edges and faces should work now.

Thank you for working on this. This is going to make a huge difference for the sculpt mode tools and features.
I implemented the same algorithm for Mesh in sculpt mode, with optimizations and features related to the tools (limited by radius, using face set visibility...) P1882. Performance and results are fantastic. I still need to fix some things, but it may be possible to integrate as a falloff type and have it available for all brushes. I'll implement the same version with bmesh for dyntopo as well. For Multires I don't see this working anytime soon because it needs to reference edges, but I can make it fallback to a simpler implementation that only uses edges.

Mask Expand using geodesic distances:

Very nice! minor issue noted, otherwise LGTM.

source/blender/editors/transform/transform_convert_mesh.c
398–400

Initialize BMLoop *l_other = l->next->next; and this check can be removed or turned into an assert.

This revision is now accepted and ready to land.Jan 12 2021, 9:13 AM

Thanks for the reviews, I'll commit this with Campbell's suggestion once master is open for new features.

Apologies for the noise, but I'll drink to your health tonight @Brecht Van Lommel (brecht). Big, big thanks !!