An exact incremental hidden surface removal algorithm
EGGH'87: Proceedings of the Second Eurographics conference on Advances in Computer Graphics Hardware
Pages 21 - 37
Abstract
This paper describes an incremental Hidden Surface Removal Algorithm (HSRA), developed to be embedded in a new architecture for raster graphics described in [1,7]. The algorithm can be classified as "exact" since it operates in object space, rather than image space. It can be classified as "incremental" because this HSRA is able to support addition, removal and changes on a single object or a group of objects. Thus a firm basis for powerful interaction and animation is established. Due to specially designed data structures for both geometric objects as well as storage of these objects, the hidden surface removal calculation on a complete scene will have the same time complexity as existing algorithms. However, the effort needed for incremental changes is much less than any other known algorithm. The data structures as well as the algorithm are designed to exploit parallelism in computation.
References
[1]
V. Akman, P.J.W. ten Hagen, and A.A.M. Kuijk, "A Vector-like Architecture for Raster Graphics," these proceedings (1988).
[2]
J.L. Bentley and D. Wood, "An Optimal Worst Case Algorithm for Reporting Intersections of Rectangles," IEEE Transactions on Computers C29(7) (1980).
[3]
J. Foley and A. van Dam, Fundamentals of Interactive Computer Graphics, Addison-Wesley, Reading, Mass. (1982).
[4]
W.R. Franklin and V. Akman, "Adaptive Grid for Polyhedral Visibility in Object Space: An Implementation," RUU-CS-86-4, University of Utrecht, The Netherlands (1986).
[5]
P.J.W. ten Hagen and T. Trienekens, "Pattern Representation," Report CSR8602, Center for Mathematics and Computer Science, Amsterdam (Jan. 1986).
[6]
P.J.W. ten Hagen, M.M. de Ruiter, and C.G. Trienekens, "Raster Graphics Facilities (RGF)," preliminary report, Center for Mathematics and Computer Science, Amsterdam (1986).
[7]
P.J.W. ten Hagen, A.A.M. Kuijk, and T. Trienekens, "Display Architecture for VLSI-based Graphics Workstations," in Advances in Computer Graphics Hardware I, ed. W. Straßer, Springer-Verlag (1987).
[8]
H.G. Mairson and J. Stolfi, "Reporting and Counting Intersections Between Two Sets of Line Segments," in Theoretical Foundations of Computer Graphics and CAD, ed. R.A. Earnshaw, Springer-Verlag, Heidelberg (1988).
[9]
I.E. Sutherland, R.F. Sproull, and R.A Schumacker, "A Characterization of Ten Hidden-Surface Algorithms," Computing Surveys 6(1) (1974).
[10]
D. Wood, "An Isothetic View of Computational Geometry," in Computational Geometry, ed. G.T. Toussaint, Elsevier Science Publishers B.V. (North Holland) (1985).
Index Terms
- An exact incremental hidden surface removal algorithm
Recommendations
An application of color graphics to the display of surface curvature
In developing a mathematical representation for a surface, designers currently must use line drawing graphics to examine the curvature of a line in a plane, a two-dimensional analysis. By combining a result from differential geometry with the use of ...
An application of color graphics to the display of surface curvature
SIGGRAPH '81: Proceedings of the 8th annual conference on Computer graphics and interactive techniquesIn developing a mathematical representation for a surface, designers currently must use line drawing graphics to examine the curvature of a line in a plane, a two-dimensional analysis. By combining a result from differential geometry with the use of ...
A simple output-sensitive algorithm for hidden surface removal
We derive a simple output-sensitive algorithm for hidden surface removal in a collection of n triangles in space for which a (partial) depth order is known. If k is the combinatorial complexity of the output visibility map, the method runs in time O(n √k ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
Sponsors
- CWI: Centrum voor Wiskunde en Informatica - Netherlands
- EUROGRAPHICS: The European Association for Computer Graphics
Publisher
Eurographics Association
Goslar, Germany
Publication History
Published: 24 August 1987
Author Tags
Qualifiers
- Article
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 0Total Downloads
- Downloads (Last 12 months)0
- Downloads (Last 6 weeks)0
Reflects downloads up to 28 Feb 2025