Recursive Wang Tiles for Real-Time Blue Noise

by syoyo

Johannes Kopf, Daniel Cohen-Or, Oliver Deussen and Dani Lischinski,
Recursive Wang Tiles for Real-Time Blue Noise
SIGGRAPH 2006.
http://johanneskopf.de/publications/blue_noise

まだ abstract とムービーしか見ていませんが、これもすごいです。デモムービーを見るだけでも(サンプリング野郎からすると)すごいのが分かるかと思いますが、

– 任意の N(点の数)
– 決定的(deterministic)
– ブルーノイズ性質
– リアルタイム
– インポータンスサンプル可能
– プログレッシブかつ stratified

と、ほぼ最強の性質を持っています。私が長年求めていた究極のサンプルジェネレータかもしれません。
penrose tile sampler を Wang tile + 階層化へと拡張した手法のようですね。
実際にレンダラの light transport やアンチエイリアシングに実装してみたいところです。
今年の SIGGRAPH はすばらしい論文がいっぱいです。

Abstract 日本語訳

良質な分布を持つ点群は、コンピュータグラフィックスのいろいろな分野で重要な役割を演じています。
たとえば、アンチエイリアシング、大域照明(グローバルイルミネーション)、ハーフトーン処理、ノンフォトリアリスティックレンダリング、ポイントベースド・モデリング、ポイントベースド・レンダリング、ジオメトリ処理などが挙げられます。

本論文では、ブルーノイズ(blue noise)フーリエスペクトルおよび高い視覚的品質を保ちながら、非常に大量の点群を高速に生成する新しい手法を提案します。

本手法では、非周期的な点群を生成します。点群は任意の広い領域に対して分布させることが可能です。
点群の局所的密度は、最大密度の限度をあらかじめ設定することなく、任意のターゲット密度関数により指定することができます。

我々の手法は決定的(deterministic)であり、タイルベース(tile-based)です。
つまり、無限に広がる可能性のある点群であっても、その局所的な位置は必要に応じて一貫して再生成することができます。

本技法のメモリ使用量は一定であり、点群の局所的位置を生成するコストは、その(生成したい)局所的位置の領域に対応するターゲット密度の積分に比例します。

これらの性質により、本手法は各種リアルタイムなインタラクティブアプリケーションに非常に適しています(そのいくつかは本論文の中でデモします)。

我々の手法hは、注意深く構築されたプログレッシブで再帰的なブルーノイズワンタイル(blue noise Wang tiles)を利用しています。
ワンタイルを利用することで、無限の非周期的なタイリング(タイル張り)の生成を可能にしています。

各タイル内でプログレッシブな点群を生成することで、空間的に点密度を変化させることができます。再帰により、本手法は高密度が必要な部分のみに適応的なタイルの分割を行うことがが可能になっています。これにより、見かけ上は一定の密度を保ちつつも、点群内に任意にズームしていくことが可能です。

Advertisements