Hacker News Reader

Comment by PaulHoule | Hacker News Reader

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/

View on HN

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.

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.

Reply on news.ycombinator.com