modules/voronoi: spot-fix a crash Phil reported

The repro is:
--seed=0x64f6820b '--module=compose,layers=blank\,pixbounce\\\,pixmap_size\\\=0.8\\\,pixmap\\\=err\,pixbounce\\\,pixmap_size\\\=0.4\\\,pixmap\\\=ignignokt,texture=voronoi\,cells\=512\,randomize\=on' '--video=mem,size=3840x2160'

The major culprit seems to be the combination of high resolution,
and small number of voronoi cells (cells=512), with randomize=on
which exercises jumpfill every frame.

The way jumpfill is implemented currently is racy by design to
allow threading, and mostly works fine despite not really being
how the algorithm is intended to work.

The assumption has been, something like:
"the seeds are already placed before the threaded phase, so the
threaded jumpfill should at least find stable seed cells in the
face of racing against other tiles being jumpfilled
simultaneously"

But it appears that assumption isn't always true, in that we
won't necessarily find one of the seed cells at the start of the
jumpfill when there aren't that many cells (512) compared to the
area of the voronoi (3840x2160).

By noticing when we've finished a tile's jumpfill with remaining
unassigned cells, we can just repeat the jumpfill, with time
passed, and the other tiles will have made progress on their work
propagating more knowledge of where cells are... so the
subsequent pass will probably leave nothing unassigned.

This approach sucks, but stops the crashing.

It'd also be possible to just change the way cells are looked up
so there's no potential for a NULL pointer dereference, just have
some uninitialized cell color which gets shown erroneously in the
output.  That avoids the computational cost of repeating the
tile's jumpfill, and likely nobody would notice the likely single
pixel of error for a single frame.

I'm just doing this quick and dirty fix to prevent the crashing
for now, and would like to just revisit voronoi more thoroughly
with an eye towards decoupling the voronoi cost from the
resolution.  It's a cheap hack the way there's a distance entry
per pixel, done just to simplify the implementation when I
slapped it together on a Zephyr train ride.

1 files changed, 20 insertions, 4 deletions

diff --git a/src/modules/voronoi/voronoi.c b/src/modules/voronoi/voronoi.c
index 0c06c1d..5b38705 100644
--- a/src/modules/voronoi/voronoi.c
+++ b/src/modules/voronoi/voronoi.c
@@ -126,9 +126,10 @@ static inline size_t voronoi_cell_origin_to_distance_idx(const voronoi_context_t
 }
 
 
-static void voronoi_jumpfill_pass(voronoi_context_t *ctxt, v2f_t *db, v2f_t *ds, size_t step, const til_fb_fragment_t *fragment)
+static size_t voronoi_jumpfill_pass(voronoi_context_t *ctxt, const v2f_t *db, const v2f_t *ds, size_t step, const til_fb_fragment_t *fragment)
 {
-	v2f_t			dp = {};
+	size_t	n_unassigned = 0;
+	v2f_t	dp = {};
 
 	dp.y = db->y;
 	for (int y = 0; y < fragment->height; y++, dp.y += ds->y) {
@@ -214,8 +215,13 @@ static void voronoi_jumpfill_pass(voronoi_context_t *ctxt, v2f_t *db, v2f_t *ds,
 
 				VORONOI_JUMPFILL;
 			}
+
+			if (!d->cell)
+				n_unassigned++;
 		}
 	}
+
+	return n_unassigned;
 }
 
 
@@ -256,6 +262,7 @@ static void voronoi_calculate_distances_render_pass(voronoi_context_t *ctxt, con
 			.x = fragment->x * ds.x - 1.f,
 			.y = fragment->y * ds.y - 1.f,
 		};
+	size_t	n_unassigned;
 
 	/* An attempt at implementing https://en.wikipedia.org/wiki/Jump_flooding_algorithm */
 
@@ -275,8 +282,17 @@ static void voronoi_calculate_distances_render_pass(voronoi_context_t *ctxt, con
 	 * changing the cell pointers while we try dereference them.  But all we really care about is finding
 	 * seeds reliably, and those should already be populated in the prepare phase.
 	 */
-	for (size_t step = MAX(fragment->frame_width, fragment->frame_height) / 2; step > 0; step >>= 1)
-		voronoi_jumpfill_pass(ctxt, &db, &ds, step, fragment);
+	do {
+		for (size_t step = MAX(fragment->frame_width, fragment->frame_height) >> 1; step > 0; step >>= 1)
+			n_unassigned = voronoi_jumpfill_pass(ctxt, &db, &ds, step, fragment);
+	} while (n_unassigned); /* FIXME: there seems to be bug/race potential with sparse voronois at high res,
+				 * especially w/randomize=on where jumpfill constantly recurs, it could leave a
+				 * spurious NULL cell resulting in a segfault.  The simplest thing to do here is
+				 * just repeat the jumpfill for the fragment.  It's inefficient, but rare, and doing
+				 * voronoi as-is that way on a high resolution is brutally slow anyways, this all needs
+				 * revisiting to make things scale better.  So for now this prevents crashing, which is
+				 * all that matters.
+				 */
 }