DISTRIBUTED BOUNDARY REPRESENTATION AND BOOLEAN OPERATIONS ON A MASSIVELY-PARALLEL COMPUTER

Boolean operation is usually the most expensive task in solid modellin g. Considerable amount of time is required in a union, difference, or intersection operation especially when an object grows in complexity a fter a series of operations. Parallel processing seems to be a promisi ng technique for improving the speed in the manipulation of complex so lid objects. This paper presents a technique for performing Boolean op erations in a distributed environment. In this method, a distributed b oundary representation scheme is adopted for representing objects in a n array of processors of a SIMD computer. Solid objects with non-manif old boundary is assumed and is modelled with a cell-complex based boun dary representation. The concept of half-wedge is employed to allow ea sy retrieval of neighbourhood or topological information in a distribu ted processing environment. Parallel algorithms for obtaining the comp lement of solids are presented. Algorithms for evaluating the intersec ting regions and hence the result of Boolean operations between object s are also discussed. The proposed method is implemented on a DECmpp 1 200/Sx machine with 8K processors. Test results on the experimental sy stem shows that the method is efficient for a test piece with 1300 or more entities. The actual performance of the system may also depends o n the relative sizes of the entities involved. Copyright (C) 1996 Else vier Science Ltd.