译者序 计算机图形及游戏开发技术是一门与数学紧密相关的技术。正由于拥有强大的数学理 论后盾,计算机模拟的虚拟世界才可以像今天这样逼真。数学在计算机图形及游戏开发中 占有重要的位置,将游戏数学单独进行讲解也成为需要。 本书着重讲解与计算机图形及游戏开发相关的数学知识,重点放在3D数学上。3D数 学是一门和计算几何相关的学科,主要研究怎样用数值方法解决几何问题。3D数学和计算 几何广泛应用在图形及游戏开发领域中,如图形变换、物理仿真等 本书首先介绍基本的代数和儿何知识,其中包括向量、矩阵、四元数、几何变换等相 关内容:在此基础上,进一步介纽与计算机游戏开发相关的数学知识,其中包括几何图元 的碰撞检测、三角形网格的实现、可见性判断等内容。由于本书是一木和计算机紧密结合 的技术性书籍,因此本书在对相关数学知识进行讨论的同时,还给出相应的C++实现代码 通过本书的学习,用户可以掌握计算机游戏开发中常用的数学方法及相关公式,并能 为进一步学习高级开发技术打下基础。 计算机图形及游戏数学是一门复杂的学科,因此在进入本书的学习之前读者需要具备 定的代数和几何学基础。本书可以作为计算机游戏开发人员使用的参考用书,也可以作 为计算机游戏初学者的入门书籍。由于译者水平有限,错误在所难免,对于书中叙述不清, 讲解有误的地方,欢迎读者批评指正。大家可以利用中国游戏开发者联盟网站 htt:/ ww.cngda com进行沟通与交流。 感谢北京递归开元教育科技有限公司提供的机会与平台,感谢家人以及业界的朋友在 本书编写过程中给予我们的支持和帮助,这里还要特别感谢任小宇、李巍、郑砚、张启竣, 在本书翻译过程中提出了非常宝贵的意见,希望我们的绵薄之力能够促进中国游戏产业的 发展。 译者于北京绿园 2005年5月 目录 第1章简介 3.5坐标系转换......23 1.1什么是3D数学 36练习 25 12为什么选择本书 第4章向量 26 13阅读本书需要的基础知识...12 41向量—数学定义 26 14概览 41.1向量与标量.......27 第2章笛卡尔坐标系统 4.1.2向量的维度 27 重由a看目目器审■ 4.13记法 211D数学 4.2向量—几何定义 222D笛卡尔数学...... 4.2.1向量的形式 是吾++出普份十世音世+世世当t分 28 221笛卡尔坐标系的实例: 422位置与位移.... 29 假想中的笛卡尔城 4.2.3向量的表达...29 222任意2D坐标系 8 4,24将向量表示为位移序列 30 22.3在2D笛卡尔坐标系中 4.3向量与点 31 定位点 10 4.3.1相对位置 31 23从2D到3D.......11 432点和向量的关系......31 231第三个维度,第三个轴 吾+b是+普 44练习...32 232在3D笛卡尔坐标系中 第5章向量运算...34 定位点 12 51线性代数与几何 34 233左手坐标系与右手坐标系...13 52符号约定 4吾删暨着斗普吾量吾世世+当世量世曾量量t 35 234本书的重要约定......15 53零向量 35 练习.... 16 54负向量 36 第3章多坐标系... 国日国 吾++吾是+是+量 17 54.1运算法则 36 31为什么要使用多坐标系 17 542几何解释.37 32一些有用的坐标系 18 55向量大小(长度或模)...... 平中干平导珊吾导干 37 士甘+世世 321世界坐标系...19 551运算法则...38 3.22物体坐标系 19 552几何解释,.........38 323摄像机坐标系......20 56标量与向量的乘法 自看由着着日串面日自由画 39 324惯性坐标系.... 5.6.1运算法则.. 39 33嵌套式坐标系.... 562几何解释 40 22 34描述坐标系... 23 57标准化向量 5.7.1运算法则 ←+4;++音+日加孟 41 V3D数学基础:图形与游戏开发 5.7.2几何解释 41 711矩阵的维度和记法......,69 58向量的加法和减法 7.12方阵 日+-+日+量出+出量-B寻吾县4斗寻寻丰善4 70 581运算法则.42 7.13向量作为矩阵使用. 71 582几何解释. 43 714转置...71 58.3一个点到另一个点的向量45 715标量和矩阵的乘法... 72 59距离公式...... 71.6矩阵乘法 72 ...46 510向量点乘 7.17向量与矩阵的乘法75 审aa++普平卡吾甚事甚喜是着 5.10.1运算法则,...47 71.8行向量与列向量 76 72矩阵——几何解释 5.10.2几何解释 t量世量音+士音中“+干吾日日「 48 510.3向量投影 721矩阵是怎样变换向量的 511向量叉乘...50 722矩阵的形式 723总结 832 5.1.1运算法则 世吾当吾吾导由中着中目目市 7,3练习.... 83 511.2几何解释 哪“ 51 52线性代数公式.........3第巳章矩阵和线性变换 513练习 和审由日如宝首十世生世 54 81变换物体与变换坐标系85 第6章3D向量类... 82旋转 57 8212D中的旋转88 61类接口 ...57 8223D中绕坐标轴的旋转89 62 Vector3类 58 8233D中绕任意轴的旋转...91 63设计决策.60 83缩放 申申t“面出 94 631 float与 double + 61 831沿巫标轴的缩放 6.32运算符重载 61 832沿任意方向缩放 63仅提供最重要的操作161 84正交投影...99 634不要重载过多的运算符......62 841向坐标轴或平面上投影... 635使用cont成员函数....62 842向任意直线或平面投影...100 63.6使用 const引用参数......62 85镜像... 101 637成员函数与非成员函数...63 86切变 102 638无缺省初始化...... 87变换的组合...... 103 639不要使用虚函数 88变换分类...,... 63.10不要使用信息屏蔽...64 881线性变换.105 6.311全局常量:零...65 882仿射变换 105 6312不存在“Pon”类......,65 883可逆变换 884 等角变换... 106 63.13关于优化...65 885正交变换... 电菲重面出量于是申 106 第7章矩阵 88.6刚体变换...... 7!矩阵—数学定义... 号吾开;由鲁中中·手 887变换类型小结.107 目录V 89练习 107 104四元数 141 第9章矩阵的更多知识.109 1041四元数记法...14 91矩阵的行列式 I09 1042四元数与复数...142 9l.1线性运算法则.1109 1043四元数和轴一角对...144 912几何解释 113 1044负四元数 144 92矩阵的逆....11114 1045单位四元数145 9.2,1运算法则 114 104.6四元数的模,... 率电即非申审市身着申申 n,145 922几何解释....15 1047四元数共轭和逆....146 93正交矩阵...116 104.8四元数乘法(叉乘)146 93!运算法则.116 1049四元数“差”......150 932几何解释....116 10410四元数点乘151 933矩阵正交化.118 104l1四元数的对数、指数和 944×4齐次矩阵.19 标量乘运算 牛量当普七十是量计吾 151 9414D齐次空间 119 10412四元数求幂152 94.24×4平移矩阵... 120 104.13四元数插值“ slerp”.154 943一般仿射变换...123 10414四元数样条 944透视投影 吾平+日寻吾■罪是丰面a l24 “ squad"...,...,,...157 945小孔成像...125 10415四元数的优点和缺点...158 946使用4×4矩阵进行 105各方法比较 4159 透视投影...... 127 10.6表达形式之间的转换,,....160 95练习 128 0.61从欧拉角转换到矩阵 第10章30中的方位与角位移 130 1062从矩阵转换到欧拉角 rate 162 10.1什么是方位? ...130 063从四元数转换到矩阵 165 102矩阵形式...132 1064从矩阵转换到四元数 167 1021用哪个矩阵....132 106.5从欧拉角转换到四元数.170 10.22矩阵形式的优点...133 10.6.6从四元数转换到欧拉角....171 1023矩阵形式的缺点...133 10.7练习 173 10.24小结 丰着和福1目品率目目中哲 134第11章G++实现175 103欧拉角...135 111概述 175 10.3.1什么是欧拉角...135 1.2 EulerAngles类 178 10.32关于欧拉角的其他约定...137 11.3 Quaternion 类 186 1033欧拉角的优点... 137 114 Rotation matrix类...:111198 1034欧拉角的缺点...138 115 Matrix4×3类 ·中中 204 10.3.5总结...140 VII3D数学基础:图形与游戏开发 第12章几何图元... 25第13章几何检测 262 121表小方法 ...25 1312D隐式直线上的最近点....1262 12.1.1隐式表示.225 132参数射线上的最近点......263 121.2参数形式表示......226 133平面上的最近点......126 1213“直接”形式表示...26 134圆或球上的最近点 264 1214自由度...27 135AABB上的最近点 122直线和射线...... 27 13.6相交性检测,... 266 1221两点表示法 228 137在2D中两条隐式直线的 1222射线的参数形式...228 相交性检测. 266 1223特殊的2D直线表示方法229 13.8在3D中两条射线的相交性检测...267 1224在不同表示方法间转换...230 139射线和平面的相交性检测. 269 123球和圆.1232 13.10AABB和平面的相交性检测...270 124矩形边界框 233 13.11三个平面间的相交性检测...270 24.1AABB的表达方法...234 1312射线和圆球的相交性检测.271 1242计算AABB.1235 13.13两个圆/球的相交性检测...73 1243AABB与边界球. 236 1314球和AABB的相交性检测....1275 l244变换AABB 236 1315球和平面的相交性检测...276 125平面 238 13.16射线和三角形的相交性检测....277 1251平面方程—隐式定义...238 13.17射线和AABB的相交性检测...281 1252用三个点定义 日tmm mt由+日m 239 1318两个AABB的相交性检测...281 1253多于三个点的 13.19其他种类的检测, ...283 “最佳”平面.... 240 1320AABB3类 1254点到平面的距离 ,242 1321练习... 298 126三角形 242第14章三角网格 ·t量mt量a如吾十册4m当吾晋平出吾场F 300 12.6.1基本性质...242 14.1表示网格 12.6.2面积. 141.1索引三角网格.1301 12.6.3重心坐标空间.246 14.12高级技术... 牛事→中丰 302 1264特殊点. 当中当是干平世+证g寻寻 252 14.13针对渲染的特殊表达 302 127多边形...255 1414顶点缓存....1303 1271简单多边形与复杂 1415三角带 303 多边形....255 14.16三角扇 306 127.2自相交多边形...256 142额外信息... 307 12.73凸多边形与凹多边形256 142.l纹理映射坐标...307 12.74三角分解和扇形分解......260 142,2表面法向量,1307 128练习,261 目录l 1423光照值 308 155缓存 342 143拓扑与一致性... 309 156纹理映射,343 144三角网格操作 309 157几何体的生成与提交 144.1逐片操作,... 309 1571LOD选择与渐进式生成...344 14.42焊接顶点...1310 1572向API投送几何体 345 144.3面拆分 “书私“喜丰 312 158变换和光照...1347 1444边缩坍 血出甘吾首重+吾卡 312 15.81变换到裁剪空间...347 1445网格消减.313 15.82顶点光照...1148 14.5C++三角网格类 313 159背面剔除与裁剪.... 349 第15章图形数学 3I9 1591背面剔除... 349 1592裁剪...350 151图形管道概述 320 15.10光栅化 l52设定视图参数 +十 nI::+++册+b吾寻干日国日丰日干斗干甲和 352 322 152,1指定输出窗口...322 第16章可见性检测 353 1522像素纵横比...... 323 16.1包围体检测 354 1523视锥...1324 161.1基于视锥的检测...354 1524视场与缩放...1324 161.2遮断检测.37 153坐标空间...326 162空间分割技术....357 15.3.1模型与世界空间.... 326 163网格系统....1358 15.32摄像机空间 。a塞十mt量世十日 326 164四叉树和八叉树......1360 1533裁剪空间 327 165BsP树 364 1534屏幕空间 329 1651经典BSP... t中,aa由 154光照与雾化 ...330 1652任意分割面 .366 154l色彩的数学... 30 166遮断剔除...367 1542光源331 1661潜在可见集...1367 543标准光照方程——概述......333 1662 Portal技术...1368 1544镜面反射分量... 333第17章后记 ...1372 154.5漫反射分量....336 附录A简单的数学概念 373 15.46环境光分量...... 337 1547光的衰减......338 A.1求和记法 373 1548光照方程—合成138 A.2角度,度和弧度 373 1549雾化 .339 A.3三角函数 374 154.10fat着色与 Gourand A4三角公式 377 着色... 申目申申国 341附录B参考文献. 简介 1.1什么是3D数学 本书将研究隐藏在3D几何世界背后的数学问题—3D数学3D数学是一门和计算几何相关的学科, 计算几何则是研究用数值方法解决几何间题的学科。这两门学科广泛应用于那些使用计算机来模拟3D世 界的领域,如图形学、游戏、仿真、机器人技术、虚拟现实和动画等等。 本书包含理论知识和用C++语言实现的示例代码两部分。理论知识部分解释3D领域中数学和几何之 间的关系,这部分还可作为相关技巧与公式的参考手册。示例实现部分则演示了怎样通过编写代码来实现 这些理论概念。示例中的编程语言使用C++,但本书所介绍的理论技术能用任何编程语言实现。 本书并不是讲解计算机图形学、仿真、或计算几何的专著。但如果您打算学习这些学科,那么您有必 要首先了解本书所介绍的内容是必要的。 12为什么选择本书 如果您打算学习3D数学并用于编写游戏或图形程序,那么本书就是为您而准备的。市场上已经有许 多书承诺能教会您如何制作一款游戏或如何把图像显示到屏幕上,那么为什么还要选择本书呢?因为本书 有许多独一无二的优点。 独一无二的主题:本书填补了讲解图形学、线性代数和编程之间关系的空白。首先这是 本入门书,意味着我们将集中精力介绍基本的3D概念一一而其他书往往是以很小的篇幅或 仅在附录中对3D概念进行简要介绍(作者通常假设读者已经具备了这些知识)所以本书的 定位是:学习编写游戏或图形程序时应该读的第一本书。其次,本书还可以当做参考手册 使用,您可以先通读一遍全文,等以后需要时再查阅具体的内容。 23D数学基础:图形与游戏开发 独一无二的讲解方法:本书通过三个方面来讲解:数学、几何和代码。数学部分列出了 些方程和公式,许多书讲解到这里就止步了。但为了使数学部分的学习更有效,我们还需 具备认识数学怎样和几何相互联系的直觉。本书将以多个例子来展示数学和几何的联系, 如3D定位、矩阵乘法和四元数。有了直观印象后,接着就是具体的代码实现部分。本书 给出了实际可用的代码示例,以使您学习3D数学编程更加直观容易。 独一无二的作者:本书是实际经验与学术权威的结合。 Fletcher dunn有六年的专业游戏编 程经验,在不同游戏平台上发表过多个作品。他现在是 Terminal Reality公司的首席程序员, BloodRayne项目的领导者。 Lan Arberry博士有18年的相关学术研究和大学教学经验。本 书是他的第六本书,也是第三本讲解游戏编程的书。他现在是北德克萨斯大学计算机科学 系的终身教授,高等教育界著名的游戏教育先锋。从1993年起,他就在北德克萨斯大学向 本科生讲授游戏开发课程。 独一无二的插图:仅仅依靠阅读文字和公式就能学会3D数学几乎是不可能的,本书提供了 很多插图助您思考。粗略翻一下本书,会发现几乎每页都有插图,而且插图经常出现在公 式和代码的旁边,我们不仅“讲述”3D数学,还通过插图“展示”给读者。总之,本书贯 彻了将数学概念、几何直观表示和代码实现结合在一起讲述的风格 独一无二的代码:本书代码中的类被设计成可以完成菜些特定任务,并且易于理解、不会 被误用。因为它们简单而且重点分明,您很容易通过一次尝试就让它成功运行。许多书中 使用了错误的类设计思想—提供了所有可能的操作,但只有很小一部分才是实际工作中会 用到的。 独一无二的写作风格:我们的写作风格通俗易懂,富于趣味性,但有时为了表达清晰,语 言就会比较正规并力图表达准确。我们想用有趣的例子来激发读者的兴趣,绝不单纯是为 了幽默。 独一无二的网站:本书没有附带光盘。光盘成本较高并且一旦发行就不能再更新。我们制 作了一个帮助网站:www.cngda.com。在那里可以浏览一些交互式的例子,以使读者能更好 地理解那些很难从字面和插图中领悟的概念。可以从网站上下载代码(包括所有漏洞补丁) 和有用的工具,也可以在上面找到习题答案和其他关于3D数学、图形和编程的网站链接。 1.3阅读本书需要的基础知识 要学习本书的理论部分,读者需要具备一些基本的代数和几何知识,包括: 代数表达式变换 代数运算法则,如结合律、分配律 函数和变量 基本的2D欧几里德几何知识