gbadev.org forum archive

This is a read-only mirror of the content originally found on forum.gbadev.org (now offline), salvaged from Wayback machine copies. A new forum can be found here.

Graphics > What is Z Buffer?

#4844 - Gordon - Sat Apr 12, 2003 4:05 am

I don't know what is Z Buffer! Are there any defination?

#4849 - Daikath - Sat Apr 12, 2003 11:00 am

A buffer where the program gets some room for error when calculating the distance in 3d before it is displayed.
_________________
?There are no stupid questions but there are a LOT of inquisitive idiots.?

#4875 - Torlus - Sun Apr 13, 2003 8:55 pm

Z-Buffer is used for 3d display. Basically, when you have to render a 3D scene into 2D (your screen) you do a perpsective projection (roughly, divide your x and y coordinates by your z coordinate gives you a good result). But then you have to cope with objects placement (determine which objects have to be seen because they are closer to you, and which ones may be hidden as they may be behind the previous ones).

For this problem there is a simple answer. When you draw an object, for each pixel belonging to this object, you will draw it on the screen and at the same time store on a buffer (which has the same size of your screen) the z coordinate of your object's pixel at the same position.
Then when you have to draw another pixel belonging to another object, you compare the z coordinate stored in the z-buffer to the z-coordinate of the pixel you have to draw. If it is lower, then it means that this pixel is "closer" to you than the previous one, so you do draw it. If it higher then it means it is faster, so you don't draw it.

I'm not sure my explanation is very clear (maybe because english isn't my natural language) :)

This algorithm is very simple to implement (so easy that some machines implement it in hardware). But it is also memory-consuming, and there are much efficient ways to cope with this problem, as S-Buffer and C-Buffer (try to "google" them, once you have understood the Z-buffer algorithm).

(I'm about to replace my crappy z-buffer stuff with some kind of S-buffer & C-buffer mix in my small engine. Please tell me if you want to contribute :) )

Open-source 3D engine for GBA and other stuff... http://heliscar.com/greg/

#4884 - Gordon - Mon Apr 14, 2003 4:05 am

Thx all!
Torlus your explaination is good enough! I got the idea of what is Z-Buffer now! Nice to see you all! where do you live? are u work?
Thx,
Bye now!

#5156 - rusty - Tue Apr 22, 2003 12:15 pm

Torlus wrote:
Z-Buffer is used for 3d display. Basically, when you have to render a 3D scene into 2D (your screen) you do a perpsective projection (roughly, divide your x and y coordinates by your z coordinate gives you a good result). But then you have to cope with objects placement (determine which objects have to be seen because they are closer to you, and which ones may be hidden as they may be behind the previous ones).

For this problem there is a simple answer. When you draw an object, for each pixel belonging to this object, you will draw it on the screen and at the same time store on a buffer (which has the same size of your screen) the z coordinate of your object's pixel at the same position.
Then when you have to draw another pixel belonging to another object, you compare the z coordinate stored in the z-buffer to the z-coordinate of the pixel you have to draw. If it is lower, then it means that this pixel is "closer" to you than the previous one, so you do draw it. If it higher then it means it is faster, so you don't draw it.

I'm not sure my explanation is very clear (maybe because english isn't my natural language) :)

This algorithm is very simple to implement (so easy that some machines implement it in hardware). But it is also memory-consuming, and there are much efficient ways to cope with this problem, as S-Buffer and C-Buffer (try to "google" them, once you have understood the Z-buffer algorithm).

(I'm about to replace my crappy z-buffer stuff with some kind of S-buffer & C-buffer mix in my small engine. Please tell me if you want to contribute :) )

Open-source 3D engine for GBA and other stuff... http://heliscar.com/greg/


s-buffering? s-buffering works great for large polys (linke the polys that make up your world), but if you intend to draw any small 3d objects/sprites, it's maybe a good idea to have a s-buffer/z-buffer hybrid.

As you draw your s-buffer, make each entry write into the z-buffer, so that when it comes time to drawing small objects, then then use the z-buffer alone.

Since your spans are writting to the z-buffer and not performing any z-tests, you don't have to clear the z-buffer at the start of each frame (or the frame buffer for that matter).

You probably already thought of that though.... :)

#5157 - Torlus - Tue Apr 22, 2003 12:40 pm

Hm.. not really. I'm not sure to understand :)
I know that s-buffer isn't very efficient when you have a lot of small spans.
c-buffer seems a bit more efficient, but you have to sort polys (what can be avoided i think with s-buffer).
In fact, I don't really know which way is the best. If someone is experienced with all these methods, help will be welcome :)
_________________
GBA,GC,NGPC,GP32,FPGA,DS stuff at http://torlus.com/

#5166 - rusty - Tue Apr 22, 2003 3:49 pm

Torlus wrote:
Hm.. not really. I'm not sure to understand :)
I know that s-buffer isn't very efficient when you have a lot of small spans.
c-buffer seems a bit more efficient, but you have to sort polys (what can be avoided i think with s-buffer).
In fact, I don't really know which way is the best. If someone is experienced with all these methods, help will be welcome :)


That's right...with the s-buffer you don't have to sort your polys (I've never actually heard of c-buffers).

Basicly..if you draw your world first using the s-buffer, then whenever you draw a span you fill in the z-buffer for area of the screen that the span occupies.

Then, after drawing your world you next draw all of the 3d objects/sprites which only use the z-buffer for the z-sorting.


You get the best of both worlds...but it takes up a bit more memory I'm afraid.

#5169 - Torlus - Tue Apr 22, 2003 4:14 pm

Oh :) I understand now :)
It seems to be a good idea, especially if the world has few polys.

For the c-buffer (coverage-buffer), it is roughly the same as s-buffer, but then considering that your spans are processed in a front-to-back order.
Then, when you have 2 spans clipping each other, you're able to "merge" them, resulting in a single span _for intersection tests_ (you still need to keep for each of those previous spans their texture coordinates, etc.)
It makes your span insertion/intersection routine easier to code (and faster).
_________________
GBA,GC,NGPC,GP32,FPGA,DS stuff at http://torlus.com/

#5170 - rusty - Tue Apr 22, 2003 4:34 pm

Torlus wrote:
Oh :) I understand now :)
It seems to be a good idea, especially if the world has few polys.

For the c-buffer (coverage-buffer), it is roughly the same as s-buffer, but then considering that your spans are processed in a front-to-back order.
Then, when you have 2 spans clipping each other, you're able to "merge" them, resulting in a single span _for intersection tests_ (you still need to keep for each of those previous spans their texture coordinates, etc.)
It makes your span insertion/intersection routine easier to code (and faster).


Gotcha. For a c-buffer, you would have to perform an average-z sort on the polys and add them to a list (similar to what we had to do on the Playstation 1) before drawing them. I'm not sure the extra memory and processing requirements would make a c-buffer a good option for the GBA, but I guess there's only one way to find out.

In truth, in a software 3d-engine you really shouldn't be drawing that many large polys for the world (only what you can see) but I guess it really depends on the type of game you want to write.

I've only just gotten into GBA coding, so I'm not exactly aware of the horsepower that the GBA has to offer for this sort of thing. Maybe once I have a little bit more experience....

#8153 - ebille - Thu Jul 03, 2003 7:35 am

i dont know how much i would recommend trying to implement a zbuffer on a gba

no hardware support,and it takes lots of memory. a c-buffer is an option

there is a technique called sorted spans. tell me if you want to know more
_________________
got milk? if so, you are a human and must be killed

#8162 - funkeejeffou - Thu Jul 03, 2003 2:34 pm

I would like to know what are sorted spans?
Also, you seem to be interested in 3d software engines (I also have Abrash's book among others), would you know how to implement a software stencil buffer using a binary tree (I don't wanna keep a screen buffer, just wanna know wich lines are left to draw)?
I'm having some difficulties creating the algorithm, but I definetly want to do a front to back drawing face algorithm.

Thanks

#8169 - DekuTree64 - Thu Jul 03, 2003 5:32 pm

I've coded some simple (and slow) tri fillers using a C-buffer, and it seems to work well. The sorting is what I'm worried about though. You can use a precomputed reciprocal to do the div by 3, but it's still a lot of centers to compute and sort before you can start drawing. For characters though, as long as each piece is convex (no polygons that could possibly overlap), then all you have to do is sort the mesh list. Might get a few artifacts sometimes, but I'll see how it goes.

And actually with a C-buffer, you don't have to store texture coords or anything, just starting/ending values for the spans. You just check against spans, draw the strip to the screen, and then add/merge it into the buffer before going down to the next line. If done right, it doesn't take anywhere near the memory of an S-buffer.

The way I do it is just a linked list of bit-packed values. You take an area of memory (I use 16K), and each entry is a word set up like bit0-11 is the index into the memory area, divided by 4, so you can reach all 4096 words of the 16K block, then bit12-21 is the starting x value, so you shift left 10, and then ASR 22 to sign extend it, and bit22-31 is the end value, so ASR 22 to load it. Then you check if spanStart is greater than cBufEnd, and if so, go to the next C-buffer entry and repeat.

For inserting new spans in to the C-buffer, you keep entry 0 in the block as the head of the linked list of free blocks. So to get a new span, you just set the previous span's 'next index' to the index entry 0 points to (0.next), then set 0's next to the entry that it's pointing to's next (that would be 0.next = 0.next.next), and then take that one you set prevSpan.next to, and set it up with the span's start/ending values, and prevSpan's old next index.
The only hitch in the plan is when you have a span that starts before a c-buf entry, and ends past the end of the entry, so you have to deal with the first half, and then take cBufEnd as spanStart, and spanEnd as the end, and keep loop through the whole thing again. So it's not really a problem after all^^

As long as you set it up each frame to have one entry for -512 to 0, and one for 240 to 511 (maximum values for the 10-bit x start/end), then as long as you check if you polygons are fully offscreen before drawing them, and don't have any crazily large ones that have one corner on the screen and one past -512 or 511, then you get x-clipping for free, and also don't have to worry about hitting the end of the C-buffer spans while drawing, cause you'll just merge with the last span.
You can also go through filling span.xEnd through nextSpan.xStart with a background color after everything is drawn, that way you get 0% overdraw, not even for screen clearing.
And resetting the buffer for the next frame is easy too. Just loop through each of the 160 lines, keeping the first entry (since 0 is used for the free list, the start of each line's linked list will always be 1 + line (you initially set up the buffer that way, and link all the rest of the 4096 into the free list)), so the first entry for the line will be set back to -512-0, and link each entry of that line back into the free list, until you hit one with next index 0, which is just the flag I use to indicate the last one of the line (not anything to do with the free list), and set it back to 240-511 (don't forget to set lineStart.next to this one!). And since spans are getting merged together all the time, there probably won't be that many left at the end of the frame.

It takes a while to explain, but it's really not that hard to implement. Just work out each of the cases of how lines will intersect the buffer spans on paper before you start, and what tests you'll need to do for each of those cases. That saved me a world of confusion for writing the actual tri fillers.

EDIT: More coolness I forgot to mention. You can set up the C-buffer by hand to have pre-covered areas, which I think is what a stencil buffer does, by rendering stuff, loading a new C-buffer, rendering more stuff, etc. You can also do screen transitions. like iris out, horizontal bars coming from the sides, and pretty much anything else you can do with the window regs in tiled modes. Don't forget to clear any pre-covered areas to black though. Actually if you're just filling it in with black, you might as well still use the window regs anyway, unless you want to do vertical strips or something.
Copying in 16K at a time might be a little slow though, but since most of the time you won't have more than a few spans per line of screen, you could easily get away with more like 4 or 8K of total C-buffer data. 8K would give you 2048 entries, so an average of 12.8 spans per line of screen (though it's just one big pool, so one line could have 100 spans, as long as all of them total to less than 2048), so of course 4K would give you 6.4 spans/line. Depends on how many triangles you'll be drawing, and how scattered around they'll be, cause if they touch, the spans merge so you don't use any extras, so it's just in the middle of drawing while there's still lots of empty space that a lot of spans would be used.
The actual drawing code won't change for the pool size, just the number of spans you link into the free list in the initialization.

#8195 - ebille - Fri Jul 04, 2003 6:03 am

im sorry by stencil buffer do you mean you want to implement a beam tree 2d bsp for vsd. like sort everything front to back, draw. put in the beam tree. then stop when the tree is solid?

or do you mean a stencil buffer like it is typically used, like for shadows and stuff

implementing a beam tree is probably not a good idea. you can get the same info from the bsp representing the scene. if its a 2d scene(for raycasting) you can actually get perfect visibility. ill check into that for you

by the way sorted spans is in Abrash's book. ill put some info on it anyway

sorted spans end up with no overdraw

it requires all the drawing of the tris (or whatever) to happen at the end of a scene. each tri is turned into horizontal span lengths. then you sort them into what horizontal scanline there in. you need to fin enough spans to cover the scanline and no more. then you just scan texture info from those triangles the spans belong to. so no overdraw, and each texture is accessed a minimal amount of time. this may seem like a lot of work, but in complicated scenes it speeds things up. so it keeps fps at a stable rate
_________________
got milk? if so, you are a human and must be killed