Apparatus for detecting the collision of moving objects

• US 5,056,031 A
• Filed: 11/09/1989
• Issued: 10/08/1991
• Est. Priority Date: 11/12/1988
• Status: Expired due to Fees

• Current Assignee: Kabushiki Kaisha Toyota Chuo Kenkyusho (Toyota Motor Corporation)
• Original Assignee: Kabushiki Kaisha Toyota Chuo Kenkyusho (Toyota Motor Corporation)
• Inventors: Ikeda, Toshiaki, Nakano, Masaru, Kuno, Toshitaka, Tanaka, Minoru
• Primary Examiner(s): Black, Thomas G.
• Application Number:
  US07/435,070
• Time in Patent Office: 698 Days
• Field of Search: 364/460, 364/461, 364/513, 364/474.2
• US Class Current: 701/301
• CPC Class Codes: B25J 9/1676 Avoiding collision or forbidden zones
• CPC Class Codes: G05B 2219/40479 Use graphic display, layout of robot path, obstacles to indicate interference
• CPC Class Codes: G05B 2219/49145 Spheres replace object, check first collision for large spheres, then small
• CPC Class Codes: G06T 17/00 Three dimensional [3D] modelling, e.g. data description of 3D objects

Abstract

An apparatus for detecting the collision of objects including a moving object includes a face information memory for storing face information describing the surfaces of each object; hierarchical sphere model generator for modeling the surfaces of each object by hierarchically covering the surfaces with spheres having various radii on the basis of the face information; sphere model memory for storing the positions of the modeled spheres generated; sphere position updater for updating the position of each modeled sphere having various radii with respect to the moving object and outputting the updated position; and sphere collision computer for executing procedures in which mutually colliding spheres are detected on the basis of the positions of the modeled spheres concerning two of the objects generated at an arbitrary time and stored in the sphere model memory and colliding spheres among spheres belonging to the mutually colliding spheres and having a smaller radius are further detected with respect to only the spheres determined to collide with each other, and for determining the collision of the two objects with each other when finally mutually colliding spheres having the smallest radius are present. The procedures are executed hierarchically and consecutively starting with spheres having a large radius toward spheres having a smaller radius.

Claims

1. An apparatus for detecting the collision of objects including at least one moving object, comprising:

face information storing means for storing face information describing the surfaces of each of said objects;

hierarchical sphere model generating means for modeling the surfaces of each of said objects by hierarchically arranging spheres having a plurality of radii uniformly over all of the surfaces of each object on the basis of said face information;

sphere model storing means for storing the positions of said modeled spheres generated;

sphere position updating means for updating the position of each of said modeled spheres having said plurality of radii with respect to said moving object in correspondence with the movement of said moving object and outputting said updated position to said sphere model storing means; and

sphere collision computing means

for executing procedures in which mutually colliding ones of said spheres are detected on the basis of the positions of said modeled spheres concerning two of said objects generated at an arbitrary time and stored in said sphere model storing means, and colliding spheres among spheres belonging to said mutually colliding spheres and having a smaller radius are further detected with respect to only said spheres determined to collide with each other, said procedures being executed hierarchically and consecutively starting with spheres having a large radius toward spheres having a smaller radius, and

for determining the collision of said two objects with each other when finally mutually colliding spheres having the smallest radius are present.

2. The apparatus according to claim 1, wherein said hierarchical sphere model generating means comprises means for modeling the surfaces of each of said objects by hierarchically covering said surfaces with spheres having a predetermined number of ranks and having a different radius for each rank on the basis of the face information.

3. The apparatus according to claim 2, wherein said hierarchical sphere model generating means comprises means for determining radii of spheres in each rank and the number of ranks on the basis of a radius of an uppermost rank sphere circumscribing the objects, a radius of a lowermost rank sphere determining an accuracy of a collision detection and a ratio of radius between an upper rank sphere and a lower rank sphere.

4. The apparatus according to claim 3, wherein said hierarchical sphere model generating means comprises means for determining said radii r_i of spheres in each rank covering the surfaces of the objects and the number of ranks n on the basis of the radius r₁ of the uppermost rank sphere, the radius r_n of the lowermost rank sphere and the ratio of radius ρ

_r by the following formulae;

##EQU7## (n is an integer by counting fractions over 1/2 as one and disregarding the rest); and

##EQU8##

5. The apparatus according to claim 1, wherein said hierarchical sphere model generating means comprises means for determining radii of spheres in medium ranks between an uppermost rank and a lowermost rank on the basis of a radius of the uppermost rank sphere circumscribing the objects and a radius of the lowermost rank smallest sphere which determines a predetermined accuracy of a collision detection, and hierarchically arranging the spheres so that the larger spheres include the smaller spheres and the surfaces of the objects.

6. The apparatus according to claim 5, wherein said hierarchical sphere model generating means comprises:

means for generating a rectangular parallelepiped-shaped envelope cell enveloping the object on the basis of the face information outputted from said face information storing means and generating an uppermost rank sphere circumscribing said envelope cell;

means for determining the radii of spheres in medium ranks on the basis of the radius of the uppermost rank largest sphere and the radius of the lowermost rank smallest sphere;

means for extracting a radius in the order of larger to smaller radii among said determined radii of said medium rank spheres and said radius of the lowermost rank sphere;

means for dividing a cell inscribing an upper rank sphere having the larger radius into a plurality of cubic cells inscribing the spheres having said extracted radius; and

means for generating spheres circumscribing said divided cubic cells respectively, extracting only such spheres that intersect with the surfaces of the objects among said generated spheres, and generating said extracted spheres as lower rank spheres with respect to said upper rank sphere.

7. The apparatus according to claim 6, wherein said hierarchical sphere model generating means comprises means for dividing said cell inscribing the upper rank sphere having the larger radius into said plurality of cubic cells having overlapping portions between the adjacent cells.

8. The apparatus according to claim 7, wherein said hierarchical sphere model generating means comprises means for dividing each cell in which said overlapping portions are deleted into a plurality of smaller cubic cells. inscribing the spheres in a lower rank than that of the spheres having said extracted radius and having overlapping portions between the adjacent cells.

9. The apparatus according to claim 1, wherein said sphere collision computing means comprises:

means for selecting each pair of spheres to be searched for the two objects among present searching spheres, said pair belonging to the same rank or one sphere belonging to a lowermost rank and the other belonging to a rank other than the lowermost rank, determining the collision between said pair of spheres, and outputting colliding pair of spheres or further searching colliding pair of spheres in a one rank upper rank than the present searching rank when no collision is searched with respect to all pairs of such spheres; and

means for determining the collision between one sphere of said outputted colliding pair of spheres and a plurality of spheres in a one rank lower rank belonging to the other sphere of said outputted pair of spheres, and detecting and storing colliding spheres among said plurality of spheres, or further searching colliding pair of spheres in a one rank upper rank than the present searching rank when no collision is searched with respect to all of said plurality of spheres.

10. The apparatus according to claim 1, wherein the spheres having a large radius encompass spheres having a smaller radius.

11. The apparatus according to claim 1, wherein said hierarchical sphere model generating means comprises means for uniformly dividing the surfaces of said objects into cells on the basis of said face information and uniformly dividing each of said cells into smaller cells to represent said surfaces with hierarchically divided cells and for generating spheres circumscribing the respective hierarchically divided cells.

12. An apparatus for detecting the collision of objects including at least one moving object, comprising:

face information storing means for storing face information describing the surfaces of each of said objects;

hierarchical sphere model generating means for modeling the surfaces of each of said objects by hierarchically covering said surfaces with spheres having a plurality of radii on the basis of said face information;

sphere model storing means for storing the positions of said modeled spheres generated;

sphere position updating means for updating the position of each of said modeled spheres having said plurality of radii with respect to said moving object in correspondence with the movement of said moving object and outputting said updated position to said sphere model storing means; and

sphere collision computing means

for executing procedures in which mutually colliding ones of said spheres are detected on the basis of the positions of said modeled spheres concerning two of said objects generated at an arbitrary time and stored in said sphere model storing means, and colliding spheres among spheres belonging to said mutually colliding spheres and having a smaller radius are further detected with respect to only said spheres determined to collide with each other, said procedures being executed hierarchically and consecutively starting with spheres having a large radius toward spheres having a smaller radius, and

for determining the collision of said two objects with each other when finally mutually colliding spheres having the smallest radius are present;

wherein said hierarchical sphere model generating means comprises means for modeling the surfaces of each of said objects by hierarchically covering said surfaces with spheres having a predetermined number of ranks and having a different radius for each rank on the basis of the face information;

means for determining radii of spheres in each rank and the number of ranks on the basis of a radius of an uppermost rank sphere circumscribing the objects, a radius of a lowermost rank sphere determining an accuracy of a collision detection and a ratio of radius between an upper rank sphere and a ratio of radius between an upper rank sphere and a lower rank sphere; and

means for determining said radii r_i of spheres in each rank covering the surfaces of the objects and the number of ranks n on the basis of the radius r_i of the uppermost rank sphere, the radius r_n of the lowermost rank sphere and the ratio of radius ρ

_r by the following formulae;

##EQU9## (n is an integer by counting fractions over 1/2 as one and disregarding the rest); and

##EQU10##

13. An apparatus for detecting the collision of objects including at least one moving object, comprising:

face information storing means for storing face information describing the surfaces of each of said objects;

hierarchical sphere model generating means for modeling the surface of each of said objects by hierarchically covering said surfaces with spheres having a plurality of radii on the basis of said face information;

sphere model storing means for storing the positions of said modeled spheres generated;

sphere position updating means for updating the position of each of said modeled spheres having said plurality of radii with respect to said moving object in correspondence with the movement of said moving object and outputting said updated position to said sphere model storing means; and

sphere collision computing means

for executing procedures in which mutually colliding ones of said spheres are detected on the basis of the positions of said modeled spheres concerning two of said objects generated at an arbitrary time and stored in said sphere model storing means, and colliding spheres among spheres belonging to said mutually colliding spheres and having a smaller radius are further detected with respect to only said spheres determined to collide with each other, said procedures being executed hierarchically and consecutively starting with spheres having a large radius toward spheres having a smaller radius, and

for determining the collision of said two objects with each other when finally mutually colliding spheres having the smallest radius are present;

wherein said hierarchical sphere model generating means comprises means for determining radii of spheres in medium ranks between an uppermost rank and a lowermost rank on the basis of a radius of the uppermost rank sphere circumscribing the objects and a radius of the lowermost rank smallest sphere which determines a predetermined accuracy of a collision detection, and hierarchically arranging the spheres so that the larger spheres include the smaller spheres and the surfaces of the objects; and

means for generating a rectangular parallelepiped-shaped envelope cell enveloping the object on the basis of the face information outputted from said face information storing means and generating an uppermost rank sphere circumscribing said envelope call;

means for determining the radii of spheres in medium ranks on the basis of the radius of the uppermost rank largest sphere and the radius of the lowermost rank smallest sphere;

means for extracting a radius in the order of larger to smaller radii among said determined radii of said medium rank spheres and said radius of the lowermost rank sphere;

means for dividing a cell inscribing an upper rank sphere having the larger radius into a plurality of cubic cells inscribing the spheres having said extracted radius; and

means for generating spheres circumscribing said divided cubic cells respectively, extracting only such spheres that intersect with the surfaces of the objects among said generated spheres, and generating said extracted spheres as lower rank spheres with respect to said upper rank sphere.

14. The apparatus according to claim 13, wherein said hierarchical sphere model generating means comprises means for dividing said cell inscribing the upper rank sphere having the larger radius into said plurality of cubic cells having overlapping portions between the adjacent cells.

15. The apparatus according to claim 14, wherein said hierarchical sphere model generating means comprises means for dividing each cell in which said overlapping portions are deleted into a plurality of smaller cubic cells inscribing the spheres in a lower rank than that of the spheres having said extracted radius and having overlapping portions between the adjacent cells.

16. An apparatus for detecting the collision of objects including at least one moving object, comprising:

face information storing means for storing face information describing the surfaces of each of said objects;

hierarchical sphere model generating means for modeling the surfaces of each of said objects by hierarchically covering said surfaces with spheres having a plurality of radii on the basis of said face information;

sphere model storing means for storing the positions of said modeled spheres generated;

sphere position updating means for updating the position of each of said modeled spheres having said plurality of radii with respect to said moving object in correspondence with the movement of said moving object and outputting said updated position to said sphere model storing means; and

sphere collision computing means

for executing procedures in which mutually colliding ones of said spheres are detected on the basis of the positions of said modeled spheres concerning two of said objects generated at an arbitrary time and stored in said sphere model storing means, and colliding spheres among spheres belonging to said mutually colliding spheres and having a smaller radius are further detected with respect to only said spheres determined to collide with each other, said procedures being executed hierarchically and consecutively starting with spheres having a large radius toward spheres having a smaller radius, and

for determining the collision of said two objects with each other when finally mutually colliding spheres having the smallest radius are present;

wherein said sphere collision computing means comprises;

means for selecting each pair of spheres to be searched for the two objects among present searching spheres, said pair belonging to the same rank or one sphere belonging to a lowermost rank and the other belonging to a rank other than the lowermost rank, determining the collision between said pair of spheres, and outputting colliding pair of spheres or further searching colliding pair of spheres in a one rank upper rank than the present searching rank when no collision is searched with respect to all pairs of such spheres; and

means for determining the collision between one sphere of said outputted colliding pair of spheres and a plurality of spheres in a one rank lower rank belonging to the other sphere of said outputted pair of spheres, and detecting and storing colliding spheres among said plurality of spheres, or further searching colliding pair of spheres in a one rank upper rank than the present searching rank when no collision is searched with respect to all of said plurality of spheres.