Sign in to follow this  
DangerDave

Generating a point cloud on a sphere

Recommended Posts

I would like to cycle through spherical polar coordinates generating a load of points on the sphere at equal distances from each other. I've got a nested for-loop cycling through the two angles (from 0 to 2*PI) by a constant; but this way points are generated closer together at the top and bottom of the sphere, e.g. at the top of the sphere I only want 1 point, where my for-loop will generate as many points as the for-loop runs for. I would like to generate the sphere this way since then its easier for me to construct a triangle mesh, I think (suggestions welcome..) Any tips/links for algorithms would be most appreciated. Cheers,

Share this post


Link to post
Share on other sites
What you are looking for is how to computationally generate geospheres. In contrast to the sphere you described, it has the vertices divided so that they form equilateral triangles.

Share this post


Link to post
Share on other sites
The problem, as you have noticed, is that points aren't uniformly distributed along phi/theta.

Check out some of these links... I don't have time to describe it thoroughly right now, but I'm sure one of the first links will cover it.

Share this post


Link to post
Share on other sites
Here... for each point, generate 2 random numbers from 0.0-1.0, R1 and R2.

Using R1 and R2, calculate phi and theta this way:
PHI = arccos(1 - R1)
THETA = 2 * PI * R2

I just scribbled and worked the integrals really quickly so I may have screwed them up, but those look right just from memory. That should give you a uniform distribution of points on the sphere.

EDIT: Sorry, I didn't catch the part about "fixed distances"... I was thinking of a random, uniformly distributed point cloud.

Share this post


Link to post
Share on other sites
Here's a method that works fairly well. Start with a random distribution of the points. Pick the two closest points and separate them a little bit (I would separate them as 3D points and then project them back to the sphere by renormalizing). Rinse. Repeat.

Over time you can reduce how much you separate the two points. After a little bit of tuning, you should get decent geospheres in not too much time.

Share this post


Link to post
Share on other sites
OK, searching google for geospheres and uniform sampling on spheres is not getting me anywhere.. Any more direct links or other search keywords most appreciated.

(Starting to think this is actually a hard problem to solve, was kinda assuming it would be a well-known general algorithm, but theres stuff I've found about space partitioning and all sorts...)

Share this post


Link to post
Share on other sites
OK, thanks for all the replies.

Its narrowed down now to a problem of generating a triangle mesh of a geodesic dome, with the triangle vertices defined in consistant CW/CCW order.

Is the only reasonable way to do this hard-code an icosahedron, then trim/tesselate it to required resolution? Are there no more general algorithms?

Share this post


Link to post
Share on other sites
The algorithm I gave you should work. To find the triangles that form the mesh, you can compute the convex hull of the points. I don't know how hard it is to find info on 3D convex hull on the web...

Share this post


Link to post
Share on other sites
Quote:
Original post by DangerDave
OK, thanks for all the replies.

Its narrowed down now to a problem of generating a triangle mesh of a geodesic dome, with the triangle vertices defined in consistant CW/CCW order.

Is the only reasonable way to do this hard-code an icosahedron, then trim/tesselate it to required resolution? Are there no more general algorithms?

That is how I have done it in the past. I am interested if you find any other ways as I am approaching this same topic.

vterrain.org's spherical LOD page seems to consist primarily of subdivisions.

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this