Non-Periodic Corner Tilings in Computer Graphics

Abstract

Rendering computer-generated images is both memory and runtime intensive. This is particularly true in realtime computer graphics where large amounts of content have to be produced very quickly and from limited data. Tile-based methods offer a solution to this problem by generating large portions of a specific content out of a much smaller data set of tiles. This dissertation investigates the use of corner tiles for this purpose—unit square tiles with color-coded corners. They tile the plane by placing them without gaps or overlaps such that tiles have matching corner colors. We present efficient algorithms to perform such a tiling that are both more flexible and less prone to artifacts than existing algorithms. We also present solutions to combinatorial problems that arise when using corner tiles, and introduce high-quality methods to perform the tile-based generation of two fundamental components of any rendering system: textures and two-dimensional sample point sets. The results of this dissertation are advantageous for both realtime and offline rendering systems where they improve state-of-the-art results in texture synthesis, image plane sampling, and lighting computations based on numerical integration.