基于物理的建模与动画

译者序
电子游戏、动画和建模等许多行业都会用到物理的知识。虽然之前市面上已经有多种介绍游戏、动画所需的物理知识的图书，但是在译者看来，这本《基于物理的建模与动画》无论从内容的广度还是深度来说，都非常值得一读。这本书覆盖了对粒子和粒子系统、刚体、流体等多种物理模型的建模和模拟，所以译者也相信把这本书翻译成中文，对国内相关领域的工作者会有很大的帮助。
这本书兼具理论性和实用性，既有详尽的理论阐释、公式推导，可以帮助读者建立起正确的概念和知识体系，也有丰富的伪代码，可供读者参考以完成自己的项目。
本书分为五个部分。第 1部分（第 1～3章）讲解了物理建模的基础知识。第 2部分（第 4～8章）介绍了基于粒子的模型，包括粒子系统、可变形网格等内容。第 3部分（第 9～12章）介绍了刚体动力学、碰撞与约束，以及模拟复杂骨骼的铰接体动力学。第 4部分（第 13～15章）介绍了流体的模拟，包括流体力学的基础知识、常用的模拟方法。第 5部分是附录，补充介绍了本书涉及的数学基础知识。
虽然原作者假定读者只需要具备大学一年级的数学知识（基础的微积分和线性代数知识），但是后续章节还是比较深入的。译者在翻译的过程中尽可能地补充了相关的知识，来帮助读者理解，特别是第 11章和第 12章。作者在第 11章中引入了一些通常只有物理专业才会学习的分析力学的知识，译者相应地补充介绍了分析力学的基础概念。读者要理解第 12章的内容需要非常熟悉刚体转动参考系中速度和加速度的变换，译者也补充了一些篇幅介绍了这方面的知识。还需要说明的是，第 12章原作者参考的几个文献，基础符号的约定其实略有差别，译者也专门查阅了这些文献，推导、整理清楚了其中的关系。
从开始翻译，到校对即将出版，陆陆续续也经历近三年的时间。译者在翻译这本书的过程中，也收获了很多。后，鉴于译者水平有限，错漏之处在所难免，希望读者批评指正。

前言
萌生撰写本书的想法源于 1994年，当时 Donald House在得克萨斯州农工大学给可视化理工硕士开了一门基于物理的建模课程。自那时开始，他每年都会教这门课， 2008年转到克莱门森大学也继续开设这门课。他离开得克萨斯州农工大学后，John Keyser接手教授这门课并延续至今。虽然我们已教授这门课 22年了，但从来没有一本支撑这门课的教科书。本书的所有插图都来自这门课的学生项目，插图标题下都载有学生的名字。
本书包含了我们在教授这门课时所用的材料，以及一些补充内容。我们的目标是对基于物理的建模领域做一个全面概括，为踏入此领域的研究人员提供有用的参考，或者将其作为一本教科书。我们在设计本书的大纲时，想法是提供一些基础性内容，基础到能让读者用代码实践动画项目，同时还要提供你踏足本领域后所需的拓展性的研究文献。如果你想要使用现成的物理模拟套件写代码，或者使用专业工具，如流行动画软件中的物理引擎，本书也会有这方面的讲解，使你知道这些软件在背后做了什么事情。
由于我们希望本书能相对“常青”，因此在写作时不考虑任何编程语言或图形 API，均以伪代码来表示算法，不含示例的源代码。在我们的课程中，学生们使用 C 编程语言并以 OpenGL作为图形 API。选择这个组合是出于性能方面的考虑。但是，若可接受一点性能开销，你在做项目时也可以采用 Java、C#或 Python语言，配合使用任何可用的图形 API，或者也可使用 Processing和 D3等有内建图形功能的套件。
我们的学生报读这门课有着不同的动机，例如想投身于这个领域，或者想在艺术方面应用动画技术。我们有许多学生为未来职业生涯考虑，想成为电影、动画及游戏工业中的视觉特效师，实际上有很多学生后来确实从事了这些工作，有的还成了大制作电影的首席特效师，获得了美国视觉特效协会（ VES）的奖项和提名。我们的学生来自不同的学术领域，从工程到艺术都有。他们没有接受相同的训练，但他们有共同的兴趣和爱好。我们这门课会有各种受众，所以这门课不是专为计算机科学和工程专业的学生而设的。这门课假设学生上过少两学期的微积分课，熟悉微分和积分的概念，也必须是一个称职的程序员并熟悉基本的图形显示技术。
为了适应多元化的学生，我们在课程中安排了必需的数学原理的相关介绍，主要是线性代数方面的知识。我们把这些内容放在 6个附录中。这种编排可以避免在本书的主线中穿插背景知识。老师可以按学生情况把这些内容安排到课程当中。而一些基本概念的复习内容，以及进阶数学概念的讲解内容，则放在正文中。
虽然我们教授的是入门课程，但本书也为向研究人员介绍这个领域而写，所以我们会选择性地在书中加入一些进阶题目，其中包括对高阶数值积分法、加速模拟的方法、稳定性分析、流体模拟技术、刚体模拟中的多接触处理、约束系统，以及铰接体的介绍。这些内容可作为第二门课程的基础，或是作为附加的学习内容。
每一本书都有其局限性，这本书亦然。本书缺少了一些基于物理的动画的重要内容，包括有限元建模（finite element modeling）、带符号距离场（signed distance field）、流体表面模拟及角色动画等。有限元越来越多地用于模拟变形材质。带符号距离场具有多种用途，如追踪流体表面随时间变化的形状，更高效地预测碰撞等。而在很多水体场景中，流体表面经常是我们感兴趣的地方。在这种情况下，好用高度场和波动的方法，而不是用纳维 –斯托克斯方程。另外，令角色栩栩如生是动画的终极目标，现今的游戏和电影亦如是，其中也越来越多地用到基于物理的动画，如配合动作捕捉制作非常写实的角色动作。若本书获得成功，我们希望这些领域的专家能为第 2版提供相关内容。
我们计划维护一个网站，为本书读者提供长期的支持。首先，这个网站会放每章的部分练习内容、能增强理解的程序示例，以及一些如矩阵和矢量的程序库。本书的勘误表放在 http://www.cs.clemson.edu/ savage/pba/。
此外，我们对不同目标受众提供了 3个课程大纲建议。
中年级计算机科学本科生的课程大纲
这个为期 15周的课程大纲的主题是基于粒子的模拟。作业项目包括三维弹跳球、粒子系统模拟、群集（flocking）系统和基于弹簧的可变形物体。若时间充裕，非常鼓励学生去设计自己的项目并加以实现。我们发现，要求在项目提议书中加入视觉参考资料，对项目的成功起到关键作用。视觉参考资料可以是任何能展示学生想达成的目标的东西。例如，可以是原创的草图或相片，或是网上找到的影像和动画。我们会正式地审核提议书，提出必要的修改建议，后按学生成功达成提议书目标的程度给予评分。 
高年级本科生或年研究生的课程大纲
这个为期 15周的课程覆盖粒子模拟更细致的内容，并提供刚体模拟及流体模拟的入门知识。这些内容类似于我们一直以来所教授的课程。除了上述内容，学生可以实现刚体模拟，其中包含与无限平面的碰撞，或者实现二维 SPH流体模拟。经验告诉我们，学生通过自己策划的项目来完成课程，受欢迎且也能出现秀的成果。我们建议采用与上一课程大纲相同的提议书及评分方法。
具有计算机图形学、线性代数及微分方程背景的研究生课程大纲
我们相信此课程大纲能覆盖整本书的内容，并注重更多进阶题目，包括多刚体碰撞、含摩擦力的接触、约束系统、铰接体及流体模拟的完整内容。老师也可以跨越本书中的内容，例如考虑与以下题目相关的文献：含自碰撞的进阶布料模拟、带符号距离场、有限元方法及角色动画。我们不尝试给这种程度的课程提供建议的教学顺序，而是鼓励老师为课程内容设置一个焦点，设计两三个作业以建立根基，然后让学生设计并实现自己的项目。

本书覆盖基于物理的建模和动画的核心内容，旨在成为这一领域研究、从业者及相关专业师生参考书。本书内容扎实，可帮助读者直接用代码实现动画项目，或使用现成物理模拟套件编写代码，抑或是掌握流行动画软件中的物理引擎等专业工具。本书知识丰富，深入剖析各种相关软件背后背后的运行机理，也不依赖任何编程语言或图形 API。

Donald H. House是美国南卡罗来纳州克莱姆森大学计算机学院视觉计算系的教授和主席。他在马萨诸塞大学阿姆赫斯特分校获得计算机和信息科学博士学位，在伦斯勒大学获得电气工程硕士学位，以及他在联合大学的数学学士学位。他早期的研究领域是布料模拟和基于物理的动画。近，他的重点是在不确定性下视觉化的认知和知觉优化。John C.Keyser是美国德克萨斯州A&M大学计算机科学与工程系的教授和副系主任，他在北卡罗莱纳大学获得计算机科学博士学位，在阿比林获得应用数学、工程物理和计算机科学学士学位基督教大学。他的研究跨越了计算机图形学的一系列主题，特别强调基于物理的模拟和实体建模。
叶劲峰（Milo Yip），从小自习编程，并爱好计算机图形学。上中学时兼职开发策略RPG《王子传奇》，该游戏在1995年于台湾发行。其后他获取了香港大学认知科学学士、香港中文大学系统工程及工程管理哲学硕士。毕业后在香港理工大学设计学院从事游戏引擎及相关技术的研发，职至项目主任。除发表学术文章外，也曾合著《DirectX9游戏编程实务》。2008年往上海育碧担任引擎工程师开发《美食从天而降（Cloudy with a Chance of Meatballs）》Xbox360/PS3/Wii/PC，2009年起于麻辣马开发《爱丽丝：疯狂回归（Alice: Madness Returns）》Xbox360/PS3/PC，2011年加入腾讯互动娱乐引擎技术中心担任专家工程师，所研发的技术已用于《斗战神》、《天涯明月刀》、《众神争霸》等项目中。

2.1　模型及模拟
2.2　牛顿运动定律
2.3　在一维中落下一个球
2.4　运动的微分方程
2.5　基本的模拟循环
2.6　数值近似方法
2.7　空气中的三维运动
2.7.1　跟踪三个维度
2.7.2　空气阻力
2.7.3　风
2.8　总结

第3章　追踪弹跳球
3.1　与平面碰撞
3.1.1　碰撞检测
3.1.2　碰撞测定
3.1.3　更改模拟循环
3.2　碰撞响应
3.2.1　弹性
3.2.2　摩擦力
3.2.3　把所有结合起来
3.3　实现弹跳球
3.3.1　数值精度
3.3.2　静止条件
3.4　多边形的几何学
3.5　点与多边形的碰撞
3.6　特例：三角形相交
3.7　总结

第2部分　基于粒子的模型
第4章　粒子系统
4.1　什么是粒子系统
4.2　随机数、随机矢量及随机点
4.3　粒子生成器
4.4　粒子模拟
4.4.1　运算的编排
4.4.2　撤销粒子
4.4.3　碰撞
4.4.4　几何
4.4.5　高效的随机数
4.5　粒子渲染
4.5.1　点及划痕
4.5.2　精灵
4.5.3　几何图形
4.5.4　体积渲染
4.6　总结

第5章　粒子编排 
5.1　加速度操作
5.1.1　引力吸引器
5.1.2　随机加速度
5.1.3　拖拽与反拖拽
5.1.4　速度限制器
5.2　速度操作
5.2.1　仿射速度操作
5.2.2　旋涡
5.3　避障
5.3.1　势场
5.3.2　操控
5.4　总结

第6章　交互粒子系统
6.1　状态向量
6.1.1　单一粒子的状态向量
6.1.2　交互粒子的状态向量
6.1.3　实现
6.2　扩展状态的概念
6.3　空间数据结构
6.3.1　均匀空间网格
6.3.2　八叉树
6.3.3　kd树
6.4　天文模拟
6.4.1　聚簇
6.4.2　一个采用均匀空间网格的简单算法
6.4.3　一个采用八叉树的自适应算法
6.5　群集系统
6.5.1　核心算法
6.5.2　距离与视域
6.5.3　加速度的优先级
6.5.4　绕过障碍
6.5.5　转向与侧飞
6.6　总结

第7章　数值积分 
7.1　级数展开与积分
7.2　韦尔莱积分与蛙跳积分
7.2.1　基础韦尔莱积分
7.2.2　速度韦尔莱积分
7.2.3　蛙跳积分
7.3　龙格–库塔积分
7.3.1　一阶和二阶龙格–库塔法
7.3.2　四阶龙格–库塔法
7.4　高阶数值积分的实现
7.4.1　状态向量算法
7.4.2　用更高阶积分做碰撞检测
7.5　积分的精度和稳定性
7.5.1　指数衰减和正弦振荡
7.5.2　指数衰减的积分
7.5.3　正弦振荡的积分
7.5.4　RK方法的性能
7.5.5　阻尼与稳定性
7.6　自适应时步
7.7　隐式积分
7.7.1　直接求解隐式积分
7.7.2　雅克比和线性化函数
7.7.3　求根法求解隐式积分
7.7.4　隐式公式的精度和稳定性
7.8　总结

第8章　可形变弹性网格
8.1　阻尼弹性连接件
8.1.1　阻尼弹簧的数学原理
8.2　弹性网格
8.2.1　支撑杆——一种弹性网格的三维结构元素
8.2.2　用支撑杆构造一个弹性网格
8.2.3　空气阻力与风
8.2.4　弹性网格的模拟
8.2.5　结构刚度
8.3　扭转弹簧
8.3.1　力矩
8.3.2　根据扭转弹簧计算力矩
8.3.3　根据扭转弹簧计算顶点受力
8.3.4　带有扭转弹簧的网格的模拟
8.4　选择好的参数
8.5　碰撞
8.5.1　碰撞的类型
8.5.2　碰撞确定
8.5.3　弹性物体的碰撞响应
8.6　晶格形变器
8.7　布料建模
8.8　总结

第3部分　刚体动力学与约束动力学
第9章　刚体动力学
9.1　刚体状态
9.2　刚体属性
9.2.1　质心
9.2.2　惯性张量
9.3　刚体运动
9.3.1　力矩
9.3.2　更新刚体状态
9.3.3　四元数表示法
9.4　实现
9.5　总结

第10章　刚体的碰撞与接触
10.1　刚体碰撞
10.1.1　与静态物体的无摩擦碰撞
10.1.2　两个运动物体间的无摩擦碰撞
10.2　碰撞检测
10.2.1　包围体
10.2.2　粗略碰撞检测
10.2.3　精确碰撞检测
10.3　线性互补问题
10.3.1　处理多个接触刚体
10.3.2　作为LCP的多个碰撞与静止接触
10.3.3　摩擦力转为LCP
10.4　总结

第11章　约束
11.1　罚函数
11.1.1　P（比例）控制器
11.1.2　PD（比例微分）控制器
11.1.3　PID（比例积分微分）控制器
11.2　约束动力学
11.2.1　单约束
11.2.2　多约束
11.3　约化坐标
11.3.1　广义坐标和广义速度
11.3.2　动能、功和势能
11.3.3　拉格朗日量与拉格朗日方程
11.3.4　落球的例子
11.3.5　钟摆的例子
11.3.6　线上运动的珠子的例子
11.4　总结

第12章　铰接体 
12.1　铰接体的结构
12.2　铰接体的动态状态
12.3　空间代数
12.3.1　空间速度与加速度
12.3.2　空间变换
12.3.3　空间力
12.3.4　空间转置
12.3.5　空间内积
12.3.6　空间叉积
12.4　空间代数记号下速度和加速度的传递
12.5　空间孤立量
12.6　次循环
12.7　计算空间铰接量
12.8　计算构件加速度
12.9　推广到树状铰接体
12.10　总结

第4部分　流体动力学
第13章　流体动力学基础
13.1　拉格朗日模拟与欧拉模拟
13.2　流体模拟的数学背景知识
13.2.1　标量场和矢量场
13.2.2　梯度
13.2.3　散度
13.2.4　旋度
13.2.5　拉普拉斯算符
13.3　纳维–斯托克斯方程
13.4　势流场
13.5　总结

第14章　光滑粒子流体动力学
14.1　空间采样和重构
14.2　粒子加速度计算
14.2.1　压强梯度
14.2.2　扩散
14.2.3　外部加速度和碰撞
14.3　核函数
14.4　流体表面和表面张力
14.5　模拟算法
14.6　总结

第15章　有限差分算法
15.1　有限差分
15.1.1　数值微分
15.1.2　微分算符
15.1.3　采样和插值
15.1.4　CFL条件
15.2　半拉格朗日法
15.2.1　w1增加外部加速度
15.2.2　w2用回溯法实现拉格朗日对流
15.2.3　w3速度扩散的隐式积分
15.2.4　w4得到一个无散速度场
15.2.5　烟模拟计算的结构
15.2.6　水模拟计算的结构
15.3　FLIP
15.4　总结

附录A　矢量
附录B　矩阵代数
附录C　仿射变换
附录D　坐标系统
附录E　四元数
附录F　重心坐标
索引

本书覆盖基于物理的建模和动画的核心内容，旨在成为这一领域研究、从业者及相关专业师生参考书。本书内容扎实，可帮助读者直接用代码实现动画项目，或使用现成物理模拟套件编写代码，抑或是掌握流行动画软件中的物理引擎等专业工具。本书知识丰富，深入剖析各种相关软件背后背后的运行机理，也不依赖任何编程语言或图形 API。

Donald H. House是美国南卡罗来纳州克莱姆森大学计算机学院视觉计算系的教授和主席。他在马萨诸塞大学阿姆赫斯特分校获得计算机和信息科学博士学位，在伦斯勒大学获得电气工程硕士学位，以及他在联合大学的数学学士学位。他早期的研究领域是布料模拟和基于物理的动画。近，他的重点是在不确定性下视觉化的认知和知觉优化。John C.Keyser是美国德克萨斯州A&M大学计算机科学与工程系的教授和副系主任，他在北卡罗莱纳大学获得计算机科学博士学位，在阿比林获得应用数学、工程物理和计算机科学学士学位基督教大学。他的研究跨越了计算机图形学的一系列主题，特别强调基于物理的模拟和实体建模。
叶劲峰（Milo Yip），从小自习编程，并爱好计算机图形学。上中学时兼职开发策略RPG《王子传奇》，该游戏在1995年于台湾发行。其后他获取了香港大学认知科学学士、香港中文大学系统工程及工程管理哲学硕士。毕业后在香港理工大学设计学院从事游戏引擎及相关技术的研发，职至项目主任。除发表学术文章外，也曾合著《DirectX9游戏编程实务》。2008年往上海育碧担任引擎工程师开发《美食从天而降（Cloudy with a Chance of Meatballs）》Xbox360/PS3/Wii/PC，2009年起于麻辣马开发《爱丽丝：疯狂回归（Alice: Madness Returns）》Xbox360/PS3/PC，2011年加入腾讯互动娱乐引擎技术中心担任专家工程师，所研发的技术已用于《斗战神》、《天涯明月刀》、《众神争霸》等项目中。