[Bf-blender-cvs] SVN commit: /data/svn/bf-blender [60618] trunk/blender/source/blender/bmesh : Triangulate Modifier changes - using scanfill

Dalai Felinto dfelinto at gmail.com
Tue Oct 8 21:28:11 CEST 2013


Revision: 60618
          http://projects.blender.org/scm/viewvc.php?view=rev&root=bf-blender&revision=60618
Author:   dfelinto
Date:     2013-10-08 19:28:11 +0000 (Tue, 08 Oct 2013)
Log Message:
-----------
Triangulate Modifier changes - using scanfill

The ear loop method is potentially too slow (O?\203?\134N).

We are not using the 'beauty' option at the moment.
I'll incorporate that next.
(and later specific methods for quad splitting)

Patch done in collaboration (and reviewed by)  with Campbell Barton.

Modified Paths:
--------------
    trunk/blender/source/blender/bmesh/intern/bmesh_core.c
    trunk/blender/source/blender/bmesh/intern/bmesh_core.h
    trunk/blender/source/blender/bmesh/intern/bmesh_polygon.c
    trunk/blender/source/blender/bmesh/intern/bmesh_polygon.h
    trunk/blender/source/blender/bmesh/tools/bmesh_triangulate.c

Modified: trunk/blender/source/blender/bmesh/intern/bmesh_core.c
===================================================================
--- trunk/blender/source/blender/bmesh/intern/bmesh_core.c	2013-10-08 19:08:21 UTC (rev 60617)
+++ trunk/blender/source/blender/bmesh/intern/bmesh_core.c	2013-10-08 19:28:11 UTC (rev 60618)
@@ -2279,3 +2279,27 @@
 	BMLoop *l = BM_face_vert_share_loop(f_sep, v_sep);
 	return bmesh_urmv_loop(bm, l);
 }
+
+/**
+ * Avoid calling this where possible,
+ * low level function for swapping faces.
+ */
+void bmesh_face_swap_data(BMesh *bm, BMFace *f_a, BMFace *f_b)
+{
+	BMLoop *l_iter, *l_first;
+
+	BLI_assert(f_a != f_b);
+
+	l_iter = l_first = BM_FACE_FIRST_LOOP(f_a);
+	do {
+		l_iter->f = f_b;
+	} while ((l_iter = l_iter->next) != l_first);
+
+	l_iter = l_first = BM_FACE_FIRST_LOOP(f_b);
+	do {
+		l_iter->f = f_a;
+	} while ((l_iter = l_iter->next) != l_first);
+
+	SWAP(BMFace, (*f_a), (*f_b));
+	bm->elem_index_dirty |= BM_FACE;
+}

Modified: trunk/blender/source/blender/bmesh/intern/bmesh_core.h
===================================================================
--- trunk/blender/source/blender/bmesh/intern/bmesh_core.h	2013-10-08 19:08:21 UTC (rev 60617)
+++ trunk/blender/source/blender/bmesh/intern/bmesh_core.h	2013-10-08 19:28:11 UTC (rev 60618)
@@ -87,4 +87,6 @@
 BMVert *bmesh_urmv(BMesh *bm, BMFace *f_sep, BMVert *v_sep);
 BMVert *bmesh_urmv_loop(BMesh *bm, BMLoop *l_sep);
 
+void    bmesh_face_swap_data(BMesh *bm, BMFace *f_a, BMFace *f_b);
+
 #endif /* __BMESH_CORE_H__ */

Modified: trunk/blender/source/blender/bmesh/intern/bmesh_polygon.c
===================================================================
--- trunk/blender/source/blender/bmesh/intern/bmesh_polygon.c	2013-10-08 19:08:21 UTC (rev 60617)
+++ trunk/blender/source/blender/bmesh/intern/bmesh_polygon.c	2013-10-08 19:28:11 UTC (rev 60618)
@@ -34,6 +34,7 @@
 
 #include "BLI_alloca.h"
 #include "BLI_math.h"
+#include "BLI_memarena.h"
 #include "BLI_scanfill.h"
 #include "BLI_listbase.h"
 
@@ -801,264 +802,127 @@
 	return crosses % 2 != 0;
 }
 
-static bool bm_face_goodline(float const (*projectverts)[2], BMFace *f, int v1i, int v2i, int v3i)
-{
-	BMLoop *l_iter;
-	BMLoop *l_first;
-
-	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)) {
-		return false;
-	}
-
-	l_iter = l_first = BM_FACE_FIRST_LOOP(f);
-	do {
-		i = BM_elem_index_get(l_iter->v);
-		copy_v2_v2(pv1, projectverts[i]);
-
-		if (ELEM3(i, v1i, v2i, v3i)) {
-#if 0
-			printf("%d in (%d, %d, %d) tri (from indices!), continuing\n", i, v1i, v2i, v3i);
-#endif
-			continue;
-		}
-
-		if (isect_point_tri_v2(pv1, v1, v2, v3) ||
-		    isect_point_tri_v2(pv1, v3, v2, v1))
-		{
-#if 0
-			if (isect_point_tri_v2(pv1, v1, v2, v3))
-				printf("%d in (%d, %d, %d)\n", v3i, i, v1i, v2i);
-			else
-				printf("%d in (%d, %d, %d)\n", v1i, i, v3i, v2i);
-#endif
-			return false;
-		}
-	} while ((l_iter = l_iter->next) != l_first);
-	return true;
-}
-
 /**
- * \brief Find Ear
+ * \brief BMESH TRIANGULATE FACE
  *
- * Used by tessellator to find the next triangle to 'clip off' of a polygon while tessellating.
+ * Currently repeatedly find the best triangle (i.e. the most "open" one), provided it does not
+ * produces a "remaining" face with too much wide/narrow angles
+ * (using cos (i.e. dot product of normalized vectors) of angles).
  *
- * \param f The face to search.
- * \param projectverts an array of face vert coords.
- * \param use_beauty Currently only applies to quads, can be extended later on.
- * \param abscoss Must be allocated by caller, and at least f->len length
- *        (allow to avoid allocating a new one for each tri!).
+ * \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 use_tag tags new flags and edges.
  */
-static BMLoop *poly_find_ear(BMFace *f, float (*projectverts)[2], const bool use_beauty, float *abscoss)
+void BM_face_triangulate(BMesh *bm, BMFace *f,
+                         BMFace **r_faces_new,
+                         MemArena *sf_arena,
+                         const bool UNUSED(use_beauty), const bool use_tag)
 {
-	BMLoop *bestear = NULL;
+	int nf_i = 0;
+	BMLoop *l_iter, *l_first, *l_new;
+	BMFace *f_new;
 
-	BMLoop *l_iter;
-	BMLoop *l_first;
+	BLI_assert(BM_face_is_normal_valid(f));
 
-	const float cos_threshold = 0.9f;
-	const float bias = 1.0f + 1e-6f;
 
-	/* just triangulate degenerate faces */
-	if (UNLIKELY(is_zero_v3(f->no))) {
-		return BM_FACE_FIRST_LOOP(f);
-	}
-
 	if (f->len == 4) {
-		BMLoop *larr[4];
-		int i = 0, i4;
-		float cos1, cos2;
-		l_iter = l_first = BM_FACE_FIRST_LOOP(f);
-		do {
-			larr[i] = l_iter;
-			i++;
-		} while ((l_iter = l_iter->next) != l_first);
+		l_first = BM_FACE_FIRST_LOOP(f);
 
-		/* pick 0/1 based on best length */
-		/* XXX Can't only rely on such test, also must check we do not get (too much) degenerated triangles!!! */
-		i = (((len_squared_v3v3(larr[0]->v->co, larr[2]->v->co) >
-		       len_squared_v3v3(larr[1]->v->co, larr[3]->v->co) * bias)) != use_beauty);
-		i4 = (i + 3) % 4;
-		/* Check produced tris aren't too flat/narrow...
-		 * Probably not the best test, but is quite efficient and should at least avoid null-area faces! */
-		cos1 = fabsf(cos_v3v3v3(larr[i4]->v->co, larr[i]->v->co, larr[i + 1]->v->co));
-		cos2 = fabsf(cos_v3v3v3(larr[i4]->v->co, larr[i + 2]->v->co, larr[i + 1]->v->co));
-#if 0
-		printf("%d, (%f, %f), (%f, %f)\n", i, cos1, cos2,
-		       fabsf(cos_v3v3v3(larr[i]->v->co, larr[i4]->v->co, larr[i + 2]->v->co)),
-		       fabsf(cos_v3v3v3(larr[i]->v->co, larr[i + 1]->v->co, larr[i + 2]->v->co)));
-#endif
-		if (cos1 < cos2)
-			cos1 = cos2;
+		f_new = BM_face_split(bm, f, l_first->v, l_first->next->next->v, &l_new, NULL, false);
+		copy_v3_v3(f_new->no, f->no);
 
-		if (cos1 > cos_threshold) {
-			if (cos1 > fabsf(cos_v3v3v3(larr[i]->v->co, larr[i4]->v->co, larr[i + 2]->v->co)) &&
-			    cos1 > fabsf(cos_v3v3v3(larr[i]->v->co, larr[i + 1]->v->co, larr[i + 2]->v->co)))
-			{
-				i = !i;
-			}
+		if (UNLIKELY(!l_new || !f_new)) {
+			fprintf(stderr, "%s: triangulator failed to split face! (bmesh internal error)\n", __func__);
 		}
-		/* 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 (*)[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;
+
+		if (use_tag) {
+			BM_elem_flag_enable(l_new->e, BM_ELEM_TAG);
+			BM_elem_flag_enable(f, BM_ELEM_TAG);
 		}
-/*		printf("%d\n", i);*/
-		bestear = larr[i];
 
+		if (r_faces_new) {
+			r_faces_new[nf_i++] = f_new;
+		}
 	}
-	else {
-		/* float angle, bestangle = 180.0f; */
-		const int len = f->len;
-		float cos, cos_best = 1.0f;
-		int i, j;
+	else if (f->len > 4) {
+		/* scanfill */
+		ScanFillContext sf_ctx;
+		ScanFillVert *sf_vert, *sf_vert_prev = NULL;
+		ScanFillFace *sf_tri;
+		int totfilltri;
 
-		/* Compute cos of all corners! */
-		i = 0;
+		/* populate scanfill */
+		BLI_scanfill_begin_arena(&sf_ctx, sf_arena);
 		l_iter = l_first = BM_FACE_FIRST_LOOP(f);
-		do {
-			const BMVert *v1 = l_iter->prev->v;
-			const BMVert *v2 = l_iter->v;
-			const BMVert *v3 = l_iter->next->v;
 
-			abscoss[i] = fabsf(cos_v3v3v3(v1->co, v2->co, v3->co));
-/*			printf("tcoss: %f\n", *tcoss);*/
-			i++;
-		} while ((l_iter = l_iter->next) != l_first);
+		/* step once before entering the loop */
+		sf_vert = BLI_scanfill_vert_add(&sf_ctx, l_iter->v->co);
+		sf_vert->tmp.p = l_iter;
+		sf_vert_prev = sf_vert;
+		l_iter = l_iter->next;
 
-		i = 0;
-		l_iter = l_first;
 		do {
-			const BMVert *v1 = l_iter->prev->v;
-			const BMVert *v2 = l_iter->v;
-			const BMVert *v3 = l_iter->next->v;
+			sf_vert = BLI_scanfill_vert_add(&sf_ctx, l_iter->v->co);
+			BLI_scanfill_edge_add(&sf_ctx, sf_vert_prev, sf_vert);
 
-			/* Compute highest cos (i.e. narrowest angle) of this tri. */
-			cos = max_fff(abscoss[i],
-			              fabsf(cos_v3v3v3(v2->co, v3->co, v1->co)),
-			              fabsf(cos_v3v3v3(v3->co, v1->co, v2->co)));
-
-			/* Compare to prev best (i.e. lowest) cos. */
-			if (cos < cos_best) {
-				if (bm_face_goodline((float const (*)[2])projectverts, f,
-				                     BM_elem_index_get(v1),
-				                     BM_elem_index_get(v2),
-				                     BM_elem_index_get(v3)))
-				{
-					/* We must check this tri would not leave a (too much) degenerated remaining face! */
-					/* For now just assume if the average of cos of all
-					 * "remaining face"'s corners is below a given threshold, it's OK. */
-					float cos_mean = fabsf(cos_v3v3v3(v1->co, v3->co, l_iter->next->next->v->co));
-					const int i_limit = (i - 1 + len) % len;
-					cos_mean += fabsf(cos_v3v3v3(l_iter->prev->prev->v->co, v1->co, v3->co));
-					j = (i + 2) % len;
-					do {
-						cos_mean += abscoss[j];
-					} while ((j = (j + 1) % len) != i_limit);
-					cos_mean /= len - 1;
-
-					/* We need a best ear in any case... */
-					if (cos_mean < cos_threshold || (!bestear && cos_mean < 1.0f)) {
-						/* OKI, keep this ear (corner...) as a potential best one! */
-						bestear = l_iter;
-						cos_best = cos;
-					}
-#if 0
-					else
-						printf("Had a nice tri (higest cos of %f, current cos_best is %f), "
-						       "but average cos of all \"remaining face\"'s corners is too high (%f)!\n",
-						       cos, cos_best, cos_mean);
-#endif
-				}
-			}
-			i++;
+			sf_vert->tmp.p = l_iter;
+			sf_vert_prev = sf_vert;
 		} while ((l_iter = l_iter->next) != l_first);
-	}
 
-	return bestear;
-}
+		BLI_scanfill_edge_add(&sf_ctx, sf_vert_prev, sf_ctx.fillvertbase.first);
 
-/**
- * \brief BMESH TRIANGULATE FACE
- *
- * Currently repeatedly find the best triangle (i.e. the most "open" one), provided it does not
- * produces a "remaining" face with too much wide/narrow angles
- * (using cos (i.e. dot product of normalized vectors) of angles).
- *
- * \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 use_tag tags new flags and edges.
- */

@@ Diff output truncated at 10240 characters. @@



More information about the Bf-blender-cvs mailing list