[Bf-blender-cvs] [a393db3c237] sculpt-dev: Sculpt-dev: commit 1 of dyntopo cleanup
Joseph Eagar
noreply at git.blender.org
Tue Feb 1 04:04:54 CET 2022
Commit: a393db3c2376f6101ba6f6846dcaa3adb53ef3fe
Author: Joseph Eagar
Date: Mon Jan 31 16:42:57 2022 -0800
Branches: sculpt-dev
https://developer.blender.org/rBa393db3c2376f6101ba6f6846dcaa3adb53ef3fe
Sculpt-dev: commit 1 of dyntopo cleanup
In an attempt to fix dyntopo artifacts with
snake hook I wrote a new heap implementation
for dyntopo, a min-max heap.
Turns out the seperation of collapse and
subdivision queues was a fundamental design
flaw in DynTopo. Unifiying them in
a single heap is much faster (as much as
2x faster depending on the setup), and
will allow for much cleaner code.
===================================================================
M source/blender/blenkernel/BKE_pbvh.h
M source/blender/blenkernel/intern/dyntopo.c
M source/blender/blenkernel/intern/pbvh_bmesh.c
A source/blender/blenlib/BLI_heap_minmax.h
M source/blender/blenlib/CMakeLists.txt
A source/blender/blenlib/intern/heap_minmax.c
M source/blender/editors/sculpt_paint/sculpt.c
M source/blender/editors/sculpt_paint/sculpt_detail.c
===================================================================
diff --git a/source/blender/blenkernel/BKE_pbvh.h b/source/blender/blenkernel/BKE_pbvh.h
index 8ae3852b0f8..c0f40ac4180 100644
--- a/source/blender/blenkernel/BKE_pbvh.h
+++ b/source/blender/blenkernel/BKE_pbvh.h
@@ -527,7 +527,8 @@ bool BKE_pbvh_bmesh_update_topology(
DyntopoMaskCB mask_cb,
void *mask_cb_data,
int custom_max_steps, // if 0, will use defaul hueristics for max steps
- bool disable_surface_relax);
+ bool disable_surface_relax,
+ bool is_snake_hook);
bool BKE_pbvh_bmesh_update_topology_nodes(PBVH *pbvh,
bool (*searchcb)(PBVHNode *node, void *data),
@@ -543,7 +544,8 @@ bool BKE_pbvh_bmesh_update_topology_nodes(PBVH *pbvh,
bool updatePBVH,
DyntopoMaskCB mask_cb,
void *mask_cb_data,
- bool disable_surface_relax);
+ bool disable_surface_relax,
+ bool is_snake_hook);
/* Node Access */
void BKE_pbvh_check_tri_areas(PBVH *pbvh, PBVHNode *node);
diff --git a/source/blender/blenkernel/intern/dyntopo.c b/source/blender/blenkernel/intern/dyntopo.c
index 0f6b15aaee3..eff61fc2878 100644
--- a/source/blender/blenkernel/intern/dyntopo.c
+++ b/source/blender/blenkernel/intern/dyntopo.c
@@ -14,6 +14,7 @@
#include "BLI_compiler_compat.h"
#include "BLI_ghash.h"
#include "BLI_heap.h"
+#include "BLI_heap_minmax.h"
#include "BLI_heap_simple.h"
#include "BLI_linklist.h"
#include "BLI_math.h"
@@ -56,6 +57,7 @@
#define DYNTOPO_MAX_ITER 4096
#define DYNTOPO_USE_HEAP
+#define DYNTOPO_USE_MINMAX_HEAP
#ifndef DYNTOPO_USE_HEAP
/* don't add edges into the queue multiple times */
@@ -193,6 +195,7 @@ void bmesh_radial_loop_append(BMEdge *e, BMLoop *l);
void bm_kill_only_edge(BMesh *bm, BMEdge *e);
void bm_kill_only_loop(BMesh *bm, BMLoop *l);
void bm_kill_only_face(BMesh *bm, BMFace *f);
+bool edge_queue_test(struct EdgeQueueContext *eq_ctx, PBVH *pbvh, BMEdge *e);
static void fix_mesh(PBVH *pbvh, BMesh *bm)
{
@@ -1420,8 +1423,28 @@ typedef struct EdgeQueueContext {
int val34_verts_size;
bool local_mode;
float surface_smooth_fac;
+
+ MinMaxHeap *heap_mm;
+ int max_heap_mm;
+ TableGSet *used_verts;
+ float view_normal[3];
+ bool use_view_normal;
+ float limit_min, limit_max, limit_mid;
} EdgeQueueContext;
+static void edge_queue_insert_unified(EdgeQueueContext *eq_ctx, BMEdge *e)
+{
+ if (/*BLI_mm_heap_len(eq_ctx->heap_mm) < eq_ctx->max_heap_mm &&*/ !(e->head.hflag &
+ BM_ELEM_TAG)) {
+ float len = len_squared_v3v3(e->v1->co, e->v2->co);
+
+ len += (BLI_thread_frand(0)-0.5f)*0.1*eq_ctx->limit_mid;
+
+ BLI_mm_heap_insert(eq_ctx->heap_mm, len, e);
+ e->head.hflag |= BM_ELEM_TAG;
+ }
+}
+
static void edge_queue_insert_val34_vert(EdgeQueueContext *eq_ctx, BMVert *v)
{
MSculptVert *mv = BKE_PBVH_SCULPTVERT(eq_ctx->cd_sculpt_vert, v);
@@ -1808,9 +1831,18 @@ static void edge_queue_insert(EdgeQueueContext *eq_ctx, BMEdge *e, float priorit
pair->v2 = e->v2;
pair->limit_len_squared = limit * limit;
+#ifdef DYNTOPO_USE_MINMAX_HEAP
+
+#endif
+
#ifdef DYNTOPO_USE_HEAP
BLI_heapsimple_insert(eq_ctx->q->heap, priority, pair);
#endif
+#ifdef DYNTOPO_USE_MINMAX_HEAP
+ edge_queue_insert_unified(eq_ctx, e);
+ BLI_table_gset_add(eq_ctx->used_verts, e->v1);
+ BLI_table_gset_add(eq_ctx->used_verts, e->v2);
+#endif
BLI_array_append(elems, pair);
eq_ctx->q->elems = elems;
@@ -1892,6 +1924,71 @@ static void long_edge_queue_edge_add_recursive(EdgeQueueContext *eq_ctx,
} while ((l_iter = l_iter->radial_next) != l_end);
}
}
+
+static void long_edge_queue_edge_add_recursive_3(EdgeQueueContext *eq_ctx,
+ BMLoop *l_edge,
+ BMLoop *l_end,
+ const float len_sq,
+ float limit_len,
+ int depth)
+{
+ BLI_assert(len_sq > square_f(limit_len));
+
+ if (l_edge->e->head.hflag & BM_ELEM_TAG) {
+ // return;
+ }
+
+# ifdef USE_EDGEQUEUE_FRONTFACE
+ if (depth > DEPTH_START_LIMIT && eq_ctx->use_view_normal) {
+ if (dot_v3v3(l_edge->f->no, eq_ctx->view_normal) < 0.0f) {
+ return;
+ }
+ }
+# endif
+
+ edge_queue_insert_unified(eq_ctx, l_edge->e);
+
+ if ((l_edge->radial_next != l_edge)) {
+ const float len_sq_cmp = len_sq * EVEN_EDGELEN_THRESHOLD;
+
+ limit_len *= EVEN_GENERATION_SCALE;
+ const float limit_len_sq = square_f(limit_len);
+
+ BMLoop *l_iter = l_edge;
+ do {
+ BMLoop *l_adjacent[2] = {l_iter->next, l_iter->prev};
+ for (int i = 0; i < (int)ARRAY_SIZE(l_adjacent); i++) {
+ BMEdge *e = l_adjacent[i]->e;
+
+ float len_sq_other = calc_weighted_edge_split(
+ eq_ctx, l_adjacent[i]->e->v1, l_adjacent[i]->e->v2);
+
+ float w = maskcb_get(eq_ctx, e);
+
+ len_sq_other *= w * w;
+
+ bool insert_ok = len_sq_other > max_ff(len_sq_cmp, limit_len_sq);
+# ifdef EVEN_NO_TEST_DEPTH_LIMIT
+ if (!insert_ok && depth >= EVEN_NO_TEST_DEPTH_LIMIT) {
+ continue;
+ }
+# else
+ if (!insert_ok) {
+ continue;
+ }
+# endif
+
+ long_edge_queue_edge_add_recursive_3(eq_ctx,
+ l_adjacent[i]->radial_next,
+ l_adjacent[i],
+ len_sq_other,
+ limit_len,
+ depth + 1);
+ }
+ } while ((l_iter = l_iter->radial_next) != l_end);
+ }
+}
+
#endif /* USE_EDGEQUEUE_EVEN_SUBDIV */
static void short_edge_queue_edge_add(EdgeQueueContext *eq_ctx, BMEdge *e)
@@ -1980,7 +2077,7 @@ static void short_edge_queue_edge_add_recursive_2(EdgeQueueThreadData *tdata,
BLI_assert(len_sq > square_f(limit_len));
if (l_edge->e->head.hflag & BM_ELEM_TAG) {
- return;
+ // return;
}
#ifdef USE_EDGEQUEUE_FRONTFACE
@@ -2032,7 +2129,7 @@ static void long_edge_queue_edge_add_recursive_2(EdgeQueueThreadData *tdata,
BLI_assert(len_sq > square_f(limit_len));
if (l_edge->e->head.hflag & BM_ELEM_TAG) {
- return;
+ // return;
}
#ifdef USE_EDGEQUEUE_FRONTFACE
@@ -2206,20 +2303,23 @@ static void long_edge_queue_task_cb(void *__restrict userdata,
but tangentially to surface.
*/
int randval = (seed = dyntopo_thread_rand(seed)) & 255;
-
+
if (do_smooth && randval > 127) {
surface_smooth_v_safe(tdata->pbvh, l_iter->v, eq_ctx->surface_smooth_fac);
}
#ifdef USE_EDGEQUEUE_EVEN_SUBDIV
- float w = maskcb_get(eq_ctx, l_iter->e);
float len_sq = calc_weighted_edge_split(eq_ctx, l_iter->e->v1, l_iter->e->v2);
- len_sq *= w * w;
+ /* subdivide walks the mesh a bit for better transitions in the topology */
if (len_sq > eq_ctx->q->limit_len_squared) {
long_edge_queue_edge_add_recursive_2(
tdata, l_iter->radial_next, l_iter, len_sq, eq_ctx->q->limit_len, 0, true);
}
+
+ if (edge_queue_test(eq_ctx, pbvh, l_iter->e)) {
+ edge_thread_data_insert(tdata, l_iter->e);
+ }
#else
const float len_sq = BM_edge_calc_length_squared(l_iter->e);
if (len_sq > eq_ctx->q->limit_len_squared) {
@@ -2758,6 +2858,15 @@ static void edge_queue_init(EdgeQueueContext *eq_ctx,
#endif
}
+static bool edge_queue_test(EdgeQueueContext *eq_ctx, PBVH *pbvh, BMEdge *e)
+{
+ float len = len_squared_v3v3(e->v1->co, e->v2->co);
+ float min = pbvh->bm_min_edge_len * pbvh->bm_min_edge_len;
+ float max = pbvh->bm_max_edge_len * pbvh->bm_max_edge_len;
+
+ return len < min || len > max;
+}
+
/* Create a priority queue containing vertex pairs connected by a long
* edge as defined by PBVH.bm_max_edge_len.
*
@@ -2853,6 +2962,17 @@ static void long_edge_queue_create(EdgeQueueContext *eq_ctx,
const int cd_sculpt_vert = pbvh->cd_sculpt_vert;
+ for (int i = 0; i < count; i++) {
+ EdgeQueueThreadData *td = tdata + i;
+ BMEdge **edges = td->edges;
+
+ for (int j = 0; j < td->totedge; j++) {
+ BMEdge *e = edges[j];
+
+ e->head.hflag &= ~BM_ELEM_TAG;
+ }
+ }
+
for (int i = 0; i < count; i++) {
EdgeQueueThreadData *td = tdata + i;
@@ -2902,12 +3022,16 @@ static void long_edge_queue_create(EdgeQueueContext *eq_ctx,
// check_vert_fan_are_tris(pbvh, e->v1);
// check_vert_fan_are_tris(pbvh, e->v2);
- float w = -calc_weighted_edge_split(eq_ctx, e->v1, e->v2);
- float w2 = maskcb_get(eq_ctx, e);
+ // float w = -calc_weighted_edge_split(eq_ctx, e->v1, e->v2);
+ // float w2 = maskcb_get(eq_ctx, e);
- w *= w2 * w2;
+ // w *= w2 * w2;
- edge_queue_insert(eq_ctx, e, w, eq_ctx->q->limit_len);
+ if (edge_queue_test(eq_ctx, pbvh, e)) {
+ edge_queue_insert_unified(eq_ctx, e);
+ }
+
+ // edge_queue_insert(eq_ctx, e, w, eq_ctx->q->limit_len);
}
MEM_SAFE_FREE(td->edges);
@@ -3188,6 +3312,7 @@ static void short_edge_queue_create(EdgeQueueContext *eq_ctx,
const bool use_projected,
bool local_mode)
{
+ return;
if (local_mode) {
edge_queue_create_local(
eq_ctx, pbvh, center, view_normal, radius, use_frontface, use_projected, true);
@@ -3836,7 +3961,9 @@ static BMVert *pbvh_bmesh_collapse_edge(PBVH *pbvh,
BM_log_edge_topo_pre(pbvh->bm_log, e);
BM_log_vert_removed(pbvh->bm_log, v_del, pbvh->cd_vert_mask_offset);
- BLI_ghash_insert(deleted_verts, (void *)v_del, NULL);
+ if (deleted_verts) {
+ BLI_ghash_insert(deleted_verts, (void *)v_del, NULL);
+ }
pbvh_bmesh_check_nodes(pbvh);
@@ -4198,12 +4325,18 @@ cleanup_valence_3_4(EdgeQueueContext *ectx,
int updateflag = SCULPTVERT_NEED_BOUNDARY | S
@@ Diff output truncated at 10240 characters. @@
More information about the Bf-blender-cvs
mailing list