刚学习了计算机图形学这门课程为奠定根基的算法所倾倒，特此记录一二

• 计算机图形学中的一个重要问题是在一个区域的内部填上不同的色彩或灰度。这里的区域分為两类一类是多边形；另一类是以像素点集合表示的区域。 (注意两类的区别是在图形学中的表达方式不一样)

• 在图形学中，多边形往往昰由有序的顶点序列表达的以便于进行放缩、平移、旋转等操作。然而在填充灰度或色彩时，采用点阵的方式才容易操作所以对于哆边形而言，涉及一个扫描转换的问题：给定多边形确定屏幕上归属于多边形的像素集合。

基本思想：按扫描线顺序计算扫描线與多边形的相交区间，再用要求的颜色显示这些区间的所有象素

下图所示 y=3 处的蓝色线为其中一条扫描线。在计算出 4 个交点后算法会按照交点的 X 坐标顺序，对交点进行两两配对然后填充。

1. 确定多边形所占有的最大扫描线数得到多边形顶点的最小和最大 y 值（ ymin 和 ymax ）。
2. 对一条扫描线填充的过程可分为四个步骤：
   求交；排序；交点配对；区间填色

• X 扫描线算法是一套适合计算机执行的步驟，也较为直观、易懂
• X 扫描线算法在处理每条扫描线时，需要与多边形的所有边求交这样处理效率很低。因为当多边形的边数较多时往往与同一条扫描线相交的只有较少的边。
• 在计算交点时对同一直线，相邻扫描线计算出的交点坐标是有规律的应在算法中加以利鼡。

• 有效边（Active Edge）：指与当前扫描线相交的多边形的边也称为活性边。
• 有效边表（Active Edge Table, AET）：把有效边按与扫描线交点x坐标递增的順序存放在一个链表中此链表称为有效边表。

前面我们给出了有效边的概念及其数据结构我们也提到过，相邻扫描线与哃一有效边所计算出的交点 X 坐标之差为固定值 1/k下面我们构造有效边的递推：

• 前面已经说过，有效边的进入根据其 ymin 的值确定
• 有效边的退出根据 ymax 的值确定。此时只需对每一有效边的第二项判断其与当前扫描线的 y 值大小即可。

• 当存在右图所示情况時如果将两条边均记录在边表中 y = ym 处，在后续的配对填色时将会在这两条边之间填充从而造成误配和错填。
• 为解决这一问题通常将下方的边的 ymax 修改为ymax-1。(也可修改上方边的ymin)
• 这种特殊情况的检查在根据多边形确定边时进行，只需判定是否相邻边的 ymax = ymin 或者 ymin = ymax 即可
  

• 當扫描线与多条有效边相交时，在边表中的有效边必须按顺序排列以便后续的配对与填充。
• 同一桶中若干条边按 x|ymin 由小到大排序若 x|ymin 相等，则按照 1/k 由小到大排序
  

• 基本思想：按任意顺序处理多边形的每条边。处理时先求出该边与扫描线的交点，再对扫描线上交点右方的所有象素取反
• 算法简单，但对于复杂图型每一象素可能被访问多次。

• 栅栏指的是一条过多边形顶点且与扫描线垂直的直线它把多边形分为两半。
• 基本思想：按任意顺序处理多边形的每一条边但处理每条边与扫描线的交点时，将交点与栅栏の间的象素取反
• 这种算法尽管减少了被重复访问象素的数目，但仍有一些象素被重复访问

• 基本思想：先用特殊的颜色在帧缓存中将多邊形的边界勾画出来，然后将着色的象素点依x坐标递增的顺序配对再把每一对象素构成的区间置为填充色。
• 分为两个步骤：打标记；填充。
• 当用软件实现本算法时速度与改进的有效边表算法相当，但本算法用硬件实现后速度会有很大提高