[Bf-blender-cvs] SVN commit: /data/svn/bf-blender [53795] trunk/blender/source/blender/bmesh /intern: optimize BM_face_exists(), was doing a lot of redundant checks.

Campbell Barton ideasman42 at gmail.com
Mon Jan 14 19:38:05 CET 2013


Revision: 53795
          http://projects.blender.org/scm/viewvc.php?view=rev&root=bf-blender&revision=53795
Author:   campbellbarton
Date:     2013-01-14 18:37:58 +0000 (Mon, 14 Jan 2013)
Log Message:
-----------
optimize BM_face_exists(), was doing a lot of redundant checks.

Modified Paths:
--------------
    trunk/blender/source/blender/bmesh/intern/bmesh_queries.c
    trunk/blender/source/blender/bmesh/intern/bmesh_queries.h

Modified: trunk/blender/source/blender/bmesh/intern/bmesh_queries.c
===================================================================
--- trunk/blender/source/blender/bmesh/intern/bmesh_queries.c	2013-01-14 17:52:11 UTC (rev 53794)
+++ trunk/blender/source/blender/bmesh/intern/bmesh_queries.c	2013-01-14 18:37:58 UTC (rev 53795)
@@ -278,7 +278,61 @@
 	return count;
 }
 
+
 /**
+ * Return true if all verts are in the face.
+ */
+bool BM_verts_in_face(BMFace *f, BMVert **varr, int len)
+{
+	BMLoop *l_iter, *l_first;
+
+#ifdef USE_BMESH_HOLES
+	BMLoopList *lst;
+#endif
+
+	int i;
+	bool ok = true;
+
+	/* simple check, we know can't succeed */
+	if (f->len < len) {
+		return false;
+	}
+
+	for (i = 0; i < len; i++) {
+		BM_ELEM_API_FLAG_ENABLE(varr[i], _FLAG_OVERLAP);
+	}
+
+#ifdef USE_BMESH_HOLES
+	for (lst = f->loops.first; lst; lst = lst->next)
+#endif
+	{
+
+#ifdef USE_BMESH_HOLES
+		l_iter = l_first = lst->first;
+#else
+		l_iter = l_first = f->l_first;
+#endif
+
+		do {
+			if (BM_ELEM_API_FLAG_TEST(l_iter->v, _FLAG_OVERLAP)) {
+				/* pass */
+			}
+			else {
+				ok = false;
+				break;
+			}
+
+		} while ((l_iter = l_iter->next) != l_first);
+	}
+
+	for (i = 0; i < len; i++) {
+		BM_ELEM_API_FLAG_DISABLE(varr[i], _FLAG_OVERLAP);
+	}
+
+	return ok;
+}
+
+/**
  * Returns whether or not a given edge is is part of a given face.
  */
 bool BM_edge_in_face(BMFace *f, BMEdge *e)
@@ -1273,67 +1327,94 @@
 }
 
 /**
- * Given a set of vertices \a varr, find out if
- * all those vertices overlap an existing face.
+ * Given a set of vertices (varr), find out if
+ * there is a face with exactly those vertices
+ * (and only those vertices).
  *
- * \note Making a face here is valid but in some cases you wont want to
- * make a face thats part of another.
- *
- * \returns true for overlap
- *
+ * \note there used to be a BM_face_exists_overlap function that checked for partial overlap,
+ * however this is no longer used, simple to add back.
  */
-bool BM_face_exists_overlap(BMVert **varr, int len, BMFace **r_overlapface)
+bool BM_face_exists(BMVert **varr, int len, BMFace **r_existface)
 {
+	BMVert *v_search = varr[0];  /* we can search any of the verts in the array */
 	BMIter viter;
 	BMFace *f;
-	int i, amount;
 
-	for (i = 0; i < len; i++) {
-		BM_ITER_ELEM (f, &viter, varr[i], BM_FACES_OF_VERT) {
-			amount = BM_verts_in_face_count(f, varr, len);
-			if (amount >= len) {
-				if (r_overlapface) {
-					*r_overlapface = f;
+
+#if 0
+	BM_ITER_ELEM (f, &viter, v_search, BM_FACES_OF_VERT) {
+		if (f->len == len) {
+			if (BM_verts_in_face(f, varr, len)) {
+				if (r_existface) {
+					*r_existface = f;
 				}
 				return true;
 			}
 		}
 	}
 
-	if (r_overlapface) {
-		*r_overlapface = NULL;
+	if (r_existface) {
+		*r_existface = NULL;
 	}
-
 	return false;
-}
 
-/**
- * Given a set of vertices (varr), find out if
- * there is a face with exactly those vertices
- * (and only those vertices).
- */
-bool BM_face_exists(BMVert **varr, int len, BMFace **r_existface)
-{
-	BMIter viter;
-	BMFace *f;
-	int i, amount;
+#else
 
-	for (i = 0; i < len; i++) {
-		BM_ITER_ELEM (f, &viter, varr[i], BM_FACES_OF_VERT) {
-			amount = BM_verts_in_face_count(f, varr, len);
-			if (amount == len && amount == f->len) {
+	/* faster to do the flagging once, and inline */
+	bool is_init = false;
+	bool is_found = false;
+	int i;
+
+
+	BM_ITER_ELEM (f, &viter, v_search, BM_FACES_OF_VERT) {
+		if (f->len == len) {
+			if (is_init == false) {
+				is_init = true;
+				for (i = 0; i < len; i++) {
+					BLI_assert(!BM_ELEM_API_FLAG_TEST(varr[i], _FLAG_OVERLAP));
+					BM_ELEM_API_FLAG_ENABLE(varr[i], _FLAG_OVERLAP);
+				}
+			}
+
+			is_found = true;
+
+			{
+				BMLoop *l_iter;
+				BMLoop *l_first;
+
+				l_iter = l_first = BM_FACE_FIRST_LOOP(f);
+
+				do {
+					if (!BM_ELEM_API_FLAG_TEST(l_iter->v, _FLAG_OVERLAP)) {
+						is_found = false;
+						break;
+					}
+				} while ((l_iter = l_iter->next) != l_first);
+			}
+
+			if (is_found) {
 				if (r_existface) {
 					*r_existface = f;
 				}
-				return true;
+				break;
 			}
 		}
 	}
 
-	if (r_existface) {
-		*r_existface = NULL;
+	if (is_found == false) {
+		if (r_existface) {
+			*r_existface = NULL;
+		}
 	}
-	return false;
+
+	if (is_init == true) {
+		for (i = 0; i < len; i++) {
+			BM_ELEM_API_FLAG_DISABLE(varr[i], _FLAG_OVERLAP);
+		}
+	}
+
+	return is_found;
+#endif
 }
 
 

Modified: trunk/blender/source/blender/bmesh/intern/bmesh_queries.h
===================================================================
--- trunk/blender/source/blender/bmesh/intern/bmesh_queries.h	2013-01-14 17:52:11 UTC (rev 53794)
+++ trunk/blender/source/blender/bmesh/intern/bmesh_queries.h	2013-01-14 18:37:58 UTC (rev 53795)
@@ -29,6 +29,7 @@
 
 bool    BM_vert_in_face(BMFace *f, BMVert *v);
 int     BM_verts_in_face_count(BMFace *f, BMVert **varr, int len);
+bool    BM_verts_in_face(BMFace *f, BMVert **varr, int len);
 
 bool    BM_edge_in_face(BMFace *f, BMEdge *e);
 bool    BM_edge_in_loop(BMEdge *e, BMLoop *l);
@@ -79,8 +80,6 @@
 BMEdge *BM_edge_exists(BMVert *v1, BMVert *v2);
 BMEdge *BM_edge_find_double(BMEdge *e);
 
-bool    BM_face_exists_overlap(BMVert **varr, int len, BMFace **r_existface);
-
 bool    BM_face_exists(BMVert **varr, int len, BMFace **r_existface);
 
 bool    BM_face_exists_multi(BMVert **varr, BMEdge **earr, int len);




More information about the Bf-blender-cvs mailing list