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

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

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

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

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