i
i
i
i
i
i
i
i
750 16. Intersection Test Methods
RayTriIntersect(o, d, p
0
, p
1
, p
2
)
returns ({REJECT, INTERSECT}, u, v, t);
1: e
1
= p
1
− p
0
2: e
2
= p
2
− p
0
3: q = d × e
2
4: a = e
1
· q
5: if(a>− and a<) return (REJECT, 0, 0, 0);
6: f =1/a
7: s = o − p
0
8: u = f (s ·q)
9: if(u<0.0) return (REJECT, 0, 0, 0);
10 : r = s × e
1
11 : v = f(d · r)
12 : if(v<0.0 or u + v>1.0) return (REJECT, 0, 0, 0);
13 : t = f (e
2
· r)
14 : return (INTERSECT,u,v,t);
A few lines may require some explanation. Line 4 computes a,whichisthe
determinant of the matrix M. This is followed by a test that avoids deter-
minants close to zero. With a properly adjusted value of , this algorithm
is extremely robust.
8
In line 9, the value of u is compared to an edge of
the triangle (u =0).
C-code for this algorithm, including both culling and nonculling ver-
sions, is available on the web [890]. The C-code has two branches: one
that efficiently culls all backfacing triangles, and one that performs inter-
section tests on two-sided triangles. All computations are delayed until
they are required. For example, the value of v is not computed until the
value of u is found to be within the allowable range (this can be seen in
the pseudocode as well).
The one-sided intersection routine eliminates all triangles where the
value of the determinant is negative. This procedure allows the routine’s
only division operation to be delayed until an intersection has been con-
firmed.
16.9 Ray/Polygon Intersection
Even though triangles are the most common rendering primitive, a rou-
tine that computes the intersection between a ray and a polygon is use-
ful to have. A polygon of n vertices is defined by an ordered vertex list
{v
0
, v
1
,...,v
n−1
}, where vertex v
i
forms an edge with v
i+1
for 0 ≤ i<
8
For floating point precision and “normal” conditions, =10
−5
works fine.
i
i
i
i
i
i
i
i
16.9. Ray/Polygon Intersection 751
n −1 and the polygon is closed by the edge from v
n−1
to v
0
. The plane of
the polygon
9
is denoted π
p
: n
p
· x + d
p
=0.
We first compute the intersection between the ray (Equation 16.1) and
π
p
, which is easily done by replacing x by the ray. The solution is presented
below:
n
p
·(o + td)+d
p
=0
⇐⇒
t =
−d
p
− n
p
· o
n
p
·d
.
(16.26)
If the denominator |n
p
·d| <,where is a very small number,
10
then
the ray is considered parallel to the polygon plane and no intersection oc-
curs.
11
Otherwise, the intersection point, p, of the ray and the polygon
plane is computed: p = o + td,wherethet-value is that from Equa-
tion 16.26. Thereafter, the problem of deciding whether p is inside the
polygon is reduced from three to two dimensions. This is done by project-
ing all vertices and p to one of the xy-, xz-, or yz-planes where the area of
the projected polygon is maximized. In other words, the coordinate com-
ponent that corresponds to max(|n
p,x
|, |n
p,y
|, |n
p,z
|) can be skipped and
the others kept as two-dimensional coordinates. For example, given a nor-
mal (0.6, −0.692, 0.4), the y component has the largest magnitude, so all
y coordinates are ignored. Note that this component information could
be precomputed once and stored within the polygon for efficiency. The
topology of the polygon and the intersection point is conserved during this
projection (assuming the polygon is indeed flat; see Section 12.2 for more
on this topic). The projection procedure is shown in Figure 16.11.
The question left is whether the two-dimensional ray/plane intersection
point p is contained in the two-dimensional polygon. Here, we will review
just one of the more useful algorithms—the “crossings” test. Haines [482]
and Schneider and Eberly [1131] provide extensive surveys of two-
dimensional, point-in-polygon strategies. A more formal treatment can
be found in the computational geometry literature [82, 975, 1033]. Lagae
and Dutr´e [711] provide a fast method for ray/quadrilateral intersection
basedontheM¨oller and Trumbore ray/triangle test. Walker [1315] pro-
vides a method for rapid testing of polygons with more than 10 vertices.
Nishita et al. [936] discuss point inclusion testing for shapes with curved
edges.
9
This plane can be computed from the vertices on the fly or stored with the polygon,
whichever is most convenient. It is sometimes called the supporting plane of the polygon.
10
An epsilon of 10
−20
or smaller can work, as the goal is to avoid overflowing when
dividing.
11
We ignore the case where the ray is in the polygon’s plane.
i
i
i
i
i
i
i
i
752 16. Intersection Test Methods
Figure 16.11. Orthographic projection of polygon vertices and intersection point p onto
the xy-plane, where the area of the projected polygon is maximized. This is an example
of using dimension reduction to obtain simpler calculations.
16.9.1 The Crossings Test
The crossings test is based on the Jordan Curve Theorem,aresultfrom
topology. From it, a point is inside a polygon if a ray from this point in an
arbitrary direction in the plane crosses an odd number of polygon edges.
The Jordan Curve Theorem actually limits itself to non-self-intersecting
loops. For self-intersecting loops, this ray test causes some areas visibly
Figure 16.12. A general polygon that is self-intersecting and concave, yet all of its
enclosed areas are not considered inside (only yellow areas are inside). Vertices are
marked with large, black dots. Three points being tested are shown, along with their
test rays. According to the Jordan Curve Theorem, a point is inside if the number
of crossings with the edges of the polygon is odd. Therefore, the uppermost and the
bottommost points are inside (one and three crossings, respectively). The two middle
points each cross two edges and are thus, because of self-intersection, considered outside
the polygon.
i
i
i
i
i
i
i
i
16.9. Ray/Polygon Intersection 753
inside the polygon to be considered outside. This is shown in Figure 16.12.
This test is also known as the parity or the even-odd test.
The crossings algorithm is the fastest test that does not use preprocess-
ing. It works by shooting a ray from the projection of the point p along the
positive x-axis. Then the number of crossings between the polygon edges
and this ray is computed. As the Jordan Curve Theorem proves, an odd
number of crossings indicates that the point is inside the polygon.
The test point p can also be thought of as being at the origin, and the
(translated) edges may be tested against the positive x-axis instead. This
option is depicted in Figure 16.13. If the y-coordinates of a polygon edge
have the same sign, then that edge cannot cross the x-axis. Otherwise, it
can, and then the x-coordinates are checked. If both are positive, then the
number of crossings is incremented. If they differ in sign, the x-coordinate
of the intersection between the edge and the x-axis must be computed, and
if it is positive, the number of crossings is again incremented.
These enclosed areas could be included as well. This variant test finds
the winding number, the number of times the polygon loop goes around
the test point. See Haines [482] for treatment.
Problems might occur when the test ray intersects a vertex, since two
crossings might be detected. These problems are solved by setting the ver-
p
Figure 16.13. The polygon has been translated by −p (p is the point to be tested for
containment in the polygon), and so the number of crossings with the positive x-axis
determines whether p is inside the polygon. Edges e
0
, e
2
, e
3
,ande
4
do not cross the
x-axis. The intersection between edge e
1
and the x-axis must be computed, but will not
yield a crossing, since the intersection has a negative x-component. Edges e
7
and e
8
will each increase the number of crossings, since the vertices of these edges have positive
x-components and one negative and one positive y-component. Finally, the edges e
5
and
e
6
share a vertex where y =0andx>0, and they will together increase the number of
crossings by one. By considering vertices on the x-axis as above the ray, e
5
is classified
as crossing the ray, e
6
as above the ray.
i
i
i
i
i
i
i
i
754 16. Intersection Test Methods
tex infinitesimally above the ray, which, in practice, is done by interpreting
the vertices with y ≥ 0 as lying above the x-axis (the ray). The code
becomes simpler and speedier, and no vertices will be intersected [480].
The pseudocode for an efficient form of the crossings test follows. It
was inspired by the work of Joseph Samosky [1101] and Mark Haigh-
Hutchinson, and the code is available on the web [482]. A two-dimensional
test point t and polygon P with vertices v
0
through v
n−1
are compared.
bool PointInPolygon(t,P)
returns ({TRUE, FALSE});
1: bool inside = FALSE
2: e
0
= v
n−1
3: bool y
0
=(e
0y
≥ t
y
)
4: for i =0to n − 1
5: e
1
= v
i
6: bool y
1
=(e
1y
≥ t
y
)
7: if(y
0
= y
1
)
8: if(((e
1y
− t
y
)(e
0x
− e
1x
) ≥ (e
1x
− t
x
)(e
0y
− e
1y
)) == y
1
)
9: inside=¬inside
10 : y
0
= y
1
11 : e
0
= e
1
12 : return inside;
Line 4 checks whether the y-value of the last vertex in the polygon is
greater than or equal to the y-value of the test point t,andstoresthe
result in the boolean y
0
. In other words, it tests whether the first endpoint
of the first edge we will test is above or below the x-axis. Line 7 tests
whether the endpoints e
0
and e
1
are on different sides of the x-axis formed
by the test point. If so, then line 8 tests whether the x-intercept is positive.
Actually, it is a bit trickier than that: To avoid the divide normally needed
for computing the intercept, we perform a sign-canceling operation here.
By inverting inside, line 9 records that a crossing took place. Lines 10 to
12 move on to the next vertex.
In the pseudocode we do not perform a test after line 7 to see whether
both endpoints have larger or smaller x-coordinates compared to the test
point. Although we presented the algorithm with using a quick accept
or reject of these types of edges, code based on the pseudocode presented
often runs faster without this test. A major factor is the number of vertices
in the polygons tested. In testing, checking the signs of the x-coordinate
differences begins to pay off when testing polygons with more than 10 to
30 vertices, as there are then enough edges that benefit from early rejection
or acceptance and fewer that require the full test on line 8. That said, the
overall increase in speed seen for 1000 vertex polygons was at most 16%.
..................Content has been hidden....................
You can't read the all page of ebook, please click here login for view all page.