掃描線算法完全解析

引言

自從今年春天選修了計算機圖形學(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即可清女。

解決了這三個問題钱烟,我們就可以給出下面的算法流程:

  1. 將掃描線初始y坐標(biāo)設(shè)為ET中非空元素的最小序號。
  2. 將AET初始化為空嫡丙。
  3. 循環(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é)計算機繪圖 楊夢寧屈尼,徐玲

最后編輯于
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者
  • 序言:七十年代末册着,一起剝皮案震驚了整個濱河市,隨后出現(xiàn)的幾起案子脾歧,更是在濱河造成了極大的恐慌甲捏,老刑警劉巖,帶你破解...
    沈念sama閱讀 221,406評論 6 515
  • 序言:濱河連續(xù)發(fā)生了三起死亡事件鞭执,死亡現(xiàn)場離奇詭異摊鸡,居然都是意外死亡,警方通過查閱死者的電腦和手機蚕冬,發(fā)現(xiàn)死者居然都...
    沈念sama閱讀 94,395評論 3 398
  • 文/潘曉璐 我一進店門免猾,熙熙樓的掌柜王于貴愁眉苦臉地迎上來,“玉大人囤热,你說我怎么就攤上這事猎提。” “怎么了旁蔼?”我有些...
    開封第一講書人閱讀 167,815評論 0 360
  • 文/不壞的土叔 我叫張陵锨苏,是天一觀的道長。 經(jīng)常有香客問我棺聊,道長伞租,這世上最難降的妖魔是什么? 我笑而不...
    開封第一講書人閱讀 59,537評論 1 296
  • 正文 為了忘掉前任限佩,我火速辦了婚禮葵诈,結(jié)果婚禮上,老公的妹妹穿的比我還像新娘祟同。我一直安慰自己作喘,他們只是感情好,可當(dāng)我...
    茶點故事閱讀 68,536評論 6 397
  • 文/花漫 我一把揭開白布晕城。 她就那樣靜靜地躺著泞坦,像睡著了一般。 火紅的嫁衣襯著肌膚如雪砖顷。 梳的紋絲不亂的頭發(fā)上贰锁,一...
    開封第一講書人閱讀 52,184評論 1 308
  • 那天,我揣著相機與錄音滤蝠,去河邊找鬼豌熄。 笑死,一個胖子當(dāng)著我的面吹牛几睛,可吹牛的內(nèi)容都是我干的房轿。 我是一名探鬼主播,決...
    沈念sama閱讀 40,776評論 3 421
  • 文/蒼蘭香墨 我猛地睜開眼,長吁一口氣:“原來是場噩夢啊……” “哼囱持!你這毒婦竟也來了夯接?” 一聲冷哼從身側(cè)響起,我...
    開封第一講書人閱讀 39,668評論 0 276
  • 序言:老撾萬榮一對情侶失蹤纷妆,失蹤者是張志新(化名)和其女友劉穎盔几,沒想到半個月后,有當(dāng)?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體掩幢,經(jīng)...
    沈念sama閱讀 46,212評論 1 319
  • 正文 獨居荒郊野嶺守林人離奇死亡逊拍,尸身上長有42處帶血的膿包…… 初始之章·張勛 以下內(nèi)容為張勛視角 年9月15日...
    茶點故事閱讀 38,299評論 3 340
  • 正文 我和宋清朗相戀三年,在試婚紗的時候發(fā)現(xiàn)自己被綠了际邻。 大學(xué)時的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片芯丧。...
    茶點故事閱讀 40,438評論 1 352
  • 序言:一個原本活蹦亂跳的男人離奇死亡,死狀恐怖世曾,靈堂內(nèi)的尸體忽然破棺而出缨恒,到底是詐尸還是另有隱情,我是刑警寧澤轮听,帶...
    沈念sama閱讀 36,128評論 5 349
  • 正文 年R本政府宣布骗露,位于F島的核電站,受9級特大地震影響血巍,放射性物質(zhì)發(fā)生泄漏萧锉。R本人自食惡果不足惜,卻給世界環(huán)境...
    茶點故事閱讀 41,807評論 3 333
  • 文/蒙蒙 一述寡、第九天 我趴在偏房一處隱蔽的房頂上張望柿隙。 院中可真熱鬧,春花似錦辨赐、人聲如沸优俘。這莊子的主人今日做“春日...
    開封第一講書人閱讀 32,279評論 0 24
  • 文/蒼蘭香墨 我抬頭看了看天上的太陽。三九已至惭婿,卻和暖如春不恭,著一層夾襖步出監(jiān)牢的瞬間,已是汗流浹背财饥。 一陣腳步聲響...
    開封第一講書人閱讀 33,395評論 1 272
  • 我被黑心中介騙來泰國打工换吧, 沒想到剛下飛機就差點兒被人妖公主榨干…… 1. 我叫王不留,地道東北人钥星。 一個月前我還...
    沈念sama閱讀 48,827評論 3 376
  • 正文 我出身青樓沾瓦,卻偏偏與公主長得像,于是被迫代替她去往敵國和親。 傳聞我的和親對象是個殘疾皇子贯莺,可洞房花燭夜當(dāng)晚...
    茶點故事閱讀 45,446評論 2 359

推薦閱讀更多精彩內(nèi)容