Finding a random point on a sphere (with spread and direction).

This topic is 713 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

Recommended Posts

I'm trying to implement a particle system (in 3D) were an emitter can have a direction and spread.

The direction is defined as a 3D normalized vector.

The spread is a scalar value (0.0 - 1.0) which represents the range, relative to the direction, that particles can start moving.

• So a spread=0.0 would be the same as the direction vector.  This special case makes the spread value moot.
• A spread=0.5 would be a half-sphere, with the dome-side oriented in the same direction as the direction vector.
• A spread=1.0 would be a whole sphere.  This special case makes the direction vector moot.

The following example illustrates the problem in 2D.  The red coloring highlights the spread.

In each picture (except the last one) the direction vector is going straight up (x=0, y=1).

The last picture (parden my poor drawing) is supposed to be the normalized vector (x=0.7, y=0.7).

[attachment=33650:example.png]

Share on other sites
Pick a random number z uniformly between cos(spread*pi) and 1. Pick a random angle theta. Make x = sqrt(1-z^2)*cos(theta), y = sqrt(1-z^2)*sin(theta). Now apply to (x,y,z) a rotation that turns (0,0,1) into the desired direction. Voilà! Edited by Álvaro

Share on other sites
Some code for you (I was bored). The meat is in the function random_direction'.

#include <iostream>
#include <cmath>
#include <ctime>

float const Pi = std::atan(1.0f) * 4.0f;

float uniform_random(float a, float b) {
return a + drand48() * (b - a);
}

struct Vector {
float x, y, z;

Vector(float x, float y, float z) : x(x), y(y), z(z) {
}
};

std::ostream &operator<<(std::ostream &os, Vector const &v) {
return os << '(' << v.x << ',' << v.y << ',' << v.z << ')';
}

Vector operator+(Vector const &v1, Vector const &v2) {
return Vector(v1.x + v2.x, v1.y + v2.y, v1.z + v2.z);
}

Vector operator*(float s, Vector const &v) {
return Vector(s * v.x, s * v.y, s * v.z);
}

float dot(Vector const &v1, Vector const &v2) {
return v1.x * v2.x + v1.y * v2.y + v1.z * v2.z;
}

float length(Vector const &v) {
return std::sqrt(dot(v, v));
}

Vector cross_product(Vector const &v1, Vector const &v2) {
return Vector(v1.y * v2.z - v1.z * v2.y,
v1.z * v2.x - v1.x * v2.z,
v1.x * v2.y - v1.y * v2.x);
}

Vector normalize(Vector const &v) {
return (1.0f / length(v)) * v;
}

Vector random_direction(Vector direction, float spread) {
// Make an orthogonal basis whose third vector is along direction'
Vector b3 = normalize(direction);
Vector different = (std::abs(b3.x) < 0.5f) ? Vector(1.0f, 0.0f, 0.0f) : Vector(0.0f, 1.0f, 0.0f);
Vector b1 = normalize(cross_product(b3, different));
Vector b2 = cross_product(b1, b3);

// Pick (x,y,z) randomly around (0,0,1)
float z = uniform_random(std::cos(spread * Pi), 1);
float r = std::sqrt(1.0f - z * z);
float theta = uniform_random(-Pi, +Pi);
float x = r * std::cos(theta);
float y = r * std::sin(theta);

// Construct the vector that has coordinates (x,y,z) in the basis formed by b1, b2, b3
return x * b1 + y * b2 + z * b3;
}

int main() {
srand48(std::time(0));

for (int i = 0; i < 10; ++i)
std::cout << random_direction(Vector(1.0f, 0.0f, 0.0f), 0.1f) << '\n';
}



Enjoy!

Share on other sites

Pick a random number z uniformly between cos(spread*pi) and 1. Pick a random angle theta. Make x = sqrt(1-z^2)*cos(theta), y = sqrt(1-z^2)*sin(theta). Now apply to (x,y,z) a rotation that turns (0,0,1) into the desired direction. Voilà!

That makes sense.

Some code for you (I was bored). The meat is in the function `random_direction'.

Thank you so much!  You made my day.

Share on other sites
EDIT: I retract the following, it was based on incomplete knowledge extrapolated from uniformly sampling polar coordinates.

------

You should be aware that this distribution is not uniform and if you emit a lot of particles you are likely to see clustering, especially toward the poles. If the clustering is acceptable then this is probably the best solution, otherwise you may prefer to use a function which generates uniformly random points on the surface of a sphere and iterates until it finds a point that lands inside of your cone. Normalizing the output of a multivariate Gaussian distribution is a good way to get a uniform distribution on the surface of a sphere, see https://en.m.wikipedia.org/wiki/Multivariate_normal_distribution

Share on other sites

You should be aware that this distribution is not uniform and if you emit a lot of particles you are likely to see clustering, especially toward the poles. If the clustering is acceptable then this is probably the best solution, otherwise you may prefer to use a function which generates uniformly random points on the surface of a sphere and iterates until it finds a point that lands inside of your cone. Normalizing the output of a multivariate Gaussian distribution is a good way to get a uniform distribution on the surface of a sphere, see https://en.m.wikipedia.org/wiki/Multivariate_normal_distribution

You must be new here... ;)

Share on other sites

You must be new here... ;)

Relatively new, yup... is it that obvious? :)

Share on other sites

You must be new here... ;)

Relatively new, yup... is it that obvious? :)

Can you explain why you think the method I proposed produces a non-uniform distribution? I am pretty sure you are wrong about that. I am being immodest, so forgive me if that bothers you. My math skills are pretty good, and I won't normally get something like this wrong.

With a bit of calculus you can prove that the projection to an axis of a uniform distribution on the sphere is actually a uniform distribution. This surprising fact allows for the simple procedure I proposed in this thread.

This page covers several ways of producing uniformly distributed samples on the sphere: http://mathworld.wolfram.com/SpherePointPicking.html . The method you proposed is listed in equation (16). What I did is based on equations (6) to (8). Edited by Álvaro

Share on other sites
Alright, I did some investigation and I retract my earlier statement. I was aware that uniformly sampling polar angles would create bunching near the poles and I didn't expect uniformly sampling along a fixed axis to be any better, since it was not immediately obvious to me that slicing a sphere at uniform intervals along the z axis would divide the sphere surface into pieces of equal area. It looks like http://mathworld.wolfram.com/SpherePointPicking.html agrees that this is actually the case. I will edit the above post accordingly.

Edit: looks like your edit beat me to the punch :)

Share on other sites

Alright, I did some investigation and I retract my earlier statement. I was aware that uniformly sampling polar angles would create bunching near the poles and I didn't expect uniformly sampling along a fixed axis to be any better, since it was not immediately obvious to me that slicing a sphere at uniform intervals along the z axis would divide the sphere surface into pieces of equal area. It looks like http://mathworld.wolfram.com/SpherePointPicking.html agrees that this is actually the case. I will edit the above post accordingly.

Edit: looks like your edit beat me to the punch :)

Yeah, it's not obvious at all, but it's a really old result. It looks like Archimedes knew about it more than 2,200 years ago!

1. 1
2. 2
3. 3
Rutin
22
4. 4
5. 5

• 11
• 18
• 14
• 9
• 9
• Forum Statistics

• Total Topics
632929
• Total Posts
3009282
• Who's Online (See full list)

There are no registered users currently online

×