射影変換の導出式 - RPGツクールと数学のブログ

ゲーム作りでも使うと便利。今回は平面図形の変換についての内容です。

f:id:fermiumbay13:20180814020024p:plain

図形を変形する数学的な方法として、さまざまな変換があります。本記事は射影変換の導出式を提示するのが目的ですが、まず変換にはどんなものがあるか紹介します。

数学的な図形の変換

簡単な変換から順番に紹介していきます。

(1) 合同変換

「位置の移動」「回転」だけを使って変形する変換を合同変換といいます。図形の大きさを変えてはいけません。中学数学で図形の合同を習いますが、その合同です。合同な図形は、合同変換をすることで必ずぴったり重ねることができます。

f:id:fermiumbay13:20180814020954p:plain

(2) 相似変換

合同変換に加えて、「拡大・縮小」をしてもいい変換のことを相似変換といいます。相似な図形は、この変換でぴったり重ねることができます。

f:id:fermiumbay13:20180814022314p:plain

(3) アフィン変換

相似変換に加えて、「伸縮・傾きの変形」もしていい変換をアフィン変換といいます。高校数学に出てくる一次変換に「位置の移動」を認めたものとも言えます。何かこういう、3Dで見てみたぞ的な感じに変換されるのがアフィン変換ですね。任意の平行四辺形を、任意の平行四辺形に変形する変換です。

f:id:fermiumbay13:20180814022229p:plain

一般に、任意の座標 $(x, y)$ がアフィン変換によって $(x',y')$ に移るとき、パラメータ $a, b, c, d, e, f$ を用いて次式で表せます。

$\displaystyle \begin{cases}x' = ax + by + c\\ y' = dx + ey + f\end{cases}$

どう変換されるか、というのがこれらのパラメータにより決まるということですね。文字が6個あるので、3点の座標が決まればパラメータは一意に決まります。

アフィン変換を使うと、正方形と平行四辺形を相互に変換できるので、例えば平行四辺形を扱うのが難しい場合に一旦正方形に変換して扱う、といった使い方ができます。

↓私はこういったパズルゲームを作るときに使いました。

f:id:fermiumbay13:20180814022716j:plain

立体的になっているタイルを選択するとそこに玉を置くことができるのですが、タイルは画面上では平行四辺形として表現されているので、平行四辺形内部をクリックしたかどうかを判定する処理が必要になります。難しいですよね。

そこで画面をクリックした瞬間に、アフィン変換を使ってこれらの平行四辺形を内部的に正方形に変換するのです。どこをクリックしたのか、という点も同時に同じアフィン変換を施します。するとこれは正方形内部をクリックしたかどうかの判定問題に落ちるわけです。正方形の中をクリックしたかどうかは座標の単純な大小比較で出来ますから、簡単に実装することができますね。

このように、複雑な図形を単純な図形に変換して問題を簡単にする、という目的でもこれらの変換は使えます。

(4) 射影変換

アフィン変換は平行四辺形に変形することはできますが、例えば台形には変換できません。任意の四角形を任意の四角形に変形することができる変換が射影変換です。

f:id:fermiumbay13:20180814020024p:plain

要するにこの変換さえ使えるようになれば、平面図形の変換はだいたい可能になります。*1

一般に、任意の座標 $(x, y)$ が射影変換によって $(x',y')$ に移るとき、パラメータ $a, b, c, d, e, f, g, h$ を用いて次式で表せます。

$\displaystyle \begin{cases}x' = \frac{ax + by + c}{gx + hy + 1}\\ y' = \frac{dx + ey + f}{gx + hy + 1}\end{cases}$

アフィン変換それぞれの変換式にさらに分母が増えた形をしています。文字が8個あるので、4点の座標が決まればパラメータは一意に決まります。

任意の四角形 $(x_{1}, y_{1}), (x_{2}, y_{2}), (x_{3}, y_{3}), (x_{4}, y_{4})$ が任意の四角形 $(x'_{1}, y'_{1}), (x'_{2}, y'_{2}), (x'_{3}, y'_{3}), (x'_{4}, y'_{4})$ に変形されるものとして連立方程式を解けば、上記パラメータは解けるはずですね。でも8元連立方程式を解く必要があるので、このまま導出式を求めるのは中々大変です。導出方法を考えて見ます。

射影変換の方針

f:id:fermiumbay13:20180814024840p:plain

↑このように直接変換するのは大変なので、↓2段階に分けて考えます。

f:id:fermiumbay13:20180814032515p:plain

変換元の図形を一旦正方形に変換して、その正方形を変換先の図形に変換するのです。射影変換を2回行うわけですが、そうすると導出式それぞれは簡単なものになるはずです。初めの変換を射影変換A、次の変換を射影変換Bとして、それぞれのパラメータ導出式を求めてみます。

射影変換Aのパラメータ導出式

四角形 $(x_{1}, y_{1}), (x_{2}, y_{2}), (x_{3}, y_{3}), (x_{4}, y_{4})$ を、正方形 $(0, 0), (1, 0), (0, 1), (1, 1)$ に、パラメータ $a, b, c, d, e, f, g, h$ を用いて射影変換するものとします。変換Aの方が難しい式になります。

f:id:fermiumbay13:20180814025537p:plain

このままでは複雑なので、記号を定義して簡潔を目指します：

原点にずらした座標： $\displaystyle \begin{cases}X_n = x_n - x_1 \\ Y_n = y_n - y_1 \end{cases}$

外積： $\displaystyle {\bf P}_i \times {\bf P}_j = X_iY_j-X_jY_i$

よく出てくる途中式を次の定数でそれぞれ表します：

$\displaystyle \begin{cases} \alpha = ({\bf P}_4 \times {\bf P}_2) - ({\bf P}_3 \times {\bf P}_2) \\ \beta = ({\bf P}_4 \times {\bf P}_2)x_3 - ({\bf P}_3 \times {\bf P}_2)x_4 \\ \gamma = ({\bf P}_4 \times {\bf P}_2)y_3 - ({\bf P}_3 \times {\bf P}_2)y_4 \end{cases}$

各パラメータを求めていきます。順番に計算していき、求まった定数を使って次の定数を求めるという方法です：

$\displaystyle g = \frac{({\bf P}_4 \times {\bf P}_3)(Y_3 \gamma - y_2 Y_3 \alpha)-({\bf P}_2 \times {\bf P}_3)(Y_3 \gamma - y_4 Y_3 \alpha)}{({\bf P}_4 \times {\bf P}_3)(y_2 Y_3 \beta - x_2 Y_3 \gamma)-({\bf P}_2 \times {\bf P}_3)(y_4 Y_3 \beta - x_4 Y_3 \gamma) }$

$\displaystyle h = -\frac{\alpha + \beta g}{\gamma}$

$\displaystyle a = \frac{Y_3\gamma-y_2Y_3\alpha - (y_2Y_3\beta - x_2Y_3\gamma)g}{({\bf P}_2 \times {\bf P}_3) \gamma}$

$\displaystyle d = \frac{({\bf P}_4 \times {\bf P}_3)Y_2}{({\bf P}_4 \times {\bf P}_2)Y_3}a$

$\displaystyle b = -\frac{X_3}{Y_3}a$

$\displaystyle e = -\frac{X_2}{Y_2}d$

$\displaystyle c = -ax_1-by_1$

$\displaystyle f = -dx_1-ey_1$

これで8つのパラメータが求められるので、次の射影変換の式で任意の座標 $(x, y)$ が座標 $(x',y')$ に変換されます：

$\displaystyle \begin{cases}x' = \frac{ax + by + c}{gx + hy + 1}\\ y' = \frac{dx + ey + f}{gx + hy + 1}\end{cases}$

上記の式で射影変換は基本的にできますが、横に伸縮しただけのような単純な射影変換の場合、導出式の分母が0になるなどして求められない場合があります。本来なら場合分けをして万能な式にすべきなのですが、ややこしくなりそうなので、そういう場合はアフィン変換を使うなどして回避するようにしてください＠＿＠

射影変換Bのパラメータ導出式

正方形 $(0, 0), (1, 0), (0, 1), (1, 1)$ を、四角形 $(x_{1}, y_{1}), (x_{2}, y_{2}), (x_{3}, y_{3}), (x_{4}, y_{4})$ に、パラメータ $a, b, c, d, e, f, g, h$ を用いて射影変換するものとします。変換Bは変換Aの逆変換に相当します。

f:id:fermiumbay13:20180814031721p:plain