椭圆生成算法的研究

《椭圆生成算法的研究》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、计算机图形学课程设计题目名称:椭圆生成算法的研究2012年1月14椭圆生成算法的研究摘要作为计算机图形学中基本几何元素之一的椭圆，其生成算法在几乎所有计算机图形学相关领域都要用到，尤其在计算机辅助设计中经常涉及。因此，研究椭圆生成对计算机图形系统十分重要。目前，已有大量的文献讨论了如何高效生成误差小的椭圆。文献一中方法之一在扫描转换的同时复制椭圆宽度数个像素，这种方法比较简单，但造成椭圆切线斜率接近-1处显得很细。文献一中方法之二扫描转换两个同心的椭圆，内椭圆的两个半径分别为a-w/2，b-w/2；外椭

2、圆的两个半径为a+w/2,b+w/2；然后填充它们间的间隙，在微分几何中有一个结论：沿着垂直椭圆弧的方向，将此椭圆上的点移动w/2的距离所形成的曲线与原椭圆同心的椭圆，而是由一个8次方程所描述的曲线，因此这种算法也有较大误差，特别是a的值接近于w时。然而，对这样8次函数进行扫描转换，计算量非常大。圆弧绘制生成宽椭圆算法与椭圆中点扫描转换算法复杂度相当，且生成的椭圆效果较好，视觉感受不到明显缺陷。本文主要对计算机图形学、椭圆的生成算法的具体实现及其应用进行综述，并简要讨论。关键词：计算机图形学椭圆生成算法

3、并行生成算法宽椭圆141一种宽椭圆生成算法计算机辅助设计领域常涉及宽椭圆生成，宽椭圆生成算法的优劣直接影响设计效果。为了生成一个圆心在原点的标准宽椭圆，每次用单像素宽的椭圆中点扫描转换算法，得到一个单像素宽椭圆上的一个点，填充一个以该点为中心，椭圆宽为直径的圆弧，扫描转换结束后，生成一个无明显视觉缺陷的第一象限12宽椭圆。作为计算机图形学中基本几何元素之一的椭圆，其生成算法在几乎所有计算机图形学相关领域都要用到，尤其在计算机辅助设计中经常涉及。因此，研究椭圆生成对计算机图形系统十分重要。目前，已有大量的

4、文献讨论了如何高效生成误差小的椭圆。椭圆的扫描转换法[1]就是其中之一，该算法基于DaSilva的算法[2]，运用二阶偏差分Pitteway[3]，VanAken[4]、KAppel[5]等所用的一些技术，该算法生成的椭圆都是单像素宽的，而现实中更多时候要生成宽椭圆，宽椭圆一般定义为沿着垂直两半径为a、b的椭圆弧的两方向，将此椭圆上的点移动2w的距离所形成的两条曲线中间部分，为了生成宽椭圆，文献一中方法之一在扫描转换的同时复制椭圆宽度数个像素，这种方法比较简单，但造成椭圆切线斜率接近-1处显得很细。文献

5、一中方法之二扫描转换两个同心的椭圆，内椭圆的两个半径分别为2a−w，2b−w；外椭圆的两个半径为2a+w，2b+w；然后填充它们间的间隙，在微分何中有一个结论：沿着垂直椭圆弧的方向，将此椭圆上的点移动2w的距离所形成的曲线与原椭圆同心的椭圆，而是由一个8次方程所描述的曲线[6]，因此这种算法也有较大误差，特别是a的值接近于w时。然而，对这样8次函数进行扫描转换，计算量非常大。圆弧绘制生成宽椭圆算法与椭圆中点扫描转换算法复杂度相当，且生成的椭圆效果较好，视觉感受不到明显缺陷。1.1算法基本思想主要考虑中心

6、在原点的标准椭圆，宽度为w，(a>b>w，a，b，w∈z)；对于中心不在坐标原点的椭圆，可先作相应的平移变换，变换为中心在原点的椭圆，把所得的像素坐标加上一个位移即可得到所求的像素坐标。此外，只讨论椭圆在第一象限内的生成算法，其他象限内的点利用椭圆的四分对称性即可得到。在第一象限内的四分之一椭圆分为两个区域来处理．两个区域之间以斜率为-1的点(即法向量两个分量相等的点)作为分界。对于区域I，以点(0，b)为始点，x方向单位长作为步长。向右生成曲线。假设当前扫描计算得到的点为批p0（x，y），扫描转换的下

7、一个点p1可能为=（x+1，y）或=（x+1，y-1），判断s1、s2的中间点在椭圆的内还是外，选择下一个扫描点。如果中点m在内(m点代入椭圆方程值小于1)，则下一个点p1为（x+1,y），否则为（x+1,y-1）；当斜率变为小于-l时，转向区域Ⅱ，此时以(a，0)为始点。y方向作为单位步长，向左生成曲线。假设当前扫描计算得到的点为p0′(x，y)，扫描转换的下一个点可能为s1′(x，y+1)或s2′(x-1，y+1)，判断、14的中间点m（x−，y+）在椭圆的内还是外，选择下一个扫描点。如果中点在内，

8、则下一个点p1′为（x，y+1）否则为（x-1，y+1）。以上简单介绍了椭圆中点扫描生成算法，接下来基于中点扫描算法来生成宽椭圆。宽椭圆生成算法思路：先以中点圆算法[1]生一个圆心在原点直径为w的圆，填充该圆，然后以椭圆扫描转换算法[1]求得椭圆上的点，将填充的圆平移到扫描转换得到的各点处（如图1）。图1生成椭圆第一象限1.2算法实现过程如图2，椭圆扫描转化得到的相邻点P0(x0，y0)、P1(x1，y1)，它们对应的圆形填充区为U1、U0