Take the 2-minute tour ×
Game Development Stack Exchange is a question and answer site for professional and independent game developers. It's 100% free, no registration required.

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.

enter image description here

What exactly is used in the Painter's algorithm to determine the order in which objects should be drawn?

share|improve this question
1  
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
1  
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
1  
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

1 Answer 1

up vote 12 down vote accepted

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.

share|improve this answer
    
Thanks for that Powerpoint, it helped me solve the problem. –  pimvdb Jul 1 '11 at 13:59

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.