ポリゴンリダクションのアルゴリズム

ポリゴンリダクションとは

モデルのポリゴンを削除すること。
実際の実行結果↓
（左から約4000ポリゴン、約2000ポリゴン、約1000ポリゴン、約200ポリゴン）

Level of Detail

同じオブジェクトに対して、構成するポリゴン数が異なるモデルを複数用意する。
カメラとオブジェクトの距離が近い場合は、ポリゴン数が多いモデルを表示する。
逆に遠い場合は、ポリゴン数が少ないモデルを表示する。
結果的に、GPUの負荷の低減になる。

実装する必要性

端末に最適化されたLevel of Detail を実現するため。
当然3DCAD上でポリゴンリダクションは可能。
しかし、複数のモデルを用意するのが面倒。
アプリ上でポリゴンリダクションを実行することで、端末の画面や計算能力に応じて、最適なポリゴン数での表示ができる。
アプリ初回起動時に実行して保存する。

ポリゴンリダクションのアルゴリズム

ポリゴンリダクションの処理前と後

１回のポリゴンリダクションの処理をすると、
・１つの辺を１つの頂点にマージ(l0 -> P)
・２つの辺を削除
・２つの面を削除(H1, H5)
・２つの頂点を削除(P0, P1)

マージする辺の決定方法

QEM(Quadratic Error Metrics)を計算する。

QEMの計算方法

辺をマージした後の新しい頂点候補の点：P
マージされる辺の１近傍の面：H1 ~ Hn
HiとPの距離をDi、Qi = Di ^2
QEM = ΣQi

辺をマージした後の頂点の最適化

マージする辺上の点Pにマージする。
（UVマップの値も同時に決定したいため）
平面：Hi = ai*x + bi*y + ci*z + di = 0
(法線方向のため√(a^2 + b^2 + c^2) = 1)
辺：始点P0、終点P1、線分上の点P(X, Y, Z)
ここでP = k(P1 - P0) + P0 (k:定数)
u = (P1 - P0)とおくと、P = k・u + p0
PとHiの距離をDi、Qi = Di^2、QEM = ΣQi
QEMを最小にするkのときPは最適な頂点
kを求める
Di = |ai・X + bi・Y + ci・Z + di| / √(a^2 + b^2 + c^2) = |ai・X + bi・Y + ci・Z + di|
Di=(ai, bi, ci, di)・(X, Y, Z, 1)^t
ni = (ai, bi, ci, di), v = (X, Y, Z, 1)とおくと
Qi = Di^2 = (ai・X + bi・Y + ci・Z + di)^2
= (ni・v^t)^2 = v・ni^t・ni・v^t
Ai = ni^t・ni、A = ΣAiとおくと
Qi = v・Ai・v^t
QEM = ΣQi = v・ΣAi・v^t = v・A・v^t
QEM = (k・u + P0)・A・(k・u + P0)^t
= (k・u + P0)・A・(k・u^t + P0^t)
= k^2・u・A・u^t + k(u・A・P0^t + P0・A・u^t) + P0・A・P0^t
QEM' = 2k・u・A・u^t + u・A・P0^t + P0・A・u^t
u・A・u^t > 0より、QEM' = 0のとき、QEMが最小
k = - (u・A・P0^t + P0・A・u^t) / 2(u・A・u^t)
よって、QEMを最小にする点Pは下式となる。
P = k(P1 - P0) + P0
(k = - (u・A・P0^t + P0・A・u^t) / 2(u・A・u^t))

ポリゴンリダクションの実行手順

手順
①：各辺について、QEMを計算する。
②：QEMが最小の辺をマージする。
③：①に戻る。

QEMを求めるために必要なデータ

k = - (u・A・P0^t + P0・A・u^t) / 2(u・A・u^t)
上のkについてを眺めると、P0、P1の座標と、その２頂点の近傍の平面の方程式で解ける。
平面の方程式は、法線方向と1頂点から求める。
CADでモデルを出力する際に、法線方向のデータを含ませておけばOK