rendering a triangle in software

F7a4a748ecf664f189bb704a660b3573
0
anubis 101 Jan 15, 2004 at 18:29

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;
    }
}

26 Replies

Please log in or register to post a reply.

F7a4a748ecf664f189bb704a660b3573
0
anubis 101 Jan 15, 2004 at 23:52

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

Fdbdc4176840d77fe6a8deca457595ab
0
dk 158 Jan 16, 2004 at 03:59

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

F7a4a748ecf664f189bb704a660b3573
0
anubis 101 Jan 16, 2004 at 11:40

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

F7a4a748ecf664f189bb704a660b3573
0
anubis 101 Jan 16, 2004 at 16:01

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

Fdbdc4176840d77fe6a8deca457595ab
0
dk 158 Jan 17, 2004 at 01:29

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.

F7a4a748ecf664f189bb704a660b3573
0
anubis 101 Jan 17, 2004 at 09:26

i’ll consider that

2b97deded6213469bcd87b65cce5d014
0
Mihail121 102 Jan 20, 2004 at 10:36

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

F7a4a748ecf664f189bb704a660b3573
0
anubis 101 Jan 20, 2004 at 12:49

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]

F7a4a748ecf664f189bb704a660b3573
0
anubis 101 Jan 20, 2004 at 12:54

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…

F7a4a748ecf664f189bb704a660b3573
0
anubis 101 Jan 20, 2004 at 12:56

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

F7a4a748ecf664f189bb704a660b3573
0
anubis 101 Jan 20, 2004 at 21:42

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.

2b97deded6213469bcd87b65cce5d014
0
Mihail121 102 Jan 24, 2004 at 09:44

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

F7a4a748ecf664f189bb704a660b3573
0
anubis 101 Jan 25, 2004 at 17:43

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 ;)

99f6aeec9715bb034bba93ba2a7eb360
0
Nick 102 Sep 07, 2004 at 21:26

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…

99f6aeec9715bb034bba93ba2a7eb360
0
Nick 102 Sep 07, 2004 at 21:33

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…

F7a4a748ecf664f189bb704a660b3573
0
anubis 101 Sep 07, 2004 at 21:54

yeah… the articles are great. i loved them.

6ad5f8c742f1e8ec61000e2b0900fc76
0
davepermen 101 Sep 15, 2004 at 10:41

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’

F7a4a748ecf664f189bb704a660b3573
0
anubis 101 Sep 15, 2004 at 13:53

well… i’d feel kind of embarassed to put my years old childrens code next to that :)

6ad5f8c742f1e8ec61000e2b0900fc76
0
davepermen 101 Sep 15, 2004 at 16:48

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

2b97deded6213469bcd87b65cce5d014
0
Mihail121 102 Sep 15, 2004 at 17:01

he-hey! i wrote one too… don’t i deserve a credit ??? :D

99f6aeec9715bb034bba93ba2a7eb360
0
Nick 102 Sep 15, 2004 at 17:13

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

6ad5f8c742f1e8ec61000e2b0900fc76
0
davepermen 101 Sep 15, 2004 at 17:44

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

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

F7a4a748ecf664f189bb704a660b3573
0
anubis 101 Sep 15, 2004 at 19:12

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 :D

99f6aeec9715bb034bba93ba2a7eb360
0
Nick 102 Sep 15, 2004 at 20:18

@davepermen

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

Hehe, I knew that was going to be interpreted wrongly. :rolleyes: 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…

6ad5f8c742f1e8ec61000e2b0900fc76
0
davepermen 101 Sep 16, 2004 at 21:53

@anubis

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 :D

[snapback]11573[/snapback]

you love it, you just don’t wanna tell, right?

but it IS to love, and you know it! :D

6ad5f8c742f1e8ec61000e2b0900fc76
0
davepermen 101 Sep 16, 2004 at 21:57

@Nick

…..softwire bla……

okay, got the problem now. you changed very much your bottlenecks, and softwire was optimized for the old days..

but yes, it should give 50 - 100% speedboost for SURE.

and this will rock. it will be about the most optimal written software renderer ever.. and still 100% dynamic.

softwire rocks! :D

can’t wait for the next swshader demos :D

i wish you, as always, all the best.. while i try to get my raytracing-stuff working :D (with softwire in, of course)