Freeze and explosive memory growth when newing a ConvexHull with specific input

[Eideren]

Hey there, pretty much as the title says. Program blocks somewhere in this function/loop https://github.com/bepu/bepuphysics2/blob/master/BepuPhysics/Collidables/ConvexHullHelper.cs#L868 it eats up more than a gig per second, saturating my ram and freezing the operating system.

We're on 2.5.0-beta.19, haven't had time to test on a more recent version, let me know.

This is the repro, it's kind of large for a convex but testing other similar convexes did not result in this issue.

var points = new System.Numerics.Vector3[]
{
     new(-0.637357891f, 0.347849399f, -0.303436399f),
     new(-0.636290252f, 0.345867455f, -0.301366687f),
     new(-0.992014945f, 0.348357588f, -0.3031407f),
     new(-1.00909662f, 0.386065364f, -0.303337872f),
     new(0.637357891f, 0.347849399f, -0.303436399f),
     new(-0.636290252f, 0.345918268f, 0.701366544f),
     new(-0.636503756f, 0.345918268f, 0.700873733f),
     new(-0.992655516f, 0.346578926f, 0.701070845f),
     new(-0.992655516f, 0.346578926f, -0.301070988f),
     new(0.636290252f, 0.345867455f, -0.301366687f),
     new(-0.995858312f, 0.348510057f, -0.301859498f),
     new(-1.01272643f, 0.385912925f, -0.302056611f),
     new(-1.01037765f, 0.390029252f, -0.302746475f),
     new(-0.637357891f, 0.389521062f, -0.302845061f),
     new(1.00909662f, 0.386065364f, -0.303337872f),
     new(0.992014945f, 0.348357588f, -0.3031407f),
     new(-0.637357891f, 0.347849399f, 0.703436255f),
     new(-0.992014945f, 0.348357588f, 0.703140557f),
     new(0.636290252f, 0.345918268f, 0.701366544f),
     new(-0.995858312f, 0.348510057f, 0.701859355f),
     new(-1.02553761f, 0.351406753f, 0.678599536f),
     new(-1.0251106f, 0.35013628f, 0.675938487f),
     new(-1.0251106f, 0.35013628f, -0.2759386f),
     new(-1.02553761f, 0.351406753f, -0.278599679f),
     new(0.992655516f, 0.346578926f, -0.301070988f),
     new(0.992655516f, 0.346578926f, 0.701070845f),
     new(0.636503756f, 0.345918268f, 0.700873733f),
     new(-1.04432738f, 0.37869662f, -0.274558783f),
     new(-1.01400757f, 0.389673531f, -0.301465213f),
     new(-1.04582202f, 0.382304758f, -0.273770332f),
     new(-1.0582062f, 0.67344743f, -0.220745891f),
     new(-1.0545764f, 0.674260557f, -0.22183004f),
     new(-0.637144327f, 0.674158931f, -0.221928596f),
     new(1.01037765f, 0.390029252f, -0.302746475f),
     new(0.637357891f, 0.389521062f, -0.302845061f),
     new(1.01272643f, 0.385912925f, -0.302056611f),
     new(0.995858312f, 0.348510057f, -0.301859498f),
     new(-1.00909662f, 0.386065364f, 0.703337729f),
     new(0.637357891f, 0.347849399f, 0.703436255f),
     new(0.992014945f, 0.348357588f, 0.703140557f),
     new(-1.01272643f, 0.385912925f, 0.702056468f),
     new(-1.04432738f, 0.37869662f, 0.67455864f),
     new(-1.04582202f, 0.380170345f, 0.671404779f),
     new(-1.04582202f, 0.380170345f, -0.271404922f),
     new(1.02553761f, 0.351406753f, -0.278599679f),
     new(1.0251106f, 0.35013628f, -0.2759386f),
     new(1.0251106f, 0.35013628f, 0.675938487f),
     new(1.02553761f, 0.351406753f, 0.678599536f),
     new(0.995858312f, 0.348510057f, 0.701859355f),
     new(-1.08980727f, 0.656575501f, -0.196303427f),
     new(-1.09023428f, 0.656982064f, -0.193346679f),
     new(-1.0584197f, 0.67675066f, -0.21867618f),
     new(-1.0550034f, 0.677512944f, -0.219858885f),
     new(-1.09023428f, 0.659827888f, -0.194233686f),
     new(0.637144327f, 0.674158931f, -0.221928596f),
     new(1.01400757f, 0.389673531f, -0.301465213f),
     new(1.0545764f, 0.674260557f, -0.22183004f),
     new(1.0582062f, 0.67344743f, -0.220745891f),
     new(1.04582202f, 0.382304758f, -0.273770332f),
     new(1.04432738f, 0.37869662f, -0.274558783f),
     new(-0.637357891f, 0.389521062f, 0.702844918f),
     new(-1.01037765f, 0.390029252f, 0.702746332f),
     new(1.00909662f, 0.386065364f, 0.703337729f),
     new(-1.01400757f, 0.389673531f, 0.70146507f),
     new(-1.04582202f, 0.382304758f, 0.673770189f),
     new(-1.09023428f, 0.656982064f, 0.593346536f),
     new(1.04582202f, 0.380170345f, -0.271404922f),
     new(1.04582202f, 0.380170345f, 0.671404779f),
     new(1.04432738f, 0.37869662f, 0.67455864f),
     new(1.01272643f, 0.385912925f, 0.702056468f),
     new(-1.09066129f, 0.832155526f, 0.199999928f),
     new(-1.0584197f, 0.86234206f, -0.0161386579f),
     new(-1.0550034f, 0.863663316f, -0.0167300105f),
     new(1.0550034f, 0.677512944f, -0.219858885f),
     new(-1.09023428f, 0.833781719f, -0.00135488808f),
     new(1.08980727f, 0.656575501f, -0.196303427f),
     new(1.0584197f, 0.67675066f, -0.21867618f),
     new(1.09023428f, 0.659827888f, -0.194233686f),
     new(1.09023428f, 0.656982064f, -0.193346679f),
     new(0.637357891f, 0.389521062f, 0.702844918f),
     new(1.01037765f, 0.390029252f, 0.702746332f),
     new(-0.637144327f, 0.674158931f, 0.621928453f),
     new(-1.0545764f, 0.674260557f, 0.621829867f),
     new(-1.0582062f, 0.67344743f, 0.620745778f),
     new(-1.08980727f, 0.656575501f, 0.596303284f),
     new(-1.09023428f, 0.659827888f, 0.594233513f),
     new(1.04582202f, 0.382304758f, 0.673770189f),
     new(1.09023428f, 0.656982064f, 0.593346536f),
     new(1.01400757f, 0.389673531f, 0.70146507f),
     new(-1.09044778f, 0.834950566f, 0.199999928f),
     new(-1.09023428f, 0.833781719f, 0.40135473f),
     new(-1.0584197f, 0.863663316f, -0.0124919862f),
     new(-1.0550034f, 0.865035474f, -0.0132804662f),
     new(1.0550034f, 0.863663316f, -0.0167300105f),
     new(-1.09002078f, 0.835204661f, 0.00219321251f),
     new(1.0584197f, 0.86234206f, -0.0161386579f),
     new(1.09023428f, 0.833781719f, -0.00135488808f),
     new(1.09066129f, 0.832155526f, 0.199999928f),
     new(1.0582062f, 0.67344743f, 0.620745778f),
     new(1.0545764f, 0.674260557f, 0.621829867f),
     new(0.637144327f, 0.674158931f, 0.621928453f),
     new(-1.0550034f, 0.677512944f, 0.619858742f),
     new(-1.0584197f, 0.67675066f, 0.618676066f),
     new(-1.0584197f, 0.86234206f, 0.41613853f),
     new(1.08980727f, 0.656575501f, 0.596303284f),
     new(1.09023428f, 0.659827888f, 0.594233513f),
     new(-1.09002078f, 0.835204661f, 0.397806644f),
     new(-1.05863321f, 0.863612533f, 0.199999928f),
     new(-1.0584197f, 0.863663316f, 0.412491858f),
     new(-1.0550034f, 0.865035474f, 0.413280308f),
     new(1.0550034f, 0.865035474f, -0.0132804662f),
     new(1.0584197f, 0.863663316f, -0.0124919862f),
     new(1.09002078f, 0.835204661f, 0.00219321251f),
     new(1.09044778f, 0.834950566f, 0.199999928f),
     new(1.09023428f, 0.833781719f, 0.40135473f),
     new(1.0584197f, 0.67675066f, 0.618676066f),
     new(1.0550034f, 0.677512944f, 0.619858742f),
     new(-1.0550034f, 0.863663316f, 0.416729867f),
     new(1.0584197f, 0.86234206f, 0.41613853f),
     new(1.0550034f, 0.865035474f, 0.413280308f),
     new(1.05863321f, 0.863612533f, 0.199999928f),
     new(1.09002078f, 0.835204661f, 0.397806644f),
     new(1.0584197f, 0.863663316f, 0.412491858f),
     new(1.0550034f, 0.8636633f, 0.41672987f),
};
var convex = new ConvexHull(points, AnyOldPool, out _);

[RossNordby]

(Noting that I've seen this! Currently traveling; probably will be some days before I can actually poke this.)

[RossNordby]

Reproduced; something wonky with face merges. Still going to be a while before I have the time to actually fix it; hopefully in the next two weeks.

Thanks for the report!

[RossNordby]

(it occurs to me that the next two weeks contain two conferences and a bunch of additional travel and I should have probably said three weeks; this is going to be a very solid record for my Longest Bug Turnaround)

[Eideren]

That's okay, we're all working on open-source time here, I understand the struggle :)

[RossNordby]

Haven't forgotten about this! Had a bit of time today; it is indeed related to face merging. Specifically, face merging works by detecting faces which share edges and have a sufficiently similar normal. In this case, the order in which faces are visited and some numerical details result in an oscillation between two faces which have extremely similar normals and share vertices but do not share detected edges, despite generating search directions which do yield each other. Since each new face doesn't rule out any vertices (all vertices are on the exterior of the 2d face hull), it just keeps re-finding the same faces and deleting the ones that were there previously. The memory explosion is caused by the fact that deletions are deferred under the assumption that there won't actually be millions of steps, so the memory growth just keeps growing.

It's quite a numerical pickle.

Some potential solutions:

1. Check all shared vertex faces.
2. Brute force test all face normals against new face normal without regard for connectivity.

There's also the option of brute force testing all points in the new face against all existing planes by offset, but this is actually very similar to what happens when a new face is built in the first place. The fact that there still exist faces that need merging is an indicator that there's a numerical disagreement between offset-based vertex collection and normal-based merging.

2 could be viewed as an extension to the face creation process; not strictly a post-process, but rather than only collecting vertices that fall within the plane offset region, it could also accept vertices which would not significantly change the normal. This would accept vertices further from the source plane when those vertices are further from the new face measurement origin.

I'm leaning towards something like... including a term for distance from edge in the coplanarity test threshold to make the frequency of merging much lower (by bundling it into initial vertex selection), introducing a brute force normal merge, but possibly only executing that normal merge when a cycle is encountered or something. Some form of non-numerical intervention is required to guarantee that no blowup is possible.

Probably can't finish this this weekend, alas!

[RossNordby]

One non-numerical intervention that could work:
For each new face candidate, look for existing faces that have two or more shared edges. Those faces are at least partially redundant.

If the new face is a subset of an existing face, toss it out and do nothing. This averts the cycle by not regenerating the same search directions.

If the new face has another vertex, merge the faces and reduce. Any newly internal vertices in the face will be removed from future consideration.

Should be discretely monotonic with that, if I'm not too tired to think goodly.