9
\$\begingroup\$

I have an algorithm that I use to render a text GUI using Swing's Canvas, it looks like this in practice:

enter image description here

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 Renderable objects. These are text gui components, layers, etc.
  • I render them onto a FastTileGraphics object (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 Tile at 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.

\$\endgroup\$
2
\$\begingroup\$

You could either use the real Java console, but that would mean you have to recreate your entire application.

If you really insist to use Swing, I would do it in another way. Create some custom print() methode for printing ASCII-symbols into a buffered-image, scale this image and use it as background for just a single AWT/Swing component. After that you create a custom actionListener for this AWT/Swing component. Now you've created a simple terminal, which will perform much faster. By the way, you also have to rewrite most of your application in this scenario.

PS your application looks cool ;-)

| improve this answer | |
\$\endgroup\$
  • 2
    \$\begingroup\$ The application is written in a way that it doesn't matter how I render. I could write a terminal application with no problem if I wanted. How would this print method look like? I already render into a BufferImage that I then draw onto the Canvas. Why would this be faster? I don't want to scale the image because I want to preserve the crispness of my glyphs. \$\endgroup\$ – Adam Arold Oct 17 at 7:16
  • 1
    \$\begingroup\$ You are using a ton of objects, just for one screen. The print method() would be some kind of copy of System.out.print(), but instead of printing out to console, it draws directly onto a buffered image in a well defined way (You have to define it to your targeted look&feel.). The important thing is, it does that without using any object, (besides 1 graphics object). For example your print() would draw each character in a 7pixel x 5pixel rectangular with some custom font. You draw 80 characters in one line, do this for 25 lines and voila you have some kind of vt-100-terminal dimension. \$\endgroup\$ – paladin Oct 17 at 7:39
  • 2
    \$\begingroup\$ PS resizing an image in a linear way lets your image remain its "crispness". Just use a scale factor which is a natural number. en.wikipedia.org/wiki/Nearest-neighbor_interpolation PPS to answer your question "Why would this be faster?" - You are reducing a lot of overhead, which you've created by using tons of objects for rendering a simple image. "Drawing" a simple int is faster than calculating, rendering, drawing an entire object. \$\endgroup\$ – paladin Oct 17 at 7:47
  • \$\begingroup\$ Right now there is literally no overhead by creating all these objects (~0.06ms). You can see that the 2 bottlenecks are the grouping and the rendering. I would be happy if I could optimize the rendering part, but I'm not sure how your suggestion would apply to my code. \$\endgroup\$ – Adam Arold Oct 17 at 7:51
  • \$\begingroup\$ My suggestion don't apply to your code. Your chosen way is unfortunately an inefficient way to achieve your task. You may try to use AWT-components instead of Swing and may also override their paint() method. AWT is faster than Swing but has less features. For example you need to implement a double-image-buffer by yourself. This would be doable in less effort, because Swing is mostly compatible to AWT. AWT-components are also able to be hardware accelerated (Swing too, but it has still more overhead.), but this makes your app often also platform dependet. Also use an IndexColorModel. \$\endgroup\$ – paladin Oct 17 at 8:09
2
\$\begingroup\$

Example for an IndexColorModel.

/* START */
public static final class GUI {
    public static final Color BLACK =   new Color(0x00, 0x00, 0x00);    
    public static final Color MAROON =  new Color(0x80, 0x00, 0x00);
    public static final Color GREEN =   new Color(0x00, 0x80, 0x00);
    public static final Color OLIVE =   new Color(0x80, 0x80, 0x00);
    public static final Color NAVY =    new Color(0x00, 0x00, 0x80);
    public static final Color PURPLE =  new Color(0x80, 0x00, 0x80);
    public static final Color TEAL =    new Color(0x00, 0x80, 0x80);
    public static final Color SILVER =  new Color(0xC0, 0xC0, 0xC0);
    public static final Color GRAY =    new Color(0x80, 0x80, 0x80);
    public static final Color RED =     new Color(0xFF, 0x00, 0x00);
    public static final Color LIME =    new Color(0x00, 0xFF, 0x00);
    public static final Color YELLOW =  new Color(0xFF, 0xFF, 0x00);
    public static final Color BLUE =    new Color(0x00, 0x00, 0xFF);
    public static final Color FUCHSIA = new Color(0xFF, 0x00, 0xFF);
    public static final Color AQUA =    new Color(0x00, 0xFF, 0xFF);
    public static final Color WHITE =   new Color(0xFF, 0xFF, 0xFF);
    
    public static final Color[] COLOR_ARRAY = {
        BLACK, MAROON, GREEN, OLIVE, NAVY, PURPLE, TEAL, SILVER,
        GRAY, RED, LIME, YELLOW, BLUE, FUCHSIA, AQUA, WHITE
    };
    
    public static final byte[] COLOR_ARRAY_RED_COMPONENTS = {
        (byte)COLOR_ARRAY[0].getRed(),
        (byte)COLOR_ARRAY[1].getRed(),
        (byte)COLOR_ARRAY[2].getRed(),
        (byte)COLOR_ARRAY[3].getRed(),
        (byte)COLOR_ARRAY[4].getRed(),
        (byte)COLOR_ARRAY[5].getRed(),
        (byte)COLOR_ARRAY[6].getRed(),
        (byte)COLOR_ARRAY[7].getRed(),
        (byte)COLOR_ARRAY[8].getRed(),
        (byte)COLOR_ARRAY[9].getRed(),
        (byte)COLOR_ARRAY[10].getRed(),
        (byte)COLOR_ARRAY[11].getRed(),
        (byte)COLOR_ARRAY[12].getRed(),
        (byte)COLOR_ARRAY[13].getRed(),
        (byte)COLOR_ARRAY[14].getRed(),
        (byte)COLOR_ARRAY[15].getRed()
    };
    public static final byte[] COLOR_ARRAY_GREEN_COMPONENTS = {
        (byte)COLOR_ARRAY[0].getGreen(),
        (byte)COLOR_ARRAY[1].getGreen(),
        (byte)COLOR_ARRAY[2].getGreen(),
        (byte)COLOR_ARRAY[3].getGreen(),
        (byte)COLOR_ARRAY[4].getGreen(),
        (byte)COLOR_ARRAY[5].getGreen(),
        (byte)COLOR_ARRAY[6].getGreen(),
        (byte)COLOR_ARRAY[7].getGreen(),
        (byte)COLOR_ARRAY[8].getGreen(),
        (byte)COLOR_ARRAY[9].getGreen(),
        (byte)COLOR_ARRAY[10].getGreen(),
        (byte)COLOR_ARRAY[11].getGreen(),
        (byte)COLOR_ARRAY[12].getGreen(),
        (byte)COLOR_ARRAY[13].getGreen(),
        (byte)COLOR_ARRAY[14].getGreen(),
        (byte)COLOR_ARRAY[15].getGreen()
    };
    public static final byte[] COLOR_ARRAY_BLUE_COMPONENTS = {
        (byte)COLOR_ARRAY[0].getBlue(),
        (byte)COLOR_ARRAY[1].getBlue(),
        (byte)COLOR_ARRAY[2].getBlue(),
        (byte)COLOR_ARRAY[3].getBlue(),
        (byte)COLOR_ARRAY[4].getBlue(),
        (byte)COLOR_ARRAY[5].getBlue(),
        (byte)COLOR_ARRAY[6].getBlue(),
        (byte)COLOR_ARRAY[7].getBlue(),
        (byte)COLOR_ARRAY[8].getBlue(),
        (byte)COLOR_ARRAY[9].getBlue(),
        (byte)COLOR_ARRAY[10].getBlue(),
        (byte)COLOR_ARRAY[11].getBlue(),
        (byte)COLOR_ARRAY[12].getBlue(),
        (byte)COLOR_ARRAY[13].getBlue(),
        (byte)COLOR_ARRAY[14].getBlue(),
        (byte)COLOR_ARRAY[15].getBlue()
    };
    
    public static final IndexColorModel INDEX_COLOR_MODEL = new IndexColorModel(
            4, 16, /* 4bit color range, 16 unique colors */
            COLOR_ARRAY_RED_COMPONENTS,
            COLOR_ARRAY_GREEN_COMPONENTS,
            COLOR_ARRAY_BLUE_COMPONENTS
    );
}
/* END */

For example this IndexColorModel uses only 16 different colors, while using 4bit per color and a 24bit color palette. When applied onto a BufferedImage, like:

new BufferedImage(640, 480, TYPE_BYTE_INDEXED, INDEX_COLOR_MODEL)

It reduces maximal color space to 4bit per color and the chosen 16 different colors. Effectively reducing image data size and thus increasing performance.

An advantage of this INDEX_COLOR_MODEL for your application would be, that you would've just to change the color palette to adjust your application colors. Which is much faster, than to repaint all components in a different color from 24bit RGB-color-space (24bit RGB-color-space is a defacto standard for using BufferedImage in Java.).

You may draw in any color to this INDEX_COLOR_MODEL BufferedImage, your chosen color will be automaticly adjusted to the colorspace of your BufferedImage. But it's adviceable to directly use the colors of your colorspace in the first place, because that's a bit faster.

I suggest you read the Java API documentation regarding this feature: https://docs.oracle.com/en/java/javase/11/docs/api/java.desktop/java/awt/image/IndexColorModel.html

The other functions (hardware acceleration, AWT, overriding paint()) are more or less easy to implement. Search and read some tutorials.

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ This doesn't work at all for me. All I see is a black screen and no error message. The problem is that I need to support transparency and dynamic colors since my users can choose their own colors. \$\endgroup\$ – Adam Arold Oct 19 at 21:34
  • \$\begingroup\$ I suggest you read about what a color palette is. For what do you need transparency? Your users may choose their own colors too, by changing the color palette. public static final Color BLACK = new Color(0x00, 0x00, 0x00); <- this is a 24bit color. Just use something like public static Color userColor = new Color(0x12, 0x34, 0x56);. When you use a "limited/indexed" color space, your "input" colors may become "deformed". What this means: If your "input" color is very dark, it might become just BLACK in the "limited/indexed" color space. Try to use the predefined colors, instead of custom. \$\endgroup\$ – paladin Oct 20 at 19:57
  • \$\begingroup\$ I tried your example but it didn't work. I just saw an empty black screen without error messages. \$\endgroup\$ – Adam Arold Oct 21 at 7:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.