# Graphics routines

Hi, I'm trying to write a library of graphics routines in Turbo Assembler 4. Line and point drawing is easy, but the flood fill is giving me some problems.

I want an algorithm that is capable of filling an area bounded by colour B, starting at position X,Y. I've written a semirecursive function that will do this, but only with small areas (about 100 pixels...). Beyond that, the stack overflows and causes a nasty crash. Ideally, I need an iterative routine that makes minimal (or no) use of the stack, although I'd guess that this is fairly difficult to do.

I can write the code myself. What I really need is a basic description of an algorithm that will do this. To kick-start my brain.

• : Hi, I'm trying to write a library of graphics routines in Turbo Assembler 4. Line and point drawing is easy, but the flood fill is giving me some problems.
:
: I want an algorithm that is capable of filling an area bounded by colour B, starting at position X,Y. I've written a semirecursive function that will do this, but only with small areas (about 100 pixels...). Beyond that, the stack overflows and causes a nasty crash. Ideally, I need an iterative routine that makes minimal (or no) use of the stack, although I'd guess that this is fairly difficult to do.
:
: I can write the code myself. What I really need is a basic description of an algorithm that will do this. To kick-start my brain.
:
[blue]Very simple...

You need a coordinate object, like so:

POINT Struc
ptX Dw ?
ptY Dw ?
POINT EndS

and then you need two arrays of these objects - you may want to allocate memory here, because their size depends on graphics mode. Take two diagonals for now, you can add later if needed. What I mean is: say mode is 640x480, so diagonal line will take [b]sqrt((640*640)+(480*480))[/b] - just get calculator and round this value to nearest 10 pixels. Then double it - that is how many POINTs you need in every array.

When you have your buffers, call them accordingly:
[code]
.DATA
bufSource Dd ? ; Allocate this as calculated above
bufTarget Dd ? ; Allocate this as calculated above
iSrcCount Dw 0 ; How many points is in 'bufSource'
iDstCount Dw 0 ; How many points will be in 'bufTarget'
[/code]

Now, code some functions (or better macros, it will be faster) to
add points to the arrays. Pass an address of the array, its count and POINT's (X,Y) parts.

Ok, we ready now... here is how to do it:

1. Put a source point (where the floodfill begins) into 'bufSource'.
2. Run in a loop for all points inside 'bufSource' and process every point according to rules of your floodfill() - you can check 4 sides or 8 sides of a pixel (do not forget to check the screen sides too) - if the pixel at the side supposed to be filled - fill it AND put its (X,Y) into 'bufTarget'.

3. Now, here you have painted a first 'wave' of pixels, so make them now a source themselves. Copy 'bufTarget' into 'bufSource' (do not forget to copy a target count too). Then make a count for 'bufTarget' to zero, to make it empty. Go back to step #2 and repeat. The wave of color will be 'leaking' into all possible non-filled areas.

Stop the process when step #2 does not produce any new pixels.
========================
Hope, it helps... but it is kind of slow - you can do the whole process in memory, but then you need to allocate a buffer for an image - copy image from screen into that buffer - do all of the above and then dump the buffer back to screen.[/blue]
• Thanks! That was almost EXACTLY the method I was considering, but I wasn't sure if it was possible. Now all I need to do is figure out how to dynamically allocate memory...

I could probably just add pixels to the source buffer and increment the item count rather than using two buffers. This would reduce memory requirements and also speed up the algorithm. I've never used object-oriented methods or custom data types in assembler before (I prefer twiddling bytes and words at base level), but this seems like a good time to learn.
• : Thanks! That was almost EXACTLY the method I was considering, but I wasn't sure if it was possible. Now all I need to do is figure out how to dynamically allocate memory...
:
: I could probably just add pixels to the source buffer and increment the item count rather than using two buffers. This would reduce memory requirements and also speed up the algorithm. I've never used object-oriented methods or custom data types in assembler before (I prefer twiddling bytes and words at base level), but this seems like a good time to learn.
:
[blue]In DOS allocate memory with INT 21H Function AH=48h - see the Ralf Brown Interrupt list...[/blue]
• I once made this thing to put a one pixel deep cover over an object.
The purpose was to shade it with deincrementing colors as a coating.
Before it was finished I tried it on the inside of a circle & it filled it.
I didn't use any buffer or allocated memory, it was fast and worked using the screens memory.
It was like a pixel with a life of it's own,
cause once you planted the pixel some where,
it got the color it was sitting on, then altered every 8 pixels around it that was the same color, working in a spiral circle
it followed edges until there was no more of the original color, then it committed sewerside & died.
It was flawed, cause it would paint it's self into a corner sometimes,
but I never added any more IQ to it, cause it worked fine for shadeing.
It wasn't much more than one small PROC working from an INTerrupt driven mouses left click.

Bitdog

• : : Thanks! That was almost EXACTLY the method I was considering, but I wasn't sure if it was possible. Now all I need to do is figure out how to dynamically allocate memory...
: :
: : I could probably just add pixels to the source buffer and increment the item count rather than using two buffers. This would reduce memory requirements and also speed up the algorithm. I've never used object-oriented methods or custom data types in assembler before (I prefer twiddling bytes and words at base level), but this seems like a good time to learn.
: :
: [blue]In DOS allocate memory with INT 21H Function AH=48h - see the Ralf Brown Interrupt list...[/blue]
:

My own Int reference is the PC Programmer's Bible, 3rd edition. It's a bit outdated, but most of the info is still accurate.
The fill algorithm is up and running. It's amazingly fast, too. Unfortunately, my Turbo Assembler isn't working properly and I had to do the hex translation myself. Thank god for opcode lists...