Eigenvalue quadric surface method for determining when two ellipsoids share common volume for use in spatial collision detection and avoidance

• US 6,694,283 B2
• Filed: 05/29/2002
• Issued: 02/17/2004
• Est. Priority Date: 05/29/2002
• Status: Active Grant

• Current Assignee: Aerospace Corporation
• Original Assignee: Aerospace Corporation
• Inventors: Alfano, Salvatore, Chan, F. Kenneth, Greer, Meredith Lynn
• Primary Examiner(s): Barlow, John
• Assistant Examiner(s): PRETLOW, DEMETRIUS R
• Application Number:
  US10/157,432
• Publication Number:
  US 20030225546A1
• Time in Patent Office: 629 Days
• Field of Search: 702/150, 702/127, 702/51, 342/36, 342/41
• US Class Current: 702/150
• CPC Class Codes: G06T 7/70 Determining position or orientation of objects or cameras camera calibration G06T7/80
• CPC Class Codes: G08G 5/04 Anti-collision systems
• CPC Class Codes: G08G 5/045 Navigation or guidance aids, e.g. determination of anti-collision manoeuvers radar or analogous systems specially adapted for anti-collision between aircraft G01S13/933

Abstract

A computationally efficient analytical method determines when two quadric surfaces, such as ellipsoids surfaces, share the same volume by adding an extra dimension to the solution space for providing extradimensional product matrices defining degenerate quadric surfaces. The method then examines computed eigenvalues associated the product matrices to determine when the two quadric surfaces share the same volume or when surface projected areas based on viewing angle share the same area. The method provides direct share volume results based on comparisons of the eigenvalues that can be rapidly computed. The method can be use for collision avoidance detection where the objects are modeled by quadric surfaces.

Claims

1. A method for determining spatial coincidence between a primary object and a secondary object, the method comprising the steps of,

receiving a primary object covariance matrix,

receiving a secondary object covariance matrix,

receiving a primary object position vector,

receiving a secondary object position vector,

extending by one dimension the primary object covariance matrix into an extended primary object covariance matrix,

inverting the secondary object covariance matrix into an inverted secondary object covariance matrix,

subtracting the primary object position vector from the secondary position vector for providing a relative position vector,

extending the secondary object inverted covariance matrix by the difference position vector into an extended object B covariance matrix,

multiplying the extended secondary object covariance matrix by the extended primary object covariance matrix for providing a product covariance matrix,

computing eigenvalues of the product covariance matrix,

examining the eigenvalues for determining the spatial coincidence of primary object and the secondary object, and

acting upon the determination of the determining step.

2. The method of claim 1 wherein primary object and secondary object are spaceborne objects, and wherein the acting step is a maneuvering step for maneuvering the primary object to avoid collision with the secondary object.

3. The method of claim 1 wherein primary object and secondary object are airborne objects, and wherein the acting step is a maneuvering step for maneuvering the secondary object to avoid collision of primary object with the secondary object.

4. The method of claim 1 wherein the primary and secondary objects are selected from the group consisting of points, lines, areas, surfaces, or volumes.

5. The method of claim 1 wherein the covariance matrices are 3×

3 and the extradimensional matrices are 4×

4.

6. The method of claim 1 wherein,

the objects are virtual objects stored in a computer system.

7. The method of claim 1 wherein the primary object is a primary ellipsoid, the secondary object is a secondary ellipsoid, and the examining step determines:

when two eigenvalues are negative real different eigenvalues, then the primary and secondary ellipsoids shared no volume in common;

when the two eigenvalues are negative real identical eigenvalues, then the primary and secondary ellipsoids shared a single point in space where the primary ellipsoid just touches the secondary ellipsoid at a side of the secondary ellipsoid nearest an origin of the primary ellipsoid;

when the two eigenvalues are complex conjugates, the surfaces of the primary and secondary ellipsoids are intersected by more than one point; and

when the two eigenvalues are positive real identical eigenvalues, then the primary and secondary ellipsoids shared volume is a single point in space where the primary ellipsoid just touches the secondary ellipsoid on a side of the secondary ellipsoid farthest from the origin of the primary ellipsoid.

8. The method of claim 1 wherein,

the primary object is a primary virtual ellipsoid,

the secondary object is a secondary virtual ellipsoid, and

in the examining step:

when two eigenvalues are negative real different eigenvalues, then the two virtual ellipsoids shared no volume in common;

when the two eigenvalues are negative real identical eigenvalues, then the virtual ellipsoids shared a single point in space where the primary virtual ellipsoid just touches the secondary virtual ellipsoid at a side of the secondary virtual ellipsoid nearest an origin of the primary virtual ellipsoid;

when the two eigenvalues are complex conjugates, the surfaces of the virtual ellipsoids are intersected by more than one point; and

when the two eigenvalues are positive real identical eigenvalues, then the virtual ellipsoids shared volume is a single point in space where the primary virtual ellipsoid just touches the secondary virtual ellipsoid on a side of the secondary virtual ellipsoid farthest from the origin of the primary virtual ellipsoid.

9. The method of claim 8 wherein the examining step further determines:

when all of the computed eigenvalues are positive real different eigenvalues, then the primary virtual ellipsoid is penetrated on two sides of the primary virtual ellipsoid by the secondary virtual ellipsoid, or then the primary virtual ellipsoid has engulfed the secondary virtual ellipsoid.

10. The method of claim 1 wherein one of the objects is in space with thrusters, and in the taking action step,

the thrusters manipulate the one object to avoid collision of the objects.

11. The method of claim 1 wherein one of the objects is manipulated by robotics, and in the taking action step,

the robotics manipulate the one of the primary or secondary objects to avoid collision of the primary and secondary objects.

12. The method of claim 1 wherein the spatial coincidence is virtual spatial coincidence realized in a computing device displaying the virtual spatial coincidence.

13. The method of claim 1 wherein the primary and secondary objects are virtual primary and secondary objects, the spatial coincidence is virtual spatial coincidence, the virtual primary and secondary objects represented in a computing device for displaying virtual objects, and the primary and secondary position vectors both indicate zero velocity of the virtual primary and secondary objects.

14. The method of claim 1 wherein,

the primary and secondary objects are three dimensional,

the primary and secondary covariance matrices and position vectors are three dimensional,

the assemble steps further comprise the steps of,

rotating the extradimensional primary and secondary covariance matrices as rotated extradimensional primary and secondary covariance matrices for viewing the primary and secondary objects through a line of sight, and

reducing the rotated extradimensional primary and secondary covariance matrices by one dimension into reduced rotated extradimensional primary and secondary covariance matrices, the multiplying steps multiplies the reduced rotated extradimensional primary and secondary covariance matrices.

15. The method of claim 14 wherein,

the primary and secondary objects are three dimensional,

the primary and secondary covariance matrices are three dimensional,

the extradimensional primary and secondary covariance matrices are four dimensional, and

the reduced rotated extradimensional primary and secondary covariance matrices are three dimensional.

16. A method for determining spatial coincidence between a primary object and a secondary object, the method comprising the steps of,

receiving a primary object 3×

3 covariance matrix,

receiving a secondary object 3×

3 covariance matrix,

receiving a primary 3×

3 position vector,

receiving an object 3×

3 position vector,

extending the primary object covariance matrix into an extended primary object 4×

4 covariance matrix with a one in the 4−

4 position, zero is inserted in the fourth row and column with a minus one in the fourth-fourth position,

inverting the secondary object 3×

3 covariance matrix into an inverted secondary object 3×

3 covariance matrix,

subtracting the primary object 3×

3 position vector from the secondary 3×

1 position vector for providing a 3×

1 relative position vector,

extending the inverted secondary object 3×

3 covariance matrix by the relative 3×

3 position vector into an extended secondary object 4×

4 covariance matrix where zero is inserted in the fourth row and column with a minus one in the fourth-fourth position,

multiplying the extended secondary object 4×

4 covariance matrix the inverted covariance matrix by the extended primary object 4×

4 covariance matrix for providing a product 4×

4 covariance matrix,

computing four eigenvalues of the product 4×

4 covariance matrix,

examining the four eigenvalues for determining when the four eigenvalues indicate spatial coincidence of the primary object with the secondary object, and

acting upon the determination of the determining step.