Method and apparatus for determining collision between virtual objects in a virtual space

• US 6,141,015 A
• Filed: 03/04/1998
• Issued: 10/31/2000
• Est. Priority Date: 03/04/1997
• Status: Expired due to Fees

• Current Assignee: Sharp Kabushiki Kaisha (Hon Hai Precision Industry Co., Ltd.)
• Original Assignee: Sharp Kabushiki Kaisha (Hon Hai Precision Industry Co., Ltd.)
• Inventors: Tanaka, Kengo
• Primary Examiner(s): Zimmerman, Mark
• Assistant Examiner(s): Vo, Cliff N.
• Application Number:
  US09/034,283
• Time in Patent Office: 972 Days
• Field of Search: 345/418, 345/419, 345/427, 345/424, 345/420
• US Class Current: 345/427
• 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/12 Bounding box
• CPC Class Codes: G06T 2210/21 Collision detection, intersection
• CPC Class Codes: G06T 2210/36 Level of detail
• CPC Class Codes: G06T 2219/2016 Rotation, translation, scaling

Abstract

A method of determining collision occurring in a virtual space generated by a system using a computer includes the steps of preparing, for drawing data approximating a virtual object in the virtual space by a plurality of rectangular parallelepipeds, machine readable first shape data for collision determination approximating the virtual object by a plurality of rectangular parallelepipeds smaller in number than rectangular parallelepipeds of the drawing data, and determining, as a prescribed point moving in the virtual space moves, whether the prescribed point and the virtual object satisfy a predetermined collision condition or not, based on a coordinate of the prescribed point in the virtual space and the first shape data, by computer calculation. An apparatus for implementing this method is also disclosed.

Claims

1. A method of determining a collision occurring in a computer-generated virtual space, comprising:

preparing machine readable first shape data for collision determination separate from drawing data which approximates a virtual object in said virtual space by a plurality of interconnected polygonal facets, said first shape data approximating said virtual object with a substantially reduced number of interconnected polygonal facets as compared to those of said drawing data;

preparing machine readable second shape data for collision determination, said second shape data approximating said virtual object with a plurality of interconnected polygonal facets larger in number than those of said first shape data but smaller in number than those of said drawing data; and

determining, while a prescribed point defining a movement vector of said virtual object moves in said virtual space, whether said prescribed point and said virtual object satisfy a predetermined collision condition based on an intersection of the movement vector with each of said plurality of polygonal facets of said first shape data in said virtual space.

2. The method according to claim 1, wherein

said prescribed point represents a position of the virtual object moving in said virtual space.

3. The method according to claim 2, further comprising:

in the case where said prescribed point and said virtual object satisfy the predetermined collision condition, determining whether said prescribed point and said virtual object satisfy the predetermined collision based on an intersection of the movement vector with each of said plurality of polygonal facets of said second shape data.

4. The method according to claim 3, wherein said plurality of interconnected polygonal facets approximating said virtual object for each of said drawing data, first shape data and second shape data form a corresponding plurality of parallelepipeds for each of said drawing data, first shape data and second shape data, the plurality of parallelepipeds of said second shape data being greater in number than those of said first shape data, but smaller in number than those of said drawing data.

5. The method according to claim 1, wherein said prescribed point represents a position of a viewpoint which is set for a user of a system generating said computer-generated virtual space.

6. The method according to claim 5

wherein, in the case where said prescribed point and said virtual object satisfy the predetermined collision condition, determining whether said prescribed point and said virtual object satisfy the predetermined collision condition based on an intersection of the movement vector with each of said plurality of polygonal facets of said second shape data.

7. The method according to claim 6, wherein said plurality of interconnected polygonal facets approximating said virtual object for each of said drawing data, first shape data and second shape data form a corresponding plurality of parallelepipeds for each of said drawing data, first shape data and second shape data, the plurality of parallelepipeds of said second shape data being greater in number than those of said first shape data, but smaller in number than those of said drawing data.

9. The method according to claim 1, further comprising:

in the case where said prescribed point and said virtual object satisfy the predetermined collision condition, determining whether said prescribed point and said virtual object satisfy the predetermined collision condition based an intersection of the movement vector with each of said plurality of polygonal facets of said second shape data.

10. The method of determining collision according to claim 9, wherein

said determining step includes the steps of

calculating a vector of movement of said prescribed point in a predetermined time period, and

determining whether each of a polygon forming each facet of each of the rectangular parallelepipeds constituting said first shape data intersects with said vector.

11. An apparatus for determining a collision occurring in a computer-generated virtual space, comprising:

means for preparing machine readable first shape data for collision determination separate from drawing data which approximates a virtual object in said virtual space by a plurality of interconnected polygonal facets, said first shape data approximating said virtual object with a substantially reduced number of interconnected polygonal facets as compared to those of said drawing data;

means for preparing machine readable second shape data for collision determination, said second shape data approximating said virtual object with a plurality of interconnected polygonal facets larger in number than those of said first shape data but smaller in number than those of said drawing data; and

means for determining while a prescribed point defining a movement vector of said virtual object moves in said virtual space, whether said prescribed point and said virtual object satisfy a predetermined collision condition based on an intersection of the movement vector with each of said plurality of polygonal facets of said first shape data in said virtual space.

8. The apparatus according to claim 18 wherein said plurality of interconnected polygonal facets approximating said virtual object for each of said drawing data, first shape data and second shape data form a corresponding plurality of parallelepipeds for each of said drawing data, first shape data and second shape data, the plurality of parallelepipeds of said second shape data being greater in number than those of said first shape data, but smaller in number than those of said drawing data.

12. The apparatus according to claim 11, wherein

said prescribed point represents a position of the virtual object moving in said virtual space.

13. The apparatus according to claim 12, further comprising:

means, in the case where said prescribed point and said virtual object satisfy the predetermined collision condition, for determining whether said prescribed point and said virtual object satisfy the predetermined collision condition based on an intersection of the movement vector with each of said plurality of polygonal facets of said second shape data.

14. The apparatus according to claim 13 wherein said plurality of interconnected polygonal facets approximating said virtual object for each of said drawing data, first shape data and second shape data form a corresponding plurality of parallelepipeds for each of said drawing data, first shape data and second shape data, the plurality of parallelepipeds of said second shape data being greater in number than those of said first shape data, but smaller in number than those of said drawing data.

15. The apparatus according to claim 11, wherein

said prescribed point represents a position of a view point set for a user of a system generating said computer-generated virtual space, wherein said user is moving in said virtual space.

16. The apparatus according to claim 15, further comprising:

means, in the case where said prescribed point and said virtual object satisfy the predetermined collision condition, for determining whether said prescribed point and said virtual object satisfy the predetermined collision condition based on an intersection of the movement vector with each of said plurality of polygonal facets of said second shape data.

17. The apparatus according to claim 16, wherein said plurality of interconnected polygonal facets approximating said virtual object for each of said drawing data, first shape data and second shape data form a corresponding plurality of parallelepipeds for each of said drawing data, first shape data and second shape data, the plurality of parallelepipeds of said second shape data being greater in number than those of said first shape data, but smaller in number than those of said drawing data.

18. The apparatus according to claim 11, further comprising:

means, in the case where said prescribed point and said virtual object satisfy the predetermined collision condition, for determining whether said prescribed point and said virtual object satisfy the predetermined collision condition based on an intersection of the movement vector with each of said plurality of polygonal facets of said second shape data.

19. The apparatus according to claim 11, further including:

means for defining a law of motion of an object in said virtual space by a machine calculable form in advance; and

, when said collision condition is satisfied;

means for calculating a position of movement of said prescribed point after collision in accordance with said law of motion.

20. An apparatus for collision determination in a virtual space, comprising:

a first memory for storing drawing data which approximates a virtual object in said virtual space by a plurality of interconnected polygonal facets;

a second memory for storing first shape data which approximates an outline of said virtual object with a substantially reduced number of interconnected polygonal facets as compared to those of said drawing data, and for storing second shape data which approximates said virtual object with a plurality of interconnected polygonal facets larger in number than those of said first shape data but smaller in number than those of said drawing data; and

a collision determining section for determining, while a prescribed point defining a movement vector of said virtual object moves in said virtual space, whether said prescribed point and said virtual object satisfy a predetermined collision condition based on an intersection of said movement vector with each of said polygonal facets of said first shape data.

21. The apparatus of claim 20, further including a vector generating section for generating said movement vector of said virtual object from movement of said prescribed point in said virtual space.

22. The apparatus of claim 20, further including:

a movement processing section for determining a position of movement of the virtual object after collision; and

a drawing section for performing CG drawing processing based on said position after collision, said position defined by an updated coordinate value of said virtual object.

23. The apparatus of claim 20, wherein, if more precise collision determination of said prescribed point and virtual object is desired, said collision determining section performs collision determination using said second shape data.

24. The apparatus of claim 23, wherein said determination as to whether said prescribed point and said virtual object satisfy a predetermined collision condition is based on an intersection of said movement vector with each of said polygonal facets of said second shape data.

25. The apparatus of claim 24, further including a shape data manager for reading said second shape data from said second memory for collision determination, wherein said shape data manager includes a separate memory for storing second shape data used for determining said intersection.

26. The apparatus of claim 20, further including a shape data manager for reading said first shape data from said second memory for collision determination, wherein said shape data manager includes a separate memory for storing first shape data used for determining said intersection.

27. The apparatus of claim 20, wherein said prescribed point defines a position of the virtual object moving in said virtual space.

28. The apparatus of claim 20, wherein said prescribed point defines a position of a viewpoint which is set for a user of a system generating the computer-generated virtual space.

29. The apparatus of claim 20, wherein said collision determining section calculates said intersection between said polygonal facets and said movement vector, said calculation being set in advance of collision determination as a program or processed during collision determination by a computer.

30. A method of determining collisions in a computer-generated space, comprising:

providing drawing data which approximates a virtual object in said virtual space by a plurality of interconnected polygonal facets;

providing first shape data which approximates an outline of said virtual object with a substantially reduced number of interconnected polygonal facets as compared to those of said drawing data;

providing second shape data which approximates said virtual object with a plurality of interconnected polygonal facets larger in number than those of said first shape data but smaller in number than those of said drawing data; and

determining, while a prescribed point defining a movement vector of said virtual object moves in said virtual space, whether said prescribed point and said virtual object satisfy a predetermined collision condition based on an intersection of said movement vector with each of said polygonal facets of said first shape data.