Saturday, July 2, 2022

Optimise grouping 512x512 coordinates into 117 smaller, quartered chunks

July 02, 2022 kotlin, leaflet No comments

Issue

I'm creating image map tiles for Leaflet.js based on data from a computer game. I'm processing the map data in Kotlin. A map tile server for Leaflet.js has to host image tiles at various zoom-levels, so I need to create them.

These are the resolutions I want to create, based on a source image of 512x512px.

512x512 pixels (zoomed out the most)
256x256 pixels
128x128 pixels
64x64 pixels
32x32 pixels (the most zoomed in)

A code example is at the bottom of this post.

I'm using groupBy at the moment, but the performance isn't great.

// for each possible chunk size...
ChunkSize.entries.flatMap { chunkSize ->
  // and for each tile...
  chunk.tiles.entries.groupBy(
    // get the chunk the tile belongs to
    { (tile, _) -> tile.toChunkPosition(chunkSize) }
  ) { (tile, colour) ->
    tile to colour
  }.map { (chunkPosition, tiles) ->
    // aggregate the grouped tiles into a map, 
    // and create a new chunk
    Chunk(
      tiles = tiles.toMap(),
      size = chunkSize,
      position = chunkPosition,
    )
  }
}
// this can take up to 0.5 seconds

It takes around 0.5 seconds to convert a 512x512px source image into

1 512x512px tile
4 256x256px tiles
16 128x128px tiles
32 64x64px tiles
64 32x32px tiles

I'd like to improve the performance.

Options

Sorting and chunking/windowing

Using windows won't be easy, because the data in the tiles isn't necessarily continuous. There might be gaps between some tiles.

Grouping

I've tried using Grouping, but I didn't note a significant difference. The lazy evaluation isn't useful here, and using a mutable map to try and improve the accumulation didn't help either.

ChunkSize.entries.flatMap { chunkSize ->
  val grouped: Map<ChunkPosition, MutableMap<TilePosition, Colour>> =
    chunk.tiles.entries.groupingBy { (tile, _) ->
      tile.toChunkPosition(chunkSize)
    }.fold(
      initialValueSelector = { _, _ -> mutableMapOf() },
    ) { _, accumulator, (tilePosition, colour) ->
      accumulator[tilePosition] = colour
      accumulator
    }

  grouped.entries.map { (chunkPosition, tiles) ->
    Chunk(
      tiles = tiles,
      size = chunkSize,
      position = chunkPosition,
    )
  }
}

Optimise `toChunkPosition`?

The function for getting the chunk position for every tile, and it's using division, which can be slow.

fun TilePosition.toChunkPosition(chunkSize: ChunkSize) =
  ChunkPosition(
    floor(x.toDouble() / chunkSize.lengthInTiles.toDouble()).toInt(),
    floor(y.toDouble() / chunkSize.lengthInTiles.toDouble()).toInt(),
  )

Coroutines

I'm open to using coroutines, so work can be done in parallel, but first I want to optimise the existing code.

Full code

This is a simplified example. The chunk sizes have been reduced to 1, 2, 4, 8, and 16 pixels.

import kotlin.math.floor
import kotlin.math.pow
import kotlin.math.roundToInt
import kotlin.time.measureTimedValue

val sourceChunk = Chunk(
  size = ChunkSize.MAX,
  position = ChunkPosition(0, 0),
  // create some dummy test data
  tiles = listOf(
    "0000000000000088",
    "1111111110000088",
    "0000000000000088",
    "0000000222722288",
    "0090000000700000",
    "3393333330700000",
    "0090000000700000",
    "0090000444744444",
    "0090000000700000",
    "5595555000700000",
    "0090000000000000",
    "0090000066666666",
  ).flatMapIndexed { y, row ->
    row.mapIndexed { x, colour ->
      TilePosition(x, y) to Colour("$colour")
    }
  }.toMap()
)

fun main() {
  println("Source chunk")
  printChunk(sourceChunk)
  println("-------")

  val (chunks, time) = measureTimedValue {
    subdivideChunk(sourceChunk)
  }

  chunks.forEach {
    println("-------")
    printChunk(it)
  }
  println("-------")
  println("took: $time")
}

fun subdivideChunk(chunk: Chunk): List<Chunk> {


  return ChunkSize.entries.flatMap { chunkSize ->

  val grouped: Map<ChunkPosition, MutableMap<TilePosition, Colour>> =
    chunk.tiles.entries.groupingBy { (tile, _) ->
      tile.toChunkPosition(chunkSize)
    }.fold(
      initialValueSelector = { _, _ -> mutableMapOf() },
    ) { _, accumulator, (tilePosition, colour) ->
      accumulator[tilePosition] = colour
      accumulator
    }

  grouped.entries.map { (chunkPosition, tiles) ->
    Chunk(
      tiles = tiles,
      size = chunkSize,
      position = chunkPosition,
    )
  }

    chunk.tiles.entries.groupBy(
      { (tile, _) -> tile.toChunkPosition(chunkSize) }
    ) { (tile, colour) ->
      tile to colour
    }.map { (chunkPosition, tiles) ->
      Chunk(
        tiles = tiles.toMap(),
        size = chunkSize,
        position = chunkPosition,
      )
    }

    chunk.tiles.entries
      .groupingBy { (tile, _) ->
        tile.toChunkPosition(chunkSize)
      }.fold(mutableMapOf<TilePosition, Colour>()) { accumulator, (tilePosition, colour) ->
        accumulator += tilePosition to colour
        accumulator
      }.map { (chunkPosition, tiles) ->
        Chunk(
          tiles = tiles,
          size = chunkSize,
          position = chunkPosition,
        )
      }
  }
}

fun printChunk(chunk: Chunk) {
  println("chunk ${chunk.position} ${chunk.size}")
  val minX = chunk.tiles.keys.minOf { it.x }
  val minY = chunk.tiles.keys.minOf { it.y }
  val maxX = chunk.tiles.keys.maxOf { it.x }
  val maxY = chunk.tiles.keys.maxOf { it.y }

  (minY..maxY).forEach { y ->
    (minX..maxX).forEach { x ->
      print(chunk.tiles[TilePosition(x, y)]?.rgba ?: " ")
    }
    println()
  }
}


data class Chunk(
  val tiles: Map<TilePosition, Colour>,
  val size: ChunkSize,
  val position: ChunkPosition,
) {
  val topLeftTile: TilePosition = position.toTilePosition(size)
  val bottomRightTile: TilePosition = TilePosition(
    x = topLeftTile.x + size.lengthInTiles - 1,
    y = topLeftTile.y + size.lengthInTiles - 1,
  )

  val xTileRange = topLeftTile.x..bottomRightTile.x
  val yTileRange = topLeftTile.y..bottomRightTile.y

  operator fun contains(tilePosition: TilePosition): Boolean =
    tilePosition.x in xTileRange && tilePosition.y in yTileRange
}

data class Colour(val rgba: String)

data class TilePosition(val x: Int, val y: Int)

fun TilePosition.toChunkPosition(chunkSize: ChunkSize) =
  ChunkPosition(
    floor(x.toDouble() / chunkSize.lengthInTiles.toDouble()).toInt(),
    floor(y.toDouble() / chunkSize.lengthInTiles.toDouble()).toInt(),
  )


data class ChunkPosition(val x: Int, val y: Int)

fun ChunkPosition.toTilePosition(chunkSize: ChunkSize) =
  TilePosition(
    x * chunkSize.lengthInTiles,
    y * chunkSize.lengthInTiles,
  )


enum class ChunkSize(
  val zoomLevel: Int,
) : Comparable<ChunkSize> {
  CHUNK_512(-1),
  CHUNK_256(0),
  CHUNK_128(1),
  CHUNK_064(2),
  CHUNK_032(3),
  ;

  /** 1, 2, 4, 8, or 16 */
  val lengthInTiles: Int = 2f.pow(3 - zoomLevel).roundToInt()

  companion object {
    val entries: Set<ChunkSize> = values().toSet()

    val MAX: ChunkSize = entries.maxByOrNull { it.lengthInTiles }!!
    val MIN: ChunkSize = entries.minByOrNull { it.lengthInTiles }!!
  }
}

Solution

I resolved this with 3 fixes

I didn't need to create sub-tiles for small zoom levels.
Instead of calculating the chunk position for each tile, I instead calculated the position once and then verified if the remaining tiles was within this chunk a 'chunk boundary'
I refactored so that instead of splitting a large chunk into smaller chunks, I built up larger chunks from smaller chunks

The result is twice as fast, when using my basic example. In the full-fat code with real data it's significantly faster, and that's without any further improvements (e.g. using coroutines to process in parallel).

CSS render pixelated

Originally I created smaller tiles because the tiles became blurry as I zoomed in.

However, the original map data is all just pixels. Zooming in doesn't increase the amount of pixels. If you open up the source image in a basic image editor, like Paint, and zoom in you'll see this source image doesn't blur.

The tiles became blurry because my web browser was 'optimising' the images. Instead, I set the CSS property image-rendering: pixelated . This disables the optimisation.

Because of this I no longer need to create zoomed in tiles. Leaflet can instead dynamically scale the larger images.

Group by chunk boundary

Instead of the 'expensive' toChunkPosition() used to determine if a tile is in a specific chunk, I instead created a 'chunk boundary' that has two boundary points - 'left top' and 'right bottom'.

data class ChunkPositionBounds(
  val leftTop: TilePosition,
  val rightBottom: TilePosition,
) : ClosedRange<TilePosition> {

  constructor(chunkPosition: ChunkPosition, chunkSize: ChunkSize) : this(
    chunkPosition.leftTopTile(chunkSize),
    chunkPosition.rightBottomTile(chunkSize),
  )

  override val start: TilePosition
    get() = leftTop

  override val endInclusive: TilePosition
    get() = rightBottom
}

I implemented the ClosedRange<MapTilePosition> so I can create a nice operator function for MapChunkPosition

data class ChunkPosition(val x: Int, val y: Int) {

   fun leftTopTile(chunkSize: ChunkSize): TilePosition =
      TilePosition(
         x * chunkSize.lengthInTiles,
         y * chunkSize.lengthInTiles,
      )

   fun rightBottomTile(chunkSize: ChunkSize): TilePosition =
      leftTopTile(chunkSize) + (chunkSize.lengthInTiles - 1)
}

Now given a chunk I can verify all its tiles have the correct position

/** Verify all [tiles][Chunk.tiles] are contained within [chunk] */
fun validateChunk(chunk: Chunk): Chunk {

   val (validTiles, invalidTiles) = chunk.tiles.entries.partition { (tilePos, _) ->
      tilePos in chunk
   }

   return if (invalidTiles.isNotEmpty()) {
      println("WARNING Chunk $chunk contained ${invalidTiles.size}/${chunk.tiles.size} out-of-bounds tiles $invalidTiles")
      chunk.copy(tiles = validTiles.associate { it.key to it.value })
   } else {
      chunk
   }
}

Re-use previously grouped tiles

The final optimisation is that I only grouped tiles into a chunk in this per-tile basis once. Once I was sure the input data was 'clean', I could re-use the chunked data to create larger tiles.

(This optimisation is not so important given that smaller tiles are not needed thanks to the css-rendering trick - but I'll describe it in case someone else finds this useful.)

/**
 * Get all chunks of size [srcChunkSize] from [srcChunks], then for each source chunk
 * create a new [ChunkPosition], based on [newChunkSize].
 *
 * Group the chunks by the new position, and merge the tiles of each chunk.
 */
fun regroupByChunkSize(
  srcChunks: List<Chunk>,
  srcChunkSize: ChunkSize,
  newChunkSize: ChunkSize,
): List<Chunk> {

  return srcChunks
    .filter { it.size == srcChunkSize }
    .groupBy { chunk ->
      chunk.position
        .leftTopTile(chunk.size)
        .toChunkPosition(newChunkSize)
    }.map { (newChunkPosition, chunks) ->

      val tiles = chunks.flatMap {
        it.tiles.entries
      }.associate { (k, v) -> k to v }

      Chunk(
        tiles = tiles,
        size = newChunkSize,
        position = newChunkPosition,
      )
    }
}

I could then iteratively call regroupByChunkSize(...) to incrementally aggregate chunks.

fun aggregateChunks(
  sourceChunks: List<Chunk>
): List<Chunk> {

  val allGroupedChunks = mutableListOf<Chunk>()

  val groupedChunks032 = sourceChunks.map { chunk -> validateChunk(chunk) }

  allGroupedChunks += groupedChunks032
  allGroupedChunks += regroupByChunkSize(allGroupedChunks, ChunkSize.CHUNK_032, ChunkSize.CHUNK_064)
  allGroupedChunks += regroupByChunkSize(allGroupedChunks, ChunkSize.CHUNK_064, ChunkSize.CHUNK_128)
  allGroupedChunks += regroupByChunkSize(allGroupedChunks, ChunkSize.CHUNK_128, ChunkSize.CHUNK_256)
  allGroupedChunks += regroupByChunkSize(allGroupedChunks, ChunkSize.CHUNK_256, ChunkSize.CHUNK_512)

  return allGroupedChunks.toList()
}

(This could be improved. Also, this example looks strange. The actual code I'm using is using Kafka, so sourceChunks is a live updating list, and each regroupByChunkSize(...) call is an independent Stream Task.)

Full example code

This code is very scruffy. I'm just using it for demo purposes.

If you want to use smaller chunk sizes, then change

val lengthInTiles: Int = 2f.pow(8 - zoomLevel).roundToInt()

val lengthInTiles: Int = 2f.pow(3 - zoomLevel).roundToInt()

import kotlin.math.floor
import kotlin.math.pow
import kotlin.math.roundToInt
import kotlin.random.Random
import kotlin.random.nextInt
import kotlin.time.measureTimedValue


fun main() {
  val sourceChunks = testData()

  val (chunks, time) = measureTimedValue {
    aggregateChunks(sourceChunks)
  }

//  chunks.forEach {
//    println("-------")
//    printChunk(it)
//  }
//  println("-------")
  println("took: $time")
}


fun aggregateChunks(
  sourceChunks: List<Chunk>
): List<Chunk> {

  val allGroupedChunks = mutableListOf<Chunk>()

  val groupedChunks032 = sourceChunks.map { chunk -> validateChunk(chunk) }

  allGroupedChunks += groupedChunks032
  allGroupedChunks += regroupByChunkSize(allGroupedChunks, ChunkSize.CHUNK_032, ChunkSize.CHUNK_064)
  allGroupedChunks += regroupByChunkSize(allGroupedChunks, ChunkSize.CHUNK_064, ChunkSize.CHUNK_128)
  allGroupedChunks += regroupByChunkSize(allGroupedChunks, ChunkSize.CHUNK_128, ChunkSize.CHUNK_256)
  allGroupedChunks += regroupByChunkSize(allGroupedChunks, ChunkSize.CHUNK_256, ChunkSize.CHUNK_512)

  return allGroupedChunks.toList()
}


/** Verify all [tiles][Chunk.tiles] are contained within [chunk] */
fun validateChunk(chunk: Chunk): Chunk {

  val (validTiles, invalidTiles) = chunk.tiles.entries.partition { (tilePos, _) ->
    tilePos in chunk
  }

  return if (invalidTiles.isNotEmpty()) {
    println("WARNING Chunk $chunk contained ${invalidTiles.size}/${chunk.tiles.size} out-of-bounds tiles $invalidTiles")
    chunk.copy(tiles = validTiles.associate { it.key to it.value })
  } else {
    chunk
  }
}


/**
 * Get all chunks of size [srcChunkSize] from [srcChunks], then for each source chunk
 * create a new [ChunkPosition], based on [newChunkSize].
 *
 * Group the chunks by the new position, and merge the tiles of each chunk.
 */
fun regroupByChunkSize(
  srcChunks: List<Chunk>,
  srcChunkSize: ChunkSize,
  newChunkSize: ChunkSize,
): List<Chunk> {

  return srcChunks
    .filter { it.size == srcChunkSize }
    .groupBy { chunk ->
      chunk.position
        .leftTopTile(chunk.size)
        .toChunkPosition(newChunkSize)
    }.map { (newChunkPosition, chunks) ->

      val tiles = chunks.flatMap {
        it.tiles.entries
      }.associate { (k, v) -> k to v }

      Chunk(
        tiles = tiles,
        size = newChunkSize,
        position = newChunkPosition,
      )
    }
}


fun printChunk(chunk: Chunk) {
  println("chunk ${chunk.position} ${chunk.size}")
  val minX = chunk.tiles.keys.minOf { it.x }
  val minY = chunk.tiles.keys.minOf { it.y }
  val maxX = chunk.tiles.keys.maxOf { it.x }
  val maxY = chunk.tiles.keys.maxOf { it.y }

  (minY..maxY).forEach { y ->
    (minX..maxX).forEach { x ->
      print(chunk.tiles[TilePosition(x, y)]?.rgba ?: " ")
    }
    println()
  }
}


data class Chunk(
  val tiles: Map<TilePosition, Colour>,
  val size: ChunkSize,
  val position: ChunkPosition,
) {

  val bounds: ChunkPositionBounds by lazy {
    ChunkPositionBounds(position, size)
  }

  operator fun contains(tilePosition: TilePosition): Boolean {
    return tilePosition in bounds
  }
}


data class ChunkPositionBounds(
  val leftTop: TilePosition,
  val rightBottom: TilePosition,
) : ClosedRange<TilePosition> {

  constructor(chunkPosition: ChunkPosition, chunkSize: ChunkSize) : this(
    chunkPosition.leftTopTile(chunkSize),
    chunkPosition.rightBottomTile(chunkSize),
  )

  override val start: TilePosition
    get() = leftTop

  override val endInclusive: TilePosition
    get() = rightBottom
}


data class Colour(val rgba: String)

data class TilePosition(val x: Int, val y: Int) : Comparable<TilePosition> {

  override operator fun compareTo(other: TilePosition): Int =
    when {
      other.x != x -> x.compareTo(other.x)
      else         -> y.compareTo(other.y)
    }

  operator fun plus(addend: Int) =
    TilePosition(x + addend, y + addend)

  fun toChunkPosition(chunkSize: ChunkSize) =
    ChunkPosition(
      floor(x.toDouble() / chunkSize.lengthInTiles.toDouble()).toInt(),
      floor(y.toDouble() / chunkSize.lengthInTiles.toDouble()).toInt(),
    )
}


data class ChunkPosition(val x: Int, val y: Int) {

  fun leftTopTile(chunkSize: ChunkSize): TilePosition =
    TilePosition(
      x * chunkSize.lengthInTiles,
      y * chunkSize.lengthInTiles,
    )

  fun rightBottomTile(chunkSize: ChunkSize): TilePosition =
    leftTopTile(chunkSize) + (chunkSize.lengthInTiles - 1)
}


enum class ChunkSize(
  val zoomLevel: Int,
) : Comparable<ChunkSize> {
  CHUNK_512(-1),
  CHUNK_256(0),
  CHUNK_128(1),
  CHUNK_064(2),
  CHUNK_032(3),
  ;

  /** 1, 2, 4, 8, or 16 */
  val lengthInTiles: Int = 2f.pow(8 - zoomLevel).roundToInt()

  companion object {
    val entries: Set<ChunkSize> = values().toSet()

    val MAX: ChunkSize = entries.maxByOrNull { it.lengthInTiles }!!
    val MIN: ChunkSize = entries.minByOrNull { it.lengthInTiles }!!
  }
}

fun testData(): List<Chunk> {
  val r = Random(1)

  val src = List(x.ChunkSize.MAX.lengthInTiles) {
    List(x.ChunkSize.MAX.lengthInTiles) { r.nextInt(0..9).toString() }
  }

  return src.flatMapIndexed { y, row ->
    row.mapIndexed { x, colour ->
      val tilePos = TilePosition(x, y)
      val tileColour = Colour("$colour")
      Chunk(
        tiles = mapOf(tilePos to tileColour),
        size = ChunkSize.MIN,
        position = tilePos.toChunkPosition(ChunkSize.MIN),
      )
    }
  }
}

Answered By - aSemy

This Answer collected from stackoverflow and tested by AndroidBugFix community admins, is licensed under cc by-sa 2.5 , cc by-sa 3.0 and cc by-sa 4.0

Saturday, July 2, 2022

Optimise grouping 512x512 coordinates into 117 smaller, quartered chunks

Issue

Options

Sorting and chunking/windowing

Grouping

Optimise `toChunkPosition`?

Coroutines

Full code

Solution

CSS render pixelated

Group by chunk boundary

Re-use previously grouped tiles

Full example code

0 comments:

Post a Comment

Popular Posts

Labels

Saturday, July 2, 2022

Issue

Options

Sorting and chunking/windowing

Grouping

Optimise toChunkPosition?

Coroutines

Full code

Solution

CSS render pixelated

Group by chunk boundary

Re-use previously grouped tiles

Full example code

0 comments:

Post a Comment

Popular Posts

Labels

Optimise `toChunkPosition`?