An overview of offt curves and surfaces
Takashi Maekawa *
Design Laboratory,Department of Ocean Engineering,Massachutts Institute of Technology,Cambridge,MA 02139-4307,USA
Received 15April 1998;accepted 22May 1998
Abstract
A literature survey on offt curves and surfaces up to 1992was carried out by Pham (Pham B,Offt curves and surfaces:a brief survey.Computer Aided Design 1992;24(4):223–229).The objective of this article is to overview the literature after 1992and tho which were not
cited in aforementioned paper.The article focus on five active areas of rearch on offts:(1)reprenting exact offts in Be
´zier /B-spline format,(2)approximations,(3)lf-interctions,(4)geodesic offts and (5)general offts.᭧1999Elvier Science Ltd.All rights rerved.
Keywords:Offt curves;Offt surfaces;Self-interctions;Pythagorean hodographs;Geodesics offts;General offts
1.Introduction
Offt curves /surfaces ,also called parallel curves /surfaces ,are defined as locus of the points which are at constant distant d along the normal from the generator curves /surfaces .Offts are widely ud in various applica-tions,such as tool path generation for 2.5D pocket machin-ing [16,15,42],3D NC machining [2,20],definition of tolerance regions [32],access space reprentations in robotics [22],curved plate (shell)reprentation in solid modeling [34],rapid prototyping where materials are soli-dified in successive two-dimensional layers [13],brush stroke reprentation [17]and in feature recognition through construction of skeletons or medial axes of geometric models [33,49].
A literature survey on offt curves and surfaces prior to 1992was conducted by Pham [36].The objective of this article is to overview the literature after 1992and tho which were not cited by [36].
Sometimes it was unavoidable to cite articles listed by Pham [36],in such cas we typed the author’s name and year of publication and referred to [36]to avoid overlaps.There are mainly five active areas of
rearch on offts:(1)reprenting exact offts in Be
皮肤天生黑怎么美白´zier /B-spline format,(2)approximations,(3)lf-interctions,(4)geodesic offts and (5)general offts.
In general,an offt is functionally more complex than its progenitor becau of the square root involved in the expres-sion of the unit normal vector.If the progenitor is a rational
B-spline,then its offt is usually not a rational B-spline,except for special cas.Special cas for curves include straight line and circle,for surfaces include plane,sphere,circular cylinder,circular cone,torus and cyclides [5].Farouki and Sakkalis [9]introduced a class of special curve called Pythagorean hodograph curves who offts are rational curves.
As a result of the wide application of offt curves and surfaces,and the difficulty in directly incorporating such entities in geometric modeling systems becau of their potential analytic and alg
ebraic complexity,a number of rearchers have developed approximation algorithms for the types of geometries in terms of piecewi polynomial or rational polynomial functions.Such approximation algo-rithms are reviewed in [7,36].
Offt curve /surface may lf-interct locally when the absolute value of the offt distance exceeds the minimum radius of curvature in the concave regions.Also the offt curve /surface may lf-interct globally when the distance between two distinct points on the curve /surface reaches a local minimum (i.e.the prence of a constriction of the curve /surface ).The local and global lf-interctions can be visualized as machining a part using a cylindrical /spherical cutter who radius is too large for 2.5D/3D milling.It is an esntial task for many practical applica-tions to detect all components of the lf-interction points /curves correctly and generate the trimmed offt curve /surface .If the cutter follows the trimmed offt,there will be no overcut or gouging,however we are left with undercut regions which must be milled with a smaller size cutter.In some of the engineering applications,we need to
0010-4485/99/$-e front matter ᭧1999Elvier Science Ltd.All rights rerved.PII:S0010-4485(99)00013-5
*Tel.:ϩ1-617-253-6762;fax:ϩ1-617-253-8125.
E-mail address:tmaekawa@deslab.mit.edu (T.Maekawa)
extend the concept of classical offt,which has constant distance d along the normal from the generator,to geodesic offt where constant distance is replaced by geodesic distance(distance measured from a curve on a surface along the geodesic curve drawn orthogonal to the curve) or general offt where offt direction is not necessarily in the normal direction.
The article is organized as follows:Wefirst review the rational reprentations of offts which can be incorporated directly into current CAD software.Secondly we summar-ize the recent developments in approximation algorithms, followed by a summary of methods for detecting all compo-nents of lf-interction points/curves of an offt curve/ surface.Then we survey the rearch on geodesic offts followed by a survey on general offts.Finally some concluding remarks are provided.
2.Pythagorean hodograph
2.1.Curves
Farouki and Sakkalis[9]introduced a class of special planar polynomial curves called Pythagorean hodograph (PH)curves r(t) (x(t),y(t)),who hodograph(derivative) components_x t ;_y t and a polynomial t(t)form a Pytha-
gorean triple_x2 t ϩ_y2 t t2 t .Thus,the PH curve has polynomial parametric speed t(t);accordingly its offt is a
rational curve and its arc length is a polynomial function s(t) of the parameter t.The Pythagorean condition is satisfied by _x t a2 t Ϫb2 t c t ;_y t 2a t b t c t ;
t t a2 t ϩb2 t c t
1
where a(t),b(t)and c(t)are polynomials satisfying gcd(a,b) 1and max(deg(a),deg(b))Ն1[9,13].This condition is only a sufficient condition for a polynomial curve to have rational offt.For most applications c(t)is chon to be1.The lowest degree PH curve occurs when the polynomial a(t)and b(t)are linear and thus from(1)its degree is cubic.However,the resulting PH curve cannot posss an inflection point and hence is not practical. When a(t)and b(t)are quadratic,the PH curve will be a quintic and is the lowest degree curve to have enoughflex-ibility for practical u.The PH quintics can inflect and can interpolate arbitraryfirst-order Hermite data[8].The degree of the offt is2mϪ1for a degree m PH curve.Therefore, the lowest degree of the offt of a PH curve for practical u is nine.
Farouki and Shah[12]developed a real-time CNC inter-polators for PH curves using the fact that the arc length s(t) of the PH curve is merely a polynomial function.As a conquence the generation of reference points along a PH curve is reduced to a quence of polynomial rootfinding problems.
The planar PH curves can be easily generalized to a space PH curves[10]by tting the four real polynomials a(t), b(t),c(t),e(t)in the form
_x t a2 t Ϫb2 t Ϫc2 t 1 t ;_y t 2a t b t 1 t ; _z t 2a t c t 1 t
2 which leads to a polynomial parametric speed t t a2 t ϩb2 t ϩc2 t 1 t .A more thorough review of PH curves can be found in[13].
Pottmann[37]generalizes the concept of PH curves to the full class of rational curves with rational offts,by utilizing the projective dual reprentation.The rational curve is obtained as the envelope of its tangent line which is described as
g t :n x t xϩn y t y h t 3 where h(t)is the signed distance of the tangent line g(t)from the origin and is a rational function.The vector n x t ;n y t is a rational unit normal of the tangent line g(t)and is given by
n x t
2a t b t
a
;n y t a
2 t Ϫb2 t
a
; 4
where Eq.(1)is ud so that the unit normal vector becomes rational.The envelope of the one-parameter family of g(t) can be obtained by solving a linear system consisting of Eq.
(3)and its derivative_g t for x and y as a function of t, resulting in:
x t ;y t X t
W t
;Y t
W t
5 where
X 2ab _abϪa_b efϪ
1
2
a4Ϫb4 _efϪe_f
Y a2Ϫb2 _abϪa_b efϩab a2ϩb2 _efϪe_f
W a2ϩb2 _abϪa_b f2:
6
Here the rational function h(t)is replaced by e t =f t .The offt to(5)is obtained by simply replacing h(
t)by h(t)ϩd or equivalently e(t)by e(t)ϩf(t)d,and thus the degree of the offt remains the same as that of(5),which is an advantage over PH curves.The rational Be´zier reprentation can be easily derived by prescribing the polynomials a(t),b(t),e(t) and f(t)and expressing the resulting polynomials X,Y and W in Bernstein form.django
The form of Eqs.(5)and(6)become simpler if the dual Be´zier reprentation is ud[37].A plane dual Be´zier curve is defined by a family of tangent lines which has the form
U t u0 t ;u1 t ;u2 t
n
i 0
U i B i;n t 7 where U i are the Be´zier lines(constant line vectors)and
T.Maekawa/Computer-Aided Design31(1999)165–173 166
B i,n(t)is the i-th Bernstein polynomial of degree n.A line vector U u0;u1;u2 determines a straight line u0ϩu1xϩu2y 0.From the homogeneous reprentation of(3)in the form,u0Wϩu1Xϩu2Y 0;the dual repre-ntation in terms of projective geometry is given by
u0:u1:u2 Ϫ a2ϩb2 e:2abf: a2Ϫb2 f: 8 When f has a factor a2ϩb2,there exists a common divisor in the dual reprentation,thus it is convenient to t f a2ϩb2 p which leads to
u0:u1:u2 Ϫe:2abp: a2Ϫb2 p: 9 The control lines U i in(7)are easily obtained by expres-sing(9)in Bernstein form.
Lu¨[23]showed that the offt to a parabola is rational and its singular point at infinity was studied by Farouki and Sederberg[11].In[23]Lu¨proved that although the offt (to a parabola)is not rational in the parameter t,it may be expresd as a rational form in a new parameter,say u,via a parameter transformation.The reparametrizing function t t(u)is a rational function of the form t f u =u where f(u)is a quadratic polynomial in u.The transformed curve x u x t u ; y u y t u is not parametrized properly,as there are two values of u,which are the roots of the quadratic equation f(u)Ϫtu 0,for each corresponding point x;y x t ;y t :While the curve r u is traced twice in opposite directions as u increas fromϪ∞to0and from0toϩ∞, r u ϩ n u d defines a two-sided he inward offt for uϽ0and the outward offt for uϾ0.The resulting rational curve is of degree6.Lu¨[24]further derives a necessary and sufficient condition for a polynomial or rational parametric curve to have rational parametric speed.
2.2.Surfaces
Pottmann[37]applies the same principle of the rational curve with rational offts to the rational surface with rational offts.While the tangent lines are ud in the curve ca,a two-parametric t of tangent planes
g u;v :n x u;v xϩn y u;v yϩn z u;v z h u;v 10 is ud for the surface,where(n x,n y,n z)is a rational unit normal of the tangent plane and h(u,v)is a rational distance function from the origin.The rest of the discussions are analogous to the curve ca.
bc是什么意思
A developable surface has a constant tangent plane along a generator.Therefore its tangent plane depends on only one parameter,say u.In other words,a developable surface can be considered as the envelope of a one parameter family of planes g(u).The cross product of the normal vectors of the two planes g(u)and_g u provides a vector of the generator to the parameter u.An explicit reprentation of rational developable surfaces with rational offts has also been given in[37].
Lu¨[25]studied the rationality of the offts to quadrics. The key idea is to transform the problem of rational offts of quadrics to a simple problem on the rationality of a cubic algebraic surface and u existing results in algebraic geometry[43].He showed that the offts of paraboloids, ellipsoids and hyperboloids can be rationally parametrized, while cylinders and cones except for parabolic cylinders, cylinders of revolution and cones of revolution do not posss any rational offt.
Very recently Pottmann et al.[39]proved that offts of a nondevelopable rational ruled surface in the whole space always admit a rational parametrization.Even though the offts to ruled surfaces are rational in the whole space where they are defined,the offt patch to a rational patch may not be expressible as a rational patch.Therefore, further rearch is needed for applying this technique to a finite patch.
Peternell and Pottmann[35]construct PH surfaces from arbitrary rational surfaces with the aid of a geometric trans-formation which describes a change between two models of Laguerre geometry.The two fundamental elements of Laguerre geometry are oriented planes and cycles.A cycle reprents an oriented sphere or a point which is a sphere with zero radius.The orientation of the fundamental elements is determined by a unit normal vectorfield or equivalently by a signed radius for spheres.An oriented sphere and an oriented plane are said to be in oriented contact,if they are tangent to each other and their unit normals coincide at the point of contact.Laguerre geometry studies properties which are invariant under Laguerre trans-formations.If we consider a surface as an envelope of its oriented tangent planes,a dilatation,which is a Laguerre transformation that adds a constant d 0to the signed radius of each cycle without moving its center,maps the surface onto its offt at distance d.
tornado
golove3.Approximation
A recent article by Elber et al.[7]prented qualitative as well as quantitative comparisons for veral plane offt curve approximation methods.They counted the number of control points of the approximated offt as a measure for efficiency while the approximation error must lie within the prescribed tolerance.They found in general that the least square methods perform very well.However,when the progenitor curve is quadratic they showed that the simple method of Tiller and Hanson(1984)[36],which translates each edge of the control polygon into the edge normal direc-tion by an offt distance,outperforms the other methods. Among the compared methods,a method by[6]was not cited in[36]and[21]appeared after1992.Therefore we start with reviewing the two approximation methods. Elber and Cohen[6]employed an adaptive offt refine-ment approach.They estimated the offt approximation error by computing the maximum value of the difference function c t ^r a t Ϫr t
changj j2Ϫd2;where^r a t is an approximation of an offt of r r t x t ;y t :The
T.Maekawa/Computer-Aided Design31(1999)165–173167
offt is refined at the parameter value(s)where the maxi-mum error occur(s).Local loops are identifi
ed by using the fact that a pair of cusps always exist within the local lf-interction loop of the offt curve.The tangent vector of the offt^t t flips its direction at the cusps,and thus v t t t ·^t t ;where t(t)is the tangent vector of the input curve,
and becomes negative at the regions bounded by the cusps. Conquently,the local loops can be identified byfinding the zero t of v(t).However the details offinding the zero t are not given.Once a local loop is identified the curve is split into three parts,the region before thefirst cusp,the region between the cusps and the region after the cond cusp. The curve before thefirst cusp and the curve after the cond cusp are intercted against each other tofind the lf-interction point.The region bonded by the lf-inter-ction points are trimmed off.
everbright
Lee et al.[21]approximate a unit circle with piecewi quadratic polynomial curve gments q j(u),j 0,…,n.The hodograph curve_q j u is thus piecewi linear.If q(u)is reparametrized such that_r t _x t ;_y t and_q u t au t ϩb;cu t ϩd have the same direction at u u(
cu t ϩd au t ϩb
_y t
_x t
; 11
the approximated offt curve is defined by ^r a r t ϩd q u t .For a polynomial curve r(t)of degree m,the approximated offt curve is a rational curve of degree3mϪ2,which is of relatively high degree.Never-theless,their method generates offt curve approximations with a smaller number of curve subdivisions.To eliminate the local and global lf-interctions the input curve is approximated by discrete points and their connecting piece-wi line gments.Then the offt curve is generated by offtting the discrete points.The local redundant gment can be detected by checking the dot product between the line gment and its corresponding offt line gment.If the dot product is negative,the offt gment is eliminated. The global lf-interctions are detected by a plane sweep algorithm.Once a valid boundary topology on the offt polygon is computed,the valid parameter intervals of the input curve are extracted.The interction points of polygonal approximations may not provide accurate parameter values for the interction points of the offt curve and hence needs to be refined using,for example Newton’s method. Most of the tool path generation algorithms for2.5D pocket machining bad on offt contouring,first approxi-mates the input curve with a combination of straight lines and circular arc gments,as CNC interpolators accommo-dates only such elements and also the offts of tho elements are also straight lines an
d circular arc gments. Then the approximated boundary curve are offt.The diffi-cult part is to identify and remove all the loops.There are two different approaches to remove such loops,namely pair-wi interction method[15]and the Voronoi diagram method[16].Very recently Rohmfeld[42]developed an algorithm to generate tool paths for arbitrary simple piece-wi smooth G0generator curves.The redundant global loops are removed by interval operations on the parameter space of the generator curves using the invariance of Gauss–Bonnet values between the generator and the so-called IGB(Invariant Gauss–Bonnet)-offt which is equivalent to the rolling ball offt.
Sederberg and Buehler[45]approximates an offt of a Be´zier curve using Hermite interpolation of any even degree not less than the degree of the initial Be´zier curve.The reprentation of the offt is a rather special interval Be´zier curve of even degree n with only the middle control point as a rectangular interval.The size of the rectangular interval indicates the tightness of the approximation.
Most of the existing offt approximation schemes gener-ate the approximate offt curve in terms of Be´zier/B-spline format in an iterative manner bad on a subdivision tech-nique to improve the accuracy of the offt curve.If local and global lf-interctions exist,they must be eliminated after the approximation.The method introduced by Kimmel and Bruckstein[18]bypass the problems.T
hey generate offts via wavefront propagation methods influid dynamics.The algorithm works on a square grid with a resolution chon according to desired accuracy.Finally the contour lines(offts)are generated bad on grid values.Gurbuz and Zeid[14]employ a different approach to avoid lf-interctions.Instead of offtting analytically, the offtting process is carried out byfilling the clod balls of radius d for each point on the object.The union of the clod balls is subtracted from the object to construct the offt.An offt of a point in space is considered as a sphere. They simplified the implementation by assuming that the shape of a point is a cube and its offt is also a cube. First the object to be offt and its enclosing space are divided into small cubic cells.Therefore the accuracy is governed by the size of the cell.The cells that are on the object are referred to as boundary cells.The boundary cells parate the original t of cells into two subspaces,in and out of the object.Offt operation is carried out for each boundary cell.Chiang et al.[3]also compute offts without lf-interctions using the technique developed in image processing.First the domain is discretized into a two-dimen-sional grid and the progenitor curve is assigned to the near-est grid point.For each grid point,the distance to the discretized curve is evaluated.By extracting the grid points who distances are equal to the offt distance,an offt without lf-interction can be contructed.This approach also pos a trade-off between accuracy achieved and memory required.
4.Self-interction
4.1.Plane curves
Self-interctions of an offt of a planar curve r(t)can be obtained by eking pairs of distinct parameter values s t
T.Maekawa/Computer-Aided Design31(1999)165–173 168
such that
r s ϩd n s r t ϩd n t
12
where n (t )is unit normal vector of r (t )and d is the offt distance.If r (t )is a polynomial curve,Eq.(12)consists of two simultaneous bivariate non-rational functions involving polynomials and square root of polynomials which ari from normalization of the normal vector.When the input
curve is a B-spline curve,we can always split it into Be
´zier (polynomial)gments by a knot inrtion algorithm.In such cas not only the lf-interction i
n the offt of each split polynomial gment but also the interctions among the offts of different split gments must be checked.This system of equations has been solved in earlier work by local numerical techniques such as Newton-type methods which require good initial approximation to all roots,and hence cannot provide full assurance that all roots will be found.In contrast,global techniques find all the roots without initial approximation.If the governing equations are a system of nonlinear polynomials,there are three class of global methods that have been favored in recent CAD-related rearch.The are:algebraic techni-ques,homotopy,and subdivision method.Among the three methods,the subdivision method is the most attractive one becau of its speed and stability [29].
Even if the global subdivision method is ud,there are still two obstacles lying ahead in solving the two simulta-neous bivariate equations.One is the involvement of the square root which makes the system non-polynomial.And the other is how to avoid the trivial solutions s t which delays a solution process bad on subdivision as it attempts to resolve an infinite number of roots.The auxiliary variable method was introduced in [29]where the auxiliary variable
日本留学费用r is t such that r 2
p (t )and hence the square root of polynomial
p t p is replaced by r .Here the system of non-rational equations involving polynomials and square roots of polynomials has been transformed into a problem of polynomial equations which consists of four equations with four unknowns,where the two additional equations and variables result from replacing the two square roots involved in Eq.(12).The trivial solution s t can be avoided by factoring out s Ϫt from the governing equations.It is apparent that the two additional equations through auxiliary variables do not contain the factor s Ϫt .However,the original two equations,where the square roots of poly-nomials have been replaced by the auxiliary variables,posss the factors s Ϫt after some algebraic manipulations.Once the division operations are completed,a system of four polynomial equations with four unknowns without the trivial solution s t results,which can be robustly and efficiently solved by the subdivision-bad Interval Projected Polyhedron algorithm [29].The remarkable feature of this algorithm is that both local and global lf-interction can be found by the same algorithm.
So far the discussion was bad on ‘‘Given a curve and an offt distance,does the offt curve lf-interct?If so,
where does it lf-interct?’’However in some applica-tions,we may encounter the ca ‘‘Given a plane curve,what is the maximum offt distance such that its offt does not lf-interct?’’In [30]it
is discusd how to find the maximum possible radius of the pipe surface,which is the envelope of the t of spheres with radius r centered at the spine curve,such that it will not lf-inter-ct.The method can be easily applied to find the maximum offt distance without lf-interction by tting the spine curve as the given planar progenitor curve.Pipe surface can be considered as a natural generalization of the offt of a space curve,as a curve in space cannot define a unique offt.4.2.Quadrics
thematrix
The cond order algebraic surfaces (i.e.quadric surfaces)are widely ud in mechanical design.Especially the natural sphere,circular cone and circular cylinder result from machining operations such as rolling,turning,filleting,drilling and milling.The offts of the natural quadrics are also natural quadrics.Implicit quadrics such as ellipsoids,elliptic cones and elliptic cylinders are commonly found in die cavities and punches and are manu-factured by NC machining [4].Although Salmon [43]discusd the offts of quadrics more than a century ago,it was not known in the CAGD literature until recently.Maekawa [27]shows that lf-interction curves of offts of all the implicit quadratic surfaces are planar implicit conics and their corresponding curve on the progenitor surface can be expresd as the interction curve between an ellipsoid,who mi-axes are proportional to the offt distance,and the implicit quadratic surfaces themlves.It is well k
nown that any regular surface can be locally approximated in the neighborhood of a point p by the expli-cit quadrics of the form r x ;y x ;y ; 1=2 a x 2ϩb y 2 T to the cond order where Ϫa and Ϫb are the principal curvatures at point p .Explicit quadrics include the hyper-bolic paraboloid (ab Ͻ0),elliptic paraboloid (ab Ͼ0and a b ),paraboloid of revolution (a b )and parabolic cylinder (a 0or b 0).Maekawa [26]shows that the lf-interction curves of offts of explicit quadrics are a parabola for both hyperbolic paraboloid and elliptic para-boloid,a straight line for parabolic cylinder and a point for paraboloid of revolution,and their corresponding curves in the xy -plane are an ellip,two straight lines and a circle.The results are applied in [26,28]to detect and trace lf-interction curves of offts of more general parametric surfaces when they form small loops in the parameter domain.Fig.1(a)shows the pre-images of the lf-interc-tion curve of the offt of the bicubic Be
´zier patch in para-meter domain.In this ca the surface is locally approximated as an elliptic paraboloid and therefore the approximated loops projected onto the tangent plane are ellips.And the offt distance is chon such that it is larger than both principal radius of curvatures and hence
desktop是什么T.Maekawa /Computer-Aided Design 31(1999)165–173169
