Sign in to follow this  

Interpolating on the face of a trinagle.

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

If you intended to correct an error in the post then please contact us.

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 this post


Link to post
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;
}
}


Share this post


Link to post
Share on other sites

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

If you intended to correct an error in the post then please contact us.

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this