looking for a pixel flood fill routine

Here you can ask questions or provide insights about how to use efficiently 6502 assembly code on the Oric.
User avatar
Dbug
Site Admin
Posts: 4444
Joined: Fri Jan 06, 2006 10:00 pm
Location: Oslo, Norway
Contact:

Re: looking for a pixel flood fill routine

Post by Dbug »



;)
User avatar
Chema
Game master
Posts: 3014
Joined: Tue Jan 17, 2006 10:55 am
Location: Gijón, SPAIN
Contact:

Re: looking for a pixel flood fill routine

Post by Chema »

hehe Nice improvement :)
User avatar
Dbug
Site Admin
Posts: 4444
Joined: Fri Jan 06, 2006 10:00 pm
Location: Oslo, Norway
Contact:

Re: looking for a pixel flood fill routine

Post by Dbug »

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.
FloodFill.zip
(16.01 KiB) Downloaded 126 times
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    
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!
flood_fill_test.png
flood_fill_test.png (3.06 KiB) Viewed 4157 times
User avatar
Dbug
Site Admin
Posts: 4444
Joined: Fri Jan 06, 2006 10:00 pm
Location: Oslo, Norway
Contact:

Re: looking for a pixel flood fill routine

Post by Dbug »

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.
FloodFill-2022-01-29.zip
(15.89 KiB) Downloaded 126 times
User avatar
Symoon
Archivist
Posts: 2307
Joined: Sat Jan 14, 2006 12:44 am
Location: Paris, France

Re: looking for a pixel flood fill routine

Post by Symoon »

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)
User avatar
Dbug
Site Admin
Posts: 4444
Joined: Fri Jan 06, 2006 10:00 pm
Location: Oslo, Norway
Contact:

Re: looking for a pixel flood fill routine

Post by Dbug »

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:

User avatar
Dbug
Site Admin
Posts: 4444
Joined: Fri Jan 06, 2006 10:00 pm
Location: Oslo, Norway
Contact:

Re: looking for a pixel flood fill routine

Post by Dbug »

I started comparing the algorithm, and it looks like the best one is Master Paint!

User avatar
Symoon
Archivist
Posts: 2307
Joined: Sat Jan 14, 2006 12:44 am
Location: Paris, France

Re: looking for a pixel flood fill routine

Post by Symoon »

Dbug wrote: Sat Feb 12, 2022 5:50 pm I started comparing the algorithm, and it looks like the best one is Master Paint!
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.
User avatar
Dbug
Site Admin
Posts: 4444
Joined: Fri Jan 06, 2006 10:00 pm
Location: Oslo, Norway
Contact:

Re: looking for a pixel flood fill routine

Post by Dbug »

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).
User avatar
Dbug
Site Admin
Posts: 4444
Joined: Fri Jan 06, 2006 10:00 pm
Location: Oslo, Norway
Contact:

Re: looking for a pixel flood fill routine

Post by Dbug »

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:

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            
User avatar
Dbug
Site Admin
Posts: 4444
Joined: Fri Jan 06, 2006 10:00 pm
Location: Oslo, Norway
Contact:

Re: looking for a pixel flood fill routine

Post by Dbug »

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).

User avatar
Dbug
Site Admin
Posts: 4444
Joined: Fri Jan 06, 2006 10:00 pm
Location: Oslo, Norway
Contact:

Re: looking for a pixel flood fill routine

Post by Dbug »

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)

User avatar
Symoon
Archivist
Posts: 2307
Joined: Sat Jan 14, 2006 12:44 am
Location: Paris, France

Re: looking for a pixel flood fill routine

Post by Symoon »

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.
User avatar
Dbug
Site Admin
Posts: 4444
Joined: Fri Jan 06, 2006 10:00 pm
Location: Oslo, Norway
Contact:

Re: looking for a pixel flood fill routine

Post by Dbug »

Symoon wrote: 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.
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.
User avatar
Symoon
Archivist
Posts: 2307
Joined: Sat Jan 14, 2006 12:44 am
Location: Paris, France

Re: looking for a pixel flood fill routine

Post by Symoon »

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 ;)
Post Reply