Graphics Reference
In-Depth Information
q
2
) and normal
n
3
=
n
1
¥
n
2
. Then
p
i+1
is the intersection of the three planes
T
1
,
T
2
,
and
T
3
. The special case where the planes
T
1
and
T
2
are parallel is easily handled sep-
arately. Convergence, although a problem theoretically, was not a problem in practice
given that points were only needed within the tolerance e
SPT
.
The method for relaxing points that we just described is what is used for deter-
mining the intersection in the interior of the surface patches, which is most of the
time, but not for relaxing points onto the boundary of the patches. In that case one
uses a Newton-Raphson approach to solve
(
)
-
()
=
0
puv
,
qst
,
along with a parameter constraint determined by the boundary to which one is
relaxing, for example, u = 0. We have a system of three equations in three unknowns.
Parallel tangent planes are again a problem.
The Barnhill-Kersey Tracing Phase.
This phase is started for each intersection
point obtained in the hunting phase. For each start point, one generates a sequence
of points that lie on the intersection. As one moves from one point
p
to the next
one needs a step direction and step size. The tangent of the intersection curve at the
current point is used as the step direction. Like in Timmer's algorithm, this is com-
puted from the cross-product of the normal vectors to the surfaces at
p
. One can save
some multiplications by using Theorem 1.10.4(2) in [AgoM05] and use the direction
(
)
¥= ∑
(
)
(
)
pp
¥
n
p
n
p p
-∑
n
p
u
v
2
u
2
v
v
2
u
instead. Unfortunately, these formulas give the zero vector if the surfaces are tangent.
In that case one can take the difference of previous intersection points. If there are
no previous points and we are at the first intersection point, say
p
= p(u
0
,v
0
) = q(s
0
,t
0
),
one samples points on the circles around (u
0
,v
0
) and (s
0
,t
0
) in the domains of the para-
meterizations to find another point on the intersection. The new step direction is then
taken to be the difference between this point and
p
.
Once one has the step direction one has to decide on a step size L. Like in Timmer's
algorithm one wants to use a formula of the form L = rDq, where r is the radius of
curvature and Dq is some predefined
angle tolerance
. However, the parameteriza-
tions were only assumed to be C
1
here and so the second derivatives are not directly
available to compute this radius. Therefore, an approximation was used. Assume that
we are a point
p
on the intersection. Two points a small distance e from
p
on the
tangent line to the intersection curve at
p
are relaxed to points
x
and
y
on the inter-
section. The three points
p
,
x
, and
y
determine a circle and we let r be its radius
because we can consider this circle to be an approximation to the osculating circle.
Formula 6.8.1 implies that
aba b
ab
-
r =
,
2
¥
where
a
=
x
-
p
and
b
=
y
-
p
. If the three points were collinear or L turned out to
be larger than some predefined
curve refinement tolerance
e
CRT
, then L was set to
e
CRT
.
