GIDForums  

Go Back   GIDForums > Computer Programming Forums > C Programming Language
User Name
Password
Register FAQ Members List Calendar Search Today's Posts Mark Forums Read
 
 
Thread Tools Search this Thread Rate Thread
  #1  
Old 12-Mar-2009, 13:20
love_rhtdmin love_rhtdmin is offline
New Member
 
Join Date: Jan 2009
Posts: 13
love_rhtdmin has a little shameless behaviour in the past

Triangle rasterization algorithm


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;
	}
}
Last edited by admin : 12-Mar-2009 at 21:28. Reason: Please insert your example C/C++ codes between [CPP] and [/CPP] tags
  #2  
Old 12-Mar-2009, 15:42
davekw7x davekw7x is offline
Outstanding Member
 
Join Date: Feb 2004
Location: Left Coast, USA
Posts: 6,153
davekw7x is a splendid one to beholddavekw7x is a splendid one to beholddavekw7x is a splendid one to beholddavekw7x is a splendid one to beholddavekw7x is a splendid one to beholddavekw7x is a splendid one to beholddavekw7x is a splendid one to beholddavekw7x is a splendid one to behold

Re: Triangle rasterization algorithm


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.
Last edited by davekw7x : 12-Mar-2009 at 16:45.
  #3  
Old 12-Mar-2009, 20:34
love_rhtdmin love_rhtdmin is offline
New Member
 
Join Date: Jan 2009
Posts: 13
love_rhtdmin has a little shameless behaviour in the past

Re: Triangle rasterization algorithm


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?
  #4  
Old 13-Mar-2009, 09:06
davekw7x davekw7x is offline
Outstanding Member
 
Join Date: Feb 2004
Location: Left Coast, USA
Posts: 6,153
davekw7x is a splendid one to beholddavekw7x is a splendid one to beholddavekw7x is a splendid one to beholddavekw7x is a splendid one to beholddavekw7x is a splendid one to beholddavekw7x is a splendid one to beholddavekw7x is a splendid one to beholddavekw7x is a splendid one to behold

Re: Triangle rasterization algorithm


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
  #5  
Old 15-Mar-2009, 09:15
love_rhtdmin love_rhtdmin is offline
New Member
 
Join Date: Jan 2009
Posts: 13
love_rhtdmin has a little shameless behaviour in the past

Re: Triangle rasterization algorithm


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
Search this Thread:

Advanced Search
Rate This Thread
Rate This Thread:

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

vB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Forum Jump

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

Network Sites: GIDNetwork · GIDApp · GIDBlog · Learning Journal by J de Silva, The

All times are GMT -6. The time now is 07:39.


vBulletin, Copyright © 2000 - 2014, Jelsoft Enterprises Ltd.