Robust and Error Controllable Boolean Operations on Free-Form Solids Represented by Catmull-Clark Subdivision Surfaces

A method for performing robust and error controllable Boolean operations on free-form solids represented by Catmull-Clark subdivision surfaces (CCSSs) is presented. The method is voxelization based but different from previous voxelization based approaches a continuous geometric representation is provided for the result of each Boolean operation. This is achieved by doing the Boolean operations in the parameter spaces of the solids instead of the object space. This approach allows us to easily compute a parametric approximation of the intersection curve and consequently build a continuous geometric representation of the Boolean operation result. The new method also allows secondary local voxelization to be performed on intersecting subpatches to increase accuracy of the Boolean operation result. Because voxelization process of the new method is very fast and robust the overall process is fast and robust. Most importantly error of each Boolean operation result can be precisely estimated hence error control is possible. The new method can handle any types of Boolean operations as long as the given solids are represented by CCSSs. Hence there are no special or degenerated cases to take care of. The new method is presented for CCSSs only but the concept works for any subdivision scheme whose limit surfaces are parametrizable.