Hamiltonian triangulations for fast rendering

EM Arkin, M Held, JSB Mitchell, SS Skiena - The Visual Computer, 1996 - Springer
The Visual Computer, 1996Springer
High-performance rendering engines are often pipelined; their speed is bounded by the rate
at which triangulation data can be sent into the machine. An ordering such that consecutive
triangles share a face, which reduces the data rate, exists if and only if the dual graph of the
triangulation contains a Hamiltonian path. We (1) show that any set of n points in the plane
has a Hamiltonian triangulation;(2) prove that certain nondegenerate point sets do not admit
a sequential triangulation;(3) test whether a polygon P has a Hamiltonian triangulation in …
Abstract
High-performance rendering engines are often pipelined; their speed is bounded by the rate at which triangulation data can be sent into the machine. An ordering such that consecutive triangles share a face, which reduces the data rate, exists if and only if the dual graph of the triangulation contains a Hamiltonian path. We (1) show thatany set ofn points in the plane has a Hamiltonian triangulation; (2) prove that certain nondegenerate point sets do not admit asequential triangulation; (3) test whether a polygonP has a Hamiltonian triangulation in time linear in the size of its visibility graph; and (4) show how to add Steiner points to a triangulation to create Hamiltonian triangulations that avoid narrow angles.
Springer