Interactive Boundary Computation of Boolean Combinations of Sculptured Solids

Boundary Representations (B-Rep) of the solid models are essential for model visualization in design verification, collision detection during object placement and simulation studies. Further, the iterative nature of the model building process necessitates quick B-rep generation, so that the turn-around time per iteration is reduced to an acceptable level. If the B-rep evaluation process is interactive, that is the best one could ask for. This research work is motivated by this problem. In this work, we present algorithms and systems for interactive and accurate boundary computation of Boolean combinations of sculptured solids. The algorithm exploits parallelism at all stages. It has been implemented on a multi-processor SGI and takes one second on average per boolean operation to compute the boundary of high degree primitives. The system has also been integrated with an immersive design and manipulation environment called CHIMP (Chapel Hill Immersive Modeling Package). The resulting system is able to interactively evaluate boundaries of the models, display them for model validation and place them at appropriate position using collision detection algorithms.

Overview of the method

The contribution of this work includes an implementation of the above parallel algorithm on shared memory multiprocessor architectures. Our experiments currently run on an {\small SGI-ONYX} with four R10000 processors each with a 194 MHz clock. In Stage 2 of our algorithm, we allocate patch pairs for exact surface-surface intersection computation. The surface intersection computation and the ray shooting operation in Stage 6 are the two costly operations where the time taken cannot be predetermined. An implementation of the dynamic load balancing scheme performs better than the centralized queue model with locks. Hence for Stages 3 and 6, we use this method for distributing the patch pairs and ray-patch pairs. All the processors are given an almost equal number of patch pairs for intersection computation. Lock free implementation is achieved by a carefully chosen data structure. A two dimensional array is used to hold the intersection curves between pairs of patches. This structure is used for curve merging in Stage 3. It ensures that only one processor is accessing any cell of the two dimensional array and thus, the intersection computation followed by curve merging is done by sharing data without memory contention. Components classification by rayshooting is performed in Stage 6. Here, the patches of one solid are equally distributed to all the processors. Each processor computes the intersection of the ray with all the patches assigned to it and also counts the parity (odd/even) of number of intersections. These results are finally merged to find whether the total number of intersections is odd or even. This result is used to classify the component. This information is propagated along the adjacency graph of the solid to resolve the other components. The above operation is done once for each solid. After all the components are classified, the components are chosen to be combined to form the final solid. As the B-rep of each patch of the component is known, the final solid is represented in its B-rep form. This stage is executed sequentially. The accuracy of the B-rep generated is determined by the accuracy of the intersection curves between solids. In our system, the accuracy of these curves can be controlled by the user. Depending on the application, our system can generate very accurate B-reps at the expense of computation time.

Click to view the stages of the algorithm. ( Same figure in postscript. )

Click to view the stages of the algorithm. ( Same figure in postscript. )

Click to view the performance graph of the algorithm. ( Same figure in postscript. )

Return to Geometric and Solid Modeling page.

Return to UNC Research Group on Modeling, Physically-Based Simulation and Applications page.