Page MenuHome

Sculpt: Fair Face Sets operation for Face Set Edit
ClosedPublic

Authored by Pablo Dobarro (pablodp606) on Nov 19 2020, 1:41 PM.
Tags
None
Tokens
"100" token, awarded by Frozen_Death_Knight."Love" token, awarded by MetinSeven."Love" token, awarded by gilberto_rodrigues."Love" token, awarded by Brandon777."Love" token, awarded by kursadk."Like" token, awarded by rpserge."Orange Medal" token, awarded by Jules."Love" token, awarded by RedMser.

Details

Summary

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 expose also the vertex and loop weights in a different function in case a tool needs to set up custom weights.

The algorithm was implemented using BMesh as it was the most
straightforward way to implement it and it can be directly use by Edit
Mode tools. It should also be possible to implement it for Mesh in case
the Mesh -> BMesh conversions adds too much overhead for a particular
tool. How to implement this for multires is still not clear to me. I
have also planned to implement a simpler version of it based on the
Sculpt API in cases were speed is more important than the quality of the
surface.

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.

Diff Detail

Repository
rB Blender

Event Timeline

Pablo Dobarro (pablodp606) requested review of this revision.Nov 19 2020, 1:41 PM
Pablo Dobarro (pablodp606) created this revision.

I think that another use case would be to have this as a modifier which can very useful for the other modifiers like pre and post shrinkwrap, remesh, armature and softbody/cloth physics.

A very welcome addition to the Sculpt Mode toolset.

Hopefully these options will be available as well:

  1. Position: Change in vertex position is minimized.
  2. Tangency: Change in vertex tangency is minimized.
  3. Curvature: Change in vertex curvature is minimized.

Thanks!

Multires I'd suggest not to worry about at this time.

The non-multires case I would suggest implementing the non-bmesh version of BKE_bmesh_prefair_and_fair_vertices().
We really shouldn't rely on BMesh if we want great performance of sculpting tools.

In that case, should I remove the BMesh version or implement a separate one for Mesh?

I do not see point of removal, it could be handy to also have it as an edit mode tool.
Also, should be possible to reuse fair amount of code by adding some sort of interface which the algorithm will query for the information.

Pablo Dobarro (pablodp606) updated this revision to Diff 31541.EditedDec 2 2020, 7:42 PM
  • Implement Fairing for BMesh and Mesh

About API in general

The issue with the current API declaration in BKE_mesh_fair.h are the following:

  • There is no explanation what the functions do: what is the result in user-measurable terms (without need to read implementation code, or to follow the link to original Python-based implementation).
  • There is no specification about corner cases (can modification happen in-place? Can the "set" of modified vertices be NULL?)
  • The semantic of BMesh and Mesh implementation is different, even the function prototypes are different. Good API will have same behavior, and just the input data type will differ. The rest should stay the same.

On the note about proper implementation abstraction.

In C the best thing you can do is something like this:

typedef struct FairingContext {
  /* Get coordinates of vertices which are adjacent to the loop with specified index.
   * Order of coordinates is <specify whether order is important or can be random>. */
  void (*adjacents_coords_from_loop)(struct FairingContext *context,
                                     const int loop,
                                     float r_adj_a[3],
                                     float r_adj_b[3]);
} FairingContext;

/* Subclass of FairingContext for the Mesh input data type. */
typedef struct MeshFairingContext {
  FairingContext context;

  Mesh *mesh;
} MeshFairingContext;

/* Subclass of FairingContext for the BMesh input data type. */
typedef struct BMeshFairingContext {
  FairingContext context;

  BMesh *bmesh;
} BMeshFairingContext;

static void mesh_adjacents_coords_from_loop_get(FairingContext *context,
                                                const int loop,
                                                float r_adj_a[3],
                                                float r_adj_b[3])
{
  MeshFairingContext *mesh_context = (MeshFairingContext *)context;
  /* The logic to access coordinates of adjacent coordinates. */
}

static void bmesh_adjacents_coords_from_loop_get(FairingContext *context,
                                                 const int loop,
                                                 float r_adj_a[3],
                                                 float r_adj_b[3])
{
  BMeshFairingContext *bmesh_context = (BMeshFairingContext *)context;
  /* The logic to access coordinates of adjacent coordinates. */
}

void BKE_mesh_prefair_and_fair_vertices(struct Mesh *mesh,
                                        struct MVert *deform_mverts,
                                        bool *affected_vertices,
                                        const int order);
{
  MeshFairingContext mesh_context;
  mesh_context.context.adjacents_coords_from_loop = mesh_adjacents_coords_from_loop_get;
  run_main_fairing_logic(&mesh_context.context);
}

void BKE_bmesh_prefair_and_fair_vertices(struct BMesh *bm,
                                         bool *affected_vertices,
                                         const int order)
{
  BMeshFairingContext bmesh_context;
  bmesh_context.context.adjacents_coords_from_loop = bmesh_adjacents_coords_from_loop_get;
  run_main_fairing_logic(&bmesh_context.context);
}

This way there is no data-specific branching in the generic underlying implementation. Any datatype can be supported without modifying the "core". Can even become an external API where anyone can provide callbacks and get weird and wonderful data type supported.

This approach contains static_cast from base to derived, which can not be checked compile-time.

In C++ you can do more compiler-time strict implementation like this:

class FairingContext {
public:
  /* Get coordinates of vertices which are adjacent to the loop with specified index.
  * Order of coordinates is <specify whether order is important or can be random>. */
  virtual void adjacents_coords_from_loop(const int loop, float r_adj_a[3], float r_adj_b[3]) = 0;
};

class MeshFairingContext : public FairingContext {
public:
  explicit MeshFairingContext(Mesh *mesh) : mesh_(mesh)
  {
  }

  virtual void adjacents_coords_from_loop(const int loop,
                                          float r_adj_a[3],
                                          float r_adj_b[3]) override
  {
    /* Get adjacent coordinates using mesh_. */
  }

  void run_main_fairing_logic()
  {
    /* Implementation of algorithm which simply uses adjacents_coords_from_loop(loop, coord_a,
    * coord_b). */
  }

protected:
  Mesh *mesh_;
};

class BMeshFairingContext : public FairingContext {
public:
  explicit MeshFairingContext(Mesh *mesh) : mesh_(mesh)
  {
  }

  virtual void adjacents_coords_from_loop(const int loop,
                                          float r_adj_a[3],
                                          float r_adj_b[3]) override
  {
    /* Get adjacent coordinates using bmesh_. */
  }

protected:
  BMesh *bmesh_;
};

void BKE_mesh_prefair_and_fair_vertices(struct Mesh *mesh,
                                        struct MVert *deform_mverts,
                                        bool *affected_vertices,
                                        const int order);
{
  MeshFairingContext mesh_context(mesh);
  mesh_context.run_main_fairing_logic();
}

void BKE_bmesh_prefair_and_fair_vertices(struct BMesh *bm,
                                        bool *affected_vertices,
                                        const int order)
{
  BMeshFairingContext bmesh_context;
  mesh_context.run_main_fairing_logic();
}

Not only C++ approach is less verbose and more type-safe, it also ensures that all necessary callbacks are specified, at compile time.

For the new code written now I would really strongly advice C++ implementation. Is more clear from implementation, data separation, encapsulation and so on. It also will allow you to use C++ primitives for hash maps, which will reduce the boiler plate code dealing with low-level GHash.

source/blender/blenkernel/BKE_mesh_fair.h
37–38

I don't think this adds much information. It is kind of implied that one chooses Mesh or BMesh funciton depending whether the caller has Mesh or BMesh data structure.

39

There is no deform_verts here. And deform_mverts is not a coordinate.
It also will help implicitly stating whether it is allowed to pass mesh->mvert as deform_mverts (to perform in-place modification, without allocating extra array).

40

Think there is a typo here.
Also, this statement does not decrease level of uncertainty, because what exactly the lack of boundary check implies.

45

Is it indexed by vertex index and denotes whether vertex was moved?
Can it be NULL?

46

What is the order?

source/blender/blenkernel/intern/mesh_fair.c
82–102 ↗(On Diff #31544)

This is not how you abstract implementation.
See the non-inlined comment for details.

Sergey Sharybin (sergey) requested changes to this revision.Dec 3 2020, 10:03 AM
This revision now requires changes to proceed.Dec 3 2020, 10:03 AM
Pablo Dobarro (pablodp606) marked 5 inline comments as done.Dec 3 2020, 8:42 PM
Pablo Dobarro (pablodp606) added inline comments.
source/blender/blenkernel/BKE_mesh_fair.h
46

I'm not sure, this is how it is called in the addon. It is used for the recursion depth when building the matrices. It controls what will be minimized with fairing. When set to 1 it uses positions, 2 uses tangency and 3 uses curvature.

  • Implement mesh fairing in C++

The inlined comment got lost after patch update, so here is a reply to it.

I'm not sure, this is how it is called in the addon. It is used for the recursion depth when building the matrices. It controls what will be minimized with fairing. When set to 1 it uses positions, 2 uses tangency and 3 uses curvature.

Then make it an enum with properly named values than a cryptic 1 and 2 int values.

From the API aspect, there is still missing explanation of what fairing does, and the mesh and bmesh versions still seems to have different semantic related on where deformed vertices are stroed.

From other general notes:

  • BKE_mesh_fair.hh should be BKE_mesh_fair.h because it has C linkage, and is intended for use from C code.
  • Please follow https://wiki.blender.org/wiki/Style_Guide/C_Cpp#Naming namely the "Class data member names" section
  • Use C++ data types from BLI, for example, blender::Map instead of GHash*
  • Use smart pointers and container types to control allocations. For example, stored dynamically allocated array should be managed by blender::Vector instead of manual malloc/free. If there are temporary allocations in functions use unique_ptr.
Brecht Van Lommel (brecht) requested changes to this revision.Dec 11 2020, 6:20 PM

Please include the appropriate license and copyright from the original code. The Original Code is Copyright (C) Blender Foundation. is incorrect.

Overall this implementation could probably be optimized significantly, especially for higher order. An algorithm like the one in meshlaplacian.c where computations are done per triangle and then distributed to vertices is going to be more efficient than computing weights from triangles surrounding vertices. Plus you'd avoid having to build adjacency data structures.

But this is probably ok for now, it can always be optimized.

source/blender/blenkernel/intern/mesh_fair.cc
188

Storage size that grows quadratically with the number of vertices will run out of memory quickly and have poor performance.

The solution is to write values with the EIG_*_add API functions directly, rather than using intermediate A and b for storage.

450

area != 0.0f

463

circuncenter -> circumcenter

source/blender/editors/sculpt_paint/sculpt_face_set.c
1060

trying to minimize ->minimizing

vertices positions -> vertex positions

1068

trying to minimize ->minimizing

vertices tangents -> vertex tangents

This revision now requires changes to proceed.Dec 11 2020, 6:20 PM
Pablo Dobarro (pablodp606) marked 5 inline comments as done.
  • Review update
  • Remove matrix allocation
This revision is now accepted and ready to land.Dec 15 2020, 2:26 PM