The painter’s algorithm (also depth-sort algorithm and priority fill) is an algorithm for
visible surface determination in
3D computer graphics
3D computer graphics, or “3D graphics,” sometimes called CGI, 3D-CGI or three-dimensional computer graphics are graphics that use a three-dimensional representation of geometric data (often Cartesian) that is stored in the computer for th ...
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
In 3D computer graphics, hidden-surface determination (also known as shown-surface determination, hidden-surface removal (HSR), occlusion culling (OC) or visible-surface determination (VSD)) is the process of identifying what surfaces and parts o ...
algorithms. 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.
The painter's algorithm was initially proposed as a basic method to address the
Hidden-surface determination
In 3D computer graphics, hidden-surface determination (also known as shown-surface determination, hidden-surface removal (HSR), occlusion culling (OC) or visible-surface determination (VSD)) is the process of identifying what surfaces and parts o ...
problem by
Martin Newell,
Richard Newell Richard Newell may refer to:
*King Biscuit Boy (Richard A. Newell), Canadian blues musician
*Dick Newell
Richard G. Newell is a British businessman and technologist in the software industry in Computer aided design (CAD) and Geographic Informati ...
, and Tom Sancha in 1972, while all three were working at
CADCentre.
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. 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.
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.
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.
Thus, a valid ordering can be described as a
topological ordering
In computer science, a topological sort or topological ordering of a directed graph is a linear ordering of its vertices such that for every directed edge ''uv'' from vertex ''u'' to vertex ''v'', ''u'' comes before ''v'' in the ordering. For in ...
of a
directed acyclic graph
In mathematics, particularly graph theory, and computer science, a directed acyclic graph (DAG) is a directed graph with no directed cycles. That is, it consists of vertices and edges (also called ''arcs''), with each edge directed from one ve ...
representing occlusions between objects.
Algorithm
Conceptually Painter's Algorithm works as follows:
# Sort each polygon by depth
# Place each polygon from the farthest polygon to the closest polygon
Pseudocode
sort ''polygons'' by ''depth''
for each ''polygon'' ''p'':
for each ''pixel'' that ''p'' covers:
paint ''p.color'' on ''pixel''
Time complexity
The painter's algorithm's time-complexity is heavily dependent on the
sorting algorithm
In computer science, a sorting algorithm is an algorithm that puts elements of a List (computing), list into an Total order, order. The most frequently used orders are numerical order and lexicographical order, and either ascending or descending. ...
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.
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.
This simplicity makes it useful in basic computer graphics output scenarios where an unsophisticated render will need to be made with little struggle.
Memory efficiency
In the early 70s, when the painter’s algorithm was developed, physical memory was relatively small. 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.
![Painters problem](https://upload.wikimedia.org/wikipedia/commons/7/78/Painters_problem.svg)
Limitations
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.
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.
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 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 w ...
, proposed as the extended algorithm to painter's algorithm, provides a method for cutting cyclical and piercing polygons.
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
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 Three-dimensional space, 3D space from a particular Perspective (graphical), perspective. Depth buffers are ...
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.
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", 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.
References
*
External links
Painter's & Z-Buffer Algorithms and Polygon Rendering* https://www.clear.rice.edu/comp360/lectures/old/HiddenSurfText.pdf
* https://www.cs.princeton.edu/courses/archive/spring01/cs598b/papers/greene93.pdf
{{Computer graphics
3D computer graphics
Computer graphics algorithms