链表的长度为多边形所覆盖的最大扫描线数，链表的每个结点称为桶（Bucket），对应多边形覆盖的每一条扫描线。
4. 像素颜色取补
边缘填充算法是先求出多边形的每条边与扫描线的交点，然后将交点右侧的所有像素颜色全部取为补色。按任意顺序处理完多边形的所有边后，就完成了多边形的填充任务。边缘填充算法利用了图像处理中的求“补”的概念，对于黑白图像，求补就是把颜色为RGB(255,255,255)（白色）的像素置为RGB(0,0,0)（黑色），反之亦然；对于彩色图像，求补就是将背景色置为填充色，反之亦然。求补的一条基本性质是一个像素求补两次就恢复为原色。如果多边形内部的像素被求补偶数次，将保持为填充色；如果被求补奇数次，显示为背景色。
5. 包围盒与栅栏
边缘填充算法的效率受到交点右侧像素的数量影响，右侧像素越多，需要取补的像素也就越多。为了提高填充效率，可以在多边形的包围盒内进行像素取补，或者在包围盒内再添加一条栅栏，处理每条边与扫描线的交点时，只将交点与栅栏之间的像素取补。若交点位于栅栏左侧，将交点之右，栅栏之左的所有像素取补；若交点位于栅栏右侧，将栅栏之右，交点之左的所有像素取补。
6. 四邻接点与八邻接点
对于区域内部任意一个种子像素，其左、上、右、下这4个像素称为四邻接点。对于区域内部任意一个种子像素，其左、上、右、下以及左上、右上、右下、左下这8个像素称为八邻接点。
7. 四连通边界与八连通边界
边界像素只能按照水平和垂直方向理解是连通的称为四连通边界，如图11所示；边界像素按照45°斜线方向理解是连通的称为八连通边界，如图12所示
图11 四联通边界 图12 八连通边界
第4章难点学习指导：
1. 使用动态链表实现有效边表填充算法
（1）调用颜色对话框读取填充色。
（2）根据示例多边形顶点坐标值，计算扫描线的最大值ScanMax和最小值ScanMin。 （3）用多边形覆盖的扫描线动态建立桶结点。
（4）循环访问多边形的所有顶点，根据边的终点y值比起点y值高或边的终点y值比
起点y值低两种情况（边的终点y值和起点y值相等的情况属于扫描线，不予考虑），计算每条边的ymin。在桶中寻找与该ymin相对应的桶结点，计算该边表的x|ymin、yMax、k（代表1/k），并依次链接该边表结点到桶结点。
（5）对每个桶结点链接的边表，根据x|ymin值的大小进行排序，若x|ymin相等，则按照k（代表1/k）由小到大排序。
（6）循环访问每个桶结点，将桶内每个结点的边表合并为有效边表，并循环访问有效边表。
（7）从有效边表中取出扫描线上相邻两条边的结点（交点）对进行配对。填充时设置一个逻辑变量bInFlag（初始值为假），每访问一个结点，把bInFlag值取反一次，若bInFlag为真，则把从当前结点的x值开始到下一结点的x值结束的区间用指定颜色填充。
（8）循环下一桶结点，按照xi+1=xi+k（k的值为1/k）修改有效边表，同时合并桶结点内的新边表，形成新的有效边表。
（9）如果桶结点的扫描线值大于等于有效边表中某个结点的ymax值，则该边成为无效边。
（10）当桶结点不为空则转（6），否则删除桶表和边表的头结点，算法结束。 2. 入栈和出栈算法
pHead是头结点指针，其数据域为空。pTop是栈顶指针，其数据域存放入栈或出栈像素。如果将像素point1先入栈，如图13所示。接着将point2像素入栈，如图14所示。
pHeadpToppoint1NULL 图13 point1像素入栈示意图
pHeadpToppoint2point1NULL 图14 point2像素入栈示意图
如果栈非空，弹出栈内的像素，图15所示为空栈。
pHeadNULL 图15 空栈示意图
第5章 二维变换与裁剪
重点：基本变换矩阵；复合变换；坐标系之间的关系；窗视变换；Cohen-sutherland裁剪算法；
难点：Liang-Barsky裁剪算法；多边形裁剪算法；
第5章重点学习指导：
1. 基本几何变换矩阵
二维基本几何变换分为平移、比例、旋转、反射和错切。变换矩阵是用行矩阵表达的。
?1?平移变换矩阵： T??0?Tx?01Ty0??Sx??0?，比例变换矩阵：T??0?1??0?0Sy00?0?? 1???cos??逆时针旋转变换矩阵：T??sin????0sin?cos?00?0??。 1????100???关于原点的二维反射变换矩阵：T?0?10
???01??0??1b0???沿x，y两个方向的二维错切变换矩阵：T?c10 。 ????001??2. 复合变换
复合变换分为两种。一种是相对于任意参考点的变换，另一种是相对于相对于任意方向的变换。共同点是先做任意点或任意方向的变换，再做具体的变换，最后做任意点或任意方向的反变换。
3. 坐标系之间的关系
用户坐标系用于建立物体的几何模型。坐标系原点可以建立在物体的任何位置，比如圆柱的底面中心，立方体的体心或者立方体的一个顶点。世界坐标系相当于三维场景的舞台，里面定义了出场物体的相互位置，视点位置和视向、光源位置。将物体借助于用户坐标系到世界坐标系的变换导入世界坐标系。观察坐标系定义了视点的位置和朝向，屏幕坐标系定义了物体的投影。在观察坐标系内对物体进行消隐。最后物体的输出由规格化设备坐标系变换到设备坐标系。如图16所示。
图16 坐标系之间的关系
4. 窗视变换
在观察坐标系中定义的确定图形显示内容的区域称为窗口。在设备坐标系中定义的输出图形的区域称为视区。窗口和视区常为矩形，大小可以不相同。一般情况下，用户把窗口内感兴趣的图形输出到屏幕上相应的视区内。可以在屏幕上可以定义多个视区，用来同时显示不同窗口内的图形信息。图形输出需要进行从窗口到视区的变换，只有窗口内的图形才能在视区中输出，并且输出的形状要根据视区的大小进行调整，这称为窗视变换。
?Sx?0窗视变换矩阵为 T???vxl?wxlSx?0Syvyb?wybSy0??0?。 1??为了减少窗视变换的计算量，常假定窗口与视区的大小一致。
5. Cohen-sutherland裁剪算法
Cohen-Sutherland裁剪算法是一种直线段裁剪算法，其特点是将窗口边界延长得到9个区域，为了判断直线段端点位于哪个区域，使用了四位二进制数编码进行数字化处理。裁剪主要分为以下三步：简取、简弃、求交。
（1）若直线段的两个端点的区域编码都为0，即RC0|RC1=0（二者按位相或的结果为0，即RC0=0且RC1=0），说明直线段的两个端点都在窗口内，应“简取”。
（2）若直线段的两个端点的区域编码都不为0，即RC0&RC1≠0（二者按位相与的结果不为0，即RC0≠0且RC1≠0，即直线段位于窗外的同一侧），说明直线段的两个端点都在窗口外，应“简弃”。
（3）若直线段既不满足“简取”也不满足“简弃”的条件，则需要与窗口进行“求交”判断。
求交这一步需要计算窗口边界与直线段的交点。
6. 中点裁剪算法
Cohen-Sutherland裁剪算法提出对直线段端点进行编码，并把直线段与窗口的位置关系划分为3种情况，对前两种情况进行了“简取”与“简弃”的简单处理。对于第3种情况，
相关推荐：
loading