Text based rendering/animation engine for the terminal

Question

This project was highly inspired by the popular drawille project, that lets one draw to the terminal using the braille unicode characters.

The advantage of drawing with braille characters compared to normal ASCII characters is simple: Because every "braille-character" is made up of 2 x 4 = 8 possible spots, we have 256 possible variants we can draw per character. These braille-patterns allow for much "finer/smoother" drawing.

My implementation also comes with a rendering engine that allows for animating whatever is drawn to the screen by using the ncurses library. My implementation aims to by very performant by:

1. Using minimal amount of memory.
2. Having very good runtime.

while still being easy to use.

Here some examples that demonstrate what can be done with this library. These examples can also be found in examples.c:

I am already fairly happy with the implementation of my grid structure, that stores and accesses data in a very compact manner. I am curious if the performance of the rendering structure can be improved any further? I am already trying to only render what has changed from the previous frame, but maybe I can optimize it even more?

Furthermore, I am unsure if my implementation makes good use of the C-style coding guidelines. Additionally, I want to make sure the library is user friendly. So, let me know what functionality you (as a user) would expect from this library's API, and if there is anything you miss when using it in the current state.

grid.c

#define _POSIX_C_SOURCE 199309L

#include <stdio.h>
#include <stdlib.h>
#include <stddef.h>
#include <time.h>

#include "grid.h"
#include "unicode.h"
#include "constants.h"


grid *grid_new(int grid_width, int grid_height)
{
    if ((grid_width % 2 != 0) || (grid_height % 4 != 0))
        return NULL;

    grid *p_grid = calloc(1, sizeof(*p_grid));

    p_grid->width = grid_width;
    p_grid->height = grid_height;
    p_grid->buffer_size = grid_width / group_width * grid_height / group_height;
    p_grid->buffer = calloc(p_grid->buffer_size, sizeof(int));

    return p_grid;
}

void grid_free(grid *p_grid)
{
    free(p_grid->buffer);
    free(p_grid);
}

void grid_clear(grid *g)
{
    for (int i = 0; i < g->buffer_size; ++i)
    {
        g->buffer[i] = 0x00;
    }
}

void grid_fill(grid *g)
{
    for (int i = 0; i < g->buffer_size; ++i)
    {
        g->buffer[i] = 0xFF;
    }
}

void grid_print_buffer(grid *g, char* tag) {
    printf(tag);
    for (int i = 0; i < g->buffer_size; i++)
    {
        printf("0x%02x%s", g->buffer[i], i == g->buffer_size - 1 ? "\n" : ",");
    }
}

void grid_modify_pixel(grid *g, int x, int y, int value)
{
    // ToDo validate coords
    int bytes_per_line = g->width / group_width;
    int byte_idx = (x / group_width) + (y / group_height) * bytes_per_line;
    int bit_idx = (x % group_width) * group_height + (y % group_height);
    g->buffer[byte_idx] = (g->buffer[byte_idx] & ~(1 << bit_idx)) | (value << bit_idx);
}

void grid_set_pixel(grid *g, int x, int y)
{
    grid_modify_pixel(g, x, y, 1);
}

void grid_unset_pixel(grid *g, int x, int y)
{
    grid_modify_pixel(g, x, y, 0);
}

void grid_draw_line(grid *g, int x1, int y1, int x2, int y2)
{
    // Bresenham's line algorithm
    int x_diff = x1 > x2 ? x1 - x2 : x2 - x1;
    int y_diff = y1 > y2 ? y1 - y2 : y2 - y1;
    int x_direction = x1 <= x2 ? 1 : -1;
    int y_direction = y1 <= y2 ? 1 : -1;

    int err = (x_diff > y_diff ? x_diff : -y_diff) / 2;
    while (1)
    {
        grid_set_pixel(g, x1, y1);
        if (x1 == x2 && y1 == y2)
        {
            break;
        }
        int err2 = err;
        if (err2 > -x_diff)
        {
            err -= y_diff;
            x1 += x_direction;
        }
        if (err2 < y_diff)
        {
            err += x_diff;
            y1 += y_direction;
        }
    }
}

void grid_draw_triangle(grid *g, int x1, int y1, int x2, int y2, int x3, int y3)
{
    // ToDo: Add filling algorithm
    grid_draw_line(g, x1, y1, x2, y2);
    grid_draw_line(g, x2, y2, x3, y3);
    grid_draw_line(g, x3, y3, x1, y1);
}

grid.h

#ifndef GRID_H
#define GRID_H

typedef struct
{
    int width;
    int height;
    int buffer_size;
    int *buffer;
} grid;

grid *grid_new(int grid_width, int grid_height);
void grid_free(grid *p_grid);
void grid_clear(grid *g);
void grid_fill(grid *g);
void grid_print_buffer(grid *g, char* tag);
void grid_modify_pixel(grid *g, int x, int y, int value);
void grid_set_pixel(grid *g, int x, int y);
void grid_unset_pixel(grid *g, int x, int y);
void grid_draw_line(grid *g, int x1, int y1, int x2, int y2);
void grid_draw_triangle(grid *g, int x1, int y1, int x2, int y2, int x3, int y3);

#endif

renderer.c

#include "grid.h"
#include "unicode.h"
#include "renderer.h"
#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include "constants.h"
#include <ncurses.h>
#include <unistd.h>
#include <locale.h>

render_context* p_render_context;
const int braille_offset = 0x2800;
const int TRANSFORMATION_MATRIX[8] ={ 0x01, 0x02, 0x04, 0x40, 0x08, 0x10, 0x20, 0x80 };
wchar_t lookup_table[256] ={};


void renderer_new(grid *p_grid) {

    // Set locale for ncurses to process unicode correctly
    setlocale(LC_ALL, "");

    // Generate braille lookup table
    grid_generate_lookup_table();

    // Create copy of initial grid for caching, but zero out buffer
    grid *p_cached_grid = calloc(1, sizeof(*p_grid));
    p_cached_grid->width = p_grid->width;
    p_cached_grid->height = p_grid->height;
    p_cached_grid->buffer_size = p_grid->buffer_size;
    p_cached_grid->buffer = calloc(p_grid->buffer_size, sizeof(int));

    // Store cached grid in render_context
    p_render_context = calloc(1, sizeof(*p_render_context));
    p_render_context->p_cached_grid = p_cached_grid;
    p_render_context->frames_rendered = 0;

    // Initialize ncurses
    initscr();
    noecho();
    curs_set(0);
}

void renderer_update(grid* p_grid)
{
    // Notes:
    // Should only render the characters that changed from current grid buffer to the cached one
 
    // Iterate over grid and look for differences to cached_grid
    for (int i = 0; i < p_grid->buffer_size; i++)
    {
        // Difference was found, note that this character must be re-rendered
        if (p_grid->buffer[i] != p_render_context->p_cached_grid->buffer[i]) {

            // Compute row and column index of the character we need to re-render
            int pos_x = i % (p_render_context->p_cached_grid->width / group_width);
            int pos_y = i / (p_render_context->p_cached_grid->width / group_width);           
            
            // Obtain correct braille character
            char uc[5];
            int braille = lookup_table[p_grid->buffer[i]];
            int_to_unicode_char(braille, uc);

            // Linebreak if we reached the right end of the grid
            if (i % (p_grid->width / group_width) == 0 && i != 0)
            {
                printw("\n");
            }

            // Render the braille character at the position that changed
            mvprintw(pos_y, pos_x, uc);

            //printw("Change index %i [%i->%i] Rerendering coordinate (%i, %i).\n", i, p_render_context->p_cached_grid->buffer[i], p_grid->buffer[i], pos_x, pos_y);
        }
    }

    // ToDo: Update p_cached_grid
    p_render_context->frames_rendered++;

    //grid_print_buffer(p_render_context->p_cached_grid, "cached: ");
    //grid_print_buffer(p_grid, "current: ");

    // Update cached buffer with current one
    memcpy(p_render_context->p_cached_grid->buffer, p_grid->buffer, sizeof(int) * p_grid->buffer_size);

    // Sleep some milliseconds so that changes are visible to the human eye
    napms(render_delay_ms);

    // Refresh terminal to render changes
    refresh();
}

void renderer_free()
{
    // Wait before all allocations are free'd
    napms(2000);

    // Free all allocations and end ncurses window
    free(p_render_context->p_cached_grid->buffer);
    free(p_render_context->p_cached_grid);
    free(p_render_context);
    endwin();
}

void grid_generate_lookup_table()
{
    for (int i = 0; i < 256; ++i)
    {
        int unicode = braille_offset;
        for (int j = 0; j < 8; ++j)
        {
            if (((i & (1 << j)) != 0))
            {
                unicode += TRANSFORMATION_MATRIX[j];
            }
        }
        lookup_table[i] = unicode;
    }
}

renderer.h

#ifndef RENDERER_H
#define RENDERER_H

#include "grid.h"

typedef struct {
    grid* p_cached_grid;
    int frames_rendered;
} render_context;

void renderer_new(grid* p_grid);
void renderer_update(grid* p_grid);
void renderer_free();
void grid_generate_lookup_table();

#endif

unicode.c

void int_to_unicode_char(unsigned int code, char *chars)
{
    if (code <= 0x7F)
    {
        chars[0] = (code & 0x7F);
        chars[1] = '\0';
    }
    else if (code <= 0x7FF)
    {
        // one continuation byte
        chars[1] = 0x80 | (code & 0x3F);
        code = (code >> 6);
        chars[0] = 0xC0 | (code & 0x1F);
        chars[2] = '\0';
    }
    else if (code <= 0xFFFF)
    {
        // two continuation bytes
        chars[2] = 0x80 | (code & 0x3F);
        code = (code >> 6);
        chars[1] = 0x80 | (code & 0x3F); 
        code = (code >> 6);
        chars[0] = 0xE0 | (code & 0xF);
        chars[3] = '\0';
    }
    else if (code <= 0x10FFFF)
    {
        // three continuation bytes
        chars[3] = 0x80 | (code & 0x3F);
        code = (code >> 6);
        chars[2] = 0x80 | (code & 0x3F);
        code = (code >> 6);
        chars[1] = 0x80 | (code & 0x3F);
        code = (code >> 6);
        chars[0] = 0xF0 | (code & 0x7);
        chars[4] = '\0';
    }
    else
    {
        // unicode replacement character
        chars[2] = 0xEF;
        chars[1] = 0xBF;
        chars[0] = 0xBD;
        chars[3] = '\0';
    }
}

unicode.h

#ifndef UNICODE_H
#define UNICODE_H

void int_to_unicode_char(unsigned int code, char *chars);

#endif

constants.c

const int group_height = 4;
const int group_width = 2;
const int render_delay_ms = 10;

constants.h

#ifndef CONSTANTS_H
#define CONSTANTS_H

extern const int group_height;
extern const int group_width;
extern const int render_delay_ms;

#endif

examples.c

#include <math.h>
#include "grid.h"
#include "renderer.h"
#include <stdio.h>

void example_filling_bar()
{
    int width = 100;
    int height = 24;

    grid *g = grid_new(width, height);
    renderer_new(g);

    // Fill grid from left to right (simple animation)
    renderer_update(g);
    for (int i = 0; i < width; i++)
    {
        for (int j = 0; j < height; j++)
        {
            grid_set_pixel(g, i, j);
        }
        renderer_update(g);
    }

    // Free allocations
    renderer_free();
    grid_free(g);
}

void example_build_block()
{
    int width = 100;
    int height = 40;

    grid *g = grid_new(width, height);
    renderer_new(g);

    for (int x = 0; x < width; x++)
    {
        for (int y = 0; y < height; y++)
        {
            grid_set_pixel(g, x, y);
            renderer_update(g);
        }
    }

    // Free allocations
    renderer_free();
    grid_free(g);
}

void example_sine_tracking()
{
    int width = 124;
    int height = 40;

    grid *g = grid_new(width, height);
    renderer_new(g);

    double shift = 0;

    while (1)
    {
        grid_clear(g);

        // Draw line
        grid_draw_line(g, 0, height / 2, width - 1, (height + sin(shift) * height) / 2);

        // Draw curve
        for (int j = 0; j < width; j++)
        {
            grid_set_pixel(g, j, (height / 2 * sin(0.05 * j + shift) + height / 2));
        }

        // Move curve
        shift += 0.05;

        renderer_update(g);
    }

    // Free allocations
    renderer_free();
    grid_free(g);
}

void example_spiral_effect()
{
    int width = 60;
    int height = 32;

    grid *g = grid_new(width, height);
    renderer_new(g);

    // Start with an empty grid
    grid_clear(g);

    int m = width, n = height;
    int sr = 0, sc = 0, er = m - 1, ec = n - 1;
    while (sr <= er && sc <= ec)
    {
        for (int i = sc; i <= ec; ++i)
        {
            grid_set_pixel(g, sr, i);
            renderer_update(g);
        }
        for (int i = sr + 1; i <= er; ++i)
        {
            grid_set_pixel(g, i, ec);
            renderer_update(g);
        }
        for (int i = ec - 1; sr != er && i >= sc; --i)
        {
            grid_set_pixel(g, er, i);
            renderer_update(g);
        }
        for (int i = er - 1; sc != ec && i > sr; --i)
        {
            grid_set_pixel(g, i, sc);
            renderer_update(g);
        }
        sr++, sc++;
        er--, ec--;
    }

    // Free allocations
    renderer_free();
    grid_free(g);
}

examples.h

#ifndef EXAMPLES_H
#define EXAMPLES_H

#include "grid.h"

void example_filling_bar();
void example_build_block();
void example_sine_tracking();
void example_spiral_effect();

#endif

main.c

#include <stdio.h>
#include <unistd.h>
#include <math.h>
#include "examples.h"

int main()
{  
    //example_sine_tracking();
    //example_build_block();
    example_spiral_effect();
    return 0;
}

And finally, the Makefile to compile everything:

prog:
    gcc -g -o dots examples.c constants.c grid.c unicode.c renderer.c main.c -Wall -Werror -lncursesw -lm
clean:
    rm dots

I appreciate every feedback! The project is also available on GitHub: https://github.com/766F6964/DotDotDot

Note: When testing this, make sure you have a terminal font installed that can display braille characters properly, otherwise it will look messed up.

Answer 1

Pretty cool code.

Little review of some side issues.

sizeof *ptr vs. sizeof type

Code nicely used sizeof *ptr in 2 of 3 cases.

grid *p_cached_grid = calloc(1, sizeof(*p_grid));
p_cached_grid->buffer = calloc(p_grid->buffer_size, sizeof(int));  // why sizeof(int)
p_render_context = calloc(1, sizeof(*p_render_context));

Recommend to continue that

// p_cached_grid->buffer = calloc(p_grid->buffer_size, sizeof(int));
p_cached_grid->buffer = calloc(p_grid->buffer_size, sizeof *(p_cached_grid->buffer));
// or
p_cached_grid->buffer = calloc(p_grid->buffer_size, sizeof p_cached_grid->buffer[0]);
// or other variations.

---

Improper handling of Surrogates

Although not important to this code, better to detect surrogates and maybe handle as an error (form Unicode replacement character).

---

Bresenham's line algorithm

A better than usual implementation.

For this code, no issue seen.

In general code fails when x1 - x2 or y1 - y2 overflows. There are ways to handle this using unsigned to handle the difference without resorting to wider math.

I'd post some sample code, but my ref code is not up to date.

Answer 2

Use named constants consistently

You defined grid_width and grid_height, very good, but unfortunately you are not using it consistently. In grid_new() for example, the first line can be replaced with:

if ((grid_width % group_width != 0) || (grid_height % group_height != 0))

Also, it is customary to have global constants such as these written in ALL CAPS, so it is easier to distinguish from variables.

Make use of memset()

You have written loops in grid_clear() and grid_fill(), but you can easily do this task with memset(), which is more likely to be optimized. For sure, grid_clear() can be rewritten to do memset(g->buffer, 0, g->buffer_size * sizeof(*g->buffer)). If g->buffer was a uint8_t *, then you can also use memset() inside grid_fill().

Use uint8_t for the grid

You are only using 8 bits for each character in the grid, so you can store it in an uint8_t instead of an int. This reduces memory usage of the grid by a factor 4, and also allows memset() to be used in grid_fill().

Consider hardcoding the lookup table

You might think, what blasfemy is this?! Everyone knows you should avoid hardcoding things! But in this case, the Unicode Braille characters are set in stone, and you are wasting a lot of code to generate the characters, and some CPU cycles everytime you start your program, when you can just write:

wchar_t lookup_table[256] = L"⠁⠂⠃⠄⠅⠆⠇⡀⡁⡂⡃⡄⡅⡆⡇"
                            L"⠈⠉⠊⠋⠌⠍⠎⠏...      "
                              ...
                            L"              ...⣿";

Consider using ncursesw

Instead of having to convert from wchar_t to a UTF-8 string yourself, you can use the wide version of ncurses that allows you to print wchar_t strings directly. Since ncurses version 6, this is included by default, and you to print wide strings you can use mvaddwstr() instead of mvprintw().

Consider not caching the grid yourself

A big feature of ncurses is that it caches what is on screen, and will only send the necessary characters and control codes to the terminal to update what has really been changed. You are doing the same yourself, thus duplicating what ncurses is doing.

I see two ways to get rid of this inefficiency. First, you can do away with your own buffers altogether, and just write directly to the screen with curses functions. Of course, if you need to update a single dot in a Braille character, you need to know what Braille pattern is already on screen. You can read the contents of the screen back with commands like mvin_wch(). The drawback is that reading back individual characters might result in lots of function calls, and you have to decode the Braille character back into a bitmask.

Another option is to keep a single buffer, and just give the whole buffer to ncurses every refresh. If you think that is inefficient, consider that you yourself were copying the whole buffer to the cached buffer every refresh. If you go this way though, you probably want to have the original buffer for easy manipulation of individual dots, and a second buffer of type wchar_t * that you update in parallel, and that you can send off to ncurses to print in one go. Note, there is also a wmemset() which might be helpful here.

I would suggest going for the second option. You should start benchmarking your code so you will be able to measure its performance objectively.