ACM Trans. Graph. (Proceedings of SIGGRAPH 2017)

An Adaptive Point Sampler on a Regular Lattice

Abdalla G. M. Ahmed1       Till Niese1       Hui Huang2       Oliver Deussen1,3


1University of Konstanz, Germany
2Shenzhen University, China
3SIAT, China



(a) The proposed ART (Adaptive Regular Tiles) sampler uses a self-similar regular tile set with 1 sample per tile to supply sequences of blue-noise samples. (b) Tiled multi-class sets can be used to partition a tiled blue noise set into separate blue-noise sets. The two bottom lines show the filling order of our recursive tile in (a). First, sample points are filled in that are shared by one of the respective child tiles. The parent tile then visits the remaining children (in an optimized order) and instructs them to add their samples. For each subsequent 16 (number of children) samples, control is passed recursively to the children -- in the same order -- to add more samples.



Abstract

We present a framework to distribute point samples with controlled spectral properties using a regular lattice of tiles with a single sample per tile. We employ a word-based identification scheme to identify individual tiles in the lattice. Our scheme is recursive, permitting tiles to be subdivided into smaller tiles that use the same set of IDs. The corresponding framework offers a very simple setup for optimization towards different spectral properties. Small lookup tables are sufficient to store all the information needed to produce different point sets. For blue noise with varying densities, we employ the bit-reversal principle to recursively traverse sub-tiles. Our framework is also capable of delivering multi-class blue noise samples. It is well-suited for different sampling scenarios in rendering, including area-light sampling (uniform and adaptive), and importance sampling. Other applications include stippling and distributing objects.


Interactive Demos

Grid Morphing: In this demo, you can draw samples right from this page, scaled to unit area. Drag to move around, use the mouse wheel or pinch to zoom. What You See Is What You Get!

2757 points
You need to upgrade your browser to view this.
Show Strata


Sequences: In this demo we compare the progressive (self-coincident) variant of ART (left) to the post-optimized variant (right). The size of the tables is larger for the latter. Drag the slider to increase or decrease the number of samples.

 

Video

Downloads

Get for free at ACM digital library
Source Code
ZIP (2.3 MB)

Bibtex

@article{Ahmed:2017:APS:3072959.3073588,
 author = {Ahmed, Abdalla G. M. and Niese, Till and Huang, Hui and Deussen, Oliver},
 title = {{An Adaptive Point Sampler on a Regular Lattice}},
 journal = {ACM Trans. Graph.},
 issue_date = {July 2017},
 volume = {36},
 number = {4},
 month = jul,
 year = {2017},
 issn = {0730-0301},
 pages = {138:1--138:13},
 articleno = {138},
 numpages = {13},
 url = {http://doi.acm.org/10.1145/3072959.3073588},
 doi = {10.1145/3072959.3073588},
 acmid = {3073588},
 publisher = {ACM},
 address = {New York, NY, USA},
 keywords = {blue noise, monte carlo, multi-class blue noise, quasi-monte carlo,
             sampling, self-similarity, thue-morse word, tiling},
}

Acknowledgments

We thank the anonymous reviewers for their detailed feedback to improve the paper. Thanks to Cengiz Öztireli for sharing the grid test scene. Thanks to Carla Avolio for the voice over of the supporting video clip. This work was partially funded by Deutsche Forschungsgemeinschaft Grant (DE-620/22-1), the National Foreign 1000 Talent Plan (WQ201344000169), Leading Talents of Guangdong Program (00201509), NSFC (61522213, 61379090, 61232011), Guangdong Science and Technology Program (2015A030312015), and Shenzhen Innovation Program (JCYJ20151015151249564).