Generating the edges is irrelevant to me.  I just want the vertices.  The
ultimate task for me is to determine the "solid angle" of a certain
projection on the sphere and analytical techniques have not been accurate
enough.

Could you please refer me to  an "electrostatic repulsion" algorithm - this
sounds like  a winner.
Many thanks,
Ilia




"Chris Johnson" <chris(at)chris-j(dot)co(dot)uk> wrote in message
news:4094ddba$1@news.povray.org...
> -[The final distribution is somewhat skewed with higher "point density"
> about the original vertices]-
> Once you have a mesh of the points, if you model electrostatic repulsion
> between the points, while keeping them bounded on the sphere, after a few
> iterations of the repulsion algorithm, the will have rearranged themselves
> into an even distribution. Alternatively, it might be a good idea to model
> the edges as springs pulling the modal together - this might avoid the
> potential problem of the points reshuffling so much that they form very
> non-iscosceles triangles. If you start with an icosahedron, I think this
> method might work.
>
> One could start with 60000 random points on a sphere and apply the
> electrostatic repulsion method to get a near-even distribution, but the
> difficulty then is finding the best way to form the edges. This problem of
> finding the "best" edges given a set of points is quite hard I think.
>
> -Chris
>
>

Post a reply to this message

"Ilia Guzei" <igu### [at] fozziechemwiscedu> schrieb im Newsbeitrag
news:40941f69@news.povray.org...
> I need to approximate a sphere with 60,000 points.  How can I generate
such
> a polyhedron with equivalent points on the sphere?  Perhaps a C algorithm
is
> posted some place on this web site but I can't find it.
Hi,

I would use a golden-section-based "Sunflower"-Distribution.
I've made a small POV-Scene which demonstrates this.
I think you won't have problems writing a similar C-program
off the POV-Source.

Source:


#version 3.5;

global_settings {
  assumed_gamma 1.0
}
camera {
  location  <1.3, 3.5, -1.0>
  direction 1.5*z
  right     x*image_width/image_height
  look_at   <0.0, 0.0,  0.0>
}
sky_sphere {
  pigment {
    gradient y
    color_map {
      [0.0 rgb <0.6,0.7,1.0>]
      [0.7 rgb <0.0,0.1,0.8>]
    }
  }
}
light_source {
  <-20, 30, -60>
  color rgb <0.9, 0.7, 0.3>
}
light_source {
  <70, 40, 80>
  color rgb <0.1, 0.3, 0.9>
}


#declare N  =  6000; // Number of Spheres
#declare M  =  N;
#declare sr = 1 * 2/sqrt(N);  // sphereradius
#declare phi= 0;
#declare gsa= 360*((sqrt(5)-1)/2);  // golden section angle
#declare py = -1;
#declare dy = 2/(N-1);

#while(M>0)
  sphere {
    py*y, sr
    translate sqrt(1-py*py)*x
    rotate phi*y
    texture {
      pigment{color rgb 1}
      finish{ambient 0 diffuse 0.5 reflection{0.6}}
    }
  }
  #declare py=-1+2*(M-1)/(N-1);
  #declare phi=phi+gsa;
  #declare M=M-1;
#end


> Thanks,
> Ilia
Regards,
Thies

Post a reply to this message

Ilia Guzei wrote:


> Shay:
> This will not be the case if you start with an
> icosahedron 
 
> Ilia:
> Unfortunately, it is the case.  Just to prove it, take
> a look at a triangle with the following apical positions
> <snip>

Yes, I see that you are correct. It seems that producing this with this type
of subdivision is impossible. Still, I made a distribution of 60k and
another at around 164k which were very close. Springs would not help
either, as topologically equal length sides of the subdivided shape are not
possible.

Probably the best way to start, however. On a subdivided mesh with all
points lying on a unit length sphere, the differences were around .0015, so
some repulsion correction would decrease that difference to beyond
measurable in a few steps.

 -Shay

Post a reply to this message

Here is an idea for fixing the vertex hoping:
http://www.geocities.com/fcmodelview/edgefix.jpg (copy and paste to browser)

To implement this, I think the easiest way would be to create a sub-routine
that connects an n-gon to an n/2-gon, and then call this routine for the
last "facets" of every slice. (Ie the "facets" closest to the vertex.)

Post a reply to this message

In article <40941f69@news.povray.org>,
 "Ilia Guzei" <igu### [at] fozziechemwiscedu> wrote:

> I need to approximate a sphere with 60,000 points.  How can I generate such
> a polyhedron with equivalent points on the sphere?  Perhaps a C algorithm is
> posted some place on this web site but I can't find it.

A recursively divided polyhedron will not give you fine control over the 
number of points. Each recursion multiplies the number of triangles by 4.

A more useful tessellation I've found is to use the tessellation of a 
cube projected onto the sphere. In other words, tessellate the sphere as 
six rectangular patches. This gives you far finer control over the 
actual resolution you want, rather than restricting you to powers of 4, 
but still gives a fairly even distribution of triangles.

-- 
Christopher James Huff <cja### [at] earthlinknet>
http://home.earthlink.net/~cjameshuff/
POV-Ray TAG: <chr### [at] tagpovrayorg>
http://tag.povray.org/

Post a reply to this message

In article <409495bc@news.povray.org>,
 "Ilia Guzei" <igu### [at] fozziechemwiscedu> wrote:

> Mersenne twister can probably produce a random enough (as in "uniform")
> distribution but I'd rather do it exactly if possible.  I need to do it once
> to generate an input table for an application, so time and algorithm
> efficiency is irrelevant.

It is not possible to do so for large numbers of points. As I recall, 
the largest number of points that can be perfectly evenly distributed is 
20, the triangles of an icosahedron or vertices of a dodecahedron.

If you need points with overall even spacing, and the spacing given by 
polyhedron subdivision is too uneven, the electrostatic repulsion method 
mentioned can help you minimize the unevenness. You basically model each 
point as a particle that repels the other particles by the 1/r^2 law. 
Figure out which direction the surrounding particles are pushing each 
particle, move it slightly in that direction and project it's new 
position onto the sphere, and repeat until the particles settle down 
enough.

-- 
Christopher James Huff <cja### [at] earthlinknet>
http://home.earthlink.net/~cjameshuff/
POV-Ray TAG: <chr### [at] tagpovrayorg>
http://tag.povray.org/

Post a reply to this message

Thanks to all who contributed to this discussion.  Paul Bourke's site was
interesting.  Ultimately, implementation of the "electrostatic repulsion"
suggestion did the trick.

I generated a desired number of points on the sphere in a random fashion and
then minimized the repulsion between the points.
While testing, a polyhedron with 8 vertices was inevitably a square prizm
rather than a cube...

Ilia



"Christopher James Huff" <cja### [at] earthlinknet> wrote in message
news:cjameshuff-F3FCDE.14012902052004@news.povray.org...
> In article <409495bc@news.povray.org>,
>  "Ilia Guzei" <igu### [at] fozziechemwiscedu> wrote:
>
> > Mersenne twister can probably produce a random enough (as in "uniform")
> > distribution but I'd rather do it exactly if possible.  I need to do it
once
> > to generate an input table for an application, so time and algorithm
> > efficiency is irrelevant.
>
> It is not possible to do so for large numbers of points. As I recall,
> the largest number of points that can be perfectly evenly distributed is
> 20, the triangles of an icosahedron or vertices of a dodecahedron.
>
> If you need points with overall even spacing, and the spacing given by
> polyhedron subdivision is too uneven, the electrostatic repulsion method
> mentioned can help you minimize the unevenness. You basically model each
> point as a particle that repels the other particles by the 1/r^2 law.
> Figure out which direction the surrounding particles are pushing each
> particle, move it slightly in that direction and project it's new
> position onto the sphere, and repeat until the particles settle down
> enough.
>
> --
> Christopher James Huff <cja### [at] earthlinknet>
> http://home.earthlink.net/~cjameshuff/
> POV-Ray TAG: <chr### [at] tagpovrayorg>
> http://tag.povray.org/

Post a reply to this message

Christopher James Huff wrote:


> 
> A more useful tessellation I've found is to...

This is how I produced my 60,000 vertices array.

 -Shay

Post a reply to this message

I haven't seen an algorithm for it specifically, though an example was on
p.binaries.animations a while ago.

Heres some C code - I've typed this straight into the post so there could
well be typos, but I think the overall idea is right:

typedef struct
{
   float x,y,z;
} point;

int maxPoints=60000;
point *points;
points=(point *)malloc(maxPoints*sizeof(point));
float repulseCoeff = 0.1;
int maxIterations = 50;
float dd;

// Initially distribute points randomly on sphere
for (int n=0; n<maxPoints; n++)
{
    do
    {
        points[n].x = frnd(2)-1;   // frnd(float max) generates random
number between 0 and max
        points[n].y = frnd(2)-1;
        points[n].z = frnd(2)-1;
    }
    while (sq(points[n].x)+sq(points[n].y)+sq(points[n].z)>1)
}

for (int i=0; i<maxIterations; i++) // Iterate this bit a few times
{
    for (int n=0; n<maxPoints; n++)
    {
        for (int m=n+1; m<maxPoints; m++) // for each pair of points...
        {
            // make them repulse each other, without a restriction that they
stay on the sphere

dd=sq(points[n].x-points[m].x)+sq(points[n].y-points[m].y)+sq(points[n].z-po
ints[m].z);
            points[n].x += (points[n].x-points[m].x)*repulseCoeff/dd;
            points[n].y += (points[n].y-points[m].y)*repulseCoeff/dd;
            points[n].z += (points[n].z-points[m].z)*repulseCoeff/dd;
            points[m].x -= (points[n].x-points[m].x)*repulseCoeff/dd;
            points[m].y -= (points[n].y-points[m].y)*repulseCoeff/dd;
            points[m].z -= (points[n].z-points[m].z)*repulseCoeff/dd;
        }
    }

    for (int n=0; n<maxPoints; n++) // for each point
    {
        // stick it back onto the sphere
        dd = sqrt(sq(points[n].x)+sq(points[n].y)+sq(points[n].z));
        points[n].x/=dd;
        points[n].y/=dd;
        points[n].z/=dd;
    }
}

-Chris

Post a reply to this message

Chris Johnson nous apporta ses lumieres ainsi en ce 2004/05/03 15:44... :

>I haven't seen an algorithm for it specifically, though an example was on
>p.binaries.animations a while ago.
>
>Heres some C code - I've typed this straight into the post so there could
>well be typos, but I think the overall idea is right:
>
>typedef struct
>{
>   float x,y,z;
>} point;
>
>int maxPoints=60000;
>point *points;
>====> points=(point *)malloc(maxPoints*sizeof(point));
>float repulseCoeff = 0.1;
>int maxIterations = 50;
>float dd;
>
>// Initially distribute points randomly on sphere
>for (int n=0; n<maxPoints; n++)
>{
>    do
>    {
>        points[n].x = frnd(2)-1;   // frnd(float max) generates random
>number between 0 and max
>        points[n].y = frnd(2)-1;
>        points[n].z = frnd(2)-1;
>    }
>    while (sq(points[n].x)+sq(points[n].y)+sq(points[n].z)>1)
>}
>
>for (int i=0; i<maxIterations; i++) // Iterate this bit a few times
>{
>    for (int n=0; n<maxPoints; n++)
>    {
>        for (int m=n+1; m<maxPoints; m++) // for each pair of points...
>        {
>            // make them repulse each other, without a restriction that they
>stay on the sphere
>
>dd=sq(points[n].x-points[m].x)+sq(points[n].y-points[m].y)+sq(points[n].z-po
>ints[m].z);
>            points[n].x += (points[n].x-points[m].x)*repulseCoeff/dd;
>            points[n].y += (points[n].y-points[m].y)*repulseCoeff/dd;
>            points[n].z += (points[n].z-points[m].z)*repulseCoeff/dd;
>            points[m].x -= (points[n].x-points[m].x)*repulseCoeff/dd;
>            points[m].y -= (points[n].y-points[m].y)*repulseCoeff/dd;
>            points[m].z -= (points[n].z-points[m].z)*repulseCoeff/dd;
>        }
>    }
>
>    for (int n=0; n<maxPoints; n++) // for each point
>    {
>        // stick it back onto the sphere
>        dd = sqrt(sq(points[n].x)+sq(points[n].y)+sq(points[n].z));
>        points[n].x/=dd;
>        points[n].y/=dd;
>        points[n].z/=dd;
>    }
>}
>
>-Chris
>
>
>  
>
There is a bug, using "malloc" and never freeing the allocated memory = 
memory leak.

Post a reply to this message