Generating a point cloud on a sphere
Author
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,
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.
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.
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.
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.
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.
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.
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.
Author
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...)
(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...)
Author
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?
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?
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...
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.
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
