ゲーム作りとかCGに関わる数学④
今回は線形補間とベジェについて考えてみましょう。
線形補間
初歩的すぎるかもしれませんが、改めて線形補間について考えてみます
仮にA地点の値をa、B地点の値をbとします。そうすると、A～Bの間を1.0としたときに
AとBの間の特定の点Mがあるとして、MはAからBまでを1.0としたときの割合t(0<=t<=1)で表すとします。点Mにおける値をmとすると
$$m=a(1-t)+bt$$
となります。これがいわゆる線形補間です。ただ、これに納得いかないという人のために説明を考えてみました。
直感的に理解する
そもそも線形補間というのは、間の補間が1本の線で補間されるからなのですが、ちょっと直感的に考えてみましょう。この点ＭがちょうどAとB
の中間にあったとします。
ある値とある値のちょうど中間の値を計算したい時はどうするでしょうか？「足して２で割る」ですね。そうすると
$$m=\frac{a+b}{2}$$
ですね。当たり前ですね。
では次にこの点Mと点Aのちょうど中間の点Nにおける値nを考えてみましょう。これまた点Aの値と点Mの値を足して2で割るのですから
$$n=\frac{a+m}{2}$$
mを展開すると
$$n=\frac{a+\frac{a+b}{2}}{2}=\frac{\frac{2a+a+b}{2}}{2}=\frac{3a+b}{4}$$
さらにこれとAの間の値は
$$\frac{a+n}{2}=\frac{a+\frac{3a+b}{4}}{2}=\frac{\frac{4a+3a+b}{4}}{2}=\frac{7a+b}{8}$$
と言った感じで、疑り深い人は各自で計算してもらうとして、図にプロットするとこんな感じ
どうやら各点を結ぶと1本の線になりそうですね。間の値を予測するのに、直線を用いるのは直感にもあってるし、何だか良さそうです。
直線で結べるという事は、傾きがあるという事で、始点A(値=a)と終点B(値=b)とした場合、分母はB-Aで分子はb-aになります。つまり
$$傾き=\frac{b-a}{B-A}$$
仮に間の点Kの値をkとすると、$$k=a+(K-A)傾き=a+\frac{(K-A)(b-a)}{B-A}=\frac{a(B-A)+(K-A)(b-a)}{B-A}$$
ここで範囲の変換を行い、A=0.0、B=1.0とすると
$$k=a+(K-0)(b-a)$$
Aを0、Bを1としているので、上記のKの値は0～1の範囲の任意の実数tで表せます
$$k=a+(t-0)(b-a)=a+t(b-a)=a(1-t)+bt$$
となり、線形補間の式になります。これが結局始点を0.0、終点を1.0としたときの直線の方程式だと分かりますね。
最初に足して2で割る作業をしたときも、分子の係数を足したものと分母は一致して、結局足して１になるようになっています。この線形補間も(1-t)+t=1で足したら1になるようになっているわけです
なお、しれっと「範囲の変換」と書きましたが、もし元のAとBが、A=10,B=25だったようなときはどうするかというと、連立方程式を立てて途中のtを求める事になります。所謂y=ax+bの連立方程式を立てるのですが、xを入力、yを出力とみなすわけです。そうすると
\begin{equation}
\left\{ \,
\begin{aligned}
& 0 = 10a+b \\
& 1 = 25a+b \\
\end{aligned}
\right.
\end{equation}
これを解くと
\begin{aligned}
1 & = 15a \\
a & = \frac{1}{15} \\
0 & = \frac{2}{3}+b \\
b & = -\frac{2}{3}
\end{aligned}
つまり変換式は
$$
y=\frac{x}{15}-\frac{2}{3}
$$
となる。実際にA,Bの値を入れて確かめてみよう。x=10を代入すると2/3が打ち消し合って0になり、x=25を代入すると、5/3-2/3=3/3=1となり1.0となる事が分かります。例えばここで、間の点例えば20を代入すると4/3-2/3=2/3となり、これをtとして用いるわけです。
この「範囲の変換」はあちこちで使用するので、覚えておきましょう。特に-1～+1や、0～1に変換することが多いです。
ともかくこれで線形補間の式に納得がいくようになったかと思います。次にこれを応用してみましょう
手書きで理解する2次ベジェ
まず、紙でもペイントソフトでもエクセルでも自分のプログラムでも何でもいいので、以下のように繋がっている２つの直線を引いて、何分割かして目盛りを引いてみましょう(ここでは10分割しています)
この直線を構成する3点をA→B→Cとします(ベジェ曲線はBを通りません)。そして、A→B、B→Cをそれぞれ線形補間し他点を求め、それを結ぶような線を引いてみましょう。最初はt=0なのでA→Bの線そのものになります。最後はt=1なのでB→Cの線そのものになります。
t=0.5の時はA→Bの中間とB→Cの中間の線になります。
これを変化させながら書き残していくと…
最終的には2次のベジェ曲線と同じになります
つまりベジェ曲線が2つの線形補間の組み合わせで表現できることが視覚的にわかったかなと思います。
参考動画：https://x.com/CTsuchinoko/status/2003290085035569551
参考プログラム：https://github.com/boxerprogrammer/game_cg_math_lesson/tree/main/Bezier
最終的に「あの」2次ベジェ曲線の式
$$M=A(1-t)^2+2B(1-t)t+Ct^2$$
とどう繋がっているか考えてみます。交点をつないでいるように見えますが実際には線形補間の式a(1-t)+btが作った線分をこれまた割合tで結んでいくこととなります。つまり
\begin{aligned}
P = A(1-t)+Bt \\
Q = B(1-t)+Ct
\end{aligned}
そして点Ｐと点Qもtで線形補間してみます。
\begin{aligned}
M = P(1-t)+Qt
\end{aligned}
これを展開
\begin{aligned}
M &= (A(1-t)+Bt)(1-t)+(B(1-t)+Ct)t\\
&= A(1-t)^2+Bt(1-t)+B(1-t)t+Ct^2\\
&= A(1-t)^2 + 2B(1-t)t + Ct^2
\end{aligned}
と言うわけで、2次ベジェの式と一致することが分かるかなと思います。
プログラムにするとこんな感じですね
Position2 QuadraticBazierCurve::GetPosition(float t) const
{
// B(t) = (1-t)^2*P0 + 2(1-t)t*P1 + t^2*P2
float u = 1.0f - t;
return Position2(
u * u * p0.x + 2 * u * t * p1.x + t * t * p2.x,
u * u * p0.y + 2 * u * t * p1.y + t * t * p2.y
);
}
3次ベジェ
最後に3次ベジェについてですが、今度は4点を使用します。ただし間の2点は通りません。
つまり
A,B,C,Dで、実際に通るのはAとDだけです。
どうやるかと言うと、手順は
- A→Bを線形補間(これをPとする)
- B→Cを線形補間(これをQとする)
- C→Dを線形補間(これをRとする)
- P→Qを線形補間(これをMとする)
- Q→Rを線形補間(これをNとする)
- MとNを線形補間(ひとまずこれをKとする)
というわけで、4以降は2次ベジェと同じことが分かりますね
では計算しましょう。
\begin{aligned}
P = A(1-t)+Bt \\
Q = B(1-t)+Ct \\
R = C(1-t)+Dt
\end{aligned}
ここからは4からですね
\begin{aligned}
M = P(1-t)+Qt \\
N = Q(1-t)+Rt \\
K = M(1-t)+Nt
\end{aligned}
ここから展開します
\begin{aligned}
K &= M(1-t)+Nt \\
&= (P(1-t)+Qt)(1-t)+(Q(1-t)+Rt)t \\
&= P(1-t)^2 + 2Q(1-t)t + Rt^2\\
&= (A(1-t)+Bt)(1-t)^2 + 2(B(1-t)+Ct)(1-t)t + (C(1-t)+Dt)t^2\\
&= A(1-t)^3+Bt(1-t)^2 + 2B(1-t)^2t+2C(1-t)t^2 + C(1-t)t^2+Dt^3\\
&=A(1-t)^3+3Bt(1-t)^2+3C(1-t)t^2+Dt^3
\end{aligned}
プログラムにするとこんな感じです
Position2 CubicBazierCurve::GetPosition(float t) const
{
// B(t) = (1-t)^3*P0 + 3(1-t)^2*t*P1 + 3(1-t)*t^2*P2 + t^3*P3
float u = 1.0f - t;
return Position2(
u * u * u * p0.x + 3 * u * u * t * p1.x + 3 * u * t * t * p2.x + t * t * t * p3.x,
u * u * u * p0.y + 3 * u * u * t * p1.y + 3 * u * t * t * p2.y + t * t * t * p3.y
);
}
ここでは説明のために2Dでお話ししましたが、普通の線形補間も、2次ベジェ補間も3次ベジェ補間もただの補間なので、3Dでも扱えます。また、ベジェが線形補間のくみあわせで作れることが分かっているのため、シェーダを書く際にlerpを組み合わせるのもアリだと思います(式が分かってるため、自作関数を作った方が速いとは思いますが)
はい、今年はちょっとボリュームが小さいですが、今年のアドベントカレンダーネタはこれで終わりとします