【计算机图形学】基本图形元素：直线的生成算法
08年9月入学，12年7月毕业，结束了我在软件学院愉快丰富的大学生活。此系列是对四年专业课程学习的回顾，索引参见：http://blog.csdn.net/xiaowei_cqu/article/details/7747205
设直线之起点为（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的取值列在下表之中。
void PaintArea::drawLineDDA(QPainter &painter,int x0, int y0, int xEnd, int yEnd){ int dx=xEnd-x0,dy=yEnd-y0,steps,k; float xIncrement,yIncrement,x=x0,y=y0; if(fabs(dx)>fabs(dy)) steps=fabs(dx); else steps=fabs(dy); xIncrement=float(dx)/float(steps); yIncrement=float(dy)/float(steps); painter.drawPoint(round(x),round(y)); for(k=0;k<steps;k++){ x+=xIncrement; y+=yIncrement; painter.drawPoint(round(x),round(y)); }}这个算法由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算法的优点是：
【算法流程图】
【相关代码】
void PaintArea::drawLineBresenham(QPainter &painter, int x0, int y0, int xEnd, int yEnd){ int x,y,dx,dy,e; if(fabs(x0-xEnd)>fabs(y0-yEnd)){ dx=xEnd-x0; dy=yEnd-y0; e=-dx; x=x0; y=y0; for(int i=0;i<=dx;i++) {painter.drawPoint(x,y); x=x+1; e=e+2*dy; if(e>=0) {y=y+1; e=e-2*dx; }} } else if(fabs(x0-xEnd)>fabs(y0-yEnd)){ dx=xEnd-x0; dy=yEnd-y0; e=-dx; x=x0; y=y0; for(int i=0;i<=dx;i++) { painter.drawPoint(x,y); y=y+1; e=e+2*dx; if(e>=0) {x=x+1; e=e-2*dy; }} }}
假定直线斜率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为下一个象素点。这就是中点画线法的基本原理。
【算法流程图】
【相关代码】
void PaintArea::drawLineMiddle(QPainter &painter, int x0, int y0, int xEnd, int yEnd){ int a,b,d,x,y; if(fabs(x0-xEnd)>fabs(y0-yEnd)){ a=y0-yEnd; b=xEnd-x0; d=2*a+b; x=x0; y=y0; painter.drawPoint(x,y); while(x<xEnd) { if(d<0) {x++;y++;d+=2*(a+b); } else{x++;d+=2*a; } painter.drawPoint(x,y); } } else if(fabs(x0-xEnd)>fabs(y0-yEnd) &&(x0-xEnd))<0)){ a=y0-yEnd; b=xEnd-x0; d=2*a+b; x=x0; y=y0; painter.drawPoint(x,y); while(x>xEnd) { if(d<0) {x--;y--; d-=2*(a+b); } else{x--;d-=2*a; } painter.drawPoint(x,y); } } else if(fabs(x0-xEnd)<fabs(y0-yEnd)&&(x0-xEnd)<0){ a=y0-yEnd; b=xEnd-x0; d=2*a+b; x=x0; y=y0; painter.drawPoint(x,y); while(y>yEnd) { if(d<0) {y++;x++;d+=2*(a+b); } else{y++;d+=2*a; } painter.drawPoint(x,y); }}else if(fabs(x0-xEnd)<fabs(y0-yEnd) &&(x0-xEnd))>0)){ a=y0-yEnd; b=xEnd-x0; d=2*a+b; x=x0; y=y0; painter.drawPoint(x,y); while(x>xEnd) { if(d<0) {x--;y--; d-=2*(a+b); } else{x--;d-=2*a; } painter.drawPoint(x,y); } }else if(fabs(x0-xEnd)<fabs(y0-yEnd)&&(x0-xEnd)>0){ a=y0-yEnd; b=xEnd-x0; d=2*a+b; x=x0; y=y0; painter.drawPoint(x,y); while(y>yEnd) { if(d<0) {y++;x++;d+=2*(a+b); } else{y++;d+=2*a; } painter.drawPoint(x,y); } } }
这个绘图软件是用QT写的，我会另外写一篇介绍编程结构，敬请期待~