Numerical Robustness - Real-Time Collision Detection - page 460

on the plane due to the rounding caused by the integer division. Therefore, Q must
somehow be adjusted to guarantee that it lies on or in front of the plane. There are two
problems to address when performing the adjustment. First, the adjustment must be
large enough to ensure that the new point position lies in front of the plane. Second,
the adjustment must not move Q to cause the segment AQ to intersect some other
geometry.
To address the first problem, the following approach can be used. Assume, without
loss of generality, that A lies in front of plane P . Then, Q must be adjusted to also lie
in front of P to satisfy ( n

d . A simple way of achieving this goal is to round
each coordinate component of Q to maximize n

· Q ) ≥

· Q . That is, if n x > 0, Q x is rounded

upward, and if n x < 0, Q x is rounded downward. Specifically, let t nom = ( d − n · A )

and t denom = n · ( B − A ). The adjusted Q x is then given by

k ) t denom ,

Q x = A x + ( t nom ( B x − A x ) +

where k 1 to round down. Q y and Q z

are computed analogously. This procedure does not necessarily result in the small-
est adjustment to Q , but for collision detection the actual position of Q is of less
importance than Q lying on the correct side of plane P .
The following integer version of TestSegmentPlane() illustrates how the intersec-
tion point adjustment can be implemented. It is assumed that Point , Vector , and
Plane are defined in terms of the 32-bit integer type int32 .

= t denom − 1 to round up and k =− t denom +

// Test if segment ab intersects plane p. If so, return 1, along with
// an adjusted intersection point q. If not, return 0
int TestSegmentPlane(Point a, Point b, Plane p, Point &q)
{

// Compute t value, t=tnom/tdenom, for directed segment ab intersecting plane p
Vector ab=b-a;
int64 tnom = p.d - Dot(p.n, a);
int64 tdenom = Dot(p.n, ab);
// Exit if segment is parallel to plane
if (tdenom == 0) return 0;

// Ensure denominator is positive so it can be multiplied through throughout
if (tdenom < 0) {
tnom = -tnom;
tdenom = -tdenom;

}

// If t not in [0..1], no intersection
if (tnom<0||tnom > tdenom) return 0;