Sculpt: Fair Face Sets operation for Face Set Edit

This implements a mesh fairing algorithm and implements the fair
operations for Face Set edit. This edit operations create a smooth as
possible geometry patch in the area of the selected Face Set.

The mesh fairing algorithm is designed by Brett Fedack for the addon
"Mesh Fairing": https://github.com/fedackb/mesh-fairing, with some
modifications:

- The main fairing function in BKE_mesh_fair.h does not triangulate
 the mesh. For the test I did in sculpt mode results are good enough
 without triangulating the topology. Depending on the use and the
 result quality needed for a particular tool, the mesh can be
 triangulate in the affected area before starting fairing.

- Cotangents loop weights are not implemented yet. The idea is to
also expose the vertex and loop weights in a different function in
 case a tool needs to set up custom weights.

This algorithm will also be used to solve the limitations of line
project and implement the Lasso Project and Polyline Project tools.
It can also be used in tools in other areas of Blender, like Edit Mode
or future retopology tools.

Reviewed By: brecht

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

2 files changed, 91 insertions, 1 deletions

diff --git a/source/blender/editors/sculpt_paint/CMakeLists.txt b/source/blender/editors/sculpt_paint/CMakeLists.txt
index 9bf3d2610d8..fff8d27ef5b 100644
--- a/source/blender/editors/sculpt_paint/CMakeLists.txt
+++ b/source/blender/editors/sculpt_paint/CMakeLists.txt
@@ -32,6 +32,7 @@ set(INC
   ../../windowmanager
   ../../../../intern/atomic
   ../../../../intern/clog
+  ../../../../intern/eigen
   ../../../../intern/glew-mx
   ../../../../intern/guardedalloc
 )
diff --git a/source/blender/editors/sculpt_paint/sculpt_face_set.c b/source/blender/editors/sculpt_paint/sculpt_face_set.c
index ad42750bb92..1fba958d695 100644
--- a/source/blender/editors/sculpt_paint/sculpt_face_set.c
+++ b/source/blender/editors/sculpt_paint/sculpt_face_set.c
@@ -41,6 +41,7 @@
 #include "BKE_context.h"
 #include "BKE_customdata.h"
 #include "BKE_mesh.h"
+#include "BKE_mesh_fair.h"
 #include "BKE_mesh_mapping.h"
 #include "BKE_multires.h"
 #include "BKE_node.h"
@@ -1024,6 +1025,8 @@ typedef enum eSculptFaceSetEditMode {
   SCULPT_FACE_SET_EDIT_GROW = 0,
   SCULPT_FACE_SET_EDIT_SHRINK = 1,
   SCULPT_FACE_SET_EDIT_DELETE_GEOMETRY = 2,
+  SCULPT_FACE_SET_EDIT_FAIR_POSITIONS = 3,
+  SCULPT_FACE_SET_EDIT_FAIR_TANGENCY = 4,
 } eSculptFaceSetEditMode;
 
 static EnumPropertyItem prop_sculpt_face_sets_edit_types[] = {
@@ -1048,6 +1051,22 @@ static EnumPropertyItem prop_sculpt_face_sets_edit_types[] = {
         "Delete Geometry",
         "Deletes the faces that are assigned to the Face Set",
     },
+    {
+        SCULPT_FACE_SET_EDIT_FAIR_POSITIONS,
+        "FAIR_POSITIONS",
+        0,
+        "Fair Positions",
+        "Creates a smooth as possible geometry patch from the Face Set minimizing changes in "
+        "vertex positions",
+    },
+    {
+        SCULPT_FACE_SET_EDIT_FAIR_TANGENCY,
+        "FAIR_TANGENCY",
+        0,
+        "Fair Tangency",
+        "Creates a smooth as possible geometry patch from the Face Set minimizing changes in "
+        "vertex tangents",
+    },
     {0, NULL, 0, NULL, NULL},
 };
 
@@ -1181,6 +1200,29 @@ static void sculpt_face_set_delete_geometry(Object *ob,
   BM_mesh_free(bm);
 }
 
+static void sculpt_face_set_edit_fair_face_set(Object *ob,
+                                               const int active_face_set_id,
+                                               const int fair_order)
+{
+  SculptSession *ss = ob->sculpt;
+  const int totvert = SCULPT_vertex_count_get(ss);
+
+  Mesh *mesh = ob->data;
+  bool *fair_vertices = MEM_malloc_arrayN(sizeof(bool), totvert, "fair vertices");
+
+  SCULPT_boundary_info_ensure(ob);
+
+  for (int i = 0; i < totvert; i++) {
+    fair_vertices[i] = !SCULPT_vertex_is_boundary(ss, i) &&
+                       SCULPT_vertex_has_face_set(ss, i, active_face_set_id) &&
+                       SCULPT_vertex_has_unique_face_set(ss, i);
+  }
+
+  MVert *mvert = SCULPT_mesh_deformed_mverts_get(ss);
+  BKE_mesh_prefair_and_fair_vertices(mesh, mvert, fair_vertices, fair_order);
+  MEM_freeN(fair_vertices);
+}
+
 static void sculpt_face_set_apply_edit(Object *ob,
                                        const int active_face_set_id,
                                        const int mode,
@@ -1204,6 +1246,12 @@ static void sculpt_face_set_apply_edit(Object *ob,
     case SCULPT_FACE_SET_EDIT_DELETE_GEOMETRY:
       sculpt_face_set_delete_geometry(ob, ss, active_face_set_id, modify_hidden);
       break;
+    case SCULPT_FACE_SET_EDIT_FAIR_POSITIONS:
+      sculpt_face_set_edit_fair_face_set(ob, active_face_set_id, MESH_FAIRING_DEPTH_POSITION);
+      break;
+    case SCULPT_FACE_SET_EDIT_FAIR_TANGENCY:
+      sculpt_face_set_edit_fair_face_set(ob, active_face_set_id, MESH_FAIRING_DEPTH_TANGENCY);
+      break;
   }
 }
 
@@ -1230,6 +1278,16 @@ static bool sculpt_face_set_edit_is_operation_valid(SculptSession *ss,
       return false;
     }
   }
+
+  if (ELEM(mode, SCULPT_FACE_SET_EDIT_FAIR_POSITIONS, SCULPT_FACE_SET_EDIT_FAIR_TANGENCY)) {
+    if (BKE_pbvh_type(ss->pbvh) == PBVH_GRIDS) {
+      /* TODO: Multires topology representation using grids and duplicates can't be used directly
+       * by the fair algorithm. Multires topology needs to be exposed in a different way or
+       * converted to a mesh for this operation. */
+      return false;
+    }
+  }
+
   return true;
 }
 
@@ -1287,11 +1345,38 @@ static void sculpt_face_set_edit_modify_face_sets(Object *ob,
   MEM_freeN(nodes);
 }
 
+static void sculpt_face_set_edit_modify_coordinates(bContext *C,
+                                                    Object *ob,
+                                                    const int active_face_set,
+                                                    const eSculptFaceSetEditMode mode)
+{
+  Sculpt *sd = CTX_data_tool_settings(C)->sculpt;
+  SculptSession *ss = ob->sculpt;
+  PBVH *pbvh = ss->pbvh;
+  PBVHNode **nodes;
+  int totnode;
+  BKE_pbvh_search_gather(pbvh, NULL, NULL, &nodes, &totnode);
+  SCULPT_undo_push_begin(ob, "face set edit");
+  for (int i = 0; i < totnode; i++) {
+    BKE_pbvh_node_mark_update(nodes[i]);
+    SCULPT_undo_push_node(ob, nodes[i], SCULPT_UNDO_COORDS);
+  }
+  sculpt_face_set_apply_edit(ob, abs(active_face_set), mode, false);
+
+  if (ss->deform_modifiers_active || ss->shapekey_active) {
+    SCULPT_flush_stroke_deform(sd, ob, true);
+  }
+  SCULPT_flush_update_step(C, SCULPT_UPDATE_COORDS);
+  SCULPT_flush_update_done(C, ob, SCULPT_UPDATE_COORDS);
+  SCULPT_undo_push_end();
+  MEM_freeN(nodes);
+}
+
 static int sculpt_face_set_edit_invoke(bContext *C, wmOperator *op, const wmEvent *event)
 {
   Object *ob = CTX_data_active_object(C);
   SculptSession *ss = ob->sculpt;
-  Depsgraph *depsgraph = CTX_data_depsgraph_pointer(C);
+  Depsgraph *depsgraph = CTX_data_ensure_evaluated_depsgraph(C);
 
   const int mode = RNA_enum_get(op->ptr, "mode");
   const bool modify_hidden = RNA_boolean_get(op->ptr, "modify_hidden");
@@ -1320,6 +1405,10 @@ static int sculpt_face_set_edit_invoke(bContext *C, wmOperator *op, const wmEven
     case SCULPT_FACE_SET_EDIT_SHRINK:
       sculpt_face_set_edit_modify_face_sets(ob, active_face_set, mode, modify_hidden);
       break;
+    case SCULPT_FACE_SET_EDIT_FAIR_POSITIONS:
+    case SCULPT_FACE_SET_EDIT_FAIR_TANGENCY:
+      sculpt_face_set_edit_modify_coordinates(C, ob, active_face_set, mode);
+      break;
   }
 
   SCULPT_tag_update_overlays(C);