summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorVito Caputo <vcaputo@pengaru.com>2022-04-29 08:03:23 -0700
committerVito Caputo <vcaputo@pengaru.com>2022-04-29 13:30:02 -0700
commitaa77b6b96694496c46a9f99fa23ba2edbf973aa2 (patch)
tree388ba7b2f08b6f7a726cd41f8cc4f0dc1b048305
parent34811cbe4bf6da3e6e22860890fca4c9fff71252 (diff)
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
-rw-r--r--configure.ac1
-rw-r--r--src/Makefile.am2
-rw-r--r--src/modules/Makefile.am2
-rw-r--r--src/modules/voronoi/Makefile.am3
-rw-r--r--src/modules/voronoi/v2f.h352
-rw-r--r--src/modules/voronoi/voronoi.c431
-rw-r--r--src/til.c2
7 files changed, 791 insertions, 2 deletions
diff --git a/configure.ac b/configure.ac
index 8331d2f..aa45307 100644
--- a/configure.ac
+++ b/configure.ac
@@ -62,5 +62,6 @@ AC_CONFIG_FILES([
src/modules/submit/Makefile
src/modules/swab/Makefile
src/modules/swarm/Makefile
+ src/modules/voronoi/Makefile
])
AC_OUTPUT
diff --git a/src/Makefile.am b/src/Makefile.am
index 20ef90f..10553fe 100644
--- a/src/Makefile.am
+++ b/src/Makefile.am
@@ -3,7 +3,7 @@ SUBDIRS = libs modules
noinst_LTLIBRARIES = libtil.la
libtil_la_SOURCES = til_args.c til_args.h til_fb.c til_fb.h til_knobs.h til.c til.h til_settings.h til_settings.c til_setup.c til_setup.h til_threads.c til_threads.h til_util.c til_util.h
libtil_la_CPPFLAGS = -I@top_srcdir@/src
-libtil_la_LIBADD = modules/blinds/libblinds.la modules/checkers/libcheckers.la modules/compose/libcompose.la modules/drizzle/libdrizzle.la modules/flui2d/libflui2d.la modules/julia/libjulia.la modules/meta2d/libmeta2d.la modules/montage/libmontage.la modules/pixbounce/libpixbounce.la modules/plasma/libplasma.la modules/plato/libplato.la modules/ray/libray.la modules/roto/libroto.la modules/rtv/librtv.la modules/snow/libsnow.la modules/sparkler/libsparkler.la modules/spiro/libspiro.la modules/stars/libstars.la modules/submit/libsubmit.la modules/swab/libswab.la modules/swarm/libswarm.la libs/grid/libgrid.la libs/puddle/libpuddle.la libs/ray/libray.la libs/sig/libsig.la libs/txt/libtxt.la libs/ascii/libascii.la libs/din/libdin.la
+libtil_la_LIBADD = modules/blinds/libblinds.la modules/checkers/libcheckers.la modules/compose/libcompose.la modules/drizzle/libdrizzle.la modules/flui2d/libflui2d.la modules/julia/libjulia.la modules/meta2d/libmeta2d.la modules/montage/libmontage.la modules/pixbounce/libpixbounce.la modules/plasma/libplasma.la modules/plato/libplato.la modules/ray/libray.la modules/roto/libroto.la modules/rtv/librtv.la modules/snow/libsnow.la modules/sparkler/libsparkler.la modules/spiro/libspiro.la modules/stars/libstars.la modules/submit/libsubmit.la modules/swab/libswab.la modules/swarm/libswarm.la modules/voronoi/libvoronoi.la libs/grid/libgrid.la libs/puddle/libpuddle.la libs/ray/libray.la libs/sig/libsig.la libs/txt/libtxt.la libs/ascii/libascii.la libs/din/libdin.la
if ENABLE_ROTOTILLER
bin_PROGRAMS = rototiller
diff --git a/src/modules/Makefile.am b/src/modules/Makefile.am
index 92a4145..e5c9971 100644
--- a/src/modules/Makefile.am
+++ b/src/modules/Makefile.am
@@ -1 +1 @@
-SUBDIRS = blinds checkers compose drizzle flui2d julia meta2d montage pixbounce plasma plato ray roto rtv snow sparkler spiro stars submit swab swarm
+SUBDIRS = blinds checkers compose drizzle flui2d julia meta2d montage pixbounce plasma plato ray roto rtv snow sparkler spiro stars submit swab swarm voronoi
diff --git a/src/modules/voronoi/Makefile.am b/src/modules/voronoi/Makefile.am
new file mode 100644
index 0000000..f26a49b
--- /dev/null
+++ b/src/modules/voronoi/Makefile.am
@@ -0,0 +1,3 @@
+noinst_LTLIBRARIES = libvoronoi.la
+libvoronoi_la_SOURCES = voronoi.c v2f.h
+libvoronoi_la_CPPFLAGS = -I@top_srcdir@/src -I@top_srcdir@/src/libs
diff --git a/src/modules/voronoi/v2f.h b/src/modules/voronoi/v2f.h
new file mode 100644
index 0000000..8f51ee0
--- /dev/null
+++ b/src/modules/voronoi/v2f.h
@@ -0,0 +1,352 @@
+/*
+ * Copyright (C) 2018-2019 - Vito Caputo - <vcaputo@pengaru.com>
+ *
+ * This program is free software: you can redistribute it and/or modify it
+ * under the terms of the GNU General Public License version 3 as published
+ * by the Free Software Foundation.
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program. If not, see <http://www.gnu.org/licenses/>.
+ */
+
+/*
+ * 2D vector operations header
+ *
+ * Variants prefixed with _ return a result vector struct by value.
+ *
+ * Variants missing the _ prefix for vector result operations return a pointer
+ * and must be either supplied the result memory as the first "res" argument
+ * which is then returned after being populated with the result's value, or
+ * NULL to allocate space for the result and that pointer is returned after being
+ * populated with its value. When supplying NULL result pointers the functions
+ * must allocate memory and thus may return NULL on OOM, so callers should
+ * check for NULL returns when supplying NULL for "res".
+ *
+ * Example:
+ * v2f_t foo, *foop;
+ *
+ * foo = _v2f_mult(&(v2f_t){1.f,1.f}, &(v2f_t){2.f,2.f});
+ *
+ * is equivalent to:
+ *
+ * v2f_mult(&foo, &(v2f_t){1.f,1.f}, &(v2f_t){2.f,2.f});
+ *
+ * or dynamically allocated:
+ *
+ * foop = v2f_mult(NULL, &(v2f_t){1.f,1.f}, &(v2f_t){2.f,2.f});
+ * free(foop);
+ *
+ * is equivalent to:
+ *
+ * foop = malloc(sizeof(v2f_t));
+ * v2f_mult(foop, &(v2f_t){1.f,1.f}, &(v2f_t){2.f,2.f});
+ * free(foop);
+ */
+
+#ifndef _V2F_H
+#define _V2F_H
+
+
+#include <math.h>
+#include <stdlib.h>
+
+
+typedef struct v2f_t {
+ float x, y;
+} v2f_t;
+
+
+static inline v2f_t * _v2f_allocated(v2f_t **ptr)
+{
+ if (!*ptr)
+ *ptr = malloc(sizeof(v2f_t));
+
+ return *ptr;
+}
+
+
+static inline v2f_t _v2f_add(const v2f_t *a, const v2f_t *b)
+{
+ return (v2f_t){a->x + b->x, a->y + b->y};
+}
+
+
+static inline v2f_t * v2f_add(v2f_t *res, const v2f_t *a, const v2f_t *b)
+{
+ if (_v2f_allocated(&res))
+ *res = _v2f_add(a, b);
+
+ return res;
+}
+
+
+static inline v2f_t _v2f_sub(const v2f_t *a, const v2f_t *b)
+{
+ return (v2f_t){a->x - b->x, a->y - b->y};
+}
+
+
+static inline v2f_t * v2f_sub(v2f_t *res, const v2f_t *a, const v2f_t *b)
+{
+ if (_v2f_allocated(&res))
+ *res = _v2f_sub(a, b);
+
+ return res;
+}
+
+
+static inline v2f_t _v2f_mult(const v2f_t *a, const v2f_t *b)
+{
+ return (v2f_t){a->x * b->x, a->y * b->y};
+}
+
+
+static inline v2f_t * v2f_mult(v2f_t *res, const v2f_t *a, const v2f_t *b)
+{
+ if (_v2f_allocated(&res))
+ *res = _v2f_mult(a, b);
+
+ return res;
+}
+
+
+static inline v2f_t _v2f_mult_scalar(const v2f_t *v, float scalar)
+{
+ return (v2f_t){ v->x * scalar, v->y * scalar };
+}
+
+
+static inline v2f_t * v2f_mult_scalar(v2f_t *res, const v2f_t *v, float scalar)
+{
+ if (_v2f_allocated(&res))
+ *res = _v2f_mult_scalar(v, scalar);
+
+ return res;
+}
+
+
+static inline v2f_t _v2f_div_scalar(const v2f_t *v, float scalar)
+{
+ return _v2f_mult_scalar(v, 1.f / scalar);
+}
+
+
+static inline v2f_t * v2f_div_scalar(v2f_t *res, const v2f_t *v, float scalar)
+{
+ if (_v2f_allocated(&res))
+ *res = _v2f_div_scalar(v, scalar);
+
+ return res;
+}
+
+
+static inline float v2f_dot(const v2f_t *a, const v2f_t *b)
+{
+ return a->x * b->x + a->y * b->y;
+}
+
+
+static inline float v2f_length(const v2f_t *v)
+{
+ return sqrtf(v2f_dot(v, v));
+}
+
+
+static inline float v2f_distance(const v2f_t *a, const v2f_t *b)
+{
+ return v2f_length(v2f_sub(&(v2f_t){}, a, b));
+}
+
+
+static inline float v2f_distance_sq(const v2f_t *a, const v2f_t *b)
+{
+ v2f_t d = _v2f_sub(a, b);
+
+ return v2f_dot(&d, &d);
+}
+
+
+static inline v2f_t _v2f_normalize(const v2f_t *v)
+{
+ return _v2f_mult_scalar(v, 1.0f / v2f_length(v));
+}
+
+
+static inline v2f_t * v2f_normalize(v2f_t *res, const v2f_t *v)
+{
+ if (_v2f_allocated(&res))
+ *res = _v2f_normalize(v);
+
+ return res;
+}
+
+
+static inline v2f_t _v2f_lerp(const v2f_t *a, const v2f_t *b, float t)
+{
+ v2f_t lerp_a, lerp_b;
+
+ lerp_a = _v2f_mult_scalar(a, 1.0f - t);
+ lerp_b = _v2f_mult_scalar(b, t);
+
+ return _v2f_add(&lerp_a, &lerp_b);
+}
+
+
+static inline v2f_t * v2f_lerp(v2f_t *res, const v2f_t *a, const v2f_t *b, float t)
+{
+ if (_v2f_allocated(&res))
+ *res = _v2f_lerp(a, b, t);
+
+ return res;
+}
+
+
+static inline v2f_t _v2f_nlerp(const v2f_t *a, const v2f_t *b, float t)
+{
+ v2f_t lerp = _v2f_lerp(a, b, t);
+
+ return _v2f_normalize(&lerp);
+}
+
+
+static inline v2f_t * v2f_nlerp(v2f_t *res, const v2f_t *a, const v2f_t *b, float t)
+{
+ if (_v2f_allocated(&res))
+ *res = _v2f_nlerp(a, b, t);
+
+ return res;
+}
+
+
+/*
+ * 1 ab-------bb
+ * | | |
+ * | | |
+ * | | |
+ * 0 aa-------ba
+ * t_x: 0---------1
+ * ^
+ * t_y
+ */
+static inline v2f_t _v2f_bilerp(const v2f_t *aa, const v2f_t *ab, const v2f_t *ba, const v2f_t *bb, float t_x, float t_y)
+{
+ v2f_t xa = _v2f_lerp(aa, ba, t_x);
+ v2f_t xb = _v2f_lerp(ab, bb, t_x);
+
+ return _v2f_lerp(&xa, &xb, t_y);
+}
+
+
+static inline v2f_t * v2f_bilerp(v2f_t *res, const v2f_t *aa, const v2f_t *ab, const v2f_t *ba, const v2f_t *bb, float t_x, float t_y)
+{
+ if (_v2f_allocated(&res))
+ *res = _v2f_bilerp(aa, ab, ba, bb, t_x, t_y);
+
+ return res;
+}
+
+
+/*
+ * abb-------bbb
+ * /| /|
+ * aba-------bba|
+ * | | | |
+ * |aab------|bab
+ * |/ |/
+ * aaa-------baa
+ */
+static inline v2f_t _v2f_trilerp(const v2f_t *aaa, const v2f_t *aba, const v2f_t *aab, const v2f_t *abb, const v2f_t *baa, const v2f_t *bba, const v2f_t *bab, const v2f_t *bbb, float t_x, float t_y, float t_z)
+{
+ v2f_t xya = _v2f_bilerp(aaa, aba, baa, bba, t_x, t_y);
+ v2f_t xyb = _v2f_bilerp(aab, abb, bab, bbb, t_x, t_y);
+
+ return _v2f_lerp(&xya, &xyb, t_z);
+}
+
+
+static inline v2f_t * v2f_trilerp(v2f_t *res, const v2f_t *aaa, const v2f_t *aba, const v2f_t *aab, const v2f_t *abb, const v2f_t *baa, const v2f_t *bba, const v2f_t *bab, const v2f_t *bbb, float t_x, float t_y, float t_z)
+{
+ if (_v2f_allocated(&res))
+ *res = _v2f_trilerp(aaa, aba, aab, abb, baa, bba, bab, bbb, t_x, t_y, t_z);
+
+ return res;
+}
+
+
+static inline v2f_t _v2f_rand(const v2f_t *min, const v2f_t *max)
+{
+ return (v2f_t){
+ .x = min->x + (float)rand() * (1.f/RAND_MAX) * (max->x - min->x),
+ .y = min->y + (float)rand() * (1.f/RAND_MAX) * (max->y - min->y),
+ };
+}
+
+
+static inline v2f_t * v2f_rand(v2f_t *res, const v2f_t *min, const v2f_t *max)
+{
+ if (_v2f_allocated(&res))
+ *res = _v2f_rand(min, max);
+
+ return res;
+}
+
+
+static inline v2f_t _v2f_ceil(const v2f_t *v)
+{
+ return (v2f_t){
+ .x = ceilf(v->x),
+ .y = ceilf(v->y),
+ };
+}
+
+
+static inline v2f_t * v2f_ceil(v2f_t *res, const v2f_t *v)
+{
+ if (_v2f_allocated(&res))
+ *res = _v2f_ceil(v);
+
+ return res;
+}
+
+
+static inline v2f_t _v2f_floor(const v2f_t *v)
+{
+ return (v2f_t){
+ .x = floorf(v->x),
+ .y = floorf(v->y),
+ };
+}
+
+
+static inline v2f_t * v2f_floor(v2f_t *res, const v2f_t *v)
+{
+ if (_v2f_allocated(&res))
+ *res = _v2f_floor(v);
+
+ return res;
+}
+
+
+static inline v2f_t _v2f_clamp(const v2f_t *v, const v2f_t *min, const v2f_t *max)
+{
+ return (v2f_t){
+ .x = v->x < min->x ? min->x : v->x > max->x ? max->x : v->x,
+ .y = v->y < min->y ? min->y : v->y > max->y ? max->y : v->y,
+ };
+}
+
+
+static inline v2f_t * v2f_clamp(v2f_t *res, const v2f_t *v, const v2f_t *min, const v2f_t *max)
+{
+ if (_v2f_allocated(&res))
+ *res = _v2f_clamp(v, min, max);
+
+ return res;
+}
+
+#endif
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 <errno.h>
+#include <float.h>
+#include <stdlib.h>
+#include <string.h>
+
+#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 <vcaputo@pengaru.com> */
+
+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 <vcaputo@pengaru.com>",
+ .flags = TIL_MODULE_OVERLAYABLE,
+};
diff --git a/src/til.c b/src/til.c
index d7281ee..5d375c3 100644
--- a/src/til.c
+++ b/src/til.c
@@ -44,6 +44,7 @@ extern til_module_t stars_module;
extern til_module_t submit_module;
extern til_module_t swab_module;
extern til_module_t swarm_module;
+extern til_module_t voronoi_module;
static const til_module_t *modules[] = {
&blinds_module,
@@ -67,6 +68,7 @@ static const til_module_t *modules[] = {
&submit_module,
&swab_module,
&swarm_module,
+ &voronoi_module,
};
© All Rights Reserved