Game Development Reference
In-Depth Information
Sweep and prune of AABB as per the AABB axes
constructed from the objects (or their OBB)
Division of objects into cells
Objects in the
same zone
Intersecting AABB
Calculation of distance by Voronoi Marching
between convex envelops of objects
In each cell, sweep and prune of
AABB bounding the objects
Polyhedrons whose
AABBs cut each other
Intersecting convex
envelops
Detection between OBB
hierarchies
Calculation of a separator plane
between the two polyhedrons
Intersecting
polyhedrons
Colliding triangles
Detection between
triangles
GJK between
polyhedrons
Figure 17.13 Steps used by two standard libraries
of the polynomial roots obtained and derive a sturdier method. The time interval is
subdivided by iteration in order to accurately examine whether the OBBs are sepa-
rated at this interval. Even though this technique proves to be more relevant than the
sphere hierarchies, it is found to be decreasingly effective as the objects come close to
each other and as more and more bounding volumes overlap. A test of hierarchical
backtracking was suggested to make use of the relative speed of the objects. Redon
et al. (2002b) suggested applying the test proposed by Vanecek (1994) to the bound-
ing volumes of the hierarchy. This test makes it possible to detect situations where the
associated triangles move back, without going through the descent of the bounding
volume. Geometrical data is added to the bounding volumes in order to carry out
these hierarchical backtracking tests. Firstly, a number bound by the characteristic
points that approximate the geometry of the associated triangles and make it possible
to estimate their speeds is given to the bounding volumes. Then, a number bound by
vectors, forming a backtracking cone, to approach the perpendiculars of the associated
triangles is included in the bounding volumes. This geometrical data, pre-calculated
and in bound number, makes it possible to carry out a hierarchical backtracking test
keeping the time constant, i.e. irrespective of the number of triangles associated with
the bounding volume.
17.2.5 Summary of acceleration
Complete solutions including three phases of the pipeline were suggested and are often
available on the WEB: SOLID, V-Collide (Lin et al., 1996), Q-Collide (Chung &
Wang, 1996), RAPID, V-Clip (Mirtich, 1997) or HCollide (Gregory et al., 1999).
Figure 17.13 compares the approaches used by Q-Collide and V-Collide. Zachmann
(2001) suggested a generic architecture that makes it possible to select the stages of the
pipeline and compared various methods: He shows that the division of the space into