Author : Paul Nettle
Page : << Previous 2 Next >>
/ / o
|-------------------| / .. / i
|-------------------| / . . / t
|---------------------\ / ... .. . / c
|-------------------| | / . .. / e
|-------------------| | /.. . / r
|-------------------| | / / i
|-------------------| | / . ..../ d
|-------------------| | / (close) . / /
+-------------------+ \--->/______________________/ Z
(front -- x-direction)
When you look at the entire z-buffer, you're looking at a stack of these planes (that's not true at all, but I want you to think of it that way for now). So, lets just consider the kitchen-table representation.
For each scanline in the z-Buffer, what you have is a list of depth values for each pixel. Even though you may only have a single polygon on the screen, and the depth values in the z-Buffer that the polygon occupies are all the same (it's orientation is perpendicular to the z-axis), you still have to check each pixel, right? Not any more.
From now on, I don't want you to think in terms of pixels. I want you to think in terms of the segments that make up that polygon. In our case, we'll stick with horizontal segments (though orientation isn't important).
When you scan convert a polygon, you break it up into horizontal SEGMENTS:
/\
/--\
/----\
/------\
/--------\
/----------\
------------\
--------\
----\
This is the key to s-Buffers. Now you have a list of segments. Rather that calling any low-level drawing routines to draw these segments, just simply call the s-buffer "insertion" routine.
No, this isn't going to be easy. The "insertion" routine can be a beast all by itself. But, there is a simple 'starter' algorithm that I've included here.
When you're all done scan-converting your polygons and adding your segments to the s-Buffer, what do you have?
You have the ENTIRE screen in a well-formatted, nicely laid out fashion. All the data is in one place, too. The screen is laid out top-to-bottom and each scanline is left-to-right. Can you think of any possible optimizations to take advantage of here? I sure can.
Now it's time to call your 'modified' low-level drawing routine. But first, a glance in the past. In a lot of applications, the low-level drawing routine might look something like this:
void LowLevelDrawer( int x1, int x2, int y, int shade1, int shade1, int Color)
{
[lots of setup code, clipping, etc.]
.
.
.
[draw the scanline]
.
.
.
[any exit code]
.
.
.
[return]
}
This is for a single horizontal line of a polygon. This routine will be getting called for each of the scanlines in a polygon, for every polygon. Hmmm...I wonder how many times that startup code is gunna get run through...
See all them parameters (I count 6)? That's just for a single piece of a single polygon for a simple gouraud shader. What about a bump-mapper and texture-mapper? Your stack will hate you for that, you're driving it nuts! Push, Pop, Push, Pop, Push, Pop....
Here's a peek at your NEW and IMPROVED s-Buffer drawing routine. It draws the ENTIRE screen:
void LowLevelDrawer( SBUFFER *Sbuf )
{
while( !Done )
{
[do a little setup for this scanline]
.
.
.
[draw all segments for a single scanline (optimized code goes here)]
.
.
.
[next scanline]
}
[any exit code]
.
.
.
[return]
}
When you leave here, you have a new screen, drawn to completion, ready for display.
One thing to note is that as you're drawing, if you watch it in slow-motion, you'll see that you're drawing each scanline from left-to-right, top-down. Nice and clean. I'll address this cool feature later...
Q: "What is...KEY ELEMENT #2: The insertion routine"
Due to the nature of it's possible complexity, the Insertion routine is the most important key element of the s-Buffer algorithm. As such, it's also the most confusing routine to write.
Like some compression routines, any version of the de-compression routine can de-compress the data stored in compressed form. However, each version of the compressing code is different. Better compression can be obtained by better analysis. The format of the output is still the same, but substantial gains can be made by better analysis in the compressing code. I believe that the Insertion routine can also have this trait. A better analysis on the part of the Insertion routine can simplify the job of the low-level drawing routines.
My point is that there is ALWAYS room for improvements to be made to any insertion routine. The closer to perfect elegance, the better.
Take my rudimentary psudo-code for example. The code relies on splitting segments that may not need splitting simply to keep the algorithm simple for explanation's sake. It does the job, but it is wasteful.
Granted, the segments won't overlap (that would defeat the purpose of s-Buffering all together). But on many occasions, a segment may be split into two segments side-by-side, causing the low-level drawing routines more effort, and wasting memory by using up more segments than are necessary. And ultimately more time is spent in the drawing phase.
Please note that the following code may not be satisfactory for real use, but will certainly improve the performance of your application regardless.
You'll need these defined before we can start...
Cur = Start of the existing segment list
New = Segment to be added to the list
First, the possible cases used in the psudo-code. In the following cases, I use characters to represent pixels of the New segment being added (`n') and the current segment in the list being compared against (`c'). So in the following example:
cccccccc
nnnnn
The Cur's right-half is overlapping with the entire New segment, and an intersection must be tested for. These examples only represent where the start x coordinates and ending X coordinates fall, they in no way represent the depth values.
Possible cases:
Case 1:
-> cccccc
-> nnnnnn
Case 2:
-> cccccccc
-> nnnnnnnn
Case 3a:
-> ccccccccc
-> nnnnnnnnn
Case 3b:
-> cccccccccc
-> nnnnnnnnnn
Page : << Previous 2 Next >>