Instance-aware simplification of 3D polygonal meshes

Virtual worlds and games increasingly deliver 3D meshes over the Internet using instanced file formats, such as COLLADA. However, existing simplification algorithms do not account for instancing in their inputs, operating instead on triangle soups or indexed triangle meshes. This makes them unsuitable for highly instanced meshes, since expanding an instanced mesh to an indexed triangle mesh and then simplifying it can result in a larger output file size. The high cost of delivering these larger files over the Internet results in long network latencies and low performance. This paper presents instance-aware simplification (IAS), an algorithm designed to efficiently simplify instanced 3D meshes. To ensure smaller output file sizes, IAS incorporates the existing compression of mesh instancing into its cost metrics. Unlike existing algorithms, IAS strictly reduces file size as it simplifies, so that IAS-simplified meshes of a given file size have higher visual quality than meshes simplified using existing algorithms. On highly instanced models, IAS results in simplified versions that are orders of magnitude smaller than existing algorithms for a given triangle count.