Page 213 - Geometric Modeling and Algebraic Geometry

216 M. Shalaby and B. J¨uttler
surfaces. A surface of revolution is created by rotating a 2D profile curve about an
axis in space. Rotation is one of the standard geometric operations defined in any
CAD/CAM interface.
This paper presents techniques for approximate implicitization of space curves
and of surfaces of revolution, which are based on the (approximate) implicitization of
planar curves. The proposed techniques are fully general in the sense that they can be
combined with any (exact or approximate) implicitization method for planar curves.
For creating the examples shown in this paper, we used a technique for simultaneous
approximation of points and associated normal vectors [10, 11, 16].
This paper is organized as follows. First we summarize the approximate implici-
tization method for planar curves. Section 12.3 presents techniques for approximate
implicitization of space curves, first as the intersection of two general cylinders, and
later as the intersection of two general surfaces which intersect approximately or-
thogonal. Representing the space curve by two ‘orthogonal’ surfaces provides a more
robust definition for the curve. Finally, in Section 12.4, two methods for approx-
imate implicitization of surfaces of revolution are presented. It is shown that – in
many cases – only approximate implicitization is capable of producing an implicit
representation that is free of unwanted branches and singularities.

12.2 Simultaneous approximation of points and normals

For the sake completeness, we give a short description of the approximate implic-
itization method presented in [10] (see also [11] for the case of surfaces). This
method is characterized by the simultaneous approximation of sampled point data
p i =(x i ,y i ), i ∈I = {1,...,N}, and estimated unit normals n i at these points.
The method consists of three main steps:
• Step 1 – Preprocessing: If no other information is available (e.g., from a given
parametric or procedural description of the curve), then each unit normal vector
n i is estimated from the nearest neighbors of the point p i . A consistent orien-
tation of the normals is achieved by a region–growing–type process. If the data
have been sampled from a curve with singularities, then it may be necessary to
organize the data into several segments, see [16] for details.
• Step2–Fitting: We generate an approximate implicit representation of the form

f(x)= c j ϕ j (x) (12.1)
j∈J
with certain coefficients c j ∈ R, finite index set J and suitable basis functions
ϕ j . For instance, one may choose tensor–product B-splines with respect to suit-
able knot sequences, or Bernstein polynomials with respect to a triangle contain-
ing the data.
The coefficients of f are obtained as the minimum of

f(p i ) + w 1 ||∇f(p i ) − n i || + w 2 T, (12.2)
2
2
i∈I