Efficient and Robust Algorithm for Overlaying Nonmatching Surface Meshes

Proceedings, 10th International Meshing Roundtable, Sandia National Laboratories, pp.281-292, October 7-10 2001

MESHING
RESEARCH
CORNER

10th International Meshing Roundtable
Newport Beach, California, U.S.A.
October 7-10, 2001

Department of Computer Science,
University of Illinois,
Urbana, IL 61801
Email: {jiao, heath} @cs.uiuc.edu

Abstract
This paper describes an eijicient and robust algorithm for computing a common refinement of two meshes modeling a common surface of arbitrary shape by overlaying them on top of each other. A common refinement is an impor- tant data structure for transferring data between meshes that have different topological structures. Our algorithm is optimal in time and space, with linear complexity. Special treatments are introduced to handle discretization and rounding errors and to ensure robustness with imprecise computations. It also addresses the additional com- plexities caused by degeneracies, sharp edges, sharp corners, and nonmatching boundaries. The algorithm has been implemented and demonstrated to be robust for complex geometries from real-world applications.

Download Full Paper (Postscript Format)