Implementing streaming simplification for large labeled meshes

Data capture technologies like airborne LIDAR produce extremely large models of digital terrain, which must be simplified to be useful. Garland and Heckbert's quadric error metric in conjunction with edge contraction gives a greedy approach to simplify a mesh that can fit in memory; we adapt it to work with boundaries and labels (e.g., object ID, ground vs. building, or some discrimination between parts of the mesh that is to be preserved during simplification). More importantly, we apply it to streaming meshes, suggested by Isenburg, which are represented as an intermixed sequence of vertices, triangles, and finalization tags indicating the last use of any vertex. These tags essentially document spatial locality in the stream. We discuss the engineering decisions that allow our algorithm to achieve fast, high-quality simplification of gigabyte datasets using a small memory footprint.