skip to main content
article

Recursive Wang tiles for real-time blue noise

Published:01 July 2006Publication History
Skip Abstract Section

Abstract

Well distributed point sets play an important role in a variety of computer graphics contexts, such as anti-aliasing, global illumination, halftoning, non-photorealistic rendering, point-based modeling and rendering, and geometry processing. In this paper, we introduce a novel technique for rapidly generating large point sets possessing a blue noise Fourier spectrum and high visual quality. Our technique generates non-periodic point sets, distributed over arbitrarily large areas. The local density of a point set may be prescribed by an arbitrary target density function, without any preset bound on the maximum density. Our technique is deterministic and tile-based; thus, any local portion of a potentially infinite point set may be consistently regenerated as needed. The memory footprint of the technique is constant, and the cost to generate any local portion of the point set is proportional to the integral over the target density in that area. These properties make our technique highly suitable for a variety of real-time interactive applications, some of which are demonstrated in the paper.Our technique utilizes a set of carefully constructed progressive and recursive blue noise Wang tiles. The use of Wang tiles enables the generation of infinite non-periodic tilings. The progressive point sets inside each tile are able to produce spatially varying point densities. Recursion allows our technique to adaptively subdivide tiles only where high density is required, and makes it possible to zoom into point sets by an arbitrary amount, while maintaining a constant apparent density.

Skip Supplemental Material Section

Supplemental Material

Low Resolution
High Resolution

References

  1. Cohen, M. F., Shade, J., Hiller, S., and Deussen, O. 2003. Wang tiles for image and texture generation. ACM Transactions on Graphics 22, 3 (Proc. SIGGRAPH 2003), 287--294. Google ScholarGoogle ScholarDigital LibraryDigital Library
  2. Cook, R. L. 1986. Stochastic sampling in computer graphics. ACM Transactions on Graphics 5, 1, 51--72. Google ScholarGoogle ScholarDigital LibraryDigital Library
  3. Cormen, T. H., Leiserson, C. E., Rivest, R. L., and Stein, C. 2001. Introduction to Algorithms, second ed. The MIT Press, Cambridge, MA, USA. Google ScholarGoogle ScholarDigital LibraryDigital Library
  4. Deussen, O., Hiller, S., Van Overveld, C. W. A. M., and Strothotte, T. 2000. Floating points: A method for computing stipple drawings. Computer Graphics Forum 19, 3 (Proc. Eurographics 2000), 40--51.Google ScholarGoogle ScholarCross RefCross Ref
  5. Dippé, M. A. Z., and Wold, E. H. 1985. Antialiasing through stochastic sampling. Computer Graphics 19, 3 (Proc. SIGGRAPH 85), 69--78. Google ScholarGoogle ScholarDigital LibraryDigital Library
  6. Dunbar, D., and Humphreys, G. 2006. A spatial data structure for fast Poisson-disk sample generation. ACM Transactions on Graphics 25, 3 (Proc. SIGGRAPH 2006). Google ScholarGoogle ScholarDigital LibraryDigital Library
  7. Durand, F., Ostromoukhov, V., Miller, M., Duranleau, F., and Dorsey, J. 2001. Decoupling strokes and high-level attributes for interactive traditional drawing. In Rendering Techniques 2001, 71--82. Google ScholarGoogle ScholarDigital LibraryDigital Library
  8. Efros, A. A., and Freeman, W. T. 2001. Image quilting for texture synthesis and transfer. In Proc. SIGGRAPH 2001, 341--346. Google ScholarGoogle ScholarDigital LibraryDigital Library
  9. Glassner, A. S. 1994. Principles of Digital Image Synthesis. Morgan Kaufmann Publishers Inc., San Francisco, CA, USA. Google ScholarGoogle ScholarDigital LibraryDigital Library
  10. Hertzmann, A. 1998. Painterly rendering with curved brush strokes of multiple sizes. In Proc. SIGGRAPH 98, 453--460. Google ScholarGoogle ScholarDigital LibraryDigital Library
  11. Hiller, S., Deussen, O., and Keller, A. 2001. Tiled blue noise samples. In Proc. Vison Modeling and Visualization 2001, 265--272. Google ScholarGoogle ScholarDigital LibraryDigital Library
  12. Hiller, S., Hellwig, H., and Deussen, O. 2003. Beyond stippling ---methods for distributing objects on the plane. Computer Graphics Forum 22, 3 (Proc. Eurographics 2003), 515--522.Google ScholarGoogle ScholarCross RefCross Ref
  13. Kalnins, R. D., Markosian, L., Meier, B. J., Kowalski, M. A., Lee, J. C., Davidson, P. L., Webb, M., Hughes, J. F., and Finkelstein, A. 2002. WYSIWYG NPR: drawing strokes directly on 3D models. ACM Transactions on Graphics 21, 3 (Proc. SIGGRAPH 2002), 755--762. Google ScholarGoogle ScholarDigital LibraryDigital Library
  14. Keller, A. 2004. Myths of computer graphics. In Monte Carlo and Quasi-Monte Carlo Methods 2004, Springer-Verlag, Berlin, Germany. Google ScholarGoogle ScholarDigital LibraryDigital Library
  15. Kollig, T., and Keller, A. 2002. Efficient multidimensional sampling. Computer Graphics Forum 21, 3 (Proc. Eurographics 2002), 557--563.Google ScholarGoogle ScholarCross RefCross Ref
  16. Kollig, T., and Keller, A. 2003. Efficient illumination by high dynamic range images. In Rendering Techniques 2003, 45--50. Google ScholarGoogle ScholarDigital LibraryDigital Library
  17. Lagae, A., and Dutré, P. 2005. A procedural object distribution function. ACM Transactions on Graphics 24, 4, 1442--1461. Google ScholarGoogle ScholarDigital LibraryDigital Library
  18. Lloyd, S. 1983. An optimization approach to relaxation labeling algorithms. Image and Vision Computing 1, 2, 85--91.Google ScholarGoogle ScholarCross RefCross Ref
  19. McCool, M., and Fiume, E. 1992. Hierarchical poisson disk sampling distributions. In Proc. Graphics interface '92, 94--105. Google ScholarGoogle ScholarDigital LibraryDigital Library
  20. Mitchell, D. P. 1987. Generating antialiased images at low sampling densities. Computer Graphics 21, 4 (Proc. SIGGRAPH 87), 65--72. Google ScholarGoogle ScholarDigital LibraryDigital Library
  21. Mitchell, D. P. 1991. Spectrally optimal sampling for distribution ray tracing. Computer Graphics 25, 4 (Proc. SIGGRAPH 91), 157--164. Google ScholarGoogle ScholarDigital LibraryDigital Library
  22. Ostromoukhov, V., Donohue, C., and Jodoin, P.-M. 2004. Fast hierarchical importance sampling with blue noise properties. ACM Transactions on Graphics 23, 3 (Proc. SIGGRAPH 2004), 488--495. Google ScholarGoogle ScholarDigital LibraryDigital Library
  23. Praun, E., Hoppe, H., Webb, M., and Finkelstein, A. 2001. Real-time hatching. In Proc. SIGGRAPH 2001, 579--584. Google ScholarGoogle ScholarDigital LibraryDigital Library
  24. Salisbury, M. P., Anderson, S. E., Barzel, R., and Salesin, D. H. 1994. Interactive pen-and-ink illustration. In Proc. SIGGRAPH 94, 101--108. Google ScholarGoogle ScholarDigital LibraryDigital Library
  25. Secord, A., Heidrich, W., and Streit, L. 2002. Fast primitive distribution for illustration. In Rendering Techniques 2002, 215--226. Google ScholarGoogle ScholarDigital LibraryDigital Library
  26. Secord, A. 2002. Weighted voronoi stippling. In Proc. NPAR 2002, 37--43. Google ScholarGoogle ScholarDigital LibraryDigital Library
  27. Shirley, P. 1991. Discrepancy as a quality measure for sample distributions. In Proc. Eurographics '91, 183--193.Google ScholarGoogle Scholar
  28. Sutherland, I. E. 1964. Sketch pad a man-machine graphical communication system. In Proc. SHARE design automation workshop '64, 6.329--6.346. Google ScholarGoogle ScholarDigital LibraryDigital Library
  29. Ulichney, R. A. 1988. Dithering with blue noise. Proc. IEEE 76, 1, 56--79.Google ScholarGoogle ScholarCross RefCross Ref
  30. Wang, H. 1961. Proving theorems by pattern recognition II. Bell Systems Technical Journal 40, 1--42.Google ScholarGoogle ScholarCross RefCross Ref
  31. Wang, H. 1965. Games, logic and computers. Scientific American 213, 5, 98--106.Google ScholarGoogle ScholarCross RefCross Ref
  32. Winkenbach, G., and Salesin, D. H. 1994. Computer-generated pen-and-ink illustration. In Proc. SIGGRAPH 94, 91--100. Google ScholarGoogle ScholarDigital LibraryDigital Library

Index Terms

  1. Recursive Wang tiles for real-time blue noise

          Recommendations

          Comments

          Login options

          Check if you have access through your login credentials or your institution to get full access on this article.

          Sign in

          Full Access

          • Published in

            cover image ACM Transactions on Graphics
            ACM Transactions on Graphics  Volume 25, Issue 3
            July 2006
            742 pages
            ISSN:0730-0301
            EISSN:1557-7368
            DOI:10.1145/1141911
            Issue’s Table of Contents

            Copyright © 2006 ACM

            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]

            Publisher

            Association for Computing Machinery

            New York, NY, United States

            Publication History

            • Published: 1 July 2006
            Published in tog Volume 25, Issue 3

            Permissions

            Request permissions about this article.

            Request Permissions

            Check for updates

            Qualifiers

            • article

          PDF Format

          View or Download as a PDF file.

          PDF

          eReader

          View online with eReader.

          eReader