Graphics Reference
In-Depth Information
splitting along the longest axis of the OBB. Thanks to the covariance-fitted OBB, this
axis corresponds to the axis of greatest spread. The object mean (computed from the
projection of the primitive vertices onto the axis) is used as the splitting point.
Primitives straddling the splitting plane are assigned to the corresponding subset
of the halfspace their centroids are in. If the longest axis fails to create two nonempty
subsets, they instead try the other axes in decreasing order of length. If all axes fail,
the set is considered indivisible. However, in the publicly available implementation
(called RAPID) if the initial partitioning fails instead of trying alternative axes the set
is simply partitioned into two equal parts based on the object median.
A strength of OBB trees is that they perform extremely well in situations of parallel
close proximity between two surfaces; that is, when all points of the first surface are
close to some point on the other surface. It can also be shown that hierarchies of OBBs
converge quadratically to match the bounded geometry, whereas AABBs and spheres
converge only linearly. In other words, if
O
(
m
) OBBs are required to approximate
some geometry within a given tolerance
O
(
m
2
) AABBs or spheres would be required
for the same task. Both
N
V
and
N
P
in the cost function tend to be smaller for OBB
trees compared to AABB and sphere trees. However, the cost for the overlap test
between two OBBs,
C
V
, is still about a magnitude slower than the overlap tests for
AABBs and spheres.
6.4.2
AABB Trees and BoxTrees
In [Bergen97] the author describes constructing binary AABB trees using top-down
recursive subdivision. At each step the set of primitives is tightly bounded with an
AABB. The set is then partitioned into two parts by splitting the AABB orthogonally
along its longest side. Primitives are assigned to the two subsets based on which side
of the splitting plane the midpoint of the projection ends up on. This assignment
method minimizes the overlap between the AABBs of the subsets, as no primitive
can now extend beyond the splitting plane by more than half its length.
The recursive construction procedure is then repeated until the subset contains one
primitive. The splitting point is chosen as the spatial median, splitting the AABB in
half. van den Bergen reports better performance with this method than with splitting
at the object median. In the rare case in which all primitives end up in one of the
subsets the set is instead split based on the object median.
The informed traversal method is used along with the “descend larger” rule to
traverse the trees. Instead of realigning the AABB trees as their objects rotate, the OBB
test is used to compare the — after transformation — relatively oriented AABBs. As
the same relative orientation is shared between all transformed AABB pairs, the trans-
formation matrix needs to be computed just once per query, simplifying the OBB test.
van den Bergen also reports obtaining a speed increase from performing only the
first 6 of the 15 axis tests for the rotated AABB tests. This is a trade-off that results
in an overall cheaper test but also false hits that give rise to more (costly) primitive
tests. The same optimization applied to OBB trees resulted in no change.
