现在主流显示器是光栅显示器，因此发展一套与之相关的算法 光栅图形算法多数属于计算机图形的底层算法 光栅图形学算法的研究内容： 1. 直线段的扫描转换算法 2. 多边形的扫描转换与区域填充算法 3. 裁剪算法 4. 反走样算法 5. 消隐算法
在数学上，直线上的点有无穷多个。但在光栅扫描显示器上，像素点是有限的，要用有限的像素逼近直线上无限的点 为了在光栅显示器上用这些离散的像素点逼近这条直线，需要知道这些像素点的x,y坐标
求出过P0，P1的直线段方程 y=kx+b k=(y1-y0)/(x1-x0) 要求其他绿色像素点的坐标，假设x已知，即从x的起点x0开始，沿x方向前进一个像素（步长=1），可以计算相应的y值 因为像素的坐标是整数，所以y值还要进行取整处理 如何把数学上的一个点扫描转换一个屏幕像素点？ 如：P(1.7,0.8) —>取整 P（1,0） P(1.7,0.8) —>+0.5 P(2.2,1.3) P(2.2,1.3)—> 取整 P(2,1) 直线是最基本的图形，一个动画或者真实感图形往往需要调用成千上万次画线程序，因此直线算法的好坏与效率将直接影响图形的质量和显示速度 为了提高效率，把计算量减下来，如何把乘法取消（y=kx+b）? 1. 数值微分法DDA yi=kxi+b y(i+1)=kx(i+1)+b =k(xi+1)+b =kxi+k+b =kxi+b+k =yi+k 因此 y(i+1)=yi+k 式子含义是：当前步的y值等于前一步的y值加上斜率k
用DDA扫描转换连接两点P0(0，0)和P1(5，3)的直线段
此种方法只适应于斜率值k小于等于1时，当大于1时光栅点太稀疏了
2. 中点画线法 计算d的值，能否采用增量算法，提高运算效率 d(i+1)=di+?(增量)
<1 当d<0时，y=y+1 P是初始点，下一个像素点不是Pd就是Pu，去它们中间点M0，将M0带入d0 将M1带入d1
因此可得：d1=d0+A+B
<2 当d大于0时，y=y 将M1带入d1
因此可得，d1=d0+A
计算d的初始值d0，直线第一个像素P0(X0，Y0)在直线上，相应的d的初始值计算如下 （x0,y0）在直线上，而Ax0+By0+C等于直线方程，因此Ax0+By0+C=0 d0=A+0.5B
且d0=A+0.5B 我们判断d，不管大小，只看符号，所以可以用2d代替d来摆脱浮点运算，写出仅含整数运算的算法。这样，中点生成直线的算法提高到整数加法，优于DDA算法 DDA算法依赖于直线的斜截式方程：y=kx+b 中点画线法依赖于直线的一般式方程：Ax+By+C=0 因此能否提出一个算法，不仅能解决画直线问题，还能解决圆弧，抛物线甚至自由曲线的问题，就是下面的方法
3. Bresenham算法 DDA把算法效率提高到每步只做一个加法 中点算法把算法效率提高到每步只做一个整数加法 Bresenham算法的思想： 是通过各行，各列像素中心构造一组虚拟的网格线，按照直线起点到终点的顺序，计算直线与各垂直网格线的交点，然后根据误差项的符号确定该列像素中与此交点最近的像素 假设每次x+1，y的递增（减）量为0或1，它取决于实际直线与最近光栅网格点的距离，这个距离的最大误差为0.5（如图d>0.5时，就离上面的点近，取上面这个点） 误差项d的初始 d0=0 d=d+k 一旦d>=1，就把它减去1，保证d的相对性，且在0和1之间 因此： d>0.5，取上面的点，d<=0.5取下面的点
但如何将该算法效率提升到整数加法 改进： 另e=d-0.5 因为d0=0，因此e0=-0.5 e>0，y方向递增1，e<0，y方向不递增 e=0时，可任取上，下光栅点显示 每走一步 e=e+k 若e>0，e=e-1 给e=e+k同乘2△x 由于算法中只用到误差项的符号，于是可以用e*2*△x来替换e 因此： e0=-△x 每走一步：e=e+2△y 若e>0，e=e-2△x 算法步骤： DDA算法是每次求出一个新的y以后取整来画，而Bresrnham算法是判断符号来决定上下两个点
