1 /*
2 * Copyright (c) 2007, 2017, 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.marlin;
27
28 import com.sun.javafx.geom.PathConsumer2D;
29 import static java.lang.Math.PI;
30 import java.util.Arrays;
31 import com.sun.marlin.stats.Histogram;
32 import com.sun.marlin.stats.StatLong;
33
34 final class Helpers implements MarlinConst {
35
36 private Helpers() {
37 throw new Error("This is a non instantiable class");
38 }
39
40 static boolean within(final float x, final float y, final float err) {
41 final float d = y - x;
42 return (d <= err && d >= -err);
43 }
44
45 static boolean within(final double x, final double y, final double err) {
46 final double d = y - x;
47 return (d <= err && d >= -err);
48 }
49
50 static int quadraticRoots(final float a, final float b,
51 final float c, float[] zeroes, final int off)
52 {
53 int ret = off;
54 float t;
55 if (a != 0.0f) {
56 final float dis = b*b - 4*a*c;
57 if (dis > 0.0f) {
58 final float sqrtDis = (float) Math.sqrt(dis);
59 // depending on the sign of b we use a slightly different
60 // algorithm than the traditional one to find one of the roots
61 // so we can avoid adding numbers of different signs (which
62 // might result in loss of precision).
63 if (b >= 0.0f) {
64 zeroes[ret++] = (2.0f * c) / (-b - sqrtDis);
65 zeroes[ret++] = (-b - sqrtDis) / (2.0f * a);
66 } else {
67 zeroes[ret++] = (-b + sqrtDis) / (2.0f * a);
68 zeroes[ret++] = (2.0f * c) / (-b + sqrtDis);
69 }
70 } else if (dis == 0.0f) {
71 t = (-b) / (2.0f * a);
72 zeroes[ret++] = t;
73 }
74 } else {
75 if (b != 0.0f) {
76 t = (-c) / b;
77 zeroes[ret++] = t;
78 }
79 }
80 return ret - off;
81 }
82
83 // find the roots of g(t) = d*t^3 + a*t^2 + b*t + c in [A,B)
84 static int cubicRootsInAB(float d, float a, float b, float c,
85 float[] pts, final int off,
86 final float A, final float B)
87 {
88 if (d == 0.0f) {
89 int num = quadraticRoots(a, b, c, pts, off);
90 return filterOutNotInAB(pts, off, num, A, B) - off;
91 }
92 // From Graphics Gems:
93 // http://tog.acm.org/resources/GraphicsGems/gems/Roots3And4.c
94 // (also from awt.geom.CubicCurve2D. But here we don't need as
95 // much accuracy and we don't want to create arrays so we use
96 // our own customized version).
97
98 // normal form: x^3 + ax^2 + bx + c = 0
99 a /= d;
100 b /= d;
101 c /= d;
102
103 // substitute x = y - A/3 to eliminate quadratic term:
104 // x^3 +Px + Q = 0
105 //
106 // Since we actually need P/3 and Q/2 for all of the
107 // calculations that follow, we will calculate
108 // p = P/3
109 // q = Q/2
110 // instead and use those values for simplicity of the code.
111 double sq_A = a * a;
112 double p = (1.0d/3.0d) * ((-1.0d/3.0d) * sq_A + b);
113 double q = (1.0d/2.0d) * ((2.0d/27.0d) * a * sq_A - (1.0d/3.0d) * a * b + c);
114
115 // use Cardano's formula
116
117 double cb_p = p * p * p;
118 double D = q * q + cb_p;
119
120 int num;
121 if (D < 0.0d) {
122 // see: http://en.wikipedia.org/wiki/Cubic_function#Trigonometric_.28and_hyperbolic.29_method
123 final double phi = (1.0d/3.0d) * Math.acos(-q / Math.sqrt(-cb_p));
124 final double t = 2.0d * Math.sqrt(-p);
125
126 pts[ off+0 ] = (float) ( t * Math.cos(phi));
127 pts[ off+1 ] = (float) (-t * Math.cos(phi + (PI / 3.0d)));
128 pts[ off+2 ] = (float) (-t * Math.cos(phi - (PI / 3.0d)));
129 num = 3;
130 } else {
131 final double sqrt_D = Math.sqrt(D);
132 final double u = Math.cbrt(sqrt_D - q);
133 final double v = - Math.cbrt(sqrt_D + q);
134
135 pts[ off ] = (float) (u + v);
136 num = 1;
137
138 if (within(D, 0.0d, 1e-8d)) {
139 pts[off+1] = -(pts[off] / 2.0f);
140 num = 2;
141 }
142 }
143
144 final float sub = (1.0f/3.0f) * a;
145
146 for (int i = 0; i < num; ++i) {
147 pts[ off+i ] -= sub;
148 }
149
150 return filterOutNotInAB(pts, off, num, A, B) - off;
151 }
152
153 static float evalCubic(final float a, final float b,
154 final float c, final float d,
155 final float t)
156 {
157 return t * (t * (t * a + b) + c) + d;
158 }
159
160 static float evalQuad(final float a, final float b,
161 final float c, final float t)
162 {
163 return t * (t * a + b) + c;
164 }
165
166 // returns the index 1 past the last valid element remaining after filtering
167 static int filterOutNotInAB(float[] nums, final int off, final int len,
168 final float a, final float b)
169 {
170 int ret = off;
171 for (int i = off, end = off + len; i < end; i++) {
172 if (nums[i] >= a && nums[i] < b) {
173 nums[ret++] = nums[i];
174 }
175 }
176 return ret;
177 }
178
179 static float linelen(float x1, float y1, float x2, float y2) {
180 final float dx = x2 - x1;
181 final float dy = y2 - y1;
182 return (float) Math.sqrt(dx*dx + dy*dy);
183 }
184
185 static void subdivide(float[] src, int srcoff, float[] left, int leftoff,
186 float[] right, int rightoff, int type)
187 {
188 switch(type) {
189 case 6:
190 Helpers.subdivideQuad(src, srcoff, left, leftoff, right, rightoff);
191 return;
192 case 8:
193 Helpers.subdivideCubic(src, srcoff, left, leftoff, right, rightoff);
194 return;
195 default:
196 throw new InternalError("Unsupported curve type");
197 }
198 }
199
200 static void isort(float[] a, int off, int len) {
201 for (int i = off + 1, end = off + len; i < end; i++) {
202 float ai = a[i];
203 int j = i - 1;
204 for (; j >= off && a[j] > ai; j--) {
205 a[j+1] = a[j];
206 }
207 a[j+1] = ai;
208 }
209 }
210
211 // Most of these are copied from classes in java.awt.geom because we need
212 // both single and double precision variants of these functions, and Line2D,
213 // CubicCurve2D, QuadCurve2D don't provide them.
214 /**
215 * Subdivides the cubic curve specified by the coordinates
216 * stored in the <code>src</code> array at indices <code>srcoff</code>
217 * through (<code>srcoff</code> + 7) and stores the
218 * resulting two subdivided curves into the two result arrays at the
219 * corresponding indices.
220 * Either or both of the <code>left</code> and <code>right</code>
221 * arrays may be <code>null</code> or a reference to the same array
222 * as the <code>src</code> array.
223 * Note that the last point in the first subdivided curve is the
224 * same as the first point in the second subdivided curve. Thus,
225 * it is possible to pass the same array for <code>left</code>
226 * and <code>right</code> and to use offsets, such as <code>rightoff</code>
227 * equals (<code>leftoff</code> + 6), in order
228 * to avoid allocating extra storage for this common point.
229 * @param src the array holding the coordinates for the source curve
230 * @param srcoff the offset into the array of the beginning of the
231 * the 6 source coordinates
232 * @param left the array for storing the coordinates for the first
233 * half of the subdivided curve
234 * @param leftoff the offset into the array of the beginning of the
235 * the 6 left coordinates
236 * @param right the array for storing the coordinates for the second
237 * half of the subdivided curve
238 * @param rightoff the offset into the array of the beginning of the
239 * the 6 right coordinates
240 * @since 1.7
241 */
242 static void subdivideCubic(float[] src, int srcoff,
243 float[] left, int leftoff,
244 float[] right, int rightoff)
245 {
246 float x1 = src[srcoff + 0];
247 float y1 = src[srcoff + 1];
248 float ctrlx1 = src[srcoff + 2];
249 float ctrly1 = src[srcoff + 3];
250 float ctrlx2 = src[srcoff + 4];
251 float ctrly2 = src[srcoff + 5];
252 float x2 = src[srcoff + 6];
253 float y2 = src[srcoff + 7];
254 if (left != null) {
255 left[leftoff + 0] = x1;
256 left[leftoff + 1] = y1;
257 }
258 if (right != null) {
259 right[rightoff + 6] = x2;
260 right[rightoff + 7] = y2;
261 }
262 x1 = (x1 + ctrlx1) / 2.0f;
263 y1 = (y1 + ctrly1) / 2.0f;
264 x2 = (x2 + ctrlx2) / 2.0f;
265 y2 = (y2 + ctrly2) / 2.0f;
266 float centerx = (ctrlx1 + ctrlx2) / 2.0f;
267 float centery = (ctrly1 + ctrly2) / 2.0f;
268 ctrlx1 = (x1 + centerx) / 2.0f;
269 ctrly1 = (y1 + centery) / 2.0f;
270 ctrlx2 = (x2 + centerx) / 2.0f;
271 ctrly2 = (y2 + centery) / 2.0f;
272 centerx = (ctrlx1 + ctrlx2) / 2.0f;
273 centery = (ctrly1 + ctrly2) / 2.0f;
274 if (left != null) {
275 left[leftoff + 2] = x1;
276 left[leftoff + 3] = y1;
277 left[leftoff + 4] = ctrlx1;
278 left[leftoff + 5] = ctrly1;
279 left[leftoff + 6] = centerx;
280 left[leftoff + 7] = centery;
281 }
282 if (right != null) {
283 right[rightoff + 0] = centerx;
284 right[rightoff + 1] = centery;
285 right[rightoff + 2] = ctrlx2;
286 right[rightoff + 3] = ctrly2;
287 right[rightoff + 4] = x2;
288 right[rightoff + 5] = y2;
289 }
290 }
291
292
293 static void subdivideCubicAt(float t, float[] src, int srcoff,
294 float[] left, int leftoff,
295 float[] right, int rightoff)
296 {
297 float x1 = src[srcoff + 0];
298 float y1 = src[srcoff + 1];
299 float ctrlx1 = src[srcoff + 2];
300 float ctrly1 = src[srcoff + 3];
301 float ctrlx2 = src[srcoff + 4];
302 float ctrly2 = src[srcoff + 5];
303 float x2 = src[srcoff + 6];
304 float y2 = src[srcoff + 7];
305 if (left != null) {
306 left[leftoff + 0] = x1;
307 left[leftoff + 1] = y1;
308 }
309 if (right != null) {
310 right[rightoff + 6] = x2;
311 right[rightoff + 7] = y2;
312 }
313 x1 = x1 + t * (ctrlx1 - x1);
314 y1 = y1 + t * (ctrly1 - y1);
315 x2 = ctrlx2 + t * (x2 - ctrlx2);
316 y2 = ctrly2 + t * (y2 - ctrly2);
317 float centerx = ctrlx1 + t * (ctrlx2 - ctrlx1);
318 float centery = ctrly1 + t * (ctrly2 - ctrly1);
319 ctrlx1 = x1 + t * (centerx - x1);
320 ctrly1 = y1 + t * (centery - y1);
321 ctrlx2 = centerx + t * (x2 - centerx);
322 ctrly2 = centery + t * (y2 - centery);
323 centerx = ctrlx1 + t * (ctrlx2 - ctrlx1);
324 centery = ctrly1 + t * (ctrly2 - ctrly1);
325 if (left != null) {
326 left[leftoff + 2] = x1;
327 left[leftoff + 3] = y1;
328 left[leftoff + 4] = ctrlx1;
329 left[leftoff + 5] = ctrly1;
330 left[leftoff + 6] = centerx;
331 left[leftoff + 7] = centery;
332 }
333 if (right != null) {
334 right[rightoff + 0] = centerx;
335 right[rightoff + 1] = centery;
336 right[rightoff + 2] = ctrlx2;
337 right[rightoff + 3] = ctrly2;
338 right[rightoff + 4] = x2;
339 right[rightoff + 5] = y2;
340 }
341 }
342
343 static void subdivideQuad(float[] src, int srcoff,
344 float[] left, int leftoff,
345 float[] right, int rightoff)
346 {
347 float x1 = src[srcoff + 0];
348 float y1 = src[srcoff + 1];
349 float ctrlx = src[srcoff + 2];
350 float ctrly = src[srcoff + 3];
351 float x2 = src[srcoff + 4];
352 float y2 = src[srcoff + 5];
353 if (left != null) {
354 left[leftoff + 0] = x1;
355 left[leftoff + 1] = y1;
356 }
357 if (right != null) {
358 right[rightoff + 4] = x2;
359 right[rightoff + 5] = y2;
360 }
361 x1 = (x1 + ctrlx) / 2.0f;
362 y1 = (y1 + ctrly) / 2.0f;
363 x2 = (x2 + ctrlx) / 2.0f;
364 y2 = (y2 + ctrly) / 2.0f;
365 ctrlx = (x1 + x2) / 2.0f;
366 ctrly = (y1 + y2) / 2.0f;
367 if (left != null) {
368 left[leftoff + 2] = x1;
369 left[leftoff + 3] = y1;
370 left[leftoff + 4] = ctrlx;
371 left[leftoff + 5] = ctrly;
372 }
373 if (right != null) {
374 right[rightoff + 0] = ctrlx;
375 right[rightoff + 1] = ctrly;
376 right[rightoff + 2] = x2;
377 right[rightoff + 3] = y2;
378 }
379 }
380
381 static void subdivideQuadAt(float t, float[] src, int srcoff,
382 float[] left, int leftoff,
383 float[] right, int rightoff)
384 {
385 float x1 = src[srcoff + 0];
386 float y1 = src[srcoff + 1];
387 float ctrlx = src[srcoff + 2];
388 float ctrly = src[srcoff + 3];
389 float x2 = src[srcoff + 4];
390 float y2 = src[srcoff + 5];
391 if (left != null) {
392 left[leftoff + 0] = x1;
393 left[leftoff + 1] = y1;
394 }
395 if (right != null) {
396 right[rightoff + 4] = x2;
397 right[rightoff + 5] = y2;
398 }
399 x1 = x1 + t * (ctrlx - x1);
400 y1 = y1 + t * (ctrly - y1);
401 x2 = ctrlx + t * (x2 - ctrlx);
402 y2 = ctrly + t * (y2 - ctrly);
403 ctrlx = x1 + t * (x2 - x1);
404 ctrly = y1 + t * (y2 - y1);
405 if (left != null) {
406 left[leftoff + 2] = x1;
407 left[leftoff + 3] = y1;
408 left[leftoff + 4] = ctrlx;
409 left[leftoff + 5] = ctrly;
410 }
411 if (right != null) {
412 right[rightoff + 0] = ctrlx;
413 right[rightoff + 1] = ctrly;
414 right[rightoff + 2] = x2;
415 right[rightoff + 3] = y2;
416 }
417 }
418
419 static void subdivideAt(float t, float[] src, int srcoff,
420 float[] left, int leftoff,
421 float[] right, int rightoff, int size)
422 {
423 switch(size) {
424 case 8:
425 subdivideCubicAt(t, src, srcoff, left, leftoff, right, rightoff);
426 return;
427 case 6:
428 subdivideQuadAt(t, src, srcoff, left, leftoff, right, rightoff);
429 return;
430 }
431 }
432
433 // From sun.java2d.loops.GeneralRenderer:
434
435 static int outcode(final float x, final float y,
436 final float[] clipRect)
437 {
438 int code;
439 if (y < clipRect[0]) {
440 code = OUTCODE_TOP;
441 } else if (y >= clipRect[1]) {
442 code = OUTCODE_BOTTOM;
443 } else {
444 code = 0;
445 }
446 if (x < clipRect[2]) {
447 code |= OUTCODE_LEFT;
448 } else if (x >= clipRect[3]) {
449 code |= OUTCODE_RIGHT;
596 }
597 if (DO_STATS) {
598 // update used marks:
599 if (numCurves > curveTypesUseMark) {
600 curveTypesUseMark = numCurves;
601 }
602 if (end > curvesUseMark) {
603 curvesUseMark = end;
604 }
605 }
606 final byte[] _curveTypes = curveTypes;
607 final float[] _curves = curves;
608 int e = 0;
609
610 for (int i = 0; i < nc; i++) {
611 switch(_curveTypes[i]) {
612 case TYPE_LINETO:
613 io.lineTo(_curves[e], _curves[e+1]);
614 e += 2;
615 continue;
616 case TYPE_QUADTO:
617 io.quadTo(_curves[e+0], _curves[e+1],
618 _curves[e+2], _curves[e+3]);
619 e += 4;
620 continue;
621 case TYPE_CUBICTO:
622 io.curveTo(_curves[e+0], _curves[e+1],
623 _curves[e+2], _curves[e+3],
624 _curves[e+4], _curves[e+5]);
625 e += 6;
626 continue;
627 default:
628 }
629 }
630 numCurves = 0;
631 end = 0;
632 }
633
634 void popAll(final PathConsumer2D io) {
635 int nc = numCurves;
636 if (nc == 0) {
637 return;
638 }
639 if (DO_STATS) {
640 // update used marks:
641 if (numCurves > curveTypesUseMark) {
642 curveTypesUseMark = numCurves;
643 }
644 if (end > curvesUseMark) {
645 curvesUseMark = end;
646 }
647 }
648 final byte[] _curveTypes = curveTypes;
649 final float[] _curves = curves;
650 int e = end;
651
652 while (nc != 0) {
653 switch(_curveTypes[--nc]) {
654 case TYPE_LINETO:
655 e -= 2;
656 io.lineTo(_curves[e], _curves[e+1]);
657 continue;
658 case TYPE_QUADTO:
659 e -= 4;
660 io.quadTo(_curves[e+0], _curves[e+1],
661 _curves[e+2], _curves[e+3]);
662 continue;
663 case TYPE_CUBICTO:
664 e -= 6;
665 io.curveTo(_curves[e+0], _curves[e+1],
666 _curves[e+2], _curves[e+3],
667 _curves[e+4], _curves[e+5]);
668 continue;
669 default:
670 }
671 }
672 numCurves = 0;
673 end = 0;
674 }
675
676 @Override
677 public String toString() {
678 String ret = "";
679 int nc = numCurves;
680 int last = end;
681 int len;
682 while (nc != 0) {
683 switch(curveTypes[--nc]) {
684 case TYPE_LINETO:
685 len = 2;
686 ret += "line: ";
687 break;
|
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 com.sun.marlin;
27
28 import com.sun.javafx.geom.PathConsumer2D;
29 import java.util.Arrays;
30 import com.sun.marlin.stats.Histogram;
31 import com.sun.marlin.stats.StatLong;
32
33 final class Helpers implements MarlinConst {
34
35 private Helpers() {
36 throw new Error("This is a non instantiable class");
37 }
38
39 static boolean within(final float x, final float y, final float err) {
40 final float d = y - x;
41 return (d <= err && d >= -err);
42 }
43
44 static boolean within(final double x, final double y, final double err) {
45 final double d = y - x;
46 return (d <= err && d >= -err);
47 }
48
49 static float evalCubic(final float a, final float b,
50 final float c, final float d,
51 final float t)
52 {
53 return t * (t * (t * a + b) + c) + d;
54 }
55
56 static float evalQuad(final float a, final float b,
57 final float c, final float t)
58 {
59 return t * (t * a + b) + c;
60 }
61
62 static int quadraticRoots(final float a, final float b, final float c,
63 final float[] zeroes, final int off)
64 {
65 int ret = off;
66 if (a != 0.0f) {
67 final float dis = b*b - 4.0f * a * c;
68 if (dis > 0.0f) {
69 final float sqrtDis = (float) Math.sqrt(dis);
70 // depending on the sign of b we use a slightly different
71 // algorithm than the traditional one to find one of the roots
72 // so we can avoid adding numbers of different signs (which
73 // might result in loss of precision).
74 if (b >= 0.0f) {
75 zeroes[ret++] = (2.0f * c) / (-b - sqrtDis);
76 zeroes[ret++] = (-b - sqrtDis) / (2.0f * a);
77 } else {
78 zeroes[ret++] = (-b + sqrtDis) / (2.0f * a);
79 zeroes[ret++] = (2.0f * c) / (-b + sqrtDis);
80 }
81 } else if (dis == 0.0f) {
82 zeroes[ret++] = -b / (2.0f * a);
83 }
84 } else if (b != 0.0f) {
85 zeroes[ret++] = -c / b;
86 }
87 return ret - off;
88 }
89
90 // find the roots of g(t) = d*t^3 + a*t^2 + b*t + c in [A,B)
91 static int cubicRootsInAB(final float d0, float a0, float b0, float c0,
92 final float[] pts, final int off,
93 final float A, final float B)
94 {
95 if (d0 == 0.0f) {
96 final int num = quadraticRoots(a0, b0, c0, pts, off);
97 return filterOutNotInAB(pts, off, num, A, B) - off;
98 }
99 // From Graphics Gems:
100 // https://github.com/erich666/GraphicsGems/blob/master/gems/Roots3And4.c
101 // (also from awt.geom.CubicCurve2D. But here we don't need as
102 // much accuracy and we don't want to create arrays so we use
103 // our own customized version).
104
105 // normal form: x^3 + ax^2 + bx + c = 0
106
107 // 2018.1: Need double precision if d is very small (flat curve) !
108 /*
109 * TODO: cleanup all that code after reading Roots3And4.c
110 */
111 final double a = ((double)a0) / d0;
112 final double b = ((double)b0) / d0;
113 final double c = ((double)c0) / d0;
114
115 // substitute x = y - A/3 to eliminate quadratic term:
116 // x^3 +Px + Q = 0
117 //
118 // Since we actually need P/3 and Q/2 for all of the
119 // calculations that follow, we will calculate
120 // p = P/3
121 // q = Q/2
122 // instead and use those values for simplicity of the code.
123 final double sub = (1.0d / 3.0d) * a;
124 final double sq_A = a * a;
125 final double p = (1.0d / 3.0d) * ((-1.0d / 3.0d) * sq_A + b);
126 final double q = (1.0d / 2.0d) * ((2.0d / 27.0d) * a * sq_A - sub * b + c);
127
128 // use Cardano's formula
129
130 final double cb_p = p * p * p;
131 final double D = q * q + cb_p;
132
133 int num;
134 if (D < 0.0d) {
135 // see: http://en.wikipedia.org/wiki/Cubic_function#Trigonometric_.28and_hyperbolic.29_method
136 final double phi = (1.0d / 3.0d) * Math.acos(-q / Math.sqrt(-cb_p));
137 final double t = 2.0d * Math.sqrt(-p);
138
139 pts[off ] = (float) ( t * Math.cos(phi) - sub);
140 pts[off + 1] = (float) (-t * Math.cos(phi + (Math.PI / 3.0d)) - sub);
141 pts[off + 2] = (float) (-t * Math.cos(phi - (Math.PI / 3.0d)) - sub);
142 num = 3;
143 } else {
144 final double sqrt_D = Math.sqrt(D);
145 final double u = Math.cbrt(sqrt_D - q);
146 final double v = - Math.cbrt(sqrt_D + q);
147
148 pts[off ] = (float) (u + v - sub);
149 num = 1;
150
151 if (within(D, 0.0d, 1e-8d)) {
152 pts[off + 1] = (float)((-1.0d / 2.0d) * (u + v) - sub);
153 num = 2;
154 }
155 }
156
157 return filterOutNotInAB(pts, off, num, A, B) - off;
158 }
159
160 // returns the index 1 past the last valid element remaining after filtering
161 static int filterOutNotInAB(final float[] nums, final int off, final int len,
162 final float a, final float b)
163 {
164 int ret = off;
165 for (int i = off, end = off + len; i < end; i++) {
166 if (nums[i] >= a && nums[i] < b) {
167 nums[ret++] = nums[i];
168 }
169 }
170 return ret;
171 }
172
173 static float fastLineLen(final float x0, final float y0,
174 final float x1, final float y1)
175 {
176 final float dx = x1 - x0;
177 final float dy = y1 - y0;
178
179 // use manhattan norm:
180 return Math.abs(dx) + Math.abs(dy);
181 }
182
183 static float linelen(final float x0, final float y0,
184 final float x1, final float y1)
185 {
186 final float dx = x1 - x0;
187 final float dy = y1 - y0;
188 return (float) Math.sqrt(dx * dx + dy * dy);
189 }
190
191 static float fastQuadLen(final float x0, final float y0,
192 final float x1, final float y1,
193 final float x2, final float y2)
194 {
195 final float dx1 = x1 - x0;
196 final float dx2 = x2 - x1;
197 final float dy1 = y1 - y0;
198 final float dy2 = y2 - y1;
199
200 // use manhattan norm:
201 return Math.abs(dx1) + Math.abs(dx2)
202 + Math.abs(dy1) + Math.abs(dy2);
203 }
204
205 static float quadlen(final float x0, final float y0,
206 final float x1, final float y1,
207 final float x2, final float y2)
208 {
209 return (linelen(x0, y0, x1, y1)
210 + linelen(x1, y1, x2, y2)
211 + linelen(x0, y0, x2, y2)) / 2.0f;
212 }
213
214
215 static float fastCurvelen(final float x0, final float y0,
216 final float x1, final float y1,
217 final float x2, final float y2,
218 final float x3, final float y3)
219 {
220 final float dx1 = x1 - x0;
221 final float dx2 = x2 - x1;
222 final float dx3 = x3 - x2;
223 final float dy1 = y1 - y0;
224 final float dy2 = y2 - y1;
225 final float dy3 = y3 - y2;
226
227 // use manhattan norm:
228 return Math.abs(dx1) + Math.abs(dx2) + Math.abs(dx3)
229 + Math.abs(dy1) + Math.abs(dy2) + Math.abs(dy3);
230 }
231
232 static float curvelen(final float x0, final float y0,
233 final float x1, final float y1,
234 final float x2, final float y2,
235 final float x3, final float y3)
236 {
237 return (linelen(x0, y0, x1, y1)
238 + linelen(x1, y1, x2, y2)
239 + linelen(x2, y2, x3, y3)
240 + linelen(x0, y0, x3, y3)) / 2.0f;
241 }
242
243 // finds values of t where the curve in pts should be subdivided in order
244 // to get good offset curves a distance of w away from the middle curve.
245 // Stores the points in ts, and returns how many of them there were.
246 static int findSubdivPoints(final Curve c, final float[] pts,
247 final float[] ts, final int type,
248 final float w2)
249 {
250 final float x12 = pts[2] - pts[0];
251 final float y12 = pts[3] - pts[1];
252 // if the curve is already parallel to either axis we gain nothing
253 // from rotating it.
254 if ((y12 != 0.0f && x12 != 0.0f)) {
255 // we rotate it so that the first vector in the control polygon is
256 // parallel to the x-axis. This will ensure that rotated quarter
257 // circles won't be subdivided.
258 final float hypot = (float)Math.sqrt(x12 * x12 + y12 * y12);
259 final float cos = x12 / hypot;
260 final float sin = y12 / hypot;
261 final float x1 = cos * pts[0] + sin * pts[1];
262 final float y1 = cos * pts[1] - sin * pts[0];
263 final float x2 = cos * pts[2] + sin * pts[3];
264 final float y2 = cos * pts[3] - sin * pts[2];
265 final float x3 = cos * pts[4] + sin * pts[5];
266 final float y3 = cos * pts[5] - sin * pts[4];
267
268 switch(type) {
269 case 8:
270 final float x4 = cos * pts[6] + sin * pts[7];
271 final float y4 = cos * pts[7] - sin * pts[6];
272 c.set(x1, y1, x2, y2, x3, y3, x4, y4);
273 break;
274 case 6:
275 c.set(x1, y1, x2, y2, x3, y3);
276 break;
277 default:
278 }
279 } else {
280 c.set(pts, type);
281 }
282
283 int ret = 0;
284 // we subdivide at values of t such that the remaining rotated
285 // curves are monotonic in x and y.
286 ret += c.dxRoots(ts, ret);
287 ret += c.dyRoots(ts, ret);
288
289 // subdivide at inflection points.
290 if (type == 8) {
291 // quadratic curves can't have inflection points
292 ret += c.infPoints(ts, ret);
293 }
294
295 // now we must subdivide at points where one of the offset curves will have
296 // a cusp. This happens at ts where the radius of curvature is equal to w.
297 ret += c.rootsOfROCMinusW(ts, ret, w2, 0.0001f);
298
299 ret = filterOutNotInAB(ts, 0, ret, 0.0001f, 0.9999f);
300 isort(ts, ret);
301 return ret;
302 }
303
304 // finds values of t where the curve in pts should be subdivided in order
305 // to get intersections with the given clip rectangle.
306 // Stores the points in ts, and returns how many of them there were.
307 static int findClipPoints(final Curve curve, final float[] pts,
308 final float[] ts, final int type,
309 final int outCodeOR,
310 final float[] clipRect)
311 {
312 curve.set(pts, type);
313
314 // clip rectangle (ymin, ymax, xmin, xmax)
315 int ret = 0;
316
317 if ((outCodeOR & OUTCODE_LEFT) != 0) {
318 ret += curve.xPoints(ts, ret, clipRect[2]);
319 }
320 if ((outCodeOR & OUTCODE_RIGHT) != 0) {
321 ret += curve.xPoints(ts, ret, clipRect[3]);
322 }
323 if ((outCodeOR & OUTCODE_TOP) != 0) {
324 ret += curve.yPoints(ts, ret, clipRect[0]);
325 }
326 if ((outCodeOR & OUTCODE_BOTTOM) != 0) {
327 ret += curve.yPoints(ts, ret, clipRect[1]);
328 }
329 isort(ts, ret);
330 return ret;
331 }
332
333 static void subdivide(final float[] src,
334 final float[] left, final float[] right,
335 final int type)
336 {
337 switch(type) {
338 case 8:
339 subdivideCubic(src, left, right);
340 return;
341 case 6:
342 subdivideQuad(src, left, right);
343 return;
344 default:
345 throw new InternalError("Unsupported curve type");
346 }
347 }
348
349 static void isort(final float[] a, final int len) {
350 for (int i = 1, j; i < len; i++) {
351 final float ai = a[i];
352 j = i - 1;
353 for (; j >= 0 && a[j] > ai; j--) {
354 a[j + 1] = a[j];
355 }
356 a[j + 1] = ai;
357 }
358 }
359
360 // Most of these are copied from classes in java.awt.geom because we need
361 // both single and double precision variants of these functions, and Line2D,
362 // CubicCurve2D, QuadCurve2D don't provide them.
363 /**
364 * Subdivides the cubic curve specified by the coordinates
365 * stored in the <code>src</code> array at indices <code>srcoff</code>
366 * through (<code>srcoff</code> + 7) and stores the
367 * resulting two subdivided curves into the two result arrays at the
368 * corresponding indices.
369 * Either or both of the <code>left</code> and <code>right</code>
370 * arrays may be <code>null</code> or a reference to the same array
371 * as the <code>src</code> array.
372 * Note that the last point in the first subdivided curve is the
373 * same as the first point in the second subdivided curve. Thus,
374 * it is possible to pass the same array for <code>left</code>
375 * and <code>right</code> and to use offsets, such as <code>rightoff</code>
376 * equals (<code>leftoff</code> + 6), in order
377 * to avoid allocating extra storage for this common point.
378 * @param src the array holding the coordinates for the source curve
379 * @param left the array for storing the coordinates for the first
380 * half of the subdivided curve
381 * @param right the array for storing the coordinates for the second
382 * half of the subdivided curve
383 * @since 1.7
384 */
385 static void subdivideCubic(final float[] src,
386 final float[] left,
387 final float[] right)
388 {
389 float x1 = src[0];
390 float y1 = src[1];
391 float cx1 = src[2];
392 float cy1 = src[3];
393 float cx2 = src[4];
394 float cy2 = src[5];
395 float x2 = src[6];
396 float y2 = src[7];
397
398 left[0] = x1;
399 left[1] = y1;
400
401 right[6] = x2;
402 right[7] = y2;
403
404 x1 = (x1 + cx1) / 2.0f;
405 y1 = (y1 + cy1) / 2.0f;
406 x2 = (x2 + cx2) / 2.0f;
407 y2 = (y2 + cy2) / 2.0f;
408
409 float cx = (cx1 + cx2) / 2.0f;
410 float cy = (cy1 + cy2) / 2.0f;
411
412 cx1 = (x1 + cx) / 2.0f;
413 cy1 = (y1 + cy) / 2.0f;
414 cx2 = (x2 + cx) / 2.0f;
415 cy2 = (y2 + cy) / 2.0f;
416 cx = (cx1 + cx2) / 2.0f;
417 cy = (cy1 + cy2) / 2.0f;
418
419 left[2] = x1;
420 left[3] = y1;
421 left[4] = cx1;
422 left[5] = cy1;
423 left[6] = cx;
424 left[7] = cy;
425
426 right[0] = cx;
427 right[1] = cy;
428 right[2] = cx2;
429 right[3] = cy2;
430 right[4] = x2;
431 right[5] = y2;
432 }
433
434 static void subdivideCubicAt(final float t,
435 final float[] src, final int offS,
436 final float[] pts, final int offL, final int offR)
437 {
438 float x1 = src[offS ];
439 float y1 = src[offS + 1];
440 float cx1 = src[offS + 2];
441 float cy1 = src[offS + 3];
442 float cx2 = src[offS + 4];
443 float cy2 = src[offS + 5];
444 float x2 = src[offS + 6];
445 float y2 = src[offS + 7];
446
447 pts[offL ] = x1;
448 pts[offL + 1] = y1;
449
450 pts[offR + 6] = x2;
451 pts[offR + 7] = y2;
452
453 x1 = x1 + t * (cx1 - x1);
454 y1 = y1 + t * (cy1 - y1);
455 x2 = cx2 + t * (x2 - cx2);
456 y2 = cy2 + t * (y2 - cy2);
457
458 float cx = cx1 + t * (cx2 - cx1);
459 float cy = cy1 + t * (cy2 - cy1);
460
461 cx1 = x1 + t * (cx - x1);
462 cy1 = y1 + t * (cy - y1);
463 cx2 = cx + t * (x2 - cx);
464 cy2 = cy + t * (y2 - cy);
465 cx = cx1 + t * (cx2 - cx1);
466 cy = cy1 + t * (cy2 - cy1);
467
468 pts[offL + 2] = x1;
469 pts[offL + 3] = y1;
470 pts[offL + 4] = cx1;
471 pts[offL + 5] = cy1;
472 pts[offL + 6] = cx;
473 pts[offL + 7] = cy;
474
475 pts[offR ] = cx;
476 pts[offR + 1] = cy;
477 pts[offR + 2] = cx2;
478 pts[offR + 3] = cy2;
479 pts[offR + 4] = x2;
480 pts[offR + 5] = y2;
481 }
482
483 static void subdivideQuad(final float[] src,
484 final float[] left,
485 final float[] right)
486 {
487 float x1 = src[0];
488 float y1 = src[1];
489 float cx = src[2];
490 float cy = src[3];
491 float x2 = src[4];
492 float y2 = src[5];
493
494 left[0] = x1;
495 left[1] = y1;
496
497 right[4] = x2;
498 right[5] = y2;
499
500 x1 = (x1 + cx) / 2.0f;
501 y1 = (y1 + cy) / 2.0f;
502 x2 = (x2 + cx) / 2.0f;
503 y2 = (y2 + cy) / 2.0f;
504 cx = (x1 + x2) / 2.0f;
505 cy = (y1 + y2) / 2.0f;
506
507 left[2] = x1;
508 left[3] = y1;
509 left[4] = cx;
510 left[5] = cy;
511
512 right[0] = cx;
513 right[1] = cy;
514 right[2] = x2;
515 right[3] = y2;
516 }
517
518 static void subdivideQuadAt(final float t,
519 final float[] src, final int offS,
520 final float[] pts, final int offL, final int offR)
521 {
522 float x1 = src[offS ];
523 float y1 = src[offS + 1];
524 float cx = src[offS + 2];
525 float cy = src[offS + 3];
526 float x2 = src[offS + 4];
527 float y2 = src[offS + 5];
528
529 pts[offL ] = x1;
530 pts[offL + 1] = y1;
531
532 pts[offR + 4] = x2;
533 pts[offR + 5] = y2;
534
535 x1 = x1 + t * (cx - x1);
536 y1 = y1 + t * (cy - y1);
537 x2 = cx + t * (x2 - cx);
538 y2 = cy + t * (y2 - cy);
539 cx = x1 + t * (x2 - x1);
540 cy = y1 + t * (y2 - y1);
541
542 pts[offL + 2] = x1;
543 pts[offL + 3] = y1;
544 pts[offL + 4] = cx;
545 pts[offL + 5] = cy;
546
547 pts[offR ] = cx;
548 pts[offR + 1] = cy;
549 pts[offR + 2] = x2;
550 pts[offR + 3] = y2;
551 }
552
553 static void subdivideLineAt(final float t,
554 final float[] src, final int offS,
555 final float[] pts, final int offL, final int offR)
556 {
557 float x1 = src[offS ];
558 float y1 = src[offS + 1];
559 float x2 = src[offS + 2];
560 float y2 = src[offS + 3];
561
562 pts[offL ] = x1;
563 pts[offL + 1] = y1;
564
565 pts[offR + 2] = x2;
566 pts[offR + 3] = y2;
567
568 x1 = x1 + t * (x2 - x1);
569 y1 = y1 + t * (y2 - y1);
570
571 pts[offL + 2] = x1;
572 pts[offL + 3] = y1;
573
574 pts[offR ] = x1;
575 pts[offR + 1] = y1;
576 }
577
578 static void subdivideAt(final float t,
579 final float[] src, final int offS,
580 final float[] pts, final int offL, final int type)
581 {
582 // if instead of switch (perf + most probable cases first)
583 if (type == 8) {
584 subdivideCubicAt(t, src, offS, pts, offL, offL + type);
585 } else if (type == 4) {
586 subdivideLineAt(t, src, offS, pts, offL, offL + type);
587 } else {
588 subdivideQuadAt(t, src, offS, pts, offL, offL + type);
589 }
590 }
591
592 // From sun.java2d.loops.GeneralRenderer:
593
594 static int outcode(final float x, final float y,
595 final float[] clipRect)
596 {
597 int code;
598 if (y < clipRect[0]) {
599 code = OUTCODE_TOP;
600 } else if (y >= clipRect[1]) {
601 code = OUTCODE_BOTTOM;
602 } else {
603 code = 0;
604 }
605 if (x < clipRect[2]) {
606 code |= OUTCODE_LEFT;
607 } else if (x >= clipRect[3]) {
608 code |= OUTCODE_RIGHT;
755 }
756 if (DO_STATS) {
757 // update used marks:
758 if (numCurves > curveTypesUseMark) {
759 curveTypesUseMark = numCurves;
760 }
761 if (end > curvesUseMark) {
762 curvesUseMark = end;
763 }
764 }
765 final byte[] _curveTypes = curveTypes;
766 final float[] _curves = curves;
767 int e = 0;
768
769 for (int i = 0; i < nc; i++) {
770 switch(_curveTypes[i]) {
771 case TYPE_LINETO:
772 io.lineTo(_curves[e], _curves[e+1]);
773 e += 2;
774 continue;
775 case TYPE_CUBICTO:
776 io.curveTo(_curves[e], _curves[e+1],
777 _curves[e+2], _curves[e+3],
778 _curves[e+4], _curves[e+5]);
779 e += 6;
780 continue;
781 case TYPE_QUADTO:
782 io.quadTo(_curves[e], _curves[e+1],
783 _curves[e+2], _curves[e+3]);
784 e += 4;
785 continue;
786 default:
787 }
788 }
789 numCurves = 0;
790 end = 0;
791 }
792
793 void popAll(final PathConsumer2D io) {
794 int nc = numCurves;
795 if (nc == 0) {
796 return;
797 }
798 if (DO_STATS) {
799 // update used marks:
800 if (numCurves > curveTypesUseMark) {
801 curveTypesUseMark = numCurves;
802 }
803 if (end > curvesUseMark) {
804 curvesUseMark = end;
805 }
806 }
807 final byte[] _curveTypes = curveTypes;
808 final float[] _curves = curves;
809 int e = end;
810
811 while (nc != 0) {
812 switch(_curveTypes[--nc]) {
813 case TYPE_LINETO:
814 e -= 2;
815 io.lineTo(_curves[e], _curves[e+1]);
816 continue;
817 case TYPE_CUBICTO:
818 e -= 6;
819 io.curveTo(_curves[e], _curves[e+1],
820 _curves[e+2], _curves[e+3],
821 _curves[e+4], _curves[e+5]);
822 continue;
823 case TYPE_QUADTO:
824 e -= 4;
825 io.quadTo(_curves[e], _curves[e+1],
826 _curves[e+2], _curves[e+3]);
827 continue;
828 default:
829 }
830 }
831 numCurves = 0;
832 end = 0;
833 }
834
835 @Override
836 public String toString() {
837 String ret = "";
838 int nc = numCurves;
839 int last = end;
840 int len;
841 while (nc != 0) {
842 switch(curveTypes[--nc]) {
843 case TYPE_LINETO:
844 len = 2;
845 ret += "line: ";
846 break;
|