Flat "fractal like" mesh fails to compute convex hull (unsure if bug or expected)

[Frooxius]

Hello!

I'm back with another weird mesh and convex hulls! ^^;

I ran into this mesh, which is a "fractal like" shape, that's entirely planar: flat_mesh.zip

Trying to compute a convex hull for this mesh fails to produce any - the resulting convex hull will have no data at all.

I am unsure if this is a bug though or if it's expected behavior because of how "flat" and one sided the shape is. Should I just reject convex hulls when it fails to compute for shapes like this? Or is there a way to realistically compute one, even if it's very thin?

Thank you for your time!

[RossNordby]

Whew! Yes, it's expected behavior this time :P

In the last round of fixes, I added returns to the ConvexHullHelper.CreateShape functions. If something went wrong (in this case, a degenerate point set lacking in volume), it now returns false rather than exploding.

In principle, it's possible to make a very thin convex shape work (see a Box with zero extent along one axis), but it requires a few changes:

1. The convex hull algorithm isn't built for degenerate shapes. It would need a fallback to handle point sets that are detected as lacking volume. This isn't super hard, but it's not there now.
2. Anything involving ComputeInertia would need an update. It assumes a nondegenerate shape, so it would also need a fallback added.
3. The hull-related pair testers may need some updates. It's likely that there are some assumptions related to faces having area during clipping which would cause problems with edge-on collisions.

A hull tester revamp is on the todo list and the other stuff would be semiquick, but I wouldn't recommend taking a dependency on me getting that done in a timely fashion.

[Frooxius]

Ah I figured! Thank you for the info!

There is one thing I thought as a potential "heuristic" fallback for this that I could implement on our end (I don't think it'd be good to have it directly int he library) - randomly displace all the point by some small amount, to give the shape a bit of of depth. It'd still be super thin, but at least it'd have some volume.

Do you think that could cause any trouble? Also it being random, it might not be guaranteed to solve the problem either, but it might make it give more what people expect in some cases.

Or we can just tell people "Bad shape, don't make that into convex hull colliders" when it fails and it just won't have a collider.

[RossNordby]

Random offsets could work okay-ish-ly, though I'd anticipate it sometimes producing some fairly wonky hulls with multiple near coplanar faces.

Another fallback might be to duplicate all points with an offset along the plane normal:

1. Grab a couple of distinct points from the point set. May require a little iteration to find non-identical points.
2. Treat the offset between them as an axis and sample the extreme points of the point set along that axis.
3. Find the point most distant from the extreme point line passing through ExtremePoint(pointSet, axis) and ExtremePoint(pointSet, -axis). (Most distant just gives a little more numerical robustness than grabbing the first nonzero distance option.)
4. Cross the extreme point line direction with the offset from the extreme point line to the most distant point to get the plane normal.
5. Duplicate all points in the point set and add planeNormal * epsilon to all duplicates.

If step 3 doesn't find any points with nonnegligible distance to the line, then the point set has both no volume and no area, and you could try a similar expansion trick on two axes to get a wee little stick, I guess.

[Frooxius]

Oh yeah that's a better way to go about it!

Thank you very much!

I'm going to close this issue.