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 S_l – C_l – E_l and S_r – C_r – E_r. 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 S_l has the same coordinates as S. Similarly, the end point of the right half and of the original curve are identical (E_r = E). More interestingly, the left half ends where the right half starts. Because E_l = S_r, 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 (S_l – C_l – E_l) 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 (S_ll – C_ll – E_ll) and a right (S_lr – C_lr – E_lr) half.
   Column C shows the state after the second iteration.
4. The topmost curve segment (S_ll – C_ll – E_ll) 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 S_ll to E_ll) is passed to the consumer.
   The new state is shown in column D.
5. The topmost curve segment (S_lr – C_lr – E_lr) 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 S_lr to E_lr) is passed to the consumer.
   The new state is shown in column E.
6. The algorithm proceeds by taking the topmost curve segment (S_r – C_r – E_r) 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 (S_r – C_r – E_r) is subdivided into a left and a right half, namely S_rl – C_rl – E_rl and S_rr – C_rr – E_rr. Both halves are pushed onto the stack.
   The new state is shown in column F.
7. The topmost curve segment (S_rl – C_rl – E_rl) 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 S_rl to E_rl) is passed to the consumer.
   The new state is shown in column G.
8. The topmost curve segment (S_rr – C_rr – E_rr) 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 S_rr to E_rr) 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.