Non-random uniform disk sampling
29 comments
·January 27, 2025PaulHoule
Sharlin
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.
fouronnes3
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
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-...
[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
> ...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.
a_e_k
In graphics, we also often try to avoid any kind of rejection sampling because it wrecks importance sampling.
cozzyd
Maybe you mean something like regular? I wouldn't call this sampling uniform.
zokier
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.
mturmon
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
and the other cases are nearby.
zokier
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
I get you. The purple circles are not kissing other circles, but the yellow ones -- not sure. In general it seems to have to do with how constrained they are.
And there may be differently-arranged also-optimal packings - e.g. for N = 18 there are others besides what is shown.
Sharlin
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
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.
david-gpu
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-91...
a_e_k
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.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_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)).
0xml
Another interesting method is Fibonacci Lattice. https://observablehq.com/@meetamit/fibonacci-lattices
sega_sai
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...
mturmon
The randomly-chosen numbers (with a fixed seed) will not have uniform coverage. They will look very noticeably "clumpy". I get the feeling that OP did not want that.
I agree that filtering the Sobol sequence, or other low-discrepancy sequence, would be another path to a solution.
throwaway127482
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
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
The article was specifically asking for concentric rings with equally spaced points - how would you fix the seed such that this property is held?
null
plagiarist
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
> 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/
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
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
[dead]
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
[2] https://extremelearning.com.au/unreasonable-effectiveness-of...
[3] https://numerical.recipes/