1 /*
2 * Copyright (c) 2007, 2018, 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.marlin;
27
28 import java.util.Arrays;
29 import sun.java2d.marlin.stats.Histogram;
30 import sun.java2d.marlin.stats.StatLong;
31
32 final class DHelpers implements MarlinConst {
33
34 private DHelpers() {
35 throw new Error("This is a non instantiable class");
36 }
37
38 static boolean within(final double x, final double y, final double err) {
39 final double d = y - x;
40 return (d <= err && d >= -err);
41 }
42
43 static double evalCubic(final double a, final double b,
44 final double c, final double d,
45 final double t)
46 {
47 return t * (t * (t * a + b) + c) + d;
48 }
49
50 static double evalQuad(final double a, final double b,
51 final double c, final double t)
52 {
53 return t * (t * a + b) + c;
54 }
55
56 static int quadraticRoots(final double a, final double b, final double c,
57 final double[] zeroes, final int off)
58 {
59 int ret = off;
60 if (a != 0.0d) {
61 final double dis = b*b - 4.0d * a * c;
62 if (dis > 0.0d) {
63 final double sqrtDis = Math.sqrt(dis);
64 // depending on the sign of b we use a slightly different
65 // algorithm than the traditional one to find one of the roots
66 // so we can avoid adding numbers of different signs (which
67 // might result in loss of precision).
68 if (b >= 0.0d) {
69 zeroes[ret++] = (2.0d * c) / (-b - sqrtDis);
70 zeroes[ret++] = (-b - sqrtDis) / (2.0d * a);
71 } else {
72 zeroes[ret++] = (-b + sqrtDis) / (2.0d * a);
73 zeroes[ret++] = (2.0d * c) / (-b + sqrtDis);
74 }
75 } else if (dis == 0.0d) {
76 zeroes[ret++] = -b / (2.0d * a);
77 }
78 } else if (b != 0.0d) {
79 zeroes[ret++] = -c / b;
80 }
81 return ret - off;
82 }
83
84 // find the roots of g(t) = d*t^3 + a*t^2 + b*t + c in [A,B)
85 static int cubicRootsInAB(final double d, double a, double b, double c,
86 final double[] pts, final int off,
87 final double A, final double B)
88 {
89 if (d == 0.0d) {
90 final int num = quadraticRoots(a, b, c, pts, off);
91 return filterOutNotInAB(pts, off, num, A, B) - off;
92 }
93 // From Graphics Gems:
94 // https://github.com/erich666/GraphicsGems/blob/master/gems/Roots3And4.c
95 // (also from awt.geom.CubicCurve2D. But here we don't need as
96 // much accuracy and we don't want to create arrays so we use
97 // our own customized version).
98
99 // normal form: x^3 + ax^2 + bx + c = 0
100
101 /*
102 * TODO: cleanup all that code after reading Roots3And4.c
103 */
104 a /= d;
105 b /= d;
106 c /= d;
107
108 // substitute x = y - A/3 to eliminate quadratic term:
109 // x^3 +Px + Q = 0
110 //
111 // Since we actually need P/3 and Q/2 for all of the
112 // calculations that follow, we will calculate
113 // p = P/3
114 // q = Q/2
115 // instead and use those values for simplicity of the code.
116 final double sub = (1.0d / 3.0d) * a;
117 final double sq_A = a * a;
118 final double p = (1.0d / 3.0d) * ((-1.0d / 3.0d) * sq_A + b);
119 final double q = (1.0d / 2.0d) * ((2.0d / 27.0d) * a * sq_A - sub * b + c);
120
121 // use Cardano's formula
122
123 final double cb_p = p * p * p;
124 final double D = q * q + cb_p;
125
126 int num;
127 if (D < 0.0d) {
128 // see: http://en.wikipedia.org/wiki/Cubic_function#Trigonometric_.28and_hyperbolic.29_method
129 final double phi = (1.0d / 3.0d) * Math.acos(-q / Math.sqrt(-cb_p));
130 final double t = 2.0d * Math.sqrt(-p);
131
132 pts[off ] = ( t * Math.cos(phi) - sub);
133 pts[off + 1] = (-t * Math.cos(phi + (Math.PI / 3.0d)) - sub);
134 pts[off + 2] = (-t * Math.cos(phi - (Math.PI / 3.0d)) - sub);
135 num = 3;
136 } else {
137 final double sqrt_D = Math.sqrt(D);
138 final double u = Math.cbrt(sqrt_D - q);
139 final double v = - Math.cbrt(sqrt_D + q);
140
141 pts[off ] = (u + v - sub);
142 num = 1;
143
144 if (within(D, 0.0d, 1e-8d)) {
145 pts[off + 1] = ((-1.0d / 2.0d) * (u + v) - sub);
146 num = 2;
147 }
148 }
149
150 return filterOutNotInAB(pts, off, num, A, B) - off;
151 }
152
153 // returns the index 1 past the last valid element remaining after filtering
154 static int filterOutNotInAB(final double[] nums, final int off, final int len,
155 final double a, final double b)
156 {
157 int ret = off;
158 for (int i = off, end = off + len; i < end; i++) {
159 if (nums[i] >= a && nums[i] < b) {
160 nums[ret++] = nums[i];
161 }
162 }
163 return ret;
164 }
165
166 static double fastLineLen(final double x0, final double y0,
167 final double x1, final double y1)
168 {
169 final double dx = x1 - x0;
170 final double dy = y1 - y0;
171
172 // use manhattan norm:
173 return Math.abs(dx) + Math.abs(dy);
174 }
175
176 static double linelen(final double x0, final double y0,
177 final double x1, final double y1)
178 {
179 final double dx = x1 - x0;
180 final double dy = y1 - y0;
181 return Math.sqrt(dx * dx + dy * dy);
182 }
183
184 static double fastQuadLen(final double x0, final double y0,
185 final double x1, final double y1,
186 final double x2, final double y2)
187 {
188 final double dx1 = x1 - x0;
189 final double dx2 = x2 - x1;
190 final double dy1 = y1 - y0;
191 final double dy2 = y2 - y1;
192
193 // use manhattan norm:
194 return Math.abs(dx1) + Math.abs(dx2)
195 + Math.abs(dy1) + Math.abs(dy2);
196 }
197
198 static double quadlen(final double x0, final double y0,
199 final double x1, final double y1,
200 final double x2, final double y2)
201 {
202 return (linelen(x0, y0, x1, y1)
203 + linelen(x1, y1, x2, y2)
204 + linelen(x0, y0, x2, y2)) / 2.0d;
205 }
206
207 static double fastCurvelen(final double x0, final double y0,
208 final double x1, final double y1,
209 final double x2, final double y2,
210 final double x3, final double y3)
211 {
212 final double dx1 = x1 - x0;
213 final double dx2 = x2 - x1;
214 final double dx3 = x3 - x2;
215 final double dy1 = y1 - y0;
216 final double dy2 = y2 - y1;
217 final double dy3 = y3 - y2;
218
219 // use manhattan norm:
220 return Math.abs(dx1) + Math.abs(dx2) + Math.abs(dx3)
221 + Math.abs(dy1) + Math.abs(dy2) + Math.abs(dy3);
222 }
223
224 static double curvelen(final double x0, final double y0,
225 final double x1, final double y1,
226 final double x2, final double y2,
227 final double x3, final double y3)
228 {
229 return (linelen(x0, y0, x1, y1)
230 + linelen(x1, y1, x2, y2)
231 + linelen(x2, y2, x3, y3)
232 + linelen(x0, y0, x3, y3)) / 2.0d;
233 }
234
235 // finds values of t where the curve in pts should be subdivided in order
236 // to get good offset curves a distance of w away from the middle curve.
237 // Stores the points in ts, and returns how many of them there were.
238 static int findSubdivPoints(final DCurve c, final double[] pts,
239 final double[] ts, final int type,
240 final double w2)
241 {
242 final double x12 = pts[2] - pts[0];
243 final double y12 = pts[3] - pts[1];
244 // if the curve is already parallel to either axis we gain nothing
245 // from rotating it.
246 if ((y12 != 0.0d && x12 != 0.0d)) {
247 // we rotate it so that the first vector in the control polygon is
248 // parallel to the x-axis. This will ensure that rotated quarter
249 // circles won't be subdivided.
250 final double hypot = Math.sqrt(x12 * x12 + y12 * y12);
251 final double cos = x12 / hypot;
252 final double sin = y12 / hypot;
253 final double x1 = cos * pts[0] + sin * pts[1];
254 final double y1 = cos * pts[1] - sin * pts[0];
255 final double x2 = cos * pts[2] + sin * pts[3];
256 final double y2 = cos * pts[3] - sin * pts[2];
257 final double x3 = cos * pts[4] + sin * pts[5];
258 final double y3 = cos * pts[5] - sin * pts[4];
259
260 switch(type) {
261 case 8:
262 final double x4 = cos * pts[6] + sin * pts[7];
263 final double y4 = cos * pts[7] - sin * pts[6];
264 c.set(x1, y1, x2, y2, x3, y3, x4, y4);
265 break;
266 case 6:
267 c.set(x1, y1, x2, y2, x3, y3);
268 break;
269 default:
270 }
271 } else {
272 c.set(pts, type);
273 }
274
275 int ret = 0;
276 // we subdivide at values of t such that the remaining rotated
277 // curves are monotonic in x and y.
278 ret += c.dxRoots(ts, ret);
279 ret += c.dyRoots(ts, ret);
280
281 // subdivide at inflection points.
282 if (type == 8) {
283 // quadratic curves can't have inflection points
284 ret += c.infPoints(ts, ret);
285 }
286
287 // now we must subdivide at points where one of the offset curves will have
288 // a cusp. This happens at ts where the radius of curvature is equal to w.
289 ret += c.rootsOfROCMinusW(ts, ret, w2, 0.0001d);
290
291 ret = filterOutNotInAB(ts, 0, ret, 0.0001d, 0.9999d);
292 isort(ts, ret);
293 return ret;
294 }
295
296 // finds values of t where the curve in pts should be subdivided in order
297 // to get intersections with the given clip rectangle.
298 // Stores the points in ts, and returns how many of them there were.
299 static int findClipPoints(final DCurve curve, final double[] pts,
300 final double[] ts, final int type,
301 final int outCodeOR,
302 final double[] clipRect)
303 {
304 curve.set(pts, type);
305
306 // clip rectangle (ymin, ymax, xmin, xmax)
307 int ret = 0;
308
309 if ((outCodeOR & OUTCODE_LEFT) != 0) {
310 ret += curve.xPoints(ts, ret, clipRect[2]);
311 }
312 if ((outCodeOR & OUTCODE_RIGHT) != 0) {
313 ret += curve.xPoints(ts, ret, clipRect[3]);
314 }
315 if ((outCodeOR & OUTCODE_TOP) != 0) {
316 ret += curve.yPoints(ts, ret, clipRect[0]);
317 }
318 if ((outCodeOR & OUTCODE_BOTTOM) != 0) {
319 ret += curve.yPoints(ts, ret, clipRect[1]);
320 }
321 isort(ts, ret);
322 return ret;
323 }
324
325 static void subdivide(final double[] src,
326 final double[] left, final double[] right,
327 final int type)
328 {
329 switch(type) {
330 case 8:
331 subdivideCubic(src, left, right);
332 return;
333 case 6:
334 subdivideQuad(src, left, right);
335 return;
336 default:
337 throw new InternalError("Unsupported curve type");
338 }
339 }
340
341 static void isort(final double[] a, final int len) {
342 for (int i = 1, j; i < len; i++) {
343 final double ai = a[i];
344 j = i - 1;
345 for (; j >= 0 && a[j] > ai; j--) {
346 a[j + 1] = a[j];
347 }
348 a[j + 1] = ai;
349 }
350 }
351
352 // Most of these are copied from classes in java.awt.geom because we need
353 // both single and double precision variants of these functions, and Line2D,
354 // CubicCurve2D, QuadCurve2D don't provide them.
355 /**
356 * Subdivides the cubic curve specified by the coordinates
357 * stored in the <code>src</code> array at indices <code>srcoff</code>
358 * through (<code>srcoff</code> + 7) and stores the
359 * resulting two subdivided curves into the two result arrays at the
360 * corresponding indices.
361 * Either or both of the <code>left</code> and <code>right</code>
362 * arrays may be <code>null</code> or a reference to the same array
363 * as the <code>src</code> array.
364 * Note that the last point in the first subdivided curve is the
365 * same as the first point in the second subdivided curve. Thus,
366 * it is possible to pass the same array for <code>left</code>
367 * and <code>right</code> and to use offsets, such as <code>rightoff</code>
368 * equals (<code>leftoff</code> + 6), in order
369 * to avoid allocating extra storage for this common point.
370 * @param src the array holding the coordinates for the source curve
371 * @param left the array for storing the coordinates for the first
372 * half of the subdivided curve
373 * @param right the array for storing the coordinates for the second
374 * half of the subdivided curve
375 * @since 1.7
376 */
377 static void subdivideCubic(final double[] src,
378 final double[] left,
379 final double[] right)
380 {
381 double x1 = src[0];
382 double y1 = src[1];
383 double cx1 = src[2];
384 double cy1 = src[3];
385 double cx2 = src[4];
386 double cy2 = src[5];
387 double x2 = src[6];
388 double y2 = src[7];
389
390 left[0] = x1;
391 left[1] = y1;
392
393 right[6] = x2;
394 right[7] = y2;
395
396 x1 = (x1 + cx1) / 2.0d;
397 y1 = (y1 + cy1) / 2.0d;
398 x2 = (x2 + cx2) / 2.0d;
399 y2 = (y2 + cy2) / 2.0d;
400
401 double cx = (cx1 + cx2) / 2.0d;
402 double cy = (cy1 + cy2) / 2.0d;
403
404 cx1 = (x1 + cx) / 2.0d;
405 cy1 = (y1 + cy) / 2.0d;
406 cx2 = (x2 + cx) / 2.0d;
407 cy2 = (y2 + cy) / 2.0d;
408 cx = (cx1 + cx2) / 2.0d;
409 cy = (cy1 + cy2) / 2.0d;
410
411 left[2] = x1;
412 left[3] = y1;
413 left[4] = cx1;
414 left[5] = cy1;
415 left[6] = cx;
416 left[7] = cy;
417
418 right[0] = cx;
419 right[1] = cy;
420 right[2] = cx2;
421 right[3] = cy2;
422 right[4] = x2;
423 right[5] = y2;
424 }
425
426 static void subdivideCubicAt(final double t,
427 final double[] src, final int offS,
428 final double[] pts, final int offL, final int offR)
429 {
430 double x1 = src[offS ];
431 double y1 = src[offS + 1];
432 double cx1 = src[offS + 2];
433 double cy1 = src[offS + 3];
434 double cx2 = src[offS + 4];
435 double cy2 = src[offS + 5];
436 double x2 = src[offS + 6];
437 double y2 = src[offS + 7];
438
439 pts[offL ] = x1;
440 pts[offL + 1] = y1;
441
442 pts[offR + 6] = x2;
443 pts[offR + 7] = y2;
444
445 x1 = x1 + t * (cx1 - x1);
446 y1 = y1 + t * (cy1 - y1);
447 x2 = cx2 + t * (x2 - cx2);
448 y2 = cy2 + t * (y2 - cy2);
449
450 double cx = cx1 + t * (cx2 - cx1);
451 double cy = cy1 + t * (cy2 - cy1);
452
453 cx1 = x1 + t * (cx - x1);
454 cy1 = y1 + t * (cy - y1);
455 cx2 = cx + t * (x2 - cx);
456 cy2 = cy + t * (y2 - cy);
457 cx = cx1 + t * (cx2 - cx1);
458 cy = cy1 + t * (cy2 - cy1);
459
460 pts[offL + 2] = x1;
461 pts[offL + 3] = y1;
462 pts[offL + 4] = cx1;
463 pts[offL + 5] = cy1;
464 pts[offL + 6] = cx;
465 pts[offL + 7] = cy;
466
467 pts[offR ] = cx;
468 pts[offR + 1] = cy;
469 pts[offR + 2] = cx2;
470 pts[offR + 3] = cy2;
471 pts[offR + 4] = x2;
472 pts[offR + 5] = y2;
473 }
474
475 static void subdivideQuad(final double[] src,
476 final double[] left,
477 final double[] right)
478 {
479 double x1 = src[0];
480 double y1 = src[1];
481 double cx = src[2];
482 double cy = src[3];
483 double x2 = src[4];
484 double y2 = src[5];
485
486 left[0] = x1;
487 left[1] = y1;
488
489 right[4] = x2;
490 right[5] = y2;
491
492 x1 = (x1 + cx) / 2.0d;
493 y1 = (y1 + cy) / 2.0d;
494 x2 = (x2 + cx) / 2.0d;
495 y2 = (y2 + cy) / 2.0d;
496 cx = (x1 + x2) / 2.0d;
497 cy = (y1 + y2) / 2.0d;
498
499 left[2] = x1;
500 left[3] = y1;
501 left[4] = cx;
502 left[5] = cy;
503
504 right[0] = cx;
505 right[1] = cy;
506 right[2] = x2;
507 right[3] = y2;
508 }
509
510 static void subdivideQuadAt(final double t,
511 final double[] src, final int offS,
512 final double[] pts, final int offL, final int offR)
513 {
514 double x1 = src[offS ];
515 double y1 = src[offS + 1];
516 double cx = src[offS + 2];
517 double cy = src[offS + 3];
518 double x2 = src[offS + 4];
519 double y2 = src[offS + 5];
520
521 pts[offL ] = x1;
522 pts[offL + 1] = y1;
523
524 pts[offR + 4] = x2;
525 pts[offR + 5] = y2;
526
527 x1 = x1 + t * (cx - x1);
528 y1 = y1 + t * (cy - y1);
529 x2 = cx + t * (x2 - cx);
530 y2 = cy + t * (y2 - cy);
531 cx = x1 + t * (x2 - x1);
532 cy = y1 + t * (y2 - y1);
533
534 pts[offL + 2] = x1;
535 pts[offL + 3] = y1;
536 pts[offL + 4] = cx;
537 pts[offL + 5] = cy;
538
539 pts[offR ] = cx;
540 pts[offR + 1] = cy;
541 pts[offR + 2] = x2;
542 pts[offR + 3] = y2;
543 }
544
545 static void subdivideLineAt(final double t,
546 final double[] src, final int offS,
547 final double[] pts, final int offL, final int offR)
548 {
549 double x1 = src[offS ];
550 double y1 = src[offS + 1];
551 double x2 = src[offS + 2];
552 double y2 = src[offS + 3];
553
554 pts[offL ] = x1;
555 pts[offL + 1] = y1;
556
557 pts[offR + 2] = x2;
558 pts[offR + 3] = y2;
559
560 x1 = x1 + t * (x2 - x1);
561 y1 = y1 + t * (y2 - y1);
562
563 pts[offL + 2] = x1;
564 pts[offL + 3] = y1;
565
566 pts[offR ] = x1;
567 pts[offR + 1] = y1;
568 }
569
570 static void subdivideAt(final double t,
571 final double[] src, final int offS,
572 final double[] pts, final int offL, final int type)
573 {
574 // if instead of switch (perf + most probable cases first)
575 if (type == 8) {
576 subdivideCubicAt(t, src, offS, pts, offL, offL + type);
577 } else if (type == 4) {
578 subdivideLineAt(t, src, offS, pts, offL, offL + type);
579 } else {
580 subdivideQuadAt(t, src, offS, pts, offL, offL + type);
581 }
582 }
583
584 // From sun.java2d.loops.GeneralRenderer:
585
586 static int outcode(final double x, final double y,
587 final double[] clipRect)
588 {
589 int code;
590 if (y < clipRect[0]) {
591 code = OUTCODE_TOP;
592 } else if (y >= clipRect[1]) {
593 code = OUTCODE_BOTTOM;
594 } else {
595 code = 0;
596 }
597 if (x < clipRect[2]) {
598 code |= OUTCODE_LEFT;
599 } else if (x >= clipRect[3]) {
600 code |= OUTCODE_RIGHT;
601 }
602 return code;
603 }
604
605 // a stack of polynomial curves where each curve shares endpoints with
606 // adjacent ones.
607 static final class PolyStack {
608 private static final byte TYPE_LINETO = (byte) 0;
609 private static final byte TYPE_QUADTO = (byte) 1;
610 private static final byte TYPE_CUBICTO = (byte) 2;
611
612 // curves capacity = edges count (8192) = edges x 2 (coords)
613 private static final int INITIAL_CURVES_COUNT = INITIAL_EDGES_COUNT << 1;
614
615 // types capacity = edges count (4096)
616 private static final int INITIAL_TYPES_COUNT = INITIAL_EDGES_COUNT;
617
618 double[] curves;
619 int end;
620 byte[] curveTypes;
621 int numCurves;
622
623 // curves ref (dirty)
624 final DoubleArrayCache.Reference curves_ref;
625 // curveTypes ref (dirty)
626 final ByteArrayCache.Reference curveTypes_ref;
627
628 // used marks (stats only)
629 int curveTypesUseMark;
630 int curvesUseMark;
631
632 private final StatLong stat_polystack_types;
633 private final StatLong stat_polystack_curves;
634 private final Histogram hist_polystack_curves;
635 private final StatLong stat_array_polystack_curves;
636 private final StatLong stat_array_polystack_curveTypes;
637
638 PolyStack(final DRendererContext rdrCtx) {
639 this(rdrCtx, null, null, null, null, null);
640 }
641
642 PolyStack(final DRendererContext rdrCtx,
643 final StatLong stat_polystack_types,
644 final StatLong stat_polystack_curves,
645 final Histogram hist_polystack_curves,
646 final StatLong stat_array_polystack_curves,
647 final StatLong stat_array_polystack_curveTypes)
648 {
649 curves_ref = rdrCtx.newDirtyDoubleArrayRef(INITIAL_CURVES_COUNT); // 32K
650 curves = curves_ref.initial;
651
652 curveTypes_ref = rdrCtx.newDirtyByteArrayRef(INITIAL_TYPES_COUNT); // 4K
653 curveTypes = curveTypes_ref.initial;
654 numCurves = 0;
655 end = 0;
656
657 if (DO_STATS) {
658 curveTypesUseMark = 0;
659 curvesUseMark = 0;
660 }
661 this.stat_polystack_types = stat_polystack_types;
662 this.stat_polystack_curves = stat_polystack_curves;
663 this.hist_polystack_curves = hist_polystack_curves;
664 this.stat_array_polystack_curves = stat_array_polystack_curves;
665 this.stat_array_polystack_curveTypes = stat_array_polystack_curveTypes;
666 }
667
668 /**
669 * Disposes this PolyStack:
670 * clean up before reusing this instance
671 */
672 void dispose() {
673 end = 0;
674 numCurves = 0;
675
676 if (DO_STATS) {
677 stat_polystack_types.add(curveTypesUseMark);
678 stat_polystack_curves.add(curvesUseMark);
679 hist_polystack_curves.add(curvesUseMark);
680
681 // reset marks
682 curveTypesUseMark = 0;
683 curvesUseMark = 0;
684 }
685
686 // Return arrays:
687 // curves and curveTypes are kept dirty
688 curves = curves_ref.putArray(curves);
689 curveTypes = curveTypes_ref.putArray(curveTypes);
690 }
691
692 private void ensureSpace(final int n) {
693 // use substraction to avoid integer overflow:
694 if (curves.length - end < n) {
695 if (DO_STATS) {
696 stat_array_polystack_curves.add(end + n);
697 }
698 curves = curves_ref.widenArray(curves, end, end + n);
699 }
700 if (curveTypes.length <= numCurves) {
701 if (DO_STATS) {
702 stat_array_polystack_curveTypes.add(numCurves + 1);
703 }
704 curveTypes = curveTypes_ref.widenArray(curveTypes,
705 numCurves,
706 numCurves + 1);
707 }
708 }
709
710 void pushCubic(double x0, double y0,
711 double x1, double y1,
712 double x2, double y2)
713 {
714 ensureSpace(6);
715 curveTypes[numCurves++] = TYPE_CUBICTO;
716 // we reverse the coordinate order to make popping easier
717 final double[] _curves = curves;
718 int e = end;
719 _curves[e++] = x2; _curves[e++] = y2;
720 _curves[e++] = x1; _curves[e++] = y1;
721 _curves[e++] = x0; _curves[e++] = y0;
722 end = e;
723 }
724
725 void pushQuad(double x0, double y0,
726 double x1, double y1)
727 {
728 ensureSpace(4);
729 curveTypes[numCurves++] = TYPE_QUADTO;
730 final double[] _curves = curves;
731 int e = end;
732 _curves[e++] = x1; _curves[e++] = y1;
733 _curves[e++] = x0; _curves[e++] = y0;
734 end = e;
735 }
736
737 void pushLine(double x, double y) {
738 ensureSpace(2);
739 curveTypes[numCurves++] = TYPE_LINETO;
740 curves[end++] = x; curves[end++] = y;
741 }
742
743 void pullAll(final DPathConsumer2D io) {
744 final int nc = numCurves;
745 if (nc == 0) {
746 return;
747 }
748 if (DO_STATS) {
749 // update used marks:
750 if (numCurves > curveTypesUseMark) {
751 curveTypesUseMark = numCurves;
752 }
753 if (end > curvesUseMark) {
754 curvesUseMark = end;
755 }
756 }
757 final byte[] _curveTypes = curveTypes;
758 final double[] _curves = curves;
759 int e = 0;
760
761 for (int i = 0; i < nc; i++) {
762 switch(_curveTypes[i]) {
763 case TYPE_LINETO:
764 io.lineTo(_curves[e], _curves[e+1]);
765 e += 2;
766 continue;
767 case TYPE_QUADTO:
768 io.quadTo(_curves[e], _curves[e+1],
769 _curves[e+2], _curves[e+3]);
770 e += 4;
771 continue;
772 case TYPE_CUBICTO:
773 io.curveTo(_curves[e], _curves[e+1],
774 _curves[e+2], _curves[e+3],
775 _curves[e+4], _curves[e+5]);
776 e += 6;
777 continue;
778 default:
779 }
780 }
781 numCurves = 0;
782 end = 0;
783 }
784
785 void popAll(final DPathConsumer2D io) {
786 int nc = numCurves;
787 if (nc == 0) {
788 return;
789 }
790 if (DO_STATS) {
791 // update used marks:
792 if (numCurves > curveTypesUseMark) {
793 curveTypesUseMark = numCurves;
794 }
795 if (end > curvesUseMark) {
796 curvesUseMark = end;
797 }
798 }
799 final byte[] _curveTypes = curveTypes;
800 final double[] _curves = curves;
801 int e = end;
802
803 while (nc != 0) {
804 switch(_curveTypes[--nc]) {
805 case TYPE_LINETO:
806 e -= 2;
807 io.lineTo(_curves[e], _curves[e+1]);
808 continue;
809 case TYPE_QUADTO:
810 e -= 4;
811 io.quadTo(_curves[e], _curves[e+1],
812 _curves[e+2], _curves[e+3]);
813 continue;
814 case TYPE_CUBICTO:
815 e -= 6;
816 io.curveTo(_curves[e], _curves[e+1],
817 _curves[e+2], _curves[e+3],
818 _curves[e+4], _curves[e+5]);
819 continue;
820 default:
821 }
822 }
823 numCurves = 0;
824 end = 0;
825 }
826
827 @Override
828 public String toString() {
829 String ret = "";
830 int nc = numCurves;
831 int last = end;
832 int len;
833 while (nc != 0) {
834 switch(curveTypes[--nc]) {
835 case TYPE_LINETO:
836 len = 2;
837 ret += "line: ";
838 break;
839 case TYPE_QUADTO:
840 len = 4;
841 ret += "quad: ";
842 break;
843 case TYPE_CUBICTO:
844 len = 6;
845 ret += "cubic: ";
846 break;
847 default:
848 len = 0;
849 }
850 last -= len;
851 ret += Arrays.toString(Arrays.copyOfRange(curves, last, last+len))
852 + "\n";
853 }
854 return ret;
855 }
856 }
857
858 // a stack of integer indices
859 static final class IndexStack {
860
861 // integer capacity = edges count / 4 ~ 1024
862 private static final int INITIAL_COUNT = INITIAL_EDGES_COUNT >> 2;
863
864 private int end;
865 private int[] indices;
866
867 // indices ref (dirty)
868 private final IntArrayCache.Reference indices_ref;
869
870 // used marks (stats only)
871 private int indicesUseMark;
872
873 private final StatLong stat_idxstack_indices;
874 private final Histogram hist_idxstack_indices;
875 private final StatLong stat_array_idxstack_indices;
876
877 IndexStack(final DRendererContext rdrCtx) {
878 this(rdrCtx, null, null, null);
879 }
880
881 IndexStack(final DRendererContext rdrCtx,
882 final StatLong stat_idxstack_indices,
883 final Histogram hist_idxstack_indices,
884 final StatLong stat_array_idxstack_indices)
885 {
886 indices_ref = rdrCtx.newDirtyIntArrayRef(INITIAL_COUNT); // 4K
887 indices = indices_ref.initial;
888 end = 0;
889
890 if (DO_STATS) {
891 indicesUseMark = 0;
892 }
893 this.stat_idxstack_indices = stat_idxstack_indices;
894 this.hist_idxstack_indices = hist_idxstack_indices;
895 this.stat_array_idxstack_indices = stat_array_idxstack_indices;
896 }
897
898 /**
899 * Disposes this PolyStack:
900 * clean up before reusing this instance
901 */
902 void dispose() {
903 end = 0;
904
905 if (DO_STATS) {
906 stat_idxstack_indices.add(indicesUseMark);
907 hist_idxstack_indices.add(indicesUseMark);
908
909 // reset marks
910 indicesUseMark = 0;
911 }
912
913 // Return arrays:
914 // values is kept dirty
915 indices = indices_ref.putArray(indices);
916 }
917
918 boolean isEmpty() {
919 return (end == 0);
920 }
921
922 void reset() {
923 end = 0;
924 }
925
926 void push(final int v) {
927 // remove redundant values (reverse order):
928 int[] _values = indices;
929 final int nc = end;
930 if (nc != 0) {
931 if (_values[nc - 1] == v) {
932 // remove both duplicated values:
933 end--;
934 return;
935 }
936 }
937 if (_values.length <= nc) {
938 if (DO_STATS) {
939 stat_array_idxstack_indices.add(nc + 1);
940 }
941 indices = _values = indices_ref.widenArray(_values, nc, nc + 1);
942 }
943 _values[end++] = v;
944
945 if (DO_STATS) {
946 // update used marks:
947 if (end > indicesUseMark) {
948 indicesUseMark = end;
949 }
950 }
951 }
952
953 void pullAll(final double[] points, final DPathConsumer2D io) {
954 final int nc = end;
955 if (nc == 0) {
956 return;
957 }
958 final int[] _values = indices;
959
960 for (int i = 0, j; i < nc; i++) {
961 j = _values[i] << 1;
962 io.lineTo(points[j], points[j + 1]);
963 }
964 end = 0;
965 }
966 }
967 }