牽著老婆滿街逛

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

統計

隨筆 - 1513
文章 - 45
評論 - 907
引用 - 0

公告

言論：
1.每日自??；
2.享受人生；
3.盡力而為；
4.堅持不懈；
5.切莫急躁；
6.慎言敏行；
7.動心忍性；
8.上善若水。

常用鏈接

留言簿(11)

隨筆分類(466)

隨筆檔案(1513)

文章分類(46)

文章檔案(45)

相冊

收藏夾(39)

搜索

積分與排名

積分 - 2533141
排名 - 2

閱讀排行榜

模擬世界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算法就滿足你的需要了?；蛘呶覀兛梢哉fGJK處理不了的只有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 楊粼波閱讀(548) 評論(0) 編輯收藏引用

只有注冊用戶登錄后才能發表評論。




網站導航: 博客園 IT新聞 BlogJava 博問 Chat2DB 管理

青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品

牽著老婆滿街逛

導航

統計

公告

常用鏈接

留言簿(11)

隨筆分類(466)

隨筆檔案(1513)

文章分類(46)

文章檔案(45)

相冊

收藏夾(39)

工具官網

技術網站

開源網站

其他窩點

收藏網站

銀行官網

友情鏈接

資源共享

搜索

積分與排名

最新評論

閱讀排行榜

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