home *** CD-ROM | disk | FTP | other *** search
/ Magazyn Amiga 5 / MA_Cover_5.iso / ppc / mesa / src / tritemp.h < prev    next >
Encoding:
Text File  |  1998-01-31  |  30.8 KB  |  885 lines
  1. /* $Id: tritemp.h,v 1.16 1997/09/18 01:08:10 brianp Exp $ */
  2.  
  3. /*
  4.  * Mesa 3-D graphics library
  5.  * Version:  2.4
  6.  * Copyright (C) 1995-1997  Brian Paul
  7.  *
  8.  * This library is free software; you can redistribute it and/or
  9.  * modify it under the terms of the GNU Library General Public
  10.  * License as published by the Free Software Foundation; either
  11.  * version 2 of the License, or (at your option) any later version.
  12.  *
  13.  * This library is distributed in the hope that it will be useful,
  14.  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  15.  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  16.  * Library General Public License for more details.
  17.  *
  18.  * You should have received a copy of the GNU Library General Public
  19.  * License along with this library; if not, write to the Free
  20.  * Software Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
  21.  */
  22.  
  23.  
  24. /*
  25.  * $Log: tritemp.h,v $
  26.  * Revision 1.16  1997/09/18 01:08:10  brianp
  27.  * fixed S_SCALE / T_SCALE mix-up
  28.  *
  29.  * Revision 1.15  1997/08/22 01:53:03  brianp
  30.  * another attempt at fixing under/overflow errors
  31.  *
  32.  * Revision 1.14  1997/08/13 02:10:13  brianp
  33.  * added code to prevent over/underflow (Guido Jansen, Magnus Lundin)
  34.  *
  35.  * Revision 1.13  1997/06/20 02:52:49  brianp
  36.  * changed color components from GLfixed to GLubyte
  37.  *
  38.  * Revision 1.12  1997/03/14 00:25:02  brianp
  39.  * fixed unitialized memory read, contributed by Tom Schmidt
  40.  *
  41.  * Revision 1.11  1997/02/09 18:51:10  brianp
  42.  * fixed typo in texture R interpolation code
  43.  *
  44.  * Revision 1.10  1996/12/20 23:12:23  brianp
  45.  * another attempt at preventing color interpolation over/underflow
  46.  *
  47.  * Revision 1.9  1996/12/18 20:38:25  brianp
  48.  * commented out unused zp declaration
  49.  *
  50.  * Revision 1.8  1996/12/12 22:37:49  brianp
  51.  * projective textures didn't work right
  52.  *
  53.  * Revision 1.7  1996/11/02 06:17:37  brianp
  54.  * fixed some float/int roundoff and over/underflow errors (hopefully)
  55.  *
  56.  * Revision 1.6  1996/10/01 04:13:09  brianp
  57.  * fixed Z interpolation for >16-bit depth buffer
  58.  * added color underflow error check
  59.  *
  60.  * Revision 1.5  1996/09/27 01:32:59  brianp
  61.  * removed unused variables
  62.  *
  63.  * Revision 1.4  1996/09/18 01:03:43  brianp
  64.  * tightened threshold for culling by area
  65.  *
  66.  * Revision 1.3  1996/09/15 14:19:16  brianp
  67.  * now use GLframebuffer and GLvisual
  68.  *
  69.  * Revision 1.2  1996/09/14 06:41:38  brianp
  70.  * perspective correct texture code wasn't sub-pixel accurate (Doug Rabson)
  71.  *
  72.  * Revision 1.1  1996/09/13 01:38:16  brianp
  73.  * Initial revision
  74.  *
  75.  */
  76.  
  77.  
  78. /*
  79.  * Triangle Rasterizer Template
  80.  *
  81.  * This file is #include'd to generate custom triangle rasterizers.
  82.  *
  83.  * The following macros may be defined to indicate what auxillary information
  84.  * must be interplated across the triangle:
  85.  *    INTERP_Z      - if defined, interpolate Z values
  86.  *    INTERP_RGB    - if defined, interpolate RGB values
  87.  *    INTERP_ALPHA  - if defined, interpolate Alpha values
  88.  *    INTERP_INDEX  - if defined, interpolate color index values
  89.  *    INTERP_ST     - if defined, interpolate integer ST texcoords
  90.  *                         (fast, simple 2-D texture mapping)
  91.  *    INTERP_STW    - if defined, interpolate float ST texcoords and W
  92.  *                         (2-D texture maps with perspective correction)
  93.  *    INTERP_UV     - if defined, interpolate float UV texcoords too
  94.  *                         (for 3-D, 4-D? texture maps)
  95.  *
  96.  * When one can directly address pixels in the color buffer the following
  97.  * macros can be defined and used to compute pixel addresses during
  98.  * rasterization (see pRow):
  99.  *    PIXEL_TYPE          - the datatype of a pixel (GLubyte, GLushort, GLuint)
  100.  *    BYTES_PER_ROW       - number of bytes per row in the color buffer
  101.  *    PIXEL_ADDRESS(X,Y)  - returns the address of pixel at (X,Y) where
  102.  *                          Y==0 at bottom of screen and increases upward.
  103.  *
  104.  * Optionally, one may provide one-time setup code per triangle:
  105.  *    SETUP_CODE    - code which is to be executed once per triangle
  106.  * 
  107.  * The following macro MUST be defined:
  108.  *    INNER_LOOP(LEFT,RIGHT,Y) - code to write a span of pixels.
  109.  *        Something like:
  110.  *
  111.  *                    for (x=LEFT; x<RIGHT;x++) {
  112.  *                       put_pixel(x,Y);
  113.  *                       // increment fixed point interpolants
  114.  *                    }
  115.  *
  116.  * This code was designed for the origin to be in the lower-left corner.
  117.  *
  118.  * Inspired by triangle rasterizer code written by Allen Akin.  Thanks Allen!
  119.  */
  120.  
  121.  
  122. /*void triangle( GLcontext *ctx, GLuint v0, GLuint v1, GLuint v2, GLuint pv )*/
  123. {
  124.    typedef struct {
  125.         GLint v0, v1;     /* Y(v0) < Y(v1) */
  126.         GLfloat dx;     /* X(v1) - X(v0) */
  127.         GLfloat dy;     /* Y(v1) - Y(v0) */
  128.         GLfixed fdxdy;  /* dx/dy in fixed-point */
  129.         GLfixed fsx;    /* first sample point x coord */
  130.         GLfixed fsy;
  131.         GLfloat adjy;   /* adjust from v[0]->fy to fsy, scaled */
  132.         GLint lines;    /* number of lines to be sampled on this edge */
  133.         GLfixed fx0;    /* fixed pt X of lower endpoint */
  134.    } EdgeT;
  135.  
  136.    struct vertex_buffer *VB = ctx->VB;
  137.    EdgeT eMaj, eTop, eBot;
  138.    GLfloat oneOverArea;
  139.    int vMin, vMid, vMax;       /* vertex indexes:  Y(vMin)<=Y(vMid)<=Y(vMax) */
  140.  
  141.    /* find the order of the 3 vertices along the Y axis */
  142.    {
  143.       GLfloat y0 = VB->Win[v0][1];
  144.       GLfloat y1 = VB->Win[v1][1];
  145.       GLfloat y2 = VB->Win[v2][1];
  146.  
  147.       if (y0<=y1) {
  148.          if (y1<=y2) {
  149.             vMin = v0;   vMid = v1;   vMax = v2;   /* y0<=y1<=y2 */
  150.          }
  151.          else if (y2<=y0) {
  152.             vMin = v2;   vMid = v0;   vMax = v1;   /* y2<=y0<=y1 */
  153.          }
  154.          else {
  155.             vMin = v0;   vMid = v2;   vMax = v1;   /* y0<=y2<=y1 */
  156.          }
  157.       }
  158.       else {
  159.          if (y0<=y2) {
  160.             vMin = v1;   vMid = v0;   vMax = v2;   /* y1<=y0<=y2 */
  161.          }
  162.          else if (y2<=y1) {
  163.             vMin = v2;   vMid = v1;   vMax = v0;   /* y2<=y1<=y0 */
  164.          }
  165.          else {
  166.             vMin = v1;   vMid = v2;   vMax = v0;   /* y1<=y2<=y0 */
  167.          }
  168.       }
  169.    }
  170.  
  171.    /* vertex/edge relationship */
  172.    eMaj.v0 = vMin;   eMaj.v1 = vMax;   /*TODO: .v1's not needed */
  173.    eTop.v0 = vMid;   eTop.v1 = vMax;
  174.    eBot.v0 = vMin;   eBot.v1 = vMid;
  175.  
  176.    /* compute deltas for each edge:  vertex[v1] - vertex[v0] */
  177.    eMaj.dx = VB->Win[vMax][0] - VB->Win[vMin][0];
  178.    eMaj.dy = VB->Win[vMax][1] - VB->Win[vMin][1];
  179.    eTop.dx = VB->Win[vMax][0] - VB->Win[vMid][0];
  180.    eTop.dy = VB->Win[vMax][1] - VB->Win[vMid][1];
  181.    eBot.dx = VB->Win[vMid][0] - VB->Win[vMin][0];
  182.    eBot.dy = VB->Win[vMid][1] - VB->Win[vMin][1];
  183.  
  184.    /* compute oneOverArea */
  185.    {
  186.       GLfloat area = eMaj.dx * eBot.dy - eBot.dx * eMaj.dy;
  187.       if (area>-0.05f && area<0.05f) {
  188.          return;  /* very small; CULLED */
  189.       }
  190.       oneOverArea = 1.0F / area;
  191.    }
  192.  
  193.    /* Edge setup.  For a triangle strip these could be reused... */
  194.    {
  195.       /* fixed point Y coordinates */
  196.       GLfixed vMin_fx = FloatToFixed(VB->Win[vMin][0] + 0.5F);
  197.       GLfixed vMin_fy = FloatToFixed(VB->Win[vMin][1] - 0.5F);
  198.       GLfixed vMid_fx = FloatToFixed(VB->Win[vMid][0] + 0.5F);
  199.       GLfixed vMid_fy = FloatToFixed(VB->Win[vMid][1] - 0.5F);
  200.       GLfixed vMax_fy = FloatToFixed(VB->Win[vMax][1] - 0.5F);
  201.  
  202.       eMaj.fsy = FixedCeil(vMin_fy);
  203.       eMaj.lines = FixedToInt(vMax_fy + FIXED_ONE - FIXED_EPSILON - eMaj.fsy);
  204.       if (eMaj.lines > 0) {
  205.          GLfloat dxdy = eMaj.dx / eMaj.dy;
  206.          eMaj.fdxdy = SignedFloatToFixed(dxdy);
  207.          eMaj.adjy = (GLfloat) (eMaj.fsy - vMin_fy);  /* SCALED! */
  208.          eMaj.fx0 = vMin_fx;
  209.          eMaj.fsx = eMaj.fx0 + (GLfixed) (eMaj.adjy * dxdy);
  210.       }
  211.       else {
  212.          return;  /*CULLED*/
  213.       }
  214.  
  215.       eTop.fsy = FixedCeil(vMid_fy);
  216.       eTop.lines = FixedToInt(vMax_fy + FIXED_ONE - FIXED_EPSILON - eTop.fsy);
  217.       if (eTop.lines > 0) {
  218.          GLfloat dxdy = eTop.dx / eTop.dy;
  219.          eTop.fdxdy = SignedFloatToFixed(dxdy);
  220.          eTop.adjy = (GLfloat) (eTop.fsy - vMid_fy); /* SCALED! */
  221.          eTop.fx0 = vMid_fx;
  222.          eTop.fsx = eTop.fx0 + (GLfixed) (eTop.adjy * dxdy);
  223.       }
  224.  
  225.       eBot.fsy = FixedCeil(vMin_fy);
  226.       eBot.lines = FixedToInt(vMid_fy + FIXED_ONE - FIXED_EPSILON - eBot.fsy);
  227.       if (eBot.lines > 0) {
  228.          GLfloat dxdy = eBot.dx / eBot.dy;
  229.          eBot.fdxdy = SignedFloatToFixed(dxdy);
  230.          eBot.adjy = (GLfloat) (eBot.fsy - vMin_fy);  /* SCALED! */
  231.          eBot.fx0 = vMin_fx;
  232.          eBot.fsx = eBot.fx0 + (GLfixed) (eBot.adjy * dxdy);
  233.       }
  234.    }
  235.  
  236.    /*
  237.     * Conceptually, we view a triangle as two subtriangles
  238.     * separated by a perfectly horizontal line.  The edge that is
  239.     * intersected by this line is one with maximal absolute dy; we
  240.     * call it a ``major'' edge.  The other two edges are the
  241.     * ``top'' edge (for the upper subtriangle) and the ``bottom''
  242.     * edge (for the lower subtriangle).  If either of these two
  243.     * edges is horizontal or very close to horizontal, the
  244.     * corresponding subtriangle might cover zero sample points;
  245.     * we take care to handle such cases, for performance as well
  246.     * as correctness.
  247.     *
  248.     * By stepping rasterization parameters along the major edge,
  249.     * we can avoid recomputing them at the discontinuity where
  250.     * the top and bottom edges meet.  However, this forces us to
  251.     * be able to scan both left-to-right and right-to-left. 
  252.     * Also, we must determine whether the major edge is at the
  253.     * left or right side of the triangle.  We do this by
  254.     * computing the magnitude of the cross-product of the major
  255.     * and top edges.  Since this magnitude depends on the sine of
  256.     * the angle between the two edges, its sign tells us whether
  257.     * we turn to the left or to the right when travelling along
  258.     * the major edge to the top edge, and from this we infer
  259.     * whether the major edge is on the left or the right.
  260.     *
  261.     * Serendipitously, this cross-product magnitude is also a
  262.     * value we need to compute the iteration parameter
  263.     * derivatives for the triangle, and it can be used to perform
  264.     * backface culling because its sign tells us whether the
  265.     * triangle is clockwise or counterclockwise.  In this code we
  266.     * refer to it as ``area'' because it's also proportional to
  267.     * the pixel area of the triangle.
  268.     */
  269.  
  270.    {
  271.       GLint ltor;               /* true if scanning left-to-right */
  272. #if INTERP_Z
  273.       GLfloat dzdx, dzdy;      GLfixed fdzdx;
  274. #endif
  275. #if INTERP_RGB
  276.       GLfloat drdx, drdy;      GLfixed fdrdx;
  277.       GLfloat dgdx, dgdy;      GLfixed fdgdx;
  278.       GLfloat dbdx, dbdy;      GLfixed fdbdx;
  279. #endif
  280. #if INTERP_ALPHA
  281.       GLfloat dadx, dady;      GLfixed fdadx;
  282. #endif
  283. #if INTERP_INDEX
  284.       GLfloat didx, didy;      GLfixed fdidx;
  285. #endif
  286. #if INTERP_ST
  287.       GLfloat dsdx, dsdy;      GLfixed fdsdx;
  288.       GLfloat dtdx, dtdy;      GLfixed fdtdx;
  289. #endif
  290. #if INTERP_STW
  291.       GLfloat dsdx, dsdy;
  292.       GLfloat dtdx, dtdy;
  293.       GLfloat dwdx, dwdy;
  294. #endif
  295. #if INTERP_UV
  296.       GLfloat dudx, dudy;
  297.       GLfloat dvdx, dvdy;
  298. #endif
  299.  
  300.       /*
  301.        * Execute user-supplied setup code
  302.        */
  303. #ifdef SETUP_CODE
  304.       SETUP_CODE
  305. #endif
  306.  
  307.       ltor = (oneOverArea < 0.0F);
  308.  
  309.       /* compute d?/dx and d?/dy derivatives */
  310. #if INTERP_Z
  311.       {
  312.          GLfloat eMaj_dz, eBot_dz;
  313.          eMaj_dz = VB->Win[vMax][2] - VB->Win[vMin][2];
  314.          eBot_dz = VB->Win[vMid][2] - VB->Win[vMin][2];
  315.          dzdx = oneOverArea * (eMaj_dz * eBot.dy - eMaj.dy * eBot_dz);
  316.          if (dzdx>DEPTH_SCALE || dzdx<-DEPTH_SCALE) {
  317.             /* probably a sliver triangle */
  318.             dzdx = 0.0;
  319.             dzdy = 0.0;
  320.          }
  321.          else {
  322.             dzdy = oneOverArea * (eMaj.dx * eBot_dz - eMaj_dz * eBot.dx);
  323.          }
  324. #if DEPTH_BITS==16
  325.          fdzdx = SignedFloatToFixed(dzdx);
  326. #else
  327.          fdzdx = (GLint) dzdx;
  328. #endif
  329.       }
  330. #endif
  331. #if INTERP_RGB
  332.       {
  333.          GLfloat eMaj_dr, eBot_dr;
  334.          eMaj_dr = (GLint) VB->Color[vMax][0] - (GLint) VB->Color[vMin][0];
  335.          eBot_dr = (GLint) VB->Color[vMid][0] - (GLint) VB->Color[vMin][0];
  336.          drdx = oneOverArea * (eMaj_dr * eBot.dy - eMaj.dy * eBot_dr);
  337.          fdrdx = SignedFloatToFixed(drdx);
  338.          drdy = oneOverArea * (eMaj.dx * eBot_dr - eMaj_dr * eBot.dx);
  339.       }
  340.       {
  341.          GLfloat eMaj_dg, eBot_dg;
  342.          eMaj_dg = (GLint) VB->Color[vMax][1] - (GLint) VB->Color[vMin][1];
  343.          eBot_dg = (GLint) VB->Color[vMid][1] - (GLint) VB->Color[vMin][1];
  344.          dgdx = oneOverArea * (eMaj_dg * eBot.dy - eMaj.dy * eBot_dg);
  345.          fdgdx = SignedFloatToFixed(dgdx);
  346.          dgdy = oneOverArea * (eMaj.dx * eBot_dg - eMaj_dg * eBot.dx);
  347.       }
  348.       {
  349.          GLfloat eMaj_db, eBot_db;
  350.          eMaj_db = (GLint) VB->Color[vMax][2] - (GLint) VB->Color[vMin][2];
  351.          eBot_db = (GLint) VB->Color[vMid][2] - (GLint) VB->Color[vMin][2];
  352.          dbdx = oneOverArea * (eMaj_db * eBot.dy - eMaj.dy * eBot_db);
  353.          fdbdx = SignedFloatToFixed(dbdx);
  354.          dbdy = oneOverArea * (eMaj.dx * eBot_db - eMaj_db * eBot.dx);
  355.       }
  356. #endif
  357. #if INTERP_ALPHA
  358.       {
  359.          GLfloat eMaj_da, eBot_da;
  360.          eMaj_da = (GLint) VB->Color[vMax][3] - (GLint) VB->Color[vMin][3];
  361.          eBot_da = (GLint) VB->Color[vMid][3] - (GLint) VB->Color[vMin][3];
  362.          dadx = oneOverArea * (eMaj_da * eBot.dy - eMaj.dy * eBot_da);
  363.          fdadx = SignedFloatToFixed(dadx);
  364.          dady = oneOverArea * (eMaj.dx * eBot_da - eMaj_da * eBot.dx);
  365.       }
  366. #endif
  367. #if INTERP_INDEX
  368.       {
  369.          GLfloat eMaj_di, eBot_di;
  370.          eMaj_di = (GLint) VB->Index[vMax] - (GLint) VB->Index[vMin];
  371.          eBot_di = (GLint) VB->Index[vMid] - (GLint) VB->Index[vMin];
  372.          didx = oneOverArea * (eMaj_di * eBot.dy - eMaj.dy * eBot_di);
  373.          fdidx = SignedFloatToFixed(didx);
  374.          didy = oneOverArea * (eMaj.dx * eBot_di - eMaj_di * eBot.dx);
  375.       }
  376. #endif
  377. #if INTERP_ST
  378.       {
  379.          GLfloat eMaj_ds, eBot_ds;
  380.          eMaj_ds = (VB->TexCoord[vMax][0] - VB->TexCoord[vMin][0]) * S_SCALE;
  381.          eBot_ds = (VB->TexCoord[vMid][0] - VB->TexCoord[vMin][0]) * S_SCALE;
  382.          dsdx = oneOverArea * (eMaj_ds * eBot.dy - eMaj.dy * eBot_ds);
  383.          fdsdx = SignedFloatToFixed(dsdx);
  384.          dsdy = oneOverArea * (eMaj.dx * eBot_ds - eMaj_ds * eBot.dx);
  385.       }
  386.       {
  387.          GLfloat eMaj_dt, eBot_dt;
  388.          eMaj_dt = (VB->TexCoord[vMax][1] - VB->TexCoord[vMin][1]) * T_SCALE;
  389.          eBot_dt = (VB->TexCoord[vMid][1] - VB->TexCoord[vMin][1]) * T_SCALE;
  390.          dtdx = oneOverArea * (eMaj_dt * eBot.dy - eMaj.dy * eBot_dt);
  391.          fdtdx = SignedFloatToFixed(dtdx);
  392.          dtdy = oneOverArea * (eMaj.dx * eBot_dt - eMaj_dt * eBot.dx);
  393.       }
  394. #endif
  395. #if INTERP_STW
  396.       {
  397.          GLfloat wMax = 1.0F / VB->Clip[vMax][3];
  398.          GLfloat wMin = 1.0F / VB->Clip[vMin][3];
  399.          GLfloat wMid = 1.0F / VB->Clip[vMid][3];
  400.          GLfloat eMaj_dw, eBot_dw;
  401.          GLfloat eMaj_ds, eBot_ds;
  402.          GLfloat eMaj_dt, eBot_dt;
  403. #if INTERP_UV
  404.          GLfloat eMaj_du, eBot_du;
  405.          GLfloat eMaj_dv, eBot_dv;
  406. #endif
  407.          eMaj_dw = wMax - wMin;
  408.          eBot_dw = wMid - wMin;
  409.          dwdx = oneOverArea * (eMaj_dw * eBot.dy - eMaj.dy * eBot_dw);
  410.          dwdy = oneOverArea * (eMaj.dx * eBot_dw - eMaj_dw * eBot.dx);
  411.  
  412.          eMaj_ds = VB->TexCoord[vMax][0]*wMax - VB->TexCoord[vMin][0]*wMin;
  413.          eBot_ds = VB->TexCoord[vMid][0]*wMid - VB->TexCoord[vMin][0]*wMin;
  414.          dsdx = oneOverArea * (eMaj_ds * eBot.dy - eMaj.dy * eBot_ds);
  415.          dsdy = oneOverArea * (eMaj.dx * eBot_ds - eMaj_ds * eBot.dx);
  416.  
  417.          eMaj_dt = VB->TexCoord[vMax][1]*wMax - VB->TexCoord[vMin][1]*wMin;
  418.          eBot_dt = VB->TexCoord[vMid][1]*wMid - VB->TexCoord[vMin][1]*wMin;
  419.          dtdx = oneOverArea * (eMaj_dt * eBot.dy - eMaj.dy * eBot_dt);
  420.          dtdy = oneOverArea * (eMaj.dx * eBot_dt - eMaj_dt * eBot.dx);
  421. #if INTERP_UV
  422.          eMaj_du = VB->TexCoord[vMax][2]*wMax - VB->TexCoord[vMin][2]*wMin;
  423.          eBot_du = VB->TexCoord[vMid][2]*wMid - VB->TexCoord[vMin][2]*wMin;
  424.          dudx = oneOverArea * (eMaj_du * eBot.dy - eMaj.dy * eBot_du);
  425.          dudy = oneOverArea * (eMaj.dx * eBot_du - eMaj_du * eBot.dx);
  426.  
  427.          /* Note: don't divide V component by W */
  428.          eMaj_dv = VB->TexCoord[vMax][3] - VB->TexCoord[vMin][3];
  429.          eBot_dv = VB->TexCoord[vMid][3] - VB->TexCoord[vMin][3];
  430.          dvdx = oneOverArea * (eMaj_dv * eBot.dy - eMaj.dy * eBot_dv);
  431.          dvdy = oneOverArea * (eMaj.dx * eBot_dv - eMaj_dv * eBot.dx);
  432. #endif
  433.       }
  434. #endif
  435.  
  436.       /*
  437.        * We always sample at pixel centers.  However, we avoid
  438.        * explicit half-pixel offsets in this code by incorporating
  439.        * the proper offset in each of x and y during the
  440.        * transformation to window coordinates.
  441.        *
  442.        * We also apply the usual rasterization rules to prevent
  443.        * cracks and overlaps.  A pixel is considered inside a
  444.        * subtriangle if it meets all of four conditions: it is on or
  445.        * to the right of the left edge, strictly to the left of the
  446.        * right edge, on or below the top edge, and strictly above
  447.        * the bottom edge.  (Some edges may be degenerate.)
  448.        *
  449.        * The following discussion assumes left-to-right scanning
  450.        * (that is, the major edge is on the left); the right-to-left
  451.        * case is a straightforward variation.
  452.        *
  453.        * We start by finding the half-integral y coordinate that is
  454.        * at or below the top of the triangle.  This gives us the
  455.        * first scan line that could possibly contain pixels that are
  456.        * inside the triangle.
  457.        *
  458.        * Next we creep down the major edge until we reach that y,
  459.        * and compute the corresponding x coordinate on the edge. 
  460.        * Then we find the half-integral x that lies on or just
  461.        * inside the edge.  This is the first pixel that might lie in
  462.        * the interior of the triangle.  (We won't know for sure
  463.        * until we check the other edges.)
  464.        *
  465.        * As we rasterize the triangle, we'll step down the major
  466.        * edge.  For each step in y, we'll move an integer number
  467.        * of steps in x.  There are two possible x step sizes, which
  468.        * we'll call the ``inner'' step (guaranteed to land on the
  469.        * edge or inside it) and the ``outer'' step (guaranteed to
  470.        * land on the edge or outside it).  The inner and outer steps
  471.        * differ by one.  During rasterization we maintain an error
  472.        * term that indicates our distance from the true edge, and
  473.        * select either the inner step or the outer step, whichever
  474.        * gets us to the first pixel that falls inside the triangle.
  475.        *
  476.        * All parameters (z, red, etc.) as well as the buffer
  477.        * addresses for color and z have inner and outer step values,
  478.        * so that we can increment them appropriately.  This method
  479.        * eliminates the need to adjust parameters by creeping a
  480.        * sub-pixel amount into the triangle at each scanline.
  481.        */
  482.  
  483.       {
  484.          int subTriangle;
  485.          GLfixed fx, fxLeftEdge, fxRightEdge, fdxLeftEdge, fdxRightEdge;
  486.          GLfixed fdxOuter;
  487.          int idxOuter;
  488.          float dxOuter;
  489.          GLfixed fError, fdError;
  490.          float adjx, adjy;
  491.          GLfixed fy;
  492.          int iy;
  493. #ifdef PIXEL_ADDRESS
  494.          PIXEL_TYPE *pRow;
  495.          int dPRowOuter, dPRowInner;  /* offset in bytes */
  496. #endif
  497. #if INTERP_Z
  498.          GLdepth *zRow;
  499.          int dZRowOuter, dZRowInner;  /* offset in bytes */
  500.          GLfixed fz, fdzOuter, fdzInner;
  501. #endif
  502. #if INTERP_RGB
  503.          GLfixed fr, fdrOuter, fdrInner;
  504.          GLfixed fg, fdgOuter, fdgInner;
  505.          GLfixed fb, fdbOuter, fdbInner;
  506. #endif
  507. #if INTERP_ALPHA
  508.          GLfixed fa, fdaOuter, fdaInner;
  509. #endif
  510. #if INTERP_INDEX
  511.          GLfixed fi, fdiOuter, fdiInner;
  512. #endif
  513. #if INTERP_ST
  514.          GLfixed fs, fdsOuter, fdsInner;
  515.          GLfixed ft, fdtOuter, fdtInner;
  516. #endif
  517. #if INTERP_STW
  518.          GLfloat sLeft, dsOuter, dsInner;
  519.          GLfloat tLeft, dtOuter, dtInner;
  520.          GLfloat wLeft, dwOuter, dwInner;
  521. #endif
  522. #if INTERP_UV
  523.          GLfloat uLeft, duOuter, duInner;
  524.          GLfloat vLeft, dvOuter, dvInner;
  525. #endif
  526.  
  527.          for (subTriangle=0; subTriangle<=1; subTriangle++) {
  528.             EdgeT *eLeft, *eRight;
  529.             int setupLeft, setupRight;
  530.             int lines;
  531.  
  532.             if (subTriangle==0) {
  533.                /* bottom half */
  534.                if (ltor) {
  535.                   eLeft = &eMaj;
  536.                   eRight = &eBot;
  537.                   lines = eRight->lines;
  538.                   setupLeft = 1;
  539.                   setupRight = 1;
  540.                }
  541.                else {
  542.                   eLeft = &eBot;
  543.                   eRight = &eMaj;
  544.                   lines = eLeft->lines;
  545.                   setupLeft = 1;
  546.                   setupRight = 1;
  547.                }
  548.             }
  549.             else {
  550.                /* top half */
  551.                if (ltor) {
  552.                   eLeft = &eMaj;
  553.                   eRight = &eTop;
  554.                   lines = eRight->lines;
  555.                   setupLeft = 0;
  556.                   setupRight = 1;
  557.                }
  558.                else {
  559.                   eLeft = &eTop;
  560.                   eRight = &eMaj;
  561.                   lines = eLeft->lines;
  562.                   setupLeft = 1;
  563.                   setupRight = 0;
  564.                }
  565.                if (lines==0) return;
  566.             }
  567.  
  568.             if (setupLeft && eLeft->lines>0) {
  569.                GLint vLower;
  570.                GLfixed fsx = eLeft->fsx;
  571.                fx = FixedCeil(fsx);
  572.                fError = fx - fsx - FIXED_ONE;
  573.                fxLeftEdge = fsx - FIXED_EPSILON;
  574.                fdxLeftEdge = eLeft->fdxdy;
  575.                fdxOuter = FixedFloor(fdxLeftEdge - FIXED_EPSILON);
  576.                fdError = fdxOuter - fdxLeftEdge + FIXED_ONE;
  577.                idxOuter = FixedToInt(fdxOuter);
  578.                dxOuter = (float) idxOuter;
  579.  
  580.                fy = eLeft->fsy;
  581.                iy = FixedToInt(fy);
  582.  
  583.                adjx = (float)(fx - eLeft->fx0);  /* SCALED! */
  584.                adjy = eLeft->adjy;               /* SCALED! */
  585.  
  586.                vLower = eLeft->v0;
  587.  
  588. #ifdef PIXEL_ADDRESS
  589.                {
  590.                   pRow = PIXEL_ADDRESS( FixedToInt(fxLeftEdge), iy );
  591.                   dPRowOuter = -BYTES_PER_ROW + idxOuter * sizeof(PIXEL_TYPE);
  592.                   /* negative because Y=0 at bottom and increases upward */
  593.                }
  594. #endif
  595.                /*
  596.                 * Now we need the set of parameter (z, color, etc.) values at
  597.                 * the point (fx, fy).  This gives us properly-sampled parameter
  598.                 * values that we can step from pixel to pixel.  Furthermore,
  599.                 * although we might have intermediate results that overflow
  600.                 * the normal parameter range when we step temporarily outside
  601.                 * the triangle, we shouldn't overflow or underflow for any
  602.                 * pixel that's actually inside the triangle.
  603.                 */
  604.  
  605. #if INTERP_Z
  606.                {
  607.                   GLfloat z0, tmp;
  608.                   z0 = VB->Win[vLower][2] + ctx->PolygonZoffset;
  609. #if DEPTH_BITS==16
  610.                   /* interpolate fixed-pt values */
  611.                   tmp = (z0 * FIXED_SCALE + dzdx * adjx + dzdy * adjy) + FIXED_HALF;
  612.                   if (tmp < MAX_GLUINT_2)
  613.                      fz = (GLfixed) tmp;
  614.                   else
  615.                      fz = MAX_GLUINT_2;
  616.                   fdzOuter = SignedFloatToFixed(dzdy + dxOuter * dzdx);
  617. #else
  618.                   /* interpolate depth values exactly */
  619.                   fz = (GLint) (z0 + dzdx*FixedToFloat(adjx) + dzdy*FixedToFloat(adjy));
  620.                   fdzOuter = (GLint) (dzdy + dxOuter * dzdx);
  621. #endif
  622.                   zRow = Z_ADDRESS( ctx, FixedToInt(fxLeftEdge), iy );
  623.                   dZRowOuter = (ctx->Buffer->Width + idxOuter) * sizeof(GLdepth);
  624.                }
  625. #endif
  626. #if INTERP_RGB
  627.                fr = (GLfixed)(IntToFixed(VB->Color[vLower][0]) + drdx * adjx + drdy * adjy)
  628.                     + FIXED_HALF;
  629.                fdrOuter = SignedFloatToFixed(drdy + dxOuter * drdx);
  630.  
  631.                fg = (GLfixed)(IntToFixed(VB->Color[vLower][1]) + dgdx * adjx + dgdy * adjy)
  632.                     + FIXED_HALF;
  633.                fdgOuter = SignedFloatToFixed(dgdy + dxOuter * dgdx);
  634.  
  635.                fb = (GLfixed)(IntToFixed(VB->Color[vLower][2]) + dbdx * adjx + dbdy * adjy)
  636.                     + FIXED_HALF;
  637.                fdbOuter = SignedFloatToFixed(dbdy + dxOuter * dbdx);
  638. #endif
  639. #if INTERP_ALPHA
  640.                fa = (GLfixed)(IntToFixed(VB->Color[vLower][3]) + dadx * adjx + dady * adjy)
  641.                     + FIXED_HALF;
  642.                fdaOuter = SignedFloatToFixed(dady + dxOuter * dadx);
  643. #endif
  644. #if INTERP_INDEX
  645.                fi = (GLfixed)(VB->Index[vLower] * FIXED_SCALE + didx * adjx
  646.                               + didy * adjy) + FIXED_HALF;
  647.                fdiOuter = SignedFloatToFixed(didy + dxOuter * didx);
  648. #endif
  649. #if INTERP_ST
  650.                {
  651.                   GLfloat s0, t0;
  652.                   s0 = VB->TexCoord[vLower][0] * S_SCALE;
  653.                   fs = (GLfixed)(s0 * FIXED_SCALE + dsdx * adjx + dsdy * adjy) + FIXED_HALF;
  654.                   fdsOuter = SignedFloatToFixed(dsdy + dxOuter * dsdx);
  655.                   t0 = VB->TexCoord[vLower][1] * T_SCALE;
  656.                   ft = (GLfixed)(t0 * FIXED_SCALE + dtdx * adjx + dtdy * adjy) + FIXED_HALF;
  657.                   fdtOuter = SignedFloatToFixed(dtdy + dxOuter * dtdx);
  658.                }
  659. #endif
  660. #if INTERP_STW
  661.                {
  662.                   GLfloat w0 = 1.0F / VB->Clip[vLower][3];
  663.                   GLfloat s0, t0, u0, v0;
  664.                   wLeft = w0 + (dwdx * adjx + dwdy * adjy) * (1.0F/FIXED_SCALE);
  665.                   dwOuter = dwdy + dxOuter * dwdx;
  666.                   s0 = VB->TexCoord[vLower][0] * w0;
  667.                   sLeft = s0 + (dsdx * adjx + dsdy * adjy) * (1.0F/FIXED_SCALE);
  668.                   dsOuter = dsdy + dxOuter * dsdx;
  669.                   t0 = VB->TexCoord[vLower][1] * w0;
  670.                   tLeft = t0 + (dtdx * adjx + dtdy * adjy) * (1.0F/FIXED_SCALE);
  671.                   dtOuter = dtdy + dxOuter * dtdx;
  672. #if INTERP_UV
  673.                   u0 = VB->TexCoord[vLower][2] * w0;
  674.                   uLeft = u0 + (dudx * adjx + dudy * adjy) * (1.0F/FIXED_SCALE);
  675.                   duOuter = dudy + dxOuter * dudx;
  676.                   /* Note: don't divide V component by W */
  677.                   v0 = VB->TexCoord[vLower][3];
  678.                   vLeft = v0 + (dvdx * adjx + dvdy * adjy) * (1.0F/FIXED_SCALE);
  679.                   dvOuter = dvdy + dxOuter * dvdx;
  680. #endif
  681.                }
  682. #endif
  683.  
  684.             } /*if setupLeft*/
  685.  
  686.  
  687.             if (setupRight && eRight->lines>0) {
  688.                fxRightEdge = eRight->fsx - FIXED_EPSILON;
  689.                fdxRightEdge = eRight->fdxdy;
  690.             }
  691.  
  692.             if (lines==0) {
  693.                continue;
  694.             }
  695.  
  696.  
  697.             /* Rasterize setup */
  698. #ifdef PIXEL_ADDRESS
  699.             dPRowInner = dPRowOuter + sizeof(PIXEL_TYPE);
  700. #endif
  701. #if INTERP_Z
  702.             dZRowInner = dZRowOuter + sizeof(GLdepth);
  703.             fdzInner = fdzOuter + fdzdx;
  704. #endif
  705. #if INTERP_RGB
  706.             fdrInner = fdrOuter + fdrdx;
  707.             fdgInner = fdgOuter + fdgdx;
  708.             fdbInner = fdbOuter + fdbdx;
  709. #endif
  710. #if INTERP_ALPHA
  711.             fdaInner = fdaOuter + fdadx;
  712. #endif
  713. #if INTERP_INDEX
  714.             fdiInner = fdiOuter + fdidx;
  715. #endif
  716. #if INTERP_ST
  717.             fdsInner = fdsOuter + fdsdx;
  718.             fdtInner = fdtOuter + fdtdx;
  719. #endif
  720. #if INTERP_STW
  721.             dwInner = dwOuter + dwdx;
  722.             dsInner = dsOuter + dsdx;
  723.             dtInner = dtOuter + dtdx;
  724. #if INTERP_UV
  725.             duInner = duOuter + dudx;
  726.             dvInner = dvOuter + dvdx;
  727. #endif
  728. #endif
  729.  
  730.             while (lines>0) {
  731.                /* initialize the span interpolants to the leftmost value */
  732.                /* ff = fixed-pt fragment */
  733. #if INTERP_Z
  734.                GLfixed ffz = fz;
  735.                /*GLdepth *zp = zRow;*/
  736. #endif
  737. #if INTERP_RGB
  738.                GLfixed ffr = fr,  ffg = fg,  ffb = fb;
  739. #endif
  740. #if INTERP_ALPHA
  741.                GLfixed ffa = fa;
  742. #endif
  743. #if INTERP_INDEX
  744.                GLfixed ffi = fi;
  745. #endif
  746. #if INTERP_ST
  747.                GLfixed ffs = fs,  fft = ft;
  748. #endif
  749. #if INTERP_STW
  750.                GLfloat ss = sLeft,  tt = tLeft,  ww = wLeft;
  751. #endif
  752. #if INTERP_UV
  753.                GLfloat uu = uLeft,  vv = vLeft;
  754. #endif
  755.                GLint left = FixedToInt(fxLeftEdge);
  756.                GLint right = FixedToInt(fxRightEdge);
  757.  
  758. #if INTERP_RGB
  759.                {
  760.                   /* need this to accomodate round-off errors */
  761.                   GLfixed ffrend = ffr+(right-left-1)*fdrdx;
  762.                   GLfixed ffgend = ffg+(right-left-1)*fdgdx;
  763.                   GLfixed ffbend = ffb+(right-left-1)*fdbdx;
  764.                   if (ffrend<0) ffr -= ffrend;
  765.                   if (ffgend<0) ffg -= ffgend;
  766.                   if (ffbend<0) ffb -= ffbend;
  767.                   if (ffr<0) ffr = 0;
  768.                   if (ffg<0) ffg = 0;
  769.                   if (ffb<0) ffb = 0;
  770.                }
  771. #endif
  772. #if INTERP_ALPHA
  773.                {
  774.                   GLfixed ffaend = ffa+(right-left-1)*fdadx;
  775.                   if (ffaend<0) ffa -= ffaend;
  776.                   if (ffa<0) ffa = 0;
  777.                }
  778. #endif
  779. #if INTERP_INDEX
  780.                if (ffi<0) ffi = 0;
  781. #endif
  782.  
  783.                INNER_LOOP( left, right, iy );
  784.  
  785.                /*
  786.                 * Advance to the next scan line.  Compute the
  787.                 * new edge coordinates, and adjust the
  788.                 * pixel-center x coordinate so that it stays
  789.                 * on or inside the major edge.
  790.                 */
  791.                iy++;
  792.                lines--;
  793.  
  794.                fxLeftEdge += fdxLeftEdge;
  795.                fxRightEdge += fdxRightEdge;
  796.  
  797.  
  798.                fError += fdError;
  799.                if (fError >= 0) {
  800.                   fError -= FIXED_ONE;
  801. #ifdef PIXEL_ADDRESS
  802.                   pRow = (PIXEL_TYPE*) ((GLubyte*)pRow + dPRowOuter);
  803. #endif
  804. #if INTERP_Z
  805.                   zRow = (GLdepth*) ((GLubyte*)zRow + dZRowOuter);
  806.                   fz += fdzOuter;
  807. #endif
  808. #if INTERP_RGB
  809.                   fr += fdrOuter;   fg += fdgOuter;   fb += fdbOuter;
  810. #endif
  811. #if INTERP_ALPHA
  812.                   fa += fdaOuter;
  813. #endif
  814. #if INTERP_INDEX
  815.                   fi += fdiOuter;
  816. #endif
  817. #if INTERP_ST
  818.                   fs += fdsOuter;   ft += fdtOuter;
  819. #endif
  820. #if INTERP_STW
  821.                   sLeft += dsOuter;
  822.                   tLeft += dtOuter;
  823.                   wLeft += dwOuter;
  824. #endif
  825. #if INTERP_UV
  826.                   uLeft += duOuter;
  827.                   vLeft += dvOuter;
  828. #endif
  829.                }
  830.                else {
  831. #ifdef PIXEL_ADDRESS
  832.                   pRow = (PIXEL_TYPE*) ((GLubyte*)pRow + dPRowInner);
  833. #endif
  834. #if INTERP_Z
  835.                   zRow = (GLdepth*) ((GLubyte*)zRow + dZRowInner);
  836.                   fz += fdzInner;
  837. #endif
  838. #if INTERP_RGB
  839.                   fr += fdrInner;   fg += fdgInner;   fb += fdbInner;
  840. #endif
  841. #if INTERP_ALPHA
  842.                   fa += fdaInner;
  843. #endif
  844. #if INTERP_INDEX
  845.                   fi += fdiInner;
  846. #endif
  847. #if INTERP_ST
  848.                   fs += fdsInner;   ft += fdtInner;
  849. #endif
  850. #if INTERP_STW
  851.                   sLeft += dsInner;
  852.                   tLeft += dtInner;
  853.                   wLeft += dwInner;
  854. #endif
  855. #if INTERP_UV
  856.                   uLeft += duInner;
  857.                   vLeft += dvInner;
  858. #endif
  859.                }
  860.             } /*while lines>0*/
  861.  
  862.          } /* for subTriangle */
  863.  
  864.       }
  865.    }
  866. }
  867.  
  868. #undef SETUP_CODE
  869. #undef INNER_LOOP
  870.  
  871. #undef PIXEL_TYPE
  872. #undef BYTES_PER_ROW
  873. #undef PIXEL_ADDRESS
  874.  
  875. #undef INTERP_Z
  876. #undef INTERP_RGB
  877. #undef INTERP_ALPHA
  878. #undef INTERP_INDEX
  879. #undef INTERP_ST
  880. #undef INTERP_STW
  881. #undef INTERP_UV
  882.  
  883. #undef S_SCALE
  884. #undef T_SCALE
  885.