Game Development Reference
In-Depth Information
Depending on the approach, the algorithm is reiterated by reversing the roles of objects
A and B (since all the points of A were not displayed, mainly those located behind the
observer's point of view). The type of tracing of object A can be different for the same
reason. They can be the front and/or rear faces in case of a convex object or simply
segments of the object. Irrespective of the approach, the major slow down is due to
the need to inspect all the data of a buffer to find values indicating a collision, which
arises in the last phase of the algorithm. In fact, not only is the reading of the buffer
slow, but in addition to that, no graphic accelerator can answer a question such as: Is
there a pixel that verifies property P ? It thus becomes necessary to make a compromise
between the size of the buffer inspected (and thus the time of search made by the
software) and the precision required. However, recent approaches (Govindaraju et al.,
2003; Knott & Pai, 2003) use a system of wired occlusion detection (extensions such
as *_ occlusion_query ) present on the current graphics cards to avoid inspecting all
the pixels. The image-based methods however present several problems of accuracy,
related to the sampling of the image, the accuracy of the Z-buffer , etc. There are
solutions available, but they are expensive in terms of processing time (Govindaraju
et al., 2004). Finally, another possible path is to design hardware that is completely
dedicated to collision detection (Zachmann & Knittel, 2003), but these research areas
are still in their initial stages.
17.2.4 Continuous temporal acceleration
When the collision detection algorithm is 4D, it is more coherent to have even the
acceleration phase in 4D. In fact, if the acceleration is only spatial, it becomes incon-
sistent with the lower level test and can omit certain collisions. In this case, most of the
spatial techniques require an adjustment for the 4D case. Please note that determining
the time as well as the exact place of collision is however of very little interest in the
acceleration phase. In case of continuous acceleration, this nonetheless makes it pos-
sible to reduce the complexity of equations. The first possible approach is performing
this detection by considering the bounding volumes, the initial and final positions of
objects (Eckstein & Shömer, 1999) or preferably even all the positions occupied dur-
ing the movement (Foisy & Hayward, 1994). This means considering the bounding
volume of the projection of the 4D volume scanned by the object during the movement
on the 3D space. The volumes of the paths of the objects can then cut each other, with-
out the objects meeting each other (same spatial position, but at different moments).
This gives a less effective acceleration, but is preferable than omitting collisions. Several
spatial accelerations mentioned earlier can be used with this type of bounding volumes:
Spatial division, topological classifications or BVH.
Acceleration methods completely dedicated to collision detection can be more
effective (as the number of false collisions detected by them is less), provided that
they are reasonable in terms of the algorithm. For example, it is possible to detect
contacts between mobile spheres (Redon et al., 2001). A contact between two AABBs
whose vertices have a uniformly straight path is equally easy to determine (Meseure &
Chaillou, 1997). It is also possible to transform the discrete separation test of two
OBBs (see table 17.1) into a continuous test (Redon et al., 2002a). All the elements of
the inequality then become piecewise polynomials, depending on time. A resolution
based on the interval arithmetics is suggested in order to avoid an expensive resolution
Search Nedrilad ::




Custom Search