Publication
Efficient Geometrically Exact Continuous Collision Detection
AbstractContinuous collision detection (CCD) between deforming triangle mesh elements in 3D is a critical tool for many applications. The standard method involving a cubic polynomial solver is vulnerable to rounding error, requiring the use of ad hoc tolerances, and nevertheless is particularly fragile in (near-)planar cases. Even with per-simulation tuning, it may still cause problems by missing collisions or erroneously flagging non-collisions. We present a geometrically exact alternative guaranteed to produce the correct Boolean result (significant collision or not) as if calculated with exact arithmetic, even in degenerate scenarios. Our critical insight is that only the parity of the number of collisions is needed for robust simula- tion, and this parity can be calculated with simpler non-constructive predicates. In essence we analyze the roots of the nonlinear system of equations defining CCD through careful consideration of the boundary of the parameter domain. The use of new conservative culling and interval filters allows typical simulations to run as fast as with the non-robust version, but without need for tuning or worries about failure cases even in geometrically degenerate scenarios. We demonstrate the effectiveness of geometrically exact detection with a novel adaptive cloth simulation, the first to guar- antee to remain intersection-free despite frequent curvature-driven remeshing.
Download publicationRelated Resources
See what’s new.
2017
An Investigation of Generative Design for Heating
Energy consumption in buildings contribute to 41% of global carbon…
2016
CircuitMagic: Automatic Capture of Handdrawn Electronic Symbols and Component Selection in an Electronic EDA CAD System using Machine Learning Techniques
Consider a modern client-server/cloud EDA CAD design system as shown…
2010
Asymetric Flow Control for Data Transfer in Hybrid Computing Systems
Hybrid computing systems that combine specialized accelerators with…
2007
Position Statement: Design Studio Culture in HCI
In defining a virtual design studio culture (from now I will call it a…
Get in touch
Something pique your interest? Get in touch if you’d like to learn more about Autodesk Research, our projects, people, and potential collaboration opportunities.
Contact us