计算机图形学

7.5 扫描线(Scan line)算法
��正如前面所说，深度缓存算法存在一些缺点：占用存储空间大，没有利用图形的相关性与连续性。为了克服这些缺点，需要对它作两方面的改进：（1）利用平面的几何相关性提高点与多边形的包含性测试和深度计算的速度；（2）减小缓冲区；把显示窗口分成若干个区域，依次处理和显示一个区域，这样Z缓冲器的大小（存储单元数）只要等于一个区域的象素个数即可。如果把这个区域取成屏幕上的一行，就得到扫描线算法。
7.5.1 扫描线算法的数据结构
��为了有效的利用几何相关性，在扫描线算法中建立如下数据结构：
��（1）多边形Y桶
��多边形Y桶实际上是一个指针数组，用于存储所有多边形的有关信息。图7.11 a) 中的消隐对象是三个多边形（这里都是三角形），b)是a)的多边形Y桶。根据多边形顶点中最小的y坐标，确定每个多边形在多边形Y桶中的位置。多边形Y桶中只保存每个多边形的序号及其多边形顶点的最大y坐标。根据序号可以从定义多边形的数据结构中获取多边形的信息：多边形所在面的方程f=ax+by+cz+d的系数（a,b,c,d）、多边形的边、顶点坐标和颜色等等。
��（2）活化多边形表APT
��活化多边形表APT实际上是一个动态的链表，用于存储与当前扫描线相交的多边形。图7.12 是y=4时的活化多边形表APT。
��（3）边Y桶
��每一个多边形都有一个边Y桶。多边形P1的边Y桶如图7.13所示。边Y桶中，存放了每条边端点中较大的y值，增量Δx，y值较小一端的x 坐标和z坐标。
��（4）活化边表AET
��在一条扫描线上，同一多边形的相邻两条边构成一个边对。活化边表AET中存放当前多边形的边界线与当前扫描线相交的各边对的信息。它随扫描线的不同而动态地变化。
��如图7.14所示，当扫描线y=2时，活化边表的指针指向边对（e₀，e₁）的信息:

AET

��当扫描线y=6时，活化边表的指针指向边对（e₀，e₅）和（e₃，e₂）的信息:
AET的每个节点包括边对中如下信息：左例（7－5－1）
其中：
��x_l：左侧边与扫描线交点的x坐标；
��Δx_l：左侧边在扫描线加1时的x坐标增量；
��y_lmax：左侧边两端点中最大的y值；
��x_r：右侧边与扫描线交点的x坐标；
��Δx_r：右侧边在扫描线加1时的x坐标增量；
��y_rmax：右侧边两端点中最大的y值；
��z_l：左侧边与扫描线交点处的多边形深度值；
��IP：多边形序号；
��Δz_l：沿扫描线方向增加一个象素时，多边形所在平面的z坐标增量，Δz_l＝－a/c；
��Δz：扫描线加1时，多边形所在平面的z坐标增量，Δz＝－b/c。