1 /* 2 * Copyright (c) 2007, 2011, Oracle and/or its affiliates. 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. Oracle designates this 8 * particular file as subject to the "Classpath" exception as provided 9 * by Oracle 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 Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA 22 * or visit www.oracle.com if you need additional information or have any 23 * questions. 24 */ 25 26 package sun.java2d.pisces; 27 28 import sun.awt.geom.PathConsumer2D; 29 30 final class Renderer implements PathConsumer2D { 31 32 private class ScanlineIterator { 33 34 private int[] crossings; 35 36 // crossing bounds. The bounds are not necessarily tight (the scan line 37 // at minY, for example, might have no crossings). The x bounds will 38 // be accumulated as crossings are computed. 39 private final int maxY; 40 private int nextY; 41 42 // indices into the segment pointer lists. They indicate the "active" 43 // sublist in the segment lists (the portion of the list that contains 44 // all the segments that cross the next scan line). 45 private int edgeCount; 46 private int[] edgePtrs; 47 48 private static final int INIT_CROSSINGS_SIZE = 10; 49 50 // Preconditions: Only subpixel scanlines in the range 51 // (start <= subpixel_y <= end) will be evaluated. No 52 // edge may have a valid (i.e. inside the supplied clip) 53 // crossing that would be generated outside that range. 54 private ScanlineIterator(int start, int end) { 55 crossings = new int[INIT_CROSSINGS_SIZE]; 56 edgePtrs = new int[INIT_CROSSINGS_SIZE]; 57 58 nextY = start; 59 maxY = end; 60 edgeCount = 0; 61 } 62 63 private int next() { 64 int cury = nextY++; 65 int bucket = cury - boundsMinY; 66 int count = this.edgeCount; 67 int ptrs[] = this.edgePtrs; 68 int bucketcount = edgeBucketCounts[bucket]; 69 if ((bucketcount & 0x1) != 0) { 70 int newCount = 0; 71 for (int i = 0; i < count; i++) { 72 int ecur = ptrs[i]; 73 if (edges[ecur+YMAX] > cury) { 74 ptrs[newCount++] = ecur; 75 } 76 } 77 count = newCount; 78 } 79 ptrs = Helpers.widenArray(ptrs, count, bucketcount >> 1); 80 for (int ecur = edgeBuckets[bucket]; ecur != NULL; ecur = (int)edges[ecur+NEXT]) { 81 ptrs[count++] = ecur; 82 // REMIND: Adjust start Y if necessary 83 } 84 this.edgePtrs = ptrs; 85 this.edgeCount = count; 86 // if ((count & 0x1) != 0) { 87 // System.out.println("ODD NUMBER OF EDGES!!!!"); 88 // } 89 int xings[] = this.crossings; 90 if (xings.length < count) { 91 this.crossings = xings = new int[ptrs.length]; 92 } 93 for (int i = 0; i < count; i++) { 94 int ecur = ptrs[i]; 95 float curx = edges[ecur+CURX]; 96 int cross = ((int) curx) << 1; 97 edges[ecur+CURX] = curx + edges[ecur+SLOPE]; 98 if (edges[ecur+OR] > 0) { 99 cross |= 1; 100 } 101 int j = i; 102 while (--j >= 0) { 103 int jcross = xings[j]; 104 if (jcross <= cross) { 105 break; 106 } 107 xings[j+1] = jcross; 108 ptrs[j+1] = ptrs[j]; 109 } 110 xings[j+1] = cross; 111 ptrs[j+1] = ecur; 112 } 113 return count; 114 } 115 116 private boolean hasNext() { 117 return nextY < maxY; 118 } 119 120 private int curY() { 121 return nextY - 1; 122 } 123 } 124 125 126 ////////////////////////////////////////////////////////////////////////////// 127 // EDGE LIST 128 ////////////////////////////////////////////////////////////////////////////// 129 // TODO(maybe): very tempting to use fixed point here. A lot of opportunities 130 // for shifts and just removing certain operations altogether. 131 132 // common to all types of input path segments. 133 private static final int YMAX = 0; 134 private static final int CURX = 1; 135 // NEXT and OR are meant to be indices into "int" fields, but arrays must 136 // be homogenous, so every field is a float. However floats can represent 137 // exactly up to 26 bit ints, so we're ok. 138 private static final int OR = 2; 139 private static final int SLOPE = 3; 140 private static final int NEXT = 4; 141 142 private float edgeMinY = Float.POSITIVE_INFINITY; 143 private float edgeMaxY = Float.NEGATIVE_INFINITY; 144 private float edgeMinX = Float.POSITIVE_INFINITY; 145 private float edgeMaxX = Float.NEGATIVE_INFINITY; 146 147 private static final int SIZEOF_EDGE = 5; 148 // don't just set NULL to -1, because we want NULL+NEXT to be negative. 149 private static final int NULL = -SIZEOF_EDGE; 150 private float[] edges = null; 151 private static final int INIT_NUM_EDGES = 8; 152 private int[] edgeBuckets = null; 153 private int[] edgeBucketCounts = null; // 2*newedges + (1 if pruning needed) 154 private int numEdges; 155 156 private static final float DEC_BND = 20f; 157 private static final float INC_BND = 8f; 158 159 // each bucket is a linked list. this method adds eptr to the 160 // start of the "bucket"th linked list. 161 private void addEdgeToBucket(final int eptr, final int bucket) { 162 edges[eptr+NEXT] = edgeBuckets[bucket]; 163 edgeBuckets[bucket] = eptr; 164 edgeBucketCounts[bucket] += 2; 165 } 166 167 // Flattens using adaptive forward differencing. This only carries out 168 // one iteration of the AFD loop. All it does is update AFD variables (i.e. 169 // X0, Y0, D*[X|Y], COUNT; not variables used for computing scanline crossings). 170 private void quadBreakIntoLinesAndAdd(float x0, float y0, 171 final Curve c, 172 final float x2, final float y2) 173 { 174 final float QUAD_DEC_BND = 32; 175 final int countlg = 4; 176 int count = 1 << countlg; 177 int countsq = count * count; 178 float maxDD = Math.max(c.dbx / countsq, c.dby / countsq); 179 while (maxDD > QUAD_DEC_BND) { 180 maxDD /= 4; 181 count <<= 1; 182 } 183 184 countsq = count * count; 185 final float ddx = c.dbx / countsq; 186 final float ddy = c.dby / countsq; 187 float dx = c.bx / countsq + c.cx / count; 188 float dy = c.by / countsq + c.cy / count; 189 190 while (count-- > 1) { 191 float x1 = x0 + dx; 192 dx += ddx; 193 float y1 = y0 + dy; 194 dy += ddy; 195 addLine(x0, y0, x1, y1); 196 x0 = x1; 197 y0 = y1; 198 } 199 addLine(x0, y0, x2, y2); 200 } 201 202 // x0, y0 and x3,y3 are the endpoints of the curve. We could compute these 203 // using c.xat(0),c.yat(0) and c.xat(1),c.yat(1), but this might introduce 204 // numerical errors, and our callers already have the exact values. 205 // Another alternative would be to pass all the control points, and call c.set 206 // here, but then too many numbers are passed around. 207 private void curveBreakIntoLinesAndAdd(float x0, float y0, 208 final Curve c, 209 final float x3, final float y3) 210 { 211 final int countlg = 3; 212 int count = 1 << countlg; 213 214 // the dx and dy refer to forward differencing variables, not the last 215 // coefficients of the "points" polynomial 216 float dddx, dddy, ddx, ddy, dx, dy; 217 dddx = 2f * c.dax / (1 << (3 * countlg)); 218 dddy = 2f * c.day / (1 << (3 * countlg)); 219 220 ddx = dddx + c.dbx / (1 << (2 * countlg)); 221 ddy = dddy + c.dby / (1 << (2 * countlg)); 222 dx = c.ax / (1 << (3 * countlg)) + c.bx / (1 << (2 * countlg)) + c.cx / (1 << countlg); 223 dy = c.ay / (1 << (3 * countlg)) + c.by / (1 << (2 * countlg)) + c.cy / (1 << countlg); 224 225 // we use x0, y0 to walk the line 226 float x1 = x0, y1 = y0; 227 while (count > 0) { 228 while (Math.abs(ddx) > DEC_BND || Math.abs(ddy) > DEC_BND) { 229 dddx /= 8; 230 dddy /= 8; 231 ddx = ddx/4 - dddx; 232 ddy = ddy/4 - dddy; 233 dx = (dx - ddx) / 2; 234 dy = (dy - ddy) / 2; 235 count <<= 1; 236 } 237 // can only do this on even "count" values, because we must divide count by 2 238 while (count % 2 == 0 && Math.abs(dx) <= INC_BND && Math.abs(dy) <= INC_BND) { 239 dx = 2 * dx + ddx; 240 dy = 2 * dy + ddy; 241 ddx = 4 * (ddx + dddx); 242 ddy = 4 * (ddy + dddy); 243 dddx = 8 * dddx; 244 dddy = 8 * dddy; 245 count >>= 1; 246 } 247 count--; 248 if (count > 0) { 249 x1 += dx; 250 dx += ddx; 251 ddx += dddx; 252 y1 += dy; 253 dy += ddy; 254 ddy += dddy; 255 } else { 256 x1 = x3; 257 y1 = y3; 258 } 259 addLine(x0, y0, x1, y1); 260 x0 = x1; 261 y0 = y1; 262 } 263 } 264 265 private void addLine(float x1, float y1, float x2, float y2) { 266 float or = 1; // orientation of the line. 1 if y increases, 0 otherwise. 267 if (y2 < y1) { 268 or = y2; // no need to declare a temp variable. We have or. 269 y2 = y1; 270 y1 = or; 271 or = x2; 272 x2 = x1; 273 x1 = or; 274 or = 0; 275 } 276 final int firstCrossing = Math.max((int)Math.ceil(y1), boundsMinY); 277 final int lastCrossing = Math.min((int)Math.ceil(y2), boundsMaxY); 278 if (firstCrossing >= lastCrossing) { 279 return; 280 } 281 if (y1 < edgeMinY) { edgeMinY = y1; } 282 if (y2 > edgeMaxY) { edgeMaxY = y2; } 283 284 final float slope = (x2 - x1) / (y2 - y1); 285 286 if (slope > 0) { // <==> x1 < x2 287 if (x1 < edgeMinX) { edgeMinX = x1; } 288 if (x2 > edgeMaxX) { edgeMaxX = x2; } 289 } else { 290 if (x2 < edgeMinX) { edgeMinX = x2; } 291 if (x1 > edgeMaxX) { edgeMaxX = x1; } 292 } 293 294 final int ptr = numEdges * SIZEOF_EDGE; 295 edges = Helpers.widenArray(edges, ptr, SIZEOF_EDGE); 296 numEdges++; 297 edges[ptr+OR] = or; 298 edges[ptr+CURX] = x1 + (firstCrossing - y1) * slope; 299 edges[ptr+SLOPE] = slope; 300 edges[ptr+YMAX] = lastCrossing; 301 final int bucketIdx = firstCrossing - boundsMinY; 302 addEdgeToBucket(ptr, bucketIdx); 303 edgeBucketCounts[lastCrossing - boundsMinY] |= 1; 304 } 305 306 // END EDGE LIST 307 ////////////////////////////////////////////////////////////////////////////// 308 309 310 public static final int WIND_EVEN_ODD = 0; 311 public static final int WIND_NON_ZERO = 1; 312 313 // Antialiasing 314 final private int SUBPIXEL_LG_POSITIONS_X; 315 final private int SUBPIXEL_LG_POSITIONS_Y; 316 final private int SUBPIXEL_POSITIONS_X; 317 final private int SUBPIXEL_POSITIONS_Y; 318 final private int SUBPIXEL_MASK_X; 319 final private int SUBPIXEL_MASK_Y; 320 final int MAX_AA_ALPHA; 321 322 // Cache to store RLE-encoded coverage mask of the current primitive 323 PiscesCache cache; 324 325 // Bounds of the drawing region, at subpixel precision. 326 private final int boundsMinX, boundsMinY, boundsMaxX, boundsMaxY; 327 328 // Current winding rule 329 private final int windingRule; 330 331 // Current drawing position, i.e., final point of last segment 332 private float x0, y0; 333 334 // Position of most recent 'moveTo' command 335 private float pix_sx0, pix_sy0; 336 337 public Renderer(int subpixelLgPositionsX, int subpixelLgPositionsY, 338 int pix_boundsX, int pix_boundsY, 339 int pix_boundsWidth, int pix_boundsHeight, 340 int windingRule) 341 { 342 this.SUBPIXEL_LG_POSITIONS_X = subpixelLgPositionsX; 343 this.SUBPIXEL_LG_POSITIONS_Y = subpixelLgPositionsY; 344 this.SUBPIXEL_MASK_X = (1 << (SUBPIXEL_LG_POSITIONS_X)) - 1; 345 this.SUBPIXEL_MASK_Y = (1 << (SUBPIXEL_LG_POSITIONS_Y)) - 1; 346 this.SUBPIXEL_POSITIONS_X = 1 << (SUBPIXEL_LG_POSITIONS_X); 347 this.SUBPIXEL_POSITIONS_Y = 1 << (SUBPIXEL_LG_POSITIONS_Y); 348 this.MAX_AA_ALPHA = (SUBPIXEL_POSITIONS_X * SUBPIXEL_POSITIONS_Y); 349 350 this.windingRule = windingRule; 351 352 this.boundsMinX = pix_boundsX * SUBPIXEL_POSITIONS_X; 353 this.boundsMinY = pix_boundsY * SUBPIXEL_POSITIONS_Y; 354 this.boundsMaxX = (pix_boundsX + pix_boundsWidth) * SUBPIXEL_POSITIONS_X; 355 this.boundsMaxY = (pix_boundsY + pix_boundsHeight) * SUBPIXEL_POSITIONS_Y; 356 357 edges = new float[INIT_NUM_EDGES * SIZEOF_EDGE]; 358 numEdges = 0; 359 edgeBuckets = new int[boundsMaxY - boundsMinY]; 360 java.util.Arrays.fill(edgeBuckets, NULL); 361 edgeBucketCounts = new int[edgeBuckets.length + 1]; 362 } 363 364 private float tosubpixx(float pix_x) { 365 return pix_x * SUBPIXEL_POSITIONS_X; 366 } 367 private float tosubpixy(float pix_y) { 368 return pix_y * SUBPIXEL_POSITIONS_Y; 369 } 370 371 public void moveTo(float pix_x0, float pix_y0) { 372 closePath(); 373 this.pix_sx0 = pix_x0; 374 this.pix_sy0 = pix_y0; 375 this.y0 = tosubpixy(pix_y0); 376 this.x0 = tosubpixx(pix_x0); 377 } 378 379 public void lineTo(float pix_x1, float pix_y1) { 380 float x1 = tosubpixx(pix_x1); 381 float y1 = tosubpixy(pix_y1); 382 addLine(x0, y0, x1, y1); 383 x0 = x1; 384 y0 = y1; 385 } 386 387 private Curve c = new Curve(); 388 @Override public void curveTo(float x1, float y1, 389 float x2, float y2, 390 float x3, float y3) 391 { 392 final float xe = tosubpixx(x3); 393 final float ye = tosubpixy(y3); 394 c.set(x0, y0, tosubpixx(x1), tosubpixy(y1), tosubpixx(x2), tosubpixy(y2), xe, ye); 395 curveBreakIntoLinesAndAdd(x0, y0, c, xe, ye); 396 x0 = xe; 397 y0 = ye; 398 } 399 400 @Override public void quadTo(float x1, float y1, float x2, float y2) { 401 final float xe = tosubpixx(x2); 402 final float ye = tosubpixy(y2); 403 c.set(x0, y0, tosubpixx(x1), tosubpixy(y1), xe, ye); 404 quadBreakIntoLinesAndAdd(x0, y0, c, xe, ye); 405 x0 = xe; 406 y0 = ye; 407 } 408 409 public void closePath() { 410 // lineTo expects its input in pixel coordinates. 411 lineTo(pix_sx0, pix_sy0); 412 } 413 414 public void pathDone() { 415 closePath(); 416 } 417 418 419 @Override 420 public long getNativeConsumer() { 421 throw new InternalError("Renderer does not use a native consumer."); 422 } 423 424 private void _endRendering(final int pix_bboxx0, final int pix_bboxx1, 425 int ymin, int ymax) 426 { 427 // Mask to determine the relevant bit of the crossing sum 428 // 0x1 if EVEN_ODD, all bits if NON_ZERO 429 int mask = (windingRule == WIND_EVEN_ODD) ? 0x1 : ~0x0; 430 431 // add 2 to better deal with the last pixel in a pixel row. 432 int width = pix_bboxx1 - pix_bboxx0; 433 int[] alpha = new int[width+2]; 434 435 int bboxx0 = pix_bboxx0 << SUBPIXEL_LG_POSITIONS_X; 436 int bboxx1 = pix_bboxx1 << SUBPIXEL_LG_POSITIONS_X; 437 438 // Now we iterate through the scanlines. We must tell emitRow the coord 439 // of the first non-transparent pixel, so we must keep accumulators for 440 // the first and last pixels of the section of the current pixel row 441 // that we will emit. 442 // We also need to accumulate pix_bbox*, but the iterator does it 443 // for us. We will just get the values from it once this loop is done 444 int pix_maxX = Integer.MIN_VALUE; 445 int pix_minX = Integer.MAX_VALUE; 446 447 int y = boundsMinY; // needs to be declared here so we emit the last row properly. 448 ScanlineIterator it = this.new ScanlineIterator(ymin, ymax); 449 for ( ; it.hasNext(); ) { 450 int numCrossings = it.next(); 451 int[] crossings = it.crossings; 452 y = it.curY(); 453 454 if (numCrossings > 0) { 455 int lowx = crossings[0] >> 1; 456 int highx = crossings[numCrossings - 1] >> 1; 457 int x0 = Math.max(lowx, bboxx0); 458 int x1 = Math.min(highx, bboxx1); 459 460 pix_minX = Math.min(pix_minX, x0 >> SUBPIXEL_LG_POSITIONS_X); 461 pix_maxX = Math.max(pix_maxX, x1 >> SUBPIXEL_LG_POSITIONS_X); 462 } 463 464 int sum = 0; 465 int prev = bboxx0; 466 for (int i = 0; i < numCrossings; i++) { 467 int curxo = crossings[i]; 468 int curx = curxo >> 1; 469 // to turn {0, 1} into {-1, 1}, multiply by 2 and subtract 1. 470 int crorientation = ((curxo & 0x1) << 1) - 1; 471 if ((sum & mask) != 0) { 472 int x0 = Math.max(prev, bboxx0); 473 int x1 = Math.min(curx, bboxx1); 474 if (x0 < x1) { 475 x0 -= bboxx0; // turn x0, x1 from coords to indeces 476 x1 -= bboxx0; // in the alpha array. 477 478 int pix_x = x0 >> SUBPIXEL_LG_POSITIONS_X; 479 int pix_xmaxm1 = (x1 - 1) >> SUBPIXEL_LG_POSITIONS_X; 480 481 if (pix_x == pix_xmaxm1) { 482 // Start and end in same pixel 483 alpha[pix_x] += (x1 - x0); 484 alpha[pix_x+1] -= (x1 - x0); 485 } else { 486 int pix_xmax = x1 >> SUBPIXEL_LG_POSITIONS_X; 487 alpha[pix_x] += SUBPIXEL_POSITIONS_X - (x0 & SUBPIXEL_MASK_X); 488 alpha[pix_x+1] += (x0 & SUBPIXEL_MASK_X); 489 alpha[pix_xmax] -= SUBPIXEL_POSITIONS_X - (x1 & SUBPIXEL_MASK_X); 490 alpha[pix_xmax+1] -= (x1 & SUBPIXEL_MASK_X); 491 } 492 } 493 } 494 sum += crorientation; 495 prev = curx; 496 } 497 498 // even if this last row had no crossings, alpha will be zeroed 499 // from the last emitRow call. But this doesn't matter because 500 // maxX < minX, so no row will be emitted to the cache. 501 if ((y & SUBPIXEL_MASK_Y) == SUBPIXEL_MASK_Y) { 502 emitRow(alpha, y >> SUBPIXEL_LG_POSITIONS_Y, pix_minX, pix_maxX); 503 pix_minX = Integer.MAX_VALUE; 504 pix_maxX = Integer.MIN_VALUE; 505 } 506 } 507 508 // Emit final row 509 if (pix_maxX >= pix_minX) { 510 emitRow(alpha, y >> SUBPIXEL_LG_POSITIONS_Y, pix_minX, pix_maxX); 511 } 512 } 513 514 public void endRendering() { 515 int spminX = Math.max((int)Math.ceil(edgeMinX), boundsMinX); 516 int spmaxX = Math.min((int)Math.ceil(edgeMaxX), boundsMaxX); 517 int spminY = Math.max((int)Math.ceil(edgeMinY), boundsMinY); 518 int spmaxY = Math.min((int)Math.ceil(edgeMaxY), boundsMaxY); 519 520 int pminX = spminX >> SUBPIXEL_LG_POSITIONS_X; 521 int pmaxX = (spmaxX + SUBPIXEL_MASK_X) >> SUBPIXEL_LG_POSITIONS_X; 522 int pminY = spminY >> SUBPIXEL_LG_POSITIONS_Y; 523 int pmaxY = (spmaxY + SUBPIXEL_MASK_Y) >> SUBPIXEL_LG_POSITIONS_Y; 524 525 if (pminX > pmaxX || pminY > pmaxY) { 526 this.cache = new PiscesCache(boundsMinX >> SUBPIXEL_LG_POSITIONS_X, 527 boundsMinY >> SUBPIXEL_LG_POSITIONS_Y, 528 boundsMaxX >> SUBPIXEL_LG_POSITIONS_X, 529 boundsMaxY >> SUBPIXEL_LG_POSITIONS_Y); 530 return; 531 } 532 533 this.cache = new PiscesCache(pminX, pminY, pmaxX, pmaxY); 534 _endRendering(pminX, pmaxX, spminY, spmaxY); 535 } 536 537 public PiscesCache getCache() { 538 if (cache == null) { 539 throw new InternalError("cache not yet initialized"); 540 } 541 return cache; 542 } 543 544 private void emitRow(int[] alphaRow, int pix_y, int pix_from, int pix_to) { 545 // Copy rowAA data into the cache if one is present 546 if (cache != null) { 547 if (pix_to >= pix_from) { 548 cache.startRow(pix_y, pix_from); 549 550 // Perform run-length encoding and store results in the cache 551 int from = pix_from - cache.bboxX0; 552 int to = pix_to - cache.bboxX0; 553 554 int runLen = 1; 555 int startVal = alphaRow[from]; 556 for (int i = from + 1; i <= to; i++) { 557 int nextVal = startVal + alphaRow[i]; 558 if (nextVal == startVal) { 559 runLen++; 560 } else { 561 cache.addRLERun(startVal, runLen); 562 runLen = 1; 563 startVal = nextVal; 564 } 565 } 566 cache.addRLERun(startVal, runLen); 567 } 568 } 569 java.util.Arrays.fill(alphaRow, 0); 570 } 571 }