ACCURATE BOOLEAN OPERATIONS FOR SUBDIVISION SURFACES AND RELAXED FITTING

An apparatus, method, and computer readable storage medium for accurately performing Boolean operations on subdivision surfaces. The present invention produces a base mesh which subdivides into a surface which represents the Boolean operation of two subdivision surfaces. The method includes (a) chopping pieces of two Catmull-Clark bases meshes which correspond to pieces of a Boolean surface computed from limit surfaces of the two base meshes; (b) creating new edges on the chopped pieces to create quadrilaterals and triangles; and (c) merging the chopped pieces with the new edges into a Boolean base mesh which approximates the Boolean surface.