- Use BVHtree to optimize the search for intersections.
Tests were done using overlap between two BVHTrees (Edges and Vertices) and with a new function called BLI_bvhtree_find_duplicate_fast.
The results were similar but with a slight advantage to the find_duplicate_fast solution.
The tests were done on a 2x subdivided suzanne and a dense high poly mesh.
Here are the results:
t1: Default AutoMerge Time (No Split);
t2: AutoMerge + Split time;
fac: t1 / t2;
|1 BVHTree Solution:||t1||t2||fac|
|Split all suzanne edges:||0.018140||0.056898||0.318820|
|Move away suzanne verts:||0.017129||0.020090||0.852576|
|Merge single suzanne vert:||0.017531||0.014227||1.232292|
|Split single suzanne edge:||0.017406||0.019180||0.907499|
|Move away verts of high poly mesh:||0.280441||0.307028||0.913406|
For reference here are values without BVHTree:
|Loop over all combinations (O^2)||t1||t2||fac|
|Split all suzanne edges:||0.018473||0.217000||0.085130|
|Move away suzanne verts:||0.017998||0.165078||0.109026|
|Merge single suzanne vert:||0.017777||0.014594||1.218125|
|Split single suzanne edge:||0.017457||0.015389||1.134390|
|Move away verts of high poly mesh:||0.282407||29.029363||0.009728|
Assuming this is called fast because it optimizes for speed over quality.
This function should document the trade off's it makes.
Could use BM_vert_pair_share_face_check_cb.
This isn't checking if the face is hidden.
Prefer to avoid adding numbers onto variable names and instead name them in a way that tells us how it's different. eg: cuts_iter_other or cuts_iter_adjacent.
this can be made into a utility function similar to BM_vert_pair_share_face_check_cb
Would also pick the *best* face since this will cause an error with edges between concave faces, which may also be joined by an adjacent face which the edge crosses.
There are a few ways this could be tested, one would be to calculate two normals on either side of the vertices with BM_face_calc_normal_subset, if they're flipped - the edge runs between concave part of a face and can be skipped, we could also check that this edge doesn't cross any edges of the face - although not sure that's needed.
Would call this DEBUG_TIME (typically used elsewhere).
Even with ifdef's like this, they should be outside the function otherwise adding inline function could cause an error - for eg.
This is no longer used.
should be static.
f isn't used,. use UNUSED(f)
This gives me:
/src/blender/source/blender/editors/mesh/editmesh_select.c: In function ‘EDBM_automerge_and_split’: /src/blender/source/blender/editors/mesh/editmesh_select.c:456:15: error: flexible array member in union 456 | int as_int;
use int as_int;
Shadows previous value, needs to be named differently.