Color interpolation

Lately I have just been fiddling with some smaller graphics things in my free time. Although I have graphics quite a bit, I have never written anything to interpolate color such as OpenGL does, so I wanted to give it a shot.

So I modified my bresenham line algorithm so that it interpolates the color of a line. It does it well, and I get good results.

I then decided that I wanted to do the same with triangles. So I wrote a function that essentially uses a scan-line fill algorithm, although it is not as full blown - and thus will really only work for triangles and not any arbitrary polygon.

The results I am getting a little bit less than satisfactory, however. They are not bad, per se, but it is definitely a much different result than what comes out of OpenGL when I have OpenGL render a color-interpolated triangle.

Here is an image (mine on the left, OpenGL on the right):



As you can see it is not quite as clean (and the colors are not in the correct order either - although that is a minor problem that I know how to fix and is not my main concern).

So here is how I do the scanline algorithm:

Code:

A triangle is defined by 3 points A, B, and C.
Step 1: retrieve a list of all points that form the line segments AB, AC, and BC.
Step 2: put all points into a master list.
Step 3: Order all points by their y-coordinate value
     Step 3.1: Create a multimap with the key being the y-coord, and the vals being the points
Step 4: Iterate through the multimap
    Step 4.1: For each y-coordinate in the multimap, look at the points associated with it.
        Step 4.1.1: Draw an interpolated line from the point with the min x-coord to the point with the max x-coord for that specific y-coord

So that is my general algorithm. The logic seems good to me, but there must be some flaw somewhere. Here is my code. It is fairly short:

Code:

void triangle ( float *surface, point a, point b, point c, color sColor, color fColor, color gColor )
{
	//Get the 3 edges of the triangle
	vector <point> listA = linepoints ( a, b, sColor, fColor );
	vector <point> listB = linepoints ( a, c, sColor, gColor );
	vector <point> listC = linepoints ( b, c, fColor, gColor );

	vector <point> master;
	for ( int x = 0; x < listA.size(); x++ ) master.push_back ( listA[x] );
	for ( int x = 0; x < listB.size(); x++ ) master.push_back ( listB[x] );
	for ( int x = 0; x < listC.size(); x++ ) master.push_back ( listC[x] );

	multimap <int, point> coordMap;

	for ( int x = 0; x < master.size(); x++ )
		coordMap.insert ( pair<int, point> ( master[x].y, master[x] ) );


	multimap<int, point>::iterator myIter = coordMap.begin();
	point min, max;
	int curY;

	curY = myIter->first;
	min = myIter->second;
	max = myIter->second;

	while ( myIter != coordMap.end() )
	{
		if ( myIter->first != curY )
		{
			line ( surface, min, max, min.pColor, max.pColor );

			curY = myIter->first;
			min = myIter->second;
			max = myIter->second;
		}
		else
		{
			if ( myIter->second.x < min.x )
				min = myIter->second;
			if ( myIter->second.x > max.x )
				max = myIter->second;
		}

		myIter++;
	}

}

Thanks for any help resolving this

Based on my pedestrian understanding of multimaps, they are sorted for you based on the compare algorithm in use. In this case, the default LESS comparator is used on your pointer.

Does the default LESS compare routine understand class pointer, and that it needs to sort on the Y coordinate first, and then the X coordinate? (If it did/could sort on Y and then X, you could avoid the "look for min and max X" routine following, and then just search for the first and last equalling Y values to find min and max X.)

Your algorithm to find min.x and max.x seems fine, although you're not doing anything with the data (perhaps because you paired down your post to keep focus on the routine?) Consider tweaking it to speed it up:

Code:

			if ( myIter->second.x < min.x )
				min = myIter->second;
			else if ( myIter->second.x > max.x )
				max = myIter->second;

Todd

Well, I didn't absorb all your code. Duh. You are inserting into the multimap with a key of Y, so that should be fine. And, you are doing something with the data - you are calling line().

I think there is a flaw in your logic in the final loop, and this might explain why the top of the triangle appears to be clipped off. The final and highest value for Y will never be sent to the line() function.

Also, perhaps you could let the multimap sort on both Y and X by changing your key from

Code:

pair<int, point>

to

Code:

pair<pair<int,int>,point>

where the internal pair is (Y,X). Just an idea. Not even sure that is legal.

Todd

And...

You could get rid of master by going directly into coordMap form each of your 3 lists, as such:

Code:

for ( int x = 0; x < listA.size(); x++ ) 
	coordMap.insert ( pair<int, point> ( listA[x].y, listA[x] ) ) ;

I know you weren't asking for suggestions such as this, but considering what you're paying for the advice, it's probably not so bad a deal. (I mean, "Game Programming" suggests to me an emphasis on the desire for performance and eliminating unnecessary steps.)





EDIT: In Ruby, you could even eliminate the 3 vectors for listA, B and C. Perhaps this can be done in C++ also by iterating over the returned set from linepoints directly, without having to assign them to a vector.

In Ruby, the syntax would be akin to this:

Code:

linepoints ( a, b, sColor, fColor ).each {|lp| 
	coordMap.insert ( pair<int, point> ( lp.y, lp ) ) ;

Okay, so I fixed the mistakes that you mentioned. I also fixed some other mistakes that I found in other pieces of my code regarding the ordering of the colors, so things look a lot better now.

There is still a small bug though. Here is my most recent image (left is OpenGL, right is mine):



A lot of the errors that were occurring in the actual interpolation of colors was happening because I was popping colors and points of their respective stacks in the wrong order in other part of my code.

Now, you can probably already easily see what the remaining problem is. That lowest line is being drawn almost all green for some reason, when it shouldn't be. There is a bit too much green all around, although it's not too bad. Also the blob of purple on the top right? Strange...

Here is the current working version of the code:

Code:

void triangle ( float *surface, point a, point b, point c, color sColor, color fColor, color gColor )
{
	//Get the 3 edges of the triangle
	vector <point> listA = linepoints ( a, b, sColor, fColor );
	vector <point> listB = linepoints ( a, c, sColor, gColor );
	vector <point> listC = linepoints ( b, c, fColor, gColor );

	multimap <int, point> coordMap;

	for ( int x = 0; x < listA.size(); x++ ) coordMap.insert ( pair<int, point> ( listA[x].y, listA[x] ) );
	for ( int x = 0; x < listB.size(); x++ ) coordMap.insert ( pair<int, point> ( listB[x].y, listB[x] ) );
	for ( int x = 0; x < listC.size(); x++ ) coordMap.insert ( pair<int, point> ( listC[x].y, listC[x] ) );

	multimap<int, point>::iterator myIter = coordMap.begin();
	point min, max;
	int curY;

	curY = myIter->first;
	min = myIter->second;
	max = myIter->second;

	int debug = 0;

	while ( myIter != coordMap.end() )
	{
		if ( myIter->first != curY )
		{
			line ( surface, min, max, min.pColor, max.pColor );

			curY = myIter->first;
			min = myIter->second;
			max = myIter->second;
		}
		else
		{
			if ( myIter->second.x < min.x )
				min = myIter->second;
			if ( myIter->second.x > max.x )
				max = myIter->second;
		}

		myIter++;
	}

	line ( surface, min, max, min.pColor, max.pColor );

}

You could still tweak this:

Code:

	while ( myIter != coordMap.end() )
	{
		if ( myIter->first != curY )
		{
			line ( surface, min, max, min.pColor, max.pColor );

			curY = myIter->first;
			min = myIter->second;
			max = myIter->second;
		}
		else
		{
			if ( myIter->second.x < min.x )
				min = myIter->second;
			else if ( myIter->second.x > max.x )
				max = myIter->second;
		}

		myIter++;
	}

Or not!

I'm not so sure the problem is in this routine. For grins, did you verify for yourself the multimap is returning points in the proper, expected, sorted order, (Y only ever increases) and that the derived minX and maxX values were proper? Y and X are signed, and the Compare routine is working with signed, right?

I don't know if it would make any difference, but you will have 3 pairs of duplicate points - each vertex will be repeated. However, the pColor may have different values. For instance, the corner "a" will have an endpoint from line ab and from line ac. Will the pColor be different for each point "a", or would the interpolation return the same pColor for point "a"? You could check this.

Todd

Any why aren't you working with doubles for your x and y coordinates? Are you getting the precision you need when finding all the points on a line?

Todd

Well that is a property of multimaps. multimap is part of the STL library, and it is defined as such:

Quote from www.cplusplus.com:

Internally, multimap containers keep their elements ordered by their keys from lower to higher

Therefore, all elements with the same key are guaranteed to be grouped together. Since my keys are simply integers, the key/value pairs will look something like this:

300 => point ( 300, 300 )
300 => point ( 500, 300 )
300 => ....
301 => ....
.....
500 => point ( 500, 500 )
......

My algorithm uses the fact that that is guaranteed while it is iterating through the multimap. For every y-value, it looks for the points that contain the min and max x-values, and then it draws a line between them.

You are correct that I will have 3 pairs of duplicate points. It is something that I had not considered, but I also do not think it will affect me in this case. The colors of those points should be the same.

Here, I will show you the actual method that draws the line and does the interpolation. It is just bresenham's algorithm:

Code:

void line ( float *surface, point a, point b, color sColor, color fColor )
{
	int Ax = a.x;
	int Bx = b.x;
	int Ay = a.y;
	int By = b.y;

	color curColor = sColor;

	//------------------------------------------------------------------------
	// INITIALIZE THE COMPONENTS OF THE ALGORITHM THAT ARE NOT AFFECTED BY THE
	// SLOPE OR DIRECTION OF THE LINE
	//------------------------------------------------------------------------
	int dX = abs(Bx-Ax);	// store the change in X and Y of the line endpoints
	int dY = abs(By-Ay);

	//------------------------------------------------------------------------
	// DETERMINE "DIRECTIONS" TO INCREMENT X AND Y (REGARDLESS OF DECISION)
	//------------------------------------------------------------------------
	int Xincr, Yincr;
	if (Ax > Bx) { Xincr=-1; } else { Xincr=1; }	// which direction in X?
	if (Ay > By) { Yincr=-1; } else { Yincr=1; }	// which direction in Y?

	//------------------------------------------------------------------------
	// DETERMINE INDEPENDENT VARIABLE (ONE THAT ALWAYS INCREMENTS BY 1 (OR -1) )
	// AND INITIATE APPROPRIATE LINE DRAWING ROUTINE (BASED ON FIRST OCTANT
	// ALWAYS). THE X AND Y'S MAY BE FLIPPED IF Y IS THE INDEPENDENT VARIABLE.
	//------------------------------------------------------------------------
	if (dX >= dY)	// if X is the independent variable
	{
		int dPr 	= dY<<1;           // amount to increment decision if right is chosen (always)
		int dPru 	= dPr - (dX<<1);   // amount to increment decision if up is chosen
		int P 		= dPr - dX;  // decision variable start value

		for (; dX>=0; dX--)            // process each point in the line one at a time (just use dX)
		{
			//putpixel(screen, Ax, Ay, Color); // plot the pixel
			putpixel ( surface, Ax, Ay, curColor );

			curColor.r += ( fColor.r - sColor.r ) / dX;
			curColor.g += ( fColor.g - sColor.g ) / dX;
			curColor.b += ( fColor.b - sColor.b ) / dX;
			curColor.a += ( fColor.a - sColor.a ) / dX;

			if (P > 0)               // is the pixel going right AND up?
			{
				Ax+=Xincr;	       // increment independent variable
				Ay+=Yincr;         // increment dependent variable
				P+=dPru;           // increment decision (for up)
			}
			else                     // is the pixel just going right?
			{
				Ax+=Xincr;         // increment independent variable
				P+=dPr;            // increment decision (for right)
			}
		}
	}
	else              // if Y is the independent variable
	{
		int dPr 	= dX<<1;           // amount to increment decision if right is chosen (always)
		int dPru 	= dPr - (dY<<1);   // amount to increment decision if up is chosen
		int P 		= dPr - dY;  // decision variable start value

		for (; dY>=0; dY--)            // process each point in the line one at a time (just use dY)
		{
			//putpixel(screen, Ax, Ay, Color); // plot the pixel
			putpixel ( surface, Ax, Ay, curColor );

			curColor.r += ( fColor.r - sColor.r ) / dY;
			curColor.g += ( fColor.g - sColor.g ) / dY;
			curColor.b += ( fColor.b - sColor.b ) / dY;
			curColor.a += ( fColor.a - sColor.a ) / dY;

			if (P > 0)               // is the pixel going up AND right?
			{
				Ax+=Xincr;         // increment dependent variable
				Ay+=Yincr;         // increment independent variable
				P+=dPru;           // increment decision (for up)
			}
			else                     // is the pixel just going up?
			{
				Ay+=Yincr;         // increment independent variable
				P+=dPr;            // increment decision (for right)
			}
		}
	}
}

The function linepoints is the exact same code as line, except that it returns a vector containing a list of all the points in the line, instead of actually plotting each point onto a raster surface. Here is that portion of the code:

Code:

			point nPoint;
			nPoint.x = Ax;
			nPoint.y = Ay;
			nPoint.pColor = curColor;
			retList.push_back ( nPoint );

I don't understand the problem here.

The linear interpolation is quite simple.

Code:

float LI(float value1,float value2,float interp)
{
 return value1+interp*(value2-value1);
}

Once you get the color of the startpoint and the color of the endpoint the rest is just calling this function to retrieve the RGB values.

So you would scan convert each edge and save the colors of the points on the line. Then draw from top to bottom, left to right.

If it's that simple then maybe you could provide an answer on why my code is malfunctioning

The first thing you need to do is simplify the system. A rasterizer doesn't need all that much. If I remember correctly here is the algo I used way back in the DOS DJGPP days. Keep in mind Bresehnams is the correct line drawing algo to use so you have that right.

1. Start at top vertex or point.
2. If next vertex is left of vertex found with step 1, place it in left array.
3. If next vertex is right of vertex found with step 1, place it in right array.

Once you have all the left and right values you do scan-convert from left to right. So let's say you have:

top - 160,100
left - 0,150
right 320,150

You now have to solve for X given a known Y for every left[] right[] you have. Y is simply incremented so you know the Y value. X is found using slope-intercept. Do this for all edges. Now you must also take into account colors at the vertices. This is actually quite simple. You are doing a linear interpolation from top vertex color to left color. You are doing the same for the top vertex color to right color. Store these value left[], right[] which contains the X's. You will also have to store the RGB's for those points - leftRGB[],rightRGB[]. The actual scan conversion is just drawing a line from left[point_num] to right[point_num]. The color is interpolated between leftRGB[point_num] and rightRGB[point_num] as you draw from left to right. If you interpolated correctly when you scan converted the edges...then the colors will be correct. Hence you have bilinear filtering. You have linear interpolated colors on X and Y.

The edge color interpolation on Y would be:

Code:

float red_inc = 1.0f/(dest_red - src_red);
float grn_inc = 1.0f/(dest_grn - src_grn);
float blu_inc = 1.0f/(dest_blu - src_blu);
float alpha_inc = 1.0f/(dest_alpha - src_alpha);

Note that you must also do this for X during your edge scan conversion.



The color interpolation from left to right then is:

Code:

float red_inc = 1.0f/(right_red- left_red);
float grn_inc = 1.0f/(right_grn - left_grn);
float blu_inc = 1.0f/(right_blu - left_blu);
float alpha_inc = 1.0f/(right_alpha - left_alpha);

So when drawing you start at left_red and increment by red_inc every time you increment x. When you arrive at right[num_point].x you will be at right_red which is correct.

For texturing you would do the same except you would linear interpolate based on texel values at the vertices rather than just RGB values and this would be the infamous linear texture mapping.