牵着老婆满街逛

严以律己,宽以待人. 三思而后行.
GMail/GTalk: yanglinbo#google.com;
MSN/Email: tx7do#yahoo.com.cn;
QQ: 3 0 3 3 9 6 9 2 0 .

模拟世界1----物理引擎概述

http://hi.baidu.com/refactor/blog/item/6e4d5aafe9b389f9faed506a.html

                 模拟世界1----物理引擎概述 by no5
                                             This doc is free as long as the auther is mentioned.

        第零节. "Make it real." ----某公司广告语。
        对于大多数玩家来说，也许是HalfLife2第一次把"物理"这个词和3D游戏联系起来。按部就
班升级的3D图形效果突然被注入了一种鲜活的元素。物理效果从被玩家广泛认知起，就注定成为下
一代主流视频游戏中不可或缺的组成部分。我们不妨来看看主流游戏引擎，Unreal3集成了Ageia的
PhysX,Source2似乎也用PhysX,至于大明星Camark的作品，你要相信他是不可能甘于落后的。
        然而在国内，除了Ageia公司的商业推动以外，我们很少能看到有这方面的学习和研究。所
以我打算出品一个"模拟世界"系列，写一点介绍性质的文章，翻译一些经典的论文。一方面作为自
己学习的总结与加深，另一方面也算是为中国的游戏制作圈做点贡献----如果你认为我有这么伟大
的话。(郑重声明1我很懒，郑重声明2我不资深)


        第一节. Hello, simulation world!
        我们从这样一个场景开始：包含重力的二维世界，一个水平线作为地面，一个圆作为我们要
模拟的动态物体，暂不考虑转动。我想稍微懂得编程的人都能把这个场景模拟出来：
         用一个二维的向量代表圆的速度: vel.
         另一个二维的向量代表圆的位置: pos.
         for every time_step:
        ｛
            vel += gravity_acceleration * time_step;
            pos += vel * time_step;
         ｝
         这样就OK了？哦，还要加入对地面的碰撞处理,变成这样：
         for every time step:
        ｛
           if(circle penetrate the ground):
                vel.y = -vel.y;
            vel += gravity_acceleration * time_step;
            pos += vel * time_step;
         ｝
这样，一个最简单的物理模拟器就完成了，当然你可以设置任意的初始位置与速度。如果你真的实现
出来，并把场景画出来，就可以看到小球在地上蹦的效果了。


        第二节. Show me the real stuff!
        我清楚你的想法，上面的东西的确弱智了点。(就像面试时要我打印Fibonacci，我就想只写
上"你丫不是让我递归吧") 不过我的hello world不是仅仅用来愚弄大众的，从小老师就告诉我们，
小故事大道理嘛。从上面的例子我们可以得出以下结论：
        从一个角度来说，物理模拟分为两部分，碰撞检测和模拟计算。你要模拟的东西不是单独的，
而是充分交互的，或者说交互才是模拟的核心。既然要交互，碰撞检测是必不可少的部分，实际
上，就代码量而言，一个物理引擎所包含的碰撞检测的代码一般都会多于模拟计算的代码。因为
相对来说，后者所面对的问题要单纯一些。
        从另一个角度来说，物理模拟还是分成两部分，数学建模和数学求解。其实这也是用数学处
理实际问题的一般规律。在上面的例子中，我们建立好2D空间，位置，速度的数学表示，是建模
的过程；而在每个time_step中，对速度和位置的改变(包括碰撞时的改变)，则是求解的过程。比
如说为什么碰撞的时候，把Y向速度反向呢？因为这就是求解的结果。(当然这个结果是非常粗糙
甚至是在某些情况下有问题的)
        好了，废话终于说完了，进入正题。(首先声明，本文所讨论的只是刚体的模拟，至于其他
的高级的(或者称为不太普及的)模拟，如粒子，布料，暂不涉及。) 现在我预感到有些同学将在下
面的阅读过程中关掉浏览器，因为他们觉得太"专业"了或者没有深入了解的兴趣。为了对这些同学所
付出的阅读时间有所交代，我决定专门为他们写个结尾："在模糊掉很多细节的前提下，物理引擎的
工作流程是这样,模拟是一桢一桢的进行的，每桢中，对所有的物体进行检测，找出相交互的物体以
及交互的细节，并根据这些信息，通过牛顿力学原理，对每个物体计算出新的速度，然后利用速度去
更新物体的方位。"
        现在大部分同学都走了，后排的同学可以往前面坐坐。
        以下部分的最低系统要求为大学数学和大学普通物理力学以及计算机图形学基本概念。推荐
配置再加上计算机图形学和较高级的理论力学知识。首先说说约束(constraint)这个概念，标准的定
义可以去参考理论力学课本。大概就是指两个刚体间的相互牵制，比如说桌子和桌子上的茶杯间的牵
制，活塞和气缸间的牵制。正是有了约束才使得物理模拟成为一个课题，否则按照最基本的几个力学
公式就可以完美模拟刚体了。所以求解约束是物理模拟的核心内容。当然在求解之前，第一部是对约
束进行建模。而约束又可以分为两类，一类是如铰链，活塞等"人为"的约束，被称之为Joint,这类约
束建模的已知条件是很清晰的。另一类则是在物体在碰撞或接触时产生的约束，这类约束建模则依赖
于碰撞检测。也就是说后一类的约束，要想得到求解，跟前一类不在一个起跑线上----它先要过碰撞
检测这道关。所以我们要照顾照顾它，先谈谈碰撞检测。
        碰撞检测本身就是个大题目，涉及到一些基本概念请参考wiki, 本文会对其中一些给出帮助
理解性的解释。一般物理引擎支持的Shape有：简单Shape如Shpere和Box，Convex，TriangleMesh
(Concave)。其碰撞检测一般分成三个部分，粗测阶段(BroadPhase)，细测阶段(NarrowPhase)和中间
阶段(MiddlePhase),请注意这些名词的中文翻译都是我自己想的，其目的仅仅是为了帮助理解，那些
翻译出来对理解没有帮助的我就不翻了，还望各老师同学理解。你可能要问为什么我不把MiddlePhase
排在中间呢，这是因为他仅仅针对TriangleMesh这种Shape，后面详述。所谓BroadPhase,就是对所有
的Shape进行初步检测，具体做法是检测每两个Shape的包围盒是否相交，是则送入下一阶段处理。这
里的包围盒一般是AABB，原因显然是它的性价比最好。下一步就是NarrowPhase了，这时，我们必须
根据不同类型的Shape给出不同的算法。比如你要支持Sphere和Box两种Shape的话，就需要实现
Sphere_vs_Sphere, Sphere_vs_Box, Box_vs_Box三种算法。显然，如果你要支持多种Shape，你的算
法数量将是很大的。某些简单Shape间的检测是相对简单的如Sphere_vs_Sphere,Sphere_vs_Box，但
并不是所有的都如此。所幸的是有一些通用的算法，如SAT和GJK。SAT支持所有的Convex Polyhedron
,而GJK更强大，支持所有的Convex。因为一般简单Shape都是Convex，所以你如果打算只支持Convex
的话，一个GJK算法就满足你的需要了。或者我们可以说GJK处理不了的只有TriangleMesh了，由于
TriangleMesh一般比较大，我们需要借助BVH，找到每一个可能与其他Shape碰撞的Triangle，再进行
精确检测。而这个中间过程就是所谓MiddlePhase。本段中提及的关键算法，均将在下节中有详述。
        其实上面的讨论中都忽略了一个事实，就是在物理引擎中，碰撞检测的工作并不是到找到哪
些Shape相交就结束了。还有很多工作要做，我们要选取合适的碰撞点，对每个碰撞点要得到法线，
相交深度等信息。这些也在下节中继续讨论。
        好了，现在我们得到了碰撞信息，两种约束站在了同一起跑线上，让我们回到约束求解这个
核心问题上来吧。我们求解约束，所希望的结果是什么呢？简单的说是新的物理状态，速度，位移。
你既可以先求出约束力，然后通过约束力更新这些状态，也可以直接算出这个约束所产生的冲量，直
接施加于刚体。
         对于每个约束，我们都能给出位移约束方程。比如说两个质点的距离固定，那么约束方程
就是 (r1 - r2)Dot(r1 - r2) = L*L。当然这个是最简单的情形，刚体的约束方程要比质点复杂，而
且各种不同的约束自然有各种不同的约束方程。而约束方程是求解的起点，或者说直接或间接的，你
都是通过约束方程和物理公式，算出了约束力或者冲量。而在各种求解的算法中，最关键的一个概念
就是约束的雅可比(Jacobian)，又叫雅可比矩阵。它的得出很简单，就是对约束方程求导。比如在上面
例子中的约束方程，如果将这个方程对时间求导，将会得到什么呢？一个速度方程。然后把这个方程
中的速度V分离出来，并整理成矩阵相乘的形式:J*V=0，这样得到的这个J矩阵就是这个约束的雅可比
矩阵。以雅可比为基础，目前主要有两种求解实现，分别是PGS求解LCP，和Sequential-Impulse
/ Impulse-Based。同上面一样，欲知具体算法如何，且听下回分解。

posted on 2008-01-09 17:44 杨粼波 阅读(530) 评论(0)  编辑 收藏 引用


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   博问   Chat2DB   管理