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