Jump to content
  • Advertisement

Archived

This topic is now archived and is closed to further replies.

Origin

Distributing equidistant points on a sphere

This topic is 5637 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 way to compute the coordinates of N points on a sphere with the distance between one point and its nearest neighbours minimized. Now that problem is well known as Spherical Covering, or finding Spherical Codes. But my problem is not to find the optimal distribution of N points on a sphere with a given radius, but to look for a radius - and possible solutions for N - where the points on the sphere meet the following conditions: Each point must have exactly six neighbours - which is given when the points are exactly, or very closely, equidistant from their neighbours. How may I calculate this? Do you know of existing solutions?

Share this post


Link to post
Share on other sites
Advertisement
If you look at the source code of glut.h you''ll find this exact solution.

Share this post


Link to post
Share on other sites
quote:
Original post by v71
If you look at the source code of glut.h you''ll find this exact solution.
May you elaborate on that?

If you''re thinking of the glutWireSphere and glutSolidSphere functions, I don''t think that these will help me. I need to find a solution for the distribution of points having the exact same distance to any of their neighbouring points.

Share this post


Link to post
Share on other sites
Is there actually an *exact* solution for this problem? Six equidistant neighbors per vertex would imply a totally regular "triangle mesh" structure. You can fill the plane with it, but AFAIK there is no solid with this property. Unlike, say, the icosahedron or subdivided versions of it with 5 neighbors per vertex... Am I wrong?

Share this post


Link to post
Share on other sites
quote:
Original post by klk
Is there actually an *exact* solution for this problem?
That's what I want to know.

quote:
Original post by klk
Six equidistant neighbors per vertex would imply a totally regular "triangle mesh" structure. You can fill the plane with it, but AFAIK there is no solid with this property. Unlike, say, the icosahedron or subdivided versions of it with 5 neighbors per vertex... Am I wrong?
Well, it needn't necessarily be exactly six neighbours. You are right that exact solutions exist for some particular and small N (like 2, 3, 4, ..., 20) with a neighbour count up to 5. But when N becomes greater, it must be six neighbours as any part of the sphere will approximate a plane.

The question is whether there can be a radius r and a number of points N so that the points meet the condition of equidistance. If there is no solution, are there approximations to ensure that each point has the same amount of neighbours with the requirement of equidistance roughly fulfilled?

[edited by - Origin on July 3, 2003 9:06:12 AM]

Share this post


Link to post
Share on other sites
Well, yeah, if you just have a lot of points, that''ll happen. It won''t be exact, but as N approaches infinity, the error will approach zero.

Share this post


Link to post
Share on other sites
You could just use an algorithm to create a geodesic(sp?) ''sphere'' of the desired complexity, and then merge groups of triangles into hexagons. There has to be an algorithm to create a correct geodesic sphere as some 3d packages have that as one of the primitives.

Share this post


Link to post
Share on other sites
quote:
Original post by Extrarius
You could just use an algorithm to create a geodesic(sp?) ''sphere'' of the desired complexity, and then merge groups of triangles into hexagons. There has to be an algorithm to create a correct geodesic sphere as some 3d packages have that as one of the primitives.
Does anybody know of such an algorithm?

Share this post


Link to post
Share on other sites
it''s easy . Create an icosahedron (20 triangle faces, 12 vertices). get the midpoints of each edges, and link them. That will give you 4 smaller triangles of identical size. Keep doing that, and you''ll generate a sphere where all the neighbours are equidistant. However, some vertices will have 5 neighbours, not 6. Those vertices with 5 neighbours would be the vertices of the origina icosahedron.

Unless someone knows a shape where all vertices have exactly 6 neighbours, and where all neighbours are equidistant... But this looks like a mathematical incongruity



// Icosahedron

const float a = (float) sqrt(2.0f/(5.0f + sqrt(5.0f)));
const float b = (float) sqrt(2.0f/(5.0f - sqrt(5.0f)));

Vector Vertices[12] =
{
Vector(-a, 0.0f, b), Vector(a, 0.0f, b), Vector(-a, 0.0f, -b), Vector(a, 0.0f, -b),
Vector(0.0f, b, a), Vector(0.0f, b, -a), Vector(0.0f, -b, a), Vector(0.0f, -b, -a),
Vector(b, a, 0.0f), Vector(-b, a, 0.0f), Vector(b, -a, 0.0f), Vector(-b, -a, 0.0f)
};

int Indices[20][3] =
{
{ 1, 4, 0 }, { 4, 9, 0 }, { 4, 5, 9 }, { 8, 5, 4 }, { 1, 8, 4 },
{ 1, 10, 8 }, { 10, 3, 8 }, { 8, 3, 5 }, { 3, 2, 5 }, { 3, 7, 2 },
{ 3, 10, 7 }, { 10, 6, 7 }, { 6, 11, 7 }, { 6, 0, 11 }, { 6, 1, 0 },
{ 10, 1, 6 }, { 11, 0, 9 }, { 2, 11, 9 }, { 5, 2, 9 }, { 11, 2, 7 }
};


also, if you want to texture it, you should not use a standard 2D bitmap, but rather, strip the basic icosahedron into several strips of triangles, and lay them flat on the bitmap, so they look something like this



http://mathworld.wolfram.com/Dodecahedron.html

the third wireframe picture. This is for a dodecahedron, but you get teh picture.

Share this post


Link to post
Share on other sites
Another way that I have seen on the pov-ray forums is by randomly scattering the points on the sphere then using electrostatic repultion(sp?) to push each node apart then normalize them to the sphere. I have never tried it but they said it converges pretty quickly.

Share this post


Link to post
Share on other sites

  • Advertisement
×

Important Information

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

GameDev.net is your game development community. Create an account for your GameDev Portfolio and participate in the largest developer community in the games industry.

Sign me up!