Graphics Gems III (IBM Version)

VII.6

ACCURATE POLYGON SCAN CONVERSION USING HALF-OPEN INTERVALS

Kurt Fleischer,     California Institute of Technology, Pasadena, California

David Salesin,     Cornell University, Ithaca, New York

Publisher Summary

This chapter describes a simple, efficient polygon scan-conversion algorithm that allows a mesh of polygons to be scan-converted, one polygon at a time, without drawing any pixel twice and without leaving any holes. The algorithm uses a slightly modified Bresenham algorithm to scan-convert the polygon edges and uses half-open intervals to disambiguate the pixels lying on edges shared by adjacent polygons. The chapter presents a scan-line algorithm for triangles; however, the technique is readily extended to arbitrary simple ...