Method of real-time collision detection between solid geometric models

• US 20040010346A1
• Filed: 07/11/2002
• Published: 01/15/2004
• Est. Priority Date: 07/11/2002
• Status: Active Grant

• Current Assignee: Ford Global Technologies, LLC (Ford Motor Company)
• Original Assignee: Ford Global Technologies, LLC (Ford Motor Company)
• Inventors: Stewart, Paul Joseph, Buttolo, Pietro
• Granted Patent: US 7,191,104 B2
• Time in Patent Office: Days
• US Class Current: 700/255
• CPC Class Codes: A63F 2300/1037 being specially adapted for converting control signals received from the game device into a haptic signal, e.g. using force feedback
• CPC Class Codes: A63F 2300/643 by determining the impact between objects, e.g. collision detection
• CPC Class Codes: G06F 3/011 Arrangements for interaction with the human body, e.g. for user immersion in virtual reality blind teaching G09B21/00
• 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/20 Editing of 3D images, e.g. changing shapes or colours, aligning objects or positioning parts
• CPC Class Codes: G06T 2210/21 Collision detection, intersection
• CPC Class Codes: G06T 2210/28 Force feedback
• CPC Class Codes: G06T 2219/2016 Rotation, translation, scaling

Abstract

A system and method of real-time collision detection between solid geometric modes is provided. The system includes a computer system and at least one computer-generated geometric model stored in the memory of the computer system. The system also includes a haptic device in communication with the computer system, and the haptic device includes a haptic end effector for transmitting information between a user and the geometric model. The method includes the steps of representing one object from the geometric model as a point cloud and another object as a mesh, and at least one of the objects is moving, and partitioning the mesh into an organized data structure. The method also includes the steps of identifying a constraint set and identifying a collision set. The method further includes the steps of rendering the constraint set by moving the colliding objects so that the set of active points do not penetrate into the mesh, and providing force feedback to a user through a haptic device relative to how much the two objects had to be moved to satisfy the constraints.

Claims

1. A method of real-time collision detection between solid geometric models comprising:

a computer system, wherein said computer system includes a memory, a processor, a user input device and a display device;

at least one computer-generated geometric model stored in the memory of said computer system;

a haptic device operatively in communication with said computer system, wherein said haptic device includes a haptic end effector for transmitting information between a user and said geometric model;

wherein a geometric object from said geometric model is represented as a point cloud and another geometric object from said geometric model as a mesh and at least one of the objects is moving, the mesh is partitioned into an organized data structure, a constraint set is identified by selecting actively colliding points from the point cloud, a collision set is identified by tracking points in the point cloud and selecting points that penetrate the mesh, the constraint set is rendered by moving the colliding objects so that none of its points penetrate into the mesh, and force feedback is provided to the user through said haptic device relative to how much the objects had to be moved to satisfy the constraints.

2. A system as set forth in claim 1 including a virtual reality display mechanism operatively in communication with said computer system and said haptic device so that the user can see said objects in a virtual environment.

3. A system as set forth in claim 1 wherein said haptic device tactilely conveys restricting penetration of one object into the other object to the user.

4. A method of real-time collision detection between solid geometric models, said method comprising the steps of:

representing one object from the geometric model as a point cloud and another object from the geometric model as a mesh, wherein at least one of the objects is moving;

partitioning the mesh into an organized data structure;

identifying a constraint set, wherein the constraint set is a minimum set of actively colliding points from the point cloud;

identifying a collision set, wherein the collision set includes points from the point cloud colliding with the partitioned mesh;

rendering the constraint set, so that none of its points penetrate into the mesh; and

providing force feedback to a user through a haptic device relative to the position of the two objects before and after the constraint set is rendered.

5. A method as set forth in claim 4 including the step of continuously tracking a position of at least one of the objects.

6. A method as set forth in claim 4 wherein said step of partitioning the mesh includes the steps of partitioning the mesh into an OctTree data structure by:

determining a tightest aligned bounding box containing the mesh wherein mesh includes a vertex, or element or triangle;

dividing the aligned bounding box into subvolumes, with each subvolume containing a portion of the mesh;

selecting a vertex or element or triangle from the mesh as a current element;

selecting a subvolume as a current volume;

determining a child subvolume of the current volume that encloses the current element;

adding the current element to the child subvolume;

determining if there are more than a predetermined number of vertices, or elements or triangles in the child subvolume, and further subdividing the child subvolume to distribute excess vertices or elements or triangles within respective subvolumes that enclose the vertices or elements or triangles; and

continuing to recursively distribute the vertices or elements or triangles of the mesh to subvolumes within the aligned bounding box until all of the vertices, elements or triangles are allocated to subvolumes.

7. A method as set forth in claim 4 including the steps of:

changing a position of at least one of the objects until none of the points in the constraint set penetrate into the mesh; and

generating a force feedback that is conveyed to the user by the haptic device restricting penetration of one object into the other object, wherein the force feedback is proportional to the change in position of at least one of the objects.

8. A method as set forth in claim 4 wherein said step of rendering the constraint set includes the steps of:

removing points from the constraint set that do not penetrate into the mesh;

determining if there is at least a predetermined number of points in the constraint set;

identifying a point in the constraint set that penetrates the farthest into the mesh, if there are at least a predetermined number of points in the constraint set; and

moving at least one of the objects along a penetration vector of the farthest penetrating point until that point does not penetrate the mesh.

9. A method as set forth in claim 8 including the step of iteratively translating and rotating at least one of the objects until the points in the constraint set do not penetrate into the mesh.

10. A method as set forth in claim 4 wherein said step of identifying a collision set further includes the steps of:

iteratively selecting a point from the point cloud as an active point;

identifying a position of the active point using tracking;

determining if the active point is a predetermined distance from the mesh or the mesh is concave and finding a new tracking point if the active point is not a predetermined distance from the mesh or the mesh is not concave;

using the position of the active point to determine if the active point is colliding on an other side of the mesh;

removing the active point from collision set if the active point is not colliding on the other side of the mesh; and

adding the active point to the collision set if the active point is colliding on the other side of the mesh.

12. A method of real-time collision detection between solid geometric models, said method comprising the steps of:

modeling an object representing one solid geometric model as a point cloud and another object representing another solid geometric model as a mesh, wherein at least one of the objects is moving;

partitioning the mesh into an organized data structure;

identifying a constraint set, wherein the constraint set includes a minimum set of actively colliding points from the point cloud;

identifying a collision set, wherein the collision set includes all points from the point cloud colliding with the partitioned mesh;

determining a position of at least one of the objects;

changing the position of at least one of the objects so that none of the points in the constraint set penetrate into the mesh;

updating the collision set; and

providing the user with a force feedback using the haptic device to render a collision between the objects that is relative to the change in position of at least one of the objects.

11. A method as set forth in claim 14 wherein the object represented by the point cloud is moving and collides into the other object represented by the mesh that is stationary.

13. A method as set forth in claim 12 wherein the organized data structure is an OctTree data structure.

14. A method as set forth in claim 13 wherein said step of partitioning the mesh includes the steps of:

determining a tightest aligned bounding box containing the mesh wherein the mesh includes a vertex, or element or triangle;

dividing the aligned bounding box into subvolumes, with each subvolume containing a portion of the mesh;

selecting a vertex or element or triangle from the mesh as a current element;

selecting a subvolume as a current volume;

determining a child subvolume of the current volume that encloses the current element;

adding the current element to the child subvolume;

determining if there are more than a predetermined number of vertices, or elements or triangles in the child subvolume, and further subdividing the child subvolume to distribute excess vertices or elements or triangles within respective subvolumes that enclose the vertices or elements or triangles; and

continuing to recursively distribute the vertices or elements or triangles of the mesh into subvolumes within the aligned bounding box until the vertices, elements or triangles are allocated to subvolumes.

15. A method as set forth in claim 12 including the steps of:

changing a position of at least one of the objects until none of the points in the constraint set penetrate into the mesh; and

generating a force feedback that is conveyed to the user by the haptic device restricting penetration of one object into the other object, wherein the force feedback is proportional to the change in position of at least one of the objects.

16. A method as set forth in claim 12 wherein said step of changing the position of at least one of the objects includes the steps of:

removing points from the constraint set that do not penetrate into the mesh;

determining if there is at least a predetermined number of points in the constraint set;

identifying a point in the constraint set that penetrates the farthest into the mesh, if there are at least a predetermined number of points in the constraint set; and

moving at least one of the objects along a penetration vector of the farthest penetrating point until that point does not penetrate the mesh.

17. A method as set forth in claim 16 including the step of iteratively translating and rotating at least one of the objects until the points in the constraint set do not penetrate into the mesh.

18. A method as set forth in claim 12 wherein said step of updating a collision set further includes the steps of:

iteratively selecting a point from the point cloud as an active point;

identifying a position of the active point using tracking;

using the position of the active point to determine if the active point is colliding on an other side of the mesh;

removing the active point from collision set if the active point is not colliding on the other side of the mesh; and

adding the active point to the collision set if the active point is colliding on the other side of the mesh.

19. A method as set forth in claim 18 including the steps of:

determining if the active point is a predetermined distance from the mesh or the mesh is concave and finding a new tracking point on the mesh if the active point is not a predetermined distance from the mesh or the mesh is not concave.

20. A method as set forth in claim 12 including the step of continuously tracking a position of at least one of the objects.

21. A method as set forth in claim 12 including the steps of:

using tracking to determine a position of at least one of the objects;

changing the position of at least one of the objects until none of the points in the constraint set penetrate into the mesh; and

generating a force feedback proportional to the amount of movement of at least one of the objects because of the constraint.