3 ms·

> First, it’s intuitively plausible that it works. Maybe; my first instinct is that there'll be some bias somewhere. Maybe I'll have some time tonight to play

> First, it’s intuitively plausible that it works. Maybe; my first instinct is that there'll be some bias somewhere. Maybe I'll have some time tonight to play with this in p5js.

pavel_lishin 1y ago
I had some time! It looks reasonably random to my eye: https://editor.p5js.org/fancybone/sketches/DUFhlJvOZ https://editor.p5js.org/fancybone/sketches/DUFhlJvOZ
- guccihat 1y ago
  Cool demo. A minor nitpick is that the code (and the article) forgets to handle the special case of a point inside the cube that happens to be exactly (0,0,0). This will result in a divide by zero when the vector is normalized.
  - NoahZuniga 1y ago
    The chance of this happening is less than 1 in 2^128. This will never happen.
    - pavel_lishin 1y ago
      Unless you're demoing it to someone very important, in which case it'll happen twice in a row.
      - rkomorn 1y ago
        Especially if you have already had the conversation with anyone and confidently stated that, yes, the possibility exists but it's so remote that it's just not worth addressing.
    - cluckindan 1y ago
      With long enough timescales, every event with a non-zero probability will eventually happen.
  - pavel_lishin 1y ago
    That nitpick is both minor, and absolutely correct!
- spyrja 1y ago
  Kind of? If you want the points to be more randomly-distributed, something like this would probably be a better approach: https://editor.p5js.org/spyrja/sketches/eYt7H36Ka https://editor.p5js.org/spyrja/sketches/eYt7H36Ka
sparky_z 1y ago
That was my first instinct as well, but I thought through it a little more and now it seems intuitively correct to me. -First of all, it's intuitive to me that the "candidate" points generated in the cube are randomly distributed without bias throughout the volume of the cube. That's almost by definition. -Once you discard all of the points outside the sphere, you're left with points that are randomly distributed throughout the volume of the sphere. I think that would be true for any shape that you cut out of the cube. So this "discard" method can be used to create randomly distributed points in any 3d volume of arbitrary shape (other than maybe one of those weird pathological topologies.) -Once the evenly distributed points are projected to the surface of the sphere, you're essentially collapsing each radial line of points down to a single point on the sphere. And since each radial line has complete rotational symmetry with every other radial line, each point on the surface of the sphere is equally likely to be chosen via this process. That's not a rigorous proof by any means, but I've satisfied myself that it's true and would be surprised if it turned out not to be.
- pavel_lishin 1y ago
  To me, it seems like there would be less likelihood of points being generated near the surface of the sphere, and that should have some sort of impact.
  - sparky_z 1y ago
    OK, look at it this way. Imagine that, after you generate the points randomly in the cube, and discard those outside the sphere, you then convert the remaining points into 3D polar coordinates (AKA spherical coordinates [0]). This doesn't change the distribution at all, just the numerical representation. So each point is described by three numbers, r, theta, and phi. You're correctly pointing out that the values of r won't be uniformly distributed. There will be many more points where the value of r is close to 1 then there will be where the value of r is close to 0. This is a natural consequence of the fact that the points are uniformly distributed throughout the volume, but there's more volume near the surface than there is near the center. That's all true. But now look at the final step. By projecting every point to the surface of the sphere, you've just overwritten every single point's r-coordinate with r=1. Any bias in the distribution of r has been discarded. This step is essentially saying "ignore r, all we care about are the values of theta and phi." [0]https://en.wikipedia.org/wiki/Spherical_coordinate_system https://en.wikipedia.org/wiki/Spherical_coordinate_system
layer8 1y ago
It should be intuitively clear that rotating the sphere (or the cube) won’t change the distribution of the random points before projection, hence the distribution of the projected points must be independent of the orientation of the sphere, and hence independent of any particular location on the sphere. Or in other words, if you take the “dotted” sphere out of the cube afterwards, you won’t be able to tell by the dots which way it was originally oriented within the cube.
bob1029 1y ago
The part that makes this work is the rejection aspect. What would be biased is if you inscribed a cube in the unit sphere. This would require additional transformations to create a uniform distribution. If you simply "throw away" the extra corner bits that aren't used, it won't affect the distribution.

> First, it’s intuitively plausible that it works. Maybe; my first instinct is that there'll be some bias somewhere. Maybe I'll have some time tonight to play with this in p5js.

pavel_lishin 1y ago

I had some time! It looks reasonably random to my eye: https://editor.p5js.org/fancybone/sketches/DUFhlJvOZ https://editor.p5js.org/fancybone/sketches/DUFhlJvOZ

guccihat 1y ago
Cool demo. A minor nitpick is that the code (and the article) forgets to handle the special case of a point inside the cube that happens to be exactly (0,0,0). This will result in a divide by zero when the vector is normalized.
- NoahZuniga 1y ago
  The chance of this happening is less than 1 in 2^128. This will never happen.
  - pavel_lishin 1y ago
    Unless you're demoing it to someone very important, in which case it'll happen twice in a row.
    - rkomorn 1y ago
      Especially if you have already had the conversation with anyone and confidently stated that, yes, the possibility exists but it's so remote that it's just not worth addressing.
  - cluckindan 1y ago
    With long enough timescales, every event with a non-zero probability will eventually happen.
- pavel_lishin 1y ago
  That nitpick is both minor, and absolutely correct!
spyrja 1y ago
Kind of? If you want the points to be more randomly-distributed, something like this would probably be a better approach: https://editor.p5js.org/spyrja/sketches/eYt7H36Ka https://editor.p5js.org/spyrja/sketches/eYt7H36Ka

sparky_z 1y ago

That was my first instinct as well, but I thought through it a little more and now it seems intuitively correct to me. -First of all, it's intuitive to me that the "candidate" points generated in the cube are randomly distributed without bias throughout the volume of the cube. That's almost by definition. -Once you discard all of the points outside the sphere, you're left with points that are randomly distributed throughout the volume of the sphere. I think that would be true for any shape that you cut out of the cube. So this "discard" method can be used to create randomly distributed points in any 3d volume of arbitrary shape (other than maybe one of those weird pathological topologies.) -Once the evenly distributed points are projected to the surface of the sphere, you're essentially collapsing each radial line of points down to a single point on the sphere. And since each radial line has complete rotational symmetry with every other radial line, each point on the surface of the sphere is equally likely to be chosen via this process. That's not a rigorous proof by any means, but I've satisfied myself that it's true and would be surprised if it turned out not to be.

pavel_lishin 1y ago
To me, it seems like there would be less likelihood of points being generated near the surface of the sphere, and that should have some sort of impact.
- sparky_z 1y ago
  OK, look at it this way. Imagine that, after you generate the points randomly in the cube, and discard those outside the sphere, you then convert the remaining points into 3D polar coordinates (AKA spherical coordinates [0]). This doesn't change the distribution at all, just the numerical representation. So each point is described by three numbers, r, theta, and phi. You're correctly pointing out that the values of r won't be uniformly distributed. There will be many more points where the value of r is close to 1 then there will be where the value of r is close to 0. This is a natural consequence of the fact that the points are uniformly distributed throughout the volume, but there's more volume near the surface than there is near the center. That's all true. But now look at the final step. By projecting every point to the surface of the sphere, you've just overwritten every single point's r-coordinate with r=1. Any bias in the distribution of r has been discarded. This step is essentially saying "ignore r, all we care about are the values of theta and phi." [0]https://en.wikipedia.org/wiki/Spherical_coordinate_system https://en.wikipedia.org/wiki/Spherical_coordinate_system

layer8 1y ago

It should be intuitively clear that rotating the sphere (or the cube) won’t change the distribution of the random points before projection, hence the distribution of the projected points must be independent of the orientation of the sphere, and hence independent of any particular location on the sphere. Or in other words, if you take the “dotted” sphere out of the cube afterwards, you won’t be able to tell by the dots which way it was originally oriented within the cube.

bob1029 1y ago

The part that makes this work is the rejection aspect. What would be biased is if you inscribed a cube in the unit sphere. This would require additional transformations to create a uniform distribution. If you simply "throw away" the extra corner bits that aren't used, it won't affect the distribution.