Fast way to generate random point on hemisphere?

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

Recommended Posts

I'm looking for a fast -- the fastest-- way to generate a uniformly distributed point on an a hemisphere centered about an arbitrary vector. I know a fast way to generate points on an axis-aligned hemisphere, but it relies on the cartesian axis and therefore isn't generalizable for an arbitrary hemisphere. I could use do a quaternion rotation (this is what I'm currently doing) but I'm thinking there may be a faster, more direct, way.

Share on other sites
The method you use for an axis-aligned hemisphere can easily be generalized to work with any set of axis. Instead of the usual i = (1,0,0), j = (0,1,0), and k = (0,0,1), you use some other set a, b, and c, such that a x b = c, b x c = a, and c x a = b. Essentially, you work entirely in the rotated frame, instead of working in the world frame and then rotating.

Share on other sites
Oh yeah, duh :)

But it can still be faster. Rather than generating an orthonormal basis (which would require doing the first step in Gram-Schmidt I think) we could just generate a pt on unit sphere and then take the dot product with the normal and negate the vector if its negative

Share on other sites
Yeah, I'd say that's the fastest (create random points on a sphere, flip those in the wrong half then scale and translate). So the question becomes: do you have a fast way to generate points on a sphere?

Share on other sites
Quote:
 Original post by Bob JanovaYeah, I'd say that's the fastest (create random points on a sphere, flip those in the wrong half then scale and translate). So the question becomes: do you have a fast way to generate points on a sphere?

Simply generate a random unit length vector, multiply it by the radius of your sphere then add the center of the sphere. It's then guaranteed to be on the sphere.

If this is not fast enough, you could create a 2d lookup-table of vectors uniformly distributed on the sphere, pickup a random float number then interpolate between the 4 vectors you fall in-between. I doubt this would be faster than normalizing then scaling the vector though, depends on the platform. What's interesting with this approach is that it may be tweaked so your emisphere is simply a range in the look-up table...

[Edited by - deks on November 15, 2006 9:40:02 PM]

Share on other sites
This seems to be reasonably fast. If you have a fast InvSqrt, you can do faster.
#include <iostream>unsigned my_rand(void){  static unsigned next1=1151752134u, next2=2070363486u;  next1 = next1 * 1701532575u + 571550083u;  next2 = next2 * 3145804233u + 4178903934u;  return (next1<<16)^next2;}struct Vector3D {  float x, y, z;    Vector3D(float x, float y, float z):x(x),y(y),z(z){  }    float dot(Vector3D const &v){    return x*v.x + y*v.y + z*v.z;  }    Vector3D & operator+=(Vector3D const &v){    x += v.x;    y += v.y;    z += v.z;        return *this;  }};std::ostream & operator<<(std::ostream &o, Vector3D const &v){  return o << '(' << v.x << ',' << v.y << ',' << v.z << ')';}float U_m1_p1(){  return float(my_rand())*(1.0f/2147483648.0f) - 1.0f;}Vector3D pick_random_point_in_sphere(){  float x0,x1,x2,x3,d2;  do{    x0=U_m1_p1();    x1=U_m1_p1();    x2=U_m1_p1();    x3=U_m1_p1();    d2=x0*x0+x1*x1+x2*x2+x3*x3;  }while(d2>1.0f);  float scale = 1.0f/d2;  return Vector3D(2*(x1*x3+x0*x2)*scale,                  2*(x2*x3+x0*x1)*scale,                  (x0*x0+x3*x3-x1*x1-x2*x2)*scale);}Vector3D pick_random_point_in_semisphere(Vector3D const &v){  Vector3D result=pick_random_point_in_sphere();  if(result.dot(v)<0){    result.x=-result.x;    result.y=-result.y;    result.z=-result.z;  }  return result;}int main(){  Vector3D dir(1,0,0), sum(0,0,0);    for(int i=0;i<10000000;++i){    sum += pick_random_point_in_semisphere(dir);  }  std::cout << sum << std::endl;}

Share on other sites
Picking an arbitrary vector (uniform in 3-space) and normalising it will not give a uniform distribution over the sphere. The density at (1, 1, 1) will be more than that at (1, 0, 0) by a factor sqrt(3).

Edit: Removed lies [rolleyes].

Regards

[Edited by - TheAdmiral on November 18, 2006 1:55:43 PM]

Share on other sites
I've used this, I think it is ok.

void RanUnitVector(void)
{
scalar a,b,l;

do
{
a = 1.0 - 2.0*ran2();
b = 1.0 - 2.0*ran2();
l = a*a + b*b;
}while(1<l);

scalar s = sqrt(1.0 - l);

x = 2.0*a*s;
y = 2.0*b*s;
z = 1.0 - 2.0*l;
}

Share on other sites
Quote:
 Original post by TheAdmiralPicking an arbitrary vector (uniform in 3-space) and normalising it will not give a uniform distribution over the sphere. The density at (1, 1, 1) will be more than that at (1, 0, 0) by a factor sqrt(3).....RegardsAdmiral

I don't want to derail the discussion, but I think that's really interesting. I can almost see it, but can you explain it a bit more?

Share on other sites
Quote:
 Original post by TheAdmiralPicking an arbitrary vector (uniform in 3-space) and normalising it will not give a uniform distribution over the sphere. The density at (1, 1, 1) will be more than that at (1, 0, 0) by a factor sqrt(3).

Of course. But you can fix this by discarding points outside of the sphere:
Vector3D pick_random_point_in_sphere(){  float x1,x2,x3,d2;  do{    x1=U_m1_p1();    x2=U_m1_p1();    x3=U_m1_p1();    d2=x1*x1+x2*x2+x3*x3;  }while(d2>1.0f);  float scale = 1.0f/sqrt(d2); // or use a fast InvSqrt for this  return Vector3D(x1*scale,x2*scale,x3*scale);}

You only need an average of 6/Pi trials (about 1.91).

1. 1
2. 2
Rutin
16
3. 3
4. 4
5. 5

• 26
• 9
• 11
• 9
• 9
• Forum Statistics

• Total Topics
633710
• Total Posts
3013486
×