1 /*
   2  * Copyright 2007 Sun Microsystems, Inc.  All Rights Reserved.
   3  * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
   4  *
   5  * This code is free software; you can redistribute it and/or modify it
   6  * under the terms of the GNU General Public License version 2 only, as
   7  * published by the Free Software Foundation.  Sun designates this
   8  * particular file as subject to the "Classpath" exception as provided
   9  * by Sun in the LICENSE file that accompanied this code.
  10  *
  11  * This code is distributed in the hope that it will be useful, but WITHOUT
  12  * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
  13  * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  14  * version 2 for more details (a copy is included in the LICENSE file that
  15  * accompanied this code).
  16  *
  17  * You should have received a copy of the GNU General Public License version
  18  * 2 along with this work; if not, write to the Free Software Foundation,
  19  * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
  20  *
  21  * Please contact Sun Microsystems, Inc., 4150 Network Circle, Santa Clara,
  22  * CA 95054 USA or visit www.sun.com if you need additional information or
  23  * have any questions.
  24  */
  25 
  26 package sun.java2d.pisces;
  27 
  28 public class Renderer extends LineSink {
  29     public static final int WIND_EVEN_ODD = 0;
  30     public static final int WIND_NON_ZERO = 1;
  31 
  32     // Initial edge list size
  33     // IMPL_NOTE - restore size after growth
  34     public static final int INITIAL_EDGES = 1000;
  35 
  36     // Recommended maximum scratchpad sizes.  The arrays will grow
  37     // larger if needed, but when finished() is called they will be released
  38     // if they have grown larger than these sizes.
  39     public static final int DEFAULT_INDICES_SIZE = 8192;
  40     public static final int DEFAULT_CROSSINGS_SIZE = 32*1024;
  41 
  42     // Antialiasing
  43     private int SUBPIXEL_LG_POSITIONS_X;
  44     private int SUBPIXEL_LG_POSITIONS_Y;
  45     private int SUBPIXEL_MASK_X;
  46     private int SUBPIXEL_MASK_Y;
  47     private int SUBPIXEL_POSITIONS_X;
  48     private int SUBPIXEL_POSITIONS_Y;
  49     int MAX_AA_ALPHA;
  50     private int MAX_AA_ALPHA_DENOM;
  51     private int HALF_MAX_AA_ALPHA_DENOM;
  52     private int XSHIFT;
  53     private int YSHIFT;
  54     private int YSTEP;
  55     private int HYSTEP;
  56     private int YMASK;
  57 
  58     private static final int MIN_QUAD_OPT_WIDTH = 100 << 16;
  59 
  60     // Cache to store RLE-encoded coverage mask of the current primitive
  61     PiscesCache cache;
  62 
  63     // Bounds of the drawing region, at S15.16 precsion
  64     private int boundsMinX, boundsMinY, boundsMaxX, boundsMaxY;
  65 
  66     // Bounds of the current primitive, at subsample precision
  67     private int rasterMinX, rasterMaxX, rasterMinY, rasterMaxY;
  68 
  69     // Pixel bounding box for current primitive
  70     private int bboxX0, bboxY0, bboxX1, bboxY1;
  71 
  72     // Current winding rule
  73     private int windingRule;
  74 
  75     // Current drawing position, i.e., final point of last segment
  76     private int x0, y0;
  77 
  78     // Position of most recent 'moveTo' command
  79     private int sx0, sy0;
  80 
  81     // Buffer to be filled with one row's worth of alpha values
  82     private byte[] rowAA; // needs to be short if 16x16 subsampling
  83 
  84     // Track the number of vertical extrema of the incoming edge list
  85     // in order to determine the maximum number of crossings of a
  86     // scanline
  87     private int firstOrientation;
  88     private int lastOrientation;
  89     private int flips;
  90 
  91     // Parameters for emitRow
  92     private int alphaWidth;
  93 
  94     public Renderer() {
  95     }
  96 
  97     public void setAntialiasing(int subpixelLgPositionsX,
  98                                 int subpixelLgPositionsY) {
  99         this.SUBPIXEL_LG_POSITIONS_X = subpixelLgPositionsX;
 100         this.SUBPIXEL_LG_POSITIONS_Y = subpixelLgPositionsY;
 101 
 102         this.SUBPIXEL_MASK_X =
 103             (1 << (SUBPIXEL_LG_POSITIONS_X)) - 1;
 104         this.SUBPIXEL_MASK_Y =
 105             (1 << (SUBPIXEL_LG_POSITIONS_Y)) - 1;
 106         this.SUBPIXEL_POSITIONS_X =
 107             1 << (SUBPIXEL_LG_POSITIONS_X);
 108         this.SUBPIXEL_POSITIONS_Y =
 109             1 << (SUBPIXEL_LG_POSITIONS_Y);
 110         this.MAX_AA_ALPHA =
 111             (SUBPIXEL_POSITIONS_X*SUBPIXEL_POSITIONS_Y);
 112         this.MAX_AA_ALPHA_DENOM = 255*MAX_AA_ALPHA;
 113         this.HALF_MAX_AA_ALPHA_DENOM = MAX_AA_ALPHA_DENOM/2;
 114         this.XSHIFT = 16 - SUBPIXEL_LG_POSITIONS_X;
 115         this.YSHIFT = 16 - SUBPIXEL_LG_POSITIONS_Y;
 116         this.YSTEP = 1 << YSHIFT;
 117         this.HYSTEP = 1 << (YSHIFT - 1);
 118         this.YMASK = ~(YSTEP - 1);
 119     }
 120 
 121     public int getSubpixelLgPositionsX() {
 122         return SUBPIXEL_LG_POSITIONS_X;
 123     }
 124 
 125     public int getSubpixelLgPositionsY() {
 126         return SUBPIXEL_LG_POSITIONS_Y;
 127     }
 128 
 129     public void setWindingRule(int windingRule) {
 130         this.windingRule = windingRule;
 131     }
 132 
 133     public int getWindingRule() {
 134         return windingRule;
 135     }
 136 
 137     public void beginRendering(int boundsX, int boundsY,
 138                                int boundsWidth, int boundsHeight) {
 139         lastOrientation = 0;
 140         flips = 0;
 141 
 142         resetEdges();
 143 
 144         this.boundsMinX = boundsX << 16;
 145         this.boundsMinY = boundsY << 16;
 146         this.boundsMaxX = (boundsX + boundsWidth) << 16;
 147         this.boundsMaxY = (boundsY + boundsHeight) << 16;
 148 
 149         this.bboxX0 = boundsX;
 150         this.bboxY0 = boundsY;
 151         this.bboxX1 = boundsX + boundsWidth;
 152         this.bboxY1 = boundsY + boundsHeight;
 153     }
 154 
 155     public void moveTo(int x0, int y0) {
 156         // System.out.println("Renderer: moveTo " + x0/65536.0 + " " + y0/65536.0);
 157         close();
 158         this.sx0 = this.x0 = x0;
 159         this.sy0 = this.y0 = y0;
 160         this.lastOrientation = 0;
 161     }
 162 
 163     public void lineJoin() {
 164         // System.out.println("Renderer: lineJoin");
 165         // do nothing
 166     }
 167 
 168     public void lineTo(int x1, int y1) {
 169         // System.out.println("Renderer: lineTo " + x1/65536.0 + " " + y1/65536.0);
 170 
 171         // Ignore horizontal lines
 172         // Next line will count flip
 173         if (y0 == y1) {
 174             this.x0 = x1;
 175             return;
 176         }
 177 
 178         int orientation = (y0 < y1) ? 1 : -1;
 179         if (lastOrientation == 0) {
 180             firstOrientation = orientation;
 181         } else if (orientation != lastOrientation) {
 182             ++flips;
 183         }
 184         lastOrientation = orientation;
 185 
 186         // Bias Y by 1 ULP so endpoints never lie on a scanline
 187         addEdge(x0, y0 | 0x1, x1, y1 | 0x1);
 188 
 189         this.x0 = x1;
 190         this.y0 = y1;
 191     }
 192 
 193     public void close() {
 194         // System.out.println("Renderer: close");
 195 
 196         int orientation = lastOrientation;
 197         if (y0 != sy0) {
 198             orientation = (y0 < sy0) ? 1 : -1;
 199         }
 200         if (orientation != firstOrientation) {
 201             ++flips;
 202         }
 203         lineTo(sx0, sy0);
 204     }
 205 
 206     public void end() {
 207         close();
 208         // System.out.println("Renderer: end");
 209         // do nothing
 210     }
 211 
 212     // Scan convert a single edge
 213     private void computeCrossingsForEdge(int index,
 214                                          int boundsMinY, int boundsMaxY) {
 215         int iy0 = edges[index + 1];
 216         int iy1 = edges[index + 3];
 217 
 218         // Clip to valid Y range
 219         int clipy0 = (iy0 > boundsMinY) ? iy0 : boundsMinY;
 220         int clipy1 = (iy1 < boundsMaxY) ? iy1 : boundsMaxY;
 221 
 222         int minY = ((clipy0 + HYSTEP) & YMASK) + HYSTEP;
 223         int maxY = ((clipy1 - HYSTEP) & YMASK) + HYSTEP;
 224 
 225         // IMPL_NOTE - If line falls outside the valid X range, could
 226         // draw a vertical line instead
 227 
 228         // Exit if no scanlines are crossed
 229         if (minY > maxY) {
 230             return;
 231         }
 232 
 233         // Scan convert line using a DDA approach
 234 
 235         int ix0 = edges[index];
 236         int ix1 = edges[index + 2];
 237         long dx = ((long) ix1) - ix0;
 238         long dy = ((long) iy1) - iy0;
 239 
 240         // Compute first crossing point at y = minY
 241         int orientation = edges[index + 4];
 242         int y = minY;
 243         long lx = (((long) y) - iy0)*dx/dy + ix0;
 244         addCrossing(y >> YSHIFT, (int)(lx >> XSHIFT), orientation);
 245 
 246         // Advance y to next scanline, exit if past endpoint
 247         y += YSTEP;
 248         if (y > maxY) {
 249             return;
 250         }
 251 
 252         // Compute xstep only if additional scanlines are crossed
 253         // For each scanline, add xstep to lx and YSTEP to y and
 254         // emit the new crossing
 255         long xstep = ((long)YSTEP*dx)/dy;
 256         for (; y <= maxY; y += YSTEP) {
 257             lx += xstep;
 258             addCrossing(y >> YSHIFT, (int)(lx >> XSHIFT), orientation);
 259         }
 260     }
 261 
 262     private void computeBounds() {
 263         rasterMinX = crossingMinX & ~SUBPIXEL_MASK_X;
 264         rasterMaxX = crossingMaxX | SUBPIXEL_MASK_X;
 265         rasterMinY = crossingMinY & ~SUBPIXEL_MASK_Y;
 266         rasterMaxY = crossingMaxY | SUBPIXEL_MASK_Y;
 267 
 268         // If nothing was drawn, we have:
 269         // minX = Integer.MAX_VALUE and maxX = Integer.MIN_VALUE
 270         // so nothing to render
 271         if (rasterMinX > rasterMaxX || rasterMinY > rasterMaxY) {
 272             rasterMinX = 0;
 273             rasterMaxX = -1;
 274             rasterMinY = 0;
 275             rasterMaxY = -1;
 276             return;
 277         }
 278 
 279         if (rasterMinX < boundsMinX >> XSHIFT) {
 280             rasterMinX = boundsMinX >> XSHIFT;
 281         }
 282         if (rasterMinY < boundsMinY >> YSHIFT) {
 283             rasterMinY = boundsMinY >> YSHIFT;
 284         }
 285         if (rasterMaxX > boundsMaxX >> XSHIFT) {
 286             rasterMaxX = boundsMaxX >> XSHIFT;
 287         }
 288         if (rasterMaxY > boundsMaxY >> YSHIFT) {
 289             rasterMaxY = boundsMaxY >> YSHIFT;
 290         }
 291     }
 292 
 293     private int clamp(int x, int min, int max) {
 294         if (x < min) {
 295             return min;
 296         } else if (x > max) {
 297             return max;
 298         }
 299         return x;
 300     }
 301 
 302     private void _endRendering() {
 303         if (flips == 0) {
 304             bboxX0 = bboxY0 = 0;
 305             bboxX1 = bboxY1 = -1;
 306             return;
 307         }
 308 
 309         // Special case for filling a single rect with a flat, opaque color
 310         // REMIND: This special case was not originally written to fill a
 311         // cache object and called directly to a Blit - it needs some code
 312         // to fill the cache instead to be useful for this usage...
 313         if (false /* Does not work with cache (yet?) */ &&
 314             edgeIdx == 10 &&
 315             edges[0] == edges[2] &&
 316             edges[1] == edges[6] &&
 317             edges[3] == edges[8] &&
 318             edges[5] == edges[7] &&
 319             Math.abs(edges[0] - edges[5]) > MIN_QUAD_OPT_WIDTH)
 320         {
 321 
 322             int x0 = edges[0] >> XSHIFT;
 323             int y0 = edges[1] >> YSHIFT;
 324             int x1 = edges[5] >> XSHIFT;
 325             int y1 = edges[3] >> YSHIFT;
 326 
 327             if (x0 > x1) {
 328                 int tmp = x0;
 329                 x0 = x1;
 330                 x1 = tmp;
 331             }
 332             if (y0 > y1) {
 333                 int tmp = y0;
 334                 y0 = y1;
 335                 y1 = tmp;
 336             }
 337 
 338             int bMinX = this.boundsMinX >> XSHIFT;
 339             int bMinY = this.boundsMinY >> YSHIFT;
 340             int bMaxX = this.boundsMaxX >> XSHIFT;
 341             int bMaxY = this.boundsMaxY >> YSHIFT;
 342 
 343             // Clip to image bounds in supersampled coordinates
 344             x0 = clamp(x0, bMinX, bMaxX);
 345             x1 = clamp(x1, bMinX, bMaxX);
 346             y0 = clamp(y0, bMinY, bMaxY);
 347             y1 = clamp(y1, bMinY, bMaxY);
 348 
 349             /*
 350              * REMIND: Need to fill the cache here instead...
 351             Blit.fillRectSrcOver(this,
 352                                  imageData, imageType,
 353                                  imageOffset,
 354                                  imageScanlineStride, imagePixelStride,
 355                                  width, height,
 356                                  x0, y0, x1, y1,
 357                                  cred, cgreen, cblue);
 358             */
 359 
 360             bboxX0 = x0 >> SUBPIXEL_LG_POSITIONS_X;
 361             bboxY0 = y0 >> SUBPIXEL_LG_POSITIONS_Y;
 362             bboxX1 = (x1 + SUBPIXEL_POSITIONS_X - 1)
 363                 >> SUBPIXEL_LG_POSITIONS_X;
 364             bboxY1 = (y1 + SUBPIXEL_POSITIONS_Y - 1)
 365                 >> SUBPIXEL_LG_POSITIONS_Y;
 366 
 367             return;
 368         }
 369 
 370         int minY = (edgeMinY > boundsMinY) ? edgeMinY : boundsMinY;
 371         int maxY = (edgeMaxY < boundsMaxY) ? edgeMaxY : boundsMaxY;
 372 
 373         // Check for empty intersection of primitive with the drawing area
 374         if (minY > maxY) {
 375             bboxX0 = bboxY0 = 0;
 376             bboxX1 = bboxY1 = -1;
 377             return;
 378         }
 379 
 380         // Compute Y extent in subpixel coordinates
 381         int iminY = (minY >> YSHIFT) & ~SUBPIXEL_MASK_Y;
 382         int imaxY = (maxY >> YSHIFT) | SUBPIXEL_MASK_Y;
 383         int yextent = (imaxY - iminY) + 1;
 384 
 385         // Maximum number of crossings
 386         int size = flips*yextent;
 387 
 388         int bmax = (boundsMaxY >> YSHIFT) - 1;
 389         if (imaxY > bmax) {
 390             imaxY = bmax;
 391         }
 392 
 393         // Initialize X bounds, will be refined for each strip
 394         bboxX0 = Integer.MAX_VALUE;
 395         bboxX1 = Integer.MIN_VALUE;
 396 
 397         // Set Y bounds
 398         bboxY0 = iminY >> SUBPIXEL_LG_POSITIONS_Y;
 399         bboxY1 = (imaxY + SUBPIXEL_POSITIONS_Y - 1) >> SUBPIXEL_LG_POSITIONS_Y;
 400 
 401         // Compute number of rows that can be processing using
 402         // a crossings table no larger than DEFAULT_CROSSINGS_SIZE.
 403         // However, we must process at least one row, so we grow the table
 404         // temporarily if needed.  This would require an object with a
 405         // huge number of flips.
 406         int rows = DEFAULT_CROSSINGS_SIZE/(flips*SUBPIXEL_POSITIONS_Y);
 407         rows = Math.min(rows, yextent);
 408         rows = Math.max(rows, 1);
 409         for (int i = iminY; i <= imaxY; i += rows*SUBPIXEL_POSITIONS_Y) {
 410             // Compute index of last scanline to be processed in this pass
 411             int last = Math.min(i + rows*SUBPIXEL_POSITIONS_Y - 1, imaxY);
 412             setCrossingsExtents(i, last, flips);
 413 
 414             int bminY = i << YSHIFT;
 415             int bmaxY = (last << YSHIFT) | ~YMASK;
 416 
 417             // Process edges from the edge list
 418             int maxIdx = edgeIdx;
 419             for (int index = 0; index < maxIdx; index += 5) {
 420                 // Test y1 < min:
 421                 //
 422                 // If edge lies entirely above current strip,
 423                 // discard it
 424                 if (edges[index + 3] < bminY) {
 425                     // Overwrite the edge with the last edge
 426                     edgeIdx -= 5;
 427                     int fidx = edgeIdx;
 428                     int tidx = index;
 429                     edges[tidx++] = edges[fidx++];
 430                     edges[tidx++] = edges[fidx++];
 431                     edges[tidx++] = edges[fidx++];
 432                     edges[tidx++] = edges[fidx++];
 433                     edges[tidx  ] = edges[fidx  ];
 434 
 435                     maxIdx -= 5;
 436                     index -= 5;
 437                     continue;
 438                 }
 439 
 440                 // Test y0 > max:
 441                 //
 442                 // If edge lies entirely below current strip,
 443                 // skip it for now
 444                 if (edges[index + 1] > bmaxY) {
 445                     continue;
 446                 }
 447 
 448                 computeCrossingsForEdge(index, bminY, bmaxY);
 449             }
 450 
 451             computeBounds();
 452             if (rasterMaxX < rasterMinX) {
 453                 continue;
 454             }
 455 
 456             bboxX0 = Math.min(bboxX0,
 457                               rasterMinX >> SUBPIXEL_LG_POSITIONS_X);
 458             bboxX1 = Math.max(bboxX1,
 459                               (rasterMaxX + SUBPIXEL_POSITIONS_X - 1)
 460                               >> SUBPIXEL_LG_POSITIONS_X);
 461             renderStrip();
 462         }
 463 
 464         // Free up any unusually large scratchpad memory used by the
 465         // preceding primitive
 466         crossingListFinished();
 467     }
 468 
 469     public void endRendering() {
 470         // Set up the cache to accumulate the bounding box
 471         if (cache != null) {
 472             cache.bboxX0 = Integer.MAX_VALUE;
 473             cache.bboxY0 = Integer.MAX_VALUE;
 474             cache.bboxX1 = Integer.MIN_VALUE;
 475             cache.bboxY1 = Integer.MIN_VALUE;
 476         }
 477 
 478         _endRendering();
 479     }
 480 
 481     public void getBoundingBox(int[] bbox) {
 482         bbox[0] = bboxX0;
 483         bbox[1] = bboxY0;
 484         bbox[2] = bboxX1 - bboxX0;
 485         bbox[3] = bboxY1 - bboxY0;
 486     }
 487 
 488     private void renderStrip() {
 489         // Grow rowAA according to the raster width
 490         int width = (rasterMaxX - rasterMinX + 1) >> SUBPIXEL_LG_POSITIONS_X;
 491         alphaWidth = width;
 492 
 493         // Allocate one extra entry in rowAA to avoid a conditional in
 494         // the rendering loop
 495         int bufLen = width + 1;
 496         if (this.rowAA == null || this.rowAA.length < bufLen) {
 497             this.rowAA = new byte[bufLen];
 498         }
 499 
 500         // Mask to determine the relevant bit of the crossing sum
 501         // 0x1 if EVEN_ODD, all bits if NON_ZERO
 502         int mask = (windingRule == WIND_EVEN_ODD) ? 0x1 : ~0x0;
 503 
 504         int y = 0;
 505         int prevY = rasterMinY - 1;
 506 
 507         int minX = Integer.MAX_VALUE;
 508         int maxX = Integer.MIN_VALUE;
 509 
 510         iterateCrossings();
 511         while (hasMoreCrossingRows()) {
 512             y = crossingY;
 513 
 514             // Emit any skipped rows
 515             for (int j = prevY + 1; j < y; j++) {
 516                 if (((j & SUBPIXEL_MASK_Y) == SUBPIXEL_MASK_Y) ||
 517                     (j == rasterMaxY)) {
 518                     emitRow(j >> SUBPIXEL_LG_POSITIONS_Y, 0, -1);
 519                 }
 520             }
 521             prevY = y;
 522 
 523             if (crossingRowIndex < crossingRowCount) {
 524                 int lx = crossings[crossingRowOffset + crossingRowIndex];
 525                 lx >>= 1;
 526                 int hx = crossings[crossingRowOffset + crossingRowCount - 1];
 527                 hx >>= 1;
 528                 int x0 = lx > rasterMinX ? lx : rasterMinX;
 529                 int x1 = hx < rasterMaxX ? hx : rasterMaxX;
 530                 x0 -= rasterMinX;
 531                 x1 -= rasterMinX;
 532 
 533                 minX = Math.min(minX, x0 >> SUBPIXEL_LG_POSITIONS_X);
 534                 maxX = Math.max(maxX, x1 >> SUBPIXEL_LG_POSITIONS_X);
 535             }
 536 
 537             int sum = 0;
 538             int prev = rasterMinX;
 539             while (crossingRowIndex < crossingRowCount) {
 540                 int crxo = crossings[crossingRowOffset + crossingRowIndex];
 541                 crossingRowIndex++;
 542 
 543                 int crx = crxo >> 1;
 544                 int crorientation = ((crxo & 0x1) == 0x1) ? 1 : -1;
 545 
 546                 if ((sum & mask) != 0) {
 547                     // Clip to active X range, if x1 < x0 loop will
 548                     // have no effect
 549                     int x0 = prev > rasterMinX ? prev : rasterMinX;
 550                     int x1 =  crx < rasterMaxX ?  crx : rasterMaxX;
 551 
 552                     // Empty spans
 553                     if (x1 > x0) {
 554                         x0 -= rasterMinX;
 555                         x1 -= rasterMinX;
 556 
 557                         // Accumulate alpha, equivalent to:
 558                         //   for (int x = x0; x < x1; x++) {
 559                         //       ++rowAA[x >> SUBPIXEL_LG_POSITIONS_X];
 560                         //   }
 561                         //
 562                         // In the middle of the span, we can update a full
 563                         // pixel at a time (i.e., SUBPIXEL_POSITIONS_X
 564                         // subpixels)
 565 
 566                         int x = x0 >> SUBPIXEL_LG_POSITIONS_X;
 567                         int xmaxm1 = (x1 - 1) >> SUBPIXEL_LG_POSITIONS_X;
 568                         if (x == xmaxm1) {
 569                             // Start and end in same pixel
 570                             rowAA[x] += x1 - x0;
 571                         } else {
 572                             // Start and end in different pixels
 573                             rowAA[x++] += SUBPIXEL_POSITIONS_X -
 574                                 (x0 & SUBPIXEL_MASK_X);
 575                             int xmax = x1 >> SUBPIXEL_LG_POSITIONS_X;
 576                             while (x < xmax) {
 577                                 rowAA[x++] += SUBPIXEL_POSITIONS_X;
 578                             }
 579                             // Note - at this point it is possible that
 580                             // x == width, which implies that
 581                             // x1 & SUBPIXEL_MASK_X == 0.  We allocate
 582                             // one extra entry in rowAA so this
 583                             // assignment will be harmless.  The alternative
 584                             // is an extra conditional here, or some other
 585                             // scheme to deal with the last pixel better.
 586                             rowAA[x] += x1 & SUBPIXEL_MASK_X;
 587                         }
 588                     }
 589                 }
 590                 sum += crorientation;
 591                 prev = crx;
 592             }
 593 
 594             // Every SUBPIXEL_POSITIONS rows, output an antialiased row
 595             if (((y & SUBPIXEL_MASK_Y) == SUBPIXEL_MASK_Y) ||
 596                 (y == rasterMaxY)) {
 597                 emitRow(y >> SUBPIXEL_LG_POSITIONS_Y, minX, maxX);
 598                 minX = Integer.MAX_VALUE;
 599                 maxX = Integer.MIN_VALUE;
 600             }
 601         }
 602 
 603         // Emit final row
 604         for (int j = prevY + 1; j <= rasterMaxY; j++) {
 605             if (((j & SUBPIXEL_MASK_Y) == SUBPIXEL_MASK_Y) ||
 606                 (j == rasterMaxY)) {
 607                 emitRow(j >> SUBPIXEL_LG_POSITIONS_Y, minX, maxX);
 608                 minX = Integer.MAX_VALUE;
 609                 maxX = Integer.MIN_VALUE;
 610             }
 611         }
 612     }
 613 
 614     private void clearAlpha(byte[] alpha,
 615                             int width,
 616                             int minX, int maxX) {
 617         if (maxX >= minX) {
 618             int w = maxX - minX + 1;
 619             if (w + minX > width) {
 620                 w = width - minX;
 621             }
 622 
 623             int aidx = minX;
 624             for (int i = 0; i < w; i++, aidx++) {
 625                 alpha[aidx] = (byte)0;
 626             }
 627         }
 628     }
 629 
 630     private void emitRow(int y, int minX, int maxX) {
 631         // Copy rowAA data into the cache if one is present
 632         if (cache != null) {
 633             if (maxX >= minX) {
 634                 int x0 = minX + (rasterMinX >> SUBPIXEL_LG_POSITIONS_X);
 635                 int x1 = maxX + (rasterMinX >> SUBPIXEL_LG_POSITIONS_X);
 636 
 637                 cache.startRow(y, x0, x1);
 638                 int srcIdx = minX;
 639 
 640                 // Perform run-length encoding
 641                 // and store results in the cache
 642                 byte startVal = rowAA[srcIdx++];
 643                 int runLen = 1;
 644                 while (srcIdx <= maxX) {
 645                     byte nextVal = rowAA[srcIdx++];
 646                     if (nextVal == startVal && runLen < 255) {
 647                         ++runLen;
 648                     } else {
 649                         cache.addRLERun(startVal, runLen);
 650 
 651                         runLen = 1;
 652                         startVal = nextVal;
 653                     }
 654                 }
 655                 cache.addRLERun(startVal, runLen);
 656                 cache.addRLERun((byte)0, 0);
 657             }
 658         }
 659 
 660         clearAlpha(rowAA,
 661                    alphaWidth,
 662                    minX, maxX);
 663     }
 664 
 665     public void setCache(PiscesCache cache) {
 666         this.cache = cache;
 667     }
 668 
 669     // Edge list data
 670 
 671     private int[] edges = new int[5*INITIAL_EDGES];
 672     private int edgeIdx = 0;
 673     private int edgeMinY = Integer.MAX_VALUE;
 674     private int edgeMaxY = Integer.MIN_VALUE;
 675 
 676     private void addEdge(int x0, int y0, int x1, int y1) {
 677         int newLen = edgeIdx + 5;
 678         if (edges.length < newLen) {
 679             int[] tmp = new int[Math.max(11*edges.length/10, newLen)];
 680             System.arraycopy(edges, 0, tmp, 0, edgeIdx);
 681             this.edges = tmp;
 682         }
 683 
 684         int orientation = 1;
 685         if (y0 > y1) {
 686             int tmp = y0;
 687             y0 = y1;
 688             y1 = tmp;
 689 
 690             orientation = -1;
 691         }
 692 
 693         // Skip edges that don't cross a subsampled scanline
 694         int eminY = ((y0 + HYSTEP) & YMASK);
 695         int emaxY = ((y1 - HYSTEP) & YMASK);
 696         if (eminY > emaxY) {
 697             return;
 698         }
 699 
 700         if (orientation == -1) {
 701             int tmp = x0;
 702             x0 = x1;
 703             x1 = tmp;
 704         }
 705 
 706         edges[edgeIdx++] = x0;
 707         edges[edgeIdx++] = y0;
 708         edges[edgeIdx++] = x1;
 709         edges[edgeIdx++] = y1;
 710         edges[edgeIdx++] = orientation;
 711 
 712         // Update Y bounds of primitive
 713         if (y0 < edgeMinY) {
 714             edgeMinY = y0;
 715         }
 716         if (y1 > edgeMaxY) {
 717             edgeMaxY = y1;
 718         }
 719     }
 720 
 721     private void resetEdges() {
 722         this.edgeIdx = 0;
 723         this.edgeMinY = Integer.MAX_VALUE;
 724         this.edgeMaxY = Integer.MIN_VALUE;
 725     }
 726 
 727     // Crossing list data
 728 
 729     private int[] crossingIndices;
 730     private int[] crossings;
 731     private int crossingMinY;
 732     private int crossingMaxY;
 733     private int crossingMinX = Integer.MAX_VALUE;
 734     private int crossingMaxX = Integer.MIN_VALUE;
 735     private int crossingMaxXEntries;
 736     private int numCrossings = 0;
 737     private boolean crossingsSorted = false;
 738 
 739     private int crossingY;
 740     private int crossingRowCount;
 741     private int crossingRowOffset;
 742     private int crossingRowIndex;
 743 
 744     private void setCrossingsExtents(int minY, int maxY, int maxXEntries) {
 745         int yextent = maxY - minY + 1;
 746 
 747         // Grow indices array as needed
 748         if (crossingIndices == null || crossingIndices.length < yextent) {
 749             this.crossingIndices =
 750                 new int[Math.max(yextent, DEFAULT_INDICES_SIZE)];
 751         }
 752         // Grow crossings array as needed
 753         if (crossings == null || crossings.length < yextent*maxXEntries) {
 754             this.crossings = new int[Math.max(yextent*maxXEntries,
 755                                               DEFAULT_CROSSINGS_SIZE)];
 756         }
 757         this.crossingMinY = minY;
 758         this.crossingMaxY = maxY;
 759         this.crossingMaxXEntries = maxXEntries;
 760         resetCrossings();
 761     }
 762 
 763     private void resetCrossings() {
 764         int yextent = crossingMaxY - crossingMinY + 1;
 765         int start = 0;
 766         for (int i = 0; i < yextent; i++) {
 767             crossingIndices[i] = start;
 768             start += crossingMaxXEntries;
 769         }
 770         crossingMinX = Integer.MAX_VALUE;
 771         crossingMaxX = Integer.MIN_VALUE;
 772         numCrossings = 0;
 773         crossingsSorted = false;
 774     }
 775 
 776     // Free sorting arrays if larger than maximum size
 777     private void crossingListFinished() {
 778         if (crossings != null && crossings.length > DEFAULT_CROSSINGS_SIZE) {
 779             crossings = new int[DEFAULT_CROSSINGS_SIZE];
 780         }
 781         if (crossingIndices != null
 782                 && crossingIndices.length > DEFAULT_INDICES_SIZE)
 783         {
 784             crossingIndices = new int[DEFAULT_INDICES_SIZE];
 785         }
 786     }
 787 
 788     private void sortCrossings(int[] x, int off, int len) {
 789         for (int i = off + 1; i < off + len; i++) {
 790             int j = i;
 791             int xj = x[j];
 792             int xjm1;
 793 
 794             while (j > off && (xjm1 = x[j - 1]) > xj) {
 795                 x[j] = xjm1;
 796                 x[j - 1] = xj;
 797                 j--;
 798             }
 799         }
 800     }
 801 
 802     private void sortCrossings() {
 803         int start = 0;
 804         for (int i = 0; i <= crossingMaxY - crossingMinY; i++) {
 805             sortCrossings(crossings, start, crossingIndices[i] - start);
 806             start += crossingMaxXEntries;
 807         }
 808     }
 809 
 810     private void addCrossing(int y, int x, int orientation) {
 811         if (x < crossingMinX) {
 812             crossingMinX = x;
 813         }
 814         if (x > crossingMaxX) {
 815             crossingMaxX = x;
 816         }
 817 
 818         int index = crossingIndices[y - crossingMinY]++;
 819         x <<= 1;
 820         crossings[index] = (orientation == 1) ? (x | 0x1) : x;
 821 
 822         ++numCrossings;
 823     }
 824 
 825     private void iterateCrossings() {
 826         if (!crossingsSorted) {
 827             sortCrossings();
 828             crossingsSorted = true;
 829         }
 830         crossingY = crossingMinY - 1;
 831         crossingRowOffset = -crossingMaxXEntries;
 832     }
 833 
 834     private boolean hasMoreCrossingRows() {
 835         if (++crossingY <= crossingMaxY) {
 836             crossingRowOffset += crossingMaxXEntries;
 837             int y = crossingY - crossingMinY;
 838             crossingRowCount = crossingIndices[y] - y*crossingMaxXEntries;
 839             crossingRowIndex = 0;
 840             return true;
 841         } else {
 842             return false;
 843         }
 844     }
 845 }