Ares Lagae
Philip Dutré
Abstract
In this article we revisit the concept of Wang tiles and introduce corner tiles, square tiles with colored corners. During past years, Wang tiles have become a valuable tool in computer graphics. Important applications of Wang tiles include texture synthesis, tile-based texture mapping, and generating Poisson disk distributions. Through their colored edges, Wang tiles enforce continuity with their direct neighbors. However, Wang tiles do not directly constrain their diagonal neighbors. This leads to continuity problems near tile corners, a problem commonly known as the corner problem. Corner tiles, on the other hand, do impose restrictions on their diagonal neighbors, and thus are not subject to the corner problem. In this article we show that previous applications of Wang tiles can also be done using corner tiles, but that corner tiles have distinct advantages for each of these applications. Compared to Wang tiles, corner tiles are easier to tile, textures synthesized with corner tiles contain more samples from the original texture, corner tiles reduce the required texture memory by a factor of two for tile-based texture mapping, and Poisson disk distributions generated with corner tiles have better spectral properties. Corner tiles result in cleaner, simpler, and more efficient applications.
- Ball, W. R. 1926. Mathematical Recreations and Essays. MacMillan, Indianapolis, IN.Google Scholar
- Berger, R. 1966. The Undecidability of the Domino Problem. American Mathematical Society.Google Scholar
- Cohen, M. F., Shade, J., Hiller, S., and Deussen, O. 2003. Wang tiles for image and texture generation. ACM Trans. Graph., 287--294. Google Scholar
- Cook, R. L. 1986. Stochastic sampling in computer graphics. ACM Trans. Graph. 5, 1, 51--72. Google Scholar
- Culik, II, K. 1996. An aperiodic set of 13 Wang tiles. Discrete Math. 160, 1--3, 245--251. Google Scholar
- DeBonet, J. S. 1997. Multiresolution sampling procedure for analysis and synthesis of texture images. In Computer Graphics Proceedings. Annual Conference Series, 361--368. Google Scholar
- Deussen, O., Hanrahan, P., Lintermann, B., Měch, R., Pharr, M., and Prusinkiewicz, P. 1998. Realistic modeling and rendering of plant ecosystems. Computer Graphics Proceedings. Annual Conference Series, 275--286. Google Scholar
- Dippé, M. A. Z. and Wold, E. H. 1985. Antialiasing through stochastic sampling. In Proceedings of the 12th Annual Conference Computer Graphics and Interactive Technology. 19, 3, 69--78. Google Scholar
- Ebert, D. S., Musgrave, F. K., Peachey, D., Perlin, K., and Worley, S. 2002. Texturing and Modeling: A Procedural Approach. Morgan Kaufmann, San Fransisco, CA. Google Scholar
- Efros, A. A. and Freeman, W. T. 2001. Image quilting for texture synthesis and transfer. In Proceedings of the 28th Annual Conference Computer Graphics and Interactive Technology. 341--346. Google Scholar
- Efros, A. A. and Leung, T. K. 1999. Texture synthesis by non-parametric sampling. In Proceedings of the International Conference on Computer Vision. 1033--1038. Google Scholar
- Fu, C.-W. and Leung, M.-K. 2005. Texture tiling on arbitrary topological surfaces using Wang tiles. In Rendering Techniques. 99--104. Google Scholar
- Glassner, A. 1999. Andrew Glassner's Notebook: Recreational Computer Graphics. Morgan Kaufmann, San Fransisco, CA. Google Scholar
- Grünbaum, B. and Shepard, G. C. 1986. Tilings and Patterns. W. H. Freeman. Google Scholar
- Heeger, D. J. and Bergen, J. R. 1995. Pyramid-based texture analysis/synthesis. In Proceedings of the 22nd Annual Conference Computer Graphics and Interactive Techniques. 229--238. Google Scholar
- Hiller, S., Deussen, O., and Keller, A. 2001. Tiled blue noise samples. In Proceedings of the Vision Modeling Visualization, 265--272. Google Scholar
- Knuth, D. E. 1968. The Art of Computer Programming Conference. vol. 1. Addison-Wesley, Reading, MA.Google Scholar
- Kwatra, V., Essa, I., Bobick, A., and Kwatra, N. 2005. Texture optimization for example-based synthesis. ACM Trans. Graph. 24, 3, 795--802. Google Scholar
- Kwatra, V., Schödl, A., Essa, I., Turk, G., and Bobick, A. 2003. Graphcut textures: Image and video synthesis using graph cuts. ACM Trans. Graph. 22, 3, 277--286. Google Scholar
- Lagae, A. and Dutré, P. 2005a. A procedural object distribution function. ACM Tran. Graph. 24, 4. Google Scholar
- Lagae, A. and Dutré, P. 2005b. Template Poisson disk tiles. Report CW 413, Department of Computer Science, K.U. Leuven, Leuven, Belgium. May.Google Scholar
- Lagae, A. and Dutré, P. 2006a. A comparison of methods for generating Poisson disk distributions. Report CW 459, Department of Computer Science, K.U. Leuven, Leuven, Belgium. Aug.Google Scholar
- Lagae, A. and Dutré, P. 2006b. The tile packing problem. Report CW 461, Department of Computer Science, K.U. Leuven, Leuven, Belgium. Aug.Google Scholar
- Lagae, A., Kari, J., and Dutré, P. 2006. Aperiodic sets of square tiles with colored corners. Report CW 460, Department of Computer Science, K.U. Leuven, Leuven, Belgium. Aug.Google Scholar
- Lefebvre, S. and Neyret, F. 2003. Pattern-Based procedural textures. In Proceedings of the Symposium on Interactive 3D Graphics. 203--212. Google Scholar
- Liang, L., Liu, C., Xu, Y.-Q., Guo, B., and Shum, H.-Y. 2001. Real-Time texture synthesis by patch-based sampling. ACM Trans. Graph. 20, 3, 127--150. Google Scholar
- Liu, Y., Lin, W.-C., and Hays, J. 2004. Near-Regular texture analysis and manipulation. ACM Trans. Graph. 23, 3, 368--376. Google Scholar
- Lloyd, S. P. 1982. Least squares quantization in PCM. IEEE Trans. Info. Theory 28, 2, 129--137.Google Scholar
- MacMahon, M. P. A. 1921. New Mathematical Pastimes. Cambridge University Press, New York.Google Scholar
- McCool, M. and Fiume, E. 1992. Hierarchical Poisson disk sampling distributions. Graphics Interface, 94--105. Google Scholar
- Mitchell, D. P. 1987. Generating antialiased images at low sampling densities. In Proceedings of the 18th Annual Conference on Computer Graphics and Interactive Techniques. 65--72. Google Scholar
- Mitchell, D. P. 1991. Spectrally optimal sampling for distribution ray tracing. In Proceedings of the 18th Annual Conference on Computer Graphics and Interactive Techniques. 157--164. Google Scholar
- Neyret, F. and Cani, M.-P. 1999. Pattern-Based texturing revisited. In Proceedings of the 26th Annual Conference on Computer Graphics and Interactive Techniques. 235--242. Google Scholar
- Ng, T.-Y., Wen, C., Tan, T.-S., Zhang, X., and Kim, Y. J. 2005. Generating an ω-tile set for texture synthesis. In Proceedings of the Computer Graphics International Conference. 177--184. Google Scholar
- Ostromoukhov, V., Donohue, C., and Jodoin, P.-M. 2004. Fast hierarchical importance sampling with blue noise properties. ACM Trans. Graph. 23, 3, 488--495. Google Scholar
- Perlin, K. 2002. Improving noise. ACM Trans. Graph., 681--682. Google Scholar
- Secord, A., Heidrich, W., and Streit, L. 2002. Fast primitive distribution for illustration. In EGRW: Proceedings of the 13th Eurographics Workshop on Rendering. 215--226. Google Scholar
- Shade, J., Cohen, M. F., and Mitchell, D. P. 2000. Tiling layered depth images. Tech. Rep., University of Washington, Department of Computer Science and Engineering.Google Scholar
- Stam, J. 1997. Aperiodic texture mapping. Tech. Rep. ERCIM-01/97-R046, European Research Consortium for Informatics and Mathematics (ECRIM).Google Scholar
- Ulichney, R. 1987. Digital Halftoning. MIT Press, Cambridge, MA. Google Scholar
- Wang, H. 1961. Proving theorems by pattern recognition II. Bell Syst. Tech. J. 40, 1--42.Google Scholar
- Wang, H. 1965. Games, logic and computers. Sci. Amer. 213, 5, 98--106.Google Scholar
- Wei, L.-Y. 2004. Tile-Based texture mapping on graphics hardware. In Proceedings of the ACM SIGGRAPH/EUROGRAPHICS Conference on Graphics Hardware. 55--63. Google Scholar
- Wei, L.-Y. and Levoy, M. 2000. Fast texture synthesis using tree-structured vector quantization. In Proceedings of the 27th Annual Conference on Computer Graphics and Interactive Techniques. 479--488. Google Scholar
- Yellot, J. I. 1983. Spectral consequences of photoreceptor sampling in the rhesus retina. Sci. 221, 382--385.Google Scholar
Index Terms
- An alternative for Wang tiles: colored edges versus colored corners
Recommendations
Wang Tiles for image and texture generation
We present a simple stochastic system for non-periodically tiling the plane with a small set of Wang Tiles. The tiles may be filled with texture, patterns, or geometry that when assembled create a continuous representation. The primary advantage of ...
Recursive Wang tiles for real-time blue noise
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 ...
Recursive Wang tiles for real-time blue noise
SIGGRAPH '06: ACM SIGGRAPH 2006 PapersWell 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 ...
Comments