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.

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:

Large purple square with a section of red on the side

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?

share|improve this question
add comment

4 Answers 4

up vote 11 down vote accepted

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.

share|improve this answer
    
You are correct in saying that I'm creating a simple renderer. The point is that I'm not using any 3D libraries. I'm doing all projection calculations myself and then draw the lines using a 2D drawing library. This is not the fastest out there and I'm not doing anything on a per-pixel basis. I just have 4 points of each surface and fill the rectangular shape with a color. Since I'm drawing a complete surface at one time, am I correct in saying that I do have to draw back to front? –  pimvdb Apr 12 '11 at 11:19
    
Sounds like a lot of fun and a great way to learn. Back to front is your only way if you're doing this without any form of depth buffer. I think you're going to have to work out all the screen co-ordinates of your polygons and then check for any overlap. Where they overlap in depth you're potentially going to need to chop up the polygons to render, so you can actually resolve the sorting correctly. You might also want to look into Back Face Culling as a way to remove polygons that shouldn't necessarily be visible –  Roger Perkins Apr 12 '11 at 11:27
    
Roger Perkins is right. You won't be able to achieve correct z-sorting that way (meaning you'll always have some edge-cases), unless you chop up the polygons. That can become rather slow though. –  bummzack Apr 12 '11 at 12:45
    
I got it working! What I did was a combination of backface culling and sorting: in a solid cube, some faces are not visible whilst others are (max of 3). So I painted the non-visible parts first, and the visible parts over them. This works like a charm, if I remove one or more sides, they are overlapping but still drawn in the correct order. Thanks! –  pimvdb Apr 12 '11 at 13:29
1  
That'll only work for simple convex shapes, like cubes. I'm glad it's currently working out for you, but it's not a general solution. –  Richard Fabian Apr 12 '11 at 19:51
show 1 more comment

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

share|improve this answer
    
Thanks, but z-buffering requires per-pixel rendering if I'm not mistaking. I'm not doing that - I'm drawing straight lines between the projected points of the cube. Is z-buffering still possible? –  pimvdb Apr 12 '11 at 11:01
    
Even if you're drawing straight lines, at some point before the image gets to the screen (or bitmap file) it will be in pixel format. –  Bart van Heukelom Apr 12 '11 at 11:40
    
That's correct but my drawing library is too slow to do pixel rendering with 20fps. Thanks though. –  pimvdb Apr 12 '11 at 11:41
add comment

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.

share|improve this answer
    
That diagram is an overhead view of what I was going to guess is going on in his screenshot. –  jhocking Jun 8 '11 at 20:42
add comment

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.

share|improve this answer
    
Thanks for your response. I did read about backface culling but the point is that I'd like to be able to remove one side. With a solid cube this might work just great, but if I remove one side then there is occulision happening - so I still need to sort them I guess. Anyway, I came up with the idea of fireing a ray from the origin through the midpoint of a surface. If that ray crosses another surface afterwards, then the first surface is overlapping the second. Could you possibly tell me whether that idea is that correct? Thanks! –  pimvdb Apr 12 '11 at 12:17
    
Although your idea would work for your example case, there are plenty of other cases where it's not going to work. For example, the same scene you have there, but with the camera tilted so that the centre of the incorrect rendering quad is not overlapping.I think you're going to have to tesselate your primitives into smaller pieces. –  Richard Fabian Apr 12 '11 at 13:22
add comment

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.