计算机图形学基础教程(nxpowerlite)

《计算机图形学基础教程(nxpowerlite)》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第四章多边形填充2才智在线QQ523458367◆有效边表填充算法◆边缘填充算法◆种子填充算法本章学习目标本章内容4.1实面积图形的概念4.2有效边表填充算法4.3边缘填充算法4.4种子填充算法4.5本章小结4.6习题4.1实面积图形的概念实面积图形既能描述物体的几何轮廓，又能表现物体的表面色彩，与人们观察物体表面的习惯相一致，同时，实面积图形也是描述三维物体、绘制三维真实感图形的基础。4.1.1多边形的表示在计算机图形学中，多边形有两种示方法：顶点表示法和点阵表示法。图4-3多边形的顶点表示法P0P1P2P3P4P5图4-4多边形的点阵表示法多边形的顶点表示法是用多边形的顶点序列来描述。

2、特点是直观、占内存少，易于进行几何变换，但由于没有明确指出哪些像素在多边形内，所以不能直接进行填充，需要对多边形进行扫描转换，顶点表示法如图4-3所示。⑴顶点表示法⑵点阵表示法多边形的点阵表示法是用多边形覆盖的像素点集来描述。特点是便于直接确定实面积图形覆盖的像素点，是多边形填充所需要的表示形式，但是缺少了多边形顶点的几何信息，如图4-4所示。⑶多边形的扫描转换将多边形的描述从顶点表示法变换到点阵表示法的过程，称为多边形的扫描转换。即从多边形的顶点信息出发，求出多边形内部的各个像素点信息。4.2有效边表填充算法4.2.1填充原理4.2.2边界像素的处理原则4.2.3有效边和有效边表4.2.

3、4边表4.2.1填充原理多边形的有效边表填充算法的基本原理是按照扫描线从小到大的移动顺序，计算当前扫描线与多边形各边的交点，然后把这些交点按x值递增的顺序进行排序、配对，以确定填充区间，然后用指定颜色点亮填充区间内的所有像素，即完成填充工作。有效边表填充算法通过访问多边形覆盖区间内的每个像素，可以填充凸、凹多边形和环，已成为目前最为有效的多边形填充算法。图4-5用一条扫描线填充多边形P0P1P2P3P4P5P6在图4-5中，多边形覆盖了12条扫描线。扫描线y＝3与多边形有4个交点（2.3，3），(4.5，3），（7，3）和（9，3）。对交点进行圆整处理后的结果为（2，3），(5，3），（7

4、，3）和（9，3）。按x值递增的顺序对交点进行排序、配对后的填充区间为（2，5）和（7，9），共有7个像素点需要填充为指定颜色。4.2.2边界像素的处理原则在实际填充过程中，需要考虑到边界像素影响问题：图4-6中正方形P0P2P4P6被等分为四个小正方形。假定小正方形P0P1P8P7被填充为绿色，P1P2P3P8被填充为橙色，P8P3P4P5被填充为绿色，P7P8P5P6被填充为橙色。四个小正方形的公共边为：P1P8、P8P5、P7P8和P8P3。考虑到公共边P1P8既是正方形P0P1P8P7的右边界，又是正方形P1P2P3P8的左边界；考虑到P7P8既是是正方形P0P1P8P7的上边界，

5、又是正方形P7P8P5P6的下边界，那么P1P8和P7P8应该填充为哪一个小正方形的颜色？同理，P8P5和P8P3应该填充为哪一个小正方形的颜色？图4-6边界像素的问题P0P1P2P3P4P5P6P7图4-7边界像素的处理P8P0P1P2P3P4P5P6P7P8在实际填充过程中，也需要考虑到像素面积大小的影响问题：对左下角为（1，1），右上角为（3，3）的正方形进行填充时，若边界上的所有像素全部填充，就得到图4-8所示的结果。所填像素覆盖的面积为3×3个单位，而正方形的面积实际只有2×2个单位。图4-8面积3×3图4-9面积2×2为了保解决这些问题，在多边形填充过程中，常采用“下闭上开”和

6、“左闭右开”的原则对边界像素进行处理。图4-6的处理结果如图4-7所示，每个小正方形的右边界像素和上边界像素都没有填充。图4-8的处理结果如图4-9所示，上面一行像素和右面一列像素没有填充。按照此原则对图4-5中的一些特殊点进行处理：1.P2点的处理原则图4-5中P2是边P3P2的终点，同时也是边P2P1的起点。按照“下闭上开”的原则，可以自动处理。图4-10局部点的处理P0P1P2P3P4P5P62.P0、P3、P5点和P4点的处理原则P0点、P3和P5是局部最低点，P4点是局部最高点。如果处理不当，扫描线y＝1会填充区间（3，8），结果填充了P3和P5点之间的像素，如图4-10所示。对

7、局部最低点P0、P3和P5的处理方法为，填充时设置一个逻辑变量（初始值为假），每访问一个结点，逻辑变量值取反一次，若逻辑变量值为真，则填充该区间，这样可以保证局部最低点处理正确。对局部最高点P4，根据“下闭上开”的原则，P4点不予填充，y＝5扫描线会自动填充P4点，如图4-10所示。4.2.3有效边和有效边表形1.有效边（ActiveEdge，AE）多边形内与当前扫描线相交的边称为有效边。在处理一条扫描线时仅对有效边进行