From aa77b6b96694496c46a9f99fa23ba2edbf973aa2 Mon Sep 17 00:00:00 2001 From: Vito Caputo Date: Fri, 29 Apr 2022 08:03:23 -0700 Subject: modules/voronoi: voronoi diagram module This adds a voronoi diagram module, which when used as an overlay produces a mosaic effect. Some settings: cells=N number of voronoi cells randomize={on,off} randomizes the cell locations every frame dirty={on,off} uses a faster sloppy/dithery-looking method Some TODO items: - use a more space efficient representation of the distance buffer, maybe use uint16_t relative offsets into the cells rather than pointers - capping their quantity to 64KiB - anti-alias edges between cells --- src/modules/voronoi/voronoi.c | 431 ++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 431 insertions(+) create mode 100644 src/modules/voronoi/voronoi.c (limited to 'src/modules/voronoi/voronoi.c') diff --git a/src/modules/voronoi/voronoi.c b/src/modules/voronoi/voronoi.c new file mode 100644 index 0000000..ea68136 --- /dev/null +++ b/src/modules/voronoi/voronoi.c @@ -0,0 +1,431 @@ +#include +#include +#include +#include + +#include "til.h" +#include "til_fb.h" +#include "til_util.h" + +#include "v2f.h" + +/* Rudimentary Voronoi diagram module: + * https://en.wikipedia.org/wiki/Voronoi_diagram + * + * When used as an overlay, the output fragment's contents are sampled for + * coloring the cells producing a realtime mosaic style effect. + */ + +/* Copyright (C) 2022 Vito Caputo */ + +typedef struct voronoi_setup_t { + til_setup_t til_setup; + size_t n_cells; + unsigned randomize:1; + unsigned dirty:1; +} voronoi_setup_t; + +typedef struct voronoi_cell_t { + v2f_t origin; + uint32_t color; +} voronoi_cell_t; + +typedef struct voronoi_distance_t { + voronoi_cell_t *cell; + float distance_sq; +} voronoi_distance_t; + +typedef struct voronoi_distances_t { + int width, height; + size_t size; + voronoi_distance_t *buf; +} voronoi_distances_t; + +typedef struct voronoi_context_t { + voronoi_setup_t setup; + voronoi_distances_t distances; + voronoi_cell_t cells[]; +} voronoi_context_t; + + +#define VORONOI_DEFAULT_N_CELLS 1024 +#define VORONOI_DEFAULT_DIRTY 0 +#define VORONOI_DEFAULT_RANDOMIZE 0 + + +static voronoi_setup_t voronoi_default_setup = { + .n_cells = VORONOI_DEFAULT_N_CELLS, + .dirty = VORONOI_DEFAULT_DIRTY, + .randomize = VORONOI_DEFAULT_RANDOMIZE, +}; + + +static void voronoi_randomize(voronoi_context_t *ctxt) +{ + float inv_rand_max= 1.f / (float)RAND_MAX; + + for (size_t i = 0; i < ctxt->setup.n_cells; i++) { + voronoi_cell_t *p = &ctxt->cells[i]; + + p->origin.x = ((float)rand() * inv_rand_max) * 2.f - 1.f; + p->origin.y = ((float)rand() * inv_rand_max) * 2.f - 1.f; + + p->color = ((uint32_t)(rand() % 256)) << 16; + p->color |= ((uint32_t)(rand() % 256)) << 8; + p->color |= ((uint32_t)(rand() % 256)); + } +} + + +static void * voronoi_create_context(unsigned ticks, unsigned num_cpus, til_setup_t *setup) +{ + voronoi_context_t *ctxt; + + if (!setup) + setup = &voronoi_default_setup.til_setup; + + ctxt = calloc(1, sizeof(voronoi_context_t) + ((voronoi_setup_t *)setup)->n_cells * sizeof(voronoi_cell_t)); + if (!ctxt) + return NULL; + + ctxt->setup = *(voronoi_setup_t *)setup; + + voronoi_randomize(ctxt); + + return ctxt; +} + + +static void voronoi_destroy_context(void *context) +{ + voronoi_context_t *ctxt = context; + + free(ctxt->distances.buf); + free(ctxt); +} + + +static int voronoi_fragmenter(void *context, const til_fb_fragment_t *fragment, unsigned number, til_fb_fragment_t *res_fragment) +{ + voronoi_context_t *ctxt = context; + + return til_fb_fragment_tile_single(fragment, 64, number, res_fragment); +} + + +static inline size_t voronoi_cell_origin_to_distance_idx(const voronoi_context_t *ctxt, const voronoi_cell_t *cell) +{ + size_t x, y; + + x = (cell->origin.x * .5f + .5f) * (float)ctxt->distances.width; + y = (cell->origin.y * .5f + .5f) * (float)ctxt->distances.height; + + return y * ctxt->distances.width + x; +} + + +static void voronoi_jumpfill_pass(voronoi_context_t *ctxt, v2f_t *ds, size_t step) +{ + voronoi_distance_t *d = ctxt->distances.buf; + v2f_t dp = {}; + + dp.y = -1.f; + for (int y = 0; y < ctxt->distances.height; y++, dp.y += ds->y) { + + dp.x = -1.f; + for (int x = 0; x < ctxt->distances.width; x++, dp.x += ds->x, d++) { + voronoi_distance_t *dq; + + if (d->cell && d->distance_sq == 0) + continue; + +#define VORONOI_JUMPFILL \ + if (dq->cell) { \ + float dist_sq = v2f_distance_sq(&dq->cell->origin, &dp); \ + \ + if (!d->cell) { /* we're unassigned, just join dq's cell */ \ + d->cell = dq->cell; \ + d->distance_sq = dist_sq; \ + } else if (dist_sq < d->distance_sq) { /* is dq's cell's origin closer than the present one? then join it */ \ + d->cell = dq->cell; \ + d->distance_sq = dist_sq; \ + } \ + } + + if (x >= step) { + /* can sample to the left */ + dq = d - step; + + VORONOI_JUMPFILL; + + if (y >= step) { + /* can sample above and to the left */ + dq = d - step * ctxt->distances.width - step; + + VORONOI_JUMPFILL; + } + + if (ctxt->distances.height - y > step) { + /* can sample below and to the left */ + dq = d + step * ctxt->distances.width - step; + + VORONOI_JUMPFILL; + } + + } + + if (ctxt->distances.width - x > step) { + /* can sample to the right */ + dq = d + step; + + VORONOI_JUMPFILL; + + if (y >= step) { + /* can sample above and to the right */ + dq = d - step * ctxt->distances.width + step; + + VORONOI_JUMPFILL; + } + + if (ctxt->distances.height - y > step) { + /* can sample below */ + dq = d + step * ctxt->distances.width + step; + + VORONOI_JUMPFILL; + } + } + + if (y >= step) { + /* can sample above */ + dq = d - step * ctxt->distances.width; + + VORONOI_JUMPFILL; + } + + if (ctxt->distances.height - y > step) { + /* can sample below */ + dq = d + step * ctxt->distances.width; + + VORONOI_JUMPFILL; + } + } + } +} + + +static void voronoi_calculate_distances(voronoi_context_t *ctxt) +{ + v2f_t ds = (v2f_t){ + .x = 2.f / ctxt->distances.width, + .y = 2.f / ctxt->distances.height, + }; + + memset(ctxt->distances.buf, 0, ctxt->distances.size * sizeof(*ctxt->distances.buf)); + +#if 0 + /* naive inefficient brute-force but correct algorithm */ + for (size_t i = 0; i < ctxt->setup.n_cells; i++) { + voronoi_distance_t *d = ctxt->distances.buf; + v2f_t dp = {}; + + dp.y = -1.f; + for (int y = 0; y < ctxt->distances.height; y++, dp.y += ds.y) { + + dp.x = -1.f; + for (int x = 0; x < ctxt->distances.width; x++, dp.x += ds.x, d++) { + float dist_sq; + + dist_sq = v2f_distance_sq(&ctxt->cells[i].origin, &dp); + if (!d->cell || dist_sq < d->distance_sq) { + d->cell = &ctxt->cells[i]; + d->distance_sq = dist_sq; + } + } + } + } +#else + /* An attempt at implementing https://en.wikipedia.org/wiki/Jump_flooding_algorithm */ + + /* first assign the obvious zero-distance cell origins */ + for (size_t i = 0; i < ctxt->setup.n_cells; i++) { + voronoi_cell_t *c = &ctxt->cells[i]; + size_t idx; + voronoi_distance_t *d; + + idx = voronoi_cell_origin_to_distance_idx(ctxt, c); + d = &ctxt->distances.buf[idx]; + + d->cell = c; + d->distance_sq = 0.f; + } + + /* now for every distance sample neighbors */ + if (ctxt->setup.dirty) { + for (size_t step = 2; step <= MAX(ctxt->distances.width, ctxt->distances.height); step *= 2) + voronoi_jumpfill_pass(ctxt, &ds, step); + } else { + for (size_t step = MAX(ctxt->distances.width, ctxt->distances.height) / 2; step > 0; step >>= 1) + voronoi_jumpfill_pass(ctxt, &ds, step); + } +#endif +} + + +static void voronoi_sample_colors(voronoi_context_t *ctxt, til_fb_fragment_t *fragment) +{ + for (size_t i = 0; i < ctxt->setup.n_cells; i++) { + voronoi_cell_t *p = &ctxt->cells[i]; + int x, y; + + x = (p->origin.x * .5f + .5f) * fragment->frame_width; + y = (p->origin.y * .5f + .5f) * fragment->frame_height; + + p->color = fragment->buf[y * fragment->pitch + x]; + } +} + + +static void voronoi_prepare_frame(void *context, unsigned ticks, unsigned n_cpus, til_fb_fragment_t *fragment, til_fragmenter_t *res_fragmenter) +{ + voronoi_context_t *ctxt = context; + + *res_fragmenter = voronoi_fragmenter; + + if (!ctxt->distances.buf || + ctxt->distances.width != fragment->frame_width || + ctxt->distances.height != fragment->frame_height) { + + free(ctxt->distances.buf); + ctxt->distances.width = fragment->frame_width; + ctxt->distances.height = fragment->frame_height; + ctxt->distances.size = fragment->frame_width * fragment->frame_height; + ctxt->distances.buf = malloc(sizeof(voronoi_distance_t) * ctxt->distances.size); + + if (!ctxt->setup.randomize) + voronoi_calculate_distances(ctxt); + } + + /* TODO: explore moving voronoi_calculate_distances() into render_fragment (threaded) */ + + if (ctxt->setup.randomize) { + voronoi_randomize(ctxt); + voronoi_calculate_distances(ctxt); + } + + /* if the fragment comes in already cleared/initialized, use it for the colors, producing a mosaic */ + if (fragment->cleared) + voronoi_sample_colors(ctxt, fragment); +} + + +static void voronoi_render_fragment(void *context, unsigned ticks, unsigned cpu, til_fb_fragment_t *fragment) +{ + voronoi_context_t *ctxt = context; + + for (int y = 0; y < fragment->height; y++) { + for (int x = 0; x < fragment->width; x++) { + fragment->buf[y * fragment->pitch + x] = ctxt->distances.buf[(y + fragment->y) * ctxt->distances.width + (fragment->x + x)].cell->color; + } + } +} + + +static int voronoi_setup(const til_settings_t *settings, til_setting_t **res_setting, const til_setting_desc_t **res_desc, til_setup_t **res_setup) +{ + const char *n_cells; + const char *n_cells_values[] = { + "512", + "1024", + "2048", + "4096", + "8192", + "16384", + "32768", + NULL + }; + const char *randomize; + const char *bool_values[] = { + "off", + "on", + NULL + }; + const char *dirty; + int r; + + r = til_settings_get_and_describe_value(settings, + &(til_setting_desc_t){ + .name = "Voronoi cells quantity", + .key = "cells", + .regex = "^[0-9]+", + .preferred = TIL_SETTINGS_STR(VORONOI_DEFAULT_N_CELLS), + .values = n_cells_values, + .annotations = NULL + }, + &n_cells, + res_setting, + res_desc); + if (r) + return r; + + r = til_settings_get_and_describe_value(settings, + &(til_setting_desc_t){ + .name = "Constantly randomize cell placement", + .key = "randomize", + .regex = "^(on|off)", + .preferred = bool_values[VORONOI_DEFAULT_RANDOMIZE], + .values = bool_values, + .annotations = NULL + }, + &randomize, + res_setting, + res_desc); + if (r) + return r; + + r = til_settings_get_and_describe_value(settings, + &(til_setting_desc_t){ + .name = "Use faster, imperfect method", + .key = "dirty", + .regex = "^(on|off)", + .preferred = bool_values[VORONOI_DEFAULT_DIRTY], + .values = bool_values, + .annotations = NULL + }, + &dirty, + res_setting, + res_desc); + if (r) + return r; + + if (res_setup) { + voronoi_setup_t *setup; + + setup = til_setup_new(sizeof(*setup), (void(*)(til_setup_t *))free); + if (!setup) + return -ENOMEM; + + sscanf(n_cells, "%u", &setup->n_cells); + + if (!strcasecmp(randomize, "on")) + setup->randomize = 1; + + if (!strcasecmp(dirty, "on")) + setup->dirty = 1; + + *res_setup = &setup->til_setup; + } + return 0; +} + + +til_module_t voronoi_module = { + .create_context = voronoi_create_context, + .destroy_context = voronoi_destroy_context, + .prepare_frame = voronoi_prepare_frame, + .render_fragment = voronoi_render_fragment, + .setup = voronoi_setup, + .name = "voronoi", + .description = "Voronoi diagram", + .author = "Vito Caputo ", + .flags = TIL_MODULE_OVERLAYABLE, +}; -- cgit v1.2.1