Vertical Scan-Conversion for Filling Purposes

R.D. Hersch

Proceedings CGInternational 88, Geneva, (Thalmann, Ed.), Springer Verlag, 1988, 318-327

Conventional scan-conversion algorithms were developed independently of filling algorithms. They cause many problems, when used for filling purposes. However, today's raster printers and plotters require extended use of filling, especially for the generation of typographic characters and graphic line art. A new scan-conversion algorithm, called vertical scan-conversion has been specifically designed to meet the requirements of parity scan line fill algorithms. Vertical scan-conversion ensures the selection of exactly one pixel per intersecting scan live between a local minimum and a local maximum of the shape outline. Pairs of selected pixels define horizontal spans. All horizontal spans contain the full set of pixels interior to the original shape. Vertical scan-conversion greatly simplifies traditional edge-tracking filling algorithms, such as ordered edge fill, flag fill and descriptive contour fill, removing the need for testinf and processing special cases.

Download the full paper: PDF 460 KB