Topic : S-Buffer FAQ
Author : Paul Nettle
Page : 1 Next >>
Go to page :


S-Buffer FAQ

This was originally posted in rec.games.programmer by Paul Nettle.

I've taken the liberty to modify the 'vitals' area simply because I've moved, and no longer wish my address or phone number to be public (marriage has the tendency to do such things :)

Aside from that, this is the original, unmodified FAQ. There have been no updates and there probably won't be any (I'm using S-Buffers for a project with which I'm contracted under NDA.)


A note from the author:

This may be a bit wordy at times, so I'll try to keep it light with some of my humor -- you may not call it humor, but at least *I* think it's funny. :)

Where did they come from? s-Buffers were developed for my game engine. Though, since I don't believe that FAQs should have anything to do with commercialization, I won't even mention the name of this product. Let's keep FAQs for their purpose -- FACTS.

The technique described in the next few hundred lines of text bears a close resemblance to some scanline rendering methods of which I believe span-buffering is one of them.

Actually, I had no idea what span-buffering was until I spoke to a gentleman named Chris Babcock who read the original posts about s-buffering. He explained to me what span-buffering was, and as it turns out, the two techniques are similar, but do have some major differences (mainly the Insertion routine and segment manager).

The major difference is that s-Buffers are more so meant for use in game engines. Engines that are meant to produce a high frame rate.

When I posted a note to the rec.games.programmer newsgroup about the fact that I had discovered a technique that would perform z-Buffers in software faster than hardware could, the response was, quite literally, overwhelming. Most of which was plagued with polite suspicion and skepticism. This alone told me that, at least, in the gaming community, this technique was unfamiliar territory. So, I propose to you, the game developer, a new technique, called s-Buffering.

The particular implementation of this technique and it's name are both my own original creation, sparked by my own, sometimes wry thoughts. This FAQ and the techniques contained within are also all my own creation. This isn't to say that there isn't somebody else out there that has once thought about these techniques or variations thereof. I have no control over their thoughts (and wouldn't want to -- Ewwwwww!). I am quite confident, however, that this technique is not popular, not documented, and not in wide use within games.

If you find the information contained within these words, diagrams, and psudo-codes useful to any degree, please contact me. If you use this technique in a product (commercial or otherwise) that you would not have done so if it had not been for this FAQ, please just drop me a line and let me know. It's nice to hear those things. Hearing good things about efforts like this can only spark more.

I would also encourage anybody and everybody to dig in. Play with this new technique. It's not perfect, and the "Insertion" routine can be it's own line of discussion -- inventing many new algorithms for insertion can very possibly improve the performance of this technique in quantum leaps. I would expect that if this technique gains any popularity, you'll see new insertion algorithms popping up in the next Siggraph Proceedings.

I'll be the caretaker of this document. Please make all corrections through me by contribution (internet e-mail preferred).

If you do have other useful information related to this FAQ, !PLEASE! contact me. I may very well want to include it in future versions of this FAQ. Lets keep the InfoBahn alive, let's contribute to it, and share ideas. We've got a hell of a lot of brains out there to draw from.

Striving for speeeeed,

Paul Nettle
Hot Wax Software

"And now for something completely different. A man with six-hundred
thirty-two-thousand four-hundred and forty-two big toes."

Q: "How do I contact Paul?"

My vitals are:

[This section removed due to a change of address]
NET: midnight@grafix3d.dyn.ml.org

Please, the name's "Paul", not "Mr. Nettle" :) I hear "Mr. Nettle", and I turn around looking for an older man.

Q: "OK, so what the heck is this all about?!!"

The movie "Weekend at Bernies" quotes this line:

"He's got good form!"
I think that's one of my favorite quotes because, to me, it has a serious side other than it's humorous description of a corpse being dragged behind a moving boat by a rope, braining itself on buoys along the way.

"Good form" is "Elegance."

Webster defines "Elegant" as:

"Marked by concision, incisiveness, and ingenuity; cleverly apt and simple"
I couldn't have said it better, Noah. Since elegance is a goal and not a destination, it's something that's to be strived for. You can't reach pure elegance since there is always *something* that's more elegant (the human body, for example).

I hope you find s-Buffers to be "simply brilliant." Not that I'm the brilliant one, mind you, I only discovered the technique. The technique then just started to jump up and down, wave it's arms, blare sirens, and was later found to be screaming out it's advantages at me. I'm just writing them down.

So, back to the question. What's this all about? Elegance, Simplicity and, of course, Speeeeeeeeeeeeeeeeeeeeeeed!

Q: "Why s-Buffers?"

First, consider z-Buffers. If you're not sure EXACTLY how they work, I'll explain briefly:

A z-Buffer is a `second copy' of the screen-image. It usually has the same resolution. This z-Buffer is initialized to the largest possible value held by an UNSIGNED INT (for 16-bit INTs, that's 0xFFFF, and for 32-bit INTs that's 0xFFFFFFFF).
During the drawing of polygons, the depth-value for each pixel written has to be kept track of. As you draw each pixel in a polygon, you compare the depth-value of that pixel with the value in the z-Buffer's corresponding pixel location. If the z-Buffer value is larger (farther away from the camera), then the pixel is plotted, and the z-Buffer is updated with the new pixel's depth. If the z-Buffer value is lower (closer to the camera), then the pixel is not drawn since it is hidden behind the existing pixel.

This is a very simple approach, and, depending on implementation, can offer pixel-perfect output. However it is very slow and cumbersome.

Your code's inner-most loop (the code that's doing the drawing of the pixels) -- the same code you've hand-assembled for speed is being used to waste clock cycles as if they're as rich a commodity as Madonna CDs. Even if that mean-ol-nasty z-Buffer says the pixel is hidden, you still need to track your deltas. You still have to keep moving through your shades, texture maps, bump maps, colors, etc.

So, you've had to add depth-tracking as well as a slow check to another buffer (possibly outside of your CPU's cache), and a conditional update to that buffer. Whew...what a waste. Such a waste in fact, that I plan to tell you how s-Buffers are not only FAST, but FASTER than z-Buffering in HARDWARE. Keep reading, it's all in here.

Is there a more elegant solution? I believe I have found one. I call it, simply, "s-Buffering."

Q: "What are s-Buffers?"

`S-Buffers' or `segmented-Buffers' are the segmented representation of a z-Buffer. They have three key elements:

An array of linked-lists (for this example)
An insertion routine for inserting segments into the s-buffer
A segment manager
These key Elements are outlined in the next few questions. To continue with the answer to this question, you'll need to read the next three Qs.

Q: "What is...KEY ELEMENT #1: The s-Buffer itself"

For the sake of simplicity, I'll just use a linked list, later, this can be expanded upon. It's the concept I'm trying to get across here.

Let's consider our trusty friend, the z-Buffer. Pull out a single scanline from the z-Buffer and set it's representation on the kitchen table (watch out, don't set it in the little puddle of spaghetti sauce).

You now have a single plane. Across the front is the x-direction through a scanline. As you run your finger from the front to the back you're moving it along the depth axis (z-axis). Now go wipe that spaghetti off your finger.


                                    Kitchen-table representation
  x     z-Buffer                (Dots represent the depth of a pixel)
+-------------------+                 _______________________
y|-------------------|                /   (far away)         / n
|-------------------|    

Page : 1 Next >>