System and method for avoiding collision between vector and solid objects

• US 6,049,756 A
• Filed: 11/12/1997
• Issued: 04/11/2000
• Est. Priority Date: 11/12/1997
• Status: Expired due to Fees

• Current Assignee: Lockheed Martin Corporation (Martin Marietta Corporation)
• Original Assignee: Lockheed Martin Corporation (Martin Marietta Corporation)
• Inventors: Libby, Vibeke
• Primary Examiner(s): Cuchlinski, Jr., William A.
• Assistant Examiner(s): Arthur, Gertrude
• Application Number:
  US08/968,994
• Time in Patent Office: 881 Days
• Field of Search: 701/25, 701/26, 701/28, 701/209, 701/206, 701/226, 701/300, 701/301, 701/302, 340/436, 318/587
• US Class Current: 701/301
• CPC Class Codes: G06T 19/003 Navigation within 3D models or images
• CPC Class Codes: G06T 2210/21 Collision detection, intersection

Abstract

An apparatus for analyzing a specified path A-B with respect to a specified obstacle determines if the path intersects the obstacle and determines a collision avoidance path when the path is determined to intersect the obstacle. The apparatus is preferably a dedicated path analyzer that provides high speed path analysis support to a host computer performing navigation functions. The path analyzer includes a collision detector and a collision avoidance path generator. The path analyzer receives from the host computer coordinates representing the specified path'"'"'s first and second endpoints (A and B) in three dimensional space and the specified obstacle'"'"'s physical extent. The collision detector generates a preliminary result signal indicating whether the specified path does not intercept the specified obstacle, unavoidably intercepts the specified obstacle, or avoidably intercepts the specified obstacle. When the preliminary result signal indicates that the specified path avoidably intercepts the specified obstacle, the collision avoidance path generator selecting a vertex (C) of a parallelepiped corresponding to the specified obstacle'"'"'s physical extent, such that a modified path A-C-B from the first specified path endpoint to the selected vertex to the second specified path endpoint circumnavigates the obstacle. The path analyzer returns signals to the host computer representing the preliminary result signal and, when the preliminary result signal indicates that the specified path avoidably intercepts the specified obstacle, the selected vertex.

Claims

1. A path analyzer, comprising:

a collision detector for receiving coordinates representing a specified path'"'"'s first and second endpoints (A, B) in three dimensional space and a specified obstacle'"'"'s physical extent and for generating a preliminary result signal indicating whether the specified path does not intercept the specified obstacle, unavoidably intercepts the specified obstacle, or avoidably intercepts the specified obstacle; and

a collision avoidance path generator, activated when the preliminary result signal indicates that the specified path avoidably intercepts the specified obstacle, the collision avoidance path generator including apparatus for selecting a vertex (C) of a predefined geometric shape corresponding to the specified obstacle'"'"'s physical extent, such that a modified path A-C-B from the first specified path endpoint to the selected vertex to the second specified path endpoint circumnavigates the obstacle.

2. The path analyzer of claim 1, wherein

the collision avoidance path generator includes:

a path endpoint classifier for classifying each of the first and second path endpoints with respect to the specified object so as to produce first and second path endpoint sector values, each sector value indicating which of N sectors of space, defined with respect to the specified object, the corresponding path endpoint is located in, where N is an integer larger than 4; and

a lookup table, addressed in accordance with the first and second path endpoint sector values, for returning a first vertex selection value; and

the selected vertex corresponds to the returned first vertex selection value when predefined vertex selection criteria are satisfied.

3. The path analyzer of claim 1, wherein

the collision avoidance path generator includes:

a path endpoint classifier for classifying each of the first and second path endpoints with respect to the specified object so as to produce first and second path endpoint sector values, each sector value indicating which of N sectors of space, defined with respect to the specified object, the corresponding path endpoint is located in, where N is an integer larger than 9; and

a lookup table, addressed in accordance with the first and second path endpoint sector values, for returning a first vertex selection value; and

the selected vertex corresponds to the returned first vertex selection value when predefined vertex selection criteria are satisfied.

4. The path analyzer of claim 1, wherein

the collision avoidance path generator includes:

a path endpoint classifier for classifying each of the first and second path endpoints with respect to the specified object so as to produce first and second path endpoint sector values, each sector value indicating which of N sectors of space, defined with respect to the specified object, the corresponding path endpoint is located in, where N is an integer larger than 9;

a lookup table, addressed in accordance with the first and second path endpoint sector values, for returning a first vertex selection value and a return code, wherein the selected vertex corresponds to the returned first vertex selection value when the return code has a first predefined value; and

an ambiguity resolver circuit, activated when the return code is any one of a predefined set of operation codes, each of which corresponds to a respective ambiguity resolution computation, for performing the ambiguity resolution computation corresponding to the return code returned by the lookup table so as to generate a second vertex selection value;

wherein the selected vertex corresponds to the second vertex selection value when the return code is any one of the predefined set of operation codes.

5. The path analyzer of claim 4, wherein the ambiguity resolver circuit includes:

a math unit for performing mathematical and logical operations; and

a state machine for directing the math unit to perform a sequence of mathematical and logical operations on values corresponding to the coordinates of the specified path endpoints and the specified obstacle'"'"'s physical extent, the sequence of mathematical and logical operations corresponding to the return code returned by the lookup table.

6. The path analyzer of claim 5, wherein

the predefined geometric shape is a parallelepiped surrounding the specified obstacle;

and

N is equal to 27 and the 27 sectors of space correspond to those shown in FIG. 2.

7. The path analyzer of claim 1, wherein the predefined geometric shape is a parallelepiped surrounding the specified obstacle.

8. A method of analyzing a path, comprising

receiving from a host computer coordinates representing a specified path'"'"'s first and second endpoints (A, B) in three dimensional space and a specified obstacle'"'"'s physical extent;

generating a preliminary result signal indicating whether the specified path does not intercept the specified obstacle, unavoidably intercepts the specified obstacle, or avoidably intercepts the specified obstacle; and

when the preliminary result signal indicates that the specified path avoidably intercepts the specified obstacle, selecting a vertex (C) of a predefined geometric shape corresponding to the specified obstacle'"'"'s physical extent, such that a modified path A-C-B from the first specified path endpoint to the selected vertex to the second specified path endpoint circumnavigates the obstacle; and

returning signals to the host computer representing the preliminary result signal and, when the preliminary result signal indicates that the specified path avoidably intercepts the specified obstacle, the selected vertex.

9. The path analysis method of claim 8, wherein

the vertex selecting step includes

classifying each of the first and second path endpoints with respect to the specified object so as to produce first and second path endpoint sector values, each sector value indicating which of N sectors of space, defined with respect to the specified object, the corresponding path endpoint is located in, where N is an integer larger than 4;

addressing a lookup table in accordance with the first and second path endpoint sector values so as to retrieve a first vertex selection value;

wherein the selected vertex corresponds to the returned first vertex selection value wherein predefined vertex selection criteria are satisfied.

10. The path analysis method of claim 8, wherein

the vertex selecting step includes

classifying each of the first and second path endpoints with respect to the specified object so as to produce first and second path endpoint sector values, each sector value indicating which of N sectors of space, defined with respect to the specified object, the corresponding path endpoint is located in, where N is an integer larger than 9;

addressing a lookup table in accordance with the first and second path endpoint sector values so as to retrieve a first vertex selection value;

wherein the selected vertex corresponds to the returned first vertex selection value wherein predefined vertex selection criteria are satisfied.

11. The path analysis method of claim 8, wherein

the vertex selecting step includes

classifying each of the first and second path endpoints with respect to the specified object so as to produce first and second path endpoint sector values, each sector value indicating which of N sectors of space, defined with respect to the specified object, the corresponding path endpoint is located in, where N is an integer larger than 9;

addressing a lookup table in accordance with the first and second path endpoint sector values so as to retrieve a first vertex selection value and a return code;

when the return code is any one of a predefined set of operation codes, each of which corresponds to a respective ambiguity resolution computation, performing the ambiguity resolution computation corresponding to the return code returned by the lookup table so as to generate a second vertex selection value;

wherein the selected vertex corresponds to the second vertex selection value when the return code is any one of the predefined set of operation codes.

12. The path analysis method of claim 11, wherein the ambiguity resolution computation performing step includes:

directing a math unit, distinct from any mathematical computation circuitry in the host computer, to perform a sequence of mathematical and logical operations on values corresponding to the coordinates of the specified path endpoints and the specified obstacle'"'"'s physical extent, the sequence of mathematical and logical operations corresponding to the return code returned by the lookup table.

13. The path analysis method of claim 12, wherein

the predefined geometric shape is a parallelepiped surrounding the specified obstacle;

and

N is equal to 27 and the 27 sectors of space correspond to those shown in FIG. 2.

14. The path analysis method of claim 8, wherein the predefined geometric shape is a parallelepiped surrounding the specified obstacle.

15. A path analyzer, comprising:

a collision detector for receiving coordinates representing a specified path'"'"'s first and second endpoints (A, B) in three dimensional space and a specified obstacle'"'"'s physical extent and for generating a preliminary result signal indicating whether the specified path intercepts the specified obstacle; and

a collision avoidance path generator, activated when the preliminary result signal indicates that the specified path avoidably intercepts the specified obstacle, the collision avoidance path generator including apparatus for selecting a vertex (C) of a predefined geometric shape corresponding to the specified obstacle'"'"'s physical extent, such that a modified path from the first specified path endpoint (A) to the second specified path endpoint (B) that passes through the selected vertex C circumnavigates the obstacle.

16. The path analyzer of claim 15, wherein

the collision avoidance path generator includes:

a path endpoint classifier for classifying each of the first and second path endpoints with respect to the specified object so as to produce first and second path endpoint sector values, each sector value indicating which of N sectors of space, defined with respect to the specified object, the corresponding path endpoint is located in, where N is an integer larger than 4;

a lookup table, addressed in accordance with the first and second path endpoint sector values, for returning a first vertex selection value and a return code, wherein the selected vertex corresponds to the returned first vertex selection value when the return code has a first predefined value; and

an ambiguity resolver circuit, activated when the return code is any one of a predefined set of operation codes, each of which corresponds to a respective ambiguity resolution computation, for performing the ambiguity resolution computation corresponding to the return code returned by the lookup table so as to generate a second vertex selection value;

wherein the selected vertex corresponds to the second vertex selection value when the return code is any one of the predefined set of operation codes.

17. A method of analyzing a path, comprising

receiving from a host computer coordinates representing a specified path'"'"'s first and second endpoints (A, B) in three dimensional space and a specified obstacle'"'"'s physical extent;

generating a preliminary result signal indicating whether the specified path intercepts the specified obstacle; and

when the preliminary result signal indicates that the specified path avoidably intercepts the specified obstacle, selecting a vertex (C) of a predefined geometric shape corresponding to the specified obstacle'"'"'s physical extent, such that a modified path from the first specified path endpoint (A) to the selected vertex to the second specified path endpoint (B) that passes through the selected vertex (C) circumnavigates the obstacle; and

returning signals to the host computer representing the preliminary result signal and, when the preliminary result signal indicates that the specified path avoidably intercepts the specified obstacle, the selected vertex.

18. The path analysis method of claim 17, wherein

the vertex selecting step includes

classifying each of the first and second path endpoints with respect to the specified object so as to produce first and second path endpoint sector values, each sector value indicating which of N sectors of space, defined with respect to the specified object, the corresponding path endpoint is located in, where N is an integer larger than 4;

addressing a lookup table in accordance with the first and second path endpoint sector values so as to retrieve a first vertex selection value and a return code;

when the return code is any one of a predefined set of operation codes, each of which corresponds to a respective ambiguity resolution computation, performing the ambiguity resolution computation corresponding to the return code returned by the lookup table so as to generate a second vertex selection value;

wherein the selected vertex corresponds to the second vertex selection value when the return code is any one of the predefined set of operation codes.