在碰撞檢測中可以分為兩個階段 Broad-Phase 和 Narrow-Phase,在 Broad-Phase 中先進行粗略的篩選可能碰撞的物體,之後才會在 Narrow-Phase 做精細的計算判斷兩物體是否產生碰撞。

為何需要分為兩個階段進行?假設場景中有兩顆球在移動,如果要判斷兩球是否產生碰撞,一顆球只需計算和另一顆球的碰撞,若有三顆球則變為兩次,以此類推若有 N 顆球則每顆球需要計算 N-1 次,計算複雜度為 O(N2)\mathcal{O(N^2)},這樣的計算量顯然是不能使用的,因此需要 Broad-Phase 先對物體進行篩選。

在 Broad-Phase 通常會先將物體簡化為包圍盒,常見的包圍盒有 AABB(Axis-Aligned Bounding Box)、OBB(Oriented Bounding Box) 等,同時使用四叉樹(QuadTree)、BVH(Bounding volume hierarchy) 等技術將物體所在的空間作分割達到減少計算量的目的。

本文將介紹 AABB、OBB 這兩種包圍盒。

閱讀全文 »

本文將以官方提供的範例 AutoPong 為參考資料,從零開始建立範例中的程式碼,並在內容加入一些變化,將包含以下部分:

  1. 設定畫面尺寸
  2. 製作球和方塊
  3. 移動球
  4. 移動方塊
  5. 球和方塊的碰撞
閱讀全文 »
0%