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.

4 files changed, 40 insertions, 162 deletions

diff --git a/source/blender/blenkernel/BKE_editmesh_bvh.h b/source/blender/blenkernel/BKE_editmesh_bvh.h
index 7b4ad4284c6..aeac00b06c1 100644
--- a/source/blender/blenkernel/BKE_editmesh_bvh.h
+++ b/source/blender/blenkernel/BKE_editmesh_bvh.h
@@ -33,15 +33,19 @@
 #define __BKE_EDITMESH_BVH_H__
 
 struct BMEditMesh;
+struct BMesh;
 struct BMFace;
 struct BMVert;
+struct BMLoop;
 struct BMBVHTree;
 struct BVHTree;
 struct Scene;
 
 typedef struct BMBVHTree BMBVHTree;
 
-BMBVHTree      *BKE_bmbvh_new(struct BMEditMesh *em, int flag, const float (*cos_cage)[3], const bool cos_cage_free);
+BMBVHTree      *BKE_bmbvh_new_from_editmesh(struct BMEditMesh *em, int flag, const float (*cos_cage)[3], const bool cos_cage_free);
+BMBVHTree      *BKE_bmbvh_new(struct BMesh *bm, struct BMLoop *(*looptris)[3], int looptris_tot, int flag,
+                              const float (*cos_cage)[3], const bool cos_cage_free);
 void            BKE_bmbvh_free(BMBVHTree *tree);
 struct BVHTree *BKE_bmbvh_tree_get(BMBVHTree *tree);
 struct BMFace  *BKE_bmbvh_ray_cast(BMBVHTree *tree, const float co[3], const float dir[3], const float radius,
diff --git a/source/blender/blenkernel/intern/editderivedmesh.c b/source/blender/blenkernel/intern/editderivedmesh.c
index 6fb5dd56ce5..c3538b141b5 100644
--- a/source/blender/blenkernel/intern/editderivedmesh.c
+++ b/source/blender/blenkernel/intern/editderivedmesh.c
@@ -1851,7 +1851,7 @@ static void statvis_calc_thickness(
 		BM_mesh_elem_index_ensure(bm, BM_VERT);
 	}
 
-	bmtree = BKE_bmbvh_new(em, 0, vertexCos, false);
+	bmtree = BKE_bmbvh_new_from_editmesh(em, 0, vertexCos, false);
 
 	for (i = 0; i < tottri; i++) {
 		BMFace *f_hit;
@@ -1951,7 +1951,7 @@ static void statvis_calc_intersect(
 		BM_mesh_elem_index_ensure(bm, BM_VERT);
 	}
 
-	bmtree = BKE_bmbvh_new(em, 0, vertexCos, false);
+	bmtree = BKE_bmbvh_new_from_editmesh(em, 0, vertexCos, false);
 
 	BM_ITER_MESH (e, &iter, bm, BM_EDGES_OF_MESH) {
 		BMFace *f_hit;
diff --git a/source/blender/blenkernel/intern/editmesh.c b/source/blender/blenkernel/intern/editmesh.c
index 1fc7d024428..88cef0ec031 100644
--- a/source/blender/blenkernel/intern/editmesh.c
+++ b/source/blender/blenkernel/intern/editmesh.c
@@ -102,9 +102,8 @@ BMEditMesh *BKE_editmesh_from_object(Object *ob)
 
 static void editmesh_tessface_calc_intern(BMEditMesh *em)
 {
-	/* use this to avoid locking pthread for _every_ polygon
-	 * and calling the fill function */
-#define USE_TESSFACE_SPEEDUP
+	/* allocating space before calculating the tessellation */
+
 
 	BMesh *bm = em->bm;
 
@@ -114,13 +113,6 @@ static void editmesh_tessface_calc_intern(BMEditMesh *em)
 	const int looptris_tot_prev_alloc = em->looptris ? (MEM_allocN_len(em->looptris) / sizeof(*em->looptris)) : 0;
 
 	BMLoop *(*looptris)[3];
-	BMIter iter;
-	BMFace *efa;
-	BMLoop *l;
-	int i = 0;
-
-	ScanFillContext sf_ctx;
-	MemArena *sf_arena = NULL;
 
 #if 0
 	/* note, we could be clever and re-use this array but would need to ensure
@@ -136,7 +128,7 @@ static void editmesh_tessface_calc_intern(BMEditMesh *em)
 
 	/* this means no reallocs for quad dominant models, for */
 	if ((em->looptris != NULL) &&
-	    /* (em->tottri >= looptris_tot)) */
+	    /* (*em->tottri >= looptris_tot)) */
 	    /* check against alloc'd size incase we over alloc'd a little */
 	    ((looptris_tot_prev_alloc >= looptris_tot) && (looptris_tot_prev_alloc <= looptris_tot * 2)))
 	{
@@ -149,136 +141,10 @@ static void editmesh_tessface_calc_intern(BMEditMesh *em)
 
 #endif
 
-	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;
-	}
-
-	em->tottri = i;
 	em->looptris = looptris;
 
-	BLI_assert(em->tottri <= looptris_tot);
-
-#undef USE_TESSFACE_SPEEDUP
+	/* after allocating the em->looptris, we're ready to tessellate */
+	BM_bmesh_calc_tessellation(em->bm, em->looptris, &em->tottri);
 
 }
 
diff --git a/source/blender/blenkernel/intern/editmesh_bvh.c b/source/blender/blenkernel/intern/editmesh_bvh.c
index cb65fd80fc4..1c0e508e9e6 100644
--- a/source/blender/blenkernel/intern/editmesh_bvh.c
+++ b/source/blender/blenkernel/intern/editmesh_bvh.c
@@ -44,7 +44,9 @@
 struct BMBVHTree {
 	BVHTree *tree;
 
-	BMEditMesh *em;
+	BMLoop *(*looptris)[3];
+	int looptris_tot;
+
 	BMesh *bm;
 
 	const float (*cos_cage)[3];
@@ -53,33 +55,39 @@ struct BMBVHTree {
 	int flag;
 };
 
-BMBVHTree *BKE_bmbvh_new(BMEditMesh *em, int flag, const float (*cos_cage)[3], const bool cos_cage_free)
+BMBVHTree *BKE_bmbvh_new_from_editmesh(BMEditMesh *em, int flag, const float (*cos_cage)[3], const bool cos_cage_free)
+{
+	return BKE_bmbvh_new(em->bm, em->looptris, em->tottri, flag, cos_cage, cos_cage_free);
+}
+
+BMBVHTree *BKE_bmbvh_new(BMesh *bm, BMLoop *(*looptris)[3], int looptris_tot, int flag, const float (*cos_cage)[3],
+const bool cos_cage_free)
 {
 	/* could become argument */
 	const float epsilon = FLT_EPSILON * 2.0f;
 
-	struct BMLoop *(*looptris)[3] = em->looptris;
 	BMBVHTree *bmtree = MEM_callocN(sizeof(*bmtree), "BMBVHTree");
 	float cos[3][3];
 	int i;
 	int tottri;
 
 	/* BKE_editmesh_tessface_calc() must be called already */
-	BLI_assert(em->tottri != 0 || em->bm->totface == 0);
+	BLI_assert(looptris_tot != 0 || bm->totface == 0);
 
 	if (cos_cage) {
-		BM_mesh_elem_index_ensure(em->bm, BM_VERT);
+		BM_mesh_elem_index_ensure(bm, BM_VERT);
 	}
 
-	bmtree->em = em;
-	bmtree->bm = em->bm;
+	bmtree->looptris = looptris;
+	bmtree->looptris_tot = looptris_tot;
+	bmtree->bm = bm;
 	bmtree->cos_cage = cos_cage;
 	bmtree->cos_cage_free = cos_cage_free;
 	bmtree->flag = flag;
 
 	if (flag & (BMBVH_RESPECT_SELECT)) {
 		tottri = 0;
-		for (i = 0; i < em->tottri; i++) {
+		for (i = 0; i < looptris_tot; i++) {
 			if (BM_elem_flag_test(looptris[i][0]->f, BM_ELEM_SELECT)) {
 				tottri++;
 			}
@@ -87,23 +95,23 @@ BMBVHTree *BKE_bmbvh_new(BMEditMesh *em, int flag, const float (*cos_cage)[3], c
 	}
 	else if (flag & (BMBVH_RESPECT_HIDDEN)) {
 		tottri = 0;
-		for (i = 0; i < em->tottri; i++) {
+		for (i = 0; i < looptris_tot; i++) {
 			if (!BM_elem_flag_test(looptris[i][0]->f, BM_ELEM_HIDDEN)) {
 				tottri++;
 			}
 		}
 	}
 	else {
-		tottri = em->tottri;
+		tottri = looptris_tot;
 	}
 
 	bmtree->tree = BLI_bvhtree_new(tottri, epsilon, 8, 8);
 
-	for (i = 0; i < em->tottri; i++) {
+	for (i = 0; i < looptris_tot; i++) {
 
 		if (flag & BMBVH_RESPECT_SELECT) {
 			/* note, the arrays wont align now! take care */
-			if (!BM_elem_flag_test(em->looptris[i][0]->f, BM_ELEM_SELECT)) {
+			if (!BM_elem_flag_test(looptris[i][0]->f, BM_ELEM_SELECT)) {
 				continue;
 			}
 		}
@@ -231,14 +239,14 @@ BMFace *BKE_bmbvh_ray_cast(BMBVHTree *bmtree, const float co[3], const float dir
 	hit.index = -1;
 
 	/* ok to leave 'uv' uninitialized */
-	bmcb_data.looptris = (const BMLoop *(*)[3])bmtree->em->looptris;
+	bmcb_data.looptris = (const BMLoop *(*)[3])bmtree->looptris;
 	bmcb_data.cos_cage = (const float (*)[3])bmtree->cos_cage;
 	
 	BLI_bvhtree_ray_cast(bmtree->tree, co, dir, radius, &hit, bmbvh_ray_cast_cb, &bmcb_data);
 	if (hit.index != -1 && hit.dist != dist) {
 		if (r_hitout) {
 			if (bmtree->flag & BMBVH_RETURN_ORIG) {
-				BMLoop **ltri = bmtree->em->looptris[hit.index];
+				BMLoop **ltri = bmtree->looptris[hit.index];
 				interp_v3_v3v3v3_uv(r_hitout, ltri[0]->v->co, ltri[1]->v->co, ltri[2]->v->co, bmcb_data.uv);
 			}
 			else {
@@ -254,7 +262,7 @@ BMFace *BKE_bmbvh_ray_cast(BMBVHTree *bmtree, const float co[3], const float dir
 			*r_dist = hit.dist;
 		}
 
-		return bmtree->em->looptris[hit.index][0]->f;
+		return bmtree->looptris[hit.index][0]->f;
 	}
 
 	return NULL;
@@ -327,7 +335,7 @@ BMFace *BKE_bmbvh_find_face_segment(BMBVHTree *bmtree, const float co_a[3], cons
 	hit.index = -1;
 
 	/* ok to leave 'uv' uninitialized */
-	bmcb_data.looptris = (const BMLoop *(*)[3])bmtree->em->looptris;
+	bmcb_data.looptris = (const BMLoop *(*)[3])bmtree->looptris;
 	bmcb_data.cos_cage = (const float (*)[3])bmtree->cos_cage;
 	bmcb_data.co_a = co_a;
 	bmcb_data.co_b = co_b;
@@ -337,7 +345,7 @@ BMFace *BKE_bmbvh_find_face_segment(BMBVHTree *bmtree, const float co_a[3], cons
 		/* duplicate of BKE_bmbvh_ray_cast() */
 		if (r_hitout) {
 			if (bmtree->flag & BMBVH_RETURN_ORIG) {
-				BMLoop **ltri = bmtree->em->looptris[hit.index];
+				BMLoop **ltri = bmtree->looptris[hit.index];
 				interp_v3_v3v3v3_uv(r_hitout, ltri[0]->v->co, ltri[1]->v->co, ltri[2]->v->co, bmcb_data.uv);
 			}
 			else {
@@ -354,7 +362,7 @@ BMFace *BKE_bmbvh_find_face_segment(BMBVHTree *bmtree, const float co_a[3], cons
 			*r_fac = hit.dist / dist;
 		}
 
-		return bmtree->em->looptris[hit.index][0]->f;
+		return bmtree->looptris[hit.index][0]->f;
 	}
 
 	return NULL;
@@ -410,13 +418,13 @@ BMVert *BKE_bmbvh_find_vert_closest(BMBVHTree *bmtree, const float co[3], const
 	hit.dist = maxdist_sq;
 	hit.index = -1;
 
-	bmcb_data.looptris = (const BMLoop *(*)[3])bmtree->em->looptris;
+	bmcb_data.looptris = (const BMLoop *(*)[3])bmtree->looptris;
 	bmcb_data.cos_cage = (const float (*)[3])bmtree->cos_cage;
 	bmcb_data.maxdist = maxdist_sq;
 
 	BLI_bvhtree_find_nearest(bmtree->tree, co, &hit, bmbvh_find_vert_closest_cb, &bmcb_data);
 	if (hit.index != -1) {
-		BMLoop **ltri = bmtree->em->looptris[hit.index];
+		BMLoop **ltri = bmtree->looptris[hit.index];
 		return ltri[bmcb_data.index_tri]->v;
 	}