第四讲：其本图元输出2解读.ppt

第四讲：基本图元的光栅化（2） Output Primitives 4.1区域填充 有两种方法可以完成区域的填充，一种方法是在扫描时，确定扫描线跨越区域的部分，并填充该部分。另一种方法是从区域内的一点（种子点）开始第规的向外扩展，直到遇到边界为止。扫描线方法在一些图形软件中一般用于填充圆、椭圆、多边形等简单形状的区域。种子点法一般用于填充交复杂的边界图形和交互绘制系统。 4.1.1 扫描线多边形填充算法 如下图所示，对每一条扫描线，我们计算出多边形中与扫描线相交的点，这些点按行从左至右排序放入一个线性表（焦点个数应为偶数个），然后在贞缓存中将每对交点中间位置的点写入颜色值。如图4.1.1所示，红色点为交点，绿色点中间点。 4.1区域填充 有时候扫描线与多边形的顶点相交，如图4.1.2。所示，这时需要对交点作特殊的处理。 第一种情况，在交点a处 ，四边形的两条边和扫描线的交点是同一个顶点，这时，连接交点的两条边在扫描线的同侧，交点数目为偶数个，则不需要多特殊处理。 4.1区域填充 第二种情况，在交点b处，关联该定点的多边形的两条边分别位于扫描线两侧。 需要对交点作特殊处理， 因为在确定交点对时，第三个交点（和第二个交点为同一点）和第四个交点之间部分并非多变形的包围区域。这时交点总数为奇数个。 4.1区域填充 所以我们首先需要确定某些顶点关联的两条边是否在扫描线的两侧。可以通过沿多边形边界按顺时针或逆时针遍历每一条边，当从一条边转到另一条边时，检查线段端点y值的变化，如果y是单调增或单调减，那么这两条边分别位于扫描线的两侧。这时为了保证交点数目为偶数，两条边与扫描线的交点只能加入交点列表中一次。对于第一种情况，则可直接将交点插入交点列表。 在第二种情况下，为了保证交点个数为偶数个,可以有两种方法解决： 方法1、按照一定方向（顺时针或逆时针）检测多边形的每条边，当关联某个顶点的两条边的端点y值单调增或单调减，那么穿过该点扫描线与多边形的交点只计入一次。 方法2：将应计为一个交点的多边形顶点关联的一条边缩短，在竖直方向上减少一个像素的长度。 4.1区域填充 沿多边形边界按顺时针或逆时针遍历每一条边，当从一条边转到另一条边时，检查线段端点y值的变化，如果y是单调增或单调减时：如果端点y值增加，那么当前边的高端点减1，如果端点y值减少（如图4.1.3a所示） ，那么紧跟该边的下一条的交高端点减1（如图4.1.3b所示） 4.1区域填充 多边形扫描转换算法步骤： （1）按顺时针（或逆时针）检查多边形的每条边，对于那些需要特殊处理的顶点，将与之关联的一条边缩短一个像素长度 （2）求出多边形的最大ymax值和最小ymin值 (3) 从第一条扫描线ymin开始 a:求出和该扫描线相交的所有交点，求交点过程中 b:交点排序 c:交点配对 d:区间填色 (4)重复（3）直到ymax 4.1区域填充 多边形扫描转换中的连续性应用和增量计算 在多边形扫描转换填充区域方法中，我们可以充分利用现实场景中的连续性来减少计算量。在从一条扫描线变化到另一条扫描线时，可以利用连续性通过计算增量来求交点。 设多边形的一条边的直线方程： y=mx+b 则⊿y=m ⊿x。⊿y、⊿x为y和x方向上的增量。 ⊿x=⊿y/m 设扫描线yk和该线段的交点为(xk,yk),在下一条扫描线的交点为 (yk+1-yk）/m, yk+1,) 因为(yk+1-yk）=1,所以下一条扫描线的交点的x坐标 xk+1=xk+1/m 4.1区域填充 计算出第一条扫描线的交点(x0,y0),第k条扫描线的交点为 x0+k/m, yk 1/m= ⊿x/⊿y ⊿x，⊿y为线段的两个端点坐标差。 在具体计算过程中可按如下方法避免浮点运算，只进行整数运算： 设一计数器，初始为0，为进入下一条扫描线，计数器增加⊿x，当计数器值⊿y时，x值增加1，同时计数器内的值减⊿y，这个过程相当于计数器保存着交点x的整数和小数部分，并增加小数部分递增，直到达到下一条扫描线 4.1区域填充 为了有效地进行多边形填充，需要建立一个存储边的线性表，表的长度为屏幕扫描线的个数。我们可以沿多边形按顺时针或逆时针检查每一条边（平行边除外），将能概括每一条边的所有信息存放到该边较低端点y值对应的表的位置（如图4