CumInCAD is a Cumulative Index about publications in Computer Aided Architectural Design
supported by the sibling associations ACADIA, CAADRIA, eCAADe, SIGraDi, ASCAAD and CAAD futures

authors Franklin, Randolph
year 1980
title A Linear Time Exact Hidden Surface Algorithm
source SIGGRAPH '80 Conference Proceedings. July, 1980. vol. 14 ; no. 3: pp. 117-133 : ill. includes bibliography
summary 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 3,000 squares
keywords hidden surfaces, algorithms, hidden lines, variables, grids, computer graphics, programming
series CADline
references Content-type: text/plain
last changed 2003/06/02 11:58
HOMELOGIN (you are user _anon_353964 from group guest) Works Powered by SciX Open Publishing Services 1.002