skip calculating the normal for each face when triangulating, all callers make sure its valid. also remove some commented code (more then one generation of bmesh old).

6 files changed, 83 insertions, 139 deletions

diff --git a/source/blender/blenlib/BLI_math_matrix.h b/source/blender/blenlib/BLI_math_matrix.h
index 415c503146c..c66536bc0e5 100644
--- a/source/blender/blenlib/BLI_math_matrix.h
+++ b/source/blender/blenlib/BLI_math_matrix.h
@@ -95,6 +95,7 @@ void mul_project_m4_v3(float M[4][4], float vec[3]);
 
 void mul_m3_v3(float M[3][3], float r[3]);
 void mul_v3_m3v3(float r[3], float M[3][3], float a[3]);
+void mul_v2_m3v3(float r[2], float M[3][3], float a[3]);
 void mul_transposed_m3_v3(float M[3][3], float r[3]);
 void mul_m3_v3_double(float M[3][3], double r[3]);
 
diff --git a/source/blender/blenlib/intern/math_matrix.c b/source/blender/blenlib/intern/math_matrix.c
index 8f9ea917b8c..b7e7fea897f 100644
--- a/source/blender/blenlib/intern/math_matrix.c
+++ b/source/blender/blenlib/intern/math_matrix.c
@@ -411,6 +411,13 @@ void mul_v3_m3v3(float r[3], float M[3][3], float a[3])
 	r[2] = M[0][2] * a[0] + M[1][2] * a[1] + M[2][2] * a[2];
 }
 
+void mul_v2_m3v3(float r[2], float M[3][3], float a[3])
+{
+	r[0] = M[0][0] * a[0] + M[1][0] * a[1] + M[2][0] * a[2];
+	r[1] = M[0][1] * a[0] + M[1][1] * a[1] + M[2][1] * a[2];
+	r[2] = M[0][2] * a[0] + M[1][2] * a[1] + M[2][2] * a[2];
+}
+
 void mul_m3_v3(float M[3][3], float r[3])
 {
 	float tmp[3];
diff --git a/source/blender/blenlib/intern/math_rotation.c b/source/blender/blenlib/intern/math_rotation.c
index b38b5a2de10..e6399ed356e 100644
--- a/source/blender/blenlib/intern/math_rotation.c
+++ b/source/blender/blenlib/intern/math_rotation.c
@@ -84,6 +84,8 @@ void mul_qt_qtqt(float q[4], const float q1[4], const float q2[4])
  * \note:
  * Assumes a unit quaternion?
  *
+ * \note: multiplying by 3x3 matrix is ~25% faster.
+ *
  * in fact not, but you may want to use a unit quat, read on...
  *
  * Shortcut for 'q v q*' when \a v is actually a quaternion.
diff --git a/source/blender/bmesh/intern/bmesh_polygon.c b/source/blender/bmesh/intern/bmesh_polygon.c
index b8b7abdbc76..af8ae5f9454 100644
--- a/source/blender/bmesh/intern/bmesh_polygon.c
+++ b/source/blender/bmesh/intern/bmesh_polygon.c
@@ -297,39 +297,51 @@ static void scale_edge_v3f(float v1[3], float v2[3], const float fac)
 	add_v3_v3v3(v2, v2, mid);
 }
 
-
 /**
- * \brief POLY ROTATE PLANE
+ * \brief POLY NORMAL TO MATRIX
  *
- * Rotates a polygon so that it's
- * normal is pointing towards the mesh Z axis
+ * Creates a 3x3 matrix from a normal.
  */
-void poly_rotate_plane(const float normal[3], float (*verts)[3], const int nverts)
+static bool poly_normal_to_xy_mat3(float r_mat[3][3], const float normal[3])
 {
-
-	float up[3] = {0.0f, 0.0f, 1.0f}, axis[3], q[4];
-	float mat[3][3];
+	float up[3] = {0.0f, 0.0f, 1.0f}, axis[3];
 	float angle;
-	int i;
 
 	cross_v3_v3v3(axis, normal, up);
-
 	angle = saacos(dot_v3v3(normal, up));
 
-	if (angle < FLT_EPSILON)
-		return;
+	if (angle >= FLT_EPSILON) {
+		if (len_squared_v3(axis) < FLT_EPSILON) {
+			axis[0] = 0.0f;
+			axis[1] = 1.0f;
+			axis[2] = 0.0f;
+		}
 
-	if (len_squared_v3(axis) < FLT_EPSILON) {
-		axis[0] = 0.0f;
-		axis[1] = 1.0f;
-		axis[2] = 0.0f;
+		axis_angle_to_mat3(r_mat, axis, angle);
+		return true;
 	}
+	else {
+		unit_m3(r_mat);
+		return false;
+	}
+}
 
-	axis_angle_to_quat(q, axis, angle);
-	quat_to_mat3(mat, q);
+/**
+ * \brief POLY ROTATE PLANE
+ *
+ * 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 int nverts)
+{
+	float mat[3][3];
 
-	for (i = 0; i < nverts; i++)
-		mul_m3_v3(mat, verts[i]);
+	if (poly_normal_to_xy_mat3(mat, normal)) {
+		int i;
+		for (i = 0; i < nverts; i++) {
+			mul_m3_v3(mat, verts[i]);
+		}
+	}
 }
 
 /**
@@ -614,16 +626,16 @@ bool BM_face_point_inside_test(BMFace *f, const float co[3])
 	return crosses % 2 != 0;
 }
 
-static bool bm_face_goodline(float const (*projectverts)[3], BMFace *f, int v1i, int v2i, int v3i)
+static bool bm_face_goodline(float const (*projectverts)[2], BMFace *f, int v1i, int v2i, int v3i)
 {
 	BMLoop *l_iter;
 	BMLoop *l_first;
-	float v1[3], v2[3], v3[3], pv1[3];
-	int i;
 
-	copy_v3_v3(v1, projectverts[v1i]);
-	copy_v3_v3(v2, projectverts[v2i]);
-	copy_v3_v3(v3, projectverts[v3i]);
+	float pv1[2];
+	const float *v1 = projectverts[v1i];
+	const float *v2 = projectverts[v2i];
+	const float *v3 = projectverts[v3i];
+	int i;
 
 	/* v3 must be on the left side of [v1, v2] line, else we know [v1, v3] is outside of f! */
 	if (testedgesidef(v1, v2, v3)) {
@@ -633,7 +645,7 @@ static bool bm_face_goodline(float const (*projectverts)[3], BMFace *f, int v1i,
 	l_iter = l_first = BM_FACE_FIRST_LOOP(f);
 	do {
 		i = BM_elem_index_get(l_iter->v);
-		copy_v3_v3(pv1, projectverts[i]);
+		copy_v2_v2(pv1, projectverts[i]);
 
 		if (ELEM3(i, v1i, v2i, v3i)) {
 #if 0
@@ -665,7 +677,7 @@ static bool bm_face_goodline(float const (*projectverts)[3], BMFace *f, int v1i,
  * \param abscoss Must be allocated by caller, and at least f->len length
  *        (allow to avoid allocating a new one for each tri!).
  */
-static BMLoop *find_ear(BMFace *f, float (*verts)[3], const bool use_beauty, float *abscoss)
+static BMLoop *find_ear(BMFace *f, float (*projectverts)[2], const bool use_beauty, float *abscoss)
 {
 	BMLoop *bestear = NULL;
 
@@ -711,7 +723,7 @@ static BMLoop *find_ear(BMFace *f, float (*verts)[3], const bool use_beauty, flo
 		/* Last check we do not get overlapping triangles
 		 * (as much as possible, there are some cases with no good solution!) */
 		i4 = (i + 3) % 4;
-		if (!bm_face_goodline((float const (*)[3])verts, f, BM_elem_index_get(larr[i4]->v),
+		if (!bm_face_goodline((float const (*)[2])projectverts, f, BM_elem_index_get(larr[i4]->v),
 		                      BM_elem_index_get(larr[i]->v), BM_elem_index_get(larr[i + 1]->v)))
 		{
 			i = !i;
@@ -756,7 +768,7 @@ static BMLoop *find_ear(BMFace *f, float (*verts)[3], const bool use_beauty, flo
 			if (BM_edge_exists(v1, v3)) {
 				is_ear = false;
 			}
-			else if (!bm_face_goodline((float const (*)[3])verts, f, BM_elem_index_get(v1),
+			else if (!bm_face_goodline((float const (*)[2])projectverts, f, BM_elem_index_get(v1),
 			                           BM_elem_index_get(v2), BM_elem_index_get(v3)))
 			{
 #if 0
@@ -767,19 +779,6 @@ static BMLoop *find_ear(BMFace *f, float (*verts)[3], const bool use_beauty, flo
 			}
 
 			if (is_ear) {
-#if 0 /* Old, already commented code */
-				/* if this code comes back, it needs to be converted to radians */
-				angle = angle_v3v3v3(verts[v1->head.eflag2], verts[v2->head.eflag2], verts[v3->head.eflag2]);
-				if (!bestear || ABS(angle - 45.0f) < bestangle) {
-					bestear = l;
-					bestangle = ABS(45.0f - angle);
-				}
-
-				if (angle > 20 && angle < 90) break;
-				if (angle < 100 && i > 5) break;
-				i += 1;
-#endif
-
 				/* Compute highest cos (i.e. narrowest angle) of this tri. */
 				cos = *tcoss;
 				tcos = fabsf(cos_v3v3v3(v2->co, v3->co, v1->co));
@@ -839,50 +838,39 @@ static BMLoop *find_ear(BMFace *f, float (*verts)[3], const bool use_beauty, flo
  * produces a "remaining" face with too much wide/narrow angles
  * (using cos (i.e. dot product of normalized vectors) of angles).
  *
- * newfaces, if non-null, must be an array of BMFace pointers,
- * with a length equal to f->len. It will be filled with the new
- * triangles, and will be NULL-terminated.
+ * \param r_faces_new if non-null, must be an array of BMFace pointers,
+ * with a length equal to (f->len - 2). It will be filled with the new
+ * triangles.
  *
  * \note newedgeflag sets a flag layer flag, obviously not the header flag.
  */
 void BM_face_triangulate(BMesh *bm, BMFace *f,
-                         float (*projectverts)[3], BMFace **newfaces,
+                         BMFace **r_faces_new,
                          const bool use_beauty, const bool use_tag)
 {
-	int i, nvert, nf_i = 0;
-	bool done;
-	BMLoop *newl;
+	const float f_len_orig = f->len;
+	int i, nf_i = 0;
+	BMLoop *l_new;
 	BMLoop *l_iter;
 	BMLoop *l_first;
 	/* BM_face_triangulate: temp absolute cosines of face corners */
-	float *abscoss = BLI_array_alloca(abscoss, f->len);
+	float (*projectverts)[2] = BLI_array_alloca(projectverts, f_len_orig);
+	float *abscoss = BLI_array_alloca(abscoss, f_len_orig);
+	float mat[3][3];
+
+	poly_normal_to_xy_mat3(mat, f->no);
 
 	/* copy vertex coordinates to vertspace area */
 	i = 0;
 	l_iter = l_first = BM_FACE_FIRST_LOOP(f);
 	do {
-		copy_v3_v3(projectverts[i], l_iter->v->co);
-		BM_elem_index_set(l_iter->v, i); /* set dirty! */
-		i++;
+		mul_v2_m3v3(projectverts[i], mat, l_iter->v->co);
+		BM_elem_index_set(l_iter->v, i++); /* set dirty! */
 	} while ((l_iter = l_iter->next) != l_first);
 
 	bm->elem_index_dirty |= BM_VERT; /* see above */
 
-	/* bmesh_face_normal_update(bm, f, f->no, projectverts); */
-
-	calc_poly_normal(f->no, projectverts, f->len);
-	poly_rotate_plane(f->no, projectverts, i);
-
-	nvert = f->len;
-
-	/* calc_poly_plane(projectverts, i); */
-	for (i = 0; i < nvert; i++) {
-		projectverts[i][2] = 0.0f;
-	}
-
-	done = false;
-	while (!done && f->len > 3) {
-		done = true;
+	while (f->len > 3) {
 		l_iter = find_ear(f, projectverts, use_beauty, abscoss);
 
 		/* force triangulation - if we can't find an ear the face is degenerate */
@@ -890,70 +878,27 @@ void BM_face_triangulate(BMesh *bm, BMFace *f,
 			l_iter = BM_FACE_FIRST_LOOP(f);
 		}
 
-		{
-			done = false;
-/*			printf("Subdividing face...\n");*/
-			f = BM_face_split(bm, l_iter->f, l_iter->prev->v, l_iter->next->v, &newl, NULL, true);
-
-			if (UNLIKELY(!f)) {
-				fprintf(stderr, "%s: triangulator failed to split face! (bmesh internal error)\n", __func__);
-				break;
-			}
-
-			copy_v3_v3(f->no, l_iter->f->no);
-
-			if (use_tag) {
-				BM_elem_flag_enable(newl->e, BM_ELEM_TAG);
-				BM_elem_flag_enable(f, BM_ELEM_TAG);
-			}
-			
-			if (newfaces)
-				newfaces[nf_i++] = f;
-
-#if 0
-			l = f->loopbase;
-			do {
-				if (l->v == v) {
-					f->loopbase = l;
-					break;
-				}
-				l = l->next;
-			} while (l != f->loopbase);
-#endif
+/*		printf("Subdividing face...\n");*/
+		f = BM_face_split(bm, l_iter->f, l_iter->prev->v, l_iter->next->v, &l_new, NULL, true);
 
+		if (UNLIKELY(!f)) {
+			fprintf(stderr, "%s: triangulator failed to split face! (bmesh internal error)\n", __func__);
+			break;
 		}
-	}
 
-	BLI_assert(f->len == 3);
+		copy_v3_v3(f->no, l_iter->f->no);
 
-#if 0 /* XXX find_ear should now always return a corner, so no more need for this piece of code... */
-	if (f->len > 3) {
-		l_iter = BM_FACE_FIRST_LOOP(f);
-		while (l_iter->f->len > 3) {
-			nextloop = l_iter->next->next;
-			f = BM_face_split(bm, l_iter->f, l_iter->v, nextloop->v,
-			                  &newl, NULL, true);
-			if (!f) {
-				printf("triangle fan step of triangulator failed.\n");
-
-				/* NULL-terminate */
-				if (newfaces) newfaces[nf_i] = NULL;
-				return;
-			}
+		if (use_tag) {
+			BM_elem_flag_enable(l_new->e, BM_ELEM_TAG);
+			BM_elem_flag_enable(f, BM_ELEM_TAG);
+		}
 
-			if (newfaces) newfaces[nf_i++] = f;
-			
-			BMO_elem_flag_enable(bm, newl->e, newedge_oflag);
-			BMO_elem_flag_enable(bm, f, newface_oflag);
-			l_iter = nextloop;
+		if (r_faces_new) {
+			r_faces_new[nf_i++] = f;
 		}
 	}
-#endif
 
-	/* NULL-terminate */
-	if (newfaces) {
-		newfaces[nf_i] = NULL;
-	}
+	BLI_assert(f->len == 3);
 }
 
 /**
diff --git a/source/blender/bmesh/intern/bmesh_polygon.h b/source/blender/bmesh/intern/bmesh_polygon.h
index 7c2b1782584..601caae2337 100644
--- a/source/blender/bmesh/intern/bmesh_polygon.h
+++ b/source/blender/bmesh/intern/bmesh_polygon.h
@@ -44,7 +44,7 @@ void  BM_vert_normal_update_all(BMVert *v);
 void  BM_face_normal_flip(BMesh *bm, BMFace *f);
 bool  BM_face_point_inside_test(BMFace *f, const float co[3]);
 
-void  BM_face_triangulate(BMesh *bm, BMFace *f, float (*projectverts)[3], BMFace **newfaces,
+void  BM_face_triangulate(BMesh *bm, BMFace *f, BMFace **newfaces,
                           const bool use_beauty, const bool use_tag);
 
 void  BM_face_legal_splits(BMesh *bm, BMFace *f, BMLoop *(*loops)[2], int len);
diff --git a/source/blender/bmesh/tools/bmesh_triangulate.c b/source/blender/bmesh/tools/bmesh_triangulate.c
index 7e6e41a12e6..9948a15ea56 100644
--- a/source/blender/bmesh/tools/bmesh_triangulate.c
+++ b/source/blender/bmesh/tools/bmesh_triangulate.c
@@ -30,7 +30,6 @@
 #include "MEM_guardedalloc.h"
 
 #include "BLI_utildefines.h"
-#include "BLI_array.h"
 
 #include "bmesh.h"
 
@@ -40,27 +39,17 @@ void BM_mesh_triangulate(BMesh *bm, const bool use_beauty, const bool tag_only)
 {
 	BMIter iter;
 	BMFace *face;
-	float (*projectverts)[3] = NULL;
-	BLI_array_declare(projectverts);
 
 	if (tag_only == false) {
 		BM_ITER_MESH (face, &iter, bm, BM_FACES_OF_MESH) {
-			BLI_array_empty(projectverts);
-			BLI_array_reserve(projectverts, face->len * 3);
-
-			BM_face_triangulate(bm, face, projectverts, NULL, use_beauty, false);
+			BM_face_triangulate(bm, face, NULL, use_beauty, false);
 		}
 	}
 	else {
 		BM_ITER_MESH (face, &iter, bm, BM_FACES_OF_MESH) {
 			if (BM_elem_flag_test(face, BM_ELEM_TAG)) {
-				BLI_array_empty(projectverts);
-				BLI_array_grow_items(projectverts, face->len * 3);
-
-				BM_face_triangulate(bm, face, projectverts, NULL, use_beauty, true);
+				BM_face_triangulate(bm, face, NULL, use_beauty, true);
 			}
 		}
 	}
-
-	BLI_array_free(projectverts);
 }