/*************************************************************************** File: tri_rast.cpp Created: 02/20/2001 Author: Maxim Garber Computer Science Department University of North Carolina - Chapel Hill garber@cs.unc.edu Description: Contains a function to rasterize a flat shaded triangle to the screen. Part of soft_gl. ----------------------------------------------------------------------------. Copyright 2001 Maxim Garber *****************************************************************************/ #include #include #define X 0 #define Y 1 #define Z 2 #define PIXEL_OFFSET 0.5f #define EPSILON 0.05 //#define EPSILON FLT_EPSILON // checks if two floats are equal bool fEqual(float a, float b) { return (fabs(a - b) < EPSILON); } //---------------------------------------------------------------------------- // Given 3D triangle ABC in screen space with clipped coordinates within the following // bounds: x in [0,W], y in [0,H], z in [0,1]. The origin for (x,y) is in the bottom // left corner of the pixel grid. z=0 is the near plane and z=1 is the far plane, // so lesser values are closer. The coordinates of the pixels are evenly spaced // in x and y 1 units apart starting at the bottom-left pixel with coords // (0.5,0.5). In other words, the pixel sample point is in the center of the // rectangular grid cell containing the pixel sample. The framebuffer has // dimensions width x height (WxH). The Color buffer is a 1D array (row-major // order) with 3 unsigned chars per pixel (24-bit color). The Depth buffer is // a 1D array (also row-major order) with a float value per pixel // For a pixel location (x,y) we can obtain // the Color and Depth array locations as: Color[(((int)y)*W+((int)x))*3] // (for the red value, green is offset +1, and blue is offset +2 and // Depth[((int)y)*W+((int)x)]. Fills the pixels contained in the triangle // with the global current color and the properly linearly interpolated depth // value (performs Z-buffer depth test before writing new pixel). // Pixel samples that lie inside the triangle edges are filled with // a bias towards the minimum values (samples that lie exactly on a triangle // edge are filled only for minimum x values along a horizontal span and for // minimum y values, samples lying on max values are not filled). //--------------------------------------------------------------------------- void RasterizeTriangle(unsigned char *Color, float *Depth, const int W, const int H, float A[3], float B[3], float C[3], unsigned char CurrentColor[3]) { // flags which get set to true as we scan passed the two other // vertices in the triangle bool passedV2 =false, passedV3 = false; // arrange points so that v1 is the one with smallest y value // (and left most in case of tie), and v2 and v3 follow in CCW order. float *v1 = A, *v2 = B, *v3 = C; if(v1[Y] > B[Y] || (v1[Y] == B[Y] && v1[X] > B[X])) {v1 = B; v2 = C; v3 = A;} if(v1[Y] > C[Y] || (v1[Y] == C[Y] && v1[X] > C[X])) {v1 = C; v2 = A; v3 = B;} // test winding order and fix it if it is CW if((v1[X]*v2[Y]*v3[Z] + v1[Z]*v2[X]*v3[Y] + v1[Y]*v2[Z]*v3[X]) - (v1[Z]*v2[Y]*v3[X] + v1[X]*v2[Z]*v3[Y] + v1[Y]*v2[X]*v3[Z]) < 0) { float *temp = v3; v3 = v2; v2 = temp; } // integer height of scan line above v1 int scanLine = (int) v1[Y]; float scanLineY = scanLine + PIXEL_OFFSET; if (v1[Y] > scanLineY){scanLine++, scanLineY += 1;} // construct values which track the left edge of triangle // all slopes taken along the Y direction float leftX, leftZ, leftXSlope, leftZSlope; if (!fEqual(v1[Y], v3[Y]) && (scanLineY < v3[Y])) { leftXSlope = (v1[X] - v3[X]) / (v1[Y] - v3[Y]); leftZSlope = (v1[Z] - v3[Z]) / (v1[Y] - v3[Y]); leftX = v1[X] + leftXSlope * (scanLineY - v1[Y]); leftZ = v1[Z] + leftZSlope * (scanLineY - v1[Y]); } else // left edge is either horizontal => infinite slope // or the intercept is above the scan line { leftXSlope = (v3[X] - v2[X]) / (v3[Y] - v2[Y]); leftZSlope = (v3[Z] - v2[Z]) / (v3[Y] - v2[Y]); leftX = v3[X] + leftXSlope * (scanLineY - v3[Y]); leftZ = v3[Z] + leftZSlope * (scanLineY - v3[Y]); passedV3 = true; } // construct values which track the right edge of triangle // all slopes taken along the Y direction float rightX, rightZ, rightXSlope, rightZSlope; if(!fEqual(v1[Y], v2[Y]) && (scanLineY < v2[Y])) // right is not horizontal { rightXSlope = (v1[X] - v2[X]) / (v1[Y] - v2[Y]); rightZSlope = (v1[Z] - v2[Z]) / (v1[Y] - v2[Y]); rightX = v1[X] + rightXSlope * (scanLineY - v1[Y]); rightZ = v1[Z] + rightZSlope * (scanLineY - v1[Y]); } else // right edge is either horizontal => infinite slope // or the intercept is above the scanline { rightXSlope = (v2[X] - v3[X]) / (v2[Y] - v3[Y]); rightZSlope = (v2[Z] - v3[Z]) / (v2[Y] - v3[Y]); rightX = v2[X] + rightXSlope * (scanLineY - v2[Y]); rightZ = v2[Z] + rightZSlope * (scanLineY - v2[Y]); passedV2 =true; } // variables used in the inner loop for filling a scan line interval int startFill, endFill; // start and end of fill region on the scan line float pixelZ, scanZSlope; // pixel Z and Z-slope across the scan line // loop until we scan past the other two vertices in the triangle while (!(passedV2 && passedV3)){ startFill = (int) (leftX + PIXEL_OFFSET); if(fEqual(startFill,leftX + PIXEL_OFFSET)) startFill--; // minimum biasing endFill = (int) (rightX - PIXEL_OFFSET); if(endFill >= rightX - PIXEL_OFFSET) endFill--; // minimum biasing // find the Z value at the center of the first pixel and the // slope that Z changes relative to X along the scan line scanZSlope = (leftZ - rightZ) / (leftX - rightX); pixelZ = leftZ + scanZSlope * (startFill + PIXEL_OFFSET - leftX); // fill the scan line interval for(int pixel = scanLine*W+startFill; pixel <= scanLine*W+endFill; pixel++){ if(pixelZ < Depth[pixel]) { Depth[pixel] = pixelZ; Color[pixel*3] = CurrentColor[0]; Color[pixel*3 + 1] = CurrentColor[1]; Color[pixel*3 + 2] = CurrentColor[2]; } // increment Z for next pixel pixelZ += scanZSlope; } // move to next scan line scanLine++; scanLineY = scanLine + PIXEL_OFFSET; // update slope and x intercept for next iteration // requires a check if we pass a vertex in which case the slope changes if (scanLineY <= v3[Y]) { leftX += leftXSlope; leftZ += leftZSlope; } if (scanLineY >= v3[Y]) { passedV3 = true; if(!fEqual(v3[Y],v2[Y])) { leftXSlope = (v3[X] - v2[X]) / (v3[Y] - v2[Y]); leftZSlope = (v3[Z] - v2[Z]) / (v3[Y] - v2[Y]); } if (scanLineY > v3[Y]) { if(fEqual(v3[Y],v2[Y])) return; leftX = v3[X] + leftXSlope * (scanLineY - v3[Y]); leftZ = v3[Z] + leftZSlope * (scanLineY - v3[Y]); } } if (scanLineY <= v2[Y]) { rightX = rightX + rightXSlope; rightZ = rightZ + rightZSlope; } if (scanLineY >= v2[Y]) { passedV2 = true; if(!fEqual(v3[Y],v2[Y])) { rightXSlope = (v2[X] - v3[X]) / (v2[Y] - v3[Y]); rightZSlope = (v2[Z] - v3[Z]) / (v2[Y] - v3[Y]); } if (scanLineY > v2[Y]) { if(fEqual(v3[Y],v2[Y])) return; rightX = v2[X] + rightXSlope * (scanLineY - v2[Y]); rightZ = v2[Z] + rightZSlope * (scanLineY - v2[Y]); } } } }