Graphics Reference
In-Depth Information
// Line segment is definitely intersecting plane. Compute vector d to adjust
// the computation of q, biasing the result to lie on the side of point a
Vector d(0,0,0);
int64 k = tdenom - 1;
// If a lies behind plane p, round division other way
if (tdenom > 0)k=-k;
if (p.n.x > 0) d.x = k; else if (p.n.x < 0) d.x = -k;
if (p.n.y > 0) d.y = k; else if (p.n.y < 0) d.y = -k;
if (p.n.z > 0) d.z = k; else if (p.n.z < 0) d.z = -k;
// Compute and return adjusted intersection point
q=a+(tnom * ab + d) / tdenom;
return 1;
}
Assuming the calculations for
tnom
and
tdenom
involve 64-bit operations, the input
values must not contain more than 30 bits of precision to avoid overflow. Additionally,
the computation of
q
must be performed using 64
×
32-bit precision multiplication
and 96/32-bit precision division.
The second problem is that after adjusting
Q
,
Q
may inadvertently end up behind
some other plane. A secondary intersection test is therefore required to determine if
segment
AQ
intersects any world geometry. If so, a new
Q
is computed, which in turn
may lie behind a third plane, and so on. Determining a
Q
that lies in front of
m
planes
— that is, which satisfies (
n
i
·
m
— is a problem that belongs to
the class of
integer linear programming problems
(see Section 9.4). These problems are
notoriously difificult to solve. Thus, rather than attempting to solve for
Q
a pragmatic
solution is simply to iterate, intersecting against one plane at a time and aborting if
no good intersection point is found within
n
iterations (at which point
A
is returned
as the intersection point).
As an example of computing the intersection point of a segment
AB
against
a world consisting of polygons
P
1
and
P
2
, consider the situation of Figure 11.12.
Initially,
AB
is found straddling the supporting plane of both
P
1
and
P
2
. Because
AB
passes through the interior of
P
1
only (and not
P
2
),
AB
is intersected against
P
1
. The unadjusted intersection point
Q
1
lies behind the plane of
P
1
, but through
adjustment (per the previous) the resulting intersection point
Q
2
lies in front of
P
1
.
Segment
AQ
2
must now be tested against the world. It is found intersecting
P
2
, result-
ing in the unadjusted intersection point
Q
3
, which adjusted becomes
Q
4
. Segment
AQ
4
is not found intersecting anything, and thus
Q
4
is returned as the intersection
point.
Overall, this integer approach is more complicated than a floating-point approach
using tolerances, explaining the more widespread use of floating-point in collision
detection applications.
Q
)
≥
d
i
,1
≤
i
≤
