VisualGMQ的博客

从0开始制作游戏物理引擎（二）

 Game Development  3207  7   

这一章描述了各种几何体表示法，以及BV构建。

几何体表示

首先要确定几何体的表示。某些几何体有多种表示，不同表示法适用于不同的情景。需要根据场景选择。

一般都会使用向量形式而非数学上的方程形式。向量形式计算非常方便，很多算法也是基于向量形式的。

  • 球体：母庸质疑，使用点和半径表示

    1
2
3
4

    struct Sphere {
	Vector3 m_center;
	float m_radius;
}

  • AABB：有两种表示

     1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

    // 使用中心和半长表示
struct AABB {
    Vector3 m_center;
    Vector3 m_half_extent;
};

// 最小最大值表示
struct AABB {
    Vector3 m_min;
    Vector3 m_max;
};

    一般使用第一种表示法。第二种可以用在快速判交里面。

  • OBB：一般使用中心和旋转表示：

     1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

    struct OBB {
  	Vector3 m_center;
    Vector3 m_half_extent;
    std::array<Vector3, 3> m_axises;
};

// 或者直接将half_extent并入m_axises也行：
struct OBB {
    Vector3 m_center;
    std::array<Vector3, 3> m_axises;  // 每个轴不是单位的，含有长度
};

// 或者直接存旋转
struct OBB {
    Vector3 m_center;
    Quaternion m_rotation;
};

    从上往下空间越来越少，但计算使用的时间可能越来越长。一般要有利于计算的是第一或者第二种。

  • 胶囊体：使用中心，半高和半径表示

     1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

    struct Capsule {
  	Vector3 m_center;
    Vector3 m_axis;
    float m_half_height;	// 不是全高，是圆柱体的半高
    float m_radius; // 两端半球的半径
};

// 或者用两端点法表示。但一般不这样，因为不利于旋转计算
struct Capsule {
    Vector3 m_p1, m_p2; // 圆柱体上下底面中心点
    float m_height;
};

    使用圆柱体半高是为了方便某些算法的计算（很多算法和圆柱中轴线相关）。

  • 3D单型（四面体）：

    1
2
3

    struct Tetrahedron {
    std::array<Vector3, 4> m_pts;
};

  • 平面：使用点法式，很多计算都可以方便地用上。一般式基本上没什么用。

    1
2
3
4

    struct Plane {
    Vector3 m_p;
    Vector3 m_normal;
};

  • 线段：使用点向式

    1
2
3
4
5

    struct Segment {
  	Vector3 m_p;
    Vector3 m_axis;
    float m_len;
};

    当然也可以用两个端点表示。但优势不大。点向式可以让m_len < 0来表示直线，同时也可以表示射线（m_len带有方向）

  • 凸多边形：

     1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

    // 直接记录所有点
struct Polygon {
    std::vector<Vector3> m_vertices;
}

// 拓扑方式
struct Edge {
    size_t m_index1, m_index2;	// 记录两端点在Polygon::m_vertices内的下标
};

struct Vertex {
    Vector3 m_position;
    std::vector<size_t> m_edges;  // 记录边在Polygon::m_edges内的下标
}

struct Polygon {
    std::vector<Vertex> m_vertices;
  	std::vector<Edge> m_edges;  
};

// 方便做旋转的方式
struct Polygon {
  	Vector3 m_center;
    std::vector<Vector3> m_dir;	// 中心点到其他点的方向
    std::vector<float> m_lens;  // 中心点到其他点的半径
    Quaternion m_rotation;
};

    拓扑方式方便使用爬山法构造BV。而最后一种方式方便平移和旋转。注意m_dir一般不进行旋转，就是原始位置。计算的时候再进行旋转。这样有利于直接设置旋转（不然会丢失顶点的原始位置，每次直接设置旋转，还得将m_dir反算回原始位置，这样既耗时，也可能产生精度损失。注意这和OBB不一样。OBB的轴的原始轴是确定的（x, y, z轴），所以不需要反算）。

BV构建

BV是Bounding Volume（包围盒）的简写。现在常用的包围盒就是AABB和球包围盒（尽管很多资料上还提到OBB包围盒，N-DOP包围盒和凸包包围盒。但不常用）。

球体包围盒存储上更少，算法上也更快，但是对于长条形物体不够“紧“。而AABB包围盒则相反。

但对于沿着中心旋转的几何体来说，球体包围盒不需要每次重新构建。而AABB需要重新构建。

具体使用需要根据场景选取，或者融合使用。

AABB包围盒构建

基于原点的构造

用于初次构造AABB。最简单的AABB构造法：遍历每个点，找到每个轴上最前/最后的点构造包围盒

爬山法构造

当对顶点很多的凸多面体或三角网格构造时，遍历所有顶点显然麻烦。这时，可以通过其拓扑表示法，利用爬山法进行构造。

爬山法的过程：

  1. 选取任意顶点
  2. 沿着顶点的边找到下一个沿着某轴正向/反向最远的点
  3. 重复步骤2，直到找到最远的点对（正方向和负方向各一个）
  4. 对每个轴做2,3步，找到所有最远点，从而构建AABB

通过拓扑结构可以省去遍历很多点。本质上是一个贪心算法。

旋转AABB的构造

如果已经有一个AABB，可以轻松构造在此基础上相对原点旋转的AABB（AABB本身不一定在原点）。但构造完的AABB不是紧密贴合的。

方法是将这个AABB视为在原点的，并直接对这个AABB进行旋转，而不是对物体旋转后再求AABB：

1
2
3
4
5
6
7

// position是AABB中心
void GetRotatedAABB(Vector3 half_len, Vector3 position, Quaternion rot, Vector3& out_min, Vector3& out_max) {
    Vector3 half_extent = std::abs(rot * half_len);  // 注意，我们计算的是旋转后AABB的大小，所以要加绝对值
    Vector3 world_center = rot * position;
    out_min = world_center - half_extent;
	out_max = world_center + half_extent;
}

（注：《实时碰撞检测算法技术》中是手动将矩阵乘法展开，每个量分开算。这里直接用矩阵乘法可以更高效利用SIMD）

这里origin_min和origin_max最好使用最原始的AABB。如果每次在之前的AABB上旋转，可能由于浮点数误差越转越大。

K-DOP

K-DOP（K-Discrete Oriented Polygon，有向离散多面体)是指用$\frac{k}{2}$对个平面构成的BV。每一对的平面都互相平行，只是位置不同。

存储使用：

1
2
3
4
5
6

template <size_t K>
struct DOP {
  	std::array<float, K> m_mins;
    std::array<float, K> m_maxs;
    std::array<Vector3, K/2> m_normals; // 可选的平面法线方向，一般不用存储
};

其中m_mins是多边形所有点投影到第$i$个平面法线指向轴(m_normals[i/2])中的最短距离（即到平面的距离）。几何体上任意一点一定满足m_mins[i] <= dot(pt[i], UNIT_X) <= m_maxs[i]。

每对平面的法线方向，是因为对于K-DOP来说，当K较少时一般我们有约定俗成的法线方向。比如三维的6-DOP就等价于AABB，法线方向就是三个轴的正向。

对于三维的16-DOP，法线方向除了三轴的正轴，还有 $(\pm x, \pm y, \pm z)$ 8个轴。

对于二维的8-DOP，除了三轴正轴外还有 $(\pm x, \pm y)$ 4轴。

K-DOP的构造

和构造AABB一样，探测轴上最远和最近的点然后存下来就行。

当然也可以用爬山法构造。

K-DOP的相交测试

两个K-DOP相交测试的前提是，K值是一样的。

其实就是AABB的相交测试的扩展。对每一个方向的轴，如果存在min1[i] > max2[i] || max1[i] < min2[i]那么就是不相交的。

球包围盒构建

基于AABB的构造

首先计算物体的AABB。然后通过AABB的中心计算球的半径（找到最远点距离中心的长度）。

或者直接得到AABB对角线的一半作为半径也可以，但这样不太贴合。

Welzl算法构建最小包围球

TODO

工程上的考量

float还是double

大部分物理引擎都可以进行float和double的配置切换。我们也可以照猫画虎：

1
2
3
4
5
6

// config.hpp
#ifdef TOY_PHYSICS_USE_DOUBLE
using real = double;
#else
using real = float;
#endif

以后就用real表示浮点数。

那么数学库也要能够配置：

1
2

using Vector3 = Eigen::Vector3<real>;
// ... 其他alias

算法函数的编写

在开发前期你可能不清楚究竟用哪种几何表示法更好（后面可能会更改表示法）。这个时候函数可以将参数全部摊开，以最有利于计算的方式编写：

1
2
3
4
5

// 不好的写法。因为可能后面AABB要换表示形式，这样这里的算法就得改
bool IsAABBIntersect(const AABB& aabb1, const AABB& aabb2);

// 将参数摊开，这适用于所有表示法。不同的表示法在外面转换成这个参数即可。丑是丑了点但耐用
bool IsAABBIntersect(Vector3 min1, Vector3 max1, Vector3 min2, Vector3 max2);

同时，摊平参数还可以防止在结构体中不小心引入的padding导致SIMD利用寄存器传递失效（见下一小节）。

SIMD优化

我们不自己造数学库，而是使用含有SIMD优化的数学库Eigen。那么就要注意有些写法看上去更慢，但实际是能够利用上SIMD的反而更快，比如判断AABB是否相交，如果逐分量判断可能会破坏SIMD（但你开-O3优化编译器说不定又给你优化成SIMD了。这里只是举个例子提醒要注意这种写法）：

1
2
3
4
5
6
7
8
9

// 正常写法
bool IsAABBIntersect(Vector3 min1, Vector3 max1, Vector3 min2, Vector3 max2) {
    return !(min1.x() > max2.x() || min1.y() > max2.y() || min1.z() > max2.z() ||
             max1.x() < min2.x() || max1.y() < min2.y() || max1.z() < min2.z());
}

// 利用SIMD的写法（这里的条件通过将上面的not条件拆开得到）
return (min1.array() < max2.array()).all() &&
       (min2.array() < max1.array()).all();

这里的小于比较Eigen可能会优化成一条SIMD指令同时比较三个分量。

另外一个考量是，由于存在SIMD优化，整个Vector3/Vector4/Quaterion等可以优化成一份SIMD数据。所以函数传参时比起传引用，不如直接传值让SIMD利用寄存器传递更快。Eigen官方的说法是固定大小且小于16字节的推荐直接传值。

参考

updatedupdated2026-07-172026-07-17