Method and apparatus for modeling interactions

• US 6,099,573 A
• Filed: 04/17/1998
• Issued: 08/08/2000
• Est. Priority Date: 04/17/1998
• Status: Expired due to Term

• Current Assignee: National Technology & Engineering Solutions Of Sandia LLC (Honeywell International Inc.)
• Original Assignee: Sandia Corporation (Martin Marietta Corporation)
• Inventors: Xavier, Patrick G.
• Primary Examiner(s): Teska, Kevin J.
• Assistant Examiner(s): Broda, Samuel
• Application Number:
  US09/061,973
• Time in Patent Office: 844 Days
• Field of Search: 395/500.23, 395/500.27, 395/500.28, 345/419, 345/441, 345/473, 700/61, 700/103, 701/301, 703/2, 703/6, 703/7
• US Class Current: 703/7
• CPC Class Codes: G05B 2219/35148 Geometric modeling for swept volume of moving solids
• CPC Class Codes: G05B 2219/40317 For collision avoidance and detection
• CPC Class Codes: G06T 17/00 Three dimensional [3D] modelling, e.g. data description of 3D objects

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.

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.

2. A method according to claim 1, wherein the interaction determined is the approximate minimum distance between said first swept representation and said second swept representation.

3. A method according to claim 2, wherein the representations of said first body and said second body comprise unions of convex polygons and convex polyhedra.

4. A method according to claim 3,

a) wherein the step of using the computer to determine the approximate minimum distance comprises using the computer to determine the minimum distance between the convex hull of a first finite set of discrete points in said first swept representation and the convex hull of a second finite set of discrete points in said second representation;

and

b) wherein the nodes in said first swept representation are in one to one correspondence with the nodes in an hierarchical bounding volume representation of said first body; and

c) wherein the nodes in said second swept representation are in one to one correspondence with the nodes in an hierarchical bounding volume representation of said second body; and

d) wherein the convex hull of said first finite set of discrete points comprises the geometry of a node in said first swept representation, and the convex hull of said second finite set of discrete points is the geometry of a node in said second swept representation; and

e) wherein the steps of using the computer to transform the representation of said first body and using the computer to transform the representation of said second body are selected from the group consisting of;

i) forming nodes in said first swept representation such that the geometry of each of said nodes is the convex hull of the union of the geometry of the corresponding node in a hierarchical bounding volume representation of said first body before said first translation and said first rotation together with the geometry of the corresponding node in a hierarchical bounding volume representation of said first body after said first translation and said first rotation, and forming nodes in said second swept representation such that the geometry of each of said nodes is the convex hull of the union of the geometry of the corresponding node in a hierarchical bounding volume representation of said second body before said second translation and said second rotation together with the geometry of the corresponding node in a hierarchical bounding volume representation of said second body after said second translation and said second rotation;

ii) forming nodes in said first swept representation such that the geometry of each of said nodes is selected from the group consisting of;

convex polyhedron and convex polygon, and is a superset of the region swept by the corresponding node in a hierarchical bounding volume representation of said first body during said first translation and said first rotation, and forming nodes in said second swept representation such that the geometry of each of said nodes is selected from the group consisting of;

convex polyhedron and convex polygon, and is a superset of the region swept by the corresponding node in a hierarchical bounding volume representation of said second body during said second translation and said second rotation; and

iii) combinations thereof.

5. A method according to claim 4, wherein the step of using the computer to determine the approximate minimum distance comprises using the computer according to Gilbert'"'"'s Algorithm using a first set of points in said first swept representation and a second set of points in said second representation as inputs to Gilbert'"'"'s Algorithm.

6. A method according to claim 4, wherein said discrete points are represented in a coordinate system having an origin, and wherein the step of using the computer to determine the minimum distance between the convex hull of a first finite set of discrete points and the convex hull of a second finite set of discrete points comprises:

a) initializing the vertices of a simplex using points from the Minkowski difference set of said first set of points and said second set of points;

b) determining whether said simplex overlaps said origin;

c) determining whether a line-segment between said simplex and said origin has its non-origin vertex on the convex hull of said Minkowski difference set and is a minimum-length line-segment from said hull to the origin, and if so, determining the minimum distance to be the length of said line segment;

d) otherwise, modifying said simplex using vertices from said Minkowski difference set and repeating step (b) through (d).

7. A method according to claim 4, wherein said discrete points are represented in a coordinate system having an origin, and wherein the step of using the computer to determine the minimum distance between the convex hull of a first finite set of discrete points and the convex hull of a second finite set of discrete points comprises:

a) initializing the vertices of a first simplex from the Minkowski difference set of said first set of points and said second set of points;

b) determining a current distance vector as a minimum-length vector from said first simplex to said origin;

c) if the length of said current distance vector is less than a minimum length, then determining said minimum distance to be zero;

d) otherwise, determining an error measure from said current distance vector, said first set of points, and said second set of points, and if said error measure is sufficiently small then determining said minimum distance to be the length of said current distance vector;

e) otherwise, if possible, forming a modified simplex from said first simplex by removing all vertices from said first simplex that do not lie on the plane perpendicular to the current distance vector and passing through a point on said first simplex closest to said origin, and by adding a closer vertex from the Minkowski difference set, wherein a closer vertex is a vertex further in the direction of said current distance vector, and repeating steps (b) through (e) using said modified simplex in place of said first simplex;

f) otherwise, determining said minimum distance to be the length of the current distance vector.

8. A method according to claim 1 wherein the interaction determined is approximate collision between the region swept by the first body during the first translation concurrent with the first rotation and the second body during the second translation concurrent with the second rotation.

9. A method according to claim 8, wherein the first and second bodies are represented by unions of convex polygons and convex polyhedra.

10. A method according to claim 9,

a) wherein the step of using the computer to determine approximate collision comprises using the computer to determine collision between the convex hull of a first finite set of discrete points in said first swept representation and the convex hull of a second finite set of discrete points in said second representation;

and

b) wherein the nodes in said first swept representation are in one to one correspondence with the nodes in an hierarchical bounding volume representation of said first body; and

c) wherein the nodes in said second swept representation are in one to one correspondence with the nodes in an hierarchical bounding volume representation of said second body, and said second swept representation; and

d) wherein the convex hull of said first finite set of discrete points comprises the geometry of a node in said first swept representation, and the convex hull of said second finite set of discrete points is the geometry of a node in said second swept representation; and

e) wherein the steps of using the computer to transform the representation of said first body and using the computer to transform the representation of said second body are selected from the group consisting of;

i) forming nodes in said first swept representation such that the geometry of each of said nodes is the convex hull of the union of the geometry of the corresponding node in a hierarchical bounding volume representation of said first body before said first translation and said first rotation together with the geometry of the corresponding node in a hierarchical bounding volume representation of said first body after said first translation and said first rotation, and forming nodes in said second swept representation such that the geometry of each of said nodes is the convex hull of the union of the geometry of the corresponding node in a hierarchical bounding volume representation of said second body before said second translation and said second rotation together with the geometry of the corresponding node in a hierarchical bounding volume representation of said second body after said second translation and said second rotation;

ii) forming nodes in said first swept representation such that the geometry of each of said nodes is selected from the group consisting of;

convex polyhedron and convex polygon, and is a superset of the region swept by the corresponding node in a hierarchical bounding volume representation of said first body during said first translation and said first rotation, and forming nodes in said second swept representation such that the geometry of each of said nodes is selected from the group consisting of;

convex polyhedron and convex polygon, and is a superset of the region swept by the corresponding node in a hierarchical bounding volume representation of said second body during said second translation and said second rotation; and

iii) combinations thereof.

11. A method according to claim 10 wherein the step of using the computer to determine approximate collision comprises using the computer according to Gilbert'"'"'s Algorithm using a first set of points in said first swept representation and a second set of points in said second representation as inputs to Gilbert'"'"'s Algorithm.

12. A method according to claim 10, wherein said discrete points are represented in a coordinate system having an origin, and wherein the step of using the computer to determine collision between the convex hull of a first finite set of discrete points and the convex hull of a second finite set of discrete points comprises:

a) initializing the vertices of a simplex using points from the Minkowski difference set of said first set of points and said second set of points;

b) determining whether said simplex overlaps said origin, and if so, determining that collision occurs;

c) determining whether a line-segment between said simplex and said origin has its non-origin vertex on the convex hull of said Minkowski difference set and is a minimum-length line-segment from said convex hull to said origin, and if so, determining whether the length of said line segment is less than a minimum length, and if so, determining that collision occurs;

d) otherwise, modifying said simplex using vertices from said Minkowski difference set and repeating step (b) through (d);

e) otherwise, determining that no collision occurs.

13. A method according to claim 10, wherein said discrete points are represented in a coordinate system having an origin, and wherein the step of using the computer to determine collision between the convex hull of a first finite set of discrete points and the convex hull of a second finite set of discrete points comprises:

a) initializing the vertices of a first simplex from the Minkowski difference set of said first set of points and said second set of points;

b) determining a current distance vector as a minimum-length vector from said first simplex to said origin;

c) if the length of said current distance vector is less than a minimum length, then determining that collision occurs;

d) otherwise, determining an error measure from said current distance vector, said first set of points, and said second set of points, and if said error measure is sufficiently small then if the length of said current distance vector is less than a minimum length the determining that collision occurs, and if the length of said current distance vector is not less than a minimum length then determining that collision does not occur;

e) otherwise, if possible, forming a modified simplex from said first simplex by removing all vertices from said first simplex that do not lie on the plane perpendicular to the current distance vector and passing through a point on said first simplex closest to the origin, and by adding a closer vertex from the Minkowski difference set, wherein a closer vertex is a vertex further in the direction of said current distance vector, and repeating steps (b) through (d) using said modified simplex in place of said first simplex;

f) otherwise, determining that no collision occurs.

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.

15. The apparatus of claim 14, wherein the means for determining an interaction comprise means for determining the approximate minimum distance between said first swept representation and said second swept representation.

16. The apparatus of claim 15, wherein the means for determining the approximate minimum distance comprises means for determining the minimum distance between the convex hull of a first finite set of discrete points in said first swept representation and the convex hull of a second finite set of discrete points in said second representation,

a) wherein the means for determining the approximate minimum distance comprises means for determining the minimum distance between the convex hull of a first finite set of discrete points in said first swept representation and the convex hull of a second finite set of discrete points in said second representation;

and

b) wherein the nodes in said first swept representation are in one to one correspondence with the nodes in an hierarchical bounding volume representation of said first body; and

c) wherein the nodes in said second swept representation are in one to one correspondence with the nodes in an hierarchical bounding volume representation of said second body, and said second swept representation; and

d) wherein the convex hull of said first finite set of discrete points comprises the geometry of a node in said first swept representation, and the convex hull of said second finite set of discrete points is the geometry of a node in said second swept representation; and

e) wherein the means for transforming the representation of said first body and the means for transforming the representation of said second body are selected from the group consisting of;

i) means for forming nodes in said first swept representation such that the geometry of each of said nodes is the convex hull of the union of the geometry of the corresponding node in a hierarchical bounding volume representation of said first body before said first translation and said first rotation together with the geometry of the corresponding node in a hierarchical bounding volume representation of said first body after said first translation and said first rotation, and means for forming nodes in said second swept representation such that the geometry of each of said nodes is the convex hull of the union of the geometry of the corresponding node in a hierarchical bounding volume representation of said second body before said second translation and said second rotation together with the geometry of the corresponding node in a hierarchical bounding volume representation of said second body after said second translation and said second rotation;

ii) means for forming nodes in said first swept representation such that the geometry of each of said nodes is selected from the group consisting of;

convex polyhedron and convex polygon, and is a superset of the region swept by the corresponding node in a hierarchical bounding volume representation of said first body during said first translation and said first rotation, and means for forming nodes in said second swept representation such that the geometry of each of said nodes is selected from the group consisting of;

convex polyhedron and convex polygon, and is a superset of the region swept by the corresponding node in a hierarchical bounding volume representation of said second body during said second translation and said second rotation; and

iii) combinations thereof.

17. The apparatus of claim 16, wherein said discrete points are represented in a coordinate system having an origin, and wherein the means for determining the minimum distance between the convex hull of a first finite set of discrete points and the convex hull of a second finite set of discrete points comprises:

a) means for initializing the vertices of a simplex using points from the Minkowski difference set of said first set of points and said second set of points;

b) means for determining whether said simplex overlaps said origin;

c) means for determining whether a line-segment between said simplex and said origin has its non-origin vertex on the convex hull of said Minkowski difference set and is a minimum-length line-segment from said convex hull to said origin, and if so, determining the minimum length to be the length of said line segment;

d) means for modifying said simplex using vertices from said Minkowski difference set and repeating step (b) through (d).

18. The apparatus of claim 16, wherein said discrete points are represented in a coordinate system having an origin, and wherein the means for determining the minimum distance between the convex hull of a first finite set of discrete points and the convex hull of a second finite set of discrete points comprises:

a) means for initializing the vertices of a first simplex from the Minkowski difference set of said first set of points and said second set of points;

b) means for determining a current distance vector as a minimum-length vector from said first simplex to said origin;

c) means for determining whether the length of said current distance vector is less than a minimum length, and if so, then determining said minimum distance to be zero;

d) means for determining an error measure from said current distance vector, said first set of points, and said second set of points, and if said error measure is sufficiently small then determining said minimum distance to be the length of said current distance vector;

e) means for, if possible, forming a modified simplex from said first simplex by removing all vertices from said first simplex that do not lie on the plane perpendicular to the current distance vector and passing through a point on said first simplex closest to said origin, and by adding a closer vertex from the Minkowski difference set, wherein a closer vertex is a vertex further in the direction of said current distance vector, and repeating steps (b) through (e) using said modified simplex in place of said first simplex;

f) means for determining said minimum distance to be the length of the current distance vector if it is not possible to form a modified simplex according to (e).

19. The apparatus of claim 14, wherein the means for determining an interaction comprise means for determining approximate collision between said first swept representation and said second swept representation.

20. The apparatus of claim 19,

a) wherein the means for determining approximate collision comprises means for determining approximate collision between the convex hull of a first finite set of discrete points in said first swept representation and the convex hull of a second finite set of discrete points in said second representation,

b) wherein the nodes in said first swept representation are in one to one correspondence with the nodes in an hierarchical bounding volume representation of said first body;

and

c) wherein the nodes in said second swept representation are in one to one correspondence with the nodes in an hierarchical bounding volume representation of said second body, and said second swept representation; and

d) wherein the convex hull of said first finite set of discrete points comprises the geometry of a node in said first swept representation, and the convex hull of said second finite set of discrete points is the geometry of a node in said second swept representation; and

e) wherein the means for transforming the representation of said first body and the means for transforming the representation of said second body are selected from the group consisting of;

i) means for forming nodes in said first swept representation such that the geometry of each of said nodes is the convex hull of the union of the geometry of the corresponding node in a hierarchical bounding volume representation of said first body before said first translation and said first rotation together with the geometry of the corresponding node in a hierarchical bounding volume representation of said first body after said first translation and said first rotation, and means for forming nodes in said second swept representation such that the geometry of each of said nodes is the convex hull of the union of the geometry of the corresponding node in a hierarchical bounding volume representation of said second body before said second translation and said second rotation together with the geometry of the corresponding node in a hierarchical bounding volume representation of said second body after said second translation and said second rotation;

ii) means for forming nodes in said first swept representation such that the geometry of each of said nodes is selected from the group consisting of;

convex polyhedron and convex polygon, and is a superset of the region swept by the corresponding node in a hierarchical bounding volume representation of said first body during said first translation and said first rotation, and means for forming nodes in said second swept representation such that the geometry of each of said nodes is selected from the group consisting of;

convex polyhedron and convex polygon, and is a superset of the region swept by the corresponding node in a hierarchical bounding volume representation of said second body during said second translation and said second rotation; and

iii) combinations thereof.

21. The apparatus of claim 20, wherein said discrete points are represented in a coordinate system having an origin, and wherein the means for determining approximate collision between the convex hull of a first finite set of discrete points and the convex hull of a second finite set of discrete points comprises:

a) means for initializing the vertices of a simplex using points from the Minkowski difference set of said first set of points and said second set of points;

b) means for determining whether said simplex overlaps said origin, and if so, determining that approximate collision occurs;

c) means for determining whether a line-segment between said simplex and said origin has its non-origin vertex on the convex hull of said Minkowski difference set and is a minimum-length line-segment from said convex hull to said origin, and if so, determining whether the length of said line segment is less than a minimum length, and if so, determining that approximate collision occurs;

d) means for, if possible, modifying said simplex using vertices from said Minkowski difference set and repeating step (b) through (d);

e) means for determining that no approximate collision occurs if it is not possible to modify said simplex according to (d).

22. The apparatus of claim 20, wherein said discrete points are represented in a coordinate system having an origin, and wherein the means for determining approximate collision between the convex hull of a first finite set of discrete points and the convex hull of a second finite set of discrete points comprises:

a) means for initializing the vertices of a first simplex from the Minkowski difference set of said first set of points and said second set of points;

b) means for determining a current distance vector as a minimum-length vector from said simplex to said origin;

c) means for determining that approximate collision occurs if the length of said current distance vector is less than a minimum length;

d) means for determining an error measure from said current distance vector, said first set of points, and said second set of points, and if said error measure is sufficiently small then if the length of said current distance vector is less than a minimum length the determining that approximate collision occurs, and if the length of said current distance vector is not less than a minimum length then determining that approximate collision does not occur;

e) means for if possible, forming a modified simplex from said first simplex by removing all vertices from said first simplex that do not lie on the plane perpendicular to the current distance vector and passing through a point on said first simplex closest to said origin, and by adding a closer vertex from the Minkowski difference set, wherein a closer vertex is a vertex further in the direction of said current distance vector, and repeating steps (b) through (d) using said modified simplex in place of said first simplex;

f) means for determining said minimum distance to be the length of the current distance vector if it is not possible to form a modified simplex according to (e).