FILLING GAPS IN THE BOUNDARY OF A POLYHEDRON

In this paper we present an algorithm for detecting and repairing defe cts in the boundary of a polyhedron. These defects, usually caused by problems in CAD software, consist of small gaps bounded by edges that are incident to only one polyhedron face. The algorithm uses a partial curve matching technique for matching parts of the defects, and an op timal triangulation of 3-D polygons for resolving the unmatched parts. It is also shown that finding a consistent set of partial curve match es with maximum score, a subproblem which is related to our repairing process, is NP-hard. Experimental results on several polyhedra are pre sented.