“Invisibility coherence for faster scan-line hidden surface algorithms” by Crocker

Invisibility coherence is a new technique developed to decrease the time necessary to render shaded images by existing scan-line hidden surface algorithms. Invisibility coherence is a technique for removing portions of a scene that are not likely to be visible. If a large portion of the scene is invisible, as is often the case in three-dimensional computer graphics, the processing time eliminated may be substantial. Invisibility coherence takes advantage of the observation that a minimal amount of processing needs to be done on objects (polygons, patches, or surfaces) that will be hidden by other objects closer to the viewer. This fact can be used to increase the efficiency of current scan-line algorithms, including both polygon-based and parametrically curved surface-based algorithms. Invisibility coherence was implemented and tested with the polygon hidden surface algorithm for constructive solid geometry developed by Peter Atherton [1]. The use of invisibility coherence substantially increases the efficiency of this scan-line algorithm. Invisibility coherence should work as well or even better with other scan-line hidden surface algorithms, such as the Lane-Carpenter, Whitted, and Blinn algorithms for parametrically curved surfaces [2]., or the Watkins, Romney, and Bouknight algorithms for polygons [3, 4, 5].

1. Atherton, P.R., “A Scan-Line Hidden Surface Removal Procedure for Constructive Solid Geometry,” Computer Graphics, Vol. 17, No. 3, July 1983, pp. 73-82.
2. Lane, J.M., Carpenter, L.C., Whitted, T., Blinn, J.F., “Scan Line Methods for Displaying Parametrically Defined Surfaces,” Comm. ACM, Vol. 23, No. 1, January 1980, pp. 23-34.
3. Watkins, G.S., A Real-Time Visible Surface Algorithm, Computer Science Department, University of Utah, UTECH-CSC-70-101, June 1970.
4. Romney, G.W., Computer Assisted Assembly and Rendering of Solids, Computer Science Department, University of Utah, TR-4-20, 1970.
5. Bouknight, W.J., “A Procedure for Generation of Three-Dimensional Half-Toned Computer Graphics Representations,” Comm. ACM, Vol. 13, No. 9, September 1970.
6. Sutherland, I.E., Sproull, R.F., and Schumacher, R.A., “A Characterization of Ten Hidden-Surface Algorithms,” ACM Computing Surveys, Vol. 6, No. 1, March 1974, pp. 1-55.
7. Weiler, K. and Atherton, P., “Hidden Surface Removal Using Polygon Area Sorting,” Computer Graphics, Vol. 11, No. 2, Summer 1977, pp. 214-222.
8. Hamlin, G. Jr and Gear, C.W., “Raster-Scan Hidden Surface Algorithm Techniques,” Computer Graphics, Vol, 11, No. 2, Summer 1977, pp. 206-213.
9. Franklin, W.R., “A Linear Time Exact Hidden Surface Algorithm,” Computer Graphics, Vol. 14, No. 3, July 1980, pp. 117-123.
10. Sechrest, S., and Greenberg, D.P., “A Visible Polygon Reconstriction Algorithm,” Computer Graphics, Vol. 15, No. 3, August 1981, pp. 17-27.