### Author Topic: Triangle rasterizing  (Read 2638 times)

0 Members and 1 Guest are viewing this topic.

#### will

• Associate
• Posts: 1
##### Triangle rasterizing
« on: January 08, 2007, 02:21:50 PM »
Hi!

I've just started to work on a software renderer and have trouble with scan converting triangles properly. I've tried a few different techniques but I always get weird artifacts. I use a pie of triangles which renders perfectly with OpenGL. This is what it looks like with my algorithm:

As you can see, it renders some triangles correctly but there are inconsistencies in the middle and at the edge of the pie.
I first tried the half-space technique but got weird results, so I tried the other one where you walk along the edges and compute each scan-line's start and end X position. I'm not using integers, I thought I'd try to get a floating point version working first, but could that cause precision problems?

Instead of explaining exactly how I've implemented the code, I'll just post it, here:
Code: [Select]
`//Point is a struct containing two integer values; x and y coordinatevoid ScanTriangle(Point tri[]){        //These will hold the index in the array to the three vertices        //Assume an order to start with... int startPoint = 0; int secondPoint = 1; int thirdPoint = 2; //Choose a vertex to start at (the lowest) if (tri[secondPoint].y < tri[startPoint].y) startPoint = 1; if (tri[thirdPoint].y < tri[startPoint].y) startPoint = 2; //If there is another vertex with the same y value, choose the one that that doesn't as starting point if (tri[startPoint].y == tri[(startPoint+1)%3].y) startPoint = (startPoint+2)%3; else if (tri[startPoint].y == tri[(startPoint+2)%3].y) startPoint = (startPoint+1)%3; //Choose index for the second and third vertex of the triangle secondPoint = (startPoint+1)%3; thirdPoint = (startPoint+2)%3; //Calculate the slopes of the edges from the starting vertex to the second and third vertex float d0 = (float)(tri[secondPoint].x-tri[startPoint].x)/(float)(tri[secondPoint].y-tri[startPoint].y); float d1 = (float)(tri[thirdPoint].x-tri[startPoint].x)/(float)(tri[thirdPoint].y-tri[startPoint].y); //Determine if we are walking up or down int yStep = tri[startPoint].y > tri[secondPoint].y ? -1 : 1; //Determine the last Y value int lastY; if (yStep < 0) lastY = Min(tri[startPoint].y, tri[secondPoint].y, tri[thirdPoint].y)-1; //-1 to get the last row aswell else lastY = Max(tri[startPoint].y, tri[secondPoint].y, tri[thirdPoint].y); //Loop and walk along the y axis to calculate the start and end values for each span float minX = (float)tri[startPoint].x; float maxX = (float)tri[startPoint].x; for (int y = tri[startPoint].y; y != lastY; y += yStep) { //We can only draw pixels at integer values, so convert and round up or down to be inside the triangle int xStart = (int)ceil(minX); int xEnd = (int)ceil(maxX)-1; //Draw the span if (y != tri[startPoint].y) { for (int x = xStart; x <= xEnd; x++) PlotPixel(x, y); } //See if a vertex has been reached, in which case the slope of that edge needs to be recalculated if (y == tri[secondPoint].y) { if (y != tri[thirdPoint].y) d0 = (float)(tri[thirdPoint].x-tri[secondPoint].x)/(float)(tri[thirdPoint].y-tri[secondPoint].y); } if (y == tri[thirdPoint].y) { if (y != tri[secondPoint].y) d1 = (float)(tri[secondPoint].x-tri[thirdPoint].x)/(float)(tri[secondPoint].y-tri[thirdPoint].y); } //Increase/decrease the length for the next span if (tri[secondPoint].x < tri[thirdPoint].x) { minX += d0*yStep; maxX += d1*yStep; } else { minX += d1*yStep; maxX += d0*yStep; } }}`The code is not at all optimized (since it doesn't work yet ) and I know it can be a pain to read code on a forum, but any hint of a solution is apreciated!
Thanks in advance

#### JeGX

• Global Moderator
• Capo Crimine
• Posts: 2370
##### Re: Triangle rasterizing
« Reply #1 on: January 08, 2007, 09:15:22 PM »
Software renderer... long long time ago...
The problem seems to be the same than for rotating an image. Google this trail.
Or maybe have a look at the book "Trick of 3d game programming gurus" by Lamothe.