-
-
Notifications
You must be signed in to change notification settings - Fork 266
New issue
Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.
By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.
Already on GitHub? Sign in to your account
Freeze and explosive memory growth when newing a ConvexHull with specific input #325
Comments
(Noting that I've seen this! Currently traveling; probably will be some days before I can actually poke this.) |
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! |
(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) |
That's okay, we're all working on open-source time here, I understand the struggle :) |
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:
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! |
One non-numerical intervention that could work: 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. |
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.
The text was updated successfully, but these errors were encountered: