http://yuri.cnblogs.com/
Broad-phase碰撞檢測
Sweep and Prune：
1.將物體的AABB分離到三個坐標(biāo)軸上。得到若干個區(qū)間。
2.根據(jù)區(qū)間的終點坐標(biāo)由小到大排序。
3.逐個遍歷排序結(jié)果，當(dāng)遇到一個區(qū)間的起始點的時候，就將這個區(qū)間放到一個列表中；當(dāng)遇到一個區(qū)間的終點時，就將這個區(qū)間從列表中清除。
當(dāng)在列表中存在區(qū)間，而又遇到一個新區(qū)間的起始點時，則遇到的區(qū)間與列表中的所有區(qū)間重疊。
4.如果一對物體在三個坐標(biāo)軸上的區(qū)間都重疊，那么他們的AABB相疊。
Mid-phase碰撞檢測
碰撞檢測樹就是將要碰撞的網(wǎng)格分離成多個部分，并將這些部分按樹的結(jié)構(gòu)組織起來。
我的碰撞檢測樹就是一BVH樹，和標(biāo)準(zhǔn)的AABB碰撞檢測樹相比，AABB樹是2叉樹，我的樹的節(jié)點數(shù)是不定的。
兩種建樹過程如下：
|
AABB：
1.計算三角形集合的AABB包圍體
2.找出一個平面，這平面能最大限度的分割三角形集合（一般在中心即可），這個平面必須與坐標(biāo)平面平行（因為包圍體是AABB）
3.穿過這個平面的三角形按中點分配到平面一側(cè)，如果中點還在平面上，隨便分配
4.將分出的這兩部分作為子節(jié)點繼續(xù)分割（步驟1），直到分出的部分只有一個三角形
|
|
我的碰撞檢測樹：
1.計算三角形集合的包圍體
2.計算三角形集合的幾何重心，將幾何重心視為原點，按三個坐標(biāo)平面將三角形集合分成8部分
3.穿過這個坐標(biāo)平面的三角形按中點分配到平面一側(cè)，如果中點還在平面上，隨便分配
4.如果有的部分中沒三角形，那么去掉它。如果只有一部分且這部分包含多個三角形，強行隨便的將這部分分成多部分（防止死遞歸）。
5.將分出的n部分作為子節(jié)點繼續(xù)分割（步驟1），直到分出的部分只有一個三角形 |
我的樹可能不如AABB樹平衡，可能性能稍差。
注：
碰撞檢測樹一般在物體定坐標(biāo)系下建立出來
可以根據(jù)情況，為不同節(jié)點選擇不同類型的包圍體，使得包圍體包圍得最緊湊
碰撞檢測：
一個幾何圖形vs樹
按深度優(yōu)先或廣度優(yōu)先遍歷樹，對于非最末級節(jié)點，判斷幾何圖形是否和節(jié)點包圍體相交，如果相交那么繼續(xù)遍歷它的子節(jié)點。對于最末級節(jié)點，還要進行幾何圖形和最末節(jié)點所對應(yīng)的三角形求交。這樣，遍歷完一次即可找到所有碰撞。
注：
1.碰撞檢測需檢測出碰撞點，碰撞法向量，和刺穿深度
2.球和三角形碰撞：
以下過程按順序執(zhí)行，一旦相交就return，停止和這個三角形繼續(xù)檢測：
(1).判斷球心與三角面垂直且過三邊的平面的位置關(guān)系，如果被包圍，那么直接判斷球心到三角面所在平面距離是否<=半徑
(2).根據(jù)(1)的結(jié)果，如果球心在哪條邊外，那么試著和那條線段求交
(3).判斷球心到三角形某頂點距離<=半徑
3.球和棱、點碰撞，碰撞法向量為那個面在碰撞點的切平面的法向量
4.通過更精確的包圍體測試，會遍歷更少節(jié)點，但更精確的包圍體測試一般會花更多時間。
樹vs樹 對于一對節(jié)點，判斷兩個節(jié)點的包圍體是否相交。如果相交，那么測試它們的子節(jié)點包圍體是否相交。
如果有一個節(jié)點是最末級節(jié)點，它對應(yīng)著一個三角形，另一個是一個非最末級節(jié)點，那么問題轉(zhuǎn)化為上面“一個幾何圖形vs樹”。
如果兩個節(jié)點都是最末級節(jié)點，那么進行三角形求交。
注：
對于剛體，它們會轉(zhuǎn)動，轉(zhuǎn)動了的AABB可以用AABB加上一個剛體變換矩陣表示。也可懶一些，直接把樹放入全局坐標(biāo)系下，更新樹。
樹的更新：
如果物體不是剛體，可能會形變，這就需要更新樹。一般自下而上的更新樹。先根據(jù)最末級節(jié)點對應(yīng)的三角形，更新最末級節(jié)點。然后一級一級更新上面的節(jié)點，使它們的包圍體包住子節(jié)點。
以后安排（先把想法記下來）
物體破裂 ：
將物體網(wǎng)格表示成一張無向圖（不用鄰接矩陣表示），在壓強足夠大的地方細化網(wǎng)格，細化出的部分作為圖的一部分，然后從壓強足夠大的幾個頂點遍歷圖。遍歷時根據(jù)物體物理材質(zhì)選擇圖的邊（第一條邊應(yīng)選擇最和切向量正交的），將其并入斷裂線，必要時就細化網(wǎng)格，直到這條線首尾封閉。這樣做是因為不同材質(zhì)的物體，其斷裂口有的光滑，有的粗糙，甚至有尖刺。這樣應(yīng)該能生成一條滿意的斷裂線。然后取出子圖，成為分裂出的物體的網(wǎng)格的一部分。不過斷口的填充就暫無想法了……
腳本：
設(shè)想了一種托管腳本。先寫好腳本，經(jīng)過編譯器將其編譯為自定的較低級中間語言，或者直接IL代碼。運行前加載時，對其進行JIT編譯，除了.Net的JIT以外，還有自己的一些，當(dāng)然肯定是自己先處理后再交給.Net……這樣腳本最終就是本機代碼，執(zhí)行速度比解釋型的快，而且異常也不用一下一下的考慮。
一開始編譯為直接IL代碼時，不能直接轉(zhuǎn)為它的字節(jié)碼，而是自己規(guī)定的字節(jié)碼，但其指令還是一一對應(yīng)的（就是把IL代碼用2進制形式表示了一下）。這主要是因為代碼中有一些東西，還不能直接轉(zhuǎn)為標(biāo)準(zhǔn)的IL字節(jié)碼
最終應(yīng)該可以構(gòu)建復(fù)雜的物體，比如一個人，由Joint、剛體（骨骼和關(guān)節(jié)）和柔體（頭發(fā)和肥膘）組成。他做個什么動作要是碰到了什么倒是自然能模擬出來。不過他的行走，怎么維持重心不好說，我的想法是對已做好的動畫解析，將其數(shù)值微分，最后算出各部分的作用力……維持重心不管他用那些肌肉，維持重心的力 應(yīng)該包括在里面……
以前有外國人擬做過類似的東西，第六屆全國中小學(xué)電腦制作活動上還有即將得一得獎的抄過——botz，一個2D質(zhì)點彈簧系統(tǒng)模擬程序，它的歐拉法積分不嚴(yán)密（或者說就不是），碰撞檢測就和邊界檢查了一下，但是要注意他的“肌肉”思想，質(zhì)點彈簧系統(tǒng)組成機器人，然后肌肉伸縮運動，我這個應(yīng)該和那個在這一點有著類似之處。更接近一點的東西就是Dr.Jan Bender的那些機器人了。
當(dāng)然稍微遙遠的東西別想得太多，畢竟還有不少東西未完成……