Feature request: 3D convex decomposition operation

[thehans]

Convex decomposition is an operation that OpenSCAD relies on as part of its minkowski operations.
Currently the only implementation we have available is through CGAL, using its dreaded Nef Polyhedra which is slow and error prone.

[elalish]

Interesting! I don't know anything about convex decomposition algorithms. Are you interested in contributing? Or do you know any good papers?

Also, does anyone use Minkowski for anything? I never found it to be a particularly intuitive or practical operation. Have you ever seen it used with anything but a sphere?

[thehans]

I'm not familiar with the algorithms involved, but this is the paper from CGAL's convex decomposition bibliography
https://www.cs.princeton.edu/~chazelle/pubs/ConvexPartitionPolyhedra.pdf

Have you ever seen it used with anything but a sphere?

Well, not really, just variations on sphere; e.g. geodesics.

For context, what prompted me to open this issue was testing an openscad script of mine which tries to perform all variety of morphological operations: dilation, erosion, closing, opening, any ultimately an operation designed to fillet all (convex and concave) edges of a geometry without changing the overall bounds (0 net offset to the faces), which I'm calling "roundover".

I was seeing a lot of inconsistencies and errors when running this script, which I created a separate issue for: openscad/openscad#4617 (full scad script included there)
The times when it errored were due to CGAL assertions during convex decomposition.

It would be amazing if we can have all our operations handled through manifold without this sort of back and forth between CGAL. This is just one of the remaining holdouts that I'm aware of. (I haven't had a chance to review ochafik's implementation to know the full list, or if there's any other operations in particular)

[pca006132]

It seems that precise convex decomposition will give you many parts, e.g. when you have a doughnut or a fillet, so I don't think this is a practical approach to implementing morphological operations.

And I don't think you need to use morphological operations for fillet, this is a complete overkill. It should be much easier to detect those edges (including their neighborhood), generate a fillet for each one and perform union for them. There are a few things that I am not sure though:

1. How should we deal with faces/edges with length smaller than the fillet radius?
2. When fillets intersect, what should we do with them?
3. What should we do when a fillet can pass through a solid part?

[elalish]

Agreed, though I'm not even sure it'll involve the Boolean. I think the main thing will be to cut the mesh along curves offset from the input edges according to the dihedral angle. Then those regions can be rebuilt, probably using our existing smooth interpolation function.

[pca006132]

I was thinking about this. People often try to use approximate convex decomposition, e.g. https://colin97.github.io/CoACD/, which allows the user to specify a threshold for concavity.

Concavity in this case (if I understand their abstract correctly) is the maximum distance for a plane to both the convex hull and the interior (other planes). If we want to offset by d, we can set the threshold to slightly more than 2d to make sure that offsetting each face by d will not result in self intersection. We probably need to check for collision for adjacent surfaces as well, which is more work than having convex input, but it feels manageable. (correct me if I am wrong, I am not sure if this is sufficient)

The drawback is that we will not be able to support general minkowski, but I doubt if people really need that.

@ochafik maybe you have something to say about this? iirc you wrote the parallel minkowski for openscad

[pca006132]

oh nevermind, after reading the paper in more details it seems that it is not that helpful in this case. the metric is about something else.

[pca006132]

I am now trying to write 3D offsetting. The algorithm has 3 phases.

1. Figure out all pairs of faces that do not share any vertex and may overlap after offsetting. (let's call them conflict pairs)
2. Cut the mesh into pieces such that the conflict pairs we found previously are in different pieces.
3. Apply the 3D offsetting and union them together.

Here is my implementation of 1 and 2: https://github.com/pca006132/manifold/blob/offset/src/manifold/src/offset.cpp#L288

This implementation approximates the offset using a miter joint (http://www.angusj.com/clipper2/Docs/Units/Clipper/Types/JoinType.htm) that enclose the sphere centered in the original vertex with radius = offset. It uses BVH for a broad phase check, and then use separating axis test to precisely check overlapping regions (with some preliminary precision hack to handle degenerate cases, not sure if they are correct though). After gathering the conflict pairs, we use separating axis test again to find cuts that can cut the pairs.

This should be much more efficient than convex decomposition because the decomposition results can be concave. Preliminary tests show that running this for sponge4 took 24s without parallelization (and parallelization should be simple). I can't imagine running convex decomposition for sponge4...

Will try to finish the remaining stuff later when I have time.

[pca006132]

and interestingly, concave surfaces are much easier to handle as we do not need to add round edges or corners. convex decomposition will break the concave surface into convex surfaces, add a bunch of round edges, and then union and remove those round edges.

[elalish]

I'm curious to see your results. My limited experience with 3D offsetting is that it's hard. For instance, asymmetric faces around a vert when offset do not meet at one vert anymore, so miters are non-trivial. This can cause an explosion of faces on a smoothly curving region.

I'm still dubious about OpenSCAD's Minkowski even with a sphere. I think it would be more valuable to apply a fillet of a given radius to a particular intersection curve, than to do a global operation.

[pca006132]

Yes, I was only something similar to miters to approximate the rounded corner volume, to make sure that every potentially overlapping pairs of triangles are considered. The approximation can distort the faces, so it is not really miter joint.

[pca006132]

Handling vertices with both convex and concave edges turns out to be much harder than what I originally expected, but none the less I seems to got it working:

with the original mesh being

I have not yet finished implementing rounding and fixing the mesh relations. The algorithm so far seems pretty efficient, the majority of it is trivially parallelizable (per vertex operations).

However, this approach has one fundamental problem: If a vertex has > 3 faces that forms a concave surface, in general they will not meet in the same position after (positive) offset. The paper I am reading about suggested approximating them, so this is what I am currently doing. In practice, I think they will only deviate a little (1 degree or something).

[elalish]

Impressive! Yes, you'll see the problem you talk about if you give a negative offset to e.g. a cuboctahedron. Let's see how well the approximation does. The other tricky part will be as the offset gets large (negative or positive) and it starts causing large-scale topology changes. That may be a good place to bring in an overlap removal algorithm.

[pca006132]

I think as we are not considering using 3D convex decomposition to implement offsetting, we should probably close this one and move all the discussion to #192. I will be opening a PR later (perhaps sometime in Nov) to push my offset implementation, so users can try it.

[zalo]

I’d still like to see your take on Offsetting to compare elalish’s and mine

I’d be curious if the speed or robustness (to repeated morphology) is better 😀

I already picked up a few tricks from elalish’s, which I’m still hoping to refine to prevent corruption explosions

[pca006132]

I would love to. Currently I am busy with sscad, the goal is to run something simple (not even geometry related) to see the performance before new year, I got a cold for the last 2 days (have not fully recover yet) so the time is a bit tight. I think I can go back to my previous code and try to make it work.

I think the major complexity of my code comes from rounding edges and corners, they are non-trivial and I don't have the mathematical knowledge to make sure that they are correct. They will likely be the performance bottleneck as well, other than the union of the decomposition results. (not sure how to name that decomposition that I do, it is not exactly approximate convex, but is also related to convex decomposition...)