[SparkAR] Collision Detection (碰撞偵測)

Lastor

Published in

Code 隨筆放置場

11 min readMay 26, 2021

最近的案子是做一個小遊戲，需要去判斷兩個矩形是否發生了碰撞，甚至是需要判斷「旋轉過的矩形」是否發生碰撞。

SparkAR 本身並不是遊戲引擎，不像 Unity 那樣幾乎都幫你做好了，只要勾選幾個設定，決定好碰撞物跟被碰撞物，以及碰撞精度，其他 Unity 自己會算，根本不用自己手刻。

如今，碰撞算法居然要自己寫!? 這一瞬間真的難倒我了，還好公司的 Unity 工程師前輩協助找到了公式，幫忙寫出了演算法，不然這「旋轉矩形」的碰撞還真的不會。案子提交之後，抽出了一點時間深入地去研究一下這算法的原理，並在此紀錄一下。

Google 搜尋碰撞偵測之類的關鍵字，可以查到有很多文章，透過各種不同的原理來實現碰撞偵測的目的。這邊我只摸懂了兩種，所以也只簡單介紹這兩種的原理 (這名子是我自己取的)：

交疊法
左右側法

※ 下面皆以 z = 0 的 2D 空間為前提來探討

交疊法

交疊法的原理相當單純，應該是直觀上最好理解的一種做法，就是判斷兩個矩形是否發生重疊。交疊法是單純計算一個點的 (x, y) 是否介於另外兩點之間，判斷範圍會變成物件的 Bounding Box。所以這個方式無法判斷「旋轉的矩形」。

可以先簡化成一維世界中，一個 point 是否與一條 line 發生交疊。只要判斷 x 是否介於 line 的兩點之間即可。

// JavaScript
const isHit = (x1 < x) && (x < x2)

而一個矩形會有 4 個 vertex，要檢查平面中的一個 point 是否撞到這個矩形，就利用上述的方式，個別判斷 point 的 x 軸是否交疊於矩形的 x 範圍，以及 y 軸是否交疊於矩形的 y 範圍，就能得知。

function checkHit(point, rectangle) {
  const {x, y} = point
  const {x: x1, y: y1} = rectangle.pointLT // 取左上的點
  const {x: x2, y: y2} = rectangle.pointRB // 取右下的點  const isXIn = x1 < x && x < x2
  const isYIn = y1 < y && y < y2
  return isXIn && isYIn
}

要得知一個矩形的範圍，只要知道他的左上跟右下的點，就可以知道這個矩形的 width 與 height，進而圈出整個矩形。

更進一步，要判斷兩個矩形是否交疊，就把這個概念多做一輪，判斷一個矩形的「left, top, right, bottom」是否交疊於另一個矩形，再把目標跟自身反過來再做一次，也就是 4 x 2 次。上下左右進行 or 判斷，最後再把兩個矩形的結果做 and 判斷即可。

由於是重複性的工作，這邊就不寫了。

左右側法

由於上面的交疊法無法判斷旋轉矩形的碰撞，所以就得另尋出路。這個做法的原理，是利用數學公式來判斷一個 point 是位於一條 line 的左側還是右側。

一條 line 其實是有方向性的，把一條線顛倒過來，對他而言的左右側也會跟著反轉。因此，就能利用這個特性判斷出一個 point 是否位在兩條 line 之間。

我們只要將兩條 line 圍出一個範圍，顛倒其中一條線，使其左右反轉，就能判斷出 point 是在 line 的外側還是內側了。

接下來就與上面的交疊法相同，判斷完 x 方向之後，再判斷 y 方向，就能知道是否交疊。這個做法由於是判斷左右側，所以適用於「旋轉的矩形」。

知道原理之後，就是 The Magic Math Time 了。要判斷一個 point 在一條 line 的哪一側，目前我知道的作法有二：

1. 使用直線方程式 (linear equation)
2. 使用向量外積(叉積 cross product)

不知各位是否記得高中數學的直線方程式，亦或是向量呢……?

使用直線方程式

這邊先介紹原理比較好懂，但算式比較複雜的直線方程式。也就是以前學過的，在笛卡爾座標系上，用來表示一條直線的式子。

# 直線方程式
# 兩點式先假設有三點, A(x1, y1), B(x2, y2), C(x, y)一般式: Ax + By + C = 0
點斜式: y = Ax + B
兩點式: (y - y1) / (x - x1) = (y2 - y1) / (x2 - x1)

國高中數學最常使用到，也是最重要的是點斜式，因為這式子對人類來說比較簡單好懂，其中點斜式的 A 表示直線斜率。這邊單純只是把點斜式列出來，但我們並沒有要用，實際要用的是另外兩個。

一般式是做這個計算主要使用的方程式，直線方程式既然是代表一條直線，也就是我們把一個點 P(x, y) 帶進去，如果符合這式子，最後等於 0，就表示這個 P 位在這條線上。

如果帶入後得到的數大於 0，也就視同在笛卡爾座標上把整條線往右邊推，也就表示這個 point 位於這條線的右側。反之，如果小於 0，則表示在線的左側。

// 假設目標點 P(x, y) 帶入方程式
const result = Ax + By + C
if (result === 0) "在線上"
if (result > 0) "在右邊"
if (result < 0) "在左邊"

知道這個直線方程式怎麼用之後，得解決另一個問題，就是那條線的方程式該怎麼求? 要寫 function 的話，勢必三個點數值都是未知的，也就得用兩點 A(x1, y1)、B(x2, y2)，來求出直線方程式。

這邊就是要利用上面提到的「兩點式」，兩點式的主要作用就是已知兩點的情況，求直線。

(何謂兩點式，可參考最下方的連結)

# 用兩點式換算, A(x1, y1), B(x2, y2), C(x, y)=> (y - y1) / (x - x1) = (y2 - y1) / (x2 - x1)
=> (y - y1)(x2 - x1) = (y2 - y1)(x - x1)
=> y(x2 - x1) - y1(x2 - x1) = x(y2 - y1) - x1(y2 - y1)
=> x(y2 - y1) - y(x2 - x1) - x1(y2 - y1) + y1(x2 - x1) = 0
=> x(y2 - y1) - y(x2 - x1) - x1y2 + x1y1 + y1x2 - y1x1 = 0
=> (y2 - y1)x + (-(x2 - x1))y + (y1x2 - x1y2) = 0# 可推導出一般式的格式 Ax + By + C = 0, 得:
A = y2 - y1
B = -(x2 - x1) = x1 - x2
C = (y1 * x2) - (x1 * y2)# 最終取得 lineAB 方程式
(y2 - y1) * x + (x1 - x2) * y + (y1 * x2) - (x1 * y2) = 0

取得直線方程式之後就可以寫成 function，將三個點帶入了。要注意的是直線具有方向性，將 A 與 B 的順序顛倒，就會得到顛倒的直線。

/**
 * pointA 與 pointB 構成 lineAB
 * pointC 為要判斷的 source 點
 */
function calcSide(pointA, pointB, pointC) {
  const {x, y} = pointC
  const {x: x1, y: y1} = pointA
  const {x: x2, y: y2} = pointB
  return (y2 - y1) * x + (x1 - x2) * y + (y1 * x2) - (x1 * y2)
}const result = calcSide(a, b, c)
// result > 0, 在右側
// result === 0, 在線上
// result < 0, 在左側

最後只要將矩形 A 上的 4 個點分別與矩形 B 上的 4 條線做判斷，就可以知道是否發生碰撞。

使用向量外積(叉積)

上面的方法是基於直線方程式，但是公式比較長，很難記憶。另一種方法是利用向量外積的特性來判斷。

首先要先了解外積的幾何意義，兩個在同一平面上的向量 P 與 Q，對其做外積 P X Q，將會得到一個新的向量。而這個向量其實就是 3D 裡面的法線向量。其垂直於該平面。

既然是法線 (Normal)，那就有分正面與反面，分別是 +z 的法線，以及 -z 的法線，去判斷正負的話，就能間接知道 C 點是在左邊還是右邊。

外積公式也跟直線方程式一樣，會有一個值，我們一樣是透過判斷該值，若大於 0 則在順時針側、小於 0 則在逆時針側、等於 0 就是在線上。跟直線方程式類似，可以假設有三個點 A、B、C，其組成直線的是 lineAB ，改成向量也就是 vectorAB。

要算外積需要兩個向量，而另一個向量就用 A 與 C 生出 vectorAC 來計算，我們可以透過後者的 (x, y) 減去前者的 (x, y) 得到該向量。

最後可以根據外積值得知，這個面是正向還是反向，也就是根據 ABC 圍成的面，C 在右邊或在翻過去變到左邊的概念。

// 這邊用陣列來表示向量矩陣, A(x1, y1), B(x2, y2), C(x, y)
[
  (x2 - x1), (y2 - y1), // vectorAB
  (x - x1), (y - y1),   // vectorAC
]cross = (x2 - x1)*(y - y1) - (y2 - y1)*(x - x1)if (cross > 0) 在3維順時針方向, 左側
if (cross < 0) 在3維逆時針方向, 右側
if (corss === 0) 表 C 在 AB線上, 不構成平面, 沒有外積

這邊也跟直線方程式一樣，將 A、B 顛倒過來代入，就可以得到一個反向的向量。

從這可以看出，向量外積的公式比起直線方程式要好記憶的多，只要能理解比較抽象的幾何意義，就可以用相對簡單的公式來判斷 point 是在 line 的哪一側。

而大多 3D runtime 環境，對於向量相關的計算都有提供現成的 API 可以用。例如 SparkAR 就有現成的內積 Reactive.dot() 與外積 Reactive.cross() 。

function calcSide(pointA, pointC, pointC) {
  // 先分別做出兩個向量 AB, AC
  const vectorAB = Reactive.vector(
    pointB.x.sub(pointA.x),
    pointB.y.sub(pointA.y),
    pointB.z.sub(pointA.z), // 位在 XY 平面, z 必為 0
  )
  const vectorAC = Reactive.vector(
    pointC.x.sub(pointA.x),
    pointC.y.sub(pointA.y),
    pointC.z.sub(pointA.z), // 位在 XY 平面, z 必為 0
  )  // 然後就可以直接調用外積的函式了
  return vectorAB.cross(vectorAC).z
}

但要注意的是，外積實質求得的還是一個 vector，而非 Scalar，所以返回值會是一個 vector，而不會像上面直接套公式算出一個值。可是我們最終要判斷的是那個值是否大/小於 0，那要如何從法向量 vector 取出那個純量值呢?

其實很單純，將這一段改成 Patches 去接一下，瞬間就能看出端倪。