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.

1 files changed, 363 insertions, 9 deletions

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 {