Source for java.awt.geom.FlatteningPathIterator

   1: /* FlatteningPathIterator.java -- Approximates curves by straight lines
   2:    Copyright (C) 2003 Free Software Foundation
   3: 
   4: This file is part of GNU Classpath.
   5: 
   6: GNU Classpath is free software; you can redistribute it and/or modify
   7: it under the terms of the GNU General Public License as published by
   8: the Free Software Foundation; either version 2, or (at your option)
   9: any later version.
  10: 
  11: GNU Classpath is distributed in the hope that it will be useful, but
  12: WITHOUT ANY WARRANTY; without even the implied warranty of
  13: MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  14: General Public License for more details.
  15: 
  16: You should have received a copy of the GNU General Public License
  17: along with GNU Classpath; see the file COPYING.  If not, write to the
  18: Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA
  19: 02110-1301 USA.
  20: 
  21: Linking this library statically or dynamically with other modules is
  22: making a combined work based on this library.  Thus, the terms and
  23: conditions of the GNU General Public License cover the whole
  24: combination.
  25: 
  26: As a special exception, the copyright holders of this library give you
  27: permission to link this library with independent modules to produce an
  28: executable, regardless of the license terms of these independent
  29: modules, and to copy and distribute the resulting executable under
  30: terms of your choice, provided that you also meet, for each linked
  31: independent module, the terms and conditions of the license of that
  32: module.  An independent module is a module which is not derived from
  33: or based on this library.  If you modify this library, you may extend
  34: this exception to your version of the library, but you are not
  35: obligated to do so.  If you do not wish to do so, delete this
  36: exception statement from your version. */
  37: 
  38: 
  39: package java.awt.geom;
  40: 
  41: import java.util.NoSuchElementException;
  42: 
  43: 
  44: /**
  45:  * A PathIterator for approximating curved path segments by sequences
  46:  * of straight lines. Instances of this class will only return
  47:  * segments of type {@link PathIterator#SEG_MOVETO}, {@link
  48:  * PathIterator#SEG_LINETO}, and {@link PathIterator#SEG_CLOSE}.
  49:  *
  50:  * <p>The accuracy of the approximation is determined by two
  51:  * parameters:
  52:  *
  53:  * <ul><li>The <i>flatness</i> is a threshold value for deciding when
  54:  * a curved segment is consided flat enough for being approximated by
  55:  * a single straight line. Flatness is defined as the maximal distance
  56:  * of a curve control point to the straight line that connects the
  57:  * curve start and end. A lower flatness threshold means a closer
  58:  * approximation.  See {@link QuadCurve2D#getFlatness()} and {@link
  59:  * CubicCurve2D#getFlatness()} for drawings which illustrate the
  60:  * meaning of flatness.</li>
  61:  *
  62:  * <li>The <i>recursion limit</i> imposes an upper bound for how often
  63:  * a curved segment gets subdivided. A limit of <i>n</i> means that
  64:  * for each individual quadratic and cubic B&#xe9;zier spline
  65:  * segment, at most 2<sup><small><i>n</i></small></sup> {@link
  66:  * PathIterator#SEG_LINETO} segments will be created.</li></ul>
  67:  *
  68:  * <p><b>Memory Efficiency:</b> The memory consumption grows linearly
  69:  * with the recursion limit. Neither the <i>flatness</i> parameter nor
  70:  * the number of segments in the flattened path will affect the memory
  71:  * consumption.
  72:  *
  73:  * <p><b>Thread Safety:</b> Multiple threads can safely work on
  74:  * separate instances of this class. However, multiple threads should
  75:  * not concurrently access the same instance, as no synchronization is
  76:  * performed.
  77:  *
  78:  * @see <a href="doc-files/FlatteningPathIterator-1.html"
  79:  * >Implementation Note</a>
  80:  *
  81:  * @author Sascha Brawer (brawer@dandelis.ch)
  82:  *
  83:  * @since 1.2
  84:  */
  85: public class FlatteningPathIterator
  86:   implements PathIterator
  87: {
  88:   /**
  89:    * The PathIterator whose curved segments are being approximated.
  90:    */
  91:   private final PathIterator srcIter;
  92: 
  93: 
  94:   /**
  95:    * The square of the flatness threshold value, which determines when
  96:    * a curve segment is considered flat enough that no further
  97:    * subdivision is needed.
  98:    *
  99:    * <p>Calculating flatness actually produces the squared flatness
 100:    * value. To avoid the relatively expensive calculation of a square
 101:    * root for each curve segment, we perform all flatness comparisons
 102:    * on squared values.
 103:    *
 104:    * @see QuadCurve2D#getFlatnessSq()
 105:    * @see CubicCurve2D#getFlatnessSq()
 106:    */
 107:   private final double flatnessSq;
 108: 
 109: 
 110:   /**
 111:    * The maximal number of subdivions that are performed to
 112:    * approximate a quadratic or cubic curve segment.
 113:    */
 114:   private final int recursionLimit;
 115: 
 116: 
 117:   /**
 118:    * A stack for holding the coordinates of subdivided segments.
 119:    *
 120:    * @see <a href="doc-files/FlatteningPathIterator-1.html"
 121:    * >Implementation Note</a>
 122:    */
 123:   private double[] stack;
 124: 
 125: 
 126:   /**
 127:    * The current stack size.
 128:    *
 129:    * @see <a href="doc-files/FlatteningPathIterator-1.html"
 130:    * >Implementation Note</a>
 131:    */
 132:   private int stackSize;
 133: 
 134: 
 135:   /**
 136:    * The number of recursions that were performed to arrive at
 137:    * a segment on the stack.
 138:    *
 139:    * @see <a href="doc-files/FlatteningPathIterator-1.html"
 140:    * >Implementation Note</a>
 141:    */
 142:   private int[] recLevel;
 143: 
 144:   
 145:   
 146:   private final double[] scratch = new double[6];
 147: 
 148: 
 149:   /**
 150:    * The segment type of the last segment that was returned by
 151:    * the source iterator.
 152:    */
 153:   private int srcSegType;
 154: 
 155: 
 156:   /**
 157:    * The current <i>x</i> position of the source iterator.
 158:    */
 159:   private double srcPosX;
 160: 
 161: 
 162:   /**
 163:    * The current <i>y</i> position of the source iterator.
 164:    */
 165:   private double srcPosY;
 166: 
 167: 
 168:   /**
 169:    * A flag that indicates when this path iterator has finished its
 170:    * iteration over path segments.
 171:    */
 172:   private boolean done;
 173: 
 174: 
 175:   /**
 176:    * Constructs a new PathIterator for approximating an input
 177:    * PathIterator with straight lines. The approximation works by
 178:    * recursive subdivisons, until the specified flatness threshold is
 179:    * not exceeded.
 180:    *
 181:    * <p>There will not be more than 10 nested recursion steps, which
 182:    * means that a single <code>SEG_QUADTO</code> or
 183:    * <code>SEG_CUBICTO</code> segment is approximated by at most
 184:    * 2<sup><small>10</small></sup> = 1024 straight lines.
 185:    */
 186:   public FlatteningPathIterator(PathIterator src, double flatness)
 187:   {
 188:     this(src, flatness, 10);
 189:   }
 190: 
 191: 
 192:   /**
 193:    * Constructs a new PathIterator for approximating an input
 194:    * PathIterator with straight lines. The approximation works by
 195:    * recursive subdivisons, until the specified flatness threshold is
 196:    * not exceeded.  Additionally, the number of recursions is also
 197:    * bound by the specified recursion limit.
 198:    */
 199:   public FlatteningPathIterator(PathIterator src, double flatness,
 200:                                 int limit)
 201:   {
 202:     if (flatness < 0 || limit < 0)
 203:       throw new IllegalArgumentException();
 204: 
 205:     srcIter = src;
 206:     flatnessSq = flatness * flatness;
 207:     recursionLimit = limit;
 208:     fetchSegment();
 209:   }
 210: 
 211: 
 212:   /**
 213:    * Returns the maximally acceptable flatness.
 214:    *
 215:    * @see QuadCurve2D#getFlatness()
 216:    * @see CubicCurve2D#getFlatness()
 217:    */
 218:   public double getFlatness()
 219:   {
 220:     return Math.sqrt(flatnessSq);
 221:   }
 222: 
 223: 
 224:   /**
 225:    * Returns the maximum number of recursive curve subdivisions.
 226:    */
 227:   public int getRecursionLimit()
 228:   {
 229:     return recursionLimit;
 230:   }
 231: 
 232: 
 233:   // Documentation will be copied from PathIterator.
 234:   public int getWindingRule()
 235:   {
 236:     return srcIter.getWindingRule();
 237:   }
 238: 
 239: 
 240:   // Documentation will be copied from PathIterator.
 241:   public boolean isDone()
 242:   {
 243:     return done;
 244:   }
 245: 
 246: 
 247:   // Documentation will be copied from PathIterator.
 248:   public void next()
 249:   {
 250:     if (stackSize > 0)
 251:     {
 252:       --stackSize;
 253:       if (stackSize > 0)
 254:       {
 255:         switch (srcSegType)
 256:         {
 257:         case PathIterator.SEG_QUADTO:
 258:           subdivideQuadratic();
 259:           return;
 260: 
 261:         case PathIterator.SEG_CUBICTO:
 262:           subdivideCubic();
 263:           return;
 264: 
 265:         default:
 266:           throw new IllegalStateException();
 267:         }
 268:       }
 269:     }
 270: 
 271:     srcIter.next();
 272:     fetchSegment();
 273:   }
 274: 
 275: 
 276:   // Documentation will be copied from PathIterator.
 277:   public int currentSegment(double[] coords)
 278:   {
 279:     if (done)
 280:       throw new NoSuchElementException();
 281: 
 282:     switch (srcSegType)
 283:     {
 284:     case PathIterator.SEG_CLOSE:
 285:       return srcSegType;
 286: 
 287:     case PathIterator.SEG_MOVETO:
 288:     case PathIterator.SEG_LINETO:
 289:       coords[0] = srcPosX;
 290:       coords[1] = srcPosY;
 291:       return srcSegType;
 292: 
 293:     case PathIterator.SEG_QUADTO:
 294:       if (stackSize == 0)
 295:       {
 296:         coords[0] = srcPosX;
 297:         coords[1] = srcPosY;
 298:       }
 299:       else
 300:       {
 301:         int sp = stack.length - 4 * stackSize;
 302:         coords[0] = stack[sp + 2];
 303:         coords[1] = stack[sp + 3];
 304:       }
 305:       return PathIterator.SEG_LINETO;
 306: 
 307:     case PathIterator.SEG_CUBICTO:
 308:       if (stackSize == 0)
 309:       {
 310:         coords[0] = srcPosX;
 311:         coords[1] = srcPosY;
 312:       }
 313:       else
 314:       {
 315:         int sp = stack.length - 6 * stackSize;
 316:         coords[0] = stack[sp + 4];
 317:         coords[1] = stack[sp + 5];
 318:       }
 319:       return PathIterator.SEG_LINETO;
 320:     }
 321: 
 322:     throw new IllegalStateException();
 323:   }
 324: 
 325: 
 326:   // Documentation will be copied from PathIterator.
 327:   public int currentSegment(float[] coords)
 328:   {
 329:     if (done)
 330:       throw new NoSuchElementException();
 331: 
 332:     switch (srcSegType)
 333:     {
 334:     case PathIterator.SEG_CLOSE:
 335:       return srcSegType;
 336: 
 337:     case PathIterator.SEG_MOVETO:
 338:     case PathIterator.SEG_LINETO:
 339:       coords[0] = (float) srcPosX;
 340:       coords[1] = (float) srcPosY;
 341:       return srcSegType;
 342: 
 343:     case PathIterator.SEG_QUADTO:
 344:       if (stackSize == 0)
 345:       {
 346:         coords[0] = (float) srcPosX;
 347:         coords[1] = (float) srcPosY;
 348:       }
 349:       else
 350:       {
 351:         int sp = stack.length - 4 * stackSize;
 352:         coords[0] = (float) stack[sp + 2];
 353:         coords[1] = (float) stack[sp + 3];
 354:       }
 355:       return PathIterator.SEG_LINETO;
 356: 
 357:     case PathIterator.SEG_CUBICTO:
 358:       if (stackSize == 0)
 359:       {
 360:         coords[0] = (float) srcPosX;
 361:         coords[1] = (float) srcPosY;
 362:       }
 363:       else
 364:       {
 365:         int sp = stack.length - 6 * stackSize;
 366:         coords[0] = (float) stack[sp + 4];
 367:         coords[1] = (float) stack[sp + 5];
 368:       }
 369:       return PathIterator.SEG_LINETO;
 370:     }
 371: 
 372:     throw new IllegalStateException();
 373:   }
 374: 
 375: 
 376:   /**
 377:    * Fetches the next segment from the source iterator.
 378:    */
 379:   private void fetchSegment()
 380:   {
 381:     int sp;
 382: 
 383:     if (srcIter.isDone())
 384:     {
 385:       done = true;
 386:       return;
 387:     }
 388: 
 389:     srcSegType = srcIter.currentSegment(scratch);
 390:     
 391:     switch (srcSegType)
 392:     {
 393:     case PathIterator.SEG_CLOSE:
 394:       return;
 395: 
 396:     case PathIterator.SEG_MOVETO:
 397:     case PathIterator.SEG_LINETO:
 398:       srcPosX = scratch[0];
 399:       srcPosY = scratch[1];
 400:       return;
 401: 
 402:     case PathIterator.SEG_QUADTO:
 403:       if (recursionLimit == 0)
 404:       {
 405:         srcPosX = scratch[2];
 406:         srcPosY = scratch[3];
 407:         stackSize = 0;
 408:         return;
 409:       }
 410:       sp = 4 * recursionLimit;
 411:       stackSize = 1;
 412:       if (stack == null)
 413:       {
 414:         stack = new double[sp + /* 4 + 2 */ 6];
 415:         recLevel = new int[recursionLimit + 1];
 416:       }
 417:       recLevel[0] = 0;
 418:       stack[sp] = srcPosX;                  // P1.x
 419:       stack[sp + 1] = srcPosY;              // P1.y
 420:       stack[sp + 2] = scratch[0];           // C.x
 421:       stack[sp + 3] = scratch[1];           // C.y
 422:       srcPosX = stack[sp + 4] = scratch[2]; // P2.x
 423:       srcPosY = stack[sp + 5] = scratch[3]; // P2.y
 424:       subdivideQuadratic();
 425:       break;
 426: 
 427:     case PathIterator.SEG_CUBICTO:
 428:       if (recursionLimit == 0)
 429:       {
 430:         srcPosX = scratch[4];
 431:         srcPosY = scratch[5];
 432:         stackSize = 0;
 433:         return;
 434:       }
 435:       sp = 6 * recursionLimit;
 436:       stackSize = 1;
 437:       if ((stack == null) || (stack.length < sp + 8))
 438:       {
 439:         stack = new double[sp + /* 6 + 2 */ 8];
 440:         recLevel = new int[recursionLimit + 1];
 441:       }
 442:       recLevel[0] = 0;
 443:       stack[sp] = srcPosX;                  // P1.x
 444:       stack[sp + 1] = srcPosY;              // P1.y
 445:       stack[sp + 2] = scratch[0];           // C1.x
 446:       stack[sp + 3] = scratch[1];           // C1.y
 447:       stack[sp + 4] = scratch[2];           // C2.x
 448:       stack[sp + 5] = scratch[3];           // C2.y
 449:       srcPosX = stack[sp + 6] = scratch[4]; // P2.x
 450:       srcPosY = stack[sp + 7] = scratch[5]; // P2.y
 451:       subdivideCubic();
 452:       return;
 453:     }
 454:   }
 455: 
 456: 
 457:   /**
 458:    * Repeatedly subdivides the quadratic curve segment that is on top
 459:    * of the stack. The iteration terminates when the recursion limit
 460:    * has been reached, or when the resulting segment is flat enough.
 461:    */
 462:   private void subdivideQuadratic()
 463:   {
 464:     int sp;
 465:     int level;
 466: 
 467:     sp = stack.length - 4 * stackSize - 2;
 468:     level = recLevel[stackSize - 1];
 469:     while ((level < recursionLimit)
 470:            && (QuadCurve2D.getFlatnessSq(stack, sp) >= flatnessSq))
 471:     {
 472:       recLevel[stackSize] = recLevel[stackSize - 1] = ++level;
 473:       QuadCurve2D.subdivide(stack, sp, stack, sp - 4, stack, sp);
 474:       ++stackSize;
 475:       sp -= 4;
 476:     }
 477:   }
 478: 
 479: 
 480:   /**
 481:    * Repeatedly subdivides the cubic curve segment that is on top
 482:    * of the stack. The iteration terminates when the recursion limit
 483:    * has been reached, or when the resulting segment is flat enough.
 484:    */
 485:   private void subdivideCubic()
 486:   {
 487:     int sp;
 488:     int level;
 489: 
 490:     sp = stack.length - 6 * stackSize - 2;
 491:     level = recLevel[stackSize - 1];
 492:     while ((level < recursionLimit)
 493:            && (CubicCurve2D.getFlatnessSq(stack, sp) >= flatnessSq))
 494:     {
 495:       recLevel[stackSize] = recLevel[stackSize - 1] = ++level;
 496:       
 497:       CubicCurve2D.subdivide(stack, sp, stack, sp - 6, stack, sp);
 498:       ++stackSize;
 499:       sp -= 6;
 500:     }
 501:   }
 502: 
 503: 
 504:   /* These routines were useful for debugging. Since they would
 505:    * just bloat the implementation, they are commented out.
 506:    *
 507:    *
 508: 
 509:   private static String segToString(int segType, double[] d, int offset)
 510:   {
 511:     String s;
 512: 
 513:     switch (segType)
 514:     {
 515:     case PathIterator.SEG_CLOSE:
 516:       return "SEG_CLOSE";
 517: 
 518:     case PathIterator.SEG_MOVETO:
 519:       return "SEG_MOVETO (" + d[offset] + ", " + d[offset + 1] + ")";
 520: 
 521:     case PathIterator.SEG_LINETO:
 522:       return "SEG_LINETO (" + d[offset] + ", " + d[offset + 1] + ")";
 523: 
 524:     case PathIterator.SEG_QUADTO:
 525:       return "SEG_QUADTO (" + d[offset] + ", " + d[offset + 1]
 526:         + ") (" + d[offset + 2] + ", " + d[offset + 3] + ")";
 527: 
 528:     case PathIterator.SEG_CUBICTO:
 529:       return "SEG_CUBICTO (" + d[offset] + ", " + d[offset + 1]
 530:         + ") (" + d[offset + 2] + ", " + d[offset + 3]
 531:         + ") (" + d[offset + 4] + ", " + d[offset + 5] + ")";
 532:     }
 533: 
 534:     throw new IllegalStateException();
 535:   }
 536: 
 537: 
 538:   private void dumpQuadraticStack(String msg)
 539:   {
 540:     int sp = stack.length - 4 * stackSize - 2;
 541:     int i = 0;
 542:     System.err.print("    " + msg + ":");
 543:     while (sp < stack.length)
 544:     {
 545:       System.err.print(" (" + stack[sp] + ", " + stack[sp+1] + ")");
 546:       if (i < recLevel.length)
 547:         System.out.print("/" + recLevel[i++]);
 548:       if (sp + 3 < stack.length)
 549:         System.err.print(" [" + stack[sp+2] + ", " + stack[sp+3] + "]");
 550:       sp += 4;
 551:     }
 552:     System.err.println();
 553:   }
 554: 
 555: 
 556:   private void dumpCubicStack(String msg)
 557:   {
 558:     int sp = stack.length - 6 * stackSize - 2;
 559:     int i = 0;
 560:     System.err.print("    " + msg + ":");
 561:     while (sp < stack.length)
 562:     {
 563:       System.err.print(" (" + stack[sp] + ", " + stack[sp+1] + ")");
 564:       if (i < recLevel.length)
 565:         System.out.print("/" + recLevel[i++]);
 566:       if (sp + 3 < stack.length)
 567:       {
 568:         System.err.print(" [" + stack[sp+2] + ", " + stack[sp+3] + "]");
 569:         System.err.print(" [" + stack[sp+4] + ", " + stack[sp+5] + "]");
 570:       }
 571:       sp += 6;
 572:     }
 573:     System.err.println();
 574:   }
 575: 
 576:   *
 577:   *
 578:   */
 579: }