Method and apparatus for modeling interactions
First Claim
1. A method for using a computer to model interactions between a first body experiencing a first translation concurrent with a first rotation and a second body experiencing a second translation concurrent with a second rotation, comprising:
- a) receiving into the computer representations of said first body, said first translation concurrent with said first rotation, said second body, and said second translation concurrent with said second rotation;
b) using the computer to transform the representation of said first body and the representation of said first translation concurrent with said first rotation into a first swept representation comprising a hierarchical bounding volume representation whose leaves each contain an approximate representation of the region swept by a section of said first body during said first translation concurrent with said first rotation, wherein the union of said volumes is approximately a superset of the region swept by the surface of said first body during said first translation concurrent with said first rotation;
c) using the computer to transform the representation of said second body and the representation of said second translation concurrent with said second rotation into a second swept representation comprising a hierarchical bounding volume representation whose leaves each contain an approximate representation of the region swept by a section of said second body during said second translation concurrent with said second rotation, wherein the union of said volumes is approximately a superset of the region swept by the surface of said second body during said second translation concurrent with said second rotation;
d) using the computer to determine an interaction between said first swept representation and said second swept representation; and
e) communicating the interaction.
3 Assignments
0 Petitions
Accused Products
Abstract
A method and apparatus for modeling interactions between bodies. The method comprises representing two bodies undergoing translations and rotations by two hierarchical swept volume representations. Interactions such as nearest approach and collision can be modeled based on the swept body representations. The present invention can serve as a practical tool in motion planning, CAD systems, simulation systems, safety analysis, and applications that require modeling time-based interactions. A body can be represented in the present invention by a union of convex polygons and convex polyhedra. As used generally herein, polyhedron includes polygon, and polyhedra includes polygons. The body undergoing translation can be represented by a swept body representation, where the swept body representation comprises a hierarchical bounding volume representation whose leaves each contain a representation of the region swept by a section of the body during the translation, and where the union of the regions is a superset of the region swept by the surface of the body during translation. Interactions between two bodies thus represented can be modeled by modeling interactions between the convex hulls of the finite sets of discrete points in the swept body representations.
-
Citations
22 Claims
-
1. A method for using a computer to model interactions between a first body experiencing a first translation concurrent with a first rotation and a second body experiencing a second translation concurrent with a second rotation, comprising:
-
a) receiving into the computer representations of said first body, said first translation concurrent with said first rotation, said second body, and said second translation concurrent with said second rotation; b) using the computer to transform the representation of said first body and the representation of said first translation concurrent with said first rotation into a first swept representation comprising a hierarchical bounding volume representation whose leaves each contain an approximate representation of the region swept by a section of said first body during said first translation concurrent with said first rotation, wherein the union of said volumes is approximately a superset of the region swept by the surface of said first body during said first translation concurrent with said first rotation; c) using the computer to transform the representation of said second body and the representation of said second translation concurrent with said second rotation into a second swept representation comprising a hierarchical bounding volume representation whose leaves each contain an approximate representation of the region swept by a section of said second body during said second translation concurrent with said second rotation, wherein the union of said volumes is approximately a superset of the region swept by the surface of said second body during said second translation concurrent with said second rotation; d) using the computer to determine an interaction between said first swept representation and said second swept representation; and e) communicating the interaction. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13)
-
-
14. An apparatus for modeling interactions between a first body experiencing a first translation concurrent with rotation and a second body experiencing a second translation concurrent with rotation, comprising:
-
a) a processor; b) a storage subsystem; c) an input subsystem; d) an output subsystem; e) means for using said input subsystem to receive into said storage subsystem representations of said first body, said first translation concurrent with rotation, said second body, and said second translation concurrent with rotation; f) means for transforming said representation of said first body and said representation of said first translation concurrent with rotation into a first swept representation comprising a hierarchical bounding volume representation whose leaves each contain a representation of the region swept by a section of said first body during said first translation concurrent with rotation, wherein the union of said volumes is a superset of the region swept by the surface of said first body during said first translation concurrent with rotation; g) means for transforming the representation of said second body and said representation of said second translation concurrent with rotation into a second swept representation comprising a hierarchical bounding volume representation whose leaves each contain a representation of the region swept by a section of said second body during said second translation concurrent with rotation, wherein the union of said volumes is a superset of the region swept by the surface of said second body during said second translation concurrent with rotation; h) means for determining an interaction between said first swept representation and said second swept representation; and i) means for using said output subsystem to communicate said interaction. - View Dependent Claims (15, 16, 17, 18, 19, 20, 21, 22)
-
Specification