Graphics Reference
In-Depth Information
p = (p1.d*u+Cross(p1.n, p3.d * p2.n - p2.d * p3.n)) / denom;
return 1;
}
The good news here is that both approaches presented are really generic solvers for
3
3 systems of linear equations. They are not limited to computing the intersection
point of three nonparallel planes.
×
5.5 Dynamic Intersection Tests
So far, the described tests have involved what amounts to static objects: the inter-
section of two objects at a given point in time. A problem with static testing is that
as the object movement increases between one point in time and the next so does
the likelihood of an object simply jumping past another object. This unwanted phe-
nomenon is called tunneling . Figure 5.32a illustrates this case with a moving sphere
tunneling past a rectangular obstruction.
The ideal solution is to have the object move continuously along its path of motion,
describing the motion parametrically over time, and solving for the point in time
where the distance to some other object becomes zero. Figure 5.32b illustrates this
continuous swept test . However, although solving the time of collision is feasible for
simple motion and simple objects dealing with arbitrary motion and complex objects
is a much more challenging problem. In fact, it is too expensive to address in most
real-time applications.
A compromise is to sample the path of the object and perform several static object
tests during a single object movement. Figure 5.32c shows how the movement of
the sphere can be subdivided into smaller steps, performing a static object-object
test at each sample point.
Tunneling can be avoided, in part, by making sure the moving object overlaps itself
from one sample point to the next. However, as indicated by the black triangle in
part (c) of the drawing there are still places where small or narrow objects may be
tunneled past. To fully address the tunneling problem, the objects would also have to
be extended in size so that all samples would together fully cover the volume formed
by the continuously swept object.
The drawback with sampling is that, worst case, no collision occurs and all n
sample points along the movement path have to be tested, resulting in an O ( n )
time complexity. Note that for the sampling method it is not really the time that
should be subdivided and sampled but the object motion. Subdividing the object
motion to maintain object overlap is not a trivial problem for other than the simplest
motions.
In many cases, objects can be assumed to be moving piecewise linearly; that is,
only translating between positions, with immediate rotational changes at the start
 
Search WWH ::




Custom Search