Allegro.cc - Online Community

Allegro.cc Forums » Programming Questions » Is floodfill function gone??

This thread is locked; no one can reply to it. rss feed Print
Is floodfill function gone??
Cisco Mir
Member #13,959
January 2012

Hello!

I'm a bit busy porting some old code I've done years ago with Allegro to work with new Allegro 5.

After some long reading to understand how screen, vscreen and everything works now and having it working pretty well :)... I can't seem to found the equivalent to floodfill.

Is this function gone on Allegro 5?? :(

Thankyou very much!

jmasterx
Member #11,410
October 2009

Yes it is. Allegro 5 is hardware accelerated therefore flood-fill would be very slow; Impractically slow.

Cisco Mir
Member #13,959
January 2012

Then I have no alternative? :(

I don't pretend to do floodfill for every frame in real time, just to create the sprites that are line-oriented...

And then use them blitting, so it's not a drama that it's slow "loading" the sprites... but now I don't have the way to "color" them!! :O

Thankyou for your answer btw!!:'(

Steve Terry
Member #1,989
March 2002
avatar

You are better off building a triangle mesh out of your shapes and filling those.

___________________________________
[ Facebook ]
Microsoft is not the Borg collective. The Borg collective has got proper networking. - planetspace.de
Bill Gates is in fact Shawn Hargreaves' ßî+çh. - Gideon Weems

weapon_S
Member #7,859
October 2006
avatar

Could you give an example of a (very problematic) 'line-based sprite'?
Maybe you could save a bitmap with transparent areas, and then only fill white or black areas (with blenders).

Johan Halmén
Member #1,550
September 2001

jmasterx said:

Yes it is. Allegro 5 is hardware accelerated therefore flood-fill would be very slow; Impractically slow.

What went wrong in the progress?

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Years of thorough research have revealed that the red "x" that closes a window, really isn't red, but white on red background.

Years of thorough research have revealed that what people find beautiful about the Mandelbrot set is not the set itself, but all the rest.

SiegeLord
Member #7,827
October 2006
avatar

What went wrong in the progress?

GPUs are only suited for tasks where you can think of using hundreds/thousands of threads in parallel. A flood fill algorithm is not very parallelizable, making it distinctly unsuitable for the GPU.

Anyway... it depends exactly on the task. I'd try these steps:
1. If the border lines form a convex shape, 5.0 can easily draw that right now
2. If the border lines form a concave shape, you'd need functions from 5.1 to draw it
3. If it's impossible (hard) to determine the shape outline (intersecting line), I'd just port the A4 flood fill to A5. Though, I looked at the code... it's a little hairy...

"For in much wisdom is much grief: and he that increases knowledge increases sorrow."-Ecclesiastes 1:18
[SiegeLord's Abode][Codes]:[DAllegro5]:[RustAllegro]

Cisco Mir
Member #13,959
January 2012

What I can't understand is:

In 1990, with deluxe paint enhanced, I can floodfill my drawings in a very decent speed with my 386 at 16mhz. In one second

Is really that hard and slow to implement a floodfill like that old one?

I personally don't know a easy way to do it, btw.

gnolam
Member #2,030
March 2002
avatar

Floodfill has never been something you want to do in realtime. And has never been especially important for games.
Nick the relevant parts of flood.c from Allegro 4.x if you really need it. But again: could you define "line-oriented sprite", please?

Clarification:
A lot of the time when someone asks how to use X to do Y, they should really just be asking how to do Y. Chances are there's a better way to do it.

--
Move to the Democratic People's Republic of Vivendi Universal (formerly known as Sweden) - officially democracy- and privacy-free since 2008-06-18!

Cisco Mir
Member #13,959
January 2012

Sorry, I will try to explaing this better, as line-oriented is probably not the best way to call it.

I have a bamboo drawing tablet. With the appropiate software I can do some drawings, and then with my own software I "draw over" this drawings the lines for the characters, so those characters are saved in a "line format" instead just graphics sprites. Probably it's similar to vector graphics with flash... if not the same, that I don't think so.

With this, the benefits for me are important, cause the engine draws the sprites before using them with the possibility of working with those "lines" doing effects like sketch effect, or the "movement" effect in rotoscopy films just altering a little bit the lines.

I don't think if I have explained really well 'cause english is not my native language. The purpose of all this is that my format creates the sprites to be used this way:

1 · Open sprite file, read line data, draw them on a bitmap
2 · Colorize (floodfill) each zone of the sprite with appropiate color, not important if "slow" because it's not real time sprite showing on screen, just preparing them.
3 · Now the sprite is available to blit fastly.

The real purpose as I said is that saving the sprite this way I can transform, zoom, "sketch", change colors... it's appropiate for the kind of project I'm in.

Thank you for answers and patience and sorry for my bad explanation.

This video (not mine) shows what I want to achieve, the possibility of simulating "movement" on still frames and colorizing them with this kind of result.

http://www.youtube.com/watch?v=pqKtEcPlQ8w&feature=related

Oscar Giner
Member #2,207
April 2002
avatar

What you're describing is vector graphics. And floodfill is not the right tool. You already have the vector information (your "lines"), so just use that to fill the shapes with filled polygons.

Cisco Mir
Member #13,959
January 2012

Ok, i will check how it works. It really seems I'm inventing a methode invented 40 years ago ;D

Thank you indeed haha! ;D

What seems to be interesting is this function (from old allegro versions):

void polygon(BITMAP *bmp, int vertices, const int *points, int color);

Draws a filled polygon with an arbitrary number of corners. Pass the number of vertices and an array containing a series of x, y points (a total of vertices*2 values).

This is probably the best solution, but again... which is the easiest equivalent with allegro 5?

Because I'm getting a bit confused with all that al_draw_prim things...

Bruce Perry
Member #270
April 2000

Your vector data may not be that easy to convert to polygons. After all, you're storing line data, and you'll need to figure out how to connect it up. If it were me, I'd probably find it easier to implement floodfill.

If you can get at the pixel data, then floodfill looks like this:

//This is pseudocode, not in any specific language
struct Point { int x,y; }
Queue<Point> queue;
int oldColour=getpixel(startX,startY);
putpixel(startX,startY,newColour);
queue.push(Point(startX,startY));
while (!queue.isEmpty()) {
    Point p=queue.pop();
    if (getpixel(p.x-1,p.y)==oldColour) { putpixel(p.x-1,p.y,newColour); queue.push(Point(p.x-1,p.y)); }
    if (getpixel(p.x+1,p.y)==oldColour) { putpixel(p.x+1,p.y,newColour); queue.push(Point(p.x+1,p.y)); }
    if (getpixel(p.x,p.y-1)==oldColour) { putpixel(p.x,p.y-1,newColour); queue.push(Point(p.x,p.y-1)); }
    if (getpixel(p.x,p.y+1)==oldColour) { putpixel(p.x,p.y+1,newColour); queue.push(Point(p.x,p.y+1)); }
}

Often the queue is implemented in this sort of way:

const int max=1024;
Point queue[max];
int head=0,tail=0;
/* push */ queue[head]=Point(...); head=(head+1)%max;
/* pop  */ Point p=queue[tail]; tail=(tail+1)%max;
/* !isEmpty */ head!=tail

I'll leave you to figure out how getpixel() and putpixel() need to work, but that's mainly because I'm fairly new to Allegro 5 myself and I'm lazy :)

--
Bruce "entheh" Perry [ Web site | DUMB | Set Up Us The Bomb !!! | Balls ]
Programming should be fun. That's why I hate C and C++.
The brxybrytl has you.

Cisco Mir
Member #13,959
January 2012

I really think floodfill is the better option for my purpose, cause I really don't want to render polygons in realtime, so flood fill is really more accurate than polygons.

I have been doing some tests with triangles and its ok... but not really good. Polygons are polygons and I'm working with beizer curves.

I'll try to figure how to implement what you suggested. Not problem with getpixel and putpixel fortunately :)

Thank you!

Matthew Leverton
Supreme Loser
January 1999
avatar

Lock the bitmap before you start calling al_get/put_pixel on it.

Bruce Perry
Member #270
April 2000

To explain the floodfill algorithm a bit more: it starts from a point and spreads out in every direction, growing through all reachable 'oldColour' pixels until there's no more room to grow. Since the computer can't think about all the points simultaneously, we have to store them and come back to them. The queue remembers all the points that are still growing.

There is a more complicated algorithm that does whole horizontal lines at once and gets much, much faster results for typical large areas, but it's probably not worth it for your case.

--
Bruce "entheh" Perry [ Web site | DUMB | Set Up Us The Bomb !!! | Balls ]
Programming should be fun. That's why I hate C and C++.
The brxybrytl has you.

Cisco Mir
Member #13,959
January 2012

I'm not very familiar with queues (i'm very dumb at programming, poorly optimitzating right now basing it on ifs and dos and ifs and dos....).

If you can translate the code you posted to c++ for using in windows with allegro, that probably will be very similar to what you posted really... you will do me a very big favor!

If it's not too much to ask!

Thank you very much, anyway! ;):-[

jmasterx
Member #11,410
October 2009

Arthur Kalliokoski
Second in Command
February 2005
avatar

Regular C

#SelectExpand
1static void _ffill(IMG *bmp,int x,int y,int fillcolor,int old) 2{ 3 if(getpixel(bmp,x,y)==old) 4 { 5 putpixel(bmp,x,y,fillcolor); 6 _ffill(bmp,x+1,y,fillcolor,old); 7 _ffill(bmp,x-1,y,fillcolor,old); 8 _ffill(bmp,x,y+1,fillcolor,old); 9 _ffill(bmp,x,y-1,fillcolor,old); 10 } 11} 12 13void floodfill(IMG *bmp, int x, int y, int fillcolor) 14{ 15 int oldcolor; 16 oldcolor = getpixel(bmp,x,y); 17 _ffill(bmp,x,y,fillcolor,oldcolor); 18}

“Throughout history, poverty is the normal condition of man. Advances which permit this norm to be exceeded — here and there, now and then — are the work of an extremely small minority, frequently despised, often condemned, and almost always opposed by all right-thinking people. Whenever this tiny minority is kept from creating, or (as sometimes happens) is driven out of a society, the people then slip back into abject poverty. This is known as "bad luck.”

― Robert A. Heinlein

Bruce Perry
Member #270
April 2000

It's like a queue for a water slide. Pixels want to enjoy the water slide and then make a nice splash into their neighbours, but they always have to join the back of the queue, behind all the other pixels that got there first. <3

[EDIT]
Arthur - that's a really bad idea. It'll probably use up half as many stack frames as there are pixels. If it doesn't overflow the stack, consider yourself lucky. It really does need to be FIFO (queue-based), not LIFO (stack-based).

--
Bruce "entheh" Perry [ Web site | DUMB | Set Up Us The Bomb !!! | Balls ]
Programming should be fun. That's why I hate C and C++.
The brxybrytl has you.

Trent Gamblin
Member #261
April 2000
avatar

You want to use a queue, not recursion, or you'll run out of stack space on (not even that-) large fills.

Bruce Perry
Member #270
April 2000

Beaten with my edit ;D

--
Bruce "entheh" Perry [ Web site | DUMB | Set Up Us The Bomb !!! | Balls ]
Programming should be fun. That's why I hate C and C++.
The brxybrytl has you.

Arthur Kalliokoski
Second in Command
February 2005
avatar

That was from an old software thing I had, I remember I had to give it a pretty big stack, like 8 megs or so, but that's nothing in this day of multi-gig computers.

That was for a worst-case with a tight spiral filling a full screen window, OTOH it was 32 bit so the return pointers were only 4 bytes each, not 8.

“Throughout history, poverty is the normal condition of man. Advances which permit this norm to be exceeded — here and there, now and then — are the work of an extremely small minority, frequently despised, often condemned, and almost always opposed by all right-thinking people. Whenever this tiny minority is kept from creating, or (as sometimes happens) is driven out of a society, the people then slip back into abject poverty. This is known as "bad luck.”

― Robert A. Heinlein

Go to: