Rasterizing triangles


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

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 :slight_smile:
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.


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