Graphics Reference
In-Depth Information
As an optimization, the division by
e
can be deferred until
t
is known to be in the
range [0, 1], making the code at the end of the large
else
statement read:
...
float tnom = b*s + f;
if (tnom < 0.0f) {
t = 0.0f;
s = Clamp(-c / a, 0.0f, 1.0f);
} else if (tnom > e) {
t = 1.0f;
s = Clamp((b - c) / a, 0.0f, 1.0f);
} else {
t=tnom/e;
}
This deferral saves one, often expensive, division operation in the general case.
5.1.9.1 2D Segment Intersection
Testing whether two 2D segments
AB
and
CD
intersect can be done by first computing
the intersection point of their extended lines and then verifying that the intersection
point lies within the bounding box of each segment. Refer to Figures 5.10a and b for
examples. The case of the lines being parallel has to be handled separately.
The intersection between the extended lines can be computed by writing the first
line in explicit form,
L
1
(
t
)
=
A
+
t
(
B
−
A
), and the second line in implicit form,
C
)
⊥
is a perpendicular to
CD
. Substituting the first
line equation for the unknown point in the second equation and solving for
t
then
gives:
n
·
(
X
−
C
)
=
0, where
n
=
(
D
−
n
·
(
A
+
t
(
B
−
A
)
−
C
)
=
0
⇔
(substituting A
+
t
(
B
−
A
)
for X)
n
·
(
A
−
C
)
+
t
(
n
·
(
B
−
A
))
=
0
⇔
(expanding the dot product; gathering similar terms)
t
(
n
·
(
B
−
A
))
=−
n
·
(
A
−
C
)
⇔
(isolating t term on LHS)
t
(
n
·
(
B
−
A
))
=
n
·
(
C
−
A
)
⇔
(removing negation on RHS by inverting vector)
t
=
n
·
(
C
−
A
)/
n
·
(
B
−
A
)
(dividing both sides by
n
·
(
B
−
A
))
L
1
(
t
) can now be obtained by substituting
t
into
the explicit equation. An alternative to testing if
P
lies within the bounding box of
AB
is to verify that 0
The actual intersection point
P
=
1.
An alternative overlap test for 2D segments can be based on the insight that the
segments overlap only if the endpoints of either segment are located on different sides
≤
t
≤
