资源描述:
《《计算机图形学》全套ppt电子课件教案第5章基本图形生成算法》由会员上传分享,免费在线阅读,更多相关内容在教育资源-天天文库。
1、第5章基本图形生成算法提出问题如何在指定的输出设备上根据坐标描述构造基本二维几何图形(点、直线、圆、椭圆、多边形域、字符串及其相关属性等)。1图形的生成:是在指定的输出设备上,根据坐标描述构造二维几何图形。图形的扫描转换:在光栅显示器等数字设备上确定一个最佳逼近于图形的象素集的过程。25.1直线的扫描转换直线的绘制要求:1.直线要直2.直线的端点要准确,即无定向性和断裂情况3.直线的亮度、色泽要均匀4.画线的速度要快5.要求直线具有不同的色泽、亮度、线型等35.1.1数值微分法(DDA法)-(DigitalDifferentialAnalyzer)解决的问
2、题:给定直线两端点P0(x0,y0)和P1(x1,y1),画出该直线。直线的微分方程:4DDA算法原理:ε=1/max(
3、△x
4、,
5、△y
6、)5max(
7、△x
8、,
9、△y
10、)=
11、△x
12、,即
13、k
14、≤1的情况:max(
15、△x
16、,
17、△y
18、)=
19、△y
20、,此时
21、k
22、≥1:6程序注意:round(x)=(int)(x+0.5)7特点:增量算法直观、易实现不利于用硬件实现85.1.2中点Bresenham算法直线的方程该直线方程将平面分为三个区域:对于直线上的点,F(x,y)=0;对于直线上方的点,F(x,y)>0;对于直线下方的点,F(x,y)<0。910基本原理:假定0≤
23、k≤1,x是最大位移方向每次在最大位移方向上走一步,而另一个方向是走步还是不走步要取决于误差项的判别11判别式:则有:12误差项的递推d<0:判下一象素取?此时d增量为1-k13误差项的递推d≥0:判下一象素取?此时d增量为-k14初始值d的计算150≤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;否则(x,y)更新为(x+1,y),d更
24、新为d-k。4.当直线没有画完时,重复步骤3。否则结束。16改进:用2d△x代替d(因为只使用d符号,可摆脱小数)1.输入直线的两端点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。否则结束。程序175.1.3改进的Bresenham算法假定直线段的0≤k≤1基本原理:18误差项的计算d初=0,每走一步:
25、d=d+k一旦y方向上走了一步,d=d-119算法步骤: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。否则结束。20改进1:令e=d-0.5e初=-0.5,每走一步有e=e+k。if(e>0)thene=e-121算法步骤为:1.输入直线的两端点P0(x0,y0)和P1(x1,y1)。2.计
26、算初始值△x、△y、e=-0.5、x=x0、y=y0。3.绘制点(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。否则结束。22改进2:用2e△x来替换ee初=-△x,每走一步有e=e+2△y。if(e>0)thene=e-2△x23算法步骤:1.输入直线的两端点P0(x0,y0)和P1(x1,y1)。2.计算初始值△x、△y、e=-△x、x=x0、y=y0。3.绘制点(x,y)。4.e更新为e+2△y,判断e的符号。若
27、e>0,则(x,y)更新为(x+1,y+1),同时将e更新为e-2△x;否则(x,y)更新为(x+1,y)。5.当直线没有画完时,重复步骤3和4。否则结束。24程序几种画线算法的比较255.2圆的扫描转换解决的问题:绘出圆心在原点,半径为整数R的圆x2+y2=R25.2.1八分法画圆八分法画圆程序P11426(y,x)(-y,x)(-x,y)(-x,-y)(-y,-x)(y,-x)(x,-y)27解决问题:285.2.2简单方程产生圆弧算法原理:利用其函数方程,直接离散计算圆的函数方程为:CAI示例29圆的极坐标方程为:CAI示例305.2.3中点Brese
28、nham画圆构造函数F(x,y)=x2+y2-R2。