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é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 */ FlatteningPathIterator(PathIterator src, double flatness)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 */ FlatteningPathIterator(PathIterator src, double flatness, int limit)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 */ getFlatness()218 public double getFlatness() 219 { 220 return Math.sqrt(flatnessSq); 221 } 222 223 224 /** 225 * Returns the maximum number of recursive curve subdivisions. 226 */ getRecursionLimit()227 public int getRecursionLimit() 228 { 229 return recursionLimit; 230 } 231 232 233 // Documentation will be copied from PathIterator. getWindingRule()234 public int getWindingRule() 235 { 236 return srcIter.getWindingRule(); 237 } 238 239 240 // Documentation will be copied from PathIterator. isDone()241 public boolean isDone() 242 { 243 return done; 244 } 245 246 247 // Documentation will be copied from PathIterator. next()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. currentSegment(double[] coords)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. currentSegment(float[] coords)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 */ fetchSegment()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 */ subdivideQuadratic()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 */ subdivideCubic()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 } 580