有理参数曲线的快速逐点生成算法  

A Fast Point-by-Point Generating Algorithm for Rational Parametric Curves

作　　者：黄有度[1] 朱功勤[1] 

机构地区：[1]合肥工业大学数学与信息科学系,合肥230009

出　　处：《计算机学报》2001年第8期809-814,共6页Chinese Journal of Computers

基　　金：国家自然科学基金 (196 710 0 2 )资助

摘　　要：参数曲线的快速逐点生成算法在计算机图形学中有重要的应用 ,该作者在 2 0 0 0年给出的参数多项式曲线的快速逐点生成算法的基础上 ,进一步给出了有理参数曲线的快速逐点生成算法 .这样 ,许多用参数多项式曲线不能表示而可用有理参数曲线表示的曲线 ,如圆、双曲线等 ,可用文中的方法精确生成 .同文献 [1]一样 ,在曲线的逐点生成过程中 ,只用到整数加减法 .由于有理函数比多项式更加复杂 ,文献 [1]中的方法并不能简单地用于有理参数曲线的生成 ,该文作出进一步的改进以克服其中的困难 .因为生成曲线的点数与函数导数绝对值的上界有关 ,文中也讨论了估计有理 Bézier函数上界的方法 ,给出了两个估计公式 .与 Float 1992年给出的结果比较 。The fast point by point generating algorithm for parametric curves has important application in Computer Graphics, and [1] has already presented a fast point by point algorithm for polynomial parametric curves, based on the algorithm a fast algorithm for rational parametric curves is obtained in this paper. In this way, many parametric curves, such as circle, hyperbolas and so on, that can not be expressed with polynomial but can be expressed with rational functions, can be generated accurately. Similar to [1], in the process of generating the curve point by point, only integer additive and subtractive operations are involved. As rational function is more complicated than polynomial, the method in [1] can not be simply used for generating rational parametric curves. In this paper further modifications are made to overcome the difficulties in rational case.Since the point number of the generated curve is related to the bound of derivative, methods for estimating the upper bound on the derivative of a rational function are discussed as well and two formulas are presented. They are|x′(t)|n max 0in-1,0jn|(x i+1 -x j)w i+1 -(x i-x j)w i| min {w i,w i+1 }, 0t1,and|x′(t)|n max 0in-1,0jn{|[(x i+1 -x j)w i+1 -(x i-x j)w i]w j|}2 2n-2 c 2, 0t1,where c= min {w 0,w n}. [8] has obtained two estimations for the bound of derivative of Bézier function, which are simple but not accurate enough, and even invalid when some weights are zero. Comparing with the results of [8], the first one of the two formulas obtained in this paper is more accurate and the latter is always valid.

关 键 词：有理参数曲线 逐点生成算法 整数加减法 计算机图形学 

分 类 号：TP391.41[自动化与计算机技术—计算机应用技术]