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.
``Hamiltonian Triangulations for Fast Rendering''.
The Visual Computer
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
|| This image shows a Hamiltonian triangulation computed by our onion-based
|| 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!