From d73df8d9b10490b2e09623972cf4d8d5f7b84162 Mon Sep 17 00:00:00 2001 From: Vito Caputo Date: Fri, 1 Sep 2023 21:54:09 -0700 Subject: flow: implement a 3D flow field module This is kind of a particle system, where the particles are pushed around through a 3D vector space treated as a flow field. No physics are being simulated here, it's just treating the flow field as direction vectors that are trilinearly interpolated when sampled to produce a single direction vector. That direction vector gets applied to particles near it. To keep things interesting the flow field evolves by having two distinct flow fields which the simulation progressively alternates sampling from. For every frame, both flow fields are sampled for every particle, but how much weight is given to the influence of one vs. the other varies by a triangle wave over time. When the weight is biased enough to one of the flow fields near a peak/valley in the triangle wave, the other gets re-populated while its influence is negligible, also interpolating its new values with 25% influence from the active field. The current flow field population routine is completely random. Yet there's a surprising amount of emergent order despite being totally randomized direction vectors. Currently supported settings include: size= the width of the 3D flow field cube in direction vectors (the number of vectors is size*size*size) count= the number of particles/elements speed= how far a particle is moved along the current sample's direction vector This was first implemented in 2017, but sat unfinished in a topic branch for myriad reasons. Now that rototiller has much more robust settings infrastructure, among other things, it seemed worth finishing this up and merging. --- src/modules/flow/Makefile.am | 3 + src/modules/flow/ff.c | 124 +++++++++++++++++ src/modules/flow/ff.h | 13 ++ src/modules/flow/flow.c | 318 +++++++++++++++++++++++++++++++++++++++++++ src/modules/flow/v3f.h | 284 ++++++++++++++++++++++++++++++++++++++ 5 files changed, 742 insertions(+) create mode 100644 src/modules/flow/Makefile.am create mode 100644 src/modules/flow/ff.c create mode 100644 src/modules/flow/ff.h create mode 100644 src/modules/flow/flow.c create mode 100644 src/modules/flow/v3f.h (limited to 'src/modules/flow') diff --git a/src/modules/flow/Makefile.am b/src/modules/flow/Makefile.am new file mode 100644 index 0000000..e20d19b --- /dev/null +++ b/src/modules/flow/Makefile.am @@ -0,0 +1,3 @@ +noinst_LTLIBRARIES = libflow.la +libflow_la_SOURCES = flow.c ff.c ff.h v3f.h +libflow_la_CPPFLAGS = -I@top_srcdir@/src diff --git a/src/modules/flow/ff.c b/src/modules/flow/ff.c new file mode 100644 index 0000000..18b55d2 --- /dev/null +++ b/src/modules/flow/ff.c @@ -0,0 +1,124 @@ +#include +#include +#include + +#include "ff.h" +#include "v3f.h" + +typedef struct ff_t { + unsigned size; + v3f_t *fields[2]; + void (*populator)(void *context, unsigned size, const v3f_t *other, v3f_t *field); + void *populator_context; +} ff_t; + + +/* populate the flow field specified by idx */ +void ff_populate(ff_t *ff, unsigned idx) +{ + unsigned other; + + assert(idx < 2); + + other = (idx + 1) % 2; + + ff->populator(ff->populator_context, ff->size, ff->fields[other], ff->fields[idx]); +} + + +ff_t * ff_new(unsigned size, void (*populator)(void *context, unsigned size, const v3f_t *other, v3f_t *field), void *context) +{ + ff_t *ff; + + ff = calloc(1, sizeof(ff_t)); + if (!ff) + return NULL; + + for (int i = 0; i < 2; i++) { + ff->fields[i] = calloc(size * size * size, sizeof(v3f_t)); + if (!ff->fields[i]) { + for (int j = 0; j < i; j++) + free(ff->fields[j]); + + free(ff); + return NULL; + } + } + + ff->size = size; + ff->populator = populator; + ff->populator_context = context; + + for (unsigned i = 0; i < 2; i++) + ff_populate(ff, i); + + return ff; +} + + +void ff_free(ff_t *ff) +{ + for (int i = 0; i < 2; i++) + free(ff->fields[i]); + + free(ff); +} + + +static inline v3f_t ff_sample(v3f_t *field, size_t size, v3f_t *min, v3f_t *max, v3f_t *t) +{ + v3f_t *a, *b, *c, *d, *e, *f, *g, *h; + size_t ss = size * size; + + a = &field[(size_t)min->x * ss + (size_t)max->y * size + (size_t)min->z]; + b = &field[(size_t)max->x * ss + (size_t)max->y * size + (size_t)min->z]; + c = &field[(size_t)min->x * ss + (size_t)min->y * size + (size_t)min->z]; + d = &field[(size_t)max->x * ss + (size_t)min->y * size + (size_t)min->z]; + e = &field[(size_t)min->x * ss + (size_t)max->y * size + (size_t)max->z]; + f = &field[(size_t)max->x * ss + (size_t)max->y * size + (size_t)max->z]; + g = &field[(size_t)min->x * ss + (size_t)min->y * size + (size_t)max->z]; + h = &field[(size_t)max->x * ss + (size_t)min->y * size + (size_t)max->z]; + + return v3f_trilerp(a, b, c, d, e, f, g, h, t); +} + + +/* return an interpolated value from ff for the supplied coordinate */ +/* coordinate must be in the range 0-1,0-1,0-1 */ +/* w must be in the range 0-1 and determines how much of field 0 or 1 contributes to the result */ +v3f_t ff_get(ff_t *ff, v3f_t *coordinate, float w) +{ + v3f_t scaled, min, max, t, A, B; + + assert(w <= 1.f && w >= 0.f); + assert(coordinate->x <= 1.f && coordinate->x >= 0.f); + assert(coordinate->y <= 1.f && coordinate->y >= 0.f); + assert(coordinate->z <= 1.f && coordinate->z >= 0.f); + + scaled = v3f_mult_scalar(coordinate, ff->size - 1); + + /* define the cube flanking the requested coordinate */ + min.x = floorf(scaled.x - 0.5f) + 0.5f; + min.y = floorf(scaled.y - 0.5f) + 0.5f; + min.z = floorf(scaled.z - 0.5f) + 0.5f; + + max.x = min.x + 1.0f; + max.y = min.y + 1.0f; + max.z = min.z + 1.0f; + + t.x = scaled.x - min.x; + t.y = scaled.y - min.y; + t.z = scaled.z - min.z; + + assert((size_t)min.x < ff->size); + assert((size_t)min.x < ff->size); + assert((size_t)min.y < ff->size); + assert((size_t)max.x < ff->size); + assert((size_t)max.x < ff->size); + assert((size_t)max.y < ff->size); + + A = ff_sample(ff->fields[0], ff->size, &min, &max, &t); + B = ff_sample(ff->fields[1], ff->size, &min, &max, &t); + + return v3f_nlerp(&A, &B, w); +} diff --git a/src/modules/flow/ff.h b/src/modules/flow/ff.h new file mode 100644 index 0000000..4d30143 --- /dev/null +++ b/src/modules/flow/ff.h @@ -0,0 +1,13 @@ +#ifndef _FF_H +#define _FF_H + +#include "v3f.h" + +typedef struct ff_t ff_t; + +ff_t * ff_new(unsigned size, void (*populator)(void *context, unsigned size, const v3f_t *other, v3f_t *field), void *context); +void ff_free(ff_t *ff); +v3f_t ff_get(ff_t *ff, v3f_t *coordinate, float w); +void ff_populate(ff_t *ff, unsigned idx); + +#endif diff --git a/src/modules/flow/flow.c b/src/modules/flow/flow.c new file mode 100644 index 0000000..636458f --- /dev/null +++ b/src/modules/flow/flow.c @@ -0,0 +1,318 @@ +#include +#include +#include +#include +#include + +#include "til.h" +#include "til_fb.h" +#include "til_module_context.h" +#include "til_settings.h" + +#include "ff.h" +#include "v3f.h" + +/* Copyright (C) 2017 Vito Caputo */ + +/* TODO: + * - make threaded + * - make colorful + */ + +#define FLOW_DEFAULT_SIZE "8" +#define FLOW_DEFAULT_COUNT "30000" +#define FLOW_DEFAULT_SPEED ".2" + +#define FLOW_MAX_SPEED 40 + +typedef struct flow_element_t { + float lifetime; + v3f_t position; +} flow_element_t; + +typedef struct flow_context_t { + til_module_context_t til_module_context; + ff_t *ff; + unsigned last_populate_idx; + unsigned n_iters; + unsigned n_elements; + flow_element_t elements[]; +} flow_context_t; + +typedef struct flow_setup_t { + til_setup_t til_setup; + + unsigned size; + unsigned count; + float speed; +} flow_setup_t; + + +static void populator(void *context, unsigned size, const v3f_t *other, v3f_t *field) +{ + flow_context_t *ctxt = context; + unsigned *seedp = &ctxt->til_module_context.seed; + unsigned x, y, z; + + for (x = 0; x < size; x++) { + for (y = 0; y < size; y++) { + for (z = 0; z < size; z++) { + v3f_t v = v3f_rand(seedp, -1.0f, 1.0f); + size_t idx = x * size * size + y * size + z; + + field[idx] = v3f_lerp(&other[idx], &v, .75f); + } + } + } +} + + +static inline float rand_within_range(unsigned *seed, float min, float max) +{ + return (min + ((float)rand_r(seed) * (1.0f/RAND_MAX)) * (max - min)); +} + + +static inline flow_element_t rand_element(unsigned *seed) +{ + flow_element_t e; + + e.lifetime = rand_within_range(seed, 0.5f, 20.0f); + e.position = v3f_rand(seed, 0.0f, 1.0f); + + return e; +} + + +static til_module_context_t * flow_create_context(const til_module_t *module, til_stream_t *stream, unsigned seed, unsigned ticks, unsigned n_cpus, til_setup_t *setup) +{ + flow_setup_t *s = (flow_setup_t *)setup; + flow_context_t *ctxt; + unsigned i; + + ctxt = til_module_context_new(module, sizeof(flow_context_t) + sizeof(ctxt->elements[0]) * s->count, stream, seed, ticks, n_cpus, setup); + if (!ctxt) + return NULL; + + ctxt->ff = ff_new(s->size, populator, ctxt); + if (!ctxt->ff) + return til_module_context_free(&ctxt->til_module_context); + + for (i = 0; i < s->count; i++) + ctxt->elements[i] = rand_element(&ctxt->til_module_context.seed); + + ctxt->n_iters = ceilf(s->speed * FLOW_MAX_SPEED); + ctxt->n_elements = s->count; + + return &ctxt->til_module_context; +} + + +static void flow_destroy_context(til_module_context_t *context) +{ + flow_context_t *ctxt = (flow_context_t *)context; + + ff_free(ctxt->ff); + free(context); +} + + +static inline uint32_t color_to_uint32_rgb(v3f_t color) { + uint32_t pixel; + + /* doing this all per-pixel, ugh. */ + + color = v3f_clamp_scalar(0.0f, 1.0f, &color); + + pixel = (uint32_t)(color.x * 255.0f); + pixel <<= 8; + pixel |= (uint32_t)(color.y * 255.0f); + pixel <<= 8; + pixel |= (uint32_t)(color.z * 255.0f); + + return pixel; +} + + +static void flow_render_fragment(til_module_context_t *context, til_stream_t *stream, unsigned ticks, unsigned cpu, til_fb_fragment_t **fragment_ptr) +{ + flow_context_t *ctxt = (flow_context_t *)context; + til_fb_fragment_t *fragment = *fragment_ptr; + float w; + + til_fb_fragment_clear(fragment); + + w = (M_2_PI * asinf(fabsf(sinf((ticks * .001f))))) * 2.f - 1.f; + /* ^^ this approximates a triangle wave, + * a sine wave dwells too long for the illusion of continuously evolving + */ + + for (unsigned j = 0; j < ctxt->n_elements; j++) { + flow_element_t *e = &ctxt->elements[j]; + v3f_t pos = e->position; + v3f_t v = ff_get(ctxt->ff, &pos, w * .5f + .5f); + + v = v3f_mult_scalar(&v, .001f); + + for (unsigned k = 0; k < ctxt->n_iters; k++) { + unsigned x, y; + v3f_t color; + + pos = v3f_add(&pos, &v); +#define ZCONST 1.0f + x = (pos.x * 2.f - 1.f) / (pos.z + ZCONST) * fragment->width + (fragment->width >> 1); + y = (pos.y * 2.f - 1.f) / (pos.z + ZCONST) * fragment->height + (fragment->height >> 1) ; + + color.x = color.y = color.z = e->lifetime; + + if (!til_fb_fragment_put_pixel_checked(fragment, TIL_FB_DRAW_FLAG_TEXTURABLE, x, y, color_to_uint32_rgb(color)) || + pos.x < 0.f || pos.x > 1.f || + pos.y < 0.f || pos.y > 1.f || + pos.z < 0.f || pos.z > 1.f) + *e = rand_element(&ctxt->til_module_context.seed); + else + e->position = pos; + } + + e->lifetime -= .1f; + if (e->lifetime <= 0.0f) + *e = rand_element(&ctxt->til_module_context.seed); + } + + /* Re-populate the other field before changing directions. + * note if the frame rate is too low and we miss a >.95 sample + * this will regress to just revisiting the previous field which + * is relatively harmless. + */ + if (fabsf(w) > .95f) { + unsigned other_idx; + + other_idx = rintf(-w * .5f + .5f); + if (other_idx != ctxt->last_populate_idx) { + ff_populate(ctxt->ff, other_idx); + ctxt->last_populate_idx = other_idx; + } + } +} + + +static int flow_setup(const til_settings_t *settings, til_setting_t **res_setting, const til_setting_desc_t **res_desc, til_setup_t **res_setup); + + +til_module_t flow_module = { + .create_context = flow_create_context, + .destroy_context = flow_destroy_context, + .render_fragment = flow_render_fragment, + .setup = flow_setup, + .name = "flow", + .description = "3D flow field", + .author = "Vito Caputo ", + .flags = TIL_MODULE_OVERLAYABLE, +}; + + +static int flow_setup(const til_settings_t *settings, til_setting_t **res_setting, const til_setting_desc_t **res_desc, til_setup_t **res_setup) +{ + til_setting_t *size; + const char *size_values[] = { + "2", + "4", + "8", + "16", + "32", + NULL + }; + til_setting_t *count; + const char *count_values[] = { + "100", + "1000", + "5000", + "10000", + "20000", + "30000", + "40000", + "50000", + NULL + }; + til_setting_t *speed; + const char *speed_values[] = { + ".02", + ".04", + ".08", + ".16", + ".2", + ".4", + ".6", + ".8", + ".9", + "1", + NULL + }; + int r; + + r = til_settings_get_and_describe_setting(settings, + &(til_setting_spec_t){ + .name = "Size of flow field cube", + .key = "size", + .regex = "\\[0-9]+", /* FIXME */ + .preferred = FLOW_DEFAULT_SIZE, + .values = size_values, + .annotations = NULL + }, + &size, + res_setting, + res_desc); + if (r) + return r; + + r = til_settings_get_and_describe_setting(settings, + &(til_setting_spec_t){ + .name = "Count of flowing elements", + .key = "count", + .regex = "\\[0-9]+", /* FIXME */ + .preferred = FLOW_DEFAULT_COUNT, + .values = count_values, + .annotations = NULL + }, + &count, + res_setting, + res_desc); + if (r) + return r; + + r = til_settings_get_and_describe_setting(settings, + &(til_setting_spec_t){ + .name = "Speed of all flow through field", + .key = "speed", + .regex = "\\.[0-9]+", /* FIXME */ + .preferred = FLOW_DEFAULT_SPEED, + .values = speed_values, + .annotations = NULL + }, + &speed, + res_setting, + res_desc); + if (r) + return r; + + if (res_setup) { + flow_setup_t *setup; + + setup = til_setup_new(settings, sizeof(*setup), NULL, &flow_module); + if (!setup) + return -ENOMEM; + + if (sscanf(size->value, "%u", &setup->size) != 1) + return til_setup_free_with_failed_setting_ret_err(&setup->til_setup, size, res_setting, -EINVAL); + + if (sscanf(count->value, "%u", &setup->count) != 1) + return til_setup_free_with_failed_setting_ret_err(&setup->til_setup, count, res_setting, -EINVAL); + + if (sscanf(speed->value, "%f", &setup->speed) != 1) + return til_setup_free_with_failed_setting_ret_err(&setup->til_setup, speed, res_setting, -EINVAL); + + *res_setup = &setup->til_setup; + } + + return 0; +} diff --git a/src/modules/flow/v3f.h b/src/modules/flow/v3f.h new file mode 100644 index 0000000..f268cfc --- /dev/null +++ b/src/modules/flow/v3f.h @@ -0,0 +1,284 @@ +#ifndef _V3F_H +#define _V3F_H + +#include +#include + +typedef struct v3f_t { + float x, y, z; +} v3f_t; + +#define v3f_set(_v3f, _x, _y, _z) \ + (_v3f)->x = _x; \ + (_v3f)->y = _y; \ + (_v3f)->z = _z; + +#define v3f_init(_x, _y, _z) \ + { \ + .x = _x, \ + .y = _y, \ + .z = _z, \ + } + +/* return if a and b are equal */ +static inline int v3f_equal(const v3f_t *a, const v3f_t *b) +{ + return (a->x == b->x && a->y == b->y && a->z == b->z); +} + + +/* return the result of (a + b) */ +static inline v3f_t v3f_add(const v3f_t *a, const v3f_t *b) +{ + v3f_t res = v3f_init(a->x + b->x, a->y + b->y, a->z + b->z); + + return res; +} + + +/* return the result of (a - b) */ +static inline v3f_t v3f_sub(const v3f_t *a, const v3f_t *b) +{ + v3f_t res = v3f_init(a->x - b->x, a->y - b->y, a->z - b->z); + + return res; +} + + +/* return the result of (-v) */ +static inline v3f_t v3f_negate(const v3f_t *v) +{ + v3f_t res = v3f_init(-v->x, -v->y, -v->z); + + return res; +} + + +/* return the result of (a * b) */ +static inline v3f_t v3f_mult(const v3f_t *a, const v3f_t *b) +{ + v3f_t res = v3f_init(a->x * b->x, a->y * b->y, a->z * b->z); + + return res; +} + + +/* return the result of (v * scalar) */ +static inline v3f_t v3f_mult_scalar(const v3f_t *v, float scalar) +{ + v3f_t res = v3f_init( v->x * scalar, v->y * scalar, v->z * scalar); + + return res; +} + + +/* return the result of (uv / scalar) */ +static inline v3f_t v3f_div_scalar(const v3f_t *v, float scalar) +{ + v3f_t res = v3f_init(v->x / scalar, v->y / scalar, v->z / scalar); + + return res; +} + + +/* return the result of (a . b) */ +static inline float v3f_dot(const v3f_t *a, const v3f_t *b) +{ + return a->x * b->x + a->y * b->y + a->z * b->z; +} + + +/* return the length of the supplied vector */ +static inline float v3f_length(const v3f_t *v) +{ + return sqrtf(v3f_dot(v, v)); +} + + +/* return the normalized form of the supplied vector */ +static inline v3f_t v3f_normalize(const v3f_t *v) +{ + v3f_t nv; + float f; + + f = 1.0f / v3f_length(v); + + v3f_set(&nv, f * v->x, f * v->y, f * v->z); + + return nv; +} + + +/* return the distance squared between two arbitrary points */ +static inline float v3f_distance_sq(const v3f_t *a, const v3f_t *b) +{ + return powf(a->x - b->x, 2) + powf(a->y - b->y, 2) + powf(a->z - b->z, 2); +} + + +/* return the distance between two arbitrary points */ +/* (consider using v3f_distance_sq() instead if possible, sqrtf() is slow) */ +static inline float v3f_distance(const v3f_t *a, const v3f_t *b) +{ + return sqrtf(v3f_distance_sq(a, b)); +} + + +/* return the cross product of two unit vectors */ +static inline v3f_t v3f_cross(const v3f_t *a, const v3f_t *b) +{ + v3f_t product = v3f_init(a->y * b->z - a->z * b->y, a->z * b->x - a->x * b->z, a->x * b->y - a->y * b->x); + + return product; +} + + +/* return the linearly interpolated vector between the two vectors at point alpha (0-1.0) */ +static inline v3f_t v3f_lerp(const v3f_t *a, const v3f_t *b, float alpha) +{ + v3f_t lerp_a, lerp_b; + + lerp_a = v3f_mult_scalar(a, 1.0f - alpha); + lerp_b = v3f_mult_scalar(b, alpha); + + return v3f_add(&lerp_a, &lerp_b); +} + + +/* return the normalized linearly interpolated vector between the two vectors at point alpha (0-1.0) */ +static inline v3f_t v3f_nlerp(const v3f_t *a, const v3f_t *b, float alpha) +{ + v3f_t lerp; + + lerp = v3f_lerp(a, b, alpha); + + return v3f_normalize(&lerp); +} + + +/* return the bilinearly interpolated value */ +/* tx:0---------1 + * 1a---------b + * || | + * || | + * || | + * 0c---------d + * ^ + * t + * y + */ +static inline v3f_t v3f_bilerp(const v3f_t *a, const v3f_t *b, const v3f_t *c, const v3f_t *d, float tx, float ty) +{ + v3f_t x1, x2; + + x1 = v3f_lerp(a, b, tx); + x2 = v3f_lerp(c, d, tx); + + return v3f_lerp(&x2, &x1, ty); +} + + +/* return the trilinearly interpolated value */ +/* + * e---------f + * /| /| + * a---------b | + * | | | | + * | g-------|-h + * |/ |/ + * c---------d + */ +static inline v3f_t v3f_trilerp(const v3f_t *a, const v3f_t *b, const v3f_t *c, const v3f_t *d, const v3f_t *e, const v3f_t *f, const v3f_t *g, const v3f_t *h, const v3f_t *t) +{ + v3f_t abcd, efgh; + + abcd = v3f_bilerp(a, b, c, d, t->x, t->y); + efgh = v3f_bilerp(e, f, g, h, t->x, t->y); + + return v3f_lerp(&abcd, &efgh, t->z); +} + + +static inline v3f_t v3f_ceil(const v3f_t *v) +{ + v3f_t res = v3f_init(ceilf(v->x), ceilf(v->y), ceilf(v->z)); + + return res; +} + + +static inline v3f_t v3f_floor(const v3f_t *v) +{ + v3f_t res = v3f_init(floorf(v->x), floorf(v->y), floorf(v->z)); + + return res; +} + + +static inline v3f_t v3f_rand(unsigned *seed, float min, float max) +{ + v3f_t res = v3f_init( (min + ((float)rand_r(seed) * (1.0f/RAND_MAX)) * (max - min)), + (min + ((float)rand_r(seed) * (1.0f/RAND_MAX)) * (max - min)), + (min + ((float)rand_r(seed) * (1.0f/RAND_MAX)) * (max - min))); + + return res; +} + + +static inline v3f_t v3f_clamp(const v3f_t min, const v3f_t max, const v3f_t *v) +{ + v3f_t res; + + if (v->x < min.x) + res.x = min.x; + else if(v->x > max.x) + res.x = max.x; + else + res.x = v->x; + + if (v->y < min.y) + res.y = min.y; + else if(v->y > max.y) + res.y = max.y; + else + res.y = v->y; + + if (v->z < min.z) + res.z = min.z; + else if(v->z > max.z) + res.z = max.z; + else + res.z = v->z; + + return res; +} + + +static inline v3f_t v3f_clamp_scalar(float min, float max, const v3f_t *v) +{ + v3f_t res; + + if (v->x < min) + res.x = min; + else if(v->x > max) + res.x = max; + else + res.x = v->x; + + if (v->y < min) + res.y = min; + else if(v->y > max) + res.y = max; + else + res.y = v->y; + + if (v->z < min) + res.z = min; + else if(v->z > max) + res.z = max; + else + res.z = v->z; + + return res; +} +#endif -- cgit v1.2.3