Thomas Schlömer
Doctoral Student in the PhD program from 01.01.2010 to 31.12.12.
advisors1. Oliver Deussen2. Ulrik Brandes organisational data

project description
NonPeriodic Tilings in GraphicsCreating 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. Tilebased 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 tilebased texture mapping. Other application domains are two and threedimensional point sets, geometry synthesis, or nonphotorealistic rendering.
Among the variety of possible tilings, methods based on square tiles with colored corners 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 nonperiodic, and the construction of the tile interiors themselves. The first aspect is important to avoid repetition artifacts and thus hide the tilebased 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 nonperiodic 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. So far, we presented an improved tiling algorithm based on a quasirandom subsequence that produces tilings that are at the same time nonperiodic and highly uniform, which noticeably improves the quality of tilebased textures. We also presented a simple extension that allows to control the resulting tilings. This enables tile based 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 also contributed to the ongoing effort of generating highly optimized point sets. 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 tilebased 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 threedimensional 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.
publications
The following list of publications covers only those, which are or were published during participation at the Graduiertenkolleg / PhD program.
id should be a number