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