backend/gsap の設計

設計目標

GSAP バックエンドは DrawList を解像度に依存しないベクターグラフィックスとして表示し、再生（再生、一時停止、逆再生、シーク、速度、ループ）は成熟したアニメーションライブラリである GSAP に任せます。シーンの数学は MoonBit に残し、JavaScript はポリゴンを保持して時計を動かすだけです。SVG に深度バッファがないのでバックエンドにもなく、可視性は描画順序で決めるしかありません。このページでは、その順序がいつ正確になるかを述べます。

数学的背景

ペインターズアルゴリズム

SVG は子要素を文書の順に塗り、それぞれが前に塗られたものを覆います。三角形を遠いものから近いものの順に出力すれば、近い面が遠い面を覆います。バックエンドは各三角形のカメラ空間での平均深度を並べ替えのキーとし、

\bar z(T) = \tfrac13 (z_0 + z_1 + z_2),

降順に並べます。同点は描画リスト内の位置で決めるので、結果は決定的です。

順序が正確になる場合。 画面上の投影が重ならない 2 つの三角形は、どの順で描いてもかまいません。重なるものについては、近い方を後で描けば順序は正しくなります。十分条件は深度の範囲が互いに素であることです。 $\max_i z_i(A) < \min_i z_i(B)$ ならば $\bar z(A) < \bar z(B)$ なので、 $B$ が先に描かれ、どこでも近い $A$ がそれを覆います。

単一の凸物体では常に正確。 メッシュが凸な立体を囲み、フロントエンドが背面を取り除いたとします。視点からピクセルを通る光線は凸な立体の境界と高々 2 点で交わり、前面から入って背面から出ます。したがって各光線上の前面は高々 1 つで、異なる前面の投影が重なるのは共有する辺に沿ってだけです。よってどの描画順序も正しく、並べ替えた順序ももちろん正しくなります。立方体、球、円柱、円錐、角錐は凸です。

失敗する場合。 非凸なメッシュ（トーラス）や複数の物体からなるシーンでは、重なる三角形の深度範囲が重なることがあります。そのとき平均深度は経験則にすぎず、三角形単位のどんな並べ方でも破綻する配置が 2 つあります。

循環的な重なり： $A$ が $B$ の一部を、 $B$ が $C$ の一部を、 $C$ が $A$ の一部を覆う。
相互貫通：2 つの三角形が交差し、交線のそれぞれの側でどちらかが手前になる。

正しい結果を得るには三角形の分割（Newell のアルゴリズム）か深度バッファが必要です。Canvas バックエンドには深度バッファがあり、これらの場合も正確です。¹1 M. E. Newell, R. G. Newell and T. L. Sancha, “A solution to the hidden surface problem”, Proc. ACM National Conference, 1972.

シェーディング

塗り色は Canvas バックエンドと同じ量子化を使います。 $q = \operatorname{round}(\operatorname{clamp}(I)\,(L - 1))$ 、色は $\operatorname{round}(\mathbf{c}\, q / (L - 1))$ で、輝度の誤差は最大 $1/(2(L - 1))$ です。

入力は時刻だけ

GsapPlayer は時計オブジェクトを $0$ から $D$ 秒まで線形イージングでトゥイーンします。タイムライン上の位置 $\tau$ （GSAP 自身の時間で、速度倍率はすでに反映済み）について、コールバックは $\tau \in [0, D]$ のとき $t = \tau$ を受け取ります。MoonBit 側はシーンを $t$ の純粋関数として描画します： $\text{frame}(t) = \text{render}(\text{scene}(t))$ 。そのためシーク、逆再生、ループ、速度変更に追加の状態は要りません。GSAP がどの $t$ を報告しても、その $t$ の画が描かれます。更新は固定のフレームレートではなくブラウザのリフレッシュレートで届くので、バックエンドはフレーム間隔を仮定しません。

設計上の判断

ペインターズアルゴリズムによるベクター出力

課題は、三角形から、ブラウザが保持してスタイルを付け直せる鮮明で拡大縮小可能な出力を作ることです。SVG のポリゴンはまさにそれですが、SVG には深度バッファがありません。選択肢は、画像にラスタライズする（ベクターの利点を失う）、正確な順序を得るため三角形を分割する（一般には複雑で遅い）、三角形単位で並べ替える、の 3 つでした。並べ替えを選びました。ライブラリの凸な基本形状では正確で、典型的なシーンではほぼ正しく、コストは $O(n \log n)$ と安価だからです。

キーは平均深度、同点は安定に

平均深度は安価で、頂点について対称です。同点を元のインデックスで決めると出力が決定的になり、テストで正確なポリゴンの順序を検証でき、静止したシーンのフレームもちらつきません。

DOM ノードの再利用

呼び出しのたびに既存の <polygon> 要素を再利用し、数の差分だけを追加・削除します。フレームごとに数千の要素を作るとそれがコストの大半を占め、ガベージコレクタにも負担をかけますが、ポリゴンごとに 2 つの属性を更新するだけならそうはなりません。マーカー data-gsap-svg-background と data-gsap-svg-triangles によってバックエンドは自分のノードを見つけ、まだそれらを持たない <svg> の子要素は置き換えます。

時計は GSAP が持つ

再生の制御は GSAP で解決済みの問題です。バックエンドは最小限のクランプされた部分集合（長さの範囲内の seek、 $[0, 1]$ の set_progress、正の速度倍率、繰り返し回数 $\ge -1$ ）だけを公開し、MoonBit の呼び出し側がデモの UI が想定しない状態にタイムラインを追い込めないようにしています。GSAP はインポートせず構築時に globalThis.gsap から探すので、読み込み方（CDN、バンドラ、ローカルのコピー）はページが決めます。

正しさと不変条件

render_draw_list の後、三角形のグループには描画リストの三角形と同数のポリゴンがあり、平均深度の降順に、同点は安定に並びます。
重なる三角形の深度範囲が互いに素であれば、画は正確です。特に、背面カリング後の単一の凸メッシュでは常に正確です。
塗り色はチャネルが $[0, 255]$ の有効な rgb(r, g, b) 文字列です。
GsapPlayer は、メソッドを通して渡された値について $\text{seek} \in [0, D]$ 、 $\text{progress} \in [0, 1]$ 、速度倍率 $> 0$ 、繰り返し回数 $\ge -1$ を保ちます。

フレームあたりのコストは、フロントエンドのパイプライン、 $n$ 個の三角形の $O(n \log n)$ の並べ替え、 $O(n)$ 回の属性更新です。

採用しなかった案

SVG でのピクセル単位の深度（たとえばピクセルのランごとに 1 つのポリゴン）は、SVG の長所をすべて捨てることになります。
BSP 木や Newell のアルゴリズム。 どちらも正確な順序を与えますが、三角形を分割し、ポリゴンの数がフレームごとに変わります。デモのシーンでは、平均深度による並べ替えの目に見える誤りはまれで、すぐに消えます。
MoonBit から requestAnimationFrame を駆動する。 GSAP がすでに提供している再生、一時停止、逆再生、シークを作り直すことになります。

境界

GSAP バックエンドは次のことをしません。

js 以外のターゲットで動くこと、DOM とグローバルな gsap なしで動くこと。
循環的な重なりや交差する三角形の解決。
隣り合うポリゴンの間に現れうる細いアンチエイリアスの継ぎ目を隠すための線の追加。
プレーヤーの UI 作成、GSAP の読み込み、ある時刻に何を描くかの決定（これらは demo_gsap パッケージが行います）。
呼び出し側がパッケージの外から色や濃淡の段階数を変えること（設定のフィールドはそこでは読み取り専用です）。

M. E. Newell, R. G. Newell and T. L. Sancha, “A solution to the hidden surface problem”, Proc. ACM National Conference, 1972. ↩