src/mesa/swrast/s_aaline.c

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