Sphere Tessellation by Icosahedron Subdivision
Gernot Hoffmann
Google Search shows hundreds of contributions, mostly smalltalk.
Exception: Dave Eberly´s documents.
I had expected: the subdivision results for high subdivision levels
in equal-sided triangles on the sphere.
Original Icosahedron: Level 0, 20 triangles
First subdivision Level 1 80 triangles
Second subdivision Level 2 320 triangles, and so on
Practical result:
Level 0: three angles 60°
Level 1: 60°, 56°, 69°
Level 2: 8 angles from 54° to 71°
This means: it cannot be expected, that a higher subdivision level
results in equal-sided triangles (60°), though this is expected
because the sphere surface is then nearly flat. A flat surface can
be tessellated by symmetric triangles/hexagons.
Where is the mistake ?
http://www.fho-emden.de/~hoffmann/ikos27042002.pdf (600kBytes)
Gernot Hoffmann
Gernot Hoffmann
Mark VandeWettering
> Sphere Tessellation by Icosahedron Subdivision:
>
> Google Search shows hundreds of contributions, mostly smalltalk.
> Exception: Dave Eberly´s documents.
>
> I had expected: the subdivision results for high subdivision levels
> in equal-sided triangles on the sphere.
> Original Icosahedron: Level 0, 20 triangles
> First subdivision Level 1 80 triangles
> Second subdivision Level 2 320 triangles, and so on
Your expectations were not correct.
> Practical result:
>
> Level 0: three angles 60°
> Level 1: 60°, 56°, 69°
> Level 2: 8 angles from 54° to 71°
>
> This means: it cannot be expected, that a higher subdivision level
> results in equal-sided triangles (60°), though this is expected
> because the sphere surface is then nearly flat. A flat surface can
> be tessellated by symmetric triangles/hexagons.
>
> Where is the mistake ?
It seems fairly obvious with a moment's inspection.
When you begin with an icosahedron, each of the vertices of the
equilateral triangles lies on the sphere. If you just subdivided
these triangles in the obvious way, then each resulting triangle
would be equilateral as well. But you don't, you subdivide and
then project the vertices out to the sphere. This distorts the
triangle, the center triangle becomes an equilateral triangle, but
the ones surrounding it aren't. This only gets worse with recursion.
There are only 20 facets ever that are true equilateral triangles,
the rest are twisted and distorted in various ways.
> http://www.fho-emden.de/~hoffmann/ikos27042002.pdf (600kBytes)
Pretty diagrams. I see that your question was also apparently
rhetorical.
Mark
> Gernot Hoffmann
--
main(){char*p="vandewettering.net";printf("\33[?38h\33\14\35\35(z)O\"oO!kHa(F "
"yFy,D!aDj+D\"j*](q])q+Dz,D*bDb)J\"\177&G*b\"_b F)zFq!I(qQ\"{Q!mIa E yEy#O!aOn"
"\"M\"{D(pD y%%Uy\\(z)O\35*b6Ib3M)zMt4GgN(fE#a2C'y/_(|P)kMy0AzN*bNb,W)zWq-P(k."
"F t1Ut\\(p5@)rRz6I*bI\35+w!@\37mark@%s\35*~@\37http://%s\33\3",p,p);}
Dave Eberly
news:a815dbcf.02050...@posting.google.com...
> This means: it cannot be expected, that a higher subdivision level
> results in equal-sided triangles (60°), though this is expected
> because the sphere surface is then nearly flat. A flat surface can
> be tessellated by symmetric triangles/hexagons.
As Mark VandeWettering already pointed out, your document
indicates that you are aware you cannot get equal-sided
triangles on subdivision of an icosahedron. This is just a
consequence of the fact that there are only five Platonic solids,
and subdivided icosahedra are Platonic.
A couple of notes on your posted document.
1. You have a subdivision scheme that avoids the recursion, but
maintains two triangle lists. You only need one list. Given a
manifold triangle mesh with V0 vertices, E0 edges, and T0 triangles,
a subdivision by adding midpoints to edges (and projecting to
sphere), then replacing one triangle by four triangles leads to new
counts V1 = V0 + E0, E1 = 2*E0 + 3*T0, T1 = 4*T0. Given the
desired number of subdivision steps, you can compute how many
vertices, edges, and triangles you will have in the final mesh.
Initially, allocate the maximum quantity of vertices as an array of
3-tuples and triangles as an array of triples of indices into the
vertex array. For the edges you maintain a map whose keys are
pairs of vertex indices (edge representation) and whose values are
used to store the indices of the vertex midpoints. With these data
structures it is easy to subdivide. Iterate over current edges. For
each edge, append a vertex to the current vertices in the array.
Store the index in the map value for that edge. Now iterate over
current triangles. One of the four triangles in a subdivision of a
triangle has its indices overwrite those of the original triangle. The
other three triples are appended to the end of the triangle array.
How you invalidate the edges from the previous subdivision to
start the next subdivision is a matter of choice (tag as invalid or
clear the map and reinitialize).
2. You ask a rhetorical question about if it is worth it to use a
subdivided icosahedron instead of spherical coordinates. That really
depends on the application, do you not think? I use subdivided
icosahedra for initializing surfaces that are evolved to "shrink
wrap" the brain matter in 3D magnetic resonance images. The
evolution scheme has problems using spherical coordinates. The
distribution of the triangles in the subdivided icosahedron lead to
much better results. The reason has to do with controlling the
smoothness and stiffness of the mesh. The high density of triangles
at the poles cause the surface to be so stiff near the poles that the
polar regions cannot evolve properly to shrink wrap the brain.
--
Dave Eberly
ebe...@magic-software.com
http://www.magic-software.com
http://www.wild-magic.com
Dave Eberly
news:OU1B8.24$Mb6....@newsread2.prod.itd.earthlink.net...
> and subdivided icosahedra are Platonic.
Of course this should say "are not Platonic". (Wish my
server would allow canceling a post...)
HP
Optimal solutions of placing points on a sphere retaining icosahedral
symmetry are available at N.J.A. Sloanes "Tables of Spherical Codes
with Icosahedral Symmetry":
http://www.research.att.com/~njas/icosahedral.codes/index.html
I have used triangle grids on the sphere created with Renka's STRIPACK
(ACM algorithm 772) for the visualization of my sphere illumination
results:
http://www.enginemonitoring.org/illum/illum.html#visualize
The disadvantage of using Sloane's configurations might be that you
have to use the stored coordinates. However Sloane provides a highly
efficient compressed format exploiting the icosahedral symmetry. See:
"Downloading the Files in Compressed Format"
http://www.research.att.com/~njas/icosahedral.codes/index.html#ALT
In my opinion it would be very hard to beat the quality of triangular
meshes created from Sloane's arrangements of points by any other
method.
Hugo Pfoertner
Gernot Hoffmann
....
Mark,
thanks for the feedback.
my question was rhetorical about the actual subdivision.
It was not rhetorical about better alternatives.
One of the following posts seems to offer better solutions.
It should be possible to achieve nearly balanced hexagons/
triangles for a very large number of triangles, as on a plane.
Best regards --Gernot Hoffmann
Gernot Hoffmann
> A couple of notes on your posted document.
>
> 1. You have a subdivision scheme that avoids the recursion, but
> maintains two triangle lists. You only need one list.
> 2. You ask a rhetorical question about if it is worth it to use a
> subdivided icosahedron instead of spherical coordinates. That really
> depends on the application, do you not think?
Dave, thanks for the feedback.
1. You are right, two triangle lists are not necessary.
It愀 just a fast and safe solution. In fact each of the lists
is highly redundant, because a vertex list and a triangle list
would do the job. It愀 merely a tutorial program, and I have
enough memory.
I had also tried to apply a true recursion - here I failed.
In fact, for a fixed number of a few subdivisions a true recursion
is not recommended.
2. Yes, I can see some useful applications - especially the mapping
of isolated patterns to triangles or groups of triangels.
But I am surprised, that the icosahedron sphere rendering is not much
more economical than with sphere coordinates.
Best regards --Gernot Hoffmann
Gernot Hoffmann
> I have used triangle grids on the sphere created with Renka's STRIPACK
> (ACM algorithm 772) for the visualization of my sphere illumination
> results:
> http://www.enginemonitoring.org/illum/illum.html#visualize
>
> The disadvantage of using Sloane's configurations might be that you
> have to use the stored coordinates. However Sloane provides a highly
> efficient compressed format exploiting the icosahedral symmetry. See:
> "Downloading the Files in Compressed Format"
> http://www.research.att.com/~njas/icosahedral.codes/index.html#ALT
>
> In my opinion it would be very hard to beat the quality of triangular
> meshes created from Sloane's arrangements of points by any other
> method.
>
> Hugo Pfoertner
Hugo, thanks for the feedback.
Of course I had expected that here and there someone had found better
solutions than my classical approach - that was the reason for posting.
In the short time I was not able to see whether the mentioned subdivi-
sions are based on an algorithm or manual optimization.
It seems, that another problem was solved: subdivision for numbers
which are not multiples of 20.
Best regards --Gernot Hoffmann
HP
Gernot,
AFAIK Neil Sloane and his colleages have run numerical optimization
programs for a very long time, at least for the general arrangement
problems on the sphere.
I have now created pictures of some optimal arrangements at
http://www.enginemonitoring.org/sphere/icoscov.pdf (156kB)
The coordinates and the triangle list for the covering with 5072
points are also available:
http://www.enginemonitoring.org/sphere/net5072.zip (88kB)
The coordinates are stored in the file cov5072 as follows (Unix lines)
x1
y1
z1
x2
y2
z2
....
The format of the mesh connectivity file 5072.tri should be obvious.
If there is interest I could also make available the data for other
arrangements.
Hugo
Gernot Hoffmann
>
> AFAIK Neil Sloane and his colleages have run numerical optimization
> programs for a very long time, at least for the general arrangement
> problems on the sphere.
> I have now created pictures of some optimal arrangements at
> http://www.enginemonitoring.org/sphere/icoscov.pdf (156kB)
> The coordinates and the triangle list for the covering with 5072
> points are also available:
> http://www.enginemonitoring.org/sphere/net5072.zip (88kB)
> The coordinates are stored in the file cov5072 as follows (Unix lines)
>
> Hugo
Hugo,
thanks for the illustrations. They look good.
But did you observe the discontinuities in the distribution of
the patterns on the equator, about 0.8*R to the left and to the
right ?
Parameter optimization is a good idea - for those who have a Cray.
But perhaps I will try this for domes with not so many facets,
with arbitrary numbers.
Thanks for the offer of vertex lists.
In fact I am more interested in methods, actually I don´t have
a practical application for a final solution.
Best regards --Gernot Hoffmann
HP
> thanks for the illustrations. They look good.
> But did you observe the discontinuities in the distribution of
> the patterns on the equator, about 0.8*R to the left and to the
> right ?
>
> Parameter optimization is a good idea - for those who have a Cray.
> But perhaps I will try this for domes with not so many facets,
> with arbitrary numbers.
>
> Thanks for the offer of vertex lists.
> In fact I am more interested in methods, actually I don´t have
> a practical application for a final solution.
>
> Best regards --Gernot Hoffmann
Gernot,
the discontinuities in the mesh are a consequence of the required
icosahedral symmetry. There are exactly 12 vertices where 5 edges
meet, all other vertices have 6 meeting edges. Of course it is not
possible to construct a covering with triangles that has only vertices
with degree 6. The mesh topology of the sphere on page 9 of your pdf
file (the texture mapping example) is exactly the same as the one on
page 4 of my illustrations. The general formula for a poyhedron with N
vertices bounded by triangles is
sum_k (6-d_k) = 12 (k=1..N), with d_k=Number of edges meeting at
vertex k. There is no trick to avoid the degree 5 vertices. The only
thing you can do is trying to smooth the surrounding mesh. Sloane's
solution is probably the optimal compromise.
BTW I worked on Crays for many years, but we have now the same
computing power on a PC we had on mainframes 10 years ago. Finding
provable _global_ optima for arrangement problems with more than a few
points still exceed our available resources. However solutions with
"engineering" accuracy can be found with reasonable effort.
Hugo
Mark VandeWettering
> Hugo,
> thanks for the illustrations. They look good.
> But did you observe the discontinuities in the distribution of
> the patterns on the equator, about 0.8*R to the left and to the
> right ?
If you mean the fact that there are some places were five triangles meet
at a vertex and some place where six do, that too is hardly surprising,
particularly if you are trying to have triangles which are nearly equilateral.
If six equilateral triangles met everywhere, they would form a plane.
Another way to think about it: the icosahedron has 20 faces and
12 vertices. 5 faces meet at each of the 12 vertices. When you
recursively subdivide, you create new vertices which are adjacent
to six faces, but the original vertices don't move and retain their
adjacency to five faces.
Mark
Gernot Hoffmann
>
> If you mean the fact that there are some places were five triangles meet
> at a vertex and some place where six do, that too is hardly surprising,
> particularly if you are trying to have triangles which are nearly equilateral.
> If six equilateral triangles met everywhere, they would form a plane.
>
> Another way to think about it: the icosahedron has 20 faces and
> 12 vertices. 5 faces meet at each of the 12 vertices. When you
> recursively subdivide, you create new vertices which are adjacent
> to six faces, but the original vertices don't move and retain their
> adjacency to five faces.
>
> Mark
Mark,
you are right, talking about the Icosahedron subdivision.
But your argumentation is not convincing for Hugo´s numerically
optimized sphere tesselation, because this is not necessarily based
on the parent Icosahedron.
So it has to be proved: a polyhedron (let´s say normal, convex ... ,
similar to a sphere, no gaps etc.) cannot be tessellated by hexagons
only.
Euler´s Polyhedron Formula:
V - E + F = 2 Assumed, this is correct.
V = Vertex number
E = Edge number
F = Face number
n = Corners per face number
r = Edges per vertex number
n*F = 2*E each edge belongs to two faces
r*V = 2*E each edge belongs to two vertices
2*E/r - E + 2*E/n = 2
2/r + 2/n = 1 + 2/E
1/r + 1/n = 1/2 +1/E
Now let´s assume r=6 edges per vertex and n=3 corners
per face - which would result in hexagons.
1/6 + 1/3 = 1/2 + 1/E
1/E = 0
Infinite number of edges - not possible on a polyhedron.
This proof follows Courant/Robbins, "What is Mathematics".
But Courant proved the non-existence of REGULAR polyhedrons beyond
the five PLATO polyhedrons. IMO, the regularity is not an essential
paradigm of the proof.
Conclusion: it´s not possible to tessellate a sphere by hexagons.
Any correction is appreciated.
Best regards -- Gernot Hoffmann
Kenneth Sloan
>
> Another way to think about it: the icosahedron has 20 faces and
> 12 vertices. 5 faces meet at each of the 12 vertices. When you
> recursively subdivide, you create new vertices which are adjacent
> to six faces, but the original vertices don't move and retain their
> adjacency to five faces.
>
> Mark
How extraordinary!
--
Kenneth Sloan sl...@uab.edu
Computer and Information Sciences (205) 934-2213
University of Alabama at Birmingham FAX (205) 934-5473
Birmingham, AL 35294-1170 http://www.cis.uab.edu/info/faculty/sloan/
Mark VandeWettering
> wett...@attbi.com (Mark VandeWettering) writes:
>
>>
>> Another way to think about it: the icosahedron has 20 faces and
>> 12 vertices. 5 faces meet at each of the 12 vertices. When you
>> recursively subdivide, you create new vertices which are adjacent
>> to six faces, but the original vertices don't move and retain their
>> adjacency to five faces.
>>
>> Mark
>
> How extraordinary!
Allright, allright, I'll desist from posting more. I must admit
to wasting too much time here already, I was merely confused as to
why Gernot apparently understands enough to see this and yet continues
to ask questions as if it weren't clear. Hugo's postings were more
rigourous and informative, so I'll defer to his excellent postings
on the subject.
HP
>
> 1/E = 0
>
> Infinite number of edges - not possible on a polyhedron.
>
> This proof follows Courant/Robbins, "What is Mathematics".
> But Courant proved the non-existence of REGULAR polyhedrons beyond
> the five PLATO polyhedrons. IMO, the regularity is not an essential
> paradigm of the proof.
>
>
> Any correction is appreciated.
>
> Best regards -- Gernot Hoffmann
Gernot,
this is a consequence of the famous Descartes theorem (sum of angular
deficiencies of a polyhedron = 720 Degrees). See e.g.
"Descartes's Lost Theorem":
http://www.ams.org/new-in-math/cover/descartes1.html
or one of the many pages on Fuller's work:
http://www.angelfire.com/mt/marksomers/88.html
Hugo