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.length > DEFAULT_CROSSINGS_SIZE) {
779 crossings = new int[DEFAULT_CROSSINGS_SIZE];
780 }
781 if (crossingIndices.length > DEFAULT_INDICES_SIZE) {
782 crossingIndices = new int[DEFAULT_INDICES_SIZE];
783 }
784 }
785
786 private void sortCrossings(int[] x, int off, int len) {
787 for (int i = off + 1; i < off + len; i++) {
788 int j = i;
789 int xj = x[j];
790 int xjm1;
791
792 while (j > off && (xjm1 = x[j - 1]) > xj) {
793 x[j] = xjm1;
794 x[j - 1] = xj;
795 j--;
796 }
797 }
798 }
799
800 private void sortCrossings() {
801 int start = 0;
802 for (int i = 0; i <= crossingMaxY - crossingMinY; i++) {
803 sortCrossings(crossings, start, crossingIndices[i] - start);
804 start += crossingMaxXEntries;
805 }
806 }
807
808 private void addCrossing(int y, int x, int orientation) {
809 if (x < crossingMinX) {
810 crossingMinX = x;
811 }
812 if (x > crossingMaxX) {
813 crossingMaxX = x;
814 }
815
816 int index = crossingIndices[y - crossingMinY]++;
817 x <<= 1;
818 crossings[index] = (orientation == 1) ? (x | 0x1) : x;
819
820 ++numCrossings;
821 }
822
823 private void iterateCrossings() {
824 if (!crossingsSorted) {
825 sortCrossings();
826 crossingsSorted = true;
827 }
828 crossingY = crossingMinY - 1;
829 crossingRowOffset = -crossingMaxXEntries;
830 }
831
832 private boolean hasMoreCrossingRows() {
833 if (++crossingY <= crossingMaxY) {
834 crossingRowOffset += crossingMaxXEntries;
835 int y = crossingY - crossingMinY;
836 crossingRowCount = crossingIndices[y] - y*crossingMaxXEntries;
837 crossingRowIndex = 0;
838 return true;
839 } else {
840 return false;
841 }
842 }
843 }