001    /* FlatteningPathIterator.java -- Approximates curves by straight lines
002       Copyright (C) 2003 Free Software Foundation
003    
004    This file is part of GNU Classpath.
005    
006    GNU Classpath is free software; you can redistribute it and/or modify
007    it under the terms of the GNU General Public License as published by
008    the Free Software Foundation; either version 2, or (at your option)
009    any later version.
010    
011    GNU Classpath is distributed in the hope that it will be useful, but
012    WITHOUT ANY WARRANTY; without even the implied warranty of
013    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
014    General Public License for more details.
015    
016    You should have received a copy of the GNU General Public License
017    along with GNU Classpath; see the file COPYING.  If not, write to the
018    Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA
019    02110-1301 USA.
020    
021    Linking this library statically or dynamically with other modules is
022    making a combined work based on this library.  Thus, the terms and
023    conditions of the GNU General Public License cover the whole
024    combination.
025    
026    As a special exception, the copyright holders of this library give you
027    permission to link this library with independent modules to produce an
028    executable, regardless of the license terms of these independent
029    modules, and to copy and distribute the resulting executable under
030    terms of your choice, provided that you also meet, for each linked
031    independent module, the terms and conditions of the license of that
032    module.  An independent module is a module which is not derived from
033    or based on this library.  If you modify this library, you may extend
034    this exception to your version of the library, but you are not
035    obligated to do so.  If you do not wish to do so, delete this
036    exception statement from your version. */
037    
038    
039    package java.awt.geom;
040    
041    import 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     */
085    public 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    }