Fix T87682 Boolean Exact crash.

The triangulator I made (using CDT) doesn't work if the face
self-intersects. Fall back to the polyfill triangulator when
that happens.

1 files changed, 22 insertions, 9 deletions

diff --git a/source/blender/blenlib/intern/mesh_boolean.cc b/source/blender/blenlib/intern/mesh_boolean.cc
index 51b88e80600..16f2220af4c 100644
--- a/source/blender/blenlib/intern/mesh_boolean.cc
+++ b/source/blender/blenlib/intern/mesh_boolean.cc
@@ -2684,12 +2684,6 @@ static IMesh raycast_patches_boolean(const IMesh &tm,
   return ans;
 }
 
-#  ifdef fast_triangulate
-/* This code uses Blenlib's BLI_polyfill_calc to do triangulation, and is therefore quite fast.
- * Unfortunately, it can product degenerate triangles that mesh_intersect will remove, leaving
- * the mesh non-PWN.
- */
-
 /**
  * Tessellate face f into triangles and return an array of `const Face *`
  * giving that triangulation. Intended to be used when f has > 4 vertices.
@@ -2697,8 +2691,12 @@ static IMesh raycast_patches_boolean(const IMesh &tm,
  * each edge in the output triangles either matches the original edge
  * for the (identical) edge of f, or else is -1. So diagonals added
  * for triangulation can later be identified by having #NO_INDEX for original.
+ *
+ * This code uses Blenlib's BLI_polyfill_calc to do triangulation, and is therefore quite fast.
+ * Unfortunately, it can product degenerate triangles that mesh_intersect will remove, leaving
+ * the mesh non-PWN.
  */
-static Array<Face *> triangulate_poly(Face *f, IMeshArena *arena)
+static Array<Face *> polyfill_triangulate_poly(Face *f, IMeshArena *arena)
 {
   /* Similar to loop body in BM_mesh_calc_tesselation. */
   int flen = f->size();
@@ -2751,7 +2749,7 @@ static Array<Face *> triangulate_poly(Face *f, IMeshArena *arena)
 
   return ans;
 }
-#  else
+
 /**
  * Which CDT output edge index is for an edge between output verts
  * v1 and v2 (in either order)?
@@ -2775,6 +2773,13 @@ static int find_cdt_edge(const CDT_result<mpq_class> &cdt_out, int v1, int v2)
  * each edge in the output triangles either matches the original edge
  * for the (identical) edge of f, or else is -1. So diagonals added
  * for triangulation can later be identified by having #NO_INDEX for original.
+ *
+ * The method used is to use the CDT triangulation. Usually that triangulation
+ * will only use the existing vertices. However, if the face self-intersects
+ * then the CDT triangulation will include the intersection points.
+ * If this happens, we use the polyfill triangulator instead. We don't
+ * use the polyfill triangulator by default because it can create degenerate
+ * triangles (which we can handle but they'll create non-manifold meshes).
  */
 static Array<Face *> triangulate_poly(Face *f, IMeshArena *arena)
 {
@@ -2816,10 +2821,19 @@ static Array<Face *> triangulate_poly(Face *f, IMeshArena *arena)
     int i_v_out[3];
     const Vert *v[3];
     int eo[3];
+    bool needs_steiner = false;
     for (int i = 0; i < 3; ++i) {
       i_v_out[i] = cdt_out.face[t][i];
+      if (cdt_out.vert_orig[i_v_out[i]].size() == 0) {
+        needs_steiner = true;
+        break;
+      }
       v[i] = (*f)[cdt_out.vert_orig[i_v_out[i]][0]];
     }
+    if (needs_steiner) {
+      /* Fall back on the polyfill triangulator. */
+      return polyfill_triangulate_poly(f, arena);
+    }
     for (int i = 0; i < 3; ++i) {
       int e_out = find_cdt_edge(cdt_out, i_v_out[i], i_v_out[(i + 1) % 3]);
       BLI_assert(e_out != -1);
@@ -2842,7 +2856,6 @@ static Array<Face *> triangulate_poly(Face *f, IMeshArena *arena)
   }
   return ans;
 }
-#  endif
 
 /**
  * Return an #IMesh that is a triangulation of a mesh with general