Re: [Tuxpaint-devel] [Tuxpaint-users] Tux Paint 0.9.27 beta releases

[Bill K. <nb...@so...>]

On Fri, Nov 19, 2021 at 11:31:33PM -0800, Bill Kendrick wrote:
> On Sat, Nov 20, 2021 at 11:14:45AM +0800, ���� wrote:
> > Hi amazing release cycle!
> > 
> > 
> > May I know whether the flood fill issue fixed?
> > I just tested the windows installer 0.9.27 but still crashed. following is windows log:
> <snip>
> 
> Unfortunately, no.  I decided to leave things as-is,
> rather than overhaul the Fill routine and potentially
> break things for a while, and delay a new release. :)

Sorry, I lied! ;-D

  https://sourceforge.net/p/tuxpaint/tuxpaint/ci/5cfc185d77edd075e4ba3d3bb3255aa6c6185869/

First off, I started taking another approach: trying to
improve the existing recursive code.

 * be more conservative when recursively calling the
   flood fill above and below points on the current
   scanline; only do so if we hadn't already done it
   on the previous (to the left) pixel; if that color
   matched, then we'll have already scanned that row
   and found that (adjacent) the pixel anyway

 * reduce how much I drop onto the stack, each call of
   the recursive function sent a LOT of arguments that
   were never changing (or being modified in a global
   way, e.g. the (x1,y1)->(x2,y2) extent of how much
   of the canvas is being updated, or the `touched[]`
   array)

 * don't call the progress bar animation or sound-playing
   (in the end, SDL_Mixer) routines as frequently
   (when it was really busy filling, it did't sound
   right anyway!)

All of these changes allowed me to successfully fill the
starter image Yang and Pere reported as troublesome
("mosaic.svg") in a 3000x2000 window on my Linux laptop!

However, when I ~quadrupled the complexity of the image,
by using the new "Panels" magic tool to duplicate the
image four times, in a 2x2 grid (which of course ends up
overlaid with the original starter image), Tux Paint would
crash for me.  It was recursing about 70,000 times!

But, at this point, I realized the recursive call was
greatly simplified, and I could more easily apply a queue
to the process (versus recursion), aka the "span fill"
algorithm.

So instead of:

  call A(x, y)

  define A() as:
    fill as far left & right on this row as we can

    for each postion "i" we filled (from left to right)
      call A(i, y - 1)
      call A(i, y + 1)

I now do:

  add (x,y) to the queue

  while the queue isn't empty
    get an (x,y) from the queue
    call A(x,y)

  define A() as:
    fill as far left & right on this row as we can

    for each postion "i" we filled (from left to right)
      add (i, y - 1) to the queue
      add (i, y + 1) to the queue

(More or less)


Right now, it DOES eat up a bunch of heap space, by allocating
(and reallocating, to enlarge) the queue structure.  It only frees
it at the end of the fill process.

However, I'll see if I can get it to be smarter, and allow the queue
to shrink, probably by treating it as a stack.  (It doesn't actually
matter whether it's a queue or a stack, in the computer science
meaning of the terms.)

-- 
-bill!
Sent from my computer