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