Modern technology enables the creation of digital 3D polygon meshes with incredible detail. Current mesh formats, which were designed when models and meshes were orders of magnitude smaller, complicate the processing of large, detailed data. This project will fully develop a new streaming mesh representation, and use it as a framework for algorithms that produce and/or consume large polygonal and polyhedral meshes. At its core are several simple, new ideas that get around current limitations in computer memory hierarchies. The immediate benefit of compressed storage, faster loading, and better memory use appeal to any application creating large models, including scientific and engineering visualization for data exploration, scanned artifacts for artistic and museum displays, landscape modeling for flood or fire control, mesh generation for scientific computing, virtual environments for collaboration and education, and 3D models for e-commerce.
This project identifies the parameters that characterize a streaming mesh, then designs and implements algorithms whose behavior can be analyzed in terms of these parameters. Initial algorithms include surface simplification, compression, and transmission for geometric models for computer graphics, and extend to include 2D and 3D stream-based Delaunay triangulators. The key ideas grew out of work on geometric models in computer graphics; the project's investigators will apply them in more general contexts. The result will be useful software, embodying a computation paradigm that can process arbitrarily large meshes while avoiding geometric artifacts, degradation of quality, and other difficulties of approaches that cut meshes into pieces to fit into available memory. This project will ensure its broader impact though distribution of software (both source code and executables) for streaming and compressing meshes, and stream-based 2D and 3D Delaunay triangulation. The project will impact education of undergraduate and graduate students, and reach out to high school and elementary students through demonstration days. The principle investigators use several means to reach groups that are underrepresented in computer science.
