 |
Author |
Topic: getting stuck in a loop (StackOverflowError) (Read 2963 times) |
|
mKoser
 
|
getting stuck in a loop (StackOverflowError)
« on: Apr 1st, 2005, 5:29pm » |
|
i am trying to do a simple flood-fill sketch. so far everything is working as it should, except, when i try and fill large areas, processing throws an error:
Quote:
Exception occurred during event dispatching:
java.lang.StackOverflowError
<<no stack trace available>>
|
|
i imagine it's because the handler (which is referring to itself) get's stuck running the code when there are too many pixels that wants to run the handler.
this following code never get's the error (since the areas will always be small enough for it to handle):
Code:
// MIKKEL CRONE KOSER
// BEYONDTHREE.COM
// FLOOD_FILL SKETCH
// APRIL 2005
//
// CLICK TO FLOOD_FILL AREAS !!!
//
color myFill, bound;
void setup()
{
size(100, 100);
rectMode(CENTER_DIAMETER);
noFill();
drawRandomBoxes();
myFill = color((int)random(100, 200), (int)random(100, 200), 0);
bound = color(0, 0, 0);
}
void loop()
{
}
void mousePressed()
{
fillFast(mouseX, mouseY, myFill);
myFill = color((int)random(100, 200), (int)random(100, 200), 0);
}
public void fillFast(int x, int y, int fill)
{
if ((x < 0) || (x >= width)) return;
if ((y < 0) || (y >= height)) return;
int old = (int)(get(x, y));
if (old == fill) return;
setPixel( x, y, myFill );
fillEast(x+1, y, fill, old);
fillSouth(x, y+1, fill, old);
fillWest(x-1, y, fill, old);
fillNorth(x, y-1, fill, old);
}
private void fillEast(int x, int y, int fill, int old)
{
if (x >= width) return;
if ((int)(get(x, y)) == old) {
setPixel( x, y, myFill );
fillEast(x+1, y, fill, old);
fillSouth(x, y+1, fill, old);
fillNorth(x, y-1, fill, old);
}
}
private void fillSouth(int x, int y, int fill, int old)
{
if (y >= height) return;
if ((int)(get(x, y)) == old) {
setPixel( x, y, myFill );
fillEast(x+1, y, fill, old);
fillSouth(x, y+1, fill, old);
fillWest(x-1, y, fill, old);
}
}
private void fillWest(int x, int y, int fill, int old)
{
if (x < 0) return;
if ((int)(get(x, y)) == old) {
setPixel( x, y, myFill );
fillSouth(x, y+1, fill, old);
fillWest(x-1, y, fill, old);
fillNorth(x, y-1, fill, old);
}
}
private void fillNorth(int x, int y, int fill, int old)
{
if (y < 0) return;
if ((int)(get(x, y)) == old) {
setPixel( x, y, myFill );
fillEast(x+1, y, fill, old);
fillWest(x-1, y, fill, old);
fillNorth(x, y-1, fill, old);
}
}
public void setPixel(int x, int y, int col){
set(x, y, myFill);
}
public void drawRandomBoxes(){
for(int i=0; i<30; i++){
int x = (int)random(0, width);
int y = (int)random(0, height);
int w = (int)random(20, 100);
int h = (int)random(20, 100);
push();
rotateZ(random(PI));
rect(x, y, w, h);
pop();
}
}
|
|
...however...
if you change the size of the sketch to...
Code:
...or bigger, and click on a large area, the error will occur.
****
I am thinking I should go down the try() catch() route, but when i tried, processing just crashed... I could also capture the last coulered pixel, and then re-initiate the process when the handler gets stuck (faking the mouse click with the latest recorded pixel-change) but this seems to be a silly way of doing it.
so, any help, pointers, suggestions are more than welcome! 
thanks,
Mikkel
|
mikkel crone koser | www.beyondthree.com | http://processing.beyondthree.com
|
|
|
mKoser
|
Re: getting stuck in a loop (StackOverflowError)
« Reply #1 on: Apr 1st, 2005, 5:36pm » |
|
and here's my try() catch() attempt ... I'm avoiding the error now, but my flood_filling stops ...
Code:
// MIKKEL CRONE KOSER
// BEYONDTHREE.COM
// FLOOD_FILL SKETCH
// APRIL 2005
color myFill, bound;
void setup()
{
size(200, 200);
rectMode(CENTER_DIAMETER);
noFill();
drawRandomBoxes();
myFill = color((int)random(100, 200), (int)random(100, 200), 0);
bound = color(0, 0, 0);
}
void loop()
{
}
void mousePressed()
{
fillFast(mouseX, mouseY, myFill);
myFill = color((int)random(100, 200), (int)random(100, 200), 0);
}
public void fillFast(int x, int y, int fill)
{
try{
if ((x < 0) || (x >= width)) return;
if ((y < 0) || (y >= height)) return;
int old = (int)(get(x, y));
if (old == fill) return;
setPixel( x, y, myFill );
fillEast(x+1, y, fill, old);
fillSouth(x, y+1, fill, old);
fillWest(x-1, y, fill, old);
fillNorth(x, y-1, fill, old);
}
catch(StackOverflowError ex){
println("HELP I'M DYING!");
return;
}
}
private void fillEast(int x, int y, int fill, int old)
{
if (x >= width) return;
if ((int)(get(x, y)) == old) {
setPixel( x, y, myFill );
fillEast(x+1, y, fill, old);
fillSouth(x, y+1, fill, old);
fillNorth(x, y-1, fill, old);
}
}
private void fillSouth(int x, int y, int fill, int old)
{
if (y >= height) return;
if ((int)(get(x, y)) == old) {
setPixel( x, y, myFill );
fillEast(x+1, y, fill, old);
fillSouth(x, y+1, fill, old);
fillWest(x-1, y, fill, old);
}
}
private void fillWest(int x, int y, int fill, int old)
{
if (x < 0) return;
if ((int)(get(x, y)) == old) {
setPixel( x, y, myFill );
fillSouth(x, y+1, fill, old);
fillWest(x-1, y, fill, old);
fillNorth(x, y-1, fill, old);
}
}
private void fillNorth(int x, int y, int fill, int old)
{
if (y < 0) return;
if ((int)(get(x, y)) == old) {
setPixel( x, y, myFill );
fillEast(x+1, y, fill, old);
fillWest(x-1, y, fill, old);
fillNorth(x, y-1, fill, old);
}
}
public void setPixel(int x, int y, int col){
set(x, y, myFill);
}
public void drawRandomBoxes(){
for(int i=0; i<30; i++){
int x = (int)random(0, width);
int y = (int)random(0, height);
int w = (int)random(20, 100);
int h = (int)random(20, 100);
push();
rotateZ(random(PI));
rect(x, y, w, h);
pop();
}
}
|
|
is there a way to manually "clear the stack" (whatever that is) so the catch() can re-initiate the filling where it stopped?
+ mikkel
|
mikkel crone koser | www.beyondthree.com | http://processing.beyondthree.com
|
|
|
fry
|
Re: getting stuck in a loop (StackOverflowError)
« Reply #2 on: Apr 2nd, 2005, 2:30am » |
|
i think the stack should be fairly enormous and that it should be able to do a flood fill just fine, and unfortunately there isnt' really a away to clear it out...
then again, i think there are better ways (faster) of doing flood fill... it's useful to explain recursion, but in actuality i think it winds up being total overkill. you might do a quick google search for a good algorithm and let us know what you come up with.
|
|
|
|
|
mKoser
|
Re: getting stuck in a loop (StackOverflowError)
« Reply #3 on: Apr 2nd, 2005, 10:53am » |
|
ok, thanks ben.
i've re-Googled and found a better approach... the source code has comments all the way through, so i'll skip the introduction.
Code:
// MIKKEL CRONE KOSER
// BEYONDTHREE.COM
// FLOOD_FILL SKETCH *array-style
// APRIL 2005
void setup(){
size(400, 400);
background(255);
noFill();
drawRandomBoxes();
}
void loop(){
}
void mousePressed(){
floodFill(mouseX, mouseY, color((int)random(100, 200), (int)random(100, 200), 0));
}
// ******* FLOOD FILL *********
// original by Mark Wutka ( http://docs.rinet.ru/UJ11/ch31.htm )
// modified for processing by Mikkel Crone Koser ( www.beyondthree.com )
//
// floodFill starts at a particular x and y coordinate and fills it, and all
// the surrounding pixels with a color. It doesn't paint over black pixels,
// so they represent the borders of the fill.
// The easiest way to code a flood fill is by doing it recursively - you
// call flood fill on a pixel, color that pixel, then it calls flood fill
// on each surrounding pixel and so on. Unfortunately, that usually causes
// stack overflows since recursion is pretty expensive.
// This routine uses an alternate method. It makes a queue of pixels that
// it still has to fill. It takes a pixel off the head of the queue and
// colors the pixels around it, then adds those pixels to the queue. In other
// words, a pixel is really added to the queue after it has been colored.
// If a pixel has already been colored, it is not added, so eventually, it
// works the queue down until it is empty.
public void floodFill(int x, int y, int col)
{
// If the pixel we are starting with is already black, we won't paint
if (get(x, y) == (int)color(0,0,0)){
return;
}
// Create the pixel queue. Assume the worst case where every pixel in the
// image may be in the queue.
int pixelQueue[] = new int[width * height];
int pixelQueueSize = 0;
// Add the start pixel to the queue (we created a single array of ints,
// even though we are enqueuing two numbers. We put the y value in the
// upper 16 bits of the integer, and the x in the lower 16. This gives
// a limit of 65536x65536 pixels, that should be enough.)
pixelQueue[0] = (y << 16) + x;
pixelQueueSize = 1;
// Color the start pixel.
set(x, y, col);
// Keep going while there are pixels in the queue.
while (pixelQueueSize > 0){
// Get the x and y values of the next pixel in the queue
x = pixelQueue[0] & 0xffff;
y = (pixelQueue[0] >> 16) & 0xffff;
// Remove the first pixel from the queue. Rather than move all the
// pixels in the queue, which would take forever, just take the one
// off the end and move it to the beginning (order doesn't matter here).
pixelQueueSize--;
pixelQueue[0] = pixelQueue[pixelQueueSize];
// If we aren't on the left side of the image, see if the pixel to the
// left has been painted. If not, paint it and add it to the queue.
if (x > 0) {
if ((get(x-1, y) != (int)color(0,0,0)) &&
(get(x-1, y) != col))
{
set(x-1, y, col);
pixelQueue[pixelQueueSize] =
(y << 16) + x-1;
pixelQueueSize++;
}
}
// If we aren't on the top of the image, see if the pixel above
// this one has been painted. If not, paint it and add it to the queue.
if (y > 0) {
if ((get(x, y-1) != (int)color(0,0,0)) &&
(get(x, y-1) != col))
{
set(x, y-1, col);
pixelQueue[pixelQueueSize] =
((y-1) << 16) + x;
pixelQueueSize++;
}
}
// If we aren't on the right side of the image, see if the pixel to the
// right has been painted. If not, paint it and add it to the queue.
if (x < width-1) {
if ((get(x+1, y) != (int)color(0,0,0)) &&
(get(x+1, y) != col))
{
set(x+1, y, col);
pixelQueue[pixelQueueSize] =
(y << 16) + x+1;
pixelQueueSize++;
}
}
// If we aren't on the bottom of the image, see if the pixel below
// this one has been painted. If not, paint it and add it to the queue.
if (y < height-1) {
if ((get(x, y+1) != (int)color(0,0,0)) &&
(get(x, y+1) != col))
{
set(x, y+1, col);
pixelQueue[pixelQueueSize] =
((y+1) << 16) + x;
pixelQueueSize++;
}
}
}
}
void drawRandomBoxes(){
for(int i=0; i<30; i++){
int x = (int)random(0, width);
int y = (int)random(0, height);
int w = (int)random(40, 400);
int h = (int)random(40, 400);
push();
rotateZ(random(PI));
rect(x, y, w, h);
pop();
}
}
|
|
+ mikkel
|
mikkel crone koser | www.beyondthree.com | http://processing.beyondthree.com
|
|
|
|
