University of Konstanz
Graduiertenkolleg / PhD Program
Computer and Information Science

Graduation Talks


Non-Periodic Tilings in Graphics


Thomas Schlömer, University Konstanz
Konstanz, Germany

date & place

Wednesday, 03.11.2010, 16:15 h
Room C 252


Creating rich and complex content is a major problem in computer graphics, especially in interactive applications where large amounts of content have to be produced very quickly and from limited data. Tile-based methods mitigate this problem by synthesizing large amounts of content out of a much smaller data set of tiles by generating a valid tiling. An example is texture synthesis: Once a set of carefully constructed tiles has been generated from a provided input texture, arbitrary amounts of this input texture can be produced at runtime in connection with tile-based texture mapping. Other application domains are two and three-dimensional point sets, geometry synthesis, or non-photorealistic rendering.
Among the variety of possible tilings, methods based on square tiles with colored corners (Figure 1, right) have proven to be particularly useful in the computer graphics setting. Such corner tiles tile the plane by placing them without gaps or overlaps such that neighboring tiles have matching corner colors. Rotation is not allowed. The quality of the synthesized result largely depends on two factors: the ability of the tiling algorithm to produce tilings which are non-periodic, and the construction of the tile interiors themselves. The first aspect is important to avoid repetition artifacts and thus hide the tile-based nature of the generation process. The second aspect is important to produce tile content which seamlessly fits between adjacent tiles for every possible tiling while still being of high quality.
So far, research has solely focused on stochastic tilings, i.e. tiles are placed randomly as long as they fulfill the matching color constraint. While this approach produces non-periodic tilings, it has numerous deficits, among them local repetition artifacts due to clusters of tiles showing identical content, and the inability to control the synthesized result. In [5], we presented an improved tiling algorithm based on a quasi-random subsequence that produces tilings that are at the same time non-periodic and highly uniform, which noticeably improves the quality of tile-based textures. We also presented a simple extension that allows to control the resulting tilings. This enables tilebased methods to generate inhomogeneous textures. Other contributions are advances in tile set reduction and the tile packing problem.
While we used existing methods to construct the tile interiors for texture synthesis, we contributed to the ongoing effort of generating highly optimized point sets in [1, 2]. The points are derived from a special class of centroidal Voronoi diagrams where each Voronoi cell is of a prescribed size. This yields point sets that both have desirable spectral properties as well as superior convergence in a numerical integration setting, e.g. direct light estimation in a raytracer. Since the underlying optimization is of quadratic time complexity, a combination with a tile-based approach is necessary in order to make the new scheme beneficial.
In the future, we would like to investigate if our observations hold for the three-dimensional case where the synthesis of tiles for e.g. volume textures or simple geometry becomes increasingly difficult. A particular challenge will be to find a balance between the size of the tile set and final synthesis quality. With the extension to other application domains, our approach contributes to the fundamental problem of efficiently generating complex content in graphics.