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
goyo
Officer Cadet
Posts: 52
Joined: Sat Jan 12, 2019 10:16 am

looking for a pixel flood fill routine

Post by goyo »

Hello,

I am looking for a assembly source routine of pixel flood fill but i only have the Petyr Miladinow Pawlow routine in Basic.

would anyone have a floodfill assembler routine to give me ? :D
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 wonder if the one in "Le Retour du Dr Genius" would be easy to extract, I remember it to have been relatively fast.
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 »

This is an interesting subject.
I'm a noob regarding the subject but I wonder: do fill algorithms on Oric take advantage of what I would call "byte structure" of the Hires screen? I mean, if a byte equals $64, it can be completely filled without checking neighborhood (might not be as simple as that with attributes and value of starting byte, but that's the idea: if the 6 visible pixels have the same value, they can be analysed as a whole)
User avatar
goyo
Officer Cadet
Posts: 52
Joined: Sat Jan 12, 2019 10:16 am

Re: looking for a pixel flood fill routine

Post by goyo »

Symoon wrote: Thu Sep 02, 2021 9:49 am This is an interesting subject.
I'm a noob regarding the subject but I wonder: do fill algorithms on Oric take advantage of what I would call "byte structure" of the Hires screen? I mean, if a byte equals $64, it can be completely filled without checking neighborhood (might not be as simple as that with attributes and value of starting byte, but that's the idea: if the 6 visible pixels have the same value, they can be analysed as a whole)
Yes i'ts seems so easy to manage a single line, but the dificulty is to manage the stack and limits his size, how to have a fixed size of the stack.

for help there is a nice wikipedia page : https://en.wikipedia.org/wiki/Flood_fill and Walk-based filling (Fixed-memory method)

but i'm not very good in English...
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 »

goyo wrote: Thu Sep 09, 2021 11:14 am for help there is a nice wikipedia page : https://en.wikipedia.org/wiki/Flood_fill and Walk-based filling (Fixed-memory method)
but i'm not very good in English...
Well, you can click on "Francais" on the bottom left to reach https://fr.wikipedia.org/wiki/Algorithm ... _diffusion

Generally speaking, on machines with limited memories you want to avoid using the stack for recursion, simply because some patterns (like a lot of small dots) will make the machine run out of memory.

The easiest way to handle that is to use an explicit stack (which you can allocate as an array anywhere in memory) and monitor the size, and if you can't push more to it, just continue with what you had stacked already, and when you are done there will be some parts that are not filled, but at least you would not have crashed :)
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 »

I've begun investigating Le Retour du Dr Genuis, the fill code is using a king of specific stack if I understand correctly (I'm in the middle of checking the code). Maybe it's just designed to work with simple surfaces, I suspect using a stack on complicated filling zones could indeed fill... The memory!
Not sure if I'll go anywhere from there, I've begun many projects in the past 5 years and almost never finish any :(
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, you could still put the disassembly of the code somewhere, if you have just a simple example which draw a couple lines in BASIC and then fill in the values, that would allow other to look at it :)
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 »

I'm far from it, still busy following the code, trying to identify all the subroutines and so on ;)
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: Fri Sep 10, 2021 7:14 pm I'm far from it, still busy following the code, trying to identify all the subroutines and so on ;)
Good luck!

Technically this type of routine should not be very large, they could be using the POINT and CURSET functions from the ROM but that would be very slow, so I would suspect they use their own custom functions for that?
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 »

Yes it seems so. There are tables with values of individual pixels on or off, being checked one by one, and I'm currently looking at the actual filling routine (before that, there was the system to find the places to fill on screen according to the displayed room in the game).
Having very little spare time doesn't help, but step by step I'm carrying on ;)
User avatar
jbperin
Flight Lieutenant
Posts: 480
Joined: Wed Nov 06, 2019 11:00 am
Location: Valence, France

Re: looking for a pixel flood fill routine

Post by jbperin »

It is not exactly a flood fill function but at paragraph 7.6 in the attached chapter of the geffer book, there's an assembly routine to fast draw a shape.
chap7.zip
(599.58 KiB) Downloaded 172 times
It says:
The following routine (Program 7.14), though still using the special graphics table, moves away from using character cells, and lets you draw an irregular shape, complete with colour.
All you have to do is provide the subroutine with the address of your object, plus details of its height (in pixels) and width (in character cells).

You must set up this information as follows:
1. Store the graphics shape in a free area of memory. The area must be pointed to by #8C, #8D.
2. A second free area is required, equal in size to the first, pointed to by #80, #81.
3. The data for the object must be stored line by line, with 1 byte for
each 6 pixels, or an attribute, and the number of bytes across
should be stored at #8E.
4. The number of lines down is required at location 8F.
5. Finally, you must load up the X and Y registers with the appropriate screen position (top left of the object).
With the parameters stored in exactly the same way, you call the routine at #115E in order to remove your artwork (Program 7.15).

Perhaps an alternate approach.
Who knows ..
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 »

jbperin wrote: Sat Sep 11, 2021 8:50 am It is not exactly a flood fill function but at paragraph 7.6 in the attached chapter of the geffer book, there's an assembly routine to fast draw a shape.
(...)
Based on the parameters, that looks like a routine that just copy some existing graphic data to the screen, like a sprite routine.
User avatar
ibisum
Wing Commander
Posts: 1645
Joined: Fri Apr 03, 2009 8:56 am
Location: Vienna, Austria
Contact:

Re: looking for a pixel flood fill routine

Post by ibisum »

Very interesting topic .. did you guys see this yet?

https://www.codeproject.com/Articles/60 ... -Algorithm

Also pretty relevant, mostly Atari though:

https://atariage.com/forums/topic/27844 ... fill-test/
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 Sep 11, 2021 11:04 am
jbperin wrote: Sat Sep 11, 2021 8:50 am It is not exactly a flood fill function but at paragraph 7.6 in the attached chapter of the geffer book, there's an assembly routine to fast draw a shape.
(...)
Based on the parameters, that looks like a routine that just copy some existing graphic data to the screen, like a sprite routine.
A bit further, the book has a PAINT routine. It seems rather short, not sure how efficient - won't have time to investigate if I want to carry on the other one ;)
User avatar
goyo
Officer Cadet
Posts: 52
Joined: Sat Jan 12, 2019 10:16 am

Re: looking for a pixel flood fill routine

Post by goyo »

Thank you for yours help.

I think i am going to loot in anciens Oric archives to find an assembly code of the floodfill algo.

The Lorigraph floodfill Algo look like very speed and optimal but it's difficult to disassemble it for me.
Post Reply