skip to main content
10.1145/1275808.1276475acmconferencesArticle/Chapter ViewAbstractPublication PagessiggraphConference Proceedingsconference-collections
Article

Sampling with polyominoes

Published: 29 July 2007 Publication History

Abstract

We present a new general-purpose method for fast hierarchical importance sampling with blue-noise properties. Our approach is based on self-similar tiling of the plane or the surface of a sphere with rectifiable polyominoes. Sampling points are associated with polyominoes, one point per polyomino. Each polyomino is recursively subdivided until the desired local density of samples is reached. A numerical code generated during the subdivision process is used for thresholding to accept or reject the sample. The exact position of the sampling point within the polyomino is determined according to a structural index, which indicates the polyomino's local neighborhood. The variety of structural indices and associated sampling point positions are computed during the offline optimization process, and tabulated. Consequently, the sampling itself is extremely fast. The method allows both deterministic and pseudo-non-deterministic sampling. It can be successfully applied in a large variety of graphical applications, where fast sampling with good spectral and visual properties is required. The prime application is rendering.

Supplementary Material

JPG File (pps078.jpg)
MP4 File (pps078.mp4)

References

[1]
Clarke, A. L., 2006. The Poly Pages. http://www.recmath.com/PolyPages.
[2]
Dunbar, D., and Humphreys, G. 2006. A Spatial Data Structure for Fast Poisson-disk Sample Generation. ACM Transactions on Graphics, 25, 3, 503--508.
[3]
Golomb, S. W. 1996. Polyominoes: Puzzles, Patterns, Problems, and Packings. Princeton University Press.
[4]
Gorski, K. M., Hivon, E., Banday, A. J., Wandelt, B. D., Hansen, F. K., Reinecke, M., and Bartelmann, M. 2005. HEALPix - A Framework for High Resolution Discretization, and Fast Analysis of Data Distributed on the Sphere. The Astrophysical Journal, 622, 759--771.
[5]
Grünbaum, B., and Shephard, G. 1986. Tilings and Patterns. W. H. Freeman.
[6]
Kopf, J., Cohen-Or, D., Deussen, O., and Lischinski, D. 2006. Recursive wang tiles for real-time blue noise. ACM Transactions on Graphics 25, 3, 509--518.
[7]
Lagae, A., and Dutré, P. 2006. An Alternative for Wang Tiles: Colored Edges versus Colored Corners. ACM Transactions on Graphics, 25, 4, 1442--1459.
[8]
Ostromoukhov, V., Donohue, C., and Jodoin, P.-M. 2004. Fast Hierarchical Importance Sampling with Blue Noise Properties. ACM Transactions on Graphics, 23, 3, 488--495.
[9]
Pharr, M., and Humphreys, G. 2004. Physically Based Rendering: Form Theory to Implementation. Morgan Kaufmann.
[10]
Rousselle, F., Leblanc, L., Clarberg, P., Ostromoukhov, V., and Poulin, P. 2007. Hierarchical Threasholding for Efficient Sampling of the Product of All-Frequency Functions. Submitted work.
[11]
Ulichney, R. A. 1993. The Void-and-cluster Method for Dither Array Generation. In Proceedings SPIE, Human Vision, Visual Processing, Digital Displays IV, B. E. Rogowitz and J. P. Allebach, Eds., vol. 1913, 332--343.

Cited By

View all

Recommendations

Comments

Information & Contributors

Information

Published In

cover image ACM Conferences
SIGGRAPH '07: ACM SIGGRAPH 2007 papers
August 2007
1019 pages
ISBN:9781450378369
DOI:10.1145/1275808
Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 29 July 2007

Permissions

Request permissions for this article.

Check for updates

Author Tags

  1. blue noise
  2. deterministic sampling
  3. importance sampling
  4. non-periodic tiling
  5. polyominoes

Qualifiers

  • Article

Conference

SIGGRAPH07
Sponsor:

Acceptance Rates

SIGGRAPH '07 Paper Acceptance Rate 108 of 455 submissions, 24%;
Overall Acceptance Rate 1,822 of 8,601 submissions, 21%

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • Downloads (Last 12 months)12
  • Downloads (Last 6 weeks)1
Reflects downloads up to 19 Feb 2025

Other Metrics

Citations

Cited By

View all

View Options

Login options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Figures

Tables

Media

Share

Share

Share this Publication link

Share on social media