Article

Free access

A linear time exact hidden surface algorithm

Author:

Wm Randolph FranklinAuthors Info & Claims

SIGGRAPH '80: Proceedings of the 7th annual conference on Computer graphics and interactive techniques

Pages 117 - 123

https://doi.org/10.1145/800250.807480

Published: 01 July 1980 Publication History

PDF eReader

Abstract

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.

References

[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.

Crossref

Google Scholar

[2]

Bentley, J.L., Ottmann, T.A. Algorithms for reporting and counting geometric intersections. IEEE T. Comput. C-28, 9 (Sept. 1979), 643-647.

Digital Library

Google Scholar

[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.

Digital Library

Google Scholar

[4]

Blinn, J.F., Newell, M.E. Texture and reflection in computer generated images. Comm. ACM 19, 10 (Oct. 1976), 542-547.

Digital Library

Google Scholar

[5]

Crow, F.C. Shadow algorithms for computer graphics. Computer Graphics 11, 2 (Summer 1977), 242-248.

Digital Library

Google Scholar

[6]

Franklin, W.R. VIEWPLOT summary, program logic manual, and user's manual. Harvard Lab for Computer Graphics, (July, Dec. 1976).

Google Scholar

[7]

Franklin, W.R. Combinatorics of hidden surface algorithms. Harvard University Center for Research in Computing Technology, TR12-78, (June 1978).

Google Scholar

[8]

Franklin, W.R. An Exact hidden sphere algorithm that operates in linear time. Computer Graphics and Image Processing, to appear.

Google Scholar

[9]

Knowlton, K., and Cherry, L. ATOMS - a 3-D opaque molecular system. Computers and Chemistry 1, 3 (1977), 161-166.

Google Scholar

[10]

Max, N.L. ATOMLLL - ATOMS with shading and highlights. Computer Graphics 13, 2 (Aug. 1979), 165-173.

Digital Library

Google Scholar

[11]

Newman, W., and Sproull, R.F. Principles of Interactive Computer Graphics, 2nd edition. McGraw-Hill, 1979.

Digital Library

Google Scholar

[12]

Rogers, D.F. and Adams, J.A. Mathematical Elements for Computer Graphics. McGraw-Hill, 1976.

Digital Library

Google Scholar

[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.

Digital Library

Google Scholar

[14]

Weiler, K., and Atherton, P. Hidden surface removal using polygon area sorting. Computer Graphics 11, 2 (Summer 1977), 214-222.

Digital Library

Google Scholar

Cited By

View all

Beichl IBernal JWitzgall CSullivan F(2016)Computational GeometryEncyclopedia of Operations Research and Management Science10.1007/978-1-4419-1153-7_142(241-246)Online publication date: 23-Jan-2016
https://doi.org/10.1007/978-1-4419-1153-7_142
Akman VFranklin WKankanhalli MNarayanaswami C(1989)Geometric computing and uniform grid techniqueComputer-Aided Design10.1016/0010-4485(89)90125-521:7(410-420)Online publication date: 1-Aug-1989
https://dl.acm.org/doi/10.1016/0010-4485%2889%2990125-5
Carlbom I(1987)An Algorithm for Geometric Set Operations Using Cellular Subdivision TechniquesIEEE Computer Graphics and Applications10.1109/MCG.1987.2769877:5(44-55)Online publication date: 1-May-1987
https://dl.acm.org/doi/10.1109/MCG.1987.276987
Show More Cited By

Index Terms

A linear time exact hidden surface algorithm
1. Computing methodologies
  1. Computer graphics
    1. Image manipulation
    2. Shape modeling
  2. Symbolic and algebraic manipulation
    1. Symbolic and algebraic algorithms
2. Theory of computation
  1. Design and analysis of algorithms
  2. Randomness, geometry and discrete structures
    1. Computational geometry

Recommendations

A linear time exact hidden surface algorithm

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 ...
A simple algorithm for Boolean operations on polygons

In this paper a simple and efficient algorithm for computing Boolean operations on polygons is presented. The algorithm works with almost any kind of input polygons: concave polygons, polygons with holes, several contours and self-intersecting edges. ...
Invisibility coherence for faster scan-line hidden surface algorithms
SIGGRAPH '84: Proceedings of the 11th annual conference on Computer graphics and interactive techniques

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 ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

SIGGRAPH '80: Proceedings of the 7th annual conference on Computer graphics and interactive techniques

July 1980

336 pages

ISBN:0897910214

DOI:10.1145/800250

ACM SIGGRAPH Computer Graphics Volume 14, Issue 3
July 1980
327 pages
ISSN:0097-8930
DOI:10.1145/965105
Issue’s Table of Contents

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 July 1980

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Acceptance Rates

SIGGRAPH '80 Paper Acceptance Rate 52 of 140 submissions, 37%;

Overall Acceptance Rate 1,822 of 8,601 submissions, 21%

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

68
Total Citations
View Citations
652
Total Downloads

Downloads (Last 12 months)106
Downloads (Last 6 weeks)21

Reflects downloads up to 05 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

View all

Beichl IBernal JWitzgall CSullivan F(2016)Computational GeometryEncyclopedia of Operations Research and Management Science10.1007/978-1-4419-1153-7_142(241-246)Online publication date: 23-Jan-2016
https://doi.org/10.1007/978-1-4419-1153-7_142
Akman VFranklin WKankanhalli MNarayanaswami C(1989)Geometric computing and uniform grid techniqueComputer-Aided Design10.1016/0010-4485(89)90125-521:7(410-420)Online publication date: 1-Aug-1989
https://dl.acm.org/doi/10.1016/0010-4485%2889%2990125-5
Carlbom I(1987)An Algorithm for Geometric Set Operations Using Cellular Subdivision TechniquesIEEE Computer Graphics and Applications10.1109/MCG.1987.2769877:5(44-55)Online publication date: 1-May-1987
https://dl.acm.org/doi/10.1109/MCG.1987.276987
Magnenat-Thalmann NThalmann D(1987)An Indexed Bibliography on Image SynthesisIEEE Computer Graphics and Applications10.1109/MCG.1987.2769177:8(27-38)Online publication date: 1-Aug-1987
https://dl.acm.org/doi/10.1109/MCG.1987.276917
Haines EGreenberg D(1986)The Light BufferIEEE Computer Graphics and Applications10.1109/MCG.1986.2768326:9(6-16)Online publication date: 1-Sep-1986
https://dl.acm.org/doi/10.1109/MCG.1986.276832
Franklin WWu PSamaddar SNichols M(1986)Prolog and geometry projectsIEEE Computer Graphics and Applications10.1109/MCG.1986.2766716:11(46-55)Online publication date: 1-Nov-1986
https://dl.acm.org/doi/10.1109/MCG.1986.276671
Dippé MSwensen J(1984)An adaptive subdivision algorithm and parallel architecture for realistic image synthesisACM SIGGRAPH Computer Graphics10.1145/964965.80859218:3(149-158)Online publication date: 1-Jan-1984
https://dl.acm.org/doi/10.1145/964965.808592
Dippé MSwensen JLuther DMueller RWeinberg REllis R(1984)An adaptive subdivision algorithm and parallel architecture for realistic image synthesisProceedings of the 11th annual conference on Computer graphics and interactive techniques10.1145/800031.808592(149-158)Online publication date: 1-Jan-1984
https://dl.acm.org/doi/10.1145/800031.808592
Franklin WBarr A(1981)Faster Calculation of Superquadric ShapesIEEE Computer Graphics and Applications10.1109/MCG.1981.16739411:3(41-47)Online publication date: 1-Jul-1981
https://dl.acm.org/doi/10.1109/MCG.1981.1673941
Beichl IBernal JWitzgall CSullivan F(2016)Computational GeometryEncyclopedia of Operations Research and Management Science10.1007/978-1-4419-1153-7_142(241-246)Online publication date: 23-Jan-2016
https://doi.org/10.1007/978-1-4419-1153-7_142
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Cited By

Index Terms

Recommendations

A linear time exact hidden surface algorithm

A simple algorithm for Boolean operations on polygons

Invisibility coherence for faster scan-line hidden surface algorithms