BOOLE: A boundary evaluation system for Boolean combinations of sculpturedsolids

In this paper we describe a system, BOOLE, that generates the boundary repr esentations (B-reps) of solids given as a CSG expression in the form of tri mmed Bezier patches. The system makes use of techniques from computational geometry, numerical linear algebra and symbolic computation to generate the B-reps. Given two solids, the system first computes the intersection curve between the two solids using our surface intersection algorithm. Using the topological information of each solid, it computes various components with in each solid generated by the intersection curve and their connectivity. T he component classification step is performed by ray-shooting. Depending on the Boolean operation performed, appropriate components are put together t o obtain the final solid. We also present techniques to parallelize this sy stem on shared memory multiprocessor machines. The system has been successf ully used to generate B-reps for a number of large industrial models includ ing parts of a notional submarine storage and handling room (courtesy - Ele ctric Boat Inc.) and Bradley fighting vehicle (courtesy - Army Research Lab s). Each of these models is composed of over 8000 Boolean operations and is represented using over 50,000 trimmed Bezier patches. Our exact representa tion of the intersection curve and use of stable numerical algorithms facil itate an accurate boundary evaluation at every Boolean set operation and ge neration of topologically consistent solids.