Sculpt: Pose Brush option to affect loose parts

This option allows posing meshes with different disconnected elements
using the Pose Brush.

This is achieved by doing the following:
- Creating an ID per vertex that stores the connected component of that vertex.
- By using those IDs, one fake topology connection is created per vertex to the nearest vertex in a different ID. The maximum distance to create that connection is determined by the "Max Element Distance" property. These fake connectivity neighbors are used in the Sculpt API functions iterators, so all the algorithms of the Pose Brush can run without modifications as if everything was part of the same mesh.

In order to make this work, the "Connected only" property of the Pose Brush needs to be disabled. This will add an extra performance cost to the Pose Brush and its preview. To achieve optimal results, max element distance should be as low as possible.

Reviewed By: sergey, campbellbarton

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

1 files changed, 262 insertions, 0 deletions

diff --git a/source/blender/editors/sculpt_paint/sculpt.c b/source/blender/editors/sculpt_paint/sculpt.c
index 123f585b250..3098a0bfcb8 100644
--- a/source/blender/editors/sculpt_paint/sculpt.c
+++ b/source/blender/editors/sculpt_paint/sculpt.c
@@ -649,6 +649,13 @@ static void sculpt_vertex_neighbors_get_faces(SculptSession *ss,
       }
     }
   }
+
+  if (ss->fake_neighbors.use_fake_neighbors) {
+    BLI_assert(ss->fake_neighbors.fake_neighbor_index != NULL);
+    if (ss->fake_neighbors.fake_neighbor_index[index] != FAKE_NEIGHBOR_NONE) {
+      sculpt_vertex_neighbor_add(iter, ss->fake_neighbors.fake_neighbor_index[index]);
+    }
+  }
 }
 
 static void sculpt_vertex_neighbors_get_grids(SculptSession *ss,
@@ -681,6 +688,13 @@ static void sculpt_vertex_neighbors_get_grids(SculptSession *ss,
                                    neighbors.coords[i].y * key->grid_size + neighbors.coords[i].x);
   }
 
+  if (ss->fake_neighbors.use_fake_neighbors) {
+    BLI_assert(ss->fake_neighbors.fake_neighbor_index != NULL);
+    if (ss->fake_neighbors.fake_neighbor_index[index] != FAKE_NEIGHBOR_NONE) {
+      sculpt_vertex_neighbor_add(iter, ss->fake_neighbors.fake_neighbor_index[index]);
+    }
+  }
+
   if (neighbors.coords != neighbors.coords_fixed) {
     MEM_freeN(neighbors.coords);
   }
@@ -7113,6 +7127,9 @@ void SCULPT_flush_update_done(const bContext *C, Object *ob, SculptUpdateType up
 
   if (update_flags & SCULPT_UPDATE_COORDS) {
     BKE_pbvh_update_bounds(ss->pbvh, PBVH_UpdateOriginalBB);
+
+    /* Coordinates were modified, so fake neighbors are not longer valid. */
+    SCULPT_fake_neighbors_free(ob);
   }
 
   if (update_flags & SCULPT_UPDATE_MASK) {
@@ -8139,6 +8156,251 @@ static void SCULPT_OT_sample_color(wmOperatorType *ot)
   ot->flag = OPTYPE_REGISTER;
 }
 
+/* Fake Neighbors. */
+/* This allows the sculpt tools to work on meshes with multiple connected components as they had
+ * only one connected component. When initialized and enabled, the sculpt API will return extra
+ * connectivity neighbors that are not in the real mesh. These neighbors are calculated for each
+ * vertex using the minimun distance to a vertex that is in a different connected component. */
+
+/* The fake neighbors first need to be ensured to be initialized.
+ * After that tools which needs fake neighbors functionality need to
+ * temporarily enable it:
+ *
+ *   void my_awesome_sculpt_tool() {
+ *     SCULPT_fake_neighbors_ensure(sd, object, brush->disconnected_distance_max);
+ *     SCULPT_fake_neighbors_enable(ob);
+ *
+ *     ... Logic of the tool ...
+ *     SCULPT_fake_neighbors_disable(ob);
+ *   }
+ *
+ * Such approach allows to keep all the connectivity information ready for reuse
+ * (withouy having lag prior to every stroke), but also makes it so the affect
+ * is localized to a specific brushes and tools only. */
+
+enum {
+  SCULPT_TOPOLOGY_ID_NONE,
+  SCULPT_TOPOLOGY_ID_DEFAULT,
+};
+
+static int SCULPT_vertex_get_connected_component(SculptSession *ss, int index)
+{
+  if (ss->vertex_info.connected_component) {
+    return ss->vertex_info.connected_component[index];
+  }
+  return SCULPT_TOPOLOGY_ID_DEFAULT;
+}
+
+static void SCULPT_fake_neighbor_init(SculptSession *ss, const float max_dist)
+{
+  const int totvert = SCULPT_vertex_count_get(ss);
+  ss->fake_neighbors.fake_neighbor_index = MEM_malloc_arrayN(
+      totvert, sizeof(int), "fake neighbor");
+  for (int i = 0; i < totvert; i++) {
+    ss->fake_neighbors.fake_neighbor_index[i] = FAKE_NEIGHBOR_NONE;
+  }
+
+  ss->fake_neighbors.current_max_distance = max_dist;
+}
+
+static void SCULPT_fake_neighbor_add(SculptSession *ss, int v_index_a, int v_index_b)
+{
+  if (ss->fake_neighbors.fake_neighbor_index[v_index_a] == FAKE_NEIGHBOR_NONE) {
+    ss->fake_neighbors.fake_neighbor_index[v_index_a] = v_index_b;
+    ss->fake_neighbors.fake_neighbor_index[v_index_b] = v_index_a;
+  }
+}
+
+static void sculpt_pose_fake_neighbors_free(SculptSession *ss)
+{
+  MEM_SAFE_FREE(ss->fake_neighbors.fake_neighbor_index);
+}
+
+typedef struct NearestVertexFakeNeighborTLSData {
+  int nearest_vertex_index;
+  float nearest_vertex_distance_squared;
+  int current_topology_id;
+} NearestVertexFakeNeighborTLSData;
+
+static void do_fake_neighbor_search_task_cb(void *__restrict userdata,
+                                            const int n,
+                                            const TaskParallelTLS *__restrict tls)
+{
+  SculptThreadedTaskData *data = userdata;
+  SculptSession *ss = data->ob->sculpt;
+  NearestVertexFakeNeighborTLSData *nvtd = tls->userdata_chunk;
+  PBVHVertexIter vd;
+
+  BKE_pbvh_vertex_iter_begin(ss->pbvh, data->nodes[n], vd, PBVH_ITER_UNIQUE)
+  {
+    int vd_topology_id = SCULPT_vertex_get_connected_component(ss, vd.index);
+    if (vd_topology_id != nvtd->current_topology_id &&
+        ss->fake_neighbors.fake_neighbor_index[vd.index] == FAKE_NEIGHBOR_NONE) {
+      float distance_squared = len_squared_v3v3(vd.co, data->nearest_vertex_search_co);
+      if (distance_squared < nvtd->nearest_vertex_distance_squared &&
+          distance_squared < data->max_distance_squared) {
+        nvtd->nearest_vertex_index = vd.index;
+        nvtd->nearest_vertex_distance_squared = distance_squared;
+      }
+    }
+  }
+  BKE_pbvh_vertex_iter_end;
+}
+
+static void fake_neighbor_search_reduce(const void *__restrict UNUSED(userdata),
+                                        void *__restrict chunk_join,
+                                        void *__restrict chunk)
+{
+  NearestVertexFakeNeighborTLSData *join = chunk_join;
+  NearestVertexFakeNeighborTLSData *nvtd = chunk;
+  if (join->nearest_vertex_index == -1) {
+    join->nearest_vertex_index = nvtd->nearest_vertex_index;
+    join->nearest_vertex_distance_squared = nvtd->nearest_vertex_distance_squared;
+  }
+  else if (nvtd->nearest_vertex_distance_squared < join->nearest_vertex_distance_squared) {
+    join->nearest_vertex_index = nvtd->nearest_vertex_index;
+    join->nearest_vertex_distance_squared = nvtd->nearest_vertex_distance_squared;
+  }
+}
+
+static int SCULPT_fake_neighbor_search(Sculpt *sd, Object *ob, const int index, float max_distance)
+{
+  SculptSession *ss = ob->sculpt;
+  PBVHNode **nodes = NULL;
+  int totnode;
+  SculptSearchSphereData data = {
+      .ss = ss,
+      .sd = sd,
+      .radius_squared = max_distance * max_distance,
+      .original = false,
+      .center = SCULPT_vertex_co_get(ss, index),
+  };
+  BKE_pbvh_search_gather(ss->pbvh, SCULPT_search_sphere_cb, &data, &nodes, &totnode);
+
+  if (totnode == 0) {
+    return -1;
+  }
+
+  SculptThreadedTaskData task_data = {
+      .sd = sd,
+      .ob = ob,
+      .nodes = nodes,
+      .max_distance_squared = max_distance * max_distance,
+  };
+
+  copy_v3_v3(task_data.nearest_vertex_search_co, SCULPT_vertex_co_get(ss, index));
+
+  NearestVertexFakeNeighborTLSData nvtd;
+  nvtd.nearest_vertex_index = -1;
+  nvtd.nearest_vertex_distance_squared = FLT_MAX;
+  nvtd.current_topology_id = SCULPT_vertex_get_connected_component(ss, index);
+
+  TaskParallelSettings settings;
+  BKE_pbvh_parallel_range_settings(&settings, true, totnode);
+  settings.func_reduce = fake_neighbor_search_reduce;
+  settings.userdata_chunk = &nvtd;
+  settings.userdata_chunk_size = sizeof(NearestVertexFakeNeighborTLSData);
+  BLI_task_parallel_range(0, totnode, &task_data, do_fake_neighbor_search_task_cb, &settings);
+
+  MEM_SAFE_FREE(nodes);
+
+  return nvtd.nearest_vertex_index;
+}
+
+typedef struct SculptTopologyIDFloodFillData {
+  int next_id;
+} SculptTopologyIDFloodFillData;
+
+static bool SCULPT_connected_components_floodfill_cb(
+    SculptSession *ss, int from_v, int to_v, bool UNUSED(is_duplicate), void *userdata)
+{
+  SculptTopologyIDFloodFillData *data = userdata;
+  ss->vertex_info.connected_component[from_v] = data->next_id;
+  ss->vertex_info.connected_component[to_v] = data->next_id;
+  return true;
+}
+
+void SCULPT_connected_components_ensure(Object *ob)
+{
+  SculptSession *ss = ob->sculpt;
+
+  /* Topology IDs already initialized. They only need to be recalculated when the PBVH is rebuild.
+   */
+  if (ss->vertex_info.connected_component) {
+    return;
+  }
+
+  const int totvert = SCULPT_vertex_count_get(ss);
+  ss->vertex_info.connected_component = MEM_malloc_arrayN(totvert, sizeof(int), "topology ID");
+
+  for (int i = 0; i < totvert; i++) {
+    ss->vertex_info.connected_component[i] = SCULPT_TOPOLOGY_ID_NONE;
+  }
+
+  int next_id = 0;
+  for (int i = 0; i < totvert; i++) {
+    if (ss->vertex_info.connected_component[i] == SCULPT_TOPOLOGY_ID_NONE) {
+      SculptFloodFill flood;
+      SCULPT_floodfill_init(ss, &flood);
+      SCULPT_floodfill_add_initial(&flood, i);
+      SculptTopologyIDFloodFillData data;
+      data.next_id = next_id;
+      SCULPT_floodfill_execute(ss, &flood, SCULPT_connected_components_floodfill_cb, &data);
+      SCULPT_floodfill_free(&flood);
+      next_id++;
+    }
+  }
+}
+
+void SCULPT_fake_neighbors_ensure(Sculpt *sd, Object *ob, const float max_dist)
+{
+  SculptSession *ss = ob->sculpt;
+  const int totvert = SCULPT_vertex_count_get(ss);
+
+  /* Fake neighbors were already initialized with the same distance, so no need to be recalculated.
+   */
+  if (ss->fake_neighbors.fake_neighbor_index &&
+      ss->fake_neighbors.current_max_distance == max_dist) {
+    return;
+  }
+
+  SCULPT_connected_components_ensure(ob);
+  SCULPT_fake_neighbor_init(ss, max_dist);
+
+  for (int i = 0; i < totvert; i++) {
+    const int from_v = i;
+
+    /* This vertex does not have a fake neighbor yet, seach one for it. */
+    if (ss->fake_neighbors.fake_neighbor_index[from_v] == FAKE_NEIGHBOR_NONE) {
+      const int to_v = SCULPT_fake_neighbor_search(sd, ob, from_v, max_dist);
+      if (to_v != -1) {
+        /* Add the fake neighbor if available. */
+        SCULPT_fake_neighbor_add(ss, from_v, to_v);
+      }
+    }
+  }
+}
+
+void SCULPT_fake_neighbors_enable(Object *ob)
+{
+  SculptSession *ss = ob->sculpt;
+  BLI_assert(ss->fake_neighbors.fake_neighbor_index != NULL);
+  ss->fake_neighbors.use_fake_neighbors = true;
+}
+
+void SCULPT_fake_neighbors_disable(Object *ob)
+{
+  SculptSession *ss = ob->sculpt;
+  BLI_assert(ss->fake_neighbors.fake_neighbor_index != NULL);
+  ss->fake_neighbors.use_fake_neighbors = false;
+}
+
+void SCULPT_fake_neighbors_free(Object *ob)
+{
+  SculptSession *ss = ob->sculpt;
+  sculpt_pose_fake_neighbors_free(ss);
+}
+
 void ED_operatortypes_sculpt(void)
 {
   WM_operatortype_append(SCULPT_OT_brush_stroke);