Page 167 - Geometric Modeling and Algebraic Geometry

9 Intersecting Biquadratic Patches 169
2. Intersect the plane with the second patch y(r, s) and compute the intersection I.
3. Restrict the intersection curve(s) I to the region of interest.
4. Intersect the cylinder with the restricted intersection curve(s).
The four steps of the algorithm will now be explained in some more detail.

Defining the plane, the cylinder and the two bounding planes.

The parameter line and its three control points are coplanar. For computing the nor-
mal vector n of the plane, we have to evaluate the cross product of two difference
vectors of the control points. The plane is given by the zero set of a linear polynomial
π(u 0 )(x, y, z)= e 0 (u 0 )+ n 1 (u 0 ) x + n 2 (u 0 ) y + n 3 (u 0 ) z. (9.12)

By extruding the parameter line in the direction of the normal vector of the plane,
we obtain the parametric form of the quadratic cylinder, which intersects the plane
orthogonally,
w(u 0 )(p, q)= x(u 0 ,p)+ q · n. (9.13)
The implicitation of the cylinder is slightly more complicated. There exist two pos-
sibilities: we can either use Sylvester resultants or the method of comparing coeffi-
cients. In both cases we will get an equation of the form

ζ(u 0 )(x, y, z):= a 0 (u 0 )+ a 1 (u 0 ) x + a 2 (u 0 ) y + a 3 (u 0 ) z
+ a 4 (u 0 ) xy + a 5 (u 0 ) xz + a 6 (u 0 ) yz
+ a 7 (u 0 ) x + a 8 (u 0 ) y + a 9 (u 0 ) z 2 =0. (9.14)
2
2
Now we have both the plane and the cylinder in their implicit representation. Note
that this is a semi-implicit representation in the sense of [6].
If the parameter line degenerates into a straight line, then we choose two planes
through it which intersect orthogonally. Note that we use exact rational arithmetic,
in order to avoid any robustness problems.
Finally, we create the two planes π 1 (x, y, z) and π 2 (x, y, z) which bound the
parameter line. For instance, one may choose the two normal planes of the parameter
line at its boundary points; this choice is always possible, provided that the curve
segment is not too long (which can be enforced by using subdivision). Alternatively
one may use the planes spanned by the boundary curves, but these planes may have
an additional intersection with the parameter line in the region of interest.

Intersection of the plane and the second patch y(r, s).
Substituting the second B´ ezier surface y(r, s) into the equation (9.12) of the plane
leads to a biquadratic equation in r and s. We can treat it as a quadratic polynomial
in r with coefficients depending on s.

π(y(r, s)) = a(s) r + b(s) r + c(s)=0. (9.15)
2