Motor de renderizado/animación basado en texto para el terminal

Question

Este proyecto se inspiró en gran medida en el popular proyecto drawille, que permite dibujar en la terminal utilizando los caracteres braille unicode.

La ventaja de dibujar con caracteres braille en comparación con los caracteres ASCII normales es simple: debido a que cada "carácter braille" se compone de 2 x 4 = 8posibles puntos, tenemos 256posibles variantes que podemos dibujar por carácter. Estos patrones braille permiten un dibujo mucho más "fino/suave".

Mi implementación también viene con un motor de renderizado que permite animar cualquier cosa que se dibuje en la pantalla usando la biblioteca ncurses. Mi implementación tiene como objetivo ser muy eficaz mediante:

1. Usando una cantidad mínima de memoria.
2. Tener muy buen tiempo de ejecución.

sin dejar de ser fácil de usar.

Aquí algunos ejemplos que demuestran lo que se puede hacer con esta librería. Estos ejemplos también se pueden encontrar en examples.c:

Ya estoy bastante contento con la implementación de mi estructura de cuadrícula, que almacena y accede a los datos de una manera muy compacta. Tengo curiosidad por saber si el rendimiento de la estructura de renderizado se puede mejorar aún más. Ya estoy tratando de representar solo lo que ha cambiado desde el cuadro anterior, pero ¿tal vez pueda optimizarlo aún más?

Además, no estoy seguro de si mi implementación hace un buen uso de las pautas de codificación de estilo C. Además, quiero asegurarme de que la biblioteca sea fácil de usar. Entonces, hágame saber qué funcionalidad esperaría usted (como usuario) de la API de esta biblioteca, y si hay algo que extraña al usarla en el estado actual.

grilla.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);
}

grilla.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

renderizador.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;
    }
}

renderizador.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

constantes.c

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

constantes.h

#ifndef CONSTANTS_H
#define CONSTANTS_H

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

#endif

ejemplos.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);
}

ejemplos.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

C Principal

#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;
}

Y finalmente, el Makefile para compilar todo:

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

¡Aprecio cada comentario! El proyecto también está disponible en GitHub:https://github.com/766F6964/DotDotDot

Nota : Al probar esto, asegúrese de tener instalada una fuente de terminal que pueda mostrar los caracteres braille correctamente, de lo contrario, se verá desordenado.

Answer 1

Código bastante bueno.

Pequeña revisión de algunos temas secundarios.

sizeof *ptrcontrasizeof type

Código muy bien utilizado sizeof *ptren 2 de 3 casos.

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));

Recomiendo continuar con eso

// 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.

---

Manejo inadecuado de sustitutos

Aunque no es importante para este código, es mejor detectar sustitutos y tal vez manejarlos como un error (formar el carácter de reemplazo de Unicode).

---

Algoritmo de línea de Bresenham

Una implementación mejor que la habitual.

Para este código, no se ha visto ningún problema.

En general , el código falla cuando x1 - x2o se y1 - y2desborda. Hay formas de manejar esto usando unsignedpara manejar la diferencia sin recurrir a matemáticas más amplias.

Publicaría un código de muestra, pero mi código de referencia no está actualizado.

Answer 2

Usar constantes nombradas consistentemente

Usted definió grid_widthy grid_height, muy bien, pero desafortunadamente no lo está usando de manera consistente. Por grid_new()ejemplo, la primera línea se puede reemplazar con:

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

Además, es habitual tener constantes globales como estas escritas en MAYÚSCULAS, por lo que es más fácil distinguirlas de las variables.

Hacer uso dememset()

Ha escrito bucles en grid_clear()y grid_fill(), pero puede realizar esta tarea fácilmente con memset(), que es más probable que esté optimizado. Por supuesto, grid_clear()se puede reescribir para hacer memset(g->buffer, 0, g->buffer_size * sizeof(*g->buffer)). Si g->bufferera un uint8_t *, entonces también puedes usar memset()inside grid_fill().

Uso uint8_tpara la cuadrícula

Solo está utilizando 8 bits para cada carácter en la cuadrícula, por lo que puede almacenarlo en un uint8_tlugar de un archivo int. Esto reduce el uso de memoria de la cuadrícula en un factor de 4 y también permite memset()su uso en grid_fill().

Considere codificar la tabla de búsqueda

Podrías pensar, ¡¿qué blasfemia es esta?! ¡Todos saben que debes evitar codificar cosas! Pero en este caso, los caracteres Unicode Braille están grabados en piedra, y está desperdiciando una gran cantidad de código para generar los caracteres, y algunos ciclos de CPU cada vez que inicia su programa, cuando solo puede escribir:

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

Considere usar ncursesw

En lugar de tener que convertir wchar_tusted mismo de una cadena UTF-8, puede usar la versión amplia de ncurses que le permite imprimir wchar_tcadenas directamente. Desde la versión 6 de ncurses, esto se incluye de forma predeterminada y puede imprimir cadenas anchas que puede usar mvaddwstr()en lugar de mvprintw().

Considere no almacenar en caché la cuadrícula usted mismo

Una gran característica de ncurses es que almacena en caché lo que está en pantalla y solo enviará los caracteres y códigos de control necesarios a la terminal para actualizar lo que realmente se ha cambiado. Estás haciendo lo mismo tú mismo, duplicando así lo que está haciendo ncurses.

Veo dos maneras de deshacerse de esta ineficiencia. En primer lugar, puede eliminar por completo sus propios búferes y simplemente escribir directamente en la pantalla con funciones curses. Por supuesto, si necesita actualizar un solo punto en un carácter Braille, necesita saber qué patrón Braille ya está en la pantalla. Puede leer el contenido de la pantalla con comandos como mvin_wch(). El inconveniente es que la lectura de caracteres individuales puede generar muchas llamadas a funciones, y debe decodificar el carácter Braille nuevamente en una máscara de bits.

Otra opción es mantener un solo búfer y simplemente darle todo el búfer a ncurses en cada actualización. Si cree que eso es ineficiente, considere que usted mismo estaba copiando todo el búfer en el búfer almacenado en caché cada actualización. Sin embargo, si sigue este camino, probablemente desee tener el búfer original para facilitar la manipulación de puntos individuales y un segundo búfer de tipo wchar_t *que actualice en paralelo y que pueda enviar a ncurses para imprimir de una sola vez. Tenga en cuenta que también hay un wmemset()que podría ser útil aquí.

Sugiero optar por la segunda opción. Debe comenzar a comparar su código para poder medir su rendimiento de manera objetiva.