多边形扫描转换：边界标志算法详解

"本资源主要介绍了多边形的扫描转换，特别是边界标志算法在填充多边形中的应用。" 在计算机图形学中，多边形的扫描转换是将多边形从顶点表示转换为点阵表示的过程，即确定多边形内部的像素并设置它们的颜色。这一过程对于在屏幕上绘制和渲染图形至关重要。多边形分为不同的类型，包括凸多边形、凹多边形以及含内环的多边形，每种类型的多边形在扫描转换时都有其特定的处理方式。 4.1多边形的扫描转换章节中提到了两种基本方法：扫描线算法和边界标志法。顶点表示法是用多边形顶点的序列来描述多边形，虽然直观且内存占用少，但不适合直接进行面着色。点阵表示法则通过表示多边形内部的像素集合，虽然失去了部分几何信息，但方便进行面着色和帧缓冲操作。 扫描线算法是一种常见的多边形扫描转换方法，尤其适用于非自交多边形。它通过沿着扫描线（垂直于屏幕的线）逐行处理，找到多边形与扫描线的交点，然后根据一定的取整规则来确定像素是否属于多边形内部。在处理交点时，有三个关键规则： 1. 当交点位于两个像素之间时，根据交点的位置向左或向右取整，确保像素位于多边形内。 2. 在边界象素处理时，遵循不填充右上边界像素的原则，以防止填充扩大。 3. 当扫描线与多边形的顶点相交时，通过比较顶点两侧边的其他端点的Y坐标，来决定是否包含该交点，以确保正确配对。 边界标志算法（Edge Marking Algorithm），如函数`edgemark_fill`所示，是另一种填充多边形的方法。它遍历多边形的所有边，对与多边形相交的扫描线上的像素打上边标志。算法中，变量`inside`用于记录当前像素是否位于多边形内部。如果像素被打上了边标志，`inside`状态反转，然后根据`inside`的值来决定是否绘制该像素（填充颜色或背景色）。 扫描线算法和边界标志算法都是为了提高效率，减少对每个像素的单独判断和计算。它们通过利用相邻像素的连贯性，降低了计算复杂度，是光栅图形处理中的核心算法。这些算法的优化和改进一直是图形学研究的重点，以满足实时渲染和高性能计算的需求。