frontend の設計

設計目標

フロントエンドは 3D のシーンが 3D でなくなる場所です。すべての出力で共通の各段階（モデル変換とビュー変換、投影、可視判定、照明、影）を担い、バックエンドには画面空間の三角形の平らなリストを、それぞれ 1 つの明るさとともに渡します。そのため、バックエンドは半日で書けます。決めることは、ある明るさの三角形が自分のデバイスでどう見えるかだけです。同じ境界によって、TUI、Canvas、SVG のバックエンドは同じ DrawList から同じ画を表示できます。

数学的背景

パイプライン

メッシュの頂点 $p$ とモデル行列 $M$ を持つ各オブジェクトと、ビュー行列 $V$ と投影 $\pi$ を持つカメラ（view の設計を参照）について、build_draw_list は次を計算します。

p_w = M p,\qquad p_c = V p_w,\qquad (x_s, y_s, z) = \pi(p_c),

さらに、カメラ空間の法線 $\hat n_F$ と中心 $c_F$ を持つ各面 $F$ について、

\text{emit } F \iff \hat n_F \cdot (0 - c_F) > 0,\qquad I_F = \max(0, \hat n_F \cdot \ell_c)\,\big(\alpha + (1 - \alpha)\, v_F\big),

を計算します。ここでカメラはカメラ空間の原点にあり、 $\ell_c = \operatorname{normalize}(V \ell)$ はカメラ空間での光の方向（方向なので $w = 0$ ）、環境光の係数は $\alpha = 0.35$ 、影の可視度 $v_F \in [0, 1]$ は後述します。 $V$ は剛体運動なので $\hat n_F \cdot \ell_c$ はワールド空間のランバート項に等しく、カメラ空間で計算すれば法線をもう 1 組持つ必要がありません。出力される各四角形は triangulate_quad の 2 つの三角形になり、どちらも $I_F$ を持ちます。

シャドウマッピング

ある点と光源の間にほかの面があるとき、その点は影の中にあります。平行光源ではすべての光線が $\ell$ に平行なので、判定は平行（正射影）投影の中で $\ell$ に沿った距離を比べることに帰着します。¹1 深度マップの手法は Lance Williams の “Casting curved shadows on curved surfaces”（SIGGRAPH 1978）で導入されました。

光源カメラ。 $c$ をシーンのワールド空間でのバウンディングボックスの中心、 $\rho = \max(1, \max_p \lVert p - c \rVert)$ とします。フロントエンドは Camera3 を $c + (2\rho + 1)\,\ell$ に置いて $c$ を向かせ、上方向 $= +y$ （座標系が退化しないよう $|\ell \cdot y| > 0.99$ のときは $+z$ ）とします。すべての頂点はその前方 $\rho + 1$ 単位以上の位置にあります。このカメラの空間では、 $x_\ell$ と $y_\ell$ は光線を横切る座標、 $z_\ell$ は光線に沿って光源から離れる距離です。

グリッド。 全頂点の光源空間でのバウンディングボックスを各辺で $\max(0.05 \cdot \text{span}, 0.25)$ だけ広げ、その上に $N = 128$ の $N \times N$ グリッドを置きます。

X = \frac{x_\ell - x_{\min}}{x_{\max} - x_{\min}}\,(N - 1),\qquad Y = \frac{y_{\max} - y_\ell}{y_{\max} - y_{\min}}\,(N - 1).

深度パス。 すべてのオブジェクトのすべての三角形を、前面か背面かにかかわらず、下の規則でグリッドにラスタライズし、各テクセルには最小の $z_\ell$ （光源に最も近い面）を残します。深度は重心座標で線形補間し、ここではそれが正確です。 $c \ne 0$ の平面 $a x + b y + c z = d$ 上では $z = (d - a x - b y)/c$ は $(x, y)$ についてアフィンであり、グリッドへの写像もアフィンだからです。

参照。 ワールド空間の点 $q$ を判定するには、フロントエンドはそれをバイアス $b$ の 2 倍だけ光源の方へ動かし、グリッドに写して最も近いテクセル $(X^\ast, Y^\ast)$ に丸めます。光源カメラの前方軸は $-\ell$ なので、 $\ell$ に沿って $2b$ 動かすと $z_\ell$ はちょうど $2b$ 減ります。点がグリッドの外にある場合、テクセルが空の場合、または

z_\ell(q) - 2b \le D(X^\ast, Y^\ast) + b \iff z_\ell(q) \le D(X^\ast, Y^\ast) + 3b ,

の場合に点は照らされているとみなすので、実効的な許容誤差は $3b$ で、 $b = \max(0.005 \cdot \text{depth span}, 10^{-4})$ です。

バイアスが必要な理由。 グリッドの解像度が有限なために面が自分自身に影を落とす現象をシャドウアクネと呼びます。最も近いテクセルの中心に丸めると、参照位置は各軸で最大で半テクセル $\Delta/2$ ずれます。ここで $\Delta$ は光源空間の単位でのテクセルの大きさです。 $q$ を通る面の光源空間での深度の勾配が $(z_x, z_y)$ なら、そのテクセルに格納された深度と $z_\ell(q)$ の差は最大で

|D - z_\ell(q)| \le \big(|z_x| + |z_y|\big)\,\frac{\Delta}{2} .

です。法線が $\ell$ と角度 $\theta$ をなす面では $\lVert (z_x, z_y) \rVert = \tan\theta$ なので、すれすれの入射では誤差は際限なく大きくなります。許容誤差 $3b$ は $\sqrt2\,\tan\theta\,\Delta/2 \le 3b$ のときアクネを取り除きます。そうでない場合は $\theta$ が $90°$ に近く、ランバート係数 $\cos\theta$ によって面はすでに暗いので、残ったアクネは目立ちません。バイアスの代償は、接触点で影が少し遅れて始まること（ピーターパン現象）で、その量はおよそ $3b$ = シーンの深度範囲の 1.5% です。

面の可視度。 フロントエンドは各面の中心と 4 頂点を判定して平均します。

v_F = \tfrac15 \sum_{q \in \{c_F, v_a, v_b, v_c, v_d\}} \mathbb{1}[q \text{ lit}] \in \{0, 0.2, 0.4, 0.6, 0.8, 1\}.

影の境界をまたぐ面は中間の値になり、フラットシェーディングされた面の上にぎざぎざの境界を描く代わりに、面の解像度で境界を和らげます。環境光の項によって、完全に影に入った面もランバートの明るさの $\alpha = 35\%$ を保つので、影の中でも形が読み取れます。光源に背を向けた面は参照せず、輝度は $0$ です。

エッジ関数によるラスタライズ

LumaBuffer::draw_triangle（と同じ規則を使う TUI とシャドウマップのラスタライザ）は、エッジ関数で被覆を判定します。画面平面上の点 $a$ 、 $b$ 、 $p$ について

E(a, b; p) = (p_x - a_x)(b_y - a_y) - (p_y - a_y)(b_x - a_x),

とします。これは $p$ のアフィン関数で、直線 $ab$ 上で 0 になり、その直線をまたぐと符号が変わります。 $|E(a, b; p)|$ は三角形 $abp$ の面積の 2 倍です。三角形 $p_0 p_1 p_2$ について

A = E(p_0, p_1; p_2),\qquad w_0 = E(p_1, p_2; p),\quad w_1 = E(p_2, p_0; p),\quad w_2 = E(p_0, p_1; p).

と置きます。各 $w_i$ は $p$ についてアフィンで、 $p_i$ 以外の 2 頂点で 0 になります。符号付き面積は頂点の巡回置換で不変なので、 $p = p_i$ では $A$ に等しくなります。したがって $w_0 + w_1 + w_2 - A$ は同一直線上にない 3 点で 0 になるアフィン関数であり、

w_0 + w_1 + w_2 = A \quad\text{for every } p, \qquad \lambda_i = \frac{w_i}{A}

は $p$ の重心座標です（ $\lambda_i(p_j) = \delta_{ij}$ 、 $\sum \lambda_i = 1$ ）。点が閉じた三角形の中にあるのは、すべての $\lambda_i \ge 0$ 、つまりすべての $w_i$ が $A$ と同じ符号か 0 のときに限ります。コードは両方の符号を判定するので、画面上での三角形の巡回順は関係ありません。カリングは 3D ですでに済んでいます。ピクセルは中心 $(x + \tfrac12, y + \tfrac12)$ で、三角形のバウンディングボックスの中だけでサンプリングし、 $|A| \le$ DEPTH_EPSILON の三角形はスキップします。覆われたピクセルの深度は透視補正された $\big(\sum \lambda_i / z_i\big)^{-1}$ です。

深度バッファ

set_if_closer は、新しい深度が格納済みのものより $\varepsilon$ = DEPTH_EPSILON を超えて小さいときだけピクセルを書き込みます。描いた三角形についての帰納法により、 $T_1, \dots, T_k$ を描いた後、各ピクセルはそこを覆う三角形のうち深度が最小のものの輝度を持ち、その深度から $\varepsilon$ 以内の三角形が複数あれば最初に描かれたものの輝度を持ちます。基底は深度 $10^{30}$ の空のバッファです。帰納段階では、 $T_{k+1}$ は $\varepsilon$ を超えて厳密に近いときに限り格納済みの値を置き換えます。したがって最終的な画像は、ほぼ同点の場合を除き描画順序に依存せず、そのため描画リストは並べ替えません。

辺は含まれ、「左上」の同点規則はありません。2 つの三角形が共有する辺のちょうど上にあるピクセルの中心は両方に覆われ、深度テストがどちらか一方を残します。四角形の 2 つの三角形は同じ輝度を持つので、面の内部では見分けがつきません。

露光とオプティカルフロー

シャッター時間 $T$ のカメラは各ピクセルで $\int_0^T L(x, t)\,dt$ を記録します。フロントエンドは正規化された露光を、 $N$ 個の描画サンプルにわたるリーマン和で近似します。

\bar L(x) = \frac1T \int_0^T L(x, t)\,dt \approx \frac1N \sum_{k=0}^{N-1} L(x, t_k),

これは重み $1/N$ の LumaBuffer::add_weighted_sample で実装されています。動く輪郭はモーションブラーとして伸びます。

オプションのフローによる位置合わせは輝度一定 $L_{\text{prev}}(x + d) \approx L_{\text{cur}}(x)$ を仮定し、総当たりのブロックマッチングでピクセルごとの整数の変位 $d$ を推定します。

d(x) = \operatorname*{arg\,min}_{\lVert d \rVert_\infty \le R}\ \sum_{\lVert o \rVert_\infty \le P} \big( L_{\text{prev}}(x + o + d) - L_{\text{cur}}(x + o) \big)^2 .

積算の前に各サンプルをそのフローでワープすると（align_with_flow）、動く内容が現在のフレームに位置合わせされ、ぼけの代わりにゴーストの少ない鮮明な輪郭が得られます。推定値は整数です。開口問題の影響を受け、一様なパッチではどの $d$ も合うので、走査順により $(-R, -R)$ が返ります。

設計上の判断

境界としての描画リスト

課題は、出力モデルがまったく異なる 3 つのバックエンド（文字のグリッド、ピクセルのキャンバス、保持される SVG ノード）が同じシーンを表示しなければならないことです。選択肢は、メッシュを渡す（各バックエンドが投影と照明を実装し直す）、ピクセルを渡す（SVG バックエンドがベクター出力を失う）、投影とシェーディングを済ませた三角形を渡す、の 3 つで、最後のものを選びました。DrawTriangle には、どのバックエンドにも必要なもの、つまり画面座標、遮蔽のためのカメラ深度、各バックエンドが自分のパレットに対応付ける $[0, 1]$ の明るさがちょうど含まれます。投影、カリング、照明、影は 1 か所で一度だけ計算され、一度だけテストされます。

四角形ごとのフラットシェーディング

面ごとに 1 つの輝度は、デモのファセット状のローポリゴンの見た目やターミナルの粗い解像度に合い、描画リストも小さく保ちます。スムーズシェーディングには core にない頂点ごとの法線と、SVG バックエンドでは表現できないピクセルごとの補間された輝度が必要になります。

影はフロントエンドで

影にはシーン全体のワールド空間の幾何が必要で、バックエンドはそれを見ないので、影はフロントエンドに属します。レイキャスティングではなくシャドウマップを選びました。コストは光源からのシーンのラスタライズ 1 回とサンプル点ごとの参照 1 回で、既存のラスタライザを再利用でき、加速構造も不要です。可視度は面ごとに 5 回しかサンプリングしないので、解像度は 128 × 128 に固定しています。より細かいマップにしてもフラットシェーディングの出力は変わりません。範囲は毎フレームシーンに合わせるので、常に解像度をすべて使えます。

共有のスカラーバッファ

LumaBuffer がバックエンドではなくフロントエンドにあるのは、深度付きのスカラー画像を必要とする利用者が 3 つあるからです。Canvas バックエンド、露光の積算、オプティカルフローです。TUI バックエンドは直接描画用に自分の文字バッファを持ち、露光効果には（draw_list_to_tui_luma を通して）LumaBuffer を使います。

データとしての時間

Timeline、ScalarTrack、ExposureSettings、フローの関数は純粋なデータとバッファの関数で、時計を呼ぶことはありません。いつ描画し、どの時刻をサンプリングするかはデモが決めるので、フロントエンドは決定的でテストしやすいままです。

正しさと不変条件

出力される三角形はカメラの方を向き（カメラ空間で $\hat n \cdot (0 - c) > 0$ ）、光の方向が単位ベクトルなら輝度は丸めを除いて $[0, 1]$ に入ります（完全に照らされた面が $1 + 2^{-52}$ になることがあります）。バックエンドがそれをクランプします。
描画リストはシーンの順に、オブジェクトごと、面ごとに並び、可視の四角形 1 つにつき三角形が 2 つあります。
上で示したとおり、LumaBuffer は各ピクセルで、そこを覆う最も近い三角形の値（ $\varepsilon$ 以内の同点なら最初に描かれたもの）を保持します。
影の参照は、マップの外や空のテクセルの下にある点を暗くすることはありません。可視度は $0.2$ の倍数です。
ExposureSettings は常に $0 < \text{shutter} \le \text{frame\_dt}$ で、サンプルは 1 つ以上です。auto はちょうど 1 サンプルになります（数を求める前にシャッターがクランプされるため）。
Timeline::frame_count は 1 以上で、サンプルの時刻は $k/\mathit{fps}$ 、進捗は $[0, 1]$ にクランプされます。

フレームあたりのコストは、変換、カリング、シェーディングが $O(V + F)$ 、ラスタライズは各三角形が覆うバウンディングボックスの面積に比例（シャドウマップと LumaBuffer の両方）、照らされた可視の面ごとに影の参照が 5 回、オプティカルフローが $O(W H (2R+1)^2 (2P+1)^2)$ です。

採用しなかった案

描画リストを深度で並べ替えること。 TUI と Canvas のバックエンドでは正しい遮蔽は深度バッファから得られ、SVG バックエンドは深度バッファがないので自分で並べ替えます。フロントエンドで並べ替えると、1 つの戦略をすべてに押し付けることになります。
グーローシェーディングやフォンシェーディング。 「四角形ごとのフラットシェーディング」を参照してください。TUI の出力も、良くなるどころか雑然とします。
隣接テクセルでのパーセンテージクローサーフィルタリング。 面ごとの 5 サンプルで、フラットシェーディングが表現できる中間の値はすでに得られます。
ExposureSettings::auto のクランプを変えること。 シャッターを 1 フレームより長くできれば auto は複数のサンプルを返せますが、1 つのフレームが次のフレームの区間の光まで積分することになります。

境界

フロントエンドは次のことをしません。

視錐台やニア平面による幾何のクリッピング。すべての頂点はカメラの前方になければなりません。
点光源やスポットライト、色付きの光、複数の光源、マテリアル、テクスチャへの対応。
文字、色、デバイス上のピクセル、ファイルの生成。
フレーム間での描画リストの並べ替え、バッチ処理、キャッシュ。
サブピクセルや密な変分法によるオプティカルフローの推定。

深度マップの手法は Lance Williams の “Casting curved shadows on curved surfaces”（SIGGRAPH 1978）で導入されました。 ↩