Stack Size / Recursive scripts

[Art]

Hi Guys,
I'm trying to implement a 2D recursive flood fill algo found on Wikipedia
in the first example here:
http://en.wikipedia.org/wiki/Flood_fill

I think I've implemented it right for the PSP, but it crashes when this function is called.
I call it with image coordinates well inside the image area, and expect it
to fill the area outside of a wire polygon.

Code: Select all

void floodfill(int x, int y, u32 target, u32 new_color) {

if (getPixelImage(x, y, polygon) != target) {return;}
if (getPixelImage(x, y, polygon) == new_color) {return;}
putPixelImage(new_color, x, y, polygon);

if &#40;x > 1 && x < 479&#41; &#123;
if &#40;y > 1 && y < 271&#41; &#123;
floodfill&#40;x-1, y, 0, 0xFFABCDEF&#41;;
floodfill&#40;x+1, y, 0, 0xFFABCDEF&#41;;
floodfill&#40;x, y+1, 0, 0xFFABCDEF&#41;;
floodfill&#40;x, y-1, 0, 0xFFABCDEF&#41;;
&#125;&#125;

&#125;

I assume from what I read on the net that this is because of stack overflow.

When I add this to my main.c file:
PSP_MAIN_THREAD_STACK_SIZE_KB(sizeinkb); // sizeinkb = 1024, 2048, etc.
The program won't run at all, no matter what value I use.
Could this be used in a thread or am I barking up the wrong tree?

Cheers, Art.

[J.F.]

Your recursion is infinite - look at these two lines:

Code: Select all

floodfill(x-1, y, 0, 0xFFABCDEF);
floodfill(x+1, y, 0, 0xFFABCDEF);

A recursion on the first line there when it causes a recursion on the second line is the exact same pixel as you started with... meaning you're recursion generated the original pixel, which is then fed back in for recursion.

[Art]

Your recursion is infinite - look at these two lines:

I don't follow why you say it is infinite.
I forgot I hard coded the colour in those lines though.. so:

Code: Select all

floodfill(x-1, y, 0, new_color);
floodfill(x+1, y, 0, new_color);

Before it makes it to the same pixel again,
the function should have already returned because a prior IF statement checks if
the colour was already changed for that pixel.

Code: Select all

if (getPixelImage(x, y, polygon) == new_color) {return;} 

[J.F.]

Yes, if the get pixel check does work, that should keep the recursion from being infinite. Better check those routines... maybe the alpha is getting stripped or something similar, which would then make the color check fail which would then allow infinite recursion.

[Art]

I pretty much narrowed it down to stack overflow by limiting the number of times the function can call itself.

If I limit it to 1000 times, it works, and partialy fills the screen
(although 1000 pixels is less than three lines on the PSP screen).

Now since I can't add this line:

Code: Select all

PSP_MAIN_THREAD_STACK_SIZE_KB(fnhuge);

without breaking it, I wonder where the stack size is defined in the first place so I can change it there?
and what is the limit it can be set to?
Art.

[J.F.]

Are you also setting the heap size? You might be using heap size max, which would prevent you from making the stack size larger. Leave enough free memory where you can increase the stack appropriately.

[Art]

I'm not using anything to adjust the heap size.
Should it handle up to 130560 (480x272) recursions?

I found this:
http://psp.jim.sh/pspsdk-doc/pspmoduleinfo_8h.html

Where it looks like this:

Code: Select all

PSP_MAIN_THREAD_STACK_SIZE_KB(size_kb)   unsigned int sce_newlib_stack_kb_size = (size_kb)
PSP_HEAP_SIZE_KB(size_kb)   int sce_newlib_heap_kb_size = (size_kb)

is what you're talking about. What should I set the heap size to?
I find that my programs usually have about 24Mb to play with on a fat
would 20Mb do it?

or to quote yourself

I normally use something like "PSP_HEAP_SIZE_KB(-256);", which means gimme everything except for 256 KB.

EDIT.. bummer, it seems it crashes the app if I include these lines with any value in them.

Art.

[J.F.]

You should be able to use those lines... if you can't, there's something wrong, possibly with your toolchain. How old is the toolchain/where did you get it/how are you running the app?

[Art]

Old :)

But I tried it on a 2008 version and it compiled and ran ok,
then did this:

Code: Select all

PSP_MODULE_INFO("AVec", 0x1000, 1, 0);
PSP_MAIN_THREAD_ATTR(0);
PSP_MAIN_THREAD_STACK_SIZE_KB(1024);
PSP_HEAP_SIZE_KB(-1024); 

and it breaks it :(
It still compiles, but doesn't run.

If I comment out this line
PSP_MAIN_THREAD_ATTR(0);
it runs until it crashes at some stage.

[J.F.]

Code: Select all

PSP_MODULE_INFO("AVec", 0x1000, 1, 0);
PSP_MAIN_THREAD_ATTR(0);
PSP_MAIN_THREAD_STACK_SIZE_KB(1024);
PSP_HEAP_SIZE_KB(-1024); 

That's old kernel mode homebrew... it should be

Code: Select all

PSP_MODULE_INFO("AVec", 0, 1, 0);
PSP_MAIN_THREAD_ATTR(PSP_THREAD_ATTR_USER);
PSP_MAIN_THREAD_STACK_SIZE_KB(1024);
PSP_HEAP_SIZE_KB(-1024); 

and if you want to use the extra memory in the Slim, you need to add to the makefile

Code: Select all

BUILD_PRX = 1
PSP_LARGE_MEMORY = 1

[Jim]

Thought experiment:
If you wanted to fill the entire screen, starting bottom right, then following the recursion in my head I see it first drawing all the way to the left, 480 pixels, then moving up 1 line, then drawing all the way to the right, then repeating. Each time it draws a pixel it puts (at least) 5 words on the stack (params+return address). So that would be 480x272x5x4 bytes needed to do the fill. That's about 2.6Mb of stack space.

The problem is that it's just not a very good algorithm. You need to do more than one pixel per recursion.

Jim

[J.F.]

Or perhaps more constraints on the recursion - maybe only have it recurse over a line at a time. In the end, I think Jim's right - recursion is a bad way to do a flood fill. You might get away with it on a PC where you have nearly infinite memory and a stupidly fast CPU, but such things shouldn't be done on the PSP where you have neither of those.

[Art]

If you wanted to fill the entire screen, starting bottom right, then following the recursion in my head I see it first drawing all the way to the left, 480 pixels, then moving up 1 line, then drawing all the way to the right, then repeating.

Yes, I started at 0,0 and it looked to do that from the top when I limited it to work for only 1000 recursions.

Or perhaps more constraints on the recursion - maybe only have it recurse over a line at a time.

If I'm understanding that right, I think there's an answer there somewhere, but you can't make a line independent.
The algo wouldn't get to the end of a line if it crashed into another color,
and you can't make any judgement about a polygon by looking at it one
line at a time.
One line of a sideways number "9" for example doesn't show you which
part you shouldn't fill.

That way sux

Yeah I know that's about the dumbest way to do it.
I've tried a few other things though,
the queue method and circular buffer in a while loop I couldn't get working.
This is one I like the look of:
http://alienryderflex.com/polygon_fill/
because I could gather the data as the lines for the wire polygon are drawn.