《图形学教案第二章图形基元的显示.ppt》由会员分享，可在线阅读，更多相关《图形学教案第二章图形基元的显示.ppt（33页珍藏版）》请在三一办公上搜索。
1、14:02:20,第二章 图形基元的显示,扫描转换 将图形描述转换成用象素矩阵表示的过程图形基元（输出图形元素）图形系统能产生的最基本图形 线段、圆、多边形,14:02:20,第一节 点扫描转换第二节 直线扫描转换算法 第三节 圆的扫描转换算法第四节 区域填充,14:02:20,第一节 点扫描转换,将一个图形区域的数学点（x,y）转换为在（x,y）的像素点，这里x和y都是实数，实现的方法之一是取x的整数部分作为x，取y的整数部分为y。也就是x=Floor(x),y=Floor(y)。,14:02:20,另一种方法是用像素坐标排列（x,y）所在坐标系统的整数值；转换时，使用x=Floor(x+0
2、.5)和y=Floor(y+0.5),这种情况把（x,y）所在坐标系统的原点放在像素（0，0）的中心。满足：x-0.5 x x+0.5;y-0.5 y y+0.5。,14:02:20,第二节 直线扫描转换算法,直接使用直线方程转换DDA直线扫描转换算法中点画线法 Bresenham画线算法,14:02:20,14:02:20,直接使用直线方程转换:设待画线段两端点的坐标值(x1,y1)和(x2,y2)，假定 x1x2 y=mx+b m=(y2-y1)/(x2-x1)b=(x2y1-x1y2)/(x2-x1)如果 对所有在x1和x2开区间之间的整数代入方程得到y值;,14:02:20,如果 对所
3、有在y1和y2开区间之间的整数代入方程得到x值,最后生成扫描转换的坐标(x,y)。,14:02:20,DDA直线扫描转换算法:,数字微分分析算法（DDA）是一种增量扫描转换方法，每一步要用到上一步的结果。,14:02:20,当 时，对x每增加1取允许的各整数值，用y=mx+b求y后取整;当 时，对x和y值互换，进行处理。,14:02:20,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;,
4、14:02:20,x=x1;y=y1;for(int i=1;i=e;i+)SetPixel(int)(x+0.5),(int)(y+0.5);x+=dx;y+=dy;,14:02:20,中点画线法：,14:02:20,假定直线斜率在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离直线近，应取为下一个象素,14:02:20,中点画线法的实现：起点和终点分别为(x0,y0)和(x1,y1)。F(x,y)=a
5、x+by+c=0其中，a=y0y1，b=x1x0，c=x0y1x1y0。直线上的点，F(x，y)=0；直线上方的点，F(x，y)0；直线下方的点，F(x，y)0。,14:02:20,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，则取正右方的P1。当d=0时，二者一样合适，取P1。,14:02:20,对每一个象素计算判别式d，根据它的符号确定下一象素。d0 时，取正右方象素P1，判断再下一个象素应取那个，应计算d1=F(xi+2，yi+0.5)=a(xi+2)+b(yi+0.5)+
6、c=d+a故d的增量为a。而若d0，则取右上方向素P2。要判断下一个象素，则要计算,14:02:20,d2=F(xi+2，yi+1.5)=a(xi+2)+b(yi+1.5)+c=d+a+b故在第二种情况，d的增量为a+b 再看d的初始值。显然，第一个象素应取左端点(x0，y0)，相应的判别式值为,14:02:20,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的计算,14:02:20,vo
7、id 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);,14:02:20,x=x0;y=y0;SetPixel(x,y);while(xx1)if(d0)x+;y+;,14:02:20,d+=delta2;else x+;d+=delta1;SetPixel(x,y);/*while*/*MidpointLine*/,14:02:20,作为一个例子，我们来看中点画线法如何光栅化一条连接两点(0，0)和(5，
8、2)的直线段。由于(x0，y0)=(0，0)且(x1，y1)=(5，2)，直线斜率k=2/5 满足0k1，所以，可以应用上述算法。,14:02:20,第一个象素应取线段左端点(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。由于d00，所以迭代循环的第一步取初始点的正右方象素(1，0)，x递增1，并将d更新为：d=d0+1=1-4=-3。,14:02:20,因为x=1x1，所以进入第二步迭代运算。这时由于d0，故取右上方象素(2，1)，x、y同时递增1，并将d更新为：d=-
9、3+2=3，这样继续分析下去知x、y、d的初值和循环迭代过程中每一步的值依序如下：,14:02:20,(0，0)、(5，2),a=y0-y1=-2，b=x1-x0=5）d0=2*a+b=1,14:02:20,Bresenham画线算法:Bresenham提出了一个更好的算法，算法中可以只用整数运算，自然也不必有四舍五入。为了说明简便，假定直线斜率m在0到1之间，并且。,14:02:20,设在第i步已经确定第i个象素点是，它是直线上点 的最接近位置，现在看第i+1步如何确定第i+1个象素点的位置。,14:02:20,下一个象素点取,，下一个象素点取,，取两象素点中的任意一个,14:02:20,应取,14:02:20,应取,确定P1,令i=1，可计算求出：,14:02:20,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+),14:02:20,SetPixel(x,y);if(p=0)y+;p+=2*(dy-dx);elsep+=2*dy;,演示,
