碰撞檢測處理論文

導語：碰撞檢測處理論文一文來源于網友上傳，不代表本站觀點，若需要原創文章可咨詢客服老師，歡迎參考。

摘要:結合實現靜態虛擬穿衣中的實際問題,詳細地介紹了基于彈簧質點模型的織物變形模型和基于AABB層次包圍盒的碰撞檢測算法。借助層次空間分解法的思想,將縫合衣片的相對位置同人模自身的結構信息相結合,靈活地構造人模AABB樹,減少了不相交元素的碰撞檢測次數,從而提高了算法的效率。最后還給出了實現整個虛擬穿衣過程的具體步驟。關鍵詞:織物變形仿真;彈簧質點模型;碰撞檢測;空間分解法;層次包圍盒法;顯式歐拉方法

1前言隨著計算機技術和人類社會經濟的發展,對于紡織服裝業CAD/CAM的應用要求也越來越高,二維服裝CAD系統已經不能滿足要求,人們迫切希望借助計算機完成一些更加實用的三維功能。若能直接將二維服裝CAD系統設計的衣片,在計算機上真實地模擬出穿在人體上的效果,便可以幫助設計師直接在計算機上進行著裝效果檢查、服裝裁剪片縫合檢查等工作。這樣就可大大提高服裝從設計階段到生產階段間的效率,具有非常重要的實用價值。要通過計算機實現這一功能,有兩個關鍵的問題必須解決:1)建立合適的織物變形模型;2)選擇高效而實用的碰撞檢測算法。

研究織物變形仿真的方法通常分為三類:幾何的、物理的和混合的(幾何和物理方法的混合)。純幾何的造型方法很難反映織物的物理特性,因此基于物理的方法研究,近年來已占據了主導地位。在織物變形物理仿真模型中[1],按比擬織物結構的方式又可分為兩大類:1)離散質點型模型:比較典型的有Feynma等建立的質點網格模型、Breen等建立的粒子模型和XProvot等建立的彈簧質點模型;2)連續介質型模型:比較典型的有Terzopoulos等建立的彈性變型模型、Liling等建立的空氣動力模型、Aono建立的波傳播模型、Collier等建立的有限元模型等。

以上的織物變形物理仿真模型,由于其建模的原理和方法不盡相同,因此,它們適用于不同的應用場合有其各自的優缺點。

我們結合設計虛擬穿衣功能的實際,認為XProvot所建立的彈簧質點模型,模型簡單,易于計算機實現,在模擬衣片復雜的動態變形過程時,能夠取得比較真實的模擬效果和較快的模擬速度。

在模擬三維服裝穿在人體上的真實效果時,會遇到大量的碰撞現象:衣片同人模之間以及衣片自身間的一種相互滲透和穿越。只有很好地解決了滲透和穿越的問題,才能逼真地完成虛擬穿衣的模擬過程。因此,碰撞檢測是整個模擬過程的關鍵。碰撞檢測非常耗時,最簡單的碰撞檢測算法是對兩個碰撞體中的所有基本幾何元素(通常為三角形)進行兩兩相交測試。

現有的碰撞檢測算法大致可劃分為兩大類:空間分解法(spacedecomposition),和層次包圍盒法(hierarchicalboundingvolumes)。前者是將整個虛擬空間劃分成相等體積的小單元格,只對占據同一單元格或相鄰單元格的幾何對象進行相交測試。比較典型的方法有八叉樹和BSP樹。層次包圍盒法的核心思想是利用體積略大而幾何特性簡單的包圍盒將復雜幾何對象包裹起來,在進行碰撞檢測時,首先進行包圍盒之間相交測試,只有包圍盒相交時,才對其所包裹的對象,做進一步求交計算。在構造碰撞體的包圍盒時,若引入樹狀層次結構,可快速剔除不發生碰撞的元素,減少大量不必要的相交測試,從而提高碰撞檢測效率。比較典型的包圍盒類型有沿坐標軸的包圍盒AABB(axisalignedboundingboxes),包圍球(sphere),方向包圍盒OBB(orientedboundingbox)等。

在本文中,我們充分利用了AABB層次包圍盒法的優勢,同時在構建靜態人模的AABB樹時,又借助層次空間分解法中子空間在空間排列上的有序性和相關性的思想,將縫合衣片的相對位置同人模自身的結構信息相結合,靈活地構造人模AABB樹,這樣減少了需相交測試的元素,從而提高了碰撞檢測的效率。

2織物的變形模型

2.1織物變形模型的描述

我們建立的織物變形模型是以XProvot的彈簧質點模型作為基礎,將織物設想為一個個質點集合,質點間相互關系歸結為質點間的彈簧作用。其中彈簧分為三類:結構彈簧、剪切彈簧和彎曲彈簧,具體構成如圖1所示。圖1織物模型離散成規則網格

1)結構彈簧:在質點Pij和Pi+1,j間,以及Pij和Pi,j+1間的彈簧為結構彈簧,結構彈簧是為了保持質點間初始狀態時的距離。

2)剪切彈簧:在質點Pij和Pi+1,j+1間,以及Pi+1,j和Pi,j+1間的彈簧為剪切彈簧。剪切彈簧是為了防止織物在自身平面過渡和不真實的變形,而給織物的一個剪切剛性。3)彎曲彈簧:在質點Pij和Pi+2,j間,以及Pij和Pi,j+2間的彈簧為彎曲彈簧,彎曲彈簧是為了防止織物彎曲。2.2質點的位移在縫合衣片過程中,衣片上所有質點因受力而產生一定的位移,質點位移我們選用Nowton運動定律來描述:F外力(i,j)+F內力(i,j)=ma(i,j)其中,m是質點P(i,j)的質量。在本文中,我們假定布料是各向均質的,因此,質點的質量可由衣片總質量除以質點總數得到,a(i,j)是該點加速度,F外力(i,j)是該點所受的外力,F內力(i,j)是該點所受的內力。為了簡化模型,在我們三維服裝CAD系統中,只考慮兩種外力:縫合力和重力?？梢杂靡韵鹿絹肀硎?F外力(i,j)=F縫合力(i,j)+F重力(i,j)

在衣片縫合過程中,為了將不同的衣片縫在一起,我們在衣片對應縫合邊上加載縫合力。在模型中,縫合力被定義成對應縫合點之間距離的線性函數。對兩個縫合點pi,j和qi,j間的縫合力,可以按如下公式計算:F縫合力(i,j)=CsDis(pi,j,qi,j)Npi,j-qi,j式中Cs為縫合力系數,該系數與織物的縫合性能有關,通常,較難變形的布料采用較大的縫合力系數;Dis(pi,j,qi,j)表示兩縫合點pi,j和qi,j間的距離;Npi,j-qi,j表示從pi,j點指向qi,j點的單位方向矢量。為了獲得較真實的仿真效果,我們在變形模型中考慮了衣片所受的重力。質點所受的重力可按如下公式計算:F重力(i,j)=mi,jg式中mi,j為質點pi,j的質量。在彈簧質點模型中,唯一考慮的彈性內力是彈簧的彈性變形力,由于采用的是理想的彈簧質點系統,可以利用胡克(Hooke)定律來計算彈簧的彈性變形力:F內力(i,j)=-∑(k,l)∈Rk(Pi,jPk,l-‖Pi,jPk,l‖0Pi,jPk,l‖Pi,jPk,l‖)其中,k是彈簧的彈性變形系數,R是P(i,j)鄰點的集合,‖Pi,jPk,l‖0表示質點P(i,j)與質點P(k,l)之間的原始距離,彈簧的彈性變形系數k可以?讕菟∮彌锏牟牧閑閱懿問呷范ā?/P>

2.3織物變形模型的求解我們選擇顯式歐拉方法來求解織物變形模型。求解公式如下:ai,j(t+△t)=1mi,jFi,j(t)Vi,j(t+△t)=Vi,j(t)+△tai,j(t+△t)Pi,j(t+△t)=Pi,j(t)+△tVi,j(t+△t)其中,Fi,j是質點P(i,j)所受所有力的合力,mi,j(t)是質點P(i,j)的質量,ai,j(t)、Vi,j(t)和Pi,j(t)分別是質點P(i,j)在時間t的加速度,速度和位置?！鱰是系統選定的時間步長。

3基于AABB樹層次包圍盒的碰撞檢測

3.1建立AABB樹一個碰撞體的AABB被定義為包含該碰撞體,且邊平行于坐標軸的最小六面體。因此,描述一個AABB,僅需六個標量。在構造AABB包圍盒時,需沿著碰撞體局部坐標系統的軸向(X,Y,Z)來構造,所以所有的AABB包圍盒具有一致的方向。

AABB樹是基于AABB的二叉樹,按照由上至下的遞歸細分方式構造生成的。在每一次遞歸過程中,要求取最小的AABB,需沿所選擇的剖分面將碰撞體分為正負兩半,并將所對應的原始幾何元素(如三角面)分別歸屬正、負兩邊,整個遞歸過程類似于空間二叉剖分,只是每次剖分的對象是AABB,而不是空間區域。遞歸細分一直要進行到每一個葉子節點只包容一個原始幾何元素為止,所以具有n個原始幾何元素的AABB樹具有n-1個非葉子節點和n個葉子節點。對于剖分面的選擇,在本文中,選擇垂直AABB的最長軸,且平分該軸的平面。經試驗證明,這種方式,在大多數情況下的算法復雜度僅為O(nlogn),較其它的剖分面選擇方法有了極大的提高。至于原始幾何元素的歸屬則應依據幾何元素的重心P在最長軸上的投影坐標。若投影坐標大于剖分面的坐標(mid),則在剖分面的正向,否則在負向,如圖2所示。圖2三角面歸屬負區域,因為其質心投影坐標小于剖分面的基準坐標

3.2AABB的相交判斷AABB間的相交測試比較簡單,兩個AABB相交當且僅當它們在三個坐標軸上的投影區間均相交。通過投影,我們即將三維求交問題轉化為一維求交問題。而對一維求交問題,我們則采用SAT(SeparatingAxesTest)[2]法。因SAT無需求交計算,只需比較兩個包圍盒分別在三個軸向上投影的重疊情況,即可得出相交測試結果,非常簡單?，F以在一個軸向上的投影情況為例說明:圖3AABBs在X軸向相交判斷。

設A,B為兩包圍盒,X為投影軸,CA,CB分別為A,B的中心點,PA,PB為點CA,CB在X上的投影。RA,RB分別為包圍盒A,B在X上的投影。若RA+RB

PAPB,(如圖3所示)則在軸向X上A和B不相交,反之在軸向X上A和B鄰接或相53第5期高成英等:虛擬穿衣中織物模型的建立和碰撞檢測的處理交。當包圍盒A,B在三條軸向上的投影均相交時,則A,B相交。定義AABB的六個最大最小值分別確定了它在三個坐標軸上的投影區間,因此AABB間的相交測試最多只需六次比較運算,非常簡單快速。

3.3AABB樹的更新當衣片移動、旋轉后,需要對AABB進行更新,根據定義AABB的6個最大最小值的組合,可以得到AABB的8個頂點,對這8個頂點進行相應的旋轉和平移變化,并根據變化后的頂點計算新的AABB。當衣片發生變形時,需要重新計算AABB樹中發生變形了的葉結點的AABB,再利用變形葉節點的新AABB來重新計算它們父節點的AABB。這種計算必須嚴格按照從下到上的方式進行。父節點AABB的具體求法為:令(Xmax1,Xmin1,Ymax1,Ymin1,Zmax1,Zmin1)和(Xmax2,Xmin2,Ymax2,Ymin2,Zmax2,Zmin2)分別是兩個變形葉結點的AABB,則父結點的AABB即為(max(Xmax1,Xmax2),min(Xmin1,Xmin2),max(Ymax1,Ymax2),min(Ymin1,Ymin2),max(Zmax1,Zmax2),min(Zmin1,Zmin2),只需6次比較運算就完成一個結點的更新,其效率遠遠高于重新構造AABB包圍盒樹。

3.4基于AABB樹的碰撞檢測算法基于AABB樹碰撞檢測算法的核心是通過有效地遍歷這兩棵樹,以確定在當前位置下,兩個碰撞體的某些部分是否發生碰撞,這是一個雙重遞歸遍歷的過程。算法描述如下:step1：分別為人模和衣片構造AABB樹。step2：人模的AABB樹的根結點遍歷衣片的AABB樹。如果發現人模AABB樹的根結點的包圍盒與衣片AABB樹內部結點的包圍盒不相交，則停止向下遍歷；如果遍歷能到達衣片AABB樹的葉節點，再用該葉節點遍歷人模AABB樹。如果能到達人模AABB樹的葉節點，則進一步進行基本幾何元素間的相交測試。step3：檢測基本幾何元素間是否相交。3.5自碰撞檢測在衣片縫合過程中,除了衣片同人模之間的碰撞外,由于衣片的動態變形,使得衣片與衣片自身間也有碰撞現象,因此必須進行進一步的自相交檢測。在系統設計中,我們利用三角形表面曲率來簡化計算。當鄰近三角形法線的夾角較小時,它們不可能發生碰撞,只有當夾角超過閾值,才有可能碰撞。我們為每個三角形建立它的臨近三角形列表,通過判斷每個三角形的所有鄰近區域的三角形表面曲率,來排除大部分不可能相交的情況,從而簡化了計算。

4虛擬穿衣的具體實現步驟

(1)讀入二維服裝CAD系統設計的衣片

(2)選擇所有需要縫合衣片的對應的縫合邊

(3)將二維衣片離散并形成初始的彈簧質點系統a)將衣片離散成規則四邊域網格,再將四邊域網格的對角線相連,形成規則三角形網格的彈簧質點系統。三角形的頂點形成質點,三角形的邊形成相應的彈簧。衣片的三角化,正是為方便地建立衣片的AABB樹;b)按質點間的相應關系,加入各種彈力。在離散衣片時,需特別注意的是在(2)中所選擇的對應縫合邊的長度一定要相等,且當衣片離散化時,在對應縫合邊上的原始幾何元素(這里為三角形)的個數也應相同。若在(2)中所選擇的對應縫合邊長度不等,或原始幾何元素個數不同時,系統將需做一些預處理:將其中一條縫合邊的所有信息刪除,將另一條縫合邊的相應信息賦給它。

(4)將衣片交互式地放置在人體模型附近的初始位置在該步驟中,首先,給每一縫合衣片賦一個別名(系統自定義的標準別名:左前片,右前片,左后片,右后片等),根據每一衣片的別名,衣片被自動地放置在人體模型附近的相應初始位置上。

(5)分別為人模和衣片建立AABB樹本文中所涉及的兩個碰撞體,分別為人模和衣片,其中人模在整個動態模擬過程中為靜態的,因此,只需在初始化時構造一次AABB樹即可。為了進一步提高碰撞檢測的效率,我們在構造人模的AABB樹時,應根據(4)中得到的縫合衣片別名,結合人模的幾何結構,靈活構造人模的AABB樹。例如:假設我們在(4)中,得到衣片分別為:左前片,右前片,左后片,右后片。我們即可知,將要縫合的為一件四片裁剪片的上衣,所以在構造人模的AABB樹,我們只取人模上半身數據來構造人模的AABB,具體層次結構如圖4所示。在進行人模和衣片間碰撞檢測時,根據衣片的別名分別進行局部檢測,(例如:左前片,就只需和人模AABB樹第三層最左邊的結點,左前半身的AABB進行碰撞檢測)有效地減少了需要碰撞檢測的元素。系統根據所縫合的衣片不同,建立的人模AABB樹亦不相同。圖4人模的AABB樹層次結構圖

(6)動態變形模型的計算根據衣片的縫合信息,我們在衣片的對應縫合邊上加載縫合力。在縫合力、重力和衣片上各質點間內部彈力的共同作用下,二維衣片將逐步變形,并逐漸被縫合在一起,整個縫合過程是一個動態的迭代過程。在動態迭代過程中,要同時進行大量的人?！缕g,及衣片—衣片間的碰撞檢測處理,并給出相應碰撞響應(當有碰撞現象發生時,要重新調整碰撞點處的位置,避免發生穿越和滲透)的處理?？p合過程結束后,便可以得到縫合好的三維服裝穿在靜態人模上的效果。

5結束語實驗證明,本文所采用的織物變形模型———彈簧質點模型,模型簡單,能夠較真實地反映虛擬環境下的織物特性。所采用的基于AABB的層次包圍盒碰撞檢測算法,除了AABB層次包圍盒自身在碰撞檢測上的較高性能外,算法還從以下幾方面提高了碰撞的檢測效率:

1)將縫合衣片的相對位置同人模自身的結構信息相結合,靈活地構造人模AABB樹,減少了人模和衣片之間不可能相交元素碰撞檢測的次數;

2)AABB包圍盒的相交判斷中,采用SAT方法進行包圍盒之間的交疊判斷,降低了算法的復雜度,提高算法效率。

3)衣片之間的碰撞判斷,利用了每個三角形相鄰區域的三角形表面曲率來簡化求交判斷。

參考文獻

［1］張慶豐，樂清洪，馬澤恩．織物變形的物理仿真技術［J］．計算機輔助設計與圖形學報，2001，（5）：449-454．［2］LouchetJ．，ProvotX．，etal．Evolutionaryidentificationofclothanimationmodels［A］．TerzopoulosD．，ThalmannD．，eds．ProceedingsoftheComputerAnimationandSimulation′95［C］．NewYork：Springer-Verlag，1995．44-54．［3］CarignanM．，YangY．，MagnenatThalmannN．Dressinganimatedsyntheticactorswithcomplexdeformableclothes［A］．ComputerGraphics（Proc．SIGGRAPH）［C］，1992，26（2）：99-104．［4］VandenBergenG．EfficientCollisionDetectionofComplexDeformableModelsusingAABBTrees［J］．JournalofGraphicsToo?歟螅?997，2（4）：1-14．［5］VolinoP．，MagnenatThalmannN．EfficientSelf-collisionDetectiononSmoothlyDiscretizedSurfaceAnimationsUsingGeometricalShapeRegularity［J］．ComputerGraphicsForum，（EuroGraphicsProc．），Blackwell，UK，1994，13：155-166．［6］DesbrunM．，GascuelM．P．Smoothedparticles：anewparadigmforanimatinghighlydeformablebodies［A］．Thalmannded．ProceedingsoftheComputerAnimationandSimulation′96［C］．NewYork：Springer-Verlag，1996．61-76．第22卷第5期2002年5月計算機應用ComputerApplicationsVol．22，No．5May，2002