Stairs mesh (.obj included) produces wrong convex hull

[Frooxius]

Hello!

I managed to find another issue! :D This time it's something with the convex hull calculation. I encountered a mesh that's being used to calculate a convex hull that worked with BEPUv1, but ends up producing invalid hull with v2, I've included it here: stairs.zip

When I load this into the ShrinkWrappedNewtsVideoDemo it reproduces the problem - instead of the stairs getting neatly wrapped, it ends up producing just a sliver from one of the sides and at some point ends up tripping a math check.

Curiously in my project I run a pass that merges nearby vertices into one (which reduces the number of them to about a half in this case), but it still occurs.

I also have algorithm laying around from BEPUv1 that converts a mesh to a convex hull mesh so I can re-export that to .obj. If I run this first and then feed it to BEPUv2 convex hull, it works normally: prewrapped_stairs.zip

---

Also I'd really like to thank you for all your help again! We ended up pushing the integration to public yesterday and even though there's still more to do (e.g. rigidbodies and constraints aren't properly integrated yet and only naively synced with delta changes), people are having lots of fun! :D https://twitter.com/mikan3134/status/1430832398082580481 https://twitter.com/Mattyrogue/status/1430567251913150472 https://twitter.com/NJELLY1/status/1430760453454524418

[RossNordby]

Couldn't get to this today, but I've reproduced it.

Given the numerical complexity of the hull computation, I have a suspicion this won't be the last issue filed around convex hull generation :P

Also I'd really like to thank you for all your help again! We ended up pushing the integration to public yesterday and even though there's still more to do (e.g. rigidbodies and constraints aren't properly integrated yet and only naively synced with delta changes), people are having lots of fun! :D

Glad to see it!

[RossNordby]

85bb145962777c89c4a99a416e9c890cac08da9e should fix this. Thanks for the report!

There were a few places where the huller was getting trapped by coplanar/collinear vertices, and this commit forces it to look elsewhere. This is primarily a numerical fix. It is conceivable that some content could sneak through with some combination of numerical errors that I did not foresee and cause a similar trap. I may be able to push through something with more logical guarantees (rather than merely numerical protections) if evil content requires it, but I'm going to wait on a repro before trying.

61 and #67 are also relevant. With user generated content in particular, I'm guessing more geometric processing is going to become mandatory.

[Frooxius]

Thank you so much! I've merged the fix and removed the workaround for now, I'll let you know if we run into any more issues with this.

I do some basic preprocessing before passing to the BEPUv2 which removes some vertices that are very close to each other, but in this case it didn't help.

Are there any external tools/algorithms that might be worth using as well? Or perhaps just increase the vertex merge threshold?

I'd definitely be happy for any in BEPUv2 as well, but I'll see if there are any more issues. There's definitely no shortage of evil content! :D I think this issue is probably good to close if you want me to open a new one, but I can also post more examples here if I find more depending on what you prefer.

[RossNordby]

Are there any external tools/algorithms that might be worth using as well? Or perhaps just increase the vertex merge threshold?

Heavy vertex merging can indeed help sometimes- it's a pretty easy win for performance in most cases, at least. You may also see benefit in some content from coarsely quantizing positions prior to merging. It'll tend to avoid some #67-ish issues by killing sliver faces and making near-coplanar faces fully coplanar and has the advantage of being super easy to implement. On the other hand, it could add extra faces where quantization of mid-face vertices creates a bump.

Mesh simplification algorithms in general may be useful. I'm not aware of specific libraries or tools here, but there should be some that could do stuff like, say, set up mesh edges in a priority queue weighted by how much the shape would be changed by their removal, then progressively merge edges that contribute the least out of existence. Basically anything that could be use to generate LODs.

I'd definitely be happy for any in BEPUv2 as well, but I'll see if there are any more issues. There's definitely no shortage of evil content! :D I think this issue is probably good to close if you want me to open a new one, but I can also post more examples here if I find more depending on what you prefer.

New issues are good- in theory the underlying issues should end up being distinct :P