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.

1 files changed, 84 insertions, 24 deletions

diff --git a/source/blender/blenkernel/intern/pbvh_bmesh.c b/source/blender/blenkernel/intern/pbvh_bmesh.c
index b6e5fcfb405..86c430d1785 100644
--- a/source/blender/blenkernel/intern/pbvh_bmesh.c
+++ b/source/blender/blenkernel/intern/pbvh_bmesh.c
@@ -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_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);
-			}
+				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);
+				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;