US 7,092,862 B2Granted

Apparatus and method for determining whether objects will collide

AssigneeInternational Business Machines Corporation

InventorCharles Gordon Hooks

Life of this patent

Estimating the term…

Loading patent…

Abstract

A computer program for determining whether a plurality of objects will collide is disclosed. The program divides each object into surfaces, subsurfaces, and elements and computes normals for the elements and normals for each subsurface. The program calculates the dot products between the subsurface normals. If the dot product is negative, the program computes the relative subsurface vector between the two subsurfaces and calculates the dot product between the first subsurface normal and the relative subsurface vector to determine if there is a possible collision of elements. If that dot product is negative, then the program calculates the dot product for the elemental normals. If that dot product is negative, then the program calculates the relative elemental vector and calculates the dot product between the first elemental normal and the relative elemental vector. If that dot product is negative, then the two objects have collided.

Claims6

Dependent claims

A computer implemented process for simulating dynamic movement of two three-dimensional objects selected from a plurality of specified objects to determine whether the two three-dimensional objects will collide in a three-dimensional space comprising:

using a computer having a memory and a collision detection program and the plurality of specified objects stored in the memory, performing the steps of;
(a) responsive to a user selection of a first object and a second object from the plurality of specified objects;
(b) designating a first object subsurface, a first object size, and a first object subsurface variance;
(c) designating a second object subsurface, a second object size, and a second object subsurface variance;
(d) calculating a first object subsurface normal for the first object subsurface;
(e) calculating a second object subsurface normal for the second subsurface;
(f) initializing a first object orientation, a first object position, and a first object velocity in the three dimensional space;
(g) initializing a second object orientation, a second object position, and a second object velocity in the three dimensional space;
(h) calculating a first dot product between the first object subsurface normal and the second object subsurface normal;
(i) determining whether the dot product is negative;
and
(j) responsive to determining that the first dot product is negative, calculating a relative subsurface vector from the first object subsurface normal to the second object subsurface normal;
(k) calculating a second dot product between the relative subsurface vector and the first object subsurface normal;
(l) responsive to a determination that the second dot product is negative, calculating a third dot product of a first object subsurface individual elemental normal to a second object subsurface individual elemental normal;
(m) responsive to a determination that the third dot product is negative, calculating a relative elemental vector from the first object elemental normal to the second object elemental normal;
(n) calculating a fourth dot product of the relative elemental vector to the first object elemental normal;
and
(o) responsive to a determination that the fourth dot product is negative, providing a determination that the objects have collided.

15 more elements

A computer program product, tangibly stored in a computer readable medium for simulating dynamic movement of two three-dimensional objects selected from a plurality of specified objects to determine whether the two three-dimensional objects will collide in a three-dimensional space comprising:

instructions for causing a computer to perform the steps of;
(a) responsive to a user selection a first object and a second object from the plurality of specified objects;
(b) designating a first object subsurface, a first object size, and a first object subsurface variance;
(c) designating a second object subsurface, a second object size, and a second object subsurface variance;
(d) calculating a first object subsurface normal for the first object subsurface;
(e) calculating a second object subsurface normal for the second subsurface;
(f) initializing a first object orientation, a first object position, and a first object velocity in the three dimensional space;
(g) initializing a second object orientation, a second object position, and a second object velocity in the three dimensional space;
(h) calculating a first dot product between the first object subsurface normal and the second object subsurface normal;
(i) determining whether the dot product is negative;
and
(j) responsive to determining that the first dot product is negative, calculating a relative subsurface vector from the first object subsurface normal to the second object subsurface normal;
(k) calculating a second dot product between the relative subsurface vector and the first object subsurface normal;
(l) responsive to a determination that the second dot product is negative, calculating a third dot product of a first object subsurface individual elemental normal to a second object subsurface individual elemental normal;
(m) responsive to a determination that the third dot product is negative, calculating a relative elemental vector from the first object elemental normal to the second object elemental normal;
(n) calculating a fourth dot product of the relative elemental vector to the first object elemental normal;
and
(o) responsive to a determination that the fourth dot product is negative, providing a determination that the objects have collided.

15 more elements

A an apparatus for simulating dynamic movement of two three-dimensional objects selected from a plurality of specified objects to determine whether the two three-dimensional objects will collide in a three-dimensional space comprising:

a computer having a memory;
a collision detection program in the memory of the computer containing instructions to cause the computer to perform the action of:
(a) responsive to a user selection of a first object and a second object from the plurality of specified objects;
(b) designating a first object subsurface, a first object size, and a first object subsurface variance;
(c) designating a second object subsurface, a second object size, and a second object subsurface variance;
(d) calculating a first object subsurface normal for the first object subsurface;
(e) calculating a second object subsurface normal for the second subsurface;
(f) initializing a first object orientation, a first object position, and a first object velocity in the three dimensional space;
(g) initializing a second object orientation, a second object position, and a second object velocity in the three dimensional space;
(h) calculating a first dot product between the first object subsurface normal and the second object subsurface normal;
(i) determining whether the dot product is negative;
and
(j) responsive to determining that the first dot product is negative, calculating a relative subsurface vector from the first object subsurface normal to the second object subsurface normal;
(k) calculating a second dot product between the relative subsurface vector and the first object subsurface normal;
(l) responsive to a determination that the second dot product is negative, calculating a third dot product of a first object subsurface individual elemental normal to a second object subsurface individual elemental normal;
(m) responsive to a determination that the third dot product is negative, calculating a relative elemental vector from the first object elemental normal to the second object elemental normal;
(n) calculating a fourth dot product of the relative elemental vector to the first object elemental normal;
and
(o) responsive to a determination that the fourth dot product is negative, providing a determination that the objects have collided.

16 more elements

Dependencies are inferred from the claim text.

Facts

Application: 10/313,324Filed 5 Dec 2002
Published: US 2004/0111245 A110 Jun 2004
Granted: 15 Aug 2006
Term ends: Not estimatedThe source records don’t support an estimate.

Classification7 codes

B25J 9/1666
Characterised by motion, path, trajectory planning: avoiding collision or forbidden zones
G06T 19/00
Manipulating three-dimensional [3d] models or images for computer graphics
G05B 2219/45085
Nc applications: space robot
G06T 2210/21
Indexing scheme for image generation or computer graphics: collision detection, intersection