Non-random uniform disk sampling | Hacker News Reader

Non-random uniform disk sampling

victorpoughon.fr

56 pointsfouronnes328 comments

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/

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.

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

> ...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.

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.

In graphics, we also often try to avoid any kind of rejection sampling because it wrecks importance sampling.

Hmm, interesting. Is this still the case if the rejection factor is known explicitly (as it would be here)?

Maybe you mean something like regular? I wouldn't call this sampling uniform.

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.

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.

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).

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.

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.

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.

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.

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...

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)).

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

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.

> 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.

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.

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...

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?

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

The article was specifically asking for concentric rings with equally spaced points - how would you fix the seed such that this property is held?

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.

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.

They will have a uniform distribution in the sense of every region with the same area will have exactly the same expected number of samples. But in fact it was not quite clear what the OP really wanted, other than coming up with their own solution.

Reply on news.ycombinator.com