Efficient Collision Detection of Complex Deformable Models using AABB Trees
G INO VAN DEN B ERGEN
Department of Mathematics and Computing Science
Eindhoven University of Technology
P.O. Box 513, 5600 MB Eindhoven
The Netherlands
E-mail: gino@win.tue.nl
November 6, 1998
Abstract
We prent a scheme for exact collision detection between complex models undergoing rigid motion and deformation. The scheme relies on a hierarchical model reprentation using axis-aligned bounding boxes (AABBs). In recent work, AABB trees have been shown to be slower than oriented bou
nding box (OBB) trees. In this paper, we describe a way to speed up overlap tests between AABBs, such that for collision detection of rigid models, the difference in performance between the two reprentations is greatly reduced. Furthermore, we show how to quickly update an AABB tree as a model is deformed. We thus find AABB trees to be the method of choice for collision detection of complex models undergoing deformation. In fact, becau they are not much slower to test, are faster to build, and u less storage than OBB trees, AABB trees might be a reasonable choice for rigid models as well.
Keywords: computer animation, collision detection, hierarchical data structures, deformable models
1
2 Building an AABB Tree
The AABB tree that we consider is, as the OBB tree described in [4], a binary
来电显示归属地tree. The two structures differ with respect to the freedom of placement of the
bounding boxes: AABBs are aligned to the axes of the model’s local coordinate
system, whereas OBBs can be arbitrarily oriented. The added freedom of an OBB
is gained at a considerable cost of storage space. An OBB is reprented using
15 scalars (9 scalars for a 3 ×3 matrix reprenting the orientation, 3 scalars for
position, and 3 for extent), whereas an AABB only requires 6 scalars (for position
and extent). Hence, an AABB tree of a model requires roughly half as much
storage space as an OBB tree of the same model.
An AABB tree is constructed top-down, by recursive subdivision. At each
recursion step, the smallest AABB of the t of primitives is computed, and the
t is split by ordering the primitives with respect to a well-chon partitioning
plane. This process continues until each subt contains one element. Thus, an
水浒传第一回
AABB tree for a t of n primitives has n leaves and n −1 internal nodes.
At each step, we choo the partitioning plane orthogonal to the longest axis
of the AABB. In this way, we get a ‘fat’ subdivision. In general, fat AABBs, i.e.,
cube-like rather than oblong, yield a better performance in interction testing,
since under the assumption that the boxes in a tree mutually overlap as little as
possible, a given query box can overlap fewer fat boxes than thin boxes.
We position the partitioning plane along the longest axis, by choosing δ,the
coordinate on the longest axis where the partitioning plane intercts the axis. We
动物名字then split the t of primitives into a negative and positive subt corresponding
to the respective halfspaces of the plane. A primitive is classified as positive if
the midpoint of its projection onto the axis is greater than δ, and negative other
wi. Figure 1 shows a primitive that straddles the partitioning plane depicted by
a dashed line. This primitive is classified as positive. It can be en that by using
this subdivision method, the degree of overlap between the AABBs of the two
subts is kept small.
For choosing the partitioning coordinate δwe tried veral heuristics. Our ex
periments with AABB trees for a number of polygonal models showed us that, in不可思议英语
字组词general, the best performance is achieved by simply choosing δto be the median
of the AABB, thus splitting the box in two equal halves. Using this heuristic, it
may take O(n2)time in the worst ca to build an AABB tree for n primitives, however, in the usual ca where the primitives are distributed more or less uni
formly over the box, building an AABB tree takes only O(n log n)time. Other
heuristics we have tried, that didn’t perform as well, are: (a) subdividing the t of
3
-
敬老院活动策划书
+
min δ mid max招聘计划书
Figure 1: The primitive is classified as positive, since its midpoint on the coordinate axis is greater than δ.
primitives in two ts of equal size, thus building an optimally balanced tree, and (b) building a halfbalanced tree, i.e., the larger subt is at most twice as large as the smaller one, and the overlap of the subts’ AABBs projected onto the longest axis is minimized.
Occasionally, it may occur that all primitives are classified to the same side of the plane. This will happen most frequently when the t of primitives contains only a few elements. In this ca, we simply split the t in two subts of (almost) equal size, disregarding the geometric location of the primitives.
Building an AABB tree of a given model is faster than building an OBB tree for that model, since the estimation of the best orientation of an OBB for a given t of primitives requires additional computations. We found that building an OBB tree takes about three times as much time as building an AABB tree, as is shown in Section 5.
3 Interction Testing
An interction test between two models is done by recursively testing pairs of nodes. For each visited pair of nodes, the AABBs are tested for overlap. Only the nodes for which the AABBs overlap are further traverd. If both nodes are leaves then the primitives are tested for interction and the result of the test is pasd
4
back. Otherwi, if one of the nodes is a leaf and the other an internal node, then the leaf node is tested for interction with each of the children of the internal node. Finally, if both nodes are internal nodes then the node with smaller volume is tested for interction with the children of the node with the larger volume. The latter heuristic choice of unfolding the node with the largest volume results in the largest reduction of total volume size in the following AABB tests, thus the lowest probability of the following tested boxes overlapping.
Since the local coordinate systems of a pair of models may be arbitrarily oriented, we need an overlap test for relatively oriented boxes. A fast overlap test for oriented boxes is prented by Gottschalk in [4]. We will refer to this test as the parating axes test (SAT). A parating axis of two
boxes is an axis for which the projections of the boxes onto the axis do not overlap. The existence of a parating axis for a pair of boxes sufficiently classifies the boxes as disjoint. It can be shown that for any disjoint pair of convex three-dimensional polytopes a parating axis can be found that is either orthogonal to a facet of one of the polytopes, or orthogonal to an edge from each polytope [3]. This results in 15 potential parating axes that need to be tested for a pair of oriented boxes (3 facet orientations per box plus 9 pairwi combinations of edge directions). The SAT exits as soon as a parating axis is found. If none of the 15 axes parate the boxes, then the boxes overlap.
We refer to the original paper for details on how the SAT is implemented such that it us the least number of operations. For the following discussion, it is important to note that this implementation requires the relative orientation reprented by a 3 ×3 matrix, and its absolute value, i.e., the matrix of absolute values of matrix elements, to be computed before performing the 15 axes tests.
In general, testing two AABB trees for interction requires more box overlap tests than testing two OBB trees of the same models, since the smallest AABB of a t of primitives is usually larger than the smallest OBB. However, since each tested pair of boxes of two OBB trees normally has a different relative orientation, the matrix operations for computing this orientation and its absolute value are repeated for each tested pair of boxes, whereas for AABB trees the relative orientation is t
he same for each tested pair of boxes, and thus needs to be computed only once. Therefore, the performance of an AABB tree might not be as bad as we would expect. The empirical results in Section 5 show that, by exploiting this feature, interction testing using AABB trees usually takes only 50% longer than using OBB trees in cas where there is a lot of overlap among the models.
For both tree types, the most time consuming operation in the interction test is the SAT, so let us e if there is room for improvement. We found that,
5守岁诗
1 2 3 4 5 6 7 8 9101112131415
Figure 2: Distribution of axes on which the SAT exits in ca of the boxes being disjoint. Axes 1 to 6 correspond to the facet orientations of the boxes, and axes 7 to 15 correspond to the combinations of edge directions.
6
