Efficient Encoding and Rendering of Triangle Meshes

High-performance rendering engines in computer graphics are often pipelined, and their speed is bounded by the rate at which triangulation data can be sent into the machine. To reduce the data rate, it is desirable to order the triangles so that consecutive triangles share a face, meaning that only one additional vertex need be transmitted to describe each triangle. Such an ordering exists if and only if the dual graph of the triangulation contains a Hamiltonian path.

A triangulation is called sequential if it can be encoded as a sequence of vertices, with one vertex per triangle, such that the insertion order never deviates from alternating left-right turns. Thus, a sequential encoding of a triangulation completelt specifies the topology of the triangulation.

Related publications:

E.M. Arkin, M. Held, J.S.B. Mitchell, S.S. Skiena (1996):
``Hamiltonian Triangulations for Fast Rendering''.
The Visual Computer 12(9):429-444, 1996.

The following images show Hamiltonian and sequential triangulations of sets of points, which were computed by means of my implementation. (Click on an image icon in order to see the full-size image. The full-size images have 1000x700 pixels.)

This image shows a point set and its convex hull. The following images show the output of my software for computing Hamiltonian and sequential triangulations.

This image shows a Hamiltonian triangulation computed by our incremental insertion method.

This image shows a Hamiltonian triangulation computed by our onion-based method.

This image shows the underlying onion layers of the point set.

This image shows a sequential triangulation of the point set. Note that a sequential triangulation need not exist for every point set!

file last modified: Thursday, 27-Feb-2020 07:29:07 CET