Geometric optimization

An algorithm is presented which describes an application independent method for reducing the number of polygonal primitives required to faithfully represent an object. Reducing polygon count without a corresponding reduction in object detail is important for: achieving interactive frame rates in scientific visualization, reducing mass storage requirements, and facilitating the transmission of large, multi-timestep geometric data sets. This paper shows how coplanar and nearly coplanar polygons can be merged into larger complex polygons and re-triangulated into fewer simple polygons than originally required. The notable contributions of this paper are: (1) a method for quickly grouping polygons into nearly coplanar sets, (2) a fast approach for merging coplanar polygon sets and, (3) a simple, robust triangulation method for polygons created by 1 and 2. The central idea of the algorithm is the notion of treating polygonal data as a collection of segments and removing redundant segments to quickly form polygon hulls which represent the merged coplanar sets