A fast 3D collision detection algorithm
10 months ago
- #collision detection
- #computational geometry
- #optimization
- The article discusses improvements to the Separating Axis Test (SAT) for collision detection between convex polyhedra.
- It introduces the idea of overlaying Gauss maps to find the faces of the Minkowski difference, reducing the need for full support function evaluations.
- The author explores the optimization problem of finding the minimum translation to separate overlapping convex sets, framing it as a non-convex QCQP.
- For convex polyhedra, the support function's properties allow for efficient traversal of vertex regions to find the global minimum without recalculating support points.
- The optimized SAT test involves traversing arcs on a sphere, tracking support points, and updating them as regions change, significantly speeding up collision detection.
- A demo is provided showing the method is 5-10x faster than traditional SAT for many-faced hulls, though some numerical issues remain with triangles.
- The approach is presented as an optimization problem on a sphere, leveraging graph traversal and support function properties for efficiency.