13-14(2)图形学-06

2020/6/6计算机图形学1计算机图形学基础主讲人：张睿哲[e-mail]2020/6/6计算机图形学2第六讲基本图形生成（五）提问八分圆思想中点画圆的基本思想怎样画圆心在任意点的圆34课前思考与知识回顾课前思考：什么叫区域填充？怎样进行区域填充？知识回顾：数据结构研究几种类型的数据？数据在计算机中有几种存储方式？什么叫链式存储结构？链表结点的结构怎样？链表适合于什么样的操作？5区域填充用某种颜色或图案来填充一个有界区域。填充区域：多边形填充任意区域的填充填充算法：扫描线填充算法---扫描线顺序有序边表算法边填充算法种子填充算法---内部一个点出发6多边形两种表示方法顶点表示：用多边形的顶点序列来表示多边形特点：直观、几何意义强、占内存少、易于进行几何变换，不能直接面着色点阵表示：用位于多边形内的像素集合来刻画多边形。特点：丢失了许多几何信息，但便于帧缓冲器表示图形，是面着色所需要的图形表示形式7多边形的扫描转换光栅图形学的一个基本问题是把多边形的顶点表示转换为点阵表示。这种转换称之为多边形的扫描转换。多边形的扫描转换本质是多边形填充，因此多边形扫描转换也是区域填充的一种。8多边形扫描转换思想多边形区域填充的一种常用方法是按扫描线顺序，计算扫描线与多边形的相交区间，再用要求的颜色显示这些区间的像素，即完成填充工作9多边形扫描转换步骤确定多边形所占有的最大扫描线数，得到多边形顶点的最小和最大y值（ymin和ymax）。从y=ymin到y=ymax，每次用一条扫描线进行填充。对一条扫描线填充的过程可分为四个步骤：a.求交b.排序c.交点配对d.区间填色10单条扫描线处理求交：计算扫描线与各多边形的交点。排序：把所有交点按x轴递增顺序排序。配对：第一个与第二个，第三个与第四个……填色：把交点对内的点设成多边形色，交点对外的点设成背景色。012345671234567yx88910扫描线5P4P1P2P3P5扫描线2I1I2I3I411交点的取舍问题当扫描线与多边形顶点相交时，存在交点的取舍问题。第5条扫描线和多边形有几个交点？第7条扫描线和多边形有几个交点？第1条扫描线和多边形有几个交点？12交点的取舍问题当扫描线与多边形的顶点相交时，若共享顶点的两条边分别落在扫描线的两边，交点只算一个；若共享顶点的两条边在扫描线的同一边，这时交点作为零个或两个。13交点的取舍问题14多边形扫描转换分析分析：影响扫描线填充算法效率因素有求交和排序。所有的边和扫描线求交，效率很低。交点计算涉及到浮点乘法运算。解决：处理扫描线时只对与它相交的直线进行处理。交点计算：x=x+1/k15数据存储分析每条扫描线所处理交点数目不定经常要进行添加和删除的操作。16有序边表算法一种采用链式存储结构的扫描线填充算法。相关概念：多边形填充进行求交运算时，与当前扫描线相交的多边形的边称为活性边。把活性边按与扫描线交点x坐标递增的顺序存放在一个链表中，此链表称为活化边表(或有序边表)。利用活化边表进行多边性填充的算法也被称为有序边表算法。17活化边表及结点有序边表的结点：扫描线5活化边表：012345671234567yx88910扫描线5P4P1P2P3P5扫描线2I1I2I3I4xymax1/knext17047-5/3862106018有序边表结构的定义typedefstructtEdge{floatx;/*当前扫描线与边的交点的x值*/floatdx;/*从当前扫描线到下一条扫描线之间的x增量*/intymax;/*边所交的最高扫描线号*/structtEdge*next;}Edge;19有序边表的使用更新a.求交：更新：链表的插入和删除b.排序c.交点配对27-1/3453/475-1/2991/220新边表为了方便有序边表的建立与更新，可以为每一条扫描线建立一个新边表，存放在该扫描线第一次出现的边。1234567891011123-1/3353/485-1/2891/21122/5712-1795p0p6721有序边表算法步骤输入欲填充多边形的顶点数及其顶点坐标。计算所有多边形顶点坐标中y的最大值和最小值，以此作为扫描线的处理范围。对处理范围内的每条扫描线建立新边表。对处理范围内的每条扫描线，重复下列步骤：用新边表建立当前扫描线的活化边表；从活化边表中依次取出一对交点，对该两个交点内的像素进行填充；为下一条扫描线更新活化边表，即增加交点的x值和删除不再相交的边；重排活化边表。