i
i
i
i
i
i
i
i
818 17. Collision Detection
17.6.2 Distance Queries
In certain applications one wants to test whether an object is at least a
certain distance from an environment. For example, when designing new
cars, there has to be enough space for different sized passengers to be able to
seat themselves comfortably. Therefore, a virtual human of different sizes
can be tried against the car seat and the car, to see if he can be seated
without bumping into the car. Preferably, the passengers should be able
to seat themselves and still be at least, say, 10 cm apart from some of the
car’s interior elements. This sort of testing is called tolerance verification.
This can be used for path planning, i.e., how an object’s collision-free path
from one point to another can be determined algorithmically. Given the
acceleration and velocity of an object, the minimum distance can be used
to estimate a lower bound on the time to impact. In this way, collision
detection can be avoided until that time [774]. Another related query is of
the penetration depth, that is, finding out how far two objects have moved
into each other. This distance can be used to move the objects back just
enough so that they do not penetrate any longer, and then an appropriate
collision response can be computed at that point.
One of the first practical approaches that compute the minimum dis-
tance between convex polyhedra is called GJK, after its inventors; Gilbert,
Johnson and Keerthi [399]. An overview of this algorithm will be given
in this section. This algorithm computes the minimum distance between
two convex objects, A and B.Todothis,thedifference object (sometimes
called the sum object) between A and B is used [1291]:
A − B = {x − y : x ∈ A, y ∈ B). (17.12)
Figure 17.15. To the left, two convex objects A and B are shown. To construct A − B,
first move A and B so that one reference point is at the origin (already done at the left).
Then B is reflected, as shown in the middle, and the chosen reference point on B is put
on the surface of A and then the reflected B is swept around A.ThiscreatesA − B,to
the right. The minimum distance, d, is shown both on the left and the right.
i
i
i
i
i
i
i
i
17.6. Miscellaneous Topics 819
This is also called the Minkowski sum of A and (reflected) B (see Sec-
tion 16.18.3). All differences x − y are treated as a point set, which forms
a convex object. An example of such a difference is shown in Figure 17.15,
which also explains how to mentally build such a difference object.
The idea of GJK is that instead of computing the minimum distance
between A and B, the minimum distance between A − B and the origin
is computed. These two distances can be shown to be equivalent. The
algorithm is visualized in Figure 17.16. Note that if the origin is inside
A − B then A and B overlap.
The algorithm starts from an arbitrary simplex in the polyhedron. A
simplex is the simplest primitive in the respective dimension, so it is a
Figure 17.16. Upper left: The minimum distance between the origin and the polygon is
to be computed. Upper right: An arbitrary triangle is chosen as a starting point for the
algorithm, and the minimum distance to that triangle is computed. Vertex 7 is closest.
Lower left: In the next step, all vertices are projected onto the line from the origin to
vertex 7, and the closest vertex replaces the one in the triangle that is farthest away on
this projection. Thus vertex 4 replaces vertex 8. The closest point on this triangle is
then found, which is located on the edge from vertex 4 to 7. Lower right: The vertices
are projected onto the line from the origin to the closest point from the previous step,
and vertex 5 thus replaces vertex 1, which is farthest away on the projection. Vertex 5
is the closest point on this triangle, and when the vertices are projected on the line to
vertex 5, we find that vertex 5 is the closest point overall. This completes the iteration.
At this time the closest point on the triangle is found, which also happens to be vertex
5. This point is returned. (Illustration after Jim´enez et al. [611].)
i
i
i
i
i
i
i
i
820 17. Collision Detection
triangle in two dimensions, and a tetrahedron in three dimensions. Then
the point on this simplex closest to the origin is computed. Van den Bergen
shows how this can be done by solving a set of linear equations [1291, 1292].
A vector is then formed starting at the origin and ending at the nearest
point. All vertices of the polyhedron are projected onto this vector, and
the one with the smallest projection distance from the origin is chosen to
be a new vertex in the updated simplex. Since a new vertex is added to
the simplex, an existing vertex in the simplex must be removed. The one
whose projection is farthest away is deleted. At this point, the minimum
distance to the updated simplex is computed, and the algorithm iterates
through all vertices again until the algorithm cannot update the simplex
any longer. The algorithm terminates in a finite number of steps for two
polyhedra [399]. The performance of this algorithm can be improved using
many techniques, such as incremental computation and caching [1291].
Van den Bergen describes a fast and robust implementation of
GJK [1291, 1292]. GJK can also be extended to compute penetration
depth [153, 1293]. GJK is not the only algorithm for computing minimum
distance; there are many others, such as the Lin-Canny algorithm [773],
V-Clip [870], PQP [730] SWIFT [299], and SWIFT++ [300] (which also
computes distance between concave rigid bodies).
17.6.3 Deformable Models
So far, the main focus of this section has been on either static models or
rigid-body animated models. Obviously, there are other sorts of motion,
such as waves on the water or a piece of cloth swaying in the wind. This
type of motion is generally not possible to describe using rigid bodies, and
instead, one can treat each vertex as being an independent vector function
over time. Collision detection for such models is generally more expensive,
and some initial research is presented here.
Assuming that the mesh connectivity stays the same for an object dur-
ing deformation, it is possible to design clever algorithms that exploit this
property. Such deformation is what would happen to a piece of cloth in
the wind (unless it is somehow torn apart). As a preprocess, an initial
hierarchical bounding volume (BV) tree is built. Instead of actually re-
building the tree when deformation has taken place, the bounding volumes
are simply refitted to the deformed geometry [731, 1290]. By using AABBs,
which are fast to recompute, this operation is pretty efficient (as compared
to OBBs). In addition, merging k children AABBs into a parent AABB
is also quick and gives an optimal parent AABB. However, in general, any
type of BV can be used. Van den Bergen organizes his tree so that all BVs
are allocated and placed in an array, where a node always is placed so that
its index is lower than its child nodes [1290, 1292]. In this way, a bottom-
i
i
i
i
i
i
i
i
17.6. Miscellaneous Topics 821
Figure 17.17. The hybrid bottom-up/top-down tree update method. The upper levels
are updated using a bottom-up strategy, and only those nodes deeper down in the tree
that are reached during a tree traversal are updated using a top-down method.
up update can be done by traversing the array from the end backwards,
recomputing each BV at each node. This means that the BVs of the leaves
are recomputed first, and then their parents’ BVs are recomputed using
the newly computed BVs, and so on back to the root of the tree. This sort
of refit operation is reported to be about ten times as fast as rebuilding the
tree from scratch [1290].
However, it has been noted that, in general, few BVs in a tree need to
be updated. This is because most of them are not used during a collision
query. A hybrid bottom-up/top-down tree update has therefore been pro-
posed [731]. The idea is to use a bottom-up update for the higher levels
(including the root), which means that only the upper BVs will be updated
each frame. The rationale for this is that the upper levels often prune away
most geometry. These updated upper levels are tested for overlap with the
other tree (also possibly deforming and updated). For nodes that do not
overlap, we can skip the updating of their subtrees, and so save much ef-
fort. On the other hand, for nodes that do overlap, a top-down strategy
is used for updating nodes in their subtrees as they are needed during a
tree traversal. Bottom-up could also be used for these, but top-down was
found to be more effective [731]. Good results were achieved when the first
n/2 upper levels were updated with a bottom-up method, and the lower
n/2 levels with a top-down method. This is shown in Figure 17.17. To
update a node top-down, the node records which vertices its entire subtree
holds, and this list is traversed and a minimal BV is computed. When
using top-down update, overlap testing is done as soon as a BV has been
updated, so that the traversal can be terminated if no overlap is found.
This, again, gives more efficiency. Initial tests show that this method is
four to five times faster than van den Bergen’s method [731].
i
i
i
i
i
i
i
i
822 17. Collision Detection
Sometimes, one can create more efficient algorithms when there is some
known information about the type of deformation. For example, if a model
is deformed using morphing (see Section 4.5), then you can morph (i.e.,
blend) the BVs in a bounding volume hierarchy in the same way that you
morph the actual geometry [732]. This does not create optimal BVs during
morphing, but they are guaranteed to always contain the morphed geome-
try. This update can also be done in a top-down manner, i.e., only where
it is needed. This technique can be used for AABBs, k-DOPs, and spheres.
Computing a morphed BV from k different BVs costs O(k), but usually k
is very low and can be regarded as a constant. James and Pai [598] present
a framework with a reduced deformation model, which is described by a
combination of displacement fields. This provide for generous increases in
performance. Ladislav and Zara present similar CD techniques for skinned
models [708].
However, when the motion is completely unstructured and has breaking
objects, these methods do not work. Some recent techniques attempt to
track how well a subtree in a BVH fits the underlying geometry, and only
rebuilds them as needed using some heuristics [733, 1397].
Another general method for deformable objects first computes minimal
AABBs around two objects to be tested for collision [1199]. If they overlap,
the overlap AABB region is computed, which simply is the intersection
volume of the AABBs. It is only inside this overlap region that a collision
can occur. A list of all triangles inside this region is created. An octree
(see Section 14.1.3) that surrounds the entire scene is then used. The idea
is then to insert triangles into the octree’s nodes, and if triangles from both
objects are found in a leaf node, then these triangles are tested against each
other. Several optimizations are possible. First, the octree does not need
to be built explicitly. When a node gets a list of triangles, the triangles
are tested against the eight children nodes, and eight new triangle lists are
created. This recursion ends at the leaves, where triangle/triangle testing
can take place. Second, this recursion can end any time the triangle list has
triangles from only one of the objects. To avoid testing a triangle pair more
than once, a checklist is kept that tracks the tested pairs. The efficiency
of this method may break down when an overlap region is very large, or
there are many triangles in an overlap region.
17.6.4 Collision Response
Collision response is the action that should be taken to avoid (abnormal)
interpenetration of objects. Assume, for example, that a sphere is moving
toward a cube. When the sphere first hits the cube, which is determined
by collision detection algorithms, we would like the sphere to change its
trajectory (e.g., velocity direction), so it appears that they collided. This
..................Content has been hidden....................
You can't read the all page of ebook, please click here login for view all page.