2.1.1 生成直线的DDA算法
数值微分法即DDA法(Digital Differential Analyzer)，是一种基于直线的微分方程来生成直线的方法。
一、直线DDA算法描述：
设(x1，y1)和(x2，y2)分别为所求直线的起点和终点坐标，由直线的微分方程得
= m =直线的斜率 (2－1) 可通过计算由x方向的增量△x引起y的改变来生成直线：
xi+1=xi+△x yi+1=yi+△y=yi+△x·m 也可通过计算由y方向的增量△y引起x的改变来生成直线：
yi+1=yi+△y xi+1=xi+△x=xi+△y/m 式(2－2)至(2－5)是递推的。
二、直线DDA算法思想：
(2－4) (2－5) (2－2) (2－3) 选定x2－x1和y2－y1中较大者作为步进方向(假设x2－x1较大)，取该方向上的增量为一个象素单位(△x=1)，然后利用式(2－1)计算另一个方向的增量(△y=△x·m=m)。通过递推公式(2－2)至(2－5)，把每次计算出的(xi+1，yi+1)经取整后送到显示器输出，则得到扫描转换后的直线。 之所以取x2－x1和y2－y1中较大者作为步进方向，是考虑沿着线段分布的象素应均匀，这在下图中可看出。
另外，算法实现中还应注意直线的生成方向，以决定Δx及Δy是取正值还是负值。
三、直线DDA算法实现：
1、已知直线的两端点坐标：(x1，y1)，(x2，y2) 2、已知画线的颜色：color
3、计算两个方向的变化量：dx=x2－x1 dy=y2－y1 4、求出两个方向最大变化量的绝对值：
steps=max(|dx|，|dy|) 5、计算两个方向的增量(考虑了生成方向)： xin=dx/steps
yin=dy/steps 6、设置初始象素坐标：x=x1,y=y1 7、用循环实现直线的绘制： for(i=1；i<=steps；i++)
{ putpixel(x，y，color)；/*在(x，y)处，以color色画点*/ x=x+xin； y=y+yin； }
五、直线DDA算法特点：
该算法简单，实现容易，但由于在循环中涉及实型数的运算，因此生成直线的速度较慢。 //@brief 浮点数转整数的宏 实现代码
#define FloatToInteger(fNum)
((fNum>0)?static_cast
/*!
* @brief DDA画线函数 *
* @param pDC [in]窗口DC * @param BeginPt [in]直线起点 * @param EndPt [in]直线终点 * @param LineCor [in]直线颜色 * @return 无 */
void CDrawMsg::DDA_DrawLine(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
pDC->SetPixel(BeginPt.x,BeginPt.y,LineCor); float x = static_cast
for (long i = 1;i<=MaxStep;i++) { } }
x = x + fXUnitLen; y = y + fYUnitLen;
pDC->SetPixel(FloatToInteger(x),FloatToInteger(y),LineCor);
2.1.2 生成直线的Bresenham算法
从上面介绍的DDA算法可以看到，由于在循环中涉及实型数据的加减运算，因此直线的生成速度较慢。
在生成直线的算法中，Bresenham算法是最有效的算法之一。Bresenham算法是一种基于误差判别式来生成直线的方法。
一、直线Bresenham算法描述：
它也是采用递推步进的办法，令每次最大变化方向的坐标步进一个象素，同时另一个方向的坐标依据误差判别式的符号来决定是否也要步进一个象素。
我们首先讨论m=△y/△x，当0≤m≤1且x1 xi+1=xi+1 yi+1=yi+m (2－6) (2－7) 有两种Bresenham算法思想，它们各自从不同角度介绍了Bresenham算法思想，得出的误差判别式都是一样的。 二、直线Bresenham算法思想之一： 由于显示直线的象素点只能取整数值坐标，可以假设直线上第i个象素点坐标为(xi，yi)，它是直线上点(xi，yi)的最佳近似，并且xi=xi(假设m<1），如下图所示。那么，直线上下一个象素点的可能位置是(xi+1，yi)或(xi+1，yi+1)。 由图中可以知道，在x=xi+1处，直线上点的y值是y=m(xi+1)+b，该点离象素点(xi+1，yi)和象素点(xi+1，yi+1)的距离分别是d1和d2： d1=y-yi=m(xi+1)+b-yi d2=(yi+1)-y=(yi+1)-m(xi+1)-b 这两个距离差是 d1-d2=2m(xi+1)-2yi＋2b-1 我们来分析公式(2-10)： (1)当此值为正时，d1>d2，说明直线上理论点离(xi+1，yi+1)象素较近，下一个象素点应取(xi+1，yi+1)。 (2)当此值为负时，d1 (3)当此值为零时，说明直线上理论点离上、下两个象素点的距离相等，取哪个点都行，假设算法规定这种情况下取(xi+1，yi+1)作为下一个象素点。 因此只要利用(d1-d2)的符号就可以决定下一个象素点的选择。为此，我们进一步定义一个新的判别式： pi=△x×(d1-d2)=2△y·xi-2△x·yi+c 式(2-11)中的△x=(x2-x1)>0，因此pi与(d1-d2)有相同的符号； (2－11) (2－10) (2－8) (2－9) 这里△y=y2-y1，m=△y/△x；c=2△y+△x(2b-1)。 下面对式(2-11)作进一步处理，以便得出误差判别递推公式并消除常数c。 将式(2-11)中的下标i改写成i+1，得到： pi+1=2△y·xi+1-2△x·yi+1+c 将式(2-12)减去(2-11)，并利用xi+1=xi+1，可得： pi+1= pi+2△y-2△x·(yi+1-yi) 再假设直线的初始端点恰好是其象素点的坐标，即满足： y1=mx1+b 由式(2-11)和式(2-14)得到p1的初始值： p1=2△y-△x 这样，我们可利用误差判别变量，得到如下算法表示： 初始 p1=2△y-△x 当pi≥0时： yi+1=yi+1, xi+1=xi+1， pi+1=pi+2(△y-△x) 否则： yi+1=yi, xi+1=xi+1， (2－12) (2－13) (2－14) (2－15) (2－16) pi+1=pi+2△y 从式(2-16)可以看出，第i+1步的判别变量pi+1仅与第i步的判别变量pi、直线的两个端点坐标分量差△x和△y有关，运算中只含有整数相加和乘2运算，而乘2可利用算术左移一位来完成，因此这个算法速度快并易于硬件实现。 三、直线Bresenham算法思想之二： 由于象素坐标的整数性，数学点(xi，yi)与所取象素点(xi，yir)间会引起误差(εi)，当xi列上已用象素坐标(xi，yir)表示直线上的点(xi，yi)，下一直线点B(xi+1，yi+1)，是取象素点C(xi+1，yir )，还是D(xi＋1，y(i+1)r)呢？ 设A为CD边的中点，正确的选择： 若B点在A点上方，选择D点； 否则，选C点。
计算机图形学常用算法及代码大全
