计算机辅助几何设计中的曲线光顺算法研究
|
摘要
随着在飞机、汽车、船舶以及家用电器等的计算机辅助几何设计(CAGD)中人们对产品外形光顺性要求的提高，曲线曲面的光顺性(fairness)研究现已成为了国内外研究的热点。本文针对目前曲线光顺算法存在的问题，提出了一种采用最小二乘法来拟合曲线型值点列的二阶导数曲线，然后通过两次积分来反求光顺曲线思想的曲线光顺算法，并给出了实际的算例来说明本文算法的优越性。本文的主要研究内容如下：
1．在综述几何造型原理的基础上，回顾几何造型技术的发展趋势和现状，并介绍了曲线曲面光顺技术的意义和发展前景。
2．介绍了光顺的基本原理和方法，在详细分析已有方法优缺点的基础了上，通过实际算例说明了目前曲线光顺算法存在的问题，并提出了解决的思路。
3．提出了一种针对小挠度曲线的逆向曲线光顺算法，该算法直接拟合曲线型值点列的二阶导数曲线，然后通过两次积分来反求出光顺后的曲线，并对该算法的误差分析、效果分析、光顺优化等问题进行了深入探讨。
4．通过对一些实际算例和工程中实际的曲线光顺问题进行的计算，显示了本文提出的曲线光顺算法的有效性和优越性。
As a result of the require of CAGD in airplane, automobile shipping and
electrical appliance etc, fairing of curves and surfaces has become the hot subject in all over the world. This paper presents a new method for fairing of curves based on fitting the derivative of second order of curves. Several practicality examples has been given to show the advantage of this arithmetic. The main results in this paper are as following:
1. Summarize the develop and actuality of CAGD. Introduce the meaning and foreground in fairing of curves and surfaces.
2. Introduce the principle and method in fairing of curves and surfaces. Through the analyze to existing method of fairing of curves and surfaces, we point out the disadvantage in presently method in fairing.
3. Presents a new method for fairing of curves which has a small flexibility based on fitting the derivative of second order of curves. We fit the derivative of second order of curves by a polynomial fitting, then find an indefinite integral of this polynomial to get a approach of curves. Otherwise, we discuss the analyze of the error and the optimize of fairing to this arithmetic.
4. Give several examples which is got from the practicality engineering problem to show the validity and advantage of the arithmetic in this paper.
1．在综述几何造型原理的基础上，回顾几何造型技术的发展趋势和现状，并介绍了曲线曲面光顺技术的意义和发展前景。
2．介绍了光顺的基本原理和方法，在详细分析已有方法优缺点的基础了上，通过实际算例说明了目前曲线光顺算法存在的问题，并提出了解决的思路。
3．提出了一种针对小挠度曲线的逆向曲线光顺算法，该算法直接拟合曲线型值点列的二阶导数曲线，然后通过两次积分来反求出光顺后的曲线，并对该算法的误差分析、效果分析、光顺优化等问题进行了深入探讨。
4．通过对一些实际算例和工程中实际的曲线光顺问题进行的计算，显示了本文提出的曲线光顺算法的有效性和优越性。
As a result of the require of CAGD in airplane, automobile shipping and
electrical appliance etc, fairing of curves and surfaces has become the hot subject in all over the world. This paper presents a new method for fairing of curves based on fitting the derivative of second order of curves. Several practicality examples has been given to show the advantage of this arithmetic. The main results in this paper are as following:
1. Summarize the develop and actuality of CAGD. Introduce the meaning and foreground in fairing of curves and surfaces.
2. Introduce the principle and method in fairing of curves and surfaces. Through the analyze to existing method of fairing of curves and surfaces, we point out the disadvantage in presently method in fairing.
3. Presents a new method for fairing of curves which has a small flexibility based on fitting the derivative of second order of curves. We fit the derivative of second order of curves by a polynomial fitting, then find an indefinite integral of this polynomial to get a approach of curves. Otherwise, we discuss the analyze of the error and the optimize of fairing to this arithmetic.
4. Give several examples which is got from the practicality engineering problem to show the validity and advantage of the arithmetic in this paper.
引文
[1] Barnhill R.E.Riesenfeld R.F. Compurer-aided geometric design,Academic press, 1974.
[2] 唐荣锡CAD／CAM技术，北京航空航天大学出版社，北京，1994。
[3] 蔡青，高光，CAD／CAM系统的可视化，集成化，智能化，网络化，西北工业大学出版社，西安，1996．
[4] 施法中计算机辅助几何设计与非均匀有理B样条(CAGD&NURBS)，北京航空航天大学出版社，北京，1994。
[5] Faux I.D.Pratt M.J.Computational geometry for design and manufacture.Ellis horwood,1979.
[6] 杨彭基 交互式计算机图形显示学，西北工业大学出版社，1987。
[7] 张永曙，刘克轩，蒋大为编著，计算机辅助几何设计的数学方法，西北工业大学出版社，西安，1986。
[8] Ferguson J C.Multivariable curve interpolation.Report D2-22504,The Boeing Co.Seattle,Washington, 1963.
[9] Coons S.Surfaces for computer aided design of space figures.AD663504,1967.
[10] Schoenberg I.On spline function.In shisha O.ed.Inegualities,Academic press,New York,1967.
[11] Bezier P E.Numerical control-Mathematics and applications,Forrest trans.Wiley, London, 1972
[12] Bezier P E.Mathematics and practical possibilities of UNISURF, In Barnhill R E.and Riesenfeld R F.ed.Computer_aided geometric design,Academic press,New York, 1974.
[13] de Boor C.On Calculation with B-splines.J.approx.theory,6,1972,50-62
[14] de Boor C.A practical guide to splines,Springer-Verlag, 1978.
[15] Gordon W J.Riesenfeld R F.B-spline curves and surfaces,In Barnhill R E.and Riesenfeld R F.ed. Computer-aided geometric design,Academic press,New York, 1974.
[16] Boehm W.Inserting new knots into B-spline curve,CAD, 12,4,1980,199-201
[17] Cohen E,,Lyche T.,Riesenfeld R F.Discrete B-spline and cubdivision technique in computer aided geometric design and computer graphics and image processing, 14,1980,87-111
[18] Cohen E.,LYche T.,Schumaker L L.Algorithms for degree raising of splines.ACM Tran. On graphics,4,3,1985,171-181
[19] Prautzsch H.Degree elevation of B-spline curves.CAGD, 1,1984,193
[20] Prautzsch H.,Piper B.A fast algorithm to raise the degree of spline curves. CAGD,8,1991,253-265.
[21] Boehm W.,Prautzsch H. The insertion algorithm,CAD,17,2,1985,58-59.
[22] Boehm W.On the efficiency of knot insertion algorithm, CAD,2,1985,141-143.
[23] Forrest A.R.Curves and surfaces for computer-aided design,Ph.D Thesis,Univ.of Cambridge, 1968
[24] Ball A.CONSURF Part 1. CAD,6,4,243-249,1974.
[25] Ball A.CONSURF Part 2.CAD,7,4,237-242,1975.
[26] Ball A.CONSURF Part 3.CAD,9,1,9-12,1977
[27] 王普，广义二次曲线及其应用，计算机辅助飞机设计与制造专辑(之一)，航空工艺技术编辑部，1979
[28] 苏步青，刘鼎元，计算几何，上海科技出版社，1981
[29] Versprille K.J. Computer Aided Design Applications of rational B-spline approximation form, Ph.D. dissertation,Syracuse,New York Feb, 1975
[30] Piegl L. A geometric investigation of the rational Bezier scheme of computer aided design. Computer in industry, 7, 1986, 401-410
[31] Piegl L. Interactive data interpolation by rational Bezier curves, IEEE CG&A,4,1987,45-58
[32] Piegl L., Tiller W. Curve and surface constructions using rational B-splines,CAD, 19,9,1987,485-498
[33] Piegl L., Tiller W. A menagerie of rational B-spline circles, IEEE CG&A,9,1989,48-56
[34] Piegl L. Key developments in computer-aided geometric design,CAD,21,5,1989,262-274
[35] Piegl L. Modifying the shape of rational B-splines,part 1: curves, CAD,21,8,1989,509-518
[36] Piegl L. Modifying the shape of rational B-splines,part2:surfaces, CAD,21,9,1989,538-546
[37] Piegl L. On NURBS:A Survey, IEEE CG&A,1,1991,55-71.
[38] Tiller W. Rational B-splines for curve and surface representation,IEEE CG&A,9,1983,61-69
[39] Tiller W. Geometric modeling using non-uniform rational B-splines: mathematical techniques,Siggraph turorial notes, ACM,New York, 1986.
[40] Tiller W. Knot removal algorithms for NURBS curves and surfaces, CAD,24,1992
[41] Vergeest S.M. CAD surface data exchange using STEP, CAD, 23, 1, 1991,269-281
[42] 周西军NURBS曲线、曲面造型理论及其应用基础研究，西北工业大学博士学位论文，
西安，1994。
[43] 苏步青 关于五次有理曲线的注记，应用数学学报，No．2,1977，80—89
[44] Forrest A. R. The twisted cubic curve: A computer aided geometric design approach, CAD, 12,4,1980,165-172.
[45] 刘鼎元 射影平面三次参数曲线的相对射影不变量及应用，浙江大学学报，计算几何论文集，1982，125—132。
[46] 刘鼎元有理Bezier曲线，浙江大学学报，计算几何论文集，1982，133—145
[47] Wang C.Y. Shape classification of the parametric cubic curve and parametric B-spline cubic curve, CAD, 13,4,181,199-206
[48] Ye Zhenglin, Wang Jiaye The location of singular and inflection points for the planar cubic B-spline curves, J. of Computer Science &Technology, 1,1992,6-11.
[49] 穆玉杰，叶正麟空间三次有理曲线讨论，高等学校计算数学学报，Vol．18，1986,128—134
[50] 吕伟，粱友栋 有理B样条曲线、曲面的几何包络性，计算数学，Vol．11，1989,85—90
[51] 康宝生有理Bernstein多项式的正性与凸性，纯粹数学与应用数学，No．4，1988，51—56
[52] 康宝生 有理曲线、曲面造型方法的理论及应用研究，西北工业大学博士学位论文，西安，1991
[53] 叶正麟 用影射变换生成形状不变的曲线曲面，计算机学报，1，1992,41-48
[54] 叶正麟 任意函数类的三阶有理曲线，西北大学学报，1，1992,11-16
[55] Barnhill R.E. Boehm W. eds. Surfaces in computer aided geometric design ,1983
[56] Boehm W. Fairn G. Kahmann J. A survey of curve and surface methods in CAGD, CAGD, 1,1984,1-60
[57] Fairn G. Trends in curve and surface design,CAD,21,5,1989,293～296.
[58] Gordon W. J. Blending-function methods of bivariate and multivariate interpolation and approximation ,SIAM J. Num. analysis,8,1,1969,158-177
[59] Gordon W.J. Spline-blended surface interpolation through curve networks, J. of Math and Mechnaics, 18,10,1969,931-952.
[60] Bernhill R E Smooth interpolation over triangles,In,[5]
[61] Sabin M.A.The use of piecewise forms for the numerical representation of shape,Ph..D.thesis,Hungarian Academy of Sciences,Budapest,Hungary, 1976
[63] Manning J.R.Continuity conditions for spline curces,The Computer Joural, 17,2,1974,181-186
[64] TIPS-1 77 version,Hokkaido University, 1978
[65] Okino N.TIPS-1 Technical Information Processing System for Computer Aided Design,Drawing and Manufacturing, Faculty of Ingineering, Hokkaido University, 1976
[66] 马岭，张鲜，朱心雄用偏微分方程构造过渡面，工程图学学报，1，1995，2—8
[67] 马岭，张鲜，朱心雄基于变分原理和B样条的偏微分方程曲面造型，计算机辅助设计与图形学学报(增刊)，8，1996，187—193
[68] Celniker G, Gossard D.Deformable Curve and surface Finite Elements for Free-form Shape Design,Computer Graphics,25,4,1991,257-266
[69] Fang L.,Gossard D. Multidimensional curve fitting to unorganized data points by nonlinear minimization,Computer Aided Design,27,1,1995,48-58
[70] Woodward C.D.Cross-sectional design of B-spline Surfaces, Computer &Graphics, 11,2,1987,193-201
[71] hosaka, m.Theory of curve and surface synthesis and their smooth fitting, Information Prss in Japan, 9 (1969), 60-68
[72] Lott,N.J.and Pullin,D.I.,Method for Fairing B-Spline Surfaces, CA D,Vol.20.No. 10,1988,597-604
[73] 甘屹，齐从谦，陈亚洲，基于遗传算法的曲线曲面光顺，同济大学学报，Vol．30,No．3,2002(同济大学机械工程系，上海 200092)
[74] 忻云龙，双三次样条函数及其在曲面光顺中的应用，复旦学报，自然科学版，1977，63-68
[75] Kjel lander, J.A.P, Smoothting of cubic parametric Spline,CAD,Vol. 15,No.3,1983, 175-179
[76] Kiellander.J.A.P, Smoothing of Cubic Parametric Surface, CAD,Vol, 15,No.5,1983,288-293
[77] Farin,G.,Rein,G.,Sapidis,N.and Worsey,A.J.,Fairing Cubic B-Spline Curves,CAGD,Vol.4,1987,91-103
[78] Sapidis,N.and Farin,G.,Automatic Fairing Algrithm for B-Spline Curves,CAD,Vol 22,No.2,1990,121-129
[79] Pigounakis,K.G.andKaklis,P.D.,Convexity-PreservingFairing,CAD,Vol.28,No.12, 1996,981-994.
[80] 复旦大学数学系，江南造船厂，单根曲线光顺的基样条法，江南造船厂技术资料，
[81] 齐东旭，田自贤，张玉心，冯家斌，曲线拟合的数值磨光方法，数学学报18(1975)，173-184
[82] 董光昌等，船体数学放样—回弹法，科学出版社，1978。
[83] 孙延奎，朱心雄．B样条曲线的小波光顺法[J],工程图学学报，1998，4
[84] 王国瑾 王振武 寿华好 B样条曲面在严格约束状态下的光顺拟合《软件学报》Vol．9,No．9Sep．1998
[85] 刘舸 李柏林 进化规划及在曲线光顺问题中的应用 《机械设计与研究》Vol．18 No．4 Aug，2002 ．
[86] 刘舸 李柏林 一种新的曲线光顺优化模型《西南交通大学学报》Vol．37 No．5 Oct．2002
[87] 刘保嘉 徐宗俊 王巍 王诗杨 曲线及曲面的光顺性研究《机械与电子》2001(5)
[2] 唐荣锡CAD／CAM技术，北京航空航天大学出版社，北京，1994。
[3] 蔡青，高光，CAD／CAM系统的可视化，集成化，智能化，网络化，西北工业大学出版社，西安，1996．
[4] 施法中计算机辅助几何设计与非均匀有理B样条(CAGD&NURBS)，北京航空航天大学出版社，北京，1994。
[5] Faux I.D.Pratt M.J.Computational geometry for design and manufacture.Ellis horwood,1979.
[6] 杨彭基 交互式计算机图形显示学，西北工业大学出版社，1987。
[7] 张永曙，刘克轩，蒋大为编著，计算机辅助几何设计的数学方法，西北工业大学出版社，西安，1986。
[8] Ferguson J C.Multivariable curve interpolation.Report D2-22504,The Boeing Co.Seattle,Washington, 1963.
[9] Coons S.Surfaces for computer aided design of space figures.AD663504,1967.
[10] Schoenberg I.On spline function.In shisha O.ed.Inegualities,Academic press,New York,1967.
[11] Bezier P E.Numerical control-Mathematics and applications,Forrest trans.Wiley, London, 1972
[12] Bezier P E.Mathematics and practical possibilities of UNISURF, In Barnhill R E.and Riesenfeld R F.ed.Computer_aided geometric design,Academic press,New York, 1974.
[13] de Boor C.On Calculation with B-splines.J.approx.theory,6,1972,50-62
[14] de Boor C.A practical guide to splines,Springer-Verlag, 1978.
[15] Gordon W J.Riesenfeld R F.B-spline curves and surfaces,In Barnhill R E.and Riesenfeld R F.ed. Computer-aided geometric design,Academic press,New York, 1974.
[16] Boehm W.Inserting new knots into B-spline curve,CAD, 12,4,1980,199-201
[17] Cohen E,,Lyche T.,Riesenfeld R F.Discrete B-spline and cubdivision technique in computer aided geometric design and computer graphics and image processing, 14,1980,87-111
[18] Cohen E.,LYche T.,Schumaker L L.Algorithms for degree raising of splines.ACM Tran. On graphics,4,3,1985,171-181
[19] Prautzsch H.Degree elevation of B-spline curves.CAGD, 1,1984,193
[20] Prautzsch H.,Piper B.A fast algorithm to raise the degree of spline curves. CAGD,8,1991,253-265.
[21] Boehm W.,Prautzsch H. The insertion algorithm,CAD,17,2,1985,58-59.
[22] Boehm W.On the efficiency of knot insertion algorithm, CAD,2,1985,141-143.
[23] Forrest A.R.Curves and surfaces for computer-aided design,Ph.D Thesis,Univ.of Cambridge, 1968
[24] Ball A.CONSURF Part 1. CAD,6,4,243-249,1974.
[25] Ball A.CONSURF Part 2.CAD,7,4,237-242,1975.
[26] Ball A.CONSURF Part 3.CAD,9,1,9-12,1977
[27] 王普，广义二次曲线及其应用，计算机辅助飞机设计与制造专辑(之一)，航空工艺技术编辑部，1979
[28] 苏步青，刘鼎元，计算几何，上海科技出版社，1981
[29] Versprille K.J. Computer Aided Design Applications of rational B-spline approximation form, Ph.D. dissertation,Syracuse,New York Feb, 1975
[30] Piegl L. A geometric investigation of the rational Bezier scheme of computer aided design. Computer in industry, 7, 1986, 401-410
[31] Piegl L. Interactive data interpolation by rational Bezier curves, IEEE CG&A,4,1987,45-58
[32] Piegl L., Tiller W. Curve and surface constructions using rational B-splines,CAD, 19,9,1987,485-498
[33] Piegl L., Tiller W. A menagerie of rational B-spline circles, IEEE CG&A,9,1989,48-56
[34] Piegl L. Key developments in computer-aided geometric design,CAD,21,5,1989,262-274
[35] Piegl L. Modifying the shape of rational B-splines,part 1: curves, CAD,21,8,1989,509-518
[36] Piegl L. Modifying the shape of rational B-splines,part2:surfaces, CAD,21,9,1989,538-546
[37] Piegl L. On NURBS:A Survey, IEEE CG&A,1,1991,55-71.
[38] Tiller W. Rational B-splines for curve and surface representation,IEEE CG&A,9,1983,61-69
[39] Tiller W. Geometric modeling using non-uniform rational B-splines: mathematical techniques,Siggraph turorial notes, ACM,New York, 1986.
[40] Tiller W. Knot removal algorithms for NURBS curves and surfaces, CAD,24,1992
[41] Vergeest S.M. CAD surface data exchange using STEP, CAD, 23, 1, 1991,269-281
[42] 周西军NURBS曲线、曲面造型理论及其应用基础研究，西北工业大学博士学位论文，
西安，1994。
[43] 苏步青 关于五次有理曲线的注记，应用数学学报，No．2,1977，80—89
[44] Forrest A. R. The twisted cubic curve: A computer aided geometric design approach, CAD, 12,4,1980,165-172.
[45] 刘鼎元 射影平面三次参数曲线的相对射影不变量及应用，浙江大学学报，计算几何论文集，1982，125—132。
[46] 刘鼎元有理Bezier曲线，浙江大学学报，计算几何论文集，1982，133—145
[47] Wang C.Y. Shape classification of the parametric cubic curve and parametric B-spline cubic curve, CAD, 13,4,181,199-206
[48] Ye Zhenglin, Wang Jiaye The location of singular and inflection points for the planar cubic B-spline curves, J. of Computer Science &Technology, 1,1992,6-11.
[49] 穆玉杰，叶正麟空间三次有理曲线讨论，高等学校计算数学学报，Vol．18，1986,128—134
[50] 吕伟，粱友栋 有理B样条曲线、曲面的几何包络性，计算数学，Vol．11，1989,85—90
[51] 康宝生有理Bernstein多项式的正性与凸性，纯粹数学与应用数学，No．4，1988，51—56
[52] 康宝生 有理曲线、曲面造型方法的理论及应用研究，西北工业大学博士学位论文，西安，1991
[53] 叶正麟 用影射变换生成形状不变的曲线曲面，计算机学报，1，1992,41-48
[54] 叶正麟 任意函数类的三阶有理曲线，西北大学学报，1，1992,11-16
[55] Barnhill R.E. Boehm W. eds. Surfaces in computer aided geometric design ,1983
[56] Boehm W. Fairn G. Kahmann J. A survey of curve and surface methods in CAGD, CAGD, 1,1984,1-60
[57] Fairn G. Trends in curve and surface design,CAD,21,5,1989,293～296.
[58] Gordon W. J. Blending-function methods of bivariate and multivariate interpolation and approximation ,SIAM J. Num. analysis,8,1,1969,158-177
[59] Gordon W.J. Spline-blended surface interpolation through curve networks, J. of Math and Mechnaics, 18,10,1969,931-952.
[60] Bernhill R E Smooth interpolation over triangles,In,[5]
[61] Sabin M.A.The use of piecewise forms for the numerical representation of shape,Ph..D.thesis,Hungarian Academy of Sciences,Budapest,Hungary, 1976
[63] Manning J.R.Continuity conditions for spline curces,The Computer Joural, 17,2,1974,181-186
[64] TIPS-1 77 version,Hokkaido University, 1978
[65] Okino N.TIPS-1 Technical Information Processing System for Computer Aided Design,Drawing and Manufacturing, Faculty of Ingineering, Hokkaido University, 1976
[66] 马岭，张鲜，朱心雄用偏微分方程构造过渡面，工程图学学报，1，1995，2—8
[67] 马岭，张鲜，朱心雄基于变分原理和B样条的偏微分方程曲面造型，计算机辅助设计与图形学学报(增刊)，8，1996，187—193
[68] Celniker G, Gossard D.Deformable Curve and surface Finite Elements for Free-form Shape Design,Computer Graphics,25,4,1991,257-266
[69] Fang L.,Gossard D. Multidimensional curve fitting to unorganized data points by nonlinear minimization,Computer Aided Design,27,1,1995,48-58
[70] Woodward C.D.Cross-sectional design of B-spline Surfaces, Computer &Graphics, 11,2,1987,193-201
[71] hosaka, m.Theory of curve and surface synthesis and their smooth fitting, Information Prss in Japan, 9 (1969), 60-68
[72] Lott,N.J.and Pullin,D.I.,Method for Fairing B-Spline Surfaces, CA D,Vol.20.No. 10,1988,597-604
[73] 甘屹，齐从谦，陈亚洲，基于遗传算法的曲线曲面光顺，同济大学学报，Vol．30,No．3,2002(同济大学机械工程系，上海 200092)
[74] 忻云龙，双三次样条函数及其在曲面光顺中的应用，复旦学报，自然科学版，1977，63-68
[75] Kjel lander, J.A.P, Smoothting of cubic parametric Spline,CAD,Vol. 15,No.3,1983, 175-179
[76] Kiellander.J.A.P, Smoothing of Cubic Parametric Surface, CAD,Vol, 15,No.5,1983,288-293
[77] Farin,G.,Rein,G.,Sapidis,N.and Worsey,A.J.,Fairing Cubic B-Spline Curves,CAGD,Vol.4,1987,91-103
[78] Sapidis,N.and Farin,G.,Automatic Fairing Algrithm for B-Spline Curves,CAD,Vol 22,No.2,1990,121-129
[79] Pigounakis,K.G.andKaklis,P.D.,Convexity-PreservingFairing,CAD,Vol.28,No.12, 1996,981-994.
[80] 复旦大学数学系，江南造船厂，单根曲线光顺的基样条法，江南造船厂技术资料，
[81] 齐东旭，田自贤，张玉心，冯家斌，曲线拟合的数值磨光方法，数学学报18(1975)，173-184
[82] 董光昌等，船体数学放样—回弹法，科学出版社，1978。
[83] 孙延奎，朱心雄．B样条曲线的小波光顺法[J],工程图学学报，1998，4
[84] 王国瑾 王振武 寿华好 B样条曲面在严格约束状态下的光顺拟合《软件学报》Vol．9,No．9Sep．1998
[85] 刘舸 李柏林 进化规划及在曲线光顺问题中的应用 《机械设计与研究》Vol．18 No．4 Aug，2002 ．
[86] 刘舸 李柏林 一种新的曲线光顺优化模型《西南交通大学学报》Vol．37 No．5 Oct．2002
[87] 刘保嘉 徐宗俊 王巍 王诗杨 曲线及曲面的光顺性研究《机械与电子》2001(5)