实时碰撞检测算法技术

出版时间：2010年6月  出版社：清华大学出版社  作者：Christer Ericson 著  页数：411  译者：刘天慧 译  
Tag标签：无  

前言

1978年，孩提时代的我就和朋友编写开发了第一款属于我们自己的计算机游戏——我仍然清楚地记得，那是一款采用。BASIC语言编写的猜谜类游戏，玩家将被问及与非洲动物相关的一些问题。恰巧，“太空入侵者”游戏也于同年发布。诚然，与“太空入侵者”相比，我们的作品多少有些黯然失色，但大家仍沉湎于其中，乐此不疲。不久，我们即在自己的家用计算机上开始模仿“太空入侵者”以及当年流行的街机游戏，并设计自己的原创游戏。时光荏苒，岁月蹉跎，昔日对游戏设计的爱好引领我成为一名业界中人，而游戏领域业已发展壮大为一项价值达数十亿美元的产业，并一直在图形硬件以及CPU的发展过程中扮演着催化剂的角色。言归正传，动作类游戏设计的挑战之一便是如何正确地处理碰撞检测问题，即判断两个对象间以及对象与场景间的相交问题。鉴于游戏最初源于2D场景，因而碰撞检测主要集中于如何在屏幕空间内高效地计算对象间的相交状态。时至今日，虽然硬件的计算速度已提高了不止1000倍，但碰撞检测仍被视为一类核心问题，这一点确实令人深思。目前，3D游戏已经成为主流，但其复杂度也随之上升——动辄千万个多边形的计算量已屡见不鲜。相应地，在处理这一类较大的数据集时，与碰撞检测相关的数据结构和算法也变得日趋复杂，皆因这一类计算具有显著的实时特征。这里需要指出的是，游戏设计只是复杂实时碰撞检测应用的一个分支，在诸如CAD／CAM系统以及3D建模设计中也面临着同样的问题。针对游戏设计以及其他实时应用程序，本书详细阐述了与碰撞检测问题相关的高效解决方案，包括相应的数据结构和算法。阅读本书需要读者具备良好的数学知识，相关内容也会在书中进行深入的探讨。同时，为了帮助读者进一步理解计算方案的实现过程，本书还提供了相应的算法、代码以及伪代码。综上所述，碰撞检测问题涵盖了丰富的内容，甚至书中的各章均可独立成书。鉴于此，本书内容力争做到有的放矢，以便为读者今后的学习打下坚实的基础。关于作者本书作者Christer Ericson毕业于瑞典Umea大学并获得计算机科学硕士学位。随后，在该校任教多年并于1996年移居美国。1999年，他曾在索尼电脑娱乐公司美国分公司担任高级主程序员、高级软件配置管理工程师和首席软件工程师。此前，他还曾在Neversoft娱乐公司担任主程序员。2002年以来，他一直在“。Full Sail游戏设计”和项目开发部担任顾问委员会委员。Christer Ericson涉猎广泛，目前他将主要精力集中在程序优化管理方面，并在游戏开发者大会上就此问题进行了演讲。

内容概要

本书详细阐述了与碰撞检测问题相关的高效解决方案及相应的数据结构和算法，主要包括：碰撞检测系统中的设计问题、数学和几何学入门、包围体、基本图元测试、层次包围体技术、空间划分、BSP树层次结构、凸体算法、基于GPU的碰撞检测、数值健壮性、几何健壮性以及优化操作。另外，本书还提供了相应的算法、代码以及伪代码，以帮助读者进一步理解计算方案的实现过程。    本书适合作为高等院校计算机及相关专业的教材和教学参考书，也可作为相关开发人员的自学教材和参考手册。

作者简介

作者：（美国）埃里克森（Christer Ericson） 译者：刘天慧

书籍目录

第1章  概述	  1.1  内容概览	  1.2  关于本书的代码	第2章  碰撞检测系统中的设计问题	  2.1  碰撞算法的设计因素	  2.2  应用程序中对象的表达方式	  2.3  查询类型	  2.4  环境模拟参数	  2.5  性能	  2.6  健壮性	  2.7  实现与使用的简洁性	  2.8  小结	第3章  数学和几何学入门	  3.1  矩阵	  3.2  坐标系统和顶点	  3.3  向量	  3.4  质心坐标	  3.5  直线、光线和线段	  3.6  平面和半空间	  3.7  多边形	  3.8  多面体	  3.9  凸包计算	  3.10  域	  3.11  Minkowski和与Minkowski差	  3.12  小结	第4章  包围体	  4.1  BV期望特征	  4.2  轴对齐包围盒	  4.3  Spheres球体	  4.4  方向包围盒	  4.5  球扫掠体	  4.6  半空间相交体	  4.7  其他类型的包围体	  4.8  小结	第5章  基本图元测试	  5.1  最近点计算	  5.2  图元测试	  5.3  直线、光线和有向线段的相交测试	  5.4  其他类型的测试	  5.5  动态相交测试	  5.6  小结	第6章  层次包围体技术	  6.1  层次结构设计问题  6.2  层次结构的构建策略	  6.3  层次结构的遍历	  6.4  包围体层次结构示例	  6.5  合并包围体	  6.6  高效的树型表达方式及遍历	  6.7  通过缓存机制改善查询	  6.8  小结	第7章  空间划分第8章  BSP树层次结构	第9章  凸体算法	第10章  基于GPU的碰撞检测	第11章  数值健壮性	第12章  几何健壮性	第13章  优化操作	参考文献

章节摘录

插图：【Barequet99】给出了一种简化算法并对点集实现了最佳OBB的粗略逼近：首先计算点集的最小AABB。其中，选择包围盒中两个间距最大的平行面上的两个点，用以确定OBB的长度方向。于是，点集投影至垂直于OBB长度方向的平面上。采用相同的方法计算最小的轴对齐矩形，且利用其中两个间距最大的平行面上的顶点计算OBB的第2个轴。OBB的第3个轴则正交于前两个轴。虽然该算法易于编码，但实际应用中，常采用具有类似复杂度的其他算法获取（接近）最优的包围盒，这一类算法将在后文加以描述。对于瘦长类型的物体对象，OBB轴应与物体的方向对齐；而对于扁平的物体对象，OBB轴应与扁平物体的法线方向对齐。上述方向对应于物体的主方向，而且4.3.3节中描述的主成分分析也可以应用于此处。对于在空间内顶点均匀分布的模型来说，基于模型顶点的包围盒计算一般能够正常运行。然而，内部顶点产生的影响往往使协方差计算产生偏移，并使得OBB呈现任意方向——即使存在极值顶点。因此，应避免使用基于加权顶点位置的包围体计算方法。足以引起注意的一点是：最小包围体的特征定义（中心位置、维度以及方向）皆独立于物体顶点的点簇（clustering）。这一点可以通过对包围体添加（或去除）额外的内部或边界偏心顶点得到验证，该方法并不影响包围体的特征定义，因此也不会影响其计算结果。然而，以上述方式增加额外顶点却会改变顶点的协方差矩阵，从而改变了依据此矩阵计算出的OBB特征。这种情况可以通过只考查极值点加以改善，即只考虑使用物体对象模型上的凸顶点，从而消除内部顶点导致的OBB非对齐问题。然而，即使全部剩余顶点皆为极值顶点，基于顶点的分布状态，最终的OBB仍可出现不可预料的错误，其结果为：点簇仍使得指向自身的某一轴产生偏移。从另一个角度来看，即孤立地对顶点实施计算将无法生产稳定、可靠的协方差矩阵。

编辑推荐

《实时碰撞检测算法技术》是由清华大学出版社出版的。

用户评论 (总计36条)

•   三维碰撞算法绝好的一本书，讲得比较透彻易懂！好书绝对！
•   这本书很好，对于学碰撞检测方面知识的人有很大帮助
•   碰撞检测中的很多东西，能学到很多东西，非常不错
•   很理论的书籍，详细讲解各种碰撞原理
•   对各种算法的应用场景、优缺点、算法步骤的描述都很详尽
•   很好，算法很有用，除了游戏外，其他方面也可用。
•   技术型书籍，对于游戏开发没入门的我来说，打算通过该书学物理引擎，不知道怎么样，等研究透了在评论吧。
•   看了一下书中的内容很实用，只是理论性的东西多一些，需要结合实践才能实现实用的系统。
•   - -。为毛子我不能评分呢，我明明买了这本书了。
•   内容详实专业，国内这方面资料比较少。希望多出些这样的书
•   作者的思维跳跃性很强，没有一定基础很难看懂。
•   希望清华能再接再厉翻译此类专业性非常强的书籍
•   老公的。好。
•   内容太难了，做游戏好多估计都用不到，可能研究生比较适合吧。希望买这本书斟酌一下，先去看看样章，内容很好，只不过太难了。
•   正是我寻找的一本书，对我的帮助很大。
•   书籍的内容都是翻译一些比较好的英文论文，应该算比较有参考价值吧
•   翻译的不错，内容丰富，专业比较强，值得购买。
•   很专业，如果不是研究这个的或者需要用到里面的知识，就别买了。
•   非常好的书，非常符合我的要求...
•   内容还可以,无光盘,只是书表皮有明显捆绑痕迹,让人不爽
•   内容很细化不空谈 学习必备
•   怎么页面上显示的有货，我买的时候就没货了呢？
•   轻而易举能看懂的人估计不是人了，是神。作者的思维跳跃性很强，没有一定基础很难看懂。有点像论文集，讲的不是很详细细致。估计作者假定读者在该领域已经有相当的经验了。
•   比较值。
•   小红马快递公司太烂了，超级烂，卓越怎么会联系这种快递公司？！
•   书很好，写得比较专业和全面。另外，亚马逊的包装配送做得很好！
•   该书算法原理从基础讲起，很容易看懂！非常全面
•   有一定高数基础的人看了会好些，更适合吧。
•   很好的入门书籍值得推荐
•   本书为碰撞检测方面唯一一本全面介绍碰撞检测方向的书籍，可惜是外国人写得，中国的学者要加油啊，书的内容还没仔细看，感觉不错，希望有用
•   该书还回顾了必要的数学基础，只要把书上要求的这些数学基础吃透一般就够用了，然后在动力系统的部分也能用得上，有了碰撞检测+动力系统，游戏物理引擎的一半差不多就搞定了。
•   游戏开发需要掌握这些知识~
•   很多人推荐，还没看，呵呵
•   算法介绍很全面很好，我是看过英文原版的，买到中文版感觉翻译质量上乘，赞
•   不错的 还包括其他很多书没有包含的算法 aabb等
•   还行，涉及内容比较多，是一本不错的工具书