What exactly causes a surface to overlap another?

Question

I cannot really figure out what causes one surface to overlap another. In a 3D engine I'm creating, my technique is failing in edge cases.

My method is sorting the surfaces to be painted from the furthest to the closest. To determine the closeness, I'm comparing the average z values. Sometimes, however, an overlapping surface has a higher average z value than the one it is overlapping. Thus, the surface further away is painted over the closer one - resulting in bizarre rendering like this:

What one is meant to see is the purple front surface of the cube only, whilst the red side surface is painted over the purple one. The average z value of the purple surface is higher, and therefore 'further away'. So I'm having some doubt as to whether this technique is correct.

What I also tried is getting the distance from the camera (i.e. origin) to the surface, but then I needed a point. I chose the middle of each surface but also this doesn't always seem to work because not all surfaces are as large as each other.

Therefore, what is a reliable way to determine the order of closeness of surfaces towards the origin?

Answer 1

You seem to be trying to implement the Painters Algorithm. I'm guessing you're trying to write a rasteriser from scratch as a learning exercise, as most modern 3D hardware uses what Bart has mentioned (the Z/Depth buffer). For the painters algorithm to work in all cases, you'd need to be prepared to subdivide the surfaces as they're rendered to solve possible scenarios (such as the overlapping polygon problem shown on the Wikipedia page).

By rendering from furthest to closest you're also spending time rendering pixels which will possibly later be occluded by other polygons, which when you start putting textures and complex shaders on the polygons wastes precious cycles. This is the reason modern hardware would prefer you to render from front to back, using the depth buffer to determine if the pixel to be rendered is further away than the one on the screen (and can therefore be discarded).

Even with most modern acceleration hardware you'll still need to sort and render from back to front any semi-transparent polygons, rendering this only once all the opaque polygons have been rendered.

Answer 2

What you have is a visibility problem. One solution is using a z-buffer.

Answer 3

Sorting the faces according to their average z-value doesn't work, because the average z-value provides no information on the actual z-value of the vertices or even surface pixels.

Example (warning, ASCII art ahead):

          /
         /
cam     /
-->    / 
      /
     /--       <--B
    /
    ^--A

There are two faces A and B. From the camera's perspective A is in front of B. Yet the average z-value of B is smaller. Let's look at the other z-values:

• the minimum z-value of A is 4
• the maximum z-value of A is 11
• therefore the average z-value of A is 7.5
• the minimum z-value of B is 6
• the maximum z-value of B is 8
• therefore the average z-value of B is 7

You could try to sort them by their minimal z-values but there cases where that won't work too. There is just no way to sort arbitrary faces correctly using just one z-value.

In Newell's algorithm http://en.wikipedia.org/wiki/Newell's_algorithm what you do is sort the min/max-ranges of the z-values. If the ranges of two faces do not overlap you can know for sure which one is in front. If they do, sometimes you absolutely have to split the faces. Sometimes it will suffice to raytrace every vertex for occlusion or some other technique.

Answer 4

It's good that you are learning about rendering by doing. Kudos. In this instance, there is no "painters algorithm" solution, instead of trying to fix it by sorting, on the PS1 we used to just try to keep polygons around the same size when they were next to each other (which you are doing as far as I can tell), and backface cull (which you're not doing)

Backface culling is checking the surface normal in screen space for it's direction (just get the sign of the depth element from the screen space transformed normal (in our case it was the z of the normal), or the cross product of two vectors of the triangle i.e. cross( v1-v0, v2-v0 ))

If you implement backface culling, you also reduce the amount of rasterising you're doing.. double win.