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