dll/opengl/mesa/tritemp.h

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