實(shí)時碰撞檢測算法技術(shù)

前言

1978年，孩提時代的我就和朋友編寫開發(fā)了第一款屬于我們自己的計(jì)算機(jī)游戲——我仍然清楚地記得，那是一款采用。BASIC語言編寫的猜謎類游戲，玩家將被問及與非洲動物相關(guān)的一些問題。恰巧，“太空入侵者”游戲也于同年發(fā)布。誠然，與“太空入侵者”相比，我們的作品多少有些黯然失色，但大家仍沉湎于其中，樂此不疲。不久，我們即在自己的家用計(jì)算機(jī)上開始模仿“太空入侵者”以及當(dāng)年流行的街機(jī)游戲，并設(shè)計(jì)自己的原創(chuàng)游戲。時光荏苒，歲月蹉跎，昔日對游戲設(shè)計(jì)的愛好引領(lǐng)我成為一名業(yè)界中人，而游戲領(lǐng)域業(yè)已發(fā)展壯大為一項(xiàng)價值達(dá)數(shù)十億美元的產(chǎn)業(yè)，并一直在圖形硬件以及CPU的發(fā)展過程中扮演著催化劑的角色。言歸正傳，動作類游戲設(shè)計(jì)的挑戰(zhàn)之一便是如何正確地處理碰撞檢測問題，即判斷兩個對象間以及對象與場景間的相交問題。鑒于游戲最初源于2D場景，因而碰撞檢測主要集中于如何在屏幕空間內(nèi)高效地計(jì)算對象間的相交狀態(tài)。時至今日，雖然硬件的計(jì)算速度已提高了不止1000倍，但碰撞檢測仍被視為一類核心問題，這一點(diǎn)確實(shí)令人深思。目前，3D游戲已經(jīng)成為主流，但其復(fù)雜度也隨之上升——動輒千萬個多邊形的計(jì)算量已屢見不鮮。相應(yīng)地，在處理這一類較大的數(shù)據(jù)集時，與碰撞檢測相關(guān)的數(shù)據(jù)結(jié)構(gòu)和算法也變得日趨復(fù)雜，皆因這一類計(jì)算具有顯著的實(shí)時特征。這里需要指出的是，游戲設(shè)計(jì)只是復(fù)雜實(shí)時碰撞檢測應(yīng)用的一個分支，在諸如CAD／CAM系統(tǒng)以及3D建模設(shè)計(jì)中也面臨著同樣的問題。針對游戲設(shè)計(jì)以及其他實(shí)時應(yīng)用程序，本書詳細(xì)闡述了與碰撞檢測問題相關(guān)的高效解決方案，包括相應(yīng)的數(shù)據(jù)結(jié)構(gòu)和算法。閱讀本書需要讀者具備良好的數(shù)學(xué)知識，相關(guān)內(nèi)容也會在書中進(jìn)行深入的探討。同時，為了幫助讀者進(jìn)一步理解計(jì)算方案的實(shí)現(xiàn)過程，本書還提供了相應(yīng)的算法、代碼以及偽代碼。綜上所述，碰撞檢測問題涵蓋了豐富的內(nèi)容，甚至?xí)械母髡戮瑟?dú)立成書。鑒于此，本書內(nèi)容力爭做到有的放矢，以便為讀者今后的學(xué)習(xí)打下堅(jiān)實(shí)的基礎(chǔ)。關(guān)于作者本書作者Christer Ericson畢業(yè)于瑞典Umea大學(xué)并獲得計(jì)算機(jī)科學(xué)碩士學(xué)位。隨后，在該校任教多年并于1996年移居美國。1999年，他曾在索尼電腦娛樂公司美國分公司擔(dān)任高級主程序員、高級軟件配置管理工程師和首席軟件工程師。此前，他還曾在Neversoft娛樂公司擔(dān)任主程序員。2002年以來，他一直在“。Full Sail游戲設(shè)計(jì)”和項(xiàng)目開發(fā)部擔(dān)任顧問委員會委員。Christer Ericson涉獵廣泛，目前他將主要精力集中在程序優(yōu)化管理方面，并在游戲開發(fā)者大會上就此問題進(jìn)行了演講。

內(nèi)容概要

本書詳細(xì)闡述了與碰撞檢測問題相關(guān)的高效解決方案及相應(yīng)的數(shù)據(jù)結(jié)構(gòu)和算法，主要包括：碰撞檢測系統(tǒng)中的設(shè)計(jì)問題、數(shù)學(xué)和幾何學(xué)入門、包圍體、基本圖元測試、層次包圍體技術(shù)、空間劃分、BSP樹層次結(jié)構(gòu)、凸體算法、基于GPU的碰撞檢測、數(shù)值健壯性、幾何健壯性以及優(yōu)化操作。另外，本書還提供了相應(yīng)的算法、代碼以及偽代碼，以幫助讀者進(jìn)一步理解計(jì)算方案的實(shí)現(xiàn)過程。    本書適合作為高等院校計(jì)算機(jī)及相關(guān)專業(yè)的教材和教學(xué)參考書，也可作為相關(guān)開發(fā)人員的自學(xué)教材和參考手冊。

作者簡介

作者：（美國）埃里克森（Christer Ericson） 譯者：劉天慧

書籍目錄

第1章  概述	  1.1  內(nèi)容概覽	  1.2  關(guān)于本書的代碼	第2章  碰撞檢測系統(tǒng)中的設(shè)計(jì)問題	  2.1  碰撞算法的設(shè)計(jì)因素	  2.2  應(yīng)用程序中對象的表達(dá)方式	  2.3  查詢類型	  2.4  環(huán)境模擬參數(shù)	  2.5  性能	  2.6  健壯性	  2.7  實(shí)現(xiàn)與使用的簡潔性	  2.8  小結(jié)	第3章  數(shù)學(xué)和幾何學(xué)入門	  3.1  矩陣	  3.2  坐標(biāo)系統(tǒng)和頂點(diǎn)	  3.3  向量	  3.4  質(zhì)心坐標(biāo)	  3.5  直線、光線和線段	  3.6  平面和半空間	  3.7  多邊形	  3.8  多面體	  3.9  凸包計(jì)算	  3.10  域	  3.11  Minkowski和與Minkowski差	  3.12  小結(jié)	第4章  包圍體	  4.1  BV期望特征	  4.2  軸對齊包圍盒	  4.3  Spheres球體	  4.4  方向包圍盒	  4.5  球掃掠體	  4.6  半空間相交體	  4.7  其他類型的包圍體	  4.8  小結(jié)	第5章  基本圖元測試	  5.1  最近點(diǎn)計(jì)算	  5.2  圖元測試	  5.3  直線、光線和有向線段的相交測試	  5.4  其他類型的測試	  5.5  動態(tài)相交測試	  5.6  小結(jié)	第6章  層次包圍體技術(shù)	  6.1  層次結(jié)構(gòu)設(shè)計(jì)問題  6.2  層次結(jié)構(gòu)的構(gòu)建策略	  6.3  層次結(jié)構(gòu)的遍歷	  6.4  包圍體層次結(jié)構(gòu)示例	  6.5  合并包圍體	  6.6  高效的樹型表達(dá)方式及遍歷	  6.7  通過緩存機(jī)制改善查詢	  6.8  小結(jié)	第7章  空間劃分第8章  BSP樹層次結(jié)構(gòu)	第9章  凸體算法	第10章  基于GPU的碰撞檢測	第11章  數(shù)值健壯性	第12章  幾何健壯性	第13章  優(yōu)化操作	參考文獻(xiàn)

章節(jié)摘錄

插圖：【Barequet99】給出了一種簡化算法并對點(diǎn)集實(shí)現(xiàn)了最佳OBB的粗略逼近：首先計(jì)算點(diǎn)集的最小AABB。其中，選擇包圍盒中兩個間距最大的平行面上的兩個點(diǎn)，用以確定OBB的長度方向。于是，點(diǎn)集投影至垂直于OBB長度方向的平面上。采用相同的方法計(jì)算最小的軸對齊矩形，且利用其中兩個間距最大的平行面上的頂點(diǎn)計(jì)算OBB的第2個軸。OBB的第3個軸則正交于前兩個軸。雖然該算法易于編碼，但實(shí)際應(yīng)用中，常采用具有類似復(fù)雜度的其他算法獲取（接近）最優(yōu)的包圍盒，這一類算法將在后文加以描述。對于瘦長類型的物體對象，OBB軸應(yīng)與物體的方向?qū)R；而對于扁平的物體對象，OBB軸應(yīng)與扁平物體的法線方向?qū)R。上述方向?qū)?yīng)于物體的主方向，而且4.3.3節(jié)中描述的主成分分析也可以應(yīng)用于此處。對于在空間內(nèi)頂點(diǎn)均勻分布的模型來說，基于模型頂點(diǎn)的包圍盒計(jì)算一般能夠正常運(yùn)行。然而，內(nèi)部頂點(diǎn)產(chǎn)生的影響往往使協(xié)方差計(jì)算產(chǎn)生偏移，并使得OBB呈現(xiàn)任意方向——即使存在極值頂點(diǎn)。因此，應(yīng)避免使用基于加權(quán)頂點(diǎn)位置的包圍體計(jì)算方法。足以引起注意的一點(diǎn)是：最小包圍體的特征定義（中心位置、維度以及方向）皆獨(dú)立于物體頂點(diǎn)的點(diǎn)簇（clustering）。這一點(diǎn)可以通過對包圍體添加（或去除）額外的內(nèi)部或邊界偏心頂點(diǎn)得到驗(yàn)證，該方法并不影響包圍體的特征定義，因此也不會影響其計(jì)算結(jié)果。然而，以上述方式增加額外頂點(diǎn)卻會改變頂點(diǎn)的協(xié)方差矩陣，從而改變了依據(jù)此矩陣計(jì)算出的OBB特征。這種情況可以通過只考查極值點(diǎn)加以改善，即只考慮使用物體對象模型上的凸頂點(diǎn)，從而消除內(nèi)部頂點(diǎn)導(dǎo)致的OBB非對齊問題。然而，即使全部剩余頂點(diǎn)皆為極值頂點(diǎn)，基于頂點(diǎn)的分布狀態(tài)，最終的OBB仍可出現(xiàn)不可預(yù)料的錯誤，其結(jié)果為：點(diǎn)簇仍使得指向自身的某一軸產(chǎn)生偏移。從另一個角度來看，即孤立地對頂點(diǎn)實(shí)施計(jì)算將無法生產(chǎn)穩(wěn)定、可靠的協(xié)方差矩陣。

編輯推薦

《實(shí)時碰撞檢測算法技術(shù)》是由清華大學(xué)出版社出版的。

圖書封面

圖書標(biāo)簽Tags

無

評論、評分、閱讀與下載

---

    實(shí)時碰撞檢測算法技術(shù) PDF格式下載

---