001/* FlatteningPathIterator.java -- Approximates curves by straight lines
002   Copyright (C) 2003 Free Software Foundation
003
004This file is part of GNU Classpath.
005
006GNU Classpath is free software; you can redistribute it and/or modify
007it under the terms of the GNU General Public License as published by
008the Free Software Foundation; either version 2, or (at your option)
009any later version.
010
011GNU Classpath is distributed in the hope that it will be useful, but
012WITHOUT ANY WARRANTY; without even the implied warranty of
013MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
014General Public License for more details.
015
016You should have received a copy of the GNU General Public License
017along with GNU Classpath; see the file COPYING.  If not, write to the
018Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA
01902110-1301 USA.
020
021Linking this library statically or dynamically with other modules is
022making a combined work based on this library.  Thus, the terms and
023conditions of the GNU General Public License cover the whole
024combination.
025
026As a special exception, the copyright holders of this library give you
027permission to link this library with independent modules to produce an
028executable, regardless of the license terms of these independent
029modules, and to copy and distribute the resulting executable under
030terms of your choice, provided that you also meet, for each linked
031independent module, the terms and conditions of the license of that
032module.  An independent module is a module which is not derived from
033or based on this library.  If you modify this library, you may extend
034this exception to your version of the library, but you are not
035obligated to do so.  If you do not wish to do so, delete this
036exception statement from your version. */
037
038
039package java.awt.geom;
040
041import java.util.NoSuchElementException;
042
043
044/**
045 * A PathIterator for approximating curved path segments by sequences
046 * of straight lines. Instances of this class will only return
047 * segments of type {@link PathIterator#SEG_MOVETO}, {@link
048 * PathIterator#SEG_LINETO}, and {@link PathIterator#SEG_CLOSE}.
049 *
050 * <p>The accuracy of the approximation is determined by two
051 * parameters:
052 *
053 * <ul><li>The <i>flatness</i> is a threshold value for deciding when
054 * a curved segment is consided flat enough for being approximated by
055 * a single straight line. Flatness is defined as the maximal distance
056 * of a curve control point to the straight line that connects the
057 * curve start and end. A lower flatness threshold means a closer
058 * approximation.  See {@link QuadCurve2D#getFlatness()} and {@link
059 * CubicCurve2D#getFlatness()} for drawings which illustrate the
060 * meaning of flatness.</li>
061 *
062 * <li>The <i>recursion limit</i> imposes an upper bound for how often
063 * a curved segment gets subdivided. A limit of <i>n</i> means that
064 * for each individual quadratic and cubic B&#xe9;zier spline
065 * segment, at most 2<sup><small><i>n</i></small></sup> {@link
066 * PathIterator#SEG_LINETO} segments will be created.</li></ul>
067 *
068 * <p><b>Memory Efficiency:</b> The memory consumption grows linearly
069 * with the recursion limit. Neither the <i>flatness</i> parameter nor
070 * the number of segments in the flattened path will affect the memory
071 * consumption.
072 *
073 * <p><b>Thread Safety:</b> Multiple threads can safely work on
074 * separate instances of this class. However, multiple threads should
075 * not concurrently access the same instance, as no synchronization is
076 * performed.
077 *
078 * @see <a href="doc-files/FlatteningPathIterator-1.html"
079 * >Implementation Note</a>
080 *
081 * @author Sascha Brawer (brawer@dandelis.ch)
082 *
083 * @since 1.2
084 */
085public class FlatteningPathIterator
086  implements PathIterator
087{
088  /**
089   * The PathIterator whose curved segments are being approximated.
090   */
091  private final PathIterator srcIter;
092
093
094  /**
095   * The square of the flatness threshold value, which determines when
096   * a curve segment is considered flat enough that no further
097   * subdivision is needed.
098   *
099   * <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}