基于Unity3d 的mesh 切割及優化

文/劉柯壯 賀體剛

1 問題分析

在VR 項目中，玩家需要用模擬的刀將飛過來的三維模型切開，被切到的模型應精確的沿切面分成兩個模型，并且生成的模型碎片也要允許切割。

由于每次揮刀的角度、方向和切割次數都是不確定的，所以無法用固定的幾個動畫來達到準確的切割效果。經過考慮，最終將問題的解決方向定在了模型的mesh 切割上。

對于模型的mesh 切割，首先確定以下兩個前提：

（1）被切割的模型面數較低。

（2）被切割物體為凸多面體。

為了將問題簡化，我們可以先假設這樣一個需求：空間中有一個立方體，目的是要以任意一個角度將模型分為兩半。

2 解決方案

在Unity 創建的cube 中，如果被切割源從中間分為兩半后，在切面處將會產生新的頂點和三角面，問題的關鍵就在于如何確定新生成的頂點和三角面、如何補全剖面以及如何優化。

2.1 確定切割源

即立方體在什么位置以什么角度被切開，這里我們可以把切割源想成一個平面，將立方體分為兩半。這里采用平面的點法式來確定這一平面，即需要獲取平面上一點和平面的法向量。

2.2 頂點分組

將一個立方體分為兩半，先要把立方體是的頂點分為兩組，分組依據是頂點是否在切割源的同一側。利用切割源點到各個頂點的向量與切割源的法向量的點乘的正負性來判斷，將結果存入一個bool 類型的數組中，數組名為above，供后面使用。

2.3 構建三角形索引數組與創建剖面點

以mesh 三角形索引的順序依次訪問3 個頂點對應的above 值。如果這三個above 值相同，則表示整個三角面都在切割源的一側，不需要做任何修改。如果三個頂點的above 值不相同，則表示該三角面將會被切割源分為兩半。這時三角面的兩條邊必然都與切割源所在平面交于一點，這兩個點就是切割之后要生成的剖面點。將計算剖面點坐標轉化為以下數學問題：

已知：平面的法向量（切割源法向量），平面經過一點的坐標（切割源經過的一點），直線經過兩點的坐標（三角面一條邊的兩個頂點）。求：平面與直線的交點。

設：平面的一點為n（n1,n2,n3），平面法向量為Vp（Vp1,Vp2,Vp3），直線經過一點為m（m1,m2,m3），直線方向向量為V（V1,V2,V3）。

可求得焦點坐標O：O=m+V*t

將兩個剖面點計算出來后，將一個三角面拆分為3 個三角面加入相應的三角形索引集合中。重復經過以上步驟，便可以將所有的剖面點分配到相應的集合中。整個立方體已經被切割源分到了兩邊，但被切開的剖面處是不閉合的。

2.4 連接剖面三角形

首先，剖面頂點集合是無序的，導致無法立即確定要連接的剖面三角形索引。但是，在以上方法生成剖面點的時候，可以發現兩個特點：

（1）剖面點列表中按索引第i（偶數）個點與第i+1 個點是相連的，一定構成三角面的一條邊。

（2）每個剖面點處其實都被重復生成了兩次，這兩個重合點連接著其他不同的剖面點。

選定剖面頂點中第一個點作為定點，定點之后的兩個點作為活動點（i 和i+1），以逆時針的順序旋轉一周，遍歷完所有頂點，該過程中兩活動點每次都與定點連接一次，通過切面的法線確定三個點的連接順序。最后會得到一個以定點向其他各點“發散”的結構。

根據第一個特點，我們可以確定一個剖面三角形的兩個頂點，一個作為定點，另一個為活動點，再根據第二個特點確定第三個頂點，構成三角形。方法是先找到兩個頂點的其中一個的重合點(可以根據遍歷剖面點列表，根據兩點的距離小于極小值確定重合點)，再找到該重合點所連接的點，這個點就是需要找的剖面三角形的第三個頂點。連接這個三角形之后，將第三個頂點作為活動點，以上述同樣的方法尋找第三個頂點。

以此方法旋轉一周，剖面連接完成。

2.5 對剖面點進行優化

雖然程序運行起來，模型可以切割了，但遺憾的是切割物體產生的速度太慢，多次切割很容易卡死，在剖面處會經常出現“破面”情況。

觀察上述的第五步，可以感覺到那里的運算和復雜，并且不夠精確，多次切割很容易產生密集的三角形，剖面點也會在一個很小的區域內集中，這樣通過距離計算的重合點就很容易找錯，造成后續的崩潰和“破面”。為了方便剖面的頂點的連接，我們必須要確定連接各頂點的依據，并將它們以一定順序排列。

由于剖面點是依據三角面的邊生成的，而mesh 上的三角面是兩兩相連的，即每條邊都是兩個三角面的公共邊，這就導致給個位置剖面點其實是重復生成了兩次。這種情況的危害是占用不必要的資源，如果不做優化的話運行效果是不能讓人滿意的。

下面我們僅對切面是凸多邊形的情況進行考慮。

優化方法：

（1）確定任意一條邊的兩個頂點，以此確定為原點和基邊。

（2）對邊緣點列表進行排序，可按照以下依據：以某一點和原點的連線與基邊的夾角按從小到大的順序。

（3）遍歷剖面頂點，標記出重合點，可以按照以下依據：兩點的距離的平方<極小值（極小值設置為1e-6）。

（4）復制出新的無重合點的剖面集合。

（5）排除共線的無效點。①生成剖面時，有出現許多剖面點共線的情況，其實在這些點中，除了兩個端點需要保留外，中間的共線點都是不必要的，為了減少生成三角面的數量，提高運行的效率，盡量的減少無效的頂點是必要的。②排除共線無效點的依據：a=第i 個頂點與第i-1 個頂點的向量；b=第i+1 個頂點與第i 個頂點的向量；如果a 與b 夾角的絕對值<極小值，則表示三點共線，排除第i 個點。

經過這樣的優化后，頂點集合的大小就小多了，尤其是在連續切割下，剖面的三角面數量會以指數形式增長，該方法通過大量減小基底來避免三角面數過高。

之后的連接剖面三角形，只需要選定剖面頂點中第一個點作為定點，定點之后的兩個點作為活動點（i 和i+1），以逆時針的順序旋轉一周便可以連接完成。

3 運行效果

將經過優化的程序運行，運行效果有了相當大的改善，對于一個立方體，可以連續切割十次左右而不卡頓，崩潰的情況解決了，“剖面”極少發生。對于“球體”這樣的較高面模型也能應對。