[Bf-blender-cvs] [3c8d261557e] master: Greatly improve speed of Delaunay when have a lot of holes.
Howard Trickey
noreply at git.blender.org
Sun Jul 18 16:50:26 CEST 2021
Commit: 3c8d261557e0b76d2d97902ade5668b6044227b6
Author: Howard Trickey
Date: Sun Jul 18 10:48:57 2021 -0400
Branches: master
https://developer.blender.org/rB3c8d261557e0b76d2d97902ade5668b6044227b6
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.
===================================================================
M source/blender/blenlib/intern/delaunay_2d.cc
M source/blender/blenlib/intern/mesh_intersect.cc
M source/blender/blenlib/tests/BLI_delaunay_2d_test.cc
===================================================================
diff --git a/source/blender/blenlib/intern/delaunay_2d.cc b/source/blender/blenlib/intern/delaunay_2d.cc
index 24a58103a10..279fe6f38b4 100644
--- a/source/blender/blenlib/intern/delaunay_2d.cc
+++ b/source/blender/blenlib/intern/delaunay_2d.cc
@@ -29,6 +29,7 @@
#include "BLI_math_boolean.hh"
#include "BLI_math_mpq.hh"
#include "BLI_mpq2.hh"
+#include "BLI_set.hh"
#include "BLI_vector.hh"
#include "BLI_delaunay_2d.h"
@@ -77,8 +78,8 @@ template<> double math_to_double<double>(const double v)
* Define a templated 2D arrangement of vertices, edges, and faces.
* The #SymEdge data structure is the basis for a structure that allows
* easy traversal to neighboring (by topology) geometric elements.
- * Each of #CDTVert, #CDTEdge, and #CDTFace have an input_id linked list,
- * whose nodes contain integers that keep track of which input verts, edges,
+ * Each of #CDTVert, #CDTEdge, and #CDTFace have an input_id set,
+ * which contain integers that keep track of which input verts, edges,
* and faces, respectively, that the element was derived from.
*
* While this could be cleaned up some, it is usable by other routines in Blender
@@ -195,8 +196,8 @@ template<typename T> struct CDTVert {
FatCo<T> co;
/** Some edge attached to it. */
SymEdge<T> *symedge{nullptr};
- /** List of corresponding vertex input ids. */
- LinkNode *input_ids{nullptr};
+ /** Set of corresponding vertex input ids. */
+ blender::Set<int> input_ids;
/** Index into array that #CDTArrangement keeps. */
int index{-1};
/** Index of a CDTVert that this has merged to. -1 if no merge. */
@@ -209,8 +210,8 @@ template<typename T> struct CDTVert {
};
template<typename Arith_t> struct CDTEdge {
- /** List of input edge ids that this is part of. */
- LinkNode *input_ids{nullptr};
+ /** Set of input edge ids that this is part of. */
+ blender::Set<int> input_ids;
/** The directed edges for this edge. */
SymEdge<Arith_t> symedges[2]{SymEdge<Arith_t>(), SymEdge<Arith_t>()};
@@ -220,8 +221,8 @@ template<typename Arith_t> struct CDTEdge {
template<typename Arith_t> struct CDTFace {
/** A symedge in face; only used during output, so only valid then. */
SymEdge<Arith_t> *symedge{nullptr};
- /** List of input face ids that this is part of. */
- LinkNode *input_ids{nullptr};
+ /** Set of input face ids that this is part of. */
+ blender::Set<int> input_ids;
/** Used by algorithms operating on CDT structures. */
int visit_index{0};
/** Marks this face no longer used. */
@@ -342,19 +343,19 @@ template<typename T> CDTArrangement<T>::~CDTArrangement()
{
for (int i : this->verts.index_range()) {
CDTVert<T> *v = this->verts[i];
- BLI_linklist_free(v->input_ids, nullptr);
+ v->input_ids.clear();
delete v;
this->verts[i] = nullptr;
}
for (int i : this->edges.index_range()) {
CDTEdge<T> *e = this->edges[i];
- BLI_linklist_free(e->input_ids, nullptr);
+ e->input_ids.clear();
delete e;
this->edges[i] = nullptr;
}
for (int i : this->faces.index_range()) {
CDTFace<T> *f = this->faces[i];
- BLI_linklist_free(f->input_ids, nullptr);
+ f->input_ids.clear();
delete f;
this->faces[i] = nullptr;
}
@@ -495,6 +496,7 @@ template<typename T> void cdt_draw(const std::string &label, const CDTArrangemen
constexpr int vert_radius = 3;
constexpr bool draw_vert_labels = true;
constexpr bool draw_edge_labels = false;
+ constexpr bool draw_face_labels = false;
if (cdt.verts.size() == 0) {
return;
@@ -559,7 +561,7 @@ template<typename T> void cdt_draw(const std::string &label, const CDTArrangemen
const CDTVert<T> *v = e->symedges[1].vert;
const vec2<double> &uco = u->co.approx;
const vec2<double> &vco = v->co.approx;
- int strokew = e->input_ids == nullptr ? thin_line : thick_line;
+ int strokew = e->input_ids.size() == 0 ? thin_line : thick_line;
f << R"(<line fill="none" stroke="black" stroke-width=")" << strokew << "\" x1=\""
<< SX(uco[0]) << "\" y1=\"" << SY(uco[1]) << "\" x2=\"" << SX(vco[0]) << "\" y2=\""
<< SY(vco[1]) << "\">\n";
@@ -586,6 +588,54 @@ template<typename T> void cdt_draw(const std::string &label, const CDTArrangemen
++i;
}
+ if (draw_face_labels) {
+ for (const CDTFace<T> *face : cdt.faces) {
+ if (!face->deleted) {
+ /* Since may not have prepared output yet, need a slow find of a SymEdge for this face. */
+ const SymEdge<T> *se_face_start = nullptr;
+ for (const CDTEdge<T> *e : cdt.edges) {
+ if (e->symedges[0].face == face) {
+ se_face_start = &e->symedges[0];
+ break;
+ }
+ if (e->symedges[1].face == face) {
+ se_face_start = &e->symedges[1];
+ }
+ }
+ if (se_face_start != nullptr) {
+ /* Find center of face. */
+ int face_nverts = 0;
+ vec2<double> cen(0.0, 0.0);
+ if (face == cdt.outer_face) {
+ cen.x = minx;
+ cen.y = miny;
+ }
+ else {
+ const SymEdge<T> *se = se_face_start;
+ do {
+ if (se->face == face) {
+ cen = cen + se->vert->co.approx;
+ face_nverts++;
+ }
+ } while ((se = se->next) != se_face_start);
+ if (face_nverts > 0) {
+ cen = cen / double(face_nverts);
+ }
+ }
+ f << "<text x=\"" << SX(cen[0]) << "\" y=\"" << SY(cen[1]) << "\""
+ << " font-size=\"small\">[";
+ f << trunc_ptr(face);
+ if (face->input_ids.size() > 0) {
+ for (int id : face->input_ids) {
+ f << " " << id;
+ }
+ }
+ f << "]</text>\n";
+ }
+ }
+ }
+ }
+
append = true;
# undef SX
# undef SY
@@ -754,7 +804,6 @@ template<> CDTVert<double>::CDTVert(const vec2<double> &pt)
this->co.exact = pt;
this->co.approx = pt;
this->co.abs_approx = pt; /* Not used, so doesn't matter. */
- this->input_ids = nullptr;
this->symedge = nullptr;
this->index = -1;
this->merge_to_index = -1;
@@ -767,7 +816,6 @@ template<> CDTVert<mpq_class>::CDTVert(const vec2<mpq_class> &pt)
this->co.exact = pt;
this->co.approx = double2(pt.x.get_d(), pt.y.get_d());
this->co.abs_approx = double2(fabs(this->co.approx.x), fabs(this->co.approx.y));
- this->input_ids = nullptr;
this->symedge = nullptr;
this->index = -1;
this->merge_to_index = -1;
@@ -833,26 +881,10 @@ CDT_state<T>::CDT_state(int num_input_verts, int num_input_edges, int num_input_
this->visit_count = 0;
}
-static bool id_in_list(const LinkNode *id_list, int id)
-{
- const LinkNode *ln;
-
- for (ln = id_list; ln != nullptr; ln = ln->next) {
- if (POINTER_AS_INT(ln->link) == id) {
- return true;
- }
- }
- return false;
-}
-
/* Is any id in (range_start, range_start+1, ... , range_end) in id_list? */
-static bool id_range_in_list(const LinkNode *id_list, int range_start, int range_end)
+static bool id_range_in_list(const blender::Set<int> &id_list, int range_start, int range_end)
{
- const LinkNode *ln;
- int id;
-
- for (ln = id_list; ln != nullptr; ln = ln->next) {
- id = POINTER_AS_INT(ln->link);
+ for (int id : id_list) {
if (id >= range_start && id <= range_end) {
return true;
}
@@ -860,19 +892,15 @@ static bool id_range_in_list(const LinkNode *id_list, int range_start, int range
return false;
}
-static void add_to_input_ids(LinkNode **dst, int input_id)
+static void add_to_input_ids(blender::Set<int> &dst, int input_id)
{
- if (!id_in_list(*dst, input_id)) {
- BLI_linklist_prepend(dst, POINTER_FROM_INT(input_id));
- }
+ dst.add(input_id);
}
-static void add_list_to_input_ids(LinkNode **dst, const LinkNode *src)
+static void add_list_to_input_ids(blender::Set<int> &dst, const blender::Set<int> &src)
{
- const LinkNode *ln;
-
- for (ln = src; ln != nullptr; ln = ln->next) {
- add_to_input_ids(dst, POINTER_AS_INT(ln->link));
+ for (int value : src) {
+ dst.add(value);
}
}
@@ -883,7 +911,7 @@ template<typename T> inline bool is_border_edge(const CDTEdge<T> *e, const CDT_s
template<typename T> inline bool is_constrained_edge(const CDTEdge<T> *e)
{
- return e->input_ids != nullptr;
+ return e->input_ids.size() > 0;
}
template<typename T> inline bool is_deleted_edge(const CDTEdge<T> *e)
@@ -979,7 +1007,7 @@ template<typename T> CDTEdge<T> *CDTArrangement<T>::add_diagonal(SymEdge<T> *s1,
for (SymEdge<T> *se = s2; se != sdiag; se = se->next) {
se->face = fnew;
}
- add_list_to_input_ids(&fnew->input_ids, fold->input_ids);
+ add_list_to_input_ids(fnew->input_ids, fold->input_ids);
return ediag;
}
@@ -1058,7 +1086,7 @@ template<typename T> CDTEdge<T> *CDTArrangement<T>::split_edge(SymEdge<T> *se, T
if (newsesym->vert->symedge == sesym) {
newsesym->vert->symedge = newsesym;
}
- add_list_to_input_ids(&e->input_ids, se->edge->input_ids);
+ add_list_to_input_ids(e->input_ids, se->edge->input_ids);
return e;
}
@@ -1880,7 +1908,7 @@ void add_edge_constraint(
SymEdge<T> *t = find_symedge_between_verts(v1, v2);
if (t != nullptr) {
/* Segment already there. */
- add_to_input_ids(&t->edge->input_ids, input_id);
+ add_to_input_ids(t->edge->input_ids, input_id);
if (r_edges != nullptr) {
BLI_linklist_append(&edge_list, t->edge);
*r_edges = edge_list.list;
@@ -2041,7 +2069,7 @@ void add_edge_constraint(
BLI_assert(cd_prev->lambda == 0.0);
BLI_assert(cd_prev->out->next->vert == cd->vert);
edge = cd_prev->out->edge;
- add_to_input_ids(&edge->input_ids, input_id);
+ add_to_input_ids(edge->input_ids, input_id);
if (r_edges != nullptr) {
BLI_linklist_append(&edge_list, edge);
}
@@ -2054,7 +2082,7 @@ void add_edge_constraint(
else {
edge = cdt_state->cdt.add_diagonal(tstart, t);
}
- add_to_input_ids(&edge->input_ids, input_id);
+ add_to_input_ids(edge->input_ids, input_id);
if (r_edges != nullptr) {
BLI_linklist_append(&edge_list, edge);
}
@@ -2132,7 +2160,7 @@ void
@@ Diff output truncated at 10240 characters. @@
More information about the Bf-blender-cvs
mailing list