Structuring scan-line algorithm for scene with single complex object case

摘要

This paper discusses software implementation of the scan-line hidden-surface removal algorithm. The main concern was minimiz- ing execution time of this algorithm in situations where we were faced with scenes with a single complex object. Polygonal meshes with two-manifold polygons are used for object models. Various data structures for implementing the algorithm (edge-table, active-edge- table, and polygon-table) are presented and their maintenance is explained. Finally, the expression for running time of the scan-line algorithm is derived.