基於遺傳算法的並行碰撞檢測系統及方法
2023-05-24 20:17:11 2
專利名稱：基於遺傳算法的並行碰撞檢測系統及方法
技術領域：
本發明關於一種並行碰撞檢測系統及方法，特別是涉及一種基於遺傳算法的並行碰撞檢測系統及方法。
背景技術：
碰撞問題多年來一直受到較多的關注，碰撞檢測方法在計算幾何、計算機動畫、CAD/CAM，仿真機器人和虛擬實境等領域中都有較好的應用前景。近些年來，國內外學者在碰撞檢測領域中做出了相當多有意義的工作並提出了一些高效的檢測方法。從空間域的角度，可以分為基於實體空間的碰撞檢測方法和基於圖像空間的碰撞檢測方法。這兩類算法的主要區別在於是利用物體三維幾何特性進行求交計算還是利用物體二維投影的圖象加上深度信息來進行相交分析。基於圖象空間的碰撞檢測算法能有效利用圖形硬體的繪製加速功能來提高碰撞檢測算法的效率。近幾年隨著圖形硬體技術的飛速發展，圖形加速卡在性能不斷迅速提高的同時甚至出現了可編程的功能，使得基於圖象空間的碰撞檢測算法進入了一個新的發展階段。對於基於實體空間的碰撞檢測算法，研究人員把各種幾何技術如層次表示法、幾何推理、代數範式、空間劃分、解析方法和最優化方法等應用到碰撞檢測中，提出了許多優秀的算法。其中基於空間剖分類算法和基於掠掃和裁剪算法是較優秀的面向含有多個物體的複雜場景的初步檢測算法，而基於特徵類算法、基於單純形類算法、基於層次包圍體樹類算法、基於距離場類算法、基於智能優化技術類算法都是基於離散碰撞檢測技術的面向兩個物體碰撞逐步求精的方法。然而，基於圖像的碰撞檢測算法也普遍存在以下三個缺陷(I)由於圖像本身均是空間離散採樣，其精度受圖像解析度的約束，從而影響碰撞檢測算法的精度；(2)多數算法仍只能處理凸體之間的碰撞檢測；(3)由於使用圖形硬體輔助計算，基於圖像的碰撞檢測還需要考慮如何合理地平衡CPU和圖形硬體的計算負荷。現有的基於實體空間的各類碰撞檢測算法也存在一些問題如檢測中刺穿現象和遺漏情況等。碰撞檢測方法一般時間複雜度為0(n2)，不能滿足實時性的要求，不利於碰撞檢測快速實現。基於空間分割技術的幾何分解方法，影響該方法效率的一個重要因素是分區的多少，而分區的數目又較難把握。八叉樹和其它幾何模型在解決碰撞檢測的框架之間的幾何幹涉問題時，不會大幅度提高方法效率。
發明內容
為克服上述現有技術存在的不足，本發明之主要目的在於提供一種基於遺傳算法的並行碰撞檢測系統及方法，其通過將進化過程劃分到不同計算節點上並行進行，並通過一定的種群間信息交換策略實現優良基因的交換，實現了提高碰撞檢測速度，同時保證較高的精度的目的，而且本發明適用於任意形狀的多面體之間的實時動態碰撞檢測。為達上述及其它目的，本發明提出一種基於遺傳算法的並行碰撞檢測系統，至少包括
問題模型建立模組，用於建立兩個多面體的線性不等式組圍成的凸空間，以將多面體模型相交問題轉化為帶約束條件的線性規劃問題；以及並行碰撞檢測模組，將進化過程劃分到不同計算節點上，利用遺傳算法分布式進行，在對約束條件處理後，通過一定的種群間信息交換策略實現優良基因的交換，以求解多面體模型相交問題，實現碰撞檢測。進一步地，該問題模型建立模組在n維歐幾裡德空間中給定一組線性不等式組為
權利要求
1.一種基於遺傳算法的並行碰撞檢測系統，至少包括 問題模型建立模組，用於建立兩個多面體的線性不等式組圍成的凸空間，以將多面體模型相交問題轉化為帶約束條件的線性規劃問題；以及 並行碰撞檢測模組，將進化過程劃分到不同計算節點上，利用遺傳算法分布式進行，在對約束條件處理後，通過一定的種群間信息交換策略實現優良基因的交換，以求解多面體模型相交問題，實現碰撞檢測。
2.如權利要求1所述的一種基於遺傳算法的並行碰撞檢測系統，其特徵在於，該問題模型建立模組在η維歐幾裡德空間中給定一組線性不等式組為
3.如權利要求2所述的一種基於遺傳算法的並行碰撞檢測系統，其特徵在於，該並行碰撞檢測模組至少包括 初始化模組，用於初始化基本的種群及確定工作組中的結點數目； 適應度函數計算模組用於將適應度函數分發到工作組中的各從進程進行計算； 收集種群模組，利用主進程接收各從進程的進化結果； 遺傳運算模組，利用遺傳算法的三個基本算子對該收集種群模組的收集結果進行操作； 子代種群生成模組，根據經選擇、交叉、變異操作後的種群，生成子代種群；以及 判斷模組用於判斷是否符合結束條件，若滿足結束條件，則結束碰撞檢測，否則進一步啟動初始化模組重新確定工作組中的結點數目。
4.如權利要求3所述的一種基於遺傳算法的並行碰撞檢測系統，其特徵在於，該適應度函數模型為 Fitness (i) = f (x) 其中，f(x)為兩個多面體的線性不等式組圍成的凸空間。
5.如權利要求4所述的一種基於遺傳算法的並行碰撞檢測系統，其特徵在於該三個基本算子為選擇、交叉及變異。
6.如權利要求5所述的一種基於遺傳算法的並行碰撞檢測系統,其特徵在於該選擇操作選用輪盤賭選擇法，該交叉算子採用單點交叉，基本變異算子採用對群體中的個體碼串隨機挑選一個或多個基因座並對該些基因座的基因值做變動。
7.如權利要求6所述的一種基於遺傳算法的並行碰撞檢測系統,其特徵在於該結束條件為生成的子代種群滿足要求。
8.一種基於遺傳算法的並行碰撞檢測方法，包括如下步驟 步驟一，建立兩個多面體的線性不等式組圍成的凸空間，以將多面體模型相交問題轉化為帶約束條件的線性規劃問題；以及 步驟二，將進化過程劃分到不同計算節點上，利用遺傳算法分布式進行，在對約束條件處理後，通過一定的種群間信息交換策略實現優良基因的交換，以求解多面體模型相交問題，實現碰撞檢測。
9.如權利要求8所述的一種基於遺傳算法的並行碰撞檢測方法，其特徵在於，步驟二還包括如下步驟 步驟1.1，初始化基本的種群； 步驟I. 2，分配種群，將群體分為若干個子群體，每個子群體包含一些個體； 步驟I. 3，將適應度函數分發到工作組中的各從進程進行計算； 步驟I. 4，主進程收集各子進程的進化結果； 步驟I. 5，對收集的結果進行選擇、交叉及變異操作； 步驟I. 6，生成子代種群；以及 步驟I. 7，判斷是否滿足結束條件，若滿足結束條件，則終止碰撞檢測，否則轉至步驟I.2繼續進行。
10.如權利要求9所述的一種基於遺傳算法的並行碰撞檢測方法，其特徵在於結束條件為生成的子代種群滿足要求。
全文摘要
本發明公開了一種基於遺傳算法的並行碰撞檢測系統及方法，該系統至少包括問題模型建立模組，用於建立兩個多面體的線性不等式組圍成的凸空間，以將多面體模型相交問題轉化為帶約束條件的線性規劃問題；以及並行碰撞檢測模組，將進化過程劃分到不同計算節點上，利用遺傳算法分布式進行，在對約束條件處理後，通過一定的種群間信息交換策略實現優良基因的交換，以求解多面體模型相交問題，實現碰撞檢測，本發明不僅實現了提高碰撞檢測速度，同時保證較高的精度的目的，而且適用於任意形狀的多面體之間的實時動態碰撞檢測。
文檔編號G06N3/12GK102982375SQ20121046584
公開日2013年3月20日 申請日期2012年11月16日 優先權日2012年11月16日
發明者熊玉梅, 寧建紅, 閆俊英 申請人:上海電機學院