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

Search Nedrilad ::

Custom Search