Polygon shading on vector type devices

Abstract

A method is presented whereby the interior of boundary-defined regions on vector type devices may be shaded using regular line, cross-hatch and dot patterns. Different shades are realized by changing shading parameters such as line width, distance between consecutive lines or dots, and orientation of patterns. The algorithm partitions any polygon (not necessarily convex), into mutually exclusive, pseudo-monotone polygons that can then be shaded independently using a fast procedure. The partitioning process is based on the topology of the polygon, and notions such as type-1 and type-2 critical points are introduced. Shading is frequently used in computer graphics applications, such as cartography, engineering graphics, art, animation and hidden-line removal.