關(guān)于 Fast Poisson-Disk Sample Generation
Chaos Chiao
一、隨便說說
從MSRA回來后仔細(xì)地想了很多事情，看著自己一度覺得很了不起的渲染器，覺得有點(diǎn)可笑。大而全的東西，注定是非常容易失敗的，尤其對(duì)于單干，把東西鋪得太開，就很危險(xiǎn)了。盡管我再做GS的時(shí)候已經(jīng)有過這樣的教訓(xùn)了。
感覺這段時(shí)間有非常強(qiáng)烈變強(qiáng)的欲望，但知道欲速則不達(dá)，所以還是停下了項(xiàng)目，重新找出來了很多布滿塵土的數(shù)學(xué)書，翻著做題。不知為什么，很多以前一看見就撓頭的題目，現(xiàn)在卻變得非常簡(jiǎn)單，可能是長(zhǎng)期的編程徹底地改變了我的思維方式吧。
但還是受不了Coding的誘惑，就像抽煙一樣（雖然我不抽煙，但也知道它很上癮），于是想找一些課題研究一下，便打開SIGGRAPH 2006的Paper list，搜索一些感興趣的。第一眼就看到了< A Spatial Structure for Fast Poisson-Disk Sample Generation >這篇文章。感覺挺驚訝的，近來很少看到Sampling Pattern的研究，似乎已經(jīng)沒什么可以再深入下去的余地了，但它卻提到了在O(NlogN)的復(fù)雜度內(nèi)可以生成Poisson Disk Pattern。不可思議呢，以前我在做Sampling & Reconstruction的時(shí)候曾經(jīng)嘗試過研究Poisson Disk，但還是用一貫的思路，就是所謂Dart-Throwing。也有想要改進(jìn)這種方法的念頭，但最后還是沒有深入下去，因?yàn)橛肧obol Pattern生成的圖像質(zhì)量已經(jīng)非常不錯(cuò)了，而且Sobol可以預(yù)計(jì)算序列，運(yùn)行時(shí)幾乎沒有任何耗時(shí)。
稍微看一下，了解了大概的算法，覺得雖然有一定的難度，但要做一個(gè)這樣的Implementation還是不太困難的。奮戰(zhàn)一天下來，算是做出來了一個(gè)，然后下面分享一些我的想法。
二、Sampling & Reconstruction、Poisson Disk
這已經(jīng)是我第二篇文章討論Sampling & Reconstruction了，上一篇只是因?yàn)镃hinaDV有一個(gè)瘋子出來說什么反混淆與反走樣，我詳細(xì)解說一下什么是Sampling & Reconstruction。當(dāng)然，這其實(shí)屬于圖形學(xué)、乃至信號(hào)處理里面最簡(jiǎn)單的概念。
Sampling主要分為Uniform Sampling、Adaptive Sampling和Stochastic Sampling。Uniform Sampling是直接在一個(gè)網(wǎng)格或者經(jīng)過抖動(dòng)的網(wǎng)格Pattern上進(jìn)行采樣，它受網(wǎng)格分辨率限制。當(dāng)網(wǎng)格分辨率遠(yuǎn)低于Source的頻率時(shí)，Uniform Sampling會(huì)出現(xiàn)非常大的誤差，其直接結(jié)果就是不連續(xù)的鋸齒，未經(jīng)抖動(dòng)的網(wǎng)格采樣還可能會(huì)產(chǎn)生嚴(yán)重的水紋波。Adaptive Sampling是在Uniform Sampling的基礎(chǔ)上進(jìn)行改良的，當(dāng)鄰近兩個(gè)采樣點(diǎn)之間的差大于閥值時(shí)，再兩點(diǎn)之間插入一個(gè)新的采樣點(diǎn)，這樣可以極大地避免不連續(xù)情況。但當(dāng)首個(gè)Sample Pattern的分布和Source的頻率相距太大時(shí)，雖然鄰近兩點(diǎn)的差值在閥值內(nèi)， 有可能Source在兩點(diǎn)之間有更多的連續(xù)變化存在，這樣的重構(gòu)會(huì)忽略掉采樣點(diǎn)之間的高頻變化。
Stochastic Sampling是完全的隨機(jī)采樣，它不受網(wǎng)格限制，使用一系列在采樣區(qū)域內(nèi)的散亂采樣點(diǎn)進(jìn)行采樣，不根據(jù)網(wǎng)格劃分采樣點(diǎn)。Stochastic Sampling非常依賴Pattern的特性，Pattern的分布直接決定了采樣的質(zhì)量。Cook提出了使用Poisson Disk分布的Pattern會(huì)非常適合二維的采樣，他指出人眼中的感光細(xì)胞也成Poisson Disk分布。所謂Poisson Disk Pattern即所有的采樣點(diǎn)到其余所有的采樣點(diǎn)的距離都大于一個(gè)閥值，可以認(rèn)為未抖動(dòng)的網(wǎng)格是Poisson Disk Pattern的其中一個(gè)特例。
這樣Poisson Disk就要求任意兩點(diǎn)之間的距離不小于閥值，比如10x10的區(qū)域內(nèi)生成100個(gè)(以上)的采樣點(diǎn)，閥值可以采用0.9（大于等于1將有可能使有的采樣點(diǎn)不能放到區(qū)域內(nèi)）。
傳統(tǒng)生成Poisson Disk序列的方法為Dart-Throwing?？梢园堰@個(gè)原始算法看作買六合彩。它不斷“Throw”一個(gè)隨機(jī)的采樣點(diǎn)，然后和已有的采樣點(diǎn)集合比較距離，若遇到小于閥值的就Discard，再重新“Throw”一個(gè)新的隨機(jī)采樣點(diǎn)；如果符合條件則“Dart”中了，添加到采樣點(diǎn)集合里。就這樣不斷循環(huán)直到完全填滿區(qū)域，或者生成的采樣點(diǎn)“足夠多”為止。如果采樣區(qū)域非常大、或者采樣點(diǎn)數(shù)目巨大，那么要計(jì)算完所有采樣點(diǎn)的幾率真的比中六合彩還要低得多。上了10,000個(gè)點(diǎn)的填充計(jì)算是基本上不可能完成的（根據(jù)我的經(jīng)驗(yàn)……），所以在程序運(yùn)行時(shí)生成Poisson Disk Pattern是非常不切實(shí)際的做法。
可是Poisson Disk分布的確太好，太適合各種圖像重構(gòu)的采樣了，所以很多人會(huì)預(yù)計(jì)算一個(gè)足夠大的Pattern，再把它Tile到采樣區(qū)域里。
另外也提一下Sobol序列，Sobol是一個(gè)Quasi-Monte Carol序列，可以擴(kuò)展到任意維度，它是一個(gè)穩(wěn)定的、覆蓋率非常好的隨機(jī)序列，用在Stochastic Sampling中也可以得到非常高質(zhì)量的采樣效果。Sobol已經(jīng)被廣泛運(yùn)用到各種圖形圖像系統(tǒng)中。
三、改進(jìn)的Dart-Throwing
Dart-Throwing屬于一種隨機(jī)算法，無法計(jì)算它的大O，因?yàn)樗踔敛豢赡芙Y(jié)束，所以一直無法在程序中用作即時(shí)計(jì)算。但Poisson Disk的分布有非常獨(dú)特的特點(diǎn)，可以讓我們預(yù)先一些不可能中標(biāo)的區(qū)域Discard掉，然后在100%中Dart的區(qū)域中Throw，這樣可以保證我們的算法每次都是神投手。
哪些區(qū)域會(huì)100%中標(biāo)？先看Poisson Disk的定義，即距離其它所有采樣點(diǎn)的距離都在閥值外。這樣在閥值距離內(nèi)的所有范圍都不可能中。如果閥值為r，已知采樣點(diǎn)P，則以P為中心半徑r~2r的圓環(huán)內(nèi)是最佳的采樣點(diǎn)出現(xiàn)區(qū)域。把隨機(jī)數(shù)映射到這個(gè)范圍內(nèi)，可以得到符合條件的采樣點(diǎn)。根據(jù)Paper，可以建立一個(gè)能進(jìn)行布爾運(yùn)算的貝殼形representation，每次把新的采樣點(diǎn)和圓環(huán)（或者貝殼）相減，得到一個(gè)貝殼狀的區(qū)域，那么新的采樣點(diǎn)可以在貝殼區(qū)域內(nèi)生成。
可是貝殼狀的區(qū)域，而且涉及二維布爾運(yùn)算，這會(huì)非常復(fù)雜，況且r~2r范圍內(nèi)生成的采樣點(diǎn)，并不能保證覆蓋率達(dá)到最大化，也有可能出現(xiàn)采樣點(diǎn)過于稀疏而導(dǎo)致無法插入新點(diǎn)。
四、Boundary Sampling
當(dāng)我們把r~2r的定義再進(jìn)一步深入研究下去，可以得到實(shí)際上如果新建立的點(diǎn)在半徑等于r的圓上，可以使覆蓋率最大化，即浪費(fèi)的空間最少（但這部等于所有采樣點(diǎn)之間的距離都是r）。那么我們就把隨機(jī)序列映射到一個(gè)貝殼區(qū)域內(nèi)簡(jiǎn)化到直接把單個(gè)隨機(jī)數(shù)映射到圓（或者弧線）上。
套用原來的思路，建立一種以圓弧為基礎(chǔ)的representation，可以進(jìn)行圓弧與圓之間的布爾運(yùn)算，相比之下計(jì)算要簡(jiǎn)單很多，只用極坐標(biāo)和簡(jiǎn)單的三角函數(shù)計(jì)算已經(jīng)可以完成了。然后通過指定一個(gè)原始的采樣點(diǎn)，我們可以一步一步地在新的點(diǎn)的圓弧上生成符合條件的新點(diǎn)。
?
在正方形區(qū)域內(nèi)生成一個(gè)Poisson Disk Pattern，從點(diǎn)0開始?？梢钥吹揭渣c(diǎn)0為中心，r為半徑的圓上任意一點(diǎn)插入的采樣點(diǎn)都符合Poisson Disk分布，所以可以很簡(jiǎn)單地直接在圓上進(jìn)行隨機(jī)插值。
?
點(diǎn)1是新插入的采樣點(diǎn)。分別以兩點(diǎn)為圓心、r為半徑的圓面相交的區(qū)域是不可能出現(xiàn)符合Poisson Disk分布的區(qū)域，所以可以直接把這部分的圓弧刪除掉（藍(lán)色），剩下（白色）的圓弧則是可以插入新的采樣點(diǎn)的區(qū)域。
?
如此這般，繼續(xù)在可能的弧線上插入新的采樣點(diǎn)，這些點(diǎn)集就完全符合Poisson Disk分布，而且可以達(dá)到最優(yōu)覆蓋率。
?
當(dāng)所有的圓弧都用完了以后，我們就得到了一個(gè)非常好的Poisson Disk Pattern了。
五、Implementation
關(guān)鍵在于可以進(jìn)行布爾運(yùn)算的圓弧的representation，我用了極坐標(biāo)來表示圓弧，這樣二維布爾運(yùn)算變成了簡(jiǎn)單的加減運(yùn)算。同時(shí)我建立了一張表來快速查詢鄰近的采樣點(diǎn)，而空閑采樣點(diǎn)集合則使用了std::set儲(chǔ)存。其實(shí)上面已經(jīng)解釋得挺清楚的了，附上動(dòng)態(tài)生成Pattern的Demo和代碼。Demo打開后不斷按 Space 就可以看到采樣點(diǎn)的生成過程。
Demo & Source
