引言
自從今年春天選修了計(jì)算機(jī)圖形學(xué)課程，這朵烏云就在頭頂盤旋不散。始終弄不明白計(jì)算機(jī)圖形學(xué)到底在研究什么，所謂的Imaging、Modeling、Rendering和Animation各自又是什么意思?？傆X得課上講的實(shí)在太過抽象，實(shí)踐的經(jīng)歷太少，到最后也不過是囫圇吞棗，不知其味。
雖然不再從事計(jì)算機(jī)圖形學(xué)相關(guān)研究，但為了彌補(bǔ)這些遺憾，最近我又重拾這些知識(shí)，更深入細(xì)致地學(xué)習(xí)一遍圖形學(xué)基礎(chǔ)知識(shí)。在學(xué)習(xí)完多邊形掃描轉(zhuǎn)換中的掃描線算法后，我決心親自寫代碼實(shí)現(xiàn)它，并動(dòng)筆寫下這一篇文章。
掃描線算法是干什么用的
我們?nèi)绾卧谟?jì)算機(jī)程序中存儲(chǔ)幾何圖形呢？比如多邊形？最容易想到的方法就是保存多邊形的頂點(diǎn)坐標(biāo)。只要按順序保存了多邊形各個(gè)頂點(diǎn)的坐標(biāo)，這個(gè)多邊形就唯一確定了。另一方面，顯示器是如何顯示幾何圖形的呢？顯示設(shè)備通常提供一個(gè)幀緩沖存儲(chǔ)器（俗稱顯存），可以把它當(dāng)做二維數(shù)組，該數(shù)組存儲(chǔ)的值與屏幕上顯示的每一像素的顏色一一對(duì)應(yīng)。那么問題來了，如何把程序中的幾何圖形轉(zhuǎn)換成顯存中的幾何圖形？這就是掃描線算法的用途。
總結(jié)下來：掃描線算法把幾何圖形在計(jì)算機(jī)中的頂點(diǎn)表示法轉(zhuǎn)換成點(diǎn)陣表示法。需要注意的是轉(zhuǎn)換成點(diǎn)陣表示法后其實(shí)是對(duì)多邊形進(jìn)行了填充，而不是只有輪廓。
基本思想
由于多邊形千變?nèi)f化，要想填充多邊形內(nèi)部的所有像素，需要找到一種合適的規(guī)則，能夠沿著一個(gè)方向，一個(gè)像素不漏地把多邊形內(nèi)部填滿，同時(shí)不污染多邊形外部。于是我們發(fā)明了一條水平方向的掃描線，它從y=0開始，判斷與多邊形的交點(diǎn)，這些交點(diǎn)把掃描線分成了若干段，我們需要判斷哪些段在多邊形內(nèi)部，哪些段在多邊形外部，然后把內(nèi)部的部分著色，完成后，令y=y+1，即掃描線上移一格，重復(fù)之前的操作，直到掃描線不再與多邊形的任何部分相交。
舉例說明，下圖所示為多邊形P1P2P3P4P5P6，而且同時(shí)畫出了掃描線掃描過程中經(jīng)過的四個(gè)位置y=1、y=2、y=6和y=7。
掃描線算法的難點(diǎn)在于如何判斷掃描線被多邊形分割后哪些部分在多邊形內(nèi)部，哪些部分在多邊形外部。
讓我們仔細(xì)觀察上圖，答案就在圖中。對(duì)于未經(jīng)過頂點(diǎn)的掃描線，如y=6，總是與多邊形有偶數(shù)個(gè)交點(diǎn)，而且位于多邊形內(nèi)部的片段和位于多邊形外部的片段交替存在。對(duì)于經(jīng)過了頂點(diǎn)的掃描線，如y=1、y=2和y=7，與多邊形的交點(diǎn)既可能是偶數(shù)，也可能是奇數(shù)。但是如果我們進(jìn)一步劃分，這些經(jīng)過了頂點(diǎn)的掃描線有些經(jīng)過了極值頂點(diǎn)，如y=1和y=7，它們的交點(diǎn)個(gè)數(shù)是奇數(shù)；而有些經(jīng)過了非極值頂點(diǎn)，如y=2，它們的交點(diǎn)個(gè)數(shù)是偶數(shù)。這樣的話，不如做一個(gè)特殊處理，把所有極值頂點(diǎn)當(dāng)成兩個(gè)點(diǎn)，就可以保證掃描線與多邊形的交點(diǎn)總是偶數(shù)。
當(dāng)然，把交點(diǎn)個(gè)數(shù)湊成偶數(shù)是有意義的，湊成偶數(shù)后就可以把這些交點(diǎn)從左到右兩兩配對(duì)，配對(duì)成功的兩個(gè)點(diǎn)之間的像素全部著色。例如，上圖的掃描線y=6與多邊形的交點(diǎn)序列是ABCD，從左到右兩兩配對(duì)為AB和CD，然后將AB之間著色，CD之間著色。
基本思想就是這樣，其實(shí)很容易理解。不過用代碼實(shí)現(xiàn)起來并不那么容易，需要考慮很多細(xì)節(jié)。
代碼實(shí)現(xiàn)詳解
首先需要提醒的是，掃描線算法的基本思想很簡單，但不同的實(shí)現(xiàn)方式會(huì)有很大的效率差異。因此，如何設(shè)計(jì)數(shù)據(jù)結(jié)構(gòu)及算法才能使掃描線算法以最快的速度完成，才是接下來我們需要面對(duì)的問題。
從以下幾個(gè)方面考慮：
問題1：如何計(jì)算當(dāng)前掃描線與多邊形的交點(diǎn)？
直觀做法：根據(jù)多邊形的頂點(diǎn)求出各個(gè)邊的方程，然后將掃描線的縱坐標(biāo)代入方程求出橫坐標(biāo)，搞定！
遺憾的是，這需要對(duì)每條掃描線遍歷所有邊，性能肯定是吃不消的。我們需要尋找一種只遍歷一次邊的方法。同時(shí)，使用方程求交點(diǎn)會(huì)用到乘法或除法運(yùn)算，對(duì)性能也是一種傷害。因此，我們提出了下面兩個(gè)數(shù)據(jù)結(jié)構(gòu)。
-
邊表（Edge Table）
所有邊按下端點(diǎn)的y坐標(biāo)歸類。
邊表
其中，每條邊包含四個(gè)成員，分別是
-
活動(dòng)邊表（Active Edge Table）
與當(dāng)前掃描線相交的邊稱為活動(dòng)邊，把它們按與掃描線交點(diǎn)x坐標(biāo)（x相等時(shí)按?x）遞增排序。
掃描線y=6時(shí)的活動(dòng)邊表如下
活動(dòng)邊表
與邊表類似，每條邊同樣包含四個(gè)成員，分別是
下面的代碼定義了邊表和活動(dòng)邊表。
//定義用于邊表ET和活動(dòng)邊表AET的通用類Edge
class Edge
{
public:
int ymax;
float x;
float dx;
Edge* next;
};
//邊表
Edge *ET[windowHeight];
//活動(dòng)邊表
Edge *AET;
利用這兩個(gè)數(shù)據(jù)結(jié)構(gòu)就很容易計(jì)算出每條掃描線與多邊形的交點(diǎn)了。我們只需要令掃描線從下往上掃描，已知每條邊的下端點(diǎn)x坐標(biāo)和?x，就可以使用增量法計(jì)算出這條邊上所有點(diǎn)的x坐標(biāo)。具體方法放到后面敘述。
問題2：如何解決前面提到的極值頂點(diǎn)按照兩個(gè)處理的問題？
如果兩條邊相交，它們的交點(diǎn)就是一個(gè)頂點(diǎn)。事實(shí)上，這個(gè)點(diǎn)本來就是按照兩個(gè)點(diǎn)處理的，因?yàn)樗謩e屬于兩條邊。那么這個(gè)問題其實(shí)應(yīng)該轉(zhuǎn)換成：如何把非極值頂點(diǎn)按照一個(gè)處理？解決辦法是把頂點(diǎn)處從上面斷開，如下圖所示。缺口在y坐標(biāo)上的長度是1個(gè)像素，所以并不會(huì)產(chǎn)生不利影響。
在后面的代碼實(shí)現(xiàn)中，我們會(huì)在建立邊表ET時(shí)判斷非極值頂點(diǎn)并對(duì)其做特殊處理，請(qǐng)稍加注意。
問題3：如何快速配對(duì)交點(diǎn)并著色？
活動(dòng)邊表AET中存儲(chǔ)了所有與當(dāng)前掃描線相交的邊及其交點(diǎn)坐標(biāo)。配對(duì)的工作就自然變得很簡單，只需要遍歷一遍AET即可。
解決了這三個(gè)問題，我們就可以給出下面的算法流程：
- 將掃描線初始y坐標(biāo)設(shè)為ET中非空元素的最小序號(hào)。
- 將AET初始化為空。
- 循環(huán)執(zhí)行以下步驟，直到ET和AET都變?yōu)榭铡?br>
(1) 如果 ET[y] 非空，則將其中的所有邊取出并插入到AET中，按x（若x相等則按?x）遞增方向排序。
(2) 若AET非空，將AET中的邊按順序兩兩配對(duì)并填色。
(3) 刪去AET中滿足y=ymax的邊。
(4) 對(duì)于AET中所有邊，賦值x = x + ?x。
(5) y = y + 1，掃描線上移一像素。
依照該流程，我在Linux下使用c++實(shí)現(xiàn)了這個(gè)算法。由于無法真正實(shí)現(xiàn)向幀緩沖存儲(chǔ)器填色，因此代碼中使用了OpenGL，但僅使用它畫點(diǎn)。
完整代碼如下。
#include <iostream>
#include <vector>
#include "GL/glut.h"
using namespace std;
/**
* @brief 定義用于邊表ET和活動(dòng)邊表AET的通用類Edge
*/
class Edge
{
public:
int ymax;
float x;
float dx;
Edge* next;
};
/**
* @brief 定義用于表示像素點(diǎn)坐標(biāo)的類Point
*/
class Point
{
public:
int x;
int y;
Point(int x, int y)
{
this->x = x;
this->y = y;
}
};
/////////////////////請(qǐng)使用對(duì)應(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;
/**
* 多邊形頂點(diǎn)
*/
/**
* 取消下行注釋以使用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()
{
//計(jì)算最高點(diǎn)的y坐標(biāo)
int maxY = 0;
for (int i = 0; i < vertices.size(); i++)
{
if (vertices[i].y > maxY)
{
maxY = vertices[i].y;
}
}
//初始化邊表ET和活動(dòng)邊表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è)置畫點(diǎn)顏色為紅色
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)前點(diǎn)1前后相鄰的共4個(gè)點(diǎn)，點(diǎn)1與點(diǎn)2的連線作為本次循環(huán)處理的邊，另外兩個(gè)點(diǎn)點(diǎn)0和點(diǎn)3用于計(jì)算奇點(diǎn)
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;
//分別計(jì)算下端點(diǎn)y坐標(biāo)、上端點(diǎn)y坐標(biāo)、下端點(diǎn)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);
//奇點(diǎn)特殊處理，若點(diǎn)2->1->0的y坐標(biāo)單調(diào)遞減則y1為奇點(diǎn)，若點(diǎn)1->2->3的y坐標(biāo)單調(diào)遞減則y2為奇點(diǎn)
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中的邊兩兩配對(duì)并填色
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值，進(jìn)入下一循環(huán)
p = AET;
while (p->next)
{
p->next->x += p->next->dx;
p = p->next;
}
}
glEnd();
glFlush();
// 釋放邊表和活動(dòng)邊表占用的內(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;
}
代碼中給出了幾個(gè)圖形示例，包括三個(gè)不同大小的多邊形、一個(gè)箭頭和一個(gè)閃電。運(yùn)行效果如下：
完整工程點(diǎn)擊這里下載GitHub/PolygonScan。
這是一個(gè)Linux下的CMake工程，請(qǐng)首先安裝依賴庫
sudo apt install cmake
sudo apt install freeglut3-dev
然后進(jìn)入工程目錄（將下面的<project_dir>換成你下載的目錄位置），按照如下方式編譯運(yùn)行
cd <project_dir>
mkdir build
cd build
cmake ..
make
./PolygonScan
即可看到效果。
結(jié)語
掃描線算法是多邊形掃描轉(zhuǎn)換中的常用算法，它的特點(diǎn)是效率高，但算法較為復(fù)雜。本文給出了一個(gè)簡單的掃描線算法，只是用作簡單的示例。而對(duì)于實(shí)際情況，由于多邊形的復(fù)雜性，比如自交多邊形，即兩條邊具有頂點(diǎn)之外的交點(diǎn)，這種多邊形無法使用掃描線算法，可能需要先拆分成若干個(gè)非自交多邊形之后再處理。而且，簡單的掃描線算法效果并不理想，從上面給出的三張效果圖可以看出，邊的鋸齒狀很嚴(yán)重，需要額外進(jìn)行抗鋸齒處理。
最后，由于作者本人也不是計(jì)算機(jī)圖形學(xué)專業(yè)，文中不免有錯(cuò)誤之處，請(qǐng)大家及時(shí)指出。
參考資料
浙江大學(xué)計(jì)算機(jī)圖形學(xué) 耿建玲
opengl實(shí)現(xiàn)直線掃描算法和區(qū)域填充算法 fore_seer
《計(jì)算機(jī)圖形學(xué) 第四版》Donald Hearn, M.Pauline Baker, Warren R.Carithers
中國科學(xué)院大學(xué)計(jì)算機(jī)圖形學(xué) 夏時(shí)洪
重慶大學(xué)計(jì)算機(jī)繪圖 楊夢寧，徐玲
