[bmx] Split pixmap into multiple tiles

[TomToad]

This will take a pixmap and split the pixmap into individual tiles of contiguous pixels.  It will even handle overlap.  Free to use in your own code.

Code (blitzmax) Select Expand

'Split Tiles
'author:TomToad
'created: March 3,2020
'may be used and modified freely in your own projects
SuperStrict

'the x, y, and color of a single pixel
Type TPixel
Field x:Int
Field y:Int
Field color:Int

Function Create:TPixel(x:Int,y:Int,Color:Int)
Local Pixel:TPixel = New TPIxel
Pixel.x = x
Pixel.y = y
Pixel.color = color
Return Pixel
End Function
End Type

'a list of pixels in a tile, plus its bounding box
Type TPixelList
Field list:TList = CreateList()
Field xmin:Int, xmax:Int
Field ymin:Int, ymax:Int

Method SetBoundingBox(xmin:Int, xmax:Int, ymin:Int, ymax:Int)
Self.xmin = xmin
Self.xmax = xmax
Self.ymin = ymin
Self.ymax = ymax
End Method

Method UpdateBoundingBox(x:Int, y:Int)
If x < xmin Then xmin = x
If x > xmax Then xmax = x
If y < ymin Then ymin = y
If y > ymax Then ymax = y
End Method
End Type

'A list of tiles
Local TileList:TList = CreateList()

Local filename:String = RequestFile("Tileset")
If Not filename Then End

'load the tileset into a pixmap
Local tileset:TPixmap = LoadPixmap(filename)
If Not tileset Then RuntimeError("Couldn't load "+filename)

'copy the tileset and make sure the pixmap is 32 bit
Local tilesetcopy:TPixmap = ConvertPixmap(tileset,PF_RGBA8888)

'Start with the upper left corner of pixmap and check if it is part of a tile.
'  If it is, then extract the tile into a pixelList and add to TIleList
Local count:Int = 0
For Local y:Int = 0 Until tilesetcopy.height
For Local x:Int = 0 Until tilesetcopy.width
If Not isEmpty(tilesetcopy,x,y,1)
Local PixelList:TPixelList = ExtractPixels(tilesetcopy,x,y,1,3)
TileList.AddLast(PixelList)
count :+ 1
Print "found tile #"+count
EndIf
Next
Next

'Now to create the actual tiles
Local tiles:TList = CreateList() 'list to hold the tiles
For Local tile:TPixelList = EachIn TileList 'iterate through each tile
Local pixmap:TPixmap = CreatePixmap(tile.xmax-tile.xmin+1,tile.ymax-tile.ymin+1,PF_RGBA8888) 'create the tile
ClearPixels(pixmap) 'clear the pixels
For Local pixel:TPixel = EachIn tile.list
setPixel(pixmap,pixel.x-tile.xmin,pixel.y-tile.ymin,pixel.color) 'copy the pixels
Next
tiles.AddLAst(pixmap)
Next


'test the result
Graphics 800,600
For Local pixmap:TPixmap = EachIn tiles
Cls
DrawPixmap pixmap,0,0
Flip
WaitKey()
Next


'function to test if a pixel is empty (Alpha < Tolerance)
Function isEmpty:Int(pixmap:TPixmap, x:Int, y:Int, Tolerance:Byte = $80)
If pixmap.pixels[y*pixmap.pitch+x*4+3] < Tolerance Then Return True
Return False
End Function

'This function uses a recursive backtrack algorythm to obtain all pixels
'  within a tile.  The pixels are added to a pixelList and the alpha is
'  set to 0.  Tolerance is used to determine which pixels are part of the
'  tile.  Reach determines how close a pixel needs to be to be part of the tile
Function ExtractPixels:TPixelList(Pixmap:TPixmap, x:Int, y:Int, Tolerance:Byte = $80, Reach:Int = 1)
Local Stack:TList = CreateList() 'Stack to use in the recursive backtrack
Local PixelList:TPixelList = New TPixelList 'create the pixelList
PixelList.SetBoundingBox(x,x,y,y) 'set the bounding box

Local pixel:TPixel = TPixel.Create(x,y,getPixel(Pixmap,x,y)) 'get the first pixel
Stack.AddLast(pixel) 'add to the stack
PixelList.List.AddLast(pixel) 'add to the pixel list
setPixel(Pixmap,x,y,0) 'set the pixel to 0 to indicate 'visited'

Local NewPixel:TPixel 'to store pixels to be pushed onto the stack
While Not Stack.isEmpty() 'repeat until the stack is empty
pixel = TPixel(Stack.RemoveFirst())
For Local py:Int = pixel.y-reach To pixel.y+reach
For Local px:Int = pixel.x-reach To pixel.x+reach
If py >= 0 And px >= 0 And py < pixmap.height And px < pixmap.width ..
And Not isEMpty(pixmap,px,py,tolerance)
NewPixel = TPixel.Create(px,py,getPixel(Pixmap,px,py))
Stack.AddLast(NewPixel)
PixelList.List.AddLast(NewPixel)
PixelList.UpdateBoundingBox(NewPixel.x,NewPixel.y)
setPixel(Pixmap,NewPixel.x,NewPixel.y,0)
EndIf
Next
Next

Wend
'Now PixelList contains all the pixels in the tile :)
Return PixelList
End Function

'quickly read a pixel color from a pixmap
Function getPixel:Int(pixmap:TPixmap,x:Int,y:Int)
Local PixelIntPtr:Int Ptr = Int Ptr(pixmap.pixels)
Local PitchInt:Int = pixmap.pitch/4

Return PixelIntPtr[y*PitchInt+x]
End Function

'quickly write to a pixel
Function setPixel(pixmap:TPixmap,x:Int,y:Int,color:Int)
Local PixelIntPtr:Int Ptr = Int Ptr(pixmap.pixels)
Local Pitchint:Int = pixmap.pitch/4

PixelIntPtr[y*PitchInt+x] = color
End Function



Edit:  New version has a "reach" parameter so that pixels nearby, but not quite touching, will be part of the same tile.  Leave at default 1 to require all pixels to touch, 2 allows a 1 pixel gap, 3 allows a 2 pixel gap, etc...

[Derron]

Good job so far.

If you want to have it "Blitzmax NG only", then you might think of utilizing the stuff in brl.mod/collections.mod -> so instead of placing stuff in a TList you could use a TStack.

I tried it and alone the replacement of TList with TStack in the extraction function reduced average convert+extraction time from 17.8ms to 13.6ms (over 1000 iterations).

Replacing the "TList" in TPixelList with "TObjectList" (a kind of "array + list") cut it down to 11.1ms on my computer.

Code (BlitzMax) Select Expand


Type TPixelList2
        Field list:TObjectList = new TObjectList
        Field xmin:Int, xmax:Int
        Field ymin:Int, ymax:Int
       
        Method SetBoundingBox(xmin:Int, xmax:Int, ymin:Int, ymax:Int)
                Self.xmin = xmin
                Self.xmax = xmax
                Self.ymin = ymin
                Self.ymax = ymax
        End Method
       
        Method UpdateBoundingBox(x:Int, y:Int)
                If x < xmin Then xmin = x
                If x > xmax Then xmax = x
                If y < ymin Then ymin = y
                If y > ymax Then ymax = y
        End Method
End Type

'This function uses a recursive backtrack algorythm to obtain all pixels
'  within a tile.  The pixels are added to a pixelList and the alpha is
'  set to 0.  Tolerance is used to determine which pixels are part of the
'  tile
Function ExtractPixels2:TPixelList2(Pixmap:TPixmap, x:Int, y:Int, Tolerance:Byte = $80)
        Local stack:TStack<TPixel> = New TStack<TPixel> 'Stack to use in the recursive backtrack
        Local PixelList:TPixelList2 = New TPixelList2 'create the pixelList
        PixelList.SetBoundingBox(x,x,y,y) 'set the bounding box
       
        Local pixel:TPixel = TPixel.Create(x,y,getPixel(Pixmap,x,y)) 'get the first pixel
        Stack.Push(pixel) 'add to the stack

        PixelList.List.AddLast(pixel) 'add to the pixel list

        setPixel(Pixmap,x,y,0) 'set the pixel to 0 to indicate 'visited'
       
        Local NewPixel:TPixel 'to store pixels to be pushed onto the stack
        While Not Stack.isEmpty() 'repeat until the stack is empty
                pixel = Stack.Pop()

                'check up
                If pixel.y > 0 And Not isEmpty(pixmap,pixel.x,pixel.y-1,tolerance)
                        NewPixel = TPixel.Create(pixel.x,pixel.y-1,getPixel(Pixmap,pixel.x,pixel.y-1))
                        Stack.Push(NewPixel)
                        PixelList.List.AddLast(NewPixel)
                        PixelList.UpdateBoundingBox(NewPixel.x,NewPixel.y)
                        setPixel(Pixmap,NewPixel.x,NewPixel.y,0)
                EndIf
                'check down
                If pixel.y < pixmap.width-1 And Not isEmpty(pixmap,pixel.x,pixel.y+1,tolerance)
                        NewPixel = TPixel.Create(pixel.x,pixel.y+1,getPixel(Pixmap,pixel.x,pixel.y+1))
                        Stack.Push(NewPixel)
                        PixelList.List.AddLast(NewPixel)
                        PixelList.UpdateBoundingBox(NewPixel.x,NewPixel.y)
                        setPixel(Pixmap,NewPixel.x,NewPixel.y,0)
                EndIf
                'check left
                If pixel.x > 0 And Not isEmpty(pixmap,pixel.x-1,pixel.y,tolerance)
                        NewPixel = TPixel.Create(pixel.x-1,pixel.y,getPixel(Pixmap,pixel.x-1,pixel.y))
                        Stack.Push(NewPixel)
                        PixelList.List.AddLast(NewPixel)
                        PixelList.UpdateBoundingBox(NewPixel.x,NewPixel.y)
                        setPixel(Pixmap,NewPixel.x,NewPixel.y,0)
                EndIf
                'check right
                If pixel.x < pixmap.width-1 And Not isEmpty(pixmap,pixel.x+1,pixel.y,tolerance)
                        NewPixel = TPixel.Create(pixel.x+1,pixel.y,getPixel(Pixmap,pixel.x+1,pixel.y))
                        Stack.Push(NewPixel)
                        PixelList.List.AddLast(NewPixel)
                        PixelList.UpdateBoundingBox(NewPixel.x,NewPixel.y)
                        setPixel(Pixmap,NewPixel.x,NewPixel.y,0)
                EndIf
        Wend
        'Now PixelList contains all the pixels in the tile :)
        Return PixelList
End Function

(you could even shape off some more micro seconds if you give the TObjectList an initial size so that memory allocation is done even less often)

BTW I am also not really used to the new collection stuff but here I thought we could give it a whirl. But I knew already that "TObjectList" is superior to TList in almost any case now (am using it in my codes for some months now).

bye
Ron

[Derron]

@ added "reach" parameter
Your for loop for the reach, am not sure if I interprete it wrong. You default to "reach = 1", but your for loop is doing

Code (BlitzMax) Select Expand


                For Local py:Int = pixel.y-reach To pixel.y+reach
                        For Local px:Int = pixel.x-reach To pixel.x+reach


so if you leave it on the default value, it checks for 3 pixels (left, current, right  ---or--- top, current, bottom).

Either:
- "reach" should default to "0" (so 1 transparent pixel is enough)
- or subtract 1 from passed "reach":
reach 1 = check current pixel only
reach 2 = check one to the left and one to the right + myself
reach 3 ...



Edit: this is my "show" code (bg rect not visible because of drawing opacque pixmaps):

Code (BlitzMax) Select Expand


'test the result
Graphics 800,600
Repeat
Cls

local x:int = 10
local y:int = 10
local padding:int = 10
local maxH:int = 0
For Local pixmap:TPixmap = EachIn tiles
if x + pixmap.width > 800
x = 10
y :+ maxH + padding
maxH = 0
endif

SetColor 75,75,75
DrawRect(x-1, y-1, pixmap.width+2, pixmap.height+2)
SetColor 150,150,150
DrawRect(x, y, pixmap.width, pixmap.height)

SetColor 255,255,255
DrawPixmap(pixmap, x, y)

x :+ pixmap.width + padding
if maxH < pixmap.height then maxH = pixmap.height
Next
Flip

Until KeyHit(KEY_ESCAPE) or AppTerminate()


bye
Ron

[TomToad]

@ added "reach" parameter
Your for loop for the reach, am not sure if I interprete it wrong. You default to "reach = 1", but your for loop is doing

Code (BlitzMax) Select Expand


                For Local py:Int = pixel.y-reach To pixel.y+reach
                        For Local px:Int = pixel.x-reach To pixel.x+reach


so if you leave it on the default value, it checks for 3 pixels (left, current, right  ---or--- top, current, bottom).

Either:
- "reach" should default to "0" (so 1 transparent pixel is enough)
- or subtract 1 from passed "reach":
reach 1 = check current pixel only
reach 2 = check one to the left and one to the right + myself
reach 3 ...

The while loop pulls a pixel from the stack and then checks the surrounding pixels to see if there are any that are "connected".  Using a reach of 1 means that it checks 1 pixel to the left, 1 to the right, 1 up, and 1 down, as well as the 4 diagonal.  And yes, it is also checking the current pixel, which is redundant, but probably faster than checking for an exclusion each iteration, especially when the reach value is larger.

[Derron]

Maybe I just misinterpret "reach". But as you already edited your example the "1" is now more easier to understand. Maybe "reach" is not the right term, maybe it should be described as "minimum sprite distance" or so ?


Nonetheless here is my "do not check first pixel two times" approach (had it done before your post but had to fetch the kids from the kindergarten ).

Code (BlitzMax) Select Expand


'This function uses a recursive backtrack algorithm to obtain all pixels
'  within a tile.  The pixels are added to a pixelList and the alpha is
'  set to 0.  Tolerance is used to determine which pixels are part of the
'  tile
Function ExtractPixels2:TPixelList2(Pixmap:TPixmap, x:Int, y:Int, Tolerance:Byte = $80, Reach:int = 1)
Local stack:TStack<TPixel> = New TStack<TPixel> 'Stack to use in the recursive backtrack
Local PixelList:TPixelList2 = New TPixelList2 'create the pixelList
PixelList.SetBoundingBox(x,x,y,y) 'set the bounding box

Local pixel:TPixel = TPixel.Create(x,y, 0) 'to store currently processed pixel
Local NewPixel:TPixel 'to store pixels to be pushed onto the stack
Repeat
For Local py:Int = pixel.y-reach To pixel.y+reach
For Local px:Int = pixel.x-reach To pixel.x+reach
If py >= 0 And px >= 0 And py < pixmap.height And px < pixmap.width ..
   And Not isEmpty(pixmap,px,py,tolerance)
NewPixel = TPixel.Create(px,py,getPixel(Pixmap,px,py))
Stack.Push(NewPixel)
PixelList.List.AddLast(NewPixel)
PixelList.UpdateBoundingBox(NewPixel.x,NewPixel.y)
setPixel(Pixmap,NewPixel.x,NewPixel.y,0)
EndIf
Next
Next
Until not Stack.TryPop(pixel) 'repeat until the stack is empty

'Now PixelList contains all the pixels in the tile :)
Return PixelList
End Function

PS: algor_i_thm.

bye
Ron

[Derron]

Also your for loops are doing some unneeded checks by looping over X when Y is already exceeding pixmap (so it only affects "reach cols/rows" of the whole pixmap).
It is surely not really improving stuff by more than 0.001% but I still post my 2 cents

Code (BlitzMax) Select Expand


Function ExtractPixels2:TPixelList2(Pixmap:TPixmap, x:Int, y:Int, Tolerance:Byte = $80, Reach:int = 1)
Local stack:TStack<TPixel> = New TStack<TPixel> 'Stack to use in the recursive backtrack
Local PixelList:TPixelList2 = New TPixelList2 'create the pixelList
PixelList.SetBoundingBox(x,x,y,y) 'set the bounding box

Local pixel:TPixel = TPixel.Create(x,y, 0) 'to store currently processed pixel
Local NewPixel:TPixel 'to store pixels to be pushed onto the stack


Repeat
For Local py:Int = Max(0, pixel.y-reach) To pixel.y+reach
if py >= pixmap.height then exit 'skip further x-loops

For Local px:Int = Max(0, pixel.x-reach) To pixel.x+reach
if px >= pixmap.width then exit 'done with this row

If Not isEmpty(pixmap,px,py,tolerance)
NewPixel = TPixel.Create(px,py,getPixel(Pixmap,px,py))
Stack.Push(NewPixel)
PixelList.List.AddLast(NewPixel)
PixelList.UpdateBoundingBox(NewPixel.x,NewPixel.y)
setPixel(Pixmap,NewPixel.x,NewPixel.y,0)
EndIf
Next
Next
Until not Stack.TryPop(pixel) 'repeat until the stack is empty

'Now PixelList contains all the pixels in the tile :)
Return PixelList
End Function



PS: Just want to remind that your initial code was already good stuff and my suggested improvements are not to nitpick or blame anything. Hope you do not mind my posts.

bye
Ron

[TomToad]

Considering that the first version only took me an hour to create, I'm sure there is plenty of room for optimizations.   I wonder how much improvement there would be to putting the upper bounds check into the For/To statemen as well,t instead of doing them each uteration?

Code Select Expand

               For Local py:Int = Max(0, pixel.y-reach) To Min(pixel.y+reach,pixmap.height-1)
                        For Local px:Int = Max(0, pixel.x-reach) To Min(pixel.x+reach,pixmap.width-1)


[Derron]

I had this before - but accidentally tried to even cache the min max in minX,maxX, minY,maxY - without taking care of the actual pixels changing each time - so it did not work and I skipped the "to" variables

It shaped off another huge chunk ...

Code (BlitzMax) Select Expand


Function ExtractPixels2:TPixelList2(Pixmap:TPixmap, x:Int, y:Int, Tolerance:Byte = $80, Reach:int = 1)
Local stack:TStack<TPixel> = New TStack<TPixel> 'Stack to use in the recursive backtrack
Local PixelList:TPixelList2 = New TPixelList2 'create the pixelList
PixelList.SetBoundingBox(x,x,y,y) 'set the bounding box

Local pixel:TPixel = TPixel.Create(x,y, 0) 'to store currently processed pixel
Repeat
For Local py:Int = Max(0, pixel.y-reach) To Min(pixel.y+reach,pixmap.height-1)
For Local px:Int = Max(0, pixel.x-reach) To Min(pixel.x+reach,pixmap.width-1)
If Not isEmpty(pixmap,px,py,tolerance)
pixel = TPixel.Create(px,py,getPixel(Pixmap,px,py))
Stack.Push(pixel)
PixelList.List.AddLast(pixel)
PixelList.UpdateBoundingBox(pixel.x,pixel.y)
setPixel(Pixmap,pixel.x,pixel.y,0)
EndIf
Next
Next
Until not Stack.TryPop(pixel) 'repeat until the stack is empty

'Now PixelList contains all the pixels in the tile :)
Return PixelList
End Function


original: 100 times took 3421ms (34.2099991ms/extraction)
new: 100 times took 1978ms (19.7800007ms/extraction)

Before it was 2500ms. All for a reach of "3" and they include pixmap conversion etc. so we have a certain reachable minimum.