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

《计算机图形学常用算法及代码大全.doc》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、2.1.1生成直线的DDA算法　　数值微分法即DDA法(DigitalDifferentialAnalyzer)，是一种基于直线的微分方程来生成直线的方法。　　一、直线DDA算法描述：　　设(x1，y1)和(x2，y2)分别为所求直线的起点和终点坐标，由直线的微分方程得=m=直线的斜率(2－1)　　可通过计算由x方向的增量△x引起y的改变来生成直线：xi+1=xi+△x(2－2)yi+1=yi+△y=yi+△x·m(2－3)　　也可通过计算由y方向的增量△y引起x的改变来生成直线：yi+1=yi+△y(2

2、－4)xi+1=xi+△x=xi+△y/m(2－5)　　式(2－2)至(2－5)是递推的。　　二、直线DDA算法思想：　　选定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中较大者作为步进方向，是考虑沿着线段分布的象素应均匀，这

3、在下图中可看出。　　另外，算法实现中还应注意直线的生成方向，以决定Δx及Δy是取正值还是负值。　　三、直线DDA算法实现：　　1、已知直线的两端点坐标：(x1，y1)，(x2，y2)　　2、已知画线的颜色：color　　3、计算两个方向的变化量：dx=x2－x1　　　　　　　　　　　　　　dy=y2－y1　　4、求出两个方向最大变化量的绝对值：　　　　　　　　　　　　　　steps=max(

4、dx

5、，

6、dy

7、)　　5、计算两个方向的增量(考虑了生成方向)：　　　　　　　　　　　　　　xin=dx/step

8、s　　　　　　　　　　　　　　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浮点数转整数的宏实现代码#defineFloatToIn

9、teger(fNum)((fNum>0)?static_cast(fNum+0.5):static_cast(fNum-0.5))/*!*@briefDDA画线函数**@parampDC[in]窗口DC*@paramBeginPt[in]直线起点*@paramEndPt[in]直线终点*@paramLineCor[in]直线颜色*@return无*/voidCDrawMsg::DDA_DrawLine(CDC*pDC,CPoint&BeginPt,CPoint&EndPt,COLORR

10、EFLineCor){longYDis=(EndPt.y-BeginPt.y);longXDis=(EndPt.x-BeginPt.x);longMaxStep=max(abs(XDis),abs(YDis));//步进的步数floatfXUnitLen=1.0f;//X方向的单位步进floatfYUnitLen=1.0f;//Y方向的单位步进fYUnitLen=static_cast(YDis)/static_cast(MaxStep);fXUnitLen=static_ca

11、st(XDis)/static_cast(MaxStep);//设置起点像素颜色pDC->SetPixel(BeginPt.x,BeginPt.y,LineCor);floatx=static_cast(BeginPt.x);floaty=static_cast(BeginPt.y);//循环步进for(longi=1;i<=MaxStep;i++){x=x+fXUnitLen;y=y+fYUnitLen;pDC->SetPixel(FloatToI

12、nteger(x),FloatToInteger(y),LineCor);}}2.1.2生成直线的Bresenham算法　　从上面介绍的DDA算法可以看到，由于在循环中涉及实型数据的加减运算，因此直线的生成速度较慢。　　在生成直线的算法中，Bresenham算法是最有效的算法之一。Bresenham算法是一种基于误差判别式来生成直线的方法。　　一、直线Bresenham算法描述：　　它也是采用递推步进的办法，令每次最大变化方向