Fix T52291: Boolean fails w/ co-linear edged ngons

This means boolean tessellation wont match viewport tessellation
however it's needed to avoid zero area triangles causing problems.

1 files changed, 128 insertions, 0 deletions

diff --git a/source/blender/bmesh/intern/bmesh_polygon.c b/source/blender/bmesh/intern/bmesh_polygon.c
index a4621b45fe6..a839f92b9e9 100644
--- a/source/blender/bmesh/intern/bmesh_polygon.c
+++ b/source/blender/bmesh/intern/bmesh_polygon.c
@@ -39,6 +39,8 @@
 #include "BLI_polyfill2d.h"
 #include "BLI_polyfill2d_beautify.h"
 #include "BLI_linklist.h"
+#include "BLI_edgehash.h"
+#include "BLI_heap.h"
 
 #include "bmesh.h"
 #include "bmesh_tools.h"
@@ -1474,3 +1476,129 @@ void BM_mesh_calc_tessellation(BMesh *bm, BMLoop *(*looptris)[3], int *r_looptri
 #undef USE_TESSFACE_SPEEDUP
 
 }
+
+
+/**
+ * A version of #BM_mesh_calc_tessellation that avoids degenerate triangles.
+ */
+void BM_mesh_calc_tessellation_beauty(BMesh *bm, BMLoop *(*looptris)[3], int *r_looptris_tot)
+{
+	/* this assumes all faces can be scan-filled, which isn't always true,
+	 * worst case we over alloc a little which is acceptable */
+#ifndef NDEBUG
+	const int looptris_tot = poly_to_tri_count(bm->totface, bm->totloop);
+#endif
+
+	BMIter iter;
+	BMFace *efa;
+	int i = 0;
+
+	MemArena *pf_arena = NULL;
+
+	/* use_beauty */
+	Heap *pf_heap = NULL;
+	EdgeHash *pf_ehash = NULL;
+
+	BM_ITER_MESH (efa, &iter, bm, BM_FACES_OF_MESH) {
+		/* don't consider two-edged faces */
+		if (UNLIKELY(efa->len < 3)) {
+			/* do nothing */
+		}
+		else if (efa->len == 3) {
+			BMLoop *l;
+			BMLoop **l_ptr = looptris[i++];
+			l_ptr[0] = l = BM_FACE_FIRST_LOOP(efa);
+			l_ptr[1] = l = l->next;
+			l_ptr[2] = l->next;
+		}
+		else if (efa->len == 4) {
+			BMLoop *l_v1 = BM_FACE_FIRST_LOOP(efa);
+			BMLoop *l_v2 = l_v1->next;
+			BMLoop *l_v3 = l_v2->next;
+			BMLoop *l_v4 = l_v1->prev;
+
+			const bool split_24 = (BM_verts_calc_rotate_beauty(l_v1->v, l_v2->v, l_v3->v, l_v4->v, 0, 0) > 0.0f);
+
+			BMLoop **l_ptr_a = looptris[i++];
+			BMLoop **l_ptr_b = looptris[i++];
+			if (split_24 == 0) {
+				l_ptr_a[0] = l_v1;
+				l_ptr_a[1] = l_v2;
+				l_ptr_a[2] = l_v3;
+
+				l_ptr_b[0] = l_v1;
+				l_ptr_b[1] = l_v3;
+				l_ptr_b[2] = l_v4;
+			}
+			else {
+				l_ptr_a[0] = l_v1;
+				l_ptr_a[1] = l_v2;
+				l_ptr_a[2] = l_v4;
+
+				l_ptr_b[0] = l_v2;
+				l_ptr_b[1] = l_v3;
+				l_ptr_b[2] = l_v4;
+			}
+		}
+		else {
+			int j;
+
+			BMLoop *l_iter;
+			BMLoop *l_first;
+			BMLoop **l_arr;
+
+			float axis_mat[3][3];
+			float (*projverts)[2];
+			unsigned int (*tris)[3];
+
+			const int totfilltri = efa->len - 2;
+
+			if (UNLIKELY(pf_arena == NULL)) {
+				pf_arena = BLI_memarena_new(BLI_MEMARENA_STD_BUFSIZE, __func__);
+				pf_heap = BLI_heap_new_ex(BLI_POLYFILL_ALLOC_NGON_RESERVE);
+				pf_ehash = BLI_edgehash_new_ex(__func__, BLI_POLYFILL_ALLOC_NGON_RESERVE);
+			}
+
+			tris = BLI_memarena_alloc(pf_arena, sizeof(*tris) * totfilltri);
+			l_arr = BLI_memarena_alloc(pf_arena, sizeof(*l_arr) * efa->len);
+			projverts = BLI_memarena_alloc(pf_arena, sizeof(*projverts) * efa->len);
+
+			axis_dominant_v3_to_m3_negate(axis_mat, efa->no);
+
+			j = 0;
+			l_iter = l_first = BM_FACE_FIRST_LOOP(efa);
+			do {
+				l_arr[j] = l_iter;
+				mul_v2_m3v3(projverts[j], axis_mat, l_iter->v->co);
+				j++;
+			} while ((l_iter = l_iter->next) != l_first);
+
+			BLI_polyfill_calc_arena((const float (*)[2])projverts, efa->len, 1, tris, pf_arena);
+
+			BLI_polyfill_beautify((const float (*)[2])projverts, efa->len, tris, pf_arena, pf_heap, pf_ehash);
+
+			for (j = 0; j < totfilltri; j++) {
+				BMLoop **l_ptr = looptris[i++];
+				unsigned int *tri = tris[j];
+
+				l_ptr[0] = l_arr[tri[0]];
+				l_ptr[1] = l_arr[tri[1]];
+				l_ptr[2] = l_arr[tri[2]];
+			}
+
+			BLI_memarena_clear(pf_arena);
+		}
+	}
+
+	if (pf_arena) {
+		BLI_memarena_free(pf_arena);
+
+		BLI_heap_free(pf_heap, NULL);
+		BLI_edgehash_free(pf_ehash, NULL);
+	}
+
+	*r_looptris_tot = i;
+
+	BLI_assert(i <= looptris_tot);
+
+}