第二章 图形基元的显示 扫描转换 将图形描述转换成用象素矩阵表示的过程 图形基元（输出图形元素）图形系统能产生的最基本图形 线段、圆、多边形

第一节 点扫描转换 第二节 直线扫描转换算法 第三节 圆的扫描转换算法 第四节 区域填充

第一节 点扫描转换 将一个图形区域的数学点（x,y）转换为在（x’, y’）的像素点，这里x和y都是实数，实现的方法之一是取x的整数部分作为x’，取y的整数部分为y’。也就是x’=Floor(x), y’= Floor(y)。

另一种方法是用像素坐标排列（x,y）所在坐标系统的整数值；转换时，使用x’=Floor(x+0. 5)和y’=Floor(y+0 另一种方法是用像素坐标排列（x,y）所在坐标系统的整数值；转换时，使用x’=Floor(x+0.5)和y’=Floor(y+0.5), 这种情况把（x,y）所在坐标系统的原点放在像素（0，0）的中心。 满足：x’-0.5≤ x <x’+0.5; y’-0.5≤ y <y’+0.5。

第二节 直线扫描转换算法 直接使用直线方程转换 DDA直线扫描转换算法 中点画线法 Bresenham画线算法

直接使用直线方程转换: 设待画线段两端点的坐标值(x1,y1)和(x2,y2)，假定 x1<x2 y=mx+b m=(y2-y1)/(x2-x1) b=(x2y1-x1y2)/(x2-x1) 如果 对所有在x1和x2开区间之间的整数代入方程得到y值;

如果 对所有在y1和y2开区间之间的整数代入方程得到x值,最后生成扫描转换的坐标(x’,y’)。

DDA直线扫描转换算法: 数字微分分析算法（DDA）是一 种增量扫描转换方法，每一步要 用到上一步的结果。

当 时，对x每增加1取允许的各整数值，用y=mx+b求y后取整;

void DDALine(int x1,int y1,int x2,int y2) { double dx,dy,e,x,y; dx=x2-x1; dy=y2-y1; e=(fabs(dx)>fabs(dy))?fabs(dx):fabs(dy); dx/=e; dy/=e;

x=x1; y=y1; for(int i=1;i<=e;i++) { SetPixel((int)(x+0.5), (int)(y+0.5)); x+=dx; y+=dy; }

中点画线法：

假定直线斜率在0、1之间 x= xi时已选（xi，yi）象素 x= xi +1与直线最近的象素P1 ( xi + 1，yi )、 P2 ( xi+1，yi+1) M表示P1与P2的中点 M = ( xi+1，yi +0.5)。 Q是直线与垂直线x = xi + 1的交点 显然，若M在Q的下方，则P2离直线近，应取为下一个象素

中点画线法的实现： 起点和终点分别为 ( x0 , y0 ) 和( x1 , y1 )。 F(x , y) = ax + by + c = 0 其中，a=y0－y1，b=x1－x0，c=x0y1－x1y0 。 直线上的点，F (x，y) = 0 ； 直线上方的点，F(x，y)>0 ； 直线下方的点，F(x，y)<0。

Q在M 的上方还是下方，只要把M 代入F(x，y)，并判断它的符号。 d = F(M ) = F( xi+1，yi+0.5 ) =a ( xi+1 ) + b ( yi+0.5 ) + c 当 d < 0 时，M 在直线下方(即在Q的下方) ，应取右上方的P2 。 而当d > 0，则取正右方的P1。 当d=0时，二者一样合适，取P1。

d1 = F ( xi+2 ，yi+0.5 ) = a ( xi+2 ) + b ( yi+0.5 ) +c = d + a d≥0 时，取正右方象素P1 ，判断再下一个象素应取那个，应计算 d1 = F ( xi+2 ，yi+0.5 ) = a ( xi+2 ) + b ( yi+0.5 ) +c = d + a 故d的增量为a。 而若d<0，则取右上方向素P2。要判断下一个象素，则要计算

d2 = F ( xi+2，yi+1.5 ) = a ( xi+2 ) + b ( yi+1.5 ) + c = d + a + b 故在第二种情况，d的增量为a + b 再看d的初始值。显然，第一个象素应取左端点(x0，y0)，相应的判别式值为

但由于(x0，y0)在直线上，故F(x0，y0)=0。 因此，d的初始值为d0 = a+0.5b d0 = F (x0 +1，y0 +0.5 ) =a( x0 +1 )+b( y0 +0.5 )+c = a x0 + b y0 + c + a + 0.5b =F ( x0，y0 ) + a + 0.5b 但由于(x0，y0)在直线上，故F(x0，y0)=0。 因此，d的初始值为d0 = a+0.5b 考虑用2d来代替d的计算

void MidpointLine (int x0,int y0,int x1,int y1) { int a,b,delta1,delta2,d,x,y ; a = y0 - y1; b = x1 - x0; d = 2 * a + b ; delta1 = 2 * a ; delta2 = 2 *( a + b);

x = x0 ; y = y0 ; SetPixel(x,y); while( x<x1 ) { if( d<0 ) x ++; y ++;

d+= delta2; } else { x ++; d+= delta1; SetPixel(x,y); } /* while */ }/* MidpointLine */

作为一个例子，我们来看中点画线法如何光栅化一条连接两点(0，0)和(5，2)的直线段。由于(x0，y0)=(0，0)且(x1，y1)=(5，2)，直线斜率k = 2/5 满足0≤k≤1，所以，可以应用上述算法。

第一个象素应取线段左端点(0，0)。判别式d的初始值为d0 = 2 第一个象素应取线段左端点(0，0)。判别式d的初始值为d0 = 2 * a + b = 1（∵a = y0 -y1 = -2，b = x1 - x0 = 5）。d 往正右方向的增量Δ1 = 2a = -4；d 往右上方的增量Δ2 = 2(a + b)= 6。 由于d0＞0，所以迭代循环的第一步取初始点的正右方象素(1，0)，x递增1，并将d更新为：d = d0 +Δ1=1-4 = - 3。

因为x=1＜x1，所以进入第二步迭代运算。这时由于d＜0，故取右上方象素(2，1)，x、y同时递增1，并将d更新为：d = - 3+Δ2 = 3，这样继续分析下去知x、y、d的初值和循环迭代过程中每一步的值依序如下：

(0，0)、(5，2), a = y0 -y1 = -2，b = x1 - x0 = 5）d0 = 2 * a + b = 1 1 -3 2 3 -1 4 5  

Bresenham画线算法 : Bresenham提出了一个更好的算法，算法中可以只用整数运算，自然也不必有四舍五入。为了说明简便，假定直线斜率m在0到1之间，并且 。

设在第i步已经确定第i个象素点是 ，它是直线上点 的最接近位置 ，现在看第i+1步如何确定第i+1个象素点的位置。

,下一个象素点取 ，下一个象素点取 ，取两象素点中的任意一个

,应取

,应取 确定P1 , 令i=1，可计算求出：

void BresenhamLine(int x1,int y1,int x2,int y2) { int x,y,dx,dy,p; x=x1; y=y1; dx=x2-x1; dy=y2-y1; p=2*dy-dx; for(;x<=x2;x++)

SetPixel(x,y); if(p>=0) { y++; p+=2*(dy-dx); } else { p+=2*dy; 演示