はじめに

東方Projectシリーズには、「へにょりレーザー」と呼ばれるレーザーがあります。魅力的な模様を描きながら読みづらい軌道で飛んできて、残機を刈り取っていくレーザーです。このへにょりレーザー、ずっと三角関数でアレコレしているんだと思ってましたが、どうやらスプライン曲線のようです。

まりお「へにょりってルーさん発なの？」
ルー「黄昏酒場の時にZUNさんのシステム触らせてもらって、sin,cosのやつ入ってないって思って勝手に入れたらそのあと地霊殿で…」
ZUN「実はsin,cos使ってないんだよな〜スプラインなんだよあれは」
まりお「専門用語だらけで全然わかんない」#2軒目備忘録
— 704. (@takegusa) May 28, 2020

確かにスプライン曲線ならあれこれ難しい処理を作らなくてもへにょりレーザーの軌道が表現できる！すごい！というわけでへにょりレーザーをスプライン曲線で実装します。

B-スプライン曲線

コンピュータグラフィックスでのスプライン曲線と言えばB-スプラインです。ゲームに限らず、CADやモデリングにも多く用いられています。しばしば聞くベジェ曲線もこの一部です。このB-スプラインは、制御点の座標と曲線の次数を与えることで、特定の時間における座標を求めることができます。

$m$ 個の制御点( ${\bf P}_i$ は制御点の座標)を持つ $n$ 次のB-スプライン曲線の時間 $t$ における座標 ${\bf C}(t)$ は、次の式で表されます。

$\displaystyle{ {\bf C}(t) = \sum_{i=0}^{m-1} N_{i, n}(t){\bf P}_i }$

ここで、 $N_{i,n}(t)$ はB-スプラインの基底関数を表します。基底関数は、

$\displaystyle{ N_{i, 0}(t)= \left\{ \begin{array}{ll} 1 & {\rm if} \:\:\: k_i \leq t < k_{i+1}\\ 0 & \rm otherwise \end{array} \right . \\ N_{i,n}(t)= \frac{t-k_i}{k_{i+n}-k_i}N_{i,n-1}(t) + \frac{k_{i+n+1}-t}{k_{i+n+1}-k_{i+1}}N_{i+1, n-1}(t) }$

で表します。 $k_j$ はノットベクトルの $j$ 番目のノットを表します。

※お詫び: 初期掲載時に数式の一部に誤りがありました。現在は修正済みです。

ノットベクトル

B-スプライン曲線を表す上でノットベクトルは欠かせない概念です。曲線をノット(要素)の数で分割し、各制御点はノットの値が一定の範囲のときに曲線に対して影響します。ノットベクトルは制御点の数と次数と1を足したものに等しい数のノットを持ちます。たとえば、制御点の数が5、次数が2であれば8つのノットを持つノットベクトルが必要です。

$n=0$ のときの基底関数では $N_{i,0}(t) = 1 \quad( {\rm if} \quad k_i \leq t \lt k_{i+1})$ とありますが、 $t$ が $i$ 番目と $i+1$ 番目のノットの範囲内にあるときにこの制御点は影響力を持つ、ということを表しています。 $i$ は制御点の番号によって決定するので、ノットベクトルの値を調整することでどの制御点にどれくらい影響力をもたせるかを決定することができます。

開一様ノットベクトル

今回は「開一様ノットベクトル」と呼ばれるノットベクトルを用います。開一様ノットベクトルの説明の前に、「一様ノットベクトル」について説明します。

一様ノットベクトルは、すべてのノットの値の間隔が等しいノットベクトルのことを指します。例えば、

$\displaystyle{ {\bf k} = [1,2,3,4,5,6,7,8] }$

のようなノットベクトルを一様ノットベクトルと呼びます。一様ノットベクトルを使用することですべての制御点の影響力が一定となり、例えば制御点4つで正方形を作ると輪のような曲線を表すことができます。

これに対し、開一様ノットベクトルは両端のノットをB-スプライン曲線の次数プラス1個重複させた一様ノットベクトルです。例えば、制御点5個、次数が2のB-スプライン曲線の開一様ノットベクトルを作る場合は、

$\displaystyle{ {\bf k} = [0, 0, 0, *, *, 1,1,1] }$

のように両端に次数プラス1個重複したノットを生成し、

$\displaystyle{ {\bf k} = [0, 0, 0, 0.33..., 0.66..., 1,1,1] }$

のように残りの要素を一様に配置します。これによって開一様ノットベクトルが作成できます。

開一様ノットベクトルの最大の特徴は、「最初の制御点と最後の制御点を必ず通る」ということにあります。以下の画像は各制御点の影響力(基底関数の計算結果)をプロットしたものですが、左端と右端では1つの制御点のみが影響力を持つことがわかります。これによって、始点と終点を指定することができるB-スプライン曲線を表現することができます。

f:id:tolt:20200531222443p:plain — 各制御点の影響力

実装

基底関数を実装してしまえば後は基底関数の計算結果を制御点の座標に掛けるだけなので、ノットベクトルの生成と基底関数を軸に実装します。 C++で書いていますが、「ベターC」としてしか今まで使ったことがないのでお見苦しいコードですがお許しください。

// B-スプラインの座標生成
// vector 制御点, int 生成する座標数, int 次数
vector<Vec2D> bSpline(vector<Vec2D> controlPoint, int pointNum, int degree) {

    // ノットベクトルの生成
    vector<float> knotVector;
    int knotNum = controlPoint.size() + degree + 1;
    for (int i = 0; i < degree; i++) {
        knotVector.insert(knotVector.begin(), 0.0f);
        knotVector.push_back(1.0f);
    }
    knotNum -= degree * 2 + 1;
    for (int i = 0; i <= knotNum; i++) {
        knotVector.insert(knotVector.begin() + degree + i, (1.0f / knotNum) * i);
    }

    // 基底関数の式
    function<float(int, int, float)> baseF = [&baseF, &knotVector](int i, int m, float t) {
        float w1 = 0.0f, w2 = 0.0f;
        if (m == 0) {
            if (knotVector[i] <= t && t <= knotVector[i + 1]) {
                return 1.0f;
            } else {
                return 0.0f;
            }
        } else {
            w1 = (t - knotVector[i]) / (knotVector[i + m] - knotVector[i]) * baseF(i, m - 1, t);
            w2 = (knotVector[i + m + 1] - t) / (knotVector[i + m + 1] - knotVector[i + 1]) * baseF(i + 1, m - 1, t);
            
            w1 = isnan(w1) ? 0.0f : w1;
            w2 = isnan(w2) ? 0.0f : w2;
        }
        return w1 + w2;
    };


    vector <Vec2D> points;
    float pointInterval = 1.0f / pointNum;
    Vec2D p;

    // 座標を計算
    for (int i = 0; i < pointNum; i++) {
        p = Vec2D(0.0f, 0.0f);
        for (int j = 0; j < controlPoint.size(); j++) {
            p += controlPoint[j] * baseF(j, degree, pointInterval * i);
        }
        points.push_back(p);
    }

    return points;
}

実際の動き

以上、開一様ノットベクトルで表されるB-スプライン曲線について説明を行いましたが、実際にこれがどのような挙動をするのかについては動画を見るのが最も早いでしょう。

スプライン曲線を使ったへにょりレーザー pic.twitter.com/jFnrXyxWc0
— とるとさんちょく (@tolt_santyoku) 2020年5月30日

開一様ノットベクトルの章で述べたように、最初の制御点と最後の制御点を通り、その他の制御点に影響されながら曲がる曲線が表現されています。

課題

上記実装では、曲線の軌道を予めすべて計算して保持しているため、レーザーの生成コストが非常に高いという問題を抱えています。リアルタイムで先の軌道を計算することでコストを分散することができるため、実際にゲームで使う場合は一度にまとめて計算しないことをお勧めします。

また、基底関数は再帰を含むため処理が多く、そのままでは多量のレーザーの生成には向きません。次数が1の場合は基底関数を呼び出さずに場合分けで処理したり、参考資料のように予め計算をしておくなど軽量化をして利用するのが良いでしょう。

おわりに

B-スプライン曲線は制御点が決まっていれば時間を与えるだけで軌道上の位置を求めることができるため、レーザーを構成する弾に時間のパラメータをもたせることで「途中で千切れるレーザー」も表現が簡単になります。原作により近いへにょりレーザーの実装に興味がある方は試してみてはいかがでしょうか。

私は学生時代にNURBSと呼ばれるB-スプラインの一つを実装していたのですが完全に忘れてしまっていて、タイムラインに流れてきた「スプライン」という単語にめちゃめちゃ反応した割に話せず、悔しかったので実装して記事にしてやりました。非常に良い再学習になったため、きっかけとなった神主とTLにこの記事を持って感謝を表したいと思います。

続きの記事(NURBS曲線)

この記事の続きを書きました。 tecofalltolt.hatenablog.jp

参考資料

naochang | B-スプライン曲線 (B-spline Curve)

Bスプライン曲線を使ってロボットの軌跡生成をしてみよう！（その１） | Tajima Robotics

隔離発展tecofallt

B-スプライン曲線でへにょりレーザーを実装する

目次