Textbasierte Rendering-/Animations-Engine für das Terminal

Question

Dieses Projekt wurde stark vom beliebten Drawille-Projekt inspiriert, mit dem man mit den Braille-Unicode-Zeichen auf das Terminal zeichnen kann.

Der Vorteil des Zeichnens mit Braille-Zeichen gegenüber normalen ASCII-Zeichen ist einfach: Da jedes "Braille-Zeichen" aus 2 x 4 = 8möglichen Punkten besteht, haben wir 256mögliche Varianten, die wir pro Zeichen zeichnen können. Diese Braille-Muster ermöglichen ein viel „feineres/glatteres“ Zeichnen.

Meine Implementierung enthält auch eine Rendering-Engine, die es ermöglicht, alles, was auf den Bildschirm gezeichnet wird, mithilfe der ncurses-Bibliothek zu animieren. Meine Implementierung zielt darauf ab, sehr performant zu sein durch:

1. Mit minimaler Menge an Speicher.
2. Mit sehr guter Laufzeit.

und trotzdem einfach zu bedienen.

Hier einige Beispiele, die zeigen, was mit dieser Bibliothek gemacht werden kann. Diese Beispiele finden Sie auch in examples.c:

Ich bin bereits ziemlich zufrieden mit der Implementierung meiner Grid-Struktur, die Daten sehr kompakt speichert und auf sie zugreift. Ich bin neugierig, ob die Leistung der Renderstruktur noch weiter verbessert werden kann? Ich versuche bereits, nur das zu rendern, was sich gegenüber dem vorherigen Frame geändert hat, aber vielleicht kann ich es noch mehr optimieren?

Darüber hinaus bin ich mir nicht sicher, ob meine Implementierung die Codierungsrichtlinien im C-Stil gut nutzt. Außerdem möchte ich sicherstellen, dass die Bibliothek benutzerfreundlich ist. Lassen Sie mich also wissen, welche Funktionalität Sie (als Benutzer) von der API dieser Bibliothek erwarten würden und ob Sie etwas vermissen, wenn Sie sie im aktuellen Zustand verwenden.

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

konstanten.c

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

Konstanten.h

#ifndef CONSTANTS_H
#define CONSTANTS_H

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

#endif

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

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

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

Und schließlich das Makefile, um alles zu kompilieren:

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

Ich freue mich über jedes Feedback! Das Projekt ist auch auf GitHub verfügbar:https://github.com/766F6964/DotDotDot

Hinweis : Wenn Sie dies testen, stellen Sie sicher, dass Sie eine Terminal-Schriftart installiert haben, die Braille-Zeichen richtig anzeigen kann, sonst sieht es durcheinander aus.

Answer 1

Ziemlich cooler Code.

Kleiner Rückblick auf einige Nebenprobleme.

sizeof *ptrvs.sizeof type

Code gut sizeof *ptrin 2 von 3 Fällen verwendet.

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

Empfehlen Sie, das fortzusetzen

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

---

Unsachgemäßer Umgang mit Leihmüttern

Obwohl für diesen Code nicht wichtig, ist es besser, Ersatzzeichen zu erkennen und möglicherweise als Fehler zu behandeln (Form Unicode-Ersatzzeichen).

---

Bresenhams Linienalgorithmus

Eine bessere als übliche Umsetzung.

Für diesen Code wurde kein Problem festgestellt.

Im Allgemeinen schlägt Code fehl, wenn x1 - x2oder y1 - y2überläuft. Es gibt Möglichkeiten, dies unsignedzu handhaben, indem Sie den Unterschied handhaben, ohne auf umfassendere Mathematik zurückzugreifen.

Ich würde einen Beispielcode posten, aber mein Ref-Code ist nicht aktuell.

Answer 2

Verwenden Sie benannte Konstanten konsequent

Sie haben grid_widthund grid_heightsehr gut definiert, aber leider verwenden Sie es nicht konsequent. grid_new()Beispielsweise kann die erste Zeile ersetzt werden durch :

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

Außerdem ist es üblich, globale Konstanten wie diese in GROSSBUCHSTABEN zu schreiben, damit sie leichter von Variablen zu unterscheiden sind.

Gebrauch machen vonmemset()

Sie haben Schleifen in grid_clear()und geschrieben grid_fill(), aber Sie können diese Aufgabe einfach mit erledigen memset(), was wahrscheinlicher optimiert ist. Sicherlich grid_clear()kann umgeschrieben werden, um zu tun memset(g->buffer, 0, g->buffer_size * sizeof(*g->buffer)). Wenn g->buffereiner war uint8_t *, dann kannst du ihn auch memset()drinnen verwenden grid_fill().

Verwenden Sie uint8_tfür das Gitter

Sie verwenden nur 8 Bits für jedes Zeichen im Raster, sodass Sie es in einer uint8_tstatt in einer speichern können int. Dies reduziert die Speichernutzung des Grids um den Faktor 4 und ermöglicht auch memset()die Verwendung in grid_fill().

Erwägen Sie, die Nachschlagetabelle fest zu codieren

Du denkst vielleicht, was ist das für eine Blasfemie?! Jeder weiß, dass Sie Hardcoding vermeiden sollten! Aber in diesem Fall sind die Unicode-Braille-Zeichen in Stein gemeißelt, und Sie verschwenden viel Code, um die Zeichen zu generieren, und einige CPU-Zyklen jedes Mal, wenn Sie Ihr Programm starten, wenn Sie einfach schreiben können:

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

Erwägen Sie die Verwendung von ncursesw

Anstatt selbst von wchar_tin einen UTF-8-String konvertieren zu müssen, können Sie die breite Version von ncurses verwenden, mit der Sie wchar_tStrings direkt drucken können. Seit ncurses Version 6 ist dies standardmäßig enthalten, und Sie können breite Zeichenfolgen drucken, die Sie mvaddwstr()anstelle von verwenden können mvprintw().

Erwägen Sie, das Grid nicht selbst zwischenzuspeichern

Ein großes Merkmal von ncurses ist, dass es zwischenspeichert, was auf dem Bildschirm angezeigt wird, und nur die erforderlichen Zeichen und Steuercodes an das Terminal sendet, um zu aktualisieren, was wirklich geändert wurde. Sie tun dasselbe selbst und duplizieren damit, was ncurses tut.

Ich sehe zwei Möglichkeiten, diese Ineffizienz zu beseitigen. Erstens können Sie ganz auf Ihre eigenen Puffer verzichten und einfach mit Curses-Funktionen direkt auf den Bildschirm schreiben. Wenn Sie einen einzelnen Punkt in einem Braille-Zeichen aktualisieren müssen, müssen Sie natürlich wissen, welches Braille-Muster bereits auf dem Bildschirm angezeigt wird. Sie können den Inhalt des Bildschirms mit Befehlen wie zurücklesen mvin_wch(). Der Nachteil ist, dass das Zurücklesen einzelner Zeichen zu vielen Funktionsaufrufen führen kann und Sie das Braille-Zeichen wieder in eine Bitmaske decodieren müssen.

Eine andere Möglichkeit besteht darin, einen einzelnen Puffer zu behalten und bei jeder Aktualisierung einfach den gesamten Puffer an ncurses zu übergeben. Wenn Sie das für ineffizient halten, bedenken Sie, dass Sie selbst bei jeder Aktualisierung den gesamten Puffer in den zwischengespeicherten Puffer kopiert haben. Wenn Sie jedoch diesen Weg gehen, möchten Sie wahrscheinlich den ursprünglichen Puffer zur einfachen Bearbeitung einzelner Punkte und einen zweiten Puffer des Typs wchar_t *haben, den Sie parallel aktualisieren und den Sie an ncurses senden können, um ihn auf einmal zu drucken. Beachten Sie, dass es auch eine gibt wmemset(), die hier hilfreich sein könnte.

Ich würde vorschlagen, sich für die zweite Option zu entscheiden. Sie sollten mit dem Benchmarking Ihres Codes beginnen, damit Sie seine Leistung objektiv messen können.