Position of object on image without AI/ML — Jump flooding algorithm

Danil
3 min readNov 23, 2024

--

Image-mask to distance field and display normals of SDF

Idea — select object on image as image mask and generate SDF to get position of this object. Also use Mipmap layers to optimize logic.

Implementation — links provided in description.

This is not tutorial.

Content:

  1. Single frame JFA base implementation — by Inigo Quilez.
  2. Optimized realtime JFA — by Flyguy on Shadertoy.
  3. SDF to single position-coordinate.
  4. Overview of possible Mipmap optimizations.
  5. Object detection using only Mipmap layer by FabriceNeyret2.

Single frame JFA base implementation:

Jump flooding algorithm on Wikipedia.

Great implementation by Inigo Quilez — Signed Jump Flooding.

Signed Jump Flooding, to create a SIGNED distance field of a shape of which we only know it’s inside and outside regions.

This implementtion use 10 to 16 passes to generate SDF to mask.
And for-loop use alot-of-texture-steps((passes x2)² per pass) to build SDF.
But result is very high quality.

it is possible to do in real time — that will cost 10–16 “compute-layers” — fine for most of modern GPUs performance but can be optimized.

Optimized realtime JFA:

Van Damme — Distanceby Flyguy on Shadertoy.
It better for real time use — because there only:

    for(int i = -1; i <= 1; i++)
{
for(int j = -1; j <= 1; j++)

And only 6-passes — used single cubemap buffer and every cube-face look on other-previous cube fase to build JFA.
(this why it delayed by 6 frames from video — can be improved by procesing 6 buffers one after other)

Because this is so “cheap” by performance — it will work literally on anything — performance can be calculated linearly.

((Multiply image resolution x*y) x3x3) x6
For 256x256 image it will be 3538944 iterations — multiply by 100(~number of operations per iteration) = around 400MHz single core processor can be enough to preceess it in real time.

Screenshot on top of this article is from this implementation — screenshot displaying SDF-normal arows.

Example of possible Mipmap use case in JFA.

SDF to single position-coordinate:

Simple — get multiple points-normals and calculate center.
(summ of vectors)

To get better position of center — more points needed.

But summ of multiple points — is Mipmap.

You can just apply mipmap layer to SDF and get better position with less points.

Overview of possible Mipmap optimizations:

Not a single JFA algorithm above use Mipmaps.

When core of JFA — is loop in some range of pixels to “blur the edge”.

I think Mipmaps can be used in JFA to find object bound-box, to get center-position, and even to implement full JFA thru mipmaps.

One of FabriceNeyret2 shaders with Mipmap trick https://www.shadertoy.com/view/XlcyR2

Object detection using only Mipmap layer:

Notice:

FabriceNeyret2 blog — GPmipmap Mipmap Advanced tricks.

Cotext — dynamic centering Britney FabriceNeyret2 Shadertoy shader.
And — tracking van damme(almost free)2.

Look at these implementations — used only Mipmap layer to get position of mask.

And as “algorithm” — is single line textureLod(iChannel1, vec2(.5), 99.)

Just read last Mipmap layer — last Mipmap layers is "average summ of all pixels".
Very interesting and impressive discovery by FabriceNeyret2!

This is so cheap by compute-performance — it require no compute, just memory reading and Mipmaps calculation can be done on hardware level — literally just scale-connect memory linearly — no compute.

--

--

Danil
Danil

No responses yet