资源描述：
《计算机图形学课件：第五章基本图形生成算法.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、第5章基本图形生成算法本章要解决的问题■如何在指定的输出设备上根据坐标描述构造基本二维几何图形。图形的生成：在指定的输出设备上，根据坐标描述构造二维几何图形。图形的扫描转换：在光栅显示器等数字设备上确定一个最佳逼近于图形的象素集的过程。5.1直线的扫描转换给定直线两端点P0(x0,y0)和P1(x1,y1)，画出该直线。要求：直、端点准确、色泽均匀、速度快等。■数值微分法(DDA法)直线的微分方程：DDA算法原理：ε=1/max(
2、△x
3、,
4、△y
5、)max(
6、△x
7、,
8、△y
9、)=
10、△x
11、，即
12、k
13、≤1的情况：max(
14、△x
15、,
16、△y
17、)=
18、△y
19、，此时
20、k
21、≥1：注：round(x)=(
22、int)(x+0.5)voidDDAline(intx0,inty0,intx1,inty1){intdx,dy,epsl,k;floatx,y,xIncre,yIncre;dx=x1-x0;dy=y1-y0;x=x0;y=y0;if(abs(dx)>abs(dy))epsl=abs(dx);elseepsl=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;}}特点：增量算
23、法直观、易实现不利于用硬件实现■中点Bresenham算法该直线方程将平面分为三个区域：对于直线上的点，F(x,y)=0；对于直线上方的点，F(x,y)>0；对于直线下方的点，F(x,y)<0。直线的方程：基本原理：假定0≤k≤1，x是最大位移方向判别式：则有：误差项的递推d<0：误差项的递推d≥0：初始值d的计算0≤k≤1时Bresenham算法的算法步骤为：1.输入直线的两端点P0(x0,y0)和P1(x1,y1)。2.计算初始值△x、△y、d=0.5-k、x=x0、y=y0；3.绘制点(x,y)。判断d的符号；若d<0，则(x,y)更新为(x+1,y+1)，d更新为d+1-k；否则
24、(x,y)更新为(x+1,y)，d更新为d-k。4.当直线没有画完时，重复步骤3。否则结束。改进：用2d△x代替d1.输入直线的两端点P0(x0,y0)和P1(x1,y1)。2.计算初始值△x、△y、d=△x-2△y、x=x0、y=y0。3.绘制点(x,y)。判断d的符号。若d<0，则(x,y)更新为(x+1,y+1)，d更新为d+2△x-2△y；否则(x,y)更新为(x+1,y),d更新为d-2△y。4.当直线没有画完时，重复步骤3。否则结束。2(0.5-k)△x=△x-2△y2(1-k)△x=2△x-2△y2(-k)△x=-2△yvoidMidBhline(intx0,inty0,i
25、ntx1,inty1){intdx,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(d<0){y++;d+=UpIncre;}elsed+=DownIncre;}}■改进的Bresenham算法假定直线段的0≤k≤1基本原理：误差项的计算d初=0，每走一步：d=d+k一旦y方向上
26、走了一步，d=d-1算法步骤：1.输入直线的两端点P0(x0,y0)和P1(x1,y1)。2.计算初始值△x、△y、d=0、x=x0、y=y0。3.绘制点(x,y)。4.d更新为d+k，判断d的符号。若d>0.5，则(x,y)更新为(x+1,y+1)，同时将d更新为d-1；否则(x,y)更新为(x+1,y)。5.当直线没有画完时，重复步骤3和4。否则结束。改进1：令e=d-0.5e初=-0.5，每走一步有e=e+k。if(e>0)thene=e-1算法步骤为：1.输入直线的两端点P0(x0,y0)和P1(x1,y1)。2.计算初始值△x、△y、e=-0.5、x=x0、y=y0。3.绘制点
27、(x,y)。4.e更新为e+k，判断e的符号。若e>0，则(x,y)更新为(x+1,y+1)，同时将e更新为e-1；否则(x,y)更新为(x+1,y)。5.当直线没有画完时，重复步骤3和4。否则结束。改进2：用2e△x来替换ee初=-△x，每走一步有e=e+2△y。if(e>0)thene=e-2△x算法步骤：1.输入直线的两端点P0(x0,y0)和P1(x1,y1)。2.计算初始值△x、△y、e=-△x、x=x0、y=y0。3.绘
