Patent ID: 7996197

Claim:
A method practiced on a computer for clearance detection that maps motions of a first body and a second body, for detecting a clearance between the first body and the second body, wherein the first body undergoes a first motion and the second body undergoes a second motion, the method comprising the steps of: providing a first bounding volume hierarchy (BVH) representation for the first body and a second BVH representation for the second body; providing a first time-dependent mapping representative of the first motion, the first time-dependent mapping having a first inverse mapping and, providing a second time-dependent mapping representative of the second motion, the second time-dependent mapping having a second inverse mapping; performing a hierarchical minimum-distance search with respect to a first volume virtually swept by the first BVH representation of the first body undergoing the first motion and a second volume virtually swept by the second BVH representation of the second body undergoing the second motion, the hierarchical minimum distance search comprising, applying the first inverse mapping to a first direction vector and applying the first time-dependent mapping to a first node in the first BVH representation to determine a first directionally furthest location on a first node swept volume, the first node-swept volume virtually swept by the first node in the first BVH representation of the first body undergoing the first motion and, applying the second inverse mapping to a second direction vector and applying the second time-dependent mapping to a second node in the second BVH representation to determine a second directionally furthest location on a second node-swept volume, the second node-swept volume virtually swept by the second node in the second BVH representation of the second body undergoing the second motion; detecting the clearance between the first body and the second body; and, providing the result of detecting the clearance between the first body and the second body to a user, to allow the user to perform one or more tasks selected from planning a motion for at least one of the first body and the second body, detecting a collision between the first body and the second body and, detecting a collision between an obstacle and at least one of the first body and the second body.