Lp Centroidal Voronoi Tessellation and its Applications

INRIAの研究者 Bruno LevyのSIGGRAPH 2010の論文です．

Mesh Processing がよくまとまっているこの本の著者の一人です．

Polygon Mesh Processing

ここにスライド等もあります．
http://www.pmp-book.org/

通常のCVTではボロノイ点から各点のL2ノルムを最小化します．
有名な方法はLloyd’s algorithmで，ボロノイ領域の点をボロノイ領域の重心に移動させることで均等にボロノイ点を配置することができます，
これを収束するまで繰り返すとボロノイ領域が綺麗にtessellationされます．
応用としてはリメッシングがあります．
CVTで拡張点を移動させて元のメッシュにプロジェクションしてあげるとクオリティの高いメッシュにリメッシングすることができます．

この論文ではそのCVTのL2ノルムだけでなくLpノルムの最小化を考えるように一般化しています．
Lpノルムを考えるとなにがいいかというと，L2ノルムの場合では，等距離の領域が円状になりますが，
L∞ノルムの場合では正方形に限りなく近くなります．正方形の領域だと四角形の領域にきれいに並べることができます．
この論文ではさらにノルムに対して変換行列Mを考えてあげることによりanisotropic な領域で距離を等しくすることができます．

Applicationとして．Anisotropic Remeshing や，Fully Automatic Feature-Sensitive Remeshing(これはFeatureにタグ付けしているし，もとのSurfaceがわかっている状態)
Variational な quad meshing(L8でだいたい正方形っぽくなって，Voronoi領域の四角形が綺麗にならぶので隣接するVoronoi点を結んであげるとquad meshになる), Hex meshing などが紹介されている．

Supplymental Material の気合の入り方もすごい．