# Rasterizing triangles

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:

``````//Point is a struct containing two integer values; x and y coordinate
void ScanTriangle(Point tri[])
{
//These will hold the index in the array to the three vertices
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!

I know it can be a pain to read code on a forum
I don’t even have to look at your code to tell what’s wrong I bet you render lines in different directions. That’s the cause.
It should always be top-down (or any other direction you choose) no matter if it’s left or right edge of triangle.
Line drawn from A to B can be slightly different that line drawn from B to A.
Example:

``````0--1
|\A|
|B\|
2--3
``````

Triangle A has 3 edges - 0-1, 1-3 and 3-0
Triangle B has 3 edges - 0-3, 3-2 and 2-0
Edge 0-3 is shared but it should not be rendered as 3-0 in triangle A and 0-3 in triangle B. It should be rendered as 0-3 or 3-0 for both A and B.

I’m a little late, but thanks alot for your advice, I think that is the problem