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