[HN Gopher] Non-random uniform disk sampling
___________________________________________________________________
Non-random uniform disk sampling
Author : fouronnes3
Score : 38 points
Date : 2025-01-27 17:09 UTC (5 hours ago)
(HTM) web link (victorpoughon.fr)
(TXT) w3m dump (victorpoughon.fr)
| PaulHoule wrote:
| 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/
| fouronnes3 wrote:
| 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 wrote:
| 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 wrote:
| > ...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 wrote:
| 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 wrote:
| In graphics, we also often try to avoid any kind of
| rejection sampling because it wrecks importance sampling.
| mturmon wrote:
| Hmm, interesting. Is this still the case if the rejection
| factor is known explicitly (as it would be here)?
| Sharlin wrote:
| 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 wrote:
| 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 wrote:
| 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)).
| sega_sai wrote:
| 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...
| throwaway127482 wrote:
| 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 wrote:
| 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 wrote:
| 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 wrote:
| 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 wrote:
| 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.
| zokier wrote:
| 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 wrote:
| 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 wrote:
| 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 wrote:
| 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.
| plagiarist wrote:
| 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 wrote:
| > 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.
___________________________________________________________________
(page generated 2025-01-27 23:01 UTC)