Overlap removal

[elalish]

This will be a large feature; I'm not sure when I'll have time to tackle it, but I want to write down my thoughts since I now have a sketch of the algorithm.

Removing overlaps would have two major uses: as the final stage of a manifold fixing algorithm for non-manifold input meshes, and also as a cleanup after Warp() that would take care of produced intersections. Technically it could also replace the Batch Boolean algorithm, but that's not a good idea as it probably won't be as fast.

In the paper this library's Boolean algorithm is based on, it makes clear that it only works for two input manifolds, not for removing the self-intersections of a single manifold. The reason is that the paper's method of linking edges can be done independently and still guarantee a manifold result, which is why the algorithm is parallelizable, but examples are given that break this guarantee in the single-manifold case.

However, the first half of the Boolean should still work basically the same. The collider will need to be updated so it can automatically skip intersections between a triangle and any edges that share a vertex with it. Then the calculation of intersection points and the winding numbers of vertices can proceed as it currently does, mostly. The verts will check for shadowing with their neighboring triangles, and use their neighbor triangles results to determine which two winding numbers this surface separates. Only verts separating winding 0 and 1 will be kept (strictly-positive fill rule).

The difference is there are a few new vertices that will not be found by these intersections of triangles with edges. These new verts will be the intersection of three non-neighboring triangles, which will be findable because they are also the intersection of three new edges, and this intersection exists if and only if the three new edges share a single set of three triangles as neighbors.

The bigger problem for manifoldness is that previously the new verts on a given partially-retained edge could be paired up arbitrarily (and independently) and still guarantee a manifold result. In the case of these new triple-intersections, that is no longer true - they depend on each other topologically. This means the assembly algorithm cannot be parallelized (that I know of), but by working serially it should be possible to start at an intersection and work our way along each seam, checking any previous neighbor pair-ups and basing the new pair-ups on those to maintain topological consistency.

Additionally, another type of new edge can form, which has only one intersection vert. This is when a manifold is folded, producing an intersection curve that terminates on both ends instead of forming a loop. In the case when a vert opposite the intersected edge (the other vert of either neighboring triangle) is shared with the triangle it is intersecting, then this new edge will go from the intersection vert to this opposite vert.