 |
|
|
|
|
|
| |
| |
|
|
|
|
| |
| |
|
|
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
|
|
| |
| |
|
|
|
|
| |
| |
|
|
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] fozzie chemwiscedu> 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
|
|
| |
| |
|
|
|
|
| |
| |
|
|
In article <40957445@news.povray.org>,
"Ilia Guzei" <igu### [at] fozziechemwiscedu> wrote:
> While testing, a polyhedron with 8 vertices was inevitably a square prizm
> rather than a cube...
It's not a prism either, but something called a "square antiprism":
http://mathworld.wolfram.com/SphericalCode.html
http://mathworld.wolfram.com/SquareAntiprism.html
--
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
|
|
| |
| |
|
|
|
|
| |
