Painter's algorithm

Last updated
A fractal landscape being rendered using the painter's algorithm on an Amiga

The painter's algorithm (also depth-sort algorithm and priority fill) is an algorithm for visible surface determination in 3D computer graphics that works on a polygon-by-polygon basis rather than a pixel-by-pixel, row by row, or area by area basis of other Hidden-Surface Removal algorithms. [1] [2] [3] The painter's algorithm creates images by sorting the polygons within the image by their depth and placing each polygon in order from the farthest to the closest object. [4] [5]

Contents

The painter's algorithm was initially proposed as a basic method to address the Hidden-surface determination problem by Martin Newell, Richard Newell, and Tom Sancha in 1972, while all three were working at CADCentre. [4] The name "painter's algorithm" refers to the technique employed by many painters where they begin by painting distant parts of a scene before parts that are nearer, thereby covering some areas of distant parts. [6] [7] Similarly, the painter's algorithm sorts all the polygons in a scene by their depth and then paints them in this order, farthest to closest. [8] It will paint over the parts that are normally not visible — thus solving the visibility problem — at the cost of having painted invisible areas of distant objects. [9] The ordering used by the algorithm is called a 'depth order' and does not have to respect the numerical distances to the parts of the scene: the essential property of this ordering is, rather, that if one object obscures part of another, then the first object is painted after the object that it obscures. [9] Thus, a valid ordering can be described as a topological ordering of a directed acyclic graph representing occlusions between objects. [10]

Painter's algorithm.svg
The distant mountains are painted first, followed by the closer meadows; finally, the trees, are painted. Although some trees are more distant from the viewpoint than some parts of the meadows, the ordering (mountains, meadows, trees) forms a valid depth order, because no object in the ordering obscures any part of a later object.

Algorithm

Conceptually Painter's Algorithm works as follows:

  1. Sort each polygon by depth
  2. Place each polygon from the farthest polygon to the closest polygon

Pseudocode

sortpolygons by depthfor eachpolygonp:     for eachpixel that p covers:         paintp.color on pixel

Time complexity

The painter's algorithm's time-complexity is heavily dependent on the sorting algorithm used to order the polygons. Assuming the use of the most optimal sorting algorithm, painter's algorithm has a worst-case complexity of O (n log n + m*n), where n is the number of polygons and m is the number of pixels to be filled.

Space complexity

The painter's algorithm's worst-case space-complexity is O(n+m), where n is the number of polygons and m is the number of pixels to be filled.

Advantages

There are two primary technical requisites that favor the use of the painter's algorithm.

Basic graphical structure

The painter's algorithm is not as complex in structure as its other depth sorting algorithm counterparts. [9] [11] Components such as the depth-based rendering order, as employed by the painter's algorithm, are one of the simplest ways to designate the order of graphical production. [8] This simplicity makes it useful in basic computer graphics output scenarios where an unsophisticated render will need to be made with little struggle. [9]

Memory efficiency

In the early 70s, when the painter's algorithm was developed, physical memory was relatively small. [12] This required programs to manage memory as efficiently as possible to conduct large tasks without crashing. The painter's algorithm prioritizes the efficient use of memory but at the expense of higher processing power since all parts of all images must be rendered. [9]

Limitations

Overlapping polygons can cause the algorithm to fail Painters problem.svg
Overlapping polygons can cause the algorithm to fail

The algorithm can fail in some cases, including cyclic overlap or piercing polygons.

Cyclical overlapping

In the case of cyclic overlap, as shown in the figure to the right, Polygons A, B, and C overlap each other in such a way that it is impossible to determine which polygon is above the others. In this case, the offending polygons must be cut to allow sorting. [4]

Piercing polygons

The case of piercing polygons arises when one polygon intersects another. Similar to cyclic overlap, this problem may be resolved by cutting the offending polygons. [4]

Efficiency

In basic implementations, the painter's algorithm can be inefficient. It forces the system to render each point on every polygon in the visible set, even if that polygon is occluded in the finished scene. This means that, for detailed scenes, the painter's algorithm can overly tax the computer hardware.

Variants

Extended painter's algorithm

Newell's algorithm, proposed as the extended algorithm to painter's algorithm, provides a method for cutting cyclical and piercing polygons. [4]

Reverse painter's algorithm

Another variant of painter's algorithm includes reverse painter's algorithm. Reverse painter's algorithm paints objects nearest to the viewer first — with the rule that paint must never be applied to parts of the image that are already painted (unless they are partially transparent). In a computer graphic system, this can be very efficient since it is not necessary to calculate the colors (using lighting, texturing, and such) for parts of a distant scene that are hidden by nearby objects. However, the reverse algorithm suffers from many of the same problems as the standard version.

Other computer graphics algorithms

The flaws of painter's algorithm led to the development of Z-buffer techniques, which can be viewed as a development of the painter's algorithm by resolving depth conflicts on a pixel-by-pixel basis, reducing the need for a depth-based rendering order. [13] Even in such systems, a variant of the painter's algorithm is sometimes employed. As Z-buffer implementations generally rely on fixed-precision depth-buffer registers implemented in hardware, there is scope for visibility problems due to rounding error. These are overlaps or gaps at joints between polygons. To avoid this, some graphics engines implement "over-rendering",[ citation needed ] drawing the affected edges of both polygons in the order given by the painter's algorithm. This means that some pixels are actually drawn twice (as in the full painter's algorithm), but this happens on only small parts of the image and has a negligible performance effect.

Related Research Articles

<span class="mw-page-title-main">Rendering (computer graphics)</span> Process of generating an image from a model

Rendering or image synthesis is the process of generating a photorealistic or non-photorealistic image from a 2D or 3D model by means of a computer program. The resulting image is referred to as the render. Multiple models can be defined in a scene file containing objects in a strictly defined language or data structure. The scene file contains geometry, viewpoint, textures, lighting, and shading information describing the virtual scene. The data contained in the scene file is then passed to a rendering program to be processed and output to a digital image or raster graphics image file. The term "rendering" is analogous to the concept of an artist's impression of a scene. The term "rendering" is also used to describe the process of calculating effects in a video editing program to produce the final video output.

<span class="mw-page-title-main">Scanline rendering</span> 3D computer graphics image rendering method

Scanline rendering is an algorithm for visible surface determination, in 3D computer graphics, that works on a row-by-row basis rather than a polygon-by-polygon or pixel-by-pixel basis. All of the polygons to be rendered are first sorted by the top y coordinate at which they first appear, then each row or scan line of the image is computed using the intersection of a scanline with the polygons on the front of the sorted list, while the sorted list is updated to discard no-longer-visible polygons as the active scan line is advanced down the picture.

<span class="mw-page-title-main">Rasterisation</span> Conversion of a vector-graphics image to a raster image

In computer graphics, rasterisation or rasterization is the task of taking an image described in a vector graphics format (shapes) and converting it into a raster image. The rasterized image may then be displayed on a computer display, video display or printer, or stored in a bitmap file format. Rasterization may refer to the technique of drawing 3D models, or to the conversion of 2D rendering primitives, such as polygons and line segments, into a rasterized format.

<span class="mw-page-title-main">Binary space partitioning</span> Method for recursively subdividing a space into two subsets using hyperplanes

In computer science, binary space partitioning (BSP) is a method for space partitioning which recursively subdivides a Euclidean space into two convex sets by using hyperplanes as partitions. This process of subdividing gives rise to a representation of objects within the space in the form of a tree data structure known as a BSP tree.

<span class="mw-page-title-main">Texture mapping</span> Method of defining surface detail on a computer-generated graphic or 3D model

Texture mapping is a method for mapping a texture on a computer-generated graphic. Texture here can be high frequency detail, surface texture, or color.

<span class="mw-page-title-main">Z-buffering</span> Type of data buffer in computer graphics

A depth buffer, also known as a z-buffer, is a type of data buffer used in computer graphics to represent depth information of objects in 3D space from a particular perspective. The depth is stored as a height map of the scene, the values representing a distance to camera, with 0 being the closest. The encoding scheme may be flipped with the highest number being the value closest to camera. Depth buffers are an aid to rendering a scene to ensure that the correct polygons properly occlude other polygons. Z-buffering was first described in 1974 by Wolfgang Straßer in his PhD thesis on fast algorithms for rendering occluded objects. A similar solution to determining overlapping polygons is the painter's algorithm, which is capable of handling non-opaque scene elements, though at the cost of efficiency and incorrect results.

<span class="mw-page-title-main">Shading</span> Depicting depth through varying levels of darkness

Shading refers to the depiction of depth perception in 3D models or illustrations by varying the level of darkness. Shading tries to approximate local behavior of light on the object's surface and is not to be confused with techniques of adding shadows, such as shadow mapping or shadow volumes, which fall under global behavior of light.

<span class="mw-page-title-main">Shadow volume</span> Computer graphics technique

Shadow volume is a technique used in 3D computer graphics to add shadows to a rendered scene. They were first proposed by Frank Crow in 1977 as the geometry describing the 3D shape of the region occluded from a light source. A shadow volume divides the virtual world in two: areas that are in shadow and areas that are not.

<span class="mw-page-title-main">Ray casting</span> Methodological basis for 3D CAD/CAM solid modeling and image rendering

Ray casting is the methodological basis for 3D CAD/CAM solid modeling and image rendering. It is essentially the same as ray tracing for computer graphics where virtual light rays are "cast" or "traced" on their path from the focal point of a camera through each pixel in the camera sensor to determine what is visible along the ray in the 3D scene. The term "Ray Casting" was introduced by Scott Roth while at the General Motors Research Labs from 1978–1980. His paper, "Ray Casting for Modeling Solids", describes modeled solid objects by combining primitive solids, such as blocks and cylinders, using the set operators union (+), intersection (&), and difference (-). The general idea of using these binary operators for solid modeling is largely due to Voelcker and Requicha's geometric modelling group at the University of Rochester. See solid modeling for a broad overview of solid modeling methods. This figure on the right shows a U-Joint modeled from cylinders and blocks in a binary tree using Roth's ray casting system in 1979.

<span class="mw-page-title-main">Hidden-surface determination</span> Visibility in 3D computer graphics

In 3D computer graphics, hidden-surface determination is the process of identifying what surfaces and parts of surfaces can be seen from a particular viewing angle. A hidden-surface determination algorithm is a solution to the visibility problem, which was one of the first major problems in the field of 3D computer graphics. The process of hidden-surface determination is sometimes called hiding, and such an algorithm is sometimes called a hider. When referring to line rendering it is known as hidden-line removal. Hidden-surface determination is necessary to render a scene correctly, so that one may not view features hidden behind the model itself, allowing only the naturally viewable portion of the graphic to be visible.

Martin Edward Newell is a British-born computer scientist specializing in computer graphics who is perhaps best known as the creator of the Utah teapot computer model.

<span class="mw-page-title-main">Reflection mapping</span>

In computer graphics, reflection mapping or environment mapping is an efficient image-based lighting technique for approximating the appearance of a reflective surface by means of a precomputed texture. The texture is used to store the image of the distant environment surrounding the rendered object.

Clipping, in the context of computer graphics, is a method to selectively enable or disable rendering operations within a defined region of interest. Mathematically, clipping can be described using the terminology of constructive geometry. A rendering algorithm only draws pixels in the intersection between the clip region and the scene model. Lines and surfaces outside the view volume are removed.

<span class="mw-page-title-main">Stencil buffer</span>

A stencil buffer is an extra data buffer, in addition to the color buffer and Z-buffer, found on modern graphics hardware. The buffer is per pixel and works on integer values, usually with a depth of one byte per pixel. The Z-buffer and stencil buffer often share the same area in the RAM of the graphics hardware.

Newell's Algorithm is a 3D computer graphics procedure for elimination of polygon cycles in the depth sorting required in hidden surface removal. It was proposed in 1972 by brothers Martin Newell and Dick Newell, and Tom Sancha, while all three were working at CADCentre.

Tiled rendering is the process of subdividing a computer graphics image by a regular grid in optical space and rendering each section of the grid, or tile, separately. The advantage to this design is that the amount of memory and bandwidth is reduced compared to immediate mode rendering systems that draw the entire frame at once. This has made tile rendering systems particularly common for low-power handheld device use. Tiled rendering is sometimes known as a "sort middle" architecture, because it performs the sorting of the geometry in the middle of the graphics pipeline instead of near the end.

Order-independent transparency (OIT) is a class of techniques in rasterisational computer graphics for rendering transparency in a 3D scene, which do not require rendering geometry in sorted order for alpha compositing.

<span class="mw-page-title-main">Depth map</span> Image also containing data on distances of objects from the camera

In 3D computer graphics and computer vision, a depth map is an image or image channel that contains information relating to the distance of the surfaces of scene objects from a viewpoint. The term is related to depth buffer, Z-buffer, Z-buffering, and Z-depth. The "Z" in these latter terms relates to a convention that the central axis of view of a camera is in the direction of the camera's Z axis, and not to the absolute Z axis of a scene.

In computer graphics, A-buffer, also known as anti-aliased, area-averaged or accumulation buffer, is a general hidden surface mechanism suited to medium scale virtual memory computers. It resolves visibility among an arbitrary collection of opaque, transparent, and intersecting objects. Using an easy to compute Fourier window, it increases the effective image resolution many times over the Z-buffer, with a moderate increase in cost.

This is a glossary of terms relating to computer graphics.

References

  1. ↑ Appel, Arthur (1968). Morrel, A. J. H. (ed.). "On calculating the illusion of reality" (PDF). Information Processing, Proceedings of IFIP Congress 1968, Edinburgh, UK, 5-10 August 1968, Volume 2 - Hardware, Applications: 945–950. Archived (PDF) from the original on 2008-07-20.
  2. ↑ Romney, Gordon Wilson (1969-09-01). "Computer Assisted Assembly and Rendering of Solids". Archived from the original on November 2, 2020.{{cite journal}}: Cite journal requires |journal= (help)
  3. ↑ Gary Scott Watkins. 1970. "A real time visible surface algorithm. Ph.D. Dissertation." The University of Utah. Order Number: AAI7023061.
  4. 1 2 3 4 5 Newell, M. E.; Newell, R. G.; Sancha, T. L. (1972-08-01). "A solution to the hidden surface problem" (PDF). Proceedings of the ACM annual conference on - ACM'72. ACM '72. Vol. 1. Boston, Massachusetts, USA: Association for Computing Machinery. pp. 443–450. doi:10.1145/800193.569954. ISBN   978-1-4503-7491-0. S2CID   13829930. Archived (PDF) from the original on 2020-09-22.
  5. ↑ Bouknight, W. Jack (1970-09-01). "A procedure for generation of three-dimensional half-toned computer graphics presentations". Communications of the ACM. 13 (9): 527–536. doi: 10.1145/362736.362739 . ISSN   0001-0782. S2CID   15941472.
  6. ↑ Berland, Dinah (1995). Historical Painting Techniques, Materials, and Studio Practice (PDF). The Getty Conservation Institute.
  7. ↑ Wylie, Chris; Romney, Gordon; Evans, David; Erdahl, Alan (1967-11-14). "Half-tone perspective drawings by computer". Proceedings of the November 14-16, 1967, fall joint computer conference on - AFIPS '67 (Fall). Anaheim, California: Association for Computing Machinery. pp. 49–58. doi:10.1145/1465611.1465619. ISBN   978-1-4503-7896-3. S2CID   3282975.
  8. 1 2 Desai, Apurva (2008). Computer Graphics. PHI Learning Pvt. Ltd. ISBN   9788120335240.
  9. 1 2 3 4 5 de Berg, Mark (2008). Computational Geometry (PDF). Springer. Archived (PDF) from the original on 2016-08-03.
  10. ↑ de Berg, Mark (1993). Ray Shooting, Depth Orders and Hidden Surface Removal. Lecture Notes in Computer Science. Vol. 703. Springer. p. 130. ISBN   9783540570202..
  11. ↑ Warnock, John E. (1969-06-01). "A Hidden Surface Algorithm for Computer Generated Halftone Pictures". Archived from the original on November 8, 2020.{{cite journal}}: Cite journal requires |journal= (help)
  12. ↑ Freiser, M.; Marcus, P. (June 1969). "A survey of some physical limitations on computer elements". IEEE Transactions on Magnetics. 5 (2): 82–90. Bibcode:1969ITM.....5...82F. doi:10.1109/TMAG.1969.1066403. ISSN   1941-0069.
  13. ↑ Nyberg, Daniel (2011). Analysis of Two Common Hidden Surface Removal Algorithms, Painter's Algorithm & Z-Buffering.
This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.