blender
/
blender
135
420
Fork 603
Code Issues 6.3k Pull Requests 754 Projects 19 Wiki Activity

Dyntopo queue added the same edges multiple times 

Use tagging to avoid re-evaluating the same edges while sculpting.

While gives only minor speedup,
it allows for changes to the queue without additional redundant checks.
This commit is contained in:
Campbell Barton 2015-04-14 18:39:40 +10:00
parent 7daa921359
commit 68eeeea57e
1 changed files with 86 additions and 26 deletions
Show Stats Download Patch File Download Diff File Expand all files Collapse all files

112
source/blender/blenkernel/intern/pbvh_bmesh.c
View File

@ -47,6 +47,9 @@
# include "BKE_global.h"
#endif
/* don't add edges into the queue multiple times */
#define USE_EDGEQUEUE_TAG
// #define USE_VERIFY
#ifdef USE_VERIFY
@ -594,6 +597,13 @@ typedef struct {
int cd_face_node_offset;
} EdgeQueueContext;
/* only tag'd edges are in the queue */
#ifdef USE_EDGEQUEUE_TAG
# define EDGE_QUEUE_TEST(e) (BM_elem_flag_test((CHECK_TYPE_INLINE(e, BMEdge *), e), BM_ELEM_TAG))
# define EDGE_QUEUE_ENABLE(e) BM_elem_flag_enable((CHECK_TYPE_INLINE(e, BMEdge *), e), BM_ELEM_TAG)
# define EDGE_QUEUE_DISABLE(e) BM_elem_flag_disable((CHECK_TYPE_INLINE(e, BMEdge *), e), BM_ELEM_TAG)
#endif
static bool edge_queue_tri_in_sphere(const EdgeQueue *q, BMFace *f)
{
BMVert *v_tri[3];
@ -635,15 +645,25 @@ static void edge_queue_insert(EdgeQueueContext *eq_ctx, BMEdge *e,
pair[0] = e->v1;
pair[1] = e->v2;
BLI_heap_insert(eq_ctx->q->heap, priority, pair);
#ifdef USE_EDGEQUEUE_TAG
BLI_assert(EDGE_QUEUE_TEST(e) == false);
EDGE_QUEUE_ENABLE(e);
#endif
}
}
static void long_edge_queue_edge_add(EdgeQueueContext *eq_ctx,
BMEdge *e)
{
const float len_sq = BM_edge_calc_length_squared(e);
if (len_sq > eq_ctx->q->limit_len_squared)
edge_queue_insert(eq_ctx, e, -len_sq);
#ifdef USE_EDGEQUEUE_TAG
if (EDGE_QUEUE_TEST(e) == false)
#endif
{
const float len_sq = BM_edge_calc_length_squared(e);
if (len_sq > eq_ctx->q->limit_len_squared) {
edge_queue_insert(eq_ctx, e, -len_sq);
}
}
}
#ifdef USE_EDGEQUEUE_EVEN_SUBDIV
@ -681,12 +701,17 @@ 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++) {
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);
#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);
}
}
}
} while ((l_iter = l_iter->radial_next) != l_end);
@ -700,9 +725,15 @@ static void long_edge_queue_edge_add_recursive(
static void short_edge_queue_edge_add(EdgeQueueContext *eq_ctx,
BMEdge *e)
{
const float len_sq = BM_edge_calc_length_squared(e);
if (len_sq < eq_ctx->q->limit_len_squared)
edge_queue_insert(eq_ctx, e, len_sq);
#ifdef USE_EDGEQUEUE_TAG
if (EDGE_QUEUE_TEST(e) == false)
#endif
{
const float len_sq = BM_edge_calc_length_squared(e);
if (len_sq < eq_ctx->q->limit_len_squared) {
edge_queue_insert(eq_ctx, e, len_sq);
}
}
}
static void long_edge_queue_face_add(EdgeQueueContext *eq_ctx,
@ -715,16 +746,21 @@ 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_EVEN_SUBDIV
const float len_sq = BM_edge_calc_length_squared(l_iter->e);
if (len_sq > eq_ctx->q->limit_len_squared) {
long_edge_queue_edge_add_recursive(
eq_ctx, l_iter->radial_next, l_iter,
len_sq, eq_ctx->q->limit_len_squared);
}
#else
long_edge_queue_edge_add(eq_ctx, l_iter->e);
#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);
if (len_sq > eq_ctx->q->limit_len_squared) {
long_edge_queue_edge_add_recursive(
eq_ctx, l_iter->radial_next, l_iter,
len_sq, eq_ctx->q->limit_len_squared);
}
#else
long_edge_queue_edge_add(eq_ctx, l_iter->e);
#endif
}
} while ((l_iter = l_iter->next) != l_first);
}
}
@ -959,6 +995,12 @@ 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;
#endif
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];
@ -967,6 +1009,21 @@ 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
EDGE_QUEUE_DISABLE(e);
#endif
/* At the moment edges never get shorter (subdiv will make new edges)
* unlike collapse where edges can become longer. */
#if 0
@ -976,11 +1033,6 @@ static bool pbvh_bmesh_subdivide_long_edges(EdgeQueueContext *eq_ctx, PBVH *bvh,
BLI_assert(len_squared_v3v3(v1->co, v2->co) > eq_ctx->q->limit_len_squared);
#endif
/* Check that the edge still exists */
if (!(e = BM_edge_exists(v1, v2))) {
continue;
}
/* Check that the edge's vertices are still in the PBVH. It's
* possible that an edge collapse has deleted adjacent faces
* and the node has been split, thus leaving wire edges and
@ -996,6 +1048,11 @@ 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
#endif
return any_subdivided;
}
@ -1175,6 +1232,9 @@ static bool pbvh_bmesh_collapse_short_edges(
if (!(e = BM_edge_exists(v1, v2))) {
continue;
}
#ifdef USE_EDGEQUEUE_TAG
EDGE_QUEUE_DISABLE(e);
#endif
if (len_squared_v3v3(v1->co, v2->co) >= min_len_squared)
continue;