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.

1 files changed, 84 insertions, 56 deletions

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 add_face_ids(
       continue;
     }
     face->visit_index = visit;
-    add_to_input_ids(&face->input_ids, face_id);
+    add_to_input_ids(face->input_ids, face_id);
     SymEdge<T> *se_start = se;
     for (se = se->next; se != se_start; se = se->next) {
       if (!id_range_in_list(se->edge->input_ids, fedge_start, fedge_end)) {
@@ -2349,7 +2377,7 @@ template<typename T> void remove_non_constraint_edges_leave_valid_bmesh(CDT_stat
     CDTFace<T> *fleft = se->face;
     CDTFace<T> *fright = sym(se)->face;
     if (fleft != cdt->outer_face && fright != cdt->outer_face &&
-        (fleft->input_ids != nullptr || fright->input_ids != nullptr)) {
+        (fleft->input_ids.size() > 0 || fright->input_ids.size() > 0)) {
       /* Is there another #SymEdge with same left and right faces?
        * Or is there a vertex not part of e touching the same left and right faces? */
       for (SymEdge<T> *se2 = se->next; dissolve && se2 != se; se2 = se2->next) {
@@ -2632,7 +2660,7 @@ CDT_result<T> get_cdt_output(CDT_state<T> *cdt_state,
       CDTVert<T> *v = cdt->verts[i];
       if (v->merge_to_index != -1) {
         if (i < cdt_state->input_vert_tot) {
-          add_to_input_ids(&cdt->verts[v->merge_to_index]->input_ids, i);
+          add_to_input_ids(cdt->verts[v->merge_to_index]->input_ids, i);
         }
         vert_to_output_map[i] = vert_to_output_map[v->merge_to_index];
       }
@@ -2648,8 +2676,8 @@ CDT_result<T> get_cdt_output(CDT_state<T> *cdt_state,
       if (i < cdt_state->input_vert_tot) {
         result.vert_orig[i_out].append(i);
       }
-      for (LinkNode *ln = v->input_ids; ln; ln = ln->next) {
-        result.vert_orig[i_out].append(POINTER_AS_INT(ln->link));
+      for (int vert : v->input_ids) {
+        result.vert_orig[i_out].append(vert);
       }
       ++i_out;
     }
@@ -2667,8 +2695,8 @@ CDT_result<T> get_cdt_output(CDT_state<T> *cdt_state,
       int vo1 = vert_to_output_map[e->symedges[0].vert->index];
       int vo2 = vert_to_output_map[e->symedges[1].vert->index];
       result.edge[e_out] = std::pair<int, int>(vo1, vo2);
-      for (LinkNode *ln = e->input_ids; ln; ln = ln->next) {
-        result.edge_orig[e_out].append(POINTER_AS_INT(ln->link));
+      for (int edge : e->input_ids) {
+        result.edge_orig[e_out].append(edge);
       }
       ++e_out;
     }
@@ -2690,8 +2718,8 @@ CDT_result<T> get_cdt_output(CDT_state<T> *cdt_state,
         result.face[f_out].append(vert_to_output_map[se->vert->index]);
         se = se->next;
       } while (se != se_start);
-      for (LinkNode *ln = f->input_ids; ln; ln = ln->next) {
-        result.face_orig[f_out].append(POINTER_AS_INT(ln->link));
+      for (int face : f->input_ids) {
+        result.face_orig[f_out].append(face);
       }
       ++f_out;
     }