home *** CD-ROM | disk | FTP | other *** search
/ Graphics Programming Black Book (Special Edition) / BlackBook.bin / disk1 / source / chapter69 / l69-1.c
Encoding:
Text File  |  1997-06-18  |  3.4 KB  |  112 lines
  1. // Quake's recursive subdivision triangle rasterizer; draws all 
  2. // pixels in a triangle other than the vertices by splitting an 
  3. // edge to form a new vertex, drawing the vertex, and recursively
  4. // processing each of the two new triangles formed by using the
  5. // new vertex. Results are less accurate than from a precise
  6. // affine or perspective texture mapper, and drawing boundaries 
  7. // are not identical to those of a precise polygon drawer, although
  8. // they are consistent between adjacent polygons drawn with this
  9. // technique.
  10. //
  11. // Invented and implemented by John Carmack of id Software.
  12.  
  13. void D_PolysetRecursiveTriangle (int *lp1, int *lp2, int *lp3)
  14. {
  15.     int    *temp;
  16.     int    d;
  17.     int    new[6];
  18.     int    z;
  19.     short  *zbuf;
  20.  
  21. // try to find an edge that's more than one pixel long in x or y
  22.     d = lp2[0] - lp1[0];
  23.     if (d < -1 || d > 1)
  24.         goto split;
  25.     d = lp2[1] - lp1[1];
  26.     if (d < -1 || d > 1)
  27.         goto split;
  28.     d = lp3[0] - lp2[0];
  29.     if (d < -1 || d > 1)
  30.         goto split2;
  31.     d = lp3[1] - lp2[1];
  32.     if (d < -1 || d > 1)
  33.         goto split2;
  34.     d = lp1[0] - lp3[0];
  35.     if (d < -1 || d > 1)
  36.         goto split3;
  37.     d = lp1[1] - lp3[1];
  38.     if (d < -1 || d > 1)
  39.     {
  40. split3:
  41.     // shuffle points so first edge is edge to split
  42.         temp = lp1;
  43.         lp1 = lp3;
  44.         lp3 = lp2;
  45.         lp2 = temp;
  46.         goto split;
  47.     }
  48.  
  49.     return;         // no pixels left to fill in triangle
  50.  
  51. split2:
  52. // shuffle points so first edge is edge to split
  53.     temp = lp1;
  54.     lp1 = lp2;
  55.     lp2 = lp3;
  56.     lp3 = temp;
  57.  
  58. split:
  59. // split first edge screen x, screen y, texture s, texture t, and z
  60. // to form a new vertex.  Lighting (index 4) is ignored; the 
  61. // difference between interpolating lighting and using the same 
  62. // shading for the entire triangle is unnoticeable for small 
  63. // triangles, so we just use the lighting for the first vertex of 
  64. // the original triangle (which was used during set-up to set 
  65. // d_colormap, used below to look up lit texels)
  66.     new[0] = (lp1[0] + lp2[0]) >> 1;        // split screen x
  67.     new[1] = (lp1[1] + lp2[1]) >> 1;        // split screen y
  68.     new[2] = (lp1[2] + lp2[2]) >> 1;        // split texture s
  69.     new[3] = (lp1[3] + lp2[3]) >> 1;        // split texture t
  70.     new[5] = (lp1[5] + lp2[5]) >> 1;        // split z
  71.  
  72. // draw the point if splitting a leading edge
  73.     if (lp2[1] > lp1[1])
  74.         goto nodraw;
  75.     if ((lp2[1] == lp1[1]) && (lp2[0] < lp1[0]))
  76.         goto nodraw;
  77.  
  78.  
  79.     z = new[5]>>16;
  80.  
  81. // point to the pixel's z-buffer entry, looking up the scanline start 
  82. // address based on screen y and adding in the screen x coordinate
  83.     zbuf = zspantable[new[1]] + new[0];
  84.  
  85. // draw the split vertex if it's not obscured by something nearer, as 
  86. // indicated by the z-buffer
  87.     if (z >= *zbuf)
  88.     {
  89.         int     pix;
  90.         
  91.     // set the z-buffer to the new pixel's distance
  92.         *zbuf = z;
  93.  
  94.     // get the texel from the model's skin bitmap, according to 
  95.     // the s and t texture coordinates, and translate it through 
  96.     // the lighting look-up table set according to the first 
  97.     // vertex for the original (top-level) triangle.  Both s and
  98.     // t are in 16.16 format
  99.         pix = d_pcolormap[skintable[new[3]>>16][new[2]>>16]];
  100.  
  101.     // draw the pixel, looking up the scanline start address 
  102.     // based on screen y and adding in the screen x coordinate
  103.         d_viewbuffer[d_scantable[new[1]] + new[0]] = pix;
  104.     }
  105.  
  106. nodraw:
  107. // recursively draw the two new triangles we created by adding the 
  108. // split vertex
  109.     D_PolysetRecursiveTriangle (lp3, lp1, new);
  110.     D_PolysetRecursiveTriangle (lp3, new, lp2);
  111. }
  112.