大規(guī)模復(fù)雜場景中非剛體模型的碰撞檢測研究

季宏宇

吉林農(nóng)業(yè)大學(xué)信息技術(shù)學(xué)院，吉林長春 130118

0 引言

隨著圖形圖像學(xué)的進(jìn)一步發(fā)展，在計算機(jī)圖形仿真領(lǐng)域，大規(guī)模復(fù)雜場景中非剛體模型的碰撞檢測已成為重要的研究課題。為了使模擬效果更加真實(shí)，需要對碰撞的發(fā)生時間發(fā)生點(diǎn)做出準(zhǔn)確及時的檢測，并做出相應(yīng)的處理，否則會發(fā)生穿透現(xiàn)象，破壞真實(shí)感。

1 非剛性物體模型分析

非剛性物體是指現(xiàn)實(shí)物理世界中的物體，它們是非剛性的，在運(yùn)動的過程中會產(chǎn)生一定的形變。物體的變形一直是計算機(jī)圖形學(xué)的研究熱點(diǎn)，1986年，Weil[1]首次討論了基于物理模型的非剛性物體的變形問題。當(dāng)時僅是用來模擬布料懸掛在釘子上的形態(tài)。Feynman則提出了一個更完善的布料懸掛模型。后來，許多研究者相繼開始采用各種物理模型來對非剛性物體進(jìn)行運(yùn)動變形模擬。

Provot[1]作為此領(lǐng)域的權(quán)威人士，對于非剛性物體的自碰撞檢測問題提出了一種解決方案。方案中指出，在某一區(qū)域內(nèi)，若曲率足夠小，則在這塊區(qū)域內(nèi)不會發(fā)生自交現(xiàn)象。經(jīng)進(jìn)深入的研究與分析，我們可以將大規(guī)模復(fù)雜場景中的非剛性物體進(jìn)行三角面片劃分，當(dāng)三角面片劃分到足夠小的空間時，可看作該點(diǎn)不發(fā)生自碰撞檢測。如果檢測到該點(diǎn)已經(jīng)發(fā)生碰撞，那么該點(diǎn)只能與復(fù)雜場景中其他物體發(fā)生了碰撞檢測。這樣我們將非剛性物體的自碰撞檢測問題歸結(jié)到剛性物體的碰撞檢測問題。

2 非剛體模型的建立

在多種非剛體模型中，Provot建立的質(zhì)點(diǎn)-彈簧模型較好地將織物的物理特性進(jìn)行了抽象。該模型不僅簡單，且能達(dá)到實(shí)時的效果。他把非剛體劃分為矩形網(wǎng)格，網(wǎng)格的交點(diǎn)稱為虛擬質(zhì)點(diǎn)，每兩個質(zhì)點(diǎn)之間用彈簧相連。

該模型的主要思想是把一塊非剛性物體劃分為m×n的矩形網(wǎng)格，每個網(wǎng)格節(jié)點(diǎn)是一個虛擬質(zhì)點(diǎn)，每個質(zhì)點(diǎn)用彈簧相連，彈簧無質(zhì)量且其長度不能為零。非剛體的質(zhì)量分布在質(zhì)點(diǎn)上。用作連接的彈簧有三類，分別是：結(jié)構(gòu)彈簧、剪切彈簧和柔性彈簧。

每個質(zhì)點(diǎn)受到內(nèi)力和外力的作用。內(nèi)力是指連接到質(zhì)點(diǎn)的各個彈簧對其作用力的合力；外力是指重力、風(fēng)力、空氣阻力、人機(jī)交互環(huán)境中人為的作用力等各種力對質(zhì)點(diǎn)作用力的合力。

利用質(zhì)點(diǎn)-彈簧模型可以非常方便的對非剛性物體進(jìn)行三角分割，每個三角形是構(gòu)成非剛性物體表面的基本幾何單元。

3 基于層次包圍盒的并行碰撞檢測

3.1 基于層次包圍盒的并行碰撞檢測概述

空間分解法與層次包圍盒法是當(dāng)前的兩類碰撞檢測算法。空間分解法以對某一單元格或相鄰單元格的幾何對象進(jìn)行相交測試。八叉樹、BSP樹是應(yīng)用較廣的方法。層次包圍盒法是利用體積略大而幾何特性簡單的包圍盒將復(fù)雜幾何對象包裹起來，在進(jìn)行碰撞檢測時，首先進(jìn)行包圍盒之間相交測試，只有包圍盒相交時，才對其所包裹的對象，做進(jìn)一步求交計算。在構(gòu)造碰撞體的包圍盒時，引入樹狀層次結(jié)構(gòu)，可快速剔除不發(fā)生碰撞的元素，減少大量不必要的相交測試，從而提高碰撞檢測效率。在非剛體模型中，基本幾何體為三角形；同時，對非剛性物體周圍的物體也進(jìn)行三角化分割。

在對非剛性物體進(jìn)行三角化分割后，為每個三角形建立包圍盒，然后自下而上建立一棵層次包圍盒二叉樹；同時，非剛性物體周圍的物體也按一定的規(guī)則建立層次包圍盒二叉樹。于是碰撞檢測歸結(jié)為兩棵二叉樹的判交算法。

由于非剛性物體本身結(jié)構(gòu)非常復(fù)雜，為了保證實(shí)時效果，本文經(jīng)分析論證，采用了當(dāng)前較為流行的層次包圍盒[2，3]算法來實(shí)現(xiàn)碰撞檢測。

3.2 基于層次包圍盒的串行原理與算法設(shè)計

兩個物體的層次包圍盒構(gòu)建完成，就可以通過遍歷他們的平衡樹來進(jìn)行他們之間的碰撞檢測，在此，我們引入任務(wù)樹的概念[4-5]。將遍歷兩個物體的平衡包圍盒樹的過程定義成一顆任務(wù)樹的遍歷。

碰撞檢測的過程可以通過一個任務(wù)樹的遍歷來實(shí)現(xiàn)。如果任意子任務(wù)中發(fā)生了碰撞，則判定兩個物體發(fā)生了碰撞。如果遍歷了任務(wù)樹后沒有檢測到有子任務(wù)發(fā)生過碰撞，則判定兩個物體發(fā)生了碰撞。因此一個任務(wù)的結(jié)果可以通過將所有子任務(wù)碰撞結(jié)果作邏輯或運(yùn)算。

基于層次包圍盒的算法設(shè)計首先為非剛性物體建立樹A，為周圍物體建立樹B。通過任務(wù)樹，進(jìn)行遍歷和判交。

4 結(jié)論

對非剛性物體進(jìn)行碰撞檢測及處理是計算機(jī)圖形仿真領(lǐng)域中一項(xiàng)非常復(fù)雜而耗時的工作，而在應(yīng)用中對其實(shí)時性的碰撞檢測算法成為非剛性物體碰撞檢測的關(guān)鍵，也是當(dāng)今學(xué)術(shù)領(lǐng)域正在不斷探索和研究的一項(xiàng)技術(shù)，需要我們在應(yīng)用中不斷總結(jié)并改進(jìn)算法。

[1]Xavier Provot，Collision and self-collision handling in cloth model dedicated to design garment[J].Eurographics Workshop on Animation and Simulation，September 1997.

[2]石教英.虛擬現(xiàn)實(shí)基礎(chǔ)及使用算法[M].北京：科學(xué)出版社，2002：216-253.

[3]高成英，劉寧，羅笑南.虛擬穿衣中織物模擬的建立和碰撞檢測的處理[J].計算機(jī)應(yīng)用，2002，22(5)：34-37.

[4]趙偉，譚瑞璞，李文輝.基于混合包圍體的OpenMP并行化碰撞檢測算法 軟件學(xué)報Journal of Software，Vol.19，Supplement，December 2008：190-201.

[5]趙偉，何艷爽，王曉兵.一種基于分治和流水線技術(shù)的并行碰撞檢測算法[J].長春工業(yè)大學(xué)學(xué)報：自然科版，2007，28(3)：241-246.