1 /*
2 * Copyright (c) 1998, 2006, 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.awt.geom;
27
28 import java.awt.geom.Rectangle2D;
29 import java.awt.geom.PathIterator;
30 import java.awt.geom.QuadCurve2D;
31 import java.util.Vector;
32
33 final class Order3 extends Curve {
34 private double x0;
35 private double y0;
36 private double cx0;
37 private double cy0;
38 private double cx1;
39 private double cy1;
40 private double x1;
41 private double y1;
42
43 private double xmin;
44 private double xmax;
45
46 private double xcoeff0;
47 private double xcoeff1;
48 private double xcoeff2;
49 private double xcoeff3;
50
51 private double ycoeff0;
52 private double ycoeff1;
53 private double ycoeff2;
54 private double ycoeff3;
55
56 public static void insert(Vector curves, double tmp[],
57 double x0, double y0,
58 double cx0, double cy0,
59 double cx1, double cy1,
60 double x1, double y1,
61 int direction)
62 {
63 int numparams = getHorizontalParams(y0, cy0, cy1, y1, tmp);
64 if (numparams == 0) {
65 // We are using addInstance here to avoid inserting horisontal
66 // segments
67 addInstance(curves, x0, y0, cx0, cy0, cx1, cy1, x1, y1, direction);
68 return;
69 }
70 // Store coordinates for splitting at tmp[3..10]
71 tmp[3] = x0; tmp[4] = y0;
72 tmp[5] = cx0; tmp[6] = cy0;
73 tmp[7] = cx1; tmp[8] = cy1;
74 tmp[9] = x1; tmp[10] = y1;
75 double t = tmp[0];
76 if (numparams > 1 && t > tmp[1]) {
77 // Perform a "2 element sort"...
78 tmp[0] = tmp[1];
79 tmp[1] = t;
80 t = tmp[0];
81 }
82 split(tmp, 3, t);
83 if (numparams > 1) {
84 // Recalculate tmp[1] relative to the range [tmp[0]...1]
85 t = (tmp[1] - t) / (1 - t);
86 split(tmp, 9, t);
87 }
88 int index = 3;
89 if (direction == DECREASING) {
90 index += numparams * 6;
91 }
92 while (numparams >= 0) {
93 addInstance(curves,
94 tmp[index + 0], tmp[index + 1],
95 tmp[index + 2], tmp[index + 3],
96 tmp[index + 4], tmp[index + 5],
97 tmp[index + 6], tmp[index + 7],
98 direction);
99 numparams--;
100 if (direction == INCREASING) {
101 index += 6;
102 } else {
103 index -= 6;
104 }
105 }
106 }
107
108 public static void addInstance(Vector curves,
109 double x0, double y0,
110 double cx0, double cy0,
111 double cx1, double cy1,
112 double x1, double y1,
113 int direction) {
114 if (y0 > y1) {
115 curves.add(new Order3(x1, y1, cx1, cy1, cx0, cy0, x0, y0,
116 -direction));
117 } else if (y1 > y0) {
118 curves.add(new Order3(x0, y0, cx0, cy0, cx1, cy1, x1, y1,
119 direction));
120 }
121 }
122
123 /*
124 * Return the count of the number of horizontal sections of the
125 * specified cubic Bezier curve. Put the parameters for the
126 * horizontal sections into the specified <code>ret</code> array.
127 * <p>
128 * If we examine the parametric equation in t, we have:
129 * Py(t) = C0(1-t)^3 + 3CP0 t(1-t)^2 + 3CP1 t^2(1-t) + C1 t^3
130 * = C0 - 3C0t + 3C0t^2 - C0t^3 +
131 * 3CP0t - 6CP0t^2 + 3CP0t^3 +
132 * 3CP1t^2 - 3CP1t^3 +
133 * C1t^3
134 * Py(t) = (C1 - 3CP1 + 3CP0 - C0) t^3 +
135 * (3C0 - 6CP0 + 3CP1) t^2 +
136 * (3CP0 - 3C0) t +
137 * (C0)
138 * If we take the derivative, we get:
139 * Py(t) = Dt^3 + At^2 + Bt + C
140 * dPy(t) = 3Dt^2 + 2At + B = 0
141 * 0 = 3*(C1 - 3*CP1 + 3*CP0 - C0)t^2
142 * + 2*(3*CP1 - 6*CP0 + 3*C0)t
143 * + (3*CP0 - 3*C0)
144 * 0 = 3*(C1 - 3*CP1 + 3*CP0 - C0)t^2
145 * + 3*2*(CP1 - 2*CP0 + C0)t
146 * + 3*(CP0 - C0)
147 * 0 = (C1 - CP1 - CP1 - CP1 + CP0 + CP0 + CP0 - C0)t^2
148 * + 2*(CP1 - CP0 - CP0 + C0)t
149 * + (CP0 - C0)
150 * 0 = (C1 - CP1 + CP0 - CP1 + CP0 - CP1 + CP0 - C0)t^2
151 * + 2*(CP1 - CP0 - CP0 + C0)t
152 * + (CP0 - C0)
153 * 0 = ((C1 - CP1) - (CP1 - CP0) - (CP1 - CP0) + (CP0 - C0))t^2
154 * + 2*((CP1 - CP0) - (CP0 - C0))t
155 * + (CP0 - C0)
156 * Note that this method will return 0 if the equation is a line,
157 * which is either always horizontal or never horizontal.
158 * Completely horizontal curves need to be eliminated by other
159 * means outside of this method.
160 */
161 public static int getHorizontalParams(double c0, double cp0,
162 double cp1, double c1,
163 double ret[]) {
164 if (c0 <= cp0 && cp0 <= cp1 && cp1 <= c1) {
165 return 0;
166 }
167 c1 -= cp1;
168 cp1 -= cp0;
169 cp0 -= c0;
170 ret[0] = cp0;
171 ret[1] = (cp1 - cp0) * 2;
172 ret[2] = (c1 - cp1 - cp1 + cp0);
173 int numroots = QuadCurve2D.solveQuadratic(ret, ret);
174 int j = 0;
175 for (int i = 0; i < numroots; i++) {
176 double t = ret[i];
177 // No splits at t==0 and t==1
178 if (t > 0 && t < 1) {
179 if (j < i) {
180 ret[j] = t;
181 }
182 j++;
183 }
184 }
185 return j;
186 }
187
188 /*
189 * Split the cubic Bezier stored at coords[pos...pos+7] representing
190 * the parametric range [0..1] into two subcurves representing the
191 * parametric subranges [0..t] and [t..1]. Store the results back
192 * into the array at coords[pos...pos+7] and coords[pos+6...pos+13].
193 */
194 public static void split(double coords[], int pos, double t) {
195 double x0, y0, cx0, cy0, cx1, cy1, x1, y1;
196 coords[pos+12] = x1 = coords[pos+6];
197 coords[pos+13] = y1 = coords[pos+7];
198 cx1 = coords[pos+4];
199 cy1 = coords[pos+5];
200 x1 = cx1 + (x1 - cx1) * t;
201 y1 = cy1 + (y1 - cy1) * t;
202 x0 = coords[pos+0];
203 y0 = coords[pos+1];
204 cx0 = coords[pos+2];
205 cy0 = coords[pos+3];
206 x0 = x0 + (cx0 - x0) * t;
207 y0 = y0 + (cy0 - y0) * t;
208 cx0 = cx0 + (cx1 - cx0) * t;
209 cy0 = cy0 + (cy1 - cy0) * t;
210 cx1 = cx0 + (x1 - cx0) * t;
211 cy1 = cy0 + (y1 - cy0) * t;
212 cx0 = x0 + (cx0 - x0) * t;
213 cy0 = y0 + (cy0 - y0) * t;
214 coords[pos+2] = x0;
215 coords[pos+3] = y0;
216 coords[pos+4] = cx0;
217 coords[pos+5] = cy0;
218 coords[pos+6] = cx0 + (cx1 - cx0) * t;
219 coords[pos+7] = cy0 + (cy1 - cy0) * t;
220 coords[pos+8] = cx1;
221 coords[pos+9] = cy1;
222 coords[pos+10] = x1;
223 coords[pos+11] = y1;
224 }
225
226 public Order3(double x0, double y0,
227 double cx0, double cy0,
228 double cx1, double cy1,
229 double x1, double y1,
230 int direction)
231 {
232 super(direction);
233 // REMIND: Better accuracy in the root finding methods would
234 // ensure that cys are in range. As it stands, they are never
235 // more than "1 mantissa bit" out of range...
236 if (cy0 < y0) cy0 = y0;
237 if (cy1 > y1) cy1 = y1;
238 this.x0 = x0;
239 this.y0 = y0;
240 this.cx0 = cx0;
241 this.cy0 = cy0;
242 this.cx1 = cx1;
243 this.cy1 = cy1;
244 this.x1 = x1;
245 this.y1 = y1;
246 xmin = Math.min(Math.min(x0, x1), Math.min(cx0, cx1));
247 xmax = Math.max(Math.max(x0, x1), Math.max(cx0, cx1));
248 xcoeff0 = x0;
249 xcoeff1 = (cx0 - x0) * 3.0;
250 xcoeff2 = (cx1 - cx0 - cx0 + x0) * 3.0;
251 xcoeff3 = x1 - (cx1 - cx0) * 3.0 - x0;
252 ycoeff0 = y0;
253 ycoeff1 = (cy0 - y0) * 3.0;
254 ycoeff2 = (cy1 - cy0 - cy0 + y0) * 3.0;
255 ycoeff3 = y1 - (cy1 - cy0) * 3.0 - y0;
256 YforT1 = YforT2 = YforT3 = y0;
257 }
258
259 public int getOrder() {
260 return 3;
261 }
262
263 public double getXTop() {
264 return x0;
265 }
266
267 public double getYTop() {
268 return y0;
269 }
270
271 public double getXBot() {
272 return x1;
273 }
274
275 public double getYBot() {
276 return y1;
277 }
278
279 public double getXMin() {
280 return xmin;
281 }
282
283 public double getXMax() {
284 return xmax;
285 }
286
287 public double getX0() {
288 return (direction == INCREASING) ? x0 : x1;
289 }
290
291 public double getY0() {
292 return (direction == INCREASING) ? y0 : y1;
293 }
294
295 public double getCX0() {
296 return (direction == INCREASING) ? cx0 : cx1;
297 }
298
299 public double getCY0() {
300 return (direction == INCREASING) ? cy0 : cy1;
301 }
302
303 public double getCX1() {
304 return (direction == DECREASING) ? cx0 : cx1;
305 }
306
307 public double getCY1() {
308 return (direction == DECREASING) ? cy0 : cy1;
309 }
310
311 public double getX1() {
312 return (direction == DECREASING) ? x0 : x1;
313 }
314
315 public double getY1() {
316 return (direction == DECREASING) ? y0 : y1;
317 }
318
319 private double TforY1;
320 private double YforT1;
321 private double TforY2;
322 private double YforT2;
323 private double TforY3;
324 private double YforT3;
325
326 /*
327 * Solve the cubic whose coefficients are in the a,b,c,d fields and
328 * return the first root in the range [0, 1].
329 * The cubic solved is represented by the equation:
330 * x^3 + (ycoeff2)x^2 + (ycoeff1)x + (ycoeff0) = y
331 * @return the first valid root (in the range [0, 1])
332 */
333 public double TforY(double y) {
334 if (y <= y0) return 0;
335 if (y >= y1) return 1;
336 if (y == YforT1) return TforY1;
337 if (y == YforT2) return TforY2;
338 if (y == YforT3) return TforY3;
339 // From Numerical Recipes, 5.6, Quadratic and Cubic Equations
340 if (ycoeff3 == 0.0) {
341 // The cubic degenerated to quadratic (or line or ...).
342 return Order2.TforY(y, ycoeff0, ycoeff1, ycoeff2);
343 }
344 double a = ycoeff2 / ycoeff3;
345 double b = ycoeff1 / ycoeff3;
346 double c = (ycoeff0 - y) / ycoeff3;
347 int roots = 0;
348 double Q = (a * a - 3.0 * b) / 9.0;
349 double R = (2.0 * a * a * a - 9.0 * a * b + 27.0 * c) / 54.0;
350 double R2 = R * R;
351 double Q3 = Q * Q * Q;
352 double a_3 = a / 3.0;
353 double t;
354 if (R2 < Q3) {
355 double theta = Math.acos(R / Math.sqrt(Q3));
356 Q = -2.0 * Math.sqrt(Q);
357 t = refine(a, b, c, y, Q * Math.cos(theta / 3.0) - a_3);
358 if (t < 0) {
359 t = refine(a, b, c, y,
360 Q * Math.cos((theta + Math.PI * 2.0)/ 3.0) - a_3);
361 }
362 if (t < 0) {
363 t = refine(a, b, c, y,
364 Q * Math.cos((theta - Math.PI * 2.0)/ 3.0) - a_3);
365 }
366 } else {
367 boolean neg = (R < 0.0);
368 double S = Math.sqrt(R2 - Q3);
369 if (neg) {
370 R = -R;
371 }
372 double A = Math.pow(R + S, 1.0 / 3.0);
373 if (!neg) {
374 A = -A;
375 }
376 double B = (A == 0.0) ? 0.0 : (Q / A);
377 t = refine(a, b, c, y, (A + B) - a_3);
378 }
379 if (t < 0) {
380 //throw new InternalError("bad t");
381 double t0 = 0;
382 double t1 = 1;
383 while (true) {
384 t = (t0 + t1) / 2;
385 if (t == t0 || t == t1) {
386 break;
387 }
388 double yt = YforT(t);
389 if (yt < y) {
390 t0 = t;
391 } else if (yt > y) {
392 t1 = t;
393 } else {
394 break;
395 }
396 }
397 }
398 if (t >= 0) {
399 TforY3 = TforY2;
400 YforT3 = YforT2;
401 TforY2 = TforY1;
402 YforT2 = YforT1;
403 TforY1 = t;
404 YforT1 = y;
405 }
406 return t;
407 }
408
409 public double refine(double a, double b, double c,
410 double target, double t)
411 {
412 if (t < -0.1 || t > 1.1) {
413 return -1;
414 }
415 double y = YforT(t);
416 double t0, t1;
417 if (y < target) {
418 t0 = t;
419 t1 = 1;
420 } else {
421 t0 = 0;
422 t1 = t;
423 }
424 double origt = t;
425 double origy = y;
426 boolean useslope = true;
427 while (y != target) {
428 if (!useslope) {
429 double t2 = (t0 + t1) / 2;
430 if (t2 == t0 || t2 == t1) {
431 break;
432 }
433 t = t2;
434 } else {
435 double slope = dYforT(t, 1);
436 if (slope == 0) {
437 useslope = false;
438 continue;
439 }
440 double t2 = t + ((target - y) / slope);
441 if (t2 == t || t2 <= t0 || t2 >= t1) {
442 useslope = false;
443 continue;
444 }
445 t = t2;
446 }
447 y = YforT(t);
448 if (y < target) {
449 t0 = t;
450 } else if (y > target) {
451 t1 = t;
452 } else {
453 break;
454 }
455 }
456 boolean verbose = false;
457 if (false && t >= 0 && t <= 1) {
458 y = YforT(t);
459 long tdiff = diffbits(t, origt);
460 long ydiff = diffbits(y, origy);
461 long yerr = diffbits(y, target);
462 if (yerr > 0 || (verbose && tdiff > 0)) {
463 System.out.println("target was y = "+target);
464 System.out.println("original was y = "+origy+", t = "+origt);
465 System.out.println("final was y = "+y+", t = "+t);
466 System.out.println("t diff is "+tdiff);
467 System.out.println("y diff is "+ydiff);
468 System.out.println("y error is "+yerr);
469 double tlow = prev(t);
470 double ylow = YforT(tlow);
471 double thi = next(t);
472 double yhi = YforT(thi);
473 if (Math.abs(target - ylow) < Math.abs(target - y) ||
474 Math.abs(target - yhi) < Math.abs(target - y))
475 {
476 System.out.println("adjacent y's = ["+ylow+", "+yhi+"]");
477 }
478 }
479 }
480 return (t > 1) ? -1 : t;
481 }
482
483 public double XforY(double y) {
484 if (y <= y0) {
485 return x0;
486 }
487 if (y >= y1) {
488 return x1;
489 }
490 return XforT(TforY(y));
491 }
492
493 public double XforT(double t) {
494 return (((xcoeff3 * t) + xcoeff2) * t + xcoeff1) * t + xcoeff0;
495 }
496
497 public double YforT(double t) {
498 return (((ycoeff3 * t) + ycoeff2) * t + ycoeff1) * t + ycoeff0;
499 }
500
501 public double dXforT(double t, int deriv) {
502 switch (deriv) {
503 case 0:
504 return (((xcoeff3 * t) + xcoeff2) * t + xcoeff1) * t + xcoeff0;
505 case 1:
506 return ((3 * xcoeff3 * t) + 2 * xcoeff2) * t + xcoeff1;
507 case 2:
508 return (6 * xcoeff3 * t) + 2 * xcoeff2;
509 case 3:
510 return 6 * xcoeff3;
511 default:
512 return 0;
513 }
514 }
515
516 public double dYforT(double t, int deriv) {
517 switch (deriv) {
518 case 0:
519 return (((ycoeff3 * t) + ycoeff2) * t + ycoeff1) * t + ycoeff0;
520 case 1:
521 return ((3 * ycoeff3 * t) + 2 * ycoeff2) * t + ycoeff1;
522 case 2:
523 return (6 * ycoeff3 * t) + 2 * ycoeff2;
524 case 3:
525 return 6 * ycoeff3;
526 default:
527 return 0;
528 }
529 }
530
531 public double nextVertical(double t0, double t1) {
532 double eqn[] = {xcoeff1, 2 * xcoeff2, 3 * xcoeff3};
533 int numroots = QuadCurve2D.solveQuadratic(eqn, eqn);
534 for (int i = 0; i < numroots; i++) {
535 if (eqn[i] > t0 && eqn[i] < t1) {
536 t1 = eqn[i];
537 }
538 }
539 return t1;
540 }
541
542 public void enlarge(Rectangle2D r) {
543 r.add(x0, y0);
544 double eqn[] = {xcoeff1, 2 * xcoeff2, 3 * xcoeff3};
545 int numroots = QuadCurve2D.solveQuadratic(eqn, eqn);
546 for (int i = 0; i < numroots; i++) {
547 double t = eqn[i];
548 if (t > 0 && t < 1) {
549 r.add(XforT(t), YforT(t));
550 }
551 }
552 r.add(x1, y1);
553 }
554
555 public Curve getSubCurve(double ystart, double yend, int dir) {
556 if (ystart <= y0 && yend >= y1) {
557 return getWithDirection(dir);
558 }
559 double eqn[] = new double[14];
560 double t0, t1;
561 t0 = TforY(ystart);
562 t1 = TforY(yend);
563 eqn[0] = x0;
564 eqn[1] = y0;
565 eqn[2] = cx0;
566 eqn[3] = cy0;
567 eqn[4] = cx1;
568 eqn[5] = cy1;
569 eqn[6] = x1;
570 eqn[7] = y1;
571 if (t0 > t1) {
572 /* This happens in only rare cases where ystart is
573 * very near yend and solving for the yend root ends
574 * up stepping slightly lower in t than solving for
575 * the ystart root.
576 * Ideally we might want to skip this tiny little
577 * segment and just fudge the surrounding coordinates
578 * to bridge the gap left behind, but there is no way
579 * to do that from here. Higher levels could
580 * potentially eliminate these tiny "fixup" segments,
581 * but not without a lot of extra work on the code that
582 * coalesces chains of curves into subpaths. The
583 * simplest solution for now is to just reorder the t
584 * values and chop out a miniscule curve piece.
585 */
586 double t = t0;
587 t0 = t1;
588 t1 = t;
589 }
590 if (t1 < 1) {
591 split(eqn, 0, t1);
592 }
593 int i;
594 if (t0 <= 0) {
595 i = 0;
596 } else {
597 split(eqn, 0, t0 / t1);
598 i = 6;
599 }
600 return new Order3(eqn[i+0], ystart,
601 eqn[i+2], eqn[i+3],
602 eqn[i+4], eqn[i+5],
603 eqn[i+6], yend,
604 dir);
605 }
606
607 public Curve getReversedCurve() {
608 return new Order3(x0, y0, cx0, cy0, cx1, cy1, x1, y1, -direction);
609 }
610
611 public int getSegment(double coords[]) {
612 if (direction == INCREASING) {
613 coords[0] = cx0;
614 coords[1] = cy0;
615 coords[2] = cx1;
616 coords[3] = cy1;
617 coords[4] = x1;
618 coords[5] = y1;
619 } else {
620 coords[0] = cx1;
621 coords[1] = cy1;
622 coords[2] = cx0;
623 coords[3] = cy0;
624 coords[4] = x0;
625 coords[5] = y0;
626 }
627 return PathIterator.SEG_CUBICTO;
628 }
629
630 public String controlPointString() {
631 return (("("+round(getCX0())+", "+round(getCY0())+"), ")+
632 ("("+round(getCX1())+", "+round(getCY1())+"), "));
633 }
634 }