diff options
Diffstat (limited to 'source/blender/blenkernel/intern/pbvh_bmesh.c')
| -rw-r--r-- | source/blender/blenkernel/intern/pbvh_bmesh.c | 497 |
1 files changed, 344 insertions, 153 deletions
diff --git a/source/blender/blenkernel/intern/pbvh_bmesh.c b/source/blender/blenkernel/intern/pbvh_bmesh.c index 88dc63d6cb2..55f9f384081 100644 --- a/source/blender/blenkernel/intern/pbvh_bmesh.c +++ b/source/blender/blenkernel/intern/pbvh_bmesh.c @@ -69,11 +69,134 @@ static void pbvh_bmesh_verify(PBVH *bvh); #endif +/** \name BMesh Utility API + * + * Use some local functions which assume triangles. + * \{ */ + +/** + * Typically using BM_LOOPS_OF_VERT and BM_FACES_OF_VERT iterators are fine, + * however this is an area where performance matters so do it in-line. + * + * Take care since 'break' won't works as expected within these macros! + */ + +#define BM_LOOPS_OF_VERT_ITER_BEGIN(l_iter_radial_, v_) \ +{ \ + struct { BMVert *v; BMEdge *e_iter, *e_first; BMLoop *l_iter_radial; } _iter; \ + _iter.v = v_; \ + if (_iter.v->e) { \ + _iter.e_iter = _iter.e_first = _iter.v->e; \ + do { \ + if (_iter.e_iter->l) { \ + _iter.l_iter_radial = _iter.e_iter->l; \ + do { \ + if (_iter.l_iter_radial->v == _iter.v) { \ + l_iter_radial_ = _iter.l_iter_radial; + +#define BM_LOOPS_OF_VERT_ITER_END \ + } \ + } while ((_iter.l_iter_radial = _iter.l_iter_radial->radial_next) != _iter.e_iter->l); \ + } \ + } while ((_iter.e_iter = BM_DISK_EDGE_NEXT(_iter.e_iter, _iter.v)) != _iter.e_first); \ + } \ +} ((void)0) + +#define BM_FACES_OF_VERT_ITER_BEGIN(f_iter_, v_) \ +{ \ + BMLoop *l_iter_radial_; \ + BM_LOOPS_OF_VERT_ITER_BEGIN(l_iter_radial_, v_) { \ + f_iter_ = l_iter_radial_->f; \ + +#define BM_FACES_OF_VERT_ITER_END \ + } \ + BM_LOOPS_OF_VERT_ITER_END; \ +} + +static void bm_edges_from_tri(BMesh *bm, BMVert *v_tri[3], BMEdge *e_tri[3]) +{ + e_tri[0] = BM_edge_create(bm, v_tri[0], v_tri[1], NULL, BM_CREATE_NO_DOUBLE); + e_tri[1] = BM_edge_create(bm, v_tri[1], v_tri[2], NULL, BM_CREATE_NO_DOUBLE); + e_tri[2] = BM_edge_create(bm, v_tri[2], v_tri[0], NULL, BM_CREATE_NO_DOUBLE); +} + +BLI_INLINE void bm_face_as_array_index_tri(BMFace *f, int r_index[3]) +{ + BMLoop *l = BM_FACE_FIRST_LOOP(f); + + BLI_assert(f->len == 3); + + r_index[0] = BM_elem_index_get(l->v); l = l->next; + r_index[1] = BM_elem_index_get(l->v); l = l->next; + r_index[2] = BM_elem_index_get(l->v); +} + +/** + * A version of #BM_face_exists, optimized for triangles + * when we know the loop and the opposite vertex. + * + * Check if any triangle is formed by (l_radial_first->v, l_radial_first->next->v, v_opposite), + * at either winding (since its a triangle no special checks are needed). + * + * <pre> + * l_radial_first->v & l_radial_first->next->v + * +---+ + * | / + * | / + * + v_opposite + * </pre> + * + * Its assumed that \a l_radial_first is never forming the target face. + */ +static bool bm_face_exists_tri_from_loop_vert( + BMLoop *l_radial_first, BMVert *v_opposite, BMFace **r_face_existing) +{ + BLI_assert(!ELEM(v_opposite, l_radial_first->v, l_radial_first->next->v, l_radial_first->prev->v)); + if (l_radial_first->radial_next != l_radial_first) { + BMLoop *l_radial_iter = l_radial_first->radial_next; + do { + BLI_assert(l_radial_iter->f->len == 3); + if (l_radial_iter->prev->v == v_opposite) { + *r_face_existing = l_radial_iter->f; + return true; + } + } while ((l_radial_iter = l_radial_iter->radial_next) != l_radial_first); + } + return false; +} + +/** + * Uses a map of vertices to lookup the final target. + * References can't point to previous items (would cause infinite loop). + */ +static BMVert *bm_vert_hash_lookup_chain(GHash *deleted_verts, BMVert *v) +{ + while (true) { + BMVert **v_next_p = (BMVert **)BLI_ghash_lookup_p(deleted_verts, v); + if (v_next_p == NULL) { + /* not remapped*/ + return v; + } + else if (*v_next_p == NULL) { + /* removed and not remapped */ + return NULL; + } + else { + /* remapped */ + v = *v_next_p; + } + } +} + +/** \} */ + /****************************** Building ******************************/ /* Update node data after splitting */ -static void pbvh_bmesh_node_finalize(PBVH *bvh, int node_index, const int cd_vert_node_offset, const int cd_face_node_offset) +static void pbvh_bmesh_node_finalize( + PBVH *bvh, const int node_index, + const int cd_vert_node_offset, const int cd_face_node_offset) { GSetIterator gs_iter; PBVHNode *n = &bvh->nodes[node_index]; @@ -200,7 +323,7 @@ static void pbvh_bmesh_node_split(PBVH *bvh, const BBC *bbc_array, int node_inde break; } } - + /* Clear this node */ /* Mark this node's unique verts as unclaimed */ @@ -224,18 +347,18 @@ static void pbvh_bmesh_node_split(PBVH *bvh, const BBC *bbc_array, int node_inde if (n->layer_disp) MEM_freeN(n->layer_disp); - + n->bm_faces = NULL; n->bm_unique_verts = NULL; n->bm_other_verts = NULL; n->layer_disp = NULL; - + if (n->draw_buffers) { GPU_free_pbvh_buffers(n->draw_buffers); n->draw_buffers = NULL; } n->flag &= ~PBVH_Leaf; - + /* Recurse */ pbvh_bmesh_node_split(bvh, bbc_array, children); pbvh_bmesh_node_split(bvh, bbc_array, children + 1); @@ -292,6 +415,7 @@ static bool pbvh_bmesh_node_limit_ensure(PBVH *bvh, int node_index) /**********************************************************************/ +#if 0 static int pbvh_bmesh_node_offset_from_elem(PBVH *bvh, BMElem *ele) { switch (ele->head.htype) { @@ -304,7 +428,7 @@ static int pbvh_bmesh_node_offset_from_elem(PBVH *bvh, BMElem *ele) } -static int pbvh_bmesh_node_lookup_index(PBVH *bvh, void *key) +static int pbvh_bmesh_node_index_from_elem(PBVH *bvh, void *key) { const int cd_node_offset = pbvh_bmesh_node_offset_from_elem(bvh, key); const int node_index = BM_ELEM_CD_GET_INT((BMElem *)key, cd_node_offset); @@ -316,18 +440,45 @@ static int pbvh_bmesh_node_lookup_index(PBVH *bvh, void *key) return node_index; } -static PBVHNode *pbvh_bmesh_node_lookup(PBVH *bvh, void *key) +static PBVHNode *pbvh_bmesh_node_from_elem(PBVH *bvh, void *key) { - return &bvh->nodes[pbvh_bmesh_node_lookup_index(bvh, key)]; + return &bvh->nodes[pbvh_bmesh_node_index_from_elem(bvh, key)]; } /* typecheck */ -#define pbvh_bmesh_node_lookup_index(bvh, key) ( \ +#define pbvh_bmesh_node_index_from_elem(bvh, key) ( \ CHECK_TYPE_ANY(key, BMFace *, BMVert *), \ - pbvh_bmesh_node_lookup_index(bvh, key)) -#define pbvh_bmesh_node_lookup(bvh, key) ( \ + pbvh_bmesh_node_index_from_elem(bvh, key)) +#define pbvh_bmesh_node_from_elem(bvh, key) ( \ CHECK_TYPE_ANY(key, BMFace *, BMVert *), \ - pbvh_bmesh_node_lookup(bvh, key)) + pbvh_bmesh_node_from_elem(bvh, key)) +#endif + +BLI_INLINE int pbvh_bmesh_node_index_from_vert(PBVH *bvh, const BMVert *key) +{ + const int node_index = BM_ELEM_CD_GET_INT((const BMElem *)key, bvh->cd_vert_node_offset); + BLI_assert(node_index != DYNTOPO_NODE_NONE); + BLI_assert(node_index < bvh->totnode); + return node_index; +} + +BLI_INLINE int pbvh_bmesh_node_index_from_face(PBVH *bvh, const BMFace *key) +{ + const int node_index = BM_ELEM_CD_GET_INT((const BMElem *)key, bvh->cd_face_node_offset); + BLI_assert(node_index != DYNTOPO_NODE_NONE); + BLI_assert(node_index < bvh->totnode); + return node_index; +} + +BLI_INLINE PBVHNode *pbvh_bmesh_node_from_vert(PBVH *bvh, const BMVert *key) +{ + return &bvh->nodes[pbvh_bmesh_node_index_from_vert(bvh, key)]; +} + +BLI_INLINE PBVHNode *pbvh_bmesh_node_from_face(PBVH *bvh, const BMFace *key) +{ + return &bvh->nodes[pbvh_bmesh_node_index_from_face(bvh, key)]; +} static BMVert *pbvh_bmesh_vert_create( @@ -357,6 +508,9 @@ static BMVert *pbvh_bmesh_vert_create( return v; } +/** + * \note Callers are responsible for checking if the face exists before adding. + */ static BMFace *pbvh_bmesh_face_create( PBVH *bvh, int node_index, BMVert *v_tri[3], BMEdge *e_tri[3], @@ -367,7 +521,7 @@ static BMFace *pbvh_bmesh_face_create( /* ensure we never add existing face */ BLI_assert(BM_face_exists(v_tri, 3, NULL) == false); - BMFace *f = BM_face_create(bvh->bm, v_tri, e_tri, 3, f_example, BM_CREATE_NO_DOUBLE); + BMFace *f = BM_face_create(bvh->bm, v_tri, e_tri, 3, f_example, BM_CREATE_NOP); f->head.hflag = f_example->head.hflag; BLI_gset_insert(node->bm_faces, f); @@ -387,16 +541,16 @@ static BMFace *pbvh_bmesh_face_create( #if 0 static int pbvh_bmesh_node_vert_use_count(PBVH *bvh, PBVHNode *node, BMVert *v) { - BMIter bm_iter; BMFace *f; int count = 0; - BM_ITER_ELEM (f, &bm_iter, v, BM_FACES_OF_VERT) { - PBVHNode *f_node = pbvh_bmesh_node_lookup(bvh, f); + BM_FACES_OF_VERT_ITER_BEGIN(f, v) { + PBVHNode *f_node = pbvh_bmesh_node_from_face(bvh, f); if (f_node == node) { count++; } } + BM_FACES_OF_VERT_ITER_END; return count; } @@ -407,19 +561,19 @@ static int pbvh_bmesh_node_vert_use_count(PBVH *bvh, PBVHNode *node, BMVert *v) static int pbvh_bmesh_node_vert_use_count_ex(PBVH *bvh, PBVHNode *node, BMVert *v, const int count_max) { - BMIter bm_iter; - BMFace *f; int count = 0; + BMFace *f; - BM_ITER_ELEM (f, &bm_iter, v, BM_FACES_OF_VERT) { - PBVHNode *f_node = pbvh_bmesh_node_lookup(bvh, f); + BM_FACES_OF_VERT_ITER_BEGIN(f, v) { + PBVHNode *f_node = pbvh_bmesh_node_from_face(bvh, f); if (f_node == node) { count++; if (count == count_max) { - break; + return count; } } } + BM_FACES_OF_VERT_ITER_END; return count; } @@ -427,16 +581,17 @@ static int pbvh_bmesh_node_vert_use_count_ex(PBVH *bvh, PBVHNode *node, BMVert * /* Return a node that uses vertex 'v' other than its current owner */ static PBVHNode *pbvh_bmesh_vert_other_node_find(PBVH *bvh, BMVert *v) { - BMIter bm_iter; + PBVHNode *current_node = pbvh_bmesh_node_from_vert(bvh, v); BMFace *f; - PBVHNode *current_node = pbvh_bmesh_node_lookup(bvh, v); - BM_ITER_ELEM (f, &bm_iter, v, BM_FACES_OF_VERT) { - PBVHNode *f_node = pbvh_bmesh_node_lookup(bvh, f); + BM_FACES_OF_VERT_ITER_BEGIN(f, v) { + PBVHNode *f_node = pbvh_bmesh_node_from_face(bvh, f); - if (f_node != current_node) + if (f_node != current_node) { return f_node; + } } + BM_FACES_OF_VERT_ITER_END; return NULL; } @@ -445,7 +600,7 @@ static void pbvh_bmesh_vert_ownership_transfer( PBVH *bvh, PBVHNode *new_owner, BMVert *v) { - PBVHNode *current_owner = pbvh_bmesh_node_lookup(bvh, v); + PBVHNode *current_owner = pbvh_bmesh_node_from_vert(bvh, v); /* mark node for update */ current_owner->flag |= PBVH_UpdateDrawBuffers | PBVH_UpdateBB; @@ -469,36 +624,36 @@ static void pbvh_bmesh_vert_remove(PBVH *bvh, BMVert *v) /* never match for first time */ int f_node_index_prev = DYNTOPO_NODE_NONE; - PBVHNode *v_node = pbvh_bmesh_node_lookup(bvh, v); + PBVHNode *v_node = pbvh_bmesh_node_from_vert(bvh, v); BLI_gset_remove(v_node->bm_unique_verts, v, NULL); BM_ELEM_CD_SET_INT(v, bvh->cd_vert_node_offset, DYNTOPO_NODE_NONE); /* Have to check each neighboring face's node */ - BMIter bm_iter; BMFace *f; - BM_ITER_ELEM (f, &bm_iter, v, BM_FACES_OF_VERT) { - const int f_node_index = pbvh_bmesh_node_lookup_index(bvh, f); + BM_FACES_OF_VERT_ITER_BEGIN(f, v) { + const int f_node_index = pbvh_bmesh_node_index_from_face(bvh, f); /* faces often share the same node, * quick check to avoid redundant #BLI_gset_remove calls */ - if (f_node_index_prev == f_node_index) - continue; - f_node_index_prev = f_node_index; + if (f_node_index_prev != f_node_index) { + f_node_index_prev = f_node_index; - PBVHNode *f_node = &bvh->nodes[f_node_index]; - f_node->flag |= PBVH_UpdateDrawBuffers | PBVH_UpdateBB; + PBVHNode *f_node = &bvh->nodes[f_node_index]; + f_node->flag |= PBVH_UpdateDrawBuffers | PBVH_UpdateBB; - /* Remove current ownership */ - BLI_gset_remove(f_node->bm_other_verts, v, NULL); + /* Remove current ownership */ + BLI_gset_remove(f_node->bm_other_verts, v, NULL); - BLI_assert(!BLI_gset_haskey(f_node->bm_unique_verts, v)); - BLI_assert(!BLI_gset_haskey(f_node->bm_other_verts, v)); + BLI_assert(!BLI_gset_haskey(f_node->bm_unique_verts, v)); + BLI_assert(!BLI_gset_haskey(f_node->bm_other_verts, v)); + } } + BM_FACES_OF_VERT_ITER_END; } static void pbvh_bmesh_face_remove(PBVH *bvh, BMFace *f) { - PBVHNode *f_node = pbvh_bmesh_node_lookup(bvh, f); + PBVHNode *f_node = pbvh_bmesh_node_from_face(bvh, f); /* Check if any of this face's vertices need to be removed * from the node */ @@ -923,13 +1078,6 @@ static void short_edge_queue_create( /*************************** Topology update **************************/ -static void bm_edges_from_tri(BMesh *bm, BMVert *v_tri[3], BMEdge *e_tri[3]) -{ - e_tri[0] = BM_edge_create(bm, v_tri[0], v_tri[1], NULL, BM_CREATE_NO_DOUBLE); - e_tri[1] = BM_edge_create(bm, v_tri[1], v_tri[2], NULL, BM_CREATE_NO_DOUBLE); - e_tri[2] = BM_edge_create(bm, v_tri[2], v_tri[0], NULL, BM_CREATE_NO_DOUBLE); -} - static void pbvh_bmesh_split_edge( EdgeQueueContext *eq_ctx, PBVH *bvh, BMEdge *e, BLI_Buffer *edge_loops) @@ -1101,15 +1249,16 @@ static bool pbvh_bmesh_subdivide_long_edges( static void pbvh_bmesh_collapse_edge( PBVH *bvh, BMEdge *e, BMVert *v1, BMVert *v2, - GSet *deleted_verts, + GHash *deleted_verts, BLI_Buffer *deleted_faces, EdgeQueueContext *eq_ctx) { BMVert *v_del, *v_conn; - float mask_v1 = BM_ELEM_CD_GET_FLOAT(v1, eq_ctx->cd_vert_mask_offset); /* one of the two vertices may be masked, select the correct one for deletion */ - if (mask_v1 < 1.0f) { + if (BM_ELEM_CD_GET_FLOAT(v1, eq_ctx->cd_vert_mask_offset) < + BM_ELEM_CD_GET_FLOAT(v2, eq_ctx->cd_vert_mask_offset)) + { v_del = v1; v_conn = v2; } @@ -1141,33 +1290,43 @@ static void pbvh_bmesh_collapse_edge( * really buy anything. */ BLI_buffer_empty(deleted_faces); - BMIter bm_iter; - BMFace *f; + BMLoop *l; - BM_ITER_ELEM (f, &bm_iter, v_del, BM_FACES_OF_VERT) { - BMVert *v_tri[3]; + BM_LOOPS_OF_VERT_ITER_BEGIN(l, v_del) { BMFace *existing_face; /* Get vertices, replace use of v_del with v_conn */ // BM_iter_as_array(NULL, BM_VERTS_OF_FACE, f, (void **)v_tri, 3); + BMFace *f = l->f; +#if 0 + BMVert *v_tri[3]; BM_face_as_array_vert_tri(f, v_tri); for (int i = 0; i < 3; i++) { if (v_tri[i] == v_del) { v_tri[i] = v_conn; } } +#endif /* Check if a face using these vertices already exists. If so, * skip adding this face and mark the existing one for * deletion as well. Prevents extraneous "flaps" from being * created. */ - if (BM_face_exists(v_tri, 3, &existing_face)) { +#if 0 + if (UNLIKELY(BM_face_exists(v_tri, 3, &existing_face))) +#else + if (UNLIKELY(bm_face_exists_tri_from_loop_vert(l->next, v_conn, &existing_face))) +#endif + { BLI_assert(existing_face); BLI_buffer_append(deleted_faces, BMFace *, existing_face); } else { + BMVert *v_tri[3] = {v_conn, l->next->v, l->prev->v}; + + BLI_assert(BM_face_exists(v_tri, 3, NULL) == false); BMEdge *e_tri[3]; - PBVHNode *n = pbvh_bmesh_node_lookup(bvh, f); + PBVHNode *n = pbvh_bmesh_node_from_face(bvh, f); int ni = n - bvh->nodes; bm_edges_from_tri(bvh->bm, v_tri, e_tri); pbvh_bmesh_face_create(bvh, ni, v_tri, e_tri, f); @@ -1180,6 +1339,7 @@ static void pbvh_bmesh_collapse_edge( BLI_buffer_append(deleted_faces, BMFace *, f); } + BM_LOOPS_OF_VERT_ITER_END; /* Delete the tagged faces */ for (int i = 0; i < deleted_faces->count; i++) { @@ -1209,10 +1369,14 @@ static void pbvh_bmesh_collapse_edge( * remove them from the PBVH */ for (int j = 0; j < 3; j++) { if ((v_tri[j] != v_del) && (v_tri[j]->e == NULL)) { - BLI_gset_insert(deleted_verts, v_tri[j]); pbvh_bmesh_vert_remove(bvh, v_tri[j]); BM_log_vert_removed(bvh->bm_log, v_tri[j], eq_ctx->cd_vert_mask_offset); + + if (v_tri[j] == v_conn) { + v_conn = NULL; + } + BLI_ghash_insert(deleted_verts, v_tri[j], NULL); BM_vert_kill(bvh->bm, v_tri[j]); } } @@ -1220,17 +1384,26 @@ static void pbvh_bmesh_collapse_edge( /* Move v_conn to the midpoint of v_conn and v_del (if v_conn still exists, it * may have been deleted above) */ - if (!BLI_gset_haskey(deleted_verts, v_conn)) { + if (v_conn != NULL) { BM_log_vert_before_modified(bvh->bm_log, v_conn, eq_ctx->cd_vert_mask_offset); mid_v3_v3v3(v_conn->co, v_conn->co, v_del->co); add_v3_v3(v_conn->no, v_del->no); normalize_v3(v_conn->no); + + /* update boundboxes attached to the connected vertex + * note that we can often get-away without this but causes T48779 */ + BM_LOOPS_OF_VERT_ITER_BEGIN(l, v_conn) { + PBVHNode *f_node = pbvh_bmesh_node_from_face(bvh, l->f); + f_node->flag |= PBVH_UpdateDrawBuffers | PBVH_UpdateNormals | PBVH_UpdateBB; + } + BM_LOOPS_OF_VERT_ITER_END; } /* Delete v_del */ BLI_assert(!BM_vert_face_check(v_del)); - BLI_gset_insert(deleted_verts, v_del); BM_log_vert_removed(bvh->bm_log, v_del, eq_ctx->cd_vert_mask_offset); + /* v_conn == NULL is OK */ + BLI_ghash_insert(deleted_verts, v_del, v_conn); BM_vert_kill(bvh->bm, v_del); } @@ -1241,17 +1414,19 @@ static bool pbvh_bmesh_collapse_short_edges( { const float min_len_squared = bvh->bm_min_edge_len * bvh->bm_min_edge_len; bool any_collapsed = false; - GSet *deleted_verts = BLI_gset_ptr_new("deleted_verts"); + /* deleted verts point to vertices they were merged into, or NULL when removed. */ + GHash *deleted_verts = BLI_ghash_ptr_new("deleted_verts"); while (!BLI_heap_is_empty(eq_ctx->q->heap)) { BMVert **pair = BLI_heap_popmin(eq_ctx->q->heap); - BMVert *v1 = pair[0], *v2 = pair[1]; + BMVert *v1 = pair[0], *v2 = pair[1]; BLI_mempool_free(eq_ctx->pool, pair); pair = NULL; /* Check the verts still exist */ - if (BLI_gset_haskey(deleted_verts, v1) || - BLI_gset_haskey(deleted_verts, v2)) + if (!(v1 = bm_vert_hash_lookup_chain(deleted_verts, v1)) || + !(v2 = bm_vert_hash_lookup_chain(deleted_verts, v2)) || + (v1 == v2)) { continue; } @@ -1285,7 +1460,7 @@ static bool pbvh_bmesh_collapse_short_edges( deleted_faces, eq_ctx); } - BLI_gset_free(deleted_verts, NULL); + BLI_ghash_free(deleted_verts, NULL, NULL); return any_collapsed; } @@ -1406,18 +1581,23 @@ void pbvh_bmesh_normals_update(PBVHNode **nodes, int totnode) } } -typedef struct FastNodeBuildInfo { +struct FastNodeBuildInfo { int totface; /* number of faces */ int start; /* start of faces in array */ struct FastNodeBuildInfo *child1; struct FastNodeBuildInfo *child2; -} FastNodeBuildInfo; +}; -/* Recursively split the node if it exceeds the leaf_limit. This function is multithreadabe since each invocation applies - * to a sub part of the arrays */ -static void pbvh_bmesh_node_limit_ensure_fast(PBVH *bvh, BMFace **nodeinfo, BBC *bbc_array, FastNodeBuildInfo *node, MemArena *arena) +/** + * Recursively split the node if it exceeds the leaf_limit. + * This function is multithreadabe since each invocation applies + * to a sub part of the arrays + */ +static void pbvh_bmesh_node_limit_ensure_fast( + PBVH *bvh, BMFace **nodeinfo, BBC *bbc_array, struct FastNodeBuildInfo *node, + MemArena *arena) { - FastNodeBuildInfo *child1, *child2; + struct FastNodeBuildInfo *child1, *child2; if (node->totface <= bvh->leaf_limit) { return; @@ -1497,8 +1677,8 @@ static void pbvh_bmesh_node_limit_ensure_fast(PBVH *bvh, BMFace **nodeinfo, BBC * each sequential part belonging to one node only */ BLI_assert((num_child1 + num_child2) == node->totface); - node->child1 = child1 = BLI_memarena_alloc(arena, sizeof(FastNodeBuildInfo)); - node->child2 = child2 = BLI_memarena_alloc(arena, sizeof(FastNodeBuildInfo)); + node->child1 = child1 = BLI_memarena_alloc(arena, sizeof(struct FastNodeBuildInfo)); + node->child2 = child2 = BLI_memarena_alloc(arena, sizeof(struct FastNodeBuildInfo)); child1->totface = num_child1; child1->start = node->start; @@ -1510,7 +1690,9 @@ static void pbvh_bmesh_node_limit_ensure_fast(PBVH *bvh, BMFace **nodeinfo, BBC pbvh_bmesh_node_limit_ensure_fast(bvh, nodeinfo, bbc_array, child2, arena); } -static void pbvh_bmesh_create_nodes_fast_recursive(PBVH *bvh, BMFace **nodeinfo, BBC *bbc_array, FastNodeBuildInfo *node, int node_index) +static void pbvh_bmesh_create_nodes_fast_recursive( + PBVH *bvh, BMFace **nodeinfo, BBC *bbc_array, + struct FastNodeBuildInfo *node, int node_index) { PBVHNode *n = bvh->nodes + node_index; /* two cases, node does not have children or does have children */ @@ -1651,7 +1833,7 @@ void BKE_pbvh_build_bmesh( bm->elem_index_dirty |= BM_FACE; /* setup root node */ - FastNodeBuildInfo rootnode = {0}; + struct FastNodeBuildInfo rootnode = {0}; rootnode.totface = bm->totface; /* start recursion, assign faces to nodes accordingly */ @@ -1693,12 +1875,14 @@ bool BKE_pbvh_bmesh_update_topology( if (mode & PBVH_Collapse) { EdgeQueue q; BLI_mempool *queue_pool = BLI_mempool_create(sizeof(BMVert *[2]), 0, 128, BLI_MEMPOOL_NOP); - EdgeQueueContext eq_ctx = {&q, queue_pool, bvh->bm, cd_vert_mask_offset, cd_vert_node_offset, cd_face_node_offset}; + EdgeQueueContext eq_ctx = { + &q, queue_pool, bvh->bm, + cd_vert_mask_offset, cd_vert_node_offset, cd_face_node_offset, + }; short_edge_queue_create(&eq_ctx, bvh, center, view_normal, radius); - modified |= !BLI_heap_is_empty(q.heap); - pbvh_bmesh_collapse_short_edges(&eq_ctx, bvh, - &deleted_faces); + modified |= pbvh_bmesh_collapse_short_edges( + &eq_ctx, bvh, &deleted_faces); BLI_heap_free(q.heap, NULL); BLI_mempool_destroy(queue_pool); } @@ -1706,15 +1890,18 @@ bool BKE_pbvh_bmesh_update_topology( if (mode & PBVH_Subdivide) { EdgeQueue q; BLI_mempool *queue_pool = BLI_mempool_create(sizeof(BMVert *[2]), 0, 128, BLI_MEMPOOL_NOP); - EdgeQueueContext eq_ctx = {&q, queue_pool, bvh->bm, cd_vert_mask_offset, cd_vert_node_offset, cd_face_node_offset}; + EdgeQueueContext eq_ctx = { + &q, queue_pool, bvh->bm, + cd_vert_mask_offset, cd_vert_node_offset, cd_face_node_offset, + }; long_edge_queue_create(&eq_ctx, bvh, center, view_normal, radius); - modified |= !BLI_heap_is_empty(q.heap); - pbvh_bmesh_subdivide_long_edges(&eq_ctx, bvh, &edge_loops); + modified |= pbvh_bmesh_subdivide_long_edges( + &eq_ctx, bvh, &edge_loops); BLI_heap_free(q.heap, NULL); BLI_mempool_destroy(queue_pool); } - + /* Unmark nodes */ for (int n = 0; n < bvh->totnode; n++) { PBVHNode *node = &bvh->nodes[n]; @@ -1735,16 +1922,6 @@ bool BKE_pbvh_bmesh_update_topology( return modified; } -BLI_INLINE void bm_face_as_array_index_tri(BMFace *f, int r_index[3]) -{ - BMLoop *l = BM_FACE_FIRST_LOOP(f); - - BLI_assert(f->len == 3); - - r_index[0] = BM_elem_index_get(l->v); l = l->next; - r_index[1] = BM_elem_index_get(l->v); l = l->next; - r_index[2] = BM_elem_index_get(l->v); -} /* In order to perform operations on the original node coordinates * (currently just raycast), store the node's triangles and vertices. @@ -1858,8 +2035,8 @@ static void pbvh_bmesh_print(PBVH *bvh) BMFace *f; BM_ITER_MESH(f, &iter, bvh->bm, BM_FACES_OF_MESH) { fprintf(stderr, " %d -> %d\n", - BM_elem_index_get(v), - pbvh_bmesh_node_lookup_index(bvh, f)); + BM_elem_index_get(f), + pbvh_bmesh_node_index_from_face(bvh, f)); } fprintf(stderr, "bm_vert_to_node:\n"); @@ -1867,7 +2044,7 @@ static void pbvh_bmesh_print(PBVH *bvh) BM_ITER_MESH(v, &iter, bvh->bm, BM_FACES_OF_MESH) { fprintf(stderr, " %d -> %d\n", BM_elem_index_get(v), - pbvh_bmesh_node_lookup_index(bvh, v)); + pbvh_bmesh_node_index_from_vert(bvh, v)); } for (int n = 0; n < bvh->totnode; n++) { @@ -1909,17 +2086,23 @@ static void pbvh_bmesh_verify(PBVH *bvh) { /* build list of faces & verts to lookup */ GSet *faces_all = BLI_gset_ptr_new_ex(__func__, bvh->bm->totface); - BMFace *f; BMIter iter; - BM_ITER_MESH(f, &iter, bvh->bm, BM_FACES_OF_MESH) { - BLI_gset_insert(faces_all, f); + + { + BMFace *f; + BM_ITER_MESH(f, &iter, bvh->bm, BM_FACES_OF_MESH) { + BLI_assert(BM_ELEM_CD_GET_INT(f, bvh->cd_face_node_offset) != DYNTOPO_NODE_NONE); + BLI_gset_insert(faces_all, f); + } } GSet *verts_all = BLI_gset_ptr_new_ex(__func__, bvh->bm->totvert); - BMVert *v; - BM_ITER_MESH(v, &iter, bvh->bm, BM_VERTS_OF_MESH) { - if (BM_ELEM_CD_GET_INT(v, bvh->cd_vert_node_offset) != DYNTOPO_NODE_NONE) { - BLI_gset_insert(verts_all, v); + { + BMVert *v; + BM_ITER_MESH(v, &iter, bvh->bm, BM_VERTS_OF_MESH) { + if (BM_ELEM_CD_GET_INT(v, bvh->cd_vert_node_offset) != DYNTOPO_NODE_NONE) { + BLI_gset_insert(verts_all, v); + } } } @@ -1936,76 +2119,83 @@ static void pbvh_bmesh_verify(PBVH *bvh) BLI_assert(totvert == BLI_gset_size(verts_all)); } - BM_ITER_MESH(f, &iter, bvh->bm, BM_FACES_OF_MESH) { - BMIter bm_iter; - BMVert *v; - PBVHNode *n = pbvh_bmesh_node_lookup(bvh, f); + { + BMFace *f; + BM_ITER_MESH(f, &iter, bvh->bm, BM_FACES_OF_MESH) { + BMIter bm_iter; + BMVert *v; + PBVHNode *n = pbvh_bmesh_node_lookup(bvh, f); - /* Check that the face's node is a leaf */ - BLI_assert(n->flag & PBVH_Leaf); + /* Check that the face's node is a leaf */ + BLI_assert(n->flag & PBVH_Leaf); - /* Check that the face's node knows it owns the face */ - BLI_assert(BLI_gset_haskey(n->bm_faces, f)); + /* Check that the face's node knows it owns the face */ + BLI_assert(BLI_gset_haskey(n->bm_faces, f)); - /* Check the face's vertices... */ - BM_ITER_ELEM (v, &bm_iter, f, BM_VERTS_OF_FACE) { - PBVHNode *nv; + /* Check the face's vertices... */ + BM_ITER_ELEM (v, &bm_iter, f, BM_VERTS_OF_FACE) { + PBVHNode *nv; - /* Check that the vertex is in the node */ - BLI_assert(BLI_gset_haskey(n->bm_unique_verts, v) ^ - BLI_gset_haskey(n->bm_other_verts, v)); + /* Check that the vertex is in the node */ + BLI_assert(BLI_gset_haskey(n->bm_unique_verts, v) ^ + BLI_gset_haskey(n->bm_other_verts, v)); - /* Check that the vertex has a node owner */ - nv = pbvh_bmesh_node_lookup(bvh, v); + /* Check that the vertex has a node owner */ + nv = pbvh_bmesh_node_lookup(bvh, v); - /* Check that the vertex's node knows it owns the vert */ - BLI_assert(BLI_gset_haskey(nv->bm_unique_verts, v)); + /* Check that the vertex's node knows it owns the vert */ + BLI_assert(BLI_gset_haskey(nv->bm_unique_verts, v)); - /* Check that the vertex isn't duplicated as an 'other' vert */ - BLI_assert(!BLI_gset_haskey(nv->bm_other_verts, v)); + /* Check that the vertex isn't duplicated as an 'other' vert */ + BLI_assert(!BLI_gset_haskey(nv->bm_other_verts, v)); + } } } /* Check verts */ - BM_ITER_MESH(v, &iter, bvh->bm, BM_VERTS_OF_MESH) { - /* vertex isn't tracked */ - if (BM_ELEM_CD_GET_INT(v, bvh->cd_vert_node_offset) == DYNTOPO_NODE_NONE) { - continue; - } + { + BMVert *v; + BM_ITER_MESH(v, &iter, bvh->bm, BM_VERTS_OF_MESH) { + /* vertex isn't tracked */ + if (BM_ELEM_CD_GET_INT(v, bvh->cd_vert_node_offset) == DYNTOPO_NODE_NONE) { + continue; + } - PBVHNode *n = pbvh_bmesh_node_lookup(bvh, v); + PBVHNode *n = pbvh_bmesh_node_lookup(bvh, v); - /* Check that the vert's node is a leaf */ - BLI_assert(n->flag & PBVH_Leaf); + /* Check that the vert's node is a leaf */ + BLI_assert(n->flag & PBVH_Leaf); - /* Check that the vert's node knows it owns the vert */ - BLI_assert(BLI_gset_haskey(n->bm_unique_verts, v)); + /* Check that the vert's node knows it owns the vert */ + BLI_assert(BLI_gset_haskey(n->bm_unique_verts, v)); - /* Check that the vertex isn't duplicated as an 'other' vert */ - BLI_assert(!BLI_gset_haskey(n->bm_other_verts, v)); + /* Check that the vertex isn't duplicated as an 'other' vert */ + BLI_assert(!BLI_gset_haskey(n->bm_other_verts, v)); - /* Check that the vert's node also contains one of the vert's - * adjacent faces */ - bool found = false; - BMIter bm_iter; - BM_ITER_ELEM (f, &bm_iter, v, BM_FACES_OF_VERT) { - if (pbvh_bmesh_node_lookup(bvh, f) == n) { - found = true; - break; + /* Check that the vert's node also contains one of the vert's + * adjacent faces */ + bool found = false; + BMIter bm_iter; + BMFace *f = NULL; + BM_ITER_ELEM (f, &bm_iter, v, BM_FACES_OF_VERT) { + if (pbvh_bmesh_node_lookup(bvh, f) == n) { + found = true; + break; + } } - } - BLI_assert(found); + BLI_assert(found || f == NULL); #if 1 - /* total freak stuff, check if node exists somewhere else */ - /* Slow */ - for (int i = 0; i < bvh->totnode; i++) { - PBVHNode *n_other = &bvh->nodes[i]; - if ((n != n_other) && (n_other->bm_unique_verts)) { - BLI_assert(!BLI_gset_haskey(n_other->bm_unique_verts, v)); + /* total freak stuff, check if node exists somewhere else */ + /* Slow */ + for (int i = 0; i < bvh->totnode; i++) { + PBVHNode *n_other = &bvh->nodes[i]; + if ((n != n_other) && (n_other->bm_unique_verts)) { + BLI_assert(!BLI_gset_haskey(n_other->bm_unique_verts, v)); + } } - } #endif + } } #if 0 @@ -2049,7 +2239,8 @@ static void pbvh_bmesh_verify(PBVH *bvh) GSET_ITER (gs_iter, n->bm_other_verts) { BMVert *v = BLI_gsetIterator_getKey(&gs_iter); - BLI_assert(!BM_vert_face_check(v)); + /* this happens sometimes and seems harmless */ + // BLI_assert(!BM_vert_face_check(v)); BLI_assert(BLI_gset_haskey(verts_all, v)); } } |