Hello!

I would like to render a sphere with an arbitrary number of points (or
smaller spheres) on its surface that I want to distribute equally (so
the distance to the neighbouring points is nearly equal for every
point). I suppose there is no perfect solution for that problem, but I
would like to approximate it as good as possible.

A funktion could look like this:
Input: Number of points (n)
Output: n pairs of angles (horizontal and vertical from sphere's center)
that describe the location of the points. (alternatively <x,y,z>-coords
on the surface)

Of course, the solution is easy for n = 1(trivial), 2(line),
3(traingle), 4(tetrahedron), 6(octahedron), 8(cube) and some more. I
also checked http://www.cris.com/~rjbono/html/domes.html , but geodesic
domes always have a "magic" number of corners.

Does anyone have an idea for this? Any help would be appreciated (also
"It does not work, because..").

/PETER/

-- 
Peter Santo (PUMP development)
Visit: http://www.ieee.rwth-aachen.de/mp3/

Post a reply to this message

On Tue, 01 Jun 1999 05:50:13 +0200, Peter Santo
<san### [at] poolinformatikrwth-aachende> wrote:


>I would like to render a sphere with an arbitrary number of points (or
>smaller spheres) on its surface that I want to distribute equally (so
>the distance to the neighbouring points is nearly equal for every
>point). I suppose there is no perfect solution for that problem, but I
>would like to approximate it as good as possible.
>
>A funktion could look like this:
>Input: Number of points (n)
>Output: n pairs of angles (horizontal and vertical from sphere's center)
>that describe the location of the points. (alternatively <x,y,z>-coords
>on the surface)
>
>Of course, the solution is easy for n = 1(trivial), 2(line),
>3(traingle), 4(tetrahedron), 6(octahedron), 8(cube) and some more. I
>also checked http://www.cris.com/~rjbono/html/domes.html , but geodesic
>domes always have a "magic" number of corners.
>
>Does anyone have an idea for this? Any help would be appreciated (also
>"It does not work, because..").

The question is tricky because "equal distribution" on a sphere turns
out not to be really well defined.  Nonetheless, there are solutions.
The FAQ for the group comp.graphics.algorithms has pointers to several
discussions and even specific point sets for many numbers.  If you
can't find the stuff referenced by the FAQ, email me and I will send
you some tech info and point sets.

Jerry Anning
clem "at" dhol "dot" com

Post a reply to this message

I long ago brought to this group an excellent link for all this kinds of
info. Here is the link to the specific subject you request information
about:

http://www.mhri.edu.au/~pdb/geometry/spherepoints/

Good luck.

--
Anthony L. Bennett
http://welcome.to/TonyB

Graphics rendered
by the Dreamachine.

Post a reply to this message

On Tue, 01 Jun 1999 05:50:13 +0200, Peter Santo
<san### [at] poolinformatikrwth-aachende> wrote:

>Hello!
>
>I would like to render a sphere with an arbitrary number of points (or
>smaller spheres) on its surface that I want to distribute equally (so
>the distance to the neighbouring points is nearly equal for every
>point). I suppose there is no perfect solution for that problem, but I
>would like to approximate it as good as possible.
>
>/PETER/

Let the points repel each other. Restrict their movement to the
surface of the sphere. Place them randomly (for ex. x=rand(),
y=rand(), z = sqrt(1-x*x-y*y) ). Start to calculate theit movement due
to repulsive forces. Stop when the velocity of the currently fastest
point does not exceed 4*pi*r/NumberOfPoints [in SpaceUnits per
TimeUnits] or some other preset value. return();

Hope this helps.
---------
Peter Popov
ICQ: 15002700

Post a reply to this message

Peter Santo <san### [at] poolinformatikrwth-aachende> wrote:
> Hello!
>
> I would like to render a sphere with an arbitrary number of points (or
> smaller spheres) on its surface that I want to distribute equally (so
> the distance to the neighbouring points is nearly equal for every
> point). I suppose there is no perfect solution for that problem, but I
> would like to approximate it as good as possible.
>
> A funktion could look like this:
> Input: Number of points (n)
> Output: n pairs of angles (horizontal and vertical from sphere's center)
> that describe the location of the points. (alternatively <x,y,z>-coords
> on the surface)
>
> Of course, the solution is easy for n = 1(trivial), 2(line),
> 3(traingle), 4(tetrahedron), 6(octahedron), 8(cube) and some more. I
> also checked http://www.cris.com/~rjbono/html/domes.html , but geodesic
> domes always have a "magic" number of corners.

There are only 3 solutions because when all points are equaly distributed
they will make out triangles with equaly long sides, and there only exists 3
such cases: the tetrahedron(4 sides), the octahedron(8 sides) and the
dodecaedron(20 sides). On a cube, for example, the points are not equaly
distributed. How ever there are recursive methods of finding a close
solution for any number of points, and that usualy is close enough. Two
methods are described in this page:
http://www.mhri.edu.au/~pdb/geometry/spherepoints/index.html

/Anders

Post a reply to this message

Peter Popov wrote:
> 
> On Tue, 01 Jun 1999 05:50:13 +0200, Peter Santo
> <san### [at] poolinformatikrwth-aachende> wrote:
> 
> >Hello!
> >
> >I would like to render a sphere with an arbitrary number of points (or
> >smaller spheres) on its surface that I want to distribute equally (so
> >the distance to the neighbouring points is nearly equal for every
> >point). I suppose there is no perfect solution for that problem, but I
> >would like to approximate it as good as possible.
> >
> >/PETER/
> 
> Let the points repel each other. Restrict their movement to the
> surface of the sphere. Place them randomly (for ex. x=rand(),
> y=rand(), z = sqrt(1-x*x-y*y) ). Start to calculate theit movement due
> to repulsive forces. Stop when the velocity of the currently fastest
> point does not exceed 4*pi*r/NumberOfPoints [in SpaceUnits per
> TimeUnits] or some other preset value. return();
> 
> Hope this helps.
> ---------
> Peter Popov
> ICQ: 15002700

I have been wondering about a solution for this some time ago.
I think your strategy is brilliant (in the way that it makes me say: why didn't
_I_ thin of that? ;-)) but I think POV will parse on this forever. You'll
probably need an external program to do the calculations. 
Anybody?

Remco

Post a reply to this message

On Tue, 01 Jun 1999 11:52:21 +0200, Remco de Korte
<rem### [at] xs4allnl> wrote:

>I have been wondering about a solution for this some time ago.
>I think your strategy is brilliant (in the way that it makes me say: why didn't
>_I_ thin of that? ;-)) but I think POV will parse on this forever. You'll
>probably need an external program to do the calculations. 
>Anybody?
>
>Remco

Nay, not mine. I think I saw it in either sci.math, sci.physics or
comp.graphics.algorithms. Check out the FAQs of those groups to find
out who the author of the algorithm is.

---------
Peter Popov
ICQ: 15002700

Post a reply to this message

Thank you all very much for your helpful information!

> >You'll
> >probably need an external program to do the calculations.
> >Anybody?

> Nay, not mine. I think I saw it in either sci.math, sci.physics or
> comp.graphics.algorithms. Check out the FAQs of those groups to find
> out who the author of the algorithm is.

What is wrong with the code at
http://www.mhri.edu.au/~pdb/geometry/spherepoints/ ?

> >but I think POV will parse on this forever.

Hmm, in fact, I thought about making the algorithm a little more
efficient (adaptive step size) and implementing it as a povray macro.
But maybe it is not a sensible thing to do, because you either render a
single image - then it is not worth writing lots of code. Or you render
an animation - then you do not want to spend too much time parsing.

/PETER/

-- 
Peter Santo (PUMP development)
Visit: http://www.ieee.rwth-aachen.de/mp3/

Post a reply to this message

Anders Haglund wrote:

>...
> > Of course, the solution is easy for n = 1(trivial), 2(line),
> > 3(traingle), 4(tetrahedron), 6(octahedron), 8(cube) and some more. I
> > also checked http://www.cris.com/~rjbono/html/domes.html , but geodesic
> > domes always have a "magic" number of corners.

The "optimal" solution for n=8 is not the cube, but a pair of
parallel squares rotated by 45 degrees (which is probably what
Anders means). The first thing Peter would have to decide is whether
he wants something which looks regular (e.g. platonic solids), or
something which has optimally distributed points (with respect to some
repulsive force).

The general solution to the former is probably to start with
one of the 5 platonic solids and regularly subdivide the faces
(this gives geodesic domes).
The latter requires numeric optimization (I'd say one should use
a rather complicated method, since povray is much slower than C).

> dodecaedron(20 sides). On a cube, for example, the points are not equaly
I guess you mean the icosahedron here (a dodecahedron has 12
pentagons).

Ralf

Post a reply to this message

> > > 3(traingle), 4(tetrahedron), 6(octahedron), 8(cube) and some more. I
> The "optimal" solution for n=8 is not the cube, but a pair of
> parallel squares rotated by 45 degrees (which is probably what
> Anders means).

.. and what I mean :)  : If a cube is enclosed by a sphere, it touches
the sphere's surface at 8 points.

> The first thing Peter would have to decide is whether
> he wants something which looks regular (e.g. platonic solids), or
> something which has optimally distributed points (with respect to some
> repulsive force).

I would like to be able to create both. I find the exact solution
mathematically challenging and the numerical approximation interesting
as it allows to render nice animations of rearranging points.
It all started with the plan to build a lamp with 15 small bulbs (bad
number) on a hemisphere. Since then I thought of several things to
render with such an algorithm, e.g. spikes on sphere-shaped creatures.

> The general solution to the former is probably to start with
> one of the 5 platonic solids and regularly subdivide the faces
> (this gives geodesic domes).

Does subdivision work with the cube and the dodecahedron?

Ok, with subdivision of triangles like this

      /\
     /  \
    /    \
   /______\
  / \    / \
 /   \  /   \
/_____\/_____\

..we can realize objects with the following number of verteces:

From tetrahedron :  4, 10,  34, 130,  512, ...
From octahedron  :  6, 18,  66, 258, 1026, ...
From cube        :  8, ?
From icosahedron : 12, 42, 162, 642, 2562, ... (is this correct?)
From dodecahedron: 20, ?

Bucky-ball (C60-Fulleren): 60, ?

Is there an exact solution for 5, 7 or 16 points?

/PETER/

-- 
Peter Santo (PUMP development)
Visit: http://www.ieee.rwth-aachen.de/mp3/

Post a reply to this message

Peter Santo wrote:
> 
> Is there an exact solution for 5, 7 or 16 points?

IIRC from my chemistry days (one of the real-world applications of this
stuff), the solution for 5 points is (in terms of the surface of a
sphere) three on the equator, 120 degrees apart, and the other two at
the poles.

I'm not sure about 7 or 16.  I get the impression that exact solutions
exist for all values of n.  It boils down to a big optimization problem,
if you construct it in terms of minimizing net forces among a set of
mutually repellant points constrained by a sphere.  Maybe linear
programming would yield solutions?

-- 
Mark Gordon
mtg### [at] povrayorg

Post a reply to this message

Peter Santo wrote:
> 
> Hello!
> 
> I would like to render a sphere with an arbitrary number of points (or
> smaller spheres) on its surface that I want to distribute equally (so
> the distance to the neighbouring points is nearly equal for every
> point). I suppose there is no perfect solution for that problem, but I
> would like to approximate it as good as possible.
> 
> A funktion could look like this:
> Input: Number of points (n)
> Output: n pairs of angles (horizontal and vertical from sphere's center)
> that describe the location of the points. (alternatively <x,y,z>-coords
> on the surface)
> 
> Of course, the solution is easy for n = 1(trivial), 2(line),
> 3(traingle), 4(tetrahedron), 6(octahedron), 8(cube) and some more. I
> also checked http://www.cris.com/~rjbono/html/domes.html , but geodesic
> domes always have a "magic" number of corners.
> 
> Does anyone have an idea for this? Any help would be appreciated (also
> "It does not work, because..").
> 
> /PETER/
> 
> --
> Peter Santo (PUMP development)
> Visit: http://www.ieee.rwth-aachen.de/mp3/

I know this is a well worn subject already but check out the post I just
made in povray.text.scene-files under the thread Kens Function Collection
for a routine for distributing points equaly along the surface of a sphere.
It is probably the same equation found in Bourke's collection.

-- 
Ken Tyler

mailto://tylereng@pacbell.net

Post a reply to this message

Hi Peter!

Peter Santo wrote:

> I would like to render a sphere with an arbitrary number of points (or
> smaller spheres) on its surface that I want to distribute equally (so
> the distance to the neighbouring points is nearly equal for every
> point). I suppose there is no perfect solution for that problem, but I
> would like to approximate it as good as possible.

I had the same problem. After some time I realized that a factor of 5 works
very fine:
Solution 1: 7 points (1 at each pole and ring at 90degree with 5 points)
Solution 2: 22 points (1 at each pole, a ring of 5 points at 45degrees, a
ring of 10 points at 90degrees, a ring of 5 points at 135 degrees)
Solution 3: 47 points (1, 5, 10, 15, 10, 5, 1)
Solution 4: 82 points (1, 5, 10, 15, 20, 15, 10, 5, 1)
Solution 5: 127 points (1, 5, 10, 15, 20, 25, 20, 15, 10, 5, 1)
... and so on ...

You cannot choose any number of points but using a factor of 5 is *very*
simple and the output looks fine. And you can choose really high numbers of
points without any complicated calculation.
A picture using this technique can be found at
http://home.ins.de/~tobias.wiersch/htm/newyear.htm

Hope this helps ...

 ... tobias wiersch

Post a reply to this message

Distributing Points on a Sphere webpage

http://www.mhri.edu.au/~pdb/geometry/spherepoints/

steve

Peter Santo wrote:

> Hello!
>
> I would like to render a sphere with an arbitrary number of points (or
> smaller spheres) on its surface that I want to distribute equally (so
> the distance to the neighbouring points is nearly equal for every
> point). I suppose there is no perfect solution for that problem, but I
> would like to approximate it as good as possible.
>
> A funktion could look like this:
> Input: Number of points (n)
> Output: n pairs of angles (horizontal and vertical from sphere's center)
> that describe the location of the points. (alternatively <x,y,z>-coords
> on the surface)
>
> Of course, the solution is easy for n = 1(trivial), 2(line),
> 3(traingle), 4(tetrahedron), 6(octahedron), 8(cube) and some more. I
> also checked http://www.cris.com/~rjbono/html/domes.html , but geodesic
> domes always have a "magic" number of corners.
>
> Does anyone have an idea for this? Any help would be appreciated (also
> "It does not work, because..").
>
> /PETER/
>
> --
> Peter Santo (PUMP development)
> Visit: http://www.ieee.rwth-aachen.de/mp3/

Post a reply to this message

Remco de Korte wrote:
> 
> I have been wondering about a solution for this some time ago.
> I think your strategy is brilliant (in the way that it makes me say: why didn't
> _I_ thin of that? ;-)) but I think POV will parse on this forever. You'll
> probably need an external program to do the calculations.
> Anybody?

I had the idea and wrote a small C-program to do that and export
the found points to POV-speres. Bottom line: it just doesn't work,
because the spheres "fall" into some local energy minimum and
make nice patterns, but for most values for N, they are far from
being equally spaced.

Markus
-- 
"Denkst Du vielleicht über den nächsten Satz nach, den Du sagen willst?
 Ich nicht eine Sekunde!!!" H. Heinol in Val Thorens

Post a reply to this message

Peter Santo wrote:
> 
> Hmm, in fact, I thought about making the algorithm a little more
> efficient (adaptive step size) and implementing it as a povray macro.
> But maybe it is not a sensible thing to do, because you either render a
> single image - then it is not worth writing lots of code. Or you render
> an animation - then you do not want to spend too much time parsing.

I had my C-code to output severay POV-files so I could
render an animation and look how the sphreses spread
across the other sphere. Thus it was called sprdsphr.

If you're interested in the program, send a
mailto:mar### [at] studentuni-siegende

and I'll send you the source for it.

Markus
-- 
"Denkst Du vielleicht über den nächsten Satz nach, den Du sagen willst?
 Ich nicht eine Sekunde!!!" H. Heinol in Val Thorens

Post a reply to this message

Markus Becker wrote:
> 
> Remco de Korte wrote:

I've been working on something like this in a program and an include file. I
have an include that calculates points on a sphere based upon such a thing with
twelve points :), recursively, which is only for a fixed amount of points but it
takes ages to parse and I'm afraid the same will happen for the include file
that will distribute any amount of points. 
I don't really need it (anymore) but if anyone is interested I could give it a
go, but don't complain about parsing time.
(as an example: calculating some 16000 points took over a day and then I broke
it off - the same would probably take a couple of minutes in a separate program)

But, to come to my actual reply: the problem with the local minimum is something
that has been bothering me too. I think it has something to do with the points
being on a sphere. There should be workarounds, but as I said, I abandoned it
for now. I think someone will come up with a brilliant solution one of these
days.

Regards,

Remco
http://www.xs4all.nl/~remcodek/pov.html

Post a reply to this message

Remco de Korte wrote:
> 
> But, to come to my actual reply: the problem with the local minimum is something
> that has been bothering me too. I think it has something to do with the points
> being on a sphere. There should be workarounds, but as I said, I abandoned it
> for now. I think someone will come up with a brilliant solution one of these
> days.

The problem is, that there is only a solution for some speacial
values of N (ie. magic numbers...). For all other values of N
this is simply impossible. You can always minimize some energy
balance, even a global one, but don't expect to be able to
distribute the points evenly on a sphere.

Markus
-- 
"Denkst Du vielleicht über den nächsten Satz nach, den Du sagen willst?
 Ich nicht eine Sekunde!!!" H. Heinol in Val Thorens

Post a reply to this message

Markus Becker wrote:
> 
> Remco de Korte wrote:
> >
> > But, to come to my actual reply: the problem with the local minimum is something
> > that has been bothering me too. I think it has something to do with the points
> > being on a sphere. There should be workarounds, but as I said, I abandoned it
> > for now. I think someone will come up with a brilliant solution one of these
> > days.
> 
> The problem is, that there is only a solution for some speacial
> values of N (ie. magic numbers...). For all other values of N
> this is simply impossible. You can always minimize some energy
> balance, even a global one, but don't expect to be able to
> distribute the points evenly on a sphere.
> 
> Markus

Is that so? I'm willing to believe it, but I wonder if there's some way to prove
that or make it acceptable for a mathematician (which I'm most definitely not).

Groeten,

Remco

Post a reply to this message

Remco de Korte wrote:
> 
> Is that so? I'm willing to believe it, but I wonder if there's some way to prove
> that or make it acceptable for a mathematician (which I'm most definitely not).

Yes, this _is_ so. It is mathematically proven. A simplified (and short)
explanation is that you can only tile certain surfaces with certain
patches.
The certain surface bein the spere and the patches being triangles,
pentagons
ans so on for the sphere surface.
If you have access to Scientific American, you should be able to find
articles about it.

For some reading, look here:
http://www.rose-hulman.edu/~brought/Epubs/REU/Wabash.html

Markus
-- 
"Denkst Du vielleicht über den nächsten Satz nach, den Du sagen willst?
 Ich nicht eine Sekunde!!!" H. Heinol in Val Thorens

Post a reply to this message

Markus Becker wrote:
> 
> Remco de Korte wrote:
> >
> > Is that so? I'm willing to believe it, but I wonder if there's some way to prove
> > that or make it acceptable for a mathematician (which I'm most definitely not).
> 
> Yes, this _is_ so. It is mathematically proven. A simplified (and short)
> explanation is that you can only tile certain surfaces with certain
> patches.
> The certain surface bein the spere and the patches being triangles,
> pentagons
> ans so on for the sphere surface.
> If you have access to Scientific American, you should be able to find
> articles about it.
> 
> For some reading, look here:
> http://www.rose-hulman.edu/~brought/Epubs/REU/Wabash.html
> 
> Markus

Aha! Thanks! This means I won't have to feel frustrated because I can't solve
this little problem.

CU!

Remco

Post a reply to this message

I don't know why I didn't see this thread earlier... it's already one
month old...

However, I just recently wrote and published a macro for geodesic
spheres which happen to be bodies that are constructed by dividing the
surface of a sphere into triangles. The principle behind it starts from
the three basic polyhedra with triangular faces:
  tetrahedron  4 faces
  octahedron   8 faces
  icosahedron  20 faces
and divides each triangular face into smaller triangles. Though it is
NOT possible to put any number of points (or triangles/corners) onto a
sphere you can choose from quite a variety of values by just selecting
the basic polyhedron and the "frequency" of subdivision for each face.
The number of faces on the final sphere is then calculated as 

  number of faces on polyhedron * (freq^2)

so you can get the following values:

freq      tetrahedron    octahedron   icosahedron
  1             4             8            20
  2            16            32            80
  3            36            72           180
  4            64           128           320
  5           100           200           500
  6           144           288           720
  8           256           512          1280
etc.    

By defining your own "drawing" (better: object placing) routine for each
face, edge and corner, you can easily distribute whatever object you
want on the faces.

You can download the macro, documentation  and see some examples at
http://www.geocities.com/SiliconValley/Lakes/5432/povray/geodesic.html


Uwe.

Post a reply to this message