libjava/java/awt/geom/FlatteningPathIterator.java

   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., 59 Temple Place, Suite 330, Boston, MA
  19 02111-1307 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 }