I made this for practice, to try out the Jump-Flood Algorithm, but it turned into a little interactive click-through thing, so here it is. It might be a little hard to understand at first, but if you're interested in parallel processing, it's an extremely powerful tool.
Jump-Flood is useful for "parallel-fill" operations. For detailed information, this wonderful article by Ben Golus explains why and how you might want to use the Jump-Flood Algorithm for a realtime "perfect thick outline" post-processing shader, by live-generating a 2D distance field from a rasterized silhouette.
In this simpler example, the input is a 1-dimensional sequence of increasing numbers, with an unpredictable number of trailing zeroes after each unique value. The goal is to "fill-forward" each unique value, so it gets copied over all of its immediately-trailing zeroes. This is easy to do in a serial process, "CPU-style" (just one big for-loop through the whole list, remembering the most recent nonzero value and overwriting any zeroes with it) - but it's much more complicated if you want to solve this same problem with a parallel routine - for example, in a GPU program, for a big list! The naive parallel approaches are very wasteful, and they scale very poorly by comparison.
Note that this demo shows the process running one "slot" at a time in each row (for clarity), but each pass of this algorithm (one row of digits) can be performed fully parallel.
The really compelling thing about this method is that when run in a parallel way, it deals with large amounts of data incredibly well: the cost scales as O(log2(N)), where N is the size of the largest continuous sequence of zeroes in the input list (the maximum "fill distance"). A beautiful algorithm!
[Please log in to post a comment]
