* PBVH node join code is now enabled for dyntopo bmeshtemp-trimesh-sculpt

* Fixed bug in dyntopo bmesh time limiting code

4 files changed, 575 insertions, 37 deletions

diff --git a/source/blender/blenkernel/intern/pbvh.c b/source/blender/blenkernel/intern/pbvh.c
index 3140837ebac..a9ec91a39bc 100644
--- a/source/blender/blenkernel/intern/pbvh.c
+++ b/source/blender/blenkernel/intern/pbvh.c
@@ -1364,7 +1364,8 @@ static void pbvh_update_draw_buffer_cb(void *__restrict userdata,
                                       node->bm_faces,
                                       node->bm_unique_verts,
                                       node->bm_other_verts,
-                                      update_flags);
+                                      update_flags,
+                                      pbvh->cd_vert_node_offset);
         break;
       case PBVH_TRIMESH:
         GPU_pbvh_trimesh_buffers_update(node->draw_buffers,
@@ -1388,7 +1389,7 @@ static void pbvh_update_draw_buffers(PBVH *pbvh, PBVHNode **nodes, int totnode,
       PBVHNode *node = nodes[n];
 
       if (node->flag & PBVH_Delete) {
-        printf("corrupted node! %p\n", node);
+        printf("corrupted node! %p %d\n", node, node->flag);
         return;
       }
 
@@ -2441,7 +2442,7 @@ bool BKE_pbvh_node_raycast(PBVH *pbvh,
                                      face_normal);
       break;
     case PBVH_BMESH:
-      //BM_mesh_elem_index_ensure(pbvh->bm, BM_VERT);
+      // BM_mesh_elem_index_ensure(pbvh->bm, BM_VERT);
       hit = pbvh_bmesh_node_raycast(node,
                                     ray_start,
                                     ray_normal,
@@ -3027,7 +3028,6 @@ void BKE_pbvh_gather_proxies(PBVH *pbvh, PBVHNode ***r_array, int *r_tot)
   for (int n = 0; n < pbvh->totnode; n++) {
     PBVHNode *node = pbvh->nodes + n;
 
-
     if (node->proxy_count > 0) {
       if (tot == space) {
         /* resize array if needed */
@@ -3424,10 +3424,12 @@ void BKE_pbvh_ensure_proxyarray(SculptSession *ss,
       if (vd.no) {
         copy_v3_v3_short(p->no[i], vd.no);
         normal_short_to_float_v3(p->fno[i], vd.no);
-      } else if (vd.fno) {
+      }
+      else if (vd.fno) {
         copy_v3_v3(p->fno[i], vd.fno);
         normal_float_to_short_v3(p->no[i], p->fno[i]);
-      } else {
+      }
+      else {
         zero_v3(p->fno[i]);
         p->fno[i][2] = 1.0f;
         normal_float_to_short_v3(p->no[i], p->fno[i]);
diff --git a/source/blender/blenkernel/intern/pbvh_bmesh.c b/source/blender/blenkernel/intern/pbvh_bmesh.c
index 0d31494daa8..05d1d2c3e2b 100644
--- a/source/blender/blenkernel/intern/pbvh_bmesh.c
+++ b/source/blender/blenkernel/intern/pbvh_bmesh.c
@@ -20,11 +20,13 @@
 
 #include "MEM_guardedalloc.h"
 
+#include "BLI_array.h"
 #include "BLI_buffer.h"
 #include "BLI_ghash.h"
 #include "BLI_heap_simple.h"
 #include "BLI_math.h"
 #include "BLI_memarena.h"
+#include "BLI_rand.h"
 #include "BLI_utildefines.h"
 #include "PIL_time.h"
 
@@ -40,17 +42,36 @@
 #define DYNTOPO_TIME_LIMIT 0.015
 #define DYNTOPO_RUN_INTERVAL 0.01
 
+#define DYNTOPO_USE_HEAP
+
+#ifndef DYNTOPO_USE_HEAP
+/* don't add edges into the queue multiple times */
+#  define USE_EDGEQUEUE_TAG
+#endif
+
 /* Avoid skinny faces */
 #define USE_EDGEQUEUE_EVEN_SUBDIV
+
 #ifdef USE_EDGEQUEUE_EVEN_SUBDIV
 #  include "BKE_global.h"
 #endif
 
+#ifdef WIN32
+#  include "crtdbg.h"
+#endif
+
+static void check_heap()
+{
+#ifdef WIN32
+  if (!_CrtCheckMemory()) {
+    printf("Memory corruption!");
+    _CrtDbgBreak();
+  }
+#endif
+}
 /* Support for only operating on front-faces */
 #define USE_EDGEQUEUE_FRONTFACE
 
-/* 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).
@@ -204,7 +225,8 @@ static BMVert *bm_vert_hash_lookup_chain(GHash *deleted_verts, BMVert *v)
 static void pbvh_bmesh_node_finalize(PBVH *pbvh,
                                      const int node_index,
                                      const int cd_vert_node_offset,
-                                     const int cd_face_node_offset)
+                                     const int cd_face_node_offset,
+                                     bool add_orco)
 {
   GSetIterator gs_iter;
   PBVHNode *n = &pbvh->nodes[node_index];
@@ -255,19 +277,24 @@ static void pbvh_bmesh_node_finalize(PBVH *pbvh,
   BKE_pbvh_node_mark_rebuild_draw(n);
 
   BKE_pbvh_node_fully_hidden_set(n, !has_visible);
-  n->flag |= PBVH_UpdateNormals;
+  n->flag |= PBVH_UpdateNormals | PBVH_UpdateTopology;
+
+  if (add_orco) {
+    BKE_pbvh_bmesh_node_save_orig(pbvh->bm, n);
+  }
 }
 
 /* Recursively split the node if it exceeds the leaf_limit */
-static void pbvh_bmesh_node_split(PBVH *pbvh, const BBC *bbc_array, int node_index)
+static void pbvh_bmesh_node_split(
+    PBVH *pbvh, const BBC *bbc_array, int node_index, bool add_orco, int depth)
 {
   const int cd_vert_node_offset = pbvh->cd_vert_node_offset;
   const int cd_face_node_offset = pbvh->cd_face_node_offset;
   PBVHNode *n = &pbvh->nodes[node_index];
 
-  if (BLI_gset_len(n->bm_faces) <= pbvh->leaf_limit) {
+  if (depth > 6 || BLI_gset_len(n->bm_faces) <= pbvh->leaf_limit) {
     /* Node limit not exceeded */
-    pbvh_bmesh_node_finalize(pbvh, node_index, cd_vert_node_offset, cd_face_node_offset);
+    pbvh_bmesh_node_finalize(pbvh, node_index, cd_vert_node_offset, cd_face_node_offset, add_orco);
     return;
   }
 
@@ -286,6 +313,10 @@ static void pbvh_bmesh_node_split(PBVH *pbvh, const BBC *bbc_array, int node_ind
   const int axis = BB_widest_axis(&cb);
   const float mid = (cb.bmax[axis] + cb.bmin[axis]) * 0.5f;
 
+  if (isnan(mid)) {
+    printf("NAN ERROR! %s\n", __func__);
+  }
+
   /* Add two new child nodes */
   const int children = pbvh->totnode;
   n->children_offset = children;
@@ -313,7 +344,7 @@ static void pbvh_bmesh_node_split(PBVH *pbvh, const BBC *bbc_array, int node_ind
       BLI_gset_insert(c2->bm_faces, f);
     }
   }
-
+#if 0
   /* Enforce at least one primitive in each node */
   GSet *empty = NULL, *other;
   if (BLI_gset_len(c1->bm_faces) == 0) {
@@ -324,6 +355,7 @@ static void pbvh_bmesh_node_split(PBVH *pbvh, const BBC *bbc_array, int node_ind
     empty = c2->bm_faces;
     other = c1->bm_faces;
   }
+
   if (empty) {
     GSET_ITER (gs_iter, other) {
       void *key = BLI_gsetIterator_getKey(&gs_iter);
@@ -332,7 +364,7 @@ static void pbvh_bmesh_node_split(PBVH *pbvh, const BBC *bbc_array, int node_ind
       break;
     }
   }
-
+#endif
   /* Clear this node */
 
   /* Mark this node's unique verts as unclaimed */
@@ -371,8 +403,8 @@ static void pbvh_bmesh_node_split(PBVH *pbvh, const BBC *bbc_array, int node_ind
   n->flag &= ~PBVH_Leaf;
 
   /* Recurse */
-  pbvh_bmesh_node_split(pbvh, bbc_array, children);
-  pbvh_bmesh_node_split(pbvh, bbc_array, children + 1);
+  pbvh_bmesh_node_split(pbvh, bbc_array, children, add_orco, depth + 1);
+  pbvh_bmesh_node_split(pbvh, bbc_array, children + 1, add_orco, depth + 1);
 
   /* Array maybe reallocated, update current node pointer */
   n = &pbvh->nodes[node_index];
@@ -389,6 +421,7 @@ static bool pbvh_bmesh_node_limit_ensure(PBVH *pbvh, int node_index)
 {
   GSet *bm_faces = pbvh->nodes[node_index].bm_faces;
   const int bm_faces_size = BLI_gset_len(bm_faces);
+
   if (bm_faces_size <= pbvh->leaf_limit) {
     /* Node limit not exceeded */
     return false;
@@ -417,7 +450,7 @@ static bool pbvh_bmesh_node_limit_ensure(PBVH *pbvh, int node_index)
   /* Likely this is already dirty. */
   pbvh->bm->elem_index_dirty |= BM_FACE;
 
-  pbvh_bmesh_node_split(pbvh, bbc_array, node_index);
+  pbvh_bmesh_node_split(pbvh, bbc_array, node_index, pbvh->nodes[node_index].bm_ortri != NULL, 0);
 
   MEM_freeN(bbc_array);
 
@@ -480,12 +513,18 @@ BLI_INLINE int pbvh_bmesh_node_index_from_face(PBVH *pbvh, const BMFace *key)
 
 BLI_INLINE PBVHNode *pbvh_bmesh_node_from_vert(PBVH *pbvh, const BMVert *key)
 {
-  return &pbvh->nodes[pbvh_bmesh_node_index_from_vert(pbvh, key)];
+  int ni = pbvh_bmesh_node_index_from_vert(pbvh, key);
+
+  return ni >= 0 ? pbvh->nodes + ni : NULL;
+  // return &pbvh->nodes[pbvh_bmesh_node_index_from_vert(pbvh, key)];
 }
 
 BLI_INLINE PBVHNode *pbvh_bmesh_node_from_face(PBVH *pbvh, const BMFace *key)
 {
-  return &pbvh->nodes[pbvh_bmesh_node_index_from_face(pbvh, key)];
+  int ni = pbvh_bmesh_node_index_from_face(pbvh, key);
+
+  return ni >= 0 ? pbvh->nodes + ni : NULL;
+  // return &pbvh->nodes[pbvh_bmesh_node_index_from_face(pbvh, key)];
 }
 
 static BMVert *pbvh_bmesh_vert_create(PBVH *pbvh,
@@ -640,6 +679,10 @@ static void pbvh_bmesh_vert_remove(PBVH *pbvh, BMVert *v)
   BM_FACES_OF_VERT_ITER_BEGIN (f, v) {
     const int f_node_index = pbvh_bmesh_node_index_from_face(pbvh, f);
 
+    if (f_node_index == DYNTOPO_NODE_NONE) {
+      continue;
+    }
+
     /* faces often share the same node,
      * quick check to avoid redundant #BLI_gset_remove calls */
     if (f_node_index_prev != f_node_index) {
@@ -662,6 +705,11 @@ static void pbvh_bmesh_face_remove(PBVH *pbvh, BMFace *f)
 {
   PBVHNode *f_node = pbvh_bmesh_node_from_face(pbvh, f);
 
+  if (!f_node) {
+    printf("pbvh corruption\n");
+    fflush(stdout);
+    return;
+  }
   /* Check if any of this face's vertices need to be removed
    * from the node */
   BMLoop *l_first = BM_FACE_FIRST_LOOP(f);
@@ -733,6 +781,10 @@ struct EdgeQueue;
 
 typedef struct EdgeQueue {
   HeapSimple *heap;
+
+  void **elems;
+  int totelems;
+
   const float *center;
   float center_proj[3]; /* for when we use projected coords. */
   float radius_squared;
@@ -742,6 +794,7 @@ typedef struct EdgeQueue {
 #endif
 
   bool (*edge_queue_tri_in_range)(const struct EdgeQueue *q, BMFace *f);
+  bool (*edge_queue_vert_in_range)(const struct EdgeQueue *q, BMVert *v);
 
   const float *view_normal;
 #ifdef USE_EDGEQUEUE_FRONTFACE
@@ -758,6 +811,17 @@ typedef struct {
   int cd_face_node_offset;
 } EdgeQueueContext;
 
+static float calc_weighted_edge(EdgeQueueContext *eq_ctx, BMEdge *e)
+{
+  float l = BM_edge_calc_length_squared(e);
+  float n;
+
+  n = (float)(BM_vert_edge_count(e->v1) + BM_vert_edge_count(e->v2)) * 0.5f;
+  n = MAX2(n - 5.0f, 1.0f);
+
+  return l * powf(n, 5.0f);
+}
+
 /* 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))
@@ -797,6 +861,12 @@ static void pbvh_bmesh_edge_tag_verify(PBVH *pbvh)
 }
 #endif
 
+static bool edge_queue_vert_in_sphere(const EdgeQueue *q, BMVert *v)
+{
+  /* Check if triangle intersects the sphere */
+  return len_squared_v3v3(q->center, v->co) <= q->radius_squared;
+}
+
 static bool edge_queue_tri_in_sphere(const EdgeQueue *q, BMFace *f)
 {
   BMVert *v_tri[3];
@@ -830,6 +900,15 @@ static bool edge_queue_tri_in_circle(const EdgeQueue *q, BMFace *f)
   return len_squared_v3v3(q->center_proj, c) <= q->radius_squared;
 }
 
+static bool edge_queue_vert_in_circle(const EdgeQueue *q, BMVert *v)
+{
+  float c[3];
+
+  project_plane_normalized_v3_v3v3(c, v->co, q->view_normal);
+
+  return len_squared_v3v3(q->center_proj, c) <= q->radius_squared;
+}
+
 /* Return true if the vertex mask is less than 1.0, false otherwise */
 static bool check_mask(EdgeQueueContext *eq_ctx, BMVert *v)
 {
@@ -838,6 +917,10 @@ static bool check_mask(EdgeQueueContext *eq_ctx, BMVert *v)
 
 static void edge_queue_insert(EdgeQueueContext *eq_ctx, BMEdge *e, float priority)
 {
+  void **elems = eq_ctx->q->elems;
+  BLI_array_declare(elems);
+  BLI_array_len_set(elems, eq_ctx->q->totelems);
+
   /* Don't let topology update affect fully masked vertices. This used to
    * have a 50% mask cutoff, with the reasoning that you can't do a 50%
    * topology update. But this gives an ugly border in the mesh. The mask
@@ -851,7 +934,14 @@ static void edge_queue_insert(EdgeQueueContext *eq_ctx, BMEdge *e, float priorit
     BMVert **pair = BLI_mempool_alloc(eq_ctx->pool);
     pair[0] = e->v1;
     pair[1] = e->v2;
+#ifdef DYNTOPO_USE_HEAP
     BLI_heapsimple_insert(eq_ctx->q->heap, priority, pair);
+#endif
+
+    BLI_array_append(elems, pair);
+    eq_ctx->q->elems = elems;
+    eq_ctx->q->totelems = BLI_array_len(elems);
+
 #ifdef USE_EDGEQUEUE_TAG
     BLI_assert(EDGE_QUEUE_TEST(e) == false);
     EDGE_QUEUE_ENABLE(e);
@@ -936,7 +1026,7 @@ static void short_edge_queue_edge_add(EdgeQueueContext *eq_ctx, BMEdge *e)
   if (EDGE_QUEUE_TEST(e) == false)
 #endif
   {
-    const float len_sq = BM_edge_calc_length_squared(e);
+    const float len_sq = calc_weighted_edge(eq_ctx, e);
     if (len_sq < eq_ctx->q->limit_len_squared) {
       edge_queue_insert(eq_ctx, e, len_sq);
     }
@@ -1011,6 +1101,8 @@ static void long_edge_queue_create(EdgeQueueContext *eq_ctx,
                                    const bool use_projected)
 {
   eq_ctx->q->heap = BLI_heapsimple_new();
+  eq_ctx->q->elems = NULL;
+  eq_ctx->q->totelems = 0;
   eq_ctx->q->center = center;
   eq_ctx->q->radius_squared = radius * radius;
   eq_ctx->q->limit_len_squared = pbvh->bm_max_edge_len * pbvh->bm_max_edge_len;
@@ -1028,10 +1120,12 @@ static void long_edge_queue_create(EdgeQueueContext *eq_ctx,
 
   if (use_projected) {
     eq_ctx->q->edge_queue_tri_in_range = edge_queue_tri_in_circle;
+    eq_ctx->q->edge_queue_vert_in_range = edge_queue_vert_in_circle;
     project_plane_normalized_v3_v3v3(eq_ctx->q->center_proj, center, view_normal);
   }
   else {
     eq_ctx->q->edge_queue_tri_in_range = edge_queue_tri_in_sphere;
+    eq_ctx->q->edge_queue_vert_in_range = edge_queue_vert_in_sphere;
   }
 
 #ifdef USE_EDGEQUEUE_TAG_VERIFY
@@ -1074,6 +1168,8 @@ static void short_edge_queue_create(EdgeQueueContext *eq_ctx,
                                     const bool use_projected)
 {
   eq_ctx->q->heap = BLI_heapsimple_new();
+  eq_ctx->q->elems = NULL;
+  eq_ctx->q->totelems = 0;
   eq_ctx->q->center = center;
   eq_ctx->q->radius_squared = radius * radius;
   eq_ctx->q->limit_len_squared = pbvh->bm_min_edge_len * pbvh->bm_min_edge_len;
@@ -1091,10 +1187,12 @@ static void short_edge_queue_create(EdgeQueueContext *eq_ctx,
 
   if (use_projected) {
     eq_ctx->q->edge_queue_tri_in_range = edge_queue_tri_in_circle;
+    eq_ctx->q->edge_queue_vert_in_range = edge_queue_vert_in_circle;
     project_plane_normalized_v3_v3v3(eq_ctx->q->center_proj, center, view_normal);
   }
   else {
     eq_ctx->q->edge_queue_tri_in_range = edge_queue_tri_in_sphere;
+    eq_ctx->q->edge_queue_vert_in_range = edge_queue_vert_in_sphere;
   }
 
   for (int n = 0; n < pbvh->totnode; n++) {
@@ -1221,15 +1319,23 @@ static void pbvh_bmesh_split_edge(EdgeQueueContext *eq_ctx,
     if (!BLI_gset_haskey(pbvh->nodes[ni].bm_unique_verts, v_new)) {
       BLI_gset_add(pbvh->nodes[ni].bm_other_verts, v_new);
     }
-
+    //*
     if (BM_vert_edge_count_is_over(v_opp, 8)) {
       BMIter bm_iter;
       BMEdge *e2;
 
       BM_ITER_ELEM (e2, &bm_iter, v_opp, BM_EDGES_OF_VERT) {
-        long_edge_queue_edge_add(eq_ctx, e2);
+        BMVert *v2 = BM_edge_other_vert(e2, v_opp);
+        bool add = eq_ctx->q->edge_queue_vert_in_range(eq_ctx->q, v2);
+
+        add = add && BM_edge_calc_length_squared(e2) > eq_ctx->q->limit_len_squared;
+
+        if (add) {
+          long_edge_queue_edge_add(eq_ctx, e2);
+        }
       }
     }
+    //*/
   }
 
   BM_edge_kill(pbvh->bm, e);
@@ -1242,12 +1348,26 @@ static bool pbvh_bmesh_subdivide_long_edges(EdgeQueueContext *eq_ctx,
   bool any_subdivided = false;
   double time = PIL_check_seconds_timer();
 
+  RNG *rng = BLI_rng_new((int)(time * 1000.0f));
+
   while (!BLI_heapsimple_is_empty(eq_ctx->q->heap)) {
     if (PIL_check_seconds_timer() - time > DYNTOPO_TIME_LIMIT) {
       break;
     }
 
+#ifndef DYNTOPO_USE_HEAP
+    if (eq_ctx->q->totelems == 0) {
+      break;
+    }
+
+    int ri = BLI_rng_get_int(rng) % eq_ctx->q->totelems;
+
+    BMVert **pair = eq_ctx->q->elems[ri];
+    eq_ctx->q->elems[ri] = eq_ctx->q->elems[eq_ctx->q->totelems - 1];
+    eq_ctx->q->totelems--;
+#else
     BMVert **pair = BLI_heapsimple_pop_min(eq_ctx->q->heap);
+#endif
     BMVert *v1 = pair[0], *v2 = pair[1];
     BMEdge *e;
 
@@ -1286,10 +1406,25 @@ static bool pbvh_bmesh_subdivide_long_edges(EdgeQueueContext *eq_ctx,
     pbvh_bmesh_split_edge(eq_ctx, pbvh, e, edge_loops);
   }
 
+#if !defined(DYNTOPO_USE_HEAP) && defined(USE_EDGEQUEUE_TAG)
+  for (int i = 0; i < eq_ctx->q->totelems; i++) {
+    BMVert **pair = eq_ctx->q->elems[i];
+    BMVert *v1 = pair[0], *v2 = pair[1];
+
+    BMEdge *e = BM_edge_exists(v1, v2);
+
+    if (e) {
+      EDGE_QUEUE_DISABLE(e);
+    }
+  }
+#endif
+
 #ifdef USE_EDGEQUEUE_TAG_VERIFY
   pbvh_bmesh_edge_tag_verify(pbvh);
 #endif
 
+  BLI_rng_free(rng);
+
   return any_subdivided;
 }
 
@@ -1481,13 +1616,25 @@ static bool pbvh_bmesh_collapse_short_edges(EdgeQueueContext *eq_ctx,
   GHash *deleted_verts = BLI_ghash_ptr_new("deleted_verts");
 
   double time = PIL_check_seconds_timer();
+  RNG *rng = BLI_rng_new(time * 1000.0);
 
   while (!BLI_heapsimple_is_empty(eq_ctx->q->heap)) {
     if (PIL_check_seconds_timer() - time > DYNTOPO_TIME_LIMIT) {
       break;
     }
+#ifndef DYNTOPO_USE_HEAP
+    if (eq_ctx->q->totelems == 0) {
+      break;
+    }
+
+    int ri = BLI_rng_get_int(rng) % eq_ctx->q->totelems;
 
+    BMVert **pair = eq_ctx->q->elems[ri];
+    eq_ctx->q->elems[ri] = eq_ctx->q->elems[eq_ctx->q->totelems - 1];
+    eq_ctx->q->totelems--;
+#else
     BMVert **pair = BLI_heapsimple_pop_min(eq_ctx->q->heap);
+#endif
     BMVert *v1 = pair[0], *v2 = pair[1];
     BLI_mempool_free(eq_ctx->pool, pair);
     pair = NULL;
@@ -1525,6 +1672,24 @@ static bool pbvh_bmesh_collapse_short_edges(EdgeQueueContext *eq_ctx,
     pbvh_bmesh_collapse_edge(pbvh, e, v1, v2, deleted_verts, deleted_faces, eq_ctx);
   }
 
+#if !defined(DYNTOPO_USE_HEAP) && defined(USE_EDGEQUEUE_TAG)
+  for (int i = 0; i < eq_ctx->q->totelems; i++) {
+    BMVert **pair = eq_ctx->q->elems[i];
+    BMVert *v1 = pair[0], *v2 = pair[1];
+
+    /* Check the verts still exist */
+    if (!(v1 = bm_vert_hash_lookup_chain(deleted_verts, v1)) ||
+        !(v2 = bm_vert_hash_lookup_chain(deleted_verts, v2)) || (v1 == v2)) {
+      continue;
+    }
+
+    BMEdge *e = BM_edge_exists(v1, v2);
+    if (e) {
+      EDGE_QUEUE_DISABLE(e);
+    }
+  }
+#endif
+  BLI_rng_free(rng);
   BLI_ghash_free(deleted_verts, NULL, NULL);
 
   return any_collapsed;
@@ -1924,7 +2089,7 @@ void BKE_pbvh_build_bmesh(PBVH *pbvh,
   pbvh->bm_log = log;
 
   /* TODO: choose leaf limit better */
-  pbvh->leaf_limit = 2000;
+  pbvh->leaf_limit = 3000;
 
   if (smooth_shading) {
     pbvh->flags |= PBVH_DYNTOPO_SMOOTH_SHADING;
@@ -2001,7 +2166,6 @@ bool BKE_pbvh_bmesh_update_topology(PBVH *pbvh,
   if (sym_axis >= 0 &&
       PIL_check_seconds_timer() - last_update_time[sym_axis] < DYNTOPO_RUN_INTERVAL) {
     return false;
-    // return false;
   }
 
   if (sym_axis >= 0) {
@@ -2037,6 +2201,9 @@ bool BKE_pbvh_bmesh_update_topology(PBVH *pbvh,
         &eq_ctx, pbvh, center, view_normal, radius, use_frontface, use_projected);
     modified |= pbvh_bmesh_collapse_short_edges(&eq_ctx, pbvh, &deleted_faces);
     BLI_heapsimple_free(q.heap, NULL);
+    if (q.elems) {
+      MEM_freeN(q.elems);
+    }
     BLI_mempool_destroy(queue_pool);
   }
 
@@ -2055,6 +2222,9 @@ bool BKE_pbvh_bmesh_update_topology(PBVH *pbvh,
     long_edge_queue_create(
         &eq_ctx, pbvh, center, view_normal, radius, use_frontface, use_projected);
     modified |= pbvh_bmesh_subdivide_long_edges(&eq_ctx, pbvh, &edge_loops);
+    if (q.elems) {
+      MEM_freeN(q.elems);
+    }
     BLI_heapsimple_free(q.heap, NULL);
     BLI_mempool_destroy(queue_pool);
   }
@@ -2065,14 +2235,12 @@ bool BKE_pbvh_bmesh_update_topology(PBVH *pbvh,
 
       if ((node->flag & PBVH_Leaf) && (node->flag & PBVH_UpdateTopology) &&
           !(node->flag & PBVH_FullyHidden)) {
+        node->flag &= ~PBVH_UpdateTopology;
+
         /* Recursively split nodes that have gotten too many
          * elements */
         pbvh_bmesh_node_limit_ensure(pbvh, i);
       }
-
-      if ((node->flag & PBVH_Leaf) && (node->flag & PBVH_UpdateTopology)) {
-        node->flag &= ~PBVH_UpdateTopology;
-      }
     }
   }
   else {  // still unmark nodes
@@ -2156,10 +2324,362 @@ void BKE_pbvh_bmesh_node_save_orig(BMesh *bm, PBVHNode *node)
   node->bm_tot_ortri = i;
 }
 
+static int pbvh_count_subtree_verts(PBVH *pbvh, PBVHNode *n)
+{
+  if (n->flag & PBVH_Leaf) {
+    n->tm_subtree_tottri = BLI_gset_len(
+        n->bm_faces);  // n->tm_unique_verts->length + n->tm_other_verts->length;
+    return n->tm_subtree_tottri;
+  }
+
+  int ni = n->children_offset;
+
+  int ret = pbvh_count_subtree_verts(pbvh, pbvh->nodes + ni);
+  ret += pbvh_count_subtree_verts(pbvh, pbvh->nodes + ni + 1);
+
+  n->tm_subtree_tottri = ret;
+
+  return ret;
+}
+
+static void pbvh_bmesh_join_subnodes(PBVH *pbvh, PBVHNode *node, PBVHNode *parent)
+{
+  if (!(node->flag & PBVH_Leaf)) {
+    int ni = node->children_offset;
+
+    if (ni > 0 && ni < pbvh->totnode - 1) {
+      pbvh_bmesh_join_subnodes(pbvh, pbvh->nodes + ni, parent);
+      pbvh_bmesh_join_subnodes(pbvh, pbvh->nodes + ni + 1, parent);
+    }
+    else {
+      printf("node corruption: %d\n", ni);
+      return;
+    }
+    if (node != parent) {
+      node->flag |= PBVH_Delete;  // mark for deletion
+    }
+
+    return;
+  }
+
+  if (node != parent) {
+    node->flag |= PBVH_Delete;  // mark for deletion
+  }
+
+  BMVert *v;
+  GSetIterator gsiter;
+
+  GSET_ITER (gsiter, node->bm_unique_verts) {
+    BMVert *v = BLI_gsetIterator_getKey(&gsiter);
+    BLI_gset_add(parent->bm_unique_verts, v);
+
+    BM_ELEM_CD_SET_INT(v, pbvh->cd_vert_node_offset, DYNTOPO_NODE_NONE);
+  }
+
+  // printf("  subtotface: %d\n", BLI_gset_len(node->bm_faces));
+
+  GSET_ITER (gsiter, node->bm_faces) {
+    BMFace *f = BLI_gsetIterator_getKey(&gsiter);
+
+    BLI_gset_add(parent->bm_faces, f);
+    BM_ELEM_CD_SET_INT(f, pbvh->cd_face_node_offset, DYNTOPO_NODE_NONE);
+  }
+}
+
+static void BKE_pbvh_bmesh_corect_tree(PBVH *pbvh, PBVHNode *node, PBVHNode *parent)
+{
+  const int size_lower = pbvh->leaf_limit - (pbvh->leaf_limit >> 1);
+  const int size_higher = pbvh->leaf_limit + (pbvh->leaf_limit >> 1);
+
+  if (node->flag & PBVH_Leaf) {
+    // pbvh_trimesh_node_limit_ensure(pbvh, (int)(node - pbvh->nodes));
+    return;
+
+    // join nodes if subtree lacks verts, unless node is root
+  }
+
+  if (node->tm_subtree_tottri < size_lower && node != pbvh->nodes) {
+    node->bm_unique_verts = BLI_gset_ptr_new("bm_unique_verts");
+    node->bm_other_verts = BLI_gset_ptr_new("bm_other_verts");
+    node->bm_faces = BLI_gset_ptr_new("bm_faces");
+
+    pbvh_bmesh_join_subnodes(pbvh, pbvh->nodes + node->children_offset, node);
+    pbvh_bmesh_join_subnodes(pbvh, pbvh->nodes + node->children_offset + 1, node);
+
+    node->children_offset = 0;
+    node->flag |= PBVH_Leaf | PBVH_UpdateRedraw | PBVH_UpdateBB | PBVH_UpdateDrawBuffers |
+                  PBVH_RebuildDrawBuffers | PBVH_UpdateOriginalBB | PBVH_UpdateMask |
+                  PBVH_UpdateVisibility | PBVH_UpdateColor | PBVH_UpdateTopology |
+                  PBVH_UpdateNormals;
+
+    GSet *other = BLI_gset_ptr_new(__func__);
+    GSetIterator gsiter;
+    BMVert *v;
+
+    node->children_offset = 0;
+    node->draw_buffers = NULL;
+
+    // make sure other list isn't overlapping with unique
+    GSET_ITER (gsiter, node->bm_other_verts) {
+      BMVert *v = BLI_gsetIterator_getKey(&gsiter);
+
+      if (!BLI_gset_haskey(node->bm_unique_verts, v)) {
+        // BLI_gset_add(other, v);
+      }
+    }
+
+    GSET_ITER (gsiter, node->bm_faces) {
+      BMFace *f = BLI_gsetIterator_getKey(&gsiter);
+      BMLoop *l = f->l_first;
+
+      BM_ELEM_CD_SET_INT(f, pbvh->cd_face_node_offset, DYNTOPO_NODE_NONE);
+
+      do {
+        if (!BLI_gset_haskey(node->bm_unique_verts, l->v)) {
+          BLI_gset_add(other, l->v);
+        }
+        l = l->next;
+      } while (l != f->l_first);
+    }
+
+    BLI_gset_free(node->bm_other_verts, NULL);
+    node->bm_other_verts = other;
+
+    BB_reset(&node->vb);
+    //*
+    GSET_ITER (gsiter, node->bm_unique_verts) {
+      BMVert *v = BLI_gsetIterator_getKey(&gsiter);
+      BB_expand(&node->vb, v->co);
+    }
+    GSET_ITER (gsiter, node->bm_other_verts) {
+      BMVert *v = BLI_gsetIterator_getKey(&gsiter);
+      BB_expand(&node->vb, v->co);
+    }  //*/
+
+    // printf("totface: %d\n", BLI_gset_len(node->bm_faces));
+    node->orig_vb = node->vb;
+
+    return;
+  }
+
+  int ni = node->children_offset;
+
+  for (int i = 0; i < 2; i++, ni++) {
+    PBVHNode *child = pbvh->nodes + ni;
+    BKE_pbvh_bmesh_corect_tree(pbvh, child, node);
+  }
+}
+
+static void pbvh_bmesh_join_nodes(PBVH *bvh)
+{
+  pbvh_count_subtree_verts(bvh, bvh->nodes);
+  BKE_pbvh_bmesh_corect_tree(bvh, bvh->nodes, NULL);
+
+  // compact nodes
+  int totnode = 0;
+  for (int i = 0; i < bvh->totnode; i++) {
+    PBVHNode *n = bvh->nodes + i;
+
+    if (!(n->flag & PBVH_Delete)) {
+      if (!(n->flag & PBVH_Leaf)) {
+        PBVHNode *n1 = bvh->nodes + n->children_offset;
+        PBVHNode *n2 = bvh->nodes + n->children_offset + 1;
+
+        if ((n1->flag & PBVH_Delete) != (n2->flag & PBVH_Delete)) {
+          printf("un-deleting an empty node\n");
+          PBVHNode *n3 = n1->flag & PBVH_Delete ? n1 : n2;
+
+          n3->flag = PBVH_Leaf;
+          n3->bm_unique_verts = BLI_gset_ptr_new("bm_unique_verts");
+          n3->bm_other_verts = BLI_gset_ptr_new("bm_other_verts");
+          n3->bm_faces = BLI_gset_ptr_new("bm_faces");
+        }
+        else if ((n1->flag & PBVH_Delete) && (n2->flag & PBVH_Delete)) {
+          n->children_offset = 0;
+          n->flag |= PBVH_Leaf;
+
+          if (!n->bm_unique_verts) {
+            // should not happen
+            n->bm_unique_verts = BLI_gset_ptr_new("bm_unique_verts");
+            n->bm_other_verts = BLI_gset_ptr_new("bm_other_verts");
+            n->bm_faces = BLI_gset_ptr_new("bm_faces");
+          }
+        }
+      }
+
+      totnode++;
+    }
+  }
+
+  int *map = MEM_callocN(sizeof(int) * bvh->totnode, "bmesh map temp");
+
+  // build idx map for child offsets
+  int j = 0;
+  for (int i = 0; i < bvh->totnode; i++) {
+    PBVHNode *n = bvh->nodes + i;
+
+    if (!(n->flag & PBVH_Delete)) {
+      map[i] = j++;
+    }
+    else if (1) {
+      if (n->layer_disp) {
+        MEM_freeN(n->layer_disp);
+        n->layer_disp = NULL;
+      }
+      if (n->draw_buffers) {
+        GPU_pbvh_buffers_free(n->draw_buffers);
+        n->draw_buffers = NULL;
+      }
+      if (n->vert_indices) {
+        MEM_freeN((void *)n->vert_indices);
+        n->vert_indices = NULL;
+      }
+      if (n->face_vert_indices) {
+        MEM_freeN((void *)n->face_vert_indices);
+        n->face_vert_indices = NULL;
+      }
+
+      if (n->bm_orco) {
+        MEM_freeN(n->bm_orco);
+        n->bm_orco = NULL;
+      }
+
+      if (n->bm_ortri) {
+        MEM_freeN(n->bm_ortri);
+        n->bm_ortri = NULL;
+      }
+
+      if (n->bm_unique_verts) {
+        BLI_gset_free(n->bm_unique_verts, NULL);
+        n->bm_unique_verts = NULL;
+      }
+
+      if (n->bm_other_verts) {
+        BLI_gset_free(n->bm_other_verts, NULL);
+        n->bm_other_verts = NULL;
+      }
+
+      if (n->bm_faces) {
+        BLI_gset_free(n->bm_faces, NULL);
+        n->bm_faces = NULL;
+      }
+    }
+  }
+
+  // compact node array
+  j = 0;
+  for (int i = 0; i < bvh->totnode; i++) {
+    if (!(bvh->nodes[i].flag & PBVH_Delete)) {
+      int i1 = map[bvh->nodes[i].children_offset];
+      int i2 = map[bvh->nodes[i].children_offset + 1];
+
+      if (bvh->nodes[i].children_offset >= bvh->totnode) {
+        printf("bad child node reference %d->%d, totnode: %d\n",
+               i,
+               bvh->nodes[i].children_offset,
+               bvh->totnode);
+        continue;
+      }
+
+      if (bvh->nodes[i].children_offset && i2 != i1 + 1) {
+        printf("      pbvh corruption during node join %d %d\n", i1, i2);
+      }
+
+      bvh->nodes[j] = bvh->nodes[i];
+      bvh->nodes[j].children_offset = i1;
+
+      j++;
+    }
+  }
+
+  if (j != totnode) {
+    printf("eek!");
+  }
+
+  if (bvh->totnode != j) {
+    memset(bvh->nodes + j, 0, sizeof(*bvh->nodes) * (bvh->totnode - j));
+    bvh->node_mem_count = j;
+  }
+
+  bvh->totnode = j;
+
+  GSetIterator gsiter;
+  BMVert *v;
+
+  // set vert/face node indices again
+  for (int i = 0; i < bvh->totnode; i++) {
+    PBVHNode *n = bvh->nodes + i;
+
+    if (!(n->flag & PBVH_Leaf)) {
+      continue;
+    }
+
+    if (!n->bm_unique_verts) {
+      printf("ERROR!\n");
+      n->bm_unique_verts = BLI_gset_ptr_new("bleh");
+      n->bm_other_verts = BLI_gset_ptr_new("bleh");
+      n->bm_faces = BLI_gset_ptr_new("bleh");
+    }
+
+    GSET_ITER (gsiter, n->bm_unique_verts) {
+      BMVert *v = BLI_gsetIterator_getKey(&gsiter);
+
+      BM_ELEM_CD_SET_INT(v, bvh->cd_vert_node_offset, i);
+    }
+
+    GSET_ITER (gsiter, n->bm_faces) {
+      BMFace *f = BLI_gsetIterator_getKey(&gsiter);
+      BM_ELEM_CD_SET_INT(f, bvh->cd_face_node_offset, i);
+    }
+  }
+
+  BMVert **scratch = NULL;
+  BLI_array_declare(scratch);
+
+  for (int i = 0; i < bvh->totnode; i++) {
+    PBVHNode *n = bvh->nodes + i;
+
+    if (!(n->flag & PBVH_Leaf)) {
+      continue;
+    }
+
+    BLI_array_clear(scratch);
+
+    GSET_ITER (gsiter, n->bm_other_verts) {
+      BMVert *v = BLI_gsetIterator_getKey(&gsiter);
+
+      int ni = BM_ELEM_CD_GET_INT(v, bvh->cd_vert_node_offset);
+      if (ni == DYNTOPO_NODE_NONE) {
+        BLI_array_append(scratch, v);
+      }
+      // BM_ELEM_CD_SET_INT(v, bvh->cd_vert_node_offset, i);
+    }
+
+    int slen = BLI_array_len(scratch);
+    for (int j = 0; j < slen; j++) {
+      BMVert *v = scratch[j];
+
+      BLI_gset_remove(n->bm_other_verts, v, NULL);
+      BLI_gset_add(n->bm_unique_verts, v);
+      BM_ELEM_CD_SET_INT(v, bvh->cd_vert_node_offset, i);
+    }
+  }
+
+  BLI_array_free(scratch);
+  MEM_freeN(map);
+}
+
 void BKE_pbvh_bmesh_after_stroke(PBVH *pbvh)
 {
+  check_heap();
+
+  pbvh_bmesh_join_nodes(pbvh);
+
+  check_heap();
+
   for (int i = 0; i < pbvh->totnode; i++) {
-    PBVHNode *n = &pbvh->nodes[i];
+    PBVHNode *n = pbvh->nodes + i;
+
     if (n->flag & PBVH_Leaf) {
       /* Free orco/ortri data */
       pbvh_bmesh_node_drop_orig(n);
@@ -2169,6 +2689,8 @@ void BKE_pbvh_bmesh_after_stroke(PBVH *pbvh)
       pbvh_bmesh_node_limit_ensure(pbvh, i);
     }
   }
+
+  BKE_pbvh_update_bounds(pbvh, (PBVH_UpdateBB | PBVH_UpdateOriginalBB | PBVH_UpdateRedraw));
 }
 
 void BKE_pbvh_bmesh_detail_size_set(PBVH *pbvh, float detail_size)
diff --git a/source/blender/gpu/GPU_buffers.h b/source/blender/gpu/GPU_buffers.h
index f7bc6fd3249..7edad4ca0ad 100644
--- a/source/blender/gpu/GPU_buffers.h
+++ b/source/blender/gpu/GPU_buffers.h
@@ -92,15 +92,17 @@ void GPU_pbvh_bmesh_buffers_update(GPU_PBVH_Buffers *buffers,
                                    struct GSet *bm_faces,
                                    struct GSet *bm_unique_verts,
                                    struct GSet *bm_other_verts,
-                                   const int update_flags);
+                                   const int update_flags,
+                                   const int cd_vert_node_offset);
 
 struct TM_TriMesh;
 void GPU_pbvh_trimesh_buffers_update(GPU_PBVH_Buffers *buffers,
-                                   struct TM_TriMesh *bm,
-                                   struct GSet *bm_faces,
-                                   struct TableGSet *bm_unique_verts,
-                                   struct TableGSet *bm_other_verts,
-                                   const int update_flags, const int cd_vert_node_offset);
+                                     struct TM_TriMesh *bm,
+                                     struct GSet *bm_faces,
+                                     struct TableGSet *bm_unique_verts,
+                                     struct TableGSet *bm_other_verts,
+                                     const int update_flags,
+                                     const int cd_vert_node_offset);
 
 void GPU_pbvh_grid_buffers_update(GPU_PBVH_Buffers *buffers,
                                   struct SubdivCCG *subdiv_ccg,
diff --git a/source/blender/gpu/intern/gpu_buffers.c b/source/blender/gpu/intern/gpu_buffers.c
index 90617f226dd..685fcabf9e0 100644
--- a/source/blender/gpu/intern/gpu_buffers.c
+++ b/source/blender/gpu/intern/gpu_buffers.c
@@ -42,6 +42,7 @@
 
 #include "BKE_DerivedMesh.h"
 #include "BKE_ccg.h"
+#include "BKE_global.h"
 #include "BKE_mesh.h"
 #include "BKE_paint.h"
 #include "BKE_pbvh.h"
@@ -794,6 +795,7 @@ static void gpu_bmesh_vert_to_buffer_copy(BMVert *v,
                                           const float fno[3],
                                           const float *fmask,
                                           const int cd_vert_mask_offset,
+                                          const int cd_vert_node_offset,
                                           const bool show_mask,
                                           const bool show_vcol,
                                           bool *empty_mask,
@@ -811,6 +813,13 @@ static void gpu_bmesh_vert_to_buffer_copy(BMVert *v,
 
   if (show_mask) {
     float effective_mask = fmask ? *fmask : BM_ELEM_CD_GET_FLOAT(v, cd_vert_mask_offset);
+
+    if (G.debug_value == 889) {
+      int ni = BM_ELEM_CD_GET_INT(v, cd_vert_node_offset);
+
+      effective_mask = ni == -1 ? 0.0f : (float)((ni*50) % 32) / 32.0f;
+    }
+
     uchar cmask = (uchar)(effective_mask * 255);
     GPU_vertbuf_attr_set(vert_buf, g_vbo_id.msk, v_index, &cmask);
     *empty_mask = *empty_mask && (cmask == 0);
@@ -1058,7 +1067,8 @@ void GPU_pbvh_bmesh_buffers_update(GPU_PBVH_Buffers *buffers,
                                    GSet *bm_faces,
                                    GSet *bm_unique_verts,
                                    GSet *bm_other_verts,
-                                   const int update_flags)
+                                   const int update_flags,
+                                   const int cd_vert_node_offset)
 {
   const bool show_mask = (update_flags & GPU_PBVH_BUFFERS_SHOW_MASK) != 0;
   const bool show_vcol = (update_flags & GPU_PBVH_BUFFERS_SHOW_VCOL) != 0;
@@ -1129,6 +1139,7 @@ void GPU_pbvh_bmesh_buffers_update(GPU_PBVH_Buffers *buffers,
                                           NULL,
                                           NULL,
                                           cd_vert_mask_offset,
+                                          cd_vert_node_offset,
                                           show_mask,
                                           show_vcol,
                                           &empty_mask,
@@ -1197,6 +1208,7 @@ void GPU_pbvh_bmesh_buffers_update(GPU_PBVH_Buffers *buffers,
                                         f->no,
                                         &fmask,
                                         cd_vert_mask_offset,
+                                        cd_vert_node_offset,
                                         show_mask,
                                         show_vcol,
                                         &empty_mask,