Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.c > #144561 > unrolled thread

OT: Flood fill algorithm (Graphics)

Back to article view | Back to comp.lang.c

Contents

  OT: Flood fill algorithm (Graphics) nobody@example.org (Scott) - 2019-06-07 04:02 +0000
    Re: OT: Flood fill algorithm (Graphics) fir <profesor.fir@gmail.com> - 2019-06-06 23:54 -0700
      Re: OT: Flood fill algorithm (Graphics) Malcolm McLean <malcolm.arthur.mclean@gmail.com> - 2019-06-07 07:57 -0700
        Re: OT: Flood fill algorithm (Graphics) nobody@example.org (Scott) - 2019-06-07 16:06 +0000
        Re: OT: Flood fill algorithm (Graphics) jadill33@gmail.com - 2019-06-07 09:56 -0700
    Re: OT: Flood fill algorithm (Graphics) unidef <jon@unidef-systems.com> - 2019-06-10 02:47 -0500
    Re: OT: Flood fill algorithm (Graphics) Peter 'Shaggy' Haywood <phaywood@alphalink.com.au> - 2019-06-13 00:25 +1000

#144561 — OT: Flood fill algorithm (Graphics)

I'm messing around with a flood fill function I wrote a long time ago.

Flood fills can be seductively simple, until you find yourself
cornered with a recursive algorithm that chews through memory like
crazy. So I wrote mine to be non-recursive and use as little memory as
possible in the form of a simple queue.

In my notes I wrote that I'd never seen it need a queue bigger than
twice the width of the raster being painted. I recall the truth of
that, but I know more now than I did then. I have better ideas on
generating pathological test cases, and I can test with much larger
rasters than were feasible in the day.

Point is, I'm asking you guys for ideas on hard cases for testing a
flood fill. I've done the usual (backgammon board, A/B dots, random
dots) and found a number of test patterns on the web, and haven't
found one that gets anywhere near using 100% of the queue.

The best one I got so far is a one-pixel Hilbert curve, which pushes
queue utilization up really fast. At 512x512 it breaks the 2*width
limit by 7%, and at 8192x8192 it needs a queue of almost 11*width to
run. It seems to fall into a pattern of needing about 50% more queue
space for every doubling of width. It's an interesting result.

[toc] | [next] | [standalone]

#144566

W dniu piątek, 7 czerwca 2019 06:00:58 UTC+2 użytkownik Scott napisał:
> I'm messing around with a flood fill function I wrote a long time ago.
> 
> Flood fills can be seductively simple, until you find yourself
> cornered with a recursive algorithm that chews through memory like
> crazy. So I wrote mine to be non-recursive and use as little memory as
> possible in the form of a simple queue.
> 
> In my notes I wrote that I'd never seen it need a queue bigger than
> twice the width of the raster being painted. I recall the truth of
> that, but I know more now than I did then. I have better ideas on
> generating pathological test cases, and I can test with much larger
> rasters than were feasible in the day.
> 
> Point is, I'm asking you guys for ideas on hard cases for testing a
> flood fill. I've done the usual (backgammon board, A/B dots, random
> dots) and found a number of test patterns on the web, and haven't
> found one that gets anywhere near using 100% of the queue.
> 
> The best one I got so far is a one-pixel Hilbert curve, which pushes
> queue utilization up really fast. At 512x512 it breaks the 2*width
> limit by 7%, and at 8192x8192 it needs a queue of almost 11*width to
> run. It seems to fall into a pattern of needing about 50% more queue
> space for every doubling of width. It's an interesting result.

good you ask on graphics topics imo (as they are ok imo) but this flod fill is of
relatively small practical usage..almost nobody uses it

[toc] | [prev] | [next] | [standalone]

#144597

On Friday, 7 June 2019 07:55:07 UTC+1, fir  wrote:
>
> good you ask on graphics topics imo (as they are ok imo) but this 
> flod fill is of relatively small practical usage..almost nobody uses it
>
It's not used much for drawing any longer as it requires colour regions
to be flat-shaded and not anti-aliased, which for most uses is too 
simple. But it's still important for binary image processing, largely
for labelling regions of the binary image.

[toc] | [prev] | [next] | [standalone]

#144600

On Fri, 7 Jun 2019 07:57:05 -0700 (PDT), Malcolm McLean
<malcolm.arthur.mclean@gmail.com> wrote:

>On Friday, 7 June 2019 07:55:07 UTC+1, fir  wrote:
>>
>> good you ask on graphics topics imo (as they are ok imo) but this 
>> flod fill is of relatively small practical usage..almost nobody uses it
>>
>It's not used much for drawing any longer as it requires colour regions
>to be flat-shaded and not anti-aliased, which for most uses is too 
>simple. But it's still important for binary image processing, largely
>for labelling regions of the binary image.

Just so. Even for graphics, it's not a huge problem to accomodate a
"fuzzy" match of HSV color characteristics.

It's also been on my mind that a raster image is a special case of an
undirected graph, and *that* is interesting. It gets me thinking on
how I'd approach a flood algorithm aimed at an arbitrarily complex
N-connected graph. A raster is a nice way to visualize how it works in
a limited space.

[toc] | [prev] | [next] | [standalone]

#144603

On Friday, June 7, 2019 at 10:57:21 AM UTC-4, Malcolm McLean wrote:
> On Friday, 7 June 2019 07:55:07 UTC+1, fir  wrote:
> >
> > good you ask on graphics topics imo (as they are ok imo) but this 
> > flod fill is of relatively small practical usage..almost nobody uses it
> >
> It's not used much for drawing any longer as it requires colour regions
> to be flat-shaded and not anti-aliased, which for most uses is too 
> simple. But it's still important for binary image processing, largely
> for labelling regions of the binary image.

I have seen binary flood fills in image segmentation.  Doctor or algorithm outlines anatomy on several slices of a CT or MRI, and a flood fill creates
a pixelated area or volume of said anatomy.

Best regards,
John D.

[toc] | [prev] | [next] | [standalone]

#144691

Scott <nobody@example.org> wrote:
> I'm messing around with a flood fill function I wrote a long time ago.
> 
> Flood fills can be seductively simple, until you find yourself
> cornered with a recursive algorithm that chews through memory like
> crazy. So I wrote mine to be non-recursive and use as little memory as
> possible in the form of a simple queue.
> 
> In my notes I wrote that I'd never seen it need a queue bigger than
> twice the width of the raster being painted. I recall the truth of
> that, but I know more now than I did then. I have better ideas on
> generating pathological test cases, and I can test with much larger
> rasters than were feasible in the day.
> 
> Point is, I'm asking you guys for ideas on hard cases for testing a
> flood fill. I've done the usual (backgammon board, A/B dots, random
> dots) and found a number of test patterns on the web, and haven't
> found one that gets anywhere near using 100% of the queue.
> 
> The best one I got so far is a one-pixel Hilbert curve, which pushes
> queue utilization up really fast. At 512x512 it breaks the 2*width
> limit by 7%, and at 8192x8192 it needs a queue of almost 11*width to
> run. It seems to fall into a pattern of needing about 50% more queue
> space for every doubling of width. It's an interesting result.
> 
> 

I’m not that great at modern math, but don’t be afraid of using
multidimensional arrays when drawing. If you’re afraid of memory usage, map
it to swap

[toc] | [prev] | [next] | [standalone]

#144934

Groovy hepcat Scott was jivin' in comp.lang.c on Fri, 7 Jun 2019 02:02
pm. It's a cool scene! Dig it.

> I'm messing around with a flood fill function I wrote a long time ago.
> 
> Flood fills can be seductively simple, until you find yourself
> cornered with a recursive algorithm that chews through memory like
> crazy. So I wrote mine to be non-recursive and use as little memory as
> possible in the form of a simple queue.

  Years ago I wrote a flood fill that was partially recursive. It filled
a line at a time iteratively, first finding the start and end of the
line. But then it visited each pixel in the line checking that the
pixel directly above was the same colour as the area to be filled, and
recursing at the pixel above. Then it did the same for the pixel below.
Or something like that. It's been a while, so the ol' memory may have a
parity error or two.
  This algorithm correctly filled anything I threw at it. It was a very
simple single colour fill, though.

-- 


----- Dig the NEW and IMPROVED news sig!! -----


-------------- Shaggy was here! ---------------
              Ain't I'm a dawg!!

[toc] | [prev] | [standalone]

Back to top | Article view | comp.lang.c

csiph-web