首先吐槽一下：今天考IT項目管理，100道選擇題。前幾天考配置管理，10道大題。如今的老師都喜歡走極端……
這個方法是在考完試回宿舍的路上想到的，適用于2D與3D。主要想法是這樣的。給定兩個幾何圖形A、B，把A和B都分成『內(nèi)『、『外』兩部分。A的『內(nèi)』就是處于B內(nèi)部的部分。于是A和B就變成了A內(nèi)、A外、B內(nèi)、B外。然后就有如下公式：
·A and B=A外+B外
·A sub B=A外+B內(nèi)
·A or B=A內(nèi)+B內(nèi)
·A xor B=A外+B外+A內(nèi)+B內(nèi)
這種數(shù)據(jù)結(jié)構(gòu)是為了滿足如下算法：一個A點在圖形內(nèi)<==>過這個點的直線交圖形與點集P，其中|{Pi|Pi<=A}|和|{Pi|Pi>=A}|都是奇數(shù)。注意我們使用的是<=和>=，這樣的話兩個集合的數(shù)量的奇偶性都是一致的。這個算法無論2D、3D多邊形還是3D多面體都能適用，就算是這個圖形有孔（鑲嵌）也可以，而且跟凹凸體無關(guān)。這個算法只有一種情況是不能用的：就是自己跟自己有交叉，譬如我們習(xí)慣的5條直線構(gòu)成五角星的畫法。這樣的話首先要對這個圖形進行處理，成為鑲嵌的圖形。
讓我們來圖示一下。現(xiàn)在我們給出兩個回形的紅色和藍色向前多邊形：
然后我們把兩個圖形分為內(nèi)外一共四部分，其中內(nèi)使用粗線：
我們把這個圖形轉(zhuǎn)換成拓撲結(jié)構(gòu)，得到了下面的連線圖。現(xiàn)在讓我們來求藍 sub 紅，也就是藍外+紅內(nèi)：
我們可以很容易地看到現(xiàn)在圖形分成了4各部分，因為下面的拓撲結(jié)構(gòu)構(gòu)成的圖一共有4個連同體。
后來我自己做過實驗，求藍 And 紅的時候圖形會被分成6個連同體，其中有5個是鑲嵌的孔。但是哪個是孔在整個過程中并沒有關(guān)系。因為我們只需要把所有的Component求出來，內(nèi)Component就是Component內(nèi)的一點在另一個圖里，而且判斷是不是內(nèi)部點的算法已經(jīng)給出了。整個流程跟哪一個連同體是孔并沒有關(guān)系。而且在實際情況下，2D多邊形和3D多面體的渲染并不在乎哪個是孔，可以正確渲染出來。唯獨3D多邊形在乎。這種情況下再慢慢處理吧。而且判斷的算法也是差不多的。不過我似乎沒有見到3D多邊形的布爾運算有什么常見的應(yīng)用。
期末考過后就可以開始寫布爾運算的代碼了。
posted on 2008-06-16 19:20
陳梓瀚(vczh) 閱讀(4568)
評論(7) 編輯 收藏 引用 所屬分類:
2D