13.472J/1.128J/2.158J/16.940J
COMPUTATIONAL GEOMETRY
Lecture 13
N. M. Patrikalakis
Massachusetts Institute of Technology
Cambridge, MA 02139-4307, USA
Copyright c 2003 Massachusetts Institute of Technology
Contents
13 O sets of Parametric Curves and Surfaces 2
13.1 Motivation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
13.2 Parametric o set curves . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
13.2.1 Di erential geometry of parametric o set curves . . . . . . . . . . . . . 5
13.2.2 Singularities of parametric o set curves . . . . . . . . . . . . . . . . . . 6
13.2.3 Approximations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
13.3 Parametric o set surfaces . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
13.3.1 Di erential geometry of parametric o set surfaces . . . . . . . . . . . . 10
13.3.2 Singularities of parametric o set surfaces . . . . . . . . . . . . . . . . . 11
13.3.3 Tracing algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
13.3.4 Self-intersections of o sets of explicit quadratic surfaces . . . . . . . . . 14
13.3.5 Approximations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
Bibliography 22
Reading in the Textbook
Chapter 11, pp. 293 - 353
1
Lecture 13
O sets of Parametric Curves and
Surfaces
13.1 Motivation
O sets are de ned as the locus of points at a signed distance d along the normal of a planar
curve or surface. A literature survey on o set curves and surfaces up to 1992 was carried out
by Pham [24], while the overview of the literature after 1992 and those which were not cited in
[24] is given by Maekawa [14]. O set curves and surfaces are widely used in various engineering
applications, such as
Tool path generation for pocket(2.5D), 3D and 5D NC machining [9, 1]. (See Figure 13.1).
Generator Surface
Tool Driving Plane
Center of Ball
Endmill
Ball Endmill Tool Path
Offset Surface
Figure 13.1: NC machining.
2
De nition of tolerance regions [4, 26, 21]. (See Figure 13.2).
Figure 13.2: De nition of tolerance regions.
Access space representations in robotics [12]. (See Figure 13.3)
a0a1a0a1a0a1a0a2a0
a0a1a0a1a0a1a0a2a0
a0a1a0a1a0a1a0a2a0
a0a1a0a1a0a1a0a2a0
a0a1a0a1a0a1a0a2a0
a0a1a0a1a0a1a0a2a0
a0a1a0a1a0a1a0a2a0
a0a2a0a1a0a1a0a1a0a2a0
a0a2a0a1a0a1a0a1a0a2a0
a0a2a0a1a0a1a0a1a0a2a0
a0a2a0a1a0a1a0a1a0a2a0
a0a2a0a1a0a1a0a1a0a2a0
a0a2a0a1a0a1a0a1a0a2a0a0a2a0a1a0a1a0a1a0a2a0
a0a2a0a1a0a1a0a1a0a2a0
a0a2a0a1a0a1a0a1a0a2a0
a0a2a0a1a0a1a0a1a0a2a0
Figure 13.3: Access space representations in robotics.
3
Curved plate (shell) representation in solid modeling [23]. (See Figure 13.4)
Figure 13.4: Plate representation.
Feature recognition through construction of skeletons or medial axes of geometric models
[22, 29]. (See Figure 13.5). The medial axis is made up of boundary o set intersections.
Figure 13.5: Medial Axis.
The concept of o set curves generalizes to
pipe surfaces when the progenitor is a general 3D curve [18].
geodesic o sets when the progenitor is curve on a surface [20] [25] [11].
4
13.2 Parametric o set curves
13.2.1 Di erential geometry of parametric o set curves
A planar parametric curve r(t) is given by
r(t) = [x(t);y(t)] ; t 2 [0;1] (13.1)
where x and y are di erentiable functions of a parameter t.
The unit normal vector of a plane curve, which is orthogonal to t, is given by
n = t ez = ( _y(t); _x(t))p_x2(t) + _y2(t) (13.2)
where ez = (0;0;1) is a unit vector perpendicular to the plane of the curve, see Figure
13.6.
For a plane curve, the Frenet formulae reduce to
dt
ds = n;
dn
ds = t (13.3)
where is the signed curvature of the curve given by
= (_r r) ezv3 = _x y _y x
( _x2 + _y2)32
(13.4)
where v = j_r(t)j is the parametric speed. The curvature of a curve at point P is positive
when the direction of n and ~PC are opposite where C is the center of the curvature of
the curve at point P, see Figure 13.6.
C
P
r(t)
n t
x
y
ez
Figure 13.6: De nitions of unit tangent and normal vectors.
5
A planar o set curve ^r(t) with signed o set distance d to the progenitor r(t) is de ned
by
^r(t) = r(t) + dn(t) (13.5)
where d > 0 corresponds to positive (\exterior") and d < 0 corresponds to negative
(\interior") o sets.
The unit tangent vector of the o set curve (see Figure 13.7 for illustration)
^t = _^r
j_^rj =
1 + d
j1 + djt (13.6)
The unit normal vector of the o set curve (see Figure 13.7 for illustration)
^n = ^t ez = 1 + dj1 + djn (13.7)
Curvature of the o set curve
^ = j1 + dj (13.8)
13.2.2 Singularities of parametric o set curves
There are two kinds of singularities on the o set curves, irregular points and self-intersections.
Irregular points
Isolated points: This point occurs when the progenitor curve with radius R is a circle and
the o set is d = R.
Cusps: This point occurs at a point t where the tangent vector vanishes.
(t) = 1d (13.9)
A cusp at t = tc can be further subdivided into [7]:
1. Ordinary cusps when _ (tc) 6= 0
2. Extraordinary points when _ (tc) = 0 and (tc) 6= 0.
Note that (1 + d)=j1 + dj in equations (13.6) and (13.7) changes abruptly from -1 to 1
when the parameter t passes through t = tc at an ordinary cusp, while at extraordinary
points (1 + d)=j1 + dj does not change its value, see Figure 13.7.
Equation (13.9) for r(t) = fx(t);y(t)g can be reduced to
d[ x(t) _y(t) _x(t) y(t)]
q
_x2(t) + _y2(t)
h
_x2(t) + _y2(t)
i
= 0 (13.10)
6
Figure 13.7: O sets to a parabola r = [t;t2] (thick solid line) with o sets d=-0.3, -0.5, -0.8,
adapted from [5]. At d = 0:3 the tangent and normal vectors of the o set have the same
sense that of the progenitor, while at d = 0:8 they ip directions.
By setting 2 = _x2 + _y2 and if r(t) is a rational polynomial curve, the computation of
cusps can be reduced to system of two nonlinear polynomial equations that can be solved
using the methods of Chapter 10.
Examples (see Figures 13.7 and 13.8)
Given a parabola r = (t;t2), the unit tangent and principal normal vectors are given by
t = drds = drdt dtds = (1;2t)p1 + 4t2 ; n = t ez = (2t; 1)p1 + 4t2
The curvature and its derivative are given by
(t) = (_r r) ezj_rj3 = 2
(1 + 4t2)32
; _ (t) = 24t(1 + 4t
2)12
(1 + 4t2)3
Since _ (0) = 0, (t) reaches an extremum at t = 0 and furthermore as (0) < 0, (0) is
a maximum with a curvature value (0) = 2. Therefore when d > 12 the o set is non-
degenerate, while when d = 12, t = 0 is an extraordinary point. Let us solve (t) = 1=d
for t which yields
t =
q
3p4d2 1
2 :
We can easily see that if d > 1=2, there is no real root. This means that there is no
singularity as long as radius of curvature is smaller than 2. If d = 1=2, there exists a
single root t = 0, while if d < 1=2 there exist two symmetric values t1, t2.
Self-intersections
7
Self-intersections of an o set curve (see also Figures 13.7 and 13.8) can be obtained by
seeking pairs of distinct parameter values s 6= t such that
r(s) + dn(s) = r(t) + dn(t): (13.11)
Substitution of equation (13.2) in (13.11) yields the system [17]
x(s) + _y(s)dp_x2(s) + _y2(s) = x(t) + _y(t)dp_x2(t) + _y2(t)
y(s) _x(s)dp_x2(s) + _y2(s) = y(t) _x(t)dp_x2(t) + _y2(t) (13.12)
If r(t) is a rational polynomial curve, this system can be converted to a nonlinear poly-
nomial system of four equations in four variables s, t, and where
2 = _x2(s) + _y2(s) (13.13)
2 = _x2(t) + _y2(t): (13.14)
Such a system can be solved using the IPP algorithm, see also [17]. However s = t
are trivial solutions, and we must exclude them from the system, otherwise a Bernstein
subdivision-based algorithm would attempt to solve for an in nite number of roots. In
this case we have addressed the problem by dividing out the common factor by some
algebraic manipulations [17].
Figure 13.8: Self-intersection of the o set curve of a parabola. Left: Interior o sets to the
parabola r(t) = [t;t2] with d = 0:8 and cutter path; Right: Trimmed interior o sets to the
parabola r(t) = [t;t2] with d = 0:8 and cutter path
8
13.2.3 Approximations
In general, an o set curve is functionally more complex than its progenitor curve because
of the square root involved in the expression of the unit normal vector. L u [13] for example
has shown that o set of a parabola is a rational curve and its singular point at in nity
was studied by Farouki and Sederberg [8]. However, this result has not been generalized
to higher order curves.
Farouki and Ne [6] have shown that the two-sided o sets of planar rational polynomial
curves are high-degree implicit algebraic curves fo(x;y) = 0 of potentially complex shape.
These equations can not typically be separated into two equations describing interior and
exterior o sets individually. The degree of this implicit o set curve is no = 4n 2 2m,
where n is the degree of polynomial generator curve r = [x(t);y(t)] and m is the degree
of (t) = GCD(x0(t);y0(t)). For example the degree of the two-sided o set curve of a
parabola r(t) = (t;t2) is 6 and of a general polynomial cubic curve is 10 with (t) a
constant.
If the progenitor surface is a NURBS curve, then its o set is usually not a NURBS curve,
except for straight lines and circles.
Because of the wide application of o set surfaces and the di culty in directly incorpo-
rating such entities in geometric modeling systems, due to their potential analytic and
algebraic complexity, a number of researchers have developed approximation algorithms
for these types of geometries in terms of piecewise polynomial or rational polynomial
functions [27, 10].
Summary of an Approximation Algorithm [27], see also Figure 13.9:
1. Input is a NURBS curve.
2. O set each leg of polygon by d.
3. Intersect consecutive legs of polygon to nd new vertices.
4. Check deviation of the approximate o set with the true o set using as weights (for
rational function) the weights of the progenitor curve.
5. If the deviation is larger than the given tolerance subdivide the curve into two and
go back to step 1. If the deviation is smaller than the given tolerance stop.
d
d
d
Approximated Offset Curve
Progenitor Curve
Figure 13.9: O set curve approximation.
9
13.3 Parametric o set surfaces
13.3.1 Di erential geometry of parametric o set surfaces
De nition
A parametric o set surface ^r(u;v) is a continuum of all points at a constant distance d
along normal to another parametric surface r(u;v) and de ned as
^r(u;v) = r(u;v) + dn(u;v) (13.15)
where d may be a positive or negative real number and n is the unit normal vector of
r(u;v).
Sign convention for normal curvature
The normal curvature is typically considered positive if its associated center of curvature
is opposite to the direction of the surface normal.
Relation between n and ^n [28]
If ^n(u;v) is the unit normal vector of ^r(u;v), then the relation between n and ^n is given
by
^S^n = (1 + d max)(1 + d min)Sn (13.16)
where ^S = j^ru ^rvj and S = jru rvj or expanding the right hand side of equation (13.16)
and using the de nitions of Gaussian curvature K and mean curvature H
K = max min; H = max + min2 (13.17)
equation (13.16) can be rewritten as follows:
^S^n = S(1 + 2Hd + Kd2)n (13.18)
If we take the norm of equation (13.16), we obtain
^S = Sj(1 + d max)(1 + d min)j (13.19)
and substituting ^S into equation (13.16) yields
^n = (1 + d max)(1 + d min)j(1 + d
max)(1 + d min)j
n (13.20)
From this relation n and ^n are collinear but may be directed in opposite directions, if
d max < 1 or d min < 1. This occurs when the o set is taken towards the concave
region of the progenitor.
O setting towards concave region of a surface is equivalent to taking the o set d > 0
where min < 0 and d < 0 where max > 0, provided the above sign convention is used.
10
Gaussian and Mean Curvatures
^K = K
1 + 2Hd + Kd2 (13.21)
^H = H + Kd
j1 + 2Hd + Kd2j (13.22)
Principal Curvatures
^ max = (1 + d min) maxj1 + d
maxjj1 + d minj
(13.23)
^ min = (1 + d max) minj1 + d
maxjj1 + d minj
(13.24)
Given an o set distance d, the critical curvature is de ned as crit = 1=d then three
categories arise [5]:
max > min > crit: The normal vector of the progenitor and its o set are directed in the
same direction. Also the sign of Gaussian and principal curvatures of the o set are the same
that of the progenitor.
max > crit > min: The normal vector of the progenitor and its o set are directed in the
opposite direction. Also the sign of Gaussian and maximum principal curvatures of the o set
are opposite to that of the progenitor, while the sign of the minimum principal curvature of
the o set is the same to that of the progenitor.
min < max < crit: The normal vector of the progenitor and its o set are directed in the
same direction, while the sign of both principal curvatures of the o set are opposite that of the
progenitor and thus the sign of Gaussian curvature of an o set remains the same as that of the
progenitor.
13.3.2 Singularities of parametric o set surfaces
Figure 13.10: O set surface (left), region bounded by self-intersection curve (center) and
trimmed o set surface (right) of elliptic paraboloid z = 12(1:75x2 + 2y2) with d = 0:6.
In NC machining, the cutter radius must not exceed the smallest concave principal
radius of curvature of the surface to avoid gouging [9].
11
x
y z
Figure 13.11: Self-intersection curves of elliptic paraboloid ( = 2, = 4) with d = 0:3. The
dot dashed line in the gure is a set of points of self-intersection curve in the xy-plane mapped
onto the progenitor surface. A pair of thin solid straight lines emanating from two distinct
points on the surface r(s;t), r(u;v) and intersecting along the parabola are the pairs of vectors
dn(s;t) and dn(u;v).
Critical O set Distance:
The largest magnitude of o set distance without degeneracy is called critical o set dis-
tance dcrit. When the o set is positive, in the absence of degeneracy due to global
properties, the maximum absolute value of the negative minimum principal curvature
on the surface determines dcrit = 1max(j minj). When the o set is negative, in the ab-
sence of degeneracy due to global properties, the minimum absolute value of the positive
maximum principal curvature on the surface determines dcrit = 1max( max). versa.
Ridges:
It is apparent from equation (13.20) that o set surfaces become singular at points called
ridges. They are de ned as a vector-valued mapping of two implicit curves in the uv-
parametric space to 3D space via the mapping (13.15), which satisfy max(u;v) = 1d or
min(u;v) = 1d [9].
Self-intersections:
Self-intersections of an o set surface are de ned by nding pairs of distinct parameter
values (s;t) 6= (u;v) such that
r(s;t) + dn(s;t) = r(u;v) + dn(u;v) (13.25)
see also Figures 13.10, 13.11.
For parametric surfaces r(u;v) = [x(u;v); y(u;v); z(u;v)]
x(s; t) + ys(s; t)zt(s; t) yt(s; t)zs(s; t)S(s; t) d = x(u; v) + yu(u; v)zv(u; v) yv(u; v)zu(u; v)S(u; v) d(13.26)
12
y(s; t) + xt(s; t)zs(s; t) xs(s; t)zt(s; t)S(s; t) d = y(u; v) + xv(u; v)zu(u; v) xu(u; v)zv(u; v)S(u; v) d(13.27)
z(s; t) + xs(s; t)yt(s; t) xt(s; t)ys(s; t)S(s; t) d = z(u; v) + xu(u; v)yv(u; v) xv(u; v)yu(u; v)S(u; v) d(13.28)
Since we can x one of the four variables (s, t, u, v), the system of equations (13.26) to
(13.28) yields three equations with three unknowns.
We can replace S(s;t) and S(u;v) by auxiliary variables and ! such that 2 = S2(s;t)
and !2 = S2(u;v).
Consequently the system involving polynomials and square root of polynomials has been
reduced to a nonlinear polynomial system consisting of ve equations with ve unknowns
as follows:
![x(s;t) x(u;v)] + d[!Nx(s;t) Nx(u;v)] = 0 (13.29)
![y(s;t) y(u;v)] + d[!Ny(s;t) Ny(u;v)] = 0 (13.30)
![z(s;t) z(u;v)] + d[!Nz(s;t) Nz(u;v)] = 0 (13.31)
2 N2x(s;t) N2y (s;t) N2z (s;t) = 0 (13.32)
!2 N2x(u;v) N2y (u;v) N2z (u;v) = 0 (13.33)
where
Nx(s;t) = ys(s;t)zt(s;t) yt(s;t)zs(s;t) (13.34)
Nx(u;v) = yu(u;v)zv(u;v) yv(u;v)zu(u;v) (13.35)
Ny(s;t) = xt(s;t)zs(s;t) xs(s;t)zt(s;t) (13.36)
Ny(u;v) = xv(u;v)zu(u;v) xu(u;v)zv(u;v) (13.37)
Nz(s;t) = xs(s;t)yt(s;t) xt(s;t)ys(s;t) (13.38)
Nz(u;v) = xu(u;v)yv(u;v) xv(u;v)yu(u;v): (13.39)
Since s = u, t = v are trivial solutions, we must exclude them from the system, otherwise a
Bernstein subdivision-based algorithm would attempt to solve for an in nite number of roots.
For the self-intersections of a normal o set of a planar polynomial curve case we have addressed
this problem by dividing out the common factor by some algebraic manipulations [17]. However,
for the surface case we can not divide out these factors from the system directly, since terms
x(s;t) x(u;v), y(s;t) y(u;v) and z(s;t) z(u;v) do not necessarily exactly involve the factors
s u and t v. See [16] for details for how to exclude trivial solutions.
13.3.3 Tracing algorithm
Finding the starting points for tracing the self-intersection curve is very similar to the same
problem for surface-surface intersection in Section 9.8.2. By considering that the self-intersection
curve is a function of another parameter , s = s( ), t = t( ), u = u( ), v = v( ), and by
di erentiating the equation for self-intersection curves of an o set with respect to yields
^rs dsd + ^rt dtd = ^ru dud + ^rv dvd (13.40)
13
If we denote ^r(s;t) = [^x(s;t); ^y(s;t); ^z(s;t)] and ^r(u;v) = [^x(u;v); ^y(u;v); ^z(u;v)], we can solve
vector equation (13.40) for dsd , dtd , dud and dvd . This is a linear system of 3 equations in 4
unknowns _s, _t, _u, _v. The solution of this underconstrained problem is given by
ds
d =
^xt ^xu ^xv
^yt ^yu ^yv
^zt ^zu ^zv
= jA1j (13.41)
dt
d =
^xs ^xu ^xv
^ys ^yu ^yv
^zs ^zu ^zv
= jA2j (13.42)
du
d =
^xs ^xt ^xv
^ys ^yt ^yv
^zs ^zt ^zv
= jA3j (13.43)
dv
d =
^xs ^xt ^xu
^ys ^yt ^yu
^zs ^zt ^zu
= jA4j: (13.44)
Here is an arbitrary non-zero factor that can be chosen to provide arc-length parametrization
in the parameter domain as follows:
d =
p
ds2 + dt2 =
q
2(jA1j2 + jA2j2)d (13.45)
hence
= 1pjA
1j2 + jA2j2
: (13.46)
The points of the self-intersection curves are computed successively by integrating the initial
value problem for a system of nonlinear di erential equations (13.41) to (13.44) using the
variable step size and variable order Adams method [2]. The sign of determines the direction
in which the solution proceeds. See Figures 13.12 and 13.13 for illustrations.
13.3.4 Self-intersections of o sets of explicit quadratic surfaces
Although o set surfaces are widely used in various engineering applications, their degenerating
mechanism is not well known in a quantitative manner. We know that any regular surface can
be locally approximated in the neighborhood of a point p by the explicit quadratic surface of
the form r(x;y) = [x;y; 12( x2 + y2)]T to the second order where and are the principal
curvatures at point p. Therefore investigations of the self-intersecting mechanisms of the o sets
of explicit quadratic surfaces due to di erential geometry properties lead to an understanding
of the self-intersecting mechanisms of o sets of regular parametric surfaces.
Locally any surface can be expressed as a graph of a di erentiable function [3]. Given
a point p on the parametric surface S, we can set an orthogonal Cartesian coordinate
system xyz such that xy-plane coincides with the tangent plane of S at p and z-axis is
along the normal at p. It follows that in the neighborhood of p any parametric surface
S can be represented in the form r(x;y) = [x;y;h(x;y)]T , where h is a di erentiable
function with h(0;0) = hx(0;0) = hy(0;0) = 0.
14
t (v)
s (u)
(a)
x
y
z
(b)
x
y
z
(c)
Figure 13.12: Self-intersection curves of the o set of bicubic patch when d=0.09. Figure (a)
shows the pre-images of the self-intersection curves in parameter domain. The same symbols
are mapped to the same points in the o set surface. Figure (b) shows the mapping of the
self-intersection curves in the parameter domain onto the progenitor surface. Figure (c) shows
the o set surface and the self-intersection curves.
15
s (u)
t (v)
(a)
x
y
z
(b)
x
y
z
(c)
Figure 13.13: Self-intersection curves of the o set of bisextic patch when d=-0.08. Figure (a)
shows the pre-images of the self-intersection curves in parameter domain. The same symbols
are mapped to the same points in the o set surface. Figure (b) shows the mapping of the
self-intersection curves in the parameter domain onto the progenitor surface. Figure (c) shows
the o set surface and the self-intersection curves.
16
We can Taylor expand h(x;y) about (0;0) as follows
h(x;y) = h(0;0) + [hx(0;0)x + hy(0;0)y] + 12![hxx(0;0)x2 + 2hxy(0;0)xy + hyy(0;0)y2]
+ 13![hxxx(0;0)x3 + 3hxxy(0;0)x2y + 3hxyy(0;0)xy2 + hyyy(0;0)y3] + R (13.47)
where lim(x;y)!(0;0) R(x2 + y2) 32 = 0.
If we take into account that h(0;0) = hx(0;0) = hy(0;0) = 0, we can consider
h(x;y) = 12[hxx(0;0)x2 + 2hxy(0;0)xy + hyy(0;0)y2] (13.48)
as the second order approximation of h(x;y).
Let us denote E, F, G and L, M, N as coe cients of the rst and second fundamental
forms of the surface. If we assume further that x and y axes are directed along the
principal directions at (0;0;0), assuming (0;0;0) is not an umbilic, then F = M = 0 [3].
It follows that hxy(0;0) = 0, since M = hxy=
q
1 + h2x + h2y. Although we have assumed
(0;0) is not an umbilic, we can show that hxy(0;0) will also vanish when the point is an
umbilic [19]. Also the principal curvatures at p can be expressed as follows [3]:
if hxx(0;0) > hyy(0;0); min = LE = hxx(0;0); max = NG = hyy(0;0)(13.49)
if hxx(0;0) < hyy(0;0); max = LE = hxx(0;0); min = NG = hyy(0;0)(13.50)
If we set = hxx(0;0) and = hyy(0;0) (thus = and = are principal curvatures)
and assuming that p is a nonplanar point, the surface can be written locally as a second
order approximation in the nonparametric form given by
z = 12( x2 + y2) (13.51)
Its corresponding parametric form is
r(x;y) = [x;y; 12( x2 + y2)]T (13.52)
In the sequel we assume that d > 0, > 0 and without loss of generality. It follows
that at (0,0,0) equation (13.50) holds and the x-axis will be the direction of maximum
principal curvature and y-axis will be the direction for the minimum principal curvature.
If and vanish at the same time, then the surface is part of a plane. Equation (13.51)
or (13.52) represents explicit quadratic surfaces which can be categorized into four
types according to combinations of and as listed in Table 13.1.
The four types of explicit quadratic surfaces are depicted in Figure 13.14.
Theorem [15] Self-intersection curves of o sets of the explicit quadratic surfaces r(x;y) =
[x;y; 12( x2 + y2)]T and their corresponding curves in the xy-plane are as follows:
17
Signs of and Types of Surfaces Types of Points at p
< 0 Hyperbolic Paraboloid Hyperbolic Point
> 0 and 6= Elliptic Paraboloid Elliptic Point
= Paraboloid Umbilical Point
= 0 or = 0 Parabolic Cylinder Parabolic Point
Table 13.1: Four types of explicit quadratic surfaces according to and
Figure 13.14: Explicit quadratic surfaces z = 12( x2+ y2). (a) Top left: Hyperbolic paraboloid
( = 3, = 1). (b) Top right: Elliptic paraboloid ( = 1, = 3). (c) Bottom left: Paraboloid
( = = 3). (d) Bottom right: Parabolic cylinder ( = 0, = 3).
18
1. An o set of hyperbolic paraboloid ( < 0 < ) self-intersects only in the y-direction when
1
< d. The resulting self-intersection curve is a parabola given by
z = 2( )x2 + ( d)
2 + 1
2 ; y = 0 (13.53)
q
( d)2 1 x
q
( d)2 1
and its corresponding curve in the parameter space (i.e., xy-plane) is an ellipse when
j j 6= or a circle when j j = , (see Figure 13.15 (a)) given by
x2 p
( d)2 1
2 + y
2
p
( d)2 1
2 = 1 (13.54)
2. An o set of an elliptic paraboloid (0 < < ) self-intersects only in the y-direction
when 1 < d < 1 and self-intersects in both x and y-directions when 1 < d. The self-
intersection curve which self-intersects in the y-direction is a parabola (see Figure 13.11)
given by equation (13.54) and the corresponding curve in the xy-plane is an ellipse (see
Figures 13.11, 13.15 (b)) given by equation (13.54). The self-intersection curve which
self-intersects in the x-direction is also a parabola given by
z = 2( )y2 + ( d)
2 + 1
2 ; x = 0 (13.55)
q
( d)2 1 x
q
( d)2 1
its corresponding curve in the xy-plane is an ellipse (see Figures 13.15 (c), (d)) given by
x2 p
( d)2 1
2 + y
2
p
( d)2 1
2 = 1 (13.56)
3. An o set of a paraboloid (0 < = ) self-intersects in all directions, when 1 = 1 < d.
The self-intersection curve is a point (0;0; ( d)2 12 ), and its corresponding curve in the
xy-plane is a circle (see Figure 13.15 (e)) given by
x2 + y2 =
p
( d)2 1
!2
(13.57)
4. An o set of a parabolic cylinder ( = 0 < ) self-intersects only in the y-direction when
1
< d. The resulting self-intersection curve is a straight line in the xz-plane
z = ( d)
2 1
2 ; y = 0 (13.58)
and its corresponding curves in the xy-plane (see Figure 13.15 (f)) are two straight lines
given by
y =
p( d)2 1
(13.59)
19
(a) x
y
-0.67 -0.33 0.00 0.33 0.67
-0.50
-0.17
0.17
0.50
(b) x
y
-0.67 -0.33 0.00 0.33 0.67
-0.50
-0.17
0.17
0.50
(c) x
y
-0.67 -0.33 0.00 0.33 0.67
-0.50
-0.17
0.17
0.50
(d) x
y
-0.67 -0.33 0.00 0.33 0.67
-0.50
-0.17
0.17
0.50
(e) x
y
-0.67 -0.33 0.00 0.33 0.67
-0.50
-0.17
0.17
0.50
(f) x
y
-0.67 -0.33 0.00 0.33 0.67
-0.50
-0.17
0.17
0.50
Figure 13.15: Self-intersection and ridge curves of o sets of explicit quadratic surfaces. The
solid lines correspond to self-intersection curves which degenerates in y-direction. The dashed
lines correspond to min(x;y) = 1d. The dot dashed lines correspond to self-intersection curves
which degenerates in x-direction. The dot dot dashed lines correspond to max(x;y) = 1d.
Symbols and represent the locations of generic lemon type umbilic and non-generic umbilic.
(a) hyperbolic paraboloid ( = 2, = 2, d = 0:6) (b) elliptic paraboloid ( = 1:75, = 2,
d = 0:55) (c) elliptic paraboloid ( = 1:75, = 2, d = 0:6) (d) elliptic paraboloid ( = 1:75,
= 2, d = 0:65) (e) paraboloid ( = = 2, d = 0:6) (f) parabolic cylinder ( = 0, = 2,
d = 0:6)
20
13.3.5 Approximations
Parametric O set Surface Approximation Algorithm [23]. (See Figure 13.16)
1. Input: NURBS surface patch.
2. O set each vertex of polygon by d with unit normal vector given by
Nij = 18
8X
i=1
ni (13.60)
3. Check deviation of the approximate o set with the true o set (using the same weights
for rational functions as the progenitor).
4. If the deviation is larger than the given tolerance subdivide the surface into four and go
back to step 1. If the deviation is smaller than the given tolerance stop.
Nij
nk
Nij = (1/8)Σ n
k=1
8
k
Figure 13.16: O set surface approximation.
21
Bibliography
[1] Y. J. Chen and B. Ravani. O set surface generation and contouring in computer-aided
design. Journal of Mechanisms, Transmissions, and Automation in Design, Transactions
of the ASME, 109(3):133{142, March 1987.
[2] G. Dahlquist and A. Bj orck. Numerical Methods. Prentice-Hall, Inc., Englewood Cli s,
NJ, 1974.
[3] P. M. do Carmo. Di erential Geometry of Curves and Surfaces. Prentice-Hall, Inc.,
Englewood Cli s, NJ, 1976.
[4] R. T. Farouki. Exact o set procedures for simple solids. Computer Aided Geometric
Design, 2(4):257{279, 1985.
[5] R. T. Farouki. The approximation of non-degenerate o set surfaces. Computer Aided
Geometric Design, 3(1):15{43, May 1986.
[6] R. T. Farouki and C. A. Ne . Algebraic properties of plane o set curves. Computer Aided
Geometric Design, 7(1 - 4):101{127, 1990.
[7] R. T. Farouki and C. A. Ne . Analytic properties of plane o set curves. Computer Aided
Geometric Design, 7(1 - 4):83{99, 1990.
[8] R. T. Farouki and T. W. Sederberg. Analysis of the o set to a parabola. Computer Aided
Geometric Design, 12(6):639{645, September 1995.
[9] I. D. Faux and M. J. Pratt. Computational Geometry for Design and Manufacture. Ellis
Horwood, Chichester, England, 1981.
[10] R. Klass. An o set spline approximation for plane cubic splines. Computer-Aided Design,
15(4):297{299, September 1983.
[11] R. Kunze, F.-E. Wolter, and T. Rausch. Geodesic Voronoi diagrams on parametric sur-
faces. In Proceedings of Computer Graphics International, CGI ’97, June 1997, pages
230{237. IEEE Computer Society Press, 1997.
[12] T. Lozano-Perez and M. A. Wesley. An algorithm for planning collision-free paths amongst
polyhedral obstacles. Communications of the ACM, 25(9):560{570, October 1979.
[13] W. L u. Rational o sets by reparametrization. Technical report, Zhejiang University,
December 1992.
22
[14] T. Maekawa. An overview of o set curves and surfaces. Design Laboratory Memorandum
98-2, MIT, Department of Ocean Engineering, Cambridge, MA, March 1998.
[15] T. Maekawa. Self-intersections of o sets of quadratic surfaces: Part I, explicit surfaces.
Engineering with Computers, 14:1{13, 1998.
[16] T. Maekawa, W. Cho, and N. M. Patrikalakis. Computation of self-intersections of o sets
of B ezier surface patches. Journal of Mechanical Design, Transactions of the ASME,
119(2):275{283, June 1997.
[17] T. Maekawa and N. M. Patrikalakis. Computation of singularities and intersections of
o sets of planar curves. Computer Aided Geometric Design, 10(5):407{429, October 1993.
[18] T. Maekawa, N. M. Patrikalakis, T. Sakkalis, and G. Yu. Analysis and applications of pipe
surfaces. Computer Aided Geometric Design, 15(5):437{458, May 1998.
[19] T. Maekawa, F.-E. Wolter, and N. M. Patrikalakis. Umbilics and lines of curvature for
shape interrogation. Computer Aided Geometric Design, 13(2):133{161, March 1996.
[20] N. M. Patrikalakis and L. Bardis. O sets of curves on rational B-spline surfaces. Engi-
neering with Computers, 5:39{46, 1989.
[21] N. M. Patrikalakis and L. Bardis. Localization of rational B-spline surfaces. Engineering
with Computers, 7(4):237{252, 1991.
[22] N. M. Patrikalakis and H. N. Gursoy. Shape interrogation by medial axis transform. In
B. Ravani, editor, Proceedings of the 16th ASME Design Automation Conference: Ad-
vances in Design Automation, Computer Aided and Computational Design, Vol. I, pages
77{88, Chicago, IL, September 1990. New York: ASME.
[23] N. M. Patrikalakis and P. V. Prakash. Free-form plate modeling using o set surfaces.
Journal of OMAE, Transactions of the ASME., 110(3):287{294, 1988.
[24] B. Pham. O set curves and surfaces: a brief survey. Computer-Aided Design, 24(4):223{
229, April 1992.
[25] T. Rausch, F.-E. Wolter, and O. Sniehotta. Computation of medial curves on surfaces.
In T. Goodman and R. Martin, editors, The Mathematics of Surfaces VII, pages 43{68.
Information Geometers, 1997.
[26] J. R. Rossignac and A. G. Requicha. O setting operations in solid modelling. Computer
Aided Geometric Design, 3(2):129{148, 1986.
[27] W. Tiller and E. G. Hanson. O sets of two-dimensional pro les. IEEE Computer Graphics
and Applications, 4(9):36{46, September 1984.
[28] T. J. Willmore. An Introduction to Di erential Geometry. Clarendon Press, Oxford, 1959.
[29] F.-E. Wolter. Cut locus and medial axis in global shape interrogation and representation.
Memorandum 92-2, Cambridge MA: MIT Ocean Engineering Design Laboratory, January
1992.
23