17. Collision Detection (3/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.3. General Hierarchical Collision Detection 803

are decomposed into triangles (see Section 12.2). Then, since each model

should be represented as a hierarchy of some kind of bounding volumes,

methods must be developed that build such hierarchies with the desired

properties. A hierarchy that is commonly used in the case of collision

detection algorithms is a data structure called a k-ary tree, where each

node may have at most k children (see Section 14.1). Many algorithms use

the simplest instance of the k-ary tree, namely the binary tree, where k =2.

At each internal node, there is a BV that encloses all of its children in its

volume, and at each leaf are one or more primitives (which in our case are

triangles). The bounding volume of an arbitrary node (either an internal

node or a leaf), A, is denoted A

, and the set of children belonging to A

is denoted A

There are three main ways to build a hierarchy: a bottom-up method,

an incremental tree-insertion,oratop-down approach. In order to create

eﬃcient, tight structures, typically the areas or the volumes of the BVs

are minimized wherever possible [63, 417, 672, 966]. For CD, it makes

more sense to minimize volume since a BV is tested against another BV.

The ﬁrst of these methods, bottom-up, starts by combining a number of

primitives and ﬁnding a BV for them. These primitives should be located

close together, which can be determined by using the distance between

the primitives. Then, either new BVs can be created in the same way,

or existing BVs can be grouped with one or more BVs constructed in a

similar way, thus yielding a new, larger parent BV. This is repeated until

only one BV exists, which then becomes the root of the hierarchy. In this

way, closely located primitives are always located near each other in the

bounding volume hierarchy. Barequet et al. present BOXTREE [63], a data

structure for performing ray tracing and collision detection, where the tree

is built from the bottom up.

The incremental tree-insertion method starts with an empty tree. Then

all other primitives and their BVs are added one at a time to this tree. This

Figure 17.8. On the left, a binary tree with three nodes is shown. We assume that only

one primitive is stored at each leaf. Now we wish to insert a new node, named N .This

node has a bounding volume (BV) and a primitive that BV encloses. Therefore, the

node will be inserted as a leaf node. In this example, say we ﬁnd that the total tree

volume is smaller if we insert N atthenodecalledC (rather than at B). Then a new

parent node P is created that encloses both C and the new node N.

804 17. Collision Detection

is illustrated in Figure 17.8. To make an eﬃcient tree, an insertion point

in the tree must be found. This point should be selected so that the total

tree volume increase is minimized. A simple method for doing this is to

descend to the child that gives a smaller increase in the tree. This kind

of algorithm typically takes O(n log n) time. Randomizing the ordering

in which primitives are inserted can improve tree formation [417]. For

more sophisticated methods, see Omohundro’s work [966]. Little is known

about incremental tree-insertion in the context of collision detection, but

it has been used with good results in ray tracing [417] and in intersection

queries [966], so it probably works well for collision detection, too.

The top-down approach, which is used by the majority of hierarchy

construction algorithms, starts by ﬁnding a BV for all primitives of the

model, which then acts as the root of the tree. Then a divide-and-conquer

strategy is applied, where the BV is ﬁrst split into k or fewer parts. For each

such part, all included primitives are found, and then a BV is created in the

same manner as for the root, i.e., the hierarchy is created recursively. It is

most common to ﬁnd some axis along which the primitives should be split,

and then to ﬁnd a good split point on this axis. In Section 16.4 geometric

probability is discussed, and this can be used when searching for a good split

point, which will result in better BVHs. Note that a potential advantage

of the top-down approach is that a hierarchy can be created lazily, i.e., on

an as-needed basis. This means that we construct the hierarchy only for

those parts of the scene where it is actually needed. But since this building

process is performed during runtime, whenever a part of the hierarchy is

created, the performance may go down signiﬁcantly. This is not acceptable

for applications such as games with real-time requirements, but may be a

great time and memory saver for CAD applications or oﬀ-line calculations

such as path planning, animation, and more.

One challenge for CD algorithms is to ﬁnd tight-ﬁtting bounding vol-

umes and hierarchy construction methods that create balanced and eﬃcient

trees. Note that balanced trees are expected to perform best on average

in all cases, since the depth of every leaf is the same (or almost the same).

This means that it takes an equal amount of time to traverse the hierarchy

down to any leaf (i.e., a primitive), and that the time of a collision query

will not vary depending on which leaves are accessed. In this sense, a bal-

anced tree is optimal. However, this does not mean that it is best for all

inputs. For example, if part of a model will seldom or never be queried for

a collision, then those parts can be located deep in an unbalanced tree, so

that the parts that are queried most often are closer to the root [434]. The

details of this procedure for an OBB tree is described on page 809.

Note also that several spatial data structures are described in relation

to accelerations algorithms in Section 14.1, and that BV creation is treated

in Section 16.3.

17.3. General Hierarchical Collision Detection 805

17.3.2 Collision Testing between Hierarchies

Usually there are two diﬀerent situations that we want to detect at diﬀer-

ent times. First, we might only be interested in whether or not the two

models collide, and then the method may terminate whenever a pair of

triangles has been found to overlap. Second, we might want all pairs of

overlapping triangles reported. The solution to the ﬁrst problem is called

collision detection, while the solution to the second is called collision de-

termination. Here, pseudocode is given that solves the ﬁrst problem. The

second situation can be solved with small alterations of the given code, and

will be discussed later.

A and B are two nodes in the model hierarchies, which at the ﬁrst call

are the roots of the models. A

and B

are used to access the BV of

the appropriate node. Recall that A

is the set of children nodes of A,and

that T

is used to denote the triangle of a leaf node (in the pseudocode,

only one triangle per node is assumed). The basic idea is, when overlap is

detected, to open a (larger) box and recursively test its contents.

FindFirstHitCD(A, B)

returns ({TRUE, FALSE});

1: if(isLeaf(A) and isLeaf(B))

2: if(overlap(T

)) return TRUE;

3: else if(isNotLeaf(A) and isNotLeaf(B))

4: if(overlap(A

))

5: if(Volume(A) > Volume(B))

6: for each child C ∈ A

7: FindFirstHitCD(C, B)

8: else

9: for each child C ∈ B

10 : FindFirstHitCD(A, C)

11 : else if(isLeaf(A) and isNotLeaf(B))

12 : if(overlap(T

))

13 : for each child C ∈ B

14 : FindFirstHitCD(C, A)

15 : else

16 : if(overlap(T

))

17 : for each child C ∈ A

18 : FindFirstHitCD(C, B)

19 : return FALSE;

As can be seen in this pseudocode, there are portions of code that could

be shared, but it is presented like this to show how the algorithm works.

Some lines deserve some attention. Lines 1–2 take care of the case where

both nodes are leaves. Lines 3–10 handle the case where both nodes are in-

806 17. Collision Detection

ternal nodes. The consequence of the comparison Volume(A) > Volume(B)

is that the node with the largest volume is descended. The idea behind such

a test is to get the same tree traversal for the calls FindFirstHitCD(A, B)

and for FindFirstHitCD(B,A), so that traversal becomes deterministic.

This is important if the ﬁrst collision detected has a special status (early

end, collision response, etc.). Perhaps even more important is that this

tends to give better performance, as the largest box is traversed ﬁrst at

each step. Another idea is to alternate between descending A and B.This

avoids the volume computation, and so could be faster. Alternatively, the

volume can be precomputed for rigid bodies, but this requires extra mem-

ory per node. Also, note for many BVs the actual volume need not be

computed, since it suﬃces with a computation that preserves the “volume

order.” As an example, for sphere it suﬃces to compare the radii.

To ﬁnd all pairs of triangles that collide, this pseudocode is modiﬁed in

the following way. The pairs of triangles that the algorithm ﬁnds are stored

in a global list, L, which begins empty. Then Line 2 requires modiﬁcation:

If the test is passed, the program should add the triangle pair to L (instead

of returning). When recursion ends, all the collision are found in L.

17.3.3 Cost Function

The function t in Equation 17.7 below was ﬁrst introduced (in a slightly

diﬀerent form, without the last term) as a framework for evaluating the

performance of hierarchical BV structures in the context of acceleration

algorithms for ray tracing [1336]. It has since been used to evaluate the

performance of CD algorithms as well [433], and it has been augmented by

the last term to include a new cost speciﬁc to some systems [672, 699] that

might have a signiﬁcant impact on performance. This cost results from the

fact that if a model is undergoing a rigid-body motion, then its BV and

parts or all of its hierarchy might have to be recomputed, depending on

the motion and the choice of BV:

t = n

+ n

. (17.7)

Here, the parameters are

: number of BV/BV overlap tests

: cost for a BV/BV overlap test

: number of primitive pairs tested for overlap

: cost for testing whether two primitives overlap

: number of BVs updated due to the model’s motion

: cost for updating a BV

Creating a better hierarchical decomposition of a model would result in

lower values of n

, n

,andn

. Creating better methods for determining

17.4. OBBTree 807

whether two BVs or two triangles overlap would lower c

and c

. However,

these are often conﬂicting goals, because changing the type of BV in order

to use a faster overlap test usually means that we get looser-ﬁtting volumes.

Examples of diﬀerent bounding volumes that have been used in the

past are spheres [572], axis-aligned bounding boxes (AABBs) [537, 1290],

oriented bounding boxes (OBBs) [433], k-DOPs (discrete oriented poly-

topes) [672, 686, 1399], pie slices [63], spherical shells [699, 700] (which

provide a good ﬁt for B´ezier patches), line swept spheres (LSSs), rectangle

swept spheres (RSSs) [730], and QuOSPOs (which combines the advan-

tages of OBBs and k-DOPs) [514]. Spheres are the fastest to transform,

and the overlap test is also fast, but they provide quite a poor ﬁt. AABBs

normally provide a better ﬁt and a fast overlap test, and they are a good

choice if there is a large amount of axially aligned geometry in a model

(as is the case in most architectural models). OBBs have a much better

ﬁt, but slower overlap tests. The ﬁt of the k-DOPs are determined by the

parameter k—higher values of k give a better ﬁt, slower overlap testing,

and poorer transform speed. For more information on k-DOPTrees, we

refer the reader to the work by Klosowski et al. [538, 672, 673].

There are obviously many parameters to ﬁne tune in order to get good

performance, and that is the focus of the following section on the OBBTree.

17.4 OBBTree

In this section, we will present the OBBTree, ﬁrst developed by Gottschalk

et al. [433], which is a data structure that has inﬂuenced the CD ﬁeld

substantially.

The OBBTree was designed to perform especially well if parallel close

proximity, where two surfaces are very close and nearly parallel, is found

during collision detection. These kinds of situations often occur in tolerance

analysis and in virtual prototyping.

Choice of Bounding Volume

AsthenameoftheOBBTree algorithm implies, the bounding volume used

is the oriented bounding box, the OBB. One reason for this choice is that

both the AABB (axis-aligned bounding box) and the sphere, which were

commonly used in previous CD algorithms, provide quite a poor ﬁt in gen-

eral. That is, they contain much empty space compared to the geometry

they are holding. The convergence of the OBB to the underlying geometry

of the models was generally better than that for either AABBs or spheres.

In 1981, Ballard [56] did similar work in two dimensions for computing intersections

between curves, so his work was a precursor to the OBBTree.

..................Content has been hidden....................

You can't read the all page of ebook, please click here login for view all page.

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

Create new playlist

Sign In

Sign Up

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