Fix T89330 Exact Boolean fails on a simple model.

The problem was an optimization I put in to triangulate quads.
It was wrong if the quad, after projecting onto a 2d plane, was
not convex. Handling quads the same as other faces fixes the bug.
Unfortunately, this will slow down Exact Boolean when the input has
many quads (the usual case, of course).
Will attempt to fix that with a later change, but for now, this
at least restores correctness.

2 files changed, 74 insertions, 14 deletions

diff --git a/source/blender/blenlib/intern/mesh_intersect.cc b/source/blender/blenlib/intern/mesh_intersect.cc
index 32f0216951a..a9c725d4adf 100644
--- a/source/blender/blenlib/intern/mesh_intersect.cc
+++ b/source/blender/blenlib/intern/mesh_intersect.cc
@@ -1998,6 +1998,10 @@ static Array<Face *> polyfill_triangulate_poly(Face *f, IMeshArena *arena)
  * 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).
+ *
+ * While it is tempting to handle quadrilaterals specially, since that
+ * is by far the usual case, we need to know if the quad is convex when
+ * projected before doing so, and that takes a fair amount of computation by itself.
  */
 static Array<Face *> triangulate_poly(Face *f, IMeshArena *arena)
 {
@@ -2099,20 +2103,6 @@ IMesh triangulate_polymesh(IMesh &imesh, IMeshArena *arena)
     if (flen == 3) {
       face_tris.append(f);
     }
-    else if (flen == 4) {
-      const Vert *v0 = (*f)[0];
-      const Vert *v1 = (*f)[1];
-      const Vert *v2 = (*f)[2];
-      const Vert *v3 = (*f)[3];
-      int eo_01 = f->edge_orig[0];
-      int eo_12 = f->edge_orig[1];
-      int eo_23 = f->edge_orig[2];
-      int eo_30 = f->edge_orig[3];
-      Face *f0 = arena->add_face({v0, v1, v2}, f->orig, {eo_01, eo_12, -1}, {false, false, false});
-      Face *f1 = arena->add_face({v0, v2, v3}, f->orig, {-1, eo_23, eo_30}, {false, false, false});
-      face_tris.append(f0);
-      face_tris.append(f1);
-    }
     else {
       Array<Face *> tris = triangulate_poly(f, arena);
       for (Face *tri : tris) {
diff --git a/source/blender/blenlib/tests/BLI_mesh_intersect_test.cc b/source/blender/blenlib/tests/BLI_mesh_intersect_test.cc
index ec57cf29cad..1a9ffbd3403 100644
--- a/source/blender/blenlib/tests/BLI_mesh_intersect_test.cc
+++ b/source/blender/blenlib/tests/BLI_mesh_intersect_test.cc
@@ -174,6 +174,76 @@ TEST(mesh_intersect, Mesh)
   EXPECT_TRUE(f->is_tri());
 }
 
+TEST(mesh_intersect, TriangulateTri)
+{
+  const char *spec = R"(3 1
+  0 0 0
+  1 0 0
+  1/2 1 0
+  0 1 2
+  )";
+
+  IMeshBuilder mb(spec);
+  IMesh im_tri = triangulate_polymesh(mb.imesh, &mb.arena);
+  EXPECT_EQ(im_tri.faces().size(), 1);
+}
+
+TEST(mesh_intersect, TriangulateQuad)
+{
+  const char *spec = R"(4 1
+  0 0 0
+  1 0 0
+  1 1 0
+  0 1 0
+  0 1 2 3
+  )";
+
+  IMeshBuilder mb(spec);
+  IMesh im_tri = triangulate_polymesh(mb.imesh, &mb.arena);
+  EXPECT_EQ(im_tri.faces().size(), 2);
+}
+
+TEST(mesh_intersect, TriangulatePentagon)
+{
+  const char *spec = R"(5 1
+  0 0 0
+  1 0 0
+  1 1 0
+  1/2 2 0
+  0 1 0
+  0 1 2 3 4
+  )";
+
+  IMeshBuilder mb(spec);
+  IMesh im_tri = triangulate_polymesh(mb.imesh, &mb.arena);
+  EXPECT_EQ(im_tri.faces().size(), 3);
+  if (DO_OBJ) {
+    write_obj_mesh(im_tri, "pentagon");
+  }
+}
+
+TEST(mesh_intersect, TriangulateTwoFaces)
+{
+  const char *spec = R"(7 2
+  461/250 -343/125 103/1000
+  -3/40 -453/200 -97/500
+  237/100 -321/200 -727/500
+  451/1000 -563/500 -1751/1000
+  12/125 -2297/1000 -181/1000
+  12/125 -411/200 -493/1000
+  1959/1000 -2297/1000 -493/1000
+  1 3 2 0 6 5 4
+  6 0 1 4
+  )";
+
+  IMeshBuilder mb(spec);
+  IMesh im_tri = triangulate_polymesh(mb.imesh, &mb.arena);
+  EXPECT_EQ(im_tri.faces().size(), 7);
+  if (DO_OBJ) {
+    write_obj_mesh(im_tri, "twofaces");
+  }
+}
+
 TEST(mesh_intersect, OneTri)
 {
   const char *spec = R"(3 1