图形学教案图形基元的显示市公开课一等奖百校联赛特等奖课件

第二章图形基元显示

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

10/10/第1页第一节点扫描转换第二节直线扫描转换算法

第三节圆扫描转换算法第四节区域填充

10/10/第2页第一节点扫描转换将一个图形区域数学点（x,y）转换为在（x’,y’）像素点，这里x和y都是实数，实现方法之一是取x整数部分作为x’，取y整数部分为y’。也就是x’=Floor(x),y’=Floor(y)。10/10/第3页另一个方法是用像素坐标排列（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。10/10/第4页第二节直线扫描转换算法直接使用直线方程转换DDA直线扫描转换算法中点画线法

Bresenham画线算法

10/10/第5页10/10/第6页直接使用直线方程转换:设待画线段两端点坐标值(x1,y1)和(x2,y2)，假定x1<x2y=mx+bm=(y2-y1)/(x2-x1)b=(x2y1-x1y2)/(x2-x1)

假如

对全部在x1和x2开区间之间整数代入方程得到y值;10/10/第7页假如

对全部在y1和y2开区间之间整数代入方程得到x值,最终生成扫描转换坐标(x’,y’)。10/10/第8页DDA直线扫描转换算法:数字微分分析算法（DDA）是一种增量扫描转换方法，每一步要用到上一步结果。10/10/第9页当

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

时，对x和y值交换，进行处理。10/10/第10页voidDDALine(intx1,inty1,intx2,inty2){ doubledx,dy,e,x,y;dx=x2-x1;dy=y2-y1;e=(fabs(dx)>fabs(dy))?fabs(dx):fabs(dy); dx/=e; dy/=e;10/10/第11页x=x1; y=y1; for(inti=1;i<=e;i++) { SetPixel((int)(x+0.5),(int)(y+0.5)); x+=dx; y+=dy; }}10/10/第12页中点画线法：10/10/第13页

假定直线斜率在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离直线近，应取为下一个象素10/10/第14页中点画线法实现：起点和终点分别为(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。10/10/第15页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。10/10/第16页

对每一个象素计算判别式d，依据它符号确定下一象素。

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。要判断下一个象素，则要计算10/10/第17页d2=F(xi+2，yi+1.5)=a(xi+2)+b(yi+1.5)+c=d+a+b故在第二种情况，d增量为a+b再看d初始值。显然，第一个象素应取左端点(x0，y0)，对应判别式值为

10/10/第18页d0=F(x0+1，y0+0.5)=a(x0+1)+b(y0+0.5)+c=ax0+by0+c+a+0.5b

=F(x0，y0)+a+0.5b但因为(x0，y0)在直线上，故F(x0，y0)=0。所以，d初始值为d0=a+0.5b考虑用2d来代替d计算10/10/第19页voidMidpointLine(intx0,inty0,intx1,inty1){ inta,b,delta1,delta2,d,x,y; a=y0-y1; b=x1-x0; d=2*a+b; delta1=2*a; delta2=2*(a+b);10/10/第20页x=x0; y=y0; SetPixel(x,y); while(x<x1) { if(d<0) { x++; y++;10/10/第21页d+=delta2; } else{ x++; d+=delta1; } SetPixel(x,y); }/*while*/}/*MidpointLine*/10/10/第22页

作为一个例子，我们来看中点画线法怎样光栅化一条连接两点(0，0)和(5，2)直线段。因为(x0，y0)=(0，0)且(x1，y1)=(5，2)，直线斜率k=2/5

满足0≤k≤1，所以，能够应用上述算法。

10/10/第23页第一个象素应取线段左端点(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。

10/10/第24页因为x=1＜x1，所以进入第二步迭代运算。这时因为d＜0，故取右上方象素(2，1)，x、y同时递增1，并将d更新为：d=-3+Δ2

=3，这么继续分析下去知x、y、d初值和循环迭代过程中每一步值依序以下：

10/10/第25页xyd00110-321331-1425521

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

a+b=1

10/10/第26页Bresenham画线算法:Bresenham提出了一个更加好算法，算法中能够只用整数运算，自然也无须有四舍五入。为了说明简便，假定直线斜率m在0到1之间，而且。10/10/第27页设在第i步已经确定第i个象素点是，它是直线上点最靠近位置，现在看第i+1步怎样确定第i+1个象素点位置。10/10/第28页,下一个象素点取

，下一个象素点取，取两象素点中任意一个10/10/第29页,应取10/10/第30页,应取

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

10/10/第31页voidBresenhamLine(intx1,inty1,intx2,inty2