计算机图形学常用算法及代码大全

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)是递推的。

2、二、直线 DDA 算法思想：选定 x2x1和 y2y1中较大者作为步进方向(假设 x2x1较大)，取该方向上的增量为一个象素单位(x=1)，然后利用式(21)计算另一个方向的增量(y=xm=m)。通过递推公式(22)至(25)，把每次计算出的(xi+1，yi+1)经取整后送到显示器输出，则得到扫描转换后的直线。之所以取 x2x1和 y2y1中较大者作为步进方向，是考虑沿着线段分布的象素应均匀，这在下图中可看出。另外，算法实现中还应注意直线的生成方向，以决定x 及y 是取正值还是负值。三、直线 DDA 算法实现：1、已知直线的两端点坐标：(x1，y1)，(x2，y2)2、已知画线的颜色：colo

3、r3、计算两个方向的变化量：dx=x2x1dy=y2y14、求出两个方向最大变化量的绝对值：steps=max(|dx|，|dy|)5、计算两个方向的增量(考虑了生成方向)：xin=dx/stepsyin=dy/steps6、设置初始象素坐标：x=x1,y=y17、用循环实现直线的绘制：for(i=1；i0)?static_cast(fNum+0.5):static_cast(fNum-0.5)/*!*brief DDA 画线函数*param pDCin窗口 DC*param BeginPtin直线起点*param EndPtin直线终点*param LineCorin直线颜色*return

4、无*/void CDrawMsg:DDA_DrawLine(CDC *pDC,CPoint &BeginPt,CPoint &EndPt,COLORREFLineCor)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(YD

5、is)/static_cast(MaxStep);fXUnitLen = 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算法算法

6、从上面介绍的DDA 算法可以看到，由于在循环中涉及实型数据的加减运算，因此直线的生成速度较慢。在生成直线的算法中，Bresenham算法是最有效的算法之一。Bresenham算法是一种基于误差判别式来生成直线的有两种 Bresenham 算法思想，它们各自从不同角度介绍了Bresenham 算法思想，得出的误差判别式都是一样的。二、直线 Bresenham 算法思想之一：由于显示直线的象素点只能取整数值坐标，可以假设直线上第 i 个象素点坐标为(xi，yi)，它是直线上点(xi，yi)的最佳近似，并且 xi=xi(假设 m1），如下图所示。那么，直线上下一个象素点的可能位置是(xi+1，yi)或(xi+1，yi+1)。由图中可以知道，在 x=xi+1 处，直线上点的 y 值是方法。一、直线Bresenham 算法描述：它也是采用递推步进的办法，令每次最大变化方向的坐标步进一个象素，同时另一个方向的坐标依据误差判别式的符号来决定是否也要步进一个象素。我们首先讨论m=y/x，当0m1 且 x1x2时的 Bresenham 算法。从 DDA 直线算法可知这些