|
Fill free shape with allegro? |
TeachMeHowToPro
Member #15,892
February 2015
|
Hello. I'm making a paint program, simular to micrrosoft paint, using allegro 5.0.10. But I get stuck at one point when coding. I have NO IDEA how to implement the "Paint bucket" tool. I'm sure that most if you are familiar with the paint bucket in painting progams. You click somewhere and it changes the color of the adjacend pixels that contain the same color as the pixel that is clicked on with another color. I have been thinking for a while now, tried many diferent ways. Some people told me to use pathfinding mechanics, but I still have no idea what to do/ Any help or code examples will be welcome |
Chris Katko
Member #1,881
January 2002
|
Flood-fill algorithm. -----sig: |
StevenVI
Member #562
July 2000
|
A naiive implementation would be a recursive algorithm that looked at the neighbors of each pixel and colored them if they were the same source color. Something like this pseudocode: function fill(bmp, x, y, color) { oldColor = bmp[x][y]; bmp[x][y] = color; if (x < bmp.width - 1 && bmp[x+1][y] == oldColor) { fill(bmp, x+1, y, color); } if (x > 0 && bmp[x-1][y] == oldColor) { fill(bmp, x-1, y, color); } // similarly for y } However, you won't get very good performance out of it, especially if you're using video bitmaps. See al_lock_bitmap for more details. In terms of a more efficient algorithm, might want to try Google. Looks like there's a discussion of flood fill algorithms on Wikipedia, too. __________________________________________________ |
TeachMeHowToPro
Member #15,892
February 2015
|
Thanks. Also when you use bmp[x][y], did you mean using al_get_pixel, or you can access pixel data with these [][]? |
StevenVI
Member #562
July 2000
|
TeachMeHowToPro said: the thing that keeps bugging me is that you have included a color variable, which you do not write in when you cll again fill(). ( You enter the bmp,x and y but ignore/miss the color). Is this a mistake from your side Yeah, that was a mistake on my part -- just updated it above. And as I said, it's pseudocode, so it's not meant to be copied verbatim, but rather just to demonstrate the algorithm. I don't actually use Allegro 5, so I have no idea what functions are available or how to interact with ALLEGRO_BITMAP objects. Do check out the Wikipedia page that Chris and I referenced. I only skimmed it, but I believe it has more details on how to optimize the algorithm, and the references will probably be helpful. __________________________________________________ |
Chris Katko
Member #1,881
January 2002
|
StevenVI said: I only skimmed it, but I believe it has more details on how to optimize the algorithm, and the references will probably be helpful. It's got everything! I used it last year to build a grid atmosphere/pressure simulator to test an idea for "lazy" or "lagged" logic updating. Basically, you start at something important, like a pump, and recursively spawn out "seekers" that follow/fill all hallways and rooms and if they can't spawn any more, they die. It's just a flood fill, but the game logic happens inbetween flood fill steps allowing multiple fills to occur at the same time, each representing game state with newer state taking precedence over older state. {"name":"e8Q4rt9.png","src":"\/\/djungxnpq2nug.cloudfront.net\/image\/cache\/1\/e\/1e6ad0dd62739291ea869175d3085164.png","w":600,"h":570,"tn":"\/\/djungxnpq2nug.cloudfront.net\/image\/cache\/1\/e\/1e6ad0dd62739291ea869175d3085164"} -----sig: |
TeachMeHowToPro
Member #15,892
February 2015
|
Thank you so much for the help! |
Chris Katko
Member #1,881
January 2002
|
You could make sure the bitmap is a memory bitmap so that per pixel access is really fast. OR, you could move the image to a memory bitmap, do the flood fill, and then move it back to the GPU. A couple block transfers might be a lot faster than lots of per-pixel access to a video bitmap. -----sig: |
Edgar Reynaldo
Major Reynaldo
May 2007
|
Chris Katko said: OR, you could move the image to a memory bitmap, do the flood fill, and then move it back to the GPU. This is essentially what al_lock_bitmap does with video bitmaps. It has to create a buffer to store the changes into and then re-upload the pixel data to the texture. If you use ALLEGRO_LOCK_WRITE_ONLY it doesn't have to copy the video bitmap data to the buffer first, which slows things down. My Website! | EAGLE GUI Library Demos | My Deviant Art Gallery | Spiraloid Preview | A4 FontMaker | Skyline! (Missile Defense) Eagle and Allegro 5 binaries | Older Allegro 4 and 5 binaries | Allegro 5 compile guide |
Thomas Fjellstrom
Member #476
June 2000
|
Edgar Reynaldo said: If you use ALLEGRO_LOCK_WRITE_ONLY it doesn't have to copy the video bitmap data to the buffer first, which slows things down. True. though that is of dubious use in the case where you want to flood fill existing areas in a bitmap. -- |
Edgar Reynaldo
Major Reynaldo
May 2007
|
Right you are. Didn't really consider that. If you use ALLEGRO_NO_PRESERVE_TEXTURE (and a sane graphics lib like OpenGL that doesn't have severe cases of amnesia (cough.. DX)), does that speed up the pipeline? You could implement a copy on write scheme, both ways, from video to memory and from memory to video. Only update the video copy when a paint action is performed. Then you could still use ALLEGRO_LOCK_WRITE_ONLY, as you would be copying a memory buffer to a video buffer and then blitting the video buffer onto the backbuffer. I wonder what fps that would get, uploading on each paint action. My Website! | EAGLE GUI Library Demos | My Deviant Art Gallery | Spiraloid Preview | A4 FontMaker | Skyline! (Missile Defense) Eagle and Allegro 5 binaries | Older Allegro 4 and 5 binaries | Allegro 5 compile guide |
Thomas Fjellstrom
Member #476
June 2000
|
Edgar Reynaldo said: If you use ALLEGRO_NO_PRESERVE_TEXTURE (and a sane graphics lib like OpenGL that doesn't have severe cases of amnesia (cough.. DX)), does that speed up the pipeline? That should keep allegro from trying to save the textures when ever something changes yes. -- |
|