src/mesa/swrast/s_aaline.c

   1 /* $Id: s_aaline.c,v 1.21 2003/03/14 15:38:04 brianp Exp $ */
   2
   3 /*
   4  * Mesa 3-D graphics library
   5  * Version:  5.0.1
   6  *
   7  * Copyright (C) 1999-2003  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 #include "glheader.h"
  29 #include "imports.h"
  30 #include "macros.h"
  31 #include "swrast/s_aaline.h"
  32 #include "swrast/s_context.h"
  33 #include "swrast/s_span.h"
  34 #include "swrast/swrast.h"
  35 #include "mtypes.h"
  36
  37
  38 #define SUB_PIXEL 4
  39
  40
  41 /*
  42  * Info about the AA line we're rendering
  43  */
  44 struct LineInfo
  45 {
  46    GLfloat x0, y0;        /* start */
  47    GLfloat x1, y1;        /* end */
  48    GLfloat dx, dy;        /* direction vector */
  49    GLfloat len;           /* length */
  50    GLfloat halfWidth;     /* half of line width */
  51    GLfloat xAdj, yAdj;    /* X and Y adjustment for quad corners around line */
  52    /* for coverage computation */
  53    GLfloat qx0, qy0;      /* quad vertices */
  54    GLfloat qx1, qy1;
  55    GLfloat qx2, qy2;
  56    GLfloat qx3, qy3;
  57    GLfloat ex0, ey0;      /* quad edge vectors */
  58    GLfloat ex1, ey1;
  59    GLfloat ex2, ey2;
  60    GLfloat ex3, ey3;
  61
  62    /* DO_Z */
  63    GLfloat zPlane[4];
  64    /* DO_FOG */
  65    GLfloat fPlane[4];
  66    /* DO_RGBA */
  67    GLfloat rPlane[4], gPlane[4], bPlane[4], aPlane[4];
  68    /* DO_INDEX */
  69    GLfloat iPlane[4];
  70    /* DO_SPEC */
  71    GLfloat srPlane[4], sgPlane[4], sbPlane[4];
  72    /* DO_TEX or DO_MULTITEX */
  73    GLfloat sPlane[MAX_TEXTURE_COORD_UNITS][4];
  74    GLfloat tPlane[MAX_TEXTURE_COORD_UNITS][4];
  75    GLfloat uPlane[MAX_TEXTURE_COORD_UNITS][4];
  76    GLfloat vPlane[MAX_TEXTURE_COORD_UNITS][4];
  77    GLfloat lambda[MAX_TEXTURE_COORD_UNITS];
  78    GLfloat texWidth[MAX_TEXTURE_COORD_UNITS];
  79    GLfloat texHeight[MAX_TEXTURE_COORD_UNITS];
  80
  81    struct sw_span span;
  82 };
  83
  84
  85
  86 /*
  87  * Compute the equation of a plane used to interpolate line fragment data
  88  * such as color, Z, texture coords, etc.
  89  * Input: (x0, y0) and (x1,y1) are the endpoints of the line.
  90  *        z0, and z1 are the end point values to interpolate.
  91  * Output:  plane - the plane equation.
  92  *
  93  * Note: we don't really have enough parameters to specify a plane.
  94  * We take the endpoints of the line and compute a plane such that
  95  * the cross product of the line vector and the plane normal is
  96  * parallel to the projection plane.
  97  */
  98 static void
  99 compute_plane(GLfloat x0, GLfloat y0, GLfloat x1, GLfloat y1,
 100               GLfloat z0, GLfloat z1, GLfloat plane[4])
 101 {
 102 #if 0
 103    /* original */
 104    const GLfloat px = x1 - x0;
 105    const GLfloat py = y1 - y0;
 106    const GLfloat pz = z1 - z0;
 107    const GLfloat qx = -py;
 108    const GLfloat qy = px;
 109    const GLfloat qz = 0;
 110    const GLfloat a = py * qz - pz * qy;
 111    const GLfloat b = pz * qx - px * qz;
 112    const GLfloat c = px * qy - py * qx;
 113    const GLfloat d = -(a * x0 + b * y0 + c * z0);
 114    plane[0] = a;
 115    plane[1] = b;
 116    plane[2] = c;
 117    plane[3] = d;
 118 #else
 119    /* simplified */
 120    const GLfloat px = x1 - x0;
 121    const GLfloat py = y1 - y0;
 122    const GLfloat pz = z0 - z1;
 123    const GLfloat a = pz * px;
 124    const GLfloat b = pz * py;
 125    const GLfloat c = px * px + py * py;
 126    const GLfloat d = -(a * x0 + b * y0 + c * z0);
 127    if (a == 0.0 && b == 0.0 && c == 0.0 && d == 0.0) {
 128       plane[0] = 0.0;
 129       plane[1] = 0.0;
 130       plane[2] = 1.0;
 131       plane[3] = 0.0;
 132    }
 133    else {
 134       plane[0] = a;
 135       plane[1] = b;
 136       plane[2] = c;
 137       plane[3] = d;
 138    }
 139 #endif
 140 }
 141
 142
 143 static INLINE void
 144 constant_plane(GLfloat value, GLfloat plane[4])
 145 {
 146    plane[0] = 0.0;
 147    plane[1] = 0.0;
 148    plane[2] = -1.0;
 149    plane[3] = value;
 150 }
 151
 152
 153 static INLINE GLfloat
 154 solve_plane(GLfloat x, GLfloat y, const GLfloat plane[4])
 155 {
 156    const GLfloat z = (plane[3] + plane[0] * x + plane[1] * y) / -plane[2];
 157    return z;
 158 }
 159
 160 #define SOLVE_PLANE(X, Y, PLANE) \
 161    ((PLANE[3] + PLANE[0] * (X) + PLANE[1] * (Y)) / -PLANE[2])
 162
 163
 164 /*
 165  * Return 1 / solve_plane().
 166  */
 167 static INLINE GLfloat
 168 solve_plane_recip(GLfloat x, GLfloat y, const GLfloat plane[4])
 169 {
 170    const GLfloat denom = plane[3] + plane[0] * x + plane[1] * y;
 171    if (denom == 0.0)
 172       return 0.0;
 173    else
 174       return -plane[2] / denom;
 175 }
 176
 177
 178 /*
 179  * Solve plane and return clamped GLchan value.
 180  */
 181 static INLINE GLchan
 182 solve_plane_chan(GLfloat x, GLfloat y, const GLfloat plane[4])
 183 {
 184    const GLfloat z = (plane[3] + plane[0] * x + plane[1] * y) / -plane[2];
 185 #if CHAN_TYPE == GL_FLOAT
 186    return CLAMP(z, 0.0F, CHAN_MAXF);
 187 #else
 188    if (z < 0)
 189       return 0;
 190    else if (z > CHAN_MAX)
 191       return CHAN_MAX;
 192    return (GLchan) IROUND_POS(z);
 193 #endif
 194 }
 195
 196
 197 /*
 198  * Compute mipmap level of detail.
 199  */
 200 static INLINE GLfloat
 201 compute_lambda(const GLfloat sPlane[4], const GLfloat tPlane[4],
 202                GLfloat invQ, GLfloat width, GLfloat height)
 203 {
 204    GLfloat dudx = sPlane[0] / sPlane[2] * invQ * width;
 205    GLfloat dudy = sPlane[1] / sPlane[2] * invQ * width;
 206    GLfloat dvdx = tPlane[0] / tPlane[2] * invQ * height;
 207    GLfloat dvdy = tPlane[1] / tPlane[2] * invQ * height;
 208    GLfloat r1 = dudx * dudx + dudy * dudy;
 209    GLfloat r2 = dvdx * dvdx + dvdy * dvdy;
 210    GLfloat rho2 = r1 + r2;
 211    /* return log base 2 of rho */
 212    if (rho2 == 0.0F)
 213       return 0.0;
 214    else
 215       return (GLfloat) (log(rho2) * 1.442695 * 0.5);/* 1.442695 = 1/log(2) */
 216 }
 217
 218
 219
 220
 221 /*
 222  * Fill in the samples[] array with the (x,y) subpixel positions of
 223  * xSamples * ySamples sample positions.
 224  * Note that the four corner samples are put into the first four
 225  * positions of the array.  This allows us to optimize for the common
 226  * case of all samples being inside the polygon.
 227  */
 228 static void
 229 make_sample_table(GLint xSamples, GLint ySamples, GLfloat samples[][2])
 230 {
 231    const GLfloat dx = 1.0F / (GLfloat) xSamples;
 232    const GLfloat dy = 1.0F / (GLfloat) ySamples;
 233    GLint x, y;
 234    GLint i;
 235
 236    i = 4;
 237    for (x = 0; x < xSamples; x++) {
 238       for (y = 0; y < ySamples; y++) {
 239          GLint j;
 240          if (x == 0 && y == 0) {
 241             /* lower left */
 242             j = 0;
 243          }
 244          else if (x == xSamples - 1 && y == 0) {
 245             /* lower right */
 246             j = 1;
 247          }
 248          else if (x == 0 && y == ySamples - 1) {
 249             /* upper left */
 250             j = 2;
 251          }
 252          else if (x == xSamples - 1 && y == ySamples - 1) {
 253             /* upper right */
 254             j = 3;
 255          }
 256          else {
 257             j = i++;
 258          }
 259          samples[j][0] = x * dx + 0.5F * dx;
 260          samples[j][1] = y * dy + 0.5F * dy;
 261       }
 262    }
 263 }
 264
 265
 266
 267 /*
 268  * Compute how much of the given pixel's area is inside the rectangle
 269  * defined by vertices v0, v1, v2, v3.
 270  * Vertices MUST be specified in counter-clockwise order.
 271  * Return:  coverage in [0, 1].
 272  */
 273 static GLfloat
 274 compute_coveragef(const struct LineInfo *info,
 275                   GLint winx, GLint winy)
 276 {
 277    static GLfloat samples[SUB_PIXEL * SUB_PIXEL][2];
 278    static GLboolean haveSamples = GL_FALSE;
 279    const GLfloat x = (GLfloat) winx;
 280    const GLfloat y = (GLfloat) winy;
 281    GLint stop = 4, i;
 282    GLfloat insideCount = SUB_PIXEL * SUB_PIXEL;
 283
 284    if (!haveSamples) {
 285       make_sample_table(SUB_PIXEL, SUB_PIXEL, samples);
 286       haveSamples = GL_TRUE;
 287    }
 288
 289 #if 0 /*DEBUG*/
 290    {
 291       const GLfloat area = dx0 * dy1 - dx1 * dy0;
 292       assert(area >= 0.0);
 293    }
 294 #endif
 295
 296    for (i = 0; i < stop; i++) {
 297       const GLfloat sx = x + samples[i][0];
 298       const GLfloat sy = y + samples[i][1];
 299       const GLfloat fx0 = sx - info->qx0;
 300       const GLfloat fy0 = sy - info->qy0;
 301       const GLfloat fx1 = sx - info->qx1;
 302       const GLfloat fy1 = sy - info->qy1;
 303       const GLfloat fx2 = sx - info->qx2;
 304       const GLfloat fy2 = sy - info->qy2;
 305       const GLfloat fx3 = sx - info->qx3;
 306       const GLfloat fy3 = sy - info->qy3;
 307       /* cross product determines if sample is inside or outside each edge */
 308       GLfloat cross0 = (info->ex0 * fy0 - info->ey0 * fx0);
 309       GLfloat cross1 = (info->ex1 * fy1 - info->ey1 * fx1);
 310       GLfloat cross2 = (info->ex2 * fy2 - info->ey2 * fx2);
 311       GLfloat cross3 = (info->ex3 * fy3 - info->ey3 * fx3);
 312       /* Check if the sample is exactly on an edge.  If so, let cross be a
 313        * positive or negative value depending on the direction of the edge.
 314        */
 315       if (cross0 == 0.0F)
 316          cross0 = info->ex0 + info->ey0;
 317       if (cross1 == 0.0F)
 318          cross1 = info->ex1 + info->ey1;
 319       if (cross2 == 0.0F)
 320          cross2 = info->ex2 + info->ey2;
 321       if (cross3 == 0.0F)
 322          cross3 = info->ex3 + info->ey3;
 323       if (cross0 < 0.0F || cross1 < 0.0F || cross2 < 0.0F || cross3 < 0.0F) {
 324          /* point is outside quadrilateral */
 325          insideCount -= 1.0F;
 326          stop = SUB_PIXEL * SUB_PIXEL;
 327       }
 328    }
 329    if (stop == 4)
 330       return 1.0F;
 331    else
 332       return insideCount * (1.0F / (SUB_PIXEL * SUB_PIXEL));
 333 }
 334
 335
 336
 337 typedef void (*plot_func)(GLcontext *ctx, struct LineInfo *line,
 338                           int ix, int iy);
 339
 340
 341
 342 /*
 343  * Draw an AA line segment (called many times per line when stippling)
 344  */
 345 static void
 346 segment(GLcontext *ctx,
 347         struct LineInfo *line,
 348         plot_func plot,
 349         GLfloat t0, GLfloat t1)
 350 {
 351    const GLfloat absDx = (line->dx < 0.0F) ? -line->dx : line->dx;
 352    const GLfloat absDy = (line->dy < 0.0F) ? -line->dy : line->dy;
 353    /* compute the actual segment's endpoints */
 354    const GLfloat x0 = line->x0 + t0 * line->dx;
 355    const GLfloat y0 = line->y0 + t0 * line->dy;
 356    const GLfloat x1 = line->x0 + t1 * line->dx;
 357    const GLfloat y1 = line->y0 + t1 * line->dy;
 358
 359    /* compute vertices of the line-aligned quadrilateral */
 360    line->qx0 = x0 - line->yAdj;
 361    line->qy0 = y0 + line->xAdj;
 362    line->qx1 = x0 + line->yAdj;
 363    line->qy1 = y0 - line->xAdj;
 364    line->qx2 = x1 + line->yAdj;
 365    line->qy2 = y1 - line->xAdj;
 366    line->qx3 = x1 - line->yAdj;
 367    line->qy3 = y1 + line->xAdj;
 368    /* compute the quad's edge vectors (for coverage calc) */
 369    line->ex0 = line->qx1 - line->qx0;
 370    line->ey0 = line->qy1 - line->qy0;
 371    line->ex1 = line->qx2 - line->qx1;
 372    line->ey1 = line->qy2 - line->qy1;
 373    line->ex2 = line->qx3 - line->qx2;
 374    line->ey2 = line->qy3 - line->qy2;
 375    line->ex3 = line->qx0 - line->qx3;
 376    line->ey3 = line->qy0 - line->qy3;
 377
 378    if (absDx > absDy) {
 379       /* X-major line */
 380       GLfloat dydx = line->dy / line->dx;
 381       GLfloat xLeft, xRight, yBot, yTop;
 382       GLint ix, ixRight;
 383       if (x0 < x1) {
 384          xLeft = x0 - line->halfWidth;
 385          xRight = x1 + line->halfWidth;
 386          if (line->dy >= 0.0) {
 387             yBot = y0 - 3.0F * line->halfWidth;
 388             yTop = y0 + line->halfWidth;
 389          }
 390          else {
 391             yBot = y0 - line->halfWidth;
 392             yTop = y0 + 3.0F * line->halfWidth;
 393          }
 394       }
 395       else {
 396          xLeft = x1 - line->halfWidth;
 397          xRight = x0 + line->halfWidth;
 398          if (line->dy <= 0.0) {
 399             yBot = y1 - 3.0F * line->halfWidth;
 400             yTop = y1 + line->halfWidth;
 401          }
 402          else {
 403             yBot = y1 - line->halfWidth;
 404             yTop = y1 + 3.0F * line->halfWidth;
 405          }
 406       }
 407
 408       /* scan along the line, left-to-right */
 409       ixRight = (GLint) (xRight + 1.0F);
 410
 411       /*printf("avg span height: %g\n", yTop - yBot);*/
 412       for (ix = (GLint) xLeft; ix < ixRight; ix++) {
 413          const GLint iyBot = (GLint) yBot;
 414          const GLint iyTop = (GLint) (yTop + 1.0F);
 415          GLint iy;
 416          /* scan across the line, bottom-to-top */
 417          for (iy = iyBot; iy < iyTop; iy++) {
 418             (*plot)(ctx, line, ix, iy);
 419          }
 420          yBot += dydx;
 421          yTop += dydx;
 422       }
 423    }
 424    else {
 425       /* Y-major line */
 426       GLfloat dxdy = line->dx / line->dy;
 427       GLfloat yBot, yTop, xLeft, xRight;
 428       GLint iy, iyTop;
 429       if (y0 < y1) {
 430          yBot = y0 - line->halfWidth;
 431          yTop = y1 + line->halfWidth;
 432          if (line->dx >= 0.0) {
 433             xLeft = x0 - 3.0F * line->halfWidth;
 434             xRight = x0 + line->halfWidth;
 435          }
 436          else {
 437             xLeft = x0 - line->halfWidth;
 438             xRight = x0 + 3.0F * line->halfWidth;
 439          }
 440       }
 441       else {
 442          yBot = y1 - line->halfWidth;
 443          yTop = y0 + line->halfWidth;
 444          if (line->dx <= 0.0) {
 445             xLeft = x1 - 3.0F * line->halfWidth;
 446             xRight = x1 + line->halfWidth;
 447          }
 448          else {
 449             xLeft = x1 - line->halfWidth;
 450             xRight = x1 + 3.0F * line->halfWidth;
 451          }
 452       }
 453
 454       /* scan along the line, bottom-to-top */
 455       iyTop = (GLint) (yTop + 1.0F);
 456
 457       /*printf("avg span width: %g\n", xRight - xLeft);*/
 458       for (iy = (GLint) yBot; iy < iyTop; iy++) {
 459          const GLint ixLeft = (GLint) xLeft;
 460          const GLint ixRight = (GLint) (xRight + 1.0F);
 461          GLint ix;
 462          /* scan across the line, left-to-right */
 463          for (ix = ixLeft; ix < ixRight; ix++) {
 464             (*plot)(ctx, line, ix, iy);
 465          }
 466          xLeft += dxdy;
 467          xRight += dxdy;
 468       }
 469    }
 470 }
 471
 472
 473 #define NAME(x) aa_ci_##x
 474 #define DO_Z
 475 #define DO_FOG
 476 #define DO_INDEX
 477 #include "s_aalinetemp.h"
 478
 479
 480 #define NAME(x) aa_rgba_##x
 481 #define DO_Z
 482 #define DO_FOG
 483 #define DO_RGBA
 484 #include "s_aalinetemp.h"
 485
 486
 487 #define NAME(x)  aa_tex_rgba_##x
 488 #define DO_Z
 489 #define DO_FOG
 490 #define DO_RGBA
 491 #define DO_TEX
 492 #include "s_aalinetemp.h"
 493
 494
 495 #define NAME(x)  aa_multitex_rgba_##x
 496 #define DO_Z
 497 #define DO_FOG
 498 #define DO_RGBA
 499 #define DO_MULTITEX
 500 #include "s_aalinetemp.h"
 501
 502
 503 #define NAME(x)  aa_multitex_spec_##x
 504 #define DO_Z
 505 #define DO_FOG
 506 #define DO_RGBA
 507 #define DO_MULTITEX
 508 #define DO_SPEC
 509 #include "s_aalinetemp.h"
 510
 511
 512
 513 void
 514 _swrast_choose_aa_line_function(GLcontext *ctx)
 515 {
 516    SWcontext *swrast = SWRAST_CONTEXT(ctx);
 517
 518    ASSERT(ctx->Line.SmoothFlag);
 519
 520    if (ctx->Visual.rgbMode) {
 521       /* RGBA */
 522       if (ctx->Texture._EnabledUnits != 0) {
 523          if (ctx->Texture._EnabledUnits > 1) {
 524             /* Multitextured! */
 525             if (ctx->Light.Model.ColorControl==GL_SEPARATE_SPECULAR_COLOR ||
 526                 ctx->Fog.ColorSumEnabled)
 527                swrast->Line = aa_multitex_spec_line;
 528             else
 529                swrast->Line = aa_multitex_rgba_line;
 530          }
 531          else {
 532             swrast->Line = aa_tex_rgba_line;
 533          }
 534       }
 535       else {
 536          swrast->Line = aa_rgba_line;
 537       }
 538    }
 539    else {
 540       /* Color Index */
 541       swrast->Line = aa_ci_line;
 542    }
 543 }