引言
自從今年春天選修了計算機圖形學(xué)課程摩骨，這朵烏云就在頭頂盤旋不散。始終弄不明白計算機圖形學(xué)到底在研究什么寥闪，所謂的Imaging幕屹、Modeling蓝丙、Rendering和Animation各自又是什么意思级遭。總覺得課上講的實在太過抽象渺尘，實踐的經(jīng)歷太少挫鸽，到最后也不過是囫圇吞棗，不知其味沧烈。
雖然不再從事計算機圖形學(xué)相關(guān)研究掠兄，但為了彌補這些遺憾像云，最近我又重拾這些知識锌雀，更深入細致地學(xué)習(xí)一遍圖形學(xué)基礎(chǔ)知識。在學(xué)習(xí)完多邊形掃描轉(zhuǎn)換中的掃描線算法后迅诬，我決心親自寫代碼實現(xiàn)它腋逆，并動筆寫下這一篇文章。
掃描線算法是干什么用的
我們?nèi)绾卧谟嬎銠C程序中存儲幾何圖形呢侈贷？比如多邊形惩歉？最容易想到的方法就是保存多邊形的頂點坐標(biāo)。只要按順序保存了多邊形各個頂點的坐標(biāo)俏蛮，這個多邊形就唯一確定了撑蚌。另一方面，顯示器是如何顯示幾何圖形的呢搏屑？顯示設(shè)備通常提供一個幀緩沖存儲器（俗稱顯存）争涌，可以把它當(dāng)做二維數(shù)組，該數(shù)組存儲的值與屏幕上顯示的每一像素的顏色一一對應(yīng)辣恋。那么問題來了亮垫，如何把程序中的幾何圖形轉(zhuǎn)換成顯存中的幾何圖形？這就是掃描線算法的用途伟骨。
總結(jié)下來：掃描線算法把幾何圖形在計算機中的頂點表示法轉(zhuǎn)換成點陣表示法饮潦。需要注意的是轉(zhuǎn)換成點陣表示法后其實是對多邊形進行了填充，而不是只有輪廓携狭。
基本思想
由于多邊形千變?nèi)f化继蜡，要想填充多邊形內(nèi)部的所有像素，需要找到一種合適的規(guī)則逛腿，能夠沿著一個方向壹瘟，一個像素不漏地把多邊形內(nèi)部填滿，同時不污染多邊形外部鳄逾。于是我們發(fā)明了一條水平方向的掃描線稻轨，它從y=0開始，判斷與多邊形的交點雕凹，這些交點把掃描線分成了若干段殴俱，我們需要判斷哪些段在多邊形內(nèi)部政冻，哪些段在多邊形外部，然后把內(nèi)部的部分著色线欲，完成后明场，令y=y+1仗岖，即掃描線上移一格卫枝，重復(fù)之前的操作，直到掃描線不再與多邊形的任何部分相交药磺。
舉例說明趴泌，下圖所示為多邊形P1P2P3P4P5P6舟舒，而且同時畫出了掃描線掃描過程中經(jīng)過的四個位置y=1、y=2嗜憔、y=6和y=7秃励。
掃描線算法的難點在于如何判斷掃描線被多邊形分割后哪些部分在多邊形內(nèi)部，哪些部分在多邊形外部吉捶。
讓我們仔細觀察上圖夺鲜，答案就在圖中。對于未經(jīng)過頂點的掃描線呐舔，如y=6币励，總是與多邊形有偶數(shù)個交點，而且位于多邊形內(nèi)部的片段和位于多邊形外部的片段交替存在珊拼。對于經(jīng)過了頂點的掃描線食呻，如y=1、y=2和y=7杆麸，與多邊形的交點既可能是偶數(shù)搁进，也可能是奇數(shù)。但是如果我們進一步劃分昔头，這些經(jīng)過了頂點的掃描線有些經(jīng)過了極值頂點饼问，如y=1和y=7，它們的交點個數(shù)是奇數(shù)揭斧；而有些經(jīng)過了非極值頂點莱革，如y=2，它們的交點個數(shù)是偶數(shù)讹开。這樣的話盅视，不如做一個特殊處理，把所有極值頂點當(dāng)成兩個點旦万，就可以保證掃描線與多邊形的交點總是偶數(shù)闹击。
當(dāng)然，把交點個數(shù)湊成偶數(shù)是有意義的成艘，湊成偶數(shù)后就可以把這些交點從左到右兩兩配對赏半，配對成功的兩個點之間的像素全部著色贺归。例如，上圖的掃描線y=6與多邊形的交點序列是ABCD断箫，從左到右兩兩配對為AB和CD拂酣，然后將AB之間著色，CD之間著色仲义。
基本思想就是這樣婶熬，其實很容易理解。不過用代碼實現(xiàn)起來并不那么容易埃撵，需要考慮很多細節(jié)赵颅。
代碼實現(xiàn)詳解
首先需要提醒的是，掃描線算法的基本思想很簡單盯另，但不同的實現(xiàn)方式會有很大的效率差異性含。因此洲赵，如何設(shè)計數(shù)據(jù)結(jié)構(gòu)及算法才能使掃描線算法以最快的速度完成鸳惯，才是接下來我們需要面對的問題。
從以下幾個方面考慮：
問題1：如何計算當(dāng)前掃描線與多邊形的交點叠萍？
直觀做法：根據(jù)多邊形的頂點求出各個邊的方程芝发，然后將掃描線的縱坐標(biāo)代入方程求出橫坐標(biāo)，搞定苛谷！
遺憾的是辅鲸，這需要對每條掃描線遍歷所有邊，性能肯定是吃不消的腹殿。我們需要尋找一種只遍歷一次邊的方法独悴。同時，使用方程求交點會用到乘法或除法運算锣尉，對性能也是一種傷害刻炒。因此，我們提出了下面兩個數(shù)據(jù)結(jié)構(gòu)自沧。
-
邊表（Edge Table）
所有邊按下端點的y坐標(biāo)歸類坟奥。
邊表
其中，每條邊包含四個成員拇厢，分別是
-
活動邊表（Active Edge Table）
與當(dāng)前掃描線相交的邊稱為活動邊爱谁，把它們按與掃描線交點x坐標(biāo)（x相等時按?x）遞增排序。
掃描線y=6時的活動邊表如下
活動邊表
與邊表類似孝偎，每條邊同樣包含四個成員访敌，分別是
下面的代碼定義了邊表和活動邊表。
//定義用于邊表ET和活動邊表AET的通用類Edge
class Edge
{
public:
int ymax;
float x;
float dx;
Edge* next;
};
//邊表
Edge *ET[windowHeight];
//活動邊表
Edge *AET;
利用這兩個數(shù)據(jù)結(jié)構(gòu)就很容易計算出每條掃描線與多邊形的交點了衣盾。我們只需要令掃描線從下往上掃描寺旺，已知每條邊的下端點x坐標(biāo)和?x荡陷，就可以使用增量法計算出這條邊上所有點的x坐標(biāo)。具體方法放到后面敘述迅涮。
問題2：如何解決前面提到的極值頂點按照兩個處理的問題废赞？
如果兩條邊相交，它們的交點就是一個頂點叮姑。事實上唉地，這個點本來就是按照兩個點處理的，因為它分別屬于兩條邊传透。那么這個問題其實應(yīng)該轉(zhuǎn)換成：如何把非極值頂點按照一個處理耘沼？解決辦法是把頂點處從上面斷開，如下圖所示朱盐。缺口在y坐標(biāo)上的長度是1個像素群嗤，所以并不會產(chǎn)生不利影響。
在后面的代碼實現(xiàn)中兵琳，我們會在建立邊表ET時判斷非極值頂點并對其做特殊處理狂秘，請稍加注意。
問題3：如何快速配對交點并著色躯肌？
活動邊表AET中存儲了所有與當(dāng)前掃描線相交的邊及其交點坐標(biāo)者春。配對的工作就自然變得很簡單，只需要遍歷一遍AET即可清女。
解決了這三個問題钱烟，我們就可以給出下面的算法流程：
- 將掃描線初始y坐標(biāo)設(shè)為ET中非空元素的最小序號。
- 將AET初始化為空嫡丙。
- 循環(huán)執(zhí)行以下步驟拴袭，直到ET和AET都變?yōu)榭铡?br>
(1) 如果 ET[y] 非空，則將其中的所有邊取出并插入到AET中曙博，按x（若x相等則按?x）遞增方向排序拥刻。
(2) 若AET非空，將AET中的邊按順序兩兩配對并填色羊瘩。
(3) 刪去AET中滿足y=ymax的邊泰佳。
(4) 對于AET中所有邊，賦值x = x + ?x尘吗。
(5) y = y + 1逝她，掃描線上移一像素。
依照該流程睬捶，我在Linux下使用c++實現(xiàn)了這個算法黔宛。由于無法真正實現(xiàn)向幀緩沖存儲器填色，因此代碼中使用了OpenGL擒贸，但僅使用它畫點臀晃。
完整代碼如下觉渴。
#include <iostream>
#include <vector>
#include "GL/glut.h"
using namespace std;
/**
* @brief 定義用于邊表ET和活動邊表AET的通用類Edge
*/
class Edge
{
public:
int ymax;
float x;
float dx;
Edge* next;
};
/**
* @brief 定義用于表示像素點坐標(biāo)的類Point
*/
class Point
{
public:
int x;
int y;
Point(int x, int y)
{
this->x = x;
this->y = y;
}
};
/////////////////////請使用對應(yīng)Demo/////////////////////
/**
* 窗體寬高
*/
/**
* 取消以下兩行的注釋以使用demo1
*/
// const int windowWidth = 18;
// const int windowHeight = 12;
/**
* 取消以下兩行的注釋以使用demo2
*/
// const int windowWidth = 180;
// const int windowHeight = 120;
/**
* Demo3, Demo4, Demo5
*/
const int windowWidth = 1800;
const int windowHeight = 1200;
/**
* 多邊形頂點
*/
/**
* 取消下行注釋以使用demo1
*/
//vector<Point> vertices = { Point(2, 5), Point(2, 10), Point(9, 6), Point(16, 11), Point(16, 4), Point(12, 2), Point(7, 2) };
/**
* 取消下行注釋以使用demo1
*/
//vector<Point> vertices = { Point(20, 50), Point(20, 100), Point(90, 60), Point(160, 110), Point(160, 40), Point(120, 20), Point(70, 20) };
/**
* 取消下行注釋以使用demo3多邊形
*/
//vector<Point> vertices = { Point(200, 500), Point(200, 1000), Point(900, 600), Point(1600, 1100), Point(1600, 400), Point(1200, 200), Point(700, 200) };
/**
* 取消下行注釋以使用demo4箭頭
*/
//vector<Point> vertices = { Point(395, 887), Point(479, 998), Point(1199, 433), Point(1101, 867), Point(1294, 715), Point(1417, 171), Point(857, 163), Point(668, 314), Point(1111, 321) };
/**
* Demo5閃電
*/
vector<Point> vertices = { Point(566, 970), Point(685, 1020), Point(754, 683), Point(985, 768), Point(1037, 481), Point(1208, 546), Point(1233, 179), Point(1140, 440), Point(951, 386), Point(899, 662), Point(668, 562) };
void init(void)
{
glClearColor(1.0, 1.0, 1.0, 0.0);
glMatrixMode(GL_PROJECTION);
gluOrtho2D(0.0, windowWidth, 0.0, windowHeight);
}
void polygonScan()
{
//計算最高點的y坐標(biāo)
int maxY = 0;
for (int i = 0; i < vertices.size(); i++)
{
if (vertices[i].y > maxY)
{
maxY = vertices[i].y;
}
}
//初始化邊表ET和活動邊表AET
Edge *ET[windowHeight];
for (int i = 0; i < maxY; i++)
{
ET[i] = new Edge();
ET[i]->next = nullptr;
}
Edge* AET = new Edge();
AET->next = nullptr;
//清空顯示窗口并設(shè)置畫點顏色為紅色
glClear(GL_COLOR_BUFFER_BIT);
glColor3f(1.0, 0.0, 0.0);
glBegin(GL_POINTS);
//建立邊表ET
for (int i = 0; i < vertices.size(); i++)
{
//取出當(dāng)前點1前后相鄰的共4個點，點1與點2的連線作為本次循環(huán)處理的邊徽惋，另外兩個點點0和點3用于計算奇點
int x0 = vertices[(i - 1 + vertices.size()) % vertices.size()].x;
int x1 = vertices[i].x;
int x2 = vertices[(i + 1) % vertices.size()].x;
int x3 = vertices[(i + 2) % vertices.size()].x;
int y0 = vertices[(i - 1 + vertices.size()) % vertices.size()].y;
int y1 = vertices[i].y;
int y2 = vertices[(i + 1) % vertices.size()].y;
int y3 = vertices[(i + 2) % vertices.size()].y;
//水平線直接舍棄
if (y1 == y2)
continue;
//分別計算下端點y坐標(biāo)案淋、上端點y坐標(biāo)、下端點x坐標(biāo)和斜率倒數(shù)
int ymin = y1 > y2 ? y2 : y1;
int ymax = y1 > y2 ? y1 : y2;
float x = y1 > y2 ? x2 : x1;
float dx = (x1 - x2) * 1.0f / (y1 - y2);
//奇點特殊處理险绘，若點2->1->0的y坐標(biāo)單調(diào)遞減則y1為奇點踢京，若點1->2->3的y坐標(biāo)單調(diào)遞減則y2為奇點
if (((y1 < y2) && (y1 > y0)) || ((y2 < y1) && (y2 > y3)))
{
ymin++;
x += dx;
}
//創(chuàng)建新邊，插入邊表ET
Edge *p = new Edge();
p->ymax = ymax;
p->x = x;
p->dx = dx;
p->next = ET[ymin]->next;
ET[ymin]->next = p;
}
//掃描線從下往上掃描宦棺，y坐標(biāo)每次加1
for (int i = 0; i < maxY; i++)
{
//取出ET中當(dāng)前掃描行的所有邊并按x的遞增順序（若x相等則按dx的遞增順序）插入AET
while (ET[i]->next)
{
//取出ET中當(dāng)前掃描行表頭位置的邊
Edge *pInsert = ET[i]->next;
Edge *p = AET;
//在AET中搜索合適的插入位置
while (p->next)
{
if (pInsert->x > p->next->x)
{
p = p->next;
continue;
}
if (pInsert->x == p->next->x && pInsert->dx > p->next->dx)
{
p = p->next;
continue;
}
//找到位置
break;
}
//將pInsert從ET中刪除瓣距，并插入AET的當(dāng)前位置
ET[i]->next = pInsert->next;
pInsert->next = p->next;
p->next = pInsert;
}
//AET中的邊兩兩配對并填色
Edge *p = AET;
while (p->next && p->next->next)
{
for (int x = p->next->x; x < p->next->next->x; x++)
{
glVertex2i(x, i);
}
p = p->next->next;
}
//刪除AET中滿足y=ymax的邊
p = AET;
while (p->next)
{
if (p->next->ymax == i)
{
Edge *pDelete = p->next;
p->next = pDelete->next;
pDelete->next = nullptr;
delete pDelete;
}
else
{
p = p->next;
}
}
//更新AET中邊的x值，進入下一循環(huán)
p = AET;
while (p->next)
{
p->next->x += p->next->dx;
p = p->next;
}
}
glEnd();
glFlush();
// 釋放邊表和活動邊表占用的內(nèi)存
for (int i = 0; i < maxY; i++)
{
Edge* ptr = ET[i];
if (ptr != nullptr)
{
delete ptr;
ptr = nullptr;
}
}
Edge* p = AET;
while (p)
{
Edge* tmp = p->next;
delete p;
p = tmp;
}
}
int main(int argc, char **argv) {
glutInit(&argc, argv);
glutInitDisplayMode(GLUT_SINGLE | GLUT_RGB);
glutInitWindowPosition(50, 100);
glutInitWindowSize(windowWidth, windowHeight);
glutCreateWindow("Polygon Scan Demo");
init();
glutDisplayFunc(polygonScan);
glutMainLoop();
return 0;
}
代碼中給出了幾個圖形示例代咸，包括三個不同大小的多邊形蹈丸、一個箭頭和一個閃電。運行效果如下：
完整工程點擊這里下載GitHub/PolygonScan呐芥。
這是一個Linux下的CMake工程逻杖，請首先安裝依賴庫
sudo apt install cmake
sudo apt install freeglut3-dev
然后進入工程目錄（將下面的<project_dir>換成你下載的目錄位置），按照如下方式編譯運行
cd <project_dir>
mkdir build
cd build
cmake ..
make
./PolygonScan
即可看到效果贩耐。
結(jié)語
掃描線算法是多邊形掃描轉(zhuǎn)換中的常用算法弧腥，它的特點是效率高厦取，但算法較為復(fù)雜潮太。本文給出了一個簡單的掃描線算法，只是用作簡單的示例虾攻。而對于實際情況铡买，由于多邊形的復(fù)雜性，比如自交多邊形霎箍，即兩條邊具有頂點之外的交點奇钞，這種多邊形無法使用掃描線算法，可能需要先拆分成若干個非自交多邊形之后再處理漂坏。而且景埃，簡單的掃描線算法效果并不理想，從上面給出的三張效果圖可以看出顶别，邊的鋸齒狀很嚴(yán)重谷徙，需要額外進行抗鋸齒處理。
最后驯绎，由于作者本人也不是計算機圖形學(xué)專業(yè)完慧，文中不免有錯誤之處，請大家及時指出剩失。
參考資料
浙江大學(xué)計算機圖形學(xué) 耿建玲
opengl實現(xiàn)直線掃描算法和區(qū)域填充算法 fore_seer
《計算機圖形學(xué) 第四版》Donald Hearn, M.Pauline Baker, Warren R.Carithers
中國科學(xué)院大學(xué)計算機圖形學(xué) 夏時洪
重慶大學(xué)計算機繪圖 楊夢寧屈尼，徐玲
