多邊形的布爾運算-或 與 異或 減法

www.cs.man.ac.uk

該頁面中最底端也有其他人的輪子.

不過呢,它們的協議大多不允許商用,就只好自己寫一個了,準確講,是基於一篇20年前的文章改編的輪子.

原演算法詳見

Polygon Boolean operations on sets of polygons?

boolean.klaasholwerda.nl

演算法正文

I.需要定義的數據結構

1.點:需要存儲一個二維點的位置信息

2.邊:需要存儲兩個點

3.多邊形:存儲邊

4.多邊形組:存儲多邊形

II.步驟

演算法規則:傳入兩個多邊形組 輸出一個多邊形組,為了方便,下文以L,R代表兩個輸入參數,以O代表輸出多邊形組

1.將傳入的點的數組轉換為邊,原作者在這一步對每個點進行了降精度操作,如:(int)(position.x*100),這樣整個操作流程就會以int型完成,不過在計算機性能足夠的情況應該不需要進行這一步.

這一步應該可以提前在new多邊形時做好,這樣可以節省演算法時間.

2.計算邊之間的交叉,這一步採用了掃描線法.先將L,R的所有點存儲到一個數組,並按照從左到右進行排序,接下來重複以下步驟:

a.選取相鄰兩個點形成一個掃描線束(scanbeam),因為已經排序,其間必定無其他點

b.遍歷所有邊,找出所有被掃描線束穿過的邊,如下圖

c.遍歷b中得到的邊,對其標記與掃描線束左側交點的y值,即上圖的ysp

d.同c,不過這次要標記右側交點,即圖中的ysn

e.按照ysn排序,並按順序遍歷ysp,如有兩邊的ysp順序不同於ysn順序,其間必有交點,計算交點位置(STFW),並為每個邊queue交點,所以一個交點會被添加到兩個邊上

比較ysn和ysp有多種辦法,比如先根據ysp排序,再根據ysn進行雞尾酒排序,每次交換即為交叉

f.移動到下一個掃描線束

3.對每條邊正式插入交點,這一步簡單,直接遍歷每條邊的交點並按照順序排列插入生成多個新邊

4.為每條邊標記是否在另一個多邊形組內,這一步其實可以在2中直接完成,原文沒有詳細講述,但我的做法如下:

對一條掃描線觀察可以發現,每次掃描線經過一條邊時會從該邊所屬多邊形外部進入內部,如圖,便可知在該掃描線交點這條邊在內外的情況

在2-d中進行此操作,對同一邊允許覆蓋之前的值,因為如果一條邊無任何交叉,它的內外值必定一致,如果有交叉,每次交叉必定會使內外值更改,要麼內->外,要麼反之.所以在3中插入新邊時,要根據2-d中求得的內外值對新邊交替設置內外值

5.根據點,線之間的連接狀況輸出圖像

通過觀察可知,如果在經歷上述步驟後無任何交叉點生成,那麼L,R要麼分離,要麼相互包含,這一步自行判斷輸出即可

若有交叉點,可以知道O中至少含有兩個交叉點,所以之前生成交叉點時可以記錄下它們,並在此步驟進行遍歷,進行以下步驟:

a.選取一個從未被選中過的(在b-e中也沒有被選中過的)交叉點作為當前點(current)

b.找出以current為頭的邊

c.若有符合條件的邊,則添加current,並把邊的尾設為current,回到b,否則到d

d.找出以current為尾的邊

e.若有符合條件的邊,則添加current,並把邊的頭設為current,回到d,否則回到b

在上述選擇中不可連續選擇同一個邊,這種情況可能發生在c剛剛到d的情況,因此應在c,e中忽視上一個選擇過的邊

在選擇過程中一旦回到最初時的點,說明已經形成環路,輸出該多邊形,並回到a,若所有交叉點已被檢查完畢,結束演算法

6.對於5中所謂"條件"

或:在L或R上,在另一個多邊形組的外部

與:同時在L和R內

異或:滿足或^滿足與

減法:以L-R為例,在L上且在R外,或在R上且在L內

如圖

至此,演算法就算結束了,原文中還有關於自交,簡化圖形的擴展,各位有興趣可以自行探索,本人也僅僅是一個高中生,會c#和unity而已,如有錯誤不足還請教誨

後記

最初的動機來自於彩虹六號這款遊戲,其中的牆體破壞令我眼前一亮,根據ubi在GDC大會上的一次演講發現需要該演算法,也就是說該演算法配合三角剖分可以進行動態的模型布爾運算,當然,僅限平面模型,現在開發的一個項目就需要這個功能.不得不吐槽國內關於計算圖形學的書真是少得可憐,之前買了一本《計算幾何—演算法設計、分析及應用》——周培德,第一眼還以為被民科坑了錢,但演算法還行,希望有這方面的大佬能分享一下好的學習來源

放個效果視頻結尾,視頻大小為2M