# [Help] Software Rasterizer - Rasterizing Triangles

This topic is 2612 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## 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,
Bombshell

##### 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 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 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
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.
does this sound good?

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 -.-

Thanks for the help,
Bombshell

try this

##### 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.
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 on other sites

[color="#1C2837"]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 -.-

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 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):
__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++; } } }}
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?

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 on other sites
did you check the file i posted?

##### 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.

1. 1
2. 2
3. 3
Rutin
15
4. 4
5. 5

• 10
• 9
• 9
• 11
• 11
• ### Forum Statistics

• Total Topics
633688
• Total Posts
3013328
×