注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

Search的博客

不断学习中!

 
 
 

日志

 
 

DDA绘图算法  

2012-11-18 16:06:57|  分类: 默认分类 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

作者:朱金灿
来源:http://blog.csdn.net/clever101/


      DDA算法和Bresenham算法是计算机图形学中绘制直线的两种常用算法。本文具体介绍一下DDA算法和Bresenham算法实现的具体思路。DDA算法主要是根据直线公式y = kx + b来推导出来的,其关键之处在于如何设定单位步进,即一个方向的步进为单位步进,另一个方向的步进必然是小于1。算法的具体思路如下:


1. 输入直线的起点、终点;


2. 计算x方向的间距:△X和y方向的间距:△Y。


3. 确定单位步进,取MaxSteps = max(△X,△Y); 若△X>=△Y,则X方向的步进为单位步进,X方向步进一个单位,Y方向步进△Y/MaxSteps;否则相反。


4. 设置第一个点的像素值


5. 令循环初始值为1,循环次数为MaxSteps,定义变量x,y,执行以下计算:
a. x增加一个单位步进,y增加一个单位步进
b. 设置位置为(x,y)的像素值


    具体实现代码如下:

  1. //@brief 浮点数转整数的宏   
  2. #define  FloatToInteger(fNum)   ((fNum>0)?static_cast<int>(fNum+0.5):static_cast<int>(fNum-0.5))   
  3. /*! 
  4. *  @brief DDA画线函数 
  5. * 
  6. *  @param pDC      [in]窗口DC 
  7. *  @param BeginPt  [in]直线起点 
  8. *  @param EndPt    [in]直线终点 
  9. *  @param LineCor  [in]直线颜色 
  10. *  @return 无 
  11. */  
  12. void CDrawMsg::DDA_DrawLine(CDC *pDC,CPoint &BeginPt,CPoint &EndPt,COLORREF LineCor)  
  13. {  
  14.     long YDis = (EndPt.y - BeginPt.y);  
  15.     long XDis = (EndPt.x-BeginPt.x);  
  16.     long MaxStep = max(abs(XDis),abs(YDis)); // 步进的步数   
  17.     float fXUnitLen = 1.0f;  // X方向的单位步进   
  18.     float fYUnitLen = 1.0f;  // Y方向的单位步进   
  19.     fYUnitLen = static_cast<float>(YDis)/static_cast<float>(MaxStep);  
  20.     fXUnitLen = static_cast<float>(XDis)/static_cast<float>(MaxStep);  
  21.     // 设置起点像素颜色   
  22.     pDC->SetPixel(BeginPt.x,BeginPt.y,LineCor);   
  23.     float x = static_cast<float>(BeginPt.x);  
  24.     float y = static_cast<float>(BeginPt.y);  
  25.     // 循环步进   
  26.     for (long i = 1;i<=MaxStep;i++)  
  27.     {  
  28.         x = x + fXUnitLen;  
  29.         y = y + fYUnitLen;  
  30.         pDC->SetPixel(FloatToInteger(x),FloatToInteger(y),LineCor);  
  31.     }  
  32. }  
//@brief 浮点数转整数的宏 #define FloatToInteger(fNum) ((fNum>0)?static_cast<int>(fNum+0.5):static_cast<int>(fNum-0.5)) /*! * @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<float>(YDis)/static_cast<float>(MaxStep); fXUnitLen = static_cast<float>(XDis)/static_cast<float>(MaxStep); // 设置起点像素颜色 pDC->SetPixel(BeginPt.x,BeginPt.y,LineCor); float x = static_cast<float>(BeginPt.x); float y = static_cast<float>(BeginPt.y); // 循环步进 for (long i = 1;i<=MaxStep;i++) { x = x + fXUnitLen; y = y + fYUnitLen; pDC->SetPixel(FloatToInteger(x),FloatToInteger(y),LineCor); } }


      Bresenham算法是DDA算法画线算法的一种改进算法。本质上它也是采取了步进的思想。不过它比DDA算法作了优化,避免了步进时浮点数运算,同时为选取符合直线方程的点提供了一个好思路。首先通过直线的斜率确定了在x方向进行单位步进还是y方向进行单位步进:当斜率k的绝对值|k|<1时,在x方向进行单位步进;当斜率k的绝对值|k|>1时,在y方向进行单位步进。

下面以|k|<1时推导Bresenham算法的数学依据:


bresenham



    请看上图,已知有一直线y = kx+b,|k|<1。我们通过斜率确定了x方向为单位步进。当x = Xm时,y = Ym。那么当x 执行一个单位步进时(即x = Xm+1时),y等于Ym还是等于Ym+1更符合这个直线方程呢?单凭肉眼我们很难得出结论,最好的办法当然是比较Ym和Ym+1和真实的方程的y值的差是多少(即Yreal = k*(Xm+1)+b),看看哪一个更靠近真实的方程的y值。

我们设
Dupper = Ym+1 - Yreal = Ym+1 - k*(Xm+1)+b); 表示Ym+1和方程真实值的差

Ddown = Yreal - Ym = k*(Xm+1)+b)- Ym; 表示Ym和方程真实值的差


那就是我们要比较Dupper和Ddown的大小。假设
Diff = Dupper - Ddown = (Ym+1 - k*(Xm+1)+b)) - (k*(Xm+1)+b)- Ym)
令△X 为线段x方向的间距,△Y 为线段y方向的间距。
Pm = △X* Diff = 2*△X* Ym-2*△Y* Xm-2*△Y-△X*(2b-1);
那么Pm+1 = Pm+2*△X*(Ym+1- Ym)-2*△Y;
其中Ym+1- Ym取0还是1,取决于Pm的符号。

根据等式Diff = Dupper - Ddown = (Ym+1 - k*(Xm+1)+b)) - (k*(Xm+1)+b)- Ym)以及k = △Y/△X,我们可以得出起始像素(x0,y0)的参数p0的值:
P0 =△X-2*△Y;

同理我们推出|k|>1的情况,Qm = 2*Xm*△Y-2*Ym*△X+(2b-2)*△X+△Y;
Qm+1 = Qm+2*(Xm+1-Xm)*△Y-2*△X;

其中Xm+1-Xm等于0还是1,取决于Qm的符号

其中第一个参数Q0 = △Y-2*△X;


    明白了数学原理,我们很快能确定算法步骤:


1. 输入线段的起点和终点。


2. 判断线段的斜率是否存在(即起点和终点的x坐标是否相同),若相同,即斜率不存在,
只需计算y方向的单位步进(△Y+1次),x方向的坐标保持不变即可绘制直线。


3. 计算线段的斜率k,分为下面几种情况处理

a. k等于0,即线段平行于x轴,即程序只需计算x方向的单位步进,y方向的值不变

b. |k|等于1,即线段的x方向的单位步进和y方向的单位步进一样,皆为1。直接循环△X次计算x和y坐标。


4. 根据输入的起点和终点的x、y坐标值的大小决定x方向和y方向的单位步进是1还是-1


6. 画出第一个点。


7. 若|k| <1,设m =0,计算P0,如果Pm>0,下一个要绘制的点为(Xm+单位步进,Ym),
Pm+1 = Pm -2*△Y;
否则要绘制的点为(Xm+单位步进,Ym+单位步进)
Pm+1 = Pm+2*△X-2*△Y;


8. 重复执行第七步△X-1次;


9. 若|k| >1,设m =0,计算Q0,如果Qm>0,下一个要绘制的点为(Xm,Ym+单位步进),
Pm+1 = Pm -2*△X;
否则要绘制的点为(Xm+单位步进,Ym+单位步进)
Pm+1 = Pm+2*△Y-2*△X;


10. 重复执行第9步△Y-1次;

  评论这张
 
阅读(245)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017