Building convex hull fails for a specific mesh (.obj included) and results in memory corruption

[Frooxius]

Hello, it's me again after a while!

I've ran into a tricky issue with user generated content when generating convex hulls for meshes, for this particular mesh - Sierpinski triangle in 3D. This mesh is particularly dense, which I'd expect to potentially generate inefficient collider, so it's probably not a good idea in the first place, but I think it managed to hit a more serious bug in the convex hull generator.

Fractal.zip

In release mode, generating convex hull for this mesh results in memory corruption and the whole program crashing.

In debug mode, this violates the assertion in ConvexHullHelper.cs at line 257 "Previous edge should include any collinear points, so this edge should not see any further collinear points beyond its start."

If I let it run past that, it will eventually violate assertion in QuickList.cs with ValidateUnsafeAdd(). This seems to come from line reducedIndices.AllocateUnsafely() = faceVertexIndices[nextIndex]; in the same file at line 395.

From me stepping through the code, it appears that FindNextIndexForFaceHull() ends up alternating between two indices infinitely, which just ends up adding more items to the reducedIndicies, past the allocated capacity, which is where the memory corruption comes from.

I have a filter for the input points before processing, which merges vertices that are too close, which reduces the initial count a fair bit, but the issue still persists. I have modified this to keep merging points more and more, until there's less than 2048, which has "fixed" the issue with this particular one, but I think it's just because it modifies the data enough so it doesn't hit whatever bug there is, so I wanted to report it anyways.

Hope this helps, let me know if you need more info or context!

[RossNordby]

Reproduced the asserts and some wonky behavior; should have a fix pushed tomorrow.

Notably, I couldn't reproduce the memory corruption. Not sure what's going on there, but there's a good chance the fix fixes that too.

[RossNordby]

should have a fix pushed tomorrow.

The ostensible fix was secretly possessed by satan; more time may be required.

[RossNordby]

Alright, should be fixed as of 0ecb874 (2.5.0-beta17).

The hulls created for that sort of pathological case should now be much less likely to contain spurious internal faces. I wasn't able to reproduce the infinite loop/memorystomp issue, but I did robustify the relevant loop's termination conditions. It no longer relies on any numerical assumptions and should rule out that particular failure.

Thanks for the report!

[Frooxius]

Thank you for the fix! I've backported this to our fork ( we're still on Mono under Unity ;_; But working on getting away from that ).

There seems to be the DebugStep debugging code left in through, we have noticed that it causes memory leaks when used. We have a PR for our fork that just removes it by commenting it out, but I'm not sure how you prefer to remove the debugging steps on your end?

Yellow-Dog-Man#3

[RossNordby]

Woooooooooops! I guess it was inevitable that I was going to forget to re-disable that one of these times. I'm at a conference, but I'll get that fixed as soon as I can; thanks for the report!