扫描线算法：非自交多边形的高效转换

多边形的扫描转换是计算机图形学中的一个重要概念，它主要用于将多边形的顶点表示转换为点阵表示，以便于在屏幕上渲染和着色。这一过程对于实时图形渲染和视频游戏等领域至关重要，因为它能够提高图形处理效率，减少计算负担。 第四章详细介绍了多边形的扫描转换，包括多边形的分类，如凸多边形、凹多边形和含内环的多边形。顶点表示和点阵表示是多边形常见的两种表示方法。顶点表示直观且占用内存较少，但无法直接进行面着色；点阵表示则牺牲了一些几何信息，但利于使用帧缓冲存储器，便于着色操作。 扫描线算法是多边形扫描转换的核心技术之一。它针对非自交多边形设计，即边与边之间除了顶点外没有其他交点。扫描线算法的目标是利用相邻像素的连贯性，提高算法效率。在处理过程中，有三条关键规则： 1. 交点取整规则：当交点位于扫描线上的两个像素之间时，根据规则1，要么向右取整（交点在左边之上），要么向左取整（交点在右边之上）。这可以避免四舍五入导致的部分像素超出多边形范围。 2. 边界象素处理：为防止填充区域扩大，扫描线算法规定只填充位于右上边界的象素之外的区域。这意味着当扫描线与多边形相交时，仅对左闭右开的区间进行填充。 3. 顶点交点处理：当扫描线与多边形顶点相交时，通过比较顶点边的Y值来确定交点的数量。若两个Y值中大于交点Y值的个数为0、1或2，就相应地取0、1或2个交点。 扫描线算法的优势在于避免了逐点判断和重复求交，大大减少了计算工作量，使得图形渲染更为高效。它体现了光栅图形算法研究中对区域连贯性、扫描线连贯性和边的连贯性的综合应用。 活动边表（AET）在多边形的扫描转换中可能是一个辅助数据结构，用于跟踪当前扫描线下的活动边界，但在提供的文件内容中并未明确提及。通常，活动边表会配合扫描线算法，帮助管理和优化多边形的扫描过程，确保正确填充每个像素。