Computer graphics processing and selective visual display system – Computer graphics processing – Three-dimension
Reexamination Certificate
1999-03-11
2003-02-11
Zimmerman, Mark (Department: 2671)
Computer graphics processing and selective visual display system
Computer graphics processing
Three-dimension
Reexamination Certificate
active
06518966
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates to collision detection for three-dimensional shapes used in computer graphics and the like and for images of the like that have depth and are obtained with range finders, stereoscopic vision, and the like.
2. Description of the Related Art
For some time, formats for collision detection have been used that employ geometric shapes with computer graphics, CAD, and the like as the format for the detection of contact and mutual interference between bodies and components. An explanation will be given regarding polygon model collision detection in which the three-dimensional shape of a body is approximated by small planes using computer graphics. To detect whether collisions have occurred among polygon models, the detection of collisions between each of the planes (polygons) is carried out for all polygon combinations.
Therefore, an explanation will be given using figures regarding a method for collision detection for two triangular polygons.
FIG. 17A
shows a state in which two triangular polygons
901
and
902
collide with each other, that is to say, overlap. In order to investigate the overlapping between the polygons, overlapping should be investigated between each line segment of the edges that constitute one of the triangles and the plane of the other triangle.
FIG. 17B
shows the state in which one edge
903
of the triangular polygon
902
and the triangular polygon
901
overlap at point
904
. Using parameter t, the equations of the straight line of the edge
903
in three-dimensional space can be expressed as
x
=
x0
+
it
(
1
)
y
=
y0
+
jt
(
2
)
z
=
z0
+
kt
,
(
3
)
where x0, y0, and z0 are coordinates of a point on the straight line; and i, j, and k are direction vectors of the straight line on the other hand, the equation of a plane on the triangular polygon
901
can be expressed as
ax+by+cz+d
=0, (4)
where a, b, and c are normal vectors to the surface, and d is the distance from the origin. Therefore, from Equation 1, Equation 2, Equation 3 and Equation 4, the parameter t of the straight line at the point of intersection
904
can be derived as
t
0
=−(
ax
0
+
by
0
+
cz
0
+
d
)/(
ai+bj+ck
). (5)
By means of the substitution of the t that has been derived in Equation 1, Equation 2 and Equation 3, it is possible to derive the coordinates of the point of intersection
904
.
Actually, since the point of intersection is calculated only from the plane and straight-line parameters, it is necessary to next investigate whether the point of intersection is within the line segment
903
and the triangular polygon
901
. With regard to whether the point of intersection
904
is within the line segment
903
, if the parameters of the two end points
905
and
906
of the line segment
903
are made t
1
and t
2
(t
1
<t
2
) and the parameter t
0
of the point of intersection in Equation 5 is
t
1
≦
t
0
(6)
and
t
0
≦
t
2
, (7)
it can be detected that it is on (within) the line segment.
In addition, with regard to the detection as to whether the point
904
is inside the triangular polygon
901
, as is shown in
FIG. 17C
, line segments are drawn from the point
904
to each of the apex points of the triangular polygon and, and if the total of the acute angles formed by the line segments is 360 degrees, it is detected that the point is inside. As is shown in
FIG. 17D
, in those cases where it is not 360 degrees, it is detected that the point is outside.
The above detection processing is carried out for the entire group of polygons constituting a model. By this means, two-polygon model collision detection is done.
However, the above-mentioned method has had a problem in that the processing time increases in proportion to the complexity of the three-dimensional shape. With the polygon model, as the shape becomes complex, the number of polygons with which detailed shapes are represented increases, and the number of comparison polygon combinations for the collision detection increases.
In particular, with regard to each of the pixels of an image measured with a range finder or the like, when the collision detection between range images (or depth images) at a given distance from the camera, or between the range images and the polygon models is considered, if the range images are thought of as being composed of rectangular polygons whose number is commensurate with the number of image pixels, collision detections for the combinations of polygons is required in an amount commensurate with the number of the pixels of the image. For example, let us assume that each pixel of a distant image is a rectangular polygon. In a worst-case scenario, an established collision involving a single triangular polygon of another body requires that the point of intersection in Equation 5 be calculated and the two magnitudes from Equations (6) and (7) for detecting the positions inside and outside of line segments be compared the number of times equal to the number of pixels, assuming that the number of sides is three. In addition, for the detection involving the interior of a rectangular polygon, it must be carried out the same number of times as the number of pixels for each of the four apex points.
A method may also be considered where a portion obtained by representing a range image as a plane rather than a polygon for each image is replaced with a large polygon, and the number of polygons is reduced. However, there is a problem in that this increases the processing for the polygon reduction.
In addition, collision detection must involve conversion to a polygon model when such detection involves solid models in which three-dimensional shapes rather than range images are represented as solid bodies whose interiors are filled with matter, as well as boxel models and various other models in which computer graphics other than meta-balls or other such polygon models are used. There has been a problem in that, with the increase of the conversion processing and the differences in the model representation methods, there is an extraordinary increase in the number of polygons with the polygon model for shapes that can be represented simply by other models. As an example of the latter problem, the globe is a fundamental shape for the meta-ball or the like, and can be simply described. However, with the polygon model, many polygons are required to describe a globe that has some degree of smoothness.
SUMMARY OF THE INVENTION
An object of the present invention is to allow the collision detection for bodies of complex shapes to be carried out with an amount of processing that is proportionate to the number of pixels of the projected image irrespective of the complexity of the body by carrying out collision detection in which arrays are correlated to each of the pixels of a projected image of a body without a collision detection of geometric shapes such as polygons.
In order to the attain the stated object, the present invention dispenses with the use of collision detection between polygons and entails instead performing collision detection that is independent of the complexity of the body shape by using body regions obtained by projecting bodies subject to collision detection onto the pixels of projected images, and by employing a depth array in which distances from an arbitrary point or plane are arranged for each of the pixels of th e projected images.
REFERENCES:
patent: 4766556 (1988-08-01), Arakawa
patent: 5579455 (1996-11-01), Greene et al.
patent: 5914721 (1999-06-01), Lim
patent: 6069633 (2000-05-01), Apparao et al.
Foley et al., “Computer Graphics: Principles and Practice” Sec. Ed, ISBN 0-201-12110-7, 1992, pp. 712-713.*
“A Simple and Efficient Method for Accurate Collision Detection Among Deformable Polyhedral Objects in Motion” by Smith A.; Kitamura, Y.; Takemura, H.; Kishino, F. Virtual Reality Annuyal International Symposium, 1995 Proceedings, pp.: 136-145.*
“Solving the Collision Detection Problem” by Garcia-
Matsushita Institute Industrial Co., Ltd.
Santiago Enrique L
Wenderoth , Lind & Ponack, L.L.P.
Zimmerman Mark
LandOfFree
Method and device for collision detection and recording... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method and device for collision detection and recording..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and device for collision detection and recording... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3149684