me | department | university | teaching | research | disclaimer | personal stuff

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.)

[Image of Zigzag Tool Path] 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.

[Image of Hamiltonian Triangulation] This image shows a Hamiltonian triangulation computed by our incremental insertion method.

[Image of Hamiltonian Triangulation] This image shows a Hamiltonian triangulation computed by our onion-based method.
[Image of Onion Layers] This image shows the underlying onion layers of the point set.

[Image of Sequential Triangulation] This image shows a sequential triangulation of the point set. Note that a sequential triangulation need not exist for every point set!

[Image of CS Logo]
file last modified: Friday, 26-Feb-2016 12:34:25 CET
email address
Copyright © 2017 Martin Held. All rights reserved.
[Rock climbing]