Page 168 - Geometric Modeling and Algebraic Geometry

170 S. Chau et al.
For each value of s, we obtain two solutions r 1 (s) and r 2 (s) of the form

b(s) & b(s) 2 c(s)
r 1,2 (s)= − ± d(s) with d(s)= − . (9.16)
2 a(s) 4 a(s) 2 a(s)
These solutions parameterize the two branches of the intersection curve I in the rs–
parameter domain of the second patch. By solving several quadratic equations we
determine the intervals S i,j ⊂ [0, 1], where d(s) ≥ 0 and 0 ≤ r i (s) ≤ 1 holds; this
leads to a (list of) feasible domain(s) (i.e., intervals) for each branch of the intersec-
tion curve.
By composing (9.16) with y we obtain the two branches k 1 (s) and k 2 (s) of the
intersection curve I,
&
1 d(s)
k 1,2 (s)= y(r 1,2 (s),s)= h(s) ± l(s)+ d(s)m(s) (9.17)
a(s) 2 a(s)
where the components of h(s), l(s) and m(s) are polynomials of degree 6, 4, and 2,
respectively.

Restriction to the region of interest.

Since the region of interest is located between the planes π 1 (x, y, z) and π 2 (x, y, z),
the two inequalities

π 1 (x, y, z) ≥ 0 and π 2 (x, y, z) ≤ 0 (9.18)

have to be satisfied. By intersecting each bounding plane with the second B´ ezier
surface y(r, s) in a similar way as described for π(u 0 )(x, y, z), we obtain

(s):= π 1 (y(r(s),s)) ≥ 0 and k π 2 (s):= π 2 (y(r(s),s)) ≤ 0 (9.19)
k π 1
This leads to additional constraints for the feasible values of the parameter s.For
each branch of the intersection curve we create the (list of) feasible domain(s) and
store it. The bounds of the intervals can be computed by solving three systems of two
biquadratic equations or – equivalently – by solving a system of three polynomials
of degree 8, which are obtained after eliminating the parameter r. Here, we represent
the polynomials in Bernstein–B´ ezier form and use a B´ ezier–clipping–type technique
see [14, 25, 26, 28], applied to floating point numbers.
Example 2. For a parameter line u = u 0 of two biquadratic B´ ezier surface patches
x(u, v) and y(r, s), Fig. 9.4, right, shows the rs–parameter domain of the second
patch. Only the first branch r 1 (s) of the intersection curve is present. The bounds 0 ≤
r ≤ 1 do not impose additional bounds on s in this case. However, the intersection
with the bounding planes π 1 and π 2 produces two additional curves, which have to
be intersected with the curve s = r 1 (s), leading to two bounds s 0 and s 1 of the
feasible domain.