001:/*
002: * Copyright 1998-2006 Sun Microsystems, Inc. All Rights Reserved.
003: * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
004: *
005: * This code is free software; you can redistribute it and/or modify it
006: * under the terms of the GNU General Public License version 2 only, as
007: * published by the Free Software Foundation. Sun designates this
008: * particular file as subject to the "Classpath" exception as provided
009: * by Sun in the LICENSE file that accompanied this code.
010: *
011: * This code is distributed in the hope that it will be useful, but WITHOUT
012: * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
013: * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
014: * version 2 for more details (a copy is included in the LICENSE file that
015: * accompanied this code).
016: *
017: * You should have received a copy of the GNU General Public License version
018: * 2 along with this work; if not, write to the Free Software Foundation,
019: * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
020: *
021: * Please contact Sun Microsystems, Inc., 4150 Network Circle, Santa Clara,
022: * CA 95054 USA or visit www.sun.com if you need additional information or
023: * have any questions.
024: */
025:
026:package sun.awt.geom;
027:
028:import java.awt.geom.Rectangle2D;
029:import java.awt.geom.PathIterator;
030:import java.awt.geom.QuadCurve2D;
031:import java.util.Vector;
032:
033:final class Order3 extends Curve {
034: private double x0;
035: private double y0;
036: private double cx0;
037: private double cy0;
038: private double cx1;
039: private double cy1;
040: private double x1;
041: private double y1;
042:
043: private double xmin;
044: private double xmax;
045:
046: private double xcoeff0;
047: private double xcoeff1;
048: private double xcoeff2;
049: private double xcoeff3;
050:
051: private double ycoeff0;
052: private double ycoeff1;
053: private double ycoeff2;
054: private double ycoeff3;
055:
056: public static void insert(Vector curves, double tmp[],
057: double x0, double y0,
058: double cx0, double cy0,
059: double cx1, double cy1,
060: double x1, double y1,
061: int direction)
062: {
063: int numparams = getHorizontalParams(y0, cy0, cy1, y1, tmp);
064: if (numparams == 0) {
065: // We are using addInstance here to avoid inserting horisontal
066: // segments
067: addInstance(curves, x0, y0, cx0, cy0, cx1, cy1, x1, y1, direction);
068: return;
069: }
070: // Store coordinates for splitting at tmp[3..10]
071: tmp[3] = x0; tmp[4] = y0;
072: tmp[5] = cx0; tmp[6] = cy0;
073: tmp[7] = cx1; tmp[8] = cy1;
074: tmp[9] = x1; tmp[10] = y1;
075: double t = tmp[0];
076: if (numparams > 1 && t > tmp[1]) {
077: // Perform a "2 element sort"...
078: tmp[0] = tmp[1];
079: tmp[1] = t;
080: t = tmp[0];
081: }
082: split(tmp, 3, t);
083: if (numparams > 1) {
084: // Recalculate tmp[1] relative to the range [tmp[0]...1]
085: t = (tmp[1] - t) / (1 - t);
086: split(tmp, 9, t);
087: }
088: int index = 3;
089: if (direction == DECREASING) {
090: index += numparams * 6;
091: }
092: while (numparams >= 0) {
093: addInstance(curves,
094: tmp[index + 0], tmp[index + 1],
095: tmp[index + 2], tmp[index + 3],
096: tmp[index + 4], tmp[index + 5],
097: tmp[index + 6], tmp[index + 7],
098: direction);
099: 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:}
|