# Interpolating on the face of a trinagle.

This topic is 3052 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## Recommended Posts

Hi, I am looking to do interpolation on the face of a triangle, like the GPU does on the face of a triangle for the texture coordinates. I am not interested in the perspective correction aspect as this is only needed for the CPU and not for visualization. Can someone point me to the right algorithm to do this on the CPU. Thanks, - Sid

##### Share on other sites

The U, V stuff in there. Read through carefully, and you will find it.

##### Share on other sites
First what you need to do is create two arrays, one for the left edge(s) of the triangle and one for the right. I used arrays of vertices for this in my software rasterizer since I was interpolating just about every variable in the vertex structure.

You'll need a function to fill out the edge arrays. I used a modified Bresenham line drawing function for this. It gives preferable results over slope interpolation:

//Stripped down and simplified.typedef struct vertex{	float	x,y;	long	sx,sy; //Projected screen coordinates	float	u,v;}vertex;vertex	left_edge[SCREEN_HEIGHT],right_edge[SCREEN_HEIGHT]; // Global edge arrays// This interpolates the u and v values down the edges of the triangle.// p1 is the starting vertex for the edge and p2 is the ending vertex.// Rather than split the function in two, it fills either edge array based // on the bool "right". If true, the right edge array is filled.// Note, it isn't necessary to clear the arrays before use. Since you will// be drawing one triangle at a time, the current triangle will overwrite the// corresponding values in the arrays.// This could be optimized better, but it works well.void FillEdgeArray(vertex p1,vertex p2,bool right){	long	dy,dx,sx,sy;	long	accum;	float	u_step,v_step;	float	u,v;	dx = p2.sx - p1.sx;	dy = p2.sy - p1.sy;	sx = SIGN(dx);	sy = SIGN(dy);	dx = ABS(dx);	dy = ABS(dy);	if(dx > dy)	{		u_step = (p2.u - p1.u) / (float)dx;		v_step = (p2.v - p1.v) / (float)dx;	}else{		u_step = (p2.u - p1.u) / (float)dy;		v_step = (p2.v - p1.v) / (float)dy;	}	u = p1.u;	v = p1.v;	if(right)	{		if(dx > dy)		{			accum = dx >> 1;			do{				if((p1.sy >= 0) && (p1.sy < 1024))				{					right_edge[p1.sy].sx = p1.sx;					right_edge[p1.sy].sy = p1.sy;					right_edge[p1.sy].u = u;					right_edge[p1.sy].v = v;				}				accum -= dy;				if(accum < 0)				{					accum += dx;					p1.sy += sy;				}				p1.sx += sx;				u += u_step;				v += v_step;			}while(p1.sx != p2.sx);		}else{			accum = dy >> 1;			do{				if((p1.sy >= 0) && (p1.sy < 1024))				{					right_edge[p1.sy].sx = p1.sx;					right_edge[p1.sy].sy = p1.sy;					right_edge[p1.sy].u = u;					right_edge[p1.sy].v = v;				}				accum -= dx;				if(accum < 0)				{					accum += dy;					p1.sx += sx;				}				p1.sy += sy;				u += u_step;				v += v_step;			}while(p1.sy != p2.sy);		}	}else{		if(dx > dy)		{			accum = dx >> 1;			do{				if((p1.sy >= 0) && (p1.sy < 1024))				{					left_edge[p1.sy].sx = p1.sx;					left_edge[p1.sy].sy = p1.sy;					left_edge[p1.sy].u = u;					left_edge[p1.sy].v = v;;				}				accum -= dy;				if(accum < 0)				{					accum += dx;					p1.sy += sy;				}				p1.sx += sx;				u += u_step;				v += v_step;			}while(p1.sx != p2.sx);		}else{			accum = dy >> 1;			do{				if((p1.sy >= 0) && (p1.sy < 1024))				{					left_edge[p1.sy].sx = p1.sx;					left_edge[p1.sy].sy = p1.sy;					left_edge[p1.sy].u = u;					left_edge[p1.sy].v = v;				}				accum -= dx;				if(accum < 0)				{					accum += dy;					p1.sx += sx;				}				p1.sy += sy;				u += u_step;				v += v_step;			}while(p1.sy != p2.sy);		}	}}

After you've filled out the edge arrays for every edge in the triangle, draw each span from the top to the bottom with something like this:
// Again, stripped down and simplified. No clipping is done in this example.// p1 and p2 should be the current entry into the edge arrays. Each entry into// the arrays corresponds to a scan line in the offscreen bitmap or window.// u and v are interpolated across the span from the interpolated u and v// coodinates in the edge arrays.// This can be optimized better and it should be inlined. This is just for// clarity.void DrawSpan(vertex p1,vertex p2){	float		u_step,v_step;	float		u,v,uu,vv;	unsigned char	tr,tg,tb,ta;	long		width,x,y,tu,tv,offset;	unsigned long	*buffer;	if(p1.sy < 0)		return;	if(p2.sx < p1.sx)		SwapPoints(&p1,&p2); // Swaps all of the values in the vertex	width = p2.sx - p1.sx;	if(width < 1)		return;	u_step = (p2.u - p1.u) / (float)width;	v_step = (p2.v - p1.v) / (float)width;	u = p1.u;	v = p1.v;	x = p1.sx;	y = p1.sy;	buffer = &ptPixels[(y * SCREEN_WIDTH) + x]; // Pointer to offscreen buffer data	// "tex" is some sort of texture structure.	// The code below is assuming a 32-bit texture.	while(width--)	{		if(u < 0)			u = 0;		if(u > 1.0)			u = 1.0;		if(v < 0)			v = 0;		if(v > 1.0)			v = 1.0;		tu = (long)(u * tex->width);		tv = (long)(v * tex->width);		offset = ((tv * tex->width) + tu) * 4;// Multiply by 4 since tex->imageData is of type unsigned char and there are four entries per pixel.		tr = (unsigned char)tex->imageData[offset];		tg = (unsigned char)tex->imageData[offset + 1];		tb = (unsigned char)tex->imageData[offset + 2];		ta = (unsigned char)tex->imageData[offset + 3];		*buffer = (ta << 24) | (tr << 16) | (tg << 8) | tb;		buffer++;		u += u_step;		v += v_step;	}}

1. 1
Rutin
25
2. 2
3. 3
4. 4
JoeJ
18
5. 5

• 14
• 14
• 11
• 11
• 9
• ### Forum Statistics

• Total Topics
631757
• Total Posts
3002131
×

## Important Information

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!