3.2 C++中的数据、代码和内存

本文是Game Engine Architecture的一部分
免责声明

3.2.1 数字的表示

在游戏引擎的开发中, 数字是我们所做的一切东西能运转起来的基础和关键(也包括一般情况下的软件开发)。每一位软件工程师都应了解计算机是如何表示和存储数字的。这一章会带给你阅读本书剩余章节需要的基本知识。

3.2.1.1 数字的进制

对大部分人来说,最常见的是十进制表示法。这种表示法使用了10个各不相同的数字(0到9),并且一个十进制数,从右到左它的每一个数字分别表示10的0至n-1次幂。例如,
7803 =(〖7×10〗^3 )+(〖8×10〗^2 )+(〖0×10〗^1 )+(〖3×10〗^0 )=7000+800+0+3。

在计算机科学中,整数和实数需要存储在计算机的内存中。并且我们知道,计算机用二进制存储数字,意味着只有0和1两个数字是可用的。我们称之为二进制表示法,因为二进制数从右到左的每一个数字分别表示2的0至n-1次幂;计算机科学家有时会用一个”0b”前缀来表示二进制数字。例如,0b1101=(〖1×2〗^3)+(〖1×2〗^2)+(〖0×2〗^1)+(〖1×2〗^0)=8+4+0+1=13。

另外一个通用的表示法是十六进制表示法。这种表示法使用了数字0到9和字母A到F;字母A到F分别代替了十进制数10到15。在C和C++中,用0x前缀来表示十六进制数。十六进制表示法之所以流行是因为计算机通常把数据分组存储,每组有8个位,也被称为字节。而由于一个十六进制数刚好占了4位,所以两个十六进制数等于一个字节。例如,0xFF=0b11111111=255 是单个字节可以存储的最大的数。十六进制数里的每一个数字,从右到左分别表示16的0至n-1次幂。如此,可以举一个例子来说明:0xB052=(11×〖16〗^3 )+(0×〖16〗^2 )+(5×〖16〗^1 )+(2×〖16〗^0 )=11×4096+0×256+5×16+2×1=45,138

3.2.1.2有符号和无符号整数

在计算机科学中,有符号和无符号的整数同时被使用。当然,“无符号整数”确实有点用词不当——在数学上,全数自然数的范围是从0(或1)到正无穷,但整数是从负无穷到正无穷。但在这本书中我们还是坚持用计算机术语“有符号整数”和“无符号整数”这两个词。

大部分现代个人计算机和游戏机,使用32位或64位宽的整数来做数学运算会表现得更出色(尽管8和16位整数也被大量用在游戏编程中)。要表示一个32位无符号整数,我们只需简单地用二进制来编码该值(见上文)。一个32位无符号整数的取值范围是0x00000000(0)到0XFFFFFFFF(4,294,967,295)。

要用32位表示一个有符号整数,我们需要一种能区分正/负数的方法。一种简单的方法就是把最高有效位保留下来作为符号位——当该位是0时,值为正;当是1时,值为负。这时我们能用剩余的31位来表示数字的绝对值大小,而绝对值的取值范围将被减半(但允许每一个绝对值有正负两种格式,包括0)。

大部分微处理器使用一种更轻量、更高效的技术——二进制补码表示法,来编码负整数。这种表示法中,数字0只有一种表示方法,尽管0 的符号位有两种表示形式(正0和负0)。在32位的二进制补码中,0xFFFFFFFF等于-1,是二进制补码表示法中最大的负数。最大有效位被设为1的任何数都是负数。所以,从0x00000000(0)到0x7FFFFFFF(2,147,483,647)表示正整数,而0x800000000(-2,147,483,648)到0xFFFFFFFF(-1)表示负整数。

3.2.1.3定点表示法

整数很适合用来表示全数,但对于分数和无理数,我们需要一个不同的格式来表示小数点这个概念。计算机科学家早期的解决方法是使用定点表示法。这种表示法中,可以任意选择使用多少个位来表示整数部分,而其余位用来表示小数部分。当我们从左到右数(即,从最高有效位到最低有效位),整数部分的每一位表示2的x次幂(…,16,8,4,2,1),而小数位则表示2的x次幂的倒数(1⁄2, 1⁄4, 1⁄8, 1⁄16,…)。
例如,用定点表示法(32位宽,且有一个符号位)来表示-173.25,16位用于表示整数部分,15位用于表示分数部分。我们首先把符号位、整数位部分、小数位部分分别转换成二进制等式(符号位是0b1,173=0b 0000 0000 1010 1101,0.25=1/4=0b 010 0000 0000 0000),然后把这3个值打包到一个32位的整数中,最终结果就是0x8056A000。如图3.4所示。
 图3.4。整数部分16位、分数部分15位的定点表示法。

定点表示法的问题是,它限制了可以表示的数字范围和小数部分可以达到的精度。考虑一个32位的定点数(1个符号位,整数部分16位,小数部分15位)的值,这种格式能表示的数字大小幅度是正负65,535(范围不是很大)。为了解决这个问题,我们采用了浮点表示法

3.2.1.4. 浮点表示法

在浮点表示法中,分数位的起点位置是任意的(根据指数的大小来确定)。一个浮点数分成三个部分:尾数(包含了小数点左右两侧的数字)、指数(指定小数点的位置)、符号位(表示正负)。在内存中有各种不同的标准来编排这三个部分,而最常见的标准是 IEEE-754。在该标准中,一个32位的浮点数的最高有效位是符号位,其次是占8位的指数,最后是占23位的尾数。

假如符号位是s,指数部分是e,尾数是m,那么浮点数v等于:v=〖s×2〗^((e-127))×(1+m) 。

符号位s有两个取值:+1或 -1。指数e被偏移了127以致负指数可以更容易地表示。以隐含的1(实际上这个1并没有储存在内存中)开头的尾数,它使用的剩余的位,会以2的幂次的倒数解释。这暗示了尾数其实是1+m,m是存储在尾数部分的小数。

图3.5。IEEE-754标准中的32位浮点数的格式。

例如,图3.5中的浮点数0.15625,因为它的s=0(暗示该浮点数是正数),e=0b0111 1100=124,并且m=0b0100…=0×2^(-1)+1×2^(-2)=1⁄4,因此,

浮点数绝对值范围和精度之间的权衡

浮点数的精度越大,绝对值的范围越小;反之亦然。这是因为尾数部分的位数量是固定的,这些位必须被数字的整数部分和小数部分共享。如果把更多的位用来表示更大的绝对值,那么就只有更少的位可以被用来保证小数的精确度。在物理层面,通常用有效数字这个词来描述这个概念。(http://en.wikipedia.org/wiki/Significant_digits)

要了解绝对值范围和精度之间的权衡,让我们来看下32位浮点数可能取到的最大值:FLT_MAX≈3.403×〖10〗^38,在32位IEEE浮点数格式下是0x7F7F FFFF。让我们再作以下分解:

  •      一个用23位来表示尾数的32位浮点数的最大绝对值是0x00FF FFFF,或说是连续的24个二进制1(尾数是23个1,再加上隐含的前置1)。
  •      在IEEE-754格式中,值为255的指数有特殊含义——它被用于一些特殊的值,如“非数字值”(NaN)和“无穷”(INF)——所以它不能被用来表示常规的浮点数。于是,8位指数的最大取值是254。再经过隐式的偏移(减127)后,它的值被限定在[-127,127]。

所以FLT_MAX=0x00FF FFFF×2^127=0xFFFF FF00 0000 0000 0000 0000 0000 0000。

换句话说,FLT_MAX的24个二进制数1被往左偏移了127位,而在尾数部分的最低有效位后面还有127 – 23 = 104个隐含的二进制0(或者104/4 = 26个十六进制0)。在我们的32位的浮点数中,这些后置0不对应任何实际的位——他们是因为指数的关系而凭空产生的。如果FLT_MAX减去一个小的数字(这里的“小”是指任何少于26个十六进制数组成的浮点数),结果仍然会是FLT_MAX,这是因为FLT_MAX的26个最低有效十六进制数字实际上并不存在!

当一个浮点数的绝对值大小小于1的时候会出现反面效果。在这种情况下,指数是一个很大的负值,导致有效数字往反向偏移,从而出现精度丢失。在更高的精确度和表示更大的绝对值之间,我们需要做一个权衡。总的来说,在我们的浮点数中有效数字(或有效位)总个数是相同的,指数可以被用来把那些有效位偏移到更高或更低的范围。

另一个要注意的是,在零和最小非零值之间有一个微小的差距(可以用任何浮点表示法来表示)。最小的非零值FLT_MIN是2^(-126)≈1.175×〖10〗^(-38),用十六进制表示是0x00900000(即,指数是0x01或者是-126当减去偏移值127后;并且尾数都是0,除了前置的1)。没有其他方法能表示一个比1.175×〖10〗^(-38)还要小的非零绝对值,因为下一个最小的有效数值就是0。等而言之,当使用浮点表示法的时候,实数线被量化了。

对于一个特定的浮点数表示法,当满足等式1+ε≠1的时候,ε被定义为最小的浮点数。对于一个有23位精度的IEEE-754浮点数,ε的值是2^(-23)(≈1.192×〖10〗^(-7))。ε的最大有效数值正好落在1.0的范围内,因此想通过增加任何比ε小的值来逼近1.0是没有任何作用的。换言之,当我们尝试补充只有23位的尾数的值时,任何用来减少ε的值的新的位会“砍断”。

有限的精度和ε的概念,对游戏软件具有实际的影响。例如,假设当我们用一个浮点变量来跟踪绝对游戏时间(秒)。在这个时钟变量的大小变得如此之大,以致即使增加1/30秒也改变不了它的值之前,我们的游戏究竟能运行多久?答案是大约12.9天。这比大多数游戏的运行时间都长,所以我们也许可以侥幸地在一个游戏中正常地使用一个32位的浮点数作为秒计时器。但更重要的是,需要能够理解浮点格式的限制,从而使我们可以预测潜在的问题,并且在必要的时候可以采取措施避免出现问题。

IEE浮点数位技巧

See[7], Section 2.1,一些真实有用的IEEE浮点数“位技巧“可以使浮点数计算快如闪电。

3.2.1.5 原子数据类型

正如你所知道的,C和C ++提供了许多原子数据类型。在这些数据类型的相对大小和符号问题上,C和C++标准提供了指引,但每个编译器可以自由地、略有不同地定义这些类型,以便在目标硬件上提供最高的性能。

  • 字符(char)。一个字符通常占8位,一般来说存放一个ASCII或者UTF-8字符8位已经足够大(见Section 5.4.4.1)。一些编译器定义了字符是有符号的,而其他一些编译器缺省情况下使用无符号字符。
  • 整型(int),短整型(short),长整型(long)。一个int被用来放置一个对目标平台来说,最高效大小的有符号整数。一般情况下奔腾系列PC机的int是32位宽。short在许多机器上是16位。Long的位长度依赖于硬件,通常是32位或64位。
  • 单精度浮点型(float)。在现代的大部分编译器中,float是32位IEEE-754浮点数。
  • 双精度浮点型(double)。double类型的精度双倍于IEEE-754浮点数(即,64位)。
  • 布尔型(bool)。布尔型变量只有真(true)/假(false)两种值。布尔变量的大小在不同的编译器和硬件架构下基本相同。Bool从来不会只用一个位来实现,但有一些编译器定义bool型为8位大小而其他的编译器则是32位。

编译器定义的大小类型

标准C/C++中的原子数据类型被设计为可移植的,因此它们是非特异性的。然而,在许多软件工程的工作中,包括游戏引擎编程,知道一个特定的变量究竟有多宽是很重要的。Visual Studio C/C++编译器定义了以下用于声明具有显式位宽度的变量的扩展关键字:__ int8,__ INT16,__ int32和__int64。

SIMD 类型

许多现代计算机和游戏机上的CPU都有一个特殊的算术逻辑单元(ALU),被称为向量处理器矢量单元。向量处理器支持一种可并行处理的单指令、多数据形式(SIMD),在其中进行的并行计算操作只用一个机器语言指令。为了让矢量单元可以处理数据,两个或多个单位数据被打包到一个64位或128位的CPU寄存器。在游戏编程中,最常用的SIMD寄存器格式,打包4个32位IEEE-754浮点数到一个128位的SIMD寄存器。该格式使我们能够比SISD(单指令、单数据)ALU更加有效地进行计算(如向量的点积和矩阵乘法)。

每个微处理器的SIMD指令集的名称各不相同,针对这些微处理器的编译器,使用自定义的语法用来声明SIMD变量。例如,对于奔腾类型的CPU,有一套被称为SSE(SIMD流指令扩展)的SIMD指令集,Microsot Visual Studio编译器为用户提供了内建数据类型__ m128来表示4个float大小的 SIMD 单位量。在PlayStation3和Xbox 360上使用的PowerPC型号的CPU,它的SIMD指令集被称为Altivec, GNU C ++编译器使用语法vector float来声明一个被打包的4个float的SIMD变量。我们将在4.7节中更详细地讨论SIMD编程是如何工作的。

可移植的类型

大多数编译器都拥有自己的“规定了大小”的各种数据类型,这些类型有相似的语义,但语法上仍有一些区别。由于这些编译器之间的差异,大多数游戏引擎通过定义自己的原子数据类型,来实现源代码的可移植性。例如,在Naughty Dog的游戏引擎中,我们使用下面的原子类型:

  • F32 是32位的IEEE-754浮点型。
  • U8,I8,U16,I16,U32,I32,U64,I64分别是无符号、有符号的8,16,32,64位的整数。
  • U32F和I32F分别是“速度快”的无符号和有符号的32位值。虽然这两个数据类型包含的都是32位的值, 但实际占用了64位内存。这使得PS3的核心——基于PowerPC的处理器(称为PPU)可以直接读写这些变量到64位的寄存器,比起32位变量的读写,会得到速度上的显著提升。
  • VF32 表示一个由4个float变量组成的SIMD值。

Ogre的原子数据类型

Ogre定义了自己的一套原子类型。Ogre::unit8,Ogre::uint16和Ogre::uint32是基本的无符号整型。

Ogre::Real 定义了一个实数浮点型。它通常被定义为32位的大小(相当于一个float),但通过改变预处理器宏OGRE_DOUBLE_PRECISION使之等于1, 它可以在全局范围内被重新定义为64位宽(就像一个double)。改变Ogre::Real的位宽度大小,一般只出现在当一个游戏对双精度数学运算有特别要求时。图形芯片(GPUs)总是用32位或16位浮点数做数学运算;当用单精度浮点数时,CPU / FPU做数学运算会更快,并且SIMD向量指令也是工作在包含4个32位float型的128位的寄存器之上。因此,大多数游戏往往更倾向于用单精度浮点数做运算。

数据类型Ogre::uchar,Ogre::ushort,Ogre::uint和Ogre::ulong分别是C++中的unsigned char,unsigned short和unsigned long的速记符号。因此,他们并没有比他们各自对应的原生C / C ++类型更有用。
Ogre::Radian和Ogre::Degree是特别有趣的。这两个类是一个简单类型Ogre::Real的封装。这两个类型的主要作用是,允许硬编码的字面常量的角度单位可以更加文档化(如,90度肯定能比1.57弧度更直观地表示直角),并提供两个单位系统之间的自动转换。此外,Ogre:: Angle代表了当前程序的默认的角度单元的角度大小。当OGRE应用程序第一次启动时,程序员可以自定义缺省值是‘弧度’还是‘度’。
也许令人惊讶的是,OGRE并不提供一些固定大小的原子数据类型,而这类型些在其他游戏引擎是司空见惯的。例如,它没有定义有符号的8,16或64位整型。如果你正在基于Ogre编写一个游戏引擎,有一天你可能会发现自己正在手动定义这些类型。

3.2.1.6 多字节值和字节序

大于8位(一个字节)宽的值被称为多字节量。在任何使用了16位或更大位宽的整数和浮点数的软件项目里这很常见。例如,4660=0x1234的整数值,用0X12和0x34两个字节表示。我们称0X12为最高有效字节(MSB),0x34为最低有效字节(LSB)。在一个32位变量里,如0xABCD1234,MSB是0xAB,LSB是0x34。同样的概念也适用于64位整数、32位和64位浮点值。

多字节的整数,可以用以下两种方式之一存放到内存中,并且不同的微处理器所选择的存储方法可能会有不同(见图3.6)。

 图3.6.0Xabcd1234的高字节序和低字节序表示法。

  • 低字节序(little-endian)。如果微处理器是在较低的内存地址存储多字节值的最低有效字节(LSB),而不是最高有效字节(MSB),我们称该处理器是低字节序的。在低字节序的机器上,整数0xABCD1234将按照连续的字节0x34,0X12,0xCD,0xAB存放。
  • 高字节序(Big-endian)。如果微处理器是在较低的内存地址存储多字节值的最高有效字节(MSB),而不是最低有效字节(LSB),我们称该处理器是高字节序的。在高字节序的机器上,整数0xABCD1234将按照连续的字节0xAB,0xCD,0X12,0x34存放。

大部分的程序员都不需要去考虑字节排列顺序。然而,当你是一个游戏程序员时,排列顺序可能会变成你身边的一根刺。这是因为游戏通常是在使用Intel奔腾处理器(低字节序)的PC或Linux机器上运行的,但运行在一个游戏主机上时可能会出问题,如Wii,Xbox 360,PS3——这三个主机使用的都是PowerPC处理器(它使用的字节顺序是可以被配置的,但默认情况下是高字节序)的某一个变种。现在想象会发生什么,当你用你的游戏引擎(使用了Intel处理器)生成待使用的数据文件,然后尝试在PowerPC处理器上加载这个数据文件。任何写进该数据文件的多字节值将按照低字节序格式的存储。但是,当游戏引擎读取该文件,它希望文件里的所有数据是按照高字节序格式存储的。结果会如何?当你写下0xABCD1234,却被读成0x3412CDAB,这显然不是你所希望的!

对于这个问题,至少有两个解决方案:

  1. 你可以把所有的数据文件转存成文本文件,并把所有的多字节数字存储成一系列有序的十进制数,每一个字符(一个字节)对应一个数字。这将是一种磁盘空间的低效用法,但这样确实可行。
  2. 你可以使用一些字节交换工具,在把数据存放到二进制文件之前做一次处理。这样做的话,你可以确保数据文件使用了目标微处理器(游戏机)的字节顺序,即使是运行在一台使用相反字节顺序的机器上。

整数的端字节交换

一个整数的端字节交换,其实并不复杂。您只需从整数值的最高有效字节的位置开始遍历,与对应的最低有效字节交换;继续这样子处理,直到到达中间点。例如,0xA7891023经过两次交换就变成了0x231089A7。

唯一棘手的部分是要知道哪些字节需要交换。比方说,你正在把一个C结构的内容或C ++类对象从内存写到文件。要正确地转换这些数据的字节顺序,你需要跟踪每个数据成员在结构体中的位置和它的大小,并根据它的大小作适当的交换。例如,这个结构:

struct Example
{
U32 m_a;
U16 m_b;
U32 m_c;
};

可能会被这样子写入到一个数据文件:

void writeExampleStruct(Example& ex, Stream& stream)
{
stream.writeU32(swapU32(ex.m_a));
stream.writeU16(swapU16(ex.m_b));
stream.writeU32(swapU32(ex.m_c));
}

交换函数可能是下面这样:

inline U16 swapU16(U16 value)
{
return ((value & 0x00FF) << 8)
| ((value & 0xFF00) >> 8);
}
inline U32 swapU32(U32 value)
{
return ((value & 0x000000FF) << 24)
| ((value & 0x0000FF00) << 8)
| ((value & 0x00FF0000) >> 8)
| ((value & 0xFF000000) >> 24);
}

你不能简单地把示例对象当做一个字节数组,并且盲目地使用一个只具备通用目的的函数来交换字节。我们需要知道哪些数据成员需要交换和每个成员的位宽度;并且每个数据成员必须单独交换。

浮点数端字节交换

让我们简要地看下浮点数端字节交换与整数端字节交换的不同。正如我们所看到的,IEEE- 754浮点值有一个详细的内部的结构,包括一些尾数位,一些指数位,和一个符号位。然而,你可以像整数一样对它做端字节交换,因为字节始终是字节。你可以使用C++的reinterpret_cast操作符操作一个浮点数指针,把浮点数重新解释为整数;这称为类型双关。但当严格别名被启用时,类型双关会导致编译器做优化的时候出现bug。(参见http://www.cocoawithlove.com/2008/04/using-pointers-to-recast-in-c-is-bad.html是对这个问题的很好的描述)。一个更方便的方法是使用一个union,如下:

union U32F32
{
U32 m_asU32;
F32 m_asF32;
};
inline F32 swapF32(F32 value)
{
U32F32 u;
u.m_asF32 = value;
// endian-swap as integer
u.m_asU32 = swapU32(u.m_asU32);
return u.m_asF32;
}

3.2.2 声明,定义和链接

3.2.2.1 编译单元再探

正如我们在第2章中所看到的,一个C或C ++程序由编译单元构成。编译器每次只编译一个.cpp文件,每一个由经过编译后输出的文件称为目标文件(.o或.obj)。.cpp文件是编译器做编译操作的最小单位。一个目标文件中不仅包含了.cpp文件中定义的所有函数编译后的机器代码,还包括所有的全局变量和静态变量。此外,目标文件可能还包含未被解析的函数引用以及在其他.cpp文件中定义的全局变量。

 图3.7.两个编译单元中的未被解析的外部引用。

 图3.8.在成功链接后外部引用全部被正常解析。

 图3.9.两个最常见的链接错误。

编译器每次只对一个编译单元进行操作,所以每当操作一个编译单元时,遇到一个引用了外部的全局变量或函数的引用,编译器必须相信、假设这个存有疑问的实体是确实存在的,如图3.7所示。把所有的目标文件合成一个最终的可执行映像是链接器的工作。在合成的过程中,链接器读取所有的目标文件,并尝试解决、解析目标文件之间所有的交叉引用。如果成功完成链接操作,一个包含所有的函数、全局变量和静态变量的可执行映像就生成了,并且所有跨编译单元的引用已被妥善解决。如图3.8。

连接器的主要工作是解决外部引用,而在这件工作上,它只可能产生两种类型的错误:

  1. 外部引用的目标可能不存在,在这种情况下,链接器会生成一个“未解决的符号(unresolved symbol)”错误。
  2. 链接器可能会找到一个以上的具有相同的名称的变量或函数,在这种情况下,它会产生一个“多重定义的符号(multiply defined symbol)”错误。

这两种情况如图3.9所示。

3.2.2.2 声明与定义

在C和C ++语言,变量和函数在使用前必须先声明和定义。理解C和C++中声明和定义之间的差别非常重要。

  • 声明是一个对象或函数的描述。它为编译器提供了实体的名称和它的数据类型或函数签名(即,返回类型和参数类型)。
  • 而在另一方面,定义描述了程序中一段独一无二的内存区域。这块内存可能包含一个变量,或结构或类的一个实例,或一个函数的机器代码。

换句话说,声明是对实体的引用,而定义是实体本身。定义总是一种声明,但反过来,情况就并非总是如此了 —— 你可以在C和C ++中写一个纯粹的声明,但又不是一个定义。

定义一个函数的方法是,在函数签名后面直接写上函数的内容,并用大括号括上:

//foo.cpp
// definition of the max() function
int max(int a, int b)
{
return (a > b) ? a : b;
}
// definition of the min() function
int min(int a, int b)
{
return (a <= b) ? a : b;
}

在头文件中可以提供函数的纯声明,使它可以被用在其他编译单元中(或在同一个编译单元的下文中)。做法就是,写一个函数签名并在后面加一个分号,前面是一个可选的前缀extern:

//foo.h
extern int max(int a, int b); // a function declaration
int min(int a, int b); // also a declaration (the
// ‘e xtern’ is optional/
// assumed)

定义类/结构体的变量或实例的方法是,在变量或实例名字的前面写上数据类型,以及一个可选的数组说明符(用方括号):

//foo.cpp
// All of these are variable definitions:
U32 gGlobalInteger = 5;
F32 gGlobalFloatArray[16];
MyClass gGlobalInstance;

在一个编译单元里定义的一个全局变量,若使用extern关键字来声明,就可以被用在其他编译单元中,

//foo.h
// These are all pure declarations:
extern U32 gGlobalInteger;
extern F32 gGlobalFloatArray[16];
extern MyClass gGlobalInstance;

多重声明和定义

毫不奇怪, 在一个C / C++程序中任何特定的数据对象或函数可以有多个相同的声明, 但每个对象或函数只能有一个定义。如果一个编译单元存在两个或更多相同的定义,编译器会注意到多个实体具有相同的名称,进而会报告一个错误。如果不同的编译单元中存在两个或更多相同的定义,编译器将无法识别该问题,因为它一次只编译一个编译单元。但在这种情况下,链接器就会给我们一个“多重符号定义“错误,当链接器试图处理相互引用时。

头文件里的定义和内联

把定义放在头文件里是一个危险的做法。其原因应该是很明显的:如果包含一个定义的一个头文件,被多个.cpp文件包含, 必然会生成一个“多重定义的符号”的链接错误。

内联函数里的定义是这个规则的一个例外,因为每次调用一个内联函数会产生这个函数的机器代码的新的拷贝,并且该段代码拷贝会直接嵌入到调用函数的机器代码段中。事实上,内联函数定义必须放置在头文件中,如果他们被不止一个编译单元使用。请注意,在.h文件里的内联关键字inline它并不足以标记一个函数声明,并且使在.cpp文件里该函数的实体代码可以被拷贝到其他的.cpp文件中。编译器必须能够“看到”函数的主体以内联它。例如:

//foo.h
// This function definition will be inlined properly.
inline int max(int a, int b)
{
return (a > b) ? a : b;
}
// This declaration cannot be inlined because the
// compiler cannot “see” the body of the function.
inline int min(int a, int b);
//foo.cpp
// The body of min() is effectively “hidden” from the
// compiler, and so it can ONLY be inlined within
// foo.cpp.
int min(int a, int b)
{
return (a <= b) ? a : b;
}

inline关键字只是给编译器的一个提示。它对每一个内联函数做成本/效益分析,衡量内联该函数会导致的机器代码量的增加与所能获得的潜在的性能优势,并且对于内不内联这个函数编译器有最终的决定权。有些编译器提供了一些语法,像 __forceinline,允许程序员绕过编译器的成本/效益分析,强制让函数直接内联。

3.2.2.3 链接

在C和C++中,每个定义都有一个称为链接的属性。有外部链接的定义除了在原来的编译单元,该定义对其他编译单元也是可见的并且是可以引用的。一个有内部链接的定义可以只在自己的编译单元内可见,但不能被其他编译单元链接。这个属性被叫做链接,是因为它规定了连接器是否可以交叉引用该实体这个问题。因此,从某种意义上说,在编译单元中的C++类定义里的public:和private:关键字就相当于在定义链接类型。

默认情况下,定义都有外部链接。static关键字用来把一个定义的链接方式改为内部链接。请注意,在两个或更多的不同.cpp文件里的两个或更多个相同的静态定义,链接器会认为是不同的实体(就好像它们被赋予了不同的名称),这样这些同类就不会产生“多重定义的符号”错误。下面是一些例子:

//foo.cpp
// This variable can be used by other .cpp files
// (external linkage).
U32 gExternalVariable;
// This variable is only usable within foo.cpp (internal
// linkage).
static U32 gInternalVariable;
// This function can be called from other .cpp files
// (external linkage).
void externalFunction()
{
// ...
}
// This function can only be called from within foo.cpp
// (internal linkage).
static void internalFunction()
{
// ...
}
//bar.cpp
// This declaration grants access to foo.cpp’s variable.
extern U32 gExternalVariable;
// This ‘gInternalVariable’ is distinct from the one
// defined in foo.cpp – no error. We could just as
// well have named it gInternalVariableForBarCpp – the
// net effect is the same.
static U32 gInternalVariable;
// This function is distinct from foo.cpp’s
// version – no error. It acts as if we had named it
// internalFunctionForBarCpp().
static void internalFunction()
{
// ...
}
// ERROR – multiply defined symbol!
void externalFunction()
{
// ...
}

从技术层面来讲,声明是不具有链接属性的,因为这些链接属性在可执行文件映像中并不分配任何存储空间;因此,在编译单元的时候,根本无需考虑是否允许连接器交叉引用该片存储空间。一个声明仅仅是某个单元里定义的某个实体的引用。然而,有内部链接的声明有时候更有利,是因为这种声明可以确定只适用于它出现的编译单元。如果我们允许放宽我们的术语的严谨性,那么所有声明总是有内部链接——没有办法可以在多个cpp文件里交叉引用一个唯一的内部链接声明。(如果我们把一个声明放到头文件中,多个cpp文件可以“看到”这个声明,而每个引用都会产生一个该声明变量的实体拷贝,每一个拷贝都有一份在编译单元内的内部链接。)这也告诉了我们为什么头文件里会允许内联函数定义:这是因为内联函数默认是有内部链接的,就好像他们已经被声明为静态的。如果多个.cpp文件#include了一个包含一个内联函数定义的头文件,每个编译单元将获得该内联函数代码段的私有拷贝,并且不会有“符号多重定义”错误的产生。链接器将每个拷贝看做一个独立的实体。

3.2.3 C / C++内存布局

一个用C或C++编写的程序会将程序数据储存在内存中的各个地方。为了理解内存是如何分配的、各种类型的C / C++变量是如何工作的,我们需要理解一个C / C++程序的内存布局。

3.2.3.1 可执行映像

当一个C / C++程序被构建,链接器会创建出一个可执行文件。大多数类unix的操作系统,包括许多游戏机中的系统,采用一个流行的可执行文件格式,称为可执行和链接格式(executable and linking format, ELF)。因此在这些系统中可执行文件都有一个.elf扩展名。Windows可执行的格式类似于ELF格式; 在Windows中可执行文件有一个.exe的扩展名。无论可执行文件的格式如何,它总是包含程序的一部分映像,并且当它运行时该映像总驻留在内存中。之所以说是一部分映像,是因为程序通常在运行时分配内存,但除此之外还有一部分内存是本来就在可执行映像里的。

可执行映像内部被切分为连续的程序段。每个操作系统的布局方式并不一致,甚至相同的操作系统中的不同可执行文件在内存布局上可能还稍有不同。但一个可执行映像通常由至少以下四个部分组成:

  1. 文本段。有时被称为代码段,这个块包含程序定义的所有函数的可执行机器代码。
  2. 数据段。这个段包含了所有初始化了的全局和静态变量。存放所有全局变量的内存,是按照程序运行时的状态被预先准确布局的,并且已为每个全局变量赋予了适当的初始值。所以当可执行文件被加载到内存中,这些早已被初始化了的全局和静态变量就可以被访问了。
  3. BSS段。“BSS”是一个过时的名字,它代表”Block started by symbol”。该片段包含所有未初始化的全局和静态变量。C和C++语言显式地定义任何未被初始化的全局或静态变量的初始值为0。与其在BSS段中储存一个可能会非常庞大的只包含0值的块,链接器仅仅储存了所有未初始化的全局和静态变量需要的0值字节的数量。当可执行文件被加载到内存,操作系统预留BSS段所请求的0值字节数,并在调用程序的入口点之前填入0值到整个段。(如main()或. WinMain())。
  4. 只读数据段。有时也被称为rodata段,这个段包含任何由程序定义的只读的(常量)全局数据。例如,所有的浮点数常量(例如,Pi=3.141592f),所有用const关键字声明的全局对象实例(例如,const Foo gReadOnlyFoo;)。注意,整数常量(例如,const int kMaxMonsters= 255)通常被编译器用作清单常量,也就是说它们被直接嵌入在所有调用了它们的机器代码段中。这类常量会被放到文本段,但他们并不存在于只读数据段。

全局变量,即在文件范围中、但在任何函数或类声明以外定义的变量,被存储在数据或BSS段,具体只取决于他们是否已经被初始化。下面的全局变量将存储在数据段,因为它已经被初始化:

//foo.cpp
F32 gInitializedGlobal = -2.0f;

而下面的全局对象, 将在BSS段给出的对它的定义的基础上,被操作系统分配内存并初始化为0,因为程序员没有对它进行初始化:

//foo.cpp
F32 gUninitializedGlobal;

我们已经看到,可以使用static关键字给一个全局变量或函数定义内部链接,这意味着它对其他编译单元来说是“看不见”的。static关键字也可以被用来声明一个函数中的全局变量。一个函数里的静态变量因为词法作用域规则,限制了只在声明了它的函数内可见 (即,变量的名字只能在函数里被“看到”)。当函数第一次被调用时,该静态变量被初始化(而不是在main()前,如文件范围级别的静态变量)。但在可执行映像中的内存布局,一个函数静态变量的行为与一个文件静态全局变量完全相同——它要么存储在数据段要么存储在BSS段,取决于它是否已经被初始化。

void readHitchhikersGuide(U32 book)
{
static U32 sBooksInTheTrilogy = 5; // data segment
static U32 sBooksRead; // BSS segment
// ...
}

3.2.3.2 程序栈

当一个可执行程序被加载到内存中并运行,操作系统会为程序栈保留一块内存区域。每当一个函数被调用时,栈内存的一个连续区域被压入栈——我们称此内存块为一个栈帧。如果函数a()调用另一个函数b(),一个新的属于b()的栈帧会被压进a()的栈帧之上。当b()返回时,它的栈帧被弹出,并且程序会从a()离开的地方继续执行。栈帧存储三种类型的数据:

  1. 它存储调用函数的返回地址,这样当被调用的函数返回时,程序就可以继续执行调用函数的剩余代码。
  2. 所有相关的CPU寄存器的内容都保存在栈帧中。这使得新函数可以以它合适的任何方式去使用寄存器,而不必担心覆盖调用函数所需要的数据。返回到调用函数时,寄存器的状态会被恢复,使调用函数可以继续执行。被调用的函数的返回值,如果有的话,通常是留在一个特定的寄存器,以便调用函数可以检索,而其他寄存器会恢复到原来的值。
  3. 栈帧还包含函数内部声明的所有局部变量,也被称为自动变量。这使得每一个不同的函数调用,可以自己维护这些局部变量的一份私有拷贝,即使是那些调用自身的递归函数。(在实践中,一些局部变量实际上是被分配到CPU的寄存器中,而不是存储在栈帧中,但在大多数情况下,这些变量是被分配在函数的栈帧内)。例如:


图3.10 栈帧

void someFunction()
{
U32 anInteger;
// ...
}

栈帧的入栈和出栈操作,通常是通过调节CPU中一个单一的寄存器的值(栈指针)来实现的。图3.10说明了当以下这些函数被执行时的情况:

void c()
{
U32 localC1;
// ...
}
F32 b()
{
F32 localB1;
I32 localB2;
// ...
c(); // call function c()
// ...
return localB1;
}
void a()
{
U32 aLocalsA1[5];
// ...
F32 localA2 = b(); // call function b()
// ...
}

当一个包含局部变量的函数返回时,它的栈帧被丢弃,并且该函数内的所有局部变量被当作不再存在。从技术层面来说,这些变量所占用的内存仍然存留在废弃的栈帧——但是该内存将很有可能会被另外一个函数调用所覆盖。返回一个局部变量的地址这种常见性的错误,像这样:

U32* getMeaningOfLife()
{
U32 anInteger = 42;
return &anInteger;
}

可能会得到你想要得到的值,如果你立即使用返回的指针并且在此期间不调用任何其他的功能。但情况往往没有这么美好,像这样的代码会导致崩溃——而且是以难以调试的方式。

3.2.3.3 动态分配堆

到目前为止,我们已经看到了一个程序的数据可以被存储为全局或静态变量或局部变量。全局变量和静态变量被分配在可执行文件的映像中。局部变量在程序栈上被分配。这些两种存储类型是被静态定义的,也就是说,当程序代码被编译和链接的时候,内存的大小和布局已经知道了。然而,一个程序的内存需求往往不能在编译时期确定。一个程序通常需要动态地分配额外的内存。

要允许动态内存分配,操作系统需要维护一个内存块,使得程序可以通过调用malloc()分配得到内存,并通过调用free()释放内存,使内存返回到内存池中以供其他程序使用。此内存块被称为堆内存,或是自由存储区。当我们动态分配内存时,我们有时会说该内存驻留在堆上。

在C ++中,全局new和delete运算符用于从堆中分配和释放内存。但要小心,C++类可以重载这些操作符来自定义分配内存的方式,甚至是全局的new和delete运算符也是可以被重载的,所以你不能简单地认为,new运算符总是从堆中分配内存。

我们将在第6章中更深入地讨论动态内存分配。如需了解详细信息,请参阅http://en.wikipedia.org/wiki/Dynamic_memory_allocation

3.2.4 成员变量

C结构和C++类中可以把变量划分成多个逻辑单元。重要的是要记住,一个类或结构的声明并不分配内存。这仅仅是一个数据布局的描述——用一刀切的方法来分离该结构或类的成员实例。例如:

struct Foo // struct declaration
{
U32 mUnsignedValue;
F32 mFloatValue;
bool mBooleanValue;
};

一旦一个结构或类被声明,该类的实例可以以分配一个原子数据类型的内存一样的方式被分配内存(定义),例如,

  • 作为程序栈上的自动变量;
void someFunction()
{
Foo localFoo;
// ...
}
  • 作为一个全局静态、文件范围静态或函数内静态的变量;
Foo gFoo;
static Foo sFoo;
void someFunction()
{
static Foo sLocalFoo;
// ...
}
  • 从堆中动态分配。在这种情况下,用于保存数据地址的指针或引用,本身可以被分配为一个局部、全局、静态甚至是动态的变量。
Foo* gpFoo = NULL; // global pointer to a Foo
void someFunction()
{
// allocate a Foo instance from the heap
gpFoo = new Foo;
// ...
// allocate another Foo, assign to local
// pointer
Foo* pAnotherFoo = new Foo;
// ...
// allocate a POINTER to a Foo from the heap
Foo** ppFoo = new Foo*;
(*ppFoo) = pAnotherFoo;

3.2.4.1. 类内部的静态成员

正如我们已经看到的,static关键字有很多不同的含义,具体取决于上下文:

  • 在文件范围内使用时,静态的意思是“限制该变量或函数的可见性,使其只能在.cpp文件内可见。”
  • 在函数范围内使用时,静态的意思是“这个变量是全局的,而不是局部的,但它只能在这个函数内可见”
  • 在一个结构或类里面使用时,静态的意思是“这个变量不是一个普通的成员变量,而更像是一个全局变量。”

注意,当在类内部声明一个静态变量,它没有控制变量的可见性(就如同它使用的是文件范围)——相反,它可以区分每个类实例的成员变量和每个如同全局变量一样的类变量。一个类的静态变量的可见性,是通过在类内部用public:,protected:或private:这三个关键字的声明来决定的。类的静态变量会自动包含在类或结构的名称空间中。所以当它在类或结构外部使用时,必须前置类或结构的名称来消除变量名的歧义。(如,Foo::sVarName)。

像用extern来声明一个普通的全局变量一样,在一个类中声明一个类的静态变量并不分配内存。类内部的静态变量必须在.cpp文件中定义后才会有内存分配。例如:

//foo.h
class Foo
{
public:
static F32 sClassStatic; // allocates no
// memory!
};
//foo.cpp
F32 Foo::sClassStatic = -1.0f; // define memory and
// init

3.2.5 对象在内存中的布局

让类和结构的内存布局可视化是很有用的。这通常是很简单的,我们可以简单地画一个结构或类的框图,用水平线分隔数据成员。下图的structFoo就是这样一个例子,如图3.11所示。

struct Foo
{
U32 mUnsignedValue;
F32 mFloatValue;
I32 mSignedValue;
};

数据成员的大小非常重要,应该在你的图表中标示出来。这并不难实现,用每个数据成员的宽度来表明它的大小(位数)——即,一个32位的整数大约是一个8位整数的宽度的4倍(见图3.12)。

struct Bar
{
U32 mUnsignedValue;
F32 mFloatValue;
bool mBooleanValue; // diagram assumes this is 8 bits
};

3.2.5.1 对齐和包装

当我们开始更仔细地思考结构和类在内存中的布局时,我们可能会开始好奇,当大小较小的数据成员中间穿插着较大的成员,会发生什么事。例如:

struct InefficientPacking
{
U32 mU1; // 32 bits
F32 mF2; // 32 bits
U8 mB3; // 8 bits
I32 mI4; // 32 bits
bool mB5; // 8 bits
char* mP6; // 32 bits
};

你可能会想象,编译器只是简单地将数据成员打包丢进内存,并且放得尽可能地紧密。然而这只是通常的情况。反而,编译器通常会在内存布局中留下一些“洞”,如图3.13所示。(一些编译器允许程序员通过使用预处理器指令请求不留下这些空洞,像#pragma pack,或通过命令行选项;但编译器默认的行为是简单地隔开所有的成员,如图3.13所示)。

为什么编译器要留这些“空洞”?原因在于,每个数据类型都有一个值得重视的对齐需求,以允许CPU更高效地读取和写入内存。一个数据对象的对齐,是指它在存储器中的地址是否是它的大小的倍数(通常是2的n次幂):

  • 以1个字节对齐的对象可以驻留在任何内存地址。
  • 以2个字节对齐的对象,仅驻留在偶数地址(即地址的最低有效四位是0x0,0X2,0x4,0x8,0xA,0xC,0xE)。
  • 4字节对齐的对象,仅驻留在4的倍数的地址(即地址的最低有效四位的是0x0,0x4,0x8, 0xC)。
  • 一个16字节对齐的对象,仅驻留在16的倍数的地址(即地址的最低有效四位是0x0)。

对齐是非常重要的,因为许多现代的处理器,实际上只可以读取和写入正确对齐的数据块。例如,如果一个程序请求从地址0x6A341174读取一个32位(4字节)整数,存储控制器将会轻松地加载数据,因为地址是四字节对齐的。(在这种情况下,其最低有效的半个字节为0x4)。然而,如果是从地址0x6A341173加载一个32位的整数,存储器控制器需要独出两个4字节的块:一个在0x6A341170,另外一个在0x6A341174。然后,它必须mask和偏移这两个32位整数的一部分,然后用逻辑OR运算,将两部分合并并放到CPU的目的地寄存器中。如图3.14所示。

 

一些微处理器甚至更懒。如果您发送一个读(或写)没有对齐的数据的请求,你可能只会得到一些无用的数据,或者,你的程序可能会完全崩溃!(PlayStation 2就是一个不容许未对齐的数据的著名的例子。)

不同的数据类型有不同的对齐要求。一个比较好的经验法则是,数据类型应该它的字节宽度对齐。例如,32位的值,一般要求按四字节对齐,16位的值则按两个字节对齐,8位的值可以存储在任何地址(单字节对齐)。支持SIMD向量运算的CPU,它的每一个SIMD寄存器包含4个32位浮点数,一共有128位(16字节)。四个浮点数的SIMD向量通常有一个16字节的对齐要求。

这把我们带回到布局结构中有“空洞”的低效率打包问题上,如图3.13所示。当较小的数据类型,如在一个结构或类里面,一些8位的布尔值中间穿插了较大的类型,如32位整数或者浮点数,编译器会在其中填充“空洞”,以确保所有的东西都被正确对齐。当声明你的数据结构时,多考虑一下对齐和包装的问题,是一个好主意。通过重新排列上面这个例子中的低效结构体的成员变量,我们可以消除一些填充空洞,如下图所示,在图3.15中:

struct MoreEfficientPacking
{
U32 mU1; // 32 bits (4-byte aligned)
F32 mF2; // 32 bits (4-byte aligned)
I32 mI4; // 32 bits (4-byte aligned)
char* mP6; // 32 bits (4-byte aligned)
U8 mB3; // 8 bits (1-byte aligned)
bool mB5; // 8 bits (1-byte aligned)

 

在图3.15中,结构体的大小是20个字节,不是我们所期望的18字节,因为在最后的两个字节是填充字节。此填充会由编译器增加,以确保在数组上下文当中的结构体的适当对齐。也就是说,如果一个结构数组被定义,并且数组的第一个元素已经被对齐,编译器的填充操作会保证所有后续元素也将被正确对齐。要让结构体之间的对齐更优良,就相当于是要让它的成员变量之间达到最大的对齐。在上面的例子中,最大的成员变量对齐是4个字节,所以整个结构体应该是四字节对齐。我平时喜欢在结构体最后面显式增加空洞,使浪费的空间可见并且显式表明,例如这样:

struct BestPacking
{
U32 mU1; // 32 bits (4-byte aligned)
F32 mF2; // 32 bits (4-byte aligned)
I32 mI4; // 32 bits (4-byte aligned)
char* mP6; // 32 bits (4-byte aligned)
U8 mB3; // 8 bits (1-byte aligned)
bool mB5; // 8 bits (1-byte aligned)
U8 _pad2]; // explicit padding
};

3.2.5.2 C++类的内存布局

有两件事让C++类在内存布局方面有点不同于C结构,那就是继承虚函数

当类B继承自类A,B的数据成员只会紧随在A的数据成员后面出现,如图3.16所示。每一个新的派生类简单地把它的数据成员附加在基类成员的后面,尽管内存对齐需求可能会导致类与类之间有一些填充字节。(多重继承确实有些怪诞的东西,像包括一个基类的多个拷贝的的派生类的内存布局。我们这里不会讨论细节,因为游戏程序员通常倾向于避免多重继承。)

如果一个类包含或继承了一个或多个虚函数,那么额外会有四个字节(字节数取决于目标硬件)被添加到该类的内存布局中,通常是在布局的开始位置。这四个字节被统称为虚表指针vptr,因为它们包含一个指向一个数据结构(被称为虚函数表vtbl)的指针。一个特定类的虚表包含了所有指向它声明或继承的虚拟函数地址的指针。每个具体类都有自己的虚表, 而每个类对象都有一个指向该虚表的指针。

虚函数表是多态的核心,因为它允许编写代码时无需知道是在操作哪个特定的具体类。返回到无处不在的Shape基类和Circle、Rectangle、Triangle子类这个例子,让我们想象一下,基本Shape定义了一个虚拟函数Draw ()。派生类都重写(override)了这个函数,提供不同的实现:Circle::Draw()、Rectangle::Draw()和Triangle::Draw()。任何继承自Shape基类的子类的虚拟表,都包含一个Draw()函数的入口,但该入口将指向不同的函数实现,取决于具体的子类。Circle的虚表将包含一个指向Circle::Draw()的指针,而Rectangle的虚表将指向Rectangle::Draw()和Triangle的虚表将指向Triangle::Draw()。给定一个Shape类指针(Shape* pShape),它指向了任意的Shape类对象,要调用Shape类的Draw()函数,只需要对虚表指针解引用,查找Draw()函数在该虚表的入口。当pShape指向Circle类对象调用的就是Circle::Draw();当pShape指向Rectangle类对象调用的就是Rectangle::Draw();当pShape指向Triangle类对象调用的就是Triangle::Draw()。

下文的代码摘录说明了这些概念。注意,基类Shape定义了两个虚函数,SetId()和Draw(),后者被声明为纯虚函数。(这意味着Shape没有提供默认实现的Draw()函数,派生类必须重写它,如果他们想被实例化的话)类Circle继承自Shape,增加一些数据成员和函数来管理它的中心和半径,并且重写了Draw()函数,如图3.17。类Triangle也继承自Shape,它增加了一个Vector3数组对象来存储它的三个顶点,并添加一些函数来获取和设置单个顶点。类Triangle重写了Draw(),为了便于说明它也重写了SetId()。Triangle类的内存布局如图3.18所示。

class Shape
{
public:
virtual void SetId(int id) { m_id = id; }
int GetId() const { return m_id; }
virtual void Draw() = 0; // pure virtual – no impl.
private:
int m_id;
};
class Circle : public Shape
{
public:
void SetCenter(const Vector3& c) { m_center=c; }
Vector3 GetCenter() const { return m_center; }
void SetRadius(float r) { m_radius = r; }
float GetRadius() const { return m_radius; }
virtual void Draw()
{
// code to draw a circle
}
private:
Vector3 m_center;
float m_radius;
};
class Triangle : public Shape
{
public:
void SetVertex(int i, const Vector3& v);
Vector3 GetVertex(int i) const { return m_vtx[i]; }
virtual void Draw()
{
// code to draw a triangle
}
virtual void SetId(int id)
{
Shape::SetId(id);
// do additional work specific to Triangles...
}
private:
Vector3 m_vtx[3];
};
// -----------------------------
void main(int, char**)
{
Shape* pShape1 = new Circle;
Shape* pShape2 = new Triangle;
// ...
pShape1->Draw();
pShape2->Draw();
// ...
}

4.2 点和向量

本文是Game Engine Architecture的一部分
免责声明

大多数的现代3D游戏是由虚拟世界中的三维物体组成的。游戏引擎需要跟踪每一个对象的位置、朝向和缩放,让它们在游戏世界中运作,然后将它们的坐标转换到屏幕空间,使它们能渲染在屏幕上。游戏中的物体几乎总是由三角形组成的,三角形的顶点则以点来表示。因此,在我们学习如何表示整个三维物体前,让我们先看一看点,以及它的近亲向量。

4.2.1 点和笛卡尔坐标系

从技术上讲,一个代表着一个n维空间中的位置。(在游戏里,n通常等于2或者3。)笛卡尔坐标系是目前为止最常为游戏程序员所使用的坐标系统。它使用二到三条相互垂直的轴来指定一个二维或三维空间中的位置。因此,一个点P是用一个二元组(Px, Py)或者一个三元组(Px, Py, Pz)来表示的。

当然了,笛卡尔坐标系并不是我们唯一的选择。一些其它常见的坐标系统包括:

  • 柱坐标系。该系统采用了一个垂直的“高度”轴h,一个由垂直方向发射出来的径向轴r,以及一个夹角theta(θ)。在柱坐标系中,一个点P由一个三元组(Ph, Pr, Pθ)表示。见图4.2。
  • 球坐标系。该系统采用了两个夹角phi(φ)和theta(θ),以及一个径向测量量r。一个点因此可以由一个三元组(Pr, Pφ, Pθ)表示。见图4.3.

笛卡尔坐标系是目前为止在游戏编程中最广泛使用的坐标系统。然而要记住,我们总应该选择最能反映手头上问题的坐标系。例如,在Midway Home Entertainment开发的游戏Crank the Weasel中,主角Crank在一座充满艺术感的城市中一边游荡一遍收集战利品。我希望让这些战利品绕着Crank的身体旋转飞舞,并越来越靠近直至消失。我将战利品的坐标表示在以Crank当前位置为中心的柱坐标系中。为了实现这样一个螺旋动画,我只需要简单地为战利品的θ赋予一个恒角速度,为其r轴赋予一个非常小的向内的恒线速度,再为其h轴赋予一个非常小的向上的恒线速度好让物品能飞进Crank的口袋。这个简单的动画看起来效果非常棒,并且使用柱坐标系来为其建模远比使用笛卡尔坐标系建模简单。

4.2.2 左手笛卡尔坐标系 vs 右手笛卡尔坐标系

在三维笛卡尔坐标系中,我们可使用两种方式来安排这三条相互垂直的轴:右手方式(RH)和左手方式(LH)。在右手笛卡尔坐标系中,当你的右手绕z轴弯曲,你的拇指将指向z轴正方向,你的其余手指从x轴绕向y轴。在左手笛卡尔坐标系中,情况完全相同,只是你要把右手换成左手。左手和右手坐标系唯一的区别在于其中一条轴的朝向。例如,如果y轴正方向朝上且x轴正方向朝右,那么在右手坐标系中z轴正方向朝向我们,而在左手坐标系中z轴正方向则背向我们。左手及右手笛卡尔坐标系如图4.4所示。

将左手坐标系转换成右手坐标系是非常容易的,反之亦然。我们只需要反转任意一条坐标轴的朝向,并使另外两条坐标轴的朝向保持不变。要记住的是,在左手和右手坐标系中数学规则并没有改变。只有我们对数字的解释 —— 在我们脑海中对数字如何映射到三维空间中的映像 —— 改变了。左手和右手公约仅适用于视图层,而对于底层的数学没什么关系。(事实上,当处理物理模拟中的叉乘时这是很有关系的。但对于绝大多数游戏编程任务来说,我们可以很安全地忽略这些微妙之处。有关更多信息,请参见http://en.wikipedia.org/wiki/Pseudovector。)

数值表示以及视图表示之间的映射完全取决于作为程序员或者是数学家的我们。我们可以选择让y轴指向上,z轴指向前,x轴指向左(RH)或指向右(LH)。或者我们也可以选择让z轴指向上。或者我们还可以让x轴指向上。重要的是,我们在做出了决定以后,应该始终坚持它。

话虽然这么说,但有时候一些约定确实在某些应用中工作得更好。例如,3D图形程序员通常使用一个左手坐标系,其中y轴向上,x轴向右且z轴指向远离观察者的方向(也就是说,沿着摄像机的朝向)。当3D图形使用该坐标系统渲染到2D屏幕上时,增加的y轴坐标对应着增加的景深(也就是距离摄像机的距离)。正如我们将要在接下来的几节中见到的,这就是为什么需要使用z缓冲方案来实现深度遮挡的原因。

4.2.3 向量

向量是一个在空间中既有大小又有方向的量。向量可以看做是一个从尾端点伸展向头端点的有向线段。相比之下,常用于表示大小的标量(也就是普通的实数值)是没有方向的。

通常标量以斜体表示(如v),而向量以黑体表示(如v)。

正如点一样,向量可以由一个由标量组成的三元组(x, y, z)表示。点和向量之间的区别实际上是非常微妙的。技术上来说,一个向量通常只是相对于一个已知点的偏移量。向量可以被移动到三维空间中的任意地方 —— 只要它的大小和方向不变,它还是同一个向量。

向量通常可以用来表示点,只要我们把它的尾部固定在坐标系的原点。这样的向量有时被称之为位置向量半径向量。根据我们目的的不同,我们可以将任意标量三元组解释为点或向量,只要我们记住位置向量的约束是把尾部定位在坐标系的原点就可以了。这意味着点和向量在数学中会以非常微妙的形式区分对待。有人把点称作绝对坐标,而把向量称作相对坐标。

在严格的线性代数场景下,大部分程序员使用名词“向量”来同时表示点(位置向量)和向量。大部分的3D数学库也是这样使用名词“向量”的。在本书中,当差别很显著时,我们会使用名词“方向向量”或只是“方向”。注意,你总是应该在脑海中保持对于点和方向的差异的清晰认识(即使你的数学库不作区分)。正如我们将要在章节4.3.6.1看到的,当需要把它们转换进齐次坐标系以执行4×4矩阵操作时,点和方向需要被区分对待。因此,将两种向量混合有可能会导致你的代码出现bug。

4.2.3.1 笛卡尔基本向量

为笛卡尔坐标系的三条轴分别定义三个正交的单位向量(也就是说,三个向量之间相互垂直,且长度均为一)总是很有用的。沿x轴的单位向量常被称作i,沿y轴单位向量常被称作j,沿z轴单位向量常被称作k。向量ijk有时候被称为笛卡尔基本向量。任意点或向量都可以通过标量(实数)乘以单位向量的和来表示。例如,
(5, 3, –2) = 5i + 3j – 2 k

4.2.4 向量操作

大多数你可以在标量上执行的数学操作也可以应用到向量上。也有一些新的操作只适用于向量。

4.2.4.1 向量乘以标量

将一个向量a和一个标量s相乘是通过将向量a中的每一部分分别与标量s相乘来完成的:

向量乘以标量将使向量的大小缩放,而保留其方向不变,如图4.5所示。将向量乘以-1将会反转向量的方向(头变尾尾变头)。

沿每个轴的缩放因子可以各不相同。这种缩放我们称之为非均匀缩放,它可以被表示为一个向量中的每一部分逐个乘以另一个缩放向量。这种运算我们使用⊗运算符表示。技术上说,我们把两个向量间的这种特殊乘法称之为Hadamard乘法。它很少在游戏产业中被使用 —— 实际上,非均匀缩放是它唯一在游戏中使用的地方:

我们将会在章节4.3.7.3中看到,缩放向量实际上只是3×3对角缩放矩阵S的一个压缩表示形式。因此方程(4.1)的另一种形式如下:

4.2.4.2 加法和减法

两个向量ab之间的加法被定义为ab中的每个部分各自相加。这可以被看做是将向量a和向量b头尾相接 —— 和将是从向量a的尾部指向向量b的头部的向量:

向量相减a – b只不过是a和-b(也就是将b乘以-1,使其反转)的加法操作。这使得结果向量的每一部分等于向量ab的每一部分分别做加法所得的差:

向量加法和减法如图4.6所示。

将点和方向相加或相减

你可以自由地对两个方向向量做加减法。然而技术上说,点却不可以相互加在一起 —— 你只可以把一个方向加到一个点上,该操作的最终结果是另一个点。同样地,你可以将两个点相减,从而得到一个方向向量。这些操作可概括如下:

  • 方向 + 方向 = 方向
  • 方向 – 方向 = 方向
  • 点 + 方向 = 点
  • 点 – 点 = 方向
  • 点 + 点 = 毫无意义(别这样做!)

4.2.4.3 大小

向量的大小是一个标量,它代表着向量在二维或三维空间中的长度。向量的大小以在向量的黑体符号旁边放置一条垂直的直线来表示。我们可以使用毕达哥拉斯定理来计算向量的大小,如图4.7所示:


4.2.4.4 在实际中运用向量操作

信不信由你,通过到迄今为止我们刚学过的向量运算知识,我们已经可以解决游戏中各种各样的问题了。当试图解决一个问题时,我们可以对已知的数据使用如加、减、乘和求长度等操作来生成新的数据。例如,假设我们拥有一个AI角色的当前位置向量P1,以及它当前的速度向量v,我们就可以通过将速度向量v与时间间隔Δt相乘,再将结果加上P1,以求得AI在下一帧的位置P2。如图4.8所示,结果方程式是P2 = P1 + (Δt)v。(这就是所谓的显式欧拉积分 —— 实际上它只在速度为常量时有效,但你懂的。)
再举个例子,假设我们有两个球体,并且我们想要知道它们是否相交。给出两个球的圆心坐标C1和C2,我们可以简单地让两点相减以求出两球之间的方向向量,d = C1 – C2。向量的大小d = |d|决定了两球中心相距多远。如果这个距离小于两球的半径之和,则它们是相交的,否则就是不想交。这如图4.9所示。

对于大多数电脑来说平方根运算的代价是昂贵的,因此游戏程序员总应该使用平方大小的方法来替代:

对于比较两个向量长度(“向量a是否长于向量b?”),以及比较其他一些(平方过的)标量时,使用平方大小是有效的。因此在我们的球体碰撞检测中,我们应该计算d^2 = |d|^2,并将之与两球半径的平方和(r1 + r2)^2进行比较,以获得最佳速度。当编写高性能软件时,永远别在不需要使用平方根的地方使用平方根!

4.2.4.5 规格化及单位向量

单位向量是指大小(长度)为一的向量。我们将会在接下来看到,单位向量在3D数学和游戏编程中是非常有用的。给定具有任意长度v = |v|的向量v,我们可以将其转换为单位向量u,且u具有和v相同的方向,但其具有单位长度。要做到这一点,我们可以简单地把v乘以它大小的倒数。我们把这种操作称之为规格化


4.2.4.6 法向量

如果一个向量垂直于某平面,我们则认为向量是这个平面的法向量。法向量在游戏和计算机图形学中是非常有用的。例如,一个平面可以由一个点和一个法向量来定义。在三维图形学的光照计算中大量使用了法向量,来定义光线和表面碰撞的方向。

法向量通常具有单位长度,但他们并不需要如此。小心不要混淆了术语“规格化(normalization)”和术语“法向量(normal vector)”。规格化的向量是任何具有单位长度的向量。法向量则是任何垂直于平面的向量,但它不必具有单位长度。

4.2.4.7 点乘和投影

向量之间可以相互作乘法,但与标量乘法不一样,向量乘法有许多种不同类型。在游戏编程中,我们最常使用以下两种乘法:

  • 点乘(也被称作标量乘或内积),和
  • 叉乘(也被称作向量乘或外积)。

两个向量之间的点乘将产生一个标量,它被定义为向量各部分乘积的和:

点乘还可以被写作是两向量的大小乘积再乘以两向量夹角的余弦值:
点乘符合交换率(也就是说做乘法的两个向量的顺序可以倒转)和加法分配率

点乘和标量乘法的结合如下所示:

向量投影

如果u是一个单位向量(|u| = 1),那么点乘(a · u)代表了向量a投影在由向量u的方向所定义的无限长直线上的投影长度,如图4.10所示。这个概念同等地适用于二维、三维以及更高的维度,以解决各种各样的三维问题。

作为点乘的大小

一个向量的平方大小可以由向量与自身的点乘得出。因此向量的大小可以简单地做平方根运算后得出:

这之所以可行是因为角度0的余弦值为1,因此剩下来的就是|a||a| = |a|^2。

点乘测试

点乘非常适合用来测试两个向量是否共线或垂直,以及他们是否大致上指向同一方向或相反方向。对于两个任意的向量ab,游戏程序员通常使用以下测试,如图4.11所示:

  • 共线。  (a ⋅ b) = |a||b|= ab(也就是说,两个向量之间的夹角正好为0度 —— 当两个向量均为单位向量时,结果为+1)。
  • 共线但反向。 (a ⋅ b) = –a(也就是说,两个向量之间的夹角为180度 —— 当两个向量均为单位向量时,结果为-1)。
  • 垂直。 (a ⋅ b) = 0(也就是说,两个向量之间的夹角为90度)。
  • 同向。(a ⋅ b) > 0(也就是说,他们之间的夹角小于90度)。
  • 反向。(a ⋅ b) < 0(也就是说,他们之间的夹角大于90度)。

点乘的一些其他应用

点乘可运用于游戏编程中的方方面面。例如,假设我们想要知道一个敌人是处于玩家的身前还是处于玩家的身后。我们可以通过将玩家的位置P与敌人的位置E相减(v = E – P)。假设我们拥有一个向量f指向玩家面对的方向。(我们将会在4.3.10.3中看到,向量f可以直接从玩家的模型世界矩阵中取得。)点乘d = v ⋅ f可以被用来测试敌人是否在玩家身前 —— 如果结果为正数则敌人在玩家身前,负数则是在身后。

点乘还可以用于判断一个点是处于平面的上方还是下方(这在编写一个月球登陆游戏中可能会很有用)。我们可以使用两个向量来定义一个平面:平面上的任意一点Q,以及一个垂直于平面的单位向量n(法向量)。为了找出点P相对于平面的高度h,我们首先要计算出从平面上任意点(点Q就很好)指向点P的向量。因此我们有了v = P – Q。向量v与单位向量n的点乘结果就是向量v在由向量n定义的直线上的投影。这正是我们想要寻找的高度。因此,h = v=(– Q)⋅n。这如图4.12所示。

4.2.4.8 叉乘

两个向量的叉乘(也被称作外积和向量积)将产生另一个垂直于这两个向量的向量,如图4.13所示。以下仅给出三维的叉乘运算:
叉乘的大小

叉乘结果向量的大小是每个被乘向量大小的积再乘以两向量夹角的正弦值。(这与点乘大小的定义十分相似,不过要把余弦换成正弦)。

叉乘|b|的大小等于以ab为边的平行四边形的面积,如图4.14所示。因为一个三角形是一个平行四边形的一半,以位置向量V1、V2和V3围成的三角形面积可以由其任意两条边的外积的大小的一半求得:

叉乘的方向

当使用右手坐标系时,你可以使用右手定则来确定叉乘的方向。将你的手握成杯状,手指从向量a转向向量b,则拇指指向的方向即为叉乘(b)的方向。

注意当使用左手坐标系时,叉乘的方向由左手定则确定。这意味着叉乘的方向取决于所选择的坐标系统。这可能在最开始看上去有点奇怪,但请记住,坐标系统的选择并不会影响我们将要进行的数学计算 —— 它仅改变了数字在三维空间中的可视化效果。当将右手坐标系和左手坐标系相互转换时,所有点和向量的数值保持不变,只是一条轴发生了反转。因此如果叉乘正好发生在我们进行了反转的那条轴(例如z轴)上时,我们需要将那一条轴所对应的值反转。如果不这样做,那我们就需要对叉乘本身的数学定义进行修改,以使得叉乘后z轴的值会在心坐标系中取反。我不会让这些规则导致我失眠。只需要记住:当可视化叉乘时,在右手坐标系中使用右手定则,而在左手坐标系中使用左手定则。

叉乘的属性

叉乘不符合交换率(因此是顺序相关的):

× b ≠ × a

然而,它符合反交换率:
× b = × a

叉乘符合加法分配律
× (c) = (× b) + (× c)

它和标量的乘法结合如下:

(sa) × b = a × (sb) = s(a × b)

笛卡尔基本向量与叉乘的关系如下:
(i x j) = -(j x i) = k
(j x k) = -(k x j) = i
(k x i) = -(i x k) = j

这三个叉乘定义了绕轴的正方向旋转。从x到y的正方向旋转(绕z轴),从y到z的正方向旋转(绕x轴),以及从z到x的正方向旋转(绕y轴)。正如我们将会看到的,这给了我们一个提示,那就是为什么绕y轴旋转的矩阵看上去与绕x或绕z轴旋转的矩阵相反。

实际中运用的叉乘

叉乘在游戏中有许多应用。其中一个最常见的用法是用来寻找垂直于另两个向量的向量。正如我们将在章节4.3.10.2所看到的,如果我们已经知道一个对象的本地单位向量组(本地向量ijk),那么我们就可以很容易找到表示这个对象朝向的矩阵。假设我们只知道一个对象的本地向量k —— 也就是该物体面对的方向。如果我们假设物体没有绕k方向的旋转,我们就可以通过将本地向量k(我们已知的)与世界坐标系的上方向向量(等于[0 1 0])做叉乘,以求得本地向量i。然后我们就可以通过简单地对ik做如下叉乘j = k x i以求得本地向量j

非常相似的方法可以用来求出一个三角形或其它形状的表面的法向量。给出平面上的三点P1、P2和P3,法向量n = normalize[(P2 – P1) x (P3 – P1)]。

叉乘还用于物理模拟。当一个力施加到一个对象上时,它将使对象产生旋转运动(如果力并非施加在对象的重心)。这个旋转力被称作力矩,它是如下计算的。给定力F,以及从重心到受力点的向量r,力矩N = r x F

4.2.5 点和向量的线性插值

在游戏中,我们经常需要找到介于两个已知向量中间的向量。例如,我们希望在两秒内将物体从A点移动到B点,帧率为每秒30帧,我们就需要在AB之间计算出60个中间位置。

线性插值是一种用于寻找两个已知点之间的中间点的简单的数学运算。该运算通常被缩写为LERP(linear interpolation)。该运算定义如下,其中β的范围是[0, 1]:

从几何上来说,L = LERP(AB, β)是某点由A开始,沿着AB方向移动百分之β距离后的位置,如图4.15所示。从数学上说,LERP函数只是求两个输入向量的加权平均,两个向量的权重分别为(1 – β)和β。注意到权重总是从0加到1,这是任何加权平均操作的通用要求。

3.1 C++回顾与最佳实践

本文是Game Engine Architecture的一部分
免责声明

3.1.1 面向对象编程简要回顾

本书中我们大部分要讨论的地方将假设你对面向对象的设计原则有着坚实的理解。如果你的知识有些生锈,那么接下来的章节将会是一个愉快的快速回顾。如果你完全不知道我在这一章里说了些什么,那么我建议你在最好继续之前先捡起一两本关于面向对象编程(如[5])的书籍,特别是C++方面的书阅读一下。

3.1.1.1 类与对象

是属性(数据)和行为(代码)的集合,它们一起构成了一个有用的、有意义的整体。类是一种规格说明书,它描述了被称为对象的类的个体实例该如何被构造。举例来说,你的宠物Rover是“狗”这个类的一个实例。因此,类与实例之间存在一个一对多的关系。

3.1.1.2 封装

封装意味着一个对象仅对外部提供有限的接口,对象内部的状态以及实现细节是对外部隐藏的。封装使得这个类的使用者的生活变得简单,因为他/她只需要去理解这个类有限的接口,而不是其潜在的复杂的实现细节。封装还允许类的作者保证类的实例总是在逻辑上具有一致的状态。

3.1.1.3 继承

继承允许新定义的类对已存在的类进行拓展。新的类可以对原有类的数据、接口和行为进行修改或拓展。如果类Child拓展自类Parent,那么我们就说Child继承自派生自Parent。在这种关系中,类Parent被称作基类或者是超类,而类Child被称作派生类或者是子类。显然,继承导致了类之间的(树形)层级关系。

继承创造了类之间的“is-a”关系。例如,圆形是形状的一种。因此如果我们在编写一个2D绘图程序,也许让圆形这个类继承自一个被称为形状的类会比较好。

我们可以使用约定好的统一建模语言(UML)来为类的层级结构绘图。在这种表示方法中,矩形代表类,空心箭头线代表着继承。继承箭头从子类指向父类。图3.1是一个由UML静态类图所表示的简单类继承。

多重继承

一些语言支持多重继承(MI),这意味着一个类可以拥有多个父类。理论上MI可以很优雅,但实际上这种设计通常会引起很多混乱和技术困难(参见http://en.wikipedia.org/wiki/Multiple_inheritance)。这是因为多重继承将一颗简单的变成了一个具有潜在复杂性的。图会带来这种各样的问题,而这些问题从来都不存在于树中 —— 例如,致命的钻石型继承(http://en.wikipedia.org/wiki/Diamond_problem),在这种情况下派生类最终包含了祖父类的两个副本(见图3.2)。在C++中,你可以使用虚拟继承来避免重复保存祖父类的数据。

大部分C++程序员完全避免使用多重继承,或者只是用其中一种受限的形式。常见的原则是,仅允许无父母的简单类被多继承进一个严格执行单继承的层次关系中。这些类有时被称作混合类,因为它们可以被用作在一颗类树的任意点引入新的方法。图3.3是一个被用作例子而设计出来的混合类。

3.1.1.4 多态

多态是一种语言特性,它允许使用一个单一的公共接口来操纵一个拥有多种不同类型对象的集合。从使用的角度看来,公共接口使得一个由异构物体组成的集合看上去像是同构的。

例如,一个2D绘图程序也许能在屏幕绘制一系列不同形状的图形。一种绘制这个异构集合的办法是使用switch语句来为每个单独的形状执行不同的绘制命令。

void drawShapes(std::list shapes)
{
     std::list::iterator pShape = shapes.begin();
     std::list::iterator pEnd = shapes.end();
     for ( ; pShape != pEnd; ++pShape)
     {
          switch (pShape-> mType)
          {
          case CIRCLE:
               // draw shape as a circle
               break
          case RECTANGLE:
               // draw shape as a rectangle
               break;
          case TRIANGLE:
                // draw shape as a triangle
               break;
               //...
          }
     }
}

这种方法的问题在于,drawShapes()需要“知道”所有能够被绘制的图形的种类。在这个简单的例子中这样做没什么问题,但随着代码在规模和复杂度上的增长,为现有系统增加新种类的形状会变得越来越困难。一旦一个新形状被增加,我们就必须在代码中找到所有嵌入了这一组形状类型处理逻辑的地方 —— 比如这个switch语句 —— 并添加一个case来处理新类型。

解决方案是将这一组处理特定类型对象的逻辑与其余绝大部分代码隔离开来。为了实现这个目标,我们可以为每一种我们希望支持的形状类型定义一个类。所有这些类均会继承自一个公共的基类。一个叫做Draw()的虚函数 —— C++语言中处理多态的主要机制 —— 将会在基类中被定义,每一个形状子类将分别以不同的方式实现该方法。由于不需要“知道”当前绘制的是哪一种图形,绘图函数现在可以简单地依次调用每一个形状的Draw()方法了。

struct Shape
{
     virtual void Draw() = 0; // pure virtual function
};

struct Circle : public Shape
{
     virtual void Draw()
     {
          // draw shape as a circle
     }
};

struct Rectangle : public Shape
{
     virtual void Draw()
     {
          // draw shape as a rectangle
     }
};

struct Triangle : public Shape
{
     void Draw()
     {
          // draw shape as a triangle
     }
};

void drawShapes(std::list shapes)
{
     std::list::iterator pShape = shapes.begin();
     std::list::iterator pEnd = shapes.end();
     for ( ; pShape != pEnd; ++pShape)
      {
          pShape->Draw();
     }
}

3.1.1.5 组合和聚合组合的做法是使用一组相互交互的对象来完成高级任务。组合创造了类之间的一种“has-a”或“uses-a”关系。(从技术的角度来说,关系“has-a”被称作组合,而关系“uses-a”被称作聚合)。例如,宇宙飞船拥有一个引擎,还拥有一个燃料箱。组合/聚合通常使得每个类变得更为单一而专注。没有经验的面向对象程序员往往过于依赖继承,而没有充分使用组合和聚合。举个例子,假设我们正在设计一款图形用户界面用作我们的游戏的前端。我们有一个叫做Window的类来代表任何矩形的GUI元素。我们还有一个叫做Rectangle的类封装了数学概念上的矩形。一个天真的程序员也许会让Window类直接继承自Rectangle类(使用“is-a”关系)。但在一个更为灵活且封装性更好的设计中,Windows类应该更倾向于包含有Rectangle类(采用“has-a”或“uses-a”关系)。这使得两个类的设计更为简洁、专注,并使它们易于测试、调试和复用。

3.1.1.6 设计模式

当同一类型的问题重复出现,且大多数程序员对于该类型问题都采用非常相似的解决方案时,我们就认为一个设计模式出现了。在面向对象编程中,一些常见的设计模式在许多书籍中被定义和描述。关于这一话题最著名的书籍可能是“四人帮”的书[17]

以下是几个常见的通用设计模式的例子。

  • 单例模式。该模式确保一个特定的类只有一个实例(单例),并对外提供访问该实例的全局方法。
  • 迭代器模式。迭代器提供了访问某个集合中元素的有效方法,且不会暴露集合底层的实现。因为迭代器“知道”集合实现的细节,所以用户不需要知道。
  • 抽象工厂模式。抽象工厂提供了接口用以创建一系列相关的类,但不需要指定具体的类。

游戏产业有着自己的一套设计模式,用以解决从渲染到碰撞到动画到音效等各个领域的困难。从某种意义上说,本书所讲的其实是现代3D游戏引擎设计中流行的高层次设计模式。

3.1.2 编码规范:为什么需要以及需要多少

工程师之间关于编码规范的讨论往往将导致狂热的“宗教式”辩论。我不希望在这里引发任何这样的辩论,但我依然认为至少去遵循一些最低限度的编码规范是一个好主意。编码规范之所以存在主要有两个原因。

  1. 其中一些规范使得代码更易于阅读、理解和维护。
  2. 另一些规范有助于防止程序员们搬起石头砸自己的脚。例如,某种编码规范可能鼓励程序员只使用编程语言的一个更小、更易于测试和更不容易出错的子集。C++语言中充斥着滥用的可能性,因此对于C++来说,这种编码规范是特别重要的。

在我看来,编码规范中最应该达成的有以下几点。

  • 接口为王。保持你的接口(.h文件)干净、简单、最小化、易于理解且注释充分。
  • 好的名字有助于理解并有利于避免混淆。对于类、函数和变量坚持使用直观表意的名字。避免让程序员不得不通过查表的方式来解密你的代码。记住,像C++这样的高级语言是为了让人类阅读的。(如果你不同意,问问你自己为什么你不直接使用机器语言来编写所有的软件。)
  • 不要污染全局命名空间。使用C++命名空间或一个公共的命名前缀以确保你的符号不会与库中的其它符号相冲突。(但注意不要过度使用命名空间,或将它们嵌套的太深。)对于使用#define定义的符号要格外小心;记住C++预处理宏仅仅只做文本替换,因此它们将跨越所有的C/C++域和命名空间。
  • 遵循C++最佳实践。像ScottMeyers所著的Effective C++系列书籍[31,32],Meyers所著的Effective STL[33],和John Lakos所著的Large-Scale C++ Software Design[27]中均提供了优秀的指导方针,这将帮助你摆脱困境。
  • 保持一致。我一直尝试使用以下规则:如果你正在从头开始编写代码,你可以按照你的喜好使用任何编码规范 —— 然后保持下去。当编辑已存在的代码时,尝试去遵循代码中已有的编码规范。
  • 突出错误。Joel Spolsky写了一篇非常好的关于编码规范的文章,可以在 http://www.joelonsoftware.com/articles/Wrong.html看到。Joel认为最“干净”的代码不一定是那些在表面上看起来干净整洁的代码,而是那些使得常见编程错误易于显现的代码。Joel的文章通常非常有趣且富有教育意义,我强烈推荐这一篇文章。

4.1 在二维中解决三维问题

本文是Game Engine Architecture的一部分
免责声明

在以下章节中,我们将学到许多在二维和三维中都能使用的数学运算。这是个很好的消息,因为这意味着有时候你可以通过在2D中的想象和画图来解决一个三维的向量问题(这是相当容易做到的!)。可悲的是,这种二维和三维之间的等效性并不一直成立。一些运算,比如交叉乘积(向量积),仅在三维中有定义。尽管如此,先使用一个简化的二维版本来考虑眼前的问题几乎总是无害的。一旦你理解了二维中的方法,你就能想到这个问题是如何扩展到三维中去的。在某些方面,你会惊喜的发现在二维中做出的结果在三维中同样可用。而在其他方面,你总能找到一个坐标系将三维中的问题化作二维。在这本书中,我们总会采用二维图示。

4 游戏中的3D数学

本文是Game Engine Architecture的一部分
免责声明

游戏是一种数学模型,它以某种方式对虚拟世界进行实时仿真。因此,数学覆盖了我们在游戏业界所做的所有工作。事实上游戏程序员几乎利用了所有的数学分支,从三角函数到代数到统计再到微积分。然而到目前为止,作为一个程序员你所最常用到的数学知识是三维向量和矩阵数学(如: 三维线性代数)

然而这样的一个数学分支依旧博大精深,因此我们不能期望在但单一的章节里覆盖它很多的知识。相反,我会试着对游戏程序员所需要的数学工具进行一个概述。与之同时,我会给出一些技巧和窍门,它们会帮助你记忆所有复杂的概念和规则。关于这个主题,我强烈推荐埃里克 ·阿帕的[28],书中对游戏3D数学进行了精彩而深入的讨论。

3 游戏软件工程的基础

本文是Game Engine Architecture的一部分
免责声明

在本章中,我们将简要地回顾一些面向对象编程中的基本概念,然后对一些高级主题进行深入探讨,这些主题应该是在任何软件工程中都非常有价值的(尤其当创建游戏的时候)。与第2章相同,我希望你不要完全地跳过本章;在旅程的一开始我们使用的是同样的一组工具,这点很重要。

2.5 其它工具

本文是Game Engine Architecture的一部分
免责声明

在游戏程序员的工具包里面还有很多其它常用工具。我们不会在这里作详细讨论,不过如果你想了解更多,下面的列表将让你知道它们的存在,并给你指明正确的方向。

  • 差异工具。差异工具,或对比工具,是一种用来比较两个版本的文本文件之间区别的程序。(参见 http://en.wikipedia.org/wiki/Diff对差异工具的讨论。)差异通常是基于文本的逐行比较,但现代的对比工具可以向你展示每一行中某个范围内被修改过的字符。大多数版本控制系统都是用差异工具。有些程序员偏爱某种差异工具,并配置版本控制器使其使用特定的差异工具进行文本对比。流行的差异工具包括ExamDiff( http://www.prestosoft.com/edp_examdiff.asp),AraxisMerge( http://www.araxis.com/),WinDiff(附带于大多数版本的Windows系统,也可以从许多独立的网站上获取),以及GUN差异工具包( http://www.gnu.org/software/diffutils/diffutils.html)。
  • 三路合并工具。当两个人同时编辑同一个文件,将生成两份独立的差异。一个可以将两份差异整合到一个最终版本的文件,使其包含有两个人所作的更改的工具叫做三路合并工具。“三路”是指实际上有三个版本的文件参与进归并操作中:原始文件、用户A的版本、和用户B的版本。(参见 http://en.wikipedia.org/wiki/3-way_merge#Three-way_merge对二路和三路合并技术的讨论。)许多合并工具自带着一个差异工具。一些流行的合并工具包括AraxisMerge( http://www.araxis.com/)和WinMerge( http://winmerge.org/)。另外,Perforce也自带了一个优秀的三路合并工具( http://www.perforce.com/perforce/products/merge.html)。
  • 十六进制文本编辑器。十六进制编辑器是一种用于查看和修改二进制文件内容的程序。它由于将数据以十六进制的整型显示而得名。大多数优秀的十六进制编辑器可以将数据显示为1至16字节的整型、32或64位的浮点型或ASCII文本。当在二进制文本文件中追踪问题,或对某种未知格式的二进制文件进行反向工程时,十六进制编辑器能帮上大忙 —— 这两种情况在游戏引擎开发周期中是比较常见的。夸张地说,世界上至少有一百万种十六进制编辑器存在。我非常幸运地在其中找到了Expert Commercial Software( http://www.expertcomsoft.com/index.html)的HexEdit,但你们也许会找到更好的。
作为一个游戏引擎程序员,你毫无疑问会遇到其它让你生活更加美好的工具。但我希望本章的内容已经涵盖了你在日常生活中使用的主要工具。

2.4 内存泄露和崩溃检测

本文是Game Engine Architecture的一部分
免责声明

两个始终困扰着C和C++程序员的问题是内存泄露和内存崩溃。当内存分配后却没有回收时,会发生内存泄露。这将会浪费内存,并最终导致致命的内存不足错误。当程序无意中在错误的内存位置写入数据时,会导致内存崩溃。这两类问题的罪魁祸首归根于被称为指针的语言特性。

指针是一个强大的工具。当正确使用时,它是善良的化身 —— 但它也会由于错误使用而非常容易地转化为邪恶的化身。如果指针指向的内存已经被释放,或指针被意外地赋予了一个整数或浮点数,那它就变成了导致内存崩溃的危险工具,因为数据几乎可以通过指针写入到任何地方。同样地,当指针被用于跟踪分配的内存时,人们通常很容易忘记在不需要的时候释放它。

显然,良好的编程风格可以有效地避免由指针带来的内存问题。而且从来不出现内存泄露和崩溃的程序肯定是可以通过编写精粹的代码实现的。经管如此,使用工具来帮助你检测潜在的内存泄露和崩溃问题肯定是无害的。幸好,这样的工具有很多。

我的个人最爱是IBM的Rational Purify,这是Purify Plus工具组件的一部分。Purify会在你的代码运行前加工你的代码,在所指针引用、内存分配和内存释放处嵌入钩子。当你在Purify中运行代码时,你将得到一个代码的实时的问题报告 —— 存在的和潜在的。当程序退出时,你将得到一个详细的内存泄露报告。每个问题直接链接到引起问题的源代码处,使得跟踪和解决这类问题变得相对容易。你可以登录http://www-306.ibm.com/software/awdtools/purify以获取更多信息。

另一个流行的工具时CompuWare的Bounds Checker。它在功能和目标上都与Purify类似。你可以在http://www.compuware.com/products/devpartner/visualc.htm找到更多信息。

2.3 性能分析工具

本文是Game Engine Architecture的一部分
免责声明

游戏通常是高性能的实时程序。因此,游戏引擎程序员总是寻找各种方法来加速他们的代码。有一个尽管相当不科学,但却非常著名的原则叫做柏拉图原则(参见http://en.wikipedia.org/wiki/Pareto_principle)。它还被称作二八原则,因为它指出,在大多数情况下,事情80%的效果是由20%的原因导致的。在计算机科学中,我们通常使用该原则的一个变体,称为一九原则。它指出任何软件中,90%的运行时间都是被10%的代码所占用的。换句话说,如果你对那10%的代码进行了优化,那么你就可以获得在运行速度上90%的收益。

那么,你怎么知道哪个10%的代码是需要被优化的呢?为此,你需要一个性能分析器。性能分析器是一种工具,它可以测量你的代码的运行时间。它可以告诉你每一个函数花费了多少时间。然后你就可以直接对那些占用了最大部分运行时间的函数进行优化。

一些性能分析器还可以告诉你每个函数被调用了多少次。这是一个非常重要的需要被理解的测量维度。一个函数可以因为两个原因而吃掉你的时间:(a)它需要花很长时间来执行自己,或(b)它被频繁地调用。例如,一个用来计算游戏世界中最优路径的,运行着A*算法的函数可能在每帧中只被调用了几次,但每次调用都需要花费大量的时间来运行。另一方面,一个用来计算向量间点乘的函数可能只需要花几个CPU周期来执行,但如果你在每帧中调用了它几十万次,这将有可能拖垮你的游戏帧率。

如果你正确地使用了性能分析器,你还可以获得更多的信息。一些性能分析器会报告调用图,也就是对于任意给定的函数,你可以查看哪些函数调用了它(这些函数通常称为父函数),和它调用了哪些函数(这些函数通常称为子函数后代)。你甚至可以看到函数调用的每个子函数花费的时间,以及这些时间占整体运行时间的比例。

性能分析器分为两大类。

  1. 统计式性能分析器。这种性能分析器一般被设计为非侵入式的,意味着无论分析器是否启用,目标代码都能以几乎相同的速度运行。这些分析器通过周期性地对CPU程序计数寄存器采样来进行工作,并会路当前正在运行的函数。在每个函数中采样的数量将生成这些函数所花费时间的近似半分比。英特尔的VTune是采用英特尔奔腾处理器的Windows机器上统计式性能分析器的黄金标准,不过现在也可用于Linux。参见 http://www.intel.com/cd/software/products/asmo-na/eng/vtune/239144.htm以获得详细信息。
  2. 插装式性能分析器。这种性能分析器旨在提供最准确和最全面的计时数据,但其代价是牺牲了目标程序的运行速度 —— 当分析器打开时,程序通常会以蜗牛般的速度运行。这种分析器通过对你的可执行文件进行预处理,在每个函数的开头和结尾插入代码来进行工作。在函数开头和结尾插入的代码将调用一个性能分析库,用来依次检查程序的调用堆栈并记录下所有的细节,包括哪些父函数调用了该函数,父函数总共调用了该函数多少次。这种分析器甚至可以被设置为监视源代码中的每一行,允许其报告每一行代码执行了多久。分析的结果通常惊人的全面而准确,但开启分析器会导致整个游戏几乎不可运行。IBM的Rational Quantify,作为Rational Purify Plus工具套件的一部分,是一个优秀的插装式性能分析器。参见 http://www.ibm.com/developerworks/rational/library/957.html以获取使用Quantify进行性能分析的介绍。

微软也发布了一个介乎于两种性能分析器之间的性能分析工具。它叫做LOP,意思是低开销性能分析器(low-overhead profiler)。它使用统计的方法,周期性地对处理器状态进行采样,这意味着他对程序的执行速度影响很小。但是,它会对每个采样所得的样本分析其调用堆栈,从而获取每个样本的父函数调用链。这将允许LOP提供那些普通统计式性能分析器所不能提供的信息,比如父函数调用的分布。

2.3.1 性能分析工具列表
有许许多多的性能分析器是可用的。为了获得一个全面的列表,请参见http://en.wikipedia.org/wiki/List_of_performance_analysis_tool