解讀Box2D (1)核心入口 void b2World::Step

最近在轉型做遊戲，那麼閱讀Box2D當然是件必要且愉快的事情。

Box2D的源碼位址https://github.com/erincatto/Box2D

Box2D的官網 http://www.box2d.org

Paladin的Box2D克隆位址 https://github.com/PaladinDu/Box2D.git

這個克隆目前并沒有新增内容，隻是增加了一些中文注釋。

在後續的學習過程中可能會添加一些demo到Testbed中。

選擇從void b2World::Step說起是因為Step是Box2D對一個邏輯針的實作。

我想這應該是一個實體引擎核心的代碼了。

了解了Step，你就了解了實體引擎的邏輯結構。

當然Box2D之是以這麼優秀，與其背後高超的結構設計，碰撞算法，邏輯優化同樣密不可分。

不過本文旨在在流程上了解Box2D。

将隻會對Step進行一定的展開。

首先讓我們看下step的聲明

/*

 *@brief 處理一個邏輯幀

 *@param dt 邏輯幀的時間長度

 *@param velocityIterations 速度計算疊代次數，

 *@note 将一個邏輯幀内的速度計算疊代velocityIterations次，疊代的次數越多，碰撞傳導的速度越快

 *@param positionIterations 位移計算疊代次數

 *@note 疊代的次數越多，解決剛體重疊的速度越快

 */



void b2World::Step(float32 dt,int32 velocityIterations,int32 positionIterations);
           

b2World::Step 的流程:

1 如果有新的剛體(Fixture)就執行一次基礎碰撞檢測。

這裡有兩點需要說明:

1.1 Box2D建立了一個AABB碰撞樹，來對物體的碰撞進行基礎檢測。

1.1.1 先說AABB是什麼鬼。

AABB的描述：

1.  AABB是一個旋轉永遠為0的矩形。
2.  每一個剛體都會産生一個AABB。
3. AABB會将剛體包裹，且比剛體略大（至少是略大）。

1.1.2 再說說AABB碰撞樹是什麼鬼

AABB碰撞樹的描述:

1. AABB碰撞樹是二叉平衡樹。
2. 每一個葉子節點都是一個剛體的AABB。
3. 非葉子節點也是一個AABB，但并不是剛體的AABB。
4. 父節點的AABB總是包涵子節點的AABB。
5. 新的葉子節點插入是第一優先級是保持樹的平衡。
6. 第二是插入到而兩個子節點中（由于兩個節點并沒有排序，是以請允許我使用第二個來形容它的位置）。
7. 詳細的樹處理操作在b2DynamicTree.cpp中。

1.2.3 使用AABB碰撞樹進行初步檢測

    使用AABB碰撞樹無疑是為了進行初步篩選，在AABB都無法碰撞的情況下剛體肯定無法碰撞。而且矩形碰撞檢測極其簡單（隻需要檢測矩形的右上角是否在B的左下角的左邊或下邊和與B的右上角是否在A的左下角的左邊或下邊）。而在查詢的時候隻需要使用剛體的AABB在樹中進行周遊（剪掉節點AABB與剛體AABB不碰撞的節點及其子節點）就能初步擷取所有可能産生碰撞的剛體。并組成碰撞元素（ Contact）。

1.2 并不是說沒有新的剛體産生就不進行碰撞處理

    由于老的剛體在上一幀的邏輯處理是就已經進行過初步碰撞檢測。是以這裡是由于新的剛體沒有處理過是以需要進行一次初步碰撞檢測。

2 進行準确碰撞檢測，并對真實碰撞的碰撞元素進行碰撞初始化

    在進行準确碰撞檢測時會排除掉一些不活躍的、重複的、無效的碰撞元素。并根據剛體的類型進行碰撞初始化。詳細碰撞實作在

void b2Collide??(

b2Manifold* manifold,

constb2CircleShape* circleA,constb2Transform& xfA,

constb2CircleShape* circleB,constb2Transform& xfB)
           

    中。當？？為一個剛體類型是，是同類型剛體碰撞否則将形如b2Collide{typeA}And{typeB}。

    不同類型的碰撞是有向的不會出現b2CollideTypeAAndTypeB與b2CollideTypeBAndTypeA兩種碰撞。

    碰撞初始化的内容主要是記錄碰撞體的發力點(point)，以友善後續實體模拟計算。比如說圓與圓碰撞時point并不是交點二十圓心。

    碰撞完畢後還會更具條件觸發開始碰撞或者結束碰撞。

值得注意的是，如果一個剛體被标記為傳感器（sensor）的話，他是不會觸發碰撞初始化處理的。需要注意的是，他隻會出發開始碰撞和結束碰撞，并不會持續發送碰撞信号。如果一個剛體沒有被标記為傳感器，在發送碰撞時她還會回調

virtual void PreSolve(b2Contact* contact,constb2Manifold* oldManifold)
           

    這個方法本意是允許使用者進行自定義個實體模拟。當然了，你也可以拿來作别的事情。

2.1. 傳感器是什麼鬼

傳感器是一種會發送碰撞信号但不進行系統實體碰撞模拟的剛體（你也可以自己模拟碰撞效果）。 傳感器是可以穿過邊界的，他真不會進行任何系統的實體碰撞。是以如果一個傳感器在高速運動。你需要在有需要的時候銷毀它。 當我們要模拟一些技能效果的時候，就可以使用傳感器。當然傳感器并不隻是這一個用途，至于其它用途就要看你的想象力了。

3 在需要的時候進行實體模拟

    Box2D在進行實體模拟（也包括下面的連續實體模拟）時使用到了island減小計算規模。Box2D将大量需要進行模拟的元素分為一個一個的island，然後再進行實體碰撞模拟。

3.1 island是什麼鬼  

island的定義:

1. island 由剛體，碰撞元素，連接配接器（joint）組成。
2. island 與island 之間互不影響（這是island存在的理由，也使得Box2D對island可以生成一個處理一個）。

    大量的剛體，碰撞事件和連接配接器被分為多個island後可以有效的降低實體模拟是消耗的計算資源。原因是碰撞的算法複雜度為O(n2)。這也是為什麼一個複雜機器我們會将其分為幾個小的子產品進行模拟，而不是使用單個動力驅動并将其組為一個整體。

3.2 連接配接器又是什麼鬼

    有的時候我們并不會實作整個實體結構的模拟（比如引擎帶動車輪旋轉），而是選擇在更宏觀的層面進行模拟（引擎運作時輪子就會轉，但實際上兩者之間沒有進行實體聯系），忽略掉這些細節是為了更高速的進行模拟。同樣的，連接配接器也是為了在較為宏觀的層面對一些看似簡單其實很複雜的實體邏輯進行模拟。     舉個栗子，b2PulleyJoint 滑輪連接配接器。     如果我們想要使用原始的實體定力進行模拟我們需要怎麼做？（這還是在理想狀态進行模拟）

1. 将繩子分割為無數個（很多，比如1個機關分割為10000份，這裡有誇張的成分）小線段。
2. 相鄰的兩個小線段受到大小相同方向相反的拉力（繩子是沒有壓力的，當然在滑輪中不需要考慮這一點）。
3. 将滑輪設定為一個可以旋轉，永遠進行靜摩擦，且旋轉阻力為0的圓。
4. 對其進行實體模拟。繩子一端的開始線段受到一個拉力，并不斷的通過下一線段進行傳導力，滑輪可以有效的改變力的方向。

    我相信，同樣可以完成對滑輪的模拟。但這樣做會增加會增加成噸的計算量。     而我們使用滑輪連接配接器進行模拟。

1. 力的發力方向為 發力點與圓的切點 指向 發力點 的方向。
2. 力的受力方向為 受力點 指向 受力點與圓的切點 的方向。
3. 發力與受力大小相同。

    完了，毫無疑問，使用模拟的方式更高效，甚至更真實（理想狀态内的真實）。如果你有興趣還可以給滑輪加個阻尼（b2PulleyJoint是有添加這一屬性的）。

    綜上所訴，使用模拟的方式表現某些實體結構會更高效且真實。然後Box2D将這些模拟進行了一些整合，也就成了現在的連接配接器了。

3.3 實體碰撞模拟的流程

    1.将碰撞元素，剛體，連結器分為一個個island。     2.進行island内部實體碰撞模拟。         2.1 更新整體的線速度，角速度。主要是環境産生的速度影響，如重力，阻尼，浮力。Box2D中對速度是有限制的。這是為了減輕實體沖突事件發生的機率（比如穿越），速度越快發生的可能性就越高。         2.2 多次疊代 連接配接器與碰撞元素 對剛體速度産生的影響。疊代次數越多越真實，因為在一個邏輯針的事件 類由于速度在改變實際上可能已經産生很遠的連鎖反應，需要多次疊代計算才可以将影響傳遞過去。         2.3 更具最新的速度更新位移。這裡也做了速度限制。 2.4 多次疊代 位置修複，防止物體被擠的連到一起了。疊代次數越多修複效果越好。當然是在沒有空間的地方多次疊代會導緻資源浪費。         2.5 出發碰撞元素影響信号。你可以在回調中擷取到碰撞中由速度産生的力（Impulses）。舉個栗子，你可以根據這個值來計算傷害，而不是簡單的使用碰撞給固定傷害。         2.6 标記不活躍剛體。這樣可以減少變化較少的剛體的計算。     3.更行AABB，以及基礎碰撞檢測以友善下一針的處理。    

4 在需要的時候進行連續實體模拟

4.1 為什麼要進行連續實體模拟

    我們知道現實世界的時間是連續的。但是實體引擎中的時間确實粒子化的，無論幾秒中計算多少次都無法模拟連續的時間（更何況由于cpu或gpu算力有限，時間1秒進行的計算次數并不多）。這就産生了一個問題，如果一個物體移動速度夠快，在兩次實體模拟計算中間穿越了另一個物體，引擎是無法發現的（一般情況下）。而連續實體模拟就是為了緩解這一問題。

4.2. 連續碰撞實體模拟的對象

    連續碰撞隻會針對标記為bullet的剛體進行處理。

4.3 連續碰撞實體模拟的流程

    1. 将Bullet 的碰撞元素，連接配接器分為一個個island。直到再也擷取不到island就會直接結束。     1.1 擷取一個bullet。     1.2 擷取bullet最塊發生的碰撞元素。     1.3 擷取該碰撞元素的兩個剛體小範圍内的碰撞元素（不會連續感染，速度太快了還沒傳遞過去？）     2.進行island内部實體碰撞模拟。     2.1 基本流程與實體模拟相同，差別的是這裡隻會更新速度，不會更新位移。不用太擔心（在一些極端情況下連續實體模拟還是會失效）在連續碰撞實體模拟前bullet就已經穿越了。實際上連續模拟是提前模拟了下一針的速度影響。     2.2 傳回第1個步驟，尋找下一個最快碰撞的碰撞元素。   到此Step就說完啦。   期待下一次更新！！！