Delaunay add support for detecting and removing holes from output.

Adds two new output modes to the CDT api which detect and remove
holes. A hole is a face from which a ray shot to the outside
intersects an even number of constraint edges, except we don't
count constraint edges in the same connected region of faces,
where a region is connected via non-constraint edges.

These modes are useful for filling in outlines meant to represent
text characters and the like.

Original patch was from Erik Abrahamsson, modified by me to work
with the "valid Bmesh" output type too. I also added tests
for the new modes.

3 files changed, 518 insertions, 15 deletions

diff --git a/source/blender/blenlib/BLI_delaunay_2d.h b/source/blender/blenlib/BLI_delaunay_2d.h
index e91726991ca..d42bd6af637 100644
--- a/source/blender/blenlib/BLI_delaunay_2d.h
+++ b/source/blender/blenlib/BLI_delaunay_2d.h
@@ -178,6 +178,8 @@ typedef enum CDT_output_type {
   CDT_FULL,
   /** All triangles fully enclosed by constraint edges or faces. */
   CDT_INSIDE,
+  /** Like previous, but detect holes and omit those from output. */
+  CDT_INSIDE_WITH_HOLES,
   /** Only point, edge, and face constraints, and their intersections. */
   CDT_CONSTRAINTS,
   /**
@@ -186,7 +188,9 @@ typedef enum CDT_output_type {
    * #BMesh faces in Blender: that is,
    * no vertex appears more than once and no isolated holes in faces.
    */
-  CDT_CONSTRAINTS_VALID_BMESH
+  CDT_CONSTRAINTS_VALID_BMESH,
+  /** Like previous, but detect holes and omit those from output. */
+  CDT_CONSTRAINTS_VALID_BMESH_WITH_HOLES,
 } CDT_output_type;
 
 /**
diff --git a/source/blender/blenlib/intern/delaunay_2d.cc b/source/blender/blenlib/intern/delaunay_2d.cc
index 9444d1a29cb..eb3e64c49e6 100644
--- a/source/blender/blenlib/intern/delaunay_2d.cc
+++ b/source/blender/blenlib/intern/delaunay_2d.cc
@@ -226,6 +226,8 @@ template<typename Arith_t> struct CDTFace {
   int visit_index{0};
   /** Marks this face no longer used. */
   bool deleted{false};
+  /** Marks this face as part of a hole. */
+  bool hole{false};
 
   CDTFace() = default;
 };
@@ -481,9 +483,9 @@ template<typename T> void cdt_draw(const std::string &label, const CDTArrangemen
  * This is just for developer debugging anyway, and should never be called in production Blender.
  */
 #  ifdef _WIN32
-  const char *drawfile = "./debug_draw.html";
+  const char *drawfile = "./cdt_debug_draw.html";
 #  else
-  const char *drawfile = "/tmp/debug_draw.html";
+  const char *drawfile = "/tmp/cdt_debug_draw.html";
 #  endif
   constexpr int max_draw_width = 1800;
   constexpr int max_draw_height = 1600;
@@ -2364,9 +2366,6 @@ template<typename T> void remove_non_constraint_edges_leave_valid_bmesh(CDT_stat
 
 template<typename T> void remove_outer_edges_until_constraints(CDT_state<T> *cdt_state)
 {
-  // LinkNode *fstack = NULL;
-  // SymEdge *se, *se_start;
-  // CDTFace *f, *fsym;
   int visit = ++cdt_state->visit_count;
 
   cdt_state->cdt.outer_face->visit_index = visit;
@@ -2415,6 +2414,137 @@ template<typename T> void remove_outer_edges_until_constraints(CDT_state<T> *cdt
   }
 }
 
+template<typename T> void remove_faces_in_holes(CDT_state<T> *cdt_state)
+{
+  CDTArrangement<T> *cdt = &cdt_state->cdt;
+  for (int i : cdt->faces.index_range()) {
+    CDTFace<T> *f = cdt->faces[i];
+    if (!f->deleted && f->hole) {
+      f->deleted = true;
+      SymEdge<T> *se = f->symedge;
+      SymEdge<T> *se_start = se;
+      SymEdge<T> *se_next = nullptr;
+      do {
+        BLI_assert(se != nullptr);
+        se_next = se->next; /* In case we delete this edge. */
+        if (se->edge && !is_constrained_edge(se->edge)) {
+          /* Invalidate one half of this edge. The other has will be or has been
+           * handled with the adjacent triangle is processed: it should be part of the same hole.
+           */
+          se->next = nullptr;
+        }
+        se = se_next;
+      } while (se != se_start);
+    }
+  }
+}
+
+/**
+ * Set the hole member of each CDTFace to true for each face that is detected to be part of a
+ * hole. A hole face is define as one for which, when a ray is shot from a point inside the face
+ * to infinity, it crosses an even number of constraint edges. We'll choose a ray direction that
+ * is extremely unlikely to exactly superimpose some edge, so avoiding the need to be careful
+ * about such overlaps.
+ *
+ * To improve performance, we gather together faces that should have the same winding number, and
+ * only shoot rays once.
+ */
+template<typename T> void detect_holes(CDT_state<T> *cdt_state)
+{
+  CDTArrangement<T> *cdt = &cdt_state->cdt;
+
+  /* Make it so that each face with the same visit_index is connected through a path of
+   * non-constraint edges. */
+  Vector<CDTFace<T> *> fstack;
+  Vector<CDTFace<T> *> region_rep_face;
+  for (int i : cdt->faces.index_range()) {
+    cdt->faces[i]->visit_index = -1;
+  }
+  int cur_region = -1;
+  cdt->outer_face->visit_index = -2; /* Don't visit this one. */
+  for (int i : cdt->faces.index_range()) {
+    CDTFace<T> *f = cdt->faces[i];
+    if (!f->deleted && f->symedge && f->visit_index == -1) {
+      fstack.append(f);
+      ++cur_region;
+      region_rep_face.append(f);
+      while (!fstack.is_empty()) {
+        CDTFace<T> *f = fstack.pop_last();
+        if (f->visit_index != -1) {
+          continue;
+        }
+        f->visit_index = cur_region;
+        SymEdge<T> *se_start = f->symedge;
+        SymEdge<T> *se = se_start;
+        do {
+          if (se->edge && !is_constrained_edge(se->edge)) {
+            CDTFace<T> *fsym = sym(se)->face;
+            if (fsym && !fsym->deleted && fsym->visit_index == -1) {
+              fstack.append(fsym);
+            }
+          }
+          se = se->next;
+        } while (se != se_start);
+      }
+    }
+  }
+  cdt_state->visit_count = ++cur_region; /* Good start for next use of visit_count. */
+
+  /* Now get hole status for each region_rep_face. */
+
+  /* Pick a ray end almost certain to be outside everything and in direction
+   * that is unlikely to hit a vertex or overlap an edge exactly. */
+  FatCo<T> ray_end;
+  ray_end.exact = vec2<T>(123456, 654321);
+  for (int i : region_rep_face.index_range()) {
+    CDTFace<T> *f = region_rep_face[i];
+    FatCo<T> mid;
+    mid.exact[0] = (f->symedge->vert->co.exact[0] + f->symedge->next->vert->co.exact[0] +
+                    f->symedge->next->next->vert->co.exact[0]) /
+                   3;
+    mid.exact[1] = (f->symedge->vert->co.exact[1] + f->symedge->next->vert->co.exact[1] +
+                    f->symedge->next->next->vert->co.exact[1]) /
+                   3;
+    int hits = 0;
+    /* TODO: Use CDT data structure here to greatly reduce search for intersections! */
+    for (const CDTEdge<T> *e : cdt->edges) {
+      if (!is_deleted_edge(e) && is_constrained_edge(e)) {
+        if (e->symedges[0].face->visit_index == e->symedges[1].face->visit_index) {
+          continue; /* Don't count hits on edges between faces in same region. */
+        }
+        auto isect = vec2<T>::isect_seg_seg(ray_end.exact,
+                                            mid.exact,
+                                            e->symedges[0].vert->co.exact,
+                                            e->symedges[1].vert->co.exact);
+        switch (isect.kind) {
+          case vec2<T>::isect_result::LINE_LINE_CROSS: {
+            hits++;
+            break;
+          }
+          case vec2<T>::isect_result::LINE_LINE_EXACT:
+          case vec2<T>::isect_result::LINE_LINE_NONE:
+          case vec2<T>::isect_result::LINE_LINE_COLINEAR:
+            break;
+        }
+      }
+    }
+    f->hole = (hits % 2) == 0;
+  }
+
+  /* Finally, propagate hole status to all holes of a region. */
+  for (int i : cdt->faces.index_range()) {
+    CDTFace<T> *f = cdt->faces[i];
+    int region = f->visit_index;
+    if (region < 0) {
+      continue;
+    }
+    CDTFace<T> *f_region_rep = region_rep_face[region];
+    if (i >= 0) {
+      f->hole = f_region_rep->hole;
+    }
+  }
+}
+
 /**
  * Remove edges and merge faces to get desired output, as per options.
  * \note the cdt cannot be further changed after this.
@@ -2439,6 +2569,13 @@ void prepare_cdt_for_output(CDT_state<T> *cdt_state, const CDT_output_type outpu
     }
   }
 
+  bool need_holes = output_type == CDT_INSIDE_WITH_HOLES ||
+                    output_type == CDT_CONSTRAINTS_VALID_BMESH_WITH_HOLES;
+
+  if (need_holes) {
+    detect_holes(cdt_state);
+  }
+
   if (output_type == CDT_CONSTRAINTS) {
     remove_non_constraint_edges(cdt_state);
   }
@@ -2448,6 +2585,14 @@ void prepare_cdt_for_output(CDT_state<T> *cdt_state, const CDT_output_type outpu
   else if (output_type == CDT_INSIDE) {
     remove_outer_edges_until_constraints(cdt_state);
   }
+  else if (output_type == CDT_INSIDE_WITH_HOLES) {
+    remove_outer_edges_until_constraints(cdt_state);
+    remove_faces_in_holes(cdt_state);
+  }
+  else if (output_type == CDT_CONSTRAINTS_VALID_BMESH_WITH_HOLES) {
+    remove_non_constraint_edges_leave_valid_bmesh(cdt_state);
+    remove_faces_in_holes(cdt_state);
+  }
 }
 
 template<typename T>
diff --git a/source/blender/blenlib/tests/BLI_delaunay_2d_test.cc b/source/blender/blenlib/tests/BLI_delaunay_2d_test.cc
index d00e8bf55fd..59c4be6d952 100644
--- a/source/blender/blenlib/tests/BLI_delaunay_2d_test.cc
+++ b/source/blender/blenlib/tests/BLI_delaunay_2d_test.cc
@@ -17,6 +17,7 @@ extern "C" {
 
 #define DO_CPP_TESTS 1
 #define DO_C_TESTS 1
+#define DO_TEXT_TESTS 0
 #define DO_RANDOM_TESTS 0
 
 #include "BLI_array.hh"
@@ -267,7 +268,7 @@ template<typename T>
 void graph_draw(const std::string &label,
                 const Array<vec2<T>> &verts,
                 const Array<std::pair<int, int>> &edges,
-                const Array<Vector<int>> &UNUSED(faces))
+                const Array<Vector<int>> &faces)
 {
   /* Would like to use BKE_tempdir_base() here, but that brings in dependence on kernel library.
    * This is just for developer debugging anyway, and should never be called in production Blender.
@@ -281,7 +282,7 @@ void graph_draw(const std::string &label,
   constexpr int max_draw_height = 1000;
   constexpr int thin_line = 1;
   constexpr int vert_radius = 3;
-  constexpr bool draw_vert_labels = true;
+  constexpr bool draw_vert_labels = false;
   constexpr bool draw_edge_labels = false;
 
   if (verts.size() == 0) {
@@ -339,6 +340,15 @@ void graph_draw(const std::string &label,
        "xml:space=\"preserve\"\n"
     << "width=\"" << view_width << "\" height=\"" << view_height << "\">n";
 
+  for (const Vector<int> &fverts : faces) {
+    f << "<polygon fill=\"azure\" stroke=\"none\"\n  points=\"";
+    for (int vi : fverts) {
+      const vec2<T> &co = verts[vi];
+      f << SX(co[0]) << "," << SY(co[1]) << " ";
+    }
+    f << "\"\n  />\n";
+  }
+
   for (const std::pair<int, int> &e : edges) {
     const vec2<T> &uco = verts[e.first];
     const vec2<T> &vco = verts[e.second];
@@ -642,6 +652,110 @@ template<typename T> void lineinsquare_test()
   if (DO_DRAW) {
     graph_draw<T>("LineInSquare - constraints", out2.vert, out2.edge, out2.face);
   }
+  CDT_result<T> out3 = delaunay_2d_calc(in, CDT_INSIDE_WITH_HOLES);
+  EXPECT_EQ(out3.vert.size(), 6);
+  EXPECT_EQ(out3.face.size(), 6);
+  if (DO_DRAW) {
+    graph_draw<T>("LineInSquare - inside with holes", out3.vert, out3.edge, out3.face);
+  }
+  CDT_result<T> out4 = delaunay_2d_calc(in, CDT_CONSTRAINTS_VALID_BMESH_WITH_HOLES);
+  EXPECT_EQ(out4.vert.size(), 6);
+  EXPECT_EQ(out4.face.size(), 2);
+  if (DO_DRAW) {
+    graph_draw<T>("LineInSquare - valid bmesh with holes", out4.vert, out4.edge, out4.face);
+  }
+}
+
+template<typename T> void lineholeinsquare_test()
+{
+  const char *spec = R"(10 1 2
+  -0.5 -0.5
+  0.5 -0.5
+  -0.5 0.5
+  0.5 0.5
+  -0.25 0.0
+  0.25 0.0
+  -0.4 -0.4
+  0.4 -0.4
+  0.4 -0.3
+  -0.4 -0.3
+  4 5
+  0 1 3 2
+  6 7 8 9
+  )";
+
+  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(), 10);
+  EXPECT_EQ(out.face.size(), 14);
+  if (DO_DRAW) {
+    graph_draw<T>("LineHoleInSquare - full", out.vert, out.edge, out.face);
+  }
+  CDT_result<T> out2 = delaunay_2d_calc(in, CDT_CONSTRAINTS);
+  EXPECT_EQ(out2.vert.size(), 10);
+  EXPECT_EQ(out2.face.size(), 2);
+  if (DO_DRAW) {
+    graph_draw<T>("LineHoleInSquare - constraints", out2.vert, out2.edge, out2.face);
+  }
+  CDT_result<T> out3 = delaunay_2d_calc(in, CDT_INSIDE_WITH_HOLES);
+  EXPECT_EQ(out3.vert.size(), 10);
+  EXPECT_EQ(out3.face.size(), 12);
+  if (DO_DRAW) {
+    graph_draw<T>("LineHoleInSquare - inside with holes", out3.vert, out3.edge, out3.face);
+  }
+  CDT_result<T> out4 = delaunay_2d_calc(in, CDT_CONSTRAINTS_VALID_BMESH_WITH_HOLES);
+  EXPECT_EQ(out4.vert.size(), 10);
+  EXPECT_EQ(out4.face.size(), 2);
+  if (DO_DRAW) {
+    graph_draw<T>("LineHoleInSquare - valid bmesh with holes", out4.vert, out4.edge, out4.face);
+  }
+}
+
+template<typename T> void nestedholes_test()
+{
+  const char *spec = R"(12 0 3
+  -0.5 -0.5
+  0.5 -0.5
+  -0.5 0.5
+  0.5 0.5
+  -0.4 -0.4
+  0.4 -0.4
+  0.4 0.4
+  -0.4 0.4
+  -0.2 -0.2
+  0.2 -0.2
+  0.2 0.2
+  -0.2 0.2
+  0 1 3 2
+  4 7 6 5
+  8 9 10 11
+  )";
+
+  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(), 12);
+  EXPECT_EQ(out.face.size(), 18);
+  if (DO_DRAW) {
+    graph_draw<T>("NestedHoles - full", out.vert, out.edge, out.face);
+  }
+  CDT_result<T> out2 = delaunay_2d_calc(in, CDT_CONSTRAINTS);
+  EXPECT_EQ(out2.vert.size(), 12);
+  EXPECT_EQ(out2.face.size(), 3);
+  if (DO_DRAW) {
+    graph_draw<T>("NestedHoles - constraints", out2.vert, out2.edge, out2.face);
+  }
+  CDT_result<T> out3 = delaunay_2d_calc(in, CDT_INSIDE_WITH_HOLES);
+  EXPECT_EQ(out3.vert.size(), 12);
+  EXPECT_EQ(out3.face.size(), 10);
+  if (DO_DRAW) {
+    graph_draw<T>("NestedHoles - inside with holes", out3.vert, out3.edge, out3.face);
+  }
+  CDT_result<T> out4 = delaunay_2d_calc(in, CDT_CONSTRAINTS_VALID_BMESH_WITH_HOLES);
+  EXPECT_EQ(out4.vert.size(), 12);
+  EXPECT_EQ(out4.face.size(), 3);
+  if (DO_DRAW) {
+    graph_draw<T>("NestedHoles - valid bmesh with holes", out4.vert, out4.edge, out4.face);
+  }
 }
 
 template<typename T> void crosssegs_test()
@@ -1025,16 +1139,28 @@ template<typename T> void overlapfaces_test()
     graph_draw<T>("OverlapFaces - inside", out2.vert, out2.edge, out2.face);
   }
 
-  CDT_result<T> out3 = delaunay_2d_calc(in, CDT_CONSTRAINTS);
-  EXPECT_EQ(out3.face.size(), 4);
+  CDT_result<T> out3 = delaunay_2d_calc(in, CDT_INSIDE_WITH_HOLES);
+  EXPECT_EQ(out3.face.size(), 14);
+  if (DO_DRAW) {
+    graph_draw<T>("OverlapFaces - inside with holes", out3.vert, out3.edge, out3.face);
+  }
+
+  CDT_result<T> out4 = delaunay_2d_calc(in, CDT_CONSTRAINTS);
+  EXPECT_EQ(out4.face.size(), 4);
   if (DO_DRAW) {
-    graph_draw<T>("OverlapFaces - constraints", out3.vert, out3.edge, out3.face);
+    graph_draw<T>("OverlapFaces - constraints", out4.vert, out4.edge, out4.face);
   }
 
-  CDT_result<T> out4 = delaunay_2d_calc(in, CDT_CONSTRAINTS_VALID_BMESH);
-  EXPECT_EQ(out4.face.size(), 5);
+  CDT_result<T> out5 = delaunay_2d_calc(in, CDT_CONSTRAINTS_VALID_BMESH);
+  EXPECT_EQ(out5.face.size(), 5);
   if (DO_DRAW) {
-    graph_draw<T>("OverlapFaces - valid bmesh", out4.vert, out4.edge, out4.face);
+    graph_draw<T>("OverlapFaces - valid bmesh", out5.vert, out5.edge, out5.face);
+  }
+
+  CDT_result<T> out6 = delaunay_2d_calc(in, CDT_CONSTRAINTS_VALID_BMESH_WITH_HOLES);
+  EXPECT_EQ(out6.face.size(), 3);
+  if (DO_DRAW) {
+    graph_draw<T>("OverlapFaces - valid bmesh with holes", out6.vert, out6.edge, out6.face);
   }
 }
 
@@ -1246,6 +1372,34 @@ template<typename T> void repeattri_test()
   }
 }
 
+template<typename T> void square_o_test()
+{
+  const char *spec = R"(8 0 2
+  0.0 0.0
+  1.0 0.0
+  1.0 1.0
+  0.0 1.0
+  0.2 0.2
+  0.2 0.8
+  0.8 0.8
+  0.8 0.2
+  0 1 2 3
+  4 5 6 7
+  )";
+  CDT_input<T> in = fill_input_from_string<T>(spec);
+  CDT_result<T> out1 = delaunay_2d_calc(in, CDT_INSIDE_WITH_HOLES);
+  EXPECT_EQ(out1.face.size(), 8);
+  if (DO_DRAW) {
+    graph_draw<T>("Square O - inside with holes", out1.vert, out1.edge, out1.face);
+  }
+
+  CDT_result<T> out2 = delaunay_2d_calc(in, CDT_CONSTRAINTS_VALID_BMESH_WITH_HOLES);
+  EXPECT_EQ(out2.face.size(), 2);
+  if (DO_DRAW) {
+    graph_draw<T>("Square O - valid bmesh with holes", out2.vert, out2.edge, out2.face);
+  }
+}
+
 TEST(delaunay_d, Empty)
 {
   empty_test<double>();
@@ -1301,6 +1455,16 @@ TEST(delaunay_d, LineInSquare)
   lineinsquare_test<double>();
 }
 
+TEST(delaunay_d, LineHoleInSquare)
+{
+  lineholeinsquare_test<double>();
+}
+
+TEST(delaunay_d, NestedHoles)
+{
+  nestedholes_test<double>();
+}
+
 TEST(delaunay_d, CrossSegs)
 {
   crosssegs_test<double>();
@@ -1371,6 +1535,11 @@ TEST(delaunay_d, RepeatTri)
   repeattri_test<double>();
 }
 
+TEST(delaunay_d, SquareO)
+{
+  square_o_test<double>();
+}
+
 #  ifdef WITH_GMP
 TEST(delaunay_m, Empty)
 {
@@ -1426,6 +1595,16 @@ TEST(delaunay_m, LineInSquare)
   lineinsquare_test<mpq_class>();
 }
 
+TEST(delaunay_m, LineHoleInSquare)
+{
+  lineholeinsquare_test<mpq_class>();
+}
+
+TEST(delaunay_m, NestedHoles)
+{
+  nestedholes_test<mpq_class>();
+}
+
 TEST(delaunay_m, CrossSegs)
 {
   crosssegs_test<mpq_class>();
@@ -1496,7 +1675,6 @@ TEST(delaunay_m, RepeatTri)
   repeattri_test<mpq_class>();
 }
 #  endif
-
 #endif
 
 #if DO_C_TESTS
@@ -1524,6 +1702,182 @@ TEST(delaunay_d, CintTwoFace)
 }
 #endif
 
+#if DO_TEXT_TESTS
+template<typename T>
+void text_test(int num_arc_points, int num_lets_per_line, int num_lines, CDT_output_type otype)
+{
+  constexpr bool print_timing = true;
+  /*
+   * Make something like a letter B:
+   *
+   *    4------------3
+   *    |              )
+   *    |  12--11       )
+   *    |  |     ) a3    ) a1
+   *    |  9---10       )
+   *    |              )
+   *    |            2
+   *    |              )
+   *    |  8----7       )
+   *    |  |     ) a2    ) a0
+   *    |  5----6       )
+   *    |              )
+   *    0------------1
+   *
+   * Where the numbers are the first 13 vertices, and the rest of
+   * the vertices are in arcs a0, a1, a2, a3, each of which have
+   * num_arc_points per arc in them.
+   */
+
+  const char *b_before_arcs = R"(13 0 3
+  0.0 0.0
+  1.0 0.0
+  1.0 1.5
+  1.0 3.0
+  0.0 3.0
+  0.2 0.2
+  0.6 0.2
+  0.6 1.4
+  0.2 1.4
+  0.2 1.6
+  0.6 1.6
+  0.6 2.8
+  0.2 2.8
+  3 4 0 1 2
+  6 5 8 7
+  10 9 12 11
+  )";
+
+  CDT_input<T> b_before_arcs_in = fill_input_from_string<T>(b_before_arcs);
+  constexpr int narcs = 4;
+  int b_npts = b_before_arcs_in.vert.size() + narcs * num_arc_points;
+  constexpr int b_nfaces = 3;
+  Array<vec2<T>> b_vert(b_npts);
+  Array<Vector<int>> b_face(b_nfaces);
+  std::copy(b_before_arcs_in.vert.begin(), b_before_arcs_in.vert.end(), b_vert.begin());
+  std::copy(b_before_arcs_in.face.begin(), b_before_arcs_in.face.end(), b_face.begin());
+  if (num_arc_points > 0) {
+    b_face[0].pop_last();  // We'll add center point back between arcs for outer face.
+    for (int arc = 0; arc < narcs; ++arc) {
+      int arc_origin_vert;
+      int arc_terminal_vert;
+      bool ccw;
+      switch (arc) {
+        case 0:
+          arc_origin_vert = 1;
+          arc_terminal_vert = 2;
+          ccw = true;
+          break;
+        case 1:
+          arc_origin_vert = 2;
+          arc_terminal_vert = 3;
+          ccw = true;
+          break;
+        case 2:
+          arc_origin_vert = 7;
+          arc_terminal_vert = 6;
+          ccw = false;
+          break;
+        case 3:
+          arc_origin_vert = 11;
+          arc_terminal_vert = 10;
+          ccw = false;
+          break;
+        default:
+          BLI_assert(false);
+      }
+      vec2<T> start_co = b_vert[arc_origin_vert];
+      vec2<T> end_co = b_vert[arc_terminal_vert];
+      vec2<T> center_co = 0.5 * (start_co + end_co);
+      BLI_assert(start_co[0] == end_co[2]);
+      double radius = abs(math_to_double<T>(end_co[1] - center_co[1]));
+      double angle_delta = M_PI / (num_arc_points + 1);
+      int start_vert = b_before_arcs_in.vert.size() + arc * num_arc_points;
+      Vector<int> &face = b_face[(arc <= 1) ? 0 : arc - 1];
+      for (int i = 0; i < num_arc_points; ++i) {
+        vec2<T> delta;
+        float ang = ccw ? (-M_PI_2 + (i + 1) * angle_delta) : (M_PI_2 - (i + 1) * angle_delta);
+        delta[0] = T(radius * cos(ang));
+        delta[1] = T(radius * sin(ang));
+        b_vert[start_vert + i] = center_co + delta;
+        face.append(start_vert + i);
+      }
+      if (arc == 0) {
+        face.append(arc_terminal_vert);
+      }
+    }
+  }
+
+  CDT_input<T> in;
+  int tot_instances = num_lets_per_line * num_lines;
+  if (tot_instances == 1) {
+    in.vert = b_vert;
+    in.face = b_face;
+  }
+  else {
+    in.vert = Array<vec2<T>>(tot_instances * b_vert.size());
+    in.face = Array<Vector<int>>(tot_instances * b_face.size());
+    T cur_x = T(0);
+    T cur_y = T(0);
+    T delta_x = T(2);
+    T delta_y = T(3.25);
+    int instance = 0;
+    for (int line = 0; line < num_lines; ++line) {
+      for (int let = 0; let < num_lets_per_line; ++let) {
+        vec2<T> co_offset(cur_x, cur_y);
+        int in_v_offset = instance * b_vert.size();
+        for (int v = 0; v < b_vert.size(); ++v) {
+          in.vert[in_v_offset + v] = b_vert[v] + co_offset;
+        }
+        int in_f_offset = instance * b_face.size();
+        for (int f : b_face.index_range()) {
+          for (int fv : b_face[f]) {
+            in.face[in_f_offset + f].append(in_v_offset + fv);
+          }
+        }
+        cur_x += delta_x;
+        ++instance;
+      }
+      cur_y += delta_y;
+      cur_x = T(0);
+    }
+  }
+  in.epsilon = b_before_arcs_in.epsilon;
+  double tstart = PIL_check_seconds_timer();
+  CDT_result<T> out = delaunay_2d_calc(in, otype);
+  double tend = PIL_check_seconds_timer();
+  if (print_timing) {
+    std::cout << "time = " << tend - tstart << "\n";
+  }
+  if (DO_DRAW) {
+    std::string label = "Text arcpts=" + std::to_string(num_arc_points);
+    if (num_lets_per_line > 1) {
+      label += " linelen=" + std::to_string(num_lets_per_line);
+    }
+    if (num_lines > 1) {
+      label += " lines=" + std::to_string(num_lines);
+    }
+    graph_draw<T>(label, out.vert, out.edge, out.face);
+  }
+}
+
+TEST(delaunay_d, TextB10)
+{
+  text_test<double>(10, 1, 1, CDT_INSIDE_WITH_HOLES);
+}
+
+TEST(delaunay_d, TextB200)
+{
+  text_test<double>(200, 1, 1, CDT_INSIDE_WITH_HOLES);
+}
+
+TEST(delaunay_d, TextB10_10_10)
+{
+  text_test<double>(10, 10, 10, CDT_INSIDE_WITH_HOLES);
+}
+
+#endif
+
 #if DO_RANDOM_TESTS
 
 enum {