Method of real time collision detection between geometric models

• US 6,873,944 B1
• Filed: 10/11/2000
• Issued: 03/29/2005
• Est. Priority Date: 10/11/2000
• Status: Active Grant

• Current Assignee: Ford Global Technologies, LLC (Ford Motor Company)
• Original Assignee: Ford Global Technologies, LLC (Ford Motor Company)
• Inventors: Stewart, Paul J., Buttolo, Pietro
• Primary Examiner(s): Broda, Samuel
• Application Number:
  US09/686,601
• Time in Patent Office: 1,630 Days
• Field of Search: 703 1- 7, 703 21- 22, 345179-184, 345/581
• US Class Current: 703/7
• CPC Class Codes: G06F 3/016 Input arrangements with force or tactile feedback as computer generated output to the user
• CPC Class Codes: G06T 19/00 Manipulating 3D models or images for computer graphics
• CPC Class Codes: G06T 2210/21 Collision detection, intersection
• CPC Class Codes: G06T 2210/28 Force feedback

Abstract

A method of real time collision detection between geometric models includes the steps of identifying a current tracking point of a force feedback device colliding with a mesh model of the geometric model and identifying a current triangle associated with the current tracking point, wherein the force feedback device is operatively connected to a computer system. The method also includes the steps of determining a new tracking point of the force feedback device colliding with the mesh model by approximating the new tracking point from the current tracking point and the current triangle, and determining a state of the new tracking point and a known state using the new tracking point and the state of the previous tracking point, wherein the state is inside, on an edge or on a vertex of either the current triangle or a new triangle. The method further includes the steps of using the state of the new tracking point to determine if a predetermined condition is met to conclude that the new tracking point is on the current triangle or if another predetermined condition is met to conclude that the new tracking point crossed to a new triangle, wherein the new triangle is connectively associated with the current triangle.

Claims

1. A method of real time collision detection between geometric models comprising the steps of:

providing a force feedback device;

providing a computer system operatively connected to the force feedback device;

identifying a current tracking point of the force feedback device representing a first geometric model colliding with a mesh model of a second geometric model and identifying a current triangle associated with the current tracking point;

determining a new tracking point of the force feedback device relative to the mesh model by approximating the new tracking point from the current tracking point and the current triangle;

determining a state of the new tracking point using the new tracking point and the state of the previous tracking point, wherein the state is inside, on an edge or on a vertex of either the current triangle or a new triangle;

using the state of the new tracking point to determine if a predetermined condition is met to conclude that the new tracking point is on the current triangle or if another predetermined condition is met to conclude that the new tracking point crossed to a new triangle, wherein the new triangle is connectively associated with the current triangle;

determining a contact force between the first geometric model and the second geometric model; and

concluding a collision between the first geometric model and the second geometric model if the contact force is greater than zero.

2. A method as set forth in claim 1 including the step of initially assuming an inside state of the current tracking point, prior to said step of identifying a current tracking point.

3. A method as set forth in claim 1 wherein said step of determining a new tracking point includes the step of projecting the current tracking point onto a plane defined by the current triangle.

4. A method as set forth in claim 1 wherein said step of determining a state of the new tracking point includes the steps of finding an intersection between a vector connecting the previous tracking point and the current tracking point with an edge of the current triangle, and using the intersection to determine the state of the new tracking point.

5. A method as set forth in claim 1 wherein said step of using the state of the new tracking point includes the steps of:

determining if the state of the new tracking point is set to inside;

determining if a predetermined condition is met indicating the new tracking point is located inside the current triangle, if an inside state is set;

concluding the new tracking point is inside the current triangle, if the predetermined condition indicating the new tracking point is inside the current triangle is met;

determining if a predetermined condition is met indicating the new tracking point is crossing over to a new triangle, if the predetermined condition indicating the new tracking point is inside the current triangle is not met;

concluding the state of the new tracking point is inside a new triangle if the predetermined condition indicating the new tracking point is crossing over to a new triangle is met; and

continuing to find the state of the new tracking point using another edge if the predetermined condition indicating the new tracking point is crossing over to a new triangle is not met.

6. A method as set forth in claim 1 wherein said step of using the state of the new tracking point includes the steps of:

determining if the state of the new tracking point is set to an edge;

determining if a predetermined condition is met indicating the new tracking point is moving back into the current triangle, if determined that the state of the new tracking point is set to edge;

concluding the state of the new tracking point is inside the current triangle, if a predetermined condition indicating the new tracking point is moving back into the current triangle is met;

determining if a predetermined condition is met indicating that the new tracking point is on the same edge of the current triangle, if a predetermined condition indicating the new tracking point is moving back into the current triangle is not met;

concluding the state of the new tracking point is the edge of the current triangle, if a predetermined condition indicating that the new tracking point is on the same edge of the current triangle is not met;

determining if a predetermined condition is met indicating that the new tracking point is crossing over to a new triangle, if the predetermined condition that the new tracking point is still on the same edge of the current triangle is not met;

using a geometrically devised look-up table to conclude the state of the new tracking point, if a predetermined condition that the new tracking point is crossing over to a new triangle is met; and

continuing to find the new tracking point using another edge if the predetermined condition that the new tracking point is crossing over to a new triangle is not met.

7. A method as set forth in claim 1 wherein said step of using the state of the new tracking point includes the steps of:

determining if the state of the new tracking point is set to a vertex;

determining if a predetermined condition is met indicating the new tracking point is moving back into the current triangle connected with the vertex, if determined that the state of the new tracking point is a vertex;

concluding the state of the new tracking point is inside the current triangle, if a predetermined condition indicating the new tracking point is moving back into the current triangle is met;

determining if a predetermined condition is met indicating that the new tracking point is moving from the vertex to an edge of the current triangle, if a predetermined condition indicating the new tracking point is moving back into the current triangle is not met;

concluding the state of the new tracking point is on the edge of the current triangle, if a predetermined condition indicating that the new tracking point is moving from the vertex to an edge of the current triangle is met;

determining if a predetermined condition is met indicating that the new tracking point is on an edge of a new triangle, if the predetermined condition that the new tracking point is moving from the vertex to an edge of the current triangle is not met;

concluding the state of the new tracking point is on the edge of the current triangle, if a predetermined condition that the new tracking point is on an edge of a new triangle is met, and continuing to find the new tracking point using another edge;

determining if a predetermined condition is met that the new tracking point is crossing onto a vertex of a new triangle, if a predetermined condition that the new tracking point is on an edge of a new triangle is not met;

concluding that the state of the new tracking point is on the vertex of the new triangle, if a predetermined condition that the new tracking point is crossing onto a vertex of a new triangle is met, and continuing to find the new tracking point;

determining if a predetermined condition is met to check a new edge of the current triangle, if a predetermined condition that the new tracking point is crossing onto a vertex of a new triangle is not met;

concluding that the state of the new tracking point is on the vertex of the current triangle, if a predetermined condition to check a new edge of the current triangle is not met; and

concluding that the state of the new tracking point is an edge of the current triangle if a predetermined condition to check a new edge of the current triangle is met and continuing to find the new tracking point.

8. A method as set forth in claim 1 wherein the step of determining the contact force comprises calculating a contact force of the new tracking point penetrating the mesh model and applying the force through the force feedback device to replicate a feeling of contact with a rigid object.

9. A method of real time collision detection with a geometric model of a vehicle comprising the steps of:

providing a force feedback device;

providing a computer system operatively connected to the force feedback device;

identifying a current tracking point of the force feedback device representing a point of an object colliding with a mesh model of the vehicle and identifying a current triangle associated with the current tracking point;

determining a new tracking point of the force feedback device relative to the mesh model by projecting the current tracking point onto a plane defined by the current triangle;

determining a state of the new tracking point relative to the current triangle or a new triangle by finding an intersection between a vector connecting the previous tracking point and the current tracking point with an edge of the current triangle, and using the intersection to determine the state of the new tracking point, wherein the state is inside, on an edge or on a vertex of either the current triangle or a new triangle;

using the state of the new tracking point to determine if a predetermined condition is met concluding the new tracking point is on the current triangle or if another predetermined condition is met to concluding the new tracking point is crossing over to a new triangle, wherein the new triangle is connectively associated with the current triangle;

determining a contact force between the new tracking point and the mesh model; and

concluding a collision between the object and the mesh model if the contact force is greater than zero.

10. A method as set forth in claim 9 wherein said step of using the state of the new tracking point includes the steps of:

determining if the state of the new tracking point is set to inside;

determining if a predetermined condition is met indicating the new tracking point is located inside the current triangle, if an inside state is set;

concluding the new tracking point is inside the current triangle, if the predetermined condition indicating the new tracking point is inside the current triangle is met;

determining if a predetermined condition is met indicating the new tracking point is crossing over to a new triangle, if the predetermined condition indicating the new tracking point is inside the current triangle is not met;

concluding the state of the new tracking point is inside a new triangle if the predetermined condition indicating the new tracking point is crossing over to a new triangle is met; and

continuing to find the state of the new tracking point using another edge if the predetermined condition indicating the new tracking point is crossing over to a new triangle is not met.

11. A method as set forth in claim 9 wherein said step of using the state of the new tracking point includes the steps of:

determining if the state of the new tracking point is set to an edge;

determining if a predetermined condition is met indicating the new tracking point is moving back into the current triangle, if determined that the state of the new tracking point is set to edge;

concluding the state of the new tracking point is inside the current triangle, if a predetermined condition indicating the new tracking point is moving back into the current triangle is met;

determining if a predetermined condition is met indicating that the new tracking point is on the same edge of the current triangle, if a predetermined condition indicating the new tracking point is moving back into the current triangle is not met;

concluding the state of the new tracking point is the edge of the current triangle, if a predetermined condition indicating that the new tracking point is on the same edge of the current triangle is not met;

determining if a predetermined condition is met indicating that the new tracking point is crossing over to a new triangle, if the predetermined condition that the new tracking point is still on the same edge of the current triangle is not met;

using a geometrically derived look-up table to conclude the state of the new tracking point, if a predetermined condition that the new tracking point is crossing over to a new triangle is met; and

continuing to find the new tracking point using another edge if the predetermined condition that the new tracking point is crossing over to a new triangle is not met.

12. A method as set forth in claim 9 wherein said step of using the state of the new tracking point includes the steps of:

determining if the state of the new tracking point is set to a vertex;

determining if a predetermined condition is met indicating the new tracking point is moving back into the current triangle connected with the vertex, if determined that the state of the new tracking point is a vertex;

concluding the state of the new tracking point is inside the current triangle, if a predetermined condition indicating the new tracking point is moving back into the current triangle is met;

determining if a predetermined condition is met indicating that the new tracking point is moving from the vertex to an edge of the current triangle, if a predetermined condition indicating the new tracking point is moving back into the current triangle is not met;

concluding the state of the new tracking point is on the edge of the current triangle, if a predetermined condition indicating that the new tracking point is moving from the vertex to an edge of the current triangle is met;

determining if a predetermined condition is met indicating that the new tracking point is on an edge of a new triangle, if the predetermined condition that the new tracking point is moving from the vertex to an edge of the current triangle is not met;

concluding the state of the new tracking point is on the edge of the current triangle, if a predetermined condition that the new tracking point is on an edge of a new triangle is met, and continuing to find the new tracking point using another edge;

determining if a predetermined condition is met that the new tracking point is crossing onto a vertex of a new triangle, if a predetermined condition that the new tracking point is on an edge of a new triangle is not met;

concluding that the state of the new tracking point is on the vertex of the new triangle, if a predetermined condition that the new tracking point is crossing onto a vertex of a new triangle is met, and continuing to find the new tracking point;

determining if a predetermined condition is met to check a new edge of the current triangle, if a predetermined condition that the new tracking point is crossing onto a vertex of a new triangle is not met;

concluding that the state of the new tracking point is on the vertex of the current triangle, if a predetermined condition to check a new edge of the current triangle is not met; and

concluding that the state of the new tracking point is an edge of the current triangle if a predetermined condition to check a new edge of the current triangle is met and continuing to find the new tracking point.

13. A method as set forth in claim 9 wherein said step of determining comprises calculating a contact force of the new tracking point penetrating the mesh model and applying the force through the force feedback device to replicate a feeling of contact with a rigid object.

14. A method of real time collision detection and force feedback with a geometric model of a vehicle comprising the steps of:

providing a force feedback device;

providing a computer system operatively connected to the force feedback device;

identifying a current tracking point of the force feedback device representing a point of a rigid object colliding with a mesh model of the vehicle and identifying a current triangle associated with the current tracking point;

determining a new tracking point of the force feedback device relative to the mesh model by projecting the current tracking point onto a plane defined by the current triangle;

determining a state of the new tracking point relative to the current triangle or a new triangle by finding an intersection between a vector connecting the previous tracking point and the current tracking point with an edge of the current triangle, and using the intersection to determine the state of the new tracking point, wherein the state is inside, on an edge or on a vertex of either the current triangle or a new triangle;

using the state of the new tracking point to determine if a predetermined condition is met concluding the new tracking point is on the current triangle or if another predetermined condition is met to concluding the new tracking point is crossing over to a new triangle, wherein the new triangle is connectively associated with the current triangle;

determining a contact force between the new tracking point and the mesh model by calculating a contact force of the new tracking point; and

concluding a collision if the contact force is greater than zero for penetrating the mesh model and applying the force through the force feedback device to replicate a feeling of contact with the rigid object.

15. A method as set forth in claim 14 wherein said step of using the state of the new tracking point includes the steps of:

determining if the state of the new tracking point is set to inside;

determining if a predetermined condition is met indicating the new tracking point is located inside the current triangle, if an inside state is set;

concluding the new tracking point is inside the current triangle, if the predetermined condition indicating the new tracking point is inside the current triangle is met;

determining if a predetermined condition is met indicating the new tracking point is crossing over to a new triangle, if the predetermined condition indicating the new tracking point is inside the current triangle is not met;

concluding the state of the new tracking point is inside a new triangle if the predetermined condition indicating the new tracking point is crossing over to a new triangle is met; and

continuing to find the state of the new tracking point using another edge if the predetermined condition indicating the new tracking point is crossing over to a new triangle is not met.

16. A method as set forth in claim 14 wherein said step of using the state of the new tracking point includes the steps of:

determining if the state of the new tracking point is set to an edge;

determining if a predetermined condition is met indicating the new tracking point is moving back into the current triangle, if determined that the state of the new tracking point is set to edge;

concluding the state of the new tracking point is inside the current triangle, if a predetermined condition indicating the new tracking point is moving back into the current triangle is met;

determining if a predetermined condition is met indicating that the new tracking point is on the same edge of the current triangle, if a predetermined condition indicating the new tracking point is moving back into the current triangle is not met;

concluding the state of the new tracking point is the edge of the current triangle, if a predetermined condition indicating that the new tracking point is on the same edge of the current triangle is not met;

determining if a predetermined condition is met indicating that the new tracking point is crossing over to a new triangle, if the predetermined condition that the new tracking point is still on the same edge of the current triangle is not met;

using a geometrically derived look-up table to conclude the state of the new tracking point, if a predetermined condition that the new tracking point is crossing over to a new triangle is met; and

continuing to find the new tracking point using another edge if the predetermined condition that the new tracking point is crossing over to a new triangle is not met.

17. A method as set forth in claim 14 wherein said step of using the state of the new tracking point includes the steps of:

determining if the state of the new tracking point is set to a vertex;

determining if a predetermined condition is met indicating the new tracking point is moving back into the current triangle connected with the vertex, if determined that the state of the new tracking point is a vertex;

concluding the state of the new tracking point is inside the current triangle, if a predetermined condition indicating the new tracking point is moving back into the current triangle is met;

determining if a predetermined condition is met indicating that the new tracking point is moving from the vertex to an edge of the current triangle, if a predetermined condition indicating the new tracking point is moving back into the current triangle is not met;

concluding the state of the new tracking point is on the edge of the current triangle, if a predetermined condition indicating that the new tracking point is moving from the vertex to an edge of the current triangle is met;

determining if a predetermined condition is met indicating that the new tracking point is on an edge of a new triangle, if the predetermined condition that the new tracking point is moving from the vertex to an edge of the current triangle is not met;

concluding the state of the new tracking point is on the edge of the current triangle, if a predetermined condition that the new tracking point is on an edge of a new triangle is met, and continuing to find the new tracking point using another edge;

determining if a predetermined condition is met that the new tracking point is crossing onto a vertex of a new triangle, if a predetermined condition that the new tracking point is on an edge of a new triangle is not met;

concluding that the state of the new tracking point is on the vertex of the new triangle, if a predetermined condition that the new tracking point is crossing onto a vertex of a new triangle is met, and continuing to find the new tracking point;

determining if a predetermined condition is met to check a new edge of the current triangle, if a predetermined condition that the new tracking point is crossing onto a vertex of a new triangle is not met;

concluding that the state of the new tracking point is on the vertex of the current triangle, if a predetermined condition to check a new edge of the current triangle is not met; and

concluding that the state of the new tracking point is an edge of the current triangle if a predetermined condition to check a new edge of the current triangle is met and continuing to find the new tracking point.

18. A method as set forth in claim 14 wherein said step of calculating the contact force of the new tracking point includes the steps of determining if the state is set to inside and modeling the new tracking point as a uniformly distributed spring and damper mesh to determine the force if the state is set to inside.

19. A method as set forth in claim 14 wherein said step of calculating the contact force of the new tracking point includes the steps of determining if the state is set to vertex, and modeling the new tracking point as a gravitational sphere to determined the force if the state is set to vertex.

20. A method as set forth in claim 14 wherein said step of calculating a force of the new tracking point penetrating the mesh model includes the steps of:

determining if the state is set to edge;

determining if the new tracking point is moving to free space if the state is set to edge;

setting the force equal to zero if the new tracking point is moving to free space; and

determining if the new tracking point is stationary on the edge or sliding along a facet connected with the edge if the new tracking point is not moving to free space, wherein the force is determined from its position on either the facet or the edge.