Page MenuHome

Split all Edge x Edge intersections with AutoMerge & Split option

Authored by Germano Cavalcante (mano-wii) on Fri, Aug 30, 4:19 PM.



This solution is more intuitive than the current solution that only tests Vert x Edge intersections.
For greater control of the merged vertices, the weld_vert bmesh operator has been replaced and is no longer used by the function.

For organization, the BM_vert_weld_linked_wire_edges_into_linked_faces function was exposed in the header although not used by another file.

A new function for bmesh_core has also been created.: BM_vert_splice_collapse.

To profile the time, tests were done on a 2x subdivided Suzanne and a dense high poly object.

The most unfavorable time was to split all Suzanne edges by other diagonal-directed edges:

t1: AutoMerge Whithout Split;
t2: AutoMerge + Split;
fac: t1 / t2;

Here are the results:

Split all edges:t1t2fac
Extrude loose verts and split all suzanne edges diagonally:0.0280741.2658410.022178
Split all suzanne edges:0.0159470.0347280.459193
Move out suzanne verts:0.0151860.0127691.189227
Merge single suzanne vert:0.0149850.0128871.162742
Split single suzanne edge:0.0151100.0128101.179504
Duplicate and move away verts of high poly mesh:0.2374190.2300891.031855

Diff Detail

rB Blender

Event Timeline

  • Use BM_edge_collapse instead of BM_vert_splice and utils
  • Revert "Use BM_edge_collapse instead of BM_vert_splice and utils"
  • Move all intersect_edges function to a new bmesh file
  • Comment #define DEBUG_TIME

Talked on, this is useful functionality, intersecting edges with eachother can be a separate, reusable function (moved out of auto-merge).

  • Use BVHTree with 7 kdop axis (14)

This type of BVHTree proved to be 2.4x more efficient than the other BVHTrees at diagonal intersections.
However it was less efficient in all other tests.
But it still beats the original AutoMerge.

Germano Cavalcante (mano-wii) planned changes to this revision.Mon, Sep 2, 2:08 PM
  • Update BM_vert_splice_collapse function;
  • BLI KdopBVH: New BLI_bvhtree_overlap_ex util
  • BMesh: New intersect tool functions
  • Transform: AutoMerge: intersect all
Campbell Barton (campbellbarton) requested changes to this revision.Thu, Sep 12, 12:40 PM

Testing this patch I'm running into an error that happens without this patch applied. reported T69792: Auto-merge split faces creates faces with unrelated wire edges.

With the same file from that report (

). extruding an edge across two triangles only splits one of the triangles (on the far side), resulting in 3 triangles when it should give 4.

1364–1378 ↗(On Diff #18121)
/src/blender/source/blender/blenlib/intern/BLI_kdopbvh.c: In function ‘BLI_bvhtree_overlap’:
/src/blender/source/blender/blenlib/intern/BLI_kdopbvh.c:1372:10: error: too many arguments to function ‘BLI_bvhtree_overlap’
 1372 |   return BLI_bvhtree_overlap(tree1,
      |          ^~~~~~~~~~~~~~~~~~~
/src/blender/source/blender/blenlib/intern/BLI_kdopbvh.c:1364:17: note: declared here
 1364 | BVHTreeOverlap *BLI_bvhtree_overlap(
      |                 ^~~~~~~~~~~~~~~~~~~

Ideally we should have build systems configured not to allow the wrong number of args.

381 ↗(On Diff #18121)

This could be made the default ray intersection function? Since co-linear check is a common error-case for this test.

In this case we might want to pass in an epsilon though.

822 ↗(On Diff #18121)

Should be max_ii (max isn't defined in Linux).

This revision now requires changes to proceed.Thu, Sep 12, 12:40 PM
Germano Cavalcante (mano-wii) marked 3 inline comments as done.Thu, Sep 12, 5:30 PM
Germano Cavalcante (mano-wii) updated this revision to Diff 18161.
  • Rebase;
  • Use new BLI_math function;
  • Fix compiller errors.

Generally looks fine, I'm getting errors though in the console.

Looks like you're missing marking bm->elem_index_dirty

Invalid Index: at /src/blender/source/blender/bmesh/intern/bmesh_operators.c:245, BMO_op_finish, vert[8] invalid index -1, 'post bmo', 'weld_verts'
Invalid Index: at /src/blender/source/blender/bmesh/intern/bmesh_operators.c:245, BMO_op_finish, edge[15] invalid index 0, 'post bmo', 'weld_verts'
Invalid Index: at /src/blender/source/blender/bmesh/intern/bmesh_operators.c:245, BMO_op_finish, vert[9] invalid index -1, 'post bmo', 'weld_verts'
Invalid Index: at /src/blender/source/blender/bmesh/intern/bmesh_operators.c:245, BMO_op_finish, edge[18] invalid index 0, 'post bmo', 'weld_verts'
332 ↗(On Diff #18161)

Unused thread argument

This revision is now accepted and ready to land.Thu, Sep 12, 6:02 PM
  • Fix elem_index_dirty flag
Germano Cavalcante (mano-wii) marked an inline comment as done.Thu, Sep 12, 6:24 PM
Germano Cavalcante (mano-wii) updated this revision to Diff 18165.
  • Fix unused thread