4 ms·

I loved the article that this links to about 'Jump Flood Algorithm'!: https://bgolus.medium.com/the-quest-for-very-wide-outlines-ba82ed442cd9 https://bgolus.me

I loved the article that this links to about 'Jump Flood Algorithm'!: https://bgolus.medium.com/the-quest-for-very-wide-outlines-ba82ed442cd9 https://bgolus.medium.com/the-quest-for-very-wide-outlines-b... So fascinating! Thanks for indirectly leading me to this! I love thinking about all the various approaches available at the pixel/texel/etc level! It's also another case where it's a very clever way of generating a type of SDF (Signed Distance Field) that is doing a lot of the heavy-lifting. Such a killer result here as well! Any-width-outline-you-like in linear time?!! Amazing when compared to the cost of the brute-force ones at huge widths! I wholeheartedly endorse SDFs, whether they are 'vector' ones, function-based, like Inigo Quilez's amazing work, Or 'raster' ones like in the article, texel-or-voxel-based. Houdini supports raster-SDFs very well I think, has a solid, mature set of SDF-tools worth checking out (there's a free version if you don't have a lic)! And of course there's all the many other places SDFs are used!! So useful! Definitely worth raising-awareness of I reckon!

johndough 2y ago
Note that the 'Jump Flood Algorithm' is O(N log N) where N is the number of pixels. There is a better O(N) algorithm which can be parallelized over the number of rows/columns of an image: https://news.ycombinator.com/item?id=36809404 https://news.ycombinator.com/item?id=36809404 Unfortunately, it requires random access writes (compute shaders) if you want to run it on the GPU. But if CPU is fine, here are a few implementations: JavaScript: https://parmanoir.com/distance/ https://parmanoir.com/distance/ C: https://github.com/983/df https://github.com/983/df C++: https://github.com/opencv/opencv/blob/4.x/modules/imgproc/src/distransform.cpp https://github.com/opencv/opencv/blob/4.x/modules/imgproc/sr... Python: https://github.com/pymatting/pymatting/blob/afd2dec073cb08b8119300feec18c179a9d436f3/pymatting/util/distance.py#L61 https://github.com/pymatting/pymatting/blob/afd2dec073cb08b8...
- pshc 2y ago
  Dang, I implemented SDFs in 2023 around that time with jump flooding. Wish I had seen this version. Thanks for pointing it out!
coinfused 2y ago
In my own projects I use JFA/SDF-based outlines the most because of their quality as well as the possibility to render distance-based effects like pulsating outlines. This (https://x.com/alexanderameye/status/1663523972485357569 https://x.com/alexanderameye/status/1663523972485357569) 3D line painting tool also uses SDFs that I then write to a tiny texture and sample at runtime. SDFs are very powerful!
jasonjmcghee 2y ago
SDFs work great as the structure for circle marching which is one approach to accelerating global illumination to the point of making it real-time, with limitations. The same approach cab be extended to use radiance cascades making it even faster! Pretty fun.

johndough 2y ago

Note that the 'Jump Flood Algorithm' is O(N log N) where N is the number of pixels. There is a better O(N) algorithm which can be parallelized over the number of rows/columns of an image: https://news.ycombinator.com/item?id=36809404 https://news.ycombinator.com/item?id=36809404 Unfortunately, it requires random access writes (compute shaders) if you want to run it on the GPU. But if CPU is fine, here are a few implementations: JavaScript: https://parmanoir.com/distance/ https://parmanoir.com/distance/ C: https://github.com/983/df https://github.com/983/df C++: https://github.com/opencv/opencv/blob/4.x/modules/imgproc/src/distransform.cpp https://github.com/opencv/opencv/blob/4.x/modules/imgproc/sr... Python: https://github.com/pymatting/pymatting/blob/afd2dec073cb08b8119300feec18c179a9d436f3/pymatting/util/distance.py#L61 https://github.com/pymatting/pymatting/blob/afd2dec073cb08b8...

pshc 2y ago
Dang, I implemented SDFs in 2023 around that time with jump flooding. Wish I had seen this version. Thanks for pointing it out!

coinfused 2y ago

In my own projects I use JFA/SDF-based outlines the most because of their quality as well as the possibility to render distance-based effects like pulsating outlines. This (https://x.com/alexanderameye/status/1663523972485357569 https://x.com/alexanderameye/status/1663523972485357569) 3D line painting tool also uses SDFs that I then write to a tiny texture and sample at runtime. SDFs are very powerful!

jasonjmcghee 2y ago

SDFs work great as the structure for circle marching which is one approach to accelerating global illumination to the point of making it real-time, with limitations. The same approach cab be extended to use radiance cascades making it even faster! Pretty fun.