Graphics Reference
In-Depth Information
Finally, the center-radius representation results in the following overlap test:
int TestAABBAABB(AABB a, AABB b)
{
if (Abs(a.c[0] - b.c[0]) > (a.r[0] + b.r[0])) return 0;
if (Abs(a.c[1] - b.c[1]) > (a.r[1] + b.r[1])) return 0;
if (Abs(a.c[2] - b.c[2]) > (a.r[2] + b.r[2])) return 0;
return 1;
}
On modern architectures, the
Abs()
call typically translates into just a single
instruction. If not, the function can be effectively implemented by simply stripping
the sign bit of the binary representation of the floating-point value. When the AABB
fields are declared as integers instead of floats, an alternative test for the center-
radius representation can be performed as follows. With integers, overlap between
two ranges
[
A
,
B
]
and
[
C
,
D
]
can be determined by the expression
overlap = (unsigned int)(B - C) <= (B - A) + (D - C);
B
, the left-hand side
becomes an impossibly large value, rendering the expression false. The forced over-
flow effectively serves to replace the absolute value function call and allows the
center-radius representation test to be written as:
By forcing an unsigned underflow in the case when
C
>
int TestAABBAABB(AABB a, AABB b)
{
int r;
r = a.r[0] + b.r[0]; if ((unsigned int)(a.c[0] - b.c[0] + r)>r+r)return 0;
r = a.r[1] + b.r[1]; if ((unsigned int)(a.c[1] - b.c[1] + r)>r+r)return 0;
r = a.r[2] + b.r[2]; if ((unsigned int)(a.c[2] - b.c[2] + r)>r+r)return 0;
return 1;
}
Working in integers allows other implementational tricks, many of which are archi-
tecture dependent. SIMD instructions, if present, typically allow AABB tests to be
implemented in just a few instructions worth of code (examples of which are found
in Chapter 13). Finally, in a collision detection system that has to perform a mas-
sive number of overlap tests it may be worthwhile ordering the tests according to
the likelihood of their being taken. For instance, if operations largely take place in
an almost flat
xz
plane the
y
-coordinate test should be performed last, as it is least
discriminatory.
