Collision detector utilizing collision contours

• US 5,515,489 A
• Filed: 02/17/1995
• Issued: 05/07/1996
• Est. Priority Date: 12/31/1991
• Status: Expired due to Term

• Current Assignee: Apple Inc.
• Original Assignee: Apple Computer Incorporated (Apple Inc.)
• Inventors: Yaeger, Larry S.
• Primary Examiner(s): Herndon, Heather R.
• Assistant Examiner(s): Burwell, Joseph R.
• Application Number:
  US08/391,254
• Time in Patent Office: 445 Days
• Field of Search: 395/152, 395/90, 395/141, 395/133, 395/137, 395/138, 345/122
• US Class Current: 345/473
• CPC Class Codes: G06T 7/00 Image analysis
• CPC Class Codes: Y10S 345/958 Collision avoidance

Abstract

A method and apparatus for determining and displaying or preventing a collision between two objects. Certain characteristics of these two objects such as their sizes, orientations, and velocities, are inputted. Based upon these characteristics, a collision contour is generated about the first object. If either or both object(s) had been moved, the collision contour is generated based on a velocity outline to account for the velocity effects. These two objects have collided if the second object'"'"'s centerpoint is included in the collision contour. Otherwise, the two objects have not collided. The result is then portrayed on a graphics display device.

Claims

1. A method for detecting a collision between a first object and a second object in a computer controlled display system, wherein at least one of said first object and said second object is non-circular, said method comprising:

reading characteristics of said first object and said second object from a memory of said computer controlled display system, wherein said characteristics indicate a shape, size and orientation of said first object and a shape, size and orientation of said second object;

generating a collision contour for a particular time, corresponding to said first object based upon said shape, size and orientation of said first object and said shape, size and orientation of said second object;

determining a centerpoint of said second object for said particular time;

determining whether said centerpoint of said second object for said particular time is included in said collision contour for said particular time;

generating a signal indicating whether said first object and said second object are in a state of collision, wherein inclusion of said centerpoint in said collision contour indicates that said first object is in a state of collision with said second object, wherein if said centerpoint does not reside in said collision contour, then said first object and said second object are not in a state of collision; and

displaying whether said first object ,and said second object are in a state of collision.

2. The method according to claim 1 further including the steps of determining, prior to generation of said collision contour, a bounding box based on said shape, size and or orientation of said first object, wherein said first object is enclosed by said bounding box, wherein said collision contour is generated based on shape, size and orientation of said bounding box.

3. The method according to claim 1 further including the steps of:

determining, prior to generation of said collision contour, a first bounding box based on said shape, size and orientation of said first object, wherein said first object is enclosed by said first bounding box;

determining, prior to generation of said collision contour, a second bounding box based on said shape, size and orientation of said second object, wherein said second object is enclosed by said second bounding box; and

wherein said collision contour is generated based on shape, size, orientation, and a velocity outline of each bounding box of said first bounding box and said second bounding box.

4. The method according to claim 3 further including the steps of:

determining a first velocity outline based on said shape, size and orientation of said first object, and on a first velocity vector representing a direction and a distance by which said first object has moved during a period of time; and

determining a second velocity outline based on said shape, size and orientation of said second object, and on a second velocity vector representing a direction and a distance by which said second object has moved during a period of time.

5. The method according to claim 1 wherein said step of generating said collision contour includes the step of generating a set of vertices representing endpoints of an outline surrounding said first object and dependent upon said shape, size and orientation of said first object, and said shape, size and orientation of said second object.

6. The method according to claim 1 wherein said step of determining whether said centerpoint of said second object is included in said collision contour is accomplished by using a Cyrus-Beck algorithm.

7. The method of claim 1 wherein said collision contour is defined by a trace of said centerpoint of said second object as said second object is moved around the perimeter of said first object in a manner wherein an edge of said second object is coincident to, but does not overlap an edge of said first object.

8. The method according to claim 1 wherein said collision contour is generated based on shape, size, orientation, and a velocity outline of each object of said first object and said second object;

and further including the steps of;

determining a first velocity outline based on said shape, size and orientation of said first object, and on a first velocity vector representing a direction and a distance by which said first object has moved during a period of time; and

determining a second velocity outline based on said shape, size and orientation of said second object, and on a second velocity vector representing a direction and a distance by which said second object has moved during a period of time.

9. The method according to claim 1 wherein said step of generating said collision contour for said particular time includes generating said collision contour for a time at which said first object is moving.

10. The method according to claim 9 wherein said step of generating said collision contour for said particular time includes generating said collision contour for a time at which said first object is moving and said second object is moving.

11. In a computer system, an apparatus for displaying a collision between a first object and a second object, wherein at least one of said first object and said second object is non-circular, the apparatus comprising:

a memory having stored therein characteristics of said first object and said second object, said characteristics indicating a shape, size and orientation of said first object and a shape, size and orientation of said second object;

a processing unit coupled to said memory for generating a collision contour for a particular time, for said first object and for determining a centerpoint of said second object for said particular time, wherein said processing unit generates said collision contour based on said shape, size and orientation of said first object and said shape, size and orientation of said second object;

a circuit for determining whether said centerpoint of said second object for said particular time is included within said collision contour for said particular time, inclusion of said centerpoint in said collision contour indicating said first object is in a state of collision with said second object and exclusion of said centerpoint in said second object indicating said first object is not in a state of collision with said second object; and

a graphics display device coupled to said processing unit for displaying whether said first object is in a state of collision with said second object.

12. The apparatus according to claim 11 wherein said first object is enclosed by a bounding box based on said shape, size and orientation of said first object;

wherein said collision contour is generated based on shape, size and orientation of said bounding box.

13. The apparatus according to claim 11 wherein said characteristics include shape, size, orientation, and a first velocity outline for said first object and shape, size, orientation, and a second velocity outline for said second object;

and wherein said collision contour is generated based on shape, size, orientation and a velocity outline for each of said first object and said second object.

14. The apparatus according to claim 13 wherein said first velocity outline is based on said shape, size and orientation of said first object, and on a first velocity vector representing a direction and a distance by which said first object has moved during a period of time and said second velocity outline is based on said shape, size and orientation of said second object, and on a second velocity vector representing a direction and a distance by which said second object has moved during a period of time.

15. The apparatus according to claim 11 wherein said collision contour includes a set of vertices representing endpoints of an outline surrounding said first object and dependent upon said shape, size arid orientation of said first object and said shape, size and orientation of said second object.

16. The apparatus according to claim 11 wherein said first object is a moving object.

17. A method for adjusting positions between a first object and a second object in a computer display system so that said first object and said second object do not overlap when displayed, wherein at least one of said first object and said second object is non-circular, said method comprising:

reading characteristics of said first object and said second object stored in a memory of said computer display system, said characteristics indicating a shape, size and orientation of said first object and a shape, size and orientation of said second object;

generating a collision contour for a particular time, for said first object based upon said shape, size and orientation of said first object and said shape, size and orientation of said second object;

determining a centerpoint of said second object for said particular time;

generating a signal indicating whether said first object and said second object are in a state of collision, wherein inclusion of said centerpoint in said collision contour indicates that said first object is in a state of collision with said second object, wherein if said centerpoint does not reside in said collision contour, then said first object and said second object are not in a state of collision;

if said first object and said second object are in a state of collision, positioning said second object so that said centerpoint of said second object is not included in said collision contour; and

displaying said first object and said second object.

18. The method according to claim 17 wherein said first object is enclosed by a bounding box based on said shape, size and orientation of said first object;

wherein said collision contour is generated based on shape, size and orientation of said bounding box.

19. In a computer system, an apparatus for adjusting positions between a first object and a second object so that said first object and said second object do not overlap when displayed, wherein at least one of said first object and said second object is non-circular, comprising:

a memory having stored therein characteristics of said first object and said second object, said characteristics indicating a shape, size and orientation of said first object and a shape, size and orientation of said second object;

a processing unit coupled to said memory for generating a collision contour for a particular time for said first object and for determining a centerpoint of said second object for said particular time, said processing unit generating said collision contour based on said shape, size and orientation of said first object and said shape, size and orientation of said second object;

a circuit for determining whether said centerpoint of said second object for said particular time, is included within said collision contour for said particular time, inclusion of said centerpoint in said collision contour indicating said first object is in a state of collision with said second object and exclusion of said centerpoint in said second object indicating said first object is not in a state of collision with said second object;

an adjustment means for positioning said first object and said second object if said first object and said second object are in a state of collision according to said circuit, so that said centerpoint of said second object is not included in said collision contour; and

a graphics display device coupled to said processing unit for displaying said first object and said second object.

20. The apparatus according to claim 19 wherein said first object is enclosed by a first bounding box based on said shape, size and orientation of said first object, and said second object is enclosed by a second bounding box based on said shape, size and orientation of said second object, wherein said collision contour is generated based on shape, size and orientation of each of said first bounding box arid said second bounding box.