Domino Tiling: A New Method of Real-Time Conforming Mesh Construction for Rendering Changeable Height Fields

In this paper we present a novel GPU-oriented method of creating an inherently continuous triangular mesh for tile-based rendering of regular height fields. The method is based on tiling data-independent semi-regular meshes of non-uniform structure, a technique that is quite different from other mesh tiling approaches. A complete, memory efficient set of mesh patterns is created by an off-line procedure and stored into the graphics adapter's memory at runtime. At rendering time, for each tile, one of the precomputed mesh patterns is selected for rendering. The selected mesh pattern fits the required level of details of the tile and ensures seamless connection with other adjacent mesh patterns, like in a game of dominoes. The scalability potential of the proposed method is demonstrated through quadtree hierarchical grouping of tiles. The efficiency is verified by experimental results on height fields for terrain representation, where the method achieves high frame rates and sustained triangle throughput on high resolution viewports with sub-pixel error tolerance. Frame rate sensitivity to real-time modifications of the height field is measured, and it is shown that the method is very tolerant and consequently well tailored for applications dealing with rapidly changeable phenomena represented by height fields.