逐点生成参数曲线的双步算法
Pixel-Level Double-Step Algorithm for Rasterizing Parametric Curves
-
摘要: 首先介绍参数曲线逐点绘制的现有算法;然后提出一个最佳的步长值并验证了其优于现有算法的步长值,且证明了其最佳性,减轻了取点过密现象.由于已找到了取点数的最佳值,因此对于传统的单步曲线生成算法来说,取点过密问题也只能解决到此程度.为了进一步解决此问题,又提出一个只用整数运算的逐点生成参数曲线的双步算法.该算法的一次循环允许沿曲线向前走两步,使算法所生成的点数减少了一半,最后所绘制的有效点则与单步算法完全相同.加快了算法的速度.实验结果表明,新算法的有效点率几乎达到1,较好地解决了取点过密问题.实验结果还表明,新算法的运行时间也远远少于现有算法.该算法对于任何参数曲线都是适用的.Abstract: Existing pixe-l level algorithms for rasterizing parametric curves aimed at finding in single step an optimum 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 oversampling has got an improved solution so far for the traditional single-step algorithm.To make further progress,a double-step algorithm that uses only integer arithmetic is presented.The number of points computed by this algorithm is reduced by half by doubling the step-length in case that the same pixels are set as the single-step algorithms do.The results of performance tests show that the ratio of the number of effective points to the number of all points computed is nearly 100%,which means that the problem of oversampling is solved even better.The results also show that the time 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.
下载: