Visibility problem

from Wikipedia, the free encyclopedia
Above: View of a scene with an observer.
Bottom left: Projected objects without occlusion calculation.
Bottom right: Rendered image after the occlusion calculation, in which it was determined that the blue sphere and the gray triangle partially obscure the yellow sphere.

The visibility problem when rendering in computer graphics is the question of which parts of surfaces in a 3D scene are visible when projected onto the two-dimensional display surface . A concealment calculation or visibility decision is accordingly a procedure with which invisible surfaces are recognized and sorted out and the visibility problem is thus solved. The visibility problem was one of the first major problems in computer graphics.

The occlusion calculation is necessary for the correct rendering of a 3D scene, because surfaces that are not visible to the viewer should not be displayed either. Many processes also speed up rendering because invisible surfaces can be excluded from further processing by the graphics pipeline .

Procedure

According to Ivan Sutherland , algorithms for computation of masking can be divided into object space methods, image space methods and list priority methods. While with the object space method the visibilities are calculated analytically and independently of the output device directly on the basis of the objects, with the image space method the concealment calculation is carried out separately for each individual image or pixel position. List priority algorithms first calculate a visibility order or "priority" based on the objects and then color the pixels of the image; so they work partly in the object space as well as in the image space.

Today's graphics hardware mostly uses a Z-buffer to calculate masking ; Ray tracing is often used in realistic image synthesis .

For a related problem, see Visibility Polygon .

Object space method

Roberts (1963)
By Larry Roberts , the first known method comes to masking calculation. Roberts' algorithm tests each polygon edge against each polyhedron to see if it is (partially or completely) covered. This test is performed by solving a linear equation problem. Roberts' algorithm only works with convex polyhedra.
Appel, Loutrel, Galimberti, Montanari (1967/69)
Appel's algorithm is representative of a class of algorithms that determine the visible edge segments. In contrast to Roberts' algorithm, they can also calculate the obscuration by individual polygons, not just by whole polyhedra. Appel defines the quantitative invisibility of a point as the number of significant polygons that obscure it. If an edge slides behind an obscuring polygon, the quantitative invisibility is increased by 1, and if it is no longer obscured by the polygon, it is decreased by 1. To solve the visibility problem, the quantitative invisibility of each point on each edge must be calculated; a point is visible if the value is 0. The algorithms of Loutrel and Galimberti and Montanari work very similarly.
Hamlet, Atherton (1977)
The Weiler-Atherton algorithm determines the visibility by starting from the a priori closest polygon and clipping all polygons against this polygon . This divides the polygons along the border of the visible and invisible parts and discards the invisible parts. At the end the algorithm returns a list of visible polygon parts.
Haloed Lines (1979)
The Haloed-Line algorithm by Appel, Rohlf and Stein works exclusively with line segments and does not depend on the objects that are made up of them. It is therefore an algorithm for the visibility decision of lines (Visible Line Determination) and not of surfaces (Visible Surface Determination). Each drawn line segment is given a contour ("halo") on both sides, which partially covers the lines behind it.

List priority procedure

Schumacker, Brand, Gilliland, Sharp (1969)
Schumacker's algorithm was the first real-time solution to the visibility problem and was optimized for flight simulations. It is only applicable to convex polyhedra. The algorithm uses a priority list that depends mainly on the scene and hardly on the viewer's position. For reasons of efficiency, the geometry is grouped into so-called clusters.
Depth Sort (1972)
The idea of ​​the Depth-Sort algorithm by Newell, Newell and Sancha is to sort all polygons according to their smallest z -coordinate, to solve any ambiguities in overlapping polygons by dividing the polygons, and finally to sort each polygon, starting with the last one, to rasterize. A simplified version of the algorithm that ignores ambiguous cases is often called the painter's algorithm . It is only suitable for applications in which the objects do not overlap along the z- axis.
BSP algorithm (1980)
The BSP algorithm by Fuchs, Kedem and Naylor is an improvement on Schumacker's algorithm, which automates the grouping of objects into clusters. For this purpose, a BSP tree is set up.

Image space method

Scanline algorithms (late 1960s)
Several similar scanline algorithms have been published. All of these methods first sort along the y axis and then along the x axis in order to finally select the visible polygon with the closest distance to the viewer for each pixel. Since the configuration of the polygons changes little from image line to image line, the "active" polygons for each image line are entered in a list that is updated as required.
Ray tracing (late 1960s)
The ray tracing algorithm, published by Appel, Goldstein and Nagel, is based on the "emission" of rays from the observer, which are sent through the image plane into the scene. Each ray is tested against all primitives and the distance is calculated if necessary. The visible object is the one with the closest distance. Numerous acceleration techniques have been developed for the ray tracing algorithm, which drastically reduce the number of objects to be tested. Raycasting is a restricted variant of raytracing that is only suitable for scenes that consist of rectangles of equal height aligned on the axes.
Warnock (1968)
The Warnock algorithm is based on the assumption that the image can be divided into rectangular regions in which at most one polygon determines the content of the image. If this is not the case in a region, it is subdivided. The subdivision continues recursively until the regions only enclose one pixel.
Z-Buffer (1974)
Edwin Catmull's very simple Z-buffer algorithm stores additional depth information for each pixel. As each object is rasterized, the pixel color value and the value in the Z-buffer are updated if the distance to the corresponding point on the object is less than the current Z-buffer value.

Implementations

The best-known approaches to solving the visibility problem in 3D computer graphics , particularly with regard to performance, are culling and the use of a Z-buffer .

literature

  • Max Agoston: Computer Graphics and Geometric Modeling: Implementation and Algorithms. Springer, London 2005, ISBN 1-85233-818-0
  • James D. Foley et al: Computer Graphics: Principles and Practice. Addison-Wesley, Reading 1995, ISBN 0-201-84840-6
  • David F. Rogers: Procedural Elements for Computer Graphics. WCB / McGraw-Hill, Boston 1998, ISBN 0-07-053548-5
  • Alan Watt: 3D Computer Graphics. Addison-Wesley, Harlow 2000, ISBN 0-201-39855-9

Individual evidence

  1. ^ Ivan Sutherland et al: A Characterization of Ten Hidden-Surface Algorithms. ACM Computing Surveys (CSUR) 6, 1 (March 1974): 1-55, ISSN  0360-0300
  2. ↑ Lawrence Roberts: Machine Perception Of Three-Dimensional Solids. Lincoln Laboratory, TR 315, MIT, Cambridge 1963 ( online )
  3. ^ Rogers: Procedural Elements for Computer Graphics, p. 303
  4. ^ Arthur Appel: The Notion of Quantitative Invisibility and the Machine Rendering of Solids. In Proceedings of the 1967 22nd ACM Annual Conference. Pp. 387-393. ACM, New York 1967
  5. ^ Philippe Paul Loutrel: A Solution to the Hidden-Line Problem for Computer-Drawn Polyhedra. Department of Electrical Engineering, New York University, Technical Report 400-167, 1967
  6. ^ R. Galimberti, U. Montanari: An Algorithm for Hidden Line Elimination. Communications of the ACM 12, 4 (April 1969): 206-211, ISSN  0001-0782
  7. ↑ Kevin Weiler, Peter Atherton: Hidden Surface Removal Using Polygon Area Sorting. ACM SIGGRAPH Computer Graphics 11, 2 (Summer 1977): 214-222, ISSN  0097-8930
  8. ^ Arthur Appel et al: The Haloed Line Effect for Hidden Line Elimination. ACM SIGGRAPH Computer Graphics 13, 2 (Aug. 1979): 151-157, ISSN  0097-8930
  9. ^ RA Schumaker et al .: Study for Applying Computer-Generated Images to Visual Simulation. AFHRL-TR-69-14. US Air Force Human Resources Laboratory, 1969
  10. ↑ Ivan Sutherland et al .: A Characterization of Ten Hidden-Surface Algorithms, p. 23
  11. ^ ME Newell et al.: A Solution to the Hidden Surface Problem. In Proceedings of the ACM Annual Conference 1972 - Volume 1. ACM, New York 1972
  12. ^ Henry Fuchs et al .: On Visible Surface Generation by Priori Tree Structures. In SIGGRAPH '80 Proceedings, pp. 124-133. ACM, New York 1980, ISBN 0-89791-021-4
  13. ↑ Jack Bouknight: A procedure for generation of three-dimensional half-toned computer graphics presentations. Communications of the ACM 13,9 (Sep 1970): 527-536, ISSN  0001-0782
  14. ↑ Jack Bouknight, K. Kelley: An algorithm for producing half-tone computer graphics presentations with shadows and movable light sources. In AFIPS Conference Proceedings, vol. 36: 1970 Fall Joint Computer Conference. Pp. 1-10. AFIPS Press, Montvale 1970
  15. ^ Gary Scott Watkins: A Real Time Visible Surface Algorithm. Dissertation, University of Utah 1970
  16. ↑ C. Wylie et al .: Halftone Perspective Drawings by Computer. In AFIPS Conference Proceedings, vol. 31: 1967 Fall Joint Computer Conference. Pp. 49-58. AFIPS Press, Montvale 1967
  17. ↑ Arthur Appel: Some Techniques for Shading Machine Renderings of Solids. In Proceedings of the Spring Joint Computer Conference 1968. pp. 37-45. AFIPS Press, Arlington
  18. ^ Mathematical Applications Group, Inc .: 3-D Simulated Graphics Offered by Service Bureau. Datamation 13, 1 (Feb. 1968): 69, ISSN  0011-6963
  19. ^ Robert Goldstein, Roger Nagel: 3-D Visual Simulation. Simulation 16, 1 (Jan. 1971): 25-31, ISSN  0037-5497
  20. ^ John Warnock: A Hidden-Surface Algorithm for Computer Generated Half-Tone Pictures. Technical Report TR 4-15, NTIS AD-753 671, Computer Graphics Department, University of Utah, Salt Lake City 1969
  21. ^ Edwin Catmull: A Subdivision Algorithm for Computer Display of Curved Surfaces. Dissertation, Report UTEC-CSc-74-133, Computer Science Department, University of Utah, Salt Lake City 1974