Graphics Reference
In-Depth Information
else if
n2(X) meets n2(Y) is a single number
then
begin
itp := 2; q := si;
Break;
end
end
;
return
(itp);
end
;
integer function
LinearProjectionType (
point set
X, Y;
point
p;
vector
n1, n2)
{ Inputs:
X = (p1,p2,...,ps) , Y = (q1,q2,...,qt) Õ line L = P(p,n1) « P(p,n2)
Output:
function returns an integer:
0 - convex hulls of X and Y intersect
1 - convex hulls of X and Y are disjoint
}
begin
vector
v;
real
a, b, c, d;
v := a direction vector for line L;
a := min( v(X) );
b := max( v(X) );
c := min( v(Y) ); d := max( v(Y) );
if
[a,b] « [c,d] = f
then return
(0)
else
return
(1);
end
;
Algorithm 13.2.1.
Continued
13.3
Curve Intersections
13.3.1
Ray-Curve Intersection
We assume that we are dealing with planar curves. Intersecting a ray with a polygo-
nal curve reduces to intersecting a ray with a segment. This is a problem that the
reader was asked to solve in Exercise 6.5.2. That leaves the interesting case of smooth
curves.
A Newton-Raphson Method.
Suppose that one wants to find the intersection of a
ray
X
from a point
p
in a direction
v
with a smooth curve parameterized by a func-
tion p(u). Let
L
be the
line
through
p
with unit direction vector
v
. One can use a rigid
motion to transform this situation into one where
p
is the origin and
v
is
e
2
, so that
L
is the y-axis. To simplify our discussion, assume that this has been done. Note that
there is typically no real cost associated to this assumption since modeling systems
usually define objects relative to associated coordinate systems. This means that to
