I have an algorithm that I use to render a text GUI using Swing's Canvas, it looks like this in practice:
My goal is to reach 60 frames per second for a full HD grid with 8x8 (in pixel) tiles. Right now a full-screen grid composed of 16x16 tiles (1920x1080) renders with 60, but 8x8 tiles have abysmal speed.
I profiled my algorithm and fixed the bottlenecks but now I've reached the limits of Swing itself. This application works with layers composed of Tile objects (with a corresponding Position) so you can imagine a whole thing as a 3D map composed of Tiles with x, y and z coordinates.
My current algorithm works like this:
- I fetch the
Renderableobjects. These are text gui components, layers, etc. - I render them onto a
FastTileGraphicsobject (this uses arrays for speed). - I divide them into chunks according to the parallelism parameter to achieve parallel decomposition of work.
- I group the
Tiles into vertical vectors (I do this because I need to support transparency and tiles can be rendered on top of each other). - If an opaque tile is encountered I overwrite the list since in that case I only need to render a single
Tileat that position. - I render the tiles onto
BufferedImages in parallel. - Then I render these images onto the
Canvas.
The implementation looks like this:
override fun render() {
val now = SystemUtils.getCurrentTimeMs()
val bs: BufferStrategy = canvas.bufferStrategy // this is a regular Swing Canvas object
val parallelism = 4
val interval = tileGrid.width / (parallelism - 1)
val tilesToRender = mutableListOf<MutableMap<Position, MutableList<Pair<Tile, TilesetResource>>>>()
0.until(parallelism).forEach { _ ->
tilesToRender.add(mutableMapOf())
}
val renderables = tileGrid.renderables // TileGrid supplies the renderables that contain the tiles
for (i in renderables.indices) {
val renderable = renderables[i]
if (!renderable.isHidden) {
val graphics = FastTileGraphics(
initialSize = renderable.size,
initialTileset = renderable.tileset,
initialTiles = emptyMap()
)
renderable.render(graphics)
graphics.contents().forEach { (tilePos, tile) ->
val finalPos = tilePos + renderable.position
val idx = finalPos.x / interval
tilesToRender[idx].getOrPut(finalPos) { mutableListOf() }
if (tile.isOpaque) {
tilesToRender[idx][finalPos] = mutableListOf(tile to renderable.tileset)
} else {
tilesToRender[idx][finalPos]?.add(tile to renderable.tileset)
}
}
}
}
canvas.bufferStrategy.drawGraphics.configure().apply {
color = Color.BLACK
fillRect(0, 0, tileGrid.widthInPixels, tileGrid.heightInPixels)
tilesToRender.map(::renderPart).map { it.join() }.forEach { img ->
drawImage(img, 0, 0, null)
}
dispose()
}
bs.show()
lastRender = now
}
private fun renderPart(
tilesToRender: MutableMap<Position, MutableList<Pair<Tile, TilesetResource>>>
): CompletableFuture<BufferedImage> = CompletableFuture.supplyAsync {
val img = BufferedImage(
tileGrid.widthInPixels,
tileGrid.heightInPixels,
BufferedImage.TRANSLUCENT
)
val gc = img.graphics.configure()
for ((pos, tiles) in tilesToRender) {
for ((tile, tileset) in tiles) {
renderTile(
graphics = gc,
position = pos,
tile = tile,
tileset = tilesetLoader.loadTilesetFrom(tileset)
)
}
}
img
}
private fun Graphics.configure(): Graphics2D {
this.color = Color.BLACK
val gc = this as Graphics2D
gc.setRenderingHint(RenderingHints.KEY_ANTIALIASING, RenderingHints.VALUE_ANTIALIAS_OFF)
gc.setRenderingHint(RenderingHints.KEY_RENDERING, RenderingHints.VALUE_RENDER_SPEED)
gc.setRenderingHint(RenderingHints.KEY_DITHERING, RenderingHints.VALUE_DITHER_ENABLE)
gc.setRenderingHint(RenderingHints.KEY_TEXT_ANTIALIASING, RenderingHints.VALUE_TEXT_ANTIALIAS_OFF)
gc.setRenderingHint(RenderingHints.KEY_FRACTIONALMETRICS, RenderingHints.VALUE_FRACTIONALMETRICS_OFF)
gc.setRenderingHint(RenderingHints.KEY_ALPHA_INTERPOLATION, RenderingHints.VALUE_ALPHA_INTERPOLATION_SPEED)
gc.setRenderingHint(RenderingHints.KEY_COLOR_RENDERING, RenderingHints.VALUE_COLOR_RENDER_QUALITY)
return gc
}
private fun renderTile(
graphics: Graphics2D,
position: Position,
tile: Tile,
tileset: Tileset<Graphics2D>
) {
if (tile.isNotEmpty) {
tileset.drawTile(tile, graphics, position)
}
}
Renderable looks like this, it just accepts a TileGraphics for rendering:
interface Renderable : Boundable, Hideable, TilesetOverride {
/**
* Renders this [Renderable] onto the given [TileGraphics] object.
*/
fun render(graphics: TileGraphics)
}
TileGraphics looks like this:
interface TileGraphics {
val tiles: Map<Position, Tile>
fun draw(
tile: Tile,
drawPosition: Position
)
}
and Tileset is an object that loads the textures from the filesystem and draws individual tiles on a surface (Graphics2D in our case):
interface Tileset<T : Any> {
fun drawTile(tile: Tile, surface: T, position: Position)
}
surface here represents the grapics object we use to draw. This is necessary because there is also a LibGDX renderer that works differently. There are also multiple kinds of Tilesets, this is how a regular monospace font is rendered:
override fun drawTile(tile: Tile, surface: Graphics2D, position: Position) {
val s = tile.asCharacterTile().get().character.toString()
val fm = surface.getFontMetrics(font)
val x = position.x * width
val y = position.y * height
surface.font = font
surface.color = tile.backgroundColor.toAWTColor()
surface.fillRect(x, y, resource.width, resource.height)
surface.color = tile.foregroundColor.toAWTColor()
surface.drawString(s, x, y + fm.ascent)
}
This algorithm runs for ~22ms.
I've profiled the whole thing and a major bottleneck is the drawing part:
tilesToRender.map(::renderPart).map { it.join() }.forEach { img ->
drawImage(img, 0, 0, null)
}
If I remove those 3 lines I get ~5ms runtime (so drawing takes ~17ms).
I also noticed that parallel decomposition doesn't help at all. If I remove all parallelism I get similar results. Increasing parallelism results in an FPS drop.
The second biggest bottleneck is the grouping code (the graphics.contents().forEach { (tilePos, tile) -> part), it takes around ~4.5ms.
The numbers in total:
21.696576799999985 <-- all
5.328403500000007 <-- without drawing
4.575503500000005 <-- without any java 2d graphics operations
0.08593370000000009 <-- without grouping
How can I optimize this algorithm? The only part that's mandatory is rendering the renderables: renderable.render(graphics) but I already optimized it and it only takes ~0.8ms, so that's negligible.
