[SparkAR] Collision Detection (碰撞偵測)
最近的案子是做一個小遊戲,需要去判斷兩個矩形是否發生了碰撞,甚至是需要判斷「旋轉過的矩形」是否發生碰撞。
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 去接一下,瞬間就能看出端倪。
隨便給兩個 z = 0 的向量算外積,最後法向量一定會落在 z 軸上,會形成一個 x, y 恆為 0 的向量,其中它的 z 軸就是我們要的外積值。
紀錄 + 介紹完兩種碰撞偵測法,以及判斷左右側的兩種數學原理,瞬間意識到原來高中數學真OO是有用的!? 萬萬沒想到,寫起 3D 圖學相關的程式之後,陸陸續續用到越來越多的高中數學。
基本出社會之後都忘得一乾二淨,重新複習這些原理實在折騰,但明確知道這些數學的用途,並且實作出來之後成就感是相當高的。如果當年高中數學能清楚的告訴我們,這些公式代表的幾何意義,可以用在哪? 學起來可能要有目標很多,或許未來人人都會寫遊戲了。(笑)
參考:
左右側判斷,
https://www.twblogs.net/a/5b7f75932b717767c6afc178
https://blog.csdn.net/rocky_shared_image/article/details/8033426
https://stackoverflow.com/questions/1560492/how-to-tell-whether-a-point-is-to-the-right-or-left-side-of-a-line
兩點式,
https://www.youtube.com/watch?v=16jS8MmyvRo
https://tw.clearwatergardenclub.org/217685-how-can-i-find-the-WBKIHH