April 02, 2020, 11:04:08 AM

Author Topic: [bmx] Split pixmap into multiple tiles  (Read 303 times)

Offline TomToad

  • Sr. Member
  • ****
  • Posts: 476
[bmx] Split pixmap into multiple tiles
« on: March 03, 2020, 12:15:56 PM »
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
  1. 'Split Tiles
  2. 'author:TomToad
  3. 'created: March 3,2020
  4. 'may be used and modified freely in your own projects
  5. SuperStrict
  6.  
  7. 'the x, y, and color of a single pixel
  8. Type TPixel
  9.         Field x:Int
  10.         Field y:Int
  11.         Field color:Int
  12.        
  13.         Function Create:TPixel(x:Int,y:Int,Color:Int)
  14.                 Local Pixel:TPixel = New TPIxel
  15.                 Pixel.x = x
  16.                 Pixel.y = y
  17.                 Pixel.color = color
  18.                 Return Pixel
  19.         End Function
  20. End Type
  21.  
  22. 'a list of pixels in a tile, plus its bounding box
  23. Type TPixelList
  24.         Field list:TList = CreateList()
  25.         Field xmin:Int, xmax:Int
  26.         Field ymin:Int, ymax:Int
  27.        
  28.         Method SetBoundingBox(xmin:Int, xmax:Int, ymin:Int, ymax:Int)
  29.                 Self.xmin = xmin
  30.                 Self.xmax = xmax
  31.                 Self.ymin = ymin
  32.                 Self.ymax = ymax
  33.         End Method
  34.        
  35.         Method UpdateBoundingBox(x:Int, y:Int)
  36.                 If x < xmin Then xmin = x
  37.                 If x > xmax Then xmax = x
  38.                 If y < ymin Then ymin = y
  39.                 If y > ymax Then ymax = y
  40.         End Method
  41. End Type
  42.  
  43. 'A list of tiles
  44. Local TileList:TList = CreateList()
  45.  
  46. Local filename:String = RequestFile("Tileset")
  47. If Not filename Then End
  48.  
  49. 'load the tileset into a pixmap
  50. Local tileset:TPixmap = LoadPixmap(filename)
  51. If Not tileset Then RuntimeError("Couldn't load "+filename)
  52.  
  53. 'copy the tileset and make sure the pixmap is 32 bit
  54. Local tilesetcopy:TPixmap = ConvertPixmap(tileset,PF_RGBA8888)
  55.  
  56. 'Start with the upper left corner of pixmap and check if it is part of a tile.
  57. '  If it is, then extract the tile into a pixelList and add to TIleList
  58. Local count:Int = 0
  59. For Local y:Int = 0 Until tilesetcopy.height
  60.         For Local x:Int = 0 Until tilesetcopy.width
  61.                 If Not isEmpty(tilesetcopy,x,y,1)
  62.                         Local PixelList:TPixelList = ExtractPixels(tilesetcopy,x,y,1,3)
  63.                         TileList.AddLast(PixelList)
  64.                         count :+ 1
  65.                         Print "found tile #"+count
  66.                 EndIf
  67.         Next
  68. Next
  69.  
  70. 'Now to create the actual tiles
  71. Local tiles:TList = CreateList() 'list to hold the tiles
  72. For Local tile:TPixelList = EachIn TileList 'iterate through each tile
  73.         Local pixmap:TPixmap = CreatePixmap(tile.xmax-tile.xmin+1,tile.ymax-tile.ymin+1,PF_RGBA8888) 'create the tile
  74.         ClearPixels(pixmap) 'clear the pixels
  75.         For Local pixel:TPixel = EachIn tile.list
  76.                 setPixel(pixmap,pixel.x-tile.xmin,pixel.y-tile.ymin,pixel.color) 'copy the pixels
  77.         Next
  78.         tiles.AddLAst(pixmap)
  79. Next
  80.                
  81.  
  82. 'test the result
  83. Graphics 800,600
  84. For Local pixmap:TPixmap = EachIn tiles
  85.         Cls
  86.         DrawPixmap pixmap,0,0
  87.         Flip
  88.         WaitKey()
  89. Next
  90.  
  91.  
  92. 'function to test if a pixel is empty (Alpha < Tolerance)
  93. Function isEmpty:Int(pixmap:TPixmap, x:Int, y:Int, Tolerance:Byte = $80)
  94.         If pixmap.pixels[y*pixmap.pitch+x*4+3] < Tolerance Then Return True
  95.         Return False
  96. End Function
  97.  
  98. 'This function uses a recursive backtrack algorythm to obtain all pixels
  99. '  within a tile.  The pixels are added to a pixelList and the alpha is
  100. '  set to 0.  Tolerance is used to determine which pixels are part of the
  101. '  tile.  Reach determines how close a pixel needs to be to be part of the tile
  102. Function ExtractPixels:TPixelList(Pixmap:TPixmap, x:Int, y:Int, Tolerance:Byte = $80, Reach:Int = 1)
  103.         Local Stack:TList = CreateList() 'Stack to use in the recursive backtrack
  104.         Local PixelList:TPixelList = New TPixelList 'create the pixelList
  105.         PixelList.SetBoundingBox(x,x,y,y) 'set the bounding box
  106.        
  107.         Local pixel:TPixel = TPixel.Create(x,y,getPixel(Pixmap,x,y)) 'get the first pixel
  108.         Stack.AddLast(pixel) 'add to the stack
  109.         PixelList.List.AddLast(pixel) 'add to the pixel list
  110.         setPixel(Pixmap,x,y,0) 'set the pixel to 0 to indicate 'visited'
  111.        
  112.         Local NewPixel:TPixel 'to store pixels to be pushed onto the stack
  113.         While Not Stack.isEmpty() 'repeat until the stack is empty
  114.                 pixel = TPixel(Stack.RemoveFirst())
  115.                 For Local py:Int = pixel.y-reach To pixel.y+reach
  116.                         For Local px:Int = pixel.x-reach To pixel.x+reach
  117.                                 If py >= 0 And px >= 0 And py < pixmap.height And px < pixmap.width ..
  118.                                                         And Not isEMpty(pixmap,px,py,tolerance)
  119.                                         NewPixel = TPixel.Create(px,py,getPixel(Pixmap,px,py))
  120.                                         Stack.AddLast(NewPixel)
  121.                                         PixelList.List.AddLast(NewPixel)
  122.                                         PixelList.UpdateBoundingBox(NewPixel.x,NewPixel.y)
  123.                                         setPixel(Pixmap,NewPixel.x,NewPixel.y,0)
  124.                                 EndIf
  125.                         Next
  126.                 Next
  127.                                        
  128.         Wend
  129.         'Now PixelList contains all the pixels in the tile :)
  130.         Return PixelList
  131. End Function
  132.  
  133. 'quickly read a pixel color from a pixmap
  134. Function getPixel:Int(pixmap:TPixmap,x:Int,y:Int)
  135.         Local PixelIntPtr:Int Ptr = Int Ptr(pixmap.pixels)
  136.         Local PitchInt:Int = pixmap.pitch/4
  137.        
  138.         Return PixelIntPtr[y*PitchInt+x]
  139. End Function
  140.  
  141. 'quickly write to a pixel
  142. Function setPixel(pixmap:TPixmap,x:Int,y:Int,color:Int)
  143.         Local PixelIntPtr:Int Ptr = Int Ptr(pixmap.pixels)
  144.         Local Pitchint:Int = pixmap.pitch/4
  145.        
  146.         PixelIntPtr[y*PitchInt+x] = color
  147. End Function
  148.                        
  149.  

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...
------------------------------------------------
8 rabbits equals 1 rabbyte.

Offline Derron

  • Hero Member
  • *****
  • Posts: 2818
Re: [bmx] Split pixmap into multiple tiles
« Reply #1 on: March 03, 2020, 01:18:52 PM »
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
  1. Type TPixelList2
  2.         Field list:TObjectList = new TObjectList
  3.         Field xmin:Int, xmax:Int
  4.         Field ymin:Int, ymax:Int
  5.        
  6.         Method SetBoundingBox(xmin:Int, xmax:Int, ymin:Int, ymax:Int)
  7.                 Self.xmin = xmin
  8.                 Self.xmax = xmax
  9.                 Self.ymin = ymin
  10.                 Self.ymax = ymax
  11.         End Method
  12.        
  13.         Method UpdateBoundingBox(x:Int, y:Int)
  14.                 If x < xmin Then xmin = x
  15.                 If x > xmax Then xmax = x
  16.                 If y < ymin Then ymin = y
  17.                 If y > ymax Then ymax = y
  18.         End Method
  19. End Type
  20.  
  21. 'This function uses a recursive backtrack algorythm to obtain all pixels
  22. '  within a tile.  The pixels are added to a pixelList and the alpha is
  23. '  set to 0.  Tolerance is used to determine which pixels are part of the
  24. '  tile
  25. Function ExtractPixels2:TPixelList2(Pixmap:TPixmap, x:Int, y:Int, Tolerance:Byte = $80)
  26.         Local stack:TStack<TPixel> = New TStack<TPixel> 'Stack to use in the recursive backtrack
  27.         Local PixelList:TPixelList2 = New TPixelList2 'create the pixelList
  28.         PixelList.SetBoundingBox(x,x,y,y) 'set the bounding box
  29.        
  30.         Local pixel:TPixel = TPixel.Create(x,y,getPixel(Pixmap,x,y)) 'get the first pixel
  31.         Stack.Push(pixel) 'add to the stack
  32.  
  33.         PixelList.List.AddLast(pixel) 'add to the pixel list
  34.  
  35.         setPixel(Pixmap,x,y,0) 'set the pixel to 0 to indicate 'visited'
  36.        
  37.         Local NewPixel:TPixel 'to store pixels to be pushed onto the stack
  38.         While Not Stack.isEmpty() 'repeat until the stack is empty
  39.                 pixel = Stack.Pop()
  40.  
  41.                 'check up
  42.                 If pixel.y > 0 And Not isEmpty(pixmap,pixel.x,pixel.y-1,tolerance)
  43.                         NewPixel = TPixel.Create(pixel.x,pixel.y-1,getPixel(Pixmap,pixel.x,pixel.y-1))
  44.                         Stack.Push(NewPixel)
  45.                         PixelList.List.AddLast(NewPixel)
  46.                         PixelList.UpdateBoundingBox(NewPixel.x,NewPixel.y)
  47.                         setPixel(Pixmap,NewPixel.x,NewPixel.y,0)
  48.                 EndIf
  49.                 'check down
  50.                 If pixel.y < pixmap.width-1 And Not isEmpty(pixmap,pixel.x,pixel.y+1,tolerance)
  51.                         NewPixel = TPixel.Create(pixel.x,pixel.y+1,getPixel(Pixmap,pixel.x,pixel.y+1))
  52.                         Stack.Push(NewPixel)
  53.                         PixelList.List.AddLast(NewPixel)
  54.                         PixelList.UpdateBoundingBox(NewPixel.x,NewPixel.y)
  55.                         setPixel(Pixmap,NewPixel.x,NewPixel.y,0)
  56.                 EndIf
  57.                 'check left
  58.                 If pixel.x > 0 And Not isEmpty(pixmap,pixel.x-1,pixel.y,tolerance)
  59.                         NewPixel = TPixel.Create(pixel.x-1,pixel.y,getPixel(Pixmap,pixel.x-1,pixel.y))
  60.                         Stack.Push(NewPixel)
  61.                         PixelList.List.AddLast(NewPixel)
  62.                         PixelList.UpdateBoundingBox(NewPixel.x,NewPixel.y)
  63.                         setPixel(Pixmap,NewPixel.x,NewPixel.y,0)
  64.                 EndIf
  65.                 'check right
  66.                 If pixel.x < pixmap.width-1 And Not isEmpty(pixmap,pixel.x+1,pixel.y,tolerance)
  67.                         NewPixel = TPixel.Create(pixel.x+1,pixel.y,getPixel(Pixmap,pixel.x+1,pixel.y))
  68.                         Stack.Push(NewPixel)
  69.                         PixelList.List.AddLast(NewPixel)
  70.                         PixelList.UpdateBoundingBox(NewPixel.x,NewPixel.y)
  71.                         setPixel(Pixmap,NewPixel.x,NewPixel.y,0)
  72.                 EndIf
  73.         Wend
  74.         'Now PixelList contains all the pixels in the tile :)
  75.         Return PixelList
  76. End Function
  77.  
(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

Offline Derron

  • Hero Member
  • *****
  • Posts: 2818
Re: [bmx] Split pixmap into multiple tiles
« Reply #2 on: March 03, 2020, 01:42:55 PM »
@ 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
  1.                 For Local py:Int = pixel.y-reach To pixel.y+reach
  2.                         For Local px:Int = pixel.x-reach To pixel.x+reach
  3.  

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
  1. 'test the result
  2. Graphics 800,600
  3. Repeat
  4.         Cls
  5.  
  6.         local x:int = 10
  7.         local y:int = 10
  8.         local padding:int = 10
  9.         local maxH:int = 0
  10.         For Local pixmap:TPixmap = EachIn tiles
  11.                 if x + pixmap.width > 800
  12.                         x = 10
  13.                         y :+ maxH + padding
  14.                         maxH = 0
  15.                 endif
  16.  
  17.                 SetColor 75,75,75
  18.                 DrawRect(x-1, y-1, pixmap.width+2, pixmap.height+2)
  19.                 SetColor 150,150,150
  20.                 DrawRect(x, y, pixmap.width, pixmap.height)
  21.  
  22.                 SetColor 255,255,255
  23.                 DrawPixmap(pixmap, x, y)
  24.                        
  25.                 x :+ pixmap.width + padding
  26.                 if maxH < pixmap.height then maxH = pixmap.height
  27.         Next
  28.         Flip
  29.  
  30. Until KeyHit(KEY_ESCAPE) or AppTerminate()
  31.  

bye
Ron

Offline TomToad

  • Sr. Member
  • ****
  • Posts: 476
Re: [bmx] Split pixmap into multiple tiles
« Reply #3 on: March 03, 2020, 02:36:49 PM »
@ 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
  1.                 For Local py:Int = pixel.y-reach To pixel.y+reach
  2.                         For Local px:Int = pixel.x-reach To pixel.x+reach
  3.  

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.
------------------------------------------------
8 rabbits equals 1 rabbyte.

Offline Derron

  • Hero Member
  • *****
  • Posts: 2818
Re: [bmx] Split pixmap into multiple tiles
« Reply #4 on: March 03, 2020, 03:05:53 PM »
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 :D).

Code: BlitzMax
  1. 'This function uses a recursive backtrack algorithm to obtain all pixels
  2. '  within a tile.  The pixels are added to a pixelList and the alpha is
  3. '  set to 0.  Tolerance is used to determine which pixels are part of the
  4. '  tile
  5. Function ExtractPixels2:TPixelList2(Pixmap:TPixmap, x:Int, y:Int, Tolerance:Byte = $80, Reach:int = 1)
  6.         Local stack:TStack<TPixel> = New TStack<TPixel> 'Stack to use in the recursive backtrack
  7.         Local PixelList:TPixelList2 = New TPixelList2 'create the pixelList
  8.         PixelList.SetBoundingBox(x,x,y,y) 'set the bounding box
  9.  
  10.         Local pixel:TPixel = TPixel.Create(x,y, 0) 'to store currently processed pixel
  11.         Local NewPixel:TPixel 'to store pixels to be pushed onto the stack
  12.         Repeat
  13.                 For Local py:Int = pixel.y-reach To pixel.y+reach
  14.                         For Local px:Int = pixel.x-reach To pixel.x+reach
  15.                                 If py >= 0 And px >= 0 And py < pixmap.height And px < pixmap.width ..
  16.                                    And Not isEmpty(pixmap,px,py,tolerance)
  17.                                         NewPixel = TPixel.Create(px,py,getPixel(Pixmap,px,py))
  18.                                         Stack.Push(NewPixel)
  19.                                         PixelList.List.AddLast(NewPixel)
  20.                                         PixelList.UpdateBoundingBox(NewPixel.x,NewPixel.y)
  21.                                         setPixel(Pixmap,NewPixel.x,NewPixel.y,0)
  22.                                 EndIf
  23.                         Next
  24.                 Next
  25.         Until not Stack.TryPop(pixel) 'repeat until the stack is empty
  26.  
  27.         'Now PixelList contains all the pixels in the tile :)
  28.         Return PixelList
  29. End Function
  30.  
PS: algor_i_thm.

bye
Ron

Offline Derron

  • Hero Member
  • *****
  • Posts: 2818
Re: [bmx] Split pixmap into multiple tiles
« Reply #5 on: March 03, 2020, 03:19:35 PM »
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
  1. Function ExtractPixels2:TPixelList2(Pixmap:TPixmap, x:Int, y:Int, Tolerance:Byte = $80, Reach:int = 1)
  2.         Local stack:TStack<TPixel> = New TStack<TPixel> 'Stack to use in the recursive backtrack
  3.         Local PixelList:TPixelList2 = New TPixelList2 'create the pixelList
  4.         PixelList.SetBoundingBox(x,x,y,y) 'set the bounding box
  5.  
  6.         Local pixel:TPixel = TPixel.Create(x,y, 0) 'to store currently processed pixel
  7.         Local NewPixel:TPixel 'to store pixels to be pushed onto the stack
  8.  
  9.  
  10.         Repeat
  11.                 For Local py:Int = Max(0, pixel.y-reach) To pixel.y+reach
  12.                         if py >= pixmap.height then exit 'skip further x-loops
  13.                        
  14.                         For Local px:Int = Max(0, pixel.x-reach) To pixel.x+reach
  15.                                 if px >= pixmap.width then exit 'done with this row
  16.  
  17.                                 If Not isEmpty(pixmap,px,py,tolerance)
  18.                                         NewPixel = TPixel.Create(px,py,getPixel(Pixmap,px,py))
  19.                                         Stack.Push(NewPixel)
  20.                                         PixelList.List.AddLast(NewPixel)
  21.                                         PixelList.UpdateBoundingBox(NewPixel.x,NewPixel.y)
  22.                                         setPixel(Pixmap,NewPixel.x,NewPixel.y,0)
  23.                                 EndIf
  24.                         Next
  25.                 Next
  26.         Until not Stack.TryPop(pixel) 'repeat until the stack is empty
  27.  
  28.         'Now PixelList contains all the pixels in the tile :)
  29.         Return PixelList
  30. End Function
  31.  


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

Offline TomToad

  • Sr. Member
  • ****
  • Posts: 476
Re: [bmx] Split pixmap into multiple tiles
« Reply #6 on: March 03, 2020, 04:23:57 PM »
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]
               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)
------------------------------------------------
8 rabbits equals 1 rabbyte.

Offline Derron

  • Hero Member
  • *****
  • Posts: 2818
Re: [bmx] Split pixmap into multiple tiles
« Reply #7 on: March 03, 2020, 04:41:05 PM »
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 :D

It shaped off another huge chunk ...

Code: BlitzMax
  1. Function ExtractPixels2:TPixelList2(Pixmap:TPixmap, x:Int, y:Int, Tolerance:Byte = $80, Reach:int = 1)
  2.         Local stack:TStack<TPixel> = New TStack<TPixel> 'Stack to use in the recursive backtrack
  3.         Local PixelList:TPixelList2 = New TPixelList2 'create the pixelList
  4.         PixelList.SetBoundingBox(x,x,y,y) 'set the bounding box
  5.  
  6.         Local pixel:TPixel = TPixel.Create(x,y, 0) 'to store currently processed pixel
  7.         Repeat
  8.                 For Local py:Int = Max(0, pixel.y-reach) To Min(pixel.y+reach,pixmap.height-1)
  9.                         For Local px:Int = Max(0, pixel.x-reach) To Min(pixel.x+reach,pixmap.width-1)
  10.                                 If Not isEmpty(pixmap,px,py,tolerance)
  11.                                         pixel = TPixel.Create(px,py,getPixel(Pixmap,px,py))
  12.                                         Stack.Push(pixel)
  13.                                         PixelList.List.AddLast(pixel)
  14.                                         PixelList.UpdateBoundingBox(pixel.x,pixel.y)
  15.                                         setPixel(Pixmap,pixel.x,pixel.y,0)
  16.                                 EndIf
  17.                         Next
  18.                 Next
  19.         Until not Stack.TryPop(pixel) 'repeat until the stack is empty
  20.  
  21.         'Now PixelList contains all the pixels in the tile :)
  22.         Return PixelList
  23. End Function
  24.  

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.


 

SimplePortal 2.3.6 © 2008-2014, SimplePortal