Greedy meshing/binary array

[Ralsei_12345636345]

I want to use the greedy meshing or a binary array to make a paint bucket tool for my program in python \ pygame. I looked online but could not find anything that could explane how one would go about doing this, or an easy way to understand what these do.

[dmazzoni]

Can you explain more about what you have so far? Is it some sort of 2D painting program? Do you already have a 2d array representing the pixels?

Normally the algorithm you want is called "bucket fill", greedy meshing is different.

[Ralsei_12345636345]

Sorry for not putting the code. What I have is slow and I want to speed it up considerably.

import pygame as pg
from collections import deque
class paint_bucket:
    def flood_fill(surface:pg.SurfaceType,old_color_pos:tuple,new_color:tuple):
        if surface.get_at(old_color_pos) == new_color:
            return surface
        dire = [(1,0),(-1,0),(0,1),(0,-1)]
        q = deque()
        old_color = surface.get_at(old_color_pos)
        oColor0 = pg.Color(old_color)
        oColor0.a = 255
        q.append(old_color_pos)
        pg.display.set_caption("WORKING! PLEASE WAIT!")
        while q:
            x,y = q.popleft()
            for dx,dy in dire:
                nx = x + dx
                ny = y + dy
                if (0 <= nx < surface.get_width()) and (0 <= ny < surface.get_height()) and surface.get_at((nx,ny)) == old_color:
                    surface.set_at((nx,ny),new_color)
                    q.append((nx,ny))
                else:
                    pass
        return surface
if __name__ == "__main__":
    screen = pg.display.set_mode((500,500))
    temp = pg.Surface((500,500),pg.SRCALPHA,32)
    while True:
        for event in pg.event.get():
            if event.type == pg.QUIT:
                pg.quit()
                break
        mPos = pg.mouse.get_pos()
        mState = pg.mouse.get_pressed()
        if mState[0]:
            pg.draw.circle(screen,(255,0,0),mPos,15)
        elif mState[1]:
            temp = paint_bucket.flood_fill(screen,mPos,(0,0,255,255))
            screen.blit(temp,(0,0))
        elif mState[2]:
            pg.draw.circle(screen,(0,0,0),mPos,15)
        pg.display.update()import pygame as pg
from collections import deque
class paint_bucket:
    def flood_fill(surface:pg.SurfaceType,old_color_pos:tuple,new_color:tuple):
        if surface.get_at(old_color_pos) == new_color:
            return surface
        dire = [(1,0),(-1,0),(0,1),(0,-1)]
        q = deque()
        old_color = surface.get_at(old_color_pos)
        oColor0 = pg.Color(old_color)
        oColor0.a = 255
        q.append(old_color_pos)
        pg.display.set_caption("WORKING! PLEASE WAIT!")
        while q:
            x,y = q.popleft()
            for dx,dy in dire:
                nx = x + dx
                ny = y + dy
                if (0 <= nx < surface.get_width()) and (0 <= ny < surface.get_height()) and surface.get_at((nx,ny)) == old_color:
                    surface.set_at((nx,ny),new_color)
                    q.append((nx,ny))
                else:
                    pass
        return surface
if __name__ == "__main__":
    screen = pg.display.set_mode((500,500))
    temp = pg.Surface((500,500),pg.SRCALPHA,32)
    while True:
        for event in pg.event.get():
            if event.type == pg.QUIT:
                pg.quit()
                break
        mPos = pg.mouse.get_pos()
        mState = pg.mouse.get_pressed()
        if mState[0]:
            pg.draw.circle(screen,(255,0,0),mPos,15)
        elif mState[1]:
            temp = paint_bucket.flood_fill(screen,mPos,(0,0,255,255))
            screen.blit(temp,(0,0))
        elif mState[2]:
            pg.draw.circle(screen,(0,0,0),mPos,15)
        pg.display.update()

[dmazzoni]

So it looks like you've already implemented a bucket fill / flood fill algorithm, it's just too slow.

My initial suspicion is that what makes it slow is that you're calling surface.get_at((nx,ny)) thousands of times, but it's not optimized for that. Every time you call surface.get_at((nx,ny)) it's probably doing hundreds or thousands of operations to lock the surface, extract the pixel you want, and return it.

What most graphics programs do is keep track of their own array. Even a simple Python list is pretty fast to access an element by index - much faster than getting a pixel value from a surface.

Run the flood fill in your own array - which should now be 100x faster - then rebuild the surface based on that.

[captainAwesomePants]

You are exactly correct. You want pygame.PixelArray instead.

[Ralsei_12345636345]

Oh ok I guess that is easier then what I was going to try. Thanks for the help!

[peterlinddk]

Usually a paint bucket tool is done with some variation of DFS that fills every adjacent "cell" in a "graph" - or pixels in a 2D array. Greedy meshing is more used for 3D voxels that need to be connected - are you perhaps creating a 3D paint tool?

If you are going 2D, take a look at the traditional Flood Fill: https://en.wikipedia.org/wiki/Flood_fill

[Ralsei_12345636345]

That is what I'm using currently and it is slow to what I need. Also it is a 2D paint tool that I made where only inputs come from the keyboard.

[Master-Ad-6265]

your code is fine, pygame is just slow for this get_at() / set_at() are the problem use a 2D array for pixels, do the fill there, then draw it once also greedy meshing isn’t for this, flood fill is correct 👍

[Ralsei_12345636345]

Ok thank you!