[Bf-blender-cvs] [9d25418a52c] master: Fix T95901: Crash in Fill curve (set to N-gon)

[Howard Trickey]

Commit: 9d25418a52c4aef9210a11a0b4e2739ab6616e94
Author: Howard Trickey
Date:   Sat Mar 26 10:47:09 2022 -0400
Branches: master
https://developer.blender.org/rB9d25418a52c4aef9210a11a0b4e2739ab6616e94

Fix T95901: Crash in Fill curve (set to N-gon)

The code that eats away faces until you find input faces in
the Constrained Delaunay Triangulation goes too far and crashes
when there are no input faces. In the test case there were input
faces but they only had two vertices, so were all ignored.

===================================================================

M	source/blender/blenlib/intern/delaunay_2d.cc

===================================================================

diff --git a/source/blender/blenlib/intern/delaunay_2d.cc b/source/blender/blenlib/intern/delaunay_2d.cc
index e6164c98402..3039b72128d 100644
--- a/source/blender/blenlib/intern/delaunay_2d.cc
+++ b/source/blender/blenlib/intern/delaunay_2d.cc
@@ -2188,17 +2188,19 @@ static int power_of_10_greater_equal_to(int x)
 }
 
 /**
-   Incrementally each edge of each input face as an edge constraint.
+ * Incrementally each edge of each input face as an edge constraint.
  * The code will ensure that the #CDTEdge's created will have ids that tie them
  * back to the original face edge (using a numbering system for those edges
  * that starts with cdt->face_edge_offset, and continues with the edges in
  * order around each face in turn. And then the next face starts at
  * cdt->face_edge_offset beyond the start for the previous face.
+ * Return the number of faces added, which may be less than input.face.size()
+ * in the case that some faces have less than 3 sides.
  */
 template<typename T>
-void add_face_constraints(CDT_state<T> *cdt_state,
-                          const CDT_input<T> &input,
-                          CDT_output_type output_type)
+int add_face_constraints(CDT_state<T> *cdt_state,
+                         const CDT_input<T> &input,
+                         CDT_output_type output_type)
 {
   int nv = input.vert.size();
   int nf = input.face.size();
@@ -2216,6 +2218,7 @@ void add_face_constraints(CDT_state<T> *cdt_state,
    * together the are >= INT_MAX, then the Delaunay calculation will take unreasonably long anyway.
    */
   BLI_assert(INT_MAX / cdt_state->face_edge_offset > nf);
+  int faces_added = 0;
   for (int f = 0; f < nf; f++) {
     int flen = input.face[f].size();
     if (flen <= 2) {
@@ -2231,6 +2234,7 @@ void add_face_constraints(CDT_state<T> *cdt_state,
         /* Ignore face edges with invalid vertices. */
         continue;
       }
+      ++faces_added;
       CDTVert<T> *v1 = cdt->get_vert_resolve_merge(iv1);
       CDTVert<T> *v2 = cdt->get_vert_resolve_merge(iv2);
       LinkNode *edge_list;
@@ -2265,6 +2269,7 @@ void add_face_constraints(CDT_state<T> *cdt_state,
       }
     }
   }
+  return faces_added;
 }
 
 /* Delete_edge but try not to mess up outer face.
@@ -2642,7 +2647,8 @@ CDT_result<T> get_cdt_output(CDT_state<T> *cdt_state,
                              const CDT_input<T> UNUSED(input),
                              CDT_output_type output_type)
 {
-  prepare_cdt_for_output(cdt_state, output_type);
+  CDT_output_type oty = output_type;
+  prepare_cdt_for_output(cdt_state, oty);
   CDT_result<T> result;
   CDTArrangement<T> *cdt = &cdt_state->cdt;
   result.face_edge_offset = cdt_state->face_edge_offset;
@@ -2774,7 +2780,11 @@ CDT_result<T> delaunay_calc(const CDT_input<T> &input, CDT_output_type output_ty
   add_input_verts(&cdt_state, input);
   initial_triangulation(&cdt_state.cdt);
   add_edge_constraints(&cdt_state, input);
-  add_face_constraints(&cdt_state, input, output_type);
+  int actual_nf = add_face_constraints(&cdt_state, input, output_type);
+  if (actual_nf == 0 && !ELEM(output_type, CDT_FULL, CDT_INSIDE, CDT_CONSTRAINTS)) {
+    /* Can't look for faces or holes if there were no valid input faces. */
+    output_type = CDT_INSIDE;
+  }
   return get_cdt_output(&cdt_state, input, output_type);
 }