计算机视觉
图像处理

【计算机图形学】基本图形元素:直线的生成算法

文章目录

直线的DDA算法

【算法介绍】

设直线之起点为(x1,y1),终点为(x2,y2),则斜率m为:

 

直线中的每一点坐标都可以由前一点坐标变化一个增量(Dx, Dy)而得到,即表示为递归式:

并有关系:Dy = m • Dx。递归式的初值为直线的起点(x1, y1),这样,就可以用加法来生成一条直线。具体方法是:

直线方向的8个象限

按照直线从(x1,y1)到(x2,y2)的方向不同,分为8个象限。对于方向在第1a象限内的直线而言,D x=1,D y=m。对于方向在第1b象限内的直线而言,取值Dy=1,Dx=1/m。各象限中直线生成时Dx, Dy的取值列在下表之中。

  • 当|dx|>|dy|时,|D x|=1, |D y|=m;否则:Dx=1/m,|Dy|=1
  • Dx, Dy的符号与dx, dy的符号相同
这两条规律可以导致程序的简化

【算法流程图】

【相关代码】

  1. void PaintArea::drawLineDDA(QPainter &painter,int x0, int y0, int xEnd, int yEnd)
  2. {
  3.     int dx=xEnd-x0,dy=yEnd-y0,steps,k;
  4.     float xIncrement,yIncrement,x=x0,y=y0;
  5.     if(fabs(dx)>fabs(dy))  steps=fabs(dx);
  6.     else  steps=fabs(dy);
  7.     xIncrement=float(dx)/float(steps);
  8.     yIncrement=float(dy)/float(steps);
  9.     painter.drawPoint(round(x),round(y));
  10.     for(k=0;k<steps;k++){
  11.         x+=xIncrement;
  12.         y+=yIncrement;
  13.         painter.drawPoint(round(x),round(y));
  14.     }
  15. }


直线的Bresenham算法

这个算法由Bresenham在1965年提出。设直线从起点(x1, y1)到终点(x2, y2)。直线可表示为方程y=mx+b。其中

我们的讨论先将直线方向限于1a象限在这种情况下,当直线光栅化时,x每次都增加1个单元,即

而y的相应增加应当小于1。为了光栅化,yi+1只可能选择如下两种位置之一(如图)。

i+1的位置选择yi-1=yi 或者 yi+1=yi+1
选择的原则是看精确值y与yi及yi+1的距离d1及d2的大小而定。计算式为:

如果d1-d2>0,则yi+1=yi+1,否则yi+1=yi。因此算法的关键在于简便地求出d1-d2的符号。将上公式得
d1-d2=2y-2yi-1=2 (xi+1)-2yi+2b-1
用dx乘等式两边,并以Pi=dx(d1-d2)代入上述等式,得
Pi=2xidy-2yidx+2dy+dx(2b-1)
d1-d2是我们用以判断符号的误差。由于在1a象限,dx总大于0,所以Pi仍旧可以用作判断符号的误差。Pi-1为:
Pi+1=Pi+2dy-2dx(yi+1-yi)
误差的初值P1,可将x1, y1,和b代入式(4)中的xi, yi而得到:
P1=2dy-dx

Bresenham算法的优点是:

  1. 不用浮点数,只用整数;
  2. 只做整数加减法和乘2运算,而乘2运算可以用硬件移位实现。
  3. Bresenham算法速度很快,并适于用硬件实现。

【算法流程图】

【相关代码】

  1. void PaintArea::drawLineBresenham(QPainter &painter, int x0, int y0, int xEnd, int yEnd)
  2. {
  3.     int x,y,dx,dy,e;
  4.     if(fabs(x0-xEnd)>fabs(y0-yEnd)){
  5.         dx=xEnd-x0; dy=yEnd-y0; e=-dx;
  6.         x=x0; y=y0;
  7.         for(int i=0;i<=dx;i++)
  8.         {painter.drawPoint(x,y);
  9.          x=x+1; e=e+2*dy;
  10.          if(e>=0) {y=y+1; e=e-2*dx; }}
  11.     }
  12.     else if(fabs(x0-xEnd)>fabs(y0-yEnd)){
  13.         dx=xEnd-x0; dy=yEnd-y0; e=-dx;
  14.         x=x0; y=y0;
  15.         for(int i=0;i<=dx;i++)
  16.         { painter.drawPoint(x,y);
  17.          y=y+1; e=e+2*dx;
  18.          if(e>=0) {x=x+1; e=e-2*dy; }}
  19.     }
  20. }

中点画线法

假 定直线斜率k在0~1之间,当前象素点为(xp,yp),则下一个象素点有两种可选择点(xp+1,yp)或P2(xp+1,yp+1)。若P1与P2的 中点(xp+1,yp+0.5)称为M,Q为理想直线与x=xp+1垂线的交点。当M在Q的下方时,则取P2应为下一个象素点;当M在Q的上方时,则取 P1为下一个象素点。这就是中点画线法的基本原理。

【算法流程图】

【相关代码】

  1. void PaintArea::drawLineMiddle(QPainter &painter, int x0, int y0, int xEnd, int yEnd)
  2. {
  3.     int a,b,d,x,y;
  4.     if(fabs(x0-xEnd)>fabs(y0-yEnd)){
  5.         a=y0-yEnd; b=xEnd-x0; d=2*a+b; x=x0; y=y0;
  6.         painter.drawPoint(x,y);
  7.         while(x<xEnd)
  8.         {   if(d<0) {x++;y++;d+=2*(a+b); }
  9.             else{x++;d+=2*a; }
  10.             painter.drawPoint(x,y);
  11.         }
  12.     }
  13.     else if(fabs(x0-xEnd)>fabs(y0-yEnd) &&(x0-xEnd))<0)){
  14.         a=y0-yEnd; b=xEnd-x0; d=2*a+b; x=x0; y=y0;
  15.         painter.drawPoint(x,y);
  16.         while(x>xEnd)
  17.         {   if(d<0) {x–;y–; d-=2*(a+b); }
  18.             else{x–;d-=2*a; }
  19.             painter.drawPoint(x,y);
  20.         }
  21.     }
  22.     else if(fabs(x0-xEnd)<fabs(y0-yEnd)&&(x0-xEnd)<0){
  23.         a=y0-yEnd; b=xEnd-x0; d=2*a+b; x=x0; y=y0;
  24.         painter.drawPoint(x,y);
  25.  while(y>yEnd)
  26.         {   if(d<0) {y++;x++;d+=2*(a+b); }
  27.             else{y++;d+=2*a; }
  28.             painter.drawPoint(x,y);
  29.         }
  30. }
  31. else if(fabs(x0-xEnd)<fabs(y0-yEnd) &&(x0-xEnd))>0)){
  32.         a=y0-yEnd; b=xEnd-x0; d=2*a+b; x=x0; y=y0;
  33.         painter.drawPoint(x,y);
  34.         while(x>xEnd)
  35.         {   if(d<0) {x–;y–; d-=2*(a+b); }
  36.             else{x–;d-=2*a; }
  37.             painter.drawPoint(x,y);
  38.         }
  39.     }
  40. else if(fabs(x0-xEnd)<fabs(y0-yEnd)&&(x0-xEnd)>0){
  41.         a=y0-yEnd; b=xEnd-x0; d=2*a+b; x=x0; y=y0;
  42.         painter.drawPoint(x,y);
  43.  while(y>yEnd)
  44.         {   if(d<0) {y++;x++;d+=2*(a+b); }
  45.             else{y++;d+=2*a; }
  46.             painter.drawPoint(x,y);
  47.         }
  48.     }
  49. }

软件截图

这个绘图软件是用QT写的,我会另外写一篇介绍编程结构,敬请期待~

结果分析

  • 此次实验自己真的倾注了很大的心血。
    因为很喜欢计算机图形学,所以很想做个像模像样的东西出来,于是就下定决心借实验的机会做个简易的windows画板。也是第一次正式的使用QT开发,摸索的过程使得整个实验拖了很长时间。最终的结果还是比较令自己满意的,至少基本功能都实现了,界面也还看得过去。
  • 过于注重表面,算法上功夫不足,有些“舍本逐末”
    我 是把整个软件做差不多了,才开始细细得来研究图元的基本算法(开始都是调用qt自带的绘制函数)。调试算法的过程才深刻感觉这比整个软件更花时间(可能因 为整个软件并没有很复杂的架构)。由于时间有限,很多地方没有细细改进。尤其是对于k的几种情况,就生生的写了很冗余的代码,实在是丑啊。
  • 以后再继续改进。
    要改进的地方还有很多。比如算法结构重构,不要写那么冗余。然后再尝试一些填充算法自己实现,还有自己会试着做做简单的图像处理,变形拉伸什么的。
    总之,坚持动手,学以致用。

转载注明来源:CV视觉网 » 【计算机图形学】基本图形元素:直线的生成算法

分享到:更多 ()
扫描二维码,给作者 打赏
pay_weixinpay_weixin

请选择你看完该文章的感受:

0不错 0超赞 0无聊 0扯淡 0不解 0路过

评论 3

评论前必须登录!