Distributing equidistant points on a sphere
Author
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?
Author
quote:Original post by v71May you elaborate on that?
If you look at the source code of glut.h you''ll find this exact solution.
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.
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?
Author
quote:Original post by klkThat's what I want to know.
Is there actually an *exact* solution for this problem?
quote:Original post by klkWell, 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.
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?
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]
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.
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.
Author
quote:Original post by ExtrariusDoes anybody know of such an algorithm?
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.
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
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.
. 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
// Icosahedronconst 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.
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.
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
