GP2X Software S-buffering

[Adventus]

I've been in the slow process of writting a simple non-perspective scanline renderer, and i stumbled upon the idea of S-buffering as opposed to Z-buffering. Heres an article giving a brief overview: S-buffer

The advantages of an optimised S-buffer over Z-buffers include:

• Zero Overdraw: Very advantageous when bandwidth is an issue (ie using the 940T) or complex per-pixel operations are desired (lighting, etc).
• Scanline Based: Based on the linear nature of scanlines, as opposed to individual pixels. Since the majority of scanlines are larger than one pixel (hopefully) the intersection based operations will hopefully be faster overall.
• Deffered Shading: Probably decrease cache misses (at least in the instruction cache) and facilitate some compile-time optimisations.

Once i get my own version working and running sufficently fast, I might try and incorporate it in some of the more extensive 3d engines (gpu940).

Questions:
Has anyone had any experience with S-buffers?
Would they be suitable on the 940T?
Is something similar to this being used in the PowerVR chips?

 

[Trenki]

AFAIK Quake 1 uses s-buffer rendering for the scene and while doing so also writes the depth values which are then going to be used by the z-buffer rendering of the characters.

I believe complex per pixel operations or deffered shading would slow down the rendering too much. Quake 1 runs fairly well, but not too fast either.

Implementing this on the 940 should be doable. One could probably also use both CPUs in parallel for rendering (something I will try to do once the OpenGL 3 specification is out, as I want to create a renderer with a similar interface)

I have already created a quite modular 3d renderer for the gp2x which uses fixed point maths. It supports vertex and pixel shaders written in hardware and it would be quite easy to integrate an s-buffer rasterizer into this library.
It would definitly safe you a lot of work as the vertex transformation and clipping stuff is already implemented perfectly. All you would have to do is create a class SBufferRasterizer derving from the appropriate base classes and then implementig the draw_triangle method. There is a problem with point and line rendering. This must be disabled.

 

[Adventus]

Yea, I'll definitely end up incorporating it into an established engine at some point. Im only writing my own as a learning experience (at the moment), so im not bothering with most the standard 3d math.

Your engine seems pretty nifty and OO but ill need to become more acquainted with the code before i have any idea how to use it. Isn't your's a sesquential pipeline:

• Input singular triangle
• Clip triangle
• Scanline convert
• Raster and Z-buffer

So i would have to modify that to get decent speed:

• Input all triangles
• Clip all
• Scanline convert all and build S-buffer
• Raster S-buffer

QUOTE
FAIK Quake 1 uses s-buffer rendering for the scene and while doing so also writes the depth values which are then going to be used by the z-buffer rendering of the characters.
Its interesting that Quake uses a hybrid approach, i guess S-buffers aren't fast enough when rendering many small triangles. Although, i suspect writing a perpixel Z-buffer all the time would almost halve the speed advantage (Since all your replacing is the Z-buffers per-pixel compare).

QUOTE
I believe complex per pixel operations or deffered shading would slow down the rendering too much. Quake 1 runs fairly well, but not too fast either.
I would be hoping that the decreased overdraw would make at least some per-pixel operations feasible, maybe not dot3 bumpmapping, but most blendmodes.

Woops my bad, By deffered shading i meant deffered texture mapping (not that they're very different....).

PS: If you wanna squeeze some more speed out of your fixed point math library, have a look at this: TFix32 Library

 

[Trenki]

Yea, I'll definitely end up incorporating it into an established engine at some point. Im only writing my own as a learning experience (at the moment), so im not bothering with most the standard 3d math.

Your engine seems pretty nifty and OO but ill need to become more acquainted with the code before i have any idea how to use it. Isn't your's a sesquential pipeline:

• Input singular triangle
• Clip triangle
• Scanline convert
• Raster and Z-buffer

So i would have to modify that to get decent speed:

• Input all triangles
• Clip all
• Scanline convert all and build S-buffer
• Raster S-buffer

No, you would not have to modify anything in the current engine but only add new code. You can already input a bunch of triangles at once. Shared vertices are only transformed once as there is a post transform vertex cache. I don't clip each triangle on its own but accumulate some triangles an do the clipping then. This can be faster because I can detect the case where not all planes need to be checked.

For S-Buffer rendering you would simply have to create a class SBufferRasterizer and derive from the IRasterizer interface. The draw_triangle method is called for each single and would be used to fill the S-Buffer. At some point the S-Buffer would need to be converted to regular pixels. This can be done by implementing another method which does this.

One thing to note about S-Buffer rendering is that you can't have blending and also no alpha test.

I had a look at the TFix32 library you pointed out but from the description I can see that my fixed point math library provides the same functionality. Note that not my whole fixpoint library is included in the rasterizer as I don't need it there.

 

[Adventus]

QUOTE
For S-Buffer rendering you would simply have to create a class SBufferRasterizer and derive from the IRasterizer interface. The draw_triangle method is called for each single and would be used to fill the S-Buffer. At some point the S-Buffer would need to be converted to regular pixels. This can be done by implementing another method which does this.
Ahh ok i understand, the draw_triangle would normally draw something, whereas if i overload it with an S-buffer alternative which doesnt draw anything then write an Sbuffer Render function... i should be set.

QUOTE
I had a look at the TFix32 library you pointed out but from the description I can see that my fixed point math library provides the same functionality. Note that not my whole fixpoint library is included in the rasterizer as I don't need it there.
I havent looked extensively, but does yours allow multiplying Fixed point numbers of differing precisions?

 

[earx]

i implemented coverage buffering (c buffer) which -should- actually be a faster algorithm than s buffer. in s buffer you store all the U,V,W coords for every span. in c buffering you don't but it requires an additional front->back sorting stage.

i benchmarked it and it seemed that only with a fairly big amount of overdraw in the scene that it really pays off. but i guess in most indoor scenes this actually is the case (even after frustum culling has been done).

 

[Adventus]

QUOTE
i implemented coverage buffering (c buffer) which -should- actually be a faster algorithm than s buffer. in s buffer you store all the U,V,W coords for every span. in c buffering you don't but it requires an additional front->back sorting stage.

i benchmarked it and it seemed that only with a fairly big amount of overdraw in the scene that it really pays off. but i guess in most indoor scenes this actually is the case (even after frustum culling has been done).
Once i get S-buffering up and running it shouldn't be too hard to implement C-buffering, although some articles or indepth explanations would be nice.... Yea I guess it does only really apply in dense scenes, although the same could be said of Z-buffering in general.

 

[Trenki]

S-Buffer, C-Buffer. I think we are talking about the same thing here, don't we? From a fast google search I could find out that in the C-Buffer spans on the same scanline can be merged. But how should this be done? I mean one has to store the start and end U,V and other parameters for interpolation purposes, so you can't merge things.

So please, what is the difference between S-Buffer and C-Buffer?

 

[Trenki]

QUOTE
For S-Buffer rendering you would simply have to create a class SBufferRasterizer and derive from the IRasterizer interface. The draw_triangle method is called for each single and would be used to fill the S-Buffer. At some point the S-Buffer would need to be converted to regular pixels. This can be done by implementing another method which does this.
Ahh ok i understand, the draw_triangle would normally draw something, whereas if i overload it with an S-buffer alternative which doesnt draw anything then write an Sbuffer Render function... i should be set.
Yes, in the draw_triangle function you would actually not draw the triangle but insert into the s-buffer and only really draw everything at the end by a different function call. You could take a lot of the source code of the subdividing affine rasterizer, so you would only have to implement the algorithm for inserting spans into the S-buffer.

QUOTE
I had a look at the TFix32 library you pointed out but from the description I can see that my fixed point math library provides the same functionality. Note that not my whole fixpoint library is included in the rasterizer as I don't need it there.
I havent looked extensively, but does yours allow multiplying Fixed point numbers of differing precisions?
No, multiplication of fixed point numbers with different precisions is not possible. I doubt that is a good idea and you can't have infix notation for this as you have to specify the precision of the result somehow.

 

[Adventus]

QUOTE
No, multiplication of fixed point numbers with different precisions is not possible. I doubt that is a good idea and you can't have infix notation for this as you have to specify the precision of the result somehow.
Hmmm, The TFix32 library seems to think you can, but, as you say, the operator* only works with same precision numbers. Differing precisions are handled like this:

TFix32<8> r;
r.MUL( TFix32<6>(2000.1) , TFix32<16>(2000.1) );

I found it to be pretty nifty.

 

[PokeParadox]

I just want to go slightly offtopic and say thanks for making me aware of those fixed point classes/libs. I was writing my own and got to a point where something was wrong and couldn't figure out what, so this saves me the hassle.

I've decided to use Trenki's FixedPoint class since I figured it's better to stay within community resources where posssible

 

[Trenki]

I've decided to use Trenki's FixedPoint class since I figured it's better to stay within community resources where posssible

Good to hear that You might also want to know that my fixed point library and vector_math library work very well together. When you use vectors or matrices of fixed point numbers the multiply accumulate operations (used in dot products, matrix multiplication etc.) will be optimized automatically and this gives a huge speed win compared to doing it the naive way.

@Adventus: If you are going to implement your s-buffering based on my rasterizer I would like to stay in touch. You can contact me via ICQ (number is in my profile).

 

[earx]

--

a typical span buffer rasteriser would work in two stages:

( 0) reset span buffer)
1) span conversion: this writes spans with interpolated X,U,V,.. coordinates to the span buffer. the span buffer is a data structure of linked lists for every scan line. nodes can be inserted, deleted (when they are totally occluded), or modified ("clipped": when partially occluded).
2) span buffer rasterisation: the easy part. just render all spans in the buffer.

--

a coverage buffer rasteriser has basically just one big stage:

( 0) reset coverage buffer)
1) masked span conversion: each span is directly checked and possibly clipped against the coverage information

the reason why front-to-back sorting is now required is because the coverage nodes do not contain any Z (depth) information. everything in the c-buffer -must- be closer to the cam than what is still to be drawn.

a coverage buffer can be implemented like a mask. in fact, if you want you can use a single bit per pixel. or you can use a simplified version of the s-buffer data structure:

(x0,x1)->(x0,x1) (c buffer)

instead of:

(x0,z0,u0,v0,..,x1,z1,u1,v1,..)->(x0,z0,u0,v0,..,x1,z1,u1,v1,..) (s buffer)

in this case you can merge spans, and this is actually quite easy. not harder than modifying a node, for sure.

 

[Adventus]

QUOTE
@Adventus: If you are going to implement your s-buffering based on my rasterizer I would like to stay in touch. You can contact me via ICQ (number is in my profile).
Will do, but dont expect anything soon....

QUOTE
the reason why front-to-back sorting is now required is because the coverage nodes do not contain any Z (depth) information. everything in the c-buffer -must- be closer to the cam than what is still to be drawn.
This may be a rather stupid question.... but how can you sort from front to back when each span has an end and start z position? Or do you split intersecting spans....

So the C-buffer masks out the positions that have already been rendered to, and guarantees that no pixel is closer at these positions by back to front sorting.

Correct me if im wrong but this is what it sounds like to me:
- Split all spans which intersect each other to insure each span is either completely infront or behind the other spans,
- Sort resulting spans back to front, and
- Render spans using a C-buffer (or 1 bit per-pixel mask).

My main problem is the first step. Wouldn't it be as slow as an S-buffer? or can you avoid this step altogether?

 

[mithris]

Hi,

I implemented a s-buffer on the GP32 a few years ago, mostly to get some
experience from it and to find out where the bottlenecks are.

My conclusion was pretty much that it's really good for polys covering large
areas, but when it comes to many small polys the span insertion takes too much
time and z-buffer or even painters would be more efficient. Actually, painters
is often pretty efficient but it comes with so many other problems it's rarely
worth it.

But using s-buffers as iirc they were used in Q1 is probably a very good idea,
render the level geometry (which usually is made up from large tris covering all
of the screen) and then use a very quick and perhaps dirty filler for the smaller
objects using the z-buffer built from the s-buffer pass.

--
m

 

[earx]

QUOTE

This may be a rather stupid question.... but how can you sort from front to back when each span has an end and start z position? Or do you split intersecting spans....



you actually have to sort the polys, not the spans. so, just like with painters, but front->back instead of back->front. sorry for not being clear on this point.

i agree with mithris that painter's comes with problems. when doing complex objects like cars, ppl, etc there is often a vast difference in polygon size. in painters algorithm, to overcome artifacts, all the bigger polys need to be split up.. which is hell for the 3d artist (or for the coder who needs to change the models..)

i did not test my c-buffer on any modern platform. it was done on an oldschool atari in 320x200. and i used random polygons all over the place, not a real scene. c-buffer probably can handle loads of small polys quickly, because it merges spans. on the other hand you may end up with painter's issues, i.e. sorting errors, but i didn't check this.

the large (s-buffer) vs small (z-buffer) poly thing seems very sensible btw =)

 

[Adventus]

QUOTE
you actually have to sort the polys, not the spans. so, just like with painters, but front->back instead of back->front. sorry for not being clear on this point.
Ahh ok, i guess that would be much more efficient.... but yea, you'll get the same problems as you get with the painters algorithm.

I did a bit of googling and came up with the following links:
- C-Buffers: http://www.bik5.com/articles/tutorials//tut_cbuffer.htm
- S-Buffers: http://tfpsly.free.fr/Docs/TomHammersley/sbuffer.htm
- S-Buffers: http://www.wadeb.com/cgdc98.doc
- Interesting Quake Engine Details: http://www.bluesnews.com/abrash/

I would consider using a tree based S-buffer approach to aid in early rejection. So you merge overlapping spans into a single parent span which describes the min X,max X and maximum Z of the child spans. You could then use an simple AABB check to first test spans against the parent. Ie:

if (Span.Z>Parent.MaxZ && Span.x0>Parent.MinX && Span.x1<Parent.MaxX){reject(s);}

Some more optimisations could be applied using this approach. Unfortunately, All these algorithms really depend on the scene complexity.

 

[d4rkm4r3]

Better then S-Buffers are "Free Span Buffers" (FSB)

http://www.gripho.it/sbuffer.en.html
(The Clipping Code in his Sample works only with Images, but its easy to modify)

stores only the free spans per scanline -> less calculation then S-Buffers.
FSP can reduce 2d clipping.

My 2D Span Clipping (in screen space) Code Sample (Leftside, X = 0)
No Division, only shifting
CODE

clipping_counter = 8;//!!!16
while(clipping_counter--)
{
tempPoly.v[j].x = (a.x + b.x)>>1;
tempPoly.v[j].y = (a.y + b.y)>>1;
tempPoly.v[j].z = (a.z + b.z)>>1;

tempPoly.v[j].tu = (a.tu + b.tu)>>1;
tempPoly.v[j].tv = (a.tv + b.tv)>>1;

tempPoly.v[j].lu = (a.lu + b.lu)>>1;
tempPoly.v[j].lv = (a.lv + b.lv)>>1;

tempPoly.v[j].l = (a.l + b.l)>>1;

if(tempPoly.v[j].x == 0)
{
break;
}
else if(tempPoly.v[j].x < 0)
{
a = tempPoly.v[j];
}
else
{
b = tempPoly.v[j];
}
}