From d09a9a9597018471af9f0df3d2263d1c57954a8c Mon Sep 17 00:00:00 2001 From: Campbell Barton Date: Sun, 19 Apr 2015 16:03:12 +1000 Subject: Dyntopo: USE_EDGEQUEUE_TAG broke even subdiv While adding edges to the queue multiple times is redundant, walking over them is still needed. --- source/blender/blenkernel/intern/pbvh_bmesh.c | 92 ++++++++++++++++++--------- 1 file changed, 63 insertions(+), 29 deletions(-) (limited to 'source/blender/blenkernel') diff --git a/source/blender/blenkernel/intern/pbvh_bmesh.c b/source/blender/blenkernel/intern/pbvh_bmesh.c index d54c598e988..a6939180013 100644 --- a/source/blender/blenkernel/intern/pbvh_bmesh.c +++ b/source/blender/blenkernel/intern/pbvh_bmesh.c @@ -49,6 +49,15 @@ /* don't add edges into the queue multiple times */ #define USE_EDGEQUEUE_TAG +/** + * Ensure we don't have dirty tags for the edge queue, and that they are left cleared. + * (slow, even for debug mode, so leave disabled for now). + */ +#if defined(USE_EDGEQUEUE_TAG) +# if !defined(NDEBUG) +# define USE_EDGEQUEUE_TAG_VERIFY +# endif +#endif // #define USE_VERIFY @@ -606,6 +615,37 @@ typedef struct { # define EDGE_QUEUE_DISABLE(e) BM_elem_flag_disable((CHECK_TYPE_INLINE(e, BMEdge *), e), BM_ELEM_TAG) #endif +#ifdef USE_EDGEQUEUE_TAG_VERIFY +/* simply check no edges are tagged + * (it's a requirement that edges enter and leave a clean tag state) */ +static void pbvh_bmesh_edge_tag_verify(PBVH *bvh) +{ + int n; + + for (n = 0; n < bvh->totnode; n++) { + PBVHNode *node = &bvh->nodes[n]; + GSetIterator gs_iter; + if (node->bm_faces) { + GSET_ITER (gs_iter, node->bm_faces) { + BMFace *f = BLI_gsetIterator_getKey(&gs_iter); + BMEdge *e_tri[3]; + BMLoop *l_iter; + + BLI_assert(f->len == 3); + l_iter = BM_FACE_FIRST_LOOP(f); + e_tri[0] = l_iter->e; l_iter = l_iter->next; + e_tri[1] = l_iter->e; l_iter = l_iter->next; + e_tri[2] = l_iter->e; + + BLI_assert((EDGE_QUEUE_TEST(e_tri[0]) == false) && + (EDGE_QUEUE_TEST(e_tri[1]) == false) && + (EDGE_QUEUE_TEST(e_tri[2]) == false)); + } + } + } +} +#endif + static bool edge_queue_tri_in_sphere(const EdgeQueue *q, BMFace *f) { BMVert *v_tri[3]; @@ -675,7 +715,13 @@ static void long_edge_queue_edge_add_recursive( const float len_sq, float limit_len) { BLI_assert(len_sq > SQUARE(limit_len)); - edge_queue_insert(eq_ctx, l_edge->e, -len_sq); + +#ifdef USE_EDGEQUEUE_TAG + if (EDGE_QUEUE_TEST(l_edge->e) == false) +#endif + { + edge_queue_insert(eq_ctx, l_edge->e, -len_sq); + } /* temp support previous behavior! */ if (UNLIKELY(G.debug_value == 1234)) { @@ -703,17 +749,12 @@ static void long_edge_queue_edge_add_recursive( BMLoop *l_adjacent[2] = {l_iter->next, l_iter->prev}; int i; for (i = 0; i < ARRAY_SIZE(l_adjacent); i++) { -#ifdef USE_EDGEQUEUE_TAG - if (EDGE_QUEUE_TEST(l_adjacent[i]->e) == false) -#endif - { - len_sq_other = BM_edge_calc_length_squared(l_adjacent[i]->e); - if (len_sq_other > max_ff(len_sq_cmp, limit_len_sq)) { -// edge_queue_insert(eq_ctx, l_adjacent[i]->e, -len_sq_other); - long_edge_queue_edge_add_recursive( - eq_ctx, l_adjacent[i]->radial_next, l_adjacent[i], - len_sq_other, limit_len); - } + len_sq_other = BM_edge_calc_length_squared(l_adjacent[i]->e); + if (len_sq_other > max_ff(len_sq_cmp, limit_len_sq)) { +// edge_queue_insert(eq_ctx, l_adjacent[i]->e, -len_sq_other); + long_edge_queue_edge_add_recursive( + eq_ctx, l_adjacent[i]->radial_next, l_adjacent[i], + len_sq_other, limit_len); } } } while ((l_iter = l_iter->radial_next) != l_end); @@ -748,9 +789,6 @@ static void long_edge_queue_face_add(EdgeQueueContext *eq_ctx, /* Check each edge of the face */ l_iter = l_first = BM_FACE_FIRST_LOOP(f); do { -#ifdef USE_EDGEQUEUE_TAG - if (EDGE_QUEUE_TEST(l_iter->e) == false) -#endif { #ifdef USE_EDGEQUEUE_EVEN_SUBDIV const float len_sq = BM_edge_calc_length_squared(l_iter->e); @@ -805,6 +843,11 @@ static void long_edge_queue_create(EdgeQueueContext *eq_ctx, eq_ctx->q->limit_len = bvh->bm_max_edge_len; #endif +#ifdef USE_EDGEQUEUE_TAG_VERIFY + pbvh_bmesh_edge_tag_verify(bvh); +#endif + + for (n = 0; n < bvh->totnode; n++) { PBVHNode *node = &bvh->nodes[n]; @@ -999,9 +1042,8 @@ static bool pbvh_bmesh_subdivide_long_edges(EdgeQueueContext *eq_ctx, PBVH *bvh, { bool any_subdivided = false; -#if defined(USE_EDGEQUEUE_TAG) && !defined(NDEBUG) -# define USE_EDGEQUEUE_TAG_VALIDATE - int heap_tot = 0, heap_overlap = 0; +#ifdef USE_EDGEQUEUE_TAG_VERIFY + pbvh_bmesh_edge_tag_verify(bvh); #endif @@ -1013,15 +1055,8 @@ static bool pbvh_bmesh_subdivide_long_edges(EdgeQueueContext *eq_ctx, PBVH *bvh, BLI_mempool_free(eq_ctx->pool, pair); pair = NULL; -#ifdef USE_EDGEQUEUE_TAG_VALIDATE - heap_tot += 1; -#endif - /* Check that the edge still exists */ if (!(e = BM_edge_exists(v1, v2))) { -#ifdef USE_EDGEQUEUE_TAG_VALIDATE - heap_overlap += 1; -#endif continue; } #ifdef USE_EDGEQUEUE_TAG @@ -1052,11 +1087,10 @@ static bool pbvh_bmesh_subdivide_long_edges(EdgeQueueContext *eq_ctx, PBVH *bvh, pbvh_bmesh_split_edge(eq_ctx, bvh, e, edge_loops); } -#ifdef USE_EDGEQUEUE_TAG_VALIDATE - // printf("%d %d\n", heap_total, heap_overlap); - BLI_assert(heap_overlap == 0); -#undef USE_EDGEQUEUE_TAG_VALIDATE +#ifdef USE_EDGEQUEUE_TAG_VERIFY + pbvh_bmesh_edge_tag_verify(bvh); #endif + return any_subdivided; } -- cgit v1.2.3