從零開始手敲次世代遊戲引擎（卌）

02-12

終於四十了。

前面兩篇我們使用bullet庫進行了一些簡單的彈性碰撞的物理場景模擬演示。也很粗略的說了一下碰撞檢測的一些相關概念。但是這顯然是不夠的。

為了真正理解計算機是怎麼進行這些物理計算的，特別是在遊戲這麼一個軟實時系統當中，是如何「又快又省」地做到這些的，我覺得非常有必要再造一下輪子。

在前面的文章當中，我們提到過，碰撞檢測的基本數學原理就是高中所學的解析幾何。簡單複習一下：

3維空間的兩個幾何體（或者2維空間的幾何形狀）如果發生碰撞，則說明它們之間有了肢體接觸。用數學的語言來說的話，就是至少存在一個點，滿足這個點既在A上又在B上。或者，如果用集合的概念來說的話，就是

$Acap B e ?$

所謂解析幾何，就是通過建立某種坐標系，將幾何體轉化為代數方程，然後用代數的方法去研究幾何問題。在解析幾何當中，A與B的交點就是代表A與B的方程所組成的方程組的所有解。（如果只考慮邊界與邊界的交點的話）

因此，很顯然的，幾何上A與B是否相交的問題，就可以轉化為在某個坐標系下代表A的方程與代表B的方程是否有共通解，也就是方程組是否有解的問題。

然而，在遊戲當中，僅僅依靠這種方法是不行的。因為：

遊戲當中絕大多數的幾何體都是無法解析表達的。就是說你寫不出它的方程。比如我們一個足球遊戲，要檢測腳與球的碰撞。球還好說，腳就是一個很難用解析的方式（方程）去表示的幾何體；
當代遊戲當中往往有成百上千個幾何體，各種形狀。如果它們均可動，那麼任何兩個幾何體之間都可能會發生碰撞。為了檢測這樣的碰撞，我們不得不檢查所有可能的組合。這是一個很大的量；
方程組是否有解的問題本身就是一個複雜的問題。就算有判定公式的些特殊情況，判定公式的計算，對於遊戲引擎那可憐的ms計算的周期來講，也往往是十分昂貴的；
遊戲當中往往需要知道的只是碰上了還是沒碰上，並不需要知道到底是A的什麼地方碰到了B的什麼地方，也就是說不需要精確解（定量判斷），只需要定性就好。

所以，一般來說遊戲當中並不會直接對場景物體求交，而是通過給場景物體包裹一個基本幾何體（被稱為是碰撞盒，也叫包圍盒，等等），將複雜的場景物體求交近似為簡單幾何體求交來進行的，也就是我們前一篇所提到過的那些基本形狀。

這些基本形狀十分有用。不僅僅在物理引擎當中會用到它們，它們對於場景的快速建模（關卡設計）、場景渲染的優化、調試等都非常有意義。所以我們有必要在引擎當中實現它們。

實現基本幾何體

讓我們在Framework目錄下面新建一個子目錄，取名為Geometries。然後在下面新建一個Geometry類，定義基本的幾何體共通的屬性：

#pragma once#include "aabb.hpp"#include "portable.hpp"namespace My { ENUM(GeometryType) { kBox, kSphere, kCylinder, kCone, kPlane, kCapsule, kTriangle }; class Geometry { public: Geometry(GeometryType geometry_type) : m_kGeometryType(geometry_type) {}; Geometry() = delete; virtual ~Geometry() = default; // GetAabb returns the axis aligned bounding box in the coordinate frame of the given transform trans. virtual void GetAabb(const Matrix4X4f& trans, Vector3f& aabbMin, Vector3f& aabbMax) const = 0; virtual void GetBoundingSphere(Vector3f& center, float& radius) const; // GetAngularMotionDisc returns the maximum radius needed for Conservative Advancement to handle // time-of-impact with rotations. virtual float GetAngularMotionDisc() const; // CalculateTemporalAabb calculates the enclosing aabb for the moving object over interval [0..timeStep) // result is conservative void CalculateTemporalAabb(const Matrix4X4f& curTrans, const Vector3f& linvel, const Vector3f& angvel, float timeStep, Vector3f& temporalAabbMin, Vector3f& temporalAabbMax) const; GeometryType GetGeometryType() const { return m_kGeometryType; }; protected: GeometryType m_kGeometryType; float m_fMargin; };}

我們首先定義了幾何體形狀類型，用於在運行時判斷實例所代表的幾何體形狀。然後我們定義了我們希望所有幾何體都支持的幾個方法：

獲取球形包圍盒（GetBoundingSphere）
獲取與坐標軸平行的長方體（立方體）包圍盒（GetAabb）
獲取物體在以當前線速度和角速度保持運動一小段時間（time Step）之後的AABB包圍盒

球形包圍盒

球形包圍盒直接的碰撞檢測比較單純，如下圖。當兩球心距離 $d>r_{1}+r_{2}$ 的時候，碰撞未發生。反之，碰撞發生。

但是，雖然公式很簡單，計算量卻不是最小的。這是因為空間任意兩點之間的距離為原點到這兩點的向量的差、所得到的向量的長度。向量的長度計算涉及到乘方與開方，是比較慢的計算。

圖片來自網路：http://jccc-mpg.wikidot.com/intersections-and-collision-detection

AABB包圍盒

AABB包圍盒是長方體包圍盒的一個特例，它的長寬高平行於坐標軸。也就是說，沒有旋轉。AABB包圍盒不見得是（或者說很多時候不是）最小的長方體包圍盒。但是因為它沒有旋轉，所以有以下這樣非常好的性質：

當且僅當兩個AABB包圍盒在各個坐標軸上所對應的（投影的）區間都發生重疊的時候，兩個AABB包圍盒才相交。

這就是說，對於AABB包圍盒的碰撞檢測，我們可以檢測其在每個坐標軸上的投影。只要有一個坐標軸上的投影不重疊，那麼兩個AABB包圍盒就不發生碰撞。

雖然對於最壞的情況（發生了碰撞），我們需要在x,y,z三個軸上各自進行一次區間是否重合的檢測，但是每次檢測實際上只是分別比較兩個投影區間的最小值/最大值，這對於CPU/GPU來說是非常簡單的操作，計算量很低。

圖片來自網路：http://myselph.de/gamePhysics/collisionDetection.html

好了。有了這個基本的幾何體類，我們就可以從它派生生成各種具體的幾何形狀的類了。比如球體：

#pragma once#include "Geometry.hpp"namespace My { class Sphere : public Geometry { public: Sphere() : Geometry(GeometryType::kSphere) {}; virtual void GetAabb(const Matrix4X4f& trans, Vector3f& aabbMin, Vector3f& aabbMax) const; float GetRadius() const { return m_fRadius; }; protected: float m_fRadius; };}

長方體：

#pragma once#include "Geometry.hpp"namespace My { class Box : public Geometry { public: Box() : Geometry(GeometryType::kBox) {}; Box(Vector3f dimension) : Geometry(GeometryType::kBox), m_vDimension(dimension) {}; virtual void GetAabb(const Matrix4X4f& trans, Vector3f& aabbMin, Vector3f& aabbMax) const; Vector3f GetDimension() const { return m_vDimension; }; Vector3f GetDimensionWithMargin() const { return m_vDimension + m_fMargin; }; protected: Vector3f m_vDimension; };}

等等。我們可以這樣不斷添加我們所需的幾何體來豐富我們引擎的功能。

下一篇我們將嘗試將這些幾何體可視化，並且實現一個我們自己的碰撞檢測模塊。

關於Windows版的連續集成

之前我們使用Circle CI實現了Linux/MacOS/Android三種平台的連續集成。但是因為Circle CI不支持Windows的連續集成，所以這個問題一直放置到現在。

好在另外有一個名為AppVeyor的雲服務商為所有GitHub上的開源項目提供了免費的Windows的連續集成環境，在本篇的代碼當中我們利用了這個環境。

使用方法非常簡單，在AppVeyor網站完成項目註冊之後，同樣是通過一個YAML文件來描述所需要做的工作。對於我們這個項目，這個文件如下：

version: 0.0.{build}image: Visual Studio 2017build_script:- cmd: >- build_crossguid build_opengex build_zlib build_bullet buildtest_script:- cmd: cmake --build build --target RUN_TESTS

只不過目前這個文件好像只能放在項目根目錄下，與Circle CI的目錄結構稍微有些不一樣。

關於編輯器

如我在系列開篇所述，可能是由於歷史原因，我更喜歡使用命令行。相應的，作為命令行當中的優秀文本編輯器-VIM，是我用來寫本系列代碼的主要工具。

但是這並不是說我推薦使用VIM，或者反對其它的編輯器。其實編輯器的選擇只有一個標準，那就是自己用得舒服即可。

其實最近我也在用VS Code，很好用。強烈推薦。