Premium
Systolic Architecture for Boolean Operations on Polygons and Polyhedra
Author(s) -
Krishnan D.,
Patnaik L.M.
Publication year - 1987
Publication title -
computer graphics forum
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.578
H-Index - 120
eISSN - 1467-8659
pISSN - 0167-7055
DOI - 10.1111/j.1467-8659.1987.tb00540.x
Subject(s) - polyhedron , computer science , intersection (aeronautics) , architecture , parallel computing , uniprocessor system , set (abstract data type) , set operations , systolic array , algorithm , theoretical computer science , mathematics , combinatorics , very large scale integration , embedded system , art , multiprocessing , engineering , visual arts , programming language , aerospace engineering
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.