Surface intersection using parallelism (Q1315806)

One of the major computational problems in designing improved solid modeling systems is the difficulty of the surface/surface intersection problem. The surface/surface intersection is the fundamental computation for supporting Boolean set operations such as intersection, union, and difference, that must be performed in the editing and modeling of complex objects constructed from simple primitives. The authors investigate a parallel approach to the surface intersection problem that shows, both theoretically and empirically, that with parallelism one can achieve both speed and precision simultaneously. First, a basic subdivision algorithm is given. It is shown that this basic algorithm can be improved by parallelism. The authors design two tolerance-based parallel subdivision algorithms, a macro-subdivision algorithm for MIND shared memory machines and a look ahead-subdivision algorithm for pipelined MIND machines. The results are examined empirically on the Sequent Balance 21000, the Alliant FX/8, and the Cray-2.