模型簡化方法
3D電腦圖學的應用近代以來發展地非常廣泛，遊戲、廣告、網頁、動畫、手機等都可以見到3D的應用，3D的運用比起2D更為人們帶來真實感，未來，3D將會大幅取代2D的應用。
而相較與2D，3D因為多了一個維度，無論動作、建模、場景、設計等皆比2D困難許多，越是精細的動作、精緻的模型，電腦的運算也越是複雜。
精緻的模型比起2D技術使用了更多的網格，網格較多時，動作所進行的計算也較為複雜，載入模型相對較慢。在載入大量模型的場景中取捨模型的精緻度就顯得相當重要，此文探討如何盡量在維持現有的形狀下，降低網格數達到簡化模型的效果。

Background
體素化
體素化是指，把物體的形狀轉換成最接近該物體形狀的體素表示形式，根據每個體素的大小與物體形狀的相似度也不同，
體素化的方式根據計算方法的不同所產生的體素化模型的形狀也不同，體素化模型範例如圖一。


▲ 圖一：體素化模型(圖片來源Mincraft寺廟http://www.dayinpai.com/model/detail/82780748803)




Gift Wrapping Algorithm
在一個平面上，假設散步多個點，根據Gift Wrapping Algorithm可以找到最外層包覆的點，依照順序連接後可以得到包覆所有點的凸多邊形，如圖二，作法為：
步驟一：尋找起始點，該點的X座標或Y座標為極值，這是為了保證該點是最外面一點，
步驟二：以起始點為起點，順時針無限延伸方向，尋找下一個連接點，並設該連接點為下次尋找的起始點，
步驟三：重複步驟一，步驟二直到下個連接點為步驟一的起始點，



▲ 圖二：Gift Wrapping Algorithm(取自http://www.csie.ntnu.edu.tw/~u91029/ConvexHull.html)


3D模型的簡化
模型的簡化目的在於，透過簡化模型盡量減少模型使用的網格，在載入模型或即時運算時減少計算量，減輕電腦計算的負擔，
在本文中利用兩個步驟達到減少網格的效果：體素化和消除內部網格，

體素化
經過體素化後的模型，因為法向量只有六個方向的關係，有效地減少了模型的複雜度，體素越小，體素化後的網格越多，體素化模型也越接近原本的模型，本文中體素化利用二元樹切割方式，移除未含原模型之體素，盡力保留完好的最大體素，達到減少體素化模型網格數的效果，切割次數越多，體素化後的模型越接近原模型，
透過以下檢測步驟，來決定體素是否需要切割，保留或移除：
步驟一：檢測模型三個軸極值座標，得到最大塊長方體，該長方體為完好包覆模型之最小長方體作為體素，
步驟二：分別為Ｘ軸，Ｙ軸，Ｚ軸為法向量且穿過體素中心做切割（即二元樹切割），形成８個相同的體素
步驟三：判別體素是否保留或移除，檢測方式如下：
判別體素是否為體素化模型內部（即六個方向是否有連接體素，有即為內部）
判別體素是否包含原模型一網格
判別體素是否包含原模型一邊
判別體素是否包含原模型一頂點
先判別1.3.2、1.3.3、1.3.4，如果皆不滿足則移除該體素，再判別1.3.1，如果為內部，則移除，
步驟四：對每塊體素重複步驟二，步驟三，步驟四，直到切割次數達到設定次數

經過上述四個步驟可以得到最外側的體素，
 
保留最外層的面，達到更進一步減少頂點的目的
經過體素化並且保留了最外層的體素，然而有些面會存在於體素模型內部，這是由於最外層體素形成封閉空間，移除內部的面只保留最外層的面，達到進一步減少頂點的效果。
體素化模型必為封閉，每塊體素都必然找的到一個以上的連接體素，且每塊連接的體素中心XYZ軸距離分別相等，我們可以將此體素化模型拆解視為，以體素長度為單位長的每一層體素，由下往上塔建，由於存在這些特性，因此可參考Gift Wrapping Algorithm，取得每一層塔建的最外部側面（頂部和底部取的最外部的側面後封蓋即可），步驟如下：

步驟一：決定一軸為塔建方向，假設以Z軸正向為塔建方向，依順時針方向尋找最外部的面圍成封閉區域，
步驟二：計算體素間的XYZ軸單位長度
步驟三：尋找起點，該起點必須為X或Y座標為極值的一面
步驟四：由起點（面中心座標）依順時針外切方向，依序向90，0，270方向尋找下個連接該面的中心點，這是因為體素每個角度皆為90度，在不回頭的情況下，只需要找三個方向即可，依照尋找的向量決定搜尋長度為X軸或Y軸長度
步驟五：若回到起點則停止搜尋，得到該層封閉區域
步驟六：消除封閉區域裡的所有的面，偵測方式為計算體素模型最大距離，偵測該層每一個面XY軸正負方向搜尋是否有最大距離內使否有形成封閉區域的外圍面，有則消除無則保留
步驟七：若除了形成封閉區域外圍的面以外還有未消除的面，重複2.2、2.3、2.4、2.5步驟，直到除了形成封閉區域的外圍面外無其他的面為止
步驟八：由Z值最小值至最大值重複步驟2.1~2.6
步驟九：封蓋頂部以及底部，方法為：
投影所有的頂點至Z座標大於體素模型Z座標最大值且法向量(0,0,1)的面T，以及Z座標小於體素模型Z座標最小值且法向量(0,0,-1)的面B
面T依據體素Z軸長度為單位依序Z軸負方向位移，若有與體素模型座標重複次數為奇數，則加入該面
面B依據體素Z軸長度為單位依序Z軸正方向位移，若有與體素模型座標重複次數為奇數，則加入該面

經過上述的步驟後，就可以得到消除內部頂點的體素模型，

趨近於原模型
體素化模型的體素大小決定該體素化模型是否接近於原模型，體素越小，則體素化模型越接近原模型，但頂點也相對增加，對於曲體、斜體，體素化模型也無法有效地表現出這些形狀，
我們希望能利用頂點相對較少的體素化模型，在頂點數目不變的情況下，能盡力表現出原模型的形狀，理想狀態是，這些頂點移動至能夠表現出模型外圍輪廓的座標，使形成的新模型能大致表現出原模型的形狀，
最直觀的方法是，使體素化模型的每個頂點移動到原模型上的外圍頂點使盡力表象出原模型的形狀，這篇文章選擇計算每個頂點至原模型上最接近的一點，注意的是因為體素化模型的形狀包覆著原模型，因此要限制體素化模型頂點只能向內部平移。
判別內部外部的方式，因為原模型被體素化模型包覆，因此只要判別體素化模型頂點的頂點向量與目標頂點的頂點向量同向即可，判別方式為只要兩頂點向量內積小於0即可：

圖三、圖四是實際操作後的圖：


▲ 圖三:101模型(4X4X4)




▲ 圖四:劇院(8X8X8)



如此一來，不需要在切割很細緻的情況下(如圖一)也能大致上形成原模型的外觀並且大量減少頂點減少運算負擔。

結論
透過此方法，在程式需要大量模型的情況下，可以根據狀況調整不同的切割次數，並且快速自動產生簡易的新模型，不需再重新建模，且體素化後的處理與同樣切割次數的體素模型相比更貼近原模型。(本文由凌群電腦提供，作者目前服務於凌羣凌群電腦系統整合事業群技術支援處，專長為電腦圖學演算法, ASP.NET設計)

參考文獻
COHEN, J., OLANO, M., AND MANOCHA, D. 1998. Appearance preserving simplification. In SIGGRAPH ’98: Proc. 25th
基于八叉樹的三維網格模型體素化方法工程圖學學報》2005年 第4期 | 吳曉軍 劉偉軍 王天然 中國科學院沈陽自動化研究所先進制造實驗室 沈陽110016