计算机图形学多边形填充

《计算机图形学多边形填充》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、◆有效边表填充算法◆边缘填充算法◆种子填充算法�实面积图形的概念�有效边表填充算法�边缘填充算法�区域填充算法实面积图形的概念实面积图形�描述物体的几何轮廓，�表现物体的表面色彩，�与人们观察物体表面的习惯相一致，�同时，实面积图形也是描述三维物体、绘制三维真实感图形的基础。多边形的表示多边形（区域）有两种表示方法：顶点表示法和点阵表示法P1P0P5P2P3P4图3多边形的顶点表示图4多边形的点阵表示法法⑴顶点表示法�用多边形的顶点序列来描述�特点是直观、占内存少，易于进行几何变换�但由于没有明确指出哪些像素在多边形内，所以不能

2、直接进行填充，需要对多边形进行扫描转换⑵点阵表示法�用多边形覆盖的像素点集来描述�特点是便于直接确定实面积图形覆盖的像素点，是多边形填充所需要的表示形式�但是缺少了多边形顶点的几何信息⑶多边形的扫描转换�将多边形的描述从顶点表示法变换到点阵表示法的过程，称为多边形的扫描转换。�即从多边形的顶点信息出发，求出多边形内部的各个像素点信息。多边形区域填充操作（1）确定多边形顶点坐标（2）生成多边形（3）填充：多边形区域内像素点的判断yP6121110P498P7P57P06P2543ABCD21P1P3123456789101112x

3、多边形的扫描转换1.填充点的判别方法“扫描线交点的奇偶数判断”法：用一根水平扫描线从左向右通过多边形而与多边形的边界相交，扫描线与边界相交奇数次后进入该多边形，相交偶数次后离开该多边形。2.交点的异常处理�当扫描线与多边形顶点相交时，称该交点为奇点�奇点可以计数为0、1或2个相交点�如果奇点的计数不正确，将会导致错误填充。�具体计数原则如下：（1）当奇点在多边形两边之下方时，该点计为2个点，如y图中的P1、P3和P5点。P6121110（2）当奇点在多边形两边之P49上方时，该点计为0个点，8P7P57如图中的P2、P4和P6点

4、。P06P2543ABCD21P1P3123456789101112x2.交点的异常处理（3）当奇点在多边形两边之间时，该点计为1个点，如图中的P7点。实现时，只需检查顶点两条边的另外两个端点的y值，由这两个y值中大于交点y值的个数是0、1、2来决定。y（4）扫描线与多边形的水平P612边重合，理论上是无穷多个1110交点，但在实际处理时不计P49其交点。8P7P57P06P2543ABCD21P1P3123456789101112x0111102223.填充算法步骤：(1)确定多边形所占有的最大扫描线数，得到多边形顶点的最小和

5、最大y值（y和y）minmax(2)从y=y到y=y，每次用一条扫描线进行填充minmax(3)对一条扫描线填充的过程可分为四个步骤：a.求交点b.排序c.交点配对d.区间填色填充过程演示特殊处理：边界像素的处理原则在实际填充过程中，需要考虑到边界像素影响问题：图6中正方形P0P2P4P6被等分为四个小正方形。假定小正方形P0P1P8P7被填充为绿色，P1P2P3P8被填充为橙色，P8P3P4P5被填充为绿色，P7P8P5P6被填充为橙色。P6P5P4P6P5P4P7P8P3P7P8P3P0P1P2P0P1P2图6边界像素的问题

6、图7边界像素的处理P6P5P4P6P5P4P7P8P3P7P8P3P0P1P2P0P1P2图6边界像素的问题图7边界像素的处理四个小正方形的公共边为：P1P8、P8P5、P7P8和P8P3。P1P8和P7P8应该填充为哪一个小正方形的颜色？P8P5和P8P3应该填充为哪一个小正方形的颜色？yy665544332211O123456O123456x图8面积3×3图9面积2×2在实际填充过程中，也需要考虑到像素面积大小的影响问题：对左下角为（1，1），右上角为（3，3）的正方形进行填充时，若边界上的所有像素全部填充，就得到图8所示的

7、结果。所填像素覆盖的面积为3×3个单位，而正方形的面积实际只有2×2个单位。yy665544332211O123456O123456x图8面积3×3图9面积2×2�为了解决这些问题，在多边形填充过程中，常采用“下闭上开”和“左闭右开”的原则对边界像素进行处理。�图6的处理结果如图4-7所示，每个小正方形的右边界像素和上边界像素都没有填充。�图8的处理结果如图4-9所示，上面一行像素和右面一列像素没有填充。2有效边表填充算法�填充原理�有效边和有效边表�边表填充原理�为了计算每条扫描线与多边形各边的交点，最简单的方法是把多边形的所

8、有边放在一个表中。�处理每条扫描线时，按顺序从表中取出所有边，分别与扫描线求交点。�缺点：效率不高�重复判别多实际每条扫描线只与少数边相交，边的连贯性�求交运算量大计算交点时没有考虑扫描线的连贯性填充原理有效边表填充算法的基本原理�按照扫描线从小到大的顺序，计算