Editing Flood fill (section)

== Span filling ==

[[Image:Smiley fill.gif|right|thumb|212px|Scanline fill using a stack for storage]]

It's possible to optimize things further by working primarily with spans, a row with constant <code>y</code>. The first published complete example works on the following basic principle.<ref name="79Smith" />

# Starting with a seed point, fill left and right. Keep track of the leftmost filled point <code>lx</code> and rightmost filled point <code>rx</code>. This defines the span. 
# Scan from <code>lx</code> to <code>rx</code> above and below the seed point, searching for new seed points to continue with.

As an optimisation, the scan algorithm does not need restart from every seed point, but only those at the start of the next span. Using a [[Stack (abstract data type)|stack]] explores spans depth first, whilst a [[Queue (abstract data type)|queue]] explores spans breadth first.

{{clear}}

 fn '''fill'''(''x'', ''y''):
     if not '''Inside'''(''x'', ''y'') then return
     let ''s'' = new empty stack or queue
     Add (''x'', ''y'') to ''s''
     while ''s'' is not empty:
         Remove an (''x'', ''y'') from ''s''
         let ''lx'' = ''x''
         while '''Inside'''(''lx'' - 1, ''y''):
             '''Set'''(''lx'' - 1, ''y'')
             ''lx'' = ''lx'' - 1
         while '''Inside'''(''x'', ''y''):
             '''Set'''(''x'', ''y'')
             ''x'' = ''x'' + 1
       '''scan'''(''lx'', ''x'' - 1, ''y'' + 1, ''s'')
       '''scan'''(''lx'', ''x'' - 1, ''y'' - 1, ''s'')
 
 fn '''scan'''(''lx'', ''rx'', ''y'', ''s''):
     let ''span_added'' = ''false''
     for ''x'' in ''lx'' .. ''rx'':
         if not '''Inside'''(''x'', ''y''):
             ''span_added'' = ''false''
         else if not ''span_added'':
             Add (''x'', ''y'') to ''s''
             ''span_added'' = ''true''

Over time, the following optimizations were realized:
* When a new scan would be entirely within a grandparent span, it would certainly only find filled pixels, and so wouldn't need queueing.<ref name="79Smith" /><ref name="82Levoy" /><ref name="85Fishkin">{{Cite conference |title=An Analysis and Algorithm for Filling Propagation |last1=Fishkin |first1=Kenneth P |last2=Barsky |first2=Brian A |year=1985 |conference=Computer-Generated Images: The State of the Art Proceedings of Graphics Interface ’85 |pages=56–76 |doi=10.1007/978-4-431-68033-8_6 }}</ref>
* Further, when a new scan overlaps a grandparent span, only the overhangs (U-turns and W-turns) need to be scanned.<ref name="85Fishkin" />
* It's possible to fill while scanning for seeds <ref name="82Levoy" />

The final, combined-scan-and-fill span filler was then published in 1990. In pseudo-code form:<ref name="90Heckbert">{{Cite book |title=Graphics Gems |last=Heckbert |first=Paul S |chapter=IV.10: A Seed Fill Algorithm |pages=275–277 |editor-last=Glassner |editor-first=Andrew S |year=1990 |publisher=Academic Press |isbn=0122861663 }}</ref>

 fn '''fill'''(''x'', ''y''):
     if not '''Inside'''(''x'', ''y'') then return
     let ''s'' = new empty queue or stack
     Add (''x'', ''x'', ''y'', 1) to ''s''
     Add (''x'', ''x'', ''y'' - 1, -1) to ''s''
     while ''s'' is not empty:
         Remove an (''x1'', ''x2'', ''y'', ''dy'') from ''s''
         let ''x'' = ''x1''
         if '''Inside'''(''x'', ''y''):
             while '''Inside'''(''x'' - 1, ''y''):
                 '''Set'''(''x'' - 1, ''y'')
                 ''x'' = ''x'' - 1
             if ''x'' < ''x1'':
                 Add (''x'', ''x1'' - 1, ''y'' - ''dy'', -''dy'') to ''s''
         while ''x1'' <= ''x2'':
             while '''Inside'''(''x1'', ''y''):
                 '''Set'''(''x1'', ''y'')
                 ''x1'' = ''x1'' + 1
             if ''x1'' > ''x'':
                 '''Add''' (''x'', ''x1'' - 1, ''y'' + ''dy'', ''dy'') to ''s''
             if ''x1'' - 1 > ''x2'':
                 '''Add''' (''x2'' + 1, ''x1'' - 1, ''y'' - ''dy'', -''dy'') to ''s''
             ''x1'' = ''x1'' + 1
             while ''x1'' < ''x2'' and not '''Inside'''(''x1'', ''y''):
                 ''x1'' = ''x1'' + 1
             ''x'' = ''x1''

===Advantages===
* 2–8x faster than the pixel-recursive algorithm.
* Access pattern is cache and bitplane-friendly.<ref name="82Levoy" />
* Can draw a horizontal line rather than setting individual pixels.<ref name="82Levoy" />

===Disadvantages===
* Still visits pixels it has already filled. (For the popular algorithm, 3 scans of most pixels. For the final one, only doing extra scans of pixels where there are holes in the filled area.)<ref name="85Fishkin" />
* Not suitable for pattern filling, as it requires pixel test results to change.