# Interpolating on the face of a trinagle.

## Recommended Posts

redeemer90    138
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
szecs    2990

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

##### Share on other sites
MarkS    180
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;	}}