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é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 }