17. Collision Detection (7/8)

Search in book...
Toggle Font Controls
Create new playlist

Name your new playlist

Playlist description (optional)
Sign In

Email address

Password

Forgot Password?

or

Continue with Facebook

Continue with Google
Sign Up

Full Name

Email address

Confirm Email Address

Password

or

Continue with Facebook

Continue with Google

17.6. Miscellaneous Topics 823

Figure 17.18. Collision response for a sphere approaching a plane. To the left the

velocity vector v is divided into two components, v

,andv

. To the right, perfectly

elastic (bouncy) collision is shown, where the new velocity is v



= v

− v

.Foraless

elastic collision, the length of −v

could be decreased.

is the task of collision response techniques, which has been and still is the

subject of intensive research [58, 258, 478, 869, 901, 1363]. It is a complex

topic, and in this section only the simplest technique will be presented.

In Section 16.18.3, a technique for computing the exact time of collision

between a sphere and a plane was presented. Here we will explain what

happens to the sphere’s motion at the time of collision.

Assume that a sphere is moving towards a plane. The velocity vector

is v, and the plane is π : n · x + d =0,wheren is normalized. This is

shown in Figure 17.18. To compute the simplest response, we represent the

velocity vector as

v = v

+ v

, where

=(v · n)n,

= v − v

(17.13)

With this representation, the velocity vector, v



, after the collision

is [718]



= v

− v

. (17.14)

Here, we have assumed that the response was totally elastic. This means

that no kinetic energy is lost, and thus that the response is “perfectly

bouncy” [1363]. Now, normally the ball is deformed slightly at collision,

and some energy transformed into heat, so some energy is lost. This is

described with a coeﬃcient of restitution, k (often also denoted ). The

velocity parallel to the plane, v

, remains unchanged, while v

is dampened

with k ∈ [0, 1]:



= v

− kv

. (17.15)

As k gets smaller, more and more energy is lost, and the collision ap-

pears less and less bouncy. At k = 0, the motion after collision is parallel

to the plane, so the ball appears to roll on the plane.

824 17. Collision Detection

More sophisticated collision response is based on physics, and involves

creating a system of equations that is solved using an ordinary diﬀeren-

tial equation (ODE) solver. In such algorithms, a point of collision and

a normal at this point is needed. The interested reader should consult

the SIGGRAPH course notes by Witkin et al. [1363] and the paper by

Dingliana et al. [258]. Also, O’Sullivan and Dingliana present experiments

that show that it is hard for a human to judge whether a collision response

is correct [977, 978]. This is especially true when more dimensions are

involved (i.e., it is easier in one dimension than in three). To produce a

real-time algorithm, they found that when there was not time enough to

compute an accurate response, a random collision response could be used.

These were found to be as believable as more accurate responses.

17.6.5 GPU-Based Collision Detection

It has been long known that rasterization can be used detect collisions

[1168]. The major diﬀerence between what has been described so far in

this chapter is that algorithms based on GPUs are often performed in

image space. This is in contrast to the techniques operating directly on the

geometry.

There is a wealth of algorithms for performing CD on the GPU, and

here we will present only one of the algorithms, called CULLIDE [436]. The

basic idea is to use occlusion queries (see Section 14.6.1) to perform a test

that determines whether an object, O, is “fully visible” (i.e., not colliding

with) another set of objects, S. Recall that an occlusion query is usually

used with a less-or-equal depth test. The occlusion query can count the

number of fragments that pass the depth test, and if no fragments pass,

then we can be certain that the rendered object (or its bounding box) is

occluded with respect to the contents of the depth buﬀer.

For collision detection, we are instead interested in ﬁnding objects that

deﬁnitely do not overlap with other objects. Govindaraju et al. suggest

that this is done by reversing the depth test, so that we use greater-or-

equal, and writing to the depth buﬀer is turned oﬀ. If both the front and

the back faces of an object are rendered, and no fragment pass the depth

test, we can conclude that the object is fully visible with respect to the

depth buﬀer. In this way, we test for overlap in the depth direction, and

in the image plane.

Next, we describe how this test can be used to implement a broad-phase

collision detection algorithm on the GPU. Assume there are n objects, de-

noted O

,1≤ i ≤ n.ThatO

does not collide with any other object simply

means that it does not collide with any of the objects, O

,...,O

i−1

,nor

with any of O

i+1

,...,O

. This can be formulated as an eﬃcient rendering

algorithm. In a ﬁrst pass, the objects are rendered in order, and we test

17.6. Miscellaneous Topics 825

Figure 17.19. To the left, two triangles are shown on top of the pixel grid. In the middle,

the triangles have been rendered using standard rasterization (with one sample at the

center of each pixel), and as can be seen no overlap between the triangles is detected.

To the right the triangles have been rasterized conservatively, so that each pixel that

overlaps with a triangle is visited. This correctly detects the true geometric overlap.

whether each object is fully visible with respect to the objects already ren-

dered. So, when O

is being rendered, this means that we test it against

,...,O

i−1

. In the second pass, we render the objects in reversed order,

and this means that O

now is tested against O

i+1

,...,O

.Thistypeof

rendering is done using orthographic projection, and typically it is done

once for each axis (x, y,andz). In other words, the objects are evaluated

from six views. If any pair overlaps from all six it is likely they may collide.

The result is a small set of objects that can potentially collide, and this

set is often called a potentially colliding set (PCS). This test can also be

improved by using another object level, i.e., by splitting each object into

a set of smaller sub-objects and continue with similar testing there. In

the end, the remaining objects or triangles in the PCS are tested for true

overlap by the CPU.

It should be noted that the performance and accuracy of these types of

image-space algorithms is inﬂuenced by the screen resolution, and in the

case of CULLIDE, also the accuracy of the depth buﬀer. In general, with a

higher resolution, we will get better accuracy and fewer objects in the PCS,

but this will also aﬀect the ﬁll rate requirements, and vice versa. For truly

correct results, we also need a conservative rasterizer [509]. The reason for

this is that the rasterizer usually only samples the geometry at the center

of the pixel. What is needed for collision detection is a rasterizer that

visits every pixel that is overlapping (ever so slightly) with the geometry

being rendered. An example of when standard rasterization can go wrong

is shown in Figure 17.19. Note that this problem can be ameliorated by

using a higher resolution, but the problem cannot be completely avoided.

Govindaraju et al. [438] have extended the CULLIDE system so that

it also can handle self-collision detection (for deformable objects) using a

new visibility testing algorithm. Georgii et al. [389] use depth peeling to

detect possible collision in the depth direction, and a mipmap hierarchy

of bounding boxes to further prune the PCS. In the end a sparse texture

826 17. Collision Detection

is packed into smaller representation, and read back to the CPU for exact

polygon-polygon testing. Collisions between objects can truly deform the

objects simply by painting the colliding areas onto the texture [1381].

17.7 Other Work

The OBBTree algorithm has been extended by Eberly to handle dynamic

collision detection [294]. This work is brieﬂy described in IEEE CG&A [89].

Algorithms for collision detection of extremely large models (millions of

triangles) have been presented by Wilson et al. [1355]. They combine BVHs

of spheres, AABBs, and OBBs, with a data structure called the overlap

graph, lazy creation of BVHs, temporal coherence, and more, into a system

called IMMPACT. Storing a bounding volume hierarchy may use much

memory, and so Gomez presents some methods for compressing an AABB

tree [421].

Frisken et al. [365] present a framework for soft bodies, where colli-

sions, impact forces, and contact determination can be computed eﬃciently.

Their framework is based on adaptively sampled distance ﬁelds (ADFs),

which is a relatively new shape representation [364].

Baraﬀ and Witkin [59] and Hughes et al. [575] present collision detection

algorithms for objects undergoing polynomial deformation. Another more

general system for arbitrary deformable objects is presented by Ganovelli et

al. [375]. Related to his are algorithms for response and collision detection

for cloth. This is treated by Baraﬀ and Witkin [61], Courshesnes et al. [202],

and Volino and Magnenat-Thalmann [1307, 1308]. Another complex phe-

nomenon is CD of hair. Hadap and Magnenat-Thalmann [473] treat hair

as a continuum, which makes it possible to simulate hair relatively quickly.

Distance queries have been extended to handle concave objects by Quin-

lan [1042], and Ehmann and Lin also handle concave objects by decom-

posing an object into convex parts [300]. Kawachi and Suzuki present

another algorithm for computing the minimum distance between concave

parts [638].

Table of Contents for 17. Collision Detection (7/8)

Create new playlist

Sign In

Sign Up

Table of Contents for
17. Collision Detection (7/8)