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.

3 files changed, 206 insertions, 77 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;
     }
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;
 }
 
diff --git a/source/blender/blenlib/tests/BLI_delaunay_2d_test.cc b/source/blender/blenlib/tests/BLI_delaunay_2d_test.cc
index 08a3818e18f..9356201063b 100644
--- a/source/blender/blenlib/tests/BLI_delaunay_2d_test.cc
+++ b/source/blender/blenlib/tests/BLI_delaunay_2d_test.cc
@@ -241,7 +241,7 @@ template<typename T> std::ostream &operator<<(std::ostream &os, const CDT_result
   for (int i : r.edge.index_range()) {
     os << "e" << i << " = (" << r.edge[i].first << ", " << r.edge[i].second << ")\n";
     os << "  orig: ";
-    for (int j : r.edge_orig[i].size()) {
+    for (int j : r.edge_orig[i].index_range()) {
       os << r.edge_orig[i][j] << " ";
     }
     os << "\n";
@@ -797,6 +797,55 @@ template<typename T> void crosssegs_test()
   }
 }
 
+template<typename T> void cutacrosstri_test()
+{
+  /* Right triangle with horizontal segment exactly crossing in the middle. */
+  const char *spec = R"(5 1 1
+  0.0 0.0
+  1.0 0.0
+  0.0 1.0
+  0.0 0.5
+  0.5 0.5
+  3 4
+  0 1 2
+  )";
+
+  CDT_input<T> in = fill_input_from_string<T>(spec);
+  CDT_result<T> out = delaunay_2d_calc(in, CDT_FULL);
+  EXPECT_EQ(out.vert.size(), 5);
+  EXPECT_EQ(out.edge.size(), 7);
+  EXPECT_EQ(out.face.size(), 3);
+  int v0_out = get_orig_index(out.vert_orig, 0);
+  int v1_out = get_orig_index(out.vert_orig, 1);
+  int v2_out = get_orig_index(out.vert_orig, 2);
+  int v3_out = get_orig_index(out.vert_orig, 3);
+  int v4_out = get_orig_index(out.vert_orig, 4);
+  EXPECT_TRUE(v0_out != -1 && v1_out != -1 && v2_out != -1 && v3_out != -1 && v4_out != -1);
+  if (out.face.size() == 3) {
+    int e0_out = get_orig_index(out.edge_orig, 0);
+    EXPECT_NE(e0_out, -1);
+    int fe0_out = get_output_edge_index(out, v0_out, v1_out);
+    EXPECT_NE(fe0_out, -1);
+    int fe1a_out = get_output_edge_index(out, v1_out, v4_out);
+    EXPECT_NE(fe1a_out, -1);
+    int fe1b_out = get_output_edge_index(out, v4_out, v2_out);
+    EXPECT_NE(fe1b_out, -1);
+    if (fe1a_out != 0 && fe1b_out != 0) {
+      EXPECT_EQ(e0_out, get_orig_index(out.edge_orig, 0));
+      EXPECT_TRUE(out.edge_orig[fe1a_out].size() == 1 && out.edge_orig[fe1a_out][0] == 11);
+      EXPECT_TRUE(out.edge_orig[fe1b_out].size() == 1 && out.edge_orig[fe1b_out][0] == 11);
+    }
+    int e_diag = get_output_edge_index(out, v0_out, v4_out);
+    EXPECT_NE(e_diag, -1);
+    if (e_diag != -1) {
+      EXPECT_EQ(out.edge_orig[e_diag].size(), 0);
+    }
+  }
+  if (DO_DRAW) {
+    graph_draw<T>("CutAcrossTri", out.vert, out.edge, out.face);
+  }
+}
+
 template<typename T> void diamondcross_test()
 {
   /* Diamond with constraint edge from top to bottom.  Some dup verts. */
@@ -1470,6 +1519,11 @@ TEST(delaunay_d, CrossSegs)
   crosssegs_test<double>();
 }
 
+TEST(delaunay_d, CutAcrossTri)
+{
+  cutacrosstri_test<double>();
+}
+
 TEST(delaunay_d, DiamondCross)
 {
   diamondcross_test<double>();
@@ -1610,6 +1664,11 @@ TEST(delaunay_m, CrossSegs)
   crosssegs_test<mpq_class>();
 }
 
+TEST(delaunay_m, CutAcrossTri)
+{
+  cutacrosstri_test<mpq_class>();
+}
+
 TEST(delaunay_m, DiamondCross)
 {
   diamondcross_test<mpq_class>();
@@ -1876,6 +1935,23 @@ TEST(delaunay_d, TextB10_10_10)
   text_test<double>(10, 10, 10, CDT_INSIDE_WITH_HOLES);
 }
 
+#  ifdef WITH_GMP
+TEST(delaunay_m, TextB10)
+{
+  text_test<mpq_class>(10, 1, 1, CDT_INSIDE_WITH_HOLES);
+}
+
+TEST(delaunay_m, TextB200)
+{
+  text_test<mpq_class>(200, 1, 1, CDT_INSIDE_WITH_HOLES);
+}
+
+TEST(delaunay_m, TextB10_10_10)
+{
+  text_test<mpq_class>(10, 10, 10, CDT_INSIDE_WITH_HOLES);
+}
+#  endif
+
 #endif
 
 #if DO_RANDOM_TESTS