001/* 002 * $Id: Morphing2D.java 3863 2010-10-26 02:53:32Z kschaefe $ 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 */ 021package org.jdesktop.swingx.geom; 022 023import java.awt.Rectangle; 024import java.awt.Shape; 025import java.awt.geom.AffineTransform; 026import java.awt.geom.FlatteningPathIterator; 027import java.awt.geom.IllegalPathStateException; 028import java.awt.geom.PathIterator; 029import java.awt.geom.Point2D; 030import 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 */ 042public 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 @Override 152 public Rectangle getBounds() { 153 return getBounds2D().getBounds(); 154 } 155 156 /** 157 * {@inheritDoc} 158 */ 159 @Override 160 public Rectangle2D getBounds2D() { 161 int n = startGeometry.getNumCoords(); 162 double xmin, ymin, xmax, ymax; 163 xmin = xmax = interp(startGeometry.getCoord(0), endGeometry.getCoord(0), 164 morph); 165 ymin = ymax = interp(startGeometry.getCoord(1), endGeometry.getCoord(1), 166 morph); 167 for (int i = 2; i < n; i += 2) { 168 double x = interp(startGeometry.getCoord(i), 169 endGeometry.getCoord(i), morph); 170 double y = interp(startGeometry.getCoord(i + 1), 171 endGeometry.getCoord(i + 1), morph); 172 if (xmin > x) { 173 xmin = x; 174 } 175 if (ymin > y) { 176 ymin = y; 177 } 178 if (xmax < x) { 179 xmax = x; 180 } 181 if (ymax < y) { 182 ymax = y; 183 } 184 } 185 return new Rectangle2D.Double(xmin, ymin, xmax - xmin, ymax - ymin); 186 } 187 188 /** 189 * {@inheritDoc} 190 */ 191 @Override 192 public boolean contains(double x, double y) { 193 throw new InternalError("unimplemented"); 194 } 195 196 /** 197 * {@inheritDoc} 198 */ 199 @Override 200 public boolean contains(Point2D p) { 201 return contains(p.getX(), p.getY()); 202 } 203 204 /** 205 * {@inheritDoc} 206 */ 207 @Override 208 public boolean intersects(double x, double y, double w, double h) { 209 throw new InternalError("unimplemented"); 210 } 211 212 /** 213 * {@inheritDoc} 214 */ 215 @Override 216 public boolean intersects(Rectangle2D r) { 217 return intersects(r.getX(), r.getY(), r.getWidth(), r.getHeight()); 218 } 219 220 /** 221 * {@inheritDoc} 222 */ 223 @Override 224 public boolean contains(double x, double y, double w, double h) { 225 throw new InternalError("unimplemented"); 226 } 227 228 /** 229 * {@inheritDoc} 230 */ 231 @Override 232 public boolean contains(Rectangle2D r) { 233 return contains(r.getX(), r.getY(), r.getWidth(), r.getHeight()); 234 } 235 236 /** 237 * {@inheritDoc} 238 */ 239 @Override 240 public PathIterator getPathIterator(AffineTransform at) { 241 return new Iterator(at, startGeometry, endGeometry, morph); 242 } 243 244 /** 245 * {@inheritDoc} 246 */ 247 @Override 248 public PathIterator getPathIterator(AffineTransform at, double flatness) { 249 return new FlatteningPathIterator(getPathIterator(at), flatness); 250 } 251 252 private static class Geometry { 253 static final double THIRD = (1.0 / 3.0); 254 static final double MIN_LEN = 0.001; 255 double bezierCoords[]; 256 int numCoords; 257 int windingrule; 258 double myTvals[]; 259 260 public Geometry(Shape s) { 261 // Multiple of 6 plus 2 more for initial moveto 262 bezierCoords = new double[20]; 263 PathIterator pi = s.getPathIterator(null); 264 windingrule = pi.getWindingRule(); 265 if (pi.isDone()) { 266 // We will have 1 segment and it will be all zeros 267 // It will have 8 coordinates (2 for moveto, 6 for cubic) 268 numCoords = 8; 269 } 270 double coords[] = new double[6]; 271 int type = pi.currentSegment(coords); 272 pi.next(); 273 if (type != PathIterator.SEG_MOVETO) { 274 throw new IllegalPathStateException("missing initial moveto"); 275 } 276 double curx = bezierCoords[0] = coords[0]; 277 double cury = bezierCoords[1] = coords[1]; 278 double newx, newy; 279 numCoords = 2; 280 while (!pi.isDone()) { 281 if (numCoords + 6 > bezierCoords.length) { 282 // Keep array size to a multiple of 6 plus 2 283 int newsize = (numCoords - 2) * 2 + 2; 284 double newCoords[] = new double[newsize]; 285 System.arraycopy(bezierCoords, 0, newCoords, 0, numCoords); 286 bezierCoords = newCoords; 287 } 288 switch (pi.currentSegment(coords)) { 289 case PathIterator.SEG_MOVETO: 290 throw new InternalError( 291 "Cannot handle multiple subpaths"); 292 case PathIterator.SEG_CLOSE: 293 if (curx == bezierCoords[0] && cury == bezierCoords[1]) 294 { 295 break; 296 } 297 coords[0] = bezierCoords[0]; 298 coords[1] = bezierCoords[1]; 299 /* NO BREAK */ 300 case PathIterator.SEG_LINETO: 301 newx = coords[0]; 302 newy = coords[1]; 303 // A third of the way from curxy to newxy: 304 bezierCoords[numCoords++] = interp(curx, newx, THIRD); 305 bezierCoords[numCoords++] = interp(cury, newy, THIRD); 306 // A third of the way from newxy back to curxy: 307 bezierCoords[numCoords++] = interp(newx, curx, THIRD); 308 bezierCoords[numCoords++] = interp(newy, cury, THIRD); 309 bezierCoords[numCoords++] = curx = newx; 310 bezierCoords[numCoords++] = cury = newy; 311 break; 312 case PathIterator.SEG_QUADTO: 313 double ctrlx = coords[0]; 314 double ctrly = coords[1]; 315 newx = coords[2]; 316 newy = coords[3]; 317 // A third of the way from ctrlxy back to curxy: 318 bezierCoords[numCoords++] = interp(ctrlx, curx, THIRD); 319 bezierCoords[numCoords++] = interp(ctrly, cury, THIRD); 320 // A third of the way from ctrlxy to newxy: 321 bezierCoords[numCoords++] = interp(ctrlx, newx, THIRD); 322 bezierCoords[numCoords++] = interp(ctrly, newy, THIRD); 323 bezierCoords[numCoords++] = curx = newx; 324 bezierCoords[numCoords++] = cury = newy; 325 break; 326 case PathIterator.SEG_CUBICTO: 327 bezierCoords[numCoords++] = coords[0]; 328 bezierCoords[numCoords++] = coords[1]; 329 bezierCoords[numCoords++] = coords[2]; 330 bezierCoords[numCoords++] = coords[3]; 331 bezierCoords[numCoords++] = curx = coords[4]; 332 bezierCoords[numCoords++] = cury = coords[5]; 333 break; 334 } 335 pi.next(); 336 } 337 // Add closing segment if either: 338 // - we only have initial moveto - expand it to an empty cubic 339 // - or we are not back to the starting point 340 if ((numCoords < 8) || 341 curx != bezierCoords[0] || 342 cury != bezierCoords[1]) { 343 newx = bezierCoords[0]; 344 newy = bezierCoords[1]; 345 // A third of the way from curxy to newxy: 346 bezierCoords[numCoords++] = interp(curx, newx, THIRD); 347 bezierCoords[numCoords++] = interp(cury, newy, THIRD); 348 // A third of the way from newxy back to curxy: 349 bezierCoords[numCoords++] = interp(newx, curx, THIRD); 350 bezierCoords[numCoords++] = interp(newy, cury, THIRD); 351 bezierCoords[numCoords++] = newx; 352 bezierCoords[numCoords++] = newy; 353 } 354 // Now find the segment endpoint with the smallest Y coordinate 355 int minPt = 0; 356 double minX = bezierCoords[0]; 357 double minY = bezierCoords[1]; 358 for (int ci = 6; ci < numCoords; ci += 6) { 359 double x = bezierCoords[ci]; 360 double y = bezierCoords[ci + 1]; 361 if (y < minY || (y == minY && x < minX)) { 362 minPt = ci; 363 minX = x; 364 minY = y; 365 } 366 } 367 // If the smallest Y coordinate is not the first coordinate, 368 // rotate the points so that it is... 369 if (minPt > 0) { 370 // Keep in mind that first 2 coords == last 2 coords 371 double newCoords[] = new double[numCoords]; 372 // Copy all coordinates from minPt to the end of the 373 // array to the beginning of the new array 374 System.arraycopy(bezierCoords, minPt, 375 newCoords, 0, 376 numCoords - minPt); 377 // Now we do not want to copy 0,1 as they are duplicates 378 // of the last 2 coordinates which we just copied. So 379 // we start the source copy at index 2, but we still 380 // copy a full minPt coordinates which copies the two 381 // coordinates that were at minPt to the last two elements 382 // of the array, thus ensuring that thew new array starts 383 // and ends with the same pair of coordinates... 384 System.arraycopy(bezierCoords, 2, 385 newCoords, numCoords - minPt, 386 minPt); 387 bezierCoords = newCoords; 388 } 389 /* Clockwise enforcement: 390 * - This technique is based on the formula for calculating 391 * the area of a Polygon. The standard formula is: 392 * Area(Poly) = 1/2 * sum(x[i]*y[i+1] - x[i+1]y[i]) 393 * - The returned area is negative if the polygon is 394 * "mostly clockwise" and positive if the polygon is 395 * "mostly counter-clockwise". 396 * - One failure mode of the Area calculation is if the 397 * Polygon is self-intersecting. This is due to the 398 * fact that the areas on each side of the self-intersection 399 * are bounded by segments which have opposite winding 400 * direction. Thus, those areas will have opposite signs 401 * on the accumulation of their area summations and end 402 * up canceling each other out partially. 403 * - This failure mode of the algorithm in determining the 404 * exact magnitude of the area is not actually a big problem 405 * for our needs here since we are only using the sign of 406 * the resulting area to figure out the overall winding 407 * direction of the path. If self-intersections cause 408 * different parts of the path to disagree as to the 409 * local winding direction, that is no matter as we just 410 * wait for the final answer to tell us which winding 411 * direction had greater representation. If the final 412 * result is zero then the path was equal parts clockwise 413 * and counter-clockwise and we do not care about which 414 * way we order it as either way will require half of the 415 * path to unwind and re-wind itself. 416 */ 417 double area = 0; 418 // Note that first and last points are the same so we 419 // do not need to process coords[0,1] against coords[n-2,n-1] 420 curx = bezierCoords[0]; 421 cury = bezierCoords[1]; 422 for (int i = 2; i < numCoords; i += 2) { 423 newx = bezierCoords[i]; 424 newy = bezierCoords[i + 1]; 425 area += curx * newy - newx * cury; 426 curx = newx; 427 cury = newy; 428 } 429 if (area < 0) { 430 /* The area is negative so the shape was clockwise 431 * in a Euclidean sense. But, our screen coordinate 432 * systems have the origin in the upper left so they 433 * are flipped. Thus, this path "looks" ccw on the 434 * screen so we are flipping it to "look" clockwise. 435 * Note that the first and last points are the same 436 * so we do not need to swap them. 437 * (Not that it matters whether the paths end up cw 438 * or ccw in the end as long as all of them are the 439 * same, but above we called this section "Clockwise 440 * Enforcement", so we do not want to be liars. ;-) 441 */ 442 // Note that [0,1] do not need to be swapped with [n-2,n-1] 443 // So first pair to swap is [2,3] and [n-4,n-3] 444 int i = 2; 445 int j = numCoords - 4; 446 while (i < j) { 447 curx = bezierCoords[i]; 448 cury = bezierCoords[i + 1]; 449 bezierCoords[i] = bezierCoords[j]; 450 bezierCoords[i + 1] = bezierCoords[j + 1]; 451 bezierCoords[j] = curx; 452 bezierCoords[j + 1] = cury; 453 i += 2; 454 j -= 2; 455 } 456 } 457 } 458 459 public int getWindingRule() { 460 return windingrule; 461 } 462 463 public int getNumCoords() { 464 return numCoords; 465 } 466 467 public double getCoord(int i) { 468 return bezierCoords[i]; 469 } 470 471 public double[] getTvals() { 472 if (myTvals != null) { 473 return myTvals; 474 } 475 476 // assert(numCoords >= 8); 477 // assert(((numCoords - 2) % 6) == 0); 478 double tvals[] = new double[(numCoords - 2) / 6 + 1]; 479 480 // First calculate total "length" of path 481 // Length of each segment is averaged between 482 // the length between the endpoints (a lower bound for a cubic) 483 // and the length of the control polygon (an upper bound) 484 double segx = bezierCoords[0]; 485 double segy = bezierCoords[1]; 486 double tlen = 0; 487 int ci = 2; 488 int ti = 0; 489 while (ci < numCoords) { 490 double prevx, prevy, newx, newy; 491 prevx = segx; 492 prevy = segy; 493 newx = bezierCoords[ci++]; 494 newy = bezierCoords[ci++]; 495 prevx -= newx; 496 prevy -= newy; 497 double len = Math.sqrt(prevx * prevx + prevy * prevy); 498 prevx = newx; 499 prevy = newy; 500 newx = bezierCoords[ci++]; 501 newy = bezierCoords[ci++]; 502 prevx -= newx; 503 prevy -= newy; 504 len += Math.sqrt(prevx * prevx + prevy * prevy); 505 prevx = newx; 506 prevy = newy; 507 newx = bezierCoords[ci++]; 508 newy = bezierCoords[ci++]; 509 prevx -= newx; 510 prevy -= newy; 511 len += Math.sqrt(prevx * prevx + prevy * prevy); 512 // len is now the total length of the control polygon 513 segx -= newx; 514 segy -= newy; 515 len += Math.sqrt(segx * segx + segy * segy); 516 // len is now sum of linear length and control polygon length 517 len /= 2; 518 // len is now average of the two lengths 519 520 /* If the result is zero length then we will have problems 521 * below trying to do the math and bookkeeping to split 522 * the segment or pair it against the segments in the 523 * other shape. Since these lengths are just estimates 524 * to map the segments of the two shapes onto corresponding 525 * segments of "approximately the same length", we will 526 * simply fudge the length of this segment to be at least 527 * a minimum value and it will simply grow from zero or 528 * near zero length to a non-trivial size as it morphs. 529 */ 530 if (len < MIN_LEN) { 531 len = MIN_LEN; 532 } 533 tlen += len; 534 tvals[ti++] = tlen; 535 segx = newx; 536 segy = newy; 537 } 538 539 // Now set tvals for each segment to its proportional 540 // part of the length 541 double prevt = tvals[0]; 542 tvals[0] = 0; 543 for (ti = 1; ti < tvals.length - 1; ti++) { 544 double nextt = tvals[ti]; 545 tvals[ti] = prevt / tlen; 546 prevt = nextt; 547 } 548 tvals[ti] = 1; 549 return (myTvals = tvals); 550 } 551 552 public void setTvals(double newTvals[]) { 553 double oldCoords[] = bezierCoords; 554 double newCoords[] = new double[2 + (newTvals.length - 1) * 6]; 555 double oldTvals[] = getTvals(); 556 int oldci = 0; 557 double x0, xc0, xc1, x1; 558 double y0, yc0, yc1, y1; 559 x0 = xc0 = xc1 = x1 = oldCoords[oldci++]; 560 y0 = yc0 = yc1 = y1 = oldCoords[oldci++]; 561 int newci = 0; 562 newCoords[newci++] = x0; 563 newCoords[newci++] = y0; 564 double t0 = 0; 565 double t1 = 0; 566 int oldti = 1; 567 int newti = 1; 568 while (newti < newTvals.length) { 569 if (t0 >= t1) { 570 x0 = x1; 571 y0 = y1; 572 xc0 = oldCoords[oldci++]; 573 yc0 = oldCoords[oldci++]; 574 xc1 = oldCoords[oldci++]; 575 yc1 = oldCoords[oldci++]; 576 x1 = oldCoords[oldci++]; 577 y1 = oldCoords[oldci++]; 578 t1 = oldTvals[oldti++]; 579 } 580 double nt = newTvals[newti++]; 581 // assert(nt > t0); 582 if (nt < t1) { 583 // Make nt proportional to [t0 => t1] range 584 double relt = (nt - t0) / (t1 - t0); 585 newCoords[newci++] = x0 = interp(x0, xc0, relt); 586 newCoords[newci++] = y0 = interp(y0, yc0, relt); 587 xc0 = interp(xc0, xc1, relt); 588 yc0 = interp(yc0, yc1, relt); 589 xc1 = interp(xc1, x1, relt); 590 yc1 = interp(yc1, y1, relt); 591 newCoords[newci++] = x0 = interp(x0, xc0, relt); 592 newCoords[newci++] = y0 = interp(y0, yc0, relt); 593 xc0 = interp(xc0, xc1, relt); 594 yc0 = interp(yc0, yc1, relt); 595 newCoords[newci++] = x0 = interp(x0, xc0, relt); 596 newCoords[newci++] = y0 = interp(y0, yc0, relt); 597 } else { 598 newCoords[newci++] = xc0; 599 newCoords[newci++] = yc0; 600 newCoords[newci++] = xc1; 601 newCoords[newci++] = yc1; 602 newCoords[newci++] = x1; 603 newCoords[newci++] = y1; 604 } 605 t0 = nt; 606 } 607 bezierCoords = newCoords; 608 numCoords = newCoords.length; 609 myTvals = newTvals; 610 } 611 } 612 613 private static class Iterator implements PathIterator { 614 AffineTransform at; 615 Geometry g0; 616 Geometry g1; 617 double t; 618 int cindex; 619 620 public Iterator(AffineTransform at, 621 Geometry g0, Geometry g1, 622 double t) { 623 this.at = at; 624 this.g0 = g0; 625 this.g1 = g1; 626 this.t = t; 627 } 628 629 /** 630 * {@inheritDoc} 631 */ 632 @Override 633 public int getWindingRule() { 634 return g0.getWindingRule(); 635 } 636 637 /** 638 * {@inheritDoc} 639 */ 640 @Override 641 public boolean isDone() { 642 return (cindex > g0.getNumCoords()); 643 } 644 645 /** 646 * {@inheritDoc} 647 */ 648 @Override 649 public void next() { 650 if (cindex == 0) { 651 cindex = 2; 652 } else { 653 cindex += 6; 654 } 655 } 656 657 double dcoords[]; 658 659 /** 660 * {@inheritDoc} 661 */ 662 @Override 663 public int currentSegment(float[] coords) { 664 if (dcoords == null) { 665 dcoords = new double[6]; 666 } 667 int type = currentSegment(dcoords); 668 if (type != SEG_CLOSE) { 669 coords[0] = (float) dcoords[0]; 670 coords[1] = (float) dcoords[1]; 671 if (type != SEG_MOVETO) { 672 coords[2] = (float) dcoords[2]; 673 coords[3] = (float) dcoords[3]; 674 coords[4] = (float) dcoords[4]; 675 coords[5] = (float) dcoords[5]; 676 } 677 } 678 return type; 679 } 680 681 /** 682 * {@inheritDoc} 683 */ 684 @Override 685 public int currentSegment(double[] coords) { 686 int type; 687 int n; 688 if (cindex == 0) { 689 type = SEG_MOVETO; 690 n = 2; 691 } else if (cindex >= g0.getNumCoords()) { 692 type = SEG_CLOSE; 693 n = 0; 694 } else { 695 type = SEG_CUBICTO; 696 n = 6; 697 } 698 if (n > 0) { 699 for (int i = 0; i < n; i++) { 700 coords[i] = interp(g0.getCoord(cindex + i), 701 g1.getCoord(cindex + i), 702 t); 703 } 704 if (at != null) { 705 at.transform(coords, 0, coords, 0, n / 2); 706 } 707 } 708 return type; 709 } 710 } 711}