3D遊戲的碰撞檢測是如何實現的？
大三學生實現了一個模擬CS的遊戲，使用Glew、GLFW庫，並使用Assimp工具導入dust2地圖模型。導入後的模型是由三角面片組織起來的。
現有的碰撞檢測演算法是對玩家實現一個AABB包圍盒，並且對場景中每一個三角面片實現AABB包圍盒，每次玩家移動的時候，就遍歷場景中所有的包圍盒（十的四次方數量級）判斷是否發生了碰撞，這種方法既開銷大又不夠精確。
我希望達到的目標是，能夠對玩家的角色模型和地圖模型分別產生比較精確的物理邊界，並且檢測它們是否發生碰撞的時間開銷在可以接受的範圍內。
在網上查找一些解決方案，它們說的大多是規則物體之間的碰撞檢測，對我遇到的問題助益甚微。
想知道有沒有什麼好一些的改進演算法。
首先，遊戲中的碰撞都是基於規則形狀的！
推薦一本神書Real-Time Collision Detection
如果是為了實現功能，接入physX物理引擎就好了，如果是為了學習裡面的演算法，那就選擇性看裡面的實現，physx已經開源了，原理的話，bullet的作者有gdc的演講ppt，講得很好的，網上能搜得到。
粗階段，各種空間管理演算法，基於grid或者樹，各有優缺點。精細階段，各種計算幾何演算法，搜一下gjk如果只是檢測是否碰了，相對簡單。如果要算碰撞約束，演算法就複雜了，通常是迭代演算法求近似解，業界都有對應的演算法，不藉助物理引擎自己擼，只能處理些簡單的情況我來說一個思路好不好？我不是開發遊戲的，所以是外行。但是我上學時是學開發遊戲的（Computer Game Engineering），所以至少屬於「民科+」水平。
這是我當初的講義上，老師給的方法：
概括的說，就是為需要精確檢測的不規則物體生成「包圍球二叉樹」。offline生成，物體移動時，只需同步移動所有包圍球球心即可。那麼碰撞檢測時，只需進行 球-球 檢測即可。對人腦和電腦，一切都很簡單。
具體方法，我估計題主這麼聰明應該能自行想出。
首先，這個二叉樹其實就是物體本地空間的空間分割二分樹。
- 設物體所有三角形集合為
;
- 根據
和
;
- 遞歸的，對
然後，在執行遞歸拆分時，同時創建二叉樹：每次形成一個集合C，除了生成C的AABB用於空間分割之外，再生成一個包圍球（即一個點+一個半徑），創建一個樹節點存儲該包圍球。三角形集合C及其拆分子集合顯然也就是樹節點的父子關係。
最後，在碰撞檢測時，從樹根開始進行弱智一般的 球-球 檢測：
假設物體1形狀複雜，已生成一個上述二叉樹，而物體2是一個石頭，只用一個球表示：
collisionDetect(樹節點，石頭槌) {
if (當前樹節點.球 與 石頭槌 不相交) {
返回（不碰撞）
} else if (當前節點是葉子) {
計算碰撞點和碰撞向量 /* 演算法很顯然，就不贅述了 */
返回（碰撞信息）
} else {
碰撞信息=collisionDetect(樹節點.左子節點，石頭槌)
if (不碰撞!=碰撞信息) {
返回（碰撞信息）
}
碰撞信息=collisionDetect(樹節點.右子節點，石頭槌)
if (不碰撞!=碰撞信息) {
返回（碰撞信息）
}
返回（不碰撞）
}
}
/* 「碰撞向量」與檢測無關，是用於「collision response」的 */
時間複雜度是 n*log2(m)。n是有必要檢測的複雜物體數量，m是平均拆分深度。「有必要」是指，對於整個場景，你還需要另一套空間分割數據結構（比如八叉樹），以便避免去檢測地道里的人和天上飛的「chopper」。
那如果兩個都是複雜物體嘞？即兩個二叉樹怎麼判斷？應該升級一下上面的naive演算法即可。當初老師沒講，我的想法是：
要麼考慮一下，作為一個遊戲，到底該不該做兩個複雜物體的碰撞？
如果真的需要，則大概應該是，
- 從其中一個物體A的二叉樹中，一次只拿出一個節點上的包圍球，然後退化為上面naive演算法，與，另一個物體B的二叉樹進行檢測……
- 如果檢測失敗，換其兄弟節點再檢測，再失敗，則不碰撞；
- 如果檢測成功，則用其子節點繼續檢測。如果已為葉子節點，則完工，返回碰撞信息。
時間複雜度應該是n*(log2(m) ^ 2)，其中n粗略為這種級別的檢測發生的次數。
憑6年前的記憶寫的，有些惶恐。
高效的碰撞檢測一般要分2個階段：
- broad phase 快速找出潛在的碰撞物體對列表，不在這個列表裡的是絕對沒可能碰撞的。broad phase確定了一批需要進一步檢查的物體對。
- narrow phase 準確找出發生碰撞的物體對列表。因為上一個階段的部分物體對實際上是沒有碰撞的，需要在這個階段剔除。
至於數據結構，要麼是各種基於空間劃分的樹，要麼BVH。
演算法的話看這兩個足夠：SAT，GJK。
這些了解清楚了，做剛體的碰撞檢測足矣。FPS遊戲一般都只是剛體之間的碰撞。
（有意思的是，曾經和一位同學交流，他們項目通過提高CPU緩存一致性，並去掉了複雜的場景樹，換用列表來管理。即使n平方的複雜度，表現依然不錯）
（曾經寫了一篇碰撞檢測科普文，但沒寫完：碰撞檢測演算法）
謝邀。
只要學習一下四叉樹和八叉樹，一切問題都很明了啦~~
碰撞計算本身也有可優化空間，但是並不是重點。利用四叉樹可以成千上萬倍的縮小檢測規模，是最首要的。
來張圖解釋思想原理。截圖來自：空間索引 - 四叉樹 - 枕邊書 - 博客園：
我們的步驟是：
1、快速批量排除大量毫無關係的物體。
2、在小範圍內查找或者檢測具體某個物體。
看圖具體來說，主角在大地圖上，有可能和如此之多的物體發生碰撞……但是有一點是顯然的，如果主角和物體不處於同一個格子內，那麼肯定不會碰到……好了，這一棍子打死好大一片，如果我們給空間分好了格子（有層次的劃分，就是四叉樹），那麼瞬間絕大部分物體就被我們跳過了。
接下來一個最小的小格子里最多也就那麼幾個物體，依次判斷即可。
重要的技術往往有一個非常簡單的內核。只要理解了上圖，再去學習四叉樹的具體實現應該就不難了。
分開兩部分:1、地圖用astar刷圖，角色通過尋路來取消場景碰撞檢測。2、角色碰撞檢測優化性能，如果是數量過多，那就BSP分割空間對於檢測不精確的問題，AABB包圍盒不行的話就用膠囊體
UE4的移動碰撞 - 李雪峰的文章 - http://zhuanlan.zhihu.com/p/33529865
正好這段時間在研究，不過是膠囊體碰撞檢測，希望可以幫助你
把場景放在樹里，根據場景的特徵你要使用不同種類的樹，這樣就快了。
簡單說下我上學時研究過的一個課題，跟你這個差不多，主要思想是只檢測主要物體和它附近的三角形，而不是整個空間的三角形。
將整個空間劃分為均勻的正方體網格，將所有三角形和主要物體根據其位置放入某個網格中。檢測時，只需要檢測主要物體所在的網格以及該網格周圍26個網格中的三角形就可以了。
你需要使用二維或三維的樹結構來提高碰撞檢測效率
3d的一般使用樹+三角形，先踢掉不可能發生碰撞的物體然後進行三角面形片求解但也會卡的，不需要複雜求解的地方(比如人被子彈幹掉或者掉hp)一般只運行腳本和碰撞檢測不運行求解器一般使用aabb，而地形受力求解就需要運行求解器了一般遊戲都有兩層物理引擎但複雜剛體約束(比如大樓坍塌)也需要簡化的，求解器最複雜一般遊戲使用簡化約束方程進行積分進行矢量擬加stack+相交測試應該說相交測試是最常用的不過並不需要連續ccd像box2d支持連續ccd可以用於憤怒的小鳥但這是2d的3d的求兩個三角形的交集部分坐標而且再分三角形就相當於2d一次兩個三角形碰撞檢測雖然物體也許少但運算成倍提升，而且好多的接觸面是多邊形的交集。。。物理引擎封裝力學演算法是最難最考驗思維能力的優化方式也是想辦法減少相交測試而且進行線性求解而且要看起來順眼基本上一個高中生能寫出box2d的solver那就是天才了啊更別說havok的流體求解器。。。
10^4 應該是你沒有實現索引樹，比如quadtree kdtree 先用它查詢在做，檢測 先AABB 檢測 然後 TBB檢測，最後hausdoff 距離和，解方程檢測
可以用多重的檢測，先用包圍球檢測篩選出可能碰撞的物體，檢測成功的物體再進行詳細的模型檢測。
BVH或八叉樹，視你場景動態物體而定
首先，你要想計算碰撞那肯定是基於規則物體的，基於三角面的想法第一不好實現，第二卡的要死。你第一步是要把你的那一堆模型，使用一些經典碰撞體擬合出來，不管是aabb還是膠囊。就好像physx裡面的cooking操作一樣。實際上如果你的擬合處理的不錯的話，最終的碰撞體列表並不會很多，再加上大部分你的場景模型其實都是靜態的碰撞體，你每一幀需要計算的物理量並不太多。我這裡假設你的場景足夠大，裡面有許多角色需要運動的話，那你的擬合體需要按照場景樹的結構不斷維護，這樣每一個物體都只需要很少的遍歷就可以判斷碰撞了。
最後，我個人倒是建議你直接用物理引擎處理這些事情，簡單方便效率高。
1.減少場景內包圍盒的數量，並不需要每個三角面片都做包圍盒。
2.使用八叉樹提高遍歷搜索的效率。
可以分幾個層面來優化遊戲中的碰撞檢測演算法：
1，場景管理：把場景中的物體，放置在一棵遞歸八叉樹中，檢測的時候如果射線與八叉樹的某個子節點不相交，則放棄整個子節點，否則一直到葉子節點，然後與葉子節點上的物體的AABB進行檢測，有相交才進入物體級別的檢測。
2，靜態物體檢測：預處理的時候，就把物體的所有三角面都用平衡二叉樹管理起來，每個節點都是一個AABB，類似於場景碰撞檢測演算法，只有相交才進入下一個階段，否則放棄整個子節點。一直到葉子節點，這時候與葉子節點的三角形列表進行逐個檢測。可以返回精確的碰撞點位置（以及需要的材質，法線等等）。如果不要求精確位置，可以考慮用一個低模來做碰撞檢測。
3，骨骼動畫物體檢測：一般用多個膠囊套住，膠囊跟著骨骼動畫更新位置及朝向。檢測的時候通過與每個膠囊進行檢測就行，一般不需要返回精確的碰撞點，如 @張心欣 所述。
沒有相關經驗，純屬yy，求從業人員求證
3-d tree? O((log n) ^ 3)八叉樹，室內場景的話就再加個PVS。
做過個3D賽車遊戲，我記得是檢測坐標的，看物體A最凸出的那個點的坐標是否位於物體B的最外圍的切面上。
不記得術語怎麼說了，或者是用點去切面，或者用線去切面。
推薦閱讀：