Qiita Teams that are logged in
You are not logged in to any team

Log in to Qiita Team
Community
OrganizationEventAdvent CalendarQiitadon (β)
Service
Qiita JobsQiita ZineQiita Blog
18
Help us understand the problem. What is going on with this article?

More than 3 years have passed since last update.

@fuziki

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

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

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

Level of Detail

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

実装する必要性

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

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

ポリゴンリダクションの処理前と後
スライド1.png

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

マージする辺の決定方法

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

QEMの計算方法

辺をマージした後の新しい頂点候補の点:P
マージされる辺の1近傍の面: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の座標と、その2頂点の近傍の平面の方程式で解ける。
平面の方程式は、法線方向と1頂点から求める。
CADでモデルを出力する際に、法線方向のデータを含ませておけばOK

18
Help us understand the problem. What is going on with this article?
Why not register and get more from Qiita?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
18
Help us understand the problem. What is going on with this article?