分析碰撞檢測庫Opcode 收藏
一．概述

Opcode是一個(gè)開源的碰撞檢測庫，其最大的特點(diǎn)是占用內(nèi)存少（與其他的碰撞檢測庫相比而言），對一個(gè)完全二叉樹中的每個(gè)三角形僅用20字節(jié)，所以它的文檔中說是“Memory-optimized bounding-volume hierarchies”。

在碰撞檢測中，利用檢測樹（Bounding-volume hierachies）結(jié)構(gòu)進(jìn)行碰撞排除是最普遍的方法（如RAPID，SOLID，QuickCD,PQP都是如此），Opcode也不例外，Opcode中默認(rèn)的包圍盒是AABB。就是說若用Opcode進(jìn)行一個(gè)Mesh的碰撞檢測，則它會(huì)為此Mesh建立AABB樹。

Opcode可以對以下情況作出檢測：
- Mesh-mesh
- Sphere-mesh
- Ray-mesh
- AABB-mesh
- OBB-mesh
- Planes-mesh

二．檢測過程

調(diào)用Opcode的代碼做檢測時(shí)主要包含三部分：

1.為Mesh生成碰撞樹

這涉及到Opcode中的Model類和OPCODECREATE類，Opcode建立碰撞樹分兩步：首先建立一般的樹（這個(gè)樹最后被遺棄），然后利用一般的樹建立一個(gè)優(yōu)化的樹。

Opcode可以建立的四種樹（關(guān)于這幾種樹在后面的內(nèi)存優(yōu)化部分會(huì)講到）：

- Normal trees (2*N-1 nodes, full size)

- No-leaf trees (N-1 nodes, full size)

- Quantized trees (2*N-1 nodes, half size)

- Quantized no-leaf trees (N-1 nodes, half size)

從代碼中可以看出在建立一般樹的時(shí)候，Opcode允許指定對節(jié)點(diǎn)進(jìn)行分組時(shí)的依據(jù)，如利用Geometry的AABB盒所在的最長軸（SPLIT_LARGEST_AXIS）進(jìn)行分組。

2.為上面所列的查詢建立相應(yīng)的Collider和Qurey方式

對一類檢測建立一個(gè)Collider，如Mesh-mesh查詢用AABBTreeCollider,Sphere-mesh查詢用SphereCollider等。

Qurey方式包括First Contact和All Contacts兩種，另外還可以指定是否采用temporal coherence（時(shí)間連續(xù)性）。

3.建立cache

關(guān)于具體的調(diào)用函數(shù)在其文檔中已經(jīng)給出，不再羅列。

三．內(nèi)存優(yōu)化

如上所述，Opcode進(jìn)行內(nèi)存優(yōu)化是其顯著的特點(diǎn)，所以在這里專門提出。其優(yōu)化方法如下：

1.合理組織內(nèi)存，每個(gè)節(jié)點(diǎn)所占用的空間較少。如RAPID為樹中的每個(gè)節(jié)點(diǎn)保存三個(gè)指針（本身、左子、右子），而通過特意組織內(nèi)存后，完全可以只要兩個(gè)指針（本身、左子），而另右子指針總在左子+1的位置上。

2.去掉葉子節(jié)點(diǎn)。在一個(gè)完全樹中共有2*N-1個(gè)節(jié)點(diǎn)，其中N個(gè)為葉子節(jié)點(diǎn)，每個(gè)葉子節(jié)點(diǎn)包含一個(gè)Primitive（三角形）和其相應(yīng)的BV（包圍盒），通常情況下檢測到葉子節(jié)點(diǎn)時(shí)先測試其BV碰撞情況再測試Primitive。Opcode去掉了N個(gè)葉子節(jié)點(diǎn)，這樣大大節(jié)省了內(nèi)存空間，它將原葉子節(jié)點(diǎn)的Primitive指針信息放到其父節(jié)點(diǎn)里，也剔除了原葉子節(jié)點(diǎn)的BV，檢測時(shí)直接檢測Primitive和BV的相交情況。雖然Primitive和BV的相交測試較BV-BV復(fù)雜，但其少了BV-BV這一步所以性能上并沒有什么損失。

這樣優(yōu)化后的內(nèi)存占用量為原來的50%。
 

這樣去掉葉子節(jié)點(diǎn)后進(jìn)行檢測的偽代碼如下：
 

A and B are two bounding volumes

A0 and A1 are both children of A

B0 and B1 are both children of B

test(A, B)

{

       if(A overlaps B)

       {

              // A0B0

              if(A0 is leaf)

                     if(B0 is leaf) test(leaf, leaf) => Primitive-Primitive test

                     else test(leaf, box) => Primitive-BV test

              else

                     if(B0 is leaf) test(box, leaf) => Primitive-BV test

                     else test(box, box) => BV-BV test

              // Repeat for A0B1

              …

              // Repeat for A1B0

              …

              // Repeat for A1B1

              …

       }

}

3.Quantize。每個(gè)float數(shù)被Quatize為16位的整型數(shù)，在runtime階段再進(jìn)行Dequantize，進(jìn)行Quantize的方法在Deering, Michael, Geometry Compression, Computer Graphics (SIGGRAPH’95 Proceedings), pp. 13-20, August 1995.中。

進(jìn)行Quatize和Dequantize會(huì)導(dǎo)致精度的下降，以至檢測不夠精確，因此Opcode在Dequatize時(shí)采取措施保證Dequatized的包圍盒大于等于原本的包圍盒，以防止檢測的丟失。這樣無疑會(huì)帶來速度的下降，好在在采用2中優(yōu)化方法后，包圍盒的數(shù)量減少了一半，所以這個(gè)影響并不像對一個(gè)標(biāo)準(zhǔn)樹的影響那樣大。另外可以利用SAT-lite、Class III axes的方法做粗糙檢測（coarser BV-BV tests），使其快速收斂到primitive-BV、primitive-primitive檢測，在Opcode的代碼中提供了采取此方法的選項(xiàng)。

這樣的優(yōu)化又在2的基礎(chǔ)上將其內(nèi)存占用量減為50%。

四．總結(jié)

總體上來說，Opcode在降低內(nèi)存占用量的同時(shí)，良好的保持了快速性。

值得注意的是，沒有一種碰撞檢測庫可以在任何情況下都達(dá)到最快速度，通常都是針對某一種或某些情況速度快一些，即使同樣的場景，若物體動(dòng)作情況不同，碰撞面多少的不同都可能會(huì)導(dǎo)致各個(gè)庫的速度變化較大。

在Opcode的文檔中是這樣敘述的：

As far as speed is concerned, it is a lot more difficult to provide accurate comparisons and fair figures. Often, simply changing the relative orientation of two models makes one library faster or slower than another. In many cases we have found our implementation to outperform RAPID (up to 5 times faster), mainly when objects were deeply overlapping. This is very encouraging since intersection testing using AABB trees usually takes 50% longer than using OBB trees in cases where there is a lot of overlap among the models. In some other cases RAPID was faster, mainly in close-proximity scenarii where OBBs are really more appropriate than AABBs (and indeed RAPID sometimes uses a single OBB-OBB test in those situations, whereas we need a lot more). Nonetheless it’s interesting to note our version was often not significantly slower than RAPID in those cases.

另外值得一提的是，北卡(UNC)的GAMMA Group做了大量的碰撞檢測工作，開發(fā)了多個(gè)碰撞檢測庫，包括用GPU的Occlusion Query來做精細(xì)檢測。

 Ps:這篇筆記是一年前寫出的，今天偶然翻出，稍微整理放到這里，歡迎點(diǎn)評(píng)。

本文來自CSDN博客，轉(zhuǎn)載請標(biāo)明出處：http://blog.csdn.net/arenak/archive/2007/12/11/1929151.aspx