Abstract
Computer aided design (CAD) models often need to be processed due to the data translation issues and requirements of the downstream applications like computational field simulation, rapid prototyping, computer graphics, computational manufacturing, and realβtime rendering before they can be used. Automatic CAD model processing tools can significantly reduce the amount of time and cost associated with the manual processing. The topology generation algorithm, commonly known as CAD repairing/healing, is presented to detect commonly found geometrical and topological issues like cracks, gaps, overlaps, intersections, Tβconnections, and no/invalid topology in the model, process them and build correct topological information. The present algorithm is based on the iterative vertex pair contraction and expansion operations called stitching and filling, respectively, to process the model accurately. Moreover, the topology generation algorithm can process manifold as well as nonβmanifold models, which makes the procedure more general and flexible. In addition, a spatial data structure is used for searching and neighbour finding to process large models efficiently. In this way, the combination of generality, accuracy, and efficiency of this algorithm seems to be a significant improvement over existing techniques. Results are presented showing the effectiveness of the algorithm to process twoβ and threeβdimensional configurations. Copyright Β© 2006 John Wiley & Sons, Ltd.