“A linear time exact hidden surface algorithm” by Franklin

This paper presents a new hidden surface algorithm. Its output is the set of the visible pieces of edges and faces, and is as accurate as the arithmetic precision of the computer. Thus calculating the hidden surfaces for a higher resolution device takes no more time. If the faces are independently and identically distributed, then the execution time is linear in the number of faces. In particular, the execution time does not increase with the depth complexity. This algorithm overlays a grid on the screen whose fineness depends on the number and size of the faces. Edges and faces are sorted into grid cells. Only objects in the same cell can intersect or hide each other. Also, if a face completely covers a cell then nothing behind it in the cell is relevant. Three programs have tested this algorithm. The first verified the variable grid concept on 50,000 intersecting edges. The second verified the linear time, fast speed, and irrelevance of depth complexity for hidden lines on 10,000 spheres. This also tested depth complexities up to 30, and showed that perspective scenes with the farther objects smaller are even faster to calculate. The third verified this for hidden surfaces on 3000 squares.

1. Bentley, J.L., Stanat, D.F., and Williams, E.H., Jr. The Complexity of finding fixed radius near neighbors. Info. Proc. Lett. 6, 6 (Dec. 1977), 209-212.
2. Bentley, J.L., Ottmann, T.A. Algorithms for reporting and counting geometric intersections. IEEE T. Comput. C-28, 9 (Sept. 1979), 643-647.
3. Blinn, J.F., Carpenter, L.C., Lane, J.M., and Whitted, T. Scan Line methods for displaying parametrically defined surfaces. Comm. ACM 23, 1 (Jan. 1980), 23-24.
4. Blinn, J.F., Newell, M.E. Texture and reflection in computer generated images. Comm. ACM 19, 10 (Oct. 1976), 542-547.
5. Crow, F.C. Shadow algorithms for computer graphics. Computer Graphics 11, 2 (Summer 1977), 242-248.
6. Franklin, W.R. VIEWPLOT summary, program logic manual, and user’s manual. Harvard Lab for Computer Graphics, (July, Dec. 1976).
7. Franklin, W.R. Combinatorics of hidden surface algorithms. Harvard University Center for Research in Computing Technology, TR12-78, (June 1978).
8. Franklin, W.R. An Exact hidden sphere algorithm that operates in linear time. Computer Graphics and Image Processing, to appear.
9. Knowlton, K., and Cherry, L. ATOMS – a 3-D opaque molecular system. Computers and Chemistry 1, 3 (1977), 161-166.
10. Max, N.L. ATOMLLL – ATOMS with shading and highlights. Computer Graphics 13, 2 (Aug. 1979), 165-173.
11. Newman, W., and Sproull, R.F. Principles of Interactive Computer Graphics, 2nd edition. McGraw-Hill, 1979.
12. Rogers, D.F. and Adams, J.A. Mathematical Elements for Computer Graphics. McGraw-Hill, 1976.
13. Sutherland, I.E., Sproull, R.F., and Schumacker, R.A. A Characterization of ten hidden surface algorithms. Computing Surveys 6, 1 (Mar. 1974), 1-55.
14. Weiler, K., and Atherton, P. Hidden surface removal using polygon area sorting. Computer Graphics 11, 2 (Summer 1977), 214-222.