图形学教案第二章图形基元的显示.ppt

第二章第二章 图形基元的显示图形基元的显示 •扫描转换扫描转换 将图形描述转换成将图形描述转换成用象素矩阵表示的过程用象素矩阵表示的过程•图形基元（输出图形元素）图形基元（输出图形元素）图形系统能产生的最基本图图形系统能产生的最基本图形形 •线段、圆、多边形线段、圆、多边形 9/4/2024•第一节第一节 点扫描转换点扫描转换•第二节第二节 直线扫描转换算法直线扫描转换算法 •第三节第三节 圆的扫描转换算法圆的扫描转换算法•第四节第四节 区域填充区域填充 9/4/2024第一节第一节 点扫描转换点扫描转换•将一个图形区域的数学点（x,y）转换为在（x’, y’）的像素点，这里x和y都是实数，实现的方法之一是取x的整数部分作为x’，取y的整数部分为y’也就是x’=Floor(x), y’= Floor(y) 9/4/2024•另一种方法是用像素坐标排列（x,y）所在坐标系统的整数值；转换时，使用x’=Floor(x+0.5)和y’=Floor(y+0.5), 这种情况把（x,y）所在坐标系统的原点放在像素（0，0）的中心 满足：x’-0.5≤≤ x

9/4/2024第二节第二节 直线扫描转换算法直线扫描转换算法•直接使用直线方程转换直接使用直线方程转换•DDADDA直线扫描转换算法直线扫描转换算法•中点画线法中点画线法 •BresenhamBresenham画线算法画线算法 9/4/20249/4/2024 直接使用直线方程转换直接使用直线方程转换: : 设待画线段两端点的坐标值设待画线段两端点的坐标值(x1,y1)(x1,y1)和和(x2,y2)(x2,y2)，，假定假定 x1

用到上一步的结果9/4/2024 当 时，对x每增加1取允许的各整数值，用y=mx+b求y后取整; 当 时，对x和y值互换，进行处理9/4/2024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;9/4/2024 x=x1;y=y1;for(int i=1;i<=e;i++){SetPixel((int)(x+0.5), (int)(y+0.5)); x+=dx;y+=dy;}}9/4/2024中点画线法：中点画线法：9/4/2024 假定直线斜率在假定直线斜率在0 0、、1 1之间之间x= x= x xi i时已选（时已选（x xi i，，y yi i））象素象素x= x= x xi i +1+1与直线最近的象素与直线最近的象素P P1 1 ( ( x xi i + 1+ 1，，y yi i ) )、、 P P2 2 ( ( x xi i+1+1，，y yi i+1)+1) M M表示表示P P1 1与与P P2 2的中点的中点 M = ( M = ( x xi i+1+1，，y yi i +0.5)+0.5)。

Q Q是直线与垂直线是直线与垂直线x x = = x xi i + 1+ 1的交点的交点显然，若显然，若M M在在Q Q的下方，则的下方，则P P2 2离直线近，离直线近，应取为下一个象素应取为下一个象素 9/4/2024中点画线法的实现：中点画线法的实现：起起点点和和终终点点分分别别为为 ( ( x x0 0 , , y y0 0 ) ) 和和( ( x x1 1 , , y y1 1 ) )F F( (x x , , y y) ) = = ax ax + + by by + + c c = 0 = 0其其中中，，a a= =y y0 0－－y y1 1，，b b= =x x1 1－－x x0 0，，c c= =x x0 0y y1 1－－x x1 1y y0 0 直线上的点，直线上的点，F F ( (x x，，y y) = 0 ) = 0 ；；直线上方的点，直线上方的点，F F( (x x，，y y)>0)>0 ；；直线下方的点，直线下方的点，F F( (x x，，y y)<0)<09/4/2024Q Q在在M M 的上方还是下方，只要把的上方还是下方，只要把M M 代代入入F F( (x x，，y y) )，，并判断它的符号。

并判断它的符号 d d = = F F( (M M ) ) = = F F( ( x xi i+1+1，，y yi i+0.5 ) +0.5 ) = =a a ( ( x xi i+1 ) ++1 ) + b b ( ( y yi i+0.5 ) ++0.5 ) + c c当当 d d < 0 < 0 时，时，M M 在直线下方在直线下方( (即在即在Q Q的下方的下方) ) ，应取右上方的，应取右上方的P P2 2 而当而当d d > 0 > 0，，则取正右方的则取正右方的P P1 1当当d d=0=0时，二者一样合适，取时，二者一样合适，取P P1 19/4/2024 对对每每一一个个象象素素计计算算判判别别式式d d，，根根据据它的符号确定下一象素它的符号确定下一象素 d d≥0 ≥0 时时，，取取正正右右方方象象素素P P1 1 ，，判判断断再下一个再下一个象素应取那个，应计算象素应取那个，应计算d d1 1 = = F F ( ( x xi i+2 +2 ，，y yi i+0.5+0.5 ) ) = = a a ( ( x xi i+2 )+2 ) + + b b ( ( y yi i+0.5 ) ++0.5 ) +c c = = d d + + a a故故d d的增量为的增量为a a。

而而若若d d<0<0，，则则取取右右上上方方向向素素P P2 2要要判判断下一个象素，则要计算断下一个象素，则要计算9/4/2024d d2 2 = = F F ( ( x xi i+2+2，，y yi i+1.5 )+1.5 )= = a a ( ( x xi i+2 ) + +2 ) + b b ( ( y yi i+1.5 ) + +1.5 ) + c c= = d d + + a a + + b b故在第二种情况，故在第二种情况，d d的增量为的增量为a a + + b b 再看再看d d的初始值显然，第一个象素的初始值显然，第一个象素应取左端点应取左端点( (x x0 0，，y y0 0) )，，相应的判别式相应的判别式值为值为 9/4/2024d d0 0 = = F F ( (x x0 0 +1+1，，y y0 0 +0.5 ) +0.5 ) =a( =a( x x0 0 +1 )++1 )+b b( ( y y0 0 +0.5 )++0.5 )+c c= = a x a x0 0 + + b yb y0 0 + + c c + + a a + 0.5 + 0.5b b = =F F ( ( x x0 0，，y y0 0 ) + ) + a a + 0.5 + 0.5b b 但由于但由于( (x x0 0，，y y0 0) )在直线上，故在直线上，故F F( (x x0 0，，y y0 0)=0)=0。

因此，因此，d d的初始值为的初始值为d d0 0 = = a a+0.5+0.5b b考虑用考虑用2 2d d来代替来代替d d的的计算计算9/4/2024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);9/4/2024 x = x0 ;y = y0 ;SetPixel(x,y);while( x

9/4/2024 第一个象素应取线段左端点(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 9/4/2024 因为x=1＜x1，所以进入第二步迭代运算这时由于d＜0，故取右上方象素(2，1)，x、y同时递增1，并将d更新为：d = - 3+Δ2 = 3，这样继续分析下去知x、y、d的初值和循环迭代过程中每一步的值依序如下： 9/4/2024xyd00110-321331-1425521  (0，，0)、、(5，，2), a = y0 - -y1 = - -2，，b = x1 - - x0 = 5））d d0 0 = 2 = 2 * * a a + + b b = 1 = 1 9/4/2024BresenhamBresenham画线算法画线算法 : Bresenham提出了一个更好的算法，算法中可以只用整数运算，自然也不必有四舍五入。

为了说明简便，假定直 线 斜 率m在 0到 1之 间 ， 并 且 9/4/2024设在第设在第i i步已经步已经确定第确定第i i个象素个象素点是点是 ，它，它是直线上点是直线上点 的最接近位置的最接近位置 ，现在看第，现在看第i i+1+1步如何确定第步如何确定第i i+1+1个象素点的个象素点的位置 9/4/2024,下一个象素点取 ，下一个象素点取 ，取两象素点中的任意一个 9/4/2024,应取9/4/2024,应取 确定P1 ,令i=1，可计算求出： 9/4/2024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++){9/4/2024SetPixel(x,y);if(p>=0){ y++;p+=2*(dy-dx);}else{p+=2*dy;}}}演示演示9/4/2024。