“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 using Wang Tiles is that once the tiles are filled, large expanses of non-periodic texture (or patterns or geometry) can be created as needed very efficiently at runtime.Wang Tiles are squares in which each edge is assigned a color. A valid tiling requires all shared edges between tiles to have matching colors. We present a new stochastic algorithm to non-periodically tile the plane with a small set of Wang Tiles at runtime.Furthermore, we present new methods to fill the tiles with 2D texture, 2D Poisson distributions, or 3D geometry to efficiently create at runtime as much non-periodic texture (or distributions, or geometry) as needed. We leverage previous texture synthesis work and adapt it to fill Wang Tiles. We demonstrate how to fill individual tiles with Poisson distributions that maintain their statistical properties when combined. These are used to generate a large arrangement of plants or other objects on a terrain. We show how such environments can be rendered efficiently by pre-lighting the individual Wang Tiles containing the geometry.We also extend the definition of Wang Tiles to include a coding of the tile corners to allow discrete objects to overlap more than one edge. The larger set of tiles provides increased degrees of freedom.

1. BERGER, R. 1966. The undecidability of the domino problem. Memoirs American Mathematical Society, 66, 1–72.]]Google Scholar
2. CULIK II, K. 1996. An aperiodic set of 13 wang tiles. Discrete Mathematics 160, 245–251.]] Google ScholarDigital Library
3. DEUSSEN, O., HANRAHAN, P., PHARR, M., LINTERMANN, B., MĚCH, R., AND PRUSINKIEWICZ, P. 1998. Realistic modeling and rendering of plant ecosystems. In SIGGRAPH 98 Conference Proceedings, 275–286.]] Google Scholar
4. DEUSSEN, O., HILLER, S., VAN OVERVELD, K., AND STROTHOTTE, T. 2000. Floating points: A method for computing stipple drawings. Computer Graphics Forum, Eurographics 2000 Conference Proceedings 19, 4, 40–51.]]Google Scholar
5. DEUSSEN, O., COLDITZ, C., STAMMINGER, M., AND DRETTAKIS, G. 2002. Efficient rendering of complex ecosystems using points and lines. In IEEE Visualization 2002, IEEE, 219–226.]] Google Scholar
6. EFROS, A., AND FREEMAN, W. 2001. Image quilting for texture synthesis. In Proceedings of SIGGRAPH 2001, 341–346.]] Google ScholarDigital Library
7. GLASSNER, A. 1998. Aperiodic tiling, part 1. IEEE Computer Graphics and Applications 18, 4 (May).]] Google ScholarDigital Library
8. GORTLER, S. J., GRZESZCZUK, R., SZELISKI, R., AND COHEN, M. F. 1996. The lumigraph. In Proceedings of SIGGRAPH 1996, 43–54.]] Google ScholarDigital Library
9. GRÜNBAUM, B., AND SHEPHARD, G. C. 1987. Tilings and Patterns. W. H. Freeman and Company. ISSN 0716711931.]]Google Scholar
10. HAUSNER, A. 2001. Simulating decorative mosaics. In SIGGRAPH 2001 Conference Proceedings, 573–578.]] Google Scholar
11. HILLER, S., DEUSSEN, O., AND KELLER, A. 2001. Tiled blue noise samples. In Proceedings of Vision Modelling Visualization 2001, Infix-Verlag, 265–272.]] Google ScholarDigital Library
12. HOPPE, H. 1996. Progressive meshes. In Proceedings of SIGGRAPH 1996, 99–108.]] Google ScholarDigital Library
13. KARI, J. 1996. An small aperiodic set of wang tiles. Discrete Mathematics 160, 259–264.]] Google ScholarDigital Library
14. LEVOY, M., AND HANRAHAN, P. 1996. Light field rendering. In Proceedings of SIGGRAPH 1996, 31–42.]] Google ScholarDigital Library
15. MCCOOL, M., AND FIUME, E. 1992. Hierarchical poisson disk sampling distributions. In Graphics Interface ’92, 94–105.]] Google Scholar
16. MĚCH, R., AND PRUSINKIEWICZ, P. 1996. Visual models of plants interacting with their environment. In Proceedings of SIGGRAPH 1996, 397–410.]] Google Scholar
17. NEYRET, F., AND CANI, M.-P. 1999. Pattern-based texturing revisited. In Proceedings of SIGGRAPH 1999, 235–242.]] Google ScholarDigital Library
18. NEYRET, F. January-March 1998. Modeling, animating, and rendering complex scenes using volumetric textures. IEEE Transactions on Visualization and Computer Graphics 4, 1, 55–70.]] Google ScholarDigital Library
19. PERBERT, F., AND CANI, M. 2001. Animating prairies in real-time. In 2001 ACM Symposion on Interacive 3D Graphics, 103–110.]] Google Scholar
20. PRUSINKIEWICZ, P., MÜNDERMANN, L., KARWOWSKI, R., AND LANE, B. 2001. The use of positional information in the modelling of plants. In Proceedings of SIGGRAPH 2001, 289–300.]] Google Scholar
21. SHADE, J., GORTLER, S., HE, L., AND SZELISKI, R. 1998. Layered depth images. In Proceedings of SIGGRAPH 1998, 231–242.]] Google ScholarDigital Library
22. SHADE, J., COHEN, M. F., AND MITCHELL, D. 2002. Tiling layered depth images. ftp://ftp.cs.washington.edu/tr/2002/12/UW-CSE-02-12-07.pdf.]]Google Scholar
23. STAM, J. 1997. Aperiodic texture mapping. Tech. rep., R046. European Research Consortium for Informatics and Mathematics (ERCIM). http://www.ercim.org/publication/technical_reports/046-abstract.html.]]Google Scholar
24. TONG, X., ZHANG, J., LIU, L., WANG, X., GUO, B., AND SHUM, H.-Y. 2002. Synthesis of bidirectional texture functions on arbitrary surfaces. ACM Transactions on Graphics 21, 3 (July), 665–672. ISSN 0730-0301 (Proceedings of ACM SIGGRAPH 2002).]] Google ScholarDigital Library
25. TURK, G. 2001. Texture synthesis on surfaces. In Proceedings of ACM SIGGRAPH 2001, ACM Press / ACM SIGGRAPH, Computer Graphics Proceedings, Annual Conference Series, 347–354. ISBN 1-58113-292-1.]] Google Scholar
26. WANG, H. 1961. Proving theorems by pattern recognition II. Bell Systems Technical Journal 40, 1–42.]]Google ScholarCross Ref
27. WANG, H. 1965. Games, logic, and computers. Scientific American (November), 98–106.]]Google Scholar
28. WEBER, J., AND PENN, J. 1995. Creation and rendering of realistic trees. In Proceedings of SIGGRAPH 1995, 119–128.]] Google Scholar
29. WEI, L.-Y., AND LEVOY, M. 2000. Fast texture synthesis using tree-structured vector quantization. In Proceedings of SIGGRAPH 2000, 479–488.]] Google ScholarDigital Library