譚穎

摘要：碰撞問題很早就引起了人們的關注，為了提高動畫的質量和計算時間，解決完全碰撞時間和反映脈沖，本文提出了優(yōu)化方法來解決碰撞問題，并在具體實例中闡述了如何使用該優(yōu)化方法。

關鍵詞：優(yōu)化方法；碰撞問題；布模擬；反映脈沖

中圖分類號：TP391文獻標識碼：A文章編號：1009-3044(2012)22-5377-02

Optimization and Application of Computing in Collision Problems

TAN Ying

(Chongqing Three Gorges University, Chongqing 404000, China)

Abstract: Collision problems have attracted peoples attention for quite a long time. In order to improve the quality of computer graphics, shorten the computing time, and solve the problem of collision time and reaction repulse, this paper proposes some optimization methods in the collision problems. Unlike other papers, this one also tries to elaborate how to practically use these methods in some concrete examples.

Key words: optimization; collision problem; cloth simulation; reaction pulse

碰撞的問題，包括碰撞檢測和碰撞反應，很早就已引起人們的關注。目前，這些問題仍然是計算機圖形學領域中最熱門的課題。許多研究人員設計出針對不同應用的優(yōu)秀的模擬技術。一般來說，一些要點應適用于這些方法，比如物理現實主義和數值穩(wěn)定性和計算效率。但是，和許多其它問題一樣，一個關注度較少的研究方向有時會被大家忽視。本文將提出解決碰撞問題的優(yōu)化方法，大大加快運算速度。此外，用布料模擬這個實際應用，通過碰撞例行試驗來驗證該方法的可行性。

本文將首先介紹關于碰撞的問題。接著將介紹優(yōu)化方法，最后討論在布仿真實例中如何使用這些方法，結果如何。

1碰撞問題

假設有兩個對象，應該如何檢查它們相互影響，如果它們不相互滲透，它們的距離是多少；如果相互重疊，滲透量是多少。從這些問題中，都存在碰撞問題。例如在動畫中，當一名警察射擊子彈，當一名球員踢球等，也是碰撞問題。因此，碰撞在我們的世界里無處不在。如果研究人員想要模擬我們日常生活的現實場景，甚至是卡通場景的碰撞約束，都必須考慮到這些問題。

有無滲透是對碰撞的簡單理解，確切地說，還有更多的方面需要考慮。以下幾個方面很重要：

A.找到確切的碰撞點，這可能會依賴于屏幕分辨率。

B.二維或三維的碰撞。

C.碰撞物體是凸的物體或非凸物體。

D.多邊形或非多邊形對象。

E.對象是開放的表面或封閉卷;

F.對象是剛體或變形的。

G.兩個還是多個的對象。

一般來說，碰撞問題可分為兩大類：碰撞檢測和碰撞反應。碰撞檢測用于檢測碰撞點碰撞的幾何信息和碰撞時間信息。因為任何的碰撞都可以歸結為邊緣或頂點和邊的碰撞，這種過程可以被簡化，以檢查最近的、將來發(fā)生的碰撞，檢測到碰撞之后，可以用碰撞反彈來作為反映。比如足球掉到地上后，不能立即停止，只有使對象反彈，看上去才自然。這兩個問題都可以通過一些優(yōu)化方法來解決。

2優(yōu)化方法

在計算機圖形計算中，優(yōu)化起到了重要作用，我首先將提出優(yōu)化的形式來描述碰撞問題，然后進行解釋。

mint

constrf(x, y, z, t) ＜= 0,

g1(x, y, z, t) ＜= 0,

g2(x, y, z, t) ＜= 0,

…

gN(x, y, z, t) ＜= 0,

ts ＜= t ＜= tf.

在這里碰撞涉及兩個對象，設為A和B，如果能夠找到碰撞時間t，則，然后可以通過A，B的速率得出碰撞的位置。

f(x, y, z, t)和gi(x, y, z, t)是描述A，B兩種涉及的對象，用gi(x, y, z, t)代表B，因為B可能分為許多凸部分。像f(x, y, z, t) ＜= 0表示碰撞點在這個對象的位置。基于這些描述，我們可以發(fā)現這個系統(tǒng)的碰撞點，因為當兩個物體同時具有最小時間t，它們就有唯一的碰撞點。

運動物體的描述，將取決于物體的形狀和運動。例如，一個球體，半徑為2，中心點為(0,0,0),時間為0時，速度為（1，2，3）單位/ S表示為：

M(x, y, z, t) = {(x, y, z, t) | (x-0-t)^2 + (y-0-2t)^2 +(z-0-3t)^2 ＜= 4}

得到以上的描述后，可以改變參數獲得發(fā)生碰撞的時間。

如果發(fā)生碰撞，需要有一個緩沖的對象，使他們彼此反彈。這同樣可以通過碰撞檢測程序得出。先得出反向的速度，根據碰撞的幾何信息，然后檢查是否另一個碰撞將發(fā)生在一個時間段，如果它發(fā)生，則需要添加一些限制，例如，只在某個時間后發(fā)生碰撞發(fā)生。

3布模擬

為什么碰撞布料模擬很難，因為布是變形的對象，無論自碰撞或與其他物體相撞，許多碰撞都可能同時發(fā)生。因為第二次碰撞的結果可能帶來的另一個碰撞，碰撞不可能一個一個的解決。所以我們需要找到一個“區(qū)”，我們發(fā)現一個潛在的區(qū)域，在不久的將來會發(fā)生碰撞，然后在此區(qū)域分配一個類似的排斥的對象，以避免沖突。

因此，我們可以使用碰撞檢測程序，很快找到“區(qū)”和涉及的對象，然后給一些在這個區(qū)域的響應對象，通過這種方式可以有效地解決多碰撞的問題。

4結論

本文重點介紹的碰撞問題，并嘗試優(yōu)化方法來解決這些問題。此外，它提供了一個布料模擬的例子來遍歷使用這種方法。很容易發(fā)現，使用這種方法，可大大提高雙方的效率和速度。然而，它也有局限性，只有可以用參數表示的對象才能適用此方法。作者也試圖找到一個直接的解決方案，找到一個系統(tǒng)里的最后位置和速度，但事實證明，現在不能做，所以人們必須一步一步來解決碰撞的結果，相信會不久的將來可以得到改善。

參考文獻：

[1] M.D.S.阿利尤,K.S.蘇丹.AL-LP -基于算法，用于檢測運動物體的碰撞[Z].運籌學學會第46條第（1995）854-886.

[2] M.D.S.阿利尤,K.S.蘇丹.碰撞檢測算法：一項調查顯示,技術研發(fā)CCSE-029的報告[R].法赫德國王石油大學和礦物質,宰赫蘭,沙特阿拉伯,1994.

[3]蔡文軍,陳虎.基于混合模型的碰撞檢測優(yōu)化算法研究[J].計算機與現代化,2006(7).

[4]徐旌德,李曄,崔慧娟,等.碼表的大小多參數的聯(lián)合優(yōu)化算法,多模式的量化[J].清華大學學報:自然科學版,2009(10).

[5]吳焰,張兵.一種改進的粒子群優(yōu)化算法[J].價值工程,2011(7).

[6]孫雅芳,王蕭丹,徐軍燕,等.全局優(yōu)化算法的基礎上[J].長春工業(yè)大學學報:自然科學版,2010(6).

[7]王金光,孫延鵬.一種簡單有效地碰撞檢測算法的實現[J].洛陽理工學院學報:自然科學版,2011(3).

[8]邵金明,何晨,蔣鈴鴿.通道路由的無線Mesh網絡的聯(lián)合優(yōu)化算法[D].上海:上海交通大學,2010.

[9]鐵經緯,王楊小凱,裴延安.虛擬場景優(yōu)化算法基于VisibilitySensor節(jié)點[J].軟件指南,2010(8).

[10]方偉,孫俊,丁彥蕊,等.醫(yī)學圖像配準基于混合量子行為的粒子群優(yōu)化算法研究[J].計算機工程與應用,2011(3).