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