基于Unity3d 的mesh 切割及優(yōu)化

文/劉柯壯 賀體剛

1 問題分析

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

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

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

（1）被切割的模型面數(shù)較低。

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

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

2 解決方案

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

2.1 確定切割源

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

2.2 頂點分組

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

2.3 構(gòu)建三角形索引數(shù)組與創(chuàng)建剖面點

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

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

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

可求得焦點坐標(biāo)O：O=m+V*t

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

2.4 連接剖面三角形

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

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

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

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

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

以此方法旋轉(zhuǎn)一周，剖面連接完成。

2.5 對剖面點進行優(yōu)化

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

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

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

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

優(yōu)化方法：

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

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

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

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

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

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

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

3 運行效果

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