PDA

View Full Version : Rasterizing triangles

Wall
08-Jan-2007, 12:43
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:
http://img225.imageshack.us/img225/287/artifactsvf2.gif

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:wink:) and I know it can be a pain to read code on a forum, but any hint of a solution is apreciated!

Simon F
08-Jan-2007, 13:58
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:
http://img225.imageshack.us/img225/287/artifactsvf2.gif

I haven't tried reading your code but I would hazard a guess that you haven't got your "on edge" fill rules correctly implemented.

If you are doing an "inside test" on an edge and it hits exactly on the edge, then you need to take the orientation of the the line into account before deciding if it's inside or outside.

Wall
08-Jan-2007, 15:08
I haven't tried reading your code but I would hazard a guess that you haven't got your "on edge" fill rules correctly implemented.

If you are doing an "inside test" on an edge and it hits exactly on the edge, then you need to take the orientation of the the line into account before deciding if it's inside or outside.

Thanks, that is probably it! Although I haven't really found a good resource on the rules for integer values, could you expand on this? As it is now I just do this to account for on-edge cases:
int xStart = (int)ceil(minX);
int xEnd = (int)ceil(maxX)-1;
So I don't take the orientation into account, I just make the left edge inside and the right outside. what kind of orientations should be treated as inside and what should be treated as outside?

Thanks

Colourless
09-Jan-2007, 00:37
It might be an accuracy problem because of snapping the floating point vertices to integer coordinates for the pixels. While your slopes are being calculated with floats, your start and end points are not for the y axis. That sort of issue tends to show very badly when doing texturing.

Simon F
09-Jan-2007, 09:27
Thanks, that is probably it! Although I haven't really found a good resource on the rules for integer values, could you expand on this? As it is now I just do this to account for on-edge cases:
int xStart = (int)ceil(minX);
int xEnd = (int)ceil(maxX)-1;
So I don't take the orientation into account, I just make the left edge inside and the right outside. what kind of orientations should be treated as inside and what should be treated as outside?
Thanks

To be honest, if you aren't worried about speed, a far better solution is to compute the edge equations of the triangle edges, i.e. a X + b Y + C = M. where (for example) M=0 when you are on the edge, > 0 when inside the edge and < 0 when outside.

When you detect the M=0 case, you use the "tie breaking" rules so that you don't leave a gap between two triangles nor fill the pixel twice along the edge where the triangles meet. For example, you can use something like

if M==0 then
if a > 0 then
InsideEdge = True
else if a < 0 then
InsideEdge = False
else if b > 0 then //i.e. a==0
InsideEdge = True
else
InsideEdge = False

Does that help?

Wall
09-Jan-2007, 10:04
Thank you both, I'll poke around with the code a bit and if I can't get it right I'll try your suggestion Simon. Using the line equation looks like a more elegant solution.

Nick
09-Jan-2007, 11:28
Advanced Rasterization (http://www.devmaster.net/forums/showthread.php?t=1884). It's a robust implementation of the line equation method. The overhead for using the correct fill convention is also very small, and I've optimized it for large triangles.