new bmesh queries BM_face_exists_overlap, BM_face_exists_overlap_subset
authorCampbell Barton <ideasman42@gmail.com>
Fri, 16 Aug 2013 13:02:34 +0000 (13:02 +0000)
committerCampbell Barton <ideasman42@gmail.com>
Fri, 16 Aug 2013 13:02:34 +0000 (13:02 +0000)
the subset version of the function checks if any faces has all its verts in the given array.

also made some additions to linklist functions (arena and pool versions of append).

source/blender/blenlib/BLI_linklist.h
source/blender/blenlib/intern/BLI_linklist.c
source/blender/bmesh/intern/bmesh_queries.c
source/blender/bmesh/intern/bmesh_queries.h

index 9c1e1f88bab1395012830556806bccd0c3ed199d..2ca363ee7800a94564fbab946fbd0b6f4acb51d2 100644 (file)
@@ -54,10 +54,16 @@ struct LinkNode *BLI_linklist_find(struct LinkNode *list, int index);
 
 void    BLI_linklist_reverse(struct LinkNode **listp);
 
+void    BLI_linklist_prepend_nlink(struct LinkNode **listp, void *ptr, struct LinkNode *nlink);
 void    BLI_linklist_prepend(struct LinkNode **listp, void *ptr);
-void    BLI_linklist_append(struct LinkNode **listp, void *ptr);
 void    BLI_linklist_prepend_arena(struct LinkNode **listp, void *ptr, struct MemArena *ma);
 void    BLI_linklist_prepend_pool(struct LinkNode **listp, void *ptr, struct BLI_mempool *mempool);
+
+void    BLI_linklist_append_nlink(LinkNode **listp, void *ptr, LinkNode *nlink);
+void    BLI_linklist_append(struct LinkNode **listp, void *ptr);
+void    BLI_linklist_append_arena(LinkNode **listp, void *ptr, struct MemArena *ma);
+void    BLI_linklist_append_pool(LinkNode **listp, void *ptr, struct BLI_mempool *mempool);
+
 void   *BLI_linklist_pop(struct LinkNode **listp);
 void   *BLI_linklist_pop_pool(struct LinkNode **listp, struct BLI_mempool *mempool);
 void    BLI_linklist_insert_after(struct LinkNode **listp, void *ptr);
@@ -67,4 +73,7 @@ void    BLI_linklist_freeN(struct LinkNode *list);
 void    BLI_linklist_free_pool(LinkNode *list, LinkNodeFreeFP freefunc, struct BLI_mempool *mempool);
 void    BLI_linklist_apply(struct LinkNode *list, LinkNodeApplyFP applyfunc, void *userdata);
 
-#endif
+#define BLI_linklist_prepend_alloca(listp, ptr) \
+       BLI_linklist_prepend_nlink(listp, ptr, alloca(sizeof(LinkNode)))
+
+#endif  /* __BLI_LINKLIST_H__ */
index 99fc5f27726139b9c903afc301c8a9dd71fe0fdb..66fcfd21fbb004a3126ba54a1c3aa66034551424 100644 (file)
@@ -89,18 +89,39 @@ void BLI_linklist_reverse(LinkNode **listp)
        *listp = rhead;
 }
 
-void BLI_linklist_prepend(LinkNode **listp, void *ptr)
+/**
+ * A version of prepend that takes the allocated link.
+ */
+void BLI_linklist_prepend_nlink(LinkNode **listp, void *ptr, LinkNode *nlink)
 {
-       LinkNode *nlink = MEM_mallocN(sizeof(*nlink), "nlink");
        nlink->link = ptr;
-       
        nlink->next = *listp;
        *listp = nlink;
 }
 
-void BLI_linklist_append(LinkNode **listp, void *ptr)
+void BLI_linklist_prepend(LinkNode **listp, void *ptr)
 {
        LinkNode *nlink = MEM_mallocN(sizeof(*nlink), "nlink");
+       BLI_linklist_prepend_nlink(listp, ptr, nlink);
+}
+
+void BLI_linklist_prepend_arena(LinkNode **listp, void *ptr, MemArena *ma)
+{
+       LinkNode *nlink = BLI_memarena_alloc(ma, sizeof(*nlink));
+       BLI_linklist_prepend_nlink(listp, ptr, nlink);
+}
+
+void BLI_linklist_prepend_pool(LinkNode **listp, void *ptr, BLI_mempool *mempool)
+{
+       LinkNode *nlink = BLI_mempool_alloc(mempool);
+       BLI_linklist_prepend_nlink(listp, ptr, nlink);
+}
+
+/**
+ * A version of append that takes the allocated link.
+ */
+void BLI_linklist_append_nlink(LinkNode **listp, void *ptr, LinkNode *nlink)
+{
        LinkNode *node = *listp;
        
        nlink->link = ptr;
@@ -117,22 +138,22 @@ void BLI_linklist_append(LinkNode **listp, void *ptr)
        }
 }
 
-void BLI_linklist_prepend_arena(LinkNode **listp, void *ptr, MemArena *ma)
+void BLI_linklist_append(LinkNode **listp, void *ptr)
+{
+       LinkNode *nlink = MEM_mallocN(sizeof(*nlink), "nlink");
+       BLI_linklist_append_nlink(listp, ptr, nlink);
+}
+
+void BLI_linklist_append_arena(LinkNode **listp, void *ptr, MemArena *ma)
 {
        LinkNode *nlink = BLI_memarena_alloc(ma, sizeof(*nlink));
-       nlink->link = ptr;
-       
-       nlink->next = *listp;
-       *listp = nlink;
+       BLI_linklist_append_nlink(listp, ptr, nlink);
 }
 
-void BLI_linklist_prepend_pool(LinkNode **listp, void *ptr, BLI_mempool *mempool)
+void BLI_linklist_append_pool(LinkNode **listp, void *ptr, BLI_mempool *mempool)
 {
        LinkNode *nlink = BLI_mempool_alloc(mempool);
-       nlink->link = ptr;
-
-       nlink->next = *listp;
-       *listp = nlink;
+       BLI_linklist_append_nlink(listp, ptr, nlink);
 }
 
 void *BLI_linklist_pop(struct LinkNode **listp)
index 6eab3c625fa0ba4da47b27a75f956c05679fb186..ddc8f3715011c9efc0ee43a2313227d7f7a4c1ea 100644 (file)
@@ -35,6 +35,7 @@
 
 #include "BLI_math.h"
 #include "BLI_alloca.h"
+#include "BLI_linklist.h"
 
 #include "bmesh.h"
 #include "intern/bmesh_private.h"
@@ -1684,6 +1685,129 @@ bool BM_face_exists_multi_edge(BMEdge **earr, int len)
        return ok;
 }
 
+
+/**
+ * Given a set of vertices (varr), find out if
+ * all those vertices overlap an existing face.
+ *
+ * \return Success
+ *
+ * \param varr  Array of unordered verts.
+ * \param len  \a varr array length.
+ * \param r_f_overlap  The overlapping face to return.
+ */
+
+bool BM_face_exists_overlap(BMVert **varr, const int len, BMFace **r_f_overlap)
+{
+       BMIter viter;
+       BMFace *f;
+       int i;
+       bool is_overlap = false;
+       LinkNode *f_lnk = NULL;
+
+       if (r_f_overlap) {
+               *r_f_overlap = NULL;
+       }
+
+#ifdef DEBUG
+       /* check flag isn't already set */
+       for(i = 0; i < len; i++) {
+               BM_ITER_ELEM (f, &viter, varr[i], BM_FACES_OF_VERT) {
+                       BLI_assert(BM_ELEM_API_FLAG_TEST(f, _FLAG_OVERLAP) == 0);
+               }
+       }
+#endif
+
+       for(i = 0; i < len; i++) {
+               BM_ITER_ELEM (f, &viter, varr[i], BM_FACES_OF_VERT) {
+                       if (BM_ELEM_API_FLAG_TEST(f, _FLAG_OVERLAP) == 0) {
+                               if (len <= BM_verts_in_face(f, varr, len)) {
+                                       if (r_f_overlap)
+                                               *r_f_overlap = f;
+
+                                       is_overlap = true;
+                                       break;
+                               }
+
+                               BM_ELEM_API_FLAG_ENABLE(f, _FLAG_OVERLAP);
+                               BLI_linklist_prepend_alloca(&f_lnk, f);
+                       }
+               }
+       }
+
+       for (; f_lnk; f_lnk = f_lnk->next) {
+               BM_ELEM_API_FLAG_DISABLE((BMFace *)f_lnk->link, _FLAG_OVERLAP);
+       }
+
+       return is_overlap;
+}
+
+/**
+ * Given a set of vertices (varr), find out if
+ * there is a face that uses vertices only from this list
+ * (that the face is a subset or made from the vertices given).
+ *
+ * \param varr  Array of unordered verts.
+ * \param len  varr array length.
+ */
+bool BM_face_exists_overlap_subset(BMVert **varr, const int len)
+{
+       BMIter viter;
+       BMFace *f;
+       int i;
+       bool is_overlap = false;
+       LinkNode *f_lnk = NULL;
+
+#ifdef DEBUG
+       /* check flag isn't already set */
+       for(i = 0; i < len; i++) {
+               BLI_assert(BM_ELEM_API_FLAG_TEST(varr[i], _FLAG_OVERLAP) == 0);
+               BM_ITER_ELEM (f, &viter, varr[i], BM_FACES_OF_VERT) {
+                       BLI_assert(BM_ELEM_API_FLAG_TEST(f, _FLAG_OVERLAP) == 0);
+               }
+       }
+#endif
+
+       for(i = 0; i < len; i++) {
+               BM_ELEM_API_FLAG_ENABLE(varr[i], _FLAG_OVERLAP);
+       }
+
+       for(i = 0; i < len; i++) {
+               BM_ITER_ELEM (f, &viter, varr[i], BM_FACES_OF_VERT) {
+                       if (BM_ELEM_API_FLAG_TEST(f, _FLAG_OVERLAP) == 0) {
+                               /* check if all vers in this face are flagged*/
+                               BMLoop *l_iter, *l_first;
+                               l_iter = l_first = BM_FACE_FIRST_LOOP(f);
+                               is_overlap = true;
+                               do {
+                                       if (BM_ELEM_API_FLAG_TEST(l_iter->v, _FLAG_OVERLAP) == 0) {
+                                               is_overlap = false;
+                                               break;
+                                       }
+                               } while ((l_iter = l_iter->next) != l_first);
+
+                               if (is_overlap) {
+                                       break;
+                               }
+
+                               BM_ELEM_API_FLAG_ENABLE(f, _FLAG_OVERLAP);
+                               BLI_linklist_prepend_alloca(&f_lnk, f);
+                       }
+               }
+       }
+
+       for(i = 0; i < len; i++) {
+               BM_ELEM_API_FLAG_DISABLE(varr[i], _FLAG_OVERLAP);
+       }
+
+       for (; f_lnk; f_lnk = f_lnk->next) {
+               BM_ELEM_API_FLAG_DISABLE((BMFace *)f_lnk->link, _FLAG_OVERLAP);
+       }
+
+       return is_overlap;
+}
+
+
 /* convenience functions for checking flags */
 bool BM_edge_is_any_vert_flag_test(const BMEdge *e, const char hflag)
 {
index 2c931de995ed28aaf4038bf8f432a5256cf70a75..38d30b2d005b03fffa9bd07c94b683560ebf288c 100644 (file)
@@ -95,6 +95,9 @@ bool    BM_face_exists(BMVert **varr, int len, BMFace **r_existface);
 bool    BM_face_exists_multi(BMVert **varr, BMEdge **earr, int len);
 bool    BM_face_exists_multi_edge(BMEdge **earr, int len);
 
+bool    BM_face_exists_overlap(BMVert **varr, const int len, BMFace **r_f_overlap);
+bool    BM_face_exists_overlap_subset(BMVert **varr, const int len);
+
 int     BM_face_share_face_count(BMFace *f_a, BMFace *f_b);
 int     BM_face_share_edge_count(BMFace *f1, BMFace *f2);