i
i
i
i
i
i
i
i
17.5. A Multiple Objects CD System 813
Figure 17.11. At the top, the interval I
4
is encountered (at the point marked (a)) when
there is only one interval in the active list (I
3
), so it is concluded that I
4
and I
3
overlap.
When I
2
is encountered, I
4
is still in the active list (since e
4
has not been encountered
yet), and so I
4
and I
2
also overlap. When e
4
is encountered, I
4
is removed (at the point
marked (b)) from the active list. At the bottom, I
2
has moved to the right, and when
the insertion sort finds that s
2
and e
4
need to change places, it can also be concluded
that I
2
and I
4
do not overlap any longer. (Illustration after Witkin et al. [1363].)
sort or insertion sort [676] can be used with great efficiency after the first
pass has taken place. These sorting algorithms sort nearly-sorted lists in
an expected time of O(n).
Insertion sort works by building up the sorted sequence incrementally.
We start with the first number in the list. If we consider only this entry,
then the list is sorted. Next, we add the second entry. If the second entry
is smaller than the first, then we change places of the first and the second
entries; otherwise, we leave them be. We continue to add entries, and we
change the places of the entries, until the list is sorted. This procedure is
repeated for all objects that we want to sort, and the result is a sorted list.
To use temporal coherence to our advantage, we keep a boolean for each
interval pair. For large models, this may not be practical, as it implies an
O(n
2
) storage cost. A specific boolean is TRUE if the pair overlaps and
FALSE otherwise. The values of the booleans are initialized at the first
step of the algorithm when the first sorting is done. Assume that a pair
of intervals were overlapping in the previous frame, and so their boolean
was TRUE. Now, if the startpoint of one interval exchanges places with
the endpoint of the other interval, then the status of this interval pair is
inverted, which in this case means that their boolean is then FALSE and
they do not overlap anymore. The same goes in the other direction, i.e., if
i
i
i
i
i
i
i
i
814 17. Collision Detection
abooleanwasFALSE, then it becomes TRUE when one startpoint changes
place with one endpoint. This is also illustrated in Figure 17.11.
So we can create a sorted list of intervals for all three main axes and
use the preceding algorithm to find overlapping intervals for each axis.
If all three intervals for a pair overlap, their AABBs (which the intervals
represent) also overlap; otherwise, they do not. The expected time is linear,
which results in an O(n + k)-expected-time sweep-and-prune algorithm,
where, again, k is the number of pairwise overlaps. This makes for fast
overlap detection of the AABBs. Note that this algorithm can deteriorate
to the worst of the sorting algorithm, which may be O(n
2
). This can
happen when clumping occurs; a common example is when a large number
of objects are lying on a floor, for example. If the z-axis is pointing in the
normal direction of the floor, we get clumping on the z-axis. One solution
wouldbetoskipthez-axis entirely and only perform the testing on the x-
and y-axes [315]. In many cases, this works well.
Grids
While grids and hierarchical grids are best known as data structures for
ray tracing acceleration, they can also be used for broad phase collision
detection [1275]. In its simplest form, a grid is just an n-dimensional array
of non-overlapping grid cells that cover the entire space of the scene. Each
cell is therefore a box, where all boxes have the same size. From a high
level, broad phase CD with a grid starts with insertion of all the objects’
BVs in our scene into the grid. Then, if two objects are associated with the
same grid cell, we immediately know that the BVs of these two objects are
likely to overlap. Hence, we perform a simple BV/BV overlap test, and if
they collide, we can proceed to the second level of the CD system. To the
left in Figure 17.12, a two-dimensional grid with four objects is shown.
To obtain good performance, it is important to choose a reasonable grid
cell size. This problem is illustrated to the right in Figure 17.12. One idea
is to find the largest object in the scene, and make the grid cell size big
enough to fit that object at all possible orientations [315]. In this way, all
objects will overlap at most eight cells in the case of a three-dimensional
grid.
Storing a large grid can be quite wasteful, especially if significant por-
tions of the grid are left unused. Therefore, it has been suggested that
spatial hashing should be used instead [315, 1261, 1275]. In general, each
grid cell is mapped to an index in a hash table. All objects overlapping
with a grid cell are inserted into the hash table, and testing can continue
as usual. Without spatial hashing, we need to determine the size of the
AABB enclosing the entire scene before memory can be allocated for the
grid. We also must limit where objects can move, so they do not leave
these bounds. These problems are avoided altogether with spatial hash-
i
i
i
i
i
i
i
i
17.5. A Multiple Objects CD System 815
Figure 17.12. Left: a low-resolution two-dimensional grid with four objects. Note that
since the ellipse and the star overlap a shared grid cell, these objects have to be tested
using a BV/BV test. In this case, they do not collide. The triangle and the star also
overlap a shared grid cell, and they do in fact collide. Right: a higher-resolution grid.
As can be seen, the star overlaps with many grid cells, which can make this procedure
expensive. Also note that there are many smaller objects where clumping occurs, and
this is another possible source of inefficiency.
ing, as objects can immediately be inserted into the hash table, no matter
where they are located.
As illustrated in Figure 17.12, it is not always optimal to use the same
grid cell size in the entire grid. Therefore, we can instead turn to hierar-
chical grids. In this case, several different nested grids with different cell
sizes are used, and an object is inserted in only the grid where the object’s
BV is (just) smaller than the grid cell. If the difference in grid cell size be-
tween adjacent levels in the hierarchical grid is exactly two, this structure
is quite similar to an octree. There are many details worth knowing about
when implementing grids and hierarchical grids for CD, and we refer to the
excellent treatment of this topic by Ericson [315].
17.5.2 Summary
The outline of the two-level collision detection system is summarized below,
and depicted in Figure 17.13.
• First, using the sweep-and-prune algorithm or a grid-based technique,
all pairs of objects whose BVs overlap are detected and stored in the
pair list.
• Second, the object pairs are sent to exact collision detection algo-
rithms, such as the OBBTree.
• Finally, the results from collision detection are forwarded and taken
care of by the application, so that action (collision response) can
be taken.
i
i
i
i
i
i
i
i
816 17. Collision Detection
Broad-phase
collision
detection
Figure 17.13. The outline of the collision detection system. The overlapping object pairs
found by the first level broad phase CD algorithm are reported to the exact CD system,
which, in turn, reports true collisions to a part of the system that should compute the
collision response. Finally, all objects are treated by the simulation, where objects get
their transforms, for example. (After Cohen et al. [181].)
17.6 Miscellaneous Topics
In this section, short introductions will be given for a number of different
topics of interest: time-critical collision detection, distance queries, collision
detection of arbitrarily deformable models, and finally, collision response.
17.6.1 Time-Critical Collision Detection
Assume that a certain game engine is rendering a scene in 7 ms when the
viewer looks at a single wall, but that the rendering takes 15 ms when the
viewer is looking down a long corridor. Clearly, this will give very differ-
ent frame rates, which is usually disturbing to the user. One rendering
algorithm that attempts to achieve constant frame rate is presented in Sec-
tion 14.7.3. Here, another approach, called time-critical collision detection,
is taken, which can be used if the application uses CD as well. It is called
“time-critical” because the CD algorithm is given a certain time frame, say
9 ms, to complete its task, and it must finish within this time. Another
reason to use such algorithms for CD is that it is very important for the
perceived causality [977, 978], e.g., detecting whether one object causes
another to move. So, returning to our example, assume that we set the
goal that each frame (including CD) should take at most 20 ms, that is,
50 frames per second. With a time-critical collision detection algorithm,
i
i
i
i
i
i
i
i
17.6. Miscellaneous Topics 817
Figure 17.14. Depth-first (left) versus breadth-first (right) traversal. Depth-first traversal
is often used in collision detection when traversing the bounding volume hierarchies, but
for time-critical CD, breadth-first traversal is used.
we can see to it that the collision detection part of the rendering engine
uses what time is left, up to 20 ms. For example, if a frame uses 15 ms for
rendering, the CD part can use only 5 ms.
The following algorithm was introduced by Hubbard [572]. The idea
is to traverse the bounding volume hierarchies in breadth-first order. This
means that all nodes at one level in the tree are visited before descending
to the next level. This is in contrast to depth-first traversal,whichtraverses
the shortest way to the leaves (as done in the pseudocode in Section 17.3.2).
These two traversals are illustrated in Figure 17.14. The reason for using
breadth-first traversal is that both the left and the right subtree of a node
are visited, which means that BVs which together enclose the entire object
are visited. With depth-first traversal, we might only visit the left subtree
because the algorithm might run out of time. When we do not know
whether we have time to traverse the whole tree, it is at least better to
traverse a little of both subtrees.
The algorithm first finds all pairs of objects whose BVs overlap, using,
for example, the algorithm in Section 17.5.1. These pairs are put in a
queue, called Q. The next phase starts by taking out the first BV pair
from the queue. Their children BVs are tested against each other and if
they overlap, the children pairs are put at the end of the queue. Then the
testing continues with the next BV pair in the queue, until either the queue
is empty (in which case all of the tree has been traversed) or until we run
out of time [572].
Another related approach is to give each BV pair a priority and sort
the queue on this priority. This priority can be based on factors such as
visibility, eccentricity, distance, etc. Dingliana and O’Sullivan describe al-
gorithms for computing approximate collision response and approximate
collision contact determination [259]. This is needed for time-critical CD
since the time may run out before the tree traversal has finished. Men-
doza and O’Sullivan present a time-critical CD algorithm for deformable
objects [858].
..................Content has been hidden....................
You can't read the all page of ebook, please click here login for view all page.