001: /*
002: * $Id: Morphing2D.java,v 1.1 2006/10/22 03:26:22 gfx Exp $
003: *
004: * Copyright 2006 Sun Microsystems, Inc., 4150 Network Circle,
005: * Santa Clara, California 95054, U.S.A. All rights reserved.
006: */
007:
008: package org.jdesktop.swingx.geom;
009:
010: import java.awt.Rectangle;
011: import java.awt.Shape;
012: import java.awt.geom.AffineTransform;
013: import java.awt.geom.FlatteningPathIterator;
014: import java.awt.geom.IllegalPathStateException;
015: import java.awt.geom.PathIterator;
016: import java.awt.geom.Point2D;
017: import java.awt.geom.Rectangle2D;
018:
019: /**
020: * <p>A morphing shape is a shape which geometry is constructed from two
021: * other shapes: a start shape and an end shape.</p>
022: * <p>The morphing property of a morphing shape defines the amount of
023: * transformation applied to the start shape to turn it into the end shape.</p>
024: * <p>Both shapes must have the same winding rule.</p>
025: *
026: * @author Jim Graham
027: * @author Romain Guy <romain.guy@mac.com> (Maintainer)
028: */
029: public class Morphing2D implements Shape {
030: private double morph;
031: private Geometry startGeometry;
032: private Geometry endGeometry;
033:
034: /**
035: * <p>Creates a new morphing shape. A morphing shape can be used to turn
036: * one shape into another one. The transformation can be controlled by the
037: * morph property.</p>
038: *
039: * @param startShape the shape to morph from
040: * @param endShape the shape to morph to
041: *
042: * @throws IllegalPathStateException if the shapes do not have the same
043: * winding rule
044: * @see #getMorphing()
045: * @see #setMorphing(double)
046: */
047: public Morphing2D(Shape startShape, Shape endShape) {
048: startGeometry = new Geometry(startShape);
049: endGeometry = new Geometry(endShape);
050: if (startGeometry.getWindingRule() != endGeometry
051: .getWindingRule()) {
052: throw new IllegalPathStateException("shapes must use same "
053: + "winding rule");
054: }
055: double tvals0[] = startGeometry.getTvals();
056: double tvals1[] = endGeometry.getTvals();
057: double masterTvals[] = mergeTvals(tvals0, tvals1);
058: startGeometry.setTvals(masterTvals);
059: endGeometry.setTvals(masterTvals);
060: }
061:
062: /**
063: * <p>Returns the morphing value between the two shapes.</p>
064: *
065: * @return the morphing value between the two shapes
066: *
067: * @see #setMorphing(double)
068: */
069: public double getMorphing() {
070: return morph;
071: }
072:
073: /**
074: * <p>Sets the morphing value between the two shapes. This value controls
075: * the transformation from the start shape to the end shape. A value of 0.0
076: * is the start shap. A value of 1.0 is the end shape. A value of 0.5 is a
077: * new shape, morphed half way from the start shape to the end shape.</p>
078: * <p>The specified value should be between 0.0 and 1.0. If not, the value
079: * is clamped in the appropriate range.</p>
080: *
081: * @param morph the morphing value between the two shapes
082: *
083: * @see #getMorphing()
084: */
085: public void setMorphing(double morph) {
086: if (morph > 1) {
087: morph = 1;
088: } else if (morph >= 0) {
089: // morphing is finite, not NaN, and in range
090: } else {
091: // morph is < 0 or NaN
092: morph = 0;
093: }
094: this .morph = morph;
095: }
096:
097: private static double interp(double v0, double v1, double t) {
098: return (v0 + ((v1 - v0) * t));
099: }
100:
101: private static double[] mergeTvals(double tvals0[], double tvals1[]) {
102: int i0 = 0;
103: int i1 = 0;
104: int numtvals = 0;
105: while (i0 < tvals0.length && i1 < tvals1.length) {
106: double t0 = tvals0[i0];
107: double t1 = tvals1[i1];
108: if (t0 <= t1) {
109: i0++;
110: }
111: if (t1 <= t0) {
112: i1++;
113: }
114: numtvals++;
115: }
116: double newtvals[] = new double[numtvals];
117: i0 = 0;
118: i1 = 0;
119: numtvals = 0;
120: while (i0 < tvals0.length && i1 < tvals1.length) {
121: double t0 = tvals0[i0];
122: double t1 = tvals1[i1];
123: if (t0 <= t1) {
124: newtvals[numtvals] = t0;
125: i0++;
126: }
127: if (t1 <= t0) {
128: newtvals[numtvals] = t1;
129: i1++;
130: }
131: numtvals++;
132: }
133: return newtvals;
134: }
135:
136: /**
137: * @{inheritDoc}
138: */
139: public Rectangle getBounds() {
140: return getBounds2D().getBounds();
141: }
142:
143: /**
144: * @{inheritDoc}
145: */
146: public Rectangle2D getBounds2D() {
147: int n = startGeometry.getNumCoords();
148: double xmin, ymin, xmax, ymax;
149: xmin = xmax = interp(startGeometry.getCoord(0), endGeometry
150: .getCoord(0), morph);
151: ymin = ymax = interp(startGeometry.getCoord(1), endGeometry
152: .getCoord(1), morph);
153: for (int i = 2; i < n; i += 2) {
154: double x = interp(startGeometry.getCoord(i), endGeometry
155: .getCoord(i), morph);
156: double y = interp(startGeometry.getCoord(i + 1),
157: endGeometry.getCoord(i + 1), morph);
158: if (xmin > x) {
159: xmin = x;
160: }
161: if (ymin > y) {
162: ymin = y;
163: }
164: if (xmax < x) {
165: xmax = x;
166: }
167: if (ymax < y) {
168: ymax = y;
169: }
170: }
171: return new Rectangle2D.Double(xmin, ymin, xmax - xmin, ymax
172: - ymin);
173: }
174:
175: /**
176: * @{inheritDoc}
177: */
178: public boolean contains(double x, double y) {
179: throw new InternalError("unimplemented");
180: }
181:
182: /**
183: * @{inheritDoc}
184: */
185: public boolean contains(Point2D p) {
186: return contains(p.getX(), p.getY());
187: }
188:
189: /**
190: * @{inheritDoc}
191: */
192: public boolean intersects(double x, double y, double w, double h) {
193: throw new InternalError("unimplemented");
194: }
195:
196: /**
197: * @{inheritDoc}
198: */
199: public boolean intersects(Rectangle2D r) {
200: return intersects(r.getX(), r.getY(), r.getWidth(), r
201: .getHeight());
202: }
203:
204: /**
205: * @{inheritDoc}
206: */
207: public boolean contains(double x, double y, double w, double h) {
208: throw new InternalError("unimplemented");
209: }
210:
211: /**
212: * @{inheritDoc}
213: */
214: public boolean contains(Rectangle2D r) {
215: return contains(r.getX(), r.getY(), r.getWidth(), r.getHeight());
216: }
217:
218: /**
219: * @{inheritDoc}
220: */
221: public PathIterator getPathIterator(AffineTransform at) {
222: return new Iterator(at, startGeometry, endGeometry, morph);
223: }
224:
225: /**
226: * @{inheritDoc}
227: */
228: public PathIterator getPathIterator(AffineTransform at,
229: double flatness) {
230: return new FlatteningPathIterator(getPathIterator(at), flatness);
231: }
232:
233: private static class Geometry {
234: static final double THIRD = (1.0 / 3.0);
235: static final double MIN_LEN = 0.001;
236: double bezierCoords[];
237: int numCoords;
238: int windingrule;
239: double myTvals[];
240:
241: public Geometry(Shape s) {
242: // Multiple of 6 plus 2 more for initial moveto
243: bezierCoords = new double[20];
244: PathIterator pi = s.getPathIterator(null);
245: windingrule = pi.getWindingRule();
246: if (pi.isDone()) {
247: // We will have 1 segment and it will be all zeros
248: // It will have 8 coordinates (2 for moveto, 6 for cubic)
249: numCoords = 8;
250: }
251: double coords[] = new double[6];
252: int type = pi.currentSegment(coords);
253: pi.next();
254: if (type != PathIterator.SEG_MOVETO) {
255: throw new IllegalPathStateException(
256: "missing initial moveto");
257: }
258: double curx = bezierCoords[0] = coords[0];
259: double cury = bezierCoords[1] = coords[1];
260: double newx, newy;
261: numCoords = 2;
262: while (!pi.isDone()) {
263: if (numCoords + 6 > bezierCoords.length) {
264: // Keep array size to a multiple of 6 plus 2
265: int newsize = (numCoords - 2) * 2 + 2;
266: double newCoords[] = new double[newsize];
267: System.arraycopy(bezierCoords, 0, newCoords, 0,
268: numCoords);
269: bezierCoords = newCoords;
270: }
271: switch (pi.currentSegment(coords)) {
272: case PathIterator.SEG_MOVETO:
273: throw new InternalError(
274: "Cannot handle multiple subpaths");
275: case PathIterator.SEG_CLOSE:
276: if (curx == bezierCoords[0]
277: && cury == bezierCoords[1]) {
278: break;
279: }
280: coords[0] = bezierCoords[0];
281: coords[1] = bezierCoords[1];
282: /* NO BREAK */
283: case PathIterator.SEG_LINETO:
284: newx = coords[0];
285: newy = coords[1];
286: // A third of the way from curxy to newxy:
287: bezierCoords[numCoords++] = interp(curx, newx,
288: THIRD);
289: bezierCoords[numCoords++] = interp(cury, newy,
290: THIRD);
291: // A third of the way from newxy back to curxy:
292: bezierCoords[numCoords++] = interp(newx, curx,
293: THIRD);
294: bezierCoords[numCoords++] = interp(newy, cury,
295: THIRD);
296: bezierCoords[numCoords++] = curx = newx;
297: bezierCoords[numCoords++] = cury = newy;
298: break;
299: case PathIterator.SEG_QUADTO:
300: double ctrlx = coords[0];
301: double ctrly = coords[1];
302: newx = coords[2];
303: newy = coords[3];
304: // A third of the way from ctrlxy back to curxy:
305: bezierCoords[numCoords++] = interp(ctrlx, curx,
306: THIRD);
307: bezierCoords[numCoords++] = interp(ctrly, cury,
308: THIRD);
309: // A third of the way from ctrlxy to newxy:
310: bezierCoords[numCoords++] = interp(ctrlx, newx,
311: THIRD);
312: bezierCoords[numCoords++] = interp(ctrly, newy,
313: THIRD);
314: bezierCoords[numCoords++] = curx = newx;
315: bezierCoords[numCoords++] = cury = newy;
316: break;
317: case PathIterator.SEG_CUBICTO:
318: bezierCoords[numCoords++] = coords[0];
319: bezierCoords[numCoords++] = coords[1];
320: bezierCoords[numCoords++] = coords[2];
321: bezierCoords[numCoords++] = coords[3];
322: bezierCoords[numCoords++] = curx = coords[4];
323: bezierCoords[numCoords++] = cury = coords[5];
324: break;
325: }
326: pi.next();
327: }
328: // Add closing segment if either:
329: // - we only have initial moveto - expand it to an empty cubic
330: // - or we are not back to the starting point
331: if ((numCoords < 8) || curx != bezierCoords[0]
332: || cury != bezierCoords[1]) {
333: newx = bezierCoords[0];
334: newy = bezierCoords[1];
335: // A third of the way from curxy to newxy:
336: bezierCoords[numCoords++] = interp(curx, newx, THIRD);
337: bezierCoords[numCoords++] = interp(cury, newy, THIRD);
338: // A third of the way from newxy back to curxy:
339: bezierCoords[numCoords++] = interp(newx, curx, THIRD);
340: bezierCoords[numCoords++] = interp(newy, cury, THIRD);
341: bezierCoords[numCoords++] = newx;
342: bezierCoords[numCoords++] = newy;
343: }
344: // Now find the segment endpoint with the smallest Y coordinate
345: int minPt = 0;
346: double minX = bezierCoords[0];
347: double minY = bezierCoords[1];
348: for (int ci = 6; ci < numCoords; ci += 6) {
349: double x = bezierCoords[ci];
350: double y = bezierCoords[ci + 1];
351: if (y < minY || (y == minY && x < minX)) {
352: minPt = ci;
353: minX = x;
354: minY = y;
355: }
356: }
357: // If the smallest Y coordinate is not the first coordinate,
358: // rotate the points so that it is...
359: if (minPt > 0) {
360: // Keep in mind that first 2 coords == last 2 coords
361: double newCoords[] = new double[numCoords];
362: // Copy all coordinates from minPt to the end of the
363: // array to the beginning of the new array
364: System.arraycopy(bezierCoords, minPt, newCoords, 0,
365: numCoords - minPt);
366: // Now we do not want to copy 0,1 as they are duplicates
367: // of the last 2 coordinates which we just copied. So
368: // we start the source copy at index 2, but we still
369: // copy a full minPt coordinates which copies the two
370: // coordinates that were at minPt to the last two elements
371: // of the array, thus ensuring that thew new array starts
372: // and ends with the same pair of coordinates...
373: System.arraycopy(bezierCoords, 2, newCoords, numCoords
374: - minPt, minPt);
375: bezierCoords = newCoords;
376: }
377: /* Clockwise enforcement:
378: * - This technique is based on the formula for calculating
379: * the area of a Polygon. The standard formula is:
380: * Area(Poly) = 1/2 * sum(x[i]*y[i+1] - x[i+1]y[i])
381: * - The returned area is negative if the polygon is
382: * "mostly clockwise" and positive if the polygon is
383: * "mostly counter-clockwise".
384: * - One failure mode of the Area calculation is if the
385: * Polygon is self-intersecting. This is due to the
386: * fact that the areas on each side of the self-intersection
387: * are bounded by segments which have opposite winding
388: * direction. Thus, those areas will have opposite signs
389: * on the acccumulation of their area summations and end
390: * up canceling each other out partially.
391: * - This failure mode of the algorithm in determining the
392: * exact magnitude of the area is not actually a big problem
393: * for our needs here since we are only using the sign of
394: * the resulting area to figure out the overall winding
395: * direction of the path. If self-intersections cause
396: * different parts of the path to disagree as to the
397: * local winding direction, that is no matter as we just
398: * wait for the final answer to tell us which winding
399: * direction had greater representation. If the final
400: * result is zero then the path was equal parts clockwise
401: * and counter-clockwise and we do not care about which
402: * way we order it as either way will require half of the
403: * path to unwind and re-wind itself.
404: */
405: double area = 0;
406: // Note that first and last points are the same so we
407: // do not need to process coords[0,1] against coords[n-2,n-1]
408: curx = bezierCoords[0];
409: cury = bezierCoords[1];
410: for (int i = 2; i < numCoords; i += 2) {
411: newx = bezierCoords[i];
412: newy = bezierCoords[i + 1];
413: area += curx * newy - newx * cury;
414: curx = newx;
415: cury = newy;
416: }
417: if (area < 0) {
418: /* The area is negative so the shape was clockwise
419: * in a Euclidean sense. But, our screen coordinate
420: * systems have the origin in the upper left so they
421: * are flipped. Thus, this path "looks" ccw on the
422: * screen so we are flipping it to "look" clockwise.
423: * Note that the first and last points are the same
424: * so we do not need to swap them.
425: * (Not that it matters whether the paths end up cw
426: * or ccw in the end as long as all of them are the
427: * same, but above we called this section "Clockwise
428: * Enforcement", so we do not want to be liars. ;-)
429: */
430: // Note that [0,1] do not need to be swapped with [n-2,n-1]
431: // So first pair to swap is [2,3] and [n-4,n-3]
432: int i = 2;
433: int j = numCoords - 4;
434: while (i < j) {
435: curx = bezierCoords[i];
436: cury = bezierCoords[i + 1];
437: bezierCoords[i] = bezierCoords[j];
438: bezierCoords[i + 1] = bezierCoords[j + 1];
439: bezierCoords[j] = curx;
440: bezierCoords[j + 1] = cury;
441: i += 2;
442: j -= 2;
443: }
444: }
445: }
446:
447: public int getWindingRule() {
448: return windingrule;
449: }
450:
451: public int getNumCoords() {
452: return numCoords;
453: }
454:
455: public double getCoord(int i) {
456: return bezierCoords[i];
457: }
458:
459: public double[] getTvals() {
460: if (myTvals != null) {
461: return myTvals;
462: }
463:
464: // assert(numCoords >= 8);
465: // assert(((numCoords - 2) % 6) == 0);
466: double tvals[] = new double[(numCoords - 2) / 6 + 1];
467:
468: // First calculate total "length" of path
469: // Length of each segment is averaged between
470: // the length between the endpoints (a lower bound for a cubic)
471: // and the length of the control polygon (an upper bound)
472: double segx = bezierCoords[0];
473: double segy = bezierCoords[1];
474: double tlen = 0;
475: int ci = 2;
476: int ti = 0;
477: while (ci < numCoords) {
478: double prevx, prevy, newx, newy;
479: prevx = segx;
480: prevy = segy;
481: newx = bezierCoords[ci++];
482: newy = bezierCoords[ci++];
483: prevx -= newx;
484: prevy -= newy;
485: double len = Math.sqrt(prevx * prevx + prevy * prevy);
486: prevx = newx;
487: prevy = newy;
488: newx = bezierCoords[ci++];
489: newy = bezierCoords[ci++];
490: prevx -= newx;
491: prevy -= newy;
492: len += Math.sqrt(prevx * prevx + prevy * prevy);
493: prevx = newx;
494: prevy = newy;
495: newx = bezierCoords[ci++];
496: newy = bezierCoords[ci++];
497: prevx -= newx;
498: prevy -= newy;
499: len += Math.sqrt(prevx * prevx + prevy * prevy);
500: // len is now the total length of the control polygon
501: segx -= newx;
502: segy -= newy;
503: len += Math.sqrt(segx * segx + segy * segy);
504: // len is now sum of linear length and control polygon length
505: len /= 2;
506: // len is now average of the two lengths
507:
508: /* If the result is zero length then we will have problems
509: * below trying to do the math and bookkeeping to split
510: * the segment or pair it against the segments in the
511: * other shape. Since these lengths are just estimates
512: * to map the segments of the two shapes onto corresponding
513: * segments of "approximately the same length", we will
514: * simply fudge the length of this segment to be at least
515: * a minimum value and it will simply grow from zero or
516: * near zero length to a non-trivial size as it morphs.
517: */
518: if (len < MIN_LEN) {
519: len = MIN_LEN;
520: }
521: tlen += len;
522: tvals[ti++] = tlen;
523: segx = newx;
524: segy = newy;
525: }
526:
527: // Now set tvals for each segment to its proportional
528: // part of the length
529: double prevt = tvals[0];
530: tvals[0] = 0;
531: for (ti = 1; ti < tvals.length - 1; ti++) {
532: double nextt = tvals[ti];
533: tvals[ti] = prevt / tlen;
534: prevt = nextt;
535: }
536: tvals[ti] = 1;
537: return (myTvals = tvals);
538: }
539:
540: public void setTvals(double newTvals[]) {
541: double oldCoords[] = bezierCoords;
542: double newCoords[] = new double[2 + (newTvals.length - 1) * 6];
543: double oldTvals[] = getTvals();
544: int oldci = 0;
545: double x0, xc0, xc1, x1;
546: double y0, yc0, yc1, y1;
547: x0 = xc0 = xc1 = x1 = oldCoords[oldci++];
548: y0 = yc0 = yc1 = y1 = oldCoords[oldci++];
549: int newci = 0;
550: newCoords[newci++] = x0;
551: newCoords[newci++] = y0;
552: double t0 = 0;
553: double t1 = 0;
554: int oldti = 1;
555: int newti = 1;
556: while (newti < newTvals.length) {
557: if (t0 >= t1) {
558: x0 = x1;
559: y0 = y1;
560: xc0 = oldCoords[oldci++];
561: yc0 = oldCoords[oldci++];
562: xc1 = oldCoords[oldci++];
563: yc1 = oldCoords[oldci++];
564: x1 = oldCoords[oldci++];
565: y1 = oldCoords[oldci++];
566: t1 = oldTvals[oldti++];
567: }
568: double nt = newTvals[newti++];
569: // assert(nt > t0);
570: if (nt < t1) {
571: // Make nt proportional to [t0 => t1] range
572: double relt = (nt - t0) / (t1 - t0);
573: newCoords[newci++] = x0 = interp(x0, xc0, relt);
574: newCoords[newci++] = y0 = interp(y0, yc0, relt);
575: xc0 = interp(xc0, xc1, relt);
576: yc0 = interp(yc0, yc1, relt);
577: xc1 = interp(xc1, x1, relt);
578: yc1 = interp(yc1, y1, relt);
579: newCoords[newci++] = x0 = interp(x0, xc0, relt);
580: newCoords[newci++] = y0 = interp(y0, yc0, relt);
581: xc0 = interp(xc0, xc1, relt);
582: yc0 = interp(yc0, yc1, relt);
583: newCoords[newci++] = x0 = interp(x0, xc0, relt);
584: newCoords[newci++] = y0 = interp(y0, yc0, relt);
585: } else {
586: newCoords[newci++] = xc0;
587: newCoords[newci++] = yc0;
588: newCoords[newci++] = xc1;
589: newCoords[newci++] = yc1;
590: newCoords[newci++] = x1;
591: newCoords[newci++] = y1;
592: }
593: t0 = nt;
594: }
595: bezierCoords = newCoords;
596: numCoords = newCoords.length;
597: myTvals = newTvals;
598: }
599: }
600:
601: private static class Iterator implements PathIterator {
602: AffineTransform at;
603: Geometry g0;
604: Geometry g1;
605: double t;
606: int cindex;
607:
608: public Iterator(AffineTransform at, Geometry g0, Geometry g1,
609: double t) {
610: this .at = at;
611: this .g0 = g0;
612: this .g1 = g1;
613: this .t = t;
614: }
615:
616: /**
617: * @{inheritDoc}
618: */
619: public int getWindingRule() {
620: return g0.getWindingRule();
621: }
622:
623: /**
624: * @{inheritDoc}
625: */
626: public boolean isDone() {
627: return (cindex > g0.getNumCoords());
628: }
629:
630: /**
631: * @{inheritDoc}
632: */
633: public void next() {
634: if (cindex == 0) {
635: cindex = 2;
636: } else {
637: cindex += 6;
638: }
639: }
640:
641: double dcoords[];
642:
643: /**
644: * @{inheritDoc}
645: */
646: public int currentSegment(float[] coords) {
647: if (dcoords == null) {
648: dcoords = new double[6];
649: }
650: int type = currentSegment(dcoords);
651: if (type != SEG_CLOSE) {
652: coords[0] = (float) dcoords[0];
653: coords[1] = (float) dcoords[1];
654: if (type != SEG_MOVETO) {
655: coords[2] = (float) dcoords[2];
656: coords[3] = (float) dcoords[3];
657: coords[4] = (float) dcoords[4];
658: coords[5] = (float) dcoords[5];
659: }
660: }
661: return type;
662: }
663:
664: /**
665: * @{inheritDoc}
666: */
667: public int currentSegment(double[] coords) {
668: int type;
669: int n;
670: if (cindex == 0) {
671: type = SEG_MOVETO;
672: n = 2;
673: } else if (cindex >= g0.getNumCoords()) {
674: type = SEG_CLOSE;
675: n = 0;
676: } else {
677: type = SEG_CUBICTO;
678: n = 6;
679: }
680: if (n > 0) {
681: for (int i = 0; i < n; i++) {
682: coords[i] = interp(g0.getCoord(cindex + i), g1
683: .getCoord(cindex + i), t);
684: }
685: if (at != null) {
686: at.transform(coords, 0, coords, 0, n / 2);
687: }
688: }
689: return type;
690: }
691: }
692: }
|