Mesh Decimation / Quadric Error Metrics

This explanation is currently available in Japanese.

ひとことで

メッシュの見た目をなるべく変えずに、面の数を減らす方法です。代表的な二次誤差（QEM）法では、各頂点に「周りの面の平面からの距離の 2 乗の和」を表す行列を持たせ、辺を 1 点に縮めたときの誤差が小さい辺から順に縮めていきます。平らな所は大きな三角形にまとめ、形が変わりやすい尾根や角には細かい三角形を残します。

ゲームでの使いどころ

• LOD（詳細度の切り替え）：遠くの物を少ない面で描くための、面数の違う複数の形を自動で作る。LOD の材料作りの定番。
• スキャン・生成したメッシュの軽量化：3D スキャンやマーチングキューブで作った、無駄に細かいメッシュを減らす。
• 当たり判定用の簡単な形：見た目用のメッシュから、物理用の粗い形を作る。
• ナビゲーションメッシュ・地形：歩ける面や地形の三角形を減らし、経路探索や描画を軽くする。

しくみ

面（平面） $ax + by + cz + d = 0$（$a^2 + b^2 + c^2 = 1$）から点 $\mathbf{v} = (x, y, z, 1)$ までの距離の 2 乗は、

と 4×4 行列 $K_p = \mathbf{p}\mathbf{p}^\top$ で書けます。各頂点に、周りの面の $K_p$ の和 $Q$ を持たせます。

1. 辺 $(v_1, v_2)$ を 1 点 $\bar{\mathbf{v}}$ に縮めるときの誤差は、$\bar{\mathbf{v}}^\top (Q_1 + Q_2) \bar{\mathbf{v}}$ です。
2. $\bar{\mathbf{v}}$ は、この誤差が最小になる位置（3×3 の連立方程式の解）にします。解けなければ、両端か中点のうち誤差の小さい方にします。
3. すべての辺を誤差の小さい順に優先度つきキューに入れ、いちばん小さい辺から縮めます。縮めた頂点の $Q$ は $Q_1 + Q_2$ にし、周りの辺の誤差を計算し直します。
4. 目標の面数になるまでくり返します。

平らな所では、周りの面がすべて同じ平面なので、縮めても誤差がほぼ 0 です。だから平らな所から先に大きな三角形にまとめられます。

実装のポイント

• 面の裏返りを防ぐ：縮めた結果、周りの面の向きが反転するなら、その縮約はしません。
• 境界を守る：開いたメッシュの縁は、縁に沿って縮むと輪郭が崩れます。縁の辺には、面に垂直な平面の誤差を強い重みで足しておきます。
• 縮約の順番を記録する：縮めた順番（どの頂点をどこへ縮めたか）を記録しておけば、先頭から好きな数だけ適用して、任意の面数の形を一瞬で作れます（プログレッシブメッシュ）。
• 色や UV も誤差に入れる：形だけで判断すると、テクスチャの境目や色の違う所が崩れます。UV や法線も誤差に含める拡張版を使います。実務では meshoptimizer などのライブラリがよく使われます。

つまずきやすい点

• 細い部分が消える：誤差の合計で判断するので、細い棒や薄い板が消えてしまうことがあります。
• シルエットの崩れ：遠くから見たときの輪郭を保つことが大切な物（木や柵）は、面の数だけでなく、見た目の大きさに応じて減らす量を決めます。
• 格子でまとめる方法との違い：頂点クラスタリングは速いですが、形の大事な所を考えずに同じ細かさでまとめるので、同じ面数でも形が大きく崩れます。

デモで試すこと

1. 左が元の地形（約 18,000 面）、右が 5% に減らしたものです。平らな野原が大きな三角形にまとめられ、山の尾根に細かい三角形が残っていることを確かめてください。
2. 「残す面の割合」を動かすと、形がすぐに変わります。縮約の順番を最初に 1 回だけ記録しておき、先頭から必要な数だけ適用しているからです。
3. 「減らし方」を「格子でまとめる」にすると、同じ面数でも、野原と山に同じ細かさの三角形が並び、尾根が崩れます。
4. 「岩」に切り替えて、細かい凸凹のある形でどこまで減らせるかを試してください。