基于圖形處理器的碰撞檢測算法的研究.pdf

1、碰撞檢測就是判斷某一時(shí)刻兩個(gè)移動(dòng)的物體之間是否發(fā)生了碰撞。作為一個(gè)典型而實(shí)用的方法，需要考慮在任意離散的時(shí)間幀序列，兩個(gè)物體是否相交。碰撞檢測是計(jì)算機(jī)動(dòng)畫、游戲設(shè)計(jì)、機(jī)器人、計(jì)算機(jī)圖形學(xué)等領(lǐng)域的一個(gè)重要的研究方向。如一個(gè)移動(dòng)的物體在虛擬現(xiàn)實(shí)場景中的漫游，移動(dòng)的路徑通常是通過人機(jī)交互臨時(shí)確定的，在這個(gè)過程中，實(shí)時(shí)的碰撞檢測顯得尤為重要。 盡管目前針對(duì)碰撞檢測的研究已經(jīng)有了許多有價(jià)值的成果，但隨著諸如虛擬現(xiàn)實(shí)等新興領(lǐng)域的涌現(xiàn)以及隨之

2、而來的物體模型與場景越來越復(fù)雜，人們對(duì)交互實(shí)時(shí)性、場景真實(shí)性的要求越來越高，特別是在大型的復(fù)雜場景中，由于場景中的物體，甚至移動(dòng)的物體數(shù)目都很多，這就需要反復(fù)的進(jìn)行大量物體間的碰撞檢測，從而給碰撞檢測問題帶來了前所未有的挑戰(zhàn)。 圖形處理器(Graphics Processing Unit，GPU)，作為一種高度并行的流處理器，憑借其強(qiáng)大的處理能力和高存儲(chǔ)帶寬，為實(shí)時(shí)的、復(fù)雜的碰撞檢測提供一種有效的方案解決平臺(tái)。圍繞此方面進(jìn)行的研

3、究成為近幾年來GPU的應(yīng)用之一，并逐漸成為研究熱點(diǎn)。本文充分的利用了圖形處理器高度的并行處理能力，提出了下面兩個(gè)算法： 1. 通過搜索兩個(gè)凸多面體的分離平面來檢測兩個(gè)凸多面體是否碰撞。該算法使用一個(gè)啟發(fā)式策略搜索兩個(gè)物體的分離平面，經(jīng)過有限的步驟，算法或者找到一個(gè)分離平面報(bào)告物體分離，或者證明兩個(gè)凸多面體碰撞。在算法中，利用GPU加速了關(guān)鍵步驟——支撐頂點(diǎn)對(duì)的計(jì)算。并結(jié)合在GPU中分區(qū)域求最大值的約減(Reduce)方法，給出了

4、適用于復(fù)雜場景中多個(gè)物體的實(shí)時(shí)碰撞檢測方案。 2. 提出了一個(gè)基于GPU實(shí)現(xiàn)的、針對(duì)于復(fù)雜的封閉、變形物體的實(shí)時(shí)碰撞檢測算法。算法有效的利用了圖形處理器中的各種緩存，以及遮擋查詢(Occlusion Query)操作，同時(shí)該算法還可以應(yīng)用于自碰撞檢測。盡管目前的算法還存在一定的局限性，但算法既不需要復(fù)雜的預(yù)處理過程，也不需要復(fù)雜的數(shù)據(jù)結(jié)構(gòu)來存儲(chǔ)數(shù)據(jù)，而且算法可以直接應(yīng)用于可以繪制的各種模型，計(jì)算效率較高。 我們用多個(gè)實(shí)例