|
The Art of Demomaking - Issue 12 - Span Based Rendering by (08 November 1999) |
Return to The Archives |
Introduction
 |
| As promised, we're going to do a bit more 3D this week. Before we move onto full polygons next week, I'll take a bit of time to explain the basics behind horizontal spans. You will also learn about the most important part of software rendering, i.e. preventing overdraw. And finally, I will guide you through the design of this week's effect, just to illustrate how to make those critical decisions that lead to extra speed in the main loop. |
|
Span Based Rendering
|
A span is basically a line of pixels, usually horizontal. Most primitive shapes like polygons or ellipses can be drawn as spans. All the pixels inside a span are written sequentially to the video memory, so we benefit from optimal cache performance. The simplest kind of span you can draw has only one colour, so no interpolation is needed. You could quite simply interpolate the colour components from one end of the span to the other: that's gouraud shading. Another approach is to apply a texture onto these spans, so you need to interpolate both your coordinates in the texture map. The nicer you want your spans to look, the more computation you require. That's the reason why most software rasterisers usually limit themselves to two mixed textures. The first texture being a static texture, and the second being some environment map. The coordinates for the static texture are always the same regardless of the view point. The texture coordinates for the environment map are computed given the normal vectors at each end of the span. The way we determine the coordinates in the environment is very similar to that I explained in the bump mapping tutorial.  So for each pixel you must load both texels in question, and mix them together with a look-up table or an equivalent method. |
|
Preventing Overdraw
|
Software rasterisers being extremely expensive computationally, all unnecessary overdraw must be avoided. Using spans enables us to use some nifty techniques to prevent overdraw. There are two main methods. Firstly we can use the famous z-buffer, even though this is slightly more expensive in software due to cache thrashing, it is extremely simple to implement, and always produces the desired results. This shows a top down view of one row of pixels. When we come to drawing the span, we check the depth value with the corresponding one in the z-buffer. If our span is in front, we draw it. The second method is ideal for software rendering, since it reduces the memory usage. It's called an occlusion buffer. Basically for each row of pixels we store the coordinates of the spans we have previously rendered. Then when it comes to rendering another span, we clip that against the previously rendered spans, and only draw the visible parts. Once drawn, we update the occlusion buffer by merging all possible spans together, so that our list of occlusion spans remains the smallest possible.  The only draw back of this method is that you need to sort your spans by depth before rendering them. |
|
Design And Optimisation
|
The whole process of coding effects is about managing to find the balance between what you imagined and what the PC can do. So you end up compromising quality so that your machine can actually render the effect at reasonable speed. Personally I do things in this order:
It takes quite a bit of fine tuning to get a perfect effect running... don't think that most demomakers can code the perfect effect in one go ;) For example recoding this effect which I had already written in pascal a while back took me about 3 hours and a half. To give you an idea of how to simplify design to get more speed out of your algorithms, I'll guide you through the numerous steps it took for this effect. I remember being impressed by this effect when I first saw it. Basically it's a vertical tube, with a weird shape, that wobbles all over the place constantly changing size. This needed to be rendered in 3D, so my first approach was to have a big array of vertices, which I would arbitrarily rotate and translate. This would be the skeleton for the texture which would be applied onto it via polygons. I didn't need to code any of that to realise the problems: firstly some vertices may not be visible, so it would be a waste to actually bother with them; secondly drawing that many polygons would be quite expensive. So I thought of using a model based on slices. Each horizontal line on the screen would correspond to a slice of the tube. The advantage here is that we are sure that everything is visible, and we can draw spans instead of polies. The only drawback is that we don't perform our 3D projection correctly: we assume the vertices of each slice project onto the same row of pixels. This is good enough and the advantages outnumber the drawbacks, so we stick with that idea. Now we can simplify the code a lot more. For each slice, we have say 32 vertices and hence 32 spans. For each of those, all we need is the x and z coordinates, since we don't bother with using the Y projection. We've just saved 4 bytes for each vertex by not using last week's VECTOR class! Likewise, when rotating the vertices, we only rotate the necessary data, so we don't use the MATRIX class either. Once rotated, we can also get away with not projecting the vertex in the normal way. Instead we use orthonormal projection, which avoids one division per vertex. This is much quicker, but all movement along the Z axis won't come across as well. I also noticed that we only need the x component of the normal at each point to calculate the coordinates in the lightmap, so that saves us another rotation... I think you get the point now. It's like that all the way through the coding process: "We don't really need this! *snip snip* That doesn't really matter! *hack hack*". So our code ends up like this:
Note that I use a z-buffer in the example for simplicity. It's not really a good idea here, but I still get 70 FPS on my PII so I'm satisfied. The ideal way would involve an occlusion buffer similar to those used in voxel landscapes. The spans don't even need to be sorted since you can send them to the rendering pipeline in the right order just by knowing the rotation angle. |
|
More Implementation Ideas
|
There are so many cool features you could implement for this effect. I didn't since I wanted to keep things simple and I ran short on time ;)
I'll leave that to those of you that are interested. |
|
Final words
|
|
Well, it's 4 AM already... this tutorial took me quite a while, but nothing beats this feeling of satisfaction :) Spans are great! They make things so easy. It's almost like they could do anything. Just make sure to avoid overdraw! After having read that third paragraph, you may be extremely confused about how to optimise an effect. You will find your own technique given enough practice, so you'd better get to it :) You can download this week's demo and source code package right here (131k) Enjoy, Alex |