ワナビから貴方へ　独り言の吐き溜め

最近試してみたポリゴンリダクションの方法は

Quadratic Error Metricという手法を使って、元の形の歪みを評価する方法。

http://www.riken.go.jp/lab-www/V-CAD/kokai/No200202.pdf

↑　元の論文

 単純に説明すると

ポリゴンリダクションによって移動した頂点の、『元の面からの距離の2乗和』を値とする

当然最初は面上に頂点が載っているわけなので0

頂点数が減少して移動すると、元の面から距離が生じる。

それの2乗の和が最小になるように頂点を移動させていく

そうすれば元の形からあまり歪まずに頂点数減らせるよね、って話

具体的にはちょっと数学的になるけれど

一つの面の正規化法線ベクトル（a,b,c）とすると 

面上の点（x,y,z）は

ax+by+cz +d =0をみたす

 つまり(a b c d)^t  (x y z 1)　= 0

この二乗がQEMなので

Q(v)=((a b c d)^t (x y z 1))^2

　ベクトルv = (x y z 1),とすると

Q(v) = v^t ((a b c d) (a b c d)^t) v

4×4の対称行列A_i＝((a b c d) (a b c d)^t)とおける

で、このAは面ごとに定まってるので、頂点の属する面を全て足し合わせる

Q(v) = v^t ( Σ　A_i) vとなる

これをAとすると

Q = v^t A v

ちょっと面倒だけどAの3×3部分を新たなAとして

ベクトルb　スカラｃとすると

Q　＝ v^t A v  + 2bv + c　とかける

これを最小化するvの値が移動後の頂点の位置になる

もちろん最初は元の位置で０

ただし二つの頂点を結合（辺を消去）して 新たな頂点を作る時

このAを二つの頂点のAの和とする 

 最小化するｖを求めるにはvで微分して求める

 2Av + 2b=0

つまりv = - A^(-1) bとして求まる

３×３の逆行列はライブラリを利用して求めると楽

Eigen３を使ったけれど、OpenCVなどでも良かったかなと思ったり

これで最適頂点が求まる