Handling of Kissing Faces

[a-day-old-bagel]

I have a need to do a boolean add on some convex hulls which meet exactly at their faces, which works, for the most part, as you'd expect.

However, on a few occasions, I get a resulting manifold that hasn't properly "connected" some of the "kissing faces."

Such an incorrect manifold doesn't have any error status attached, to be clear. It still says "no error."
I'm also already running with the recent double precision update. I was hoping that would clear up this issue, but no luck.

It makes sense that this is a precision issue, where kissing faces that don't share all their vertices might not properly resolve, but I was hoping there would be some way to tweak an epsilon somewhere such that two planes that are "extremely close" could be considered to intersect.

EDIT: To add, these kissing faces are produced via splits or trims using the exact same plane, so they should be perfectly coplanar, but, of course, floating point is the enemy of all "shoulds."

Here is a bad case, where you can see that the brownish hull on the right has not been split by the grey hull on the left, and following this is a picture of a good case, where you can see the brownish hull has been split.

I'm just hoping to hear that "kissing faces" isn't one of those intractable problems.

[elalish]

I'm afraid it is pretty intractable. The Boolean actually treats inexact inputs as exact, so there is no epsilon for determining whether an intersection occurs or not. For exactly coincident faces, we use symbolic perturbation based on normals to do the nicer thing you're asking for, but if the faces are not axis aligned, that basically never happens. We consider both examples you show to be correct output because you'll get a correct winding number for any point in R3 that's not within precision of the faces.

What are you trying to accomplish with this algorithm?

[a-day-old-bagel]

There are some compound objects that are composed of convex hulls. They are built up as part of a non-mesh modeling workflow. I've been using Manifold to do some calculations, which requires bringing them into a mesh representation (since Manifold works with meshes).

I don't believe this is a case where I can restructure the entire application to avoid this one issue, and I can't use CGAL or something due to the annoying licensing. Also I like Manifold better.

[pca006132]

Thinking about it, it may not be that intractable? For example can we merge faces that are closer than 2*epsilon together, and move the vertices to the middle for example? I am talking about a pretty trivial case but I feel that this may be something that can be generalized a bit.

[elalish]

Yeah, in fact our SimplifyTopology step does quite a bit of this already - it'll even remove small handles and delete entire objects that are small or thin enough. But that one operates on neighbors - it'll be a bit more expensive to deal with non-neighbors - that starts to look a bit more like Merge(). And keeping a manifoldness guarantee during those kinds of operations is quite non-trivial. If someone wants to sketch out what they think is a robust algorithm, I'd be interested to see it.

[pca006132]

True. This is probably something users/we may want to run at the end when exporting the manifold.

[a-day-old-bagel]

When the issue appears, the resulting mesh has an extremely thin "pocket" where I had wanted two faces to merge. In the pictured "bad" case, there is an edge inside of there, across which there is a tremendously small angle, which should be 0. Of course, if it were perfectly 0 then this wouldn't be manifold anymore I suppose. I don't know how "neighborly" things have to be to be subject to the SimplifyTopology you mentioned, but that super-thin pocket seems like a thing that might be detectable.

[pca006132]

Yes, it is detectable, just not something that can be done locally by checking a face against its neighbors. We need to do a global collision check for all faces, this is why we are saying it is expensive. I can try to sketch out my idea, but will need some time as my todo list is getting long now... Will open an issue to track this.

[elalish]

And to be clear, even at 0 degrees or exactly coincident faces, all of this is perfectly manifold. Our manifoldness definition is purely topological - there are no geometric checks at all to determine manifoldness. This is what we call marginal geometry, which is to say it's on the verge of self-intersection, but that's something we're robust to, rather than making guarantees about.

[a-day-old-bagel]

I notice that if I project this geometry down onto the floor plane (resulting in a CrossSection), the Simplify method does seem to resolve the gap. Before using Simplify, you can see the gap in the CrossSection too. But of course, that projection can't be reversed to get the 3D geometry back, and I don't immediately see any analogue to Simplify in the Manifold class.

Even if this is pretty intractable, and I have to find some other way around it, I do appreciate the thoughtful answers here. Thank you.

[zalo]

Manifold's Simplification is hiding in the .AsOriginal() method; I've noticed it clean up slivers on some gnarly Minkowski outputs before 😅

[a-day-old-bagel]

As an update for anyone facing similar issues (no pun intended), I've been manually offsetting each kissing face outward into its partner by a value of 1e-12 along its normal, and then relying on the built-in vertex neighbor merging to reduce the complexity of the resulting overlap. It seems to work robustly for now, and I haven't seen any more issues yet.

Of course, this is only possible because in my data structure I already know which face pairs are supposed to kiss. Without that knowledge, I'd have no short term solution.

[starseeker]

I think this is either similar to or the same fundamental issue as #614 ? I too would love an automatic way to resolve such cases, if it is possible. Offsetting our faces to avoid the problem in the first place is something I need to look into, but I suspect there will be some subtleties in our use case that'll make it "interesting". I'll be following #926 with interest :-)

[pca006132]

Current idea: Only consider a pair of triangles that are close. We subdivide the pair of triangles according to the intersection of their projection into the median plane between the two faces, and join the two triangles by surrounding them with 6 triangles and remove the original two.

Situations:

1. Multiple pairs: Mark all pairs of triangles that are close. For each connected component of marked pairs, we only need to do this once, and the local simplification pass should handle the rest.
2. Part of the pairs of triangles are close, e.g. they are not parallel: Subdivide the triangle to find the part that is close.

[elalish]

Honestly, I sense this will get pretty thorny - it's been hard enough ensuring our existing decimator maintains manifoldness. I think I'd rather tackle this via #289 - that should really address marginal geometry as well as serious overlaps.