Interpolating on the face of a trinagle.
Author
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
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:
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:
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; }}This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement