Author Topic: Fixed-Memory Flood Fill Pseudocode  (Read 16399 times)

0 Members and 1 Guest are viewing this topic.

Offline Xeda112358

  • they/them
  • Moderator
  • LV12 Extreme Poster (Next: 5000)
  • ************
  • Posts: 4704
  • Rating: +719/-6
  • Calc-u-lator, do doo doo do do do.
    • View Profile
Re: Fixed-Memory Flood Fill Pseudocode
« Reply #30 on: April 03, 2012, 04:25:53 pm »
Cool ! I wasn't sure if I had explained it well enough :)

Offline MGOS

  • LV6 Super Member (Next: 500)
  • ******
  • Posts: 336
  • Rating: +95/-0
    • View Profile
Re: Fixed-Memory Flood Fill Pseudocode
« Reply #31 on: April 03, 2012, 04:52:37 pm »
Well, do you know what a pxl-test returns outside of the screen? Do I have to do exception handeling right there?

Offline Xeda112358

  • they/them
  • Moderator
  • LV12 Extreme Poster (Next: 5000)
  • ************
  • Posts: 4704
  • Rating: +719/-6
  • Calc-u-lator, do doo doo do do do.
    • View Profile
Re: Fixed-Memory Flood Fill Pseudocode
« Reply #32 on: April 03, 2012, 05:10:50 pm »
yeah, in Axe it returns zero. I wrote my own hex code to make a custom pixel test (it returns 1 if the pixel is off and in bounds, otherwise zero)

Offline MGOS

  • LV6 Super Member (Next: 500)
  • ******
  • Posts: 336
  • Rating: +95/-0
    • View Profile
Re: Fixed-Memory Flood Fill Pseudocode
« Reply #33 on: April 03, 2012, 05:18:26 pm »
That's clever for this use.

Offline Xeda112358

  • they/them
  • Moderator
  • LV12 Extreme Poster (Next: 5000)
  • ************
  • Posts: 4704
  • Rating: +719/-6
  • Calc-u-lator, do doo doo do do do.
    • View Profile
Re: Fixed-Memory Flood Fill Pseudocode
« Reply #34 on: April 03, 2012, 05:27:12 pm »
I don't have enough time to post the code, so I squished some screenies together of the call:

Offline MGOS

  • LV6 Super Member (Next: 500)
  • ******
  • Posts: 336
  • Rating: +95/-0
    • View Profile
Re: Fixed-Memory Flood Fill Pseudocode
« Reply #35 on: April 04, 2012, 04:15:03 pm »
Again, thanks, but I came up with another, also very fast (maybe faster than yours :)) routine for fixed memory flood filling by myself.
It used besides the drawing buffer(s) a stack (L1) and a 768 byte second buffer.
You can imagine that it works like memory swapping on a computer, if the RAM is full, data will be stored on the hard drive instead.
My routine searches iterative for pixels to fill using the stack, but if the stack overflows, it swaps to the other buffer using the slower searching routine.
When the stack empties, the data will be put back on the stack.
Like this I can achieve small areas filled extremely fast and bigger areas also with decent speed.
The only disadvantage is that it uses another 768 byte buffer (L3 when not uing grayscale) and L1 as stack. But I'm able to carry that.

Code: [Select]
:.FLOOD
:Buff(768)→GDB1
:15→A .Coordinates of "paint bucket"
:15→B
:0→S→D→C .Screen buffer size, data buffer size and counting var
:PUS(A,B) .Add the first pixel to stack
:While S+D . as long there's sth in the buffers
:C++
:POP() .Get a pixel
:!If pxl-Test(P,Q) .Test if it's off
:Pxl-On(P,Q) .if yes, turn it on
:P?PUS(P-1,Q) .Put pixels around it on the stack
:P-95?PUS(P+1,Q)
:Q-63?PUS(P,Q+1)
:Q?PUS(P,Q-1)
:End
:C^64??DispGraph .Only display every 64 time; not needed
:ReturnIf getKey(15)
:End
:DispGraph
:Return
:
:Lbl PUS .Push algorithm
:ReturnIf pxl-Test(r1,r2) .only push if the pixel is white
:If D-357 .if stack isn't full yet
:r1→{D*2+L1} .add to stack
:r2→{D*2+1+L1}
:D++ .increment stack pointer
:sub(CHKr,r1,r2) .check if pixel is black on the back buffer, if yes, remove it there
:Else!If pxl-Test(r1,r2,GDB1) .if stack is full, make sure that the pixel isn't in memory yet
:Pxl-On(r1,r2,GDB1) .turn it on on the back buffer
:S++ .increment buffer size
:End
:Return
:
:Lbl POP .Pop algorithm
:If D .if there's something on the stack
:D-- .decremt stack pointer
:{D*2+L1}→P .get the coordinates from the stack
:{D*2+1+L1}→Q
:CHK(P,Q) .check if pixel is black on the back buffer, if yes, remove it there
:Else .if stack empty
:For(Q,0,63 .go on searching the back buffer (slow...)
:For(P,0,95
:If pxl-Test(P,Q,GDB1) .if you got a pixel
:Pxl-Off(P,Q,GDB1) .turn it off
:S-- .decrement the buffer size
:Return .return to main
:End
:End
:End
:End
:Return
:
:Lbl CHK .check algorithm
:If pxl-Test(r1,r2,GDB1) .check if pixel is black on the back buffer
:Pxl-Off(r1,r2,GDB1  .if yes, remove it there
:S-- .decrement the buffer size
:End
:Return
« Last Edit: April 04, 2012, 04:45:16 pm by MGOS »

Offline Xeda112358

  • they/them
  • Moderator
  • LV12 Extreme Poster (Next: 5000)
  • ************
  • Posts: 4704
  • Rating: +719/-6
  • Calc-u-lator, do doo doo do do do.
    • View Profile
Re: Fixed-Memory Flood Fill Pseudocode
« Reply #36 on: April 04, 2012, 04:41:11 pm »
Wow, very nice way to combine the two methods. That should indeed be faster! I was limited to just one 768 byte buffer because I had to use the other two for grayscale. Again, nice o.o

Offline MGOS

  • LV6 Super Member (Next: 500)
  • ******
  • Posts: 336
  • Rating: +95/-0
    • View Profile
Re: Fixed-Memory Flood Fill Pseudocode
« Reply #37 on: April 04, 2012, 04:51:12 pm »
What about using an arbitrary buffer in the program file? I'm gonna have grayscale too, but I think I can afford having that buffer.

Offline Xeda112358

  • they/them
  • Moderator
  • LV12 Extreme Poster (Next: 5000)
  • ************
  • Posts: 4704
  • Rating: +719/-6
  • Calc-u-lator, do doo doo do do do.
    • View Profile
Re: Fixed-Memory Flood Fill Pseudocode
« Reply #38 on: April 04, 2012, 04:56:54 pm »
Yah, and also, if you really wanted to, you could use your method, but instead:
1) Use one buffer for the backup buffer (in case the stack overflows)
2) Use the other two for gray
3) Use some code to figure out how much RAM is left and then create a tempstring (or TempProg or appvar) with the remaining RAM to use as a stack.
Then, if the user has lots of available RAM, their flood filling will be really fast, but in case they don't have enough they won't need to worry.

Offline MGOS

  • LV6 Super Member (Next: 500)
  • ******
  • Posts: 336
  • Rating: +95/-0
    • View Profile
Re: Fixed-Memory Flood Fill Pseudocode
« Reply #39 on: April 04, 2012, 05:02:34 pm »
That's actually an interesting thought...  ::)
Maybe I'll add that later... firstly, my next step is to get the main program working, and then we'll see.
« Last Edit: April 04, 2012, 05:03:24 pm by MGOS »