CW 2007_08

Ares Lagae
Tile-based methods in computer graphics

Advisor(s): Philip Dutré

Abstract

Many complex signals, such as point distributions and textures, cannot efficiently be synthesized and stored. In this dissertation we present tile-based methods to solve this problem. Instead of synthesizing a complex signal when needed, the signal is synthesized on forehand over a small set of tiles. Arbitrary large amounts of that signal can then efficiently be generated when needed by generating a stochastic tiling.

Tile-based methods are traditionally based on Wang tiles. The colored edges of Wang tiles only constrain the four direct neighboring tiles, but not the four diagonally neighboring tiles. This problem introduces unwanted artifacts in the tiled signals, and complicates methods for synthesizing signals over a set of Wang tiles. To solve this problem we present corner tiles. Corner tiles are unit square tiles with colored corners rather than colored edges. The colored corners of corner tiles constrain all neighboring tiles. We revisit the most important applications of Wang tiles, and we show that corner tiles have substantial advantages for each of these applications.

Stochastic tilings are traditionally generated using scanline stochastic tiling algorithms. However, these algorithms store the complete tiling and are therefore not efficient. To solve this problem, we present direct stochastic tiling algorithms for Wang tiles and corner tiles. These algorithms are capable of evaluating a stochastic tiling locally, without explicitely constructing and storing the tiling up to that point. We also introduce long-period hash functions to generate very large tilings.

Poisson disk distributions and textures are two examples of complex signals. We present tile-based methods for generating Poisson disk distributions and for synthesizing textures. Tile-based methods not only allow to efficiently generate Poisson disk distributions and synthesize textures, but also enable new applications such as tile-based texture synthesis and a procedural object distribution function. This new texture basis function allows to distribute procedural objects over a procedural background, using intuitive parameters such as the scale, size and orientation of the objects. We also present an overview of applications of tiled Poisson disk distributions, and a detailed comparison of methods for generating Poisson disk distributions. We study corner tiles in the context of the tiling problem and aperiodic tile sets, and we construct several new aperiodic sets of Wang tiles and corner tiles.

The tile-based methods we present in this dissertation are a valuable tool for computer graphics, and help to keep up with the continuously increasing demand for more complexity and realism in digitally synthesized images.

Libridoc 812 / text.pdf (8.6M) for screen / text.pdf ( 32M) for printing / text.pdf (216M) full resolution / mailto: graphics team