圆弧曲线段的有理三次DP及广义Ball表示
|
摘要
本文讨论了CAGD领域中的两类重要的曲线——广义Ball曲线和有理DP曲线表示圆弧曲线的问题，主要对有理三次DP曲线表示圆弧曲线段以及三次Wang-Ball曲线，三次Said-Ball曲线表示圆弧曲线段的问题进行了研究。这些曲线都具有求值及升降阶运算的快速性质，除三次Wang-Ball曲线外还具有保形性。本文的目的是拓广这些曲线的表示范围，使得所推导的结果可以用于鉴别一条已知的曲线是否是圆弧曲线，或者由给定的圆弧设计一条曲线来表示它。在系统地论述CAGD中此两类曲线曲面的内容、特点、已有的研究成果的基础上，就以下这些方面给出研究成果：
1．几类曲线求值的计算复杂度分析
我们首先给出有理n次DP曲线、n次Wang-Ball曲线、n次Said-Ball曲线与有理n次Bézier曲线求值的计算复杂度分析与比较．这表明引入以上曲线，研究圆弧用以上曲线表示的条件、拓广这些曲线的表示范围是十分必要的。
2．给出了三次Wang-Ball曲线表示圆弧曲线的充要条件。
运用两种不同的方法来分别推导出两组充要条件，第一种方法是按圆弧的性质，运用了解析几何及线性代数原理；第二种方法利用了Wang-Ball曲线向有理Bézier曲线的转换原理及后者表示圆弧的充要条件。最后验证这两组充要条件是等价的。
3．给出了有理三次DP-Ball曲线表示圆弧曲线的充要条件。
运用与三次Wang-Ball曲线类似的方法，同样给出两种方法的证明，并且相互验证。
4．几何作图法及实例检验
我们分别给出了三次Wang-Ball曲线表示圆弧曲线和有理三次DP曲线表示圆弧曲线的几何作图法，并以此作为设计圆弧曲线的基础，给出了不同圆心角度的一些例子。此外，我们还利用三次Wang-Ball曲线表示圆弧曲线和有理三次DP曲线表示圆弧曲线的充要条件来鉴别一条三次Wang-Ball曲线或有理三次DP曲线是否表示圆弧曲线，并给出了例子。
This thesis discusses two types of curves——generalized Ball curves and rational DP curves which are of great importance in CAGD researches, and makes a study in the representation of arc by rational cubic Wall-Ball curves, rational cubic Said-Ball curves and rational cubic DP curves. These curves have shown greatly efficient effects on evaluating, degree elevation and degree reduction, and they are shape preserving except the rational cubic Wall-Ball curves. The purpose of this thesis is to exert their range of representation, and use the conclusion to identify if a curve is arc and to design a curve to represent arc. Based on a systematic discussion on the content, characteristics and the up-to-now accomplishments of these curves in CAGD, we present our researches in four ways as follows:
1. The time complexity analysis for the evaluating algorithms of these curves
At first, we provide the time complexity analysis and compare for the evaluating algorithms of rational n degrees DP curves, n degrees Wall-Ball curves, n degrees Said-Ball curves and rational n degrees Bézier curves. This indicates that it's necessary to study the conditions for these curves representation of arc and exert their range of representation.
2. The rational cubic Wall-Ball curves representation of arc
As a kind of generalized Ball curves, Wang-Ball curves have shown greatly efficient effects on evaluating parametric curves, degree elevation. In order to exert its effect on geometric design, we give the sufficient and necessary conditions of the rational cubic Wall-Ball curves representation of arc.
This thesis use two different method to obtain two groups of the sufficient and necessary conditions, one method is to use the properties of arc and use the theories of analytic geometry and linear algebra, and the other method is to transform the rational cubic Wall-Ball curves to the rational cubic Bézier curves and use the conditions for the rational cubic Bézier curves representation of arc. At last we prove these two groups of the sufficient and necessary conditions are equivalent.
3. The rational cubic DP curves representation of arc
Rational DP curves not only have an evaluation algorithm of linear complexity, but also are composed by normalized totally positive (NTP) bases., we give the sufficient and necessary conditions of the rational cubic DP curves representation of arc.
We use the method as Wall-Ball curves', also obtain two kinds of conditions, and we prove they are equivalent.
4. geometric construction and some examples
We obtain the geometric construction for the representation of arc by rational cubic Wall-Ball curves and rational cubic DP curves, and based on the geometric construction, we give some examples for designing arc of different central angles. We also use the sufficient and necessary conditions for the rational cubic Wall-Ball curves representation of arc and the rational cubic DP curves representation of arc to identify if a rational cubic DP curve or a rational cubic Wall-Ball curve is arc, and give some examples.
1．几类曲线求值的计算复杂度分析
我们首先给出有理n次DP曲线、n次Wang-Ball曲线、n次Said-Ball曲线与有理n次Bézier曲线求值的计算复杂度分析与比较．这表明引入以上曲线，研究圆弧用以上曲线表示的条件、拓广这些曲线的表示范围是十分必要的。
2．给出了三次Wang-Ball曲线表示圆弧曲线的充要条件。
运用两种不同的方法来分别推导出两组充要条件，第一种方法是按圆弧的性质，运用了解析几何及线性代数原理；第二种方法利用了Wang-Ball曲线向有理Bézier曲线的转换原理及后者表示圆弧的充要条件。最后验证这两组充要条件是等价的。
3．给出了有理三次DP-Ball曲线表示圆弧曲线的充要条件。
运用与三次Wang-Ball曲线类似的方法，同样给出两种方法的证明，并且相互验证。
4．几何作图法及实例检验
我们分别给出了三次Wang-Ball曲线表示圆弧曲线和有理三次DP曲线表示圆弧曲线的几何作图法，并以此作为设计圆弧曲线的基础，给出了不同圆心角度的一些例子。此外，我们还利用三次Wang-Ball曲线表示圆弧曲线和有理三次DP曲线表示圆弧曲线的充要条件来鉴别一条三次Wang-Ball曲线或有理三次DP曲线是否表示圆弧曲线，并给出了例子。
This thesis discusses two types of curves——generalized Ball curves and rational DP curves which are of great importance in CAGD researches, and makes a study in the representation of arc by rational cubic Wall-Ball curves, rational cubic Said-Ball curves and rational cubic DP curves. These curves have shown greatly efficient effects on evaluating, degree elevation and degree reduction, and they are shape preserving except the rational cubic Wall-Ball curves. The purpose of this thesis is to exert their range of representation, and use the conclusion to identify if a curve is arc and to design a curve to represent arc. Based on a systematic discussion on the content, characteristics and the up-to-now accomplishments of these curves in CAGD, we present our researches in four ways as follows:
1. The time complexity analysis for the evaluating algorithms of these curves
At first, we provide the time complexity analysis and compare for the evaluating algorithms of rational n degrees DP curves, n degrees Wall-Ball curves, n degrees Said-Ball curves and rational n degrees Bézier curves. This indicates that it's necessary to study the conditions for these curves representation of arc and exert their range of representation.
2. The rational cubic Wall-Ball curves representation of arc
As a kind of generalized Ball curves, Wang-Ball curves have shown greatly efficient effects on evaluating parametric curves, degree elevation. In order to exert its effect on geometric design, we give the sufficient and necessary conditions of the rational cubic Wall-Ball curves representation of arc.
This thesis use two different method to obtain two groups of the sufficient and necessary conditions, one method is to use the properties of arc and use the theories of analytic geometry and linear algebra, and the other method is to transform the rational cubic Wall-Ball curves to the rational cubic Bézier curves and use the conditions for the rational cubic Bézier curves representation of arc. At last we prove these two groups of the sufficient and necessary conditions are equivalent.
3. The rational cubic DP curves representation of arc
Rational DP curves not only have an evaluation algorithm of linear complexity, but also are composed by normalized totally positive (NTP) bases., we give the sufficient and necessary conditions of the rational cubic DP curves representation of arc.
We use the method as Wall-Ball curves', also obtain two kinds of conditions, and we prove they are equivalent.
4. geometric construction and some examples
We obtain the geometric construction for the representation of arc by rational cubic Wall-Ball curves and rational cubic DP curves, and based on the geometric construction, we give some examples for designing arc of different central angles. We also use the sufficient and necessary conditions for the rational cubic Wall-Ball curves representation of arc and the rational cubic DP curves representation of arc to identify if a rational cubic DP curve or a rational cubic Wall-Ball curve is arc, and give some examples.
引文
[BR74] Barnhill R.E., Riesenfeld R.F. Computer-aided Geometric Design, academic press, New York, 1974.
[Fer63] Ferguson, J.C., Multivariable curve interpolation, Report No.D2-22504, The Boeing Co., Seattle, Washington, 1963.
[Fer64] Ferguson, J.C., Multivariable curve interpolation, Journal ACM, 11 (1964),221-228.
[Coo64] Coons, S.A., Surfaces for computer aided design of space Figures, MIT Project MAC-TR-255, June, 1964.
[Coo67] Coons, S.A., Surfaces for computer aided design of space forms, MIT Project MAC-TR-41, June, 1967.
[Bez72] Bezier, R, Numerical Control: Mathematics and Applications, John Wiley and Sons, New York, 1972.
[Bez74] Bezier, P., Mathematical and practical possibilities of UNISURF, Computer Aided Geometric Design, in: Barnhill, R.E. and Riesenfield, R.E., eds.,Academic Press, New York, 1974, 127-152
[Bez86] Bezier, P., The Mathematical basis of the UNISURF CAD system, Butterworths, England, 1986.
[Sch46] Schoenberg, I.J., Contributions to the Problem of approximation of equidistant data by analytic function, Quart, Applied Mathematics, 4(1946), 45-99,112-141.
[deB72] deBoor, C., On calculation with B-spline, Journal of Approximation Theory, 6(1972),50-62.
[Cox71] Cox, M.G., The numerical evaluation of B-spline , Report No. NPL-DNACS-4, National Laboratory, 1971.
[GR74] Gordon, W.J. and Riesenfeld, R.F., B-spline curves and surfaces, in: Bamhill, R.E. and Riesenfeld, R.F. eds., Computer Aided Geometric Design. Academic Press, New York, 1974, 95-126.
[RC64] Rowin, M.S. and Conic, cubic and T-conic segments, D23-23252, The Beoing Company, Seattle, WA98124, 1964.
[Coo67] Coons, S.A., Surfaces for computer aided design of space forms, MIT Project MAC-TR-41, June, 1967.
[Bal74] Ball A. A. CONSURF, Part 1: Introduction to conic lofting title, Computer Aided Design, 1974, 6(4): 243-249.
[For80] Forrest, A. R., The twisted cubic curve: A computer aided geometric design approach, Computer Aided Design, 12(1980), 165-172.
[Far83] Farin, G, Algorithms for rational Bézier curves, Computer Aided Design, 15(1983), 73—79.
[Pie85] Pigel, L., Representation of quadric primitives by rational polynomials, Computer Aided Geometric Design, 2(1985), 151-155.
[刘85] 刘鼎元，有理Bézier曲线．应用数学学报，8(1985)，70-82．
[汪85] 汪国昭，沈金福，有理Bézier曲线的离散和几何性质，浙江大学学报，19(1985)，123-130．
[PT87] Pigel, L. and Tiller, W., Curve and surface constructions using rational B-splines, Computer Aided Design, 19(1987), 485-498.
[PT89] Pigel, L. and Tiller, W., A menagerie of rational B-splines circles, IEEE Computer Graphics and its Application, 9(1989), 48-56.
[Pie89a] Pigel, L., Modifying the shape of rational B-splines, part 1: curves, Computer Aided Design, 21(1989), 509—518.
[Pie89b] Pigel, L., Modifying the shape of rational B-splines, part 2: surfaces, Computer Aided Design, 21(1989), 538—546.
[Pie91] Pigel, L., On NURBS: a survey, IEEE Computer Graphics and Application, 10(1991), 55-71.
[Ti183] Tiller, W., Rational B-splines for curve and surface representation, IEEE Computer Graphics and Application, 3(1983), 61-69.
[Til86] Tiller, W., Geometric modeling using non-uniform rational B-splines: mathematical techniques, SIGGRAH tutorial notes, ACM, New York, 1986.
[Ti192] Tiller, W., Knot-remove algorithms for NURBS curves and surfaces, Computer Aided Design, 24(1992), 445-453.
[Far94] Farin, G., NURBS curve and surfaces: From Projective Geometry to Practical Use, A K Peters Ltd, Wellesley, Massachusetts, 1994.
[Ver91] Vergeest, S. M., CAD Surface data exchange using STEP, Computer Aided Design, 23(1991), 269-281.
[Bal74] Ball A. A. CONSURF, Part 1: Introduction to conic lofting title, Computer Aided Design, 1974, 6(4): 243-249.
[Bal75] Ball A, A. CONSURF, Part 2: Description of algorithm, Computer Aided Design, 1975, 7(4): 237-242.
[Bal77] Ball A. A. CONSURF, Part 3: How the program is used, Computer Aided Design, 1977, 9(1): 9-12.
[李85] 李建新，计算几何学中的有理函数法及其应用，南航学报，1985，(1)：18-31．
[王87] 王国瑾，高次Ball曲线及其几何性质，高校应用数学学报，1987，2(1)：126-140．
[Sai89] Said H. B. Generalized Ball curve and its recursive algorithm. ACM Transactions on Graphics, 1989, 8(4): 360-371.
[GS88] Goodman, T. N. T., Said, H. B.. Shape preserving properties of the generalized Ball basis. Technical Report M6/88, School of Mathematical and Computer Sciences, Universiti Sains Malaysia, Penang, Malasia, Sept, 1988.
[GS91a] Goodman T. N. T, Said H. B. Shape preserving properties of the generalized Ball basis[J]. Computer Aided Geometric Design, 1991, 8(2): 115-121.
[GS91b] Goodman T. N. T, Said H. B. Properties of generalized Ball curves and surfaces[J]. Computer Aided Design, 1991, 23(8): 554-560.
[HWJ96] Hu S. M. et al, Properties of two types of generalized Ball curves, Computer Aided Design, 1996, 28(2): 125-133.
[刘96] 刘松涛，刘根红，广义Ball样条曲线及三角域上曲面的升阶公式和转换算法．应用数学学报，1996，19(2)：243-253．
[奚97] 奚梅成．Ball基函数的对偶基及其应用．计算数学，1997，19(2)：147-153．
[HWS98] Hu, S. M., Wang, G. J. and Sun, J. G., A type of triangular Ball surface and its properties, Journal of Computer Science and Technology, 13(1998), 63-72.
[丁00] 丁友东，等．广义Ball曲线的性质及其应用．应用数学学报，2000，23(4)：580-595．
[PD00] Phien, H. N., Dejdumrong, N., Efficient algorithms for Bézier curves, Computer Aided Geometric Design, 2000, 17(3): 247-250.
[WC01] Wang Goujin, Cheng Min, New algorithms for evaluating parametric surface, Progress in Natural Science, 2001, 11(2): 142-148.
[陈01] 陈凌钧，等．Bézier曲线与Said-Ball曲线的递归转换算法．计算机辅助设计与图形学学报，2001，13(3)：264-266．
[邬00] 邬弘毅 两类新的广义Ball曲线 应用数学学报 2000，23(2)：196-205．
[DP03] Delgado, J., Pena, J. M., A Shape Preserving Representation with an Evaluation Algorithm of Linear Complexity. Computer Aided Geometric Design, 2003, 20: 1-20.
[WGJ88] 王国瑾，圆弧曲线的有理三次Bernstein基表示，高校应用数学学报，1998，3(2)：237-248．
[SW98] 寿华好，王国瑾，圆弧曲线的有理四次Bernstein基表示，高校应用数学学报，1998，13A(2)：233-238．
[WW92] Wang Guojin, Wang Guozhao, The rational cubic Bézier representation of conics, Computer Aided Geometric Design, 1992, 9(6): 447-455.
[NHHK01] Nattawit Dejdumrong, H. N. P., H. LT. and Kyaw, Rational Wang-Ball Curves, International Journal of Mathematical Education in Science and Technology, 32(2001), 565-584.
[HDH99] H. L. Tien, D. Hansuebsan and H. N. Phien, Rational Ball Curves, International Journal of Mathematical Education in Science and Technology, 30(1999), 243-257.
[ND06] Natasha Dejdumrong, Rational DP Curve, International Conference on Computer Graphics, Imaging and Visualisation, (1996) 478-483.
[Fer63] Ferguson, J.C., Multivariable curve interpolation, Report No.D2-22504, The Boeing Co., Seattle, Washington, 1963.
[Fer64] Ferguson, J.C., Multivariable curve interpolation, Journal ACM, 11 (1964),221-228.
[Coo64] Coons, S.A., Surfaces for computer aided design of space Figures, MIT Project MAC-TR-255, June, 1964.
[Coo67] Coons, S.A., Surfaces for computer aided design of space forms, MIT Project MAC-TR-41, June, 1967.
[Bez72] Bezier, R, Numerical Control: Mathematics and Applications, John Wiley and Sons, New York, 1972.
[Bez74] Bezier, P., Mathematical and practical possibilities of UNISURF, Computer Aided Geometric Design, in: Barnhill, R.E. and Riesenfield, R.E., eds.,Academic Press, New York, 1974, 127-152
[Bez86] Bezier, P., The Mathematical basis of the UNISURF CAD system, Butterworths, England, 1986.
[Sch46] Schoenberg, I.J., Contributions to the Problem of approximation of equidistant data by analytic function, Quart, Applied Mathematics, 4(1946), 45-99,112-141.
[deB72] deBoor, C., On calculation with B-spline, Journal of Approximation Theory, 6(1972),50-62.
[Cox71] Cox, M.G., The numerical evaluation of B-spline , Report No. NPL-DNACS-4, National Laboratory, 1971.
[GR74] Gordon, W.J. and Riesenfeld, R.F., B-spline curves and surfaces, in: Bamhill, R.E. and Riesenfeld, R.F. eds., Computer Aided Geometric Design. Academic Press, New York, 1974, 95-126.
[RC64] Rowin, M.S. and Conic, cubic and T-conic segments, D23-23252, The Beoing Company, Seattle, WA98124, 1964.
[Coo67] Coons, S.A., Surfaces for computer aided design of space forms, MIT Project MAC-TR-41, June, 1967.
[Bal74] Ball A. A. CONSURF, Part 1: Introduction to conic lofting title, Computer Aided Design, 1974, 6(4): 243-249.
[For80] Forrest, A. R., The twisted cubic curve: A computer aided geometric design approach, Computer Aided Design, 12(1980), 165-172.
[Far83] Farin, G, Algorithms for rational Bézier curves, Computer Aided Design, 15(1983), 73—79.
[Pie85] Pigel, L., Representation of quadric primitives by rational polynomials, Computer Aided Geometric Design, 2(1985), 151-155.
[刘85] 刘鼎元，有理Bézier曲线．应用数学学报，8(1985)，70-82．
[汪85] 汪国昭，沈金福，有理Bézier曲线的离散和几何性质，浙江大学学报，19(1985)，123-130．
[PT87] Pigel, L. and Tiller, W., Curve and surface constructions using rational B-splines, Computer Aided Design, 19(1987), 485-498.
[PT89] Pigel, L. and Tiller, W., A menagerie of rational B-splines circles, IEEE Computer Graphics and its Application, 9(1989), 48-56.
[Pie89a] Pigel, L., Modifying the shape of rational B-splines, part 1: curves, Computer Aided Design, 21(1989), 509—518.
[Pie89b] Pigel, L., Modifying the shape of rational B-splines, part 2: surfaces, Computer Aided Design, 21(1989), 538—546.
[Pie91] Pigel, L., On NURBS: a survey, IEEE Computer Graphics and Application, 10(1991), 55-71.
[Ti183] Tiller, W., Rational B-splines for curve and surface representation, IEEE Computer Graphics and Application, 3(1983), 61-69.
[Til86] Tiller, W., Geometric modeling using non-uniform rational B-splines: mathematical techniques, SIGGRAH tutorial notes, ACM, New York, 1986.
[Ti192] Tiller, W., Knot-remove algorithms for NURBS curves and surfaces, Computer Aided Design, 24(1992), 445-453.
[Far94] Farin, G., NURBS curve and surfaces: From Projective Geometry to Practical Use, A K Peters Ltd, Wellesley, Massachusetts, 1994.
[Ver91] Vergeest, S. M., CAD Surface data exchange using STEP, Computer Aided Design, 23(1991), 269-281.
[Bal74] Ball A. A. CONSURF, Part 1: Introduction to conic lofting title, Computer Aided Design, 1974, 6(4): 243-249.
[Bal75] Ball A, A. CONSURF, Part 2: Description of algorithm, Computer Aided Design, 1975, 7(4): 237-242.
[Bal77] Ball A. A. CONSURF, Part 3: How the program is used, Computer Aided Design, 1977, 9(1): 9-12.
[李85] 李建新，计算几何学中的有理函数法及其应用，南航学报，1985，(1)：18-31．
[王87] 王国瑾，高次Ball曲线及其几何性质，高校应用数学学报，1987，2(1)：126-140．
[Sai89] Said H. B. Generalized Ball curve and its recursive algorithm. ACM Transactions on Graphics, 1989, 8(4): 360-371.
[GS88] Goodman, T. N. T., Said, H. B.. Shape preserving properties of the generalized Ball basis. Technical Report M6/88, School of Mathematical and Computer Sciences, Universiti Sains Malaysia, Penang, Malasia, Sept, 1988.
[GS91a] Goodman T. N. T, Said H. B. Shape preserving properties of the generalized Ball basis[J]. Computer Aided Geometric Design, 1991, 8(2): 115-121.
[GS91b] Goodman T. N. T, Said H. B. Properties of generalized Ball curves and surfaces[J]. Computer Aided Design, 1991, 23(8): 554-560.
[HWJ96] Hu S. M. et al, Properties of two types of generalized Ball curves, Computer Aided Design, 1996, 28(2): 125-133.
[刘96] 刘松涛，刘根红，广义Ball样条曲线及三角域上曲面的升阶公式和转换算法．应用数学学报，1996，19(2)：243-253．
[奚97] 奚梅成．Ball基函数的对偶基及其应用．计算数学，1997，19(2)：147-153．
[HWS98] Hu, S. M., Wang, G. J. and Sun, J. G., A type of triangular Ball surface and its properties, Journal of Computer Science and Technology, 13(1998), 63-72.
[丁00] 丁友东，等．广义Ball曲线的性质及其应用．应用数学学报，2000，23(4)：580-595．
[PD00] Phien, H. N., Dejdumrong, N., Efficient algorithms for Bézier curves, Computer Aided Geometric Design, 2000, 17(3): 247-250.
[WC01] Wang Goujin, Cheng Min, New algorithms for evaluating parametric surface, Progress in Natural Science, 2001, 11(2): 142-148.
[陈01] 陈凌钧，等．Bézier曲线与Said-Ball曲线的递归转换算法．计算机辅助设计与图形学学报，2001，13(3)：264-266．
[邬00] 邬弘毅 两类新的广义Ball曲线 应用数学学报 2000，23(2)：196-205．
[DP03] Delgado, J., Pena, J. M., A Shape Preserving Representation with an Evaluation Algorithm of Linear Complexity. Computer Aided Geometric Design, 2003, 20: 1-20.
[WGJ88] 王国瑾，圆弧曲线的有理三次Bernstein基表示，高校应用数学学报，1998，3(2)：237-248．
[SW98] 寿华好，王国瑾，圆弧曲线的有理四次Bernstein基表示，高校应用数学学报，1998，13A(2)：233-238．
[WW92] Wang Guojin, Wang Guozhao, The rational cubic Bézier representation of conics, Computer Aided Geometric Design, 1992, 9(6): 447-455.
[NHHK01] Nattawit Dejdumrong, H. N. P., H. LT. and Kyaw, Rational Wang-Ball Curves, International Journal of Mathematical Education in Science and Technology, 32(2001), 565-584.
[HDH99] H. L. Tien, D. Hansuebsan and H. N. Phien, Rational Ball Curves, International Journal of Mathematical Education in Science and Technology, 30(1999), 243-257.
[ND06] Natasha Dejdumrong, Rational DP Curve, International Conference on Computer Graphics, Imaging and Visualisation, (1996) 478-483.