Game Development Reference
In-Depth Information
earliest time the objects come in contact is given by the smallest t for which
t r
A
B .
We need to perform a ray cast on the CSO to find the t at the first hit. We will
denote this instance of time by t hit . The corresponding point t hit r is called the
hit spot . If the origin is not contained in A
B , meaning t hit > 0, then the hit
spot must be a point on the boundary of A
B . In that case, there exists a proper
normal at the hit spot.
A nonzero vector n and a point p on the boundary of the CSO define a sup-
porting plane if
n
·
p =max
{
n
·
x : x
A
B
}
.
A supporting plane exists for all points on the boundary as long as the CSO is con-
vex. Clearly, any nonzero vector n is a normal of a supporting plane at s A−B ( n ).
Let us make a few observations. For a supporting plane with normal n and
point p on the boundary of A
B , we know that all points x for which n
·
x > n
·
p
are not contained in A
B .Now,let x = t r be a point on the ray. We find that
the section of the ray corresponding to
t n
·
r > n
·
p
is not contained in A
B , and thus cannot contain the hit spot. More specifically,
for
t clip = n
·
p
r ,
n
·
we know the following:
1. If n
·
r < 0,then t clip is a lower bound for t hit . Moreover, if n
·
p < 0,then
t clip is positive and indeed the ray is clipped.
2. If n
p < 0,then
t clip is negative and the ray can be rejected since it will never hit the CSO.
·
r > 0,then t clip is an upper bound for t hit .Now,if n
·
3. If n
p < 0,
then the ray can be rejected as well, since it completely lies in the positive
half-space of the supporting plane.
·
r =0, then the ray is not clipped at all. Furthermore, if n
·
Note that in all three cases the ray is either clipped by or completely contained in
the positive half-space of the supporting plane if n
p < 0.
Our strategy for computing t hit is to iteratively clip sections of the ray that
are guaranteed not to intersect the CSO until we arrive at the hit spot. This ap-
proach is generally known as conservative advancement [Mirtich and Canny 95];
·