rendering a triangle in software

just an old code snippet i found on one of my code backup cds. i removed the clipping parts from the code since they don't really belong to the snippet title

void SoftRasta::renderTriangleSolid16(RenderTriangle &t, unsigned char* buffer, unsigned short &pitch)
{
	int i0 = 0, i1 = 1, i2 = 2;
	
	// sort verts by height
	if(t.coords[i0].y > t.coords[i1].y) mySwap(i0, i1);
	if(t.coords[i0].y > t.coords[i2].y) mySwap(i0, i2);
	if(t.coords[i1].y > t.coords[i2].y) mySwap(i1, i2);
	
	int x0 = (int)t.coords[i0].x, y0 = (int)t.coords[i0].y;
	int x1 = (int)t.coords[i1].x, y1 = (int)t.coords[i1].y;
	int x2 = (int)t.coords[i2].x, y2 = (int)t.coords[i2].y;
	
	unsigned short pitch16 = pitch >> 1;
	
	// test for easy cases, else split trinagle in two and render both halfs
	if(y1 == y2){
 
 if(x1 > x2) mySwap(x1, x2);
 renderFlatTriangle16(x1, y1, x2, y2, x0, y0, buffer, pitch16, t.color);
	}
	else if(y0 == y1){
 
 if(x0 > x1) mySwap(x0, x1);
 renderFlatTriangle16(x0, y0, x1, y1, x2, y2, buffer, pitch16, t.color);
	}
	else{
 
 // compute x pos of the vert that builds the splitting line with x1
 int tmp_x = x0 + (int)(0.5f + (float)(y1-y0) * (float)(x2-x0) / (float)(y2-y0));
 
 if(x1 > tmp_x) mySwap(x1, tmp_x);
 renderFlatTriangle16(x1, y1, tmp_x, y1, x0, y0, buffer, pitch16, t.color);
 renderFlatTriangle16(x1, y1, tmp_x, y1, x2, y2, buffer, pitch16, t.color);
	}
}

void SoftRasta::renderFlatTriangle16(int x0, int y0, int x1, int y1, int x2, int y2, unsigned char* buffer, unsigned short pitch16, unsigned short color)
{
	unsigned short* pixel = NULL;
	
	// compute slopes for the two triangle legs
	float dx0 = (float)(x2 - x0) / (y2 - y0);
	float dx1 = (float)(x2 - x1) / (y2 - y1);
	
	int yRange = 0;
	
	float lx = (float) x0, rx = (float) x1;
	
	if(y0 < y2){ yRange = y2 - y0; pixel = (unsigned short*)buffer + y0 * pitch16; }
	else  { yRange = y0 - y2; pixel = (unsigned short*)buffer + y2 * pitch16; lx = rx = (float)x2; }
	
	for(int i=0; i<yRange; ++i){
 	
 for(int j=(int)(lx); j<(int)((rx) + 1.0f); ++j){
  
 	*(pixel + j) = color;
 }
 	
 lx  += dx0;
 rx  += dx1;
 pixel += pitch16;
	}
}

on a second thought the textured version might have been more interesting
maybe i can dig them up, too

Very interesting indeed...is this part of a software renderer you made?

i guess. it was a seperate code file i backed up for some reason. it must be several years old. i was surprised that the cd still worked at all. i'm trying to find more pieces of that renderer

which reminds me, is there going to be an update on the software rendering tuts ? maybe i can be of help ???

That's a good idea! Or maybe you could write your own tutorial on rendering a triangle (with texturing maybe) as well as explaining the math and theory behind it. That would be an excellent tutorial.

i'll consider that

This reminds me something too.... i always wondered how the trick which Chris Hecker discusses in his article actually works. I mean the stuff that you can precalculate the slopes only once and use combinations of them during the rendering process. If someone can point me to an article/tutorials that discusses that in detail and with nice and clean explanations i'll give that person five virtual bucks!!!

i thought the trick he did was not interpolating 1/z every pixel but only every n pixels... anyway, it's also at least 4-5 years since i read that particular article. i'll reread it if i can still find it. a lot of the good old information seems to be disappearing these days. maybe you have a link to it ?

[EDIT] : nm, his own site is still active... [/EDIT]

hmmm, just pondered about this. if the difference between the z coords is small enough you might just use affine mapping.
though it's not a very brilliant idea it might speed up rendering by a big margin...

sry, i completely misunderstood your post... anways, let me read through that article again...

well, the trick you are reffering to is just 9th grade trigonometry. you should take a piece of paper and work it out. it's quite simple actually...
i don't even know how to explain it better than he does. it's all there in his paper.

I'm not having problems with maths but i'm having troubles to translate that article from english )) . Anyway i'll try some more. 10x

P.S.
The stuff with the dissapearing knowledge is true!!!

sry, i didn't mean to be rude. anyways, if you can't understand the article we would have a hard time explaining it to you in englsih

Here's another way to sort vertices conveniently, without using indices:

void Rasterizer::drawTriangle(const Vertex *V1, const Vertex *V2, const Vertex *V3)
{
	if(V1->y > V3->y) swap(V1, V3);
	if(V2->y > V3->y) swap(V2, V3);
	if(V1->y > V2->y) swap(V1, V2);

	const Vertex &v1 = *V1;
	const Vertex &v2 = *V2;
	const Vertex &v3 = *V3;
...

Vertices get passed as pointers, then they are sorted by swapping the pointers, and finally the pointers are dereferences so you can work with . instead of -> all the time. All my other parameters are in a 'context' structure directly accessible for the Rasterizer class. This avoids passing all the arguments to the function.

Just a suggestion. Makes the code very clean in my opinion...

By the way, Chris Hecker's articles are worth gold when implementing a software rasterizer. I read each of them three times or more, and it was well worth it to understand every little bit he talks about.

Anyway, even though he presents the legacy method of rendering triangles, there are (better) alternatives. Triangle Scan Conversion using 2D Homogeneous Coordinates is more optimal for advanced rasterization...

yeah... the articles are great. i loved them.

maybe we could link both topics together. yours having a link to nicks, and nicks back to yours, to show the two possible ways 'as one'

well... i'd feel kind of embarassed to put my years old childrens code next to that

hehe. hey, whats the problem. it's a working scanline software rastericer. you deserve credit.

he-hey! i wrote one too... don't i deserve a credit ???

Yeah, it looks a lot like the rasterizer I've been using in swShader for years. But, you have a nice way of handling the triangle in two pieces!

Besides, the rasterizer using half-space functions isn't perfect you know. The trivial implementation looks really elegant and small but it has flaws and is slow. To get good performance (only slightly faster than the scanline rasterizer) I had to use many many tricks that make things a lot messier. And converting it to MMX/SSE is madly complicated, even though I have years of assembly experience.

now i feel .. scared... NICK HAS PROBLEMS WITH ASSEMBLY!!

okay.. i definitely stay with raytracing for EVER. never looking back at rastericers AT ALL!

okay.. i definitely stay with raytracing for EVER. never looking back at rastericers AT ALL!

yeah man... thanks for ruining my life by getting me hooked up on this you bastard !!! it's your fault... just so that you know

Originally Posted by davepermen

now i feel .. scared... NICK HAS PROBLEMS WITH ASSEMBLY!!

Hehe, I knew that was going to be interpreted wrongly. The problem lies with SoftWire really. My automatic register allocator is currently unable to produce sufficiently efficient code. It puts things in registers that could really stay in memory, and vice-versa. So it creates a lot of spilling code (writing registers to temporary memory places to free them for other data), and also redundant copies (even though it uses copy propagation). I can add hints but that's not really elegant. The problem is more fundamental, in the way SoftWire works. It cannot look ahead at what data will be needed most, or even needed at all.

This problem has been there from the start, but it was never experienced as a problem before because the generated code was still close to optimal, with only tiny inneficiencies. With the new rasterizer and quad pipeline, register pressure is really high. Every single component requires a full SSE register. So storing two 4D vector per pixel means eight registers are needed per quad, that's all of them. It's obvious that even a simple shader uses more than two vectors, and then I'm not even talking about temporaries that are needed for the SSE implementation, or things like z and w and the gradients. So SoftWire has a really hard time keeping the most useful data in registers.

Anyway, don't panic, I know what needs to be done. I have to rewrite it so that registers aren't allocated immediately, but only when their associated variables are really used. Absolutely all register allocation operations (including copy propagation) have to be deferred to the very last moment. The implementation of it is very tricky since the generated code obviously has to be correct no matter what situation.

Either way, that was what I referred to when saying the assembly implementation is "madly complicated". It should be worth it though, because I still have good hopes it will be 50-100% faster than processing one pixel at a time...