From kde-devel  Mon Dec 11 18:16:53 2000
From: John Califf <jcaliff () compuzone ! net>
Date: Mon, 11 Dec 2000 18:16:53 +0000
To: kde-devel
Subject: Re: recursion, stacksize & linux
X-MARC-Message: https://marc.info/?l=kde-devel&m=97656977232070
MIME-Version: 1
Content-Type: multipart/mixed; boundary="--------------2620FE55F08298173CFD89BA"

This is a multi-part message in MIME format.
--------------2620FE55F08298173CFD89BA
Content-Type: text/plain; charset=us-ascii
Content-Transfer-Encoding: 7bit

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
--------------2620FE55F08298173CFD89BA
Content-Type: text/plain; charset=us-ascii;
 name="recurse.txt"
Content-Transfer-Encoding: 7bit
Content-Disposition: inline;
 filename="recurse.txt"

// 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

--------------2620FE55F08298173CFD89BA--

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