Rasterizing triangles

[Wall]

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

 

[Simon F]

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:

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]

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]

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]

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]

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]

Advanced Rasterization. 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.