Jump to content
  • Advertisement
Sign in to follow this  
stuh505

Fast way to generate random point on hemisphere?

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

If you intended to correct an error in the post then please contact us.

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 this post


Link to post
Share on other sites
Advertisement
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 this post


Link to post
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 this post


Link to post
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 this post


Link to post
Share on other sites
Quote:
Original post by Bob Janova
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?

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 this post


Link to post
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 this post


Link to post
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
Admiral

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

Share this post


Link to post
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 this post


Link to post
Share on other sites
Quote:
Original post by TheAdmiral
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).

....

Regards
Admiral


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 this post


Link to post
Share on other sites
Quote:
Original post by TheAdmiral
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).

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).

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

Participate in the game development conversation and more when you create an account on GameDev.net!

Sign me up!