Triangle rasterization algorithm

love_rhtdmin · #1 12-Mar-2009, 13:20

The triangle rasterization algorithm given in the fundamentals of computer graphics by Peter Shirley,Michael Ashikhmin book is as below

Code:

xmin = floor(xi)
xmax = ceiling(xi)
ymin = floor(yi)
ymax = ceiling(yi)
for y=ymin to ymax do
   for x=xmin to xmax do
     alpha = f12(x,y)/f12(x0,y0)
     beta = f20(x,y)/f20(x0,y0)
     gamma = f01(x,y)/f01(x0,y0)
     if(alpha>0 and beta>0 and gamma>0)
        c = alpha*c0+beta*c1+gamma*c2
        drawpixel(x,y) with color c

I implemented this algorithm incrementally as below. However, I am getting wrong values for constatnt alpha20_const,alpha01_const which are zero most of the times for a triangle with vertices (x0,y0),(x1,y1),(x2,y2) and colors (r0,g0,b0),(r1,g1,b1),(r2,g2,b2) respectively((r,g,b) triplet gives RGB combination for the color in graphics)) Please help me out to figure out the mistakes I have made in the implementation given below. I am multiplying the pixel coordinates with the transformation matrix, M before plotting it to the screen to apply the transformation to the triangle.

CPP / C++ / C Code:

void triangle_rasterize(float x0,float y0,float r0,float g0,float b0,float x1,float y1,float r1,float g1,float b1,float x2,float y2,float r2,float g2,float b2)
{
	float A12,A20,A01,B12,B20,B01,C12,C20,C01;
	float alpha12_y,alpha20_y,alpha01_y,alpha12_const,alpha20_const,alpha01_const;
	float alpha12_xy,alpha20_xy,alpha01_xy,alpha,beta,gama;
	float ymax=-9999.99,ymin=9999.99,xmin=9999.99,xmax=-9999.99,y,x,r,g,b;
	printf("\n In triangle rasterization");
	printf("(%f %f %f)  (%f %f %f)  (%f %f %f)",x0,y0,z0,x1,y1,z1,x2,y2,z2);
	//find xmax,xmin,ymax,ymin
	if(x0>xmax)	xmax = x0;
	if(x1>xmax)	xmax = x1;
	if(x2>xmax)	xmax = x2;

	if(y0>ymax)	ymax = y0;
	if(y1>ymax)	ymax = y1;
	if(y2>ymax)	ymax = y2;

	if(x0<xmin)	xmin = x0;
	if(x1<xmin)	xmin = x1;
	if(x2<xmin)	xmin = x2;

	if(y0<ymin)	ymin = y0;
	if(y1<ymin)	ymin = y1;
	if(y2<ymin)	ymin = y2;

	printf("\n xmin,ymin,xmax,ymax are (%f %f) (%f %f)",xmin,ymin,xmax,ymax);	
	A12 = y1-y2;	B12 = x2-x1;	C12 = (x1*y2) - (x2*y1);
	A20 = y2-y0;	B20 = x0-x2;	C20 = (x2*y0) - (x0*y2);
	A01 = y0-y1;	B01 = x1-x0;	C01 = (x0*y1) - (x1*y0);
	
	alpha12_y = B12*ymin + C12;	alpha12_const = (A12*x0) + (B12*y0) + C12;
	alpha20_y = B20*ymin + C20;	alpha20_const = (A20*x0) + (B20*y0) + C20;
	alpha01_y = B01*ymin + C01;	alpha01_const = (A01*x0) + (B01*y0) + C01;

	printf("\n constants are %f %f %f",alpha12_const,alpha20_const,alpha01_const);
	for(y = ymin; y<=ymax; y++){
		alpha12_xy = alpha12_y + (A12*xmin);
		alpha20_xy = alpha20_y + (A20*xmin);
		alpha01_xy = alpha01_y + (A01*xmin);

		for(x=xmin; x<=xmax; x++){
			alpha = alpha12_xy/alpha12_const;
			beta = alpha20_xy/alpha20_const;
			gama = alpha01_xy/alpha01_const;
			printf("\n alpha beta and gamma are %f %f %f",alpha,beta,gama);	
			if(alpha>0 & beta>0 & gama>0){
				// c = alpha*c0 + beta*c1 + gama*c2;
				// drawpixel(x,y) with color c;
				r = alpha*r0 + beta*r1 + gama*r2;
				g = alpha*g0 + beta*g1 + beta*g2;
				b = alpha*b0 + beta*b1 + gama*b2;
				printf("\n Final color is (%f %f %f)",r,g,b);
				result[0][0]=x; result[1][0]=y;  result[2][0]=0.0,  result[3][0]=1.0;
				matrixMul(M,4,4,result,4,1,start);
				glBegin(GL_POINTS);			
					glColor3f(r,g,b);
					glVertex2f(start[0][0]/start[3][0],start[1][0]/start[3][0]);
				glEnd();
			}
		}
		alpha12_y = alpha12_y + B12;
		alpha20_y = alpha20_y + B20;
		alpha01_y = alpha01_y + B01;
	}
}

davekw7x · #2 12-Mar-2009, 15:42

Quote:

Originally Posted by love_rhtdmin

The triangle rasterization algorithm given in the fundamentals of computer graphics by Peter Shirley,Michael Ashikhmin book

I don't have that book, but I believe the following are incorrect. At least they don't make sense to me.

Code:

     alpha = f12(x,y)/f12(x0,y0)
     beta  = f20(x,y)/f20(x0,y0)
     gamma = f01(x,y)/f01(x0,y0)

Check again. Shouldn't the equations be the following?

Code:

     alpha = f12(x,y)/f12(x0,y0)
     beta  = f20(x,y)/f20(x1,y1)
     gamma = f01(x,y)/f01(x2,y2)

Quote:

Originally Posted by love_rhtdmin

...I am getting wrong values for constatnt alpha20_const,alpha01_const...

Well, show us a particular triangle where the answers from your program are wrong. What did you expect the values to be? What were the values?

Maybe consider the following. (See Footnote.)

CPP / C++ / C Code:

    alpha12_y = B12 * ymin + C12;
    alpha12_const = (A12 * x0) + (B12 * y0) + C12;
    alpha20_y = B20 * ymin + C20;

    /*alpha20_const = (A20 * x0) + (B20 * y0) + C20; */ /* your value */
    alpha20_const = (A20 * x1) + (B20 * y1) + C20; /* I think this is right */

    alpha01_y = B01 * ymin + C01;

    /*alpha01_const = (A01 * x0) + (B01 * y0) + C01; *//* your value */
    alpha01_const = (A01 * x2) + (B01 * y2) + C01; /* I think this is right */

Regards,

Dave

Footnote: I have not tested this, and don't expect to.

love_rhtdmin · #3 12-Mar-2009, 20:34

Thanks Dave,
I did the corrections for beta and gamma computation as you suggested. Also I changed the condition in if loop(which is after the computation of alpha12_const, alpha20_const,alpha01_const ) as follows
if(alpha12_const!=0 & alpha20_const !=0 & alpha01_const!=0). This is the algorithm for triangle filling using barycentric coordinates. So a point in this coordinate system is given by (alpha,beta,gamma). For computing these values of a point, I am calculating signed distance of that point from the edge of the triangle. I am setting only those pixels that are inside the triangle i.e. pixels with alpha,beta and gamma all three values between 0 and 1.However I am not getting a single pixel for a valid triangle. I took example of triangle with vertices (100,100) ,(100,500),(500,600) as (x0,y0),(x1,y1),(x2,y2) respectively which is right angle triangle. But according to the computation I get alpha as always 1 and beta is always negative and gamma as positive with the same value as beta
e.g. alpha =1 beta = -0.556 gamma = 0.556
So how is it possible that there is not a single pixel with values of alpha,beta and gamma all three between 0 and 1?

davekw7x · #4 13-Mar-2009, 09:06

Quote:

Originally Posted by love_rhtdmin

... I did the corrections for beta and gamma computation as you suggested.

Those were for the constant parts of the terms that you actually need to use for each x and y.

Quote:

Originally Posted by love_rhtdmin

Also I changed the condition in if loop(which is after the computation of alpha12_const, alpha20_const,alpha01_const ) as follows
if(alpha12_const!=0 & alpha20_const !=0 & alpha01_const!=0).

Huh? Why would you do that?

Quote:

Originally Posted by love_rhtdmin

This is the algorithm for triangle filling using barycentric coordinates.

Pixels in the triangle are those for which alpha, beta, and gamma are all greater than or equal to zero and less than or equal to 1. (If you want just the interior of the triangle, and not the border, then the conditions are greater than zero and less than or equal to 1.) If calculated correctly, the values of alpha, beta, and gamma will always be less than or equal to 1, so you need only check whether all are greater than or equal to zero. Points for which alpha or beta or gamma is negative are definitely outside the triangle!

CPP / C++ / C Code:

            if ((alpha >= 0) && (beta >= 0) && (gama >= 0))
            {

Quote:

Originally Posted by love_rhtdmin

... I am not getting a single pixel for a valid triangle. I took example of triangle with vertices (100,100) ,(100,500),(500,600) as (x0,y0),(x1,y1),(x2,y2) respectively which is right angle triangle.

Well...actually it's not a right triangle, but it is a triangle.

Quote:

Originally Posted by love_rhtdmin

...
So how is it possible that there is not a single pixel with values of alpha,beta and gamma all three between 0 and 1?

Well, it isn't possible. Therefore something is wrong with your calculations of alpha and beta and gamma, right?

For each value of x and y, you must calculate a new value for alpha, beta, and gamma.

I'm not sure how you arrived at your loop calculations, but I claim that if they were working properly the output would be correct.

In cases of OPC (Other People's Code), I just start from fundamentals and do the calculations in a way that is "obvious" to me. If they have done some work that seems valid, I may keep it. If there is any question, I rewrite it.

In case of my own code, if I couldn't see anything wrong, but I am pretty sure there is something wrong, I might wipe the slate clean and try another formulation.

Using your notation, I might calculate alpha, beta, and gamma with something like:

CPP / C++ / C Code:

    for (y = ymin; y <= ymax; y++)
    {
        for (x = xmin; x <= xmax; x++)
        {
            alpha12_xy = A12 * x + B12 * y + C12;
            alpha = alpha12_xy / alpha12_const;

            alpha20_xy = "something" * x + "something" * y + "something";
            beta = alpha20_xy / alpha20_const;

            alpha01_xy = "something" * x + "something" * y + "something";
            gama = alpha01_xy / alpha01_const;
            if ((alpha >= 0) && (beta >= 0) && (gama >= 0))
            {

                 /* light the pixel */
          
             }           
        }
.
.
.

Here's how I would try testing it:

1. On a piece of graph paper, plot three points that make a triangle. Since I am going to visually inspect the output from the program, I pick a small triangle. For an example, I will choose the three points that make up a right triangle: (1,1) (6,1) (1,5). I pick a scale on the graph paper that will let me draw the triangle easily and see at a glance what pixels will be lighted.

Then I create a main program that calls the function with these three values. I pick a single color for all points so that I don't have to worry about interpolation, just the part that decides what pixels will be lighted.

Then I make a version of the function that doesn't actually use any plotting routines, but just prints out coordinates of the lighted pixels.

The loop inside the function might look something like:

CPP / C++ / C Code:

    for (y = ymin; y <= ymax; y++)
    {
        for (x = xmin; x <= xmax; x++)
        {
            alpha12_xy = "something" * x + "something" * y + "something";
            alpha = alpha12_xy / alpha12_const;

            alpha20_xy = "something" * x + "something" * y + "something";
            beta = alpha20_xy / alpha20_const;

            alpha01_xy = "something" * x + "something" * y + "something";
            gama = alpha01_xy / alpha01_const;

            if ((alpha >= 0) && (beta >= 0) && (gama >= 0))
            {
                printf("There is a lighted pixel at (%.0f,%.0f)\n", x,y);
            }
        }
    }

From my pencil and paper doodlings, I would expect to see printed values for
points in and on the triangle. Namely for the points:

(1,1) (2,1) (3,1) (4,1) (5,1) (6,1) (1,2) (2,2) (3,2) (4,2) (1,3) (2,3) (3,3) (1,4) (2,4) (1,5)

Regards,

Dave

love_rhtdmin · #5 15-Mar-2009, 09:15

Dave,
Thanks a lot. I figured out the mistakes in this algorithm with the hints provided by you. Also please assist me on my other post of finding normal at a triangle vertex.

Thread Tools	Search this Thread
Show Printable Version Email this Page	Search this Thread: Advanced Search
Rate This Thread
Rate This Thread:

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
pascal's triangle element	aijazbaig1	C Programming Language	2	27-Aug-2007 03:18
triangle (polygon), drawing, sizing, and rotation programme using linked lists...	promsan	C Programming Language	12	14-May-2007 14:03
Help on homework!	kemmal	C Programming Language	1	06-Nov-2006 11:22
Algorithm Help Please!	daking_09	C++ Forum	0	24-May-2006 19:12
help.... SLR * algorithm	tay	C Programming Language	4	10-Sep-2004 11:48

Triangle rasterization algorithm

Re: Triangle rasterization algorithm

Re: Triangle rasterization algorithm

Re: Triangle rasterization algorithm

Re: Triangle rasterization algorithm