Efficient algorithms for scan-converting 3D polygons

A three-dimensional scan-conversion algorithm, that scan-converts 3D planar polygons into their discrete voxel-map representation within a Cubic Frame Buffer (CFB), is presented. The algorithm, which is a variation of a conventional 2D scan-line filling algorithm, is incremental and uses only simple operations like additions and tests inside the inner loops. The algorithm performs scan-conversion with computational complexity which is linear in the number of voxels written to the CFB. Another algorithm that scan-converts polygons clipped to the CFB boundaries with no added time complexity is also presented. Furthermore, an all-integer decision mechanism which makes the inner-most loop of the algorithm more efficient is discussed too. All the algorithms guarantee lack of 6-connected "tunnels" in the converted polygons. The algorithms have been implemented as part of the 3D geometry processor of the CUBE Architecture, which is a voxel-based system for 3D graphics. These algorithms allow the CUBE system to generate a discrete voxel representation of the essential 3D polygon primitive, enabling CUBE to also cater to applications generating synthetic images.