Skip to content(if available)orjump to list(if available)

SDFs and the Fast sweeping algorithm in Jax

SDFs and the Fast sweeping algorithm in Jax

7 comments

·May 8, 2025
Visit

singron

You might also be interested in JFA https://en.m.wikipedia.org/wiki/Jump_flooding_algorithm

cyber_kinetist

As 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-d... for a better explanation)

beansbeansbeans

Thats 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

The 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.

andybak

First skim and I'm confused about the meaning of "interface" in this context. Anyone?

ljouhet

https://en.wikipedia.org/wiki/Interface_(matter)

Skepfyr

I think this is something like a boundary between two fluids. For example, if you had oil and water in a glass you could describe the 2d surface where they meet as the interface.