5 ms·

why would anyone think you could do that? if someone thought, "i want to uniformly sample a subset of x-y space, i guess i'll instead ill sample in r-theta spac

why would anyone think you could do that? if someone thought, "i want to uniformly sample a subset of x-y space, i guess i'll instead ill sample in r-theta space and then use the nonlinear transformation x = r cos theta and y = r sin theta to sample uniformly." i would assume someone didnt even know what uniform meant if they did that. and graphics people are so insane about perf, they arent going to just start doing sqrt over and over. they are going to rejection sample anyway because it just 2 fmas

deleted 4y ago
[deleted]
beaugunderson 4y ago
and for those looking for a demonstration of an O(n) approach, Jason Davies' demo of Poisson Disk sampling is a good start and links to Bridson's algorithm: https://www.jasondavies.com/poisson-disc/ https://www.jasondavies.com/poisson-disc/
thomasahle 4y ago
It's not clear that rejection sampling would be faster. Assmuning this is a graphics operation running on a GPU. Taking the sqrt is pretty optimized, and having a branch for every point to be sampled is not fun.
- jeffparsons 4y ago
  Spot on. A lot of graphics people in the thread point this out. (I am not a graphics person — I occasionally tinker, but mostly just appreciate it from a distance.)
- onedognight 4y ago
  Rejection sampling doesn’t need sin/cos. What costs more, generating a random number and maybe a second or a random number and a sin/cos? This sounds very platform dependent. Note that when generating random points in the 4-ball (i.e. a quaternion)? The ball takes up a much smaller percentage of the space in the hypercube compared to the disk in a square, so rejections sampling can take many iterations.
  - OskarS 4y ago
    > What costs more, generating a random number and maybe a second or a random number and a sin/cos You’re adding a very unpredictable loop branch and a bunch of data dependencies doing that. For GPUs (and maybe even CPUs), the sqrt way is almost certainly faster.
    - gpderetta 4y ago
      If you have ALUs to spare, you can generate multiple points in parallel, say 4, and it is likely that at least one is inside the disk and you can select it branchlessly. Then you only need to loop in the very very rare case.
      - thomasahle 4y ago
        Just saying it's not clear and one would have to benchmark to find out.
toxicFork 4y ago
The thinking goes more like this: I want to get a random point in a circle. What parameters make up a point in a circle? Radius and angle can be one, so let's randomise those. This is something that's done a lot in game development.
- eru 4y ago
  And it _is_ a random point in a circle. Just not a uniformly distributed one. Btw, here's a way to sample a uniform random point on the edge of a circle without trigonometric functions: Sample x and y coordinates from a standard normal distribution. Then project the result on the circle, by normalising the distance. (You can approximate normal distributions fairly easily. Or your favourite computing environment might have specialised optimized machinery built-in.)
  - toxicFork 4y ago
    > Sample x and y coordinates from a standard normal distribution. Then project the result on the circle, by normalising the distance. I wonder if that's uniform... I expect that you would have more points mapped to the corners.
    - keefe8 4y ago
      It appears to be uniform. I tested empirically in Python: https://pastebin.com/raw/ca03uywJ https://pastebin.com/raw/ca03uywJ
      - toxicFork 4y ago
        https://codepen.io/toxicfork/pen/OJQzLba https://codepen.io/toxicfork/pen/OJQzLba This says otherwise
        Malipeddi 4y ago
        Normal distribution is not the same as uniform distribution. I edited in a normal distribution sampler in your codepen example. https://pastebin.com/raw/CP4yNRE9 https://pastebin.com/raw/CP4yNRE9
mattpharr 4y ago
Rejection sampling is not a good choice here. First, the cost is 2 FMAs * the cost of generating 2 random numbers * the number of rejection sampling iterations. On average, you reject (4-pi)/4 ~= 0.25 of the time. However, if you're running on a GPU in a warp (or the equivalent) of 32 threads, then you pay the cost of the maximum number of rejections over all the threads. The bigger issue is that a direct mapping from [0,1]^2 to the disk, as is described in this tweet, if you have well-distributed uniform samples in [0,1]^2, you get well-distributed samples on the disk. Thus, stratified or low discrepancy samples in [0,1]^2 end up being well distributed on the disk. In turn, this generally gives benefits in terms of error with Monte Carlo integration of functions over the disk.
- namibj 4y ago
  You can have the threads cooperate, distributing from those that got extra to those that were unlucky.
na85 4y ago
>why would anyone think you could do that? They don't realize/they lack intuition about the nonlinearity of going from rectangular to polar coordinates. Things like this aren't necessarily immediately obvious, depending on one's academic background.
eru 4y ago
> and graphics people are so insane about perf, they arent going to just start doing sqrt over and over. they are going to rejection sample anyway because it just 2 fmas If you can re-jig the rest of your algorithm to consume the square of the radius (instead of the radius itself), you don't need to take a square-root here.
- olliej 4y ago
  Sqrt is actually one of the faster operations, though obviously avoiding the need for any operation is clearly preferable :)
  - eru 4y ago
    Here's a much simpler way to get the same distribution (in JavaScript syntax): var radius1 = Math.max(Math.random(), Math.random()); var radius2 = Math.sqrt(Math.random()); Basically taking the maximum of two uniformly distributed random variables is the same as taking the square root of one of them in terms of their distributions. Whether taking the max of two variables is cheaper than the square-root of one depends on implementation details, I guess? You can also re-use the random variable that the max 'tossed' away by scaling it.
qsort 4y ago
Haven't you ever forgotten the determinant of the jacobian?
- nh23423fefe 4y ago
  this cuts deep

deleted 4y ago

[deleted]

beaugunderson 4y ago

and for those looking for a demonstration of an O(n) approach, Jason Davies' demo of Poisson Disk sampling is a good start and links to Bridson's algorithm: https://www.jasondavies.com/poisson-disc/ https://www.jasondavies.com/poisson-disc/

thomasahle 4y ago

It's not clear that rejection sampling would be faster. Assmuning this is a graphics operation running on a GPU. Taking the sqrt is pretty optimized, and having a branch for every point to be sampled is not fun.

jeffparsons 4y ago
Spot on. A lot of graphics people in the thread point this out. (I am not a graphics person — I occasionally tinker, but mostly just appreciate it from a distance.)
onedognight 4y ago
Rejection sampling doesn’t need sin/cos. What costs more, generating a random number and maybe a second or a random number and a sin/cos? This sounds very platform dependent. Note that when generating random points in the 4-ball (i.e. a quaternion)? The ball takes up a much smaller percentage of the space in the hypercube compared to the disk in a square, so rejections sampling can take many iterations.
- OskarS 4y ago
  > What costs more, generating a random number and maybe a second or a random number and a sin/cos You’re adding a very unpredictable loop branch and a bunch of data dependencies doing that. For GPUs (and maybe even CPUs), the sqrt way is almost certainly faster.
  - gpderetta 4y ago
    If you have ALUs to spare, you can generate multiple points in parallel, say 4, and it is likely that at least one is inside the disk and you can select it branchlessly. Then you only need to loop in the very very rare case.
    - thomasahle 4y ago
      Just saying it's not clear and one would have to benchmark to find out.

toxicFork 4y ago

The thinking goes more like this: I want to get a random point in a circle. What parameters make up a point in a circle? Radius and angle can be one, so let's randomise those. This is something that's done a lot in game development.

eru 4y ago
And it _is_ a random point in a circle. Just not a uniformly distributed one. Btw, here's a way to sample a uniform random point on the edge of a circle without trigonometric functions: Sample x and y coordinates from a standard normal distribution. Then project the result on the circle, by normalising the distance. (You can approximate normal distributions fairly easily. Or your favourite computing environment might have specialised optimized machinery built-in.)
- toxicFork 4y ago
  > Sample x and y coordinates from a standard normal distribution. Then project the result on the circle, by normalising the distance. I wonder if that's uniform... I expect that you would have more points mapped to the corners.
  - keefe8 4y ago
    It appears to be uniform. I tested empirically in Python: https://pastebin.com/raw/ca03uywJ https://pastebin.com/raw/ca03uywJ
    - toxicFork 4y ago
      https://codepen.io/toxicfork/pen/OJQzLba https://codepen.io/toxicfork/pen/OJQzLba This says otherwise
      - Malipeddi 4y ago
        Normal distribution is not the same as uniform distribution. I edited in a normal distribution sampler in your codepen example. https://pastebin.com/raw/CP4yNRE9 https://pastebin.com/raw/CP4yNRE9

mattpharr 4y ago

Rejection sampling is not a good choice here. First, the cost is 2 FMAs * the cost of generating 2 random numbers * the number of rejection sampling iterations. On average, you reject (4-pi)/4 ~= 0.25 of the time. However, if you're running on a GPU in a warp (or the equivalent) of 32 threads, then you pay the cost of the maximum number of rejections over all the threads. The bigger issue is that a direct mapping from [0,1]^2 to the disk, as is described in this tweet, if you have well-distributed uniform samples in [0,1]^2, you get well-distributed samples on the disk. Thus, stratified or low discrepancy samples in [0,1]^2 end up being well distributed on the disk. In turn, this generally gives benefits in terms of error with Monte Carlo integration of functions over the disk.

namibj 4y ago
You can have the threads cooperate, distributing from those that got extra to those that were unlucky.

na85 4y ago

>why would anyone think you could do that? They don't realize/they lack intuition about the nonlinearity of going from rectangular to polar coordinates. Things like this aren't necessarily immediately obvious, depending on one's academic background.

eru 4y ago

> and graphics people are so insane about perf, they arent going to just start doing sqrt over and over. they are going to rejection sample anyway because it just 2 fmas If you can re-jig the rest of your algorithm to consume the square of the radius (instead of the radius itself), you don't need to take a square-root here.

olliej 4y ago
Sqrt is actually one of the faster operations, though obviously avoiding the need for any operation is clearly preferable :)
- eru 4y ago
  Here's a much simpler way to get the same distribution (in JavaScript syntax): var radius1 = Math.max(Math.random(), Math.random()); var radius2 = Math.sqrt(Math.random()); Basically taking the maximum of two uniformly distributed random variables is the same as taking the square root of one of them in terms of their distributions. Whether taking the max of two variables is cheaper than the square-root of one depends on implementation details, I guess? You can also re-use the random variable that the max 'tossed' away by scaling it.

qsort 4y ago

Haven't you ever forgotten the determinant of the jacobian?

nh23423fefe 4y ago
this cuts deep