[prev in list] [next in list] [prev in thread] [next in thread] 

List:       kde-devel
Subject:    Re: recursion, stacksize & linux
From:       John Califf <jcaliff () compuzone ! net>
Date:       2000-12-11 18:16:53
[Download RAW message or body]

David van Hoose wrote:
> 
> John Califf wrote:
> >
> How about transforming the recursive function to a loop?
> You don't have to worry about overruning the systems memory.
> And think about it. It will run faster too.
> If you need help with this, I'll take a look at the code.
> 
> --
> -Dave
> 
> >> Visit http://master.kde.org/mailman/listinfo/kde-devel#unsub to unsubscribe <<

I will probably use the approach taken in the gtk app (gpaint) which
allocates a buffer on the heap and uses it as a fake stack to avoid
overfow problems.  It's actually the same one I'm now using slightly
modified.  It's proven to work.

You can look at the two routines (attached) in the file recurse.txt if
you want, but changing recursion to a loop is not always so simple. 
This is what I tried with the quadrants approach.  I'd think this is a
well known problem is graphics programming.  These kinds of things are
very interesting and I will be checking out some books to do some more
research on related algorithms needed for krayon.

Thanks for all your insights into this.

John
["recurse.txt" (text/plain)]

// from krayon

void Fill::drawFlood(KisLayer *lay, QRect & layerRect, int x, int y)
{
    // make sure desired pixel is in bounds - can operate on 
    // selection as well as entire image, so layerRect is not
    // always same as imageExtents (later)
    if(!layerRect.contains(x, y)) 
        return;

    // pixel is not same color as source pixel color, return
    if((lay->pixel(0, x, y) != sRed)
    || (lay->pixel(1, x, y) != sGreen) 
    || (lay->pixel(2, x, y) != sBlue))
    {
        return;
    }

    // pixel is already the desired (new) color, return
    if((lay->pixel(0, x, y) == nRed)
    && (lay->pixel(1, x, y) == nGreen) 
    && (lay->pixel(2, x, y) == nBlue))
    {
        return;
    }

    // pixel is same as original color, set it to new color
    lay->setPixel(0, x, y, nRed);
    lay->setPixel(1, x, y, nGreen);
    lay->setPixel(2, x, y, nBlue);
    
    if(layerRect.contains(x, y-1)) 
        drawFlood(lay, layerRect, x, y-1);
    if(layerRect.contains(x, y+1))         
        drawFlood(lay, layerRect, x, y+1);
    if(layerRect.contains(x-1, y))         
        drawFlood(lay, layerRect, x-1, y);
    if(layerRect.contains(x+1, y))         
        drawFlood(lay, layerRect, x+1, y);
}

// from gpaint

#define STACKSIZE 10000

/* algorithm based on SeedFill.c from GraphicsGems 1 */

static void flood_fill(struct fillinfo *info, int x, int y)
{
   struct fillpixelinfo stack[STACKSIZE];
   struct fillpixelinfo * sp = stack;
   
   int l, x1, x2, dy;
   
#define PUSH(py, pxl, pxr, pdy) \
{  struct fillpixelinfo *p = sp;\
   if (((py) + (pdy) >= 0) && ((py) + (pdy) < info->height))\
   {\
      p->y = (py);\
      p->xl = (pxl);\
      p->xr = (pxr);\
      p->dy = (pdy);\
      sp++; \
   }\
}
   
   
#define POP(py, pxl, pxr, pdy) \
{\
   sp--;\
   (py) = sp->y + sp->dy;\
   (pxl) = sp->xl;\
   (pxr) = sp->xr;\
   (pdy) = sp->dy;\
}

      
   if ((x >= 0) && (x < info->width) && (y >= 0) && (y < info->height))
   {
      if ((info->or == info->r) && (info->og == info->g) && (info->ob == info->b))
         return;
      
      PUSH(y, x, x, 1);
      PUSH(y + 1, x, x, -1);
      	 
      while (sp > stack)	
      {
         POP(y, x1, x2, dy);
	 for (x = x1; (x >= 0) && is_old_pixel_value(info, x, y); x--)
	    set_new_pixel_value(info, x, y);
	 if (x >= x1) goto skip;
	 l = x + 1;
	 if (l < x1)
	    PUSH(y, l, x1 - 1, -dy);
	 x = x1 + 1;
	 do
	 {
	    for (; (x < info->width) && is_old_pixel_value(info, x, y); x++)
	       set_new_pixel_value(info, x, y);
	    
	    PUSH(y, l, x - 1, dy);
	    if (x > x2 + 1)
	       PUSH(y, x2 + 1, x - 1, -dy);
skip:
            for (x++; x <= x2 && !is_old_pixel_value(info, x, y); x++) 
	       ;
	    
	    l = x;
	 } while (x <= x2);
	 	       
	
      }
   }

#undef POP
#undef PUSH

>> Visit http://master.kde.org/mailman/listinfo/kde-devel#unsub to unsubscribe <<


[prev in list] [next in list] [prev in thread] [next in thread]