Graphics Reference
In-Depth Information
if (m > n) return GREATER_THAN;
}
int olda = a, oldb = b;
a=d%c;b=c;c=oldb % olda; d = olda;
}
if (a == 0) return c == 0 ? EQUAL : LESS_THAN;
return GREATER_THAN;
}
A similar method is presented in [Avnaim95].
After eliminating all divisions present in tests, what remains is dealing with divi-
sions in constructions, such as computing the intersection point between the segment
S
and the plane
P
. Handling these divisions is where the real problem occurs. Because
the intersection point is not exactly representable, in general, it must be rounded or
truncated to integer coordinates. The resulting point is unlikely to lie on the plane.
Instead, it will typically lie either in front of or behind the plane. If
S
represents
the movement of a particle from position
A
to position
B
, rounding the intersection
point to lie behind the plane effectively places the particle outside the world, likely
leading to errant behavior as the particle continues its movement from the rounded
position.
Ensuring that a construction satisfies the criteria imposed by the collision detection
system requires careful consideration and coding. An example is given in the next
section, for the case of segment-plane intersection.
11.5.3
Segment Intersection Using Integer Arithmetic
Yet again the problem of intersecting the line segment
S
(
t
)
=
A
+
t
(
B
−
A
), 0
≤
t
≤
1,
against the plane
P
given by (
n
d
is revisited. It is assumed
S
represents the
linear motion of a point object
O
from position
A
to position
B
over a time interval
given by
t
.
O
intersects the plane at time
t
as
·
X
)
=
A
)
(
n
t
=
(
d
−
n
·
·
(
B
−
A
)),
which substituted in
S
(
t
) gives the intersection point
Q
as
]
n
Q
=
A
+[
(
d
−
n
·
A
)(
B
−
A
)
·
(
B
−
A
).
Assume the segment straddles the plane, with
A
in front of the plane and
B
behind
it. Because the coordinate components of
Q
are integers,
Q
is highly unlikely to lie
