How to gain accurate results with Painter's algorithm?

A while ago I asked how to determine when a face is overlapping another. The advice was to use a Z-buffer.

However, I cannot use a Z-buffer in my current project and hence I would like to use the Painter's algorithm. I have no good clue as to when a surface is behind or in front of another, though. I've tried numerous methods but they all fail in edge cases, or they fail even in general cases.

This is a list of sorting methods I've tried so far:

• Distance to midpoint of each face
• Average distance to each vertex of each face
• Average z value of each vertex
• Higest z value of vertices of each face and draw those first
• Lowest z value of vertices of each face and draw those last

The problem is that a face might have a closer distance but is still further away. All these methods seem unreliable.

Edit: For example, in the following image the surface with the blue point as midpoint is painted over the surface with the red point as midpoint, because the blue point is closer. However, this is because the surface of the red point is larger and the midpoint is further away. The surface with the red point should be painted over the blue one, because it is closer, whilst the midpoint distance says the opposite. What exactly is used in the Painter's algorithm to determine the order in which objects should be drawn?

• The painters algorithm is just drawing from back to front. – Jonathan Connell Jul 1 '11 at 10:57
• @3nixios: Yes, obviously, but in what way can I determine the order of 'back to front'? – pimvdb Jul 1 '11 at 10:58
• All your objects, triangles or vertices will be a certain distance away from the camera when you start drawing. Implementing the basic algorithm (have you succeded?) would be to determine this distance from the camera for each triangle and draw them in the order furthest to nearest. Once that is done, you need to start looking for intersections and cutting up your triangles, which is a whole different ball game. Why can't you use Z-Buffer already? :P – Jonathan Connell Jul 1 '11 at 11:05
• @3nixios: You're completely correct, but the problem I'm facing is calculating the distance. As I stated, I've tried several distance methods but they're all not perfect. This order results from midpoint distance sorting: i.imgur.com/AcfCm.png. – pimvdb Jul 1 '11 at 11:13
• Are all your polygons on a regular grid like that? If so there may be grid specific things you can do to improve this. – CiscoIPPhone Jul 1 '11 at 12:19

Usually the distance of the midpoint of a polygon to the camera is being used for z-sorting. The painter's algorithm cannot be 100% accurate by it's nature. There will always be cases where sorting will fail, no matter what reference point you use.

If you want correct z-sorting with the painter's algorithm, you'll have to slice overlapping polygons into smaller parts (eg. by using a quad-tree) and sort these parts individually. This can become quite heavy on the CPU though..

Found this Powerpoint file that illustrates the issue nicely (PDF Version).

• Thanks for that Powerpoint, it helped me solve the problem. – pimvdb Jul 1 '11 at 13:59
• The link is broken. Can anybody find a copy? – Keavon Apr 21 '15 at 7:04
• @Keavon Edited. I found a working link for the file. – bummzack Apr 21 '15 at 11:27

In such cases for me it always worked using bsp-trees. Split the scene until you have convex set of polygons in bsp-tree's node and then you can easily sort polygons within the nodes. Note that by sorting polygons from the bsp-tree node it seems like the same problem as you described above, but there is a condition not so obvious - after constructing the bsp-tree all the problematic cases are already solved - in node you should end up with set of polygons from which the convexity test must pass - if you pick a plane from one polygon from this set, the rest of the polygons are all either in front of the plane or behind the plane. Using that info makes sorting easy - the sorting functor takes 2 polygons - check in which half-space is the 1st polygon against the 2nd polygon and also check the placement of camera against the second polygon. The 1st polygon is visually behind the 2nd polygon if: * side(p1, p2) == infront && side(camera, p2) == behind * side(p1, p2) == behind && side(camera, p2) == infront There are however certain cases where above condition if called with (p1, p2) tells that p1 is visually behind p2, and if called with (p2, p1), tells that p2 is visually behind p1 - in such cases the order doesn't matter as the polygons don't overlap on screen from the camera.

Note also that the tests for determining the side of camera placement against polygons and traversing of bsp-tree are slightly different when dealing with orthographic and perspective projection.

If you cannot afford splitting of the input polygons, I think you are out of luck.