Sign in to follow this  
Bombshell93

[Help] Software Rasterizer - Rasterizing Triangles

Recommended Posts

BIGEDIT (change of question):
I've set the base of my engine up in C++ in hope I can squeeze all I need out of this engine.

Can someone present the most powerful triangle rasterization techniques and explain their strengths and weaknesses?
minor accuracy issues are no problems and all it will be doing is filling 2 buffers, a mesh-index and a depth buffer. for determining visibility of objects for occlusion culling.

any and all help appreciated,
Thanks in advanced,
Bombshell

Share this post


Link to post
Share on other sites
I have spent a lot of time trying to figure out how to rasterize a triangle and I have come to a solution.
First, order your vertices vertically from the uppermost to the downmost.
Then you can divide your triangle in two sub-triangles(the mid vertex marks the division line between the two triangles). Check if the triangle has an effective height, so that you have at least one sub-triangle. If you haven't any sub-triangles you can skip the rest, of the rasterization(as the triangle is not a triangle, but a line).
Then you could rasterize each sub-triangle, or the only one you have. So, find the edges of the subtriangle, and then use linear interpolation to find the start-x and end-x coordinates to draw each horizontal span from the first edge to the second. Then switch to the second sub-triangle e do the same(you can consider starting from the bottom to initialize the first start-x and end-x of the span to the x of the bottom vertex).
I hope I was clear,
Marco

Share this post


Link to post
Share on other sites
I've set the base of my engine up in C++ in hope I can squeeze all I need out of this engine.

Can someone present the most powerful triangle rasterization techniques and explain their strengths and weaknesses?
minor accuracy issues are no problems and all it will be doing is filling 2 buffers, a mesh-index and a depth buffer. for determining visibility of objects for occlusion culling.

Share this post


Link to post
Share on other sites
I'm a bit confused on why your splitting the triangle into 2. But I think I have a take on your technique.

EDIT: pseudo fix and another fix
[code]I find max.Y Vertice, mid.Y vertic, min.Y vertice. Find each edges per y, x increment. (for each y increment x by ___)
E1 = min to max increment; E2 = min to mid increment; E3 = mid to max increment;

if E3 > E1 then E1 is the start of the x span
start = max.X
end = max.X
for int y = min.Y; y < max.Y; y++
start += E1
end += E2
<span class="Apple-tab-span" style="white-space:pre"> </span>if y == mid.Y
E2 = E3
for int x = start; x < end; x++
interpolate depth values and draw pixel.

else E1 is the end of the x span.
start = min.X
end = min.X
for int y = 0; y < max.Y - min.Y; y++<div><span class="Apple-tab-span" style="white-space:pre"> </span>start += E2
end += E1
if y == mid.Y
E2 = E3
for int x = start; x < end; x++
interpolate depth values and draw pixel.[/code]
does this sound good?

[b]BIGGER EDIT: I can't seem to make fixxes to my post because the forums are acting broken, it keeps adding in unnecessary HTML messing up the post and making it hard to read, skip anything in <> or </> brackets -.-[/b]

Thanks for the help,
Bombshell

Share this post


Link to post
Share on other sites
[quote name='bombshell93' timestamp='1318763033' post='4873093']
I'm a bit confused on why your splitting the triangle into 2. But I think I have a take on your technique.
[/quote]it was usually done to simplify the whole algorithm. you just have one starting point and two lines you interpolate, a start and end height. it's really quite simple, you dont have somewhere in the loop a check if one of the lines ends and it need to be replaced by the 3rd line (gradients).

some people even reuse the same code and interpolate the 2nd sub-triangle bottom up, that way you have the code in your L1 cache and you dont have to maintain the same code twice. performance wise it's the same.


Share this post


Link to post
Share on other sites
[quote name='bombshell93' timestamp='1318763033' post='4873093']
[color="#1C2837"][size="2"]BIGGER EDIT: I can't seem to make fixxes to my post because the forums are acting broken, it keeps adding in unnecessary HTML messing up the post and making it hard to read, skip anything in <> or </> brackets -.-[/size][/color]
[/quote]

if you copy it into notepad first, then into the forum, it won't have any formatting - you can then just put [source][/source] around it and it'll become all magical and reveal the secrets of the universe and stuff :)

I remember writing code to software-rasterise triangles many many moons ago and yeah, splitting it in two does sound rather familiar. Quite a few graphics programming books had code for it - and a few even had code examples of that holy grail of perspective corrected textured triangles. Ah, games like Frontier Elite, with their wonderful shearing-and-non-perspective-corrected textures ;)

For a software engine, a rummage around at a used bookstore might turn up some useful information.

Share this post


Link to post
Share on other sites
I've been looking at more methods that make use of SIMD and some which seem to go overboard with code (I guess I won't know the difference until I benchmark them, so I'll probably test a few things)
Here is the code I have at the moment. (note its for an occlusion culling engine so the index is to let me know what objects are visible):
[code]__declspec(dllexport) void Push::Graphics::RasterizerClass::Triangle(D3DXVECTOR3* a, D3DXVECTOR3* b, D3DXVECTOR3* c, short* index)
{
float E1, E2, E3;
D3DXVECTOR3 *max, *mid, *min;

if (a->y > b->y && a->y > c->y)
{
max = a;
if (b->y > c->y) { mid = b; min = c; }
else { mid = c; min = b; }
}
else if (b->y > c->y)
{
max = b;
if (a->y > c->y) { mid = a; min = c; }
else { mid = c; min = a; }
}
else
{
max = c;
if (a->y > b->y) { mid = a; min = b; }
else { mid = b; min = a; }
}

E1 = (min->x - max->x) / (min->y - max->y);
E2 = (min->x - mid->x) / (min->y - mid->y);
E3 = (mid->x - max->x) / (mid->y - max->y);

if (E3 > E1)
{
int start = min->x;
int end = min->x;
float depth;
long loc;
for (int Y = min->y; Y < max->y; Y++)
{
start += E1;
end += E2;

if (Y == mid->y) { E2 = E3; }

loc = (Width * Y) + start;
for (int X = start; X < end; X++)
{
depth = (1000.0f);
if (DepthBuffer[loc] > depth)
{
DepthBuffer[loc] = depth;
ObjectBuffer[loc] = *index;
}
loc++;
}
}
}}[/code]
QUICKEDIT: I have not put the else in to draw the triangle when E3 < 1 yet, it completely slipped my mind.
I made most of this up as I went along, I re-wrote it several times trying to simplify it. I'm just setting up the function to sort and pass in the vertices now so I can test it.
The main problem I have at the moment though is interpolating data. UV's, Colour or in this case Depth, is fastest done by taking the vertex values and gradiating it over the surface. But every time I look it up I get a text wall of 3 unknown products, which I understand to a degree and relates to what my original concept of 3 point interpolation was but my main concern is how its calculated.
any sample I have come across has had massive amounts of calculations per pixel, which I just can't see as being efficient. Sadly none of my ideas are weighing much stronger either,
Could anyone help me on this?

Thanks in advanced,
Bombshell

P.S. on the subject of getting a graphics programming book, does anyone have any suggestions for books covering a wide spectrum?
I expect in the next few weeks to be looking into everything from particle based mesh generation and sparse voxel octree's to water physics and post processed anti-aliasing.

Share this post


Link to post
Share on other sites
It can be helpful to think more in spans and edge-pairs then triangles when you want to write an efficent sw rasterizer.

Basicly, you can keep an edge-list sorted on y,x and step through it, generate spans, and clip them, and draw the whole triangle blob in one pass without overdraw and only fill once per pixel.
You can feed a triangle soup to the edge-list and it will take care of it efficiently.
You don't even need a depth buffer.

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this