计算机图形学-第二章基本图形的生成与计算.ppt
《计算机图形学-第二章基本图形的生成与计算.ppt》由会员分享,可在线阅读,更多相关《计算机图形学-第二章基本图形的生成与计算.ppt(58页珍藏版)》请在三一办公上搜索。
1、第二章 基本图形的生成与计算,第一节 直线的扫描转换第二节 圆与椭圆的扫描转换 第三节 线画图元的属性控制,教学时数:8学时(含实验2学时)教学目的与要求:要求学生全面了解基本图形生成的各种算法,理解掌握直线、圆、椭圆生成的基本算法以及线划图元的属性控制方法,能通过编程实现各种算法。教学重点:直线、圆、椭圆生成的基本算法以及线划图元的属性控制方法,实验教学难点:直线、圆、椭圆生成的基本算法,本章主要阅读文献资料:1、刘大有主编:计算机图形学(第1版),机械工业出版社,2003年8月版。2、陈传波,陆枫编著:计算机图形学基础(第1版),电子工业出版社,2002年3月版。3、孙家广等:计算机图形学
2、(新版),清华大学出版社,1999年。,图形的扫描转换,图形的扫描转换,在光栅显示器上显示的任何一种图形,实际上都是一些具有一种或多种颜色的像素的集合。确定一个像素集合及其颜色,用于显示一个图形的过程,称为图形的扫描转换或光栅化。图形的扫描转换(光栅化):确定一个像素集合,用于显示一个图形的过程。步骤如下:1、确定有关像素。2、用图形的颜色或其它属性,对像素进行写操作。,所以扫描转换的主要工作是确定最佳逼近于图形的像素集。对一维图形,不考虑线宽,则用一个像素宽的直线来显示图形。二维图形的光栅化,即区域的填充:确定区域所对应的像素集,并用所要求的颜色或图案显示。任何图形的光栅化,必须显示在一个窗
3、口内,否则不予显示。即确定一个图形的哪些部分在窗口内,哪些在窗口外,即裁剪。裁剪通常在扫描转换之前进行。,21 直线的扫描转换,在数学上,理想的直线是没有宽度的,由无数个点构成的集合。我们只能在显示器所给定的有限个象素组成的矩阵中,确定最佳逼近于该直线的一组象素,并且按扫描顺序,用当前的写方式,对这些象素进行写操作。生成图形的常用算法有:数值微分法中点画线法Bresenham直线生成算法,21 直线的扫描转换一、数值微分法,数值微分法(digital differential analyzer,DDA)假定直线的起点、终点分别为:(x0,y0),(x1,y1),且都为整数。,21 直线的扫描转
4、换一、数值微分法,1、直接求交法求表示直线段P0P1的像素集的最简单方法是利用直线方程直接计算。假设待扫描转换的直线段为P0(x0,y0)P1(x1,y1),端点坐标均为整数 再令x=x1-x0,yy1-y0,斜率ky/x,直线方程为ykx+B。从直线的起点开始,确定最佳逼近于直线的直线,确定最佳逼近于直线的y坐标。让x从起点到终点变化,x每增加1对应的y坐标为y=kx+B,21 直线的扫描转换一、数值微分法,但是由于y值由y=kx+B计算而来,可能为浮点数,需要对y值取整对某个xi它所对应的yi=kxi+B的结果进行四舍五入,记为yi,rround(yi)(int)(yi+0.5),故对直线
5、段P0P1扫描实际得到像素集为(xi,yi,r),其中yi,r是yi四舍五入所得的整数值。这个方法直观,但效率太低,因为每一步需要一次浮点乘法和一次四舍五入取整运算。,21 直线的扫描转换一、数值微分法,2、增量算法注意到公式yi+1=kxi+1+B=k(xi+x)+B=kxi+B+kx=yi+kx因此当x=1时,有yi+1=yi+k,(xi+1,yi+k),(xi,round(yi),(x i,yi),栅格交点表示象素点位置,。,。,。,。,(xi+1,round(yi+k),21 直线的扫描转换一、数值微分法,所以:当x每递增1,y递增k(即直线斜率);注意上述分析的算法仅适用于k 1的情
6、形。在这种情况下,x每增加1,y最多增加1。当 k 1时,必须把x,y地位互换,大家自己依此处理,要保证任意两点连线正确显示。,21 直线的扫描转换一、数值微分法,增量算法:在一个迭代算法中,如果每一步的x、y值是用前一步的值加上一个增量来获得,则称为增量算法。DDA算法的本质是用数值方法解微分方程,通过同时对x和y各增加一个小增量,计算下一步的x,y值,因此DDA算法就是一个增量算法。缺点:在此算法中,y、m必须是float,且每一步都必须对y进行舍入取整,不利于硬件实现。,21 直线的扫描转换一、数值微分法,扫描转换直线段的DDA算法:void DDALine(int x0,int y0,
7、int x1,int y1,int color)int x;float dx,dy,y,k;dx=x1-x0;dy=y1-y0;k=dy/dx;y=y0;for(x=x0;x=x1;x+)drawpixel(x,(int)(y+0.5),color);/*以颜色color显示象素*/y=y+k;,21 直线的扫描转换一、数值微分法,例:画直线段P0(0,0)-P1(5,2)x int(y+0.5)y+0.5000+0.5100.4+0.5210.8+0.5311.2+0.5421.6+0.5522.0+0.5,21 直线的扫描转换二、中点画线法,原理:假定直线斜率0K1,若直线在x方向上增加一
8、个单位,则在y方向上的增量只能在0、1之间。假设已确定点亮象素点P(Xp,Yp),则下一个与直线最接近的像素只能是P1点或P2点。设M为中点,Q为交点现需确定下一个点亮的象素。,P,P2,P1,Q,21 直线的扫描转换二、中点画线法,当M在Q的下方-P2离直线更近更近-取P2。M在Q的上方-P1离直线更近更近-取P1M与Q重合,P1、P2任取一点。问题:如何判断M与Q点的关系?,假设直线的起点和终点分别为(x0,y0)和(x1,y1),则方程为:ax+by+c=0其中a=y0-y1,b=x1-x0,c=x0y1-x1y0由常识知:欲判断M点是在Q点上方还是在Q点下方,只需把M代入F(x,y),
9、并检查它的符号。,21 直线的扫描转换二、中点画线法,21 直线的扫描转换二、中点画线法,构造判别式:d=F(M)=F(xp+1,yp+0.5)=a(xp+1)+b(yp+0.5)+c当d0,M在直线(Q点)上方,取右方P1;当d=0,选P1或P2均可,约定取P1;能否采用增量算法呢?,P,P2,P1,Q,21 直线的扫描转换二、中点画线法,若d0-M在直线上方-取P1;此时再下一个象素的判别式为 d1=F(xp+2,yp+0.5)=a(xp+2)+b(yp+0.5)+c=a(xp+1)+b(yp+0.5)+c+a=d+a;增量为a若dM在直线下方-取P2;此时再下一个象素的判别式为 d2=F
10、(xp+2,yp+1.5)=a(xp+2)+b(yp+1.5)+c=a(xp+1)+b(yp+0.5)+c+a+b=d+a+b;增量为abd0=F(xp+1,yp+0.5)=a(xp+1)+b(yp+0.5)+c=axp+byp+c+a+0.5b=F(xp,yp)+a+0.5b=a+0.5b(2a+b),21 直线的扫描转换二、中点画线法,例:用中点画线法光栅化一条连接两点(0,0)和(5,2)的直线段。,x,y,d的初值和循环迭代过程中每一步的值,21 直线的扫描转换二、中点画线法,程序Midpointline(x0,y0,x1,y1,color)int x0,y0,x1,y1,color;
11、int a,b,d1,d2,d,x,y;a=y0-y1;b=x1 x0;d=2*a+b;d1=2*a;d2=2*(a+b);x=x0;y=y0;drawpixel(x,y,color);while(xx1)if(d0)x+;y+;d+=d2;else x+;d+=d1;drawpixel(x,y,color);该方法只适用于0=k=1的情形,其他情形大家自己依此处理,要保证任意两点连线正确显示,21 直线的扫描转换三、Bresenham画线算法,在直线生成的算法中Bresenham算法是最有效的算法之一。该方法最初是为数字绘图仪设计的,由于适用于光栅图形显示器,所以被广泛用于直线的扫描转换与其
12、他一些应用。令 k=y/x,就0k1的情况来说明Bresenham算法。Bresenham也是通过在每列像素中确定与理想直线最近的像素来进行直线的扫描转换的。算法原理:过各行、各列像素中心构造一组虚拟网格线,按直线从起点到终点的顺序计算直线与各垂直网格线的交点,然后确定该列像素中与此交点最近的像素,21 直线的扫描转换三、Bresenham画线算法,右图所示,线段两端点P0P1坐标分别为(x0,y0),(x1,y1),为整数,则起点P0的像素已经确定下一个像素的列坐标x必为x+1,行坐标要么不变,要么加1行坐标是否加1取决于误差项d,由于线段的起始点在像素中心,所以d的初始值为0,显然在直线P
13、0P1上,x每增加1,对应的d的值增加直线的斜率值k,d=d+k(k=dy/dx),一旦d=1则减去1因此d始终在0,1之间,21 直线的扫描转换三、Bresenham画线算法,令e=d-0.5,当e=0时,x增1,y增1当e0时,x增1,y不增加由于e=d-0.5并且d的初值为0,所以e的初值为-0.5,d,d,d,d,k,当d0.5时,直线与x+1列垂直网格线交点最接近于当前像素(x,y)的右上方像素(x+1,y+1);而当d0.5时,更接近于像素(x+1,y);当d0.5时,与上述二像素一样近,约定取(x+1,y+1)。,21 直线的扫描转换三、Bresenham画线算法,Bresenh
14、amLine(x0,y0,x1,y1,color)int x0,y0,x1,y1,color;int x,y,dx,dy;float k,e;int e;dx=x1-x0;dy=y1-y0;k=dy/dx;e=-0.5;x=x0;y=y0;e=-dx;x=x0;y=y0;for(i=0;i=0)y=y+1;e=e-1;y=y+1;e=e-2*dx;,e=e+k e=e+dy/dx 2*e*dx=2*e*dx+2dy令e=2*e*dx 则e=e+2dy 即将原来的e同时乘上2*dx,2-2 圆与椭圆的扫描转换一、圆弧的扫描转换,处理对象:圆心在原点的圆弧圆的八对称性,2-2 圆与椭圆的扫描转换一
15、、圆弧的扫描转换,圆弧的正负划分性,圆弧外的点:F(x,y)0圆弧内的点:F(x,y)0,2-2 圆与椭圆的扫描转换一、圆弧的扫描转换中点算法,考虑对象:第二个八分圆,第一象限的八分之一圆弧,P,P1,P2,2-2 圆与椭圆的扫描转换一、圆弧的扫描转换中点算法,问题:与直线情形类似圆弧的隐函数:F(X,Y)=X2+Y2-R2=0 切线斜率m in-1,0中点 M=(Xp+1,Yp-0.5),当F(M)0时,M在圆内,说明P1距离圆弧更近,取P1;当F(M)0时,P取P2,2-2 圆与椭圆的扫描转换一、圆弧的扫描转换中点算法,构造判别式 d=F(M)=F(Xp+1,Yp-0.5)=(Xp+1)2



- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 计算机 图形学 第二 基本 图形 生成 计算

链接地址:https://www.31ppt.com/p-6606244.html