Graphics Reference
In-Depth Information
where
AE
=+=+
DC
BA
DA
BC
and 0 £ r, s £ 1. The two quadratic equations in two unknowns r and s are easily solved
and one simply has to check if r and s lie in [0,1]. The solutions become even easier
if the quadrilateral is a trapezoid with two parallel sides.
10.2.2.6
Problem.
To find the intersection, if any, of the ray
X
and an oriented
faceted surface.
Solution.
This problem reduces to checking for an intersection of the ray with each
of the facets of the surface using the solution to Problem 10.2.2.4. In fact, we only
have to look at front-facing (front) facets, that is, facets whose normals (induced from
the orientation) have a nonpositive dot product with
v
.
10.2.2.7 Problem.
To find the intersection, if any, of the ray
X
and a generalized
bounding box
B
= B(
X
,
n
1
,
n
2
,...,
n
k
) (as defined in Section 6.2).
Solution.
First of all, finding the intersection of the line
L
with a slab is easy. One
simply substitutes the equation for the line into the equation of the far and near planes
for the slab. This will produce an interval [a
i
,b
i
] of parameters t so that
p
+ t
v
lies in
the ith slab. Let
I
be the intersection of these intervals. Equivalently, if
{
}
a
=
max
t
pv
+
t
lies on one of the near planes
and
{
}
b
=
min
t
pv
+
t
lies on one of the far planes
,
then
I
= [a,b]. Finally, if
I
π f and a ≥ 0, then
p
+ a
v
is the nearest intersection of
X
with
B
.
10.2.3
Ray Tracing CSG Objects
Ray tracing CSG objects is much simpler than constructing them. The basic idea,
described in [Roth82], only involves computing ray intersections with the primitives
used in the CSG tree that defines the object and then combining the resulting one-
dimensional segments with the set operations from that CSG tree.
Let T be a CSG tree that defines an object
X
. Let
r
be a ray with starting point
p
0
and unit direction vector
v
. Let LT and RT be the left and right subtree of the root of
T and assume that they correspond to objects
A
and
B
, respectively. The ray
r
will
intersect
A
and
B
in a collection of segments S
A
and S
B
.
Given the operation
op
at the root of T, the ray
r
will intersect
X
in the segments
S
A
op
S
B
. See Figure 10.6. This leads to Algorithm 10.2.3.1. In the algorithm we have
made use of the fact that if the ray does not intersect the object corresponding to the
