Triangulate Modifier changes - using scanfill

The ear loop method is potentially too slow (OˆN).

We are not using the 'beauty' option at the moment.
I'll incorporate that next.
(and later specific methods for quad splitting)

Patch done in collaboration (and reviewed by)  with Campbell Barton.

4 files changed, 113 insertions, 222 deletions

diff --git a/source/blender/bmesh/intern/bmesh_core.c b/source/blender/bmesh/intern/bmesh_core.c
index 164a92125cd..0b14cf22276 100644
--- a/source/blender/bmesh/intern/bmesh_core.c
+++ b/source/blender/bmesh/intern/bmesh_core.c
@@ -2279,3 +2279,27 @@ BMVert *bmesh_urmv(BMesh *bm, BMFace *f_sep, BMVert *v_sep)
 	BMLoop *l = BM_face_vert_share_loop(f_sep, v_sep);
 	return bmesh_urmv_loop(bm, l);
 }
+
+/**
+ * Avoid calling this where possible,
+ * low level function for swapping faces.
+ */
+void bmesh_face_swap_data(BMesh *bm, BMFace *f_a, BMFace *f_b)
+{
+	BMLoop *l_iter, *l_first;
+
+	BLI_assert(f_a != f_b);
+
+	l_iter = l_first = BM_FACE_FIRST_LOOP(f_a);
+	do {
+		l_iter->f = f_b;
+	} while ((l_iter = l_iter->next) != l_first);
+
+	l_iter = l_first = BM_FACE_FIRST_LOOP(f_b);
+	do {
+		l_iter->f = f_a;
+	} while ((l_iter = l_iter->next) != l_first);
+
+	SWAP(BMFace, (*f_a), (*f_b));
+	bm->elem_index_dirty |= BM_FACE;
+}
diff --git a/source/blender/bmesh/intern/bmesh_core.h b/source/blender/bmesh/intern/bmesh_core.h
index a18c2ebd32c..9e33509c2c8 100644
--- a/source/blender/bmesh/intern/bmesh_core.h
+++ b/source/blender/bmesh/intern/bmesh_core.h
@@ -87,4 +87,6 @@ BMFace *bmesh_jfke(BMesh *bm, BMFace *f1, BMFace *f2, BMEdge *e);
 BMVert *bmesh_urmv(BMesh *bm, BMFace *f_sep, BMVert *v_sep);
 BMVert *bmesh_urmv_loop(BMesh *bm, BMLoop *l_sep);
 
+void    bmesh_face_swap_data(BMesh *bm, BMFace *f_a, BMFace *f_b);
+
 #endif /* __BMESH_CORE_H__ */
diff --git a/source/blender/bmesh/intern/bmesh_polygon.c b/source/blender/bmesh/intern/bmesh_polygon.c
index 0978faee9e4..d11ae82b3d2 100644
--- a/source/blender/bmesh/intern/bmesh_polygon.c
+++ b/source/blender/bmesh/intern/bmesh_polygon.c
@@ -34,6 +34,7 @@
 
 #include "BLI_alloca.h"
 #include "BLI_math.h"
+#include "BLI_memarena.h"
 #include "BLI_scanfill.h"
 #include "BLI_listbase.h"
 
@@ -801,264 +802,127 @@ bool BM_face_point_inside_test(BMFace *f, const float co[3])
 	return crosses % 2 != 0;
 }
 
-static bool bm_face_goodline(float const (*projectverts)[2], BMFace *f, int v1i, int v2i, int v3i)
-{
-	BMLoop *l_iter;
-	BMLoop *l_first;
-
-	float pv1[2];
-	const float *v1 = projectverts[v1i];
-	const float *v2 = projectverts[v2i];
-	const float *v3 = projectverts[v3i];
-	int i;
-
-	/* v3 must be on the left side of [v1, v2] line, else we know [v1, v3] is outside of f! */
-	if (testedgesidef(v1, v2, v3)) {
-		return false;
-	}
-
-	l_iter = l_first = BM_FACE_FIRST_LOOP(f);
-	do {
-		i = BM_elem_index_get(l_iter->v);
-		copy_v2_v2(pv1, projectverts[i]);
-
-		if (ELEM3(i, v1i, v2i, v3i)) {
-#if 0
-			printf("%d in (%d, %d, %d) tri (from indices!), continuing\n", i, v1i, v2i, v3i);
-#endif
-			continue;
-		}
-
-		if (isect_point_tri_v2(pv1, v1, v2, v3) ||
-		    isect_point_tri_v2(pv1, v3, v2, v1))
-		{
-#if 0
-			if (isect_point_tri_v2(pv1, v1, v2, v3))
-				printf("%d in (%d, %d, %d)\n", v3i, i, v1i, v2i);
-			else
-				printf("%d in (%d, %d, %d)\n", v1i, i, v3i, v2i);
-#endif
-			return false;
-		}
-	} while ((l_iter = l_iter->next) != l_first);
-	return true;
-}
-
 /**
- * \brief Find Ear
+ * \brief BMESH TRIANGULATE FACE
  *
- * Used by tessellator to find the next triangle to 'clip off' of a polygon while tessellating.
+ * Currently repeatedly find the best triangle (i.e. the most "open" one), provided it does not
+ * produces a "remaining" face with too much wide/narrow angles
+ * (using cos (i.e. dot product of normalized vectors) of angles).
  *
- * \param f The face to search.
- * \param projectverts an array of face vert coords.
- * \param use_beauty Currently only applies to quads, can be extended later on.
- * \param abscoss Must be allocated by caller, and at least f->len length
- *        (allow to avoid allocating a new one for each tri!).
+ * \param r_faces_new if non-null, must be an array of BMFace pointers,
+ * with a length equal to (f->len - 2). It will be filled with the new
+ * triangles.
+ *
+ * \note use_tag tags new flags and edges.
  */
-static BMLoop *poly_find_ear(BMFace *f, float (*projectverts)[2], const bool use_beauty, float *abscoss)
+void BM_face_triangulate(BMesh *bm, BMFace *f,
+                         BMFace **r_faces_new,
+                         MemArena *sf_arena,
+                         const bool UNUSED(use_beauty), const bool use_tag)
 {
-	BMLoop *bestear = NULL;
+	int nf_i = 0;
+	BMLoop *l_iter, *l_first, *l_new;
+	BMFace *f_new;
 
-	BMLoop *l_iter;
-	BMLoop *l_first;
+	BLI_assert(BM_face_is_normal_valid(f));
 
-	const float cos_threshold = 0.9f;
-	const float bias = 1.0f + 1e-6f;
-
-	/* just triangulate degenerate faces */
-	if (UNLIKELY(is_zero_v3(f->no))) {
-		return BM_FACE_FIRST_LOOP(f);
-	}
 
 	if (f->len == 4) {
-		BMLoop *larr[4];
-		int i = 0, i4;
-		float cos1, cos2;
-		l_iter = l_first = BM_FACE_FIRST_LOOP(f);
-		do {
-			larr[i] = l_iter;
-			i++;
-		} while ((l_iter = l_iter->next) != l_first);
+		l_first = BM_FACE_FIRST_LOOP(f);
 
-		/* pick 0/1 based on best length */
-		/* XXX Can't only rely on such test, also must check we do not get (too much) degenerated triangles!!! */
-		i = (((len_squared_v3v3(larr[0]->v->co, larr[2]->v->co) >
-		       len_squared_v3v3(larr[1]->v->co, larr[3]->v->co) * bias)) != use_beauty);
-		i4 = (i + 3) % 4;
-		/* Check produced tris aren't too flat/narrow...
-		 * Probably not the best test, but is quite efficient and should at least avoid null-area faces! */
-		cos1 = fabsf(cos_v3v3v3(larr[i4]->v->co, larr[i]->v->co, larr[i + 1]->v->co));
-		cos2 = fabsf(cos_v3v3v3(larr[i4]->v->co, larr[i + 2]->v->co, larr[i + 1]->v->co));
-#if 0
-		printf("%d, (%f, %f), (%f, %f)\n", i, cos1, cos2,
-		       fabsf(cos_v3v3v3(larr[i]->v->co, larr[i4]->v->co, larr[i + 2]->v->co)),
-		       fabsf(cos_v3v3v3(larr[i]->v->co, larr[i + 1]->v->co, larr[i + 2]->v->co)));
-#endif
-		if (cos1 < cos2)
-			cos1 = cos2;
-
-		if (cos1 > cos_threshold) {
-			if (cos1 > fabsf(cos_v3v3v3(larr[i]->v->co, larr[i4]->v->co, larr[i + 2]->v->co)) &&
-			    cos1 > fabsf(cos_v3v3v3(larr[i]->v->co, larr[i + 1]->v->co, larr[i + 2]->v->co)))
-			{
-				i = !i;
-			}
+		f_new = BM_face_split(bm, f, l_first->v, l_first->next->next->v, &l_new, NULL, false);
+		copy_v3_v3(f_new->no, f->no);
+
+		if (UNLIKELY(!l_new || !f_new)) {
+			fprintf(stderr, "%s: triangulator failed to split face! (bmesh internal error)\n", __func__);
 		}
-		/* Last check we do not get overlapping triangles
-		 * (as much as possible, there are some cases with no good solution!) */
-		i4 = (i + 3) % 4;
-		if (!bm_face_goodline((float const (*)[2])projectverts, f,
-		                      BM_elem_index_get(larr[i4]->v),
-		                      BM_elem_index_get(larr[i]->v),
-		                      BM_elem_index_get(larr[i + 1]->v)))
-		{
-			i = !i;
+
+		if (use_tag) {
+			BM_elem_flag_enable(l_new->e, BM_ELEM_TAG);
+			BM_elem_flag_enable(f, BM_ELEM_TAG);
 		}
-/*		printf("%d\n", i);*/
-		bestear = larr[i];
 
+		if (r_faces_new) {
+			r_faces_new[nf_i++] = f_new;
+		}
 	}
-	else {
-		/* float angle, bestangle = 180.0f; */
-		const int len = f->len;
-		float cos, cos_best = 1.0f;
-		int i, j;
+	else if (f->len > 4) {
+		/* scanfill */
+		ScanFillContext sf_ctx;
+		ScanFillVert *sf_vert, *sf_vert_prev = NULL;
+		ScanFillFace *sf_tri;
+		int totfilltri;
 
-		/* Compute cos of all corners! */
-		i = 0;
+		/* populate scanfill */
+		BLI_scanfill_begin_arena(&sf_ctx, sf_arena);
 		l_iter = l_first = BM_FACE_FIRST_LOOP(f);
-		do {
-			const BMVert *v1 = l_iter->prev->v;
-			const BMVert *v2 = l_iter->v;
-			const BMVert *v3 = l_iter->next->v;
 
-			abscoss[i] = fabsf(cos_v3v3v3(v1->co, v2->co, v3->co));
-/*			printf("tcoss: %f\n", *tcoss);*/
-			i++;
-		} while ((l_iter = l_iter->next) != l_first);
+		/* step once before entering the loop */
+		sf_vert = BLI_scanfill_vert_add(&sf_ctx, l_iter->v->co);
+		sf_vert->tmp.p = l_iter;
+		sf_vert_prev = sf_vert;
+		l_iter = l_iter->next;
 
-		i = 0;
-		l_iter = l_first;
 		do {
-			const BMVert *v1 = l_iter->prev->v;
-			const BMVert *v2 = l_iter->v;
-			const BMVert *v3 = l_iter->next->v;
-
-			/* Compute highest cos (i.e. narrowest angle) of this tri. */
-			cos = max_fff(abscoss[i],
-			              fabsf(cos_v3v3v3(v2->co, v3->co, v1->co)),
-			              fabsf(cos_v3v3v3(v3->co, v1->co, v2->co)));
-
-			/* Compare to prev best (i.e. lowest) cos. */
-			if (cos < cos_best) {
-				if (bm_face_goodline((float const (*)[2])projectverts, f,
-				                     BM_elem_index_get(v1),
-				                     BM_elem_index_get(v2),
-				                     BM_elem_index_get(v3)))
-				{
-					/* We must check this tri would not leave a (too much) degenerated remaining face! */
-					/* For now just assume if the average of cos of all
-					 * "remaining face"'s corners is below a given threshold, it's OK. */
-					float cos_mean = fabsf(cos_v3v3v3(v1->co, v3->co, l_iter->next->next->v->co));
-					const int i_limit = (i - 1 + len) % len;
-					cos_mean += fabsf(cos_v3v3v3(l_iter->prev->prev->v->co, v1->co, v3->co));
-					j = (i + 2) % len;
-					do {
-						cos_mean += abscoss[j];
-					} while ((j = (j + 1) % len) != i_limit);
-					cos_mean /= len - 1;
-
-					/* We need a best ear in any case... */
-					if (cos_mean < cos_threshold || (!bestear && cos_mean < 1.0f)) {
-						/* OKI, keep this ear (corner...) as a potential best one! */
-						bestear = l_iter;
-						cos_best = cos;
-					}
-#if 0
-					else
-						printf("Had a nice tri (higest cos of %f, current cos_best is %f), "
-						       "but average cos of all \"remaining face\"'s corners is too high (%f)!\n",
-						       cos, cos_best, cos_mean);
-#endif
-				}
-			}
-			i++;
+			sf_vert = BLI_scanfill_vert_add(&sf_ctx, l_iter->v->co);
+			BLI_scanfill_edge_add(&sf_ctx, sf_vert_prev, sf_vert);
+
+			sf_vert->tmp.p = l_iter;
+			sf_vert_prev = sf_vert;
 		} while ((l_iter = l_iter->next) != l_first);
-	}
 
-	return bestear;
-}
+		BLI_scanfill_edge_add(&sf_ctx, sf_vert_prev, sf_ctx.fillvertbase.first);
 
-/**
- * \brief BMESH TRIANGULATE FACE
- *
- * Currently repeatedly find the best triangle (i.e. the most "open" one), provided it does not
- * produces a "remaining" face with too much wide/narrow angles
- * (using cos (i.e. dot product of normalized vectors) of angles).
- *
- * \param r_faces_new if non-null, must be an array of BMFace pointers,
- * with a length equal to (f->len - 2). It will be filled with the new
- * triangles.
- *
- * \note use_tag tags new flags and edges.
- */
-void BM_face_triangulate(BMesh *bm, BMFace *f,
-                         BMFace **r_faces_new,
-                         const bool use_beauty, const bool use_tag)
-{
-	const float f_len_orig = f->len;
-	int i, nf_i = 0;
-	BMLoop *l_new;
-	BMLoop *l_iter;
-	BMLoop *l_first;
-	/* BM_face_triangulate: temp absolute cosines of face corners */
-	float (*projectverts)[2] = BLI_array_alloca(projectverts, f_len_orig);
-	float *abscoss = BLI_array_alloca(abscoss, f_len_orig);
-	float mat[3][3];
+		/* calculate filled triangles */
+		totfilltri = BLI_scanfill_calc_ex(&sf_ctx, 0, f->no);
+		BLI_assert(totfilltri <= f->len - 2);
 
-	BLI_assert(BM_face_is_normal_valid(f));
 
-	axis_dominant_v3_to_m3(mat, f->no);
+		/* loop over calculated triangles and create new geometry */
+		for (sf_tri = sf_ctx.fillfacebase.first; sf_tri; sf_tri = sf_tri->next) {
+			/* the order is reverse, otherwise the normal is flipped */
+			BMLoop *l_tri[3] = {
+			    sf_tri->v3->tmp.p,
+			    sf_tri->v2->tmp.p,
+			    sf_tri->v1->tmp.p};
 
-	/* copy vertex coordinates to vertspace area */
-	i = 0;
-	l_iter = l_first = BM_FACE_FIRST_LOOP(f);
-	do {
-		mul_v2_m3v3(projectverts[i], mat, l_iter->v->co);
-		BM_elem_index_set(l_iter->v, i++); /* set dirty! */
-	} while ((l_iter = l_iter->next) != l_first);
+			BMVert *v_tri[3] = {
+			    l_tri[0]->v,
+			    l_tri[1]->v,
+			    l_tri[2]->v};
 
-	bm->elem_index_dirty |= BM_VERT; /* see above */
+			f_new = BM_face_create_verts(bm, v_tri, 3, f, false, true);
+			l_new = BM_FACE_FIRST_LOOP(f_new);
 
-	while (f->len > 3) {
-		l_iter = poly_find_ear(f, projectverts, use_beauty, abscoss);
+			BLI_assert(v_tri[0] == l_new->v);
 
-		/* force triangulation - if we can't find an ear the face is degenerate */
-		if (l_iter == NULL) {
-			l_iter = BM_FACE_FIRST_LOOP(f);
-		}
+			/* copy CD data */
+			BM_elem_attrs_copy(bm, bm, l_tri[0], l_new);
+			BM_elem_attrs_copy(bm, bm, l_tri[1], l_new->next);
+			BM_elem_attrs_copy(bm, bm, l_tri[2], l_new->prev);
 
-/*		printf("Subdividing face...\n");*/
-		f = BM_face_split(bm, l_iter->f, l_iter->prev->v, l_iter->next->v, &l_new, NULL, true);
+			if (use_tag) {
+				BM_elem_flag_enable(l_new->e, BM_ELEM_TAG);
+			}
 
-		if (UNLIKELY(!f)) {
-			fprintf(stderr, "%s: triangulator failed to split face! (bmesh internal error)\n", __func__);
-			break;
+			if (r_faces_new && sf_tri->prev) {
+				r_faces_new[nf_i++] = f_new;
+			}
 		}
 
-		copy_v3_v3(f->no, l_iter->f->no);
+		if (sf_ctx.fillfacebase.first) {
+			/* we can't delete the real face, so swap data and delete */
+			bmesh_face_swap_data(bm, f, f_new);
+			BM_face_kill(bm, f_new);
 
-		if (use_tag) {
-			BM_elem_flag_enable(l_new->e, BM_ELEM_TAG);
-			BM_elem_flag_enable(f, BM_ELEM_TAG);
+			if (use_tag) {
+				BM_elem_flag_enable(f, BM_ELEM_TAG);
+			}
 		}
 
-		if (r_faces_new) {
-			r_faces_new[nf_i++] = f;
-		}
+		/* garbage collection */
+		BLI_scanfill_end_arena(&sf_ctx, sf_arena);
 	}
-
-	BLI_assert(f->len == 3);
 }
 
 /**
diff --git a/source/blender/bmesh/intern/bmesh_polygon.h b/source/blender/bmesh/intern/bmesh_polygon.h
index 14fe1e76360..b7117621273 100644
--- a/source/blender/bmesh/intern/bmesh_polygon.h
+++ b/source/blender/bmesh/intern/bmesh_polygon.h
@@ -53,6 +53,7 @@ void  BM_face_normal_flip(BMesh *bm, BMFace *f) ATTR_NONNULL();
 bool  BM_face_point_inside_test(BMFace *f, const float co[3]) ATTR_WARN_UNUSED_RESULT ATTR_NONNULL();
 
 void  BM_face_triangulate(BMesh *bm, BMFace *f, BMFace **newfaces,
+                          struct MemArena *sf_arena,
                           const bool use_beauty, const bool use_tag) ATTR_NONNULL(1, 2);
 
 void  BM_face_legal_splits(BMFace *f, BMLoop *(*loops)[2], int len) ATTR_NONNULL();