# The GNU Implementation of FlatteningPathIterator

Sascha Brawer, November 2003

This document describes the GNU implementation of the class `java.awt.geom.FlatteningPathIterator`. It does not describe how a programmer should use this class; please refer to the generated API documentation for this purpose. Instead, it is intended for maintenance programmers who want to understand the implementation, for example because they want to extend the class or fix a bug.

## Data Structures

The algorithm uses a stack. Its allocation is delayed to the time when the source path iterator actually returns the first curved segment (either `SEG_QUADTO` or `SEG_CUBICTO`). If the input path does not contain any curved segments, the value of the `stack` variable stays `null`. In this quite common case, the memory consumption is minimal.

`stack`
  The variable `stack` is a `double` array that holds the start, control and end points of individual sub-segments.
`recLevel`
  The variable `recLevel` holds how many recursive sub-divisions were needed to calculate a segment. The original curve has recursion level 0. For each sub-division, the corresponding recursion level is increased by one.
`stackSize`
  Finally, the variable `stackSize` indicates how many sub-segments are stored on the stack.

## Algorithm

The implementation separately processes each segment that the base iterator returns.

In the case of `SEG_CLOSE`, `SEG_MOVETO` and `SEG_LINETO` segments, the implementation simply hands the segment to the consumer, without actually doing anything.

Any `SEG_QUADTO` and `SEG_CUBICTO` segments need to be flattened. Flattening is performed with a fixed-sized stack, holding the coordinates of subdivided segments. When the base iterator returns a `SEG_QUADTO` and `SEG_CUBICTO` segments, it is recursively flattened as follows:

1. Intialization: Allocate memory for the stack (unless a sufficiently large stack has been allocated previously). Push the original quadratic or cubic curve onto the stack. Mark that segment as having a `recLevel` of zero.
2. If the stack is empty, flattening the segment is complete, and the next segment is fetched from the base iterator.
3. If the stack is not empty, pop a curve segment from the stack.
   - If its `recLevel` exceeds the recursion limit, hand the current segment to the consumer.
   - Calculate the squared flatness of the segment. If it smaller than `flatnessSq`, hand the current segment to the consumer.
   - Otherwise, split the segment in two halves. Push the right half onto the stack. Then, push the left half onto the stack. Continue with step two.

The implementation is slightly complicated by the fact that consumers pull the flattened segments from the `FlatteningPathIterator`. This means that we actually cannot “hand the curent segment over to the consumer.” But the algorithm is easier to understand if one assumes a push paradigm.

## Example

The following example shows how a `FlatteningPathIterator` processes a `SEG_QUADTO` segment. It is (arbitrarily) assumed that the recursion limit was set to 2.

> | A | B | C | D | E | F | G | H
> --- | --- | --- | --- | --- | --- | --- | --- | ---
> `stack[0]` | — | — | Sll.x | — | — | — | — | —
> `stack[1]` | — | — | Sll.y | — | — | — | — | —
> `stack[2]` | — | — | Cll.x | — | — | — | — | —
> `stack[3]` | — | — | Cll.y | — | — | — | — | —
> `stack[4]` | — | Sl.x | Ell.x = Slr.x | Slr.x | — | Srl.x | — | —
> `stack[5]` | — | Sl.y | Ell.x = Slr.y | Slr.y | — | Srl.y | — | —
> `stack[6]` | — | Cl.x | Clr.x | Clr.x | — | Crl.x | — | —
> `stack[7]` | — | Cl.y | Clr.y | Clr.y | — | Crl.y | — | —
> `stack[8]` | S.x | El.x = Sr.x | Elr.x = Sr.x | Elr.x = Sr.x | Sr.x | Erl.x = Srr.x | Srr.x | —
> `stack[9]` | S.y | El.y = Sr.y | Elr.y = Sr.y | Elr.y = Sr.y | Sr.y | Erl.y = Srr.y | Srr.y | —
> `stack[10]` | C.x | Cr.x | Cr.x | Cr.x | Cr.x | Crr.x | Crr.x | —
> `stack[11]` | C.y | Cr.y | Cr.y | Cr.y | Cr.y | Crr.y | Crr.y | —
> `stack[12]` | E.x | Er.x | Er.x | Er.x | Er.x | Err.x | Err.x | —
> `stack[13]` | E.y | Er.y | Er.y | Er.y | Er.y | Err.y | Err.x | —
> `stackSize` | 1 | 2 | 3 | 2 | 1 | 2 | 1 | 0
> `recLevel[2]` | — | — | 2 | — | — | — | — | —
> `recLevel[1]` | — | 1 | 2 | 2 | — | 2 | — | —
> `recLevel[0]` | 0 | 1 | 1 | 1 | 1 | 2 | 2 | —

1. The data structures are initialized as follows.
   - The segment’s end point E, control point C, and start point S are pushed onto the stack.
   - Currently, the curve in the stack would be approximated by one single straight line segment (S – E). Therefore, `stackSize` is set to 1.
   - This single straight line segment is approximating the original curve, which can be seen as the result of zero recursive splits. Therefore, `recLevel[0]` is set to zero.
   Column A shows the state after the initialization step.
2. The algorithm proceeds by taking the topmost curve segment (S – C – E) from the stack.
   - The recursion level of this segment (stored in `recLevel[0]`) is zero, which is smaller than the limit 2.
   - The method `java.awt.geom.QuadCurve2D.getFlatnessSq` is called to calculate the squared flatness.
   - For the sake of argument, we assume that the squared flatness is exceeding the threshold stored in `flatnessSq`. Thus, the curve segment S – C – E gets subdivided into a left and a right half, namely Sl – Cl – El and Sr – Cr – Er. Both halves are pushed onto the stack, so the left half is now on top.
     The left half starts at the same point as the original curve, so Sl has the same coordinates as S. Similarly, the end point of the right half and of the original curve are identical (Er = E). More interestingly, the left half ends where the right half starts. Because El = Sr, their coordinates need to be stored only once, which amounts to saving 16 bytes (two `double` values) for each iteration.
   Column B shows the state after the first iteration.
3. Again, the topmost curve segment (Sl – Cl – El) is taken from the stack.
   - The recursion level of this segment (stored in `recLevel[1]`) is 1, which is smaller than the limit 2.
   - The method `java.awt.geom.QuadCurve2D.getFlatnessSq` is called to calculate the squared flatness.
   - Assuming that the segment is still not considered flat enough, it gets subdivided into a left (Sll – Cll – Ell) and a right (Slr – Clr – Elr) half.
   Column C shows the state after the second iteration.
4. The topmost curve segment (Sll – Cll – Ell) is popped from the stack.
   - The recursion level of this segment (stored in `recLevel[2]`) is 2, which is not smaller than the limit 2. Therefore, a `SEG_LINETO` (from Sll to Ell) is passed to the consumer.
   The new state is shown in column D.
5. The topmost curve segment (Slr – Clr – Elr) is popped from the stack.
   - The recursion level of this segment (stored in `recLevel[1]`) is 2, which is not smaller than the limit 2. Therefore, a `SEG_LINETO` (from Slr to Elr) is passed to the consumer.
   The new state is shown in column E.
6. The algorithm proceeds by taking the topmost curve segment (Sr – Cr – Er) from the stack.
   - The recursion level of this segment (stored in `recLevel[0]`) is 1, which is smaller than the limit 2.
   - The method `java.awt.geom.QuadCurve2D.getFlatnessSq` is called to calculate the squared flatness.
   - For the sake of argument, we again assume that the squared flatness is exceeding the threshold stored in `flatnessSq`. Thus, the curve segment (Sr – Cr – Er) is subdivided into a left and a right half, namely Srl – Crl – Erl and Srr – Crr – Err. Both halves are pushed onto the stack.
   The new state is shown in column F.
7. The topmost curve segment (Srl – Crl – Erl) is popped from the stack.
   - The recursion level of this segment (stored in `recLevel[2]`) is 2, which is not smaller than the limit 2. Therefore, a `SEG_LINETO` (from Srl to Erl) is passed to the consumer.
   The new state is shown in column G.
8. The topmost curve segment (Srr – Crr – Err) is popped from the stack.
   - The recursion level of this segment (stored in `recLevel[2]`) is 2, which is not smaller than the limit 2. Therefore, a `SEG_LINETO` (from Srr to Err) is passed to the consumer.
   The new state is shown in column H.
9. The stack is now empty. The FlatteningPathIterator will fetch the next segment from the base iterator, and process it.

In order to split the most recently pushed segment, the `subdivideQuadratic()` method passes `stack` directly to `QuadCurve2D.subdivide(double[],int,double[],int,double[],int)`. Because the stack grows towards the beginning of the array, no data needs to be copied around: `subdivide` will directly store the result into the stack, which will have the contents shown to the right.