Archived

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

Origin

Distributing equidistant points on a sphere

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
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
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
quote:
Original post by oliii
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.
Correct. That would restrict the possible values for N and yield different numbers of neighbours. It would fulful the equidistance condition, though.

quote:
Original post by Yohumbus
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.
You mean something like this, right?
That works good, but it sometimes yields seven neighbours.

Maybe one can tweak it until all points have six neighbours....

Share this post


Link to post
Share on other sites
An approximation to a sphere forms a planar graph. Now looking at the formula:

V + F = E + 2

where:
V is the number of nodes or vertices.
F is the number of faces or regions.
E is the number of edges or arcs.

If you have N vertices then V = N.

If each vertex is connected to 6 others then the number of ends of arcs is 6N. Each arcs has 2 ends, so E = 3N.

Each vertex is a vertex of 6 faces. Now each face has 3 vertices. Therefore F = 2N.

N + 2N = 3N + 2
0 = 2. Oh dear, either I've got it wrong or your 'sphere' is impossible.


To clarify the F = 2N bit, each vertex is part of 6 corners. So the number of corners is 6N. As each face, which must be a triangle needs 3 corners, F = 2N

[edited by - higherspeed on July 4, 2003 2:19:09 PM]

Share this post


Link to post
Share on other sites
quote:
Original post by higherspeed
An approximation to a sphere forms a planar graph. Now looking at the formula:

V + F = E + 2

where:
V is the number of nodes or vertices.
F is the number of faces or regions.
E is the number of edges or arcs.

If you have N vertices then V = N.

If each vertex is connected to 6 others then the number of ends of arcs is 6N. Each arcs has 2 ends, so E = 3N.

Each vertex is a vertex of 6 faces. Now each face has 3 vertices. Therefore F = 2N.

N + 2N = 3N + 2
0 = 2. Oh dear, either I''ve got it wrong or your ''sphere'' is impossible.
Well, you got it right... This can''t be done.

With C being the number of connections:

V = N
E = (C/2)N
F = (C/3)N

N + (C/3)N = (C/2)N + 2

(1 - C/6) * N = 2

This excludes C > 5 and leaves possible values for N up to 12 (for C = 5), but not higher. That''s odd, but it''s true.

Can the sphere be done nonetheless if two points connect to only 5 instead of 6 neighboring points?

Share this post


Link to post
Share on other sites
quote:
Original post by oliii
YES!

use an icosahedron, and recursively subdivide the edges through the middle. Splits the triangles into 4 smaller triangles, ect...
Is it exactly two points then?

Well, thanks a lot!

Share this post


Link to post
Share on other sites
By symmetry arguments, you can''t just have 2 points with 5 neighbours.



As you can see from that limited angle you can see at least 2 points with 5 adjacent vertices. The first one is an icosahedron split once. The second is each tri spilt into 9 I think. The total number of points with 5 connections remains constant through spliting. I think that number''s twelve.

If I''ve misinterpreted the way you''ve split the icosahedron then I''m sorry.

Share this post


Link to post
Share on other sites
no that''s right. the only points ending up with 5 neighbours will be the original points of the icosahedron. If you split the edges through the middle, the connectivity for those points will acutally never change.

However, the points that are the result of edges splited in two will be connected to 6 vertices. Each split-vertex will be connected to the other edges of the two triangles sharing that edge.

So, 2 connections to link the edge points to the mid-vertex, and 2 other connections per triangles, that will connect each mid-points of the triangles together. 6 connections in total.




// original tris

// -------------


\ / \ /
-+---------------+-
/ \ /
/ \ /
/ \ /
/ \ /
/ \ /
/ \ /
/ \ /
-+---------------+-
/ \ / \


// calculate midpoints

// -------------------


\ / \ /
-+-------*-------+-
/ \ /
/ \ /
/ \ /
* * *
/ \ /
/ \ /
/ \ /
-+-------*-------+-
/ \ / \




// link midpoints together

// -----------------------


\ / \ / \ /
-+-------*-------+-
/ \ / \ /
/ \ / \ /
\/ \ / \ /
-*-------*-------*-
/ \ / \ / \
/ \ / \ /
/ \ / \ /
-+-------*-------+-
/ \ / \ / \




the trick with the starting icosahedron, is that the first 12 vertices will be linked to only 5 vertices


| |
| |
| |
-----+---------------+------
/ \ /
/ \ /
/ \ /
/ \ /
/ \ /
/ \ /
/ \ /
----+---------------+------
| |
| |



that''s about it That would give you a near optimum sphere. But as demonstrated before, you can''t get a perfect sphere anyway.

Share this post


Link to post
Share on other sites
Yeah, I''ve already implemented the splitting.

I think I can live with 12 points being different. With many points, it doesn''t even matter anymore.

Thanks again.

Share this post


Link to post
Share on other sites