Page 160 - Geometric Modeling and Algebraic Geometry

162 S. Chau et al.
In this paper we address the computation of the intersection curve of two sur-
face patches of bidegree (2,2), i.e., biquadratic tensor–product patches. Our aim is to
compute the intersection by using – as far as possible – symbolic techniques, in order
to avoid problems with numerical robustness.
We chose the tensor–product representation, since it is more common in CAD en-
vironment. Approximations of general tensor–product surfaces by biquadratic ones
can easily be generated by combining degree reduction techniques with subdivision.
The techniques presented in this paper can immediately be extended to the case of tri-
angular patches. Indeed, tringular patches can be seen as degenerate tensor–product
patches, where one edge collapses into a single point.
The remainder of the paper is organized as follows. After some preliminaries,
Sections 9.3 to 9.5 present three different techniques for computing the intersection
curves, which are based on resultants,on approximate implicitization (which was one
of the main research topics in the GAIA II project), and on intersections of parameter
lines, respectively. Section 9.6 discusses the computation of self–intersections. We
apply the three techniques to three representative examples and report the results in
Section 9.7. Finally, we conclude this paper.

9.2 Intersection and self–intersection curves

We consider the intersection curves of two biquadratic B´ ezier surfaces x(u, v) and
y(r, s), both with parameter domains [0, 1] . They are assumed to be given by their
2
parametric representations with rational coefficients (control points). More precisely,
these representations have the form
2 2

x(u, v)= c i,j B i (u)B j (v) (9.1)
i=0 j=0
with certain rational control points c i,j ∈ Q and the quadratic Bernstein polynomi-
3

i
als B j (t)= 2 t (1 − t) 2−i (and similarly for the second patch y(r, s)).
i
The intersection curve is defined by the system of three non–linear equations
x(u, v)= y(r, s) (9.2)
which defines the intersection as a curve (in the generic case) in [0, 1] . Similarly,
4
self intersections of one of the patches are characterized by
v
x(u, v)= x(¯u, ¯). (9.3)
∗
∗
In this case, the set of solutions contains the 2–plane u = u , v = v as a trivial
component.
While these equations could be solved by using numerical methods, we plan to
explore how far it is possible to compute the intersections by using symbolic compu-
tations, in order to avoid rounding errors and robustness problems.
The “generic” algorithm for computing the (self–) intersection curve(s), consists
of three steps: