Howdy, Stranger!

It looks like you're new here. If you want to get involved, click one of these buttons!


z-sorting of planes

programmeurkeprogrammeurke Member Posts: 19
still doing the basic-3d work (all by myself, btw)
i made a rotating, filled cube but the sorting work isn't that easy, the planes are made of four coordinates which makes it more difficult to sort the z-coords, can anybody help me?
thanx in advance


  • MutilateMutilate Member Posts: 22
    First of all greetings to you, I think we are the only two hardcore programmers (or fouls) around who are still doing an software 3d-engine without any kind of specified library or hardware acceleration, (I may be even worse 'cause I'm doing it in asm but whaterver).

    Second I have just got working a prespective correct texture mapper (just triangles for now, but optimized for cpu/fpu and Quake1's tricked), tell me if u are interessted.

    For your question I admit that I still didn't have done nothing on the subject of z-sorting but here what I found on several documents:

    The moust used methode is the bsp tree, I didn't still really get it, but in someway it should give you the polys in z-order and also exclude some polys that don't need to be draw, u find documetations at

    The easyest way instead to sort polys, would be to use as key the middle z of the poly by adding all z-coordinates, then divde by 4 and finally trown it in a binary tree that would sort polys in real time (so u dont need to sort the given array at the end)

    When u have sorted your polys you would then draw they from the farest to the closest one. That's called the painter algorithm.

    But there are other ways that allow u also to intersect polys.

    The z-buffer, you surely have allready readed of it somewhere, the idea (very simple) is to have a buffer big as the screen where you store the z value of the points you draw. So u only draw a points when his z is lesser than the previous one (in the buffer). You can allow interection if u interpolate the z value over the poly when u draw it. If you use prospective corrected texture mapping it would be a good idea to store 1/z insteed of z 'cause u are allready intepolating it, it will change only the condition (draw if old_1/z<new_1/z) and will allow you to reset the buffer by clearing it (all 0) instead of set it to 32767 (or whatever you are using as range). But the z-buffer isn't a big deal with the cpu, it would slow down your engine terribly.

    A good (and smarter) middle way is the s-buffer. Scan line buffer should be called I think, the idea is again to use a buffer were you store your z (or 1/z), but this time you store it not as a point but as a scann-line (horizontal line). Well it's a bit tricky to find all the overleap conditions, but it can really speed things up if you don't use the s-buffer only for z-sorting but also as drawing structure. That means that u don't store only the screen_y and the two screen_x,z(1/z) values but also all the other variable that u need to draw (color_ARGB,u,v,u/z,v/z,...), and then you perform drawing by drawing (that's right...for sure) all the resulting scann-lines after sorting (that means eliminate the ones u dont need to draw) and cuting them.
    I could write pages of optimization that comes in my mind by using the I let to you to find out.
    You may also ask my again when I will have build up a working algorithm.


Sign In or Register to comment.