🎉 Celebrating 25 Years of GameDev.net! 🎉

Not many can claim 25 years on the Internet! Join us in celebrating this milestone. Learn more about our history, and thank you for being a part of our community!

random point in sphere

Started by
10 comments, last by RomanGenkhel 4 years, 6 months ago

Ok, this should be really simple...

I just wrote this (with Unreal Engine):

float ExtX = 100.f, ExtY = 100.f;

float x = 0.f, y = 0.f;
float Radius = sqrt(FMath::SRand());
float Angle = FMath::SRand() * 2.f * PI;
x = FMath::Sin(Angle) * Radius * ExtX;
y = FMath::Cos(Angle) * Radius * ExtY;

to get evenly distributed random points on a circle or ellipse. 100.000 points placed like this look fine.

Now I want to get something similar for spheres (potentially "warped" on 3 axes)

I tried this:

float ExtX = 100.f, ExtY = 100.f, ExtZ = 100.f;

float Radius = sqrt(sqrt(FMath::SRand()));
float Angle1 = FMath::SRand() * 2.f * PI;
float Angle2 = FMath::SRand() * 2.f * PI;

x = FMath::Sin(Angle2) * FMath::Cos(Angle1) * Radius * ExtX;
y = FMath::Cos(Angle2) * FMath::Cos(Angle1) * Radius * ExtY;
z = FMath::Sin(Angle1) * Radius * ExtZ;

But points clearly have a bias towards the Z-axis now. What am I missing?

Advertisement

It's because you're passing a uniform distribution through a cosine for the x and y coordinates (*Cos(Angle1)), and then it's not uniform anymore. You could try choosing a uniform random value for cos(Angle1) instead of Angle1 itself, that is:

float cosAngle1 = 2 * SRand - 1; // uniform within [-1, 1]
float sinAngle1 = sqrt(1 - cosAngle1 * cosAngle1); // corresponding sine

or "brutally" clip 3 uniform distributions to a sphere:

do
{	
  x = 2 * SRand - 1;	
  y = 2 * SRand - 1;	
  z = 2 * SRand - 1;
} while (x * x + y * y + z * z > 1);

The few extra loops might be less costly than the calls to sine and cos actually!


If we consider generated points with a given Angle1, we notice that as the angle approaches 90 degrees (or we are getting closer to the poles on the Z-axis) the points sit on a circle of decreasing circumference so the points will end up closer together.

To resolve this, you could bias the generation of Angle1 so that it is more likely to be close to 0 which will counteract this property or if Unreal Engine can generate Gaussian or normally distributed random values you can generate 3d points which if they are not zero their distance to the centre of the sphere can be normalised so that they have the correct radius. Extending these to ellipsoids (what I assume you mean by 'warped' spheres) I am not so sure about.

Do you know what kind of bias for Angle1 I would need to make points evenly distributed? Otherwise, I think clamping doesn't sound so bad, when you put it like that... at least that's some maths I understand ^^

Max Power said:
what kind of bias for Angle1 I would need to make points evenly distributed

Well that would be arc-cosine as in:

float Angle1 = acos(2 * SRand -1);

But unless you need Angle1 elsewhere you can then directly compute "cosAngle1" and "sinAngle1" as suggested above, which would save a very ugly cos(acos(...)) ^^:

float ExtX = 100.f, ExtY = 100.f, ExtZ = 100.f;

float Radius = sqrt(sqrt(FMath::SRand()));
float cosAngle1 = 2.0f * FMath::SRand() - 1.0f;
float sinAngle1 = sqrt(1.0f - cosAngle1  * cosAngle1); // because sin² + cos² = 1
float Angle2 = FMath::SRand() * 2.f * PI;

x = FMath::Sin(Angle2) * cosAngle1 * Radius * ExtX;
y = FMath::Cos(Angle2) * cosAngle1 * Radius * ExtY;
z = sinAngle1 * Radius * ExtZ;
do {
  float x = FMath::SRand() * 2.f - 1.f;
  float y = FMath::SRand() * 2.f - 1.f;
  float z = FMath::SRand() * 2.f - 1.f;
} while (x * x + y * y + z * z < 1.f);
x *= ExtX;
y *= ExtY;
z *= ExtZ;

No trigonometry, no square roots, and you can tell it's correct just by looking at it. The only drawback is that the worst case performance is terrible, but it makes up for it by being that much faster in the average case.

This problem made me think a bit about it, and just got an idea. Not sure if it produces uniform distribution, nor if it covers the entire sphere volume.

mx = 1
x = Random(-mx, mx)
mx -= x * x
y = Random(-mx, mx)
mx -= y * y
z = Random(-mx, mx)

What do you think? Can this work?


I would go for "a light breeze"'s implementation for any practical application, but it's fun to think of alternatives.

Similarly for the case of the circle, pick a random radius as the cubic root of a random number picked from a uniform distribution between 0 and 1. Then pick a point uniformly on the sphere of that radius.

Picking a point uniformly on a sphere (of radius 1, say) can be done in several ways. My two favorite methods are:

  1. Pick z uniformly between -1 and 1, then pick an angle at random to determine x and y. This really does work!!
  2. Pick three numbers from a Gaussian distribution, then normalize the resulting vector.
true
alvaro said:

I would go for "a light breeze"'s implementation for any practical application, but it's fun to think of alternatives.

Similarly for the case of the circle, pick a random radius as the cubic root of a random number picked from a uniform distribution between 0 and 1. Then pick a point uniformly on the sphere of that radius.

Picking a point uniformly on a sphere (of radius 1, say) can be done in several ways. My two favorite methods are:

  1. Pick z uniformly between -1 and 1, then pick an angle at random to determine x and y. This really does work!!
  2. Pick three numbers from a Gaussian distribution, then normalize the resulting vector.

Either I am misunderstanding something or your method 1 would create a higher density of points around the poles (0, 0, -1) and (0, 0, 1). Could you explain in more detail?


The z coordinate of a uniformly distributed random point on a sphere is uniformly distributed. I know this fact is surprising, which is why I gave it a double exclamation mark.

3blue1brown has a video about the formula for the area of a sphere that centers around the same fact: https://youtu.be/GNcFjFmqEc8

This topic is closed to new replies.

Advertisement