2016年12月6日 星期二

「IMPULSE衝力2D物理引擎」的探索過程與運作原理


在寫完前一篇「IMPULSE衝力2D物理引擎」的介紹後,感覺還少了些什麼?一個物理與數學的中輟生(我大三之後就沒再學物理了,且也快忘光了),是如何從coding的角度來探索物理引擎的呢?物理引擎內,到底是什麼程式呢?請看這一篇的紀錄文章。




這篇文章大概分成兩個部分,前半是(艱苦的)探索過程,後半是運作原理。原理的部分很複雜,所以採簡要敘述與列出參考資料,不過要有心理準備,參考資料都是英文的。

這個主題,大大的超出了我的能力與預期,幾度想在中途放棄,但是想到能讓遊戲中的物體,有著真實世界的碰撞反應。諸如「憤怒鳥就是這樣做出來的」、「能做出來實在是太酷了」這樣的信念,讓我一直堅持到了最後。


【探索過程】
 
一開始不知道要從哪裡下手,於是試著從Scratch的作品說明中找一些線索。

https://scratch.mit.edu/projects/86958095/

在說明中有提到原作者所參考的文章,如下圖






















從關鍵字找到了Randy Gual所寫的一篇教學,教人用C++語言寫出一個簡單的物理引擎,
文章共有4篇。

https://gamedevelopment.tutsplus.com/series/how-to-create-a-custom-physics-engine--gamedev-12715



這4篇文章介紹了許多物理引擎的概念,與相關的物理數學公式,文章尾端都有作者的介紹,他是一個學習資訊科學的學生(原文寫於2013),如下圖。(好厲害的學生啊)


以下是Randy Gaul最後寫出的物理引擎的示範程式影片,從影片中可以看到不同形狀物體之間的碰撞反應(有圓形、矩形與多邊形)



不過有再多的資料與影片還不夠,對我來說,最重要的是找到可以運行的code,這樣我才能依據文章來實際跑code(這是我的學習方式),但是有個問題發生,Randy的C++程式,我一直沒有適當的環境來運行,有試了Visual Studio也不行,我對C++不熟,所以就卡住了。

怎麼辦呢?難道就放棄了嗎?再找看看吧,一定有方法的,果不其然,找到了Philip Diffenderfer用Java做出了這個引擎,而且也有程式放在Github,如下圖

https://github.com/ClickerMonkey/ImpulseEngine



經過了一番努力,終於在Eclipse的環境下,成功的運行Demo的Java程式,這樣我就可以來學習原理了,Oh,Yeah。


看了一些資料與程式後,覺得還是要自己來寫一次,會比較踏實,我比較熟的是python,所以就開始用python + pygame,來把這個學習用的簡易物理引擎來寫一次。因為想要接近原本的程式,所以連需要用到的2d向量與矩陣的部份,也自己寫一次,所以就慢慢的一邊用我破破的Java與C++來學原理,一邊用python寫,同時對照著教學文章,這樣的多次循環,到最後終於完成了python版的程式。

https://github.com/beardad1975/impulse_engine


自己剛用python寫完時,因為python的效能不好,而且我也不會最佳化,效果還好,所以並沒有覺得太高興。不過,神奇的是,後來再去看Scratch版本的物理引擎,發現作者是做原程式的移植,所以程式的流程與函數名稱,都跟原來的很接近,讀起Scratch程式,就容易多了,一下子就能捉到程式的概要,這才了解到,原來之前的努力沒有白費,是會有回報的,差點流下了興奮的眼淚。感謝這中間多位無私分享資料的外國網友,讓我有這種難以想像的學習機會。


由於大致了解了物理引擎的架構,所以把原本的遊戲改成彈珠遊戲也簡單多了。

https://scratch.mit.edu/projects/134193915/

嚴格來說是沒有什麼大不了的,但是遊戲改寫出的那天晚上,一直興奮的睡不著呢!
(想到遊戲背後的這一堆理論)



【運作原理】
由於自己的英文僅到尚可的程度,所以也不確定是否完全了解原本的理論,不過基於分享的精神,還是試著把「IMPULSE衝力2D物理引擎」的運作原理做一個說明。

首先是資料結構的部分,每個物件的資料,都放在一個Rigid body的清單中,Rigid body是物理所稱的剛體,剛體在受力的前、中、後都不會產生變形,這樣的假設可以大大簡化問題(柔體的公式一定更複雜)

Rigid body的資料清單如下,放的都是一些如位置、速度、加速度、質量…等相關的物理量,一個物件的資料就有28項,作者griffpatch把Scratch的清單,當成2維陣列來使用,這樣是一種處理複雜的資料的方法。這個清單是動態的,當使用者加入一個新的物件,就會再增加28個項目資料到這個清單中。(Scratch的資料結構只有一維陣列,這個程式能移植,真是要給griffpatch一個大大的讚,我光用python就寫得很頭大了)




   還有另一個重要的清單,叫做 Manifolds(切觸流形),這個字我之前在學習3D列印時,曾經在一些軟體看過,但不知道是什麼意思。找了半天資料後,我的理解是物體與物體之間碰撞時的接觸面,如下圖:

來源:https://research.ncl.ac.uk/game/mastersdegree/gametechnologies/
如果是兩個3D物體的碰撞,Manifold接觸可能是一個面、一條線或是一個點。而以本文討論的2D物體,Manifold接觸會是一條線或是一個點。這個Manifold的清單,紀錄著兩兩物件碰撞時的碰撞方向、碰撞點、彈性係數、摩擦力…等資訊。




再來看一下物理引擎的主迴圈,由於這是一個示範引擎的程式,了解主迴圈後,就可以知道下手修改的方向。迴圈如下圖(黃色矩形處)



其中最重要的是一些自定義的積木(深藍色),作者的自定積木實作了很多,以下只說明一些重要的自定義積木。


跟使用者操作相關的有Fire!與Spawn Stuff,這兩個積木讓我們可以用滑鼠發射憤怒鳥,或是用1-6數字鍵,新增一些物件。



跟繪圖有關的積木是draw bodies,會畫出所有在Rigid Body清單中的物體。
有使用到 Scratch的畫筆與分身功能。


再來是step這個自定義積木。可別小看這個積木,它可是物理運算的核心。
積木如下圖。


這個step會計算出短暫時間內(如1/50秒),所有物體的移動變化、轉動變化與碰撞反應。 由於所有的物理運算都在step內。以下再針對step內的主要自定義積木做說明。

New Manifold積木主要在做碰撞偵測,看看兩個物體是否有碰撞,如果有的話,把相關的碰撞資訊放在Manifolds清單中,這邊使用到的演算法是SAT(Separating Axis Theorem),可以用來判斷兩個多邊形是否有碰撞

SAT參考資料:https://gamedevelopment.tutsplus.com/tutorials/collision-detection-using-the-separating-axis-theorem--gamedev-169

概念圖如下(簡單來說是,如果能在兩個多邊形之間找到一條分隔的線,則兩者沒有碰撞)


當兩物件有碰撞時,要找出碰撞的接觸點,使用的演算法是Sutherland-Hodgman的clipping,
參考資料:https://research.ncl.ac.uk/game/mastersdegree/gametechnologies/physics5collisionmanifolds/




    再來是Integrate Forces與Integrate Velocities,這兩個積木會把外力轉成加速度,加速度改變速度,速度產生新的位移,當然也有計算轉動的力矩、角加速度、角速度與角位移。相關的概念與牛頓的第1、2 、3運動定律有關。

參考資料:https://research.ncl.ac.uk/game/mastersdegree/gametechnologies/physics1introductiontonewtoniandynamics/
       


在做計算時,是以積分的數值方法,一步步算出位移,雖然用到微積分看起來很嚇人,但是使用尤拉法計算,意外的簡單(缺點是誤差較大)。

有些資料中提到一件有趣的事,說物理引擎能做出一個影片(一個畫面一個畫面step),只是畫面之間的變化,是由物理公式來與使用者的變因來決定的。




     Initialize Manifold這個積木主要是決定出兩碰撞物體的彈性碰撞係數,與摩擦係數。


    再來也是很重要的Apply Impulse,Impulse在物理是衝量,代表是短時間內,一股很大的撞擊力量,造成兩碰撞物體立即改變速度。Randy Gual在他的教學文章列出的衝量公式,如下圖:


參考資料:https://research.ncl.ac.uk/game/mastersdegree/gametechnologies/physics6collisionresponse/
 

    Correct Positions這個積木會修正碰撞物體的位置,讓兩物體儘量不重疊


    Clear Force會把積木轉換過的力與力矩歸零


    主要的程式大致解說至此,這個遊戲可以拿來重覆利用(像library),雖然因scratch的限制麻煩點,但是從主迴圈下手,大致就可以了,再注意一些小細節,其他的物理引擎就照原本運作就可以了。

【結語】

   物理引擎很酷,但是深入了解之後也相當複雜,且牽連到的領域多,有資訊、物理、數學,相關的資料都需要英文的閱讀。但是反過來想,本文所提到的這些知識,都是從網路上獲得,也算是公開的資料,且資料也算很多,也很多外國網友在學習與討論,但是幾乎找不到中文資料,也許這就是外國與我們的差距吧!

另外,自己從小到大的學習中,曾經學到一些相關基礎知識,但最後卻學不下去,如果在學習數學、物理的成長過程中,能有這麼有趣的例子,我一定會認真學習這些基礎學科的。以上是一點小小的感想。












3 則留言:

  1. 我是台灣人,我也自己做了一個脈衝物理引擎,你也可以看看。https://scratch.mit.edu/projects/947245469/

    回覆刪除