重心座標概念理解與實作

關於本篇

重心座標(Barycentric coordinate)是Dowen應用於地形碰撞偵測上的數學,此外在OpenGL的Tesselation中也會用到,如此重要的座標概念,幾乎沒有中文文獻,或許是因為容易理解,不過對Dowen來說還是花了不少時間。

重心座標 (Barycentric coordinate)

國中的時候我們教過,三角形中腺交於一點稱為重心,而重心公式大家應該都還記得就是三點相加後除以三。

$G = \frac{1}{3}A + \frac{1}{3}B + \frac{1}{3}C$

而其中的三個$\frac{1}{3}$,化為向量就是$\left(\frac{1}{3},\frac{1}{3},\frac{1}{3}\right)$,而重心座標系的性質即是三個參數相加為一。

正式定義

重心座標系中,定義每個點各自擁有一個比例參數$\lambda$,其各點乘上比例參數可以完美地表達該點座標。而這樣的比例參數化為向量就是重心座標系中的座標。以下面這張示意圖來看,要表達點$P$,用重心座標系的表示法就會如下:

$P = \lambda_A A + \lambda_B B + \lambda_C C$

在國中時,通常會給各個線段的比例與一些值,但實際上到了圖學中,我們所知道的反而是$A$,$B$,$C$,$P$,然後要求出各個比例參數,看起來很不可思議,但是接下來我們會利用向量來解決這樣的問題。

比例參數

首先引入下方這張圖,代表我們會使用到的概念:

那麼$P$點的表達示如下:

$P = A + u \cdot (C-A) + v \cdot (B-A)$

然後以向量表示且將A位移後:

$P - A = u V_0 + v V_1$

由於這個公式中有兩個未知數$u$,$v$,因此需要兩條公式才可以求解,因此利用向量的內積,產生兩條式子。

$$\begin{cases} V_2 \cdot V_0 = u V_0 \cdot V_0 + v V_1 \cdot V_0 \\ V_2 \cdot V_1 = u V_0 \cdot V_1 + v V_1 \cdot V_1 \end{cases}$$

整理過後得到解果如下:

$$u = \frac{(V_1 \cdot V_1)(V_2 \cdot V_0)-(V_1 \cdot V_0)(V_2 \cdot V_1)}{(V_0 \cdot V_0)(V_1 \cdot V_1) - (V_0 \cdot V_1)(V_1 \cdot V_0)}\\ v = \frac{(V_0 \cdot V_0)(V_2 \cdot V_1)-(V_0 \cdot V_1)(V_2 \cdot V_0)}{(V_0 \cdot V_0)(V_1 \cdot V_1) - (V_0 \cdot V_1)(V_1 \cdot V_0)}$$

其化為程式最佳寫法如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
// Compute vectors        
v0 = C - A
v1 = B - A
v2 = P - A

// Compute dot products
dot00 = dot(v0, v0)
dot01 = dot(v0, v1)
dot02 = dot(v0, v2)
dot11 = dot(v1, v1)
dot12 = dot(v1, v2)

// Compute barycentric coordinates
invDenom = 1 / (dot00 * dot11 - dot01 * dot01)
u = (dot11 * dot02 - dot01 * dot12) * invDenom
v = (dot00 * dot12 - dot01 * dot02) * invDenom

回到原本說需要有三個比例參數。為什麼只剩下兩個?讓Dowen在往後推幾步,就會有所明瞭。

第一步 將向量換回座標:

$V_2 = u V_0 + v V_1$

第二步 展開,並將$A$移回去:

$$\begin{aligned} P &= A + u \cdot C - u \cdot A + v \cdot B - v \cdot A \\ P &= (1 - u - v) \cdot A + u \cdot C + v \cdot B \\ P &= \lambda_A A + \lambda_B B + \lambda_C C \end{aligned}$$

提取出三個$\lambda$成為$(\lambda_A ,\lambda_B, \lambda_C)$,就取得重心座標系的座標了。

而要換成我們一般直角坐標就是利用$P = \lambda_A A + \lambda_B B + \lambda_C C$,就可以得到原座標。

小結

本篇從直角坐標系推倒出重心座標系,又從重心座標系轉回直角坐標系,直觀上不出什麼有用的價值,但是在圖學中地形上,我們有一個三角形與一個缺少高度的XZ座標或說UV座標,做法是只看XZ平面,算出測試座標在XZ平面上的哪一個重心座標系,利用重心座標系在三角形平面上的比例將頂點三點的高度做轉換,即可獲得3D直角坐標系的高度座標,即可完成地形的碰撞偵測。

參考資料:Point in triangle test