一種混合cpu和gpu的大規模物體群的碰撞剔除方法
2023-07-26 16:48:51 2
一種混合cpu和gpu的大規模物體群的碰撞剔除方法
【專利摘要】本發明公開了一種混合CPU和GPU的大規模物體群的碰撞剔除方法，其步驟：1)把物體群分成小形狀物體群和大形狀物體群兩類；2)將小形狀物體群存入GPU的Global內存中，在GPU中建立改進的LBVH樹，再用並行SaP算法進行葉子節點內和葉子節點間的碰撞剔除計算；3)在CPU上用並行SaP算法完成基於檢測粒度的共享工作隊列的多線程的大形狀物體群之間的碰撞剔除計算，再協同GPU同步計算的LBVH小形狀物體群的碰撞剔除結果，用兩次並行SaP算法進行大形狀物體群和小形狀物體群之間的碰撞剔除計算；4)建立協同CPU和GPU同步碰撞檢測的計算模型；5)分析比較不同數量級物體群的碰撞剔除計算時間。本發明在百萬級以下的物體群規模情況下，比現有傳統並行算法快10-30倍。
【專利說明】一種混合CPU和GPU的大規模物體群的碰撞剔除方法
【技術領域】
[0001] 本發明涉及三維模型碰撞檢測【技術領域】，尤其是指一種混合CPU和GPU的大規模 物體群的碰撞剔除方法。
【背景技術】
[0002] 隨著三維電影、動畫和遊戲等的快速發展，面向複雜三維場景的快速碰撞檢 測問題已成為人們探索的研究熱點之一。碰撞檢測問題是三維圖形中的經典問題， 包括基於包圍盒的檢測，基於時間或空間連貫性的檢測等。隨著多核CPUs的出現和 GPGPU (General-Purpose Computation on Graphics Processing Units)的興起，碰撞檢測 在多核處理器上的研究也有一些成果，但是大多數研究是基於GPU計算的。CPU和GPU具有 不同的運算特性，如何充分發揮各自的運算能力，協作CPU和GPU的並行處理任務是目前碰 撞檢測問題新的研究領域。所以，需要建立一些新的方法，用於大規模物體群的碰撞檢測和 剔除。
【發明內容】
[0003] 本發明的目的在於克服現有技術的不足，提供一種混合CPU和GPU的大規模物體 群的碰撞剔除方法，運用了多核技術和同步並行計算，尤其適用於由少量的大形狀和大量 的小形狀組成的物體群，對於複雜三維場景的快速碰撞剔除計算具有重要意義。
[0004] 為實現上述目的，本發明所提供的技術方案為：一種混合CPU和GPU的大規模物體 群的碰撞剔除方法，包括以下步驟：
[0005] 1)大規模物體群分類預處理，由CPU完成所有輸入物體的聚類分析，把物體群分 成小形狀物體群和大形狀物體群兩類；
[0006] 2)將小形狀物體群存入GPU的Global內存中，在GPU中建立改進的LBVH樹，再用 並行SaP算法進行葉子節點內和葉子節點間的碰撞剔除計算；
[0007] 3)在CPU上用並行SaP算法完成基於檢測粒度的共享工作隊列的多線程的大形狀 物體群之間的碰撞剔除計算，再協同GPU同步計算的LBVH小形狀物體群的碰撞剔除結果， 用兩次並行SaP算法進行大形狀物體群和小形狀物體群之間的碰撞剔除計算；
[0008] 4)建立協同CPU和GPU同步碰撞檢測的計算模型，實現混合多核的同步並行計 算；
[0009] 5)分析比較不同數量級物體群的碰撞剔除計算時間。
[0010] 在所述步驟1)中，提出用物體AABB包圍盒的對角線長度作為統計量，並向有序列 表的兩端聚集，最後確定大形狀物體群和小形狀物體群的分割點。
[0011] 所述步驟2)包括以下過程：
[0012] 2. 1)在GPU上進行小形狀物體群的碰撞剔除計算，包括：提出改進的LBVH算法， 對物體群進行空間劃分，再用並行SaP算法計算LBVH葉子上的各劃分空間的物體位置關 系；
[0013] 2. 2)在並行SaP計算中，要確定SaP的掃描方向，提出用與最大方差軸夾角最小的 空間主軸作為並行SaP的掃描方向，以減少任何形狀包圍體投影后的重構工作量；其中，最 大方差軸方向w為：
【權利要求】
1. 一種混合CPU和GPU的大規模物體群的碰撞剔除方法，其特徵在於，包括以下步驟： 1) 大規模物體群分類預處理，由CPU完成所有輸入物體的聚類分析，把物體群分成小 形狀物體群和大形狀物體群兩類； 2) 將小形狀物體群存入GPU的Global內存中，在GPU中建立改進的LBVH樹，再用並行 SaP算法進行葉子節點內和葉子節點間的碰撞剔除計算； 3) 在CPU上用並行SaP算法完成基於檢測粒度的共享工作隊列的多線程的大形狀物體 群之間的碰撞剔除計算，再協同GPU同步計算的LBVH小形狀物體群的碰撞剔除結果，用兩 次並行SaP算法進行大形狀物體群和小形狀物體群之間的碰撞剔除計算； 4) 建立協同CPU和GPU同步碰撞檢測的計算模型，實現混合多核的同步並行計算； 5) 分析比較不同數量級物體群的碰撞剔除計算時間。
2. 根據權利要求1所述的一種混合CPU和GPU的大規模物體群的碰撞剔除方法，其特 徵在於，在所述步驟1)中，提出用物體AABB包圍盒的對角線長度作為統計量，並向有序列 表的兩端聚集，最後確定大形狀物體群和小形狀物體群的分割點。
3. 根據權利要求1所述的一種混合CPU和GPU的大規模物體群的碰撞剔除方法，其特 徵在於，所述步驟2)包括以下過程： 2. 1)在GPU上進行小形狀物體群的碰撞剔除計算，包括：提出改進的LBVH算法，對物 體群進行空間劃分，再用並行SaP算法計算LBVH葉子上的各劃分空間的物體位置關係； 2. 2)在並行SaP計算中，要確定SaP的掃描方向，提出用與最大方差軸夾角最小的空間 主軸作為並行SaP的掃描方向，以減少任何形狀包圍體投影后的重構工作量；其中，最大方 差軸方向w為：
式中，X為輸入物體群的坐標數據集，argmax(w)為w方向各分量的最大值；因此，掃描 方向s為：
2. 3)在構造LBVH樹時，即進行物體群的空間劃分時，為了提高並行SaP的計算密度，葉 子內包含的物體數量應該足夠多，並且葉子內物體的分布方向應與SaP掃描方向一致，以 降低並行SaP的冗餘檢測計算，因此，提出對原來LBVH的Morton編碼方式做以下改進：（i) 增加非掃描方向坐標的表示位，增加精度；（ii)減少掃描方向的坐標表示位；（iii)將掃描 方向的坐標表7]^位移向低位； 2. 4)改進後的Morton編碼仍保持最小點或最大點不變性，所以，在構造LBVH樹時可以 使用物體包圍盒的最小點，從而減少包圍盒其它頂點定位的空間搜索計算； 2. 5)葉子內物體的碰撞剔除檢測就是完成一個劃分子空間的碰撞剔除檢測，採用並行SaP算法； 2. 6)葉子間物體的碰撞剔除檢測，在構造LBVH樹時，空間劃分不是嚴格地分離物體， 一些物體可能跨越兩個子空間，所以要判斷跨越葉子的物體是否與葉子內的物體有碰撞， 在此提出用向後、向前的二次並行SaP掃描方法，執行下面步驟2. 6. 1)至步驟2. 6. 3): 2.6. 1)查找跨越葉子的物體，稱作跨越物體，即檢查每個物體最大點的編碼是否超出 其所在區間，查找的複雜度是O(logN)，N為物體個數； 2. 6. 2)判斷跨越物體與葉子的碰撞情況； 2.6.3)兩次使用並行SaP算法求跨越物體與碰撞葉子內的物體的碰撞檢測：第一次是 按照投影最小值排序後進行向後掃描，求跨越物體之後的物體碰撞檢測；第二次是按照投 影最大值排序後進行向前掃描，求跨越物體之前的物體碰撞檢測；最後還需刪除重複的碰 撞對。
4. 根據權利要求1所述的一種混合CPU和GPU的大規模物體群的碰撞剔除方法，其特 徵在於：在步驟3)中，由於CPU的線程數相對於GPU的線程數是很少的，但是線程的運算相 對GPU要獨立，所以，大形狀物體群之間的碰撞檢測算法採用共享工作隊列的任務分組的 檢測策略，即每個線程從共享工作隊列中獲取一組任務進行碰撞檢測，這裡，一組任務的大 小稱作檢測粒度，假設共享工作隊列的物體個數為n，即隊列長度，檢測粒度為w，線程數為 t，第i個線程的共享工作隊列的任務索引為Pi，大形狀物體群碰撞檢測算法包括以下步驟 3. 1.l)-3. 1. 5)： 3. 1. 1)初始化各線程的任務索引Pi= 0(i= 1，2,…，t); 3. 1. 2)啟動SaP工作線程，每個線程並行執行以下步驟； 3. 1. 3)如果i>n，則當前線程結束； 3. 1. 4)對m=min(Pi+w,n) _Pi個隊列元素進行SaP碰撞檢測； 3. 1. 5)更新任務索引值Pi=minh+w，n)，執行上面步驟3. 1. 3); 大形狀物體群和小形狀物體群之間的碰撞剔除計算也是用基於檢測粒度的共享工作 隊列的多線程方法，主要有以下三個步驟： 3. 2. 1)CPU獲取GPU中計算得到的較小物體的LBVH層次結構； 3. 2. 2)對每一個大形狀物體，在LBVH層次中檢測與之相交的葉子節點； 3. 2. 3)兩次使用並行SaP算法求大形狀物體與碰撞葉子內的物體的碰撞對。
5. 根據權利要求1所述的一種混合CPU和GPU的大規模物體群的碰撞剔除方法，其特 徵在於，所述步驟4)包括以下過程： 4. 1)當CPU上完成大規模物體群的聚類分析時，同步進行大形狀物體群的CPU碰撞檢 測，以及小形狀物體群的GPU上的LBVH構造、葉子內物體的投影和排序計算； 4.2) 當上面步驟4. 1)中的CPU檢測和GPU計算完成時，同步進行大形狀和小形狀物體 群的CPU上向後並行SaP檢測，以及小形狀物體群的GPU上葉子內SaP檢測和葉子間向後 並行SaP檢測和向前SaP投影和排序計算； 4.3) 當上面步驟4. 2)中的CPU檢測和GPU計算完成時，同步進行大形狀和小形狀物體 群的CPU上向前並行SaP檢測，以及小形狀物體群的GPU上葉子間向前SaP檢測，最後，CPU 和GPU分別檢測重複的碰撞對，完成全部碰撞剔除檢測。
【文檔編號】G06T1/20GK104408685SQ201410713568
【公開日】2015年3月11日 申請日期:2014年11月28日 優先權日:2014年11月28日
【發明者】楊喬傑, 陳澤琳 申請人:華南理工大學