资源描述：
《第5章基本图形生成算法》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、第5章基本图形生成算法提出问题如何在指定的输出设备上根据坐标描述构造基本二维几何图形（点、直线、圆、椭圆、多边形域、字符串及其相关属性等）。2021/6/101华中理工大学计算机学院陆枫99-7图形的生成：是在指定的输出设备上，根据坐标描述构造二维几何图形。图形的扫描转换：在光栅显示器等数字设备上确定一个最佳逼近于图形的象素集的过程。2021/6/102华中理工大学计算机学院陆枫99-75.1直线的扫描转换直线的绘制要求：1.直线要直2.直线的端点要准确，即无定向性和断裂情况3.直线的亮度、色泽要均匀4.画线
2、的速度要快5.要求直线具有不同的色泽、亮度、线型等2021/6/103华中理工大学计算机学院陆枫99-75.1.1数值微分法(DDA法)解决的问题：给定直线两端点P0(x0,y0)和P1(x1,y1)，画出该直线。直线的微分方程：2021/6/104华中理工大学计算机学院陆枫99-7DDA算法原理：ε=1/max(
3、△x
4、,
5、△y
6、)2021/6/105华中理工大学计算机学院陆枫99-7max(
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：2021
23、/6/106华中理工大学计算机学院陆枫99-7程序注意：round(x)=(int)(x+0.5)2021/6/107华中理工大学计算机学院陆枫99-7特点：增量算法直观、易实现不利于用硬件实现2021/6/108华中理工大学计算机学院陆枫99-75.1.2中点Bresenham算法直线的方程该直线方程将平面分为三个区域：对于直线上的点，F(x,y)=0；对于直线上方的点，F(x,y)>0；对于直线下方的点，F(x,y)<0。2021/6/109华中理工大学计算机学院陆枫99-72021/6/1010华中理工
24、大学计算机学院陆枫99-7基本原理：假定0≤k≤1，x是最大位移方向2021/6/1011华中理工大学计算机学院陆枫99-7判别式：则有：2021/6/1012华中理工大学计算机学院陆枫99-7误差项的递推d<0：2021/6/1013华中理工大学计算机学院陆枫99-7误差项的递推d≥0：2021/6/1014华中理工大学计算机学院陆枫99-7初始值d的计算2021/6/1015华中理工大学计算机学院陆枫99-70≤k≤1时Bresenham算法的算法步骤为：1.输入直线的两端点P0(x0,y0)和P1(x1
25、,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更新为d-k。4.当直线没有画完时，重复步骤3。否则结束。2021/6/1016华中理工大学计算机学院陆枫99-7改进：用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
26、<0，则(x,y)更新为(x+1,y+1)，d更新为d+2△x-2△y；否则(x,y)更新为(x+1,y),d更新为d-2△y。4.当直线没有画完时，重复步骤3。否则结束。程序2021/6/1017华中理工大学计算机学院陆枫99-75.1.3改进的Bresenham算法假定直线段的0≤k≤1基本原理：2021/6/1018华中理工大学计算机学院陆枫99-7误差项的计算d初=0，每走一步：d=d+k一旦y方向上走了一步，d=d-12021/6/1019华中理工大学计算机学院陆枫99-7算法步骤：1.输入直线的两
27、端点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。否则结束。2021/6/1020华中理工大学计算机学院陆枫99-7改进1：令e=d-0.5e初=-0.5，每走一步有e=e+k。if(e>0)thene=e-12021/6/1021华中理工大学计算机学院陆枫99
28、-7算法步骤为：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的符号。若e>0，则(x,y)更新为(x+1,y+1)，同时将e更新为e-1；否则(x,y)更新为(x+1,y)。5.当直线没有画完时，重复步骤3和4。否则结束。2021/6/1022华中理工大学计算机学院陆枫99-7
