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.

Thanks,
Ilia

Post a reply to this message

If you can cope with a number close to 60000, start with an octahedron (or
possibly an icosahedron), then subdivide each triangle into four (by drawing
a new triangle with its vertices the midpoints of the edges of the original
triangle), then rescale the position of these midpoints onto the sphere
surface. This subdivision is then repeated.

If you need exactly 60,000 points, there are ways that I can see of doing
it, but they're not very nice.

-Chris

Post a reply to this message

> 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.

if you can live with other numbers around 60,000 (whos going to count
them anyway?!) then see this
   http://astronomy.swin.edu.au/~pbourke/modelling/sphere/

-- 
Paul Bourke
pdb_NOSPAMswin.edu.au

Post a reply to this message

I have done that, but the distribution is not even as the four triangles
resulting from division of each original one are not equilateral.  The final
distribution is somewhat skewed with higher "point density" about the
original vertices.

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.

The exact number of points does not matter as long as it is large enough.


Best regards,
Ilia

"Chris Johnson" <chris(at)chris-j(dot)co(dot)uk> wrote in message
news:40946490$1@news.povray.org...
> If you can cope with a number close to 60000, start with an octahedron (or
> possibly an icosahedron), then subdivide each triangle into four (by
drawing
> a new triangle with its vertices the midpoints of the edges of the
original
> triangle), then rescale the position of these midpoints onto the sphere
> surface. This subdivision is then repeated.
>
> If you need exactly 60,000 points, there are ways that I can see of doing
> it, but they're not very nice.
>
> -Chris
>
>

Post a reply to this message

Ilia Guzei wrote:

> I have done that, but the distribution is not even as
> the four triangles resulting from division of each
> original one are not equilateral.  The final distrib-
> ution is somewhat skewed with higher "point density"
> about the original vertices.

This will not be the case if you start with an icosahedron

> The exact number of points does not matter as long as
> it is large enough. 

60k is simple to generate exactly. I don't have the vocabulary to explain
how, but I can generate this array in a few minutes and email it to you if
you would like.

Let me know.

 -Shay

Post a reply to this message

Paul Bourke 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.
> 
> 
> if you can live with other numbers around 60,000 (whos going to count
> them anyway?!) then see this
>    http://astronomy.swin.edu.au/~pbourke/modelling/sphere/
> 

Very interesting, thank you for the link.

Sebastian H.

Post a reply to this message

Sebastian H. wrote:
> Paul Bourke 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.
>>
>>
>>
>> if you can live with other numbers around 60,000 (whos going to count
>> them anyway?!) then see this
>>    http://astronomy.swin.edu.au/~pbourke/modelling/sphere/
>>
> 
> Very interesting, thank you for the link.
> 

http://astronomy.swin.edu.au/~pbourke
Wow I think I'll spend some time on your site!

Regards,
Sebastian H.

Post a reply to this message

The polar method isn't going to help here in its current form if the
subdivision method generates a distribution that is too uneven: as you say,
the polar method generates very small triangles at the poles. It could
perhaps be modified to generate fewer triangles at each "line of latitude"
closer to the poles, but this might be tricky.

-Chris

Post a reply to this message

-[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

>
> > I have done that, but the distribution is not even as
> > the four triangles resulting from division of each
> > original one are not equilateral.  The final distrib-
> > ution is somewhat skewed with higher "point density"
> > about the original vertices.
>
> This will not be the case if you start with an icosahedron
>

Unfortunately, it is the case.  Just to prove it, take a look at a triangle
with the following apical positions A=1 0 0 , B=0 1 0, C=0 0 1.
Let's divide sides AB and AC in half and normalize the resulting points.
AB/2 = D = {cos(45), cos(45), 0}  and  AC/2 = E = {cos(45), 0, cos(45)}.
The resulting triangle  ADC  is not equiltateral :
AD = AE = sqrt (pow(1-cos(45),2)+pow(cos(45),2)) = 0.76
DE = sqrt(0+ 1/2 + 1/2) = 1.

It's the same story with icosahedron.



> > The exact number of points does not matter as long as
> > it is large enough.
>
> 60k is simple to generate exactly. I don't have the vocabulary to explain
> how, but I can generate this array in a few minutes and email it to you if
> you would like.

If you could send me your algorithm I would most certainly appreciate it.  I
want to be able to generate any number of points to model the sphere, I am
not sure what number will satisfy my task but the more the better.

Ilia

Post a reply to this message