summaryrefslogtreecommitdiff
path: root/src/modules
diff options
context:
space:
mode:
authorVito Caputo <vcaputo@pengaru.com>2023-05-27 19:10:26 -0700
committerVito Caputo <vcaputo@pengaru.com>2023-05-27 23:09:05 -0700
commit31c03632c303c6087768f37a8fe02bc8571f6560 (patch)
treef98dd4cf80fea40f0cda9ec1c95bf2e06f209d5a /src/modules
parentd86a346790c5405c29ba80cf200bba4f99bd775a (diff)
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()
Diffstat (limited to 'src/modules')
-rw-r--r--src/modules/voronoi/voronoi.c66
1 files changed, 30 insertions, 36 deletions
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 */
© All Rights Reserved