bepu / bepuphysics2

Pure C# 3D real time physics simulation library, now with a higher version number.
Apache License 2.0
2.4k stars 274 forks source link

ConvexHullHelper can generate spurious faces in pathological cases #60

Open RossNordby opened 5 years ago

RossNordby commented 5 years ago

With many near-coplanar points, it's possible for the ConvexHullHelper's convex hull algorithm to create spurious overlapping faces. Some mitigating factors:

  1. It tends to only happen in extreme pathological cases, so most uses won't run into it.
  2. The extra faces won't necessarily break anything- they might have a mild impact on contact manifold quality and performance in some cases.
  3. There exist external content-time tools which can be used to optimize and simplify convex hulls to avoid this case.
  4. Standard convex hull guidance is to stick to point clouds with unambiguous faces to avoid contact manifold jumping; this bug only happens if this advice is ignored.

It wouldn't be too hard to fix. A simple post-pass that attempts to detect and throw out (or merge) extra faces by normal or involved indices would suffice. I just didn't bother for the release since it's not critical.

RossNordby commented 5 years ago

A convex hull simplification algorithm (#61) would also capture the spurious faces.

george-tsiros commented 3 years ago

so worst possible case is when i have a flat quad made out of thousands of triangles, instead of one single quad?

RossNordby commented 3 years ago

That might cause some issues, yes.