从零开始手敲次世代游戏引擎(二十三)

接上一篇,我们继续进行数学库方面的工作。(题图为ispc自带的延迟渲染的example,与本文没有直接关系) 本文所对应的代码在article_23分支当中。 在游戏当中,最为广泛使用的数学是线性代数。线性代数里面有两个最主要的概念,向量和矩阵。 首先我们来看看向量的定义,以一个2维向量为例(下面的定义均在Framework/GeomMath/geommath.hpp当中):

 template <typename T>     struct Vector2Type     {         union {             T data[2];             struct { T x, y; };             struct { T r, g; };             struct { T u, v; };             swizzle<Vector2Type<T>, 0, 1> xy;             swizzle<Vector2Type<T>, 1, 0> yx;         };         Vector2Type<T>() {};         Vector2Type<T>(const T& _v) : x(_v), y(_v) {};         Vector2Type<T>(const T& _x, const T& _y) : x(_x), y(_y) {};         operator float*() { return data; };         operator const float*() const { return static_cast<const float*>(data); };     };

这里我们使用了C++模板来泛化实际的数据类型,这样我们可以根据需要,使用单精度浮点,或者双精度浮点,甚至是半精度(half float)浮点等。当然我们也可以使用其它类型,如整型,定点浮点类型等。 我们使用了联合(union),来提供一种类似HLSL/GLSL等渲染语言提供的swizzle功能。为此我们还写了一个swizzle模板,可以较为方便地实现swizzle。这个swizzle模板是这么定义的(参考引用1):

 template< typename T, int ... Indexes>     class swizzle {         float v[sizeof...(Indexes)];     public:         T& operator=(const T& rhs)         {             int indexes[] = { Indexes... };             for (int i = 0; i < sizeof...(Indexes); i++) {                 v[indexes[i]] = rhs[i];             }             return *(T*)this;         }         operator T () const         {             return T( v[Indexes]... );         }     };

这个swizzle模板首先是一个不定参的可变模板。这是C++ 11之后新增加的功能,我们在之前也用到过一次。 另外一个需要注意到的是虽然class swizzle有一个成员变量 float v[],但是因为我们在Vector的定义当中是把swizzle的实例和data进行union的,因此实际上在Vector当中的任意一个swizzle实例,并不会增加额外的内存需求。 但是注意由于不同的swizzle实例我们传给它的模板参数是不一样的,所以下面的参数包的展开也是每个实例都不同的:

     T& operator=(const T& rhs)         {             int indexes[] = { Indexes... };         operator T () const         {             return T( v[Indexes]... );

所以,这部分应该是有额外的开销的。具体是怎么样的开销,我们可以通过编译输出llvm中间文件(.ll)来查看。这部分这里先不展开,放在今后的性能分析与优化的章节进行具体讨论。 回到Vector定义的代码。在构造函数之下,我们提供了两行运算符的重载:

     operator float*() { return data; };         operator const float*() const { return static_cast<const float*>(data); };

这是因为我们将会调用ispc代码进行线性代数计算,但是ispc并不支持C++ (虽然它支持部分C++的特性,比如可以在代码任何位置声明变量)。所以,我们需要将我们的向量类转换为浮点数组,来传给ispc。 其实即使不使用ispc,我们仍然需要这些类型转换。这是因为GPU也不懂得C++的类。我们需要将封装在类当中的数据作为线性的buffer传递给GPU。这个在之前图形模块的例程当中已经体验过了。 注意我们之所以定义了了两个版本,是因为我们需要顾及“左值”和“右值”这两种情况。所谓“左值”就是当变量出现在等号的左边,也就是作为被写入的对象;而“右值”则自然是等号的右边,作为被参照(读取)的对象。(更为准确的说,左值就是有名称的变量,是指阁纳数值的”容器”;而右值是被阁纳的数值本身,比如立即数,cpu寄存器当中的计算结果,一个尚未被分配名称的地址空间,等等。) 第一行是”左值“的定义。我们返回的是指向我们data内存区域的指针,之后我们可以利用这个指针修改data内保持的值; 而第二行是”右值“的定义,返回的是指向浮点常数(const float)的指针,这个指针只能用来读取data当中的变量,不能进行”写“操作。 虽然”左值“方式的定义,也可以用在”右值“ (float *也可以放在等式右边使用),但是这样做有一下一些缺点:

  1. 编译器会认为以”左值“方式定义的变量,其内容会在执行当中改变。因此编译器会在编译出来的代码当中,尝试回写变量的值,或者做一些cache的同步操作(请回想我们前面讨论内存管理的时候提到的cache对于执行速度的影响),这会显著影响代码的执行速度;
  2. 为了防止出错,以及让编译器最大限度地优化代码,对于在代码执行过程当中不会被改变的参数,我们要尽可能地将其声明为const类型。然而,如果我们将一个对象实例声明为const类型,那么这个对象实例的所有非const类型的方法都将不可以调用。所以我们必须另外准备一个const类型的方法。而const类型的方法只可以返回const类型的指针。

照此类推,我们定义了3维和4维的向量,不赘述。 接下来我们就可以定义向量之间的运算了。以向量加为例,我们首先在C++ (geommath.hpp)当中定义如下方法和运算符重载:

 template <template<typename> class TT, typename T>     void VectorAdd(TT<T>& result, const TT<T>& vec1, const TT<T>& vec2)     {         ispc::AddByElement(vec1, vec2, result, countof(result.data));     }     template <template<typename> class TT, typename T>     TT<T> operator+(const TT<T>& vec1, const TT<T>& vec2)     {         TT<T> result;         VectorAdd(result, vec1, vec2);         return result;     }

代码比较简单,就是直接调用了ispc所写的计算函数。注意我们是如何定义函数的形式参数的:所有”右值“参数都被声明成了const引用类型,而”左值“参数都被声明成了”左值“引用类型。 模板的使用有一点点复杂,用到了模板类型的模板参数。

template <template<typename> class TT, typename T>

本来,我们可以将向量的维度作为另外一个模板变量,从而定义一个通用的向量模板,看起来大概是下面这个样子:

template <typename T, int D> class Vector {    T data[D];    ...

那么,我们的运算符也可以简单地定义为下面这个样子:

 template <typename T, int D>     void VectorAdd(Vector<T, D>& result, const Vector<T, D>& vec1, const Vector<T, D>& vec2)

甚至进一步简化为下面这个样子:

 template <typename T>     void VectorAdd(T& result, const T& vec1, const T& vec2)

但是,两个方面的问题导致我们不能这么做:

  1. 因为我们导入了swizzling。对于不同维度的Vector,需要支持的swizzling的个数是不同的。这很难用一个模板去实现;(如果有实现的方法,请一定告诉我)
  2. 上面最后一种形式太泛。不仅仅是我们定义的Vector类型,我们后面定义的Matrix类型也可以匹配上。这会增加我们代码出错的几率。我们在使用模板所提供的泛化的同时,也希望尽可能限制这种意想之外的匹配;

所以我采用了下面这种定义方式:

 template <template<typename> class TT, typename T>     void VectorAdd(TT<T>& result, const TT<T>& vec1, const TT<T>& vec2)

这种方式使得只有带一个模板参数的模板可以匹配这个模板函数。我们的Vector2, Vector3, Vector4都符合这个特征,而Matrix(参见后文)就不符合这个特征。当然这仍然可能导致意想之外的匹配,但是发生的可能性已经大大降低了。 蕴含在部分代码的另外一个“黑魔法”就是countof。它被用来将向量的维度传递给ispc的代码:

 template <template<typename> class TT, typename T>     void VectorAdd(TT<T>& result, const TT<T>& vec1, const TT<T>& vec2)     {         ispc::AddByElement(vec1, vec2, result, countof(result.data));     }

这个countof在VC系列里面是自带的,但是为了可移植性,也为了学习,我们自己实现了一下。它的定义如下:

 template<typename T, size_t SizeOfArray>         constexpr size_t countof(T (&array)[SizeOfArray]) { return SizeOfArray; }

这里面同样有一点点黑魔法。我们定义了一个constexpr类型的函数。这也是C++ 11所新增的功能。这种类型的函数是在编译的时候进行计算的,计算的结果作为一个常数被带入到调用这个函数的位置并进行编译。比如sizeof()这个函数,它并不是在程序运行的时候进行的。 另外一点技巧就是countof()的参数,我们通过定义一个数组的引用来获取数组的尺寸(维度)。虽然在运行的时候我们无法直接得知一个数组的尺寸,但是在编译的时候,这个尺寸编译器是知道的。通过如上的定义方式,这个尺寸会被带入SizeOfArray这个参数当中,并且因为return SizeOfArray这个函数体,这个函数最终的结果就是实参数组的维度。 我们当然可以把这个维度作为一个变量保存在我们的Vector类当中。但是我这里想要的是保持每种类型的Vector它在内存上的尺寸与其包含的实际数据的尺寸相同。也就是说,Vector2f在内存上就应该只有2个float的大小;而Vector3f就是3个float的大小。这对于我们后面控制内存分配以及对齐方式等非常重要,所以对于这些基础数据类型定义我们要避免使用额外的类成员变量。 最后是关于运算的函数形式和运算符形式:

 // (函数形式)     void VectorAdd(TT<T>& result, const TT<T>& vec1, const TT<T>& vec2)     // (运算符形式)     TT<T> operator+(const TT<T>& vec1, const TT<T>& vec2)

我们可以只定义其中一种。出于以下考虑我定义了两种:

  1. 函数形式不需要在函数内分配内存(无论是堆还是栈),也不存在额外的拷贝操作,效率高;但是函数形式不容易实现多个计算操作在一行上面的书写;
  2. 如果将result作为函数的返回值进行返回,那么会多一次拷贝操作。如果我们在函数内分配内存并将其地址(指针)作为返回值返回,那么如果是在栈上分配的内存,则当函数结束的时候栈指针回退,我们返回的指针实际上已经是无效的(虽然我们如果立即使用,那么还是可以读到正确的值);如果我们是在堆上分配,那么我们需要在函数外释放这个内存,这个违反了谁分配谁释放的一般设计原则,容易引出内存方面的问题;
  3. 运算符形式最大的好处就是方便书写,直观。对于一些性能不是很敏感的地方我们可能更希望使用这个。

然后我们再来看一下ispc书写的部分:

export void AddByElement(uniform const float a[], uniform const float b[], uniform float result[], uniform const int count) {     foreach(index = 0 ... count)     {         result[index] = a[index] + b[index];     }     return; }

书写ispc的时候,我们遵循一个基本的原则:尽量通用化。如我们前面所述,在ispc层面我们看不到Vector和Matrix的封装,所有的都只是基本数据类型的序列。两个向量的相加就是两个向量对应的成员的相加,对于矩阵也是一样。所以,我们用ispc所写的代码,就是完成两个基本数据类型序列的相加,而不关心它到底是什么。 相对于shading语言,ispc的一个好处就是可以直接被C/C++代码调用,而不是通过一堆API将参数上传到某个地方,然后开始计算,计算完了再将结果取回来。(当然,其实这个过程是存在的,只是被ispc所隐蔽掉了。当ispc跑在CPU的向量计算单元上的时候,一部分参数需要通过CPU向量扩展命令装载到CPU的向量计算单元,在计算完了的时候再取回来(pack / unpack);而当ispc跑在GPU上的时候,需要将相关的参数展开到GPU所内看到的内存空间,再计算完成之后再取回来) 在分布式计算领域,有一个很著名的Map – Reduce模型,其实就是和这个差不多的意思。 也是因为如此,并不是所有以ispc所写的函数都能被C/C++调用。只有被”export”了的函数,才可以被C/C++调用。不仅仅如此,由于C/C++是以串行逻辑执行的,所以被”export“的函数只能有uniform类型的形参。如我们在上一篇所述,uniform类型的形参被同一批并行计算的所有”线程“(注意这里的线程与串行计算世界的线程不同,是真正可以在同一个CPU内核上同时执行的计算)所共享。而未被声明为uniform类型的变量,是每一个线程都有一个单独的拷贝,互不干涉的。 所以,实际上被export的函数起到了一个Map – Reduce的作用,或者说分发器 – 收集器的作用。注意我们下面的

 foreach(index = 0 ... count)     {         result[index] = a[index] + b[index];     }

这个foreach实际上就是一个分发器。C/C++/Java当中的for / foreach是逐个执行的,而这里的foreach实际上是生成count个“线程”(还记得这个count的由来么?它是我们在geommath.hpp当中用countof()获取的向量/矩阵的维度),然后让它们同时执行foreach循环体内的操作,也就是:

     result[index] = a[index] + b[index];

这个语句在每个“线程”当中只会被执行一次(并不会循环),每个“线程”负责一个index的执行。注意这里的index并不是uniform类型的,所以每个线程的index的值并不一样。假设count为4,那么这个语句的作用就是生成4个线程,1号线程的(index = 0),2号线程的(index = 1),照此类推。在执行一次循环的时间内,4个index的计算都会进行,就相当于通常执行4次循环的结果。 而最后的结果收集是通过result这个uniform变量进行的。因为是uniform变量,这个变量在内存上只有一个,每个线程写的是第index个数据。在这个例子当中,因为每个线程的index不同,写的地方也不同,所以不需要特别的控制(同时写就好)。而在另外一些计算当中,比如计算向量的点积:

extern void MulByElement(uniform const float a[], uniform const float b[], uniform float result[], uniform const int count); export void DotProduct(uniform const float a[], uniform const float b[], uniform float* uniform result, uniform const int count) {     *result = 0;     uniform float * uniform r = uniform new uniform float [count];     MulByElement(a, b, r, count);     foreach_active(i) {         *result += r[i];     }     delete[] r; }

因为我们最后的结果只是一个浮点数,我们需要将并列计算的向量的各个分量的积进行累加,这里就不能再并列了。因此我们使用了 foreach_active(i)这么一个收集器,将并列计算的结果进行串行化累计。因为是串行执行,这个loop会执行向量的维度次,而不是只执行1次。 好了,向量相关的基本就是这样。其它的运算也是上面所说的演绎。接下来我们看一下矩阵的定义:

 template <typename T, int ROWS, int COLS>     struct Matrix     {         union {             T data[ROWS][COLS];         };         auto operator[](int row_index) {             return data[row_index];         }         const auto  operator[](int row_index) const {             return data[row_index];         }         operator float*() { return &data[0][0]; };         operator const float*() const { return static_cast<const float*>(&data[0][0]); };     };

相对于向量的定义,我们的data从一维数组变成了二维数组,并且增加了ROWS和COLS这两个模板参数,用来定义矩阵的维度。我们当然也可以把data仍然定义为一维数组,就如同DirectXMath里面那样。但是如我上面所述,向量和矩阵在概念上就有很多不同,为了在代码上彻底区分这两个概念,避免我们定义的一些模板可以同时套用到这两个类型上,我们人为地进行了一些不兼容的定义。 比如,基于这样的定义,我们的矩阵加法就需要如下定义:

 template <typename T, int ROWS, int COLS>     void MatrixAdd(Matrix<T, ROWS, COLS>& result, const Matrix<T, ROWS, COLS>& matrix1, const Matrix<T, ROWS, COLS>& matrix2)     {         ispc::AddByElement(matrix1, matrix2, result, countof(result.data));     }     template <typename T, int ROWS, int COLS>     Matrix<T, ROWS, COLS> operator+(const Matrix<T, ROWS, COLS>& matrix1, const Matrix<T, ROWS, COLS>& matrix2)     {         Matrix<T, ROWS, COLS> result;         MatrixAdd(result, matrix1, matrix2);         return result;     }

可以看到,实质进行的计算是一样的,使用的ispc代码都是一样的,都是ispc::AddByElement()。但是在模板形参方面我们做了明显的区分,使得两者不能混用。 事实上,我们回过头来看计算机编程语言的发展:从二进制汇编到C/C++,到objectC/C#/Java,一直都有两种趋势同时在进行:

  1. 语言自身的泛化,自动化,降低编程的难度,提高可移植性
  2. 强类型,强规则,降低出错的可能性,提高程序的效率

我们这里也是同样的思路。在使用模板进行泛化,使得我们可以轻松支持不同数据类型、不同维度的向量和矩阵的同时,通过模板特化(template specialization),实现尽可能强的类型检查。 好了,关于数学库的第一次介绍就到这里。最后我们为它加上一个测试用例。因为数学库是一个核心组件,它的正确就变得尤为重要。CMake缺省集成了CTest这个广泛使用的自动化测试框架,我们来初步看看它的用法。 首先在Framework/GeomMath下面新建test文件夹,书写test.cpp如下(篇幅问题,测试内容有删减,具体的请直接看代码):

#include <iostream> #include "geommath.hpp" using namespace std; using namespace My; void vector_test() {     Vector2f x = { 55.3f, 22.1f };     cout << "Vector2f: ";     cout << x;     Vector3f a = { 1.0f, 2.0f, 3.0f };     Vector3f b = { 5.0f, 6.0f, 7.0f };     cout << "vec 1: ";     cout << a;     cout << "vec 2: ";     cout << b;     Vector3f c;     CrossProduct(c, a, b);     cout << "Cross Product of vec 1 and vec 2: ";     cout << c;     ... } void matrix_test() {     Matrix4X4f m1;     BuildIdentityMatrix(m1);     cout << "Idendity Matrix: ";     cout << m1;     float yaw = 0.2, pitch = 0.3, roll = 0.4;     MatrixRotationYawPitchRoll(m1, yaw, pitch, roll);     cout << "Matrix of yaw(" << yaw << ") pitch(" << pitch << ") roll(" << roll << "):";     cout << m1;     ... } int main() {     cout << std::fixed;     vector_test();     matrix_test();     return 0; }

然后还是和之前一样,将其加入到CMakeLists.txt的链条当中。比较特别的是和它同级的CMakeLists.txt,里面多了个add_test指令:

add_test(NAME Test_GeomMath COMMAND GeomMathTest)

这个是告诉CMake,这个是一个测试。然后在顶级的CMakeLists.txt里面需要打开测试开关:

include(CTest)

这样就好了。 不过在编译执行之前,我想先介绍一下cmake的一个简单的编译方式。 到目前为止,我们都是先用cmake生成Makefile或者Visual Studio工程,然后再用传统的Linux程序编译命令(make)或者Visual Studio的编译命令(msbuild)或者IDE进行编译的。其实,cmake对于这些也有包装,在创建编译用目录并在其中生成Makefile或者VS工程之后,我们只需要执行下面的命令就可以编译(假设我们在编译用目录顶级):

cmake --build . --config Debug --clean-first

用这种方式的好处是我们可以动态地改变编译的配置,比如我们要编译调试版,那么就是上面这个,编译Release版,只需要将 –config Debug 改为 –config Release 就可以了。 在编译完成之后,我们可以用下面的命令执行测试:

cmake --build . --config Debug --target test

如果你还是用我们之前的办法编译,那么在Windows下通过编译执行Test.vcxproj这个项目可以完成测试,而在Linux下通过make test可以编译测试用例并如下执行就可以看到结果:

[tim@iZphicesefdwajZ GameEngineFromScratch]$ ./build/Framework/GeomMath/test/GeomMathTest Vector2f: ( 55.299999,22.100000 ) vec 1: ( 1.000000,2.000000,3.000000 ) vec 2: ( 5.000000,6.000000,7.000000 ) Cross Product of vec 1 and vec 2: ( -4.000000,8.000000,-4.000000 ) Dot Product of vec 1 and vec 2: 38.000000 Element Product of vec 1 and vec 2: ( 5.000000,12.000000,21.000000 ) vec 3: ( -3.000000,3.000000,6.000000,1.000000 ) vec 4: ( 2.000000,0.000000,-0.700000,0.000000 ) vec 3 + vec 4: ( -1.000000,3.000000,5.300000,1.000000 ) vec 3 - vec 4: ( -5.000000,3.000000,6.700000,1.000000 ) normalized: ( -0.559402,0.335641,0.749598,0.111880 ) Idendity Matrix: 1.000000,0.000000,0.000000,0.000000 0.000000,1.000000,0.000000,0.000000 0.000000,0.000000,1.000000,0.000000 0.000000,0.000000,0.000000,1.000000 Matrix of yaw(0.200000) pitch(0.300000) roll(0.400000): 0.925564,0.372026,-0.070200,0.000000 -0.327580,0.879923,0.344132,0.000000 0.189796,-0.295520,0.936293,0.000000 0.000000,0.000000,0.000000,1.000000 Matrix of Rotation on Y(angle = 1.570796): -0.000000,0.000000,-1.000000,0.000000 0.000000,1.000000,0.000000,0.000000 1.000000,0.000000,-0.000000,0.000000 0.000000,0.000000,0.000000,1.000000 Matrix of Rotation on Z(angle = 1.570796): -0.000000,1.000000,0.000000,0.000000 -1.000000,-0.000000,0.000000,0.000000 0.000000,0.000000,1.000000,0.000000 0.000000,0.000000,0.000000,1.000000 Matrix of Translation on X(5.000000) Y(6.500000) Z(-7.000000): 1.000000,0.000000,0.000000,0.000000 0.000000,1.000000,0.000000,0.000000 0.000000,0.000000,1.000000,0.000000 5.000000,6.500000,-7.000000,1.000000 Vector : ( 1.000000,0.000000,0.000000 ) Transform by Rotation Y Matrix: -0.000000,0.000000,-1.000000,0.000000 0.000000,1.000000,0.000000,0.000000 1.000000,0.000000,-0.000000,0.000000 0.000000,0.000000,0.000000,1.000000 Now the vector becomes: ( -0.000000,0.000000,-1.000000 ) Vector : ( 1.000000,0.000000,0.000000 ) Transform by Rotation Z Matrix: -0.000000,1.000000,0.000000,0.000000 -1.000000,-0.000000,0.000000,0.000000 0.000000,0.000000,1.000000,0.000000 0.000000,0.000000,0.000000,1.000000 Now the vector becomes: ( -0.000000,1.000000,0.000000 ) Vector : ( 1.000000,0.000000,0.000000 ) Transform by Translation Matrix: 1.000000,0.000000,0.000000,0.000000 0.000000,1.000000,0.000000,0.000000 0.000000,0.000000,1.000000,0.000000 5.000000,6.500000,-7.000000,1.000000 Now the vector becomes: ( 1.000000,0.000000,0.000000 ) View Matrix with position(( 0.000000,0.000000,-5.000000 ) ) lookAt(( 0.000000,0.000000,0.000000 ) ) up(( 0.000000,1.000000,0.000000 ) ): 1.000000,0.000000,0.000000,0.000000 0.000000,1.000000,0.000000,0.000000 0.000000,0.000000,1.000000,0.000000 -0.000000,-0.000000,5.000000,1.000000 Perspective Matrix with fov(1.570796) aspect(1.777778) near ... far(1.000000 ... 100.000000): 0.562500,0.000000,0.000000,0.000000 0.000000,1.000000,0.000000,0.000000 0.000000,0.000000,1.010101,1.000000 0.000000,0.000000,-1.010101,0.000000 MVP: 0.562500,0.000000,0.000000,0.000000 0.000000,1.000000,0.000000,0.000000 0.000000,0.000000,1.010101,1.000000 0.000000,-0.000000,4.040404,5.000000

本作品采用知识共享署名 4.0 国际许可协议进行许可。

参考引用

  1. c++ vector swizzling
  2. constexpr specifier (since C++11)
  3. https://cmake.org/Wiki/CMake/Testing_With_CTest
  4. https://en.wikipedia.org/wiki/Rotation_matrix
  5. http://en.cppreference.com/w/cpp/language/template_parameters

发表评论

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 博主赞过: