《Computational Geometry》lecnotes 13 N. M. Patrikalakis

13472J/1.128J/2158J/16940J COMPUTATIONAL GEOMETRY Lecture 13 N. M. Patrikalakis Massachusetts Institute of Technology Cambridge MA 02139-4307. USA Copyright @2003 Massachusetts Institute of Technology Contents 1 3 Offsets of Parametric curves and surfaces 13.1 Motivation 13.2 Parametric offset curves 13.2.1 Differential geometry of parametric offset curves 13.2.2 Singularities of parametric offset curves 13.2.3 Approximations 13.3 Parametric offset surfaces 3.1 Differential geometry of parametric offset surfaces 13.3.2 Singularities of parametric offse et surfaces 13.3.3 Tracing algorithm 13 13.3.4 Self-intersections of offsets of explicit quadratic surfaces 13.3.5 Approximations Bibliography Reading in the Textbook Chapter 11, pp. 293-353

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 Offsets of Parametric Curves and Surfaces 2 13.1 Motivation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 13.2 Parametric offset curves . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 13.2.1 Differential geometry of parametric offset curves . . . . . . . . . . . . . 5 13.2.2 Singularities of parametric offset curves . . . . . . . . . . . . . . . . . . 6 13.2.3 Approximations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 13.3 Parametric offset surfaces . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 13.3.1 Differential geometry of parametric offset surfaces . . . . . . . . . . . . 10 13.3.2 Singularities of parametric offset surfaces . . . . . . . . . . . . . . . . . 11 13.3.3 Tracing algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13 13.3.4 Self-intersections of offsets of explicit quadratic surfaces . . . . . . . . . 14 13.3.5 Approximations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21 Bibliography 22 Reading in the Textbook • Chapter 11, pp. 293 - 353 1

Lecture 13 Offsets of parametric curves and Surfaces 13.1 Motivation Offsets are defined as the locus of points at a signed distance d along the normal of a planar curve or surface. A literature survey on offset 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 24] is given by Maekawa [14]. Offset 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) of Bal Tool Driving Plane Figure 13. 1: NC machining

Lecture 13 Offsets of Parametric Curves and Surfaces 13.1 Motivation Offsets are defined as the locus of points at a signed distance d along the normal of a planar curve or surface. A literature survey on offset 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]. Offset 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

Definition of tolerance regions[4, 26, 21].(See Figure 13.2) Figure 13.2: Definition of tolerance regions Access space representations in robotics 12.(See Figure 13.3) 「 Figure 13.3: Access space representations in robotics

• Definition of tolerance regions [4, 26, 21]. (See Figure 13.2). Figure 13.2: Definition of tolerance regions. • Access space representations in robotics [12]. (See Figure 13.3) ￾✁￾✁￾✁￾✂￾ ￾✁￾✁￾✁￾✂￾ ￾✁￾✁￾✁￾✂￾ ￾✁￾✁￾✁￾✂￾ ￾✁￾✁￾✁￾✂￾ ￾✁￾✁￾✁￾✂￾ ￾✁￾✁￾✁￾✂￾ ￾✂￾✁￾✁￾✁￾✂￾ ￾✂￾✁￾✁￾✁￾✂￾ ￾✂￾✁￾✁￾✁￾✂￾ ￾✂￾✁￾✁￾✁￾✂￾ ￾✂￾✁￾✁￾✁￾✂￾ ￾✂￾✁￾✁￾✁￾✂￾ ￾✂￾✁￾✁￾✁￾✂￾ ￾✂￾✁￾✁￾✁￾✂￾ ￾✂￾✁￾✁￾✁￾✂￾ ￾✂￾✁￾✁￾✁￾✂￾ 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. e feature recognition through construction of skeleto medial axes of geometric models 22, 29.( See Figure 13.5). The medial axis is made up of boundary offset intersections Figure 13.5: Medial Axis The concept of offset curves generalizes to pipe surfaces when the progenitor is a general 3D curve [18] geodesic offsets when the progenitor is curve on a surface[20[25][11]

• 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 offset intersections. Figure 13.5: Medial Axis. The concept of offset curves generalizes to • pipe surfaces when the progenitor is a general 3D curve [18]. • geodesic offsets when the progenitor is curve on a surface [20] [25] [11]. 4

13.2 Parametric offset curves 13.2.1 Differential geometry of parametric offset curves lanar parametric curve r(t)is given by r(t)={x(t,y(切),t∈[0.,1 where a and y are differentiable functions of a parameter t The unit normal vector of a plane curve, which is orthogonal to t, is given by n=t×ez ((t),-i(t) √x(t)+y2(t) where e2=(0, 0, 1) is a unit vector perpendicular to the plane of the curve, see Figure For a plane curve, the Frenet formulae reduce to dt ds ds where K is the signed curvature of the curve given by 2)2 (13.4) where v=r(t)I is the parametric speed. The curvature k 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 y (t) h Figure 13.6: Definitions of unit tangent and normal vectors

13.2 Parametric offset curves 13.2.1 Differential geometry of parametric offset curves • A planar parametric curve r(t) is given by r(t) = [x(t), y(t)] , t ∈ [0, 1] (13.1) where x and y are differentiable 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 x˙ 2 (t) + y˙ 2 (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) · ez v 3 = x˙y¨ − y˙x¨ (x˙ 2 + y˙ 2) 3 2 (13.4) where v = |r˙(t)| is the parametric speed. The curvature κ of a curve at point P is positive when the direction of n and P~C 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: Definitions of unit tangent and normal vectors. 5

A planar offset curve r(t) with signed offset distance d to the progenitor r(t) is defined by r(t=r(t)+dn(t) (13.5) where d>0 corresponds to positive("exterior")and d<0 corresponds to negative The unit tangent vector of the offset curve(see Figure 13.7 for illustration) r 1+kd i1+ The unit normal vector of the offset curve(see Figure 13.7 for illustration) n=t xez 1+d (137) . Curvature of the offset curve 13.2.2 Singularities of parametric offset curves There are two kinds of singularities on the offset 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 offset is d Cusps: This point occurs at a point t where the tangent vector vanishes d (13.9) A cusp at t=te can be further subdivided into 7 1. Ordinary cusps when A(tc)#0 2. Extraordinary points when i(tc)=0 and k(tc)#0 Note that(1+Kd)/1+nd in equations(13.6)and(13.7) changes abruptly from-1 to 1 Equation(13.9)for r(t)=a(t), y(t)) can be reduced to Cusp, while at extraordinary when the parameter t passes through t= tc at an ordinary points(1+nd)/1+ nd does not change its value, see Fi e13.7. 1(0(6-y/2(+2()(2()+0(=0

• A planar offset curve ˆr(t) with signed offset distance d to the progenitor r(t) is defined by ˆr(t) = r(t) + dn(t) (13.5) where d > 0 corresponds to positive (“exterior”) and d < 0 corresponds to negative (“interior”) offsets. • The unit tangent vector of the offset curve (see Figure 13.7 for illustration) ˆt = ˙ˆr | ˙ˆr| = 1 + κd |1 + κd| t (13.6) • The unit normal vector of the offset curve (see Figure 13.7 for illustration) nˆ = ˆt × ez = 1 + κd |1 + κd| n (13.7) • Curvature of the offset curve κˆ = κ |1 + κd| (13.8) 13.2.2 Singularities of parametric offset curves There are two kinds of singularities on the offset 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 offset is d = −R. Cusps: This point occurs at a point t where the tangent vector vanishes. κ(t) = − 1 d (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)/|1 + κd| 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)/|1 + κd| does not change its value, see Figure 13.7. Equation (13.9) for r(t) = {x(t), y(t)} can be reduced to d [x¨(t)y˙(t) − x˙(t)y¨(t)] − q x˙ 2(t) + y˙ 2(t) h x˙ 2 (t) + y˙ 2 (t) i = 0 (13.10) 6

Figure 13.7: Offsets to a parabola r=[t, t(thick solid line)with offsets d=-03,-05,-08, dapted from [5. At d=-03 the tangent and normal vectors of the offset have the same sense that of the progenitor, while at d=-08 they flip directions By setting T=i+y 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=(t, t), the unit tangent and principal normal vectors are given by dr dr dt (1, 2t) V1+42' n=txe (2,-1 dt ds The curvature and its derivative are given ()=xE rP(1+412)2 (t) 24(1+42) (1+4t2)3 Since A(0)=0, k(t) reaches an extremum at t=0 and furthermore as K(0) t the offset is non- degenerate, while when d=-i,t=0 is an extraordinary point. Let us solve k(t)=-1/d t which yield 3√4d-1 We can easily see that if d>-1/2, there is no real root. This means that there 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

Figure 13.7: Offsets to a parabola r = [t,t 2 ] (thick solid line) with offsets d=-0.3, -0.5, -0.8, adapted from [5]. At d = −0.3 the tangent and normal vectors of the offset have the same sense that of the progenitor, while at d = −0.8 they flip directions. By setting τ 2 = x˙ 2 + y˙ 2 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,t 2 ), the unit tangent and principal normal vectors are given by t = dr ds = dr dt dt ds = (1, 2t) √ 1 + 4t 2 , n = t × ez = (2t, −1) √ 1 + 4t 2 The curvature and its derivative are given by κ(t) = (r˙ × ¨r) · ez |r˙| 3 = 2 (1 + 4t 2) 3 2 , κ˙(t) = −24t(1 + 4t 2 ) 1 2 (1 + 4t 2) 3 Since κ˙(0) = 0, κ(t) reaches an extremum at t = 0 and furthermore as κ¨(0) − 1 2 the offset is non￾degenerate, while when d = − 1 2 , t = 0 is an extraordinary point. Let us solve κ(t) = −1/d for t which yields t = ± q 3 √ 4d 2 − 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 offset curve(see also Figures 13.7 and 13. 8)can be obtained by seeking pairs of distinct parameter values sf 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] r(s)+、()+y(=()+-i(d i(sd √x(t)+y2(t) (t)d 以()()+(5=0)-√( (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, T and o where r2=i2(s)+2( 2=i2(t)+j2(t) (13.14) Such a system can be solved using the IPP algorithm, see also [17. However s are trivial solutions, and we must exclude them from the system, otherwise a Bernstein subdivision-based algorithm would attempt to solve for an infinite number of roots. In this case we have addressed the problem by dividing out the common factor by some Figure 13.8: Self-intersection of the offset curve of a parabola. Left: Interior offsets to the parabola r(t)=t, t] with d=-08 and cutter path; Right: Trimmed interior offsets to the parabola r(t)=[t, t2] with d=-0.8 and cutter path

Self-intersections of an offset 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)d p x˙ 2(s) + y˙ 2(s) = x(t) + y˙(t)d p x˙ 2(t) + y˙ 2(t) y(s) − x˙(s)d p x˙ 2(s) + y˙ 2(s) = y(t) − x˙(t)d p x˙ 2(t) + y˙ 2(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 = x˙ 2 (s) + y˙ 2 (s) (13.13) σ 2 = x˙ 2 (t) + y˙ 2 (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 infinite 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 offset curve of a parabola. Left: Interior offsets to the parabola r(t) = [t,t 2 ] with d = −0.8 and cutter path; Right: Trimmed interior offsets to the parabola r(t) = [t,t 2 ] with d = −0.8 and cutter path 8

13.2.3 Approximations In general, an offset curve is functionally more complex than its progenitor curve because of the square root involved in the expression of the unit normal vector. Li[13 for example has shown that offset of a parabola is a rational curve and its singular point at infinity was studied by Farouki and Sederberg[8. However, this result has not been generalized to higher order curves Farouki and Neff [6 have shown that the two-sided offsets of planar rational polynomial curves are high-degree implicit algebraic curves fo(a, y)=0 of potentially complex shape. These equations can not typically be separated into two equations describing interior and exterior offsets individually. The degree of this implicit offset curve is no= 4n-2-2m where n is the degree of polynomial generator curve r=[r(t),y(t) and m is the degree of o(t)= GCD('(t),y(t)). For example the degree of the two-sided offset curve of a parabola r(t)=(t, t2)is 6 and of a general polynomial cubic curve is 10 with o(t) constant If the progenitor surface is a NUrBS curve, then its offset is usually not a NURBS curve except for straight lines and circles Because of the wide application of offset surfaces and the difficulty 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 Input is a NUrBs curve 2. Offset each leg of polygon by d 3. Intersect consecutive legs of polygon to find new vertices 4. Check deviation of the approximate offset with the true offset 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 Approximated offset Curve Progen tor curve Figure 13.9: Offset curve approximation

13.2.3 Approximations • In general, an offset curve is functionally more complex than its progenitor curve because of the square root involved in the expression of the unit normal vector. Lu¨ [13] for example has shown that offset of a parabola is a rational curve and its singular point at infinity was studied by Farouki and Sederberg [8]. However, this result has not been generalized to higher order curves. Farouki and Neff [6] have shown that the two-sided offsets 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 offsets individually. The degree of this implicit offset 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(x 0 (t), y 0 (t)). For example the degree of the two-sided offset curve of a parabola r(t) = (t,t 2 ) 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 offset is usually not a NURBS curve, except for straight lines and circles. • Because of the wide application of offset surfaces and the difficulty 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. Offset each leg of polygon by d. 3. Intersect consecutive legs of polygon to find new vertices. 4. Check deviation of the approximate offset with the true offset 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: Offset curve approximation. 9

13.3 Parametric offset surfaces 13.3.1 Differential geometry of parametric offset surfaces ● Definition A parametric offset 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 defined as r(u, v)=r(u, u)+dn(u, u) (13.15) where d may be a positive or negative real number and n is the unit normal vector of r(u,) 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] If n(u, u) is the unit normal vector of r(u, u), then the relation between n and n is given Sn=(1+dmaa)(1+domin)s where S=furu and S=ru xrul or expanding the right hand side of equation(13 16) and using the definitions of Gaussian curvature K and mean curvature h min,H (13.17) quation(13 16)can be rewritten as follows Sn=S(1+2Hd+Kd If we take the norm of equation(13.16), we obtain S=SI(1 +dkmaz)(1+domin ) 13.19) and substituting S into equation(13. 16) yields n≈(1+dma)(1+ demit l(1+dkmaz)(1+drmir ainn From this relation n and f are collinear but may be directed in opposite directions, if domar 0 where kmin 0, provided the above sign convention is used

13.3 Parametric offset surfaces 13.3.1 Differential geometry of parametric offset surfaces • Definition A parametric offset 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 defined 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ˆ = |ˆru׈rv| and S = |ru×rv| or expanding the right hand side of equation (13.16) and using the definitions of Gaussian curvature K and mean curvature H K = κmaxκmin, H = κmax + κmin 2 (13.17) equation (13.16) can be rewritten as follows: Sˆnˆ = S(1 + 2Hd + Kd 2 )n (13.18) If we take the norm of equation (13.16), we obtain Sˆ = S|(1 + dκmax)(1 + dκmin)| (13.19) and substituting Sˆ into equation (13.16) yields nˆ = (1 + dκmax)(1 + dκmin) |(1 + dκmax)(1 + dκmin)| n (13.20) From this relation n and nˆ are collinear but may be directed in opposite directions, if dκmax 0 where κmin 0, provided the above sign convention is used. 10