Re: looking for a pixel flood fill routine
Posted: Wed Jan 19, 2022 9:52 pm
forum.defence-force.org
Defence Force forums
https://forum.defence-force.net/
looking for a pixel flood fill routine
Page 3 of 4
Re: looking for a pixel flood fill routine
Posted: Wed Jan 19, 2022 10:53 pm
hehe Nice improvement 
Re: looking for a pixel flood fill routine
Posted: Thu Jan 20, 2022 7:21 pm
I'm now down to "238", but running a bit out of gaz, so sharing the current code.
No guarantee there are no bugs, and the buffer sizes is not adjusted, so it's just so you can play with it.
in the C file there's a #ifdef that can be used to swap between the circle test and an actual picture with complicated patterns.
Don't assume that because the circle works that you did not break anything, test on the image
It started from Geoff Phillips BASIC program (https://library.defence-force.org/index ... =007084743) which I converted to C, and then I converted the C to assembler and from there started to hack around.
I never managed to get Geoff assembler version to work, and his uses the actual CPU stack in page 1, disables interrupts, etc... for mine I choose instead to just use a separate array in normal memory, and I'm not disabling interrupts so technically that would speed up mine by about 20%
I've used a many hacks, mostly reusing existing registers values across "functions", so if you just swap code around it will mostly fail because registers are expected to have specific values.
I also did boundary checking by patching the tables: Instead of checking if Y is out of the screen, I just patched the last 56 pointers of the HIRES address tables to point to a fake scanline with only FF values, this way the filler does not crash, and it detects the values as "pixel is filled".
I dealt with the +/-1 values by instead adding an offset in the address of the tables, but when doing -1 you then start to cross boundaries, which adds clock cycles penalties, so I shifted all the tables by one byte.
Feel free to ask questions, and if somebody knows how to import a picture in Lorigraph and Masterpaint, would be interesting to measure how long it takes to fill my test picture in these two programs!
No guarantee there are no bugs, and the buffer sizes is not adjusted, so it's just so you can play with it.
in the C file there's a #ifdef that can be used to swap between the circle test and an actual picture with complicated patterns.
Don't assume that because the circle works that you did not break anything, test on the image
Code: Select all
#if 1
memcpy((unsigned char*)0xa000,LabelPicture,8000);
#else
curset(120,100,3);
circle(50,1);
#endif
I never managed to get Geoff assembler version to work, and his uses the actual CPU stack in page 1, disables interrupts, etc... for mine I choose instead to just use a separate array in normal memory, and I'm not disabling interrupts so technically that would speed up mine by about 20%
I've used a many hacks, mostly reusing existing registers values across "functions", so if you just swap code around it will mostly fail because registers are expected to have specific values.
I also did boundary checking by patching the tables: Instead of checking if Y is out of the screen, I just patched the last 56 pointers of the HIRES address tables to point to a fake scanline with only FF values, this way the filler does not crash, and it detects the values as "pixel is filled".
I dealt with the +/-1 values by instead adding an offset in the address of the tables, but when doing -1 you then start to cross boundaries, which adds clock cycles penalties, so I shifted all the tables by one byte.
Feel free to ask questions, and if somebody knows how to import a picture in Lorigraph and Masterpaint, would be interesting to measure how long it takes to fill my test picture in these two programs!
- flood_fill_test.png (3.06 KiB) Viewed 4209 times
Re: looking for a pixel flood fill routine
Posted: Sat Jan 29, 2022 7:43 pm
I've done a bit more work on the flood fill routine, testing by comparing with The Hobbit, the "hidden path with trolls foot prints" goes from 1 minute to 6 seconds (so I guess it's a 10x factor).
Edit: Here is the source code for the ones who want to play, still work in progress, but cleaner than the previous version.
Edit: Here is the source code for the ones who want to play, still work in progress, but cleaner than the previous version.
Re: looking for a pixel flood fill routine
Posted: Sat Jan 29, 2022 9:16 pm
Wow nice!
The Hobbit would have been more player-friendly at such a speed! (from memory, the program was already quite big though, not sure there would have been room for improvement)
The Hobbit would have been more player-friendly at such a speed! (from memory, the program was already quite big though, not sure there would have been room for improvement)
Re: looking for a pixel flood fill routine
Posted: Thu Feb 10, 2022 8:57 pm
Someone signaled that there was an issue with the flood fill, but it was a user error, so I guess the next step is to properly document all that and make it part of the OSDK:
Re: looking for a pixel flood fill routine
Posted: Sat Feb 12, 2022 5:50 pm
I started comparing the algorithm, and it looks like the best one is Master Paint!
Re: looking for a pixel flood fill routine
Posted: Sat Feb 12, 2022 6:05 pm
Mmmmh so that means I can happily forget resuming my attempt at de-assembling Lorigraph, and we should focus on Master Paint instead?
Well maybe both could be interesting anyway, for instance if Lorigraph one is smaller in code size. Sigh.
BTW, where's Goyo? I wonder if he didn't want filling routines for his excellent tool OricHir.
Re: looking for a pixel flood fill routine
Posted: Sat Feb 12, 2022 6:18 pm
Well, it's always interesting to know the various ways things are implemented, for all we know, it may be that Lorigraph routines has a better algorithm but the Master Paint assembler code is more optimized.
I'm currently tracing Master Paint, from what I found so far:
- $500 contains a 8000 bytes copy of the original picture, it's used to do the pattern filling (by doing the pixel checks there)
- $5400 is a 256 bytes tables of X modulo 6
- $5500 is the X divided by 6 table
- $5000 is where the fill code actually starts, and by a SEI (which makes sense for performance).
I'm currently tracing Master Paint, from what I found so far:
- $500 contains a 8000 bytes copy of the original picture, it's used to do the pattern filling (by doing the pixel checks there)
- $5400 is a 256 bytes tables of X modulo 6
- $5500 is the X divided by 6 table
- $5000 is where the fill code actually starts, and by a SEI (which makes sense for performance).
Re: looking for a pixel flood fill routine
Posted: Sun Feb 13, 2022 9:55 am
From what I see so far, Master Paint works on bytes three by three, by storing them temporarily in zero page, then when it's done write them back to the screen memory.
I'm still trying to figure out how that all work together, but here are the routines:
Rewrite:
Load:
Pointer computation
I'm still trying to figure out how that all work together, but here are the routines:
Rewrite:
Code: Select all
subroutine_rewrite_bytes
51AD 20 E8 51 JSR subroutine_compute_addr ; $51E8
51B0 C9 FF CMP #$FF
51B2 F0 12 BEQ skip_rewrite_bytes ; $51C6
51B4 C8 INY
51B5 A5 04 LDA zp_mod_6_value ; $04
51B7 91 00 STA (zp_ptr_image),Y ; $00
51B9 C8 INY
51BA A5 05 LDA zp_write_value_2 ; $05
51BC 91 00 STA (zp_ptr_image),Y ; $00
51BE C8 INY
51BF A5 06 LDA zp_write_value_3 ; $06
51C1 91 00 STA (zp_ptr_image),Y ; $00
51C3 98 TYA
51C4 95 68 STA $68,X
skip_rewrite_bytes
51C6 60 RTS Load:
Code: Select all
subroutine_load_bytes
51C7 A5 6A LDA $6A
51C9 0A ASL
51CA A9 00 LDA #0
51CC B0 02 BCS $51D0
51CE A9 01 LDA #1
51D0 85 6E STA $6E
51D2 20 E8 51 JSR subroutine_compute_addr ; $51E8
51D5 B1 00 LDA (zp_ptr_image),Y ; $00
51D7 85 60 STA $60
51D9 88 DEY
51DA B1 00 LDA (zp_ptr_image),Y ; $00
51DC 85 61 STA $61
51DE 88 DEY
51DF B1 00 LDA (zp_ptr_image),Y ; $00
51E1 85 67 STA $67
51E3 88 DEY
51E4 98 TYA
51E5 95 68 STA $68,X
51E7 60 RTS Pointer computation
Code: Select all
subroutine_compute_addr
51E8 A9 00 LDA #0
51EA 85 00 STA zp_ptr_image_low ; $00
51EC A6 6E LDX $6E
51EE 18 CLC
51EF A9 56 LDA #$56
51F1 65 6E ADC $6E
51F3 85 01 STA zp_ptr_image_high ; $01
51F5 B5 68 LDA $68,X
51F7 A8 TAY
51F8 60 RTS Re: looking for a pixel flood fill routine
Posted: Sun Feb 13, 2022 8:10 pm
Master Paint's routine is very complicated
So I took a pause, and instead converted the one at the bottom of this page.
The results are promising, we basically get about the speed of the Master Paint routine (ok, I only tested on two pictures), and the code is only 194 bytes long (plus the tables 1280 bytes).
So I took a pause, and instead converted the one at the bottom of this page.
The results are promising, we basically get about the speed of the Master Paint routine (ok, I only tested on two pictures), and the code is only 194 bytes long (plus the tables 1280 bytes).
Re: looking for a pixel flood fill routine
Posted: Mon Feb 14, 2022 9:32 pm
I managed to get a bit faster than Master Paint, and the code is now even more compact (141 bytes), while removing the need for my two 128 bytes stack arrays for X and Y coordinates (used the normal cpu stack with PHA/PLA instead)
Re: looking for a pixel flood fill routine
Posted: Tue Feb 15, 2022 9:57 am
Great news. It looks like some wizard coding is being made here
Do we have some kind of ASM code database or wiki, where one could search for classical routines?
Could be interesting.
Do we have some kind of ASM code database or wiki, where one could search for classical routines?
Could be interesting.
Re: looking for a pixel flood fill routine
Posted: Tue Feb 15, 2022 10:28 am
Well, we could add things like classic Master Paint, Genius, etc... in the Defence Force wiki, but regarding "classical routines", these things are so close to the hardware layout that they are really not usable from a system to another, like for example, for all intent and purpose, the Oric HIRES mode is actually monochrome, while other machines like the C64 or the Amstrad CPC do have actual different bit patterns for different colors in the pixel cells.
If you want a comprehensive list of most algorithms, the Wikipedia article is pretty good, as well as that page.
Re: looking for a pixel flood fill routine
Posted: Tue Feb 15, 2022 10:39 am
Actually I was going a bit off topic, and thinking about a specific Oric-oriented routines repository or whatever (could be a PDF! )
So that beginners or occasional ASM coders (like me ) could try and use, or get inspired by.
For instance a few years ago I found (on the internet) a compact and fast conversion routine to display hexadecimal values. Anyone can find it by doing some research, but it took me a wile to find it, and having them in a single place could be cool.
Well, off-topic anyway
So that beginners or occasional ASM coders (like me
) could try and use, or get inspired by.For instance a few years ago I found (on the internet) a compact and fast conversion routine to display hexadecimal values. Anyone can find it by doing some research, but it took me a wile to find it, and having them in a single place could be cool.
Well, off-topic anyway