从零开始手敲次世代游戏引擎(卌)

终于四十了。
前面两篇我们使用bullet库进行了一些简单的弹性碰撞的物理场景仿真演示。也很粗略的说了一下碰撞检测的一些相关概念。但是这显然是不够的。
为了真正理解计算机是怎么进行这些物理计算的,特别是在游戏这么一个软实时系统当中,是如何“又快又省”地做到这些的,我觉得非常有必要再造一下轮子。
在前面的文章当中,我们提到过,碰撞检测的基本数学原理就是高中所学的解析几何。简单复习一下:
3维空间的两个几何体(或者2维空间的几何形状)如果发生碰撞,则说明它们之间有了肢体接触。用数学的语言来说的话,就是至少存在一个点,满足这个点既在A上又在B上。或者,如果用集合的概念来说的话,就是
Acap Bne Ø
所谓解析几何,就是通过建立某种坐标系,将几何体转化为代数方程,然后用代数的方法去研究几何问题。在解析几何当中,A与B的交点就是代表A与B的方程所组成的方程组的所有解。(如果只考虑边界与边界的交点的话)
因此,很显然的,几何上A与B是否相交的问题,就可以转化为在某个坐标系下代表A的方程与代表B的方程是否有共通解,也就是方程组是否有解的问题。
然而,在游戏当中,仅仅依靠这种方法是不行的。因为:
  1. 游戏当中绝大多数的几何体都是无法解析表达的。就是说你写不出它的方程。比如我们一个足球游戏,要检测脚与球的碰撞。球还好说,脚就是一个很难用解析的方式(方程)去表示的几何体;
  2. 当代游戏当中往往有成百上千个几何体,各种形状。如果它们均可动,那么任何两个几何体之间都可能会发生碰撞。为了检测这样的碰撞,我们不得不检查所有可能的组合。这是一个很大的量;
  3. 方程组是否有解的问题本身就是一个复杂的问题。就算有判定公式的些特殊情况,判定公式的计算,对于游戏引擎那可怜的ms计算的周期来讲,也往往是十分昂贵的;
  4. 游戏当中往往需要知道的只是碰上了还是没碰上,并不需要知道到底是A的什么地方碰到了B的什么地方,也就是说不需要精确解(定量判断),只需要定性就好。
所以,一般来说游戏当中并不会直接对场景物体求交,而是通过给场景物体包裹一个基本几何体(被称为是碰撞盒,也叫包围盒,等等),将复杂的场景物体求交近似为简单几何体求交来进行的,也就是我们前一篇所提到过的那些基本形状。
这些基本形状十分有用。不仅仅在物理引擎当中会用到它们,它们对于场景的快速建模(关卡设计)、场景渲染的优化、调试等都非常有意义。所以我们有必要在引擎当中实现它们。
实现基本几何体
让我们在Framework目录下面新建一个子目录,取名为Geometries。然后在下面新建一个Geometry类,定义基本的几何体共通的属性:
我们首先定义了几何体形状类型,用于在运行时判断实例所代表的几何体形状。然后我们定义了我们希望所有几何体都支持的几个方法:
  1. 获取球形包围盒(GetBoundingSphere)
  2. 获取与坐标轴平行的长方体(立方体)包围盒(GetAabb)
  3. 获取物体在以当前线速度和角速度保持运动一小段时间(time Step)之后的AABB包围盒
球形包围盒
球形包围盒直接的碰撞检测比较单纯,如下图。当两球心距离 d>r_{1}+r_{2} 的时候,碰撞未发生。反之,碰撞发生。
但是,虽然公式很简单,计算量却不是最小的。这是因为空间任意两点之间的距离为原点到这两点的向量的差、所得到的向量的长度。向量的长度计算涉及到乘方与开方,是比较慢的计算。
图片来自网络:http://jccc-mpg.wikidot.com/intersections-and-collision-detection
AABB包围盒
AABB包围盒是长方体包围盒的一个特例,它的长宽高平行于坐标轴。也就是说,没有旋转。AABB包围盒不见得是(或者说很多时候不是)最小的长方体包围盒。但是因为它没有旋转,所以有以下这样非常好的性质:
  1. 当且仅当两个AABB包围盒在各个坐标轴上所对应的(投影的)区间都发生重叠的时候,两个AABB包围盒才相交。
这就是说,对于AABB包围盒的碰撞检测,我们可以检测其在每个坐标轴上的投影。只要有一个坐标轴上的投影不重叠,那么两个AABB包围盒就不发生碰撞。
虽然对于最坏的情况(发生了碰撞),我们需要在x,y,z三个轴上各自进行一次区间是否重合的检测,但是每次检测实际上只是分别比较两个投影区间的最小值/最大值,这对于CPU/GPU来说是非常简单的操作,计算量很低。
图片来自网络:http://myselph.de/gamePhysics/collisionDetection.html
好了。有了这个基本的几何体类,我们就可以从它派生生成各种具体的几何形状的类了。比如球体:
长方体:
等等。我们可以这样不断添加我们所需的几何体来丰富我们引擎的功能。
下一篇我们将尝试将这些几何体可视化,并且实现一个我们自己的碰撞检测模块。
关于Windows版的连续集成
之前我们使用Circle CI实现了Linux/MacOS/Android三种平台的连续集成。但是因为Circle CI不支持Windows的连续集成,所以这个问题一直放置到现在。
好在另外有一个名为AppVeyor的云服务商为所有GitHub上的开源项目提供了免费的Windows的连续集成环境,在本篇的代码当中我们利用了这个环境。
使用方法非常简单,在AppVeyor网站完成项目注册之后,同样是通过一个YAML文件来描述所需要做的工作。对于我们这个项目,这个文件如下:
只不过目前这个文件好像只能放在项目根目录下,与Circle CI的目录结构稍微有些不一样。
关于编辑器
如我在系列开篇所述,可能是由于历史原因,我更喜欢使用命令行。相应的,作为命令行当中的优秀文本编辑器-VIM,是我用来写本系列代码的主要工具。
但是这并不是说我推荐使用VIM,或者反对其它的编辑器。其实编辑器的选择只有一个标准,那就是自己用得舒服即可。
其实最近我也在用VS Code,很好用。强烈推荐。

发表评论

Fill in your details below or click an icon to log in:

WordPress.com 徽标

您正在使用您的 WordPress.com 账号评论。 登出 /  更改 )

Google photo

您正在使用您的 Google 账号评论。 登出 /  更改 )

Twitter picture

您正在使用您的 Twitter 账号评论。 登出 /  更改 )

Facebook photo

您正在使用您的 Facebook 账号评论。 登出 /  更改 )

Connecting to %s

%d 博主赞过: