Apparatus for detecting the collision of moving objects

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.sub.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.sub.i of the uppermost rank sphere, the radius r.sub.n of the lowermost rank sphere and the ratio of radius .rho..sub.r by the following formulae;
• ##EQU9## (n is an integer by counting fractions over 1/2 as one and disregarding the rest);
• and ##EQU10##

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.

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.