diff options
author | Howard Trickey <howard.trickey@gmail.com> | 2021-07-18 17:48:57 +0300 |
---|---|---|
committer | Howard Trickey <howard.trickey@gmail.com> | 2021-07-18 17:48:57 +0300 |
commit | 3c8d261557e0b76d2d97902ade5668b6044227b6 (patch) | |
tree | bb93cca1993dbe982a9c3b62275a5a2a3739ac9f /source/blender/blenlib/intern/mesh_intersect.cc | |
parent | e82c5c660778b3805f50f3f2901923692c17db2a (diff) |
Greatly improve speed of Delaunay when have a lot of holes.
Using part of a patch from Erik Abrahamsson, this replaces the
use of linked lists for original id tracking by Sets.
I had thought that the lists were unlikely to grow to more than
a few elements, but when the mesh has a lot of holes (whose
original ids go *outside* the hole, and therefore, most of the
mesh), this assumption can be very wrong.
On a Text regression test, the time went from 11.67s to 0.16s
with this fix. I also tested to make sure that Boolean didn't
slow down with this, and found it actually had a very slight speedup.
Using Sets exposed a dependency on the ordering of the items
in the id lists, luckily caught by a mesh intersect regression test,
so fixed that.
Diffstat (limited to 'source/blender/blenlib/intern/mesh_intersect.cc')
-rw-r--r-- | source/blender/blenlib/intern/mesh_intersect.cc | 65 |
1 files changed, 45 insertions, 20 deletions
diff --git a/source/blender/blenlib/intern/mesh_intersect.cc b/source/blender/blenlib/intern/mesh_intersect.cc index f91dd762e70..400b3f94a3f 100644 --- a/source/blender/blenlib/intern/mesh_intersect.cc +++ b/source/blender/blenlib/intern/mesh_intersect.cc @@ -1875,6 +1875,16 @@ static void do_cdt(CDT_data &cd) } } +/* Find an original edge index that goes with the edge that the CDT output edge + * that goes between verts i0 and i1 (in the CDT output vert indexing scheme). + * There may be more than one: if so, prefer one that was originally a face edge. + * The input to CDT for a triangle with some intersecting segments from other triangles + * will have both edges and a face constraint for the main triangle (this is redundant + * but allows us to discover which face edge goes with which output edges). + * If there is any face edge, return one of those as the original. + * If there is no face edge but there is another edge in the input problem, then that + * edge must have come from intersection with another triangle, so set *r_is_intersect + * to true in that case. */ static int get_cdt_edge_orig( int i0, int i1, const CDT_data &cd, const IMesh &in_tm, bool *r_is_intersect) { @@ -1900,35 +1910,50 @@ static int get_cdt_edge_orig( } /* Pick an arbitrary orig, but not one equal to NO_INDEX, if we can help it. */ - /* TODO: if edge has origs from more than on part of the nary input, + /* TODO: if edge has origs from more than one part of the nary input, * then want to set *r_is_intersect to true. */ + int face_eorig = NO_INDEX; + bool have_non_face_eorig = false; for (int orig_index : cd.cdt_out.edge_orig[e]) { /* orig_index encodes the triangle and pos within the triangle of the input edge. */ if (orig_index >= foff) { - int in_face_index = (orig_index / foff) - 1; - int pos = orig_index % foff; - /* We need to retrieve the edge orig field from the Face used to populate the - * in_face_index'th face of the CDT, at the pos'th position of the face. */ - int in_tm_face_index = cd.input_face[in_face_index]; - BLI_assert(in_tm_face_index < in_tm.face_size()); - const Face *facep = in_tm.face(in_tm_face_index); - BLI_assert(pos < facep->size()); - bool is_rev = cd.is_reversed[in_face_index]; - int eorig = is_rev ? facep->edge_orig[2 - pos] : facep->edge_orig[pos]; - if (eorig != NO_INDEX) { - return eorig; + if (face_eorig == NO_INDEX) { + int in_face_index = (orig_index / foff) - 1; + int pos = orig_index % foff; + /* We need to retrieve the edge orig field from the Face used to populate the + * in_face_index'th face of the CDT, at the pos'th position of the face. */ + int in_tm_face_index = cd.input_face[in_face_index]; + BLI_assert(in_tm_face_index < in_tm.face_size()); + const Face *facep = in_tm.face(in_tm_face_index); + BLI_assert(pos < facep->size()); + bool is_rev = cd.is_reversed[in_face_index]; + int eorig = is_rev ? facep->edge_orig[2 - pos] : facep->edge_orig[pos]; + if (eorig != NO_INDEX) { + face_eorig = eorig; + } } } else { - /* This edge came from an edge input to the CDT problem, - * so it is an intersect edge. */ - *r_is_intersect = true; - /* TODO: maybe there is an orig index: - * This happens if an input edge was formed by an input face having - * an edge that is co-planar with the cluster, while the face as a whole is not. */ - return NO_INDEX; + if (!have_non_face_eorig) { + have_non_face_eorig = true; + } + if (face_eorig != NO_INDEX && have_non_face_eorig) { + /* Only need at most one orig for each type. */ + break; + } } } + if (face_eorig != NO_INDEX) { + return face_eorig; + } + else if (have_non_face_eorig) { + /* This must have been an input to the CDT problem that was an intersection edge. */ + /* TODO: maybe there is an orig index: + * This happens if an input edge was formed by an input face having + * an edge that is co-planar with the cluster, while the face as a whole is not. */ + *r_is_intersect = true; + return NO_INDEX; + } return NO_INDEX; } |