Idea of a auto-retopology algorithm

This one is an idea I had for a possible multithreaded bakeable auto-retopology algorithm.

The main goal of this post is for people to try to highlight as many problems as this algorithm can encounter, or point out if there is already another better solution i don't know about :))

The algorithm is explained as pseudo-code with images, as I tried to make it as easy to understand as possible, but there is my personal opinion on the approach too

Notes:

• When I talk about "cubes" i mean voxels; however, I think that way it is easier to visualize even if you don't understand voxels.
• There are three sets of images, the first one has a easy topology on a character's arm, the second one has a more difficult topology on a plane. The last one has a finger-like terrible topology with a gap in it.
• There is no implementation of the algorithm, and the images were made by hand-modeling the interaction of the algorithm to the environment. The results may vary, if i'm in the wrong
• Non-connected edges means there is no direct path through the face that also doesn't go through a seam

#########

ALGORITHM

#########

Make a cube grid along the mesh of the model, the size of them being inverse proportion of vertex density times a constant (resolution chosen by user)

0 < t <= number of threads

Choose t of the cubes, project it to the mesh in a way that you get a single plane (skinwrap modifier-like projection) and (multithread lock) lock them as a in-use resource, assign them to a cube from the grid .

In the first iteration the grid can be moved to match better the first created plane

Now starts a loop that can be multithreaded:
For every edge of the original mesh that intercepts the plane:  get the vector of the edge, and record it. All vectors will be used as to determine were the face/faces should be extruded to

My approach would be to hash the xyz direction of the vector into a hashmap/array of 6 pre-defined groups (+x, -x, +y, -y, +z, -z) and make the arithmetic mean of the vectors that land in each position (And therefore you need to keep track of how many vectors you have stored). This mean, together with the vector of the edge being extruded gives the program where to place the new edge. Also, if there is too much difference between two oposite axis, it means there is a split in the edge flow, and it should spawn two faces instead of only one

&emsp;If two vertex have no direct path trough the plane: &emsp;.&emsp;split the cube into smaller cubes, leaving the non-connected sub-groups in these smaller cubes, and leave those cubes for later iterations

Once done, for each non-connected edge of the final mesh's edges, check every neighbour cube:

If it already has a face:  . If the angle between the calculated vector and the ocupied face's closest edge is big enough (i guess greater than around -20º):  . . extrude a new face

&emsp;.&emsp;.&emsp;If the angle is not too big (i guess less than around 20º): &emsp;.&emsp;.&emsp;.&emsp;connect the adjacent edges

. . Otherwise:

&emsp;.&emsp;.&emsp;.&emsp;If the distance between the edges is too small: &emsp;.&emsp;.&emsp;.&emsp;.&emsp;merge them at center &emsp;.&emsp;Otherwise: &emsp;.&emsp;.&emsp;create a new face from the two edges &emsp;Otherwise, if there is no face nearby: &emsp;.&emsp;Extrude the face along the calculated edge

This picture ends up with a non-desirable topology because of the edge flow. It could be an option to check for curvature in the mesh before extruding it curved
Once you have a face created: unlock the in-use cube lock the nearest cube assign the new created face to that nearest cube

`

Repeat the loop until completion

Pseudo-code (no images) pastebin.com/cU7e5zKv

In my opinion this algorithm is good because:

• It can be multithreaded easily
• Generates mostly quads
• Follows the flow of the edges
• Can be set to depend on vertex denisty
• Although it may need auxiliar voxel remeshing, once you've got the grid it should work in planes and non-waterproof meshes
• Linear in complexity
• Hard edges may be faked with seams
• It can be "baked" meaning you'd only have to update modified vertices, which maybe can become a real-time auto-retopology tool

And also has its drawbacks

• It does need to have three meshes, which may lead to high ram usage
• It tends to generate tris around hard edges
• Although it is linear in complexity, it needs to iterate over a lot of edges

Thank you for reading this