Numerical Robustness - Real-Time Collision Detection - page 444

11.3.2 Robustness Through Thick Planes

To illustrate the problems that may occur due to most real numbers not being exactly
representable as floating-point numbers, consider computing the intersection point
of two line segments AB and CD , as shown in Figure 11.5. The grid points correspond
to machine-representable numbers. Because the exact intersection point P does not
lie on the grid, it is snapped to some neighboring grid point Q , according to the active
rounding rule. Imagine CD constitutes a 2D world boundary and AB the directed
movement of a point object. Placing the point at position Q effectively moves it
outside the world, likely causing the point to fall out of the world, not detecting any
more collisions on future movements.
In 3D, a similar problem situation occurs when, for example, intersecting a segment
AB against a plane P . Due to floating-point errors, the computed intersection point is
unlikely to lie on either AB or P . Instead, it lies somewhere in the immediate vicinity
of both, as illustrated in Figure 11.6a. Because the intersection point ends up behind
the plane roughly half the time, a point object moving from A to B is again very likely
to end up falling out of the world.
An effective way of dealing with the problem of intersection points not lying on
the plane is to introduce a tolerance, treating the plane as having thickness . Let the
maximum distance a computed intersection point can deviate from P be denoted
by e . Then if the plane is treated as having a radius of r , r e , the intersection point

— wherever it is — must lie on this thick plane and fall-through is avoided (Figure
11.6b). Determining how large e can be, so that an appropriate r can be chosen, is
not trivial and depends on many application-specific factors. A pragmatic solution is
to determine r empirically by testing intersection points against the thick plane and
increasing r until all intersection points (over the full range of input values) correctly
classify as lying on the thick plane.
Introducing thick planes also helps increase the accuracy of the intersection point
between the segment and the plane. If the segment is nearly perpendicular to the

>

A

D

P

Q

C

B

Figure 11.5 The intersection point P between two segments AB and CD is rarely exactly
representable using floating-point numbers.

It is approximated by snapping to a nearby

machine-representable point Q .