From 554fd8c5195424bdbcabf5de30fdc183aba391bd Mon Sep 17 00:00:00 2001 From: upstream source tree Date: Sun, 15 Mar 2015 20:14:05 -0400 Subject: obtained gcc-4.6.4.tar.bz2 from upstream website; verified gcc-4.6.4.tar.bz2.sig; imported gcc-4.6.4 source tree from verified upstream tarball. downloading a git-generated archive based on the 'upstream' tag should provide you with a source tree that is binary identical to the one extracted from the above tarball. if you have obtained the source via the command 'git clone', however, do note that line-endings of files in your working directory might differ from line-endings of the respective files in the upstream repository. --- .../geom/doc-files/FlatteningPathIterator-1.html | 481 +++++++++++++++++++++ 1 file changed, 481 insertions(+) create mode 100644 libjava/classpath/java/awt/geom/doc-files/FlatteningPathIterator-1.html (limited to 'libjava/classpath/java/awt/geom/doc-files/FlatteningPathIterator-1.html') diff --git a/libjava/classpath/java/awt/geom/doc-files/FlatteningPathIterator-1.html b/libjava/classpath/java/awt/geom/doc-files/FlatteningPathIterator-1.html new file mode 100644 index 000000000..5a52d693e --- /dev/null +++ b/libjava/classpath/java/awt/geom/doc-files/FlatteningPathIterator-1.html @@ -0,0 +1,481 @@ + + + + + The GNU Implementation of java.awt.geom.FlatteningPathIterator + + + + + +

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:

+ +

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.
If the stack is empty, flattening the segment is complete, +and the next segment is fetched from the base iterator.
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] — — S_ll.x — — — — —
stack[1] — — S_ll.y — — — — —
stack[2] — — C_ll.x — — — — —
stack[3] — — C_ll.y — — — — —
stack[4] — S_l.x E_ll.x + = S_lr.x S_lr.x — S_rl.x — —
stack[5] — S_l.y E_ll.x + = S_lr.y S_lr.y — S_rl.y — —
stack[6] — C_l.x C_lr.x C_lr.x — C_rl.x — —
stack[7] — C_l.y C_lr.y C_lr.y — C_rl.y — —
stack[8] S.x E_l.x + = S_r.x E_lr.x + = S_r.x E_lr.x + = S_r.x S_r.x E_rl.x + = S_rr.x S_rr.x —
stack[9] S.y E_l.y + = S_r.y E_lr.y + = S_r.y E_lr.y + = S_r.y S_r.y E_rl.y + = S_rr.y S_rr.y —
stack[10] C.x C_r.x C_r.x C_r.x C_r.x C_rr.x C_rr.x —
stack[11] C.y C_r.y C_r.y C_r.y C_r.y C_rr.y C_rr.y —
stack[12] E.x E_r.x E_r.x E_r.x E_r.x E_rr.x E_rr.x —
stack[13] E.y E_r.y E_r.y E_r.y E_r.y E_rr.y E_rr.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 —
+

	A	B	C	D	E	F	G	H
`stack[0]`	—	—	S_ll.x	—	—	—	—	—
`stack[1]`	—	—	S_ll.y	—	—	—	—	—
`stack[2]`	—	—	C_ll.x	—	—	—	—	—
`stack[3]`	—	—	C_ll.y	—	—	—	—	—
`stack[4]`	—	S_l.x	E_ll.x + = S_lr.x	S_lr.x	—	S_rl.x	—	—
`stack[5]`	—	S_l.y	E_ll.x + = S_lr.y	S_lr.y	—	S_rl.y	—	—
`stack[6]`	—	C_l.x	C_lr.x	C_lr.x	—	C_rl.x	—	—
`stack[7]`	—	C_l.y	C_lr.y	C_lr.y	—	C_rl.y	—	—
`stack[8]`	S.x	E_l.x + = S_r.x	E_lr.x + = S_r.x	E_lr.x + = S_r.x	S_r.x	E_rl.x + = S_rr.x	S_rr.x	—
`stack[9]`	S.y	E_l.y + = S_r.y	E_lr.y + = S_r.y	E_lr.y + = S_r.y	S_r.y	E_rl.y + = S_rr.y	S_rr.y	—
`stack[10]`	C.x	C_r.x	C_r.x	C_r.x	C_r.x	C_rr.x	C_rr.x	—
`stack[11]`	C.y	C_r.y	C_r.y	C_r.y	C_r.y	C_rr.y	C_rr.y	—
`stack[12]`	E.x	E_r.x	E_r.x	E_r.x	E_r.x	E_rr.x	E_rr.x	—
`stack[13]`	E.y	E_r.y	E_r.y	E_r.y	E_r.y	E_rr.y	E_rr.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	—

+ +

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.
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.
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.
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.
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.
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.
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.
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.
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.

+ + + -- cgit v1.2.3