《计算机图形学常用算法及代码大全》由会员分享，可在线阅读，更多相关《计算机图形学常用算法及代码大全（41页珍藏版）》请在金锄头文库上搜索。
1、2.1.1 生成直线的DDA算法数值微分法即DDA法(Digital Differential Analyzer)，是一种基于直线的微分方程来生成直线的方法。一、直线DDA算法描述：设(x1，y1)和(x2，y2)分别为所求直线的起点和终点坐标，由直线的微分方程得= m =直线的斜率(21)可通过计算由x方向的增量x引起y的改变来生成直线：xi+1=xi+x(22)yi+1=yi+y=yi+xm(23)也可通过计算由y方向的增量y引起x的改变来生成直线：yi+1=yi+y(24)xi+1=xi+x=xi+y/m(25)式(22)至(25)是递推的。二、直线DDA算法思想：选定x2x1和y2y1
2、中较大者作为步进方向(假设x2x1较大)，取该方向上的增量为一个象素单位(x=1)，然后利用式(21)计算另一个方向的增量(y=xm=m)。通过递推公式(22)至(25)，把每次计算出的(xi+1，yi+1)经取整后送到显示器输出，则得到扫描转换后的直线。之所以取x2x1和y2y1中较大者作为步进方向，是考虑沿着线段分布的象素应均匀，这在下图中可看出。另外，算法实现中还应注意直线的生成方向，以决定x及y是取正值还是负值。三、直线DDA算法实现：1、已知直线的两端点坐标：(x1，y1)，(x2，y2)2、已知画线的颜色：color3、计算两个方向的变化量：dx=x2x1 dy=y2y14、求出两
3、个方向最大变化量的绝对值： steps=max(|dx|，|dy|)5、计算两个方向的增量(考虑了生成方向)： xin=dx/steps yin=dy/steps6、设置初始象素坐标：x=x1,y=y17、用循环实现直线的绘制：for(i=1；i0)?static_cast(fNum+0.5):static_cast(fNum-0.5)/*!* brief DDA画线函数* param pDC in窗口DC* param BeginPt in直线起点* param EndPt in直线终点* param LineCor in直线颜色* return 无*/void CDrawMsg:DDA_D
4、rawLine(CDC *pDC,CPoint &BeginPt,CPoint &EndPt,COLORREF LineCor)long YDis = (EndPt.y - BeginPt.y);long XDis = (EndPt.x-BeginPt.x);long MaxStep = max(abs(XDis),abs(YDis); / 步进的步数float fXUnitLen = 1.0f; / X方向的单位步进float fYUnitLen = 1.0f; / Y方向的单位步进fYUnitLen = static_cast(YDis)/static_cast(MaxStep);fXUn
5、itLen = static_cast(XDis)/static_cast(MaxStep);/ 设置起点像素颜色pDC-SetPixel(BeginPt.x,BeginPt.y,LineCor); float x = static_cast(BeginPt.x);float y = static_cast(BeginPt.y);/ 循环步进for (long i = 1;iSetPixel(FloatToInteger(x),FloatToInteger(y),LineCor);2.1.2 生成直线的Bresenham算法从上面介绍的DDA算法可以看到，由于在循环中涉及实型数据的加减运算，因
6、此直线的生成速度较慢。在生成直线的算法中，Bresenham算法是最有效的算法之一。Bresenham算法是一种基于误差判别式来生成直线的方法。一、直线Bresenham算法描述：它也是采用递推步进的办法，令每次最大变化方向的坐标步进一个象素，同时另一个方向的坐标依据误差判别式的符号来决定是否也要步进一个象素。我们首先讨论m=y/x，当0m1且x1x2时的Bresenham算法。从DDA直线算法可知这些条件成立时，公式(2-2)、(2-3)可写成：xi+1=xi+1(26)yi+1=yi+m(27)有两种Bresenham算法思想，它们各自从不同角度介绍了Bresenham算法思想，得出的误差
7、判别式都是一样的。二、直线Bresenham算法思想之一：由于显示直线的象素点只能取整数值坐标，可以假设直线上第i个象素点坐标为(xi，yi)，它是直线上点(xi，yi)的最佳近似，并且xi=xi(假设md2，说明直线上理论点离(xi+1，yi+1)象素较近，下一个象素点应取(xi+1，yi+1)。(2)当此值为负时，d10，因此pi与(d1-d2)有相同的符号；这里y=y2-y1，m=y/x；c=2y+x(2b-1)。下面对式(2-11)作进一步处理，以便得出误差判别递推公式并消除常数c。将式(2-11)中的下标i改写成i+1，得到：pi+1=2yxi+1-2xyi+1+c(212)将式(2
8、-12)减去(2-11)，并利用xi+1=xi+1，可得：pi+1= pi+2y-2x(yi+1-yi)(213)再假设直线的初始端点恰好是其象素点的坐标，即满足：y1=mx1+b(214)由式(2-11)和式(2-14)得到p1的初始值： p1=2y-x(215)这样，我们可利用误差判别变量，得到如下算法表示：初始 p1=2y-x(216)当pi0时： yi+1=yi+1,xi+1=xi+1，pi+1=pi+2(y-x)否则：yi+1=yi,xi+1=xi+1， pi+1=pi+2y从式(2-16)可以看出，第i+1步的判别变量pi+1仅与第i步的判别变量pi、直线的两个端点坐标分量差x和y
9、有关，运算中只含有整数相加和乘2运算，而乘2可利用算术左移一位来完成，因此这个算法速度快并易于硬件实现。三、直线Bresenham算法思想之二：由于象素坐标的整数性，数学点(xi，yi)与所取象素点(xi，yir)间会引起误差(i)，当xi列上已用象素坐标(xi，yir)表示直线上的点(xi，yi)，下一直线点B(xi+1，yi+1)，是取象素点C(xi+1，yir )，还是D(xi1，y(i+1)r)呢？设A为CD边的中点，正确的选择：若B点在A点上方，选择D点； 否则，选C点。用误差式描述为：(xi+1)=BC-AC=(yi+1-yir)-0.5(28)求递推公式：(xi+2)=(yi+2
10、-y(i+1)r)-0.5 = yi+1+m-y(i+1)r-0.5(29)当(xi+1)0时，选D点，y(i+1)r = yir+1(xi+2)= yi+1+m-yir-1-0.5=(xi+1)+m-1(210)当(xi+1)0时，选C点，y(i+1)r = yir(xi+2)= yi+1+myir-0.5=(xi+1)+m(211)初始时：(xs+1)=BC-AC=m-0.5(212)为了运算中不含实型数，同时不影响不等式的判断，将方程两边同乘一正整数。令方程两边同乘2x，即d=2x，则：初始时：d = 2y-x(213)递推式：当d0时： d=d+2(yx)；y+；x+；否则： d=d+
11、2y；x+； (214)实现代码void Bresenhamline (int x0,int y0,int x1, int y1,int color)int x, y, dx, dy;float k, e;dx = x1-x0, dy = y1- y0, k=dy/dx;e=-0.5, x=x0, y=y0;for (i=0; i=0) y+, e=e-1;或者将e扩大2dx倍；void Bresenhamline (int x0,int y0,int x1, int y1,int color)int x, y, dx, dy;float k, e;dx = x1-x0, dy = y1- y0, k=dy/dx;e=-dx, x=x0, y=y0;for (i=0; i=dx;
