Overview
This algorithm provides a method to tessellate a surface into a reduced polygonal mesh while retaining all salient geometric features. Other polygonization techniques restrict the final mesh to a rectangular topology or are based on recursive subdivision schemes. The method developed in this research models surface polygonization as a specialized form of a mesh reduction problem. Unlike general mesh decimation techniques, this method is able to take advantage of the fact that the precise surface definition is known before polygonization is attempted. The mesh reduction is accomplished by using a general process called “edge reduction” along boundaries and interiors of subregions of the surface. In edge reduction, an edge in the mesh is deleted by replacing it’s two vertices with one new vertex. This new vertex is located by solving a maximin optimization problem or is arbitrarily located at the centroid of the feasible region. The quality of the mesh is determined by a user-selected criterion. Since the algorithm operates on local subregions of the mesh, global minimization of the mesh size and symmetry properties are not guaranteed. The results of a series of tests show the method proves to be insensitive to the initial grid size and the starting location of the reduction process. Optimization-based mesh reduction produces substantially smaller meshes compared to implementation without optimization.
Additional Media
The upper half of the following images shows the mesh after boundary edge reduction. The bottom half of the image shows the mesh after interior reduction which is the final step in the method.
Publications
- Khan, M. A. and Vance, Judy M., “A Mesh Reduction Approach to Parametric Surface Polygonization,” 1995 ASME Design Automation Conference Proceedings, Boston, MA, Sept. 1995.
- Khan, M. A. and Vance, Judy M., “Mesh Reduction Using an Angle Criterion Approach,” ASME Journal of Mechanical Design, Vol. 118, No. 2, June 1996, pp. 300-305.
- M. Asif Khan, A mesh reduction approach to parametric surface polygonization, M.S. Thesis, Iowa State University, 1994
Personnel
- Judy M. Vance, Principal Investigator, jmvance@iastate.edu
- M. Asif Khan, Graduate Research Assistant, makhan@iastate.edu
