基于系数矩阵的NURBS曲线细分及其应用
|
摘要
细分方法是曲线曲面几何造型中的常用方法,它可以克服参数表示方法的局限性,并具有从离散到离散、规则简单、易于修改和极限曲线曲面良好的光滑性等优点,广泛应用于三维几何造型、计算机动画和多分辨率分析等领域。NURBS方法可以用统一的数学形式精确地表示二次曲线曲面,是定义工业产品几何形状的唯一数学描述方法,因此解决NURBS曲线曲面细分问题对几何造型有着重要的意义。为了满足实际几何造型中对于精度的要求,分析NURBS细分曲线曲面误差也显得极为重要。本文在讨论NURBS曲线系数矩阵基础上,研究了NURBS曲线细分和二次曲面细分,并应用NURBS曲线点投影的裁剪圆算法分析了NURBS细分曲线的误差。取得了以下主要研究成果:
(1)利用NURBS曲线矩阵形式中的系数矩阵,得到了NURBS曲线的细分表示。并利用该细分表示,实现了具有代表性的二次NURBS曲线2-尺度细分、二次NURBS曲线3-尺度细分、三次NURBS曲线2-尺度细分,进一步推广至高次NURBS曲线的多尺度细分。
(2)讨论了NURBS曲线点投影问题,研究了B样条曲线乘积和点投影的裁剪圆算法,应用裁剪圆算法分析了NURBS细分曲线的误差,并给出了NURBS曲线每次细分后控制多边形与极限曲线误差的计算实例。
(3)通过圆和椭圆的九顶点NURBS表示,结合旋转曲面特征,将NURBS曲线细分应用到二次曲面细分,实现了单叶双曲面、双叶双曲面、椭圆抛物面和三轴椭球等曲面的细分。并采用MATLAB R2009a搭建了“NURBS曲线曲面细分”软件平台,在文中所用到的图例都由该平台计算生成。
Subdivision schemes have important applications in curves and surfaces modeling and engineering designing. Applying subdivision schemes to geometric modeling may overcome the limitations of parametric schemes. Subdivision is efficient to design, represent and approach arbitrarily topological curves and surfaces. Because subdivision schemes have the advantages of discrete-to-discrete, simple rules, efficiency and convenient modification, which have already been widely used in 3D geometric modeling, computer animation and multiresolution analysis. NURBS may represent curves and surfaces accurately by uniform algebraic expression. Therefore, it is important to solve the problem of NURBS curves and surfaces subdivision for geometric modeling. For the accuracy of engineering, analyzing the error of NURBS curves subdivision is needed. This thesis studies subdivision schemes and applications of NURBS curves based on coefficient matrix, and point projection clipping circular algorithm is used to analyze the error of NURBS curves subdivision. The main results are as follow:
(1) It studies the subdivision expression of NURBS curves based on NURBS coefficient matrix, with which 2-band subdivision scheme of quadratic NURBS curves, 3-band subdivision scheme of quadratic NURBS curves and 2-band subdivision scheme of cubic NURBS curves are obtained. Consequently, it can subdivide higher degree NURBS curves with multi-band.
(2) It discusses NURBS point projection, and researches B-spline curves product and clipping circular algorithm in detail. Analyzing the error of NURBS curves subdivision with clipping circular algorithm of point projection and examples are given.
(3) Through the nine vertex representation of circle and ellipse, combined with the characteristics of rotary surfaces, it obtains quadratic NURBS surfaces subdivision based on NURBS curves subdivision, and achieves subdivision of hyperboloid of one sheet, hyperboloid of two sheets, elliptic paraboloid and triaxial ellipsoid and so on.‘NURBS curves and surfaces subdivision’software platform is constructed by MATLAB R2009a, examples used in the thesis are generated by this software platform.
(1)利用NURBS曲线矩阵形式中的系数矩阵,得到了NURBS曲线的细分表示。并利用该细分表示,实现了具有代表性的二次NURBS曲线2-尺度细分、二次NURBS曲线3-尺度细分、三次NURBS曲线2-尺度细分,进一步推广至高次NURBS曲线的多尺度细分。
(2)讨论了NURBS曲线点投影问题,研究了B样条曲线乘积和点投影的裁剪圆算法,应用裁剪圆算法分析了NURBS细分曲线的误差,并给出了NURBS曲线每次细分后控制多边形与极限曲线误差的计算实例。
(3)通过圆和椭圆的九顶点NURBS表示,结合旋转曲面特征,将NURBS曲线细分应用到二次曲面细分,实现了单叶双曲面、双叶双曲面、椭圆抛物面和三轴椭球等曲面的细分。并采用MATLAB R2009a搭建了“NURBS曲线曲面细分”软件平台,在文中所用到的图例都由该平台计算生成。
Subdivision schemes have important applications in curves and surfaces modeling and engineering designing. Applying subdivision schemes to geometric modeling may overcome the limitations of parametric schemes. Subdivision is efficient to design, represent and approach arbitrarily topological curves and surfaces. Because subdivision schemes have the advantages of discrete-to-discrete, simple rules, efficiency and convenient modification, which have already been widely used in 3D geometric modeling, computer animation and multiresolution analysis. NURBS may represent curves and surfaces accurately by uniform algebraic expression. Therefore, it is important to solve the problem of NURBS curves and surfaces subdivision for geometric modeling. For the accuracy of engineering, analyzing the error of NURBS curves subdivision is needed. This thesis studies subdivision schemes and applications of NURBS curves based on coefficient matrix, and point projection clipping circular algorithm is used to analyze the error of NURBS curves subdivision. The main results are as follow:
(1) It studies the subdivision expression of NURBS curves based on NURBS coefficient matrix, with which 2-band subdivision scheme of quadratic NURBS curves, 3-band subdivision scheme of quadratic NURBS curves and 2-band subdivision scheme of cubic NURBS curves are obtained. Consequently, it can subdivide higher degree NURBS curves with multi-band.
(2) It discusses NURBS point projection, and researches B-spline curves product and clipping circular algorithm in detail. Analyzing the error of NURBS curves subdivision with clipping circular algorithm of point projection and examples are given.
(3) Through the nine vertex representation of circle and ellipse, combined with the characteristics of rotary surfaces, it obtains quadratic NURBS surfaces subdivision based on NURBS curves subdivision, and achieves subdivision of hyperboloid of one sheet, hyperboloid of two sheets, elliptic paraboloid and triaxial ellipsoid and so on.‘NURBS curves and surfaces subdivision’software platform is constructed by MATLAB R2009a, examples used in the thesis are generated by this software platform.
引文
[1]Fergusion J.C. Multivariable curve interpolation[R]. The Boeing Co. Seattle, Washington, 1963.
[2]Fergusion J.C. Multivariable curve interpolation[J]. Journal of ACM, 1964, 2: 221-228.
[3]Coons S.A. Surfaces for computer aided design of space figures[R]. MIT, 1964, project MAC-TR-225.
[4]Schoenberg I.J. Contributions to the problem of approximation of equidistant data by analytic functions[J]. Quart. Appl. Math. 1946, 4: 45-99.
[5]Bézier P.E. Numerical control-mathematics and applications[M]. Forrest trans. Wiley, London, 1972.
[6]de Boor C. On calculating with B-Splines[J]. Journal of Approximation Theory, 1972, 6: 50-62.
[7]Gordon W.J., Riesenfeld R.F. Bernstein Bézier methods for the computer aided geometric design of free-form curves and surfaces[J], Journal of ACM, 1974, 21: 293-310.
[8]Versprille K.J. Computer aided design applications of the rational B-spline approximation form [D]. Syracuse University, 1975.
[9]Piegl L. Curve fitting algorithm for rough cutting[J]. Computer Aided Design, 1986, 18: 79-82.
[10]Ti11er W. Rational B-splines for curve and surface representation[J]. IEEE. Computer Graphics and its Application, 1983, 3: 61-69.
[11]Piegl L., Ti11er W. Curve and surface construction using B-splines[J]. Computer Aided Design, 1987, 19: 487-498.
[12]Hu S., Wallner J. A second order algorithm for orthogonal projection onto curves and surfaces[J]. Computer Aided Geometric Design, 2005, 22(3): 251-260.
[13]Ma Y.L., Hewitt W.T. Point inversion and projection for NURBS curve and surface: Control polygon approach[J]. Computer Aided Geometric Design, 2003, 20(2): 79-99.
[14]Edelsbrunner H. On computing the extreme distances between two convex polygons[R]. Graz University of Technology, 1982, 96.
[15]Chin F., Wang C.A. Optimal algorithms for the intersection and the minimum distance problems between planar polygons[J]. IEEE Transactions on Computational, 1983, C-32(12), 1203-1207.
[16]Johnson D.E., Cohen E. A framework for efficient minimum distance computation[J]. IEEE International Conference Robotics & Automation, 1998, 3678-3684.
[17]Mortenson M.E. Geometric modeling[M]. New York, 1985, 305-317.
[18]Limaiem A., Trochu F. Geometric algorithms for the intersection of curves and surfaces[J]. Comput. Graph., 1995, 19(3): 391-403.
[19]Lin M., Manocha D. Fast interference detection between geometric models[J].The Visual Computer, 1995, 541-561.
[20]Piegl L., Tiller W. Parameterization for surface fitting in reverse engineering[J]. Computer Aided Design, 2001, 33(8): 593-603.
[21]Selimovic I. Improved algorithms for the projection of points on NURBS curves and surfaces[J]. Computer Aided Geometric Design, 2006, 23(5): 439-445.
[22]Chen X.D., et al. Computing the minimum distance between a point and a NURBS curve[J]. Computer Aided Design, 2008, 40: 1051-1054.
[23]陈小雕等. B样条曲面方向投影问题的几何计算方法[J].计算机辅助设计与图形学学报, 2009, 21(6): 721-724.
[24]Piegl L., Tiller W. The NURBS book[M]. Springer-Verlag, New York, 1997.
[25]Rham G.de. Sur une conrbe plane[J]. Math. Pures. Appl, 1956, 35: 25-42.
[26]Chaikin G.M. An algorithm for high speed curve generation[J]. Computer Graphics and Image Processing, 1971, 3(4): 346-349.
[27]Riesenfeld R.F. Chaikin’s algorithm[J]. IEEE Computer Graphics and Application, 1975, 4: 304-310.
[28]Lane J.M., Riesenfeld R.F. A theoretical development for the computer generation and display of piecewise polynomial surface[J]. Pattern Anal. Mach. Intelling, 1980, 2: 35-45.
[29]Doo D., Sabin M. Behaviour of recursive division surfaces near extraordinary points[J]. Computer Aided Design, 1978, 10(6): 356-360.
[30]Catmull E., Clark J. Recursively generated B-spline surfaces on arbitray topological meshes[J]. Computer Aided Design, 1978, 10(6): 345-352.
[31]Dyn N., Levin D., Gregory J.A. A 4-point interpolatory subdivision scheme for curve design[J]. Computer Aided Geometric Design, 1987, 4(4): 257-268.
[32]Dyn N., Gregory J.A., Levin D. A butterfly subdivision scheme for surface interpolation with tension control[J]. ACM Transactions on Graphics, 1990, 9: 160-169.
[33]Kobbelt L. 3 -subdivision[J]. Computer Graphics Proceedings. ACM SIGGRAPH, 2000, 103-112.
[34]李桂清.细分模式构造及其拟合技术[R].浙江:浙江大学, 2003.
[35]Denis Z., Peter S. Subdivisionfor modeling and animation[J]. SIGGRAPH, 2000.
[36]王学福,孙家广,秦开怀. NURBS的符号矩阵表示及其应用[J].计算机学报, 1993, 16(1): 29-34.
[37]潘日晶. NURBS曲线曲面的显式矩阵表示及其算法[J].计算机学报, 2001, 24(4): 358-366.
[38]Liu L.G., Wang G.J. Explicit matrix representation for NURBS curves and surfaces[J]. Computer Aided Geometric Design, 2002, 19(6): 409-419.
[39]Han L.W., Wu T.R. Subdivision generation for the blending of quadratic surfaces[J]. Journal of Information & Computational Science, 2004, 1: 35-40.
[40]McDonnell K.T., Chang Y.S., Qin H. Digital sculpture: a subdivision-based approach to interactive implicit surface modeling[J]. Graphical Models, 2005, 67: 347-369.
[41]丁永胜,蒋大为等. NURBS细分曲线算法[J].计算机工程与应用, 2005, 16: 74-76.
[42]韩力文,周蕴时. NURBS曲线与曲面的细分算法[J].计算技术与自动化, 2002, 21(3): 20-22.
[43]习海燕.基于矩阵表示的NURBS曲线曲面细分[D].石家庄:河北师范大学, 2009.
[44]朱心雄.自由曲线曲面造型技术[M].科学出版社, 2000.
[45]Chen X.D., Su H., Yong J.H., Paul J.C., Sun J.G. A counterexample on point inversion and projection for NURBS curve[J]. Computer Aided Geometric Design 2007, 24: 302.
[46]Selimovic I. Improved algorithms for the projection of points on NURBS curves and surfaces[J]. Computer Aided Geometric Design 2006, 23(5): 439-45.
[47]Morken K. Some identities for products and degree raising of splines[J]. Constructive Approximation 1991, 7(2): 195-208.
[48]Sederberg T., Zheng J., Swell D. Non-uniform recursive subdivision surfaces[J]. Computer Graphics, 1998, 387-394.
[49]Eugenia M., Alberto S. Surface subdivision for generating super-quadrics[J]. The Visual Computer, 1998, 14: 1-17.
[50]Géraldine M., Warren J. A subdivision scheme for surfaces of revolution[J]. Computer Aided Geometric Design, 2001, 18: 483-502.
[51]魏国富.细分方法及其应用[D].合肥:中国科学技术大学,2002.
[52]康宝生,马翔,周儒荣.旋转曲面和球面的NURBS表示[J].南京航空航天大学学报, 1994, 26(1): 80-87.
[53]谌炎辉,周良德.二次曲面的NURBS表示及控制顶点和权因子的计算[J].湘潭大学自然科学学报, 2005, 27(2): 150-154.
[2]Fergusion J.C. Multivariable curve interpolation[J]. Journal of ACM, 1964, 2: 221-228.
[3]Coons S.A. Surfaces for computer aided design of space figures[R]. MIT, 1964, project MAC-TR-225.
[4]Schoenberg I.J. Contributions to the problem of approximation of equidistant data by analytic functions[J]. Quart. Appl. Math. 1946, 4: 45-99.
[5]Bézier P.E. Numerical control-mathematics and applications[M]. Forrest trans. Wiley, London, 1972.
[6]de Boor C. On calculating with B-Splines[J]. Journal of Approximation Theory, 1972, 6: 50-62.
[7]Gordon W.J., Riesenfeld R.F. Bernstein Bézier methods for the computer aided geometric design of free-form curves and surfaces[J], Journal of ACM, 1974, 21: 293-310.
[8]Versprille K.J. Computer aided design applications of the rational B-spline approximation form [D]. Syracuse University, 1975.
[9]Piegl L. Curve fitting algorithm for rough cutting[J]. Computer Aided Design, 1986, 18: 79-82.
[10]Ti11er W. Rational B-splines for curve and surface representation[J]. IEEE. Computer Graphics and its Application, 1983, 3: 61-69.
[11]Piegl L., Ti11er W. Curve and surface construction using B-splines[J]. Computer Aided Design, 1987, 19: 487-498.
[12]Hu S., Wallner J. A second order algorithm for orthogonal projection onto curves and surfaces[J]. Computer Aided Geometric Design, 2005, 22(3): 251-260.
[13]Ma Y.L., Hewitt W.T. Point inversion and projection for NURBS curve and surface: Control polygon approach[J]. Computer Aided Geometric Design, 2003, 20(2): 79-99.
[14]Edelsbrunner H. On computing the extreme distances between two convex polygons[R]. Graz University of Technology, 1982, 96.
[15]Chin F., Wang C.A. Optimal algorithms for the intersection and the minimum distance problems between planar polygons[J]. IEEE Transactions on Computational, 1983, C-32(12), 1203-1207.
[16]Johnson D.E., Cohen E. A framework for efficient minimum distance computation[J]. IEEE International Conference Robotics & Automation, 1998, 3678-3684.
[17]Mortenson M.E. Geometric modeling[M]. New York, 1985, 305-317.
[18]Limaiem A., Trochu F. Geometric algorithms for the intersection of curves and surfaces[J]. Comput. Graph., 1995, 19(3): 391-403.
[19]Lin M., Manocha D. Fast interference detection between geometric models[J].The Visual Computer, 1995, 541-561.
[20]Piegl L., Tiller W. Parameterization for surface fitting in reverse engineering[J]. Computer Aided Design, 2001, 33(8): 593-603.
[21]Selimovic I. Improved algorithms for the projection of points on NURBS curves and surfaces[J]. Computer Aided Geometric Design, 2006, 23(5): 439-445.
[22]Chen X.D., et al. Computing the minimum distance between a point and a NURBS curve[J]. Computer Aided Design, 2008, 40: 1051-1054.
[23]陈小雕等. B样条曲面方向投影问题的几何计算方法[J].计算机辅助设计与图形学学报, 2009, 21(6): 721-724.
[24]Piegl L., Tiller W. The NURBS book[M]. Springer-Verlag, New York, 1997.
[25]Rham G.de. Sur une conrbe plane[J]. Math. Pures. Appl, 1956, 35: 25-42.
[26]Chaikin G.M. An algorithm for high speed curve generation[J]. Computer Graphics and Image Processing, 1971, 3(4): 346-349.
[27]Riesenfeld R.F. Chaikin’s algorithm[J]. IEEE Computer Graphics and Application, 1975, 4: 304-310.
[28]Lane J.M., Riesenfeld R.F. A theoretical development for the computer generation and display of piecewise polynomial surface[J]. Pattern Anal. Mach. Intelling, 1980, 2: 35-45.
[29]Doo D., Sabin M. Behaviour of recursive division surfaces near extraordinary points[J]. Computer Aided Design, 1978, 10(6): 356-360.
[30]Catmull E., Clark J. Recursively generated B-spline surfaces on arbitray topological meshes[J]. Computer Aided Design, 1978, 10(6): 345-352.
[31]Dyn N., Levin D., Gregory J.A. A 4-point interpolatory subdivision scheme for curve design[J]. Computer Aided Geometric Design, 1987, 4(4): 257-268.
[32]Dyn N., Gregory J.A., Levin D. A butterfly subdivision scheme for surface interpolation with tension control[J]. ACM Transactions on Graphics, 1990, 9: 160-169.
[33]Kobbelt L. 3 -subdivision[J]. Computer Graphics Proceedings. ACM SIGGRAPH, 2000, 103-112.
[34]李桂清.细分模式构造及其拟合技术[R].浙江:浙江大学, 2003.
[35]Denis Z., Peter S. Subdivisionfor modeling and animation[J]. SIGGRAPH, 2000.
[36]王学福,孙家广,秦开怀. NURBS的符号矩阵表示及其应用[J].计算机学报, 1993, 16(1): 29-34.
[37]潘日晶. NURBS曲线曲面的显式矩阵表示及其算法[J].计算机学报, 2001, 24(4): 358-366.
[38]Liu L.G., Wang G.J. Explicit matrix representation for NURBS curves and surfaces[J]. Computer Aided Geometric Design, 2002, 19(6): 409-419.
[39]Han L.W., Wu T.R. Subdivision generation for the blending of quadratic surfaces[J]. Journal of Information & Computational Science, 2004, 1: 35-40.
[40]McDonnell K.T., Chang Y.S., Qin H. Digital sculpture: a subdivision-based approach to interactive implicit surface modeling[J]. Graphical Models, 2005, 67: 347-369.
[41]丁永胜,蒋大为等. NURBS细分曲线算法[J].计算机工程与应用, 2005, 16: 74-76.
[42]韩力文,周蕴时. NURBS曲线与曲面的细分算法[J].计算技术与自动化, 2002, 21(3): 20-22.
[43]习海燕.基于矩阵表示的NURBS曲线曲面细分[D].石家庄:河北师范大学, 2009.
[44]朱心雄.自由曲线曲面造型技术[M].科学出版社, 2000.
[45]Chen X.D., Su H., Yong J.H., Paul J.C., Sun J.G. A counterexample on point inversion and projection for NURBS curve[J]. Computer Aided Geometric Design 2007, 24: 302.
[46]Selimovic I. Improved algorithms for the projection of points on NURBS curves and surfaces[J]. Computer Aided Geometric Design 2006, 23(5): 439-45.
[47]Morken K. Some identities for products and degree raising of splines[J]. Constructive Approximation 1991, 7(2): 195-208.
[48]Sederberg T., Zheng J., Swell D. Non-uniform recursive subdivision surfaces[J]. Computer Graphics, 1998, 387-394.
[49]Eugenia M., Alberto S. Surface subdivision for generating super-quadrics[J]. The Visual Computer, 1998, 14: 1-17.
[50]Géraldine M., Warren J. A subdivision scheme for surfaces of revolution[J]. Computer Aided Geometric Design, 2001, 18: 483-502.
[51]魏国富.细分方法及其应用[D].合肥:中国科学技术大学,2002.
[52]康宝生,马翔,周儒荣.旋转曲面和球面的NURBS表示[J].南京航空航天大学学报, 1994, 26(1): 80-87.
[53]谌炎辉,周良德.二次曲面的NURBS表示及控制顶点和权因子的计算[J].湘潭大学自然科学学报, 2005, 27(2): 150-154.