计算机图形学教案第5章基本图形生成算法.ppt
《计算机图形学教案第5章基本图形生成算法.ppt》由会员分享,可在线阅读,更多相关《计算机图形学教案第5章基本图形生成算法.ppt(129页珍藏版)》请在三一办公上搜索。
1、第5章 基本图形生成算法,本章要解决的问题 如何在指定的输出设备上根据坐标描述构造基本二维几何图形。,图形的生成:在指定的输出设备上,根据坐标描述构造二维几何图形。图形的扫描转换:在光栅显示器等数字设备上确定一个最佳逼近于图形的象素集的过程(连续图形到象素集的转换)。,5.1 直线的扫描转换,给定直线两端点P0(x0,y0)和P1(x1,y1),画出该直线。要求:直、端点准确、色泽均匀、速度快等。,数值微分法(DDA法),直线的微分方程:,DDA算法原理:,=1/max(|x|,|y|),max(|x|,|y|)=|x|,即|k|1的情况:,max(|x|,|y|)=|y|,此时|k|1:,注
2、:round(x)=(int)(x+0.5),void DDAline(int x0,int y0,int x1,int y1)int dx,dy,epsl,k;float x,y,xIncre,yIncre;dx=x1-x0;dy=y1-y0;x=x0;y=y0;if(abs(dx)abs(dy)epsl=abs(dx);else epsl=abs(dy);xIncre=(float)(dx)/epsl;yIncre=(float)(dy)/epsl;for(k=0;k=epsl;k+)putpixel(int)(x+0.5),(int)(y+0.5);x+=xIncre;y+=yIncre
3、;,特点:增量算法直观、易实现不利于用硬件实现,中点Bresenham算法,该直线方程将平面分为三个区域:对于直线上的点,F(x,y)=0;对于直线上方的点,F(x,y)0;对于直线下方的点,F(x,y)0。,直线的方程:,基本原理:假定0k1,x是最大位移方向,判别式:,则有:,误差项的递推d0:,误差项的递推d0:,初始值d的计算,0k1时Bresenham算法的算法步骤为:1.输入直线的两端点P0(x0,y0)和P1(x1,y1)。2.计算初始值x、y、d=0.5-k、x=x0、y=y0;3.绘制点(x,y)。判断d的符号;若d0,则(x,y)更新为(x+1,y+1),d更新为d+1-k
4、;否则(x,y)更新为(x+1,y),d更新为d-k。4.当直线没有画完时,重复步骤3。否则结束。,改进:用2dx代替d1.输入直线的两端点P0(x0,y0)和P1(x1,y1)。2.计算初始值x、y、d=x-2y、x=x0、y=y0。3.绘制点(x,y)。判断d的符号。若d0,则(x,y)更新为(x+1,y+1),d更新为 d+2x-2y;否则(x,y)更新为(x+1,y),d更新为d-2y。4.当直线没有画完时,重复步骤3。否则结束。,2(0.5-k)x=x-2y,2(1-k)x=2x-2y,2(-k)x=-2y,void MidBhline(int x0,int y0,int x1,in
5、t y1)int dx,dy,d,UpIncre,DownIncre,x,y,xend;if(x0 x1)x=x1;x1=x0;x0=x;y=y1;y1=y0;y0=y;x=x0;y=y0;dx=x1-x0;dy=y1-y0;d=dx-2*dy;UpIncre=2*dx-2*dy;DownIncre=-2*dy;while(x=x1)putpixel(x,y);x+;if(d0)y+;d+=UpIncre;else d+=DownIncre;,改进的Bresenham算法,假定直线段的0k1基本原理:,误差项的计算d初=0,每走一步:d=d+k 一旦y方向上走了一步,d=d-1,算法步骤:1.
6、输入直线的两端点P0(x0,y0)和P1(x1,y1)。2.计算初始值x、y、d=0、x=x0、y=y0。3.绘制点(x,y)。4.d更新为d+k,判断d的符号。若d0.5,则(x,y)更新为(x+1,y+1),同时将d更新为d-1;否则(x,y)更新为(x+1,y)。5.当直线没有画完时,重复步骤3和4。否则结束。,改进1:令e=d-0.5,e初=-0.5,每走一步有e=e+k。if(e0)then e=e-1,算法步骤为:1.输入直线的两端点P0(x0,y0)和P1(x1,y1)。2.计算初始值x、y、e=-0.5、x=x0、y=y0。3.绘制点(x,y)。4.e更新为e+k,判断e的符号
7、。若e0,则(x,y)更新为(x+1,y+1),同时将e更新为e-1;否则(x,y)更新为(x+1,y)。5.当直线没有画完时,重复步骤3和4。否则结束。,改进2:用2ex来替换ee初=-x,每走一步有e=e+2y。if(e0)then e=e-2x,算法步骤:1.输入直线的两端点P0(x0,y0)和P1(x1,y1)。2.计算初始值x、y、e=-x、x=x0、y=y0。3.绘制点(x,y)。4.e更新为e+2y,判断e的符号。若e0,则(x,y)更新为(x+1,y+1),同时将e更新为e-2x;否则(x,y)更新为(x+1,y)。5.当直线没有画完时,重复步骤3和4。否则结束。,void B
8、hline(int x0,int y0,int x1,int y1)int x,y,dx,dy,e;if(x0 x1)x=x1;x1=x0;x0=x;y=y1;y1=y0;y0=y;dx=x1-x0;dy=y1-y0;x=x0;y=y0;e=-dx;while(x0)y+;e=e-2*dx;,思考题,对于前述几种直线生成算法和程序:1.当最大位移方向是y时,应如何修改?2.要达到通用时,应如何修改?,5.2 圆的扫描转换,解决的问题:绘出圆心在原点,半径为整数R的圆x2+y2=R2,八分法画圆,(y,x),(-y,x),(-x,y),(-x,-y),(-y,-x),(y,-x),(x,-y),
9、解决问题:,八分法画圆程序:,void circlePoint(int x,int y)putpixel(x,y);putpixel(y,x);putpixel(-y,x);putpixel(-x,y);putpixel(-x,-y);putpixel(-y,-x);putpixel(y,-x);putpixel(x,-y);,考虑通用:,void circlePoint(int x0,int y0,int x,int y)putpixel(x-x0,y-y0);putpixel(y-x0,x-y0);putpixel(-y+x0,x-y0);putpixel(-x+x0,y-y0);putp
10、ixel(-x+x0,-y+y0);putpixel(-y+x0,-x+y0);putpixel(y-x0,-x+y0);putpixel(x-x0,-y+y0);,简单方程产生圆弧,算法原理:利用其函数方程,直接离散计算,圆的函数方程为:,圆的极坐标方程为:,中点Bresenham画圆,构造函数F(x,y)=x2-y2-R2。对于圆上的点,有F(x,y)=0;对于圆外的点,F(x,y)0;而对于圆内的点,F(x,y)0。算法原理,当d0时:下一点取Pu(xi+1,yi);当d0时:下一点取Pd(xi+1,yi-1)。,构造判别式:,误差项的递推d0:,d0:,判别式的初始值,算法步骤:1.输
11、入圆的半径R。2.计算初始值d=1.25-R、x=0、y=R。3.绘制点(x,y)及其在八分圆中的另外七个对称点。4.判断d的符号。若d0,则先将d更新为d+2x+3,再将(x,y)更新为(x+1,y);否则先将d更新为d+2(x-y)+5,再将(x,y)更新为(x+1,y-1)。5.当xy时,重复步骤3和4。否则结束。,改进:用d-0.25代替d算法步骤:1.输入圆的半径R。2.计算初始值d=1-R、x=0、y=R。3.绘制点(x,y)及其在八分圆中的另外七个对称点。4.判断d的符号。若d0,则先将d更新为d+2x+3,再将(x,y)更新为(x+1,y);否则先将d更新为d+2(x-y)+5
12、,再将(x,y)更新为(x+1,y-1)。5.当xy时,重复步骤3和4。否则结束。,d 0.25,中点Bh画圆程序,void MidBhcircle(int r)int x,y,d;x=0;y=r;d=1-r;while(xy)circlePoint(x,y);if(d0)d+=2*x+3;else d+=2*(x-y)+5;y-;x+;,5.3 椭圆的扫描转换,椭圆的特征,椭圆上:F(x,y)=0椭圆内:F(x,y)0只需计算第一象限,四分椭圆,以弧上斜率为1的点作为分界将第一象限椭圆弧分为上下两部分。,两部分的最大位移方向不同,引理5-1:若在当前中点,法向量的y分量比x分量大,即,而在下
13、一个中点,不等号改变方向,则说明椭圆弧从上部分转入下部分。,法向量,椭圆的中点Bresenham算法,算法原理,x步长为1,y步长为1,先推导上半部分的椭圆绘制公式,判别式,若d10,取Pu(xi+1,yi)若d10,取Pd(xi+1,yi-1),误差项的递推d10:,d10:,判别式的初始值,再来推导椭圆弧下半部分的绘制公式原理,判别式,若d20,取Pl(xi,yi-1)若d20,取Pr(xi+1,yi-1),5-19 下半部分椭圆弧的绘制原理,误差项的递推d20:,d20:,注意:上半部分的终止判别:b2(x+1)a2(y-0.5)下半部分误差项的初值:用上半部的(x,y)计算算法步骤:1
14、.输入椭圆的长半轴a和短半轴b。2.计算初始值d=b2+a2(-b+0.25)、x=0、y=b。3.绘制点(x,y)及其在四分象限上的另外三个对称点。,4.判断d的符号。若d0,则先将d更新为d+b2(2x+3),再将(x,y)更新为(x+1,y);否则先将d更新为d+b2(2x+3)+a2(-2y+2),再将(x,y)更新为(x+1,y-1)。5.当b2(x+1)a2(y-0.5)时,重复步骤3和4。否则转到步骤6。6.用上半部分计算的最后点(x,y)来计算下半部分中d的初值:,7.绘制点(x,y)及其在四分象限上的另外三个对称点。8.判断d的符号。若d0,则先将d更新为b2(2xi+2)+
15、a2(-2yi+3),再将(x,y)更新为(x+1,y-1);否则先将d更新为d+a2(-2yi+3),再将(x,y)更新为(x,y-1)。9.当y0时,重复步骤7和8。否则结束。,第一象限椭圆弧的扫描转换程序,void MidBhllipse(int a,int b)int x,y;float d1,d2;x=0;y=b;d1=b*b+a*a*(-b+0.25);putpixel(x,y);putpixel(-x,-y);putpixel(-x,y);putpixel(x,-y);,while(b*b*(x+1)a*a*(y-0.5)if(d1=0)d1+=b*b*(2*x+3);x+;el
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 计算机 图形学 教案 基本 图形 生成 算法
![提示](https://www.31ppt.com/images/bang_tan.gif)
链接地址:https://www.31ppt.com/p-6606248.html