fix for crash with laplacian smooth when unselected ngons were used, volume calculation assumed unselected face were not ngons.

- added convenience function BM_face_calc_tessellation() to get triangles from an ngon.
- expose volume function as BM_mesh_calc_volume().

5 files changed, 135 insertions, 44 deletions

diff --git a/source/blender/bmesh/intern/bmesh_polygon.c b/source/blender/bmesh/intern/bmesh_polygon.c
index 9592c34fc75..c77e1603885 100644
--- a/source/blender/bmesh/intern/bmesh_polygon.c
+++ b/source/blender/bmesh/intern/bmesh_polygon.c
@@ -35,12 +35,16 @@
  *    degenerate faces.
  */
 
-#include "BLI_math.h"
-#include "BLI_array.h"
+#include "DNA_listBase.h"
 
 #include "MEM_guardedalloc.h"
 
+#include "BLI_math.h"
+#include "BLI_array.h"
+#include "BLI_scanfill.h"
+
 #include "bmesh.h"
+
 #include "intern/bmesh_private.h"
 
 /**
@@ -151,6 +155,100 @@ static void bm_face_calc_poly_normal_vertex_cos(BMFace *f, float n[3],
 }
 
 /**
+ * For tools that insist on using triangles, ideally we would cache this data.
+ *
+ * \param r_loops  Empty array of loops, (f->len)
+ * \param r_index  Empty array of loops, ((f->len - 2) * 3)
+ */
+void BM_face_calc_tessellation(BMFace *f, BMLoop **r_loops, int (*_r_index)[3])
+{
+	int *r_index = (int *)_r_index;
+	BMLoop *l_first = BM_FACE_FIRST_LOOP(f);
+	BMLoop *l_iter;
+
+	if (f->len == 3) {
+		*r_loops++ = (l_iter = l_first);
+		*r_loops++ = (l_iter = l_iter->next);
+		*r_loops++ = (         l_iter->next);
+
+		r_index[0] = 0;
+		r_index[1] = 1;
+		r_index[2] = 2;
+	}
+	else if (f->len == 4) {
+		BMLoop *l_iter;
+		*r_loops++ = (l_iter = l_first);
+		*r_loops++ = (l_iter = l_iter->next);
+		*r_loops++ = (l_iter = l_iter->next);
+		*r_loops++ = (         l_iter->next);
+
+		r_index[0] = 0;
+		r_index[1] = 1;
+		r_index[2] = 2;
+
+		r_index[3] = 0;
+		r_index[4] = 2;
+		r_index[5] = 3;
+	}
+	else {
+		int j;
+
+		ScanFillContext sf_ctx;
+		ScanFillVert *sf_vert, *sf_vert_last = NULL, *sf_vert_first = NULL;
+		/* ScanFillEdge *e; */ /* UNUSED */
+		ScanFillFace *sf_tri;
+		int totfilltri;
+
+		BLI_scanfill_begin(&sf_ctx);
+
+		j = 0;
+		l_iter = l_first;
+		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;
+			}
+
+			r_loops[j] = l_iter;
+
+			/* 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, f->no);
+		BLI_assert(totfilltri <= f->len - 2);
+		(void)totfilltri;
+
+		for (sf_tri = sf_ctx.fillfacebase.first; sf_tri; sf_tri = sf_tri->next) {
+			int i1 = BM_elem_index_get((BMLoop *)sf_tri->v1->tmp.p);
+			int i2 = BM_elem_index_get((BMLoop *)sf_tri->v2->tmp.p);
+			int i3 = BM_elem_index_get((BMLoop *)sf_tri->v3->tmp.p);
+
+			if (i1 > i2) { SWAP(int, i1, i2); }
+			if (i2 > i3) { SWAP(int, i2, i3); }
+			if (i1 > i2) { SWAP(int, i1, i2); }
+
+			*r_index++ = i1;
+			*r_index++ = i2;
+			*r_index++ = i3;
+		}
+
+		BLI_scanfill_end(&sf_ctx);
+	}
+}
+
+/**
  * get the area of the face
  */
 float BM_face_calc_area(BMFace *f)
diff --git a/source/blender/bmesh/intern/bmesh_polygon.h b/source/blender/bmesh/intern/bmesh_polygon.h
index 601caae2337..ccb85449808 100644
--- a/source/blender/bmesh/intern/bmesh_polygon.h
+++ b/source/blender/bmesh/intern/bmesh_polygon.h
@@ -27,6 +27,7 @@
  *  \ingroup bmesh
  */
 
+void  BM_face_calc_tessellation(BMFace *f, BMLoop **r_loops, int (*r_index)[3]);
 float BM_face_calc_area(BMFace *f);
 float BM_face_calc_perimeter(BMFace *f);
 void  BM_face_calc_center_bounds(BMFace *f, float center[3]);
diff --git a/source/blender/bmesh/intern/bmesh_queries.c b/source/blender/bmesh/intern/bmesh_queries.c
index 70df0b56607..54950f2af82 100644
--- a/source/blender/bmesh/intern/bmesh_queries.c
+++ b/source/blender/bmesh/intern/bmesh_queries.c
@@ -1652,3 +1652,33 @@ bool BM_face_is_any_edge_flag_test(BMFace *f, const char hflag)
 	} while ((l_iter = l_iter->next) != l_first);
 	return false;
 }
+
+float BM_mesh_calc_volume(BMesh *bm)
+{
+	/* warning, calls own tessellation function, may be slow */
+	float vol = 0.0f;
+	BMFace *f;
+	BMIter fiter;
+
+	BM_ITER_MESH (f, &fiter, bm, BM_FACES_OF_MESH) {
+		const int tottri = f->len - 2;
+		BMLoop **loops = BLI_array_alloca(loops, f->len);
+		int    (*index)[3] = BLI_array_alloca(index, tottri);
+		int j;
+
+		BM_face_calc_tessellation(f, loops, index);
+
+		for (j = 0; j < tottri; j++) {
+			const float *p1 = loops[index[j][0]]->v->co;
+			const float *p2 = loops[index[j][1]]->v->co;
+			const float *p3 = loops[index[j][2]]->v->co;
+
+			/* co1.dot(co2.cross(co3)) / 6.0 */
+			float cross[3];
+			cross_v3_v3v3(cross, p2, p3);
+			vol += (1.0f / 6.0f) * dot_v3v3(p1, cross);
+		}
+	}
+
+	return fabsf(vol);
+}
diff --git a/source/blender/bmesh/intern/bmesh_queries.h b/source/blender/bmesh/intern/bmesh_queries.h
index 7cb5749a4bf..f894912aad3 100644
--- a/source/blender/bmesh/intern/bmesh_queries.h
+++ b/source/blender/bmesh/intern/bmesh_queries.h
@@ -110,4 +110,6 @@ bool BM_edge_is_any_vert_flag_test(BMEdge *e, const char hflag);
 bool BM_face_is_any_vert_flag_test(BMFace *f, const char hflag);
 bool BM_face_is_any_edge_flag_test(BMFace *f, const char hflag);
 
+float BM_mesh_calc_volume(BMesh *bm);
+
 #endif /* __BMESH_QUERIES_H__ */
diff --git a/source/blender/bmesh/operators/bmo_smooth_laplacian.c b/source/blender/bmesh/operators/bmo_smooth_laplacian.c
index 8c5694dd4bf..311fe646125 100644
--- a/source/blender/bmesh/operators/bmo_smooth_laplacian.c
+++ b/source/blender/bmesh/operators/bmo_smooth_laplacian.c
@@ -69,7 +69,6 @@ struct BLaplacianSystem {
 };
 typedef struct BLaplacianSystem LaplacianSystem;
 
-static float compute_volume(BMesh *bm);
 static float cotan_weight(float *v1, float *v2, float *v3);
 static int vert_is_boundary(BMVert *v);
 static LaplacianSystem *init_laplacian_system(int a_numEdges, int a_numFaces, int a_numVerts);
@@ -416,45 +415,6 @@ static int vert_is_boundary(BMVert *v)
 	return 0;
 }
 
-static float compute_volume(BMesh *bm)
-{
-	float vol = 0.0f;
-	float x1, y1, z1, x2, y2, z2, x3, y3, z3, x4, y4, z4;
-	int i;
-	BMFace *f;
-	BMIter fiter;
-	BMIter vi;
-	BMVert *vn;
-	BMVert *vf[4];
-
-	BM_ITER_MESH (f, &fiter, bm, BM_FACES_OF_MESH) {
-		BM_ITER_ELEM_INDEX (vn, &vi, f, BM_VERTS_OF_FACE, i) {
-			vf[i] = vn;
-		}
-		x1 = vf[0]->co[0];
-		y1 = vf[0]->co[1];
-		z1 = vf[0]->co[2];
-
-		x2 = vf[1]->co[0];
-		y2 = vf[1]->co[1];
-		z2 = vf[1]->co[2];
-
-		x3 = vf[2]->co[0];
-		y3 = vf[2]->co[1];
-		z3 = vf[2]->co[2];
-
-		vol += (1.0f / 6.0f) * (0.0f - x3 * y2 * z1 + x2 * y3 * z1 + x3 * y1 * z2 - x1 * y3 * z2 - x2 * y1 * z3 + x1 * y2 * z3);
-
-		if (i == 4) {
-			x4 = vf[3]->co[0];
-			y4 = vf[3]->co[1];
-			z4 = vf[3]->co[2];
-			vol += (1.0f / 6.0f) * (x1 * y3 * z4 - x1 * y4 * z3 - x3 * y1 * z4 + x3 * z1 * y4 + y1 * x4 * z3 - x4 * y3 * z1);
-		}
-	}
-	return fabs(vol);
-}
-
 static void volume_preservation(BMOperator *op, float vini, float vend, int usex, int usey, int usez)
 {
 	float beta;
@@ -510,7 +470,7 @@ static void validate_solution(LaplacianSystem *sys, int usex, int usey, int usez
 	}
 
 	if (preserve_volume) {
-		vini = compute_volume(sys->bm);
+		vini = BM_mesh_calc_volume(sys->bm);
 	}
 	BMO_ITER (v, &siter, sys->op->slots_in, "verts", BM_VERT) {
 		m_vertex_id = BM_elem_index_get(v);
@@ -527,7 +487,7 @@ static void validate_solution(LaplacianSystem *sys, int usex, int usey, int usez
 		}
 	}
 	if (preserve_volume) {
-		vend = compute_volume(sys->bm);
+		vend = BM_mesh_calc_volume(sys->bm);
 		volume_preservation(sys->op, vini, vend, usex, usey, usez);
 	}