Semi-Lagrangian Advection

This explanation is currently available in Japanese.

ひとことで

流れに乗せて何か（煙の濃さ、色、速度そのもの）を運ぶとき、各マスの中心から流れを逆向きにたどり、たどり着いた場所の値を補間して持ってくる方法です。「この場所には、少し前にどこから流れてきたか」を調べるので、どんなに速い流れや大きな時間刻みでも値が暴れず、格子で流体を解くときの定番になっています。

ゲームでの使いどころ

• 格子流体の中心部品：安定流体法の煙や速度の移流は、ほぼすべてこの方法です。
• テクスチャを流す：フローマップで水面や溶岩の模様を流すのも、「各ピクセルで、流れの上流の色を読む」という同じ考え方です。
• ペイント・インク・汚れの広がり：『スプラトゥーン』のようにインクが面を流れる表現や、川に絵の具を流す演出。
• 時間方向の再投影：TAAで前のフレームの色を動きに合わせて持ってくる処理も、発想は同じです。

しくみ

量 $q$（煙の濃さなど）が速度 $\mathbf{u}$ の流れに運ばれるとき、式は次のとおりです。

「流れに乗って動く粒から見ると、$q$ は変わらない」という意味です。これを利用して、

1. 逆向きにたどる：各マスの中心 $\mathbf{x}$ から、速度を逆向きに 1 ステップ分たどります。

2. 補間して持ってくる：たどり着いた場所 $\mathbf{x}_{\text{前}}$ はふつうマスの中心からずれているので、周りの 4 マス（3 次元なら 8 マス）の値を双線形補間して、新しい値にします。

なぜ安定か：新しい値は、いつも「周りにある値の重み付き平均」です。元の値の最大より大きく、最小より小さくなることはないので、時間刻みがどれだけ大きくても値が暴れません。1 ステップで何マス分も流れても問題ありません。

代わりにぼやける：補間は平均をとる操作なので、くり返すほどくっきりした模様がならされていきます（数値拡散）。

MacCormack 法（BFECC）

ぼやけを減らす工夫として、半ラグランジュ移流を 2 回使います。

1. 普通に 1 ステップ進めた結果 $\hat{q}$ を求める。
2. $\hat{q}$ を逆向きに 1 ステップ戻した結果 $\tilde{q}$ を求める。誤差がなければ $\tilde{q}$ は元の $q$ に一致するはず。
3. 戻らなかった分（誤差）の半分を補正する：$q_{\text{新}} = \hat{q} + (q - \tilde{q})/2$。
4. 補正で新しい極値が生まれないよう、たどった先の 4 マスの最小・最大の範囲に収める（リミッター）。

計算は約 2 倍ですが、模様がずっとくっきり保たれます。

実装のポイント

• GPU ならとても簡単：テクスチャのバイリニアフィルタがそのまま補間になるので、数行で書けます。
• たどり方を正確に：速い渦の中では、1 回の直線でたどると曲がり方を無視してしまいます。途中の速度も使う（RK2 でたどる）と、渦の形が崩れにくくなります。
• 壁の外に出たら：たどった先が壁や格子の外なら、境界の値を使うか、壁の手前で止めます。

つまずきやすい点

• 前向きに差分で解こうとする：「その場所の傾き × 速度」で前向きに更新する素直な方法（中心差分 + 前進オイラー）は、どんなに小さな刻みでも不安定で、しま模様が暴れて壊れます。
• ぼやけを許容しすぎる：煙なら多少ぼやけても自然ですが、細い模様や境界をくっきり保ちたい場合は MacCormack 法や、粒子で運ぶ方法（PIC・FLIP）を使います。
• 質量が保存されない：補間で値が少しずつ増減するので、煙の総量は正確には保たれません。ゲームではたいてい目立ちませんが、水の量などには注意が必要です。

デモで試すこと

1. 3 枚のパネルに、同じ絵を同じ流れで運んだ結果が並んでいます。左の素朴な方法はすぐにしま模様が暴れて壊れ、中央の半ラグランジュ移流は壊れない代わりにぼやけ、右の MacCormack 法はくっきりしたまま運ばれます。
2. 「ねじって戻す」の流れは、周期の半分で向きが反転し、周期の終わりに元の絵に戻るはずの流れです。周期ごとに、中央と右の絵がどれだけ元の絵に戻れるかを比べてください。
3. 中央のパネルの黄の線は、各マスの中心から流れを逆向きにたどった道筋です。
4. 「1 ステップで流れる距離」を 3〜4 マスまで上げても、半ラグランジュ移流は壊れません。1 回の補間でより遠くの値を持ってくるだけです。