The Painter's algorithm gets its name from the how an traditional oil painter paints a traditional landscape. First, the groundwork is laid out, by painting the background colors of the sky and the ground. Then the most distant objects are painted, then the second most distant, then nearer, and so forth. Each sequential layer completely obscures the layer that it covers. This is known as drawing from back-to-front.
Basic Painter's Algorithm:
Step 1:Sort objects from near to far.
Step 2:Render farthest object which hasn't been rendered already.
Step 3:Repeat step 2 until all objects have been rendered.
Here it is in the form of pseudocode:
Based on code from here.
DrawScene(){
view.objects(vertexList, transList, vertices); // input the objects
((ObjList) objList[0]).setVertexList(tranList);
raster.fill(getBackground());
sort(0, objects-1); // sort the objects
for (int i=objects-1; i=0; i--){
objList[i].Draw(raster); //draw objects from farthest to nearest
}
}
So, assume we have a set of objects, where S={A, B, C, D}, and all of the objects do not intersect each other. In step 1, we order the objects from near to far. The reordered set looks like {C, B, D, A}. In step 2, we render the farthest object, which in this case is A, so we render it.
In step 3, we repeat the process until all the objects are rendered. Here is the rest of the objects, rendered in order:
This might seem simple, until you need to define near to far. Otherwise there will be problems.
The choices most often used to define what is the depth of the object:
1. Take the maximum depth of the object.
2. Take the minimum depth of the object.
3. Take the centroid of the object.(The average of the depth of all the points of the object)