Merge remote-tracking branch 'origin/master' into openvdbopenvdb

1 files changed, 154 insertions, 8 deletions

diff --git a/source/blender/bmesh/intern/bmesh_polygon.c b/source/blender/bmesh/intern/bmesh_polygon.c
index 6acd790fc0c..7b9d17b27b5 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"
@@ -132,7 +134,7 @@ static void bm_face_calc_poly_center_mean_vertex_cos(
  */
 void BM_face_calc_tessellation(
         const BMFace *f, const bool use_fixed_quad,
-        BMLoop **r_loops, unsigned int (*r_index)[3])
+        BMLoop **r_loops, uint (*r_index)[3])
 {
 	BMLoop *l_first = BM_FACE_FIRST_LOOP(f);
 	BMLoop *l_iter;
@@ -196,7 +198,7 @@ void BM_face_calc_point_in_face(const BMFace *f, float r_co[3])
 		 * but without this we can't be sure the point is inside a concave face. */
 		const int tottri = f->len - 2;
 		BMLoop **loops = BLI_array_alloca(loops, f->len);
-		unsigned int  (*index)[3] = BLI_array_alloca(index, tottri);
+		uint (*index)[3] = BLI_array_alloca(index, tottri);
 		int j;
 		int j_best = 0;  /* use as fallback when unset */
 		float area_best  = -1.0f;
@@ -575,11 +577,11 @@ void BM_face_calc_center_mean_weighted(const BMFace *f, float r_cent[3])
  * Rotates a polygon so that it's
  * normal is pointing towards the mesh Z axis
  */
-void poly_rotate_plane(const float normal[3], float (*verts)[3], const unsigned int nverts)
+void poly_rotate_plane(const float normal[3], float (*verts)[3], const uint nverts)
 {
 	float mat[3][3];
 	float co[3];
-	unsigned int i;
+	uint i;
 
 	co[2] = 0.0f;
 
@@ -844,7 +846,7 @@ void BM_face_normal_flip_ex(
         BMesh *bm, BMFace *f,
         const int cd_loop_mdisp_offset, const bool use_loop_mdisp_flip)
 {
-	bmesh_loop_reverse(bm, f, cd_loop_mdisp_offset, use_loop_mdisp_flip);
+	bmesh_kernel_loop_reverse(bm, f, cd_loop_mdisp_offset, use_loop_mdisp_flip);
 	negate_v3(f->no);
 }
 
@@ -941,7 +943,7 @@ void BM_face_triangulate(
 
 	{
 		BMLoop **loops = BLI_array_alloca(loops, f->len);
-		unsigned int (*tris)[3] = BLI_array_alloca(tris, f->len);
+		uint (*tris)[3] = BLI_array_alloca(tris, f->len);
 		const int totfilltri = f->len - 2;
 		const int last_tri = f->len - 3;
 		int i;
@@ -1425,7 +1427,7 @@ void BM_mesh_calc_tessellation(BMesh *bm, BMLoop *(*looptris)[3], int *r_looptri
 
 			float axis_mat[3][3];
 			float (*projverts)[2];
-			unsigned int (*tris)[3];
+			uint (*tris)[3];
 
 			const int totfilltri = efa->len - 2;
 
@@ -1451,7 +1453,7 @@ void BM_mesh_calc_tessellation(BMesh *bm, BMLoop *(*looptris)[3], int *r_looptri
 
 			for (j = 0; j < totfilltri; j++) {
 				BMLoop **l_ptr = looptris[i++];
-				unsigned int *tri = tris[j];
+				uint *tri = tris[j];
 
 				l_ptr[0] = l_arr[tri[0]];
 				l_ptr[1] = l_arr[tri[1]];
@@ -1474,3 +1476,147 @@ 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;
+
+			/* #BM_verts_calc_rotate_beauty performs excessive checks we don't need!
+			 * It's meant for rotating edges, it also calculates a new normal.
+			 *
+			 * Use #BLI_polyfill_beautify_quad_rotate_calc since we have the normal.
+			 */
+#if 0
+			const bool split_13 = (BM_verts_calc_rotate_beauty(
+			        l_v1->v, l_v2->v, l_v3->v, l_v4->v, 0, 0) < 0.0f);
+#else
+			float axis_mat[3][3], v_quad[4][2];
+			axis_dominant_v3_to_m3(axis_mat, efa->no);
+			mul_v2_m3v3(v_quad[0], axis_mat, l_v1->v->co);
+			mul_v2_m3v3(v_quad[1], axis_mat, l_v2->v->co);
+			mul_v2_m3v3(v_quad[2], axis_mat, l_v3->v->co);
+			mul_v2_m3v3(v_quad[3], axis_mat, l_v4->v->co);
+
+			const bool split_13 = BLI_polyfill_beautify_quad_rotate_calc(
+			        v_quad[0], v_quad[1], v_quad[2], v_quad[3]) < 0.0f;
+#endif
+
+			BMLoop **l_ptr_a = looptris[i++];
+			BMLoop **l_ptr_b = looptris[i++];
+			if (split_13) {
+				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);
+
+}