Triangular mesh generation for surfaces of 3D objects

Three-dimensional graphics and visualization have become indispensable in many exciting areas of technology-oriented society, from the imaginative entertainment industry, to the precision-driven medical applications. Underlying 3D data, however, vary widely from continuous mathematical functions and random sampling point sets, to regular grid range images, to 3D volumetric data (CT, MR and PET). The industrial standard (VRML and OpenGL) has focused on the triangular mesh surface representation for modeling 3D objects. As the explosion of data continues and the demand for 3D data access across the Internet intensifies, it is rapidly becoming critical to develop a fast unifying generation algorithm for succinct triangular mesh representation of 3D object with guaranteed accuracy.; This dissertation formulates a general optimal surface triangulation problem of minimizing number of triangles/vertices under L-_∞ distortion constraint. This problem has been shown to be in the NP-hard class of computational complexity. A novel algorithm featuring multiple cooperating agents under constrained resource planning paradigm for fitting a triangular mesh to both explicit surface z = f(x, y) and implicit surface f(x, y, z) = 0 in either discrete or continuous form is designed, implemented and validated. The guaranteed and controllable quality ensures a succinct and adaptive triangular mesh fit in near-linear time with respect to the number of sampled surface points. The top-down iterative refinement and relaxation process is superior to the traditional two-stage (generation-simplification) bottom-up approach, which is inherently computation-redundant, memory-intensive and may even bog down before any simplification starts. As a post-processing step, a fast bit-efficient coder-decoder is designed to further reduce the representation complexity for the generated triangular mesh.; The optimality and effectiveness of the developed mesh generation and mesh compression algorithms are thoroughly analyzed theoretically and validated experimentally with benchmark data from several important application domains, including medical imaging, body modeling, image coding, and geometric compression. The capacity and generality of the developed algorithms open an entirely new spectrum of technologies, which surely contribute to the ultimate goal of putting 3D shape on an equal footing with other media, such as image, audio and video, that have brought revolution to human life in history.