1樓：TC130
TC130：遊戲物理引擎(二) 碰撞檢測之Broad-Phase
TC130：遊戲物理引擎(三) 碰撞檢測之Narrow-Phase
2樓：FXCarl
你的方法其實並沒有什麼問題，碰撞檢測就是圖元相交測試。三角形和三角形的交叉是這樣的
選擇乙個三角麵片 A 取出三個邊
和另外乙個三角形 B 所在的平面做相交測試，看看是否邊的兩個端點在面的兩側
如果穿過表面，計算平面上點 P 到三角形 B 三邊的投影距離，看看是否在三角形 B 內部
得到是否三角形相交
可能有幾個改進的方向：
需求上的
確定遊戲不是需要做凸體碰撞檢測？
製作上的
是不是可以把角色從複雜的網格簡化成比較簡單的形體就像 @張心欣 說的
是不是可以把場景用來做碰撞檢測的幾何形狀做的比渲染用的簡單些
實現上的
是否考慮搞個物理引擎來試試
考慮一下用比較簡單的空間分割方式來加速一下
先把空間劃分成柵格，然後記錄柵格內的三角形列表
先確定要碰撞的三角形是哪個柵格裡的，然後再做相交測試
最後才是技巧
把柵格做成一層一層的，就是四叉樹或者八叉樹
把柵格做成一堆一堆物件聚合起來的，就是層次包圍樹
在場景中選個三角形平面為起點，把剩下的多邊形一層一層分在左右兩邊的樹就是BSP
BSP 有好多優化問題
等專案做完了總結的時候可以看 GJK 之類的演算法往理論上提公升了
我覺得有專案壓力的時候就不要臨時去學習技術了，來不及。先確定需求，不行改製作，臨時學來的技術往往很不可靠 ……
3樓：李雪峰
UE4的移動碰撞 - 李雪峰的文章 - http://zhuanlan /p/33529865
正好這段時間在研究，不過是膠囊體碰撞檢測，希望可以幫助你
4樓：maja
10^4 應該是你沒有實現索引樹，比如quadtree kdtree 先用它查詢在做，檢測先AABB 檢測然後 TBB檢測，最後hausdoff 距離和，解方程檢測
5樓：武龍飛
分開兩部分:
1、地圖用astar刷圖，角色通過尋路來取消場景碰撞檢測。
2、角色碰撞檢測
優化效能，如果是數量過多，那就BSP分割空間對於檢測不精確的問題，AABB包圍盒不行的話就用膠囊體
6樓：Daly
如果是為了實現功能，接入physX物理引擎就好了，如果是為了學習裡面的演算法，那就選擇性看裡面的實現，physx已經開源了，原理的話，bullet的作者有gdc的演講ppt，講得很好的，網上能搜得到。
粗階段，各種空間管理演算法，基於grid或者樹，各有優缺點。
精細階段，各種計算幾何演算法，搜一下gjk
如果只是檢測是否碰了，相對簡單。如果要算碰撞約束，演算法就複雜了，通常是迭代演算法求近似解，業界都有對應的演算法，不借助物理引擎自己擼，只能處理些簡單的情況
7樓：pancystar
首先，你要想計算碰撞那肯定是基於規則物體的，基於三角面的想法第一不好實現，第二卡的要死。
你第一步是要把你的那一堆模型，使用一些經典碰撞體擬合出來，不管是aabb還是膠囊。就好像physx裡面的cooking操作一樣。
實際上如果你的擬合處理的不錯的話，最終的碰撞體列表並不會很多，再加上大部分你的場景模型其實都是靜態的碰撞體，你每一幀需要計算的物理量並不太多。
我這裡假設你的場景足夠大，裡面有許多角色需要運動的話，那你的擬合體需要按照場景樹的結構不斷維護，這樣每乙個物體都只需要很少的遍歷就可以判斷碰撞了。
最後，我個人倒是建議你直接用物理引擎處理這些事情，簡單方便效率高。
8樓：
可以分幾個層面來優化遊戲中的碰撞檢測演算法：
1，場景管理：把場景中的物體，放置在一棵遞迴八叉樹中，檢測的時候如果射線與八叉樹的某個子節點不相交，則放棄整個子節點，否則一直到葉子節點，然後與葉子節點上的物體的AABB進行檢測，有相交才進入物體級別的檢測。
2，靜態物體檢測：預處理的時候，就把物體的所有三角面都用平衡二叉樹管理起來，每個節點都是乙個AABB，類似於場景碰撞檢測演算法，只有相交才進入下乙個階段，否則放棄整個子節點。一直到葉子節點，這時候與葉子節點的三角形列表進行逐個檢測。
可以返回精確的碰撞點位置（以及需要的材質，法線等等）。如果不要求精確位置，可以考慮用乙個低模來做碰撞檢測。
3，骨骼動畫物體檢測：一般用多個膠囊套住，膠囊跟著骨骼動畫更新位置及朝向。檢測的時候通過與每個膠囊進行檢測就行，一般不需要返回精確的碰撞點，如 @張心欣 所述。
9樓：張心欣
首先，遊戲中的碰撞都是基於規則形狀的！
比如這是虛幻4引擎中的碰撞模型，黃色的是角色，線框膠囊形狀的包圍是實際處理的碰撞檢測物件！計算是到膠囊為止的，並不會對其內的三角形再進行額外的檢測。
這樣的話乙個人也就被分為了十幾二十個檢測，再加上包圍盒和八叉樹，一幀就算有數十人亂跑，所需執行的碰撞檢測也就在數百次左右O(NlogN).
10樓：算了吧小魚
做過個3D賽車遊戲，我記得是檢測座標的，看物體A最凸出的那個點的座標是否位於物體B的最外圍的切面上。
不記得術語怎麼說了，或者是用點去切面，或者用線去切面。
11樓：
高效的碰撞檢測一般要分2個階段：
broad phase 快速找出潛在的碰撞物體對列表，不在這個列表裡的是絕對沒可能碰撞的。broad phase確定了一批需要進一步檢查的物體對。
narrow phase 準確找出發生碰撞的物體對列表。因為上乙個階段的部分物體對實際上是沒有碰撞的，需要在這個階段剔除。
至於資料結構，要麼是各種基於空間劃分的樹，要麼BVH。
演算法的話看這兩個足夠：SAT，GJK。
這些了解清楚了，做剛體的碰撞檢測足矣。FPS遊戲一般都只是剛體之間的碰撞。
（有意思的是，曾經和一位同學交流，他們專案通過提高CPU快取一致性，並去掉了複雜的場景樹，換用列表來管理。即使n平方的複雜度，表現依然不錯）
（曾經寫了一篇碰撞檢測科普文，但沒寫完：碰撞檢測演算法）
12樓：簡單點
簡單說下我上學時研究過的乙個課題，跟你這個差不多，主要思想是只檢測主要物體和它附近的三角形，而不是整個空間的三角形。
將整個空間劃分為均勻的正方體網格，將所有三角形和主要物體根據其位置放入某個網格中。檢測時，只需要檢測主要物體所在的網格以及該網格周圍26個網格中的三角形就可以了。
彈幕遊戲的碰撞檢測一般是怎麼實現的？
施展 上個月正好在公司花兩天做了個彈幕遊戲的demo。彈幕碰撞主要是將敵人和自己的子彈區分開，分別存入兩個網格物件中。網格物件持有乙個二維陣列 當然一維陣列也可以 陣列的長度為 螢幕長度 單個網格的長度 螢幕高度 單個網格的高度 效果如下圖 陣列用於存放處在該網格中的所有子彈。假設螢幕為480 80...
256位元組3D程式是如何實現3D引擎的呢？
Mack 利用演算法生成資源的方式。有個第三方外掛程式substance也利用這種方式極大壓縮貼圖，可以使用他的材質庫或者工具生成貼圖，遊戲在執行時還原貼圖，極大的壓縮貼圖。和很多實時生成的大地形，無限種賽道等有些類似，利用時間換空間。 戴文宗 稍微補充下。這類效果和體積的Demo一般只會用到 ra...
3ds的裸眼3D與3D遊戲的3D有什麼區別？
韓愛卿 我看大家也都解釋差不多了 我們平時所玩的3D遊戲，就是用建模來完成的。而3DS的裸眼3D，則是在顯示效果上完成3D化，甚至有些遊戲就沒有3D建模，而是通過圖層都位置實現景深效果 可能不太準確 雖然在市場表現上，裸眼3D顯得比較雞肋。但其實，在許多遊戲上，裸眼3D的開啟都使遊戲體驗上公升了乙個...