Systolic Architecture for Boolean Operations on Polygons and Polyhedra

Abstract

In Computer-Aided Design applications there is often a need to compute the union, intersection and Merence of two polygons or polyhedra. The sequential algorithms for this problem are characterized by poor speed of response and large computational complexity. In order to remove these defects, an algorithm amenable to implementation on a parallel architecture is proposed. The parallel architecture designed is a systolic one which forms a dedicated subsystem to perform set-theoretic operations on polygons. The improvement in speed gained by using the systolic array as compared to a uniprocessor has been evaluated using simulation techniques. Extensions of this architecture to perform the same operations on polyhedra are also discussed.