BMesh Refactor: BKE_bmbvh_new can now be created without an EditMesh.

This adds BM_bmesh_calc_tessellation() so we can get triangles from a
bmesh without having to have an editmesh available.

2 files changed, 161 insertions, 0 deletions

diff --git a/source/blender/bmesh/intern/bmesh_polygon.c b/source/blender/bmesh/intern/bmesh_polygon.c
index e88fdb8a7e8..3db6ba0e7c9 100644
--- a/source/blender/bmesh/intern/bmesh_polygon.c
+++ b/source/blender/bmesh/intern/bmesh_polygon.c
@@ -31,6 +31,8 @@
 #include "DNA_listBase.h"
 #include "DNA_modifier_types.h"
 
+#include "MEM_guardedalloc.h"
+
 #include "BLI_alloca.h"
 #include "BLI_math.h"
 #include "BLI_memarena.h"
@@ -1268,3 +1270,160 @@ void BM_face_as_array_loop_quad(BMFace *f, BMLoop *r_loops[4])
 	r_loops[2] = l; l = l->next;
 	r_loops[3] = l;
 }
+
+
+/**
+ * \brief BM_bmesh_calc_tessellation get the looptris and its number from a certain bmesh
+ * \param looptris
+ *
+ * \note \a looptris  Must be pre-allocated to at least the size of given by: poly_to_tri_count
+ */
+void BM_bmesh_calc_tessellation(BMesh *bm, BMLoop *(*looptris)[3], int *r_looptris_tot)
+{
+	/* use this to avoid locking pthread for _every_ polygon
+	 * and calling the fill function */
+#define USE_TESSFACE_SPEEDUP
+
+	/* this assumes all faces can be scan-filled, which isn't always true,
+	 * worst case we over alloc a little which is acceptable */
+	const int looptris_tot = poly_to_tri_count(bm->totface, bm->totloop);
+
+	BMIter iter;
+	BMFace *efa;
+	BMLoop *l;
+	int i = 0;
+
+	ScanFillContext sf_ctx;
+	MemArena *sf_arena = NULL;
+
+	BM_ITER_MESH (efa, &iter, bm, BM_FACES_OF_MESH) {
+		/* don't consider two-edged faces */
+		if (UNLIKELY(efa->len < 3)) {
+			/* do nothing */
+		}
+
+#ifdef USE_TESSFACE_SPEEDUP
+
+		/* no need to ensure the loop order, we know its ok */
+
+		else if (efa->len == 3) {
+#if 0
+			int j;
+			BM_ITER_ELEM_INDEX (l, &liter, efa, BM_LOOPS_OF_FACE, j) {
+				looptris[i][j] = l;
+			}
+			i += 1;
+#else
+			/* more cryptic but faster */
+			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;
+#endif
+		}
+		else if (efa->len == 4) {
+#if 0
+			BMLoop *ltmp[4];
+			int j;
+			BLI_array_grow_items(looptris, 2);
+			BM_ITER_ELEM_INDEX (l, &liter, efa, BM_LOOPS_OF_FACE, j) {
+				ltmp[j] = l;
+			}
+
+			looptris[i][0] = ltmp[0];
+			looptris[i][1] = ltmp[1];
+			looptris[i][2] = ltmp[2];
+			i += 1;
+
+			looptris[i][0] = ltmp[0];
+			looptris[i][1] = ltmp[2];
+			looptris[i][2] = ltmp[3];
+			i += 1;
+#else
+			/* more cryptic but faster */
+			BMLoop **l_ptr_a = looptris[i++];
+			BMLoop **l_ptr_b = looptris[i++];
+			(l_ptr_a[0] = l_ptr_b[0] = l = BM_FACE_FIRST_LOOP(efa));
+			(l_ptr_a[1]              = l = l->next);
+			(l_ptr_a[2] = l_ptr_b[1] = l = l->next);
+			(             l_ptr_b[2] = l->next);
+#endif
+		}
+
+#endif /* USE_TESSFACE_SPEEDUP */
+
+		else {
+			int j;
+			BMLoop *l_iter;
+			BMLoop *l_first;
+
+			ScanFillVert *sf_vert, *sf_vert_last = NULL, *sf_vert_first = NULL;
+			/* ScanFillEdge *e; */ /* UNUSED */
+			ScanFillFace *sf_tri;
+			int totfilltri;
+
+			if (UNLIKELY(sf_arena == NULL)) {
+				sf_arena = BLI_memarena_new(BLI_SCANFILL_ARENA_SIZE, __func__);
+			}
+
+			BLI_scanfill_begin_arena(&sf_ctx, sf_arena);
+
+			/* scanfill time */
+			j = 0;
+			l_iter = l_first = BM_FACE_FIRST_LOOP(efa);
+			do {
+				sf_vert = BLI_scanfill_vert_add(&sf_ctx, l_iter->v->co);
+				sf_vert->tmp.p = l_iter;
+
+				if (sf_vert_last) {
+					/* e = */ BLI_scanfill_edge_add(&sf_ctx, sf_vert_last, sf_vert);
+				}
+
+				sf_vert_last = sf_vert;
+				if (sf_vert_first == NULL) {
+					sf_vert_first = sf_vert;
+				}
+
+				/*mark order */
+				BM_elem_index_set(l_iter, j++); /* set_loop */
+
+			} while ((l_iter = l_iter->next) != l_first);
+
+			/* complete the loop */
+			BLI_scanfill_edge_add(&sf_ctx, sf_vert_first, sf_vert);
+
+			totfilltri = BLI_scanfill_calc_ex(&sf_ctx, 0, efa->no);
+			BLI_assert(totfilltri <= efa->len - 2);
+			(void)totfilltri;
+
+			for (sf_tri = sf_ctx.fillfacebase.first; sf_tri; sf_tri = sf_tri->next) {
+				BMLoop **l_ptr = looptris[i++];
+				BMLoop *l1 = sf_tri->v1->tmp.p;
+				BMLoop *l2 = sf_tri->v2->tmp.p;
+				BMLoop *l3 = sf_tri->v3->tmp.p;
+
+				if (BM_elem_index_get(l1) > BM_elem_index_get(l2)) { SWAP(BMLoop *, l1, l2); }
+				if (BM_elem_index_get(l2) > BM_elem_index_get(l3)) { SWAP(BMLoop *, l2, l3); }
+				if (BM_elem_index_get(l1) > BM_elem_index_get(l2)) { SWAP(BMLoop *, l1, l2); }
+
+				l_ptr[0] = l1;
+				l_ptr[1] = l2;
+				l_ptr[2] = l3;
+			}
+
+			BLI_scanfill_end_arena(&sf_ctx, sf_arena);
+		}
+	}
+
+	if (sf_arena) {
+		BLI_memarena_free(sf_arena);
+		sf_arena = NULL;
+	}
+
+	*r_looptris_tot = looptris_tot;
+
+	BLI_assert(i <= looptris_tot);
+
+#undef USE_TESSFACE_SPEEDUP
+
+}
diff --git a/source/blender/bmesh/intern/bmesh_polygon.h b/source/blender/bmesh/intern/bmesh_polygon.h
index 4759c73cb4d..5d98a9a40db 100644
--- a/source/blender/bmesh/intern/bmesh_polygon.h
+++ b/source/blender/bmesh/intern/bmesh_polygon.h
@@ -29,6 +29,8 @@
 
 #include "BLI_compiler_attrs.h"
 
+void  BM_bmesh_calc_tessellation(BMesh *bm, BMLoop *(*looptris)[], int *r_looptris_tot);
+
 int   BM_face_calc_tessellation(const BMFace *f, BMLoop **r_loops, int (*r_index)[3]) ATTR_WARN_UNUSED_RESULT ATTR_NONNULL();
 void  BM_face_calc_normal(const BMFace *f, float r_no[3]) ATTR_NONNULL();
 void  BM_face_calc_normal_vcos(BMesh *bm, BMFace *f, float r_no[3],