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