A Comparison of Methods for Generating Poisson Disk Distributions

by syoyo

A Comparison of Methods for Generating Poisson Disk Distributions
http://www.cs.kuleuven.ac.be/publicaties/rapporten/cw/CW459.abs.html

タイルサンプラー野郎 Ares Lagae [1] による貴重な Poisson disk サンプリング手法の比較レポートを読みました。

まずレポートでは、結論として、

– 一様密度なら著者が提案した corner based poisson disk tiles が最強!
– インポータンスサンプリングするならしょうがねー、 recursive wang tiles に軍配をやるよ
(RWT を一様密度に使うと corner based より分布は悪いけどね)

です[2]。

以下、各種比較した手法に対する著者の主張をまとめると以下の通り。

– ダーツ投げ(dart throwing)系
遅いのでインタラクティブ系には使えない。[Jones 06], [Dunbar and Humphreys 06] は高速化手法を提案
しているが、それでも tile ベースの手法に比べれば遅い。また品質(半径)を上げようとすると Lloyd の緩和法
を使うことになってしまい、やっぱり遅くなってしまう。

– Tiled blue noise sampler [Hiller et al 2001]

品質が悪い(半径が小さい、スペクトル分布が悪い)ので勧めない。
タイルの境界と境界でないところで半径に差がある。

# 個人的には当時はこれ最強の blue noise sampler じゃね?と思っていましたが、
# 手法は常に古くなって新しいもので改善されていくものだなぁと実感。

– Penrose tile sampler [Ostromoukhov et al 2004]
– Recursive Wang Tiles [Kopf et al 2006]

どちらもスペクトルの品質は平均以下。
また、RWT の半径はおどろくほど低い。
RWT は一様密度に対しては使うべきでない。

私は [Hiller et al 01] でブルーノイズに出会ってから、Penrose tile sampler で衝撃を受けて、RWT, SWP で
さらに衝撃を受けてきました。

このサンプラーの分野はことごとく新発の手法が既存手法の欠点を明らかにし、それらを改善する手法が提案されてきました。
この分野ほど、毎年のようにその当時まで最強のサンプラーだったものが、
差分レベルではなくほとんど完全に新しい提案手法で更なる最強のサンプラーに
ドラマティックに塗り替えられていくのは、なかなか他の CG 分野でもなかったのではないか思います。
(SHexp までの PRT はこれに近いものがありますが)
この激動の(?)最強サンプラー合戦時代をリアルタイムで目の当たりにすることができて、
私はとても運がよかったと思います。

[1] http://www.cs.kuleuven.be/~ares/
[2] このレポートが出たのは Sampling with Polyominoes が発表されるまえであることに注意。
一様分布の場合に SWP と corner based ではどちらがよいかは調べてみる必要がある。

[Jones 06] Thouis Jones, Efficient Generation of Poisson-Disk Sampling Patterns.
http://people.csail.mit.edu/thouis/

[Dunbar and Humphreys 06] Daniel Dunbar and Greg Humphreys, A Spatial Data Structure for Fast Poisson-Disk Sample Generation.
http://www.cs.virginia.edu/~gfx/pubs/antimony/

[Hiller et al 2001] Stefan Hiller, Oliver Deussen and Alexander Keller, Tiled blue noise samples.
http://citeseer.ist.psu.edu/493970.html

[Ostromoukhov et al 04] Victor Ostromoukhov, Charles Donohue and Pierre-Marc Jodoin 2004, Fast Hierarchical Importance Sampling With Blue Noise Properties.
http://www.iro.umontreal.ca/~ostrom/publications/

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

Advertisements