逐点生成参数曲线的双步算法  

Pixel- Level Double- Step Algorithm for RastPixel- Level Double- Step Algorithm for Rasterizing Parametric Curves

作　　者：刘勇奎[1] 周晓敏[2] 

机构地区：[1]大连民族学院计算机系,大连116600 [2]沈阳工业大学信息科学与工程学院,沈阳110023

出　　处：《计算机辅助设计与图形学学报》2002年第7期619-623,共5页Journal of Computer-Aided Design & Computer Graphics

基　　金：国家自然科学基金 (6940 3 0 0 4);辽宁省科技基金 (0 14 5 0 8)资助

摘　　要：首先介绍参数曲线逐点绘制的现有算法 ;然后提出一个最佳的步长值并验证了其优于现有算法的步长值 ,且证明了其最佳性 ,减轻了取点过密现象 .由于已找到了取点数的最佳值 ,因此对于传统的单步曲线生成算法来说 ,取点过密问题也只能解决到此程度 .为了进一步解决此问题 ,又提出一个只用整数运算的逐点生成参数曲线的双步算法 .该算法的一次循环允许沿曲线向前走两步 ,使算法所生成的点数减少了一半 ,最后所绘制的有效点则与单步算法完全相同 .加快了算法的速度 .实验结果表明 ,新算法的有效点率几乎达到 1,较好地解决了取点过密问题 .实验结果还表明 ,新算法的运行时间也远远少于现有算法 .Existing pixel- level algorithms for rasterizing parametric curves aim ed at finding in single step an optim um step- length for the whole curve. We propose a new approach,its result is verified to be better than those of the existing ones and is proved to be optimum.Thus the problem of oversam pling has gotan improved solution so far for the traditional single- step algorithm . To m ake further progress,a double- step algorithm that uses only integer arithm etic is presented.The number of points com puted by this algorithm is reduced by half by doubling the step- length in case that the same pixels are set as the single- step algorithm s do.The results of performance tests show that the ratio of the number of effective points to the num ber of all points com puted is nearly 10 0 % ,which means that the problem of oversam pling is solved even better.The results also show that the tim e needed by the new algorithm for rasterizing curves is much less than that needed by the other algorithms. The new algorithm can be used to draw any parametric curves.

关 键 词：参数曲线 逐点绘制 整数运算 双步算法 计算机图形学 曲线绘制 

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