リアルタイムCGの演算について考える

はじめに

こんにちは。
代表の釣崎です。

2020年に書いて以来の５年ぶりの登場でございます。
tec.tecotec.co.jp

その昔、といっても10年くらい前まで社内wikiたるものがあり、
そこでかつて展開されていた3D部という社内部活動の中で2013年に私が書いていた記事を引っ張り出してきてくれたスタッフがいて、そのままここで記事化することにした。

今や家庭用ゲームと言えばレンダリングCG主体、リアルタイムCGと言えばUE5でもUnityでもその剛体の物理演算はハードウエアに極めて近いレイヤーで内包されており、こんなロジックを意識することは微塵もないのだが、１フレームの間に何が起きているのか考えてみるのは非常におもしろいものだ。

目次

球の線形発射について

宇宙空間のようにエネルギーが減衰しない状況において、 \ (x_0, y_0, z_0) \ の位置にある点がベクトル \ (1, 2, 3) \ の向きに飛んでいく場合を考える。

x = x0;
y = y0;
z = z0;
vx = 1;
vy = 2;
vz = 3;

while(1)
{
    /* 画面が毎フレーム無限にリフレッシュするとします */

    x = x + vx;
    y = y + vy;
    z = z + vz;

    refresh();
}

球が壁にぶつかるとき（その1）- 平面の表現 -

学校では、点 \ \mathrm{P} \ (x_p, y_p, z_p) \ を通り、法線ベクトルが \ (a, b, c) \ の平面の方程式は

\large{ \begin{eqnarray} a \left(x - xp \right) + b \left( y - yp \right) + c \left( z - zp \right) = 0 \end{eqnarray} }

と習ったと思うが、3Dのユークリッド空間をプログラムする上では以下のように考える。

平面が2つの異なるベクトル \ (x_1, y_1, z_1) \ 及び \ (x_2, y_2, z_2) \ を含む点 \ \mathrm{P} \ によって構成されると仮定する場合、平面の表現方法は以下のようになる。

\large{ \begin{eqnarray} \begin{pmatrix} x \\ y \\ z \end{pmatrix} = s \begin{pmatrix} x_1 \\ y_1 \\ z_1 \end{pmatrix} + t \begin{pmatrix} x_2 \\ y_2 \\ z_2 \end{pmatrix} + \begin{pmatrix} x_p \\ y_p \\ z_p \end{pmatrix} \end{eqnarray} }

球が壁にぶつかるとき（その2）- ポリゴンの表現 -

上記平面の表現方法の延長で \ s \ と \ t \ を限定すると、以下のように空間上にポリゴン表現ができる。

\large{ \begin{eqnarray} \begin{pmatrix} x \\ y \\ z \end{pmatrix} = s \begin{pmatrix} x_1 \\ y_1 \\ z_1 \end{pmatrix} + t \begin{pmatrix} x_2 \\ y_2 \\ z_2 \end{pmatrix} + \begin{pmatrix} x_p \\ y_p \\ z_p \end{pmatrix} \end{eqnarray} }

球が壁にぶつかるとき（その3）- 直線と線分の表現 -

学校では、点 \ \mathrm{P}(x_p, y_p, z_p) \ を通り、向きが \ (x_1, y_1, z_1) \ である直線の方程式は

\large{ \begin{eqnarray} \frac{x-x_p}{x_1} = \frac{y-y_p}{y_1} = \frac{z-z_p}{z_1} \end{eqnarray} }

と習ったと思うが、こちらも平面と同様、パラメトリックに表現すると以下のようになる。

\large{ \begin{eqnarray} \begin{pmatrix} x\\y\\z \end{pmatrix} = L \begin{pmatrix} x_1\\y_1\\z_1 \end{pmatrix} + \begin{pmatrix} x_p\\y_p\\z_p \end{pmatrix} \end{eqnarray} }

これらを踏まえた上で、最初の球が発射するときのプログラムが以下になる。

x1 = 1;
y1 = 2;
z1 = 3;
L = 0;

while(1)
{
    /* 画面が毎フレーム無限にリフレッシュするとします */

    x = xp + L * x1;
    y = yp + L * y1;
    z = zp + L * z1;
    L++;

    refresh();
}

球が壁にぶつかるとき（その4）- 実践編（1） -

\ z = 100 \ の平面（ポリゴン）があったとして、これを表現してみよう。

平面は2つの異なるベクトルと固定点 \ \mathrm{P} \ が決まれば良い。

\large{ \begin{eqnarray} \begin{pmatrix} x\\y\\z \end{pmatrix} = s \begin{pmatrix} x_1\\y_1\\z_1 \end{pmatrix} + t \begin{pmatrix} x_2\\y_2\\z_2 \end{pmatrix} + \begin{pmatrix} x_p\\y_p\\z_p \end{pmatrix} \end{eqnarray} }

ではこの式に、 \ z = 0 \ の平面を当てはめてみよう。

\large{ \begin{eqnarray} \begin{pmatrix} x\\y\\z \end{pmatrix} = s \begin{pmatrix} 1\\0\\0 \end{pmatrix} + t \begin{pmatrix} 0\\1\\0 \end{pmatrix} + \begin{pmatrix} 0\\0\\100 \end{pmatrix} \end{eqnarray} }

\text{すなわち}

\large{ \begin{eqnarray} \begin{pmatrix} x\\y\\z \end{pmatrix} = \begin{pmatrix} s\\t\\100 \end{pmatrix} , (s, t) \in (0, 100) \end{eqnarray} }

ということになる。

球が壁にぶつかるとき（その5）- 実践編（2） -

では、いよいよ球が壁にぶつかるかの判定をしたいと思う。

ここまでの話で球が以下のように飛んでいることは分かった。

x = 0;
y = 0;
z = 0;
L = 1;
while(1)
{
    /* 画面が毎フレーム無限にリフレッシュするとします */

    x = x + L * 1;
    y = y + L * 2;
    z = z + L * 3;
    /* 当初の(vx, vy, vz) = (1, 2, 3)であるとする*/

    refresh();
}

この球が下記平面と交差したかが分かれば良いので、

\large{ \begin{eqnarray} \begin{pmatrix} x\\y\\z \end{pmatrix} = \begin{pmatrix} s\\t\\100 \end{pmatrix}, (s, t) \in (0, 100) \end{eqnarray} }

左辺を平面、右辺を球のベクトルとして結んでみれば良いね！

\large{ \begin{eqnarray} \begin{pmatrix} s\\t\\100 \end{pmatrix} = \begin{pmatrix} x\\y\\z \end{pmatrix} + l \begin{pmatrix} 1\\2\\3 \end{pmatrix} \end{eqnarray} }

これで3元連立方程式が成立するので、 \ l,s,t \ の値は次のように算出できる。

\large{ \begin{eqnarray} l = \frac{100 - z}{3}, s = x + \frac{100 - z}{3}, t = y + 2 \times \frac{100 - z}{3} \end{eqnarray} }

このときの計算結果が

\large{ \begin{eqnarray} \quad 0 \lt l \lt 1 \ \text{かつ} \ 0 \lt s \lt 100 \ \text{かつ} \ 0 \lt t \lt 100 \end{eqnarray} }

の範囲であればこの平面と球のベクトルが交差しているということになるので、プログラムは以下のようになる。

x = 0;
y = 0;
z = 0;
L = 1;

while(1)
{
    /* 画面が毎フレーム無限にリフレッシュするとします */

    l = (100 - z) / 3;
    s = x + l;
    t = y + 2 * l;

    if(0 < l < 1 && 0 < s < 100 && 0 < t < 100)
    {
        /* 球が壁にぶつかるときの演出をここに入れる */
    }
    else
    {
        x = x + L * 1;
        y = y + L * 2;
        z = z + L * 3;
        /* 引き続き飛び続ける */
    }

    refresh();
}

ちなみに下記のように書けば簡単なのだが、このプログラムを用いる場合 \ z = 100 \ 以外への対応が不可能となるため、ここでは上記のプログラムを使用することにする。

x = 0;
y = 0;
z = 0;
L = 1;

while(1)
{
    /* 画面が毎フレーム無限にリフレッシュするとします */

    x = x + L * 1;
    y = y + L * 2;
    z = z + L * 3;
    /* まだ飛び続ける */
    
    if(100 < z)
    {
        /* 球が壁にぶつかるときの演出をここに入れる */
    }
    
    refresh();
}

球が壁にぶつかるとき（その6） - もうひとつの解 -

球が壁にぶつかるとき（その1）で、学校では点 \ \mathrm{P}(x_p, y_p, z_p) \ を通り法線ベクトルが \ (a, b, c) \ の平面の方程式は

\large{ \begin{eqnarray} a(x - x_p) + b(y - y_p) + c(z - z_p) = 0 \end{eqnarray} }

だったと記述した。

この式を展開すると、

\large{ \begin{eqnarray} ax + by + cz - (a \times x_0 + b \times y_0 + c \times z_0) = 0 \end{eqnarray} }

となり、 - (a \times x_0 + b \times y_0 + c \times z_0)の部分を dと置くと、

\large{ \begin{eqnarray} ax + by + cz + d = 0 \end{eqnarray} }

という4つの係数で表現でき、平面を4次元ベクトルとして扱います。

\large{ \begin{eqnarray} vPlane = \begin{pmatrix} a\\b\\c\\d \end{pmatrix} \end{eqnarray} }

球が壁に当たったかどうかを判定するということは、すなわち、フレームの前後で点がこの平面の表から裏側へ移ったか（平面を突き抜けたかどうか）さえ分かれば良いということなので、その判定をすることにする。

移動する前の球の位置ベクトルを \ v_0=(x_0,y_0,z_0,1) \ 移動後を \ v_1=(x_1,y_1,z_1,1) \ とすると、 \ vPlane・v0 \ と \ vPlane・v1 \ との内積をとり符号が反転していれば突き抜けたことになるね！

\large{ \begin{eqnarray} vPlane \cdot v_0 = a \times x_0 + b \times y_0 + c \times z_0 + d \times 1 \end{eqnarray} }

\large{ \begin{eqnarray} vPlane \cdot v1 = a \times x_1 + b \times y_1 + c \times z_1 + d \times 1 \end{eqnarray} }

それぞれの符号が異なるかどうかは、掛け算をして負になるかどうかで判定できる。

プログラム的に記載すると以下のようになる。

if((a * x0 + b * y0 + c * z0 + d * 1) * (a * x1 + b * y1 + c * z1 + d * 1) < 0)
{
    /* 球が壁にぶつかるときの演出をここに入れる */
}

数式だけでわかりにくかったようなので図面を足してみた。

毎フレームごとに球から平面vPlaneに垂直なベクトルを垂らしていると、 平面を突き抜けた瞬間にvPlaneの法線ベクトルと逆向きになっちゃうよね、 という話。

Coffee Break

ひと段落したのでコーヒーブレイクにしよう。

3D空間の剛体に関しては点と直線と平面の３つの要素で （一旦これをプリミティブと呼ぶことにする） ほとんどのものは構成されている。

ところが、現実社会には点と直線と平面というものは存在しない。

必ず「厚み」を持っていて、 厳密には、1)点は球であり、 2)直線は円柱であり、 3)平面は薄い直方体のようなものだ。

現実社会の工業製品はこの３つのプリミティブを使って作ることが一番大量生産できるため、 我々の身の回りを見渡すと、ほとんどは球と円柱と平面で構成されていることが分かる （素材がゴム・衣類などは別として）。

曲線や曲面を要するものは車や飛行機だったりとだいたい高級品が多く、 陶器なども手作りだったりと、めちゃくちゃ製造コストがかかるのだ。

一方で、草や木、石など自然の万物を美しいと感じてしまうのは、形が不規則性に富んでいるからで、 これらフラクタルをコンピュータでオートに生成するのは非常に難しい。

「自然は曲線を造り、人間は直線を創る。」

これは昔どこかの偉い人が言った言葉だったと思うのだけど、 個人的にはアサガオのツルが棒づたいに伸びていく様なんかは、まさに直線と曲線の美であって自然の万物と人工物が融合した形である という風に思う。


生ポリvs生ポリの判定については、ブロードフェーズ・ナローフェーズ、バウンディングボックス、スイープ＆プルーンという考え方を軸に、ミンコフスキーさんが登場してくるのでまたいつか書きたいと思う。


テコテックの採用活動について

テコテックでは新卒採用、中途採用共に積極的に募集をしています。
採用サイトにて会社の雰囲気や福利厚生、募集内容をご確認いただけます。
ご興味を持っていただけましたら是非ご覧ください。 tecotec.co.jp