1 /* 2 * Copyright (c) 1997, 2018, Oracle and/or its affiliates. All rights reserved. 3 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. 4 * 5 * This code is free software; you can redistribute it and/or modify it 6 * under the terms of the GNU General Public License version 2 only, as 7 * published by the Free Software Foundation. Oracle designates this 8 * particular file as subject to the "Classpath" exception as provided 9 * by Oracle in the LICENSE file that accompanied this code. 10 * 11 * This code is distributed in the hope that it will be useful, but WITHOUT 12 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or 13 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 14 * version 2 for more details (a copy is included in the LICENSE file that 15 * accompanied this code). 16 * 17 * You should have received a copy of the GNU General Public License version 18 * 2 along with this work; if not, write to the Free Software Foundation, 19 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. 20 * 21 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA 22 * or visit www.oracle.com if you need additional information or have any 23 * questions. 24 */ 25 26 package java.awt.geom; 27 28 import java.util.*; 29 30 /** 31 * The {@code FlatteningPathIterator} class returns a flattened view of 32 * another {@link PathIterator} object. Other {@link java.awt.Shape Shape} 33 * classes can use this class to provide flattening behavior for their paths 34 * without having to perform the interpolation calculations themselves. 35 * 36 * @author Jim Graham 37 */ 38 public class FlatteningPathIterator implements PathIterator { 39 static final int GROW_SIZE = 24; // Multiple of cubic & quad curve size 40 41 PathIterator src; // The source iterator 42 43 double squareflat; // Square of the flatness parameter 44 // for testing against squared lengths 45 46 int limit; // Maximum number of recursion levels 47 48 double[] hold = new double[14]; // The cache of interpolated coords 49 // Note that this must be long enough 50 // to store a full cubic segment and 51 // a relative cubic segment to avoid 52 // aliasing when copying the coords 53 // of a curve to the end of the array. 54 // This is also serendipitously equal 55 // to the size of a full quad segment 56 // and 2 relative quad segments. 57 58 double curx, cury; // The ending x,y of the last segment 59 60 double movx, movy; // The x,y of the last move segment 61 62 int holdType; // The type of the curve being held 63 // for interpolation 64 65 int holdEnd; // The index of the last curve segment 66 // being held for interpolation 67 68 int holdIndex; // The index of the curve segment 69 // that was last interpolated. This 70 // is the curve segment ready to be 71 // returned in the next call to 72 // currentSegment(). 73 74 int[] levels; // The recursion level at which 75 // each curve being held in storage 76 // was generated. 77 78 int levelIndex; // The index of the entry in the 79 // levels array of the curve segment 80 // at the holdIndex 81 82 boolean done; // True when iteration is done 83 84 /** 85 * Constructs a new {@code FlatteningPathIterator} object that 86 * flattens a path as it iterates over it. The iterator does not 87 * subdivide any curve read from the source iterator to more than 88 * 10 levels of subdivision which yields a maximum of 1024 line 89 * segments per curve. 90 * @param src the original unflattened path being iterated over 91 * @param flatness the maximum allowable distance between the 92 * control points and the flattened curve 93 */ FlatteningPathIterator(PathIterator src, double flatness)94 public FlatteningPathIterator(PathIterator src, double flatness) { 95 this(src, flatness, 10); 96 } 97 98 /** 99 * Constructs a new {@code FlatteningPathIterator} object 100 * that flattens a path as it iterates over it. 101 * The {@code limit} parameter allows you to control the 102 * maximum number of recursive subdivisions that the iterator 103 * can make before it assumes that the curve is flat enough 104 * without measuring against the {@code flatness} parameter. 105 * The flattened iteration therefore never generates more than 106 * a maximum of {@code (2^limit)} line segments per curve. 107 * @param src the original unflattened path being iterated over 108 * @param flatness the maximum allowable distance between the 109 * control points and the flattened curve 110 * @param limit the maximum number of recursive subdivisions 111 * allowed for any curved segment 112 * @exception IllegalArgumentException if 113 * {@code flatness} or {@code limit} 114 * is less than zero 115 */ FlatteningPathIterator(PathIterator src, double flatness, int limit)116 public FlatteningPathIterator(PathIterator src, double flatness, 117 int limit) { 118 if (flatness < 0.0) { 119 throw new IllegalArgumentException("flatness must be >= 0"); 120 } 121 if (limit < 0) { 122 throw new IllegalArgumentException("limit must be >= 0"); 123 } 124 this.src = src; 125 this.squareflat = flatness * flatness; 126 this.limit = limit; 127 this.levels = new int[limit + 1]; 128 // prime the first path segment 129 next(false); 130 } 131 132 /** 133 * Returns the flatness of this iterator. 134 * @return the flatness of this {@code FlatteningPathIterator}. 135 */ getFlatness()136 public double getFlatness() { 137 return Math.sqrt(squareflat); 138 } 139 140 /** 141 * Returns the recursion limit of this iterator. 142 * @return the recursion limit of this 143 * {@code FlatteningPathIterator}. 144 */ getRecursionLimit()145 public int getRecursionLimit() { 146 return limit; 147 } 148 149 /** 150 * Returns the winding rule for determining the interior of the 151 * path. 152 * @return the winding rule of the original unflattened path being 153 * iterated over. 154 * @see PathIterator#WIND_EVEN_ODD 155 * @see PathIterator#WIND_NON_ZERO 156 */ getWindingRule()157 public int getWindingRule() { 158 return src.getWindingRule(); 159 } 160 161 /** 162 * Tests if the iteration is complete. 163 * @return {@code true} if all the segments have 164 * been read; {@code false} otherwise. 165 */ isDone()166 public boolean isDone() { 167 return done; 168 } 169 170 /* 171 * Ensures that the hold array can hold up to (want) more values. 172 * It is currently holding (hold.length - holdIndex) values. 173 */ ensureHoldCapacity(int want)174 void ensureHoldCapacity(int want) { 175 if (holdIndex - want < 0) { 176 int have = hold.length - holdIndex; 177 int newsize = hold.length + GROW_SIZE; 178 double[] newhold = new double[newsize]; 179 System.arraycopy(hold, holdIndex, 180 newhold, holdIndex + GROW_SIZE, 181 have); 182 hold = newhold; 183 holdIndex += GROW_SIZE; 184 holdEnd += GROW_SIZE; 185 } 186 } 187 188 /** 189 * Moves the iterator to the next segment of the path forwards 190 * along the primary direction of traversal as long as there are 191 * more points in that direction. 192 */ next()193 public void next() { 194 next(true); 195 } 196 next(boolean doNext)197 private void next(boolean doNext) { 198 int level; 199 200 if (holdIndex >= holdEnd) { 201 if (doNext) { 202 src.next(); 203 } 204 if (src.isDone()) { 205 done = true; 206 return; 207 } 208 holdType = src.currentSegment(hold); 209 levelIndex = 0; 210 levels[0] = 0; 211 } 212 213 switch (holdType) { 214 case SEG_MOVETO: 215 case SEG_LINETO: 216 curx = hold[0]; 217 cury = hold[1]; 218 if (holdType == SEG_MOVETO) { 219 movx = curx; 220 movy = cury; 221 } 222 holdIndex = 0; 223 holdEnd = 0; 224 break; 225 case SEG_CLOSE: 226 curx = movx; 227 cury = movy; 228 holdIndex = 0; 229 holdEnd = 0; 230 break; 231 case SEG_QUADTO: 232 if (holdIndex >= holdEnd) { 233 // Move the coordinates to the end of the array. 234 holdIndex = hold.length - 6; 235 holdEnd = hold.length - 2; 236 hold[holdIndex + 0] = curx; 237 hold[holdIndex + 1] = cury; 238 hold[holdIndex + 2] = hold[0]; 239 hold[holdIndex + 3] = hold[1]; 240 hold[holdIndex + 4] = curx = hold[2]; 241 hold[holdIndex + 5] = cury = hold[3]; 242 } 243 244 level = levels[levelIndex]; 245 while (level < limit) { 246 if (QuadCurve2D.getFlatnessSq(hold, holdIndex) < squareflat) { 247 break; 248 } 249 250 ensureHoldCapacity(4); 251 QuadCurve2D.subdivide(hold, holdIndex, 252 hold, holdIndex - 4, 253 hold, holdIndex); 254 holdIndex -= 4; 255 256 // Now that we have subdivided, we have constructed 257 // two curves of one depth lower than the original 258 // curve. One of those curves is in the place of 259 // the former curve and one of them is in the next 260 // set of held coordinate slots. We now set both 261 // curves level values to the next higher level. 262 level++; 263 levels[levelIndex] = level; 264 levelIndex++; 265 levels[levelIndex] = level; 266 } 267 268 // This curve segment is flat enough, or it is too deep 269 // in recursion levels to try to flatten any more. The 270 // two coordinates at holdIndex+4 and holdIndex+5 now 271 // contain the endpoint of the curve which can be the 272 // endpoint of an approximating line segment. 273 holdIndex += 4; 274 levelIndex--; 275 break; 276 case SEG_CUBICTO: 277 if (holdIndex >= holdEnd) { 278 // Move the coordinates to the end of the array. 279 holdIndex = hold.length - 8; 280 holdEnd = hold.length - 2; 281 hold[holdIndex + 0] = curx; 282 hold[holdIndex + 1] = cury; 283 hold[holdIndex + 2] = hold[0]; 284 hold[holdIndex + 3] = hold[1]; 285 hold[holdIndex + 4] = hold[2]; 286 hold[holdIndex + 5] = hold[3]; 287 hold[holdIndex + 6] = curx = hold[4]; 288 hold[holdIndex + 7] = cury = hold[5]; 289 } 290 291 level = levels[levelIndex]; 292 while (level < limit) { 293 if (CubicCurve2D.getFlatnessSq(hold, holdIndex) < squareflat) { 294 break; 295 } 296 297 ensureHoldCapacity(6); 298 CubicCurve2D.subdivide(hold, holdIndex, 299 hold, holdIndex - 6, 300 hold, holdIndex); 301 holdIndex -= 6; 302 303 // Now that we have subdivided, we have constructed 304 // two curves of one depth lower than the original 305 // curve. One of those curves is in the place of 306 // the former curve and one of them is in the next 307 // set of held coordinate slots. We now set both 308 // curves level values to the next higher level. 309 level++; 310 levels[levelIndex] = level; 311 levelIndex++; 312 levels[levelIndex] = level; 313 } 314 315 // This curve segment is flat enough, or it is too deep 316 // in recursion levels to try to flatten any more. The 317 // two coordinates at holdIndex+6 and holdIndex+7 now 318 // contain the endpoint of the curve which can be the 319 // endpoint of an approximating line segment. 320 holdIndex += 6; 321 levelIndex--; 322 break; 323 } 324 } 325 326 /** 327 * Returns the coordinates and type of the current path segment in 328 * the iteration. 329 * The return value is the path segment type: 330 * SEG_MOVETO, SEG_LINETO, or SEG_CLOSE. 331 * A float array of length 6 must be passed in and can be used to 332 * store the coordinates of the point(s). 333 * Each point is stored as a pair of float x,y coordinates. 334 * SEG_MOVETO and SEG_LINETO types return one point, 335 * and SEG_CLOSE does not return any points. 336 * @param coords an array that holds the data returned from 337 * this method 338 * @return the path segment type of the current path segment. 339 * @exception NoSuchElementException if there 340 * are no more elements in the flattening path to be 341 * returned. 342 * @see PathIterator#SEG_MOVETO 343 * @see PathIterator#SEG_LINETO 344 * @see PathIterator#SEG_CLOSE 345 */ currentSegment(float[] coords)346 public int currentSegment(float[] coords) { 347 if (isDone()) { 348 throw new NoSuchElementException("flattening iterator out of bounds"); 349 } 350 int type = holdType; 351 if (type != SEG_CLOSE) { 352 coords[0] = (float) hold[holdIndex + 0]; 353 coords[1] = (float) hold[holdIndex + 1]; 354 if (type != SEG_MOVETO) { 355 type = SEG_LINETO; 356 } 357 } 358 return type; 359 } 360 361 /** 362 * Returns the coordinates and type of the current path segment in 363 * the iteration. 364 * The return value is the path segment type: 365 * SEG_MOVETO, SEG_LINETO, or SEG_CLOSE. 366 * A double array of length 6 must be passed in and can be used to 367 * store the coordinates of the point(s). 368 * Each point is stored as a pair of double x,y coordinates. 369 * SEG_MOVETO and SEG_LINETO types return one point, 370 * and SEG_CLOSE does not return any points. 371 * @param coords an array that holds the data returned from 372 * this method 373 * @return the path segment type of the current path segment. 374 * @exception NoSuchElementException if there 375 * are no more elements in the flattening path to be 376 * returned. 377 * @see PathIterator#SEG_MOVETO 378 * @see PathIterator#SEG_LINETO 379 * @see PathIterator#SEG_CLOSE 380 */ currentSegment(double[] coords)381 public int currentSegment(double[] coords) { 382 if (isDone()) { 383 throw new NoSuchElementException("flattening iterator out of bounds"); 384 } 385 int type = holdType; 386 if (type != SEG_CLOSE) { 387 coords[0] = hold[holdIndex + 0]; 388 coords[1] = hold[holdIndex + 1]; 389 if (type != SEG_MOVETO) { 390 type = SEG_LINETO; 391 } 392 } 393 return type; 394 } 395 } 396