计算机图形学：多边形扫描转换与AET算法

"当沿着扫描线_scan-plc编程手册" 这篇文档主要介绍了一种用于多边形扫描转换的算法，该算法沿着扫描线进行操作，适用于计算机图形学中图形的绘制和填充。以下是该算法的详细步骤和相关知识点： 1. 扫描线算法概述： 在扫描线算法中，首先从边表中选取与当前扫描线`y`相等的边，这些边被称为有效边。然后，将有效边按照它们在x轴上的增量顺序进行排序，形成有效边表（AET）。 2. 边表处理： 对于有效边表中的每一对边，根据它们的x增量顺序组成区间对，并进行填充。填充过程通常涉及到计算交点并进行像素着色。 3. 边的更新： 每次扫描线移动到`y1 += 1`时，有效边的x值需要更新。新的x值计算公式为 `xx1 += k`，同时最小y值更新为 `miny += y1`。这一步骤是为了根据扫描线的移动调整边的位置信息。 4. 边的移除： 如果扫描线`y`超过了某边的最大y值，说明这条边不再与扫描线相交，此时将该边从有效边表中删除。 5. 算法终止条件： 当有效边表中没有边时，说明已经处理到了多边形的最大y值，扫描转换结束。 6. 边结构： 在构建边的信息时，需要包含当前最小y值、对应的x值、最大y值以及斜率的倒数。如果边是水平线，斜率倒数为无穷大，还需要记录另一个顶点的x值。若斜率倒数不为无穷大，可以省略这个额外的x值信息。边的类定义如下（以C++为例）： ```cpp class CAET { // 构造边类的属性 int min_y; int cur_x; int max_y; double k; // 斜率倒数 int another_x; // 当斜率倒数为无穷大时记录的另一个顶点的x值 }; ``` 7. 计算机图形学基础： 文档也简述了计算机图形学的基本概念，它是计算机科学的一个分支，广泛应用于CAD、动画、虚拟现实等领域。计算机图形学涉及如何使用计算机表示、生成、处理和显示图形，其定义随着技术发展而不断演进。 通过这种扫描线算法，可以高效地进行多边形的填充，尤其是在计算机图形渲染和图像处理中。这种方法减少了在每个扫描线上查找和计算交点的复杂性，提高了处理效率。