Fix T72721: Add visibility flags updates to the PBVH

Currently, there its a function that sets manually the fully_hidden flag
of the nodes from the visibility operators in paint_hide.c. The undo
code was not updating the flag, so the visibility state of the nodes was
incorrect after preforming undo operations. This sometimes was drawing
fully hidden nodes with empty buffers, causing artifacts in the
geometry.

I added a function to mark nodes which visibility state changed (similar
as we are updating the mask flags and the nodes bounding boxes). This
way, the tools, operators and undo code don't have to update the
visibility flags, making everything much simpler to understand and
maintain.

I did not remove the flag update code from the current visibility
operators in this patch, but after reimplementing them (and all the new
ones) in the new visibility system, all visibility updates should be
done using this method and the BKE_pbvh_node_fully_hidden_set function
should be removed.

Reviewed By: jbakker

Maniphest Tasks: T72721

Differential Revision: https://developer.blender.org/D6767

4 files changed, 154 insertions, 7 deletions

diff --git a/source/blender/blenkernel/BKE_pbvh.h b/source/blender/blenkernel/BKE_pbvh.h
index 9eb10d296de..a26148d11bf 100644
--- a/source/blender/blenkernel/BKE_pbvh.h
+++ b/source/blender/blenkernel/BKE_pbvh.h
@@ -66,13 +66,14 @@ typedef enum {
   PBVH_UpdateDrawBuffers = 1 << 4,
   PBVH_UpdateRedraw = 1 << 5,
   PBVH_UpdateMask = 1 << 6,
+  PBVH_UpdateVisibility = 1 << 8,
 
-  PBVH_RebuildDrawBuffers = 1 << 7,
-  PBVH_FullyHidden = 1 << 8,
-  PBVH_FullyMasked = 1 << 9,
-  PBVH_FullyUnmasked = 1 << 10,
+  PBVH_RebuildDrawBuffers = 1 << 9,
+  PBVH_FullyHidden = 1 << 10,
+  PBVH_FullyMasked = 1 << 11,
+  PBVH_FullyUnmasked = 1 << 12,
 
-  PBVH_UpdateTopology = 1 << 11,
+  PBVH_UpdateTopology = 1 << 13,
 } PBVHNodeFlags;
 
 typedef struct PBVHFrustumPlanes {
@@ -246,6 +247,7 @@ void BKE_pbvh_node_mark_update_mask(PBVHNode *node);
 void BKE_pbvh_node_mark_rebuild_draw(PBVHNode *node);
 void BKE_pbvh_node_mark_redraw(PBVHNode *node);
 void BKE_pbvh_node_mark_normals_update(PBVHNode *node);
+void BKE_pbvh_node_mark_visibility_update(PBVHNode *node);
 void BKE_pbvh_node_mark_topology_update(PBVHNode *node);
 void BKE_pbvh_node_fully_hidden_set(PBVHNode *node, int fully_hidden);
 void BKE_pbvh_node_fully_masked_set(PBVHNode *node, int fully_masked);
@@ -286,6 +288,7 @@ void BKE_pbvh_bmesh_after_stroke(PBVH *bvh);
 
 void BKE_pbvh_update_bounds(PBVH *bvh, int flags);
 void BKE_pbvh_update_vertex_data(PBVH *bvh, int flags);
+void BKE_pbvh_update_visibility(PBVH *bvh);
 void BKE_pbvh_update_normals(PBVH *bvh, struct SubdivCCG *subdiv_ccg);
 void BKE_pbvh_redraw_BB(PBVH *bvh, float bb_min[3], float bb_max[3]);
 void BKE_pbvh_get_grid_updates(PBVH *bvh, bool clear, void ***r_gridfaces, int *r_totface);
diff --git a/source/blender/blenkernel/intern/pbvh.c b/source/blender/blenkernel/intern/pbvh.c
index 141e93183fb..3be3adf0e8f 100644
--- a/source/blender/blenkernel/intern/pbvh.c
+++ b/source/blender/blenkernel/intern/pbvh.c
@@ -1378,6 +1378,140 @@ void BKE_pbvh_update_vertex_data(PBVH *bvh, int flag)
   }
 }
 
+static void pbvh_faces_node_visibility_update(PBVH *bvh, PBVHNode *node)
+{
+  MVert *mvert;
+  const int *vert_indices;
+  int totvert, i;
+  BKE_pbvh_node_num_verts(bvh, node, NULL, &totvert);
+  BKE_pbvh_node_get_verts(bvh, node, &vert_indices, &mvert);
+
+  for (i = 0; i < totvert; i++) {
+    MVert *v = &mvert[vert_indices[i]];
+    if (!(v->flag & ME_HIDE)) {
+      BKE_pbvh_node_fully_hidden_set(node, false);
+      return;
+    }
+  }
+
+  BKE_pbvh_node_fully_hidden_set(node, true);
+}
+
+static void pbvh_grids_node_visibility_update(PBVH *bvh, PBVHNode *node)
+{
+  CCGElem **grids;
+  BLI_bitmap **grid_hidden;
+  int *grid_indices, totgrid, i;
+
+  BKE_pbvh_node_get_grids(bvh, node, &grid_indices, &totgrid, NULL, NULL, &grids);
+  grid_hidden = BKE_pbvh_grid_hidden(bvh);
+  CCGKey key = *BKE_pbvh_get_grid_key(bvh);
+
+  for (i = 0; i < totgrid; i++) {
+    int g = grid_indices[i], x, y;
+    BLI_bitmap *gh = grid_hidden[g];
+
+    if (!gh) {
+      BKE_pbvh_node_fully_hidden_set(node, false);
+      return;
+    }
+
+    for (y = 0; y < key.grid_size; y++) {
+      for (x = 0; x < key.grid_size; x++) {
+        if (!BLI_BITMAP_TEST(gh, y * key.grid_size + x)) {
+          BKE_pbvh_node_fully_hidden_set(node, false);
+          return;
+        }
+      }
+    }
+  }
+  BKE_pbvh_node_fully_hidden_set(node, true);
+}
+
+static void pbvh_bmesh_node_visibility_update(PBVH *bvh, PBVHNode *node)
+{
+  BMesh *bm;
+  GSet *unique, *other;
+
+  bm = BKE_pbvh_get_bmesh(bvh);
+  unique = BKE_pbvh_bmesh_node_unique_verts(node);
+  other = BKE_pbvh_bmesh_node_other_verts(node);
+
+  GSetIterator gs_iter;
+
+  GSET_ITER (gs_iter, unique) {
+    BMVert *v = BLI_gsetIterator_getKey(&gs_iter);
+    if (!BM_elem_flag_test(v, BM_ELEM_HIDDEN)) {
+      BKE_pbvh_node_fully_hidden_set(node, false);
+      return;
+    }
+  }
+
+  GSET_ITER (gs_iter, other) {
+    BMVert *v = BLI_gsetIterator_getKey(&gs_iter);
+    if (!BM_elem_flag_test(v, BM_ELEM_HIDDEN)) {
+      BKE_pbvh_node_fully_hidden_set(node, false);
+      return;
+    }
+  }
+
+  BKE_pbvh_node_fully_hidden_set(node, true);
+}
+
+static void pbvh_update_visibility_task_cb(void *__restrict userdata,
+                                           const int n,
+                                           const TaskParallelTLS *__restrict UNUSED(tls))
+{
+
+  PBVHUpdateData *data = userdata;
+  PBVH *bvh = data->bvh;
+  PBVHNode *node = data->nodes[n];
+  if (node->flag & PBVH_UpdateMask) {
+    switch (BKE_pbvh_type(bvh)) {
+      case PBVH_FACES:
+        pbvh_faces_node_visibility_update(bvh, node);
+        break;
+      case PBVH_GRIDS:
+        pbvh_grids_node_visibility_update(bvh, node);
+        break;
+      case PBVH_BMESH:
+        pbvh_bmesh_node_visibility_update(bvh, node);
+        break;
+    }
+    node->flag &= ~PBVH_UpdateMask;
+  }
+}
+
+static void pbvh_update_visibility(PBVH *bvh, PBVHNode **nodes, int totnode)
+{
+  PBVHUpdateData data = {
+      .bvh = bvh,
+      .nodes = nodes,
+  };
+
+  PBVHParallelSettings settings;
+  BKE_pbvh_parallel_range_settings(&settings, true, totnode);
+  BKE_pbvh_parallel_range(0, totnode, &data, pbvh_update_visibility_task_cb, &settings);
+}
+
+void BKE_pbvh_update_visibility(PBVH *bvh)
+{
+  if (!bvh->nodes) {
+    return;
+  }
+
+  PBVHNode **nodes;
+  int totnode;
+
+  BKE_pbvh_search_gather(
+      bvh, update_search_cb, POINTER_FROM_INT(PBVH_UpdateVisibility), &nodes, &totnode);
+  pbvh_update_visibility(bvh, nodes, totnode);
+
+  if (nodes) {
+    MEM_freeN(nodes);
+  }
+}
+
 void BKE_pbvh_redraw_BB(PBVH *bvh, float bb_min[3], float bb_max[3])
 {
   PBVHIter iter;
@@ -1533,6 +1667,11 @@ void BKE_pbvh_node_mark_normals_update(PBVHNode *node)
   node->flag |= PBVH_UpdateNormals;
 }
 
+void BKE_pbvh_node_mark_visibility_update(PBVHNode *node)
+{
+  node->flag |= PBVH_UpdateVisibility;
+}
+
 void BKE_pbvh_node_fully_hidden_set(PBVHNode *node, int fully_hidden)
 {
   BLI_assert(node->flag & PBVH_Leaf);
diff --git a/source/blender/blenkernel/intern/subdiv_ccg.c b/source/blender/blenkernel/intern/subdiv_ccg.c
index 8654c50a783..3c1a9c4d3d6 100644
--- a/source/blender/blenkernel/intern/subdiv_ccg.c
+++ b/source/blender/blenkernel/intern/subdiv_ccg.c
@@ -623,9 +623,9 @@ void BKE_subdiv_ccg_destroy(SubdivCCG *subdiv_ccg)
   MEM_SAFE_FREE(subdiv_ccg->grid_flag_mats);
   if (subdiv_ccg->grid_hidden != NULL) {
     for (int grid_index = 0; grid_index < num_grids; grid_index++) {
-      MEM_freeN(subdiv_ccg->grid_hidden[grid_index]);
+      MEM_SAFE_FREE(subdiv_ccg->grid_hidden[grid_index]);
     }
-    MEM_freeN(subdiv_ccg->grid_hidden);
+    MEM_SAFE_FREE(subdiv_ccg->grid_hidden);
   }
   if (subdiv_ccg->subdiv != NULL) {
     BKE_subdiv_free(subdiv_ccg->subdiv);
diff --git a/source/blender/editors/sculpt_paint/sculpt_undo.c b/source/blender/editors/sculpt_paint/sculpt_undo.c
index cd34e2c6f99..bc4ed0bf7bf 100644
--- a/source/blender/editors/sculpt_paint/sculpt_undo.c
+++ b/source/blender/editors/sculpt_paint/sculpt_undo.c
@@ -80,6 +80,7 @@ static void update_cb(PBVHNode *node, void *rebuild)
   BKE_pbvh_node_mark_update_mask(node);
   if (*((bool *)rebuild)) {
     BKE_pbvh_node_mark_rebuild_draw(node);
+    BKE_pbvh_node_mark_visibility_update(node);
   }
   BKE_pbvh_node_fully_hidden_set(node, 0);
 }
@@ -641,6 +642,10 @@ static void sculpt_undo_restore_list(bContext *C, Depsgraph *depsgraph, ListBase
       tag_update |= true;
     }
 
+    if (update_visibility) {
+      BKE_pbvh_update_visibility(ss->pbvh);
+    }
+
     if (BKE_pbvh_type(ss->pbvh) == PBVH_FACES && update_visibility) {
       Mesh *mesh = ob->data;
       BKE_mesh_flush_hidden_from_verts(mesh);