A popular representation of a terrain surface whose elevation has been sampled at regularly spaced intervals is a triangulation of a subset of the sample points that consists of axis-aligned, right-angled isoceles triangles. We call such triangulations bintree triangulations. We insist that the triangulation be composed of triangles that have only three vertices on their boundary.

A terrain visualization algorithm selects a triangulation from the bintree hierarchy, according to some accuracy or complexity constraint, and renders it as a set of triangles. One technique used to speed the rendering is to construct triangle strips from the triangulation. Each triangle strip is a sequence of adjacent triangles. If the rendering system knows the coordinates of the vertices of one triangle in the strip, it knows two of the vertices of the next triangle in the strip and only needs the coordinates of one vertex in order to render the next triangle. This decreases the amount of data that needs to be sent to the graphics hardware. Hamiltonicity of the dual graph of the triangulation implies that the triangulation can be represented using one triangle strip.

Reading Group Discussion.

I'm going to discuss a method for refining a class of balanced bintree triangulations which maintains a hamiltonian cycle in the dual graph. I'm also going to talk about building refinable balanced bintree triangulations using two types of tiles.

The big question I'm trying to figure out is: given an integral orthogonal polygon P, i.e., a polygon for which all edges are horizontal or vertical and have integer length, is there a placement of tiles such that no skewed triangles are formed, every point inside P is covered by exactly one tile to form a single cycle, and no point outside of P is covered by a tile. I suspect that this is np-hard, but haven't come up with a proof for it yet.

Reference: UBC CS Technical Report TR-2006-03