US 7,996,197 B1Granted

Clearance detector and method for motion and distance

AssigneeSandia Corporation

InventorPatrick G. Xavier

Life of this patent

Estimating the term…

Loading patent…

Abstract

A method for correct and efficient detection of clearances between three-dimensional bodies in computer-based simulations, where one or both of the volumes is subject to translation and/or rotations. The method conservatively determines of the size of such clearances and whether there is a collision between the bodies. Given two bodies, each of which is undergoing separate motions, the method utilizes bounding-volume hierarchy representations for the two bodies and, mappings and inverse mappings for the motions of the two bodies. The method uses the representations, mappings and direction vectors to determine the directionally furthest locations of points on the convex hulls of the volumes virtually swept by the bodies and hence the clearance between the bodies, without having to calculate the convex hulls of the bodies. The method includes clearance detection for bodies comprising convex geometrical primitives and more specific techniques for bodies comprising convex polyhedra.

Claims14

Dependent claims

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.

5 more elements

A non-transitory computer readable medium tangibly embodying at least one set of instructions 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 at least one set of instructions for performing the steps of:

receiving a first boundary volume hierarchy (BVH) representation for the first body and a second BVH representation for the second body;
receiving a first time-dependent mapping representative of the first motion, the first time-dependent mapping having a first inverse mapping and, receiving a second time-dependent mapping 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.

4 more elements

Dependencies are inferred from the claim text.

Facts

Application: 11/654,826Filed 18 Jan 2007 · continuation in part
Priority: 12 Sep 2002
Granted: 9 Aug 2011
Term ends: Not estimatedThe source records don’t support an estimate.

Classification3 codes

G05B 19/4097
Numerical control [NC], i.e. automatically operating machines, in particular machine tools, e.g. in a manufacturing environment, so as to…
G05B 2219/35223
Nc in input of data, input till input file format: tolerance, consider tolerance in design, design for assembly
G05B
Control or regulating systems in general