src/mesa/swrast/s_aatriangle.c

   1 /* $Id: s_aatriangle.c,v 1.26 2002/10/24 23:57:24 brianp Exp $ */
   2
   3 /*
   4  * Mesa 3-D graphics library
   5  * Version:  4.1
   6  *
   7  * Copyright (C) 1999-2002  Brian Paul   All Rights Reserved.
   8  *
   9  * Permission is hereby granted, free of charge, to any person obtaining a
  10  * copy of this software and associated documentation files (the "Software"),
  11  * to deal in the Software without restriction, including without limitation
  12  * the rights to use, copy, modify, merge, publish, distribute, sublicense,
  13  * and/or sell copies of the Software, and to permit persons to whom the
  14  * Software is furnished to do so, subject to the following conditions:
  15  *
  16  * The above copyright notice and this permission notice shall be included
  17  * in all copies or substantial portions of the Software.
  18  *
  19  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS
  20  * OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
  21  * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.  IN NO EVENT SHALL
  22  * BRIAN PAUL BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN
  23  * AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN
  24  * CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
  25  */
  26
  27
  28 /*
  29  * Antialiased Triangle rasterizers
  30  */
  31
  32
  33 #include "glheader.h"
  34 #include "macros.h"
  35 #include "imports.h"
  36 #include "mmath.h"
  37 #include "s_aatriangle.h"
  38 #include "s_context.h"
  39 #include "s_span.h"
  40
  41
  42 /*
  43  * Compute coefficients of a plane using the X,Y coords of the v0, v1, v2
  44  * vertices and the given Z values.
  45  * A point (x,y,z) lies on plane iff a*x+b*y+c*z+d = 0.
  46  */
  47 static INLINE void
  48 compute_plane(const GLfloat v0[], const GLfloat v1[], const GLfloat v2[],
  49               GLfloat z0, GLfloat z1, GLfloat z2, GLfloat plane[4])
  50 {
  51    const GLfloat px = v1[0] - v0[0];
  52    const GLfloat py = v1[1] - v0[1];
  53    const GLfloat pz = z1 - z0;
  54
  55    const GLfloat qx = v2[0] - v0[0];
  56    const GLfloat qy = v2[1] - v0[1];
  57    const GLfloat qz = z2 - z0;
  58
  59    /* Crossproduct "(a,b,c):= dv1 x dv2" is orthogonal to plane. */
  60    const GLfloat a = py * qz - pz * qy;
  61    const GLfloat b = pz * qx - px * qz;
  62    const GLfloat c = px * qy - py * qx;
  63    /* Point on the plane = "r*(a,b,c) + w", with fixed "r" depending
  64       on the distance of plane from origin and arbitrary "w" parallel
  65       to the plane. */
  66    /* The scalar product "(r*(a,b,c)+w)*(a,b,c)" is "r*(a^2+b^2+c^2)",
  67       which is equal to "-d" below. */
  68    const GLfloat d = -(a * v0[0] + b * v0[1] + c * z0);
  69
  70    plane[0] = a;
  71    plane[1] = b;
  72    plane[2] = c;
  73    plane[3] = d;
  74 }
  75
  76
  77 /*
  78  * Compute coefficients of a plane with a constant Z value.
  79  */
  80 static INLINE void
  81 constant_plane(GLfloat value, GLfloat plane[4])
  82 {
  83    plane[0] = 0.0;
  84    plane[1] = 0.0;
  85    plane[2] = -1.0;
  86    plane[3] = value;
  87 }
  88
  89 #define CONSTANT_PLANE(VALUE, PLANE)    \
  90 do {                                    \
  91    PLANE[0] = 0.0F;                     \
  92    PLANE[1] = 0.0F;                     \
  93    PLANE[2] = -1.0F;                    \
  94    PLANE[3] = VALUE;                    \
  95 } while (0)
  96
  97
  98
  99 /*
 100  * Solve plane equation for Z at (X,Y).
 101  */
 102 static INLINE GLfloat
 103 solve_plane(GLfloat x, GLfloat y, const GLfloat plane[4])
 104 {
 105    ASSERT(plane[2] != 0.0F);
 106    return (plane[3] + plane[0] * x + plane[1] * y) / -plane[2];
 107 }
 108
 109
 110 #define SOLVE_PLANE(X, Y, PLANE) \
 111    ((PLANE[3] + PLANE[0] * (X) + PLANE[1] * (Y)) / -PLANE[2])
 112
 113
 114 /*
 115  * Return 1 / solve_plane().
 116  */
 117 static INLINE GLfloat
 118 solve_plane_recip(GLfloat x, GLfloat y, const GLfloat plane[4])
 119 {
 120    const GLfloat denom = plane[3] + plane[0] * x + plane[1] * y;
 121    if (denom == 0.0F)
 122       return 0.0F;
 123    else
 124       return -plane[2] / denom;
 125 }
 126
 127
 128 /*
 129  * Solve plane and return clamped GLchan value.
 130  */
 131 static INLINE GLchan
 132 solve_plane_chan(GLfloat x, GLfloat y, const GLfloat plane[4])
 133 {
 134    GLfloat z = (plane[3] + plane[0] * x + plane[1] * y) / -plane[2] + 0.5F;
 135    if (z < 0.0F)
 136       return 0;
 137    else if (z > CHAN_MAXF)
 138       return (GLchan) CHAN_MAXF;
 139    return (GLchan) (GLint) z;
 140 }
 141
 142
 143
 144 /*
 145  * Compute how much (area) of the given pixel is inside the triangle.
 146  * Vertices MUST be specified in counter-clockwise order.
 147  * Return:  coverage in [0, 1].
 148  */
 149 static GLfloat
 150 compute_coveragef(const GLfloat v0[3], const GLfloat v1[3],
 151                   const GLfloat v2[3], GLint winx, GLint winy)
 152 {
 153    /* Given a position [0,3]x[0,3] return the sub-pixel sample position.
 154     * Contributed by Ray Tice.
 155     *
 156     * Jitter sample positions -
 157     * - average should be .5 in x & y for each column
 158     * - each of the 16 rows and columns should be used once
 159     * - the rectangle formed by the first four points
 160     *   should contain the other points
 161     * - the distrubition should be fairly even in any given direction
 162     *
 163     * The pattern drawn below isn't optimal, but it's better than a regular
 164     * grid.  In the drawing, the center of each subpixel is surrounded by
 165     * four dots.  The "x" marks the jittered position relative to the
 166     * subpixel center.
 167     */
 168 #define POS(a, b) (0.5+a*4+b)/16
 169    static const GLfloat samples[16][2] = {
 170       /* start with the four corners */
 171       { POS(0, 2), POS(0, 0) },
 172       { POS(3, 3), POS(0, 2) },
 173       { POS(0, 0), POS(3, 1) },
 174       { POS(3, 1), POS(3, 3) },
 175       /* continue with interior samples */
 176       { POS(1, 1), POS(0, 1) },
 177       { POS(2, 0), POS(0, 3) },
 178       { POS(0, 3), POS(1, 3) },
 179       { POS(1, 2), POS(1, 0) },
 180       { POS(2, 3), POS(1, 2) },
 181       { POS(3, 2), POS(1, 1) },
 182       { POS(0, 1), POS(2, 2) },
 183       { POS(1, 0), POS(2, 1) },
 184       { POS(2, 1), POS(2, 3) },
 185       { POS(3, 0), POS(2, 0) },
 186       { POS(1, 3), POS(3, 0) },
 187       { POS(2, 2), POS(3, 2) }
 188    };
 189
 190    const GLfloat x = (GLfloat) winx;
 191    const GLfloat y = (GLfloat) winy;
 192    const GLfloat dx0 = v1[0] - v0[0];
 193    const GLfloat dy0 = v1[1] - v0[1];
 194    const GLfloat dx1 = v2[0] - v1[0];
 195    const GLfloat dy1 = v2[1] - v1[1];
 196    const GLfloat dx2 = v0[0] - v2[0];
 197    const GLfloat dy2 = v0[1] - v2[1];
 198    GLint stop = 4, i;
 199    GLfloat insideCount = 16.0F;
 200
 201 #ifdef DEBUG
 202    {
 203       const GLfloat area = dx0 * dy1 - dx1 * dy0;
 204       ASSERT(area >= 0.0);
 205    }
 206 #endif
 207
 208    for (i = 0; i < stop; i++) {
 209       const GLfloat sx = x + samples[i][0];
 210       const GLfloat sy = y + samples[i][1];
 211       const GLfloat fx0 = sx - v0[0];
 212       const GLfloat fy0 = sy - v0[1];
 213       const GLfloat fx1 = sx - v1[0];
 214       const GLfloat fy1 = sy - v1[1];
 215       const GLfloat fx2 = sx - v2[0];
 216       const GLfloat fy2 = sy - v2[1];
 217       /* cross product determines if sample is inside or outside each edge */
 218       GLfloat cross0 = (dx0 * fy0 - dy0 * fx0);
 219       GLfloat cross1 = (dx1 * fy1 - dy1 * fx1);
 220       GLfloat cross2 = (dx2 * fy2 - dy2 * fx2);
 221       /* Check if the sample is exactly on an edge.  If so, let cross be a
 222        * positive or negative value depending on the direction of the edge.
 223        */
 224       if (cross0 == 0.0F)
 225          cross0 = dx0 + dy0;
 226       if (cross1 == 0.0F)
 227          cross1 = dx1 + dy1;
 228       if (cross2 == 0.0F)
 229          cross2 = dx2 + dy2;
 230       if (cross0 < 0.0F || cross1 < 0.0F || cross2 < 0.0F) {
 231          /* point is outside triangle */
 232          insideCount -= 1.0F;
 233          stop = 16;
 234       }
 235    }
 236    if (stop == 4)
 237       return 1.0F;
 238    else
 239       return insideCount * (1.0F / 16.0F);
 240 }
 241
 242
 243
 244 /*
 245  * Compute how much (area) of the given pixel is inside the triangle.
 246  * Vertices MUST be specified in counter-clockwise order.
 247  * Return:  coverage in [0, 15].
 248  */
 249 static GLint
 250 compute_coveragei(const GLfloat v0[3], const GLfloat v1[3],
 251                   const GLfloat v2[3], GLint winx, GLint winy)
 252 {
 253    /* NOTE: 15 samples instead of 16. */
 254    static const GLfloat samples[15][2] = {
 255       /* start with the four corners */
 256       { POS(0, 2), POS(0, 0) },
 257       { POS(3, 3), POS(0, 2) },
 258       { POS(0, 0), POS(3, 1) },
 259       { POS(3, 1), POS(3, 3) },
 260       /* continue with interior samples */
 261       { POS(1, 1), POS(0, 1) },
 262       { POS(2, 0), POS(0, 3) },
 263       { POS(0, 3), POS(1, 3) },
 264       { POS(1, 2), POS(1, 0) },
 265       { POS(2, 3), POS(1, 2) },
 266       { POS(3, 2), POS(1, 1) },
 267       { POS(0, 1), POS(2, 2) },
 268       { POS(1, 0), POS(2, 1) },
 269       { POS(2, 1), POS(2, 3) },
 270       { POS(3, 0), POS(2, 0) },
 271       { POS(1, 3), POS(3, 0) }
 272    };
 273    const GLfloat x = (GLfloat) winx;
 274    const GLfloat y = (GLfloat) winy;
 275    const GLfloat dx0 = v1[0] - v0[0];
 276    const GLfloat dy0 = v1[1] - v0[1];
 277    const GLfloat dx1 = v2[0] - v1[0];
 278    const GLfloat dy1 = v2[1] - v1[1];
 279    const GLfloat dx2 = v0[0] - v2[0];
 280    const GLfloat dy2 = v0[1] - v2[1];
 281    GLint stop = 4, i;
 282    GLint insideCount = 15;
 283
 284 #ifdef DEBUG
 285    {
 286       const GLfloat area = dx0 * dy1 - dx1 * dy0;
 287       ASSERT(area >= 0.0);
 288    }
 289 #endif
 290
 291    for (i = 0; i < stop; i++) {
 292       const GLfloat sx = x + samples[i][0];
 293       const GLfloat sy = y + samples[i][1];
 294       const GLfloat fx0 = sx - v0[0];
 295       const GLfloat fy0 = sy - v0[1];
 296       const GLfloat fx1 = sx - v1[0];
 297       const GLfloat fy1 = sy - v1[1];
 298       const GLfloat fx2 = sx - v2[0];
 299       const GLfloat fy2 = sy - v2[1];
 300       /* cross product determines if sample is inside or outside each edge */
 301       GLfloat cross0 = (dx0 * fy0 - dy0 * fx0);
 302       GLfloat cross1 = (dx1 * fy1 - dy1 * fx1);
 303       GLfloat cross2 = (dx2 * fy2 - dy2 * fx2);
 304       /* Check if the sample is exactly on an edge.  If so, let cross be a
 305        * positive or negative value depending on the direction of the edge.
 306        */
 307       if (cross0 == 0.0F)
 308          cross0 = dx0 + dy0;
 309       if (cross1 == 0.0F)
 310          cross1 = dx1 + dy1;
 311       if (cross2 == 0.0F)
 312          cross2 = dx2 + dy2;
 313       if (cross0 < 0.0F || cross1 < 0.0F || cross2 < 0.0F) {
 314          /* point is outside triangle */
 315          insideCount--;
 316          stop = 15;
 317       }
 318    }
 319    if (stop == 4)
 320       return 15;
 321    else
 322       return insideCount;
 323 }
 324
 325
 326
 327 static void
 328 rgba_aa_tri(GLcontext *ctx,
 329             const SWvertex *v0,
 330             const SWvertex *v1,
 331             const SWvertex *v2)
 332 {
 333 #define DO_Z
 334 #define DO_FOG
 335 #define DO_RGBA
 336 #include "s_aatritemp.h"
 337 }
 338
 339
 340 static void
 341 index_aa_tri(GLcontext *ctx,
 342              const SWvertex *v0,
 343              const SWvertex *v1,
 344              const SWvertex *v2)
 345 {
 346 #define DO_Z
 347 #define DO_FOG
 348 #define DO_INDEX
 349 #include "s_aatritemp.h"
 350 }
 351
 352
 353 /*
 354  * Compute mipmap level of detail.
 355  * XXX we should really include the R coordinate in this computation
 356  * in order to do 3-D texture mipmapping.
 357  */
 358 static INLINE GLfloat
 359 compute_lambda(const GLfloat sPlane[4], const GLfloat tPlane[4],
 360                const GLfloat qPlane[4], GLfloat cx, GLfloat cy,
 361                GLfloat invQ, GLfloat texWidth, GLfloat texHeight)
 362 {
 363    const GLfloat s = solve_plane(cx, cy, sPlane);
 364    const GLfloat t = solve_plane(cx, cy, tPlane);
 365    const GLfloat invQ_x1 = solve_plane_recip(cx+1.0F, cy, qPlane);
 366    const GLfloat invQ_y1 = solve_plane_recip(cx, cy+1.0F, qPlane);
 367    const GLfloat s_x1 = s - sPlane[0] / sPlane[2];
 368    const GLfloat s_y1 = s - sPlane[1] / sPlane[2];
 369    const GLfloat t_x1 = t - tPlane[0] / tPlane[2];
 370    const GLfloat t_y1 = t - tPlane[1] / tPlane[2];
 371    GLfloat dsdx = s_x1 * invQ_x1 - s * invQ;
 372    GLfloat dsdy = s_y1 * invQ_y1 - s * invQ;
 373    GLfloat dtdx = t_x1 * invQ_x1 - t * invQ;
 374    GLfloat dtdy = t_y1 * invQ_y1 - t * invQ;
 375    GLfloat maxU, maxV, rho, lambda;
 376    dsdx = FABSF(dsdx);
 377    dsdy = FABSF(dsdy);
 378    dtdx = FABSF(dtdx);
 379    dtdy = FABSF(dtdy);
 380    maxU = MAX2(dsdx, dsdy) * texWidth;
 381    maxV = MAX2(dtdx, dtdy) * texHeight;
 382    rho = MAX2(maxU, maxV);
 383    lambda = LOG2(rho);
 384    return lambda;
 385 }
 386
 387
 388 static void
 389 tex_aa_tri(GLcontext *ctx,
 390            const SWvertex *v0,
 391            const SWvertex *v1,
 392            const SWvertex *v2)
 393 {
 394 #define DO_Z
 395 #define DO_FOG
 396 #define DO_RGBA
 397 #define DO_TEX
 398 #include "s_aatritemp.h"
 399 }
 400
 401
 402 static void
 403 spec_tex_aa_tri(GLcontext *ctx,
 404                 const SWvertex *v0,
 405                 const SWvertex *v1,
 406                 const SWvertex *v2)
 407 {
 408 #define DO_Z
 409 #define DO_FOG
 410 #define DO_RGBA
 411 #define DO_TEX
 412 #define DO_SPEC
 413 #include "s_aatritemp.h"
 414 }
 415
 416
 417 static void
 418 multitex_aa_tri(GLcontext *ctx,
 419                 const SWvertex *v0,
 420                 const SWvertex *v1,
 421                 const SWvertex *v2)
 422 {
 423 #define DO_Z
 424 #define DO_FOG
 425 #define DO_RGBA
 426 #define DO_MULTITEX
 427 #include "s_aatritemp.h"
 428 }
 429
 430 static void
 431 spec_multitex_aa_tri(GLcontext *ctx,
 432                      const SWvertex *v0,
 433                      const SWvertex *v1,
 434                      const SWvertex *v2)
 435 {
 436 #define DO_Z
 437 #define DO_FOG
 438 #define DO_RGBA
 439 #define DO_MULTITEX
 440 #define DO_SPEC
 441 #include "s_aatritemp.h"
 442 }
 443
 444
 445 /*
 446  * Examine GL state and set swrast->Triangle to an
 447  * appropriate antialiased triangle rasterizer function.
 448  */
 449 void
 450 _mesa_set_aa_triangle_function(GLcontext *ctx)
 451 {
 452    ASSERT(ctx->Polygon.SmoothFlag);
 453
 454    if (ctx->Texture._EnabledUnits != 0) {
 455       if (ctx->_TriangleCaps & DD_SEPARATE_SPECULAR) {
 456          if (ctx->Texture._EnabledUnits > 1) {
 457             SWRAST_CONTEXT(ctx)->Triangle = spec_multitex_aa_tri;
 458          }
 459          else {
 460             SWRAST_CONTEXT(ctx)->Triangle = spec_tex_aa_tri;
 461          }
 462       }
 463       else {
 464          if (ctx->Texture._EnabledUnits > 1) {
 465             SWRAST_CONTEXT(ctx)->Triangle = multitex_aa_tri;
 466          }
 467          else {
 468             SWRAST_CONTEXT(ctx)->Triangle = tex_aa_tri;
 469          }
 470       }
 471    }
 472    else if (ctx->Visual.rgbMode) {
 473       SWRAST_CONTEXT(ctx)->Triangle = rgba_aa_tri;
 474    }
 475    else {
 476       SWRAST_CONTEXT(ctx)->Triangle = index_aa_tri;
 477    }
 478
 479    ASSERT(SWRAST_CONTEXT(ctx)->Triangle);
 480 }