เอ็นจิ้นการแสดงผล / แอนิเมชั่นข้อความสำหรับเทอร์มินัล

Aug 17 2020

โปรเจ็กต์นี้ได้รับแรงบันดาลใจอย่างมากจากโปรเจ็กต์ drawille ที่เป็นที่นิยมซึ่งช่วยให้วาดหนึ่งครั้งไปยังเทอร์มินัลโดยใช้อักขระเบรลล์ยูนิโคด

ข้อได้เปรียบของการวาดภาพด้วยตัวอักษรเบรลล์เมื่อเทียบกับอักขระ ASCII ปกติเป็นเรื่องง่าย: เพราะทุก "อักษรเบรลล์ตัวอักษร" ถูกสร้างขึ้นจาก2 x 4 = 8จุดที่เป็นไปได้เรามี256สายพันธุ์ที่เป็นไปได้เราสามารถวาดต่อตัวอักษร รูปแบบอักษรเบรลล์เหล่านี้ช่วยให้สามารถวาดภาพได้ "ละเอียดกว่า / ราบรื่นกว่า"

การใช้งานของฉันยังมาพร้อมกับเอ็นจิ้นการเรนเดอร์ที่ช่วยให้สามารถสร้างภาพเคลื่อนไหวสิ่งที่วาดไปยังหน้าจอได้โดยใช้ไลบรารี ncurses การใช้งานของฉันมีจุดมุ่งหมายเพื่อการดำเนินการโดย:

  1. ใช้หน่วยความจำน้อยที่สุด
  2. มีรันไทม์ที่ดีมาก

ในขณะที่ยังใช้งานง่าย

นี่คือตัวอย่างบางส่วนที่แสดงให้เห็นถึงสิ่งที่สามารถทำได้กับไลบรารีนี้ ตัวอย่างเหล่านี้สามารถพบได้ในexamples.c:

ฉันค่อนข้างพอใจกับการใช้โครงสร้างกริดของฉันซึ่งจัดเก็บและเข้าถึงข้อมูลในลักษณะที่กะทัดรัดมาก ฉันสงสัยว่าประสิทธิภาพของโครงสร้างการเรนเดอร์สามารถปรับปรุงเพิ่มเติมได้หรือไม่? ฉันพยายามเรนเดอร์เฉพาะสิ่งที่เปลี่ยนแปลงไปจากเฟรมก่อนหน้าอยู่แล้ว แต่ฉันอาจจะปรับให้เหมาะสมมากกว่านี้ได้ไหม

นอกจากนี้ฉันไม่แน่ใจว่าการติดตั้งของฉันใช้ประโยชน์จากแนวทางการเข้ารหัสรูปแบบ C หรือไม่ นอกจากนี้ฉันต้องการให้แน่ใจว่าไลบรารีเป็นมิตรกับผู้ใช้ ดังนั้นโปรดแจ้งให้เราทราบว่าคุณ (ในฐานะผู้ใช้) จะคาดหวังฟังก์ชันใดจาก API ของไลบรารีนี้และหากมีสิ่งใดที่คุณพลาดเมื่อใช้งานในสถานะปัจจุบัน

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

กริด 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

ค่าคงที่ c

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

ค่าคงที่ h

#ifndef CONSTANTS_H
#define CONSTANTS_H

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

#endif

ตัวอย่าง 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);
}

ตัวอย่าง 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;
}

และสุดท้าย Makefile จะรวบรวมทุกอย่าง:

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

ขอขอบคุณทุกคำติชม! โครงการนี้ยังมีอยู่ใน GitHub:https://github.com/766F6964/DotDotDot

หมายเหตุ : เมื่อทดสอบสิ่งนี้ตรวจสอบให้แน่ใจว่าคุณได้ติดตั้งแบบอักษรเทอร์มินัลที่สามารถแสดงอักขระเบรลล์ได้อย่างถูกต้องมิฉะนั้นจะดูยุ่งเหยิง

คำตอบ

3 chux-ReinstateMonica Aug 19 2020 at 13:08

รหัสสวย ๆ

ทบทวนปัญหาด้านข้างเล็กน้อย

sizeof *ptr เทียบกับ sizeof type

ใช้รหัสอย่างดีsizeof *ptrใน 2 จาก 3 กรณี

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

แนะนำให้ดำเนินการต่อไป

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

การจัดการตัวแทนที่ไม่เหมาะสม

แม้ว่าจะไม่สำคัญกับรหัสนี้แต่ควรตรวจหาตัวแทนและอาจจัดการเป็นข้อผิดพลาดได้ดีกว่า (ในรูปแบบอักขระการแทนที่ Unicode)


อัลกอริทึมบรรทัดของ Bresenham

การใช้งานที่ดีกว่าปกติ

สำหรับรหัสนี้ไม่พบปัญหา

ในทั่วไปรหัสล้มเหลวเมื่อx1 - x2หรือy1 - y2ล้น มีวิธีจัดการโดยใช้unsignedเพื่อจัดการกับความแตกต่างโดยไม่ต้องใช้คณิตศาสตร์ที่กว้างขึ้น

ฉันจะโพสต์โค้ดตัวอย่าง แต่รหัสอ้างอิงของฉันไม่เป็นปัจจุบัน

3 G.Sliepen Aug 17 2020 at 22:09

ใช้ค่าคงที่ที่มีชื่ออย่างสม่ำเสมอ

คุณกำหนดgrid_widthและgrid_heightดีมาก แต่น่าเสียดายที่คุณไม่ได้ใช้มันอย่างสม่ำเสมอ ในgrid_new()ตัวอย่างเช่นบรรทัดแรกจะถูกแทนที่ด้วย:

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

นอกจากนี้เป็นเรื่องปกติที่จะต้องมีค่าคงที่ส่วนกลางเช่นค่าเหล่านี้เขียนด้วยตัวพิมพ์ใหญ่ทั้งหมดดังนั้นจึงง่ายต่อการแยกแยะจากตัวแปร

ใช้ประโยชน์จาก memset()

คุณได้เขียนลูปในgrid_clear()และgrid_fill()แต่คุณสามารถทำงานนี้ได้อย่างง่ายดายmemset()ซึ่งมีแนวโน้มที่จะได้รับการปรับให้เหมาะสมมากกว่า แน่นอนว่าgrid_clear()สามารถเขียนใหม่memset(g->buffer, 0, g->buffer_size * sizeof(*g->buffer))ได้ ถ้าg->bufferเป็นuint8_t *แล้วคุณยังสามารถใช้ภายในmemset()grid_fill()

ใช้uint8_tสำหรับกริด

คุณเป็นเพียงการใช้ 8 บิตสำหรับตัวอักษรในตารางแต่ละเพื่อให้คุณสามารถเก็บไว้ในแทนuint8_t intซึ่งจะช่วยลดการใช้หน่วยความจำของกริดโดยปัจจัย 4 และยังช่วยให้memset()สามารถใช้งานgrid_fill()ได้

พิจารณาฮาร์ดโค้ดตารางการค้นหา

คุณอาจคิดว่านี่คือ blasfemy อะไร! ทุกคนรู้ว่าคุณควรหลีกเลี่ยงการเข้ารหัส! แต่ในกรณีนี้อักขระ Unicode Braille ถูกตั้งค่าเป็นก้อนหินและคุณกำลังเสียรหัสจำนวนมากในการสร้างอักขระและวงจร CPU บางส่วนทุกครั้งที่คุณเริ่มโปรแกรมเมื่อคุณสามารถเขียน:

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

พิจารณาใช้ ncursesw

แทนที่จะต้องแปลงwchar_tสตริงจากเป็น UTF-8 ด้วยตัวเองคุณสามารถใช้ ncurses เวอร์ชันกว้างที่ช่วยให้คุณพิมพ์wchar_tสตริงได้โดยตรง เนื่องจาก ncurses เวอร์ชัน 6 สิ่งนี้จะรวมอยู่ในค่าเริ่มต้นและคุณสามารถพิมพ์สตริงแบบกว้างที่คุณสามารถใช้mvaddwstr()แทนmvprintw()ได้

อย่าทำแคชกริดด้วยตัวเอง

คุณสมบัติที่สำคัญของ ncurses คือมันจะแคชสิ่งที่อยู่บนหน้าจอและจะส่งเฉพาะอักขระที่จำเป็นและรหัสควบคุมไปยังเทอร์มินัลเพื่ออัปเดตสิ่งที่มีการเปลี่ยนแปลงจริงๆ คุณกำลังทำสิ่งเดียวกันกับตัวเองดังนั้นการทำซ้ำสิ่งที่ ncurses กำลังทำอยู่

ฉันเห็นสองวิธีในการกำจัดความไร้ประสิทธิภาพนี้ ขั้นแรกคุณสามารถกำจัดบัฟเฟอร์ของคุณเองได้ทั้งหมดและเพียงแค่เขียนลงบนหน้าจอโดยตรงด้วยฟังก์ชันสาปแช่ง แน่นอนว่าหากคุณต้องการอัปเดตจุดเดียวในตัวอักษรเบรลล์คุณต้องรู้ว่ามีรูปแบบอักษรเบรลล์แบบใดอยู่บนหน้าจอแล้ว mvin_wch()คุณสามารถอ่านเนื้อหาของกลับหน้าจอที่มีคำสั่งเช่น ข้อเสียคือการอ่านอักขระแต่ละตัวกลับอาจทำให้เกิดการเรียกใช้ฟังก์ชันจำนวนมากและคุณต้องถอดรหัสอักขระเบรลล์กลับไปเป็นบิตมาสก์

อีกทางเลือกหนึ่งคือเก็บบัฟเฟอร์เดียวและให้บัฟเฟอร์ทั้งหมดเพื่อ ncurses ทุกครั้งที่รีเฟรช หากคุณคิดว่าไม่มีประสิทธิภาพให้พิจารณาว่าคุณกำลังคัดลอกบัฟเฟอร์ทั้งหมดไปยังบัฟเฟอร์แคชทุกการรีเฟรช หากคุณทำเช่นนี้คุณอาจต้องการมีบัฟเฟอร์ดั้งเดิมเพื่อให้ง่ายต่อการจัดการจุดแต่ละจุดและบัฟเฟอร์ที่สองของประเภทwchar_t *ที่คุณอัปเดตพร้อมกันและคุณสามารถส่งไปยัง ncurses เพื่อพิมพ์ได้ในครั้งเดียว หมายเหตุนอกจากนี้ยังมีสิ่งwmemset()ที่อาจเป็นประโยชน์ที่นี่

ฉันขอแนะนำให้ไปที่ตัวเลือกที่สอง คุณควรเริ่มเปรียบเทียบโค้ดของคุณเพื่อที่คุณจะสามารถวัดประสิทธิภาพได้อย่างเป็นกลาง