Algorithms for manipulating triangulated surfaces

Triangulations are powerful tools for surface modeling. They can be used to fit any irregular boundary shapes and surface discontinuity fault patterns. However, without the help of row and column information as in rectangular grids, manipulating a triangulated surface interactively is not an easy task. Efficiency is a major concern for manipulation functions. This article will propose some algorithms to manipulate triangulated surfaces such as: finding the path of a given route in a triangulated surface; getting the profile of a vertex function along a given route; and partitioning a surface domain by vertical plane(s). These algorithms have applications to interactive graphics where the user wishes to slice multisurface folds to obtain various views of a solid, and to dynamical problems where one wishes to introduce fracture systems into pre-existing surfaces. Some other useful operations such as merging of two domains, moving a vertex with preset rules, and combined use with rectangular grids, are also discussed. The proposed algorithms have been implemented in a triangulation database system developed by W.M. Smith of Cullen Image Processing Laboratory at University of Houston. This process requires both expansion and modification of Smith’s system. The principal modification introduced enables the system to treat multiple surfaces in main memory rather than only one surface at a time from a file database. The algorithms can be applied to any multi-connected surface domain. Holes and irregular boundary conditions are given careful treatment A theoretical analysis of time complexity is not available at this stage. Empirical results for the time required by these algorithms are given instead.