Sculpt: Expand Operator

Expand is a new operator for Sculpt Mode which is intended to be the main
tool for masking, Face Set editing, interacting with the filters and pattern
creation.

The fundamentals of the tool are similar to the previous sculpt.mask_expand
operator. It shares the same default shortcuts and functionality, making
the previous operator obsolete.

The shortcuts to execute the operator are:
- Shift + A: Expand mask
- Shift + Alt + A: Expand mask by normals
- Shift + W: Expand Face Set
- Shift + Alt + W: Resize current Face Set

The main changes compared to the previous sculpt.mask_expand operator are:
- Modal keymap, all operator options can be changed in real time while the
operator is running.
- Supports creating Mask, Face Sets and Sculpt Vertex Colors.
- Much better code, new features can be easily integrated.

Limitations:
- All Mask operations are supported for Sculpt Vertex colors, but not exposed
by default as their support is still experimental.
- Dyntopo does not support any Face Set or Sculpt Vertex Colors. functionality
 (they are not implemented in general for Dyntopo).
- Multires does not support any feature related to geodesic distances.
- Multires does not support vertex colors.
- Multires does not support recursions.
- In Multires, Face Sets snaping does not initialize all current enabled Face
Sets when toggling snapping.
- In Multires, Face Sets are created at base mesh level (works by this by
 design, like any other tool).
- Unlike the previous mask_expand operator, this one does not blur the mask
by default after finishing Expand as that does not fit the new design.
The mask can still be blurred by using the mask filter manually.

Reviewed By: JacquesLucke

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

release/scripts/modules/bl_keymap_utils/keymap_hierarchy.py

@@ -114,6 +114,7 @@ _km_hierarchy = [
         ('Custom Normals Modal Map', 'EMPTY', 'WINDOW', []),
         ('Bevel Modal Map', 'EMPTY', 'WINDOW', []),
         ('Paint Stroke Modal', 'EMPTY', 'WINDOW', []),
+        ('Sculpt Expand Modal', 'EMPTY', 'WINDOW', []),
         ('Paint Curve', 'EMPTY', 'WINDOW', []),
 
         ('Object Non-modal', 'EMPTY', 'WINDOW', []),  # mode change

release/scripts/presets/keyconfig/keymap_data/blender_default.py

@@ -4470,6 +4470,15 @@ def km_sculpt(params):
          {"properties": [("mode", 'INVERT')]}),
         ("sculpt.brush_stroke", {"type": 'LEFTMOUSE', "value": 'PRESS', "shift": True},
          {"properties": [("mode", 'SMOOTH')]}),
+        # Expand
+        ("sculpt.expand", {"type": 'A', "value": 'PRESS', "shift": True},
+         {"properties": [("target", "MASK"), ("falloff_type", "GEODESIC"), ("invert", True)]}),
+        ("sculpt.expand", {"type": 'A', "value": 'PRESS', "shift": True, "alt": True},
+         {"properties": [("target", "MASK"), ("falloff_type", "NORMALS"), ("invert", False)]}),
+        ("sculpt.expand", {"type": 'W', "value": 'PRESS', "shift": True},
+         {"properties": [("target", "FACE_SETS"), ("falloff_type", "GEODESIC"), ("invert", False), ("use_modify_active", False)]}),
+        ("sculpt.expand", {"type": 'W', "value": 'PRESS', "shift": True, "alt": True},
+         {"properties": [("target", "FACE_SETS"), ("falloff_type", "BOUNDARY_FACE_SET"),("invert", False), ("use_modify_active", True)]}),
         # Partial Visibility Show/hide
         ("sculpt.face_set_change_visibility", {"type": 'H', "value": 'PRESS'},
          {"properties": [("mode", 'TOGGLE')]}),
@@ -4477,8 +4486,6 @@ def km_sculpt(params):
          {"properties": [("mode", 'HIDE_ACTIVE')]}),
         ("sculpt.face_set_change_visibility", {"type": 'H', "value": 'PRESS', "alt": True},
          {"properties": [("mode", 'SHOW_ALL')]}),
-        ("sculpt.mask_expand", {"type": 'W', "value": 'PRESS', "shift": True},
-         {"properties": [("use_normals", False), ("keep_previous_mask", False), ("invert", False), ("smooth_iterations", 0), ("create_face_set", True)]}),
         ("sculpt.face_set_edit", {"type": 'W', "value": 'PRESS', "ctrl": True},
          {"properties": [("mode", 'GROW')]}),
         ("sculpt.face_set_edit", {"type": 'W', "value": 'PRESS', "ctrl": True, "alt": True},
@@ -4499,10 +4506,6 @@ def km_sculpt(params):
         ("paint.mask_lasso_gesture", {"type": 'LEFTMOUSE', "value": 'PRESS', "shift": True, "ctrl": True}, None),
         ("wm.context_toggle", {"type": 'M', "value": 'PRESS', "ctrl": True},
          {"properties": [("data_path", 'scene.tool_settings.sculpt.show_mask')]}),
-        ("sculpt.mask_expand", {"type": 'A', "value": 'PRESS', "shift": True},
-         {"properties": [("use_normals", False), ("keep_previous_mask", False), ("invert", True), ("smooth_iterations", 2), ("create_face_set", False)]}),
-        ("sculpt.mask_expand", {"type": 'A', "value": 'PRESS', "shift": True, 'alt': True},
-         {"properties": [("use_normals", True), ("keep_previous_mask", True), ("invert", False), ("smooth_iterations", 0), ("create_face_set", False)]}),
         # Dynamic topology
         ("sculpt.dynamic_topology_toggle", {"type": 'D', "value": 'PRESS', "ctrl": True}, None),
         ("sculpt.dyntopo_detail_size_edit", {"type": 'D', "value": 'PRESS', "shift": True}, None),
@@ -5571,6 +5574,39 @@ def km_paint_stroke_modal(_params):
 
     return keymap
 
+def km_sculpt_expand_modal(_params):
+    items = []
+    keymap = (
+        "Sculpt Expand Modal",
+        {"space_type": 'EMPTY', "region_type": 'WINDOW', "modal": True},
+        {"items": items},
+    )
+
+    items.extend([
+        ("CANCEL", {"type": 'ESC', "value": 'PRESS', "any": True}, None),
+        ("CANCEL", {"type": 'RIGHTMOUSE', "value": 'PRESS', "any": True}, None),
+        ("CONFIRM", {"type": 'LEFTMOUSE', "value": 'PRESS', "any": True}, None),
+        ("INVERT", {"type": 'F', "value": 'PRESS', "any": True, "repeat" : False}, None),
+        ("PRESERVE", {"type": 'E', "value": 'PRESS', "any": True, "repeat" : False}, None),
+        ("GRADIENT", {"type": 'G', "value": 'PRESS', "any": True, "repeat" : False}, None),
+        ("RECURSION_STEP_GEODESIC", {"type": 'R', "value": 'PRESS', "repeat" : False}, None),
+        ("RECURSION_STEP_TOPOLOGY", {"type": 'R', "value": 'PRESS', "alt" : True ,"any": True, "repeat" : False}, None),
+        ("MOVE_TOGGLE", {"type": 'SPACE', "value": 'ANY', "any": True, "repeat" : False}, None),
+        ("FALLOFF_GEODESICS", {"type": 'ONE', "value": 'PRESS', "any": True, "repeat" : False}, None),
+        ("FALLOFF_TOPOLOGY", {"type": 'TWO', "value": 'PRESS', "any": True, "repeat" : False}, None),
+        ("FALLOFF_TOPOLOGY_DIAGONALS", {"type": 'THREE', "value": 'PRESS', "any": True, "repeat" : False}, None),
+        ("FALLOFF_SPHERICAL", {"type": 'FOUR', "value": 'PRESS', "any": True, "repeat" : False}, None),
+        ("SNAP_TOGGLE", {"type": 'LEFT_CTRL', "value": 'ANY', "repeat" : False}, None),
+        ("LOOP_COUNT_INCREASE", {"type": 'W', "value": 'PRESS', "any": True, "repeat" : True}, None),
+        ("LOOP_COUNT_DECREASE", {"type": 'Q', "value": 'PRESS', "any": True, "repeat" : True}, None),
+        ("BRUSH_GRADIENT_TOGGLE", {"type": 'B', "value": 'PRESS', "any": True, "repeat" : False}, None),
+        ("TEXTURE_DISTORTION_INCREASE", {"type": 'Y', "value": 'PRESS', "any": False, "repeat" : True}, None),
+        ("TEXTURE_DISTORTION_DECREASE", {"type": 'T', "value": 'PRESS', "any": False, "repeat" : True}, None),
+    ])
+    return keymap
+
+
+
 
 # Fallback for gizmos that don't have custom a custom key-map.
 def km_generic_gizmo(_params):
@@ -7085,6 +7121,7 @@ def generate_keymaps(params=None):
         km_view3d_zoom_modal(params),
         km_view3d_dolly_modal(params),
         km_paint_stroke_modal(params),
+        km_sculpt_expand_modal(params),
 
         # Gizmos.
         km_generic_gizmo(params),

source/blender/blenkernel/BKE_paint.h

@@ -469,10 +469,19 @@ typedef struct SculptSession {
   struct MPropCol *vcol;
   float *vmask;
 
-  /* Mesh connectivity */
+  /* Mesh connectivity maps. */
+  /* Vertices to adjacent polys. */
   struct MeshElemMap *pmap;
   int *pmap_mem;
 
+  /* Edges to adjacent polys. */
+  struct MeshElemMap *epmap;
+  int *epmap_mem;
+
+  /* Vertices to adjacent edges. */
+  struct MeshElemMap *vemap;
+  int *vemap_mem;
+
   /* Mesh Face Sets */
   /* Total number of polys of the base mesh. */
   int totfaces;
@@ -508,6 +517,7 @@ typedef struct SculptSession {
 
   struct StrokeCache *cache;
   struct FilterCache *filter_cache;
+  struct ExpandCache *expand_cache;
 
   /* Cursor data and active vertex for tools */
   int active_vertex_index;

source/blender/blenkernel/intern/paint.c

@@ -1422,6 +1422,12 @@ static void sculptsession_free_pbvh(Object *object)
   MEM_SAFE_FREE(ss->pmap);
   MEM_SAFE_FREE(ss->pmap_mem);
 
+  MEM_SAFE_FREE(ss->epmap);
+  MEM_SAFE_FREE(ss->epmap_mem);
+
+  MEM_SAFE_FREE(ss->vemap);
+  MEM_SAFE_FREE(ss->vemap_mem);
+
   MEM_SAFE_FREE(ss->persistent_base);
 
   MEM_SAFE_FREE(ss->preview_vert_index_list);
@@ -1471,6 +1477,13 @@ void BKE_sculptsession_free(Object *ob)
 
     MEM_SAFE_FREE(ss->pmap);
     MEM_SAFE_FREE(ss->pmap_mem);
+
+    MEM_SAFE_FREE(ss->epmap);
+    MEM_SAFE_FREE(ss->epmap_mem);
+
+    MEM_SAFE_FREE(ss->vemap);
+    MEM_SAFE_FREE(ss->vemap_mem);
+
     if (ss->bm_log) {
       BM_log_free(ss->bm_log);
     }

source/blender/editors/sculpt_paint/CMakeLists.txt

@@ -61,10 +61,12 @@ set(SRC
   sculpt_cloth.c
   sculpt_detail.c
   sculpt_dyntopo.c
+  sculpt_expand.c
   sculpt_face_set.c
   sculpt_filter_color.c
   sculpt_filter_mask.c
   sculpt_filter_mesh.c
+  sculpt_geodesic.c
   sculpt_mask_expand.c
   sculpt_multiplane_scrape.c
   sculpt_paint_color.c

source/blender/editors/sculpt_paint/paint_cursor.c

@@ -1626,6 +1626,16 @@ static void paint_cursor_draw_3d_view_brush_cursor_inactive(PaintCursorContext *
     paint_cursor_pose_brush_origins_draw(pcontext);
   }
 
+  /* Expand operation origin. */
+  if (pcontext->ss->expand_cache) {
+    cursor_draw_point_screen_space(
+        pcontext->pos,
+        pcontext->region,
+        SCULPT_vertex_co_get(pcontext->ss, pcontext->ss->expand_cache->initial_active_vertex),
+        pcontext->vc.obact->obmat,
+        2);
+  }
+
   if (brush->sculpt_tool == SCULPT_TOOL_BOUNDARY) {
     paint_cursor_preview_boundary_data_update(pcontext, update_previews);
     paint_cursor_preview_boundary_data_pivot_draw(pcontext);

source/blender/editors/sculpt_paint/paint_ops.c

@@ -1393,4 +1393,7 @@ void ED_keymap_paint(wmKeyConfig *keyconf)
   /* paint stroke */
   keymap = paint_stroke_modal_keymap(keyconf);
   WM_modalkeymap_assign(keymap, "SCULPT_OT_brush_stroke");
+
+  /* sculpt expand. */
+  sculpt_expand_modal_keymap(keyconf);
 }

source/blender/editors/sculpt_paint/sculpt.c

@@ -1103,6 +1103,12 @@ void SCULPT_floodfill_add_initial(SculptFloodFill *flood, int index)
   BLI_gsqueue_push(flood->queue, &index);
 }
 
+void SCULPT_floodfill_add_and_skip_initial(SculptFloodFill *flood, int index)
+{
+  BLI_gsqueue_push(flood->queue, &index);
+  BLI_BITMAP_ENABLE(flood->visited_vertices, index);
+}
+
 void SCULPT_floodfill_add_initial_with_symmetry(
     Sculpt *sd, Object *ob, SculptSession *ss, SculptFloodFill *flood, int index, float radius)
 {
@@ -9006,7 +9012,7 @@ static bool SCULPT_connected_components_floodfill_cb(
   return true;
 }
 
-static void sculpt_connected_components_ensure(Object *ob)
+void SCULPT_connected_components_ensure(Object *ob)
 {
   SculptSession *ss = ob->sculpt;
 
@@ -9081,7 +9087,7 @@ void SCULPT_fake_neighbors_ensure(Sculpt *sd, Object *ob, const float max_dist)
     return;
   }
 
-  sculpt_connected_components_ensure(ob);
+  SCULPT_connected_components_ensure(ob);
   SCULPT_fake_neighbor_init(ss, max_dist);
 
   for (int i = 0; i < totvert; i++) {
@@ -9790,4 +9796,6 @@ void ED_operatortypes_sculpt(void)
   WM_operatortype_append(SCULPT_OT_color_filter);
   WM_operatortype_append(SCULPT_OT_mask_by_color);
   WM_operatortype_append(SCULPT_OT_dyntopo_detail_size_edit);
+
+  WM_operatortype_append(SCULPT_OT_expand);
 }

source/blender/editors/sculpt_paint/sculpt_boundary.c

@@ -518,11 +518,13 @@ SculptBoundary *SCULPT_boundary_data_init(Object *object,
 
   SculptBoundary *boundary = MEM_callocN(sizeof(SculptBoundary), "Boundary edit data");
 
-  const bool init_boundary_distances = brush->boundary_falloff_type !=
-                                       BRUSH_BOUNDARY_FALLOFF_CONSTANT;
+  const bool init_boundary_distances = brush ? brush->boundary_falloff_type !=
+                                                   BRUSH_BOUNDARY_FALLOFF_CONSTANT :
+                                               false;
+
   sculpt_boundary_indices_init(ss, boundary, init_boundary_distances, boundary_initial_vertex);
 
-  const float boundary_radius = radius * (1.0f + brush->boundary_offset);
+  const float boundary_radius = brush ? radius * (1.0f + brush->boundary_offset) : radius;
   sculpt_boundary_edit_data_init(ss, boundary, boundary_initial_vertex, boundary_radius);
 
   return boundary;

source/blender/editors/sculpt_paint/sculpt_geodesic.c

@@ -0,0 +1,360 @@
+/*
+ * This program is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU General Public License
+ * as published by the Free Software Foundation; either version 2
+ * of the License, or (at your option) any later version.
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, write to the Free Software Foundation,
+ * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
+ *
+ * The Original Code is Copyright (C) 2020 Blender Foundation.
+ * All rights reserved.
+ */
+
+/** \file
+ * \ingroup edsculpt
+ */
+
+#include "MEM_guardedalloc.h"
+
+#include "BLI_blenlib.h"
+#include "BLI_linklist_stack.h"
+#include "BLI_math.h"
+#include "BLI_task.h"
+
+#include "BLT_translation.h"
+
+#include "DNA_brush_types.h"
+#include "DNA_mesh_types.h"
+#include "DNA_meshdata_types.h"
+#include "DNA_object_types.h"
+
+#include "BKE_brush.h"
+#include "BKE_ccg.h"
+#include "BKE_colortools.h"
+#include "BKE_context.h"
+#include "BKE_image.h"
+#include "BKE_mesh.h"
+#include "BKE_mesh_mapping.h"
+#include "BKE_multires.h"
+#include "BKE_node.h"
+#include "BKE_object.h"
+#include "BKE_paint.h"
+#include "BKE_pbvh.h"
+#include "BKE_scene.h"
+#include "BKE_subdiv_ccg.h"
+
+#include "DEG_depsgraph.h"
+
+#include "WM_api.h"
+#include "WM_message.h"
+#include "WM_toolsystem.h"
+#include "WM_types.h"
+
+#include "RNA_access.h"
+#include "RNA_define.h"
+
+#include "ED_object.h"
+#include "ED_screen.h"
+#include "ED_sculpt.h"
+#include "ED_view3d.h"
+#include "paint_intern.h"
+#include "sculpt_intern.h"
+
+#include "IMB_colormanagement.h"
+#include "IMB_imbuf.h"
+
+#include "bmesh.h"
+
+#include <math.h>
+#include <stdlib.h>
+#define SCULPT_GEODESIC_VERTEX_NONE -1
+
+/* Propagate distance from v1 and v2 to v0. */
+static bool sculpt_geodesic_mesh_test_dist_add(
+    MVert *mvert, const int v0, const int v1, const int v2, float *dists, GSet *initial_vertices)
+{
+  if (BLI_gset_haskey(initial_vertices, POINTER_FROM_INT(v0))) {
+    return false;
+  }
+
+  BLI_assert(dists[v1] != FLT_MAX);
+  if (dists[v0] <= dists[v1]) {
+    return false;
+  }
+
+  float dist0;
+  if (v2 != SCULPT_GEODESIC_VERTEX_NONE) {
+    BLI_assert(dists[v2] != FLT_MAX);
+    if (dists[v0] <= dists[v2]) {
+      return false;
+    }
+    dist0 = geodesic_distance_propagate_across_triangle(
+        mvert[v0].co, mvert[v1].co, mvert[v2].co, dists[v1], dists[v2]);
+  }
+  else {
+    float vec[3];
+    sub_v3_v3v3(vec, mvert[v1].co, mvert[v0].co);
+    dist0 = dists[v1] + len_v3(vec);
+  }
+
+  if (dist0 < dists[v0]) {
+    dists[v0] = dist0;
+    return true;
+  }
+
+  return false;
+}
+
+static float *SCULPT_geodesic_mesh_create(Object *ob,
+                                          GSet *initial_vertices,
+                                          const float limit_radius)
+{
+  SculptSession *ss = ob->sculpt;
+  Mesh *mesh = BKE_object_get_original_mesh(ob);
+
+  const int totvert = mesh->totvert;
+  const int totedge = mesh->totedge;
+
+  const float limit_radius_sq = limit_radius * limit_radius;
+
+  MEdge *edges = mesh->medge;
+  MVert *verts = SCULPT_mesh_deformed_mverts_get(ss);
+
+  float *dists = MEM_malloc_arrayN(totvert, sizeof(float), "distances");
+  BLI_bitmap *edge_tag = BLI_BITMAP_NEW(totedge, "edge tag");
+
+  if (!ss->epmap) {
+    BKE_mesh_edge_poly_map_create(&ss->epmap,
+                                  &ss->epmap_mem,
+                                  mesh->medge,
+                                  mesh->totedge,
+                                  mesh->mpoly,
+                                  mesh->totpoly,
+                                  mesh->mloop,
+                                  mesh->totloop);
+  }
+  if (!ss->vemap) {
+    BKE_mesh_vert_edge_map_create(
+        &ss->vemap, &ss->vemap_mem, mesh->medge, mesh->totvert, mesh->totedge);
+  }
+
+  /* Both contain edge indices encoded as *void. */
+  BLI_LINKSTACK_DECLARE(queue, void *);
+  BLI_LINKSTACK_DECLARE(queue_next, void *);
+
+  BLI_LINKSTACK_INIT(queue);
+  BLI_LINKSTACK_INIT(queue_next);
+
+  for (int i = 0; i < totvert; i++) {
+    if (BLI_gset_haskey(initial_vertices, POINTER_FROM_INT(i))) {
+      dists[i] = 0.0f;
+    }
+    else {
+      dists[i] = FLT_MAX;
+    }
+  }
+
+  /* Masks vertices that are further than limit radius from an initial vertex. As there is no need
+   * to define a distance to them the algorithm can stop earlier by skipping them. */
+  BLI_bitmap *affected_vertex = BLI_BITMAP_NEW(totvert, "affected vertex");
+  GSetIterator gs_iter;
+
+  if (limit_radius == FLT_MAX) {
+    /* In this case, no need to loop through all initial vertices to check distances as they are
+     * all going to be affected. */
+    BLI_bitmap_set_all(affected_vertex, true, totvert);
+  }
+  else {
+    /* This is an O(n^2) loop used to limit the geodesic distance calculation to a radius. When
+     * this optimization is needed, it is expected for the tool to request the distance to a low
+     * number of vertices (usually just 1 or 2). */
+    GSET_ITER (gs_iter, initial_vertices) {
+      const int v = POINTER_AS_INT(BLI_gsetIterator_getKey(&gs_iter));
+      float *v_co = verts[v].co;
+      for (int i = 0; i < totvert; i++) {
+        if (len_squared_v3v3(v_co, verts[i].co) <= limit_radius_sq) {
+          BLI_BITMAP_ENABLE(affected_vertex, i);
+        }
+      }
+    }
+  }
+
+  /* Add edges adjacent to an initial vertex to the queue. */
+  for (int i = 0; i < totedge; i++) {
+    const int v1 = edges[i].v1;
+    const int v2 = edges[i].v2;
+    if (!BLI_BITMAP_TEST(affected_vertex, v1) && !BLI_BITMAP_TEST(affected_vertex, v2)) {
+      continue;
+    }
+    if (dists[v1] != FLT_MAX || dists[v2] != FLT_MAX) {
+      BLI_LINKSTACK_PUSH(queue, POINTER_FROM_INT(i));
+    }
+  }
+
+  do {
+    while (BLI_LINKSTACK_SIZE(queue)) {
+      const int e = POINTER_AS_INT(BLI_LINKSTACK_POP(queue));
+      int v1 = edges[e].v1;
+      int v2 = edges[e].v2;
+
+      if (dists[v1] == FLT_MAX || dists[v2] == FLT_MAX) {
+        if (dists[v1] > dists[v2]) {
+          SWAP(int, v1, v2);
+        }
+        sculpt_geodesic_mesh_test_dist_add(
+            verts, v2, v1, SCULPT_GEODESIC_VERTEX_NONE, dists, initial_vertices);
+      }
+
+      if (ss->epmap[e].count != 0) {
+        for (int poly_map_index = 0; poly_map_index < ss->epmap[e].count; poly_map_index++) {
+          const int poly = ss->epmap[e].indices[poly_map_index];
+          if (ss->face_sets[poly] <= 0) {
+            continue;
+          }
+          const MPoly *mpoly = &mesh->mpoly[poly];
+
+          for (int loop_index = 0; loop_index < mpoly->totloop; loop_index++) {
+            const MLoop *mloop = &mesh->mloop[loop_index + mpoly->loopstart];
+            const int v_other = mloop->v;
+            if (ELEM(v_other, v1, v2)) {
+              continue;
+            }
+            if (sculpt_geodesic_mesh_test_dist_add(
+                    verts, v_other, v1, v2, dists, initial_vertices)) {
+              for (int edge_map_index = 0; edge_map_index < ss->vemap[v_other].count;
+                   edge_map_index++) {
+                const int e_other = ss->vemap[v_other].indices[edge_map_index];
+                int ev_other;
+                if (edges[e_other].v1 == (uint)v_other) {
+                  ev_other = edges[e_other].v2;
+                }
+                else {
+                  ev_other = edges[e_other].v1;
+                }
+
+                if (e_other != e && !BLI_BITMAP_TEST(edge_tag, e_other) &&
+                    (ss->epmap[e_other].count == 0 || dists[ev_other] != FLT_MAX)) {
+                  if (BLI_BITMAP_TEST(affected_vertex, v_other) ||
+                      BLI_BITMAP_TEST(affected_vertex, ev_other)) {
+                    BLI_BITMAP_ENABLE(edge_tag, e_other);
+                    BLI_LINKSTACK_PUSH(queue_next, POINTER_FROM_INT(e_other));
+                  }
+                }
+              }
+            }
+          }
+        }
+      }
+    }
+
+    for (LinkNode *lnk = queue_next; lnk; lnk = lnk->next) {
+      const int e = POINTER_AS_INT(lnk->link);
+      BLI_BITMAP_DISABLE(edge_tag, e);
+    }
+
+    BLI_LINKSTACK_SWAP(queue, queue_next);
+
+  } while (BLI_LINKSTACK_SIZE(queue));
+
+  BLI_LINKSTACK_FREE(queue);
+  BLI_LINKSTACK_FREE(queue_next);
+  MEM_SAFE_FREE(edge_tag);
+  MEM_SAFE_FREE(affected_vertex);
+
+  return dists;
+}
+
+/* For sculpt mesh data that does not support a geodesic distances algorithm, fallback to the
+ * distance to each vertex. In this case, only one of the initial vertices will be used to
+ * calculate the distance. */
+static float *SCULPT_geodesic_fallback_create(Object *ob, GSet *initial_vertices)
+{
+
+  SculptSession *ss = ob->sculpt;
+  Mesh *mesh = BKE_object_get_original_mesh(ob);
+  const int totvert = mesh->totvert;
+  float *dists = MEM_malloc_arrayN(totvert, sizeof(float), "distances");
+  int first_affected = SCULPT_GEODESIC_VERTEX_NONE;
+  GSetIterator gs_iter;
+  GSET_ITER (gs_iter, initial_vertices) {
+    first_affected = POINTER_AS_INT(BLI_gsetIterator_getKey(&gs_iter));
+    break;
+  }
+
+  if (first_affected == SCULPT_GEODESIC_VERTEX_NONE) {
+    for (int i = 0; i < totvert; i++) {
+      dists[i] = FLT_MAX;
+    }
+    return dists;
+  }
+
+  const float *first_affected_co = SCULPT_vertex_co_get(ss, first_affected);
+  for (int i = 0; i < totvert; i++) {
+    dists[i] = len_v3v3(first_affected_co, SCULPT_vertex_co_get(ss, i));
+  }
+
+  return dists;
+}
+
+float *SCULPT_geodesic_distances_create(Object *ob,
+                                        GSet *initial_vertices,
+                                        const float limit_radius)
+{
+  SculptSession *ss = ob->sculpt;
+  switch (BKE_pbvh_type(ss->pbvh)) {
+    case PBVH_FACES:
+      return SCULPT_geodesic_mesh_create(ob, initial_vertices, limit_radius);
+    case PBVH_BMESH:
+    case PBVH_GRIDS:
+      return SCULPT_geodesic_fallback_create(ob, initial_vertices);
+  }
+  BLI_assert(false);
+  return NULL;
+}
+
+float *SCULPT_geodesic_from_vertex_and_symm(Sculpt *sd,
+                                            Object *ob,
+                                            const int vertex,
+                                            const float limit_radius)
+{
+  SculptSession *ss = ob->sculpt;
+  GSet *initial_vertices = BLI_gset_int_new("initial_vertices");
+
+  const char symm = SCULPT_mesh_symmetry_xyz_get(ob);
+  for (char i = 0; i <= symm; ++i) {
+    if (SCULPT_is_symmetry_iteration_valid(i, symm)) {
+      int v = -1;
+      if (i == 0) {
+        v = vertex;
+      }
+      else {
+        float location[3];
+        flip_v3_v3(location, SCULPT_vertex_co_get(ss, vertex), i);
+        v = SCULPT_nearest_vertex_get(sd, ob, location, FLT_MAX, false);
+      }
+      if (v != -1) {
+        BLI_gset_add(initial_vertices, POINTER_FROM_INT(v));
+      }
+    }
+  }
+
+  float *dists = SCULPT_geodesic_distances_create(ob, initial_vertices, limit_radius);
+  BLI_gset_free(initial_vertices, NULL);
+  return dists;
+}
+
+float *SCULPT_geodesic_from_vertex(Object *ob, const int vertex, const float limit_radius)
+{
+  GSet *initial_vertices = BLI_gset_int_new("initial_vertices");
+  BLI_gset_add(initial_vertices, POINTER_FROM_INT(vertex));
+  float *dists = SCULPT_geodesic_distances_create(ob, initial_vertices, limit_radius);
+  BLI_gset_free(initial_vertices, NULL);
+  return dists;
+}

source/blender/editors/sculpt_paint/sculpt_intern.h

@@ -187,6 +187,8 @@ void SCULPT_boundary_info_ensure(Object *object);
 /* Boundary Info needs to be initialized in order to use this function. */
 bool SCULPT_vertex_is_boundary(const SculptSession *ss, const int index);
 
+void SCULPT_connected_components_ensure(Object *ob);
+
 /* Sculpt Visibility API */
 
 void SCULPT_vertex_visible_set(SculptSession *ss, int index, bool visible);
@@ -300,6 +302,7 @@ void SCULPT_floodfill_add_initial_with_symmetry(struct Sculpt *sd,
                                                 int index,
                                                 float radius);
 void SCULPT_floodfill_add_initial(SculptFloodFill *flood, int index);
+void SCULPT_floodfill_add_and_skip_initial(SculptFloodFill *flood, int index);
 void SCULPT_floodfill_execute(
     struct SculptSession *ss,
     SculptFloodFill *flood,
@@ -361,6 +364,21 @@ float *SCULPT_boundary_automasking_init(Object *ob,
                                         int propagation_steps,
                                         float *automask_factor);
 
+/* Geodesic distances. */
+
+/* Returns an array indexed by vertex index containing the geodesic distance to the closest vertex
+in the initial vertex set. The caller is responsible for freeing the array.
+Geodesic distances will only work when used with PBVH_FACES, for other types of PBVH it will
+fallback to euclidean distances to one of the initial vertices in the set. */
+float *SCULPT_geodesic_distances_create(struct Object *ob,
+                                        struct GSet *initial_vertices,
+                                        const float limit_radius);
+float *SCULPT_geodesic_from_vertex_and_symm(struct Sculpt *sd,
+                                            struct Object *ob,
+                                            const int vertex,
+                                            const float limit_radius);
+float *SCULPT_geodesic_from_vertex(Object *ob, const int vertex, const float limit_radius);
+
 /* Filters. */
 void SCULPT_filter_cache_init(struct bContext *C, Object *ob, Sculpt *sd, const int undo_type);
 void SCULPT_filter_cache_free(SculptSession *ss);
@@ -1066,6 +1084,155 @@ void SCULPT_filter_to_orientation_space(float r_v[3], struct FilterCache *filter
 void SCULPT_filter_to_object_space(float r_v[3], struct FilterCache *filter_cache);
 void SCULPT_filter_zero_disabled_axis_components(float r_v[3], struct FilterCache *filter_cache);
 
+/* Sculpt Expand. */
+typedef enum eSculptExpandFalloffType {
+  SCULPT_EXPAND_FALLOFF_GEODESIC,
+  SCULPT_EXPAND_FALLOFF_TOPOLOGY,
+  SCULPT_EXPAND_FALLOFF_TOPOLOGY_DIAGONALS,
+  SCULPT_EXPAND_FALLOFF_NORMALS,
+  SCULPT_EXPAND_FALLOFF_SPHERICAL,
+  SCULPT_EXPAND_FALLOFF_BOUNDARY_TOPOLOGY,
+  SCULPT_EXPAND_FALLOFF_BOUNDARY_FACE_SET,
+  SCULPT_EXPAND_FALLOFF_ACTIVE_FACE_SET,
+} eSculptExpandFalloffType;
+
+typedef enum eSculptExpandTargetType {
+  SCULPT_EXPAND_TARGET_MASK,
+  SCULPT_EXPAND_TARGET_FACE_SETS,
+  SCULPT_EXPAND_TARGET_COLORS,
+} eSculptExpandTargetType;
+
+typedef enum eSculptExpandRecursionType {
+  SCULPT_EXPAND_RECURSION_TOPOLOGY,
+  SCULPT_EXPAND_RECURSION_GEODESICS,
+} eSculptExpandRecursionType;
+
+#define EXPAND_SYMM_AREAS 8
+
+typedef struct ExpandCache {
+  /* Target data elements that the expand operation will affect. */
+  eSculptExpandTargetType target;
+
+  /* Falloff data. */
+  eSculptExpandFalloffType falloff_type;
+
+  /* Indexed by vertex index, precalculated falloff value of that vertex (without any falloff
+   * editing modification applied). */
+  float *vert_falloff;
+  /* Max falloff value in *vert_falloff. */
+  float max_vert_falloff;
+
+  /* Indexed by base mesh poly index, precalculated falloff value of that face. These values are
+   * calculated from the per vertex falloff (*vert_falloff) when needed. */
+  float *face_falloff;
+  float max_face_falloff;
+
+  /* Falloff value of the active element (vertex or base mesh face) that Expand will expand to. */
+  float active_falloff;
+
+  /* When set to true, expand skips all falloff computations and considers all elements as enabled.
+   */
+  bool all_enabled;
+
+  /* Initial mouse and cursor data from where the current falloff started. This data can be changed
+   * during the execution of Expand by moving the origin. */
+  float initial_mouse_move[2];
+  float initial_mouse[2];
+  int initial_active_vertex;
+  int initial_active_face_set;
+
+  /* Maximum number of vertices allowed in the SculptSession for previewing the falloff using
+   * geodesic distances. */
+  int max_geodesic_move_preview;
+
+  /* Original falloff type before starting the move operation. */
+  eSculptExpandFalloffType move_original_falloff_type;
+  /* Falloff type using when moving the origin for preview. */
+  eSculptExpandFalloffType move_preview_falloff_type;
+
+  /* Face set ID that is going to be used when creating a new Face Set. */
+  int next_face_set;
+
+  /* Face Set ID of the Face set selected for editing. */
+  int update_face_set;
+
+  /* Mouse position since the last time the origin was moved. Used for reference when moving the
+   * initial position of Expand. */
+  float original_mouse_move[2];
+
+  /* Active components checks. */
+  /* Indexed by symmetry pass index, contains the connected component ID found in
+   * SculptSession->vertex_info.connected_component. Other connected components not found in this
+   * array will be ignored by Expand. */
+  int active_connected_components[EXPAND_SYMM_AREAS];
+
+  /* Snapping. */
+  /* GSet containing all Face Sets IDs that Expand will use to snap the new data. */
+  GSet *snap_enabled_face_sets;
+
+  /* Texture distortion data. */
+  Brush *brush;
+  struct Scene *scene;
+  struct MTex *mtex;
+
+  /* Controls how much texture distortion will be applied to the current falloff */
+  float texture_distortion_strength;
+
+  /* Cached PBVH nodes. This allows to skip gathering all nodes from the PBVH each time expand
+   * needs to update the state of the elements. */
+  PBVHNode **nodes;
+  int totnode;
+
+  /* Expand state options. */
+
+  /* Number of loops (times that the falloff is going to be repeated). */
+  int loop_count;
+
+  /* Invert the falloff result. */
+  bool invert;
+
+  /* When set to true, preserves the previous state of the data and adds the new one on top. */
+  bool preserve;
+
+  /* When set to true, the mask or colors will be applied as a gradient. */
+  bool falloff_gradient;
+
+  /* When set to true, Expand will use the Brush falloff curve data to shape the gradient. */
+  bool brush_gradient;
+
+  /* When set to true, Expand will move the origin (initial active vertex and cursor position)
+   * instead of updating the active vertex and active falloff. */
+  bool move;
+
+  /* When set to true, Expand will snap the new data to the Face Sets IDs found in
+   * *original_face_sets. */
+  bool snap;
+
+  /* When set to true, Expand will use the current Face Set ID to modify an existing Face Set
+   * instead of creating a new one. */
+  bool modify_active_face_set;
+
+  /* When set to true, Expand will reposition the sculpt pivot to the boundary of the expand result
+   * after finishing the operation. */
+  bool reposition_pivot;
+
+  /* Color target data type related data. */
+  float fill_color[4];
+  short blend_mode;
+
+  /* Face Sets at the first step of the expand operation, before starting modifying the active
+   * vertex and active falloff. These are not the original Face Sets of the sculpt before starting
+   * the operator as they could have been modified by Expand when initializing the operator and
+   * before starting changing the active vertex. These Face Sets are used for restoring and
+   * checking the Face Sets state while the Expand operation modal runs. */
+  int *initial_face_sets;
+
+  /* Original data of the sculpt as it was before running the Expand operator. */
+  float *original_mask;
+  int *original_face_sets;
+  float (*original_colors)[4];
+} ExpandCache;
+
 typedef struct FilterCache {
   bool enabled_axis[3];
   bool enabled_force_axis[3];
@@ -1150,6 +1317,10 @@ bool SCULPT_get_redraw_rect(struct ARegion *region,
 
 /* Operators. */
 
+/* Expand. */
+void SCULPT_OT_expand(struct wmOperatorType *ot);
+void sculpt_expand_modal_keymap(struct wmKeyConfig *keyconf);
+
 /* Gestures. */
 void SCULPT_OT_face_set_lasso_gesture(struct wmOperatorType *ot);
 void SCULPT_OT_face_set_box_gesture(struct wmOperatorType *ot);