Graphics Reference
In-Depth Information
available), in practice the extra memory accesses incurred are likely to make it slower
than the scalar triple product solution. In addition, the higher memory overhead of the
Plücker coordinate approach is unappealing. Finally, note that the triangle face normal
n
=
(
B
−
A
)
×
(
C
−
A
) can be recovered from the three stored cross products as
n
A
).
This type of test can be extended into a segment test by explicitly computing the
intersection
t
value of
L
(
t
)
=−
(
C
×
B
)
−
(
A
×
C
)
−
(
B
×
P
) with the plane of
ABC
once the line
PQ
has been found intersecting
ABC
, discarding an intersection unless 0
=
P
+
t
(
Q
−
1.
An alternative approach for intersecting a segment against a triangle is given in
Section 5.3.6.
Determining directly in 3D whether a line or a segment intersects with the interior
of a triangle by computing the sidedness of the line against the triangle edges is
overall the most robust way of performing a triangle intersection test. Section 11.3.3
discusses the reasons for this inherent robustness.
The approach of using triple scalar products to determine if the intersection takes
place outside an edge can also be applied to arbitrary convex polygons, but for effi-
ciency it is better to test the point of intersection between the line and the plane
against the polygon interior. The triple scalar method does, however, extend nicely
to intersection against quadrilaterals, as shown in the following section.
≤
t
≤
5.3.5
Intersecting Line Against Quadrilateral
The triple scalar method described in the previous section can be used almost unmod-
ified for computing the intersection point
R
of a line with a quadrilateral
ABCD
.
Assume
ABCD
is convex and given counterclockwise. A point inside
ABCD
must
then be either inside the triangle
ABC
or inside the triangle
DAC
.
Because the edge
CA
is shared between both triangles, if this edge is tested first
it can be used to effectively discriminate which triangle
R
must
not
lie inside. For
example, if
R
lies to the left of
CA
,
R
cannot lie inside
DAC
, and thus only
ABC
has
to be tested, with only two additional edges to test against. If instead
R
lies to the
right of
CA
, only
DAC
must be tested, in that
R
cannot lie inside
ABC
. Again, only
two additional edges must be tested. The case of
R
lying on
CA
can be arbitrarily
assigned to either triangle. Whether
R
lies to the left or to the right of
CA
, in both
cases only three edges are tested in all. In terms of floating-point operations, the cost
of intersecting a line against a quadrilateral is therefore the same as that of intersecting
against a triangle!
For this intersection test, it is not possible to return the barycentric coordinates
of the intersection point directly. Additionally, to which one of the two triangles
the coordinates relate would have to be specified or, alternatively, the coordinates
would always have to be given with respect to, say,
ABC
, even if the intersection
point lies inside
DAC
. In the following sample implementation, the intersection
point is computed inside the function and returned instead of the point's barycentric
coordinates.
