|
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. Agui GUI API -> https://github.com/jmasterx/Agui |
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
|
You are better off building a triangle mesh out of your shapes and filling those. ___________________________________ |
weapon_S
Member #7,859
October 2006
|
Could you give an example of a (very problematic) 'line-based sprite'? |
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 what people find beautiful about the Mandelbrot set is not the set itself, but all the rest. |
SiegeLord
Member #7,827
October 2006
|
Johan Halmén said: 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: "For in much wisdom is much grief: and he that increases knowledge increases sorrow."-Ecclesiastes 1:18 |
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
|
Floodfill has never been something you want to do in realtime. And has never been especially important for games. Clarification: -- |
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 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. |
Oscar Giner
Member #2,207
April 2002
|
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 Thank you indeed haha! 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 -- |
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
|
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. -- |
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
|
Agui GUI API -> https://github.com/jmasterx/Agui |
Arthur Kalliokoski
Second in Command
February 2005
|
Regular C 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}
They all watch too much MSNBC... they get ideas. |
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] -- |
Trent Gamblin
Member #261
April 2000
|
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 -- |
Arthur Kalliokoski
Second in Command
February 2005
|
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. They all watch too much MSNBC... they get ideas. |
|