文/劉柯壯 賀體剛

1 問題分析

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

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

對(duì)于模型的mesh 切割，首先確定以下兩個(gè)前提：

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

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

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

2 解決方案

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

2.1 確定切割源

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

2.2 頂點(diǎn)分組

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

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

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

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

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

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

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

2.4 連接剖面三角形

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

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

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

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

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

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

2.5 對(duì)剖面點(diǎn)進(jìn)行優(yōu)化

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

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

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

下面我們僅對(duì)切面是凸多邊形的情況進(jìn)行考慮。

優(yōu)化方法：

（1）確定任意一條邊的兩個(gè)頂點(diǎn)，以此確定為原點(diǎn)和基邊。

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

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

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

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

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

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

3 運(yùn)行效果

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