libjava/classpath/java/awt/geom/doc-files/FlatteningPathIterator-1.html

   1 <?xml version="1.0" encoding="US-ASCII"?>
   2 <!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Strict//EN"
   3   "http://www.w3.org/TR/xhtml1/DTD/xhtml1-strict.dtd">
   4 <html xmlns="http://www.w3.org/1999/xhtml" xml:lang="en" lang="en">
   5 <head>
   6   <title>The GNU Implementation of java.awt.geom.FlatteningPathIterator</title>
   7   <meta name="author" content="Sascha Brawer" />
   8   <style type="text/css"><!--
   9     td { white-space: nowrap; }
  10     li { margin: 2mm 0; }
  11   --></style>
  12 </head>
  13 <body>
  14
  15 <h1>The GNU Implementation of FlatteningPathIterator</h1>
  16
  17 <p><i><a href="http://www.dandelis.ch/people/brawer/">Sascha
  18 Brawer</a>, November 2003</i></p>
  19
  20 <p>This document describes the GNU implementation of the class
  21 <code>java.awt.geom.FlatteningPathIterator</code>. It does
  22 <em>not</em> describe how a programmer should use this class; please
  23 refer to the generated API documentation for this purpose. Instead, it
  24 is intended for maintenance programmers who want to understand the
  25 implementation, for example because they want to extend the class or
  26 fix a bug.</p>
  27
  28
  29 <h2>Data Structures</h2>
  30
  31 <p>The algorithm uses a stack. Its allocation is delayed to the time
  32 when the source path iterator actually returns the first curved
  33 segment (either <code>SEG_QUADTO</code> or <code>SEG_CUBICTO</code>).
  34 If the input path does not contain any curved segments, the value of
  35 the <code>stack</code> variable stays <code>null</code>. In this quite
  36 common case, the memory consumption is minimal.</p>
  37
  38 <dl><dt><code>stack</code></dt><dd>The variable <code>stack</code> is
  39 a <code>double</code> array that holds the start, control and end
  40 points of individual sub-segments.</dd>
  41
  42 <dt><code>recLevel</code></dt><dd>The variable <code>recLevel</code>
  43 holds how many recursive sub-divisions were needed to calculate a
  44 segment. The original curve has recursion level 0. For each
  45 sub-division, the corresponding recursion level is increased by
  46 one.</dd>
  47
  48 <dt><code>stackSize</code></dt><dd>Finally, the variable
  49 <code>stackSize</code> indicates how many sub-segments are stored on
  50 the stack.</dd></dl>
  51
  52 <h2>Algorithm</h2>
  53
  54 <p>The implementation separately processes each segment that the
  55 base iterator returns.</p>
  56
  57 <p>In the case of <code>SEG_CLOSE</code>,
  58 <code>SEG_MOVETO</code> and <code>SEG_LINETO</code> segments, the
  59 implementation simply hands the segment to the consumer, without actually
  60 doing anything.</p>
  61
  62 <p>Any <code>SEG_QUADTO</code> and <code>SEG_CUBICTO</code> segments
  63 need to be flattened. Flattening is performed with a fixed-sized
  64 stack, holding the coordinates of subdivided segments. When the base
  65 iterator returns a <code>SEG_QUADTO</code> and
  66 <code>SEG_CUBICTO</code> segments, it is recursively flattened as
  67 follows:</p>
  68
  69 <ol><li>Intialization: Allocate memory for the stack (unless a
  70 sufficiently large stack has been allocated previously). Push the
  71 original quadratic or cubic curve onto the stack. Mark that segment as
  72 having a <code>recLevel</code> of zero.</li>
  73
  74 <li>If the stack is empty, flattening the segment is complete,
  75 and the next segment is fetched from the base iterator.</li>
  76
  77 <li>If the stack is not empty, pop a curve segment from the
  78 stack.
  79
  80   <ul><li>If its <code>recLevel</code> exceeds the recursion limit,
  81   hand the current segment to the consumer.</li>
  82
  83   <li>Calculate the squared flatness of the segment. If it smaller
  84   than <code>flatnessSq</code>, hand the current segment to the
  85   consumer.</li>
  86
  87   <li>Otherwise, split the segment in two halves. Push the right
  88   half onto the stack. Then, push the left half onto the stack.
  89   Continue with step two.</li></ul></li>
  90 </ol>
  91
  92 <p>The implementation is slightly complicated by the fact that
  93 consumers <em>pull</em> the flattened segments from the
  94 <code>FlatteningPathIterator</code>. This means that we actually
  95 cannot &#x201c;hand the curent segment over to the consumer.&#x201d;
  96 But the algorithm is easier to understand if one assumes a
  97 <em>push</em> paradigm.</p>
  98
  99
 100 <h2>Example</h2>
 101
 102 <p>The following example shows how a
 103 <code>FlatteningPathIterator</code> processes a
 104 <code>SEG_QUADTO</code> segment. It is (arbitrarily) assumed that the
 105 recursion limit was set to 2.</p>
 106
 107 <blockquote>
 108 <table border="1" cellspacing="0" cellpadding="8">
 109   <tr align="center" valign="baseline">
 110     <th></th><th>A</th><th>B</th><th>C</th>
 111     <th>D</th><th>E</th><th>F</th><th>G</th><th>H</th>
 112   </tr>
 113   <tr align="center" valign="baseline">
 114     <th><code>stack[0]</code></th>
 115     <td>&#x2014;</td>
 116     <td>&#x2014;</td>
 117     <td><i>S<sub>ll</sub>.x</i></td>
 118     <td>&#x2014;</td>
 119     <td>&#x2014;</td>
 120     <td>&#x2014;</td>
 121     <td>&#x2014;</td>
 122     <td>&#x2014;</td>
 123   </tr>
 124   <tr align="center" valign="baseline">
 125     <th><code>stack[1]</code></th>
 126     <td>&#x2014;</td>
 127     <td>&#x2014;</td>
 128     <td><i>S<sub>ll</sub>.y</i></td>
 129     <td>&#x2014;</td>
 130     <td>&#x2014;</td>
 131     <td>&#x2014;</td>
 132     <td>&#x2014;</td>
 133     <td>&#x2014;</td>
 134   </tr>
 135   <tr align="center" valign="baseline">
 136     <th><code>stack[2]</code></th>
 137     <td>&#x2014;</td>
 138     <td>&#x2014;</td>
 139     <td><i>C<sub>ll</sub>.x</i></td>
 140     <td>&#x2014;</td>
 141     <td>&#x2014;</td>
 142     <td>&#x2014;</td>
 143     <td>&#x2014;</td>
 144     <td>&#x2014;</td>
 145   </tr>
 146   <tr align="center" valign="baseline">
 147     <th><code>stack[3]</code></th>
 148     <td>&#x2014;</td>
 149     <td>&#x2014;</td>
 150     <td><i>C<sub>ll</sub>.y</i></td>
 151     <td>&#x2014;</td>
 152     <td>&#x2014;</td>
 153     <td>&#x2014;</td>
 154     <td>&#x2014;</td>
 155     <td>&#x2014;</td>
 156   </tr>
 157   <tr align="center" valign="baseline">
 158     <th><code>stack[4]</code></th>
 159     <td>&#x2014;</td>
 160     <td><i>S<sub>l</sub>.x</i></td>
 161     <td><i>E<sub>ll</sub>.x</i>
 162              = <i>S<sub>lr</sub>.x</i></td>
 163     <td><i>S<sub>lr</sub>.x</i></td>
 164     <td>&#x2014;</td>
 165     <td><i>S<sub>rl</sub>.x</i></td>
 166     <td>&#x2014;</td>
 167     <td>&#x2014;</td>
 168   </tr>
 169   <tr align="center" valign="baseline">
 170     <th><code>stack[5]</code></th>
 171     <td>&#x2014;</td>
 172     <td><i>S<sub>l</sub>.y</i></td>
 173     <td><i>E<sub>ll</sub>.x</i>
 174              = <i>S<sub>lr</sub>.y</i></td>
 175     <td><i>S<sub>lr</sub>.y</i></td>
 176     <td>&#x2014;</td>
 177     <td><i>S<sub>rl</sub>.y</i></td>
 178     <td>&#x2014;</td>
 179     <td>&#x2014;</td>
 180   </tr>
 181   <tr align="center" valign="baseline">
 182     <th><code>stack[6]</code></th>
 183     <td>&#x2014;</td>
 184     <td><i>C<sub>l</sub>.x</i></td>
 185     <td><i>C<sub>lr</sub>.x</i></td>
 186     <td><i>C<sub>lr</sub>.x</i></td>
 187     <td>&#x2014;</td>
 188     <td><i>C<sub>rl</sub>.x</i></td>
 189     <td>&#x2014;</td>
 190     <td>&#x2014;</td>
 191   </tr>
 192   <tr align="center" valign="baseline">
 193     <th><code>stack[7]</code></th>
 194     <td>&#x2014;</td>
 195     <td><i>C<sub>l</sub>.y</i></td>
 196     <td><i>C<sub>lr</sub>.y</i></td>
 197     <td><i>C<sub>lr</sub>.y</i></td>
 198     <td>&#x2014;</td>
 199     <td><i>C<sub>rl</sub>.y</i></td>
 200     <td>&#x2014;</td>
 201     <td>&#x2014;</td>
 202   </tr>
 203   <tr align="center" valign="baseline">
 204     <th><code>stack[8]</code></th>
 205     <td><i>S.x</i></td>
 206     <td><i>E<sub>l</sub>.x</i>
 207              = <i>S<sub>r</sub>.x</i></td>
 208     <td><i>E<sub>lr</sub>.x</i>
 209              = <i>S<sub>r</sub>.x</i></td>
 210     <td><i>E<sub>lr</sub>.x</i>
 211              = <i>S<sub>r</sub>.x</i></td>
 212     <td><i>S<sub>r</sub>.x</i></td>
 213     <td><i>E<sub>rl</sub>.x</i>
 214              = <i>S<sub>rr</sub>.x</i></td>
 215     <td><i>S<sub>rr</sub>.x</i></td>
 216     <td>&#x2014;</td>
 217   </tr>
 218   <tr align="center" valign="baseline">
 219     <th><code>stack[9]</code></th>
 220     <td><i>S.y</i></td>
 221     <td><i>E<sub>l</sub>.y</i>
 222              = <i>S<sub>r</sub>.y</i></td>
 223     <td><i>E<sub>lr</sub>.y</i>
 224              = <i>S<sub>r</sub>.y</i></td>
 225     <td><i>E<sub>lr</sub>.y</i>
 226              = <i>S<sub>r</sub>.y</i></td>
 227     <td><i>S<sub>r</sub>.y</i></td>
 228     <td><i>E<sub>rl</sub>.y</i>
 229              = <i>S<sub>rr</sub>.y</i></td>
 230     <td><i>S<sub>rr</sub>.y</i></td>
 231     <td>&#x2014;</td>
 232   </tr>
 233   <tr align="center" valign="baseline">
 234     <th><code>stack[10]</code></th>
 235     <td><i>C.x</i></td>
 236     <td><i>C<sub>r</sub>.x</i></td>
 237     <td><i>C<sub>r</sub>.x</i></td>
 238     <td><i>C<sub>r</sub>.x</i></td>
 239     <td><i>C<sub>r</sub>.x</i></td>
 240     <td><i>C<sub>rr</sub>.x</i></td>
 241     <td><i>C<sub>rr</sub>.x</i></td>
 242     <td>&#x2014;</td>
 243   </tr>
 244   <tr align="center" valign="baseline">
 245     <th><code>stack[11]</code></th>
 246     <td><i>C.y</i></td>
 247     <td><i>C<sub>r</sub>.y</i></td>
 248     <td><i>C<sub>r</sub>.y</i></td>
 249     <td><i>C<sub>r</sub>.y</i></td>
 250     <td><i>C<sub>r</sub>.y</i></td>
 251     <td><i>C<sub>rr</sub>.y</i></td>
 252     <td><i>C<sub>rr</sub>.y</i></td>
 253     <td>&#x2014;</td>
 254   </tr>
 255   <tr align="center" valign="baseline">
 256     <th><code>stack[12]</code></th>
 257     <td><i>E.x</i></td>
 258     <td><i>E<sub>r</sub>.x</i></td>
 259     <td><i>E<sub>r</sub>.x</i></td>
 260     <td><i>E<sub>r</sub>.x</i></td>
 261     <td><i>E<sub>r</sub>.x</i></td>
 262     <td><i>E<sub>rr</sub>.x</i></td>
 263     <td><i>E<sub>rr</sub>.x</i></td>
 264     <td>&#x2014;</td>
 265   </tr>
 266   <tr align="center" valign="baseline">
 267     <th><code>stack[13]</code></th>
 268     <td><i>E.y</i></td>
 269     <td><i>E<sub>r</sub>.y</i></td>
 270     <td><i>E<sub>r</sub>.y</i></td>
 271     <td><i>E<sub>r</sub>.y</i></td>
 272     <td><i>E<sub>r</sub>.y</i></td>
 273     <td><i>E<sub>rr</sub>.y</i></td>
 274     <td><i>E<sub>rr</sub>.x</i></td>
 275     <td>&#x2014;</td>
 276   </tr>
 277   <tr align="center" valign="baseline">
 278      <th><code>stackSize</code></th>
 279      <td>1</td>
 280      <td>2</td>
 281      <td>3</td>
 282      <td>2</td>
 283      <td>1</td>
 284      <td>2</td>
 285      <td>1</td>
 286      <td>0</td>
 287    </tr>
 288    <tr align="center" valign="baseline">
 289      <th><code>recLevel[2]</code></th>
 290      <td>&#x2014;</td>
 291      <td>&#x2014;</td>
 292      <td>2</td>
 293      <td>&#x2014;</td>
 294      <td>&#x2014;</td>
 295      <td>&#x2014;</td>
 296      <td>&#x2014;</td>
 297      <td>&#x2014;</td>
 298    </tr>
 299    <tr align="center" valign="baseline">
 300      <th><code>recLevel[1]</code></th>
 301      <td>&#x2014;</td>
 302      <td>1</td>
 303      <td>2</td>
 304      <td>2</td>
 305      <td>&#x2014;</td>
 306      <td>2</td>
 307      <td>&#x2014;</td>
 308      <td>&#x2014;</td>
 309    </tr>
 310    <tr align="center" valign="baseline">
 311      <th><code>recLevel[0]</code></th>
 312      <td>0</td>
 313      <td>1</td>
 314      <td>1</td>
 315      <td>1</td>
 316      <td>1</td>
 317      <td>2</td>
 318      <td>2</td>
 319      <td>&#x2014;</td>
 320    </tr>
 321  </table>
 322 </blockquote>
 323
 324 <ol>
 325
 326 <li>The data structures are initialized as follows.
 327
 328 <ul><li>The segment&#x2019;s end point <i>E</i>, control point
 329 <i>C</i>, and start point <i>S</i> are pushed onto the stack.</li>
 330
 331   <li>Currently, the curve in the stack would be approximated by one
 332   single straight line segment (<i>S</i> &#x2013; <i>E</i>).
 333   Therefore, <code>stackSize</code> is set to 1.</li>
 334
 335   <li>This single straight line segment is approximating the original
 336   curve, which can be seen as the result of zero recursive
 337   splits. Therefore, <code>recLevel[0]</code> is set to
 338   zero.</li></ul>
 339
 340 Column A shows the state after the initialization step.</li>
 341
 342 <li>The algorithm proceeds by taking the topmost curve segment
 343 (<i>S</i> &#x2013; <i>C</i> &#x2013; <i>E</i>) from the stack.
 344
 345   <ul><li>The recursion level of this segment (stored in
 346   <code>recLevel[0]</code>) is zero, which is smaller than
 347   the limit 2.</li>
 348
 349   <li>The method <code>java.awt.geom.QuadCurve2D.getFlatnessSq</code>
 350   is called to calculate the squared flatness.</li>
 351
 352   <li>For the sake of argument, we assume that the squared flatness is
 353   exceeding the threshold stored in <code>flatnessSq</code>. Thus, the
 354   curve segment <i>S</i> &#x2013; <i>C</i> &#x2013; <i>E</i> gets
 355   subdivided into a left and a right half, namely
 356   <i>S<sub>l</sub></i> &#x2013; <i>C<sub>l</sub></i> &#x2013;
 357   <i>E<sub>l</sub></i> and <i>S<sub>r</sub></i> &#x2013;
 358   <i>C<sub>r</sub></i> &#x2013; <i>E<sub>r</sub></i>. Both halves are
 359   pushed onto the stack, so the left half is now on top.
 360
 361   <br />&nbsp;<br />The left half starts at the same point
 362   as the original curve, so <i>S<sub>l</sub></i> has the same
 363   coordinates as <i>S</i>.  Similarly, the end point of the right
 364   half and of the original curve are identical
 365   (<i>E<sub>r</sub></i> = <i>E</i>).  More interestingly, the left
 366   half ends where the right half starts. Because
 367   <i>E<sub>l</sub></i> = <i>S<sub>r</sub></i>, their coordinates need
 368   to be stored only once, which amounts to saving 16 bytes (two
 369   <code>double</code> values) for each iteration.</li></ul>
 370
 371 Column B shows the state after the first iteration.</li>
 372
 373 <li>Again, the topmost curve segment (<i>S<sub>l</sub></i>
 374 &#x2013; <i>C<sub>l</sub></i> &#x2013; <i>E<sub>l</sub></i>) is
 375 taken from the stack.
 376
 377   <ul><li>The recursion level of this segment (stored in
 378   <code>recLevel[1]</code>) is 1, which is smaller than
 379   the limit 2.</li>
 380
 381   <li>The method <code>java.awt.geom.QuadCurve2D.getFlatnessSq</code>
 382   is called to calculate the squared flatness.</li>
 383
 384   <li>Assuming that the segment is still not considered
 385   flat enough, it gets subdivided into a left
 386   (<i>S<sub>ll</sub></i> &#x2013; <i>C<sub>ll</sub></i> &#x2013;
 387   <i>E<sub>ll</sub></i>) and a right (<i>S<sub>lr</sub></i>
 388   &#x2013; <i>C<sub>lr</sub></i> &#x2013; <i>E<sub>lr</sub></i>)
 389   half.</li></ul>
 390
 391 Column C shows the state after the second iteration.</li>
 392
 393 <li>The topmost curve segment (<i>S<sub>ll</sub></i> &#x2013;
 394 <i>C<sub>ll</sub></i> &#x2013; <i>E<sub>ll</sub></i>) is popped from
 395 the stack.
 396
 397   <ul><li>The recursion level of this segment (stored in
 398   <code>recLevel[2]</code>) is 2, which is <em>not</em> smaller than
 399   the limit 2. Therefore, a <code>SEG_LINETO</code> (from
 400   <i>S<sub>ll</sub></i> to <i>E<sub>ll</sub></i>) is passed to the
 401   consumer.</li></ul>
 402
 403   The new state is shown in column D.</li>
 404
 405
 406 <li>The topmost curve segment (<i>S<sub>lr</sub></i> &#x2013;
 407 <i>C<sub>lr</sub></i> &#x2013; <i>E<sub>lr</sub></i>) is popped from
 408 the stack.
 409
 410   <ul><li>The recursion level of this segment (stored in
 411   <code>recLevel[1]</code>) is 2, which is <em>not</em> smaller than
 412   the limit 2. Therefore, a <code>SEG_LINETO</code> (from
 413   <i>S<sub>lr</sub></i> to <i>E<sub>lr</sub></i>) is passed to the
 414   consumer.</li></ul>
 415
 416   The new state is shown in column E.</li>
 417
 418 <li>The algorithm proceeds by taking the topmost curve segment
 419 (<i>S<sub>r</sub></i> &#x2013; <i>C<sub>r</sub></i> &#x2013;
 420 <i>E<sub>r</sub></i>) from the stack.
 421
 422   <ul><li>The recursion level of this segment (stored in
 423   <code>recLevel[0]</code>) is 1, which is smaller than
 424   the limit 2.</li>
 425
 426   <li>The method <code>java.awt.geom.QuadCurve2D.getFlatnessSq</code>
 427   is called to calculate the squared flatness.</li>
 428
 429   <li>For the sake of argument, we again assume that the squared
 430   flatness is exceeding the threshold stored in
 431   <code>flatnessSq</code>. Thus, the curve segment
 432   (<i>S<sub>r</sub></i> &#x2013; <i>C<sub>r</sub></i> &#x2013;
 433   <i>E<sub>r</sub></i>) is subdivided into a left and a right half,
 434   namely
 435   <i>S<sub>rl</sub></i> &#x2013; <i>C<sub>rl</sub></i> &#x2013;
 436   <i>E<sub>rl</sub></i> and <i>S<sub>rr</sub></i> &#x2013;
 437   <i>C<sub>rr</sub></i> &#x2013; <i>E<sub>rr</sub></i>. Both halves
 438   are pushed onto the stack.</li></ul>
 439
 440   The new state is shown in column F.</li>
 441
 442 <li>The topmost curve segment (<i>S<sub>rl</sub></i> &#x2013;
 443 <i>C<sub>rl</sub></i> &#x2013; <i>E<sub>rl</sub></i>) is popped from
 444 the stack.
 445
 446   <ul><li>The recursion level of this segment (stored in
 447   <code>recLevel[2]</code>) is 2, which is <em>not</em> smaller than
 448   the limit 2. Therefore, a <code>SEG_LINETO</code> (from
 449   <i>S<sub>rl</sub></i> to <i>E<sub>rl</sub></i>) is passed to the
 450   consumer.</li></ul>
 451
 452   The new state is shown in column G.</li>
 453
 454 <li>The topmost curve segment (<i>S<sub>rr</sub></i> &#x2013;
 455 <i>C<sub>rr</sub></i> &#x2013; <i>E<sub>rr</sub></i>) is popped from
 456 the stack.
 457
 458   <ul><li>The recursion level of this segment (stored in
 459   <code>recLevel[2]</code>) is 2, which is <em>not</em> smaller than
 460   the limit 2. Therefore, a <code>SEG_LINETO</code> (from
 461   <i>S<sub>rr</sub></i> to <i>E<sub>rr</sub></i>) is passed to the
 462   consumer.</li></ul>
 463
 464   The new state is shown in column H.</li>
 465
 466 <li>The stack is now empty. The FlatteningPathIterator will fetch the
 467 next segment from the base iterator, and process it.</li>
 468
 469 </ol>
 470
 471 <p>In order to split the most recently pushed segment, the
 472 <code>subdivideQuadratic()</code> method passes <code>stack</code>
 473 directly to
 474 <code>QuadCurve2D.subdivide(double[],int,double[],int,double[],int)</code>.
 475 Because the stack grows towards the beginning of the array, no data
 476 needs to be copied around: <code>subdivide</code> will directly store
 477 the result into the stack, which will have the contents shown to the
 478 right.</p>
 479
 480 </body>
 481 </html>