« February 2020 | Main

March 12, 2020

矩阵 decompose 的一点优化

我们的游戏引擎中,有个重要的功能是将一个矩阵分解成 S 缩放,R 旋转,T 位移三个分量。这里 T 直接取矩阵的第四行即可,代价比较高的是 S 和 R 的分解,其中 R 又取决于 S 的提取。

但是,游戏中大量的矩阵中是不包含缩放的,即 S 分量大多是 (1,1,1) 。一旦不用缩放,又可以简化 R 提取的操作。所以我打算对传统算法做一点优化。在提取 S 的时候多加一次判断,看值是否接近 1 。

计算 S 的方法是将矩阵的前三行当作三个 vector 3 分别取 length 。length 其实是取 dot 然后计算 sqrt。由于大多数情况预测 dot 值很可能为 1 ,那么当 dot 接近 1 的时候,就不必再开方了。

我很好奇判断一个数字是否接近 1 有没有什么技巧可以提高性能,所以我写了三个版本测试。

static inline int
equal_one(float f) {
  union {
    float f;
    uint32_t n;
  } u;
  u.f = f;
  return ((u.n + 0x1f) & ~0x3f) == 0x3f800000;  // float 1
}

#define EPSILON 0.000001f 

static inline int
equal_one_float1(float f) {
  float  v = f - 1.0f;
  return fabs(v) < EPSILON;
}

static inline int
equal_one_float2(float f) {
  float  v = f - 1.0f;
  return -EPSILON < v && v < EPSILON;
}

后两个版本很常规,区别在于要不要调用 fabs 取绝对值。第一个版本则是针对 float 的 ieee 754 的二进制表示做的,是一个整数运算的版本。

我在 PC 上做了简单的性能测试,第一版和第二版性能几乎一致,而第三版要慢 3 倍。我认为原因在于第三版多了一次比较操作(有分支情况)。而针对 ieee 754 的 float 做 fabs 本质上仅仅是将高位置为 0 ,甚至比整数版 abs 还要快。现代编译器一般都会做此优化。

暂时没有在 arm CPU 上测试。不过如果不开 NEON 的话,arm 的浮点运算将全部导致函数调用,肯定不如第一个版本好。

第一版的缺点是扩展性不足,一旦从 float 换成 double 就要重新编写。

March 11, 2020

不变量及运算优化

去年的时候,我们对正在开发中的游戏引擎做了一点 profile 工作。后来发现,在场景中对象很多的时候,有一处运算占据了 10% 以上的 cpu 时间。当时我的判断是,这处地方值得优化,但并不是工作重点,所以就搁置了。

问题的具体描述是这样的:

我们的引擎每帧会将场景中的对象依次提交到一个渲染队列中,每个可渲染物件,除了自身的网格、材质外,还有它自身的包围盒(通常是 AABB),以及它在世界空间中的矩阵。

我们有一套资源系统,场景中的对象会引用资源系统中的对象,这些资源对象是一个不变量,会被多个场景对象所引用。而资源对象又可以是一个树结构,比如一个模型就可以由若干子模型所构成。提交到最终渲染队列中的是不可再拆分的子模型的信息。

也就是说,在场景管理的层次,对象的数量是远少于提交到渲染队列中的对象数量的。这就是为什么我们渲染每次重建渲染队列,而没有将每帧提交给渲染队列的列表持久化为一个链表并作增减维护的原因。

问题出在提交给渲染队列的每个物件的包围盒上。

这个包围盒信息用于渲染的 culling ,最简单的 culling 是用摄像机的视锥体和每个包围盒做相交判断,剔除掉不在视野中的对象,它们就不必渲染。以后还可以扩展为更复杂的 culling 管理模块。(比如,Umbra 就是这样一个相当著名的 culling 中间件。)

我们有考虑过用 GPU 做 culling 的方案,但限于开发人手的精力,暂时还是聚焦在 CPU 方案上。所以,必不可少的是在提交每个物件的包围盒到渲染队列中时,需要根据物件原本的包围盒和世界空间的矩阵做一次“简单的”运算,变换为在世界空间的包围盒。

这个运算虽然简单,但最后的 profile 结果显示,它并不像预想的那么廉价。这可能是因为大部分渲染工作都已经交给了 GPU 完成,所以简单的 CPU 运算,在量大的情况下,也凸显出时间占比来。

考虑到复杂场景中虽然物件众多,但帧间保持不变的静态物件其实占大多数,所以大量的运算其实是重复进行的,一定有优化的余地。

一个直接的想法就是把整个渲染队列保持为一个持久化队列,每帧根据提交去增减这个队列。但因为可渲染物件其实是被大量复用的,这就要求不断地复制这些原本在资源模块中简单引用的对象(子模型)的数据。我判断这样做是得不偿失的。

我更希望,对相同数据做重复运算,这一点的优化可以跟透明,而不需要对已有系统做大量的改造。

仔细考量,我们发现,针对每个渲染物件做的操作是将世界空间的矩阵、子模型相对于资源中模型的根节点的变换矩阵、以及子模型的 AABB 一起做一个运算。如果这三者(两个矩阵和一个 AABB)完全相同时,结果也一致。

但是,输入数据实在的太大了,有 16+16+8=40 个 float 。如果用 160 字节做 key 建一个 cache ,未必能有什么改善。

思考到这里,我突然想到,我们的数学库其实老早就将 matrix/vector 这些东西视为不变量了。每个矩阵在我们的系统中都是一个唯一的 id ,代表着一个不可改变的值对象。所以我们根本不需要用 matrix 的实际值做 cache key ,而用 id 即可。这样,cache 的 key 被大大缩减,方案其实是可行的。

另外,当一个资源中的模型进入渲染队列时,往往它所包含的所有子模型都会被渲染。所以,我们只需要建一个 cache ,用世界空间的矩阵做 key 就完全够用了。注:如果有两个场景物件在世界空间的矩阵的值完全相同,它们也会是两个不同的 id (因为是经过不同的运算路径计算出来的);而帧间不变的静态物件,会被场景管理模块所优化,必须重复计算世界空间中的矩阵,从而让其矩阵 id 保持不变。

而 cache 的 value 域,我们可以顺序存放对应的所有子模型的变换矩阵、AABB、以及上一次计算出来的世界空间的 AABB 。一旦可以匹配的上,就可以直接使用上一帧 cache 的运算结果。