大規模復雜場景中非剛體模型的碰撞檢測研究

季宏宇

吉林農業大學信息技術學院，吉林長春 130118

0 引言

隨著圖形圖像學的進一步發展，在計算機圖形仿真領域，大規模復雜場景中非剛體模型的碰撞檢測已成為重要的研究課題。為了使模擬效果更加真實，需要對碰撞的發生時間發生點做出準確及時的檢測，并做出相應的處理，否則會發生穿透現象，破壞真實感。

1 非剛性物體模型分析

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

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

2 非剛體模型的建立

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

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

每個質點受到內力和外力的作用。內力是指連接到質點的各個彈簧對其作用力的合力；外力是指重力、風力、空氣阻力、人機交互環境中人為的作用力等各種力對質點作用力的合力。

利用質點-彈簧模型可以非常方便的對非剛性物體進行三角分割，每個三角形是構成非剛性物體表面的基本幾何單元。

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

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

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

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

由于非剛性物體本身結構非常復雜，為了保證實時效果，本文經分析論證，采用了當前較為流行的層次包圍盒[2，3]算法來實現碰撞檢測。

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

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

碰撞檢測的過程可以通過一個任務樹的遍歷來實現。如果任意子任務中發生了碰撞，則判定兩個物體發生了碰撞。如果遍歷了任務樹后沒有檢測到有子任務發生過碰撞，則判定兩個物體發生了碰撞。因此一個任務的結果可以通過將所有子任務碰撞結果作邏輯或運算。

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

4 結論

對非剛性物體進行碰撞檢測及處理是計算機圖形仿真領域中一項非常復雜而耗時的工作，而在應用中對其實時性的碰撞檢測算法成為非剛性物體碰撞檢測的關鍵，也是當今學術領域正在不斷探索和研究的一項技術，需要我們在應用中不斷總結并改進算法。

[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]石教英.虛擬現實基礎及使用算法[M].北京：科學出版社，2002：216-253.

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

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

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