Algorithms for Handling the Fill Area Primitive of GKS

The fill area primitive of GKS (Graphical Kernel System)¹ is one of the more powerful features which differentiates it from earlier device independent graphics software and systems. Its specification is extremely general in the form of a closed boundary, possibly self-intersecting, and whose interior can be filled in a variety of styles. However a complete implementation of this primitive is very complex. It is difficult to find a single graphics workstation incorporating this primitive in hardware or firmware. Most GKS implementations will have to include software for simulating the appearance of this primitive on the commonly available displays and hard-copy graphics devices. Correct and efficient algorithms are necessary for developing this software. Because of the generality many of the existing algorithms are not directly applicable. In this paper we describe:
1. a new algorithm for clipping a fill area polygon, using what we have named as the Bridge Technique.
2. implementation of a plane sweep algorithm, by Nievergelt and Preparata,² for solid filling and hatching, particularly applicable to vector devices.
3. extension of the plane sweep algorithm for filling with any given pattern on raster as well as vector devices.
The algorithms have been designed to work for all special cases as well. In fact they have been implemented having in mind the fill area set primitive of GKS-3D extension.³ All these algorithms have been very successfully implemented in a commercially available GKS implementation, namely indoGKS.