第5章基本图形生成算法.PPT
《第5章基本图形生成算法.PPT》由会员分享,可在线阅读,更多相关《第5章基本图形生成算法.PPT(117页珍藏版)》请在淘文阁 - 分享文档赚钱的网站上搜索。
1、第5章基本图形生成算法 Still waters run deep.流静水深流静水深,人静心深人静心深 Where there is life,there is hope。有生命必有希望。有生命必有希望图图形形的的生生成成:是在指定的输出设备上,根据坐标描述构造二维几何图形。图图形形的的扫扫描描转转换换:在光栅显示器等数字设备上确定一个最佳逼近于图形的象素集的过程。2022/11/162华中理工大学计算机学院 陆枫 99-75.1 直线的扫描转换直线的扫描转换直线的绘制要求:直线的绘制要求:1.直线要直2.直线的端点要准确,即无定向性和断裂情况3.直线的亮度、色泽要均匀4.画线的速度要快5.要
2、求直线具有不同的色泽、亮度、线型等2022/11/163华中理工大学计算机学院 陆枫 99-75.1.1 数值微分法数值微分法(DDA法)解决的问题解决的问题:给定直线两端点P0(x0,y0)和P1(x1,y1),画出该直线。直线的微分方程:2022/11/164华中理工大学计算机学院 陆枫 99-7DDA算法原理算法原理:=1/max(|x|,|y|)2022/11/165华中理工大学计算机学院 陆枫 99-7max(|x|,|y|)=|x|,即|k|1的情况:max(|x|,|y|)=|y|,此时|k|1:2022/11/166华中理工大学计算机学院 陆枫 99-7程序程序注意注意:rou
3、nd(x)=(int)(x+0.5)2022/11/167华中理工大学计算机学院 陆枫 99-7特点特点:增量算法直观、易实现不利于用硬件实现2022/11/168华中理工大学计算机学院 陆枫 99-75.1.2 中点中点Bresenham算法算法直线的方程该直线方程将平面分为三个区域:对于直线上的点,F(x,y)=0;对于直线上方的点,F(x,y)0;对于直线下方的点,F(x,y)0。2022/11/169华中理工大学计算机学院 陆枫 99-72022/11/1610华中理工大学计算机学院 陆枫 99-7基本原理基本原理:假定0k1,x是最大位移方向2022/11/1611华中理工大学计算机
4、学院 陆枫 99-7判别式判别式:则有:2022/11/1612华中理工大学计算机学院 陆枫 99-7误差项的递推误差项的递推d0:2022/11/1613华中理工大学计算机学院 陆枫 99-7误差项的递推误差项的递推d0:2022/11/1614华中理工大学计算机学院 陆枫 99-7初始值初始值d的计算的计算2022/11/1615华中理工大学计算机学院 陆枫 99-70k1时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)
5、更新为(x+1,y+1),d更新为d+1-k;否则(x,y)更新为(x+1,y),d更新为d-k。4.当直线没有画完时,重复步骤3。否则结束。2022/11/1616华中理工大学计算机学院 陆枫 99-7改进改进:用2dx代替d1.输入直线的两端点P0(x0,y0)和P1(x1,y1)。2.计算初始值x、y、d=x-2y、x=x0、y=y0。3.绘制点(x,y)。判断d的符号。若d0.5,则(x,y)更新为(x+1,y+1),同时将d更新为d-1;否则(x,y)更新为(x+1,y)。5.当直线没有画完时,重复步骤3和4。否则结束。2022/11/1620华中理工大学计算机学院 陆枫 99-7改
6、进改进1:令e=d-0.5e初=-0.5,每走一步有e=e+k。if(e0)thene=e-12022/11/1621华中理工大学计算机学院 陆枫 99-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的符号。若e0,则(x,y)更新为(x+1,y+1),同时将e更新为e-1;否则(x,y)更新为(x+1,y)。5.当直线没有画完时,重复步骤3和4。否则结束。2022/11/1622华中理工大学计算机学院 陆枫 99-7改进改进2:用2ex来替换ee初=-x
7、,每走一步有e=e+2y。if(e0)thene=e-2x2022/11/1623华中科技大学计算机学院 陆枫算法步骤算法步骤: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。否则结束。2022/11/1624华中理工大学计算机学院 陆枫 99-7程序程序几种画线算法的比较2022/11/1625华中理工大学计算机学院 陆枫 99-
8、75.2 圆的扫描转换圆的扫描转换解决的问题:解决的问题:绘出圆心在原点,半径为整数R的圆x2+y2=R25.2.1 八分法画圆八分法画圆八分法画圆八分法画圆2022/11/1626华中理工大学计算机学院 陆枫 99-7(y,x)(-y,x)(-x,y)(-x,-y)(-y,-x)(y,-x)(x,-y)2022/11/1627华中理工大学计算机学院 陆枫 99-7解决问题解决问题:2022/11/1628华中理工大学计算机学院 陆枫 99-75.2.2 简单方程产生圆弧简单方程产生圆弧算法原理算法原理:利用其函数方程,直接离散计算圆的函数方程为:2022/11/1629华中理工大学计算机学院
9、 陆枫 99-7圆的极坐标方程为:2022/11/1630华中理工大学计算机学院 陆枫 99-75.2.3 中点中点Bresenham画圆画圆构造函数F(x,y)=x2-y2-R2。对于圆上的点,有F(x,y)=0;对于圆外的点,F(x,y)0;而对于圆内的点,F(x,y)0时,下一点取Pd(xi+1,yi-1)。M的坐标为:M(xi+1,yi-0.5)当F(xM,yM)0时,取Pd(xi+1,yi-1)当F(xM,yM)=0时,约定取Pu。构造判别式构造判别式:2022/11/1633华中理工大学计算机学院 陆枫 99-7误差项的递推误差项的递推d0:2022/11/1634华中理工大学计算
10、机学院 陆枫 99-7d0:2022/11/1635华中理工大学计算机学院 陆枫 99-7判别式的初始值判别式的初始值2022/11/1636华中理工大学计算机学院 陆枫 99-7算法步骤算法步骤:1.输入圆的半径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。否则结束。2022/11/1637华中理工大学计算机学院 陆枫 99-7改进:改进:
11、用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,再将(x,y)更新为(x+1,y-1)。5.当x0;对于椭圆内的点,F(x,y)0,取Pd(xi+1,yi-1)2022/11/1645华中理工大学计算机学院 陆枫 99-7误差项的递推误差项的递推d10:2022/11/1646华中理工大学计算机学院 陆枫 99-7d10:2022/11/1647华中理工大学计算机学
12、院 陆枫 99-7判别式的初始值判别式的初始值再来推导椭圆弧下半部分的绘制公式原理原理2022/11/1649华中理工大学计算机学院 陆枫 99-7判别式判别式若d20,取Pl(xi,yi-1)若d20,取Pr(xi+1,yi-1)2022/11/1650华中理工大学计算机学院 陆枫 99-7误差项的递推误差项的递推d20:2022/11/1651华中理工大学计算机学院 陆枫 99-7d20:2022/11/1652华中理工大学计算机学院 陆枫 99-7注意注意:上半部分的终止判别下半部分误差项的初值算法步骤算法步骤:1.输入椭圆的长半轴a和短半轴b。2.计算初始值d=b2+a2(-b+0.2
13、5)、x=0、y=b。3.绘制点(x,y)及其在四分象限上的另外三个对称点。2022/11/1653华中理工大学计算机学院 陆枫 99-74.判断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)0时,重复步骤7和8。否则结束。程序程序2022/11/1655华中理工大学计算机学院 陆枫 99-75.4 多边形的扫描转换与区域填充多边形的扫描转换与区域填充多多边边形形的的扫扫描描转转换换主要是通过确定穿越区域的扫描线的覆
14、盖区间来填充,区区域域填填充充是从给定的位置开始涂描直到指定的边界条件为止。2022/11/1656华中理工大学计算机学院 陆枫 99-75.4.1 多边形的扫描转换多边形的扫描转换顶点表示顶点表示用多边形的顶点序列来刻划多边形点阵表示点阵表示是用位于多边形内的象素的集合来刻划多边形扫扫描描转转换换多多边边形形或或多多边边形形的的填填充充:从多边形顶点表示到点阵表示的转换。1.什么是多边形的扫描转换2022/11/1657华中理工大学计算机学院 陆枫 99-72.x-扫描线算法基本思想基本思想2022/11/1658华中理工大学计算机学院 陆枫 99-7算法步骤算法步骤:(1)确定多边形所占有
15、的最大扫描线数,得到多边形顶点的最小和最大y值(ymin和ymax)。(2)从y=ymin到y=ymax,每次用一条扫描线进行填充。(3)对一条扫描线填充的过程可分为四个步骤:a.求交b.排序c.交点配对d.区间填色2022/11/1659华中理工大学计算机学院 陆枫 99-7存存在在问问题题:当扫描线与多边形顶点相交时,交点的取舍问题。2022/11/1660华中理工大学计算机学院 陆枫 99-7解决:当扫描线与多边形的顶点相交时,若共享顶点的两条边分别落在扫描线的两边,交点只算一个;若共享顶点的两条边在扫描线的同一边,这时交点作为零个或两个。2022/11/1661华中理工大学计算机学院
16、陆枫 99-7011110222填充过程实例2022/11/1662华中理工大学计算机学院 陆枫 99-73.改进的有效边表算法(改进的有效边表算法(Y连贯性算法)连贯性算法)改进原理改进原理:处理一条扫描线时,仅对有效边求交利用扫描线的连贯性利用多边形边的连贯性2022/11/1663华中理工大学计算机学院 陆枫 99-7有有效效边边(Active Edge):指与当前扫描线相交的多边形的边,也称为活性边。有有效效边边表表(Active Edge Table,AET):把有效边按与扫描线交点x坐标递增的顺序存放在一个链表中,此链表称为有效边表。有效边表的每个结点:xymax1/knext20
17、22/11/1664华中理工大学计算机学院 陆枫 99-7边表(边表(Edge Table)边表的构造:(1)首先构造一个纵向链表,链表的长度为多边形所占有的最大扫描线数,链表的每个结点,称为一个桶,则对应多边形覆盖的每一条扫描线。(2)将每条边的信息链入与该边最小y坐标(ymin)相对应的桶处。也就是说,若某边的较低端点为ymin,则该边就放在相应的扫描线桶中。2022/11/1665华中理工大学计算机学院 陆枫 99-7(3)每条边的数据形成一个结点,内容包括:该扫描线与该边的初始交点x(即较低端点的x值),1/k,以及该边的最大y值ymax。x|yminymax1/kNEXT(4)同一桶
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 基本 图形 生成 算法
限制150内