[發明專利]具有沖量傳播的多線程物理引擎

有效

• 申請號: 201210271847.4
• 申請日: 2012-08-01
• 公開（公告）號: CN103106120A
• 公開（公告）日: 2013-05-15
• 發明（設計）人: E·O·梅德里希;P·E·沙爾特;R·A·希勒;M·R·塔布斯
• 申請（專利權）人: 國際商業機器公司
• 主分類號: G06F9/54
• 分類號: G06F9/54;G06F9/38
• 代理公司: 北京市中咨律師事務所 11247
• 代理人: 張亞非;于靜

技術領域

本發明一般涉及數據處理，更具體地，涉及圖形圖像處理和呈現（rendering）以及與之相關的物理沖量傳播。

背景技術

呈現來自三維場景的二維圖像的過程通常被稱為圖像處理。隨著現代計算機產業的發展，圖像處理也在發展。圖像處理發展中的一個特定目標是使得三維場景的二維模擬或呈現盡可能地真實。

此外，圖像處理經常與建模或模擬現實世界場景相關聯地使用，其中，表示物理、真實世界物體的虛擬或模擬物體在模擬場景中互相作用。例如，視頻游戲越來越能夠描繪越來越多的現實虛擬環境，例如通過高爾夫球的飛行、賽車的真實世界性能特征、飛行器的飛行或戰爭游戲中的爆炸結果。在圖像處理的其他商業和科學應用（例如，飛行模擬、彈道模擬等）中，對虛擬環境中的物體的相互作用的準確建模受到更大的關注。

在很多現代數據處理系統中，對物體的真實世界相互作用的建模由通常被稱為物理引擎的計算機軟件來處理。物理引擎嘗試通過使用剛體動力學、軟體動力學和/或流體動力學原理來模擬物理現象。大多數物理引擎的一個關鍵組件是碰撞檢測/碰撞響應系統，其試圖檢測虛擬環境中的物體何時互相碰撞?；跈z測到的碰撞，典型地執行動力學模擬，以解析碰撞后施加到物體的力和運動。

某些物理引擎還依賴于基于沖量的算法，其中，沖量被施加到物體之間，以在其之間傳播力。例如，當剛性或可變形的物體互相接觸時，施加到一個物體的力必須被施加到與該物體接觸的其他物體。類似地，施加到流體、織物或其他高度可變形的實體的力必須典型地傳播經過這些實體。

盡管某些更高精度的物理引擎不會受時間限制，許多其他的、特別是在交互視頻游戲應用中使用的那些引擎，需要“實時”運行。因此，與物理計算例如碰撞檢測和沖量傳播相關聯地執行的操作經常需要被快速和高效地完成。

傳統的碰撞檢測和沖量傳播技術典型地在串行、單線程的應用中運行，其中，運動中的每個物體相對于場景中的所有其他物體被測試，且沖量在物體之間一個接一個的傳播。在一些實例中，碰撞檢測會利用空間裁剪來降低所需的碰撞計算的次數。此外，物體可以用細節層次（LOD）模型來建模，以將物體簡化為更容易計算的形狀，以便檢測兩個物體何時互相接觸。例如，很多碰撞檢測技術使用簡單的形狀例如球形或其他立方體積來表示更復雜的物體。更詳細的包圍體（bounding?volume）可以在某些應用中被設計，以提高碰撞精度，但是，這樣做通常是以更多處理時間和/或硬件需求為代價的。

隨著半導體技術在時鐘速度以及并行處理的越來越多的使用方面的提升，實時物理引擎的能力必然會提升。在芯片級別，多個處理器核心通常被置于同一芯片上，其與分離的處理器芯片、或者在一定程度上與完全分離的計算機類似的方式來運行。此外，即使在核心內部，通過使用專門用于處理特定類型操作的多個執行單元，并行處理也被使用。基于硬件的流水線在很多實例中也被使用，從而可占用多個時鐘周期執行的特定操作被分解為階段，使得其他操作能在較早的操作完成之前被啟動。多線程也被使用以使多指令流被并行處理，使更多總體工作能在任何給定時鐘周期內被執行。

但是，即使有提升的時鐘速度和并行處理，傳統的碰撞檢測和沖量傳播技術在大多數傳統架構下仍然有性能瓶頸。特別地，傳統技術通常需要大量的隨機存儲器存取，以檢索和管理場景中的物體，這被發現引起低的高速緩存利用率和其他性能相關的瓶頸。

此外，在很多動態、實時的環境中，將負載分布到執行的多個并行線程中會有問題。特別地，在給定場景中的物體的數量、以及這些物體的分布會隨時間而變化。盡管在某個時刻需要大量處理資源的多個物體間的碰撞會在場景的一個區域中發生，在另一時刻，更多碰撞且由此更重的處理工作量會在場景的另一區域中發生。

因此在本領域中仍然存在對高效地處理物理引擎中的物理碰撞檢測和沖量傳播的需求。

發明內容

本發明通過提供電路布置和方法來解決與現有技術相關的這些和其他問題，該電路布置和方法通過將場景中的物體所有權分配給單獨的線程、并通過在擁有接觸物體的線程之間傳遞線程間沖量消息在互相接觸的物體之間傳播沖量、而使用物體所被分配給的線程來局部傳播沖量經過這樣的物體，來實現多線程物理引擎中的沖量傳播。