3 ms·
You might also be interested in JFA https://en.m.wikipedia.org/wiki/Jump_flooding_algorithm https://en.m.wikipedia.org/wiki/Jump_flooding_algorithm
by singron 1y ago
You might also be interested in JFA https://en.m.wikipedia.org/wiki/Jump_flooding_algorithm https://en.m.wikipedia.org/wiki/Jump_flooding_algorithm
- cyber_kinetist 1y agoAs a bonus: the vanilla JFA can only calculate unsigned distances, but you can extend this to signed distance computation using a simple trick: by inverting your JFA result and setting it as the seed for running a second DFA. (See https://blog.demofox.org/2016/03/02/actually-making-signed-distance-field-textures-with-jfa/ https://blog.demofox.org/2016/03/02/actually-making-signed-d... for a better explanation)
- beansbeansbeans 1y agoThats a cool algorithm!! I couldnt find resources on how it might be used to compute distance functions (though it seems like it can). It seems to be for approximating voronoi diagrams.
- singron 1y agoThe two problems are highly related, which is why it can do both. At the end of the algorithm, you have a per-pixel assignment of the (approximately) closest seed pixel. If you want a voronoi diagram, then you color each pixel according to the identify of its seed pixel. If you want a distance function, then you color it with the distance to that pixel.