直线的光栅画法

今天看GOLang的书，里面有个程序示例用到了图形学里面的中点圆画法和直线的光栅画法。专业选修课老师讲过这俩种算法，但是睡过去了 T_T 。中点圆画法和直线光栅画法的基本思想是一致的（增量，增量修正，中点判断，判别式去乘法去除法去浮点运算，迭代，圆还使用了对称性），闲着无事推一下简单的直线光栅画法。

场景

屏幕上的每一个图像都是由一个个微小的像素点构成，这些像素点构成了像素阵列，作图就是给这个阵列上的像素点设置颜色的过程。

像素点之间是有间隔的，但是很小，被肉眼忽略。一条直线y=kx+b是连续的，我们无法在阵列上严格的画出他，只能选取直线轨迹附近的像素点近似地表现出来。

问题

如果通过解直线方程去确定每一个x对应的y然后画点，虽然简单准确，但无疑是低效的，首先每一个点都要根据x去求y，而且避免不了乘法和浮点运算。

解

设P1(x1,y1),P2(x2,y2)是直线的俩个端点（x2>x1），并且我们在斜率0<=k<=1的情况下讨论（其他情况可以通过平移对称等变换映射过去）。
dx=x2-x1
dy=y2-y1
k=dy/dx
若当前已画点为(x0,y0),则下一个点有俩个待选点Pa(x0+1,y0)和Pb(x0+1,y0+1):
if y0+k>y0+0.5则选择Pb，否则选择Pa.其中y0+k表示按直线方程来计算下一个点y值的精确值，y0+0.5表示俩个待选点的中点的y值。这个判断等价于：

Note:选择中点y值来作判断其实是一个间接的判断,严格的讲应是判断这俩个待选点到直线的垂直距离的大小，但是作图之后你会发现和这种判断方式是等价的，因为构成了俩个相似的直角三角形。

  Dj=y0+k-y0-0.5
  if Dj>0{
   chose Pb
  }else{
   chose Pa
  }

令Dg=2*Dj*dx，则Dg=2*dy-dx,那么原判断等价于

  if Dg>0{
   chose Pb
  }else{
   chose Pa
  }

这里我们通过Dg判断出了下一个点，那么再下一个点呢？
在下一个点y的精确值为y0+k+k,待选点的y值是上一个点的y值或是在其上加1后的值，即假设上一个点是(x,y)则下一个点是(x,y)或(x,y+1)这是由该该直线的斜率定死了的。

• 当Dg>0时：
  下一个点Pn1为（x0+1,y0+1），当当前点为Pn1时()：

    Dj=(y0+k+k)-(y0+1)-0.5
    if Dj>0{
      Pn2=(x0+2,y0+2)
    }else{
      Pn2=(x0+2,y0+1)
    }

Dj在原来的基础上增加了dDj=k-1.对应Dg增加dDg=2*dy-2*dx

• 当Dg<0时：

    Dj=(y0+k+k)-y0-0.5
    if Dj>0{
      Pn2=(x0+2,y0+1)
    }else{
      Pn2=(x0+2,y0)
    }

Dj在原来的基础上增加了dDj=k.对应Dg增加dDg=2*dy

所以有如下的伪代码：

   Dg=2*dy-dx;
   Point  point(x1,y1);
   for(int i=x1;i<x2+1;i++){
     drawPoint(point);
     point.x+=1;
     if(Dg>0){
       Dg+=2*dy-2*dx;
       point.y+=1;
     }else{
       Dg+=2*dy
     }
   }
   std::cout<<"Draw line done!"<<std::endl;

判别式Dg还有乘法，将其除以2即可，下面这段代码为全象限的完整算法：

  //by yyrdl ,2015/12/18
 func drawLine(img draw.Image, start, end image.Point,fill color.Color) {
	x0, x1 := start.X, end.X
    y0, y1 := start.Y, end.Y
    Δx := math.Abs(float64(x1 - x0))
    Δy := math.Abs(float64(y1 - y0))
    if Δx >= Δy {  
        if x0 > x1 {
            x0, y0, x1, y1 = x1, y1, x0, y0
        }
        y := y0
        yStep := 1
        if y0 > y1 {
            yStep = -1
        }
        remainder :=  Δy-Δx/2 
        for x := x0; x <= x1; x++ {
            img.Set(x, y, fill)
            if remainder>0.0{
				remainder+=Δy-Δx
				y+=yStep
			}else{
				remainder+=Δy
			}
        }
    } else {
        if y0 > y1 {
            x0, y0, x1, y1 = x1, y1, x0, y0
        }
        x := x0
        xStep := 1
        if x0 > x1 {
            xStep = -1
        }
		Δx,Δy=Δy,Δx 
        remainder :=  Δy-Δx/2 
        for y := y0; y <= y1; y++ {
            img.Set(x, y, fill)
           if remainder>0.0{
				remainder+=Δy-Δx
				x+=xStep
			}else{
				remainder+=Δy
			}
        }
    }
}

另外我正在看的《Programming in Go》这本书中的实现是(连他的注释也copy了过来)：

// Based on my Perl Image::Base.pm module's line() method 
func drawLine(img draw.Image, start, end image.Point,fill color.Color) {
    x0, x1 := start.X, end.X
    y0, y1 := start.Y, end.Y
    Δx := math.Abs(float64(x1 - x0))
    Δy := math.Abs(float64(y1 - y0))
    if Δx >= Δy { // shallow slope
        if x0 > x1 {
            x0, y0, x1, y1 = x1, y1, x0, y0
        }
        y := y0
        yStep := 1
        if y0 > y1 {
            yStep = -1
        }
        remainder := float64(int(Δx/2)) - Δx
        for x := x0; x <= x1; x++ {
            img.Set(x, y, fill)
            remainder += Δy
            if remainder >= 0.0 {
                remainder -= Δx
                y += yStep
            }
        }
    } else { // steep slope
        if y0 > y1 {
            x0, y0, x1, y1 = x1, y1, x0, y0
        }
        x := x0
        xStep := 1
        if x0 > x1 {
            xStep = -1
        }
        remainder := float64(int(Δy/2)) - Δy
        for y := y0; y <= y1; y++ {
            img.Set(x, y, fill)
            remainder += Δx
            if remainder >= 0.0 {
                remainder -= Δy
                x += xStep
            }
        }
    }
}

俩段代码99%相似，remainder的迭代更新规则也是一模一样的，只是初始值不一样，我不明白他的初始值是怎么来的，严重怀疑作者疏忽了，但是俩个代码画出的图却都是正常的。。。。

PS： 中点圆画法也是按照这样的思路推出来的，没事可以推一下
-----记录，分享