The Painter’s algorithm, also known as Priority Fill, is one of the simplest solutions to the visibility problem in 3D computer graphics for example to create a error-free 3D configurator. When projecting a 3D scene onto a 2D plane, it is eventually necessary to decide which polygons are visible and which are hidden.
The term “Painter’s Algorithm” refers to the technique used by many painters to paint distant parts of a scene in front of closer parts and thus cover some areas of distant parts. The Painter’s algorithm sorts all polygons in a scene according to their depth and then paints them in this order, farthest from the next. It overpaints normally invisible parts – solving the visibility problem – at the expense of painting invisible areas of distant objects. The order used by the algorithm is called a “Depth Order” and does not have to take into account the numerical distances to the parts of the scene: The essential property of this order is that when an object obscures one part of another, the first object after the object that obscures it is painted. Thus, a final order can be described as a topological order of a directed acyclic graph representing occlusions between objects.
The algorithm may fail in some cases, including cyclic overlap or penetrating polygons. In the case of a cyclic overlap, as shown in the figure below, the circles A, B, and C overlap in such a way that it is impossible to determine which circle is above the other. In this case, the disturbing circles must be cut off to allow sorting. The Newell algorithm proposed in 1972 provides a method for cutting such objects. Numerous methods have also been proposed in the field of computer geometry.
The case of penetrating polygons occurs when one polygon intersects another. As with cyclic overlapping, this problem can be solved by cutting off the interfering polygons.
In basic implementations, the Painter’s algorithm can be inefficient. It forces the system to display every point on every polygon in the visible set, even if that polygon is included in the finished scene. This means that the Painter’s algorithm can regularly load the computer hardware for detailed scenes.
Sometimes the Reverse Painter’s algorithm is used, where objects are first painted near the viewer – with the rule that color must never be applied to already painted parts of the image (unless they are partially transparent). In a computer graphics system, this can be very efficient as it is not necessary to calculate the colors (by lighting, texturing, etc.) for parts of a distant scene that are hidden by nearby objects. However, the reverse algorithm has many of the same problems as the standard version.
These and other errors of the algorithm led to the development of Z-buffer techniques, which can be seen as a development of Painter’s algorithm by solving depth conflicts pixel by pixel, reducing the need for depth-based rendering order. Since Z-buffer implementations are generally based on hardware implemented registers with fixed accuracy, there is scope for visibility problems due to rounding errors. These are overlaps or gaps at the junctions between the polygons. To avoid this, some implementations of the graphics engine “overwrite” them by drawing the affected edges of both polygons in the order specified by Painter’s algorithm. This means that some pixels are actually drawn twice (as in the Full Painter’s algorithm), but this happens only to small parts of the image and has a negligible performance effect.
We hope that we were able to give you a first insight into the topic. If you have any suggestions or questions regarding this topic, please feel free to contact our experts in our forum.
Thank you very much for your visit.