前言
先說接下來這段跟本文內容沒什麼關聯，更多的是自己的心得碎碎念。
去年很榮幸有機會參加到一個遊戲物理的線下講座，由FB社團Unity應用領域主辦，講者是版上著名的頑皮狗工程師cjcat/Allen Chou大大。
我覺得程式背景的遊戲開發者都應該去看看他的自傳和所有ptt GameDesign版上的文章:
我在大學時讀到他的這些生涯心得分享後有如被灌了甚麼超級雞湯一樣，不斷冒出國外讀書應徵大遊戲公司的想像，我覺得他的故事如此勵志的一大原因是他根本不是本科系畢業的卻能有如此成就，會讓你有種就算現在從零開始也完全沒問題的想像。
但你根本不會想到人家在大學讀電機的期間就有辦法投稿全英文的遊戲引擎教學文章以及強大的語言能力差距
說來也真神奇，就在我發現cj大大的文章後不過幾天就出現這個遊戲物理講座的消息。
所以會參加這個講座可能有9成的理由都只是因為憧憬，在這之前我對於遊戲物理根本也沒太多的想法。
因為主流遊戲引擎都馬內建好物理引擎了，何況就算要自己寫遊戲引擎也幾乎都是用現成的lib，像Unity和Unreal其實也都只是porting用別人現成的物理引擎。
不過當時就有一種學習引擎底層才算是遊戲工程師的抱負，就抱著試試看的心情報名。
看了一下報名表單，問題來了，表單內容要求要有一定的基本物理學知識，但學校的物理課離我實在太久遠了。
首先我大學的資工系根本沒物理必修，再者我讀高職的物理課也就只有高一還是高二有上過而已。
不過好險報名的日期距離當下有兩週時間，以及在我朋友的慫恿兼鼓勵之下，覺得兩週時間應該夠學到基礎程度，於是就找了台大的開放課程影片普通物理學-張寶棣來看。當下估計是到第八章左右就足夠了，所以規劃一天看3片就好。
最後兩週過去是的確補完了一些基本概念跟公式了，其實後面幾章都在講題目也沒看完，但我自己覺得應該是夠用了。
讀過物理後也的確讓我對接下來這個講座更有自信能學到東西。
講座是三週分三次，當下學習完回去也能複習投影片和看原始碼。
投影片跟專案原始碼都有放到Github
結論是我真的蠻感謝這個講座，我自己學過之後對開發上的幫助有:
- 本來我在之前是完全看不懂 Unity的Physics2D設定中的那堆參數到底有什麼鬼意義，網路上的討論資料也少得可憐，就只能亂調亂調完全不知道怎麼優化。學過之後再加上有去研究Box2D的原始碼，那些設定值的意義就能理解了
- 當然也接觸過講座我才有勇氣去研究Box2D的原始碼以及了解到關於遊戲物理的用詞、關鍵字與領域。
- 我也沒想到現在專案真的有用上這項技術 ─ 在Unity內刻一個Partial Physics Simulation。
寫著寫著有點離題先回來，總之
我在學習遊戲物理，有鑑於網路上的中文資料真的很少很少，真的有做深入分析教學的就Allen Chou大大的blog，但也不是中文資料，作為中文圈的新手入門還是有些難度。
這篇文會介紹遊戲物理引擎的運作流程與各階段的行為概述，深入的實作方法當然就不會講解了。
就只是當個開頭，真要了解各階段的實作方法可以查查這些關鍵字以及演算法。
預計之後應該會繼續寫幾篇紀錄自己學習遊戲物理的系列文章，希望能持續下去。
本篇很多來源是取自Game Physics: Introduction & Acknowledgements
基本名詞定義
- Rigidbody 剛體: 不會變形的固定物體，所有質點到中心的距離都不會改變，一般物理引擎都是以剛體為最基礎的運動物件，下文會直接用Body來代替。
- Collider: 剛體的一部份，可碰撞的形狀。剛體如果不帶有Collider則它就只是一個質點，Collider就相當於剛體本身的形狀。一個剛體可有多個Collider組成。
- Collision 碰撞: 當兩個Collider有交疊時我們會稱之為碰撞。
- Contact Point 接觸點: 當兩個Collider發生碰撞會產生一個以上的接觸點，之後都會直接簡稱Contact。
- Contact Manifold: 收集兩個Collider之間的所有Contact的一個集合，它本身算是紀錄兩個collider之間的交疊(intersection)情形的資料
再來因為我主要的學習來源都是取自Box2D，它是一套開源的2D物理引擎，Unity的Physics2D也是直接porting它的。
所以很常會提到它的作者Erin Catto(現任暴雪的遊戲物理工程師)的演講內容以及投影片。
主流程
遊戲物理引擎在一次物理更新(Step)中會做的整個流程:
可能不是所有物理引擎都是這套流程，不過至少Box2D是走這條。
Broadphase
這階段主要目的是 找到所有可能發生碰撞的組合(Pair) ，所以會用比較粗略但高效率的演算法把不可能發生碰撞的物件組合剔除，常見的有動態AABB Tree、Quad Tree/Octree、Kd Tree、BSP Tree等等。(Box2D使用動態AABB Tree)
如果沒做Broadphase，那就是拿到所有Body彼此之間的組合，也就會有個組合，這又稱為N-squared broadphase。
Broadphase相關內容:
Collision Detection (Narrowphase)
這個階段就是要真正確定兩物件是否有碰撞。
何謂碰撞？粗略的定義就是兩個Collider有沒有重疊。
理論上這階段只在乎有沒有重疊，也就是一個True或False的答案而已。
不過為了後續resolve碰撞結果，通常這裡的演算法都會支援輸出額外資訊如:
- 最小穿透量(Minimum Translation Vector)或稱Penetration :離開碰撞的最短路徑
- 碰撞點(Contact point): 兩形狀穿透最深的兩個點，通常相減就是最小穿透量
一般物理引擎常見的做法是會分成 Primitive case 和 Convex polygon case 來處理所有情形:
- Primitive case: 準備好所有基本形狀的碰撞檢測，而且各種組合的碰撞檢測也要處理。
- 舉例來說，這裡只準備Box和Circle兩種形狀，就會需要有這些演算法:
- Box vs Box
- Circle vs Circle
- Box vs Circle
- 舉例來說，這裡只準備Box和Circle兩種形狀，就會需要有這些演算法:
- Convex polygon case: 凸多邊形的情況有蠻多演算法可以使用，常見的有SAT和GJK，主流應該是GJK+MPR，可以檢測高效率任何凸多邊形的碰撞且拿的到碰撞點與穿透量。
- Concave polygon case: 凹多邊形通常會被decomposite成多個凸多邊形的組合來算。
Continuous Collision Detection
這個階段的一大難題之一，簡述問題就是
「當Body速度過快導致兩次更新之間直接穿透了中間的物件而沒有檢測到碰撞」
也有分各大門派的解法，Box2D的解法是: Physics for Game Programmers; Continuous Collision by Erin Catto
Collision Detection相關內容:
- 遊戲中的碰撞檢測Collision Detection - 實作SAT
- Collision Detection Using the Separating Axis Theorem
- Computing Distance using GJK — GDC 2010 - Box2D作者 Erin Catto做的關於GJK的手把手教學，步驟超細，非常簡單易懂。
- Implementing GJK (2006) - By Casey Muratori - 強推，建議先有看完上面那篇，對GJK的基本了解再看。主要是以程式角度實作GJK，影片一直嘴論文作者寫了一堆學術爛方法導致閱讀不易，其實GJK並沒有那麼難，重點是影片裡面提到不少實務上的優化方法。
- Game Physics: Collision Detection – GJK
- Real-Time Collision Detection - 遊戲物理聖經本之一，整本書都在講Collision Detection的各種演算法。
Resolution
這個階段是在解決(Resolve)各種約束(Constraint)，舉例來說兩物件的碰撞就算是一種Contact Constraint，而解決它就可以讓兩物件不再碰撞。
約束(Constraint)
Constraint之於Physics如同Shader之於Graphics。
所有物理效果都仰賴Constraint來達成，若想要做出自己的物理效果也可以仰賴建構Constraint來達成。
可以想像成，物理世界中有各種約束，
基本款的碰撞約束代表的是「兩個Collider之間不能重疊」。所以當兩者重疊了，這個約束就被違反了。
也因此，解碰撞就是要解Contact Constraint。
又以Joint為例，假設是一般的Fixed Joint(Weld Joint)，他的約束就是「兩個anchor必須在同一個點上」。
假設世界中這兩個約束都解決了(Resolved)，那代表兩者的Collider沒有重疊但兩者的anchor是在同一個位置上。
又Collider沒重疊又anchor重疊聽起來很矛盾，所以一般情況下當你用Joint連起兩物件時都會預設取消掉兩者的碰撞檢測，會把雙方當作沒有撞到彼此也就不需要解Contact。
所以中心思想就是「當物理世界中所有約束都成立的情況下，整個世界的物理運作就是正確的」。
Constraint Solver
解開約束有很多方法，但這裡的門派就有點五花八門了，我只有研究過Erin Catto的方法，所以就只介紹他的方法Sequential Impulse。
關於Sequential Impulse的教學，我很推薦直接看Allen Chou這個中文教學影片遊戲物理約束系列
我之後應該會寫一篇自己學習後對Sequential Impulse的理解，這篇就先點到為止。
Constraint & Sequential Impulse相關內容:
- Game Physics: Resolution – Constraints & Sequential Impulse - 跟上面的中文教學影片的內容一樣的英文文字版本
- Game Physics: Resolution – Contact Constraints - 跟上面的中文教學影片的內容一樣的英文文字版本
- Fast and Simple Physics using Sequential Impulse - Erin Catto 在GDC2006的投影片
- Physics for Game Programmers: Understanding Constraints - Erin Catto 在GDC2014的影片
Velocity Constraint & Position Constraint
約束也有分種類，在Box2D中有速度約束(Velocity Constraint)也有位置約束(Position Constraint)。
速度約束自然是在約束剛體的速度，位置約束就是在約束剛體的位置。
舉實際例子來看，假設兩物件碰撞了，會希望發生兩件事:
- 兩物件不再碰撞(交疊)
- 兩者因為產生彈性或非彈性碰撞而改變速度
1.的情況雖然速度約束通常也能解決，但直接用位置約束來強迫兩者分開會更有效率。
2.的情況就完全要仰賴速度約束了。
Integration
在解完Velocity Constraint之後，我們會需要讓Body套用它的Velocity，使其修改Body的Transform來形成運動。這個過程就是把速度積分成位置位移量，也就是Velocity Integration。
主流只模擬Position和Rotation，所以存有Linear Velocity和Angular Velocity，但就算要模擬Scale運動也是可行的(不過這可能就不符合剛體物理的定義了)。
另外加速度或加加速度也是可以模擬的，就看這個物理需要多精準。
這方面的積分方法也有不少選擇，Box2D是用Semi-implicit Euler method，其他還有像是Verlet method也是常看到的選擇。
積分方法的選擇會影響到運動路徑的準確性、穩定度當然還有效能問題，另外也與timestep的可接受變化程度息息相關。常見的作法都會讓timestep為一個固定值，這樣在各個積分方法上都會相對穩定。
Integration相關內容:
- Math for Game Developers - Spaceship Orbits (Semi-Implicit Euler)
- Math for Game Developers - Verlet Integration
結論
可以發現各個階段的學問都不少，要完全造出整套物理引擎的難度是很高的。
我寫下這篇文是希望能當作一個Roadmap，當我之後對哪一部分有實作需求時就可以直接針對那方面來學習。
事實上我自己有實作過的範疇也幾乎都是Resolution階段，之後有機會可以來寫一篇我在Unity上刻的Partial Physics Simulation的實作心得。
下一篇我應該會寫Sequential Impulse，以及會把Box2D的各種Constraints分析一輪。
本篇文如果有任何錯誤的見解麻煩告知，我會盡快修正