diff options
| -rw-r--r-- | source/blender/blenlib/BLI_linklist.h | 13 | ||||
| -rw-r--r-- | source/blender/blenlib/intern/BLI_linklist.c | 49 | ||||
| -rw-r--r-- | source/blender/bmesh/intern/bmesh_queries.c | 124 | ||||
| -rw-r--r-- | source/blender/bmesh/intern/bmesh_queries.h | 3 |
4 files changed, 173 insertions, 16 deletions
diff --git a/source/blender/blenlib/BLI_linklist.h b/source/blender/blenlib/BLI_linklist.h index 9c1e1f88bab..2ca363ee780 100644 --- a/source/blender/blenlib/BLI_linklist.h +++ b/source/blender/blenlib/BLI_linklist.h @@ -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__ */ diff --git a/source/blender/blenlib/intern/BLI_linklist.c b/source/blender/blenlib/intern/BLI_linklist.c index 99fc5f27726..66fcfd21fbb 100644 --- a/source/blender/blenlib/intern/BLI_linklist.c +++ b/source/blender/blenlib/intern/BLI_linklist.c @@ -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) diff --git a/source/blender/bmesh/intern/bmesh_queries.c b/source/blender/bmesh/intern/bmesh_queries.c index 6eab3c625fa..ddc8f371501 100644 --- a/source/blender/bmesh/intern/bmesh_queries.c +++ b/source/blender/bmesh/intern/bmesh_queries.c @@ -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) { diff --git a/source/blender/bmesh/intern/bmesh_queries.h b/source/blender/bmesh/intern/bmesh_queries.h index 2c931de995e..38d30b2d005 100644 --- a/source/blender/bmesh/intern/bmesh_queries.h +++ b/source/blender/bmesh/intern/bmesh_queries.h @@ -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); |