CG-光栅图形学多边形扫描转换算法-学习笔记

一、多边形扫描转换算法——X扫描线算法

1. 背景

1°  多边形的两种重要表示方法：顶点表示和点阵表示；

2° 光栅图形的一个基本问题就是把多边形的顶点表示转换成点阵表示。称为多边形的扫描转换；

2. 原理

X-扫描线算法填充多边形的基本思想是按扫描线顺序，计算扫描线与多边形的相交区间，再用要求的颜色显示这些区间的像素，即完成填充工作；区间的端点可以通过计算扫描线与多边形边界线的交点获得。 

  

 如扫描线y=3与多边形的便捷相交于4点：（2,3）、（4,3）、（7,3）、（9,3）；

这四点定义了扫描线上的区间（2,4）、（7,9），区间内像素应取填充色；

 算法核心：按X递增顺序排列交点的X坐标序列。

3. 算法步骤

1° 确定多边形所占有的最大扫描线书，得到多边形顶点的最小和最大Y值（y_min、y_max）;

2° 从y = y_min到y = y_max，每次用一条扫描线进行填充；

3° 对一条扫描线填充的过程可分为四个步骤：

        a. 求交：计算扫描线与多边形各边的交点；

        b. 排序：把所有交点按递增顺序进行排序；

        c. 交点配对：第一个与第二个，第三个与第四个；

        d. 区间填色：把这些相交区间的像素置成不同于背景色的填充色；

4. 交点取舍问题  ---->  交点的个数应保证为偶数个

a. 若共享顶点的两条边分别落在扫描线的两边，交点只算一个；

b. 若共享顶点的两条边在扫描线的同一边，这时交点作为零个或两个；

【注意】检查共享顶点的两条边的另外两个两个端点的y值，按这个y值中大于交点y值的个数来决定交点数；（大于-->2、小于--->0）

5. 求交

为了计算每条扫描线与多边形的交点，最简单的方法是把多边形的所有边放在一个表中。在处理每条扫描线是，按顺序从表中取出所有的边，分别与扫描线求交；计算量非常大！！！

二、多边形扫描转换算法——改进的X扫描线算法

 1. 引入特殊的数据结构

1）活性边表（AET）：把当前扫描线相交的边成为活性边，并把它们按与扫描线交点x坐标递增的顺序存放在一个链表中；

2）结点内容（一个结点在数据结构里可用结构来表示）

            x：当前扫描线与边的交点坐标

            ∆x：从当前扫描线到下一条扫描线间x的增量        

            y_max：该边所交的最高扫描线的坐标值y_max

3）新边表（NET）：为了方便活性边表的建立与更新，用来存放多边形的边的信息

     a）首先构造一个纵向链表，链表的长度为多边形所占有的最大扫描线数，链表的每个结点，成为一个吊桶，对应多边形覆盖的每一条扫描线；

                                ====》

    b）NET挂在与该边低端y值相同的线桶中。也就是说，存放在该扫描线第一次出现的边；

数据结构内容：该边的y_max、该边较低点的x坐标值xmin，该边的斜率1/k、指向下一条具有相同较低端y坐标的边的指针；

示例：

2. 算法原理

1° 随着扫描线的移动，扫描线与多边形的交点和上一次交点相关：

设边的直线斜率为k：

推导得：，即∆x = 1 / k；

2° 需要知道一条边何时不再与下一条扫描线相交，以便及时把它从有效边表中删除出去，避免下一步进行无谓的计算；y_max是边所在的最大扫描线值，通过它可以知道何时才能“抛弃”该边。

从上边这个NET表里就知道多边形是从哪里开始的：在这个表里只有1、3、5、7处有边，从y=1开始做，而在1这条线上有两条边进来了，然后就把这两条边放进活性边表来处理。

3° 每一次更新，需要对已有的边进行三个处理：

     1）是否被去除掉；

     2）如果不被去除，第二就要对它的数据进行更新。所谓更新数据就是要更新它的x值，即x+1/k;

     3）看有没有新的边进来，新的边在NET里，可以插入排序插进来；