5 ms·

Non-random uniform disk sampling

56 points by fouronnes3 2y ago

PaulHoule 2y ago
See [1] [2] and there is a great treatment of the topic in this book [3]. I don't know exactly what's he doing, but if I was doing some kind of monte carlo integration (like the family of energy surfaces in 6-dimensional space that I plotted the volume of as a function of energy for my PhD thesis) I'd be really concerned about the "uniform" part. [1] https://en.wikipedia.org/wiki/Low-discrepancy_sequence https://en.wikipedia.org/wiki/Low-discrepancy_sequence [2] https://extremelearning.com.au/unreasonable-effectiveness-of-quasirandom-sequences/ https://extremelearning.com.au/unreasonable-effectiveness-of... [3] https://numerical.recipes/ https://numerical.recipes/
- fouronnes3 2y ago
  Thanks for the links. Yeah, I'm not too sure that "uniform" is the right term here. I'm happy to be corrected on what the best term is for that specific set of requirements. It's surprising how hard a time I've had googling this problem. Surely I'm far from the first to wonder about it. I think a mix of AI enshittification, and the ambiguous meanings of "sampling" and "uniform" made it hard to find good material on it.
  - PaulHoule 2y ago
    Sampling points on a disc is a special problem that turns up a lot in practice. One obvious thing to do is just sample points on the square and throw out the ones that aren't in the disc but numericists don't like the throwing away bit because of performance. That Numerical Recipes book [1] has a section on it (has one on disc sampling and those sexy quasirandom numbers), the #1 answer on this StackOverflow page describes an algorithm that I remember from it. https://stats.stackexchange.com/questions/481543/generating-random-points-uniformly-on-a-disk https://stats.stackexchange.com/questions/481543/generating-... [1] I took a class on numerics taught by one of the authors; great book but it's a shame about the software license
    - mturmon 2y ago
      > ...numericists don't like the throwing away bit... Although in 2 dimensions (setting of OP), this isn't that bad (you waste a proportion of (1-pi/4), or 21%, of your samples) -- perhaps 21% might be worth worrying about for some applications. Of course, it gets much worse in higher dimensions, because the unit ball is much smaller than the unit cube there.
      - mattkrause 2y ago
        This obviously depends on a million other factors too (implementation, language, architecture, etc) but I've benchmarked this a few times and, at least for naive implementations in 2D/3D, rejection sampling was often faster.
    - a_e_k 2y ago
      In graphics, we also often try to avoid any kind of rejection sampling because it wrecks importance sampling.
      - mturmon 2y ago
        Hmm, interesting. Is this still the case if the rejection factor is known explicitly (as it would be here)?
  - cozzyd 2y ago
    Maybe you mean something like regular? I wouldn't call this sampling uniform.
- Sharlin 2y ago
  One use case that immediately comes to mind as a hobbyist graphics coder is generating rays to simulate things like depth of field or soft shadows.
david-gpu 2y ago
This subject has been studied in depth before, hasn't it? E.g. Shirley's mapping, which can be combined with a low-discrepancy sequence such as Hammersley. Here is an introduction for those curious: https://towardsdatascience.com/unit-disk-uniform-sampling-91880f3740fa https://towardsdatascience.com/unit-disk-uniform-sampling-91...
- a_e_k 2y ago
  I was going to mention the Shirley and Chiu mapping. A copy of the original paper can be found here and is nice and easy to read, with pseudocode: https://web.archive.org/web/20190223095317id_/http://pdfs.semanticscholar.org/4322/6a3916a85025acbb3a58c17f6dc0756b35ac.pdf https://web.archive.org/web/20190223095317id_/http://pdfs.se... Alternatively for the non-random and arbitrary N case here, an approach based on Phyllotaxis that samples a Fermat spiral every ~137.508 degrees (i.e., the golden angle, or the golden ratio fraction of a circle) also works pretty well: https://en.wikipedia.org/wiki/Fermat%27s_spiral#The_golden_ratio_and_the_golden_angle https://en.wikipedia.org/wiki/Fermat%27s_spiral#The_golden_r.... It works nicely for any N, even if the N isn't square or close to square (just choose the scaling appropriately, e.g., c = 1/sqrt(N)).
sega_sai 2y ago
A bit of a strange ad-hoc solution. First as other pointed out, one can generate the Sobol sequence or similar, but even with a random sample one can generate the random numbers deterministically. I.e Sample r^2 ~ Uniform(0,r0^2) and angle from U(0,2*pi) and use the fixed seed...
- deleted 2y ago
  [deleted]
- throwaway127482 2y ago
  Wouldn't a fixed seed mean you're repeating values a bunch, which would be inefficient? And how would you know when to stop generating values?
  - sega_sai 2y ago
    You would fix the seed once in the beginning before sampling. Also you would need to sample exactly N-times as there no rejection required. as the points will all be within the circle by construction and will have uniform distribution
    - throwaway127482 2y ago
      The article was specifically asking for concentric rings with equally spaced points - how would you fix the seed such that this property is held?
      - sega_sai 2y ago
        The problem was stated in the beginning as 'Consider the problem of generating N points on a disk of diameter D. The function must be deterministic and the points somewhat uniformly spread around on the disk. Importantly, I want to generate exactly N points, for any integer value of N.' Then the author decided to do it through concentric rings.
- mturmon 2y ago
zokier 2y ago
Having one point at the center does not feel intuitive. For example the N=19 feels like it would be more uniform as same as N=20 but without center point. Similarly N=3 could be just the points on the outer circle, similar to what N=4 is now.
- Sharlin 2y ago
  N=19 (and likely N=18 etc) could also be more uniform if it already jumped to M=2, so that it would be like N=20 except with five points on the inner ring. Or maybe with six on the inner and twelve on the outer. Would probably be fairly easy to turn this into an optimization problem if one wanted a really uniform distribution (eg. distribute points on rings such that some sum of squared distances is minimized).
- Jaxan 2y ago
  I agree that N=3 (and also N=2 for that matter) could be distributed better. EDIT: but for large N these things probably don’t matter that much. And I guess that’s the application in the end.
- mturmon 2y ago
  It turns out there are differing interpretations of what to do about the edges. For an "interior" packing (there is a technical word for this that I don't recall rn), following the link by @mbauman below, the n=3 case is: http://hydra.nat.uni-magdeburg.de/packing/cci/d1.html http://hydra.nat.uni-magdeburg.de/packing/cci/d1.html and the other cases are nearby.
  - zokier 2y ago
    circle packing feels slightly different problem, especially as it doesn't tend to have any obvious algorithmic solutions available; circle packing produces irregular packings which I'm not sure I'd call super uniform btw what are the colors indicating on that page? its missing a legend and its not immediately obvious to me.
    - mturmon 2y ago
plagiarist 2y ago
Isn't this a variation of a sphere-packing problem? We know an optimally dense packing for 2D spheres. Then vary the radius of what is being packed until N of them fit in the disk's area.
- mbauman 2y ago
  > We know an optimally dense packing for 2D spheres We do? I think this is the latest state of the research here — only 14 Ns are proven optimal and it's certainly nowhere close to a general algorithm: http://hydra.nat.uni-magdeburg.de/packing/cci/ http://hydra.nat.uni-magdeburg.de/packing/cci/ There's something to be said for a dozen lines of numpy that gets "close enough". That said, I do think there should be something better.
  - plagiarist 2y ago
    If they're 2D and packed on a plane, though, I think we do. That's reasonable if we're talking about "close enough." I wouldn't argue with the brevity of the numpy, though. Choosing how to place the disk over a plane of circles in an optimal way could be complicated.
- TacticalCoder 2y ago
  [dead]
0xml 2y ago
Another interesting method is Fibonacci Lattice. https://observablehq.com/@meetamit/fibonacci-lattices https://observablehq.com/@meetamit/fibonacci-lattices

56 points by fouronnes3 2y ago

See [1] [2] and there is a great treatment of the topic in this book [3]. I don't know exactly what's he doing, but if I was doing some kind of monte carlo integration (like the family of energy surfaces in 6-dimensional space that I plotted the volume of as a function of energy for my PhD thesis) I'd be really concerned about the "uniform" part. [1] https://en.wikipedia.org/wiki/Low-discrepancy_sequence https://en.wikipedia.org/wiki/Low-discrepancy_sequence [2] https://extremelearning.com.au/unreasonable-effectiveness-of-quasirandom-sequences/ https://extremelearning.com.au/unreasonable-effectiveness-of... [3] https://numerical.recipes/ https://numerical.recipes/

fouronnes3 2y ago
Thanks for the links. Yeah, I'm not too sure that "uniform" is the right term here. I'm happy to be corrected on what the best term is for that specific set of requirements. It's surprising how hard a time I've had googling this problem. Surely I'm far from the first to wonder about it. I think a mix of AI enshittification, and the ambiguous meanings of "sampling" and "uniform" made it hard to find good material on it.
- PaulHoule 2y ago
  Sampling points on a disc is a special problem that turns up a lot in practice. One obvious thing to do is just sample points on the square and throw out the ones that aren't in the disc but numericists don't like the throwing away bit because of performance. That Numerical Recipes book [1] has a section on it (has one on disc sampling and those sexy quasirandom numbers), the #1 answer on this StackOverflow page describes an algorithm that I remember from it. https://stats.stackexchange.com/questions/481543/generating-random-points-uniformly-on-a-disk https://stats.stackexchange.com/questions/481543/generating-... [1] I took a class on numerics taught by one of the authors; great book but it's a shame about the software license
  - mturmon 2y ago
    > ...numericists don't like the throwing away bit... Although in 2 dimensions (setting of OP), this isn't that bad (you waste a proportion of (1-pi/4), or 21%, of your samples) -- perhaps 21% might be worth worrying about for some applications. Of course, it gets much worse in higher dimensions, because the unit ball is much smaller than the unit cube there.
    - mattkrause 2y ago
      This obviously depends on a million other factors too (implementation, language, architecture, etc) but I've benchmarked this a few times and, at least for naive implementations in 2D/3D, rejection sampling was often faster.
  - a_e_k 2y ago
    In graphics, we also often try to avoid any kind of rejection sampling because it wrecks importance sampling.
    - mturmon 2y ago
      Hmm, interesting. Is this still the case if the rejection factor is known explicitly (as it would be here)?
- cozzyd 2y ago
  Maybe you mean something like regular? I wouldn't call this sampling uniform.
Sharlin 2y ago
One use case that immediately comes to mind as a hobbyist graphics coder is generating rays to simulate things like depth of field or soft shadows.

david-gpu 2y ago

This subject has been studied in depth before, hasn't it? E.g. Shirley's mapping, which can be combined with a low-discrepancy sequence such as Hammersley. Here is an introduction for those curious: https://towardsdatascience.com/unit-disk-uniform-sampling-91880f3740fa https://towardsdatascience.com/unit-disk-uniform-sampling-91...

a_e_k 2y ago
I was going to mention the Shirley and Chiu mapping. A copy of the original paper can be found here and is nice and easy to read, with pseudocode: https://web.archive.org/web/20190223095317id_/http://pdfs.semanticscholar.org/4322/6a3916a85025acbb3a58c17f6dc0756b35ac.pdf https://web.archive.org/web/20190223095317id_/http://pdfs.se... Alternatively for the non-random and arbitrary N case here, an approach based on Phyllotaxis that samples a Fermat spiral every ~137.508 degrees (i.e., the golden angle, or the golden ratio fraction of a circle) also works pretty well: https://en.wikipedia.org/wiki/Fermat%27s_spiral#The_golden_ratio_and_the_golden_angle https://en.wikipedia.org/wiki/Fermat%27s_spiral#The_golden_r.... It works nicely for any N, even if the N isn't square or close to square (just choose the scaling appropriately, e.g., c = 1/sqrt(N)).

sega_sai 2y ago

A bit of a strange ad-hoc solution. First as other pointed out, one can generate the Sobol sequence or similar, but even with a random sample one can generate the random numbers deterministically. I.e Sample r^2 ~ Uniform(0,r0^2) and angle from U(0,2*pi) and use the fixed seed...

deleted 2y ago
[deleted]
throwaway127482 2y ago
Wouldn't a fixed seed mean you're repeating values a bunch, which would be inefficient? And how would you know when to stop generating values?
- sega_sai 2y ago
  You would fix the seed once in the beginning before sampling. Also you would need to sample exactly N-times as there no rejection required. as the points will all be within the circle by construction and will have uniform distribution
  - throwaway127482 2y ago
    The article was specifically asking for concentric rings with equally spaced points - how would you fix the seed such that this property is held?
    - sega_sai 2y ago
      The problem was stated in the beginning as 'Consider the problem of generating N points on a disk of diameter D. The function must be deterministic and the points somewhat uniformly spread around on the disk. Importantly, I want to generate exactly N points, for any integer value of N.' Then the author decided to do it through concentric rings.
mturmon 2y ago

zokier 2y ago

Having one point at the center does not feel intuitive. For example the N=19 feels like it would be more uniform as same as N=20 but without center point. Similarly N=3 could be just the points on the outer circle, similar to what N=4 is now.

Sharlin 2y ago
N=19 (and likely N=18 etc) could also be more uniform if it already jumped to M=2, so that it would be like N=20 except with five points on the inner ring. Or maybe with six on the inner and twelve on the outer. Would probably be fairly easy to turn this into an optimization problem if one wanted a really uniform distribution (eg. distribute points on rings such that some sum of squared distances is minimized).
Jaxan 2y ago
I agree that N=3 (and also N=2 for that matter) could be distributed better. EDIT: but for large N these things probably don’t matter that much. And I guess that’s the application in the end.
mturmon 2y ago
It turns out there are differing interpretations of what to do about the edges. For an "interior" packing (there is a technical word for this that I don't recall rn), following the link by @mbauman below, the n=3 case is: http://hydra.nat.uni-magdeburg.de/packing/cci/d1.html http://hydra.nat.uni-magdeburg.de/packing/cci/d1.html and the other cases are nearby.
- zokier 2y ago
  circle packing feels slightly different problem, especially as it doesn't tend to have any obvious algorithmic solutions available; circle packing produces irregular packings which I'm not sure I'd call super uniform btw what are the colors indicating on that page? its missing a legend and its not immediately obvious to me.
  - mturmon 2y ago

plagiarist 2y ago

Isn't this a variation of a sphere-packing problem? We know an optimally dense packing for 2D spheres. Then vary the radius of what is being packed until N of them fit in the disk's area.

mbauman 2y ago
> We know an optimally dense packing for 2D spheres We do? I think this is the latest state of the research here — only 14 Ns are proven optimal and it's certainly nowhere close to a general algorithm: http://hydra.nat.uni-magdeburg.de/packing/cci/ http://hydra.nat.uni-magdeburg.de/packing/cci/ There's something to be said for a dozen lines of numpy that gets "close enough". That said, I do think there should be something better.
- plagiarist 2y ago
  If they're 2D and packed on a plane, though, I think we do. That's reasonable if we're talking about "close enough." I wouldn't argue with the brevity of the numpy, though. Choosing how to place the disk over a plane of circles in an optimal way could be complicated.
TacticalCoder 2y ago
[dead]

0xml 2y ago

Another interesting method is Fibonacci Lattice. https://observablehq.com/@meetamit/fibonacci-lattices https://observablehq.com/@meetamit/fibonacci-lattices