Sculpt: New API for keeping track of topology islands

Mesh islands (shells) are now calculated on an as-needed
basis and cached inside of a temp attribute,
`sculpt_topology_island_key`.  This attribute is updated
as needed when geometry changes (e.g. the trim brush)
or when mesh visibility changes.

This replaces the old behavior where the "topology" automasking
mode would walk the entire mesh on every stroke.

source/blender/blenkernel/BKE_paint.h

@@ -559,6 +559,8 @@ typedef struct SculptAttributePointers {
   SculptAttribute *automasking_stroke_id;
   SculptAttribute *automasking_cavity;
 
+  SculptAttribute *topology_island_key; /* CD_PROP_INT8 */
+
   /* BMesh */
   SculptAttribute *dyntopo_node_id_vertex;
   SculptAttribute *dyntopo_node_id_face;
@@ -756,6 +758,7 @@ typedef struct SculptSession {
 
   int last_automasking_settings_hash;
   uchar last_automask_stroke_id;
+  bool islands_valid; /* Is attrs.topology_island_key valid? */
 } SculptSession;
 
 void BKE_sculptsession_free(struct Object *ob);

source/blender/blenkernel/BKE_pbvh.h

@@ -74,18 +74,40 @@ struct PBVHPublic {
  * to be vertices.  This is not true of edges or faces which are pulled from
  * the base mesh.
  */
+
+#ifdef __cplusplus
+/* A few C++ methods to play nice with sets and maps. */
+#  define PBVH_REF_CXX_METHODS(Class) \
+    bool operator==(const Class b) const \
+    { \
+      return i == b.i; \
+    } \
+    uint64_t hash() const \
+    { \
+      return i; \
+    }
+#else
+#  define PBVH_REF_CXX_METHODS(cls)
+#endif
+
 typedef struct PBVHVertRef {
   intptr_t i;
+
+  PBVH_REF_CXX_METHODS(PBVHVertRef)
 } PBVHVertRef;
 
 /* NOTE: edges in PBVH_GRIDS are always pulled from the base mesh. */
 typedef struct PBVHEdgeRef {
   intptr_t i;
+
+  PBVH_REF_CXX_METHODS(PBVHVertRef)
 } PBVHEdgeRef;
 
 /* NOTE: faces in PBVH_GRIDS are always puled from the base mesh. */
 typedef struct PBVHFaceRef {
   intptr_t i;
+
+  PBVH_REF_CXX_METHODS(PBVHVertRef)
 } PBVHFaceRef;
 
 #define PBVH_REF_NONE -1LL

source/blender/editors/sculpt_paint/paint_hide.c

@@ -378,6 +378,8 @@ static int hide_show_exec(bContext *C, wmOperator *op)
   /* End undo. */
   SCULPT_undo_push_end(ob);
 
+  SCULPT_topology_islands_invalidate(ob->sculpt);
+
   /* Ensure that edges and faces get hidden as well (not used by
    * sculpt but it looks wrong when entering editmode otherwise). */
   if (pbvh_type == PBVH_FACES) {

source/blender/editors/sculpt_paint/paint_mask.c

@@ -1385,6 +1385,7 @@ static void sculpt_gesture_trim_begin(bContext *C, SculptGestureContext *sgconte
   Depsgraph *depsgraph = CTX_data_ensure_evaluated_depsgraph(C);
   sculpt_gesture_trim_calculate_depth(sgcontext);
   sculpt_gesture_trim_geometry_generate(sgcontext);
+  SCULPT_topology_islands_invalidate(ss);
   BKE_sculpt_update_object_for_edit(depsgraph, sgcontext->vc.obact, true, false, false);
   SCULPT_undo_push_node(sgcontext->vc.obact, NULL, SCULPT_UNDO_GEOMETRY);
 }

source/blender/editors/sculpt_paint/sculpt.cc

@@ -17,10 +17,12 @@
 #include "BLI_ghash.h"
 #include "BLI_gsqueue.h"
 #include "BLI_math.h"
+#include "BLI_set.hh"
 #include "BLI_task.h"
 #include "BLI_task.hh"
 #include "BLI_timeit.hh"
 #include "BLI_utildefines.h"
+#include "BLI_vector.hh"
 
 #include "DNA_brush_types.h"
 #include "DNA_customdata_types.h"
@@ -75,6 +77,8 @@
 
 using blender::float3;
 using blender::MutableSpan;
+using blender::Set;
+using blender::Vector;
 
 /* -------------------------------------------------------------------- */
 /** \name Sculpt PBVH Abstraction API
@@ -412,6 +416,8 @@ void SCULPT_face_set_visibility_set(SculptSession *ss, int face_set, bool visibl
 
 void SCULPT_face_visibility_all_invert(SculptSession *ss)
 {
+  SCULPT_topology_islands_invalidate(ss);
+
   BLI_assert(ss->face_sets != nullptr);
   BLI_assert(ss->hide_poly != nullptr);
   switch (BKE_pbvh_type(ss->pbvh)) {
@@ -435,6 +441,8 @@ void SCULPT_face_visibility_all_invert(SculptSession *ss)
 
 void SCULPT_face_visibility_all_set(SculptSession *ss, bool visible)
 {
+  SCULPT_topology_islands_invalidate(ss);
+
   switch (BKE_pbvh_type(ss->pbvh)) {
     case PBVH_FACES:
     case PBVH_GRIDS:
@@ -626,6 +634,9 @@ void SCULPT_visibility_sync_all_from_faces(Object *ob)
 {
   SculptSession *ss = ob->sculpt;
   Mesh *mesh = BKE_object_get_original_mesh(ob);
+
+  SCULPT_topology_islands_invalidate(ss);
+
   switch (BKE_pbvh_type(ss->pbvh)) {
     case PBVH_FACES: {
       /* We may have adjusted the ".hide_poly" attribute, now make the hide status attributes for
@@ -6301,4 +6312,70 @@ void SCULPT_face_set_set(SculptSession *ss, PBVHFaceRef face, int fset)
   }
 }
 
+int SCULPT_vertex_island_get(SculptSession *ss, PBVHVertRef vertex)
+{
+  if (ss->attrs.topology_island_key) {
+    return *static_cast<uint8_t *>(SCULPT_vertex_attr_get(vertex, ss->attrs.topology_island_key));
+  }
+
+  return -1;
+}
+
+void SCULPT_topology_islands_invalidate(SculptSession *ss)
+{
+  ss->islands_valid = false;
+}
+
+void SCULPT_topology_islands_ensure(Object *ob)
+{
+  SculptSession *ss = ob->sculpt;
+
+  if (ss->attrs.topology_island_key && ss->islands_valid &&
+      BKE_pbvh_type(ss->pbvh) != PBVH_BMESH) {
+    return;
+  }
+
+  SculptAttributeParams params;
+  params.permanent = params.stroke_only = params.simple_array = false;
+
+  ss->attrs.topology_island_key = BKE_sculpt_attribute_ensure(
+      ob, ATTR_DOMAIN_POINT, CD_PROP_INT8, SCULPT_ATTRIBUTE_NAME(topology_island_key), &params);
+  SCULPT_vertex_random_access_ensure(ss);
+
+  int totvert = SCULPT_vertex_count_get(ss);
+  Set<PBVHVertRef> visit;
+  Vector<PBVHVertRef> stack;
+  uint8_t island_nr = 0;
+
+  for (int i = 0; i < totvert; i++) {
+    PBVHVertRef vertex = BKE_pbvh_index_to_vertex(ss->pbvh, i);
+
+    if (visit.contains(vertex)) {
+      continue;
+    }
+
+    stack.clear();
+    stack.append(vertex);
+    visit.add(vertex);
+
+    while (stack.size()) {
+      PBVHVertRef vertex2 = stack.pop_last();
+      SculptVertexNeighborIter ni;
+
+      *static_cast<uint8_t *>(
+          SCULPT_vertex_attr_get(vertex2, ss->attrs.topology_island_key)) = island_nr;
+
+      SCULPT_VERTEX_NEIGHBORS_ITER_BEGIN (ss, vertex2, ni) {
+        if (visit.add(ni.vertex) && SCULPT_vertex_any_face_visible_get(ss, ni.vertex)) {
+          stack.append(ni.vertex);
+        }
+      }
+      SCULPT_VERTEX_NEIGHBORS_ITER_END(ni);
+    }
+
+    island_nr++;
+  }
+
+  ss->islands_valid = true;
+}
 /** \} */

source/blender/editors/sculpt_paint/sculpt_automasking.cc

@@ -181,9 +181,6 @@ static bool SCULPT_automasking_needs_factors_cache(const Sculpt *sd, const Brush
 {
 
   const int automasking_flags = sculpt_automasking_mode_effective_bits(sd, brush);
-  if (automasking_flags & BRUSH_AUTOMASKING_TOPOLOGY) {
-    return true;
-  }
 
   if (automasking_flags & (BRUSH_AUTOMASKING_BOUNDARY_EDGES |
                            BRUSH_AUTOMASKING_BOUNDARY_FACE_SETS | BRUSH_AUTOMASKING_VIEW_NORMAL)) {
@@ -540,6 +537,11 @@ float SCULPT_automasking_factor_get(AutomaskingCache *automasking,
     return automasking_factor_end(ss, automasking, vert, 0.0f);
   }
 
+  if (automasking->settings.flags & BRUSH_AUTOMASKING_TOPOLOGY &&
+      SCULPT_vertex_island_get(ss, vert) != automasking->settings.initial_island_nr) {
+    return 0.0f;
+  }
+
   if (automasking->settings.flags & BRUSH_AUTOMASKING_FACE_SETS) {
     if (!SCULPT_vertex_has_face_set(ss, vert, automasking->settings.initial_face_set)) {
       return 0.0f;
@@ -615,41 +617,6 @@ static bool automask_floodfill_cb(
               SCULPT_vertex_co_get(ss, to_v), data->location, data->radius, data->symm));
 }
 
-static void SCULPT_topology_automasking_init(Sculpt *sd, Object *ob)
-{
-  SculptSession *ss = ob->sculpt;
-  Brush *brush = BKE_paint_brush(&sd->paint);
-
-  if (BKE_pbvh_type(ss->pbvh) == PBVH_FACES && !ss->pmap) {
-    BLI_assert_unreachable();
-    return;
-  }
-
-  const int totvert = SCULPT_vertex_count_get(ss);
-  for (int i : IndexRange(totvert)) {
-    PBVHVertRef vertex = BKE_pbvh_index_to_vertex(ss->pbvh, i);
-
-    (*(float *)SCULPT_vertex_attr_get(vertex, ss->attrs.automasking_factor)) = 0.0f;
-  }
-
-  /* Flood fill automask to connected vertices. Limited to vertices inside
-   * the brush radius if the tool requires it. */
-  SculptFloodFill flood;
-  SCULPT_floodfill_init(ss, &flood);
-  const float radius = ss->cache ? ss->cache->radius : FLT_MAX;
-  SCULPT_floodfill_add_active(sd, ob, ss, &flood, radius);
-
-  AutomaskFloodFillData fdata = {0};
-
-  fdata.radius = radius;
-  fdata.use_radius = ss->cache && sculpt_automasking_is_constrained_by_radius(brush);
-  fdata.symm = SCULPT_mesh_symmetry_xyz_get(ob);
-
-  copy_v3_v3(fdata.location, SCULPT_active_vertex_co_get(ss));
-  SCULPT_floodfill_execute(ss, &flood, automask_floodfill_cb, &fdata);
-  SCULPT_floodfill_free(&flood);
-}
-
 static void sculpt_face_sets_automasking_init(Sculpt *sd, Object *ob)
 {
   SculptSession *ss = ob->sculpt;
@@ -827,6 +794,11 @@ AutomaskingCache *SCULPT_automasking_cache_init(Sculpt *sd, Brush *brush, Object
   bool use_stroke_id = false;
   int mode = sculpt_automasking_mode_effective_bits(sd, brush);
 
+  if (mode & BRUSH_AUTOMASKING_TOPOLOGY && ss->active_vertex.i != PBVH_REF_NONE) {
+    SCULPT_topology_islands_ensure(ob);
+    automasking->settings.initial_island_nr = SCULPT_vertex_island_get(ss, ss->active_vertex);
+  }
+
   if ((mode & BRUSH_AUTOMASKING_VIEW_OCCLUSION) && (mode & BRUSH_AUTOMASKING_VIEW_NORMAL)) {
     use_stroke_id = true;
 
@@ -919,7 +891,6 @@ AutomaskingCache *SCULPT_automasking_cache_init(Sculpt *sd, Brush *brush, Object
   /* Additive modes. */
   if (SCULPT_is_automasking_mode_enabled(sd, brush, BRUSH_AUTOMASKING_TOPOLOGY)) {
     SCULPT_vertex_random_access_ensure(ss);
-    SCULPT_topology_automasking_init(sd, ob);
   }
   if (SCULPT_is_automasking_mode_enabled(sd, brush, BRUSH_AUTOMASKING_FACE_SETS)) {
     SCULPT_vertex_random_access_ensure(ss);

source/blender/editors/sculpt_paint/sculpt_intern.h

@@ -410,6 +410,7 @@ typedef struct AutomaskingSettings {
   /* Flags from eAutomasking_flag. */
   int flags;
   int initial_face_set;
+  int initial_island_nr;
 
   float cavity_factor;
   int cavity_blur_steps;
@@ -1941,6 +1942,27 @@ bool SCULPT_tool_can_reuse_automask(int sculpt_tool);
 
 void SCULPT_ensure_valid_pivot(const struct Object *ob, struct Scene *scene);
 
+/* -------------------------------------------------------------------- */
+/** \name Topology island API
+ * \{
+ * Each mesh island shell gets its own integer
+ * key; these are temporary and internally limited to 8 bits.
+ * Uses the `ss->topology_island_key` attribute.
+ */
+
+/* Ensures vertex island keys exist and are valid. */
+void SCULPT_topology_islands_ensure(struct Object *ob);
+
+/* Mark vertex island keys as invalid.  Call when adding or hiding
+ * geometry.
+ */
+void SCULPT_topology_islands_invalidate(SculptSession *ss);
+
+/* Get vertex island key.*/
+int SCULPT_vertex_island_get(SculptSession *ss, PBVHVertRef vertex);
+
+/** \} */
+
 #ifdef __cplusplus
 }
 #endif

source/blender/editors/sculpt_paint/sculpt_ops.c

@@ -1323,6 +1323,8 @@ static int sculpt_reveal_all_exec(bContext *C, wmOperator *op)
     }
   }
 
+  SCULPT_topology_islands_invalidate(ss);
+
   if (!with_bmesh) {
     /* As an optimization, free the hide attribute when making all geometry visible. This allows
      * reduced memory usage without manually clearing it later, and allows sculpt operations to