9
$\begingroup$

JFA (the algorithm described here: http://www.comp.nus.edu.sg/~tants/jfa/i3d06.pdf) can be used to get an approximation of a Voronoi diagram, or a distance transform. It does so in logarithmic time based on the size of the resulting image, not on the number of seeds.

What do you do if your image is not the same size on each axis though?

If they were similar sizes, I'm sure you could just let the shorter axis have extra JFA steps of size 1, while the larger axis finished it work (like having a 512 x 256 sized image). For vastly different sized axis dimensions this could be a lot more inefficient though - say that you had a volume texture that was 512 x 512 x 4.

Is it possible to run JFA on each axis separately and still get decent results?

Or at that point is a different algorithm more appropriate to use? If so, what algorithm might that be?

In my situation ideally I'm looking to support both single point seeds, as well as arbitrary shaped seeds. Possibly even weighted seeds, where the distance to a seed is adjusted by a multiplier and/or an adder to give it more or less influence.

$\endgroup$
7
$\begingroup$

Quick answers to your individual questions

What do you do if your image is not the same size on each axis though?

The paper uses square images with side lengths that are a power of 2. This is for ease of explanation, but is not necessary for the algorithm to work. See section 3.1:

Without loss of generality, we can assume n is a power of 2.

That is, this assumption is not required in order for the algorithm to work.

Is it possible to run JFA on each axis separately and still get decent results?

Running on each axis separately is likely to give more incorrect pixel results, and take longer to run in most cases. In extreme cases where one of the image side lengths is less than 8 (the number of jump directions), it may be faster as the algorithm treats those 8 directions sequentially, but for any wider image, separating the axes loses the advantage of treating them in parallel.

In my situation ideally I'm looking to support both single point seeds, as well as arbitrary shaped seeds

The paper mentions arbitrary shaped seeds in section 6 under the subheading "Generalized Voronoi Diagram":

...our algorithms treat such generalized seeds as collections of point seeds and thus expect to inherit the good performance obtained for point seeds.

So provided it suits your purpose to model arbitrary shapes as collections of pixels, you don't need to make any adjustment to the algorithm. Simply feed in a texture that labels all pixels in an arbitrary shaped seed with the same seed number, but different locations.

Possibly even weighted seeds, where the distance to a seed is adjusted by a multiplier and/or an adder to give it more or less influence

For "weighting on seeds such as multiplicative and additive", the paper only mentions the possibility in passing in section 8, as potential future work. However, this should be straightforward to implement provided your desired weighting can be included in the seed data that is passed from pixel to pixel.

The current algorithm passes <s, position(s)> to specify a seed and its position, and only one seed is stored per pixel at any one time. Extending this to store <s, position(s), weight(s)> provides all the information required to weight the distance function and calculate whether the new seed being passed to a pixel is closer to it than the one it is currently storing.

You could even include two weights, one multiplicative and one additive, and just set the multiplicative one to 1 and the additive one to 0 when not required. Then your algorithm would include the possibility of being used for multiplicatively weighted seeds, additively weighted seeds, or even a combination of both at once or some of each. This would just need

<s, position(s), multiplicative(s), additive(s)>

and the current algorithm would be equivalent to this new algorithm using

<s, position(s), 1, 0>


Detailed explanation of why

As in the paper, all uses of $\log()$ refer to the base 2 logarithm.

The algorithm does not need to be adapted for different side lengths

If the side lengths are not equal, and are not powers of 2, there is no need to adapt the algorithm. It already deals with pixels on the edge of the image for which some of the jump directions lead outside the image. Since the algorithm already omits the seed information for directions that lead outside the image, a width or height that is not a power of 2 will not be a problem. For an image of width W and height H, the maximum jump size required will be

$$\large2^{\lceil\log(\max(W,H))\rceil-1}$$

For the case of equal width and height N, this reduces to

$$\large2^{\lceil\log(N)\rceil-1}$$

In the case of a side length N that is a power of 2, this reduces to

$$\large2^{\log(N)-1}=N/2$$

as used in the paper.

In more intuitive terms, round the maximum side length up to the next power of 2, and then halve that to get the maximum jump size.

This is always enough to cover every pixel in the image from every other pixel in the image, as the offset to any pixel will be in the range 0 to N-1 if the longest side length is N. Combinations of the powers of 2 from 0 to N/2 will cover every integer up to N-1 if N is a power of 2, and if N is not a power of 2 the range covered can only be larger than required, due to taking the ceiling of the logarithm (rounding up to the next power of 2).

Images with sides not a power of 2 will not be drastically less efficient

The number of jumps depends on the longest side length, say L. If L is a power of 2 then the number of jumps is $\log(L)$. If L is not a power of 2 then the number of jumps is $\lceil\log(L)\rceil$. For a reasonably large image this will not be a large difference.

For example, a 1024 by 1024 image will require 10 jump iterations. A 512 by 512 image will require 9 jump iterations. Anything between the two sizes will also require 10 iterations. Even in the worst case of an image only just over a power of 2, like a 513 by 513 image, it will only require 1 additional iteration, which at this scale is approximately 11% more (10 instead of 9).

Non-square images are less efficient per area

Since the number of iterations required is determined by the longest side length, the time taken for a 1024 by 1024 image will be the same as for a 1024 by 16 image. A square image allows a larger area to be covered in the same number of iterations.

Separating axes is likely to reduce quality

Section 5 of the paper describes possible errors. Every pixel is reachable by a path from every other pixel, but some paths do not bring the correct nearest seed, due to that seed not being the nearest to a previous pixel in the path. A pixel that does not allow a seed to propagate past it is said to have "killed" that seed. If the nearest seed to a pixel is killed on all paths to that pixel, then the pixel will record some other seed and there will be an incorrect colour in the final image.

Only one path needs to exist that does not kill the seed in order for the final result to be correct. Incorrect colours only occur when all paths from the correct seed to a given pixel are blocked.

If a path involves alternating horizontal and vertical jumps, separating axes will make this path impossible (all horizontal jumps will be taken before all vertical jumps, making alternating impossible). Diagonal jumps will not be possible at all. So any path that alternates or contains diagonal jumps will be excluded. Every pixel will still have a path to every other pixel, but since there are now fewer paths there is more chance of a given pixel being blocked from receiving the correct seed, so the final result will be more error prone.

Separating axes is likely to make the algorithm take longer

The efficiency would probably be reduced by separating axes, as the flooding would no longer be done in parallel, but would instead be repeated for each axis. For 2D this would likely take approximately twice as long, and for 3D approximately 3 times as long.

This may be somewhat mitigated by the lack of diagonal jumps, but I would still expect an overall reduction in efficiency.

$\endgroup$
  • 1
    $\begingroup$ I've started experimenting with some of this already. I've found that sampling in a + sign (5 reads) instead of the full 9 showed no differences in my testing, but im sure with more complex situations, there would be differences. Doing a full x jfa and then a full y jfa does make lots of errors. I'll be interested to hear more details/info if you have it, but accepting your answer :P $\endgroup$ – Alan Wolfe Feb 29 '16 at 20:43
  • 1
    $\begingroup$ Forgot, here's link to one of my experiments: shadertoy.com/view/Mdy3D3 $\endgroup$ – Alan Wolfe Feb 29 '16 at 20:44
  • $\begingroup$ Interesting that it works apparently just as well with only 5 reads - especially since they can't be parallelised. Since the paper lists the cases that lead to error maybe you could deliberately set these up and see if 5 jump directions is still as good. $\endgroup$ – trichoplax Feb 29 '16 at 20:49
  • $\begingroup$ Sounds like you are ready to post your own answer... $\endgroup$ – trichoplax Feb 29 '16 at 20:50
  • $\begingroup$ my info supplements yours :P $\endgroup$ – Alan Wolfe Feb 29 '16 at 21:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.