From 31c03632c303c6087768f37a8fe02bc8571f6560 Mon Sep 17 00:00:00 2001 From: Vito Caputo Date: Sat, 27 May 2023 19:10:26 -0700 Subject: modules/voronoi: split voronoi_calculate_distances() Preparatory commit for doing the voronoi distance calculations in parallel when possible, as part of render_fragment() instead of all in prepare_frame(). Not all of the distance calculation work can easily be threaded, but it should be possible to compute the post-seed distances concurrently within the spatial bounds of the tiled fragment. This commit doesn't actually change anything functionally, as it's just splitting the old voronoi_calculate_distances() into two and calling them both in succession still from voronoi_prepare_frame(). Subsequent commits will work towards making the render_pass() fragment-aware then ultimately moved to voronoi_render_fragment() --- src/modules/voronoi/voronoi.c | 66 ++++++++++++++++++++----------------------- 1 file changed, 30 insertions(+), 36 deletions(-) (limited to 'src/modules/voronoi') diff --git a/src/modules/voronoi/voronoi.c b/src/modules/voronoi/voronoi.c index 0ae23e7..54dc7ac 100644 --- a/src/modules/voronoi/voronoi.c +++ b/src/modules/voronoi/voronoi.c @@ -39,6 +39,7 @@ typedef struct voronoi_distances_t { int width, height; size_t size; voronoi_distance_t *buf; + unsigned recalc_needed:1; } voronoi_distances_t; typedef struct voronoi_context_t { @@ -69,6 +70,8 @@ static void voronoi_randomize(voronoi_context_t *ctxt) p->color |= ((uint32_t)(rand_r(&ctxt->seed) % 256)) << 8; p->color |= ((uint32_t)(rand_r(&ctxt->seed) % 256)); } + + ctxt->distances.recalc_needed = 1; } @@ -198,39 +201,18 @@ static void voronoi_jumpfill_pass(voronoi_context_t *ctxt, v2f_t *ds, size_t ste } -static void voronoi_calculate_distances(voronoi_context_t *ctxt) +/* distance calculating is split into two halves: + * 1. a serialized global/cell-oriented part, where the distances are wholesale + * reset then the "seeds" placed according to the cells. + * 2. a concurrent distance-oriented part, where per-pixel distances are computed + * within the bounds of the supplied fragment (tiled) + * + * These occur in prepare_pass/render_pass, respectively. + */ +static void voronoi_calculate_distances_prepare_pass(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]; @@ -243,11 +225,21 @@ static void voronoi_calculate_distances(voronoi_context_t *ctxt) d->cell = c; d->distance_sq = 0.f; } +} + + +static void voronoi_calculate_distances_render_pass(voronoi_context_t *ctxt, const til_fb_fragment_t *fragment) +{ + v2f_t ds = (v2f_t){ + .x = 2.f / ctxt->distances.width, + .y = 2.f / ctxt->distances.height, + }; + + /* An attempt at implementing https://en.wikipedia.org/wiki/Jump_flooding_algorithm */ /* now for every distance sample neighbors */ for (size_t step = MAX(ctxt->distances.width, ctxt->distances.height) / 2; step > 0; step >>= 1) voronoi_jumpfill_pass(ctxt, &ds, step); -#endif } @@ -281,16 +273,18 @@ static void voronoi_prepare_frame(til_module_context_t *context, til_stream_t *s 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); + ctxt->distances.recalc_needed = 1; } /* TODO: explore moving voronoi_calculate_distances() into render_fragment (threaded) */ - if (ctxt->setup->randomize) { + if (ctxt->setup->randomize) voronoi_randomize(ctxt); - voronoi_calculate_distances(ctxt); + + if (ctxt->distances.recalc_needed) { + voronoi_calculate_distances_prepare_pass(ctxt); + voronoi_calculate_distances_render_pass(ctxt, fragment); + ctxt->distances.recalc_needed = 0; } /* if the fragment comes in already cleared/initialized, use it for the colors, producing a mosaic */ -- cgit v1.2.1