clh@tacitus.tfic.bc.ca (Chris Hermansen) (02/17/90)
Last week, Mike Goodchild was in Vancouver at Simon Fraser University and gave a talk at one of Tom Poiker's evening sessions on "Tesselating the Sphere". This is quite a long way from my daily grind, but the subject material was fascinating. Basically, he spoke of performing an inital tesselation with an octahedron, then further subdividing the triangular faces of the octahedron with triangles. His encoding scheme therfore required three bits for the first subdivision and two bits for each subdivision thereafter. Mike mentioned someone else's name as having done the seminal work on this topic; unfortunately, I can't remember what it was. At any rate, there were many interesting things about this tesselation. First of all, it didn't require some sort of projection of the sphere (eg as mappers do), and the tessera numbering scheme presented fit nicely into a binary digital encoding. In particular, a 32 bit numbering (leaving one bit unused, by my calculation, and 14 subdivisions of the initial octahedron) obtains a pretty decent resolution on the surface of the earth (less than a kilometer, by my calculations). This type of representation is obviously of (at least academic) interest to those of us who deal with digital maps and GISs; are there any readers of this group with more info to contribute? Chris Hermansen Timberline Forest Inventory Consultants Voice: 1 604 733 0731 302 - 958 West 8th Avenue FAX: 1 604 733 0634 Vancouver B.C. CANADA uunet!ubc-cs!van-bc!tacitus!clh V5Z 1E5 clh@tfic.bc.ca -or- Chris_Hermansen@mtsg.ubc.ca May you work in an interesting place.
mpogue@dg.dg.com (Mike Pogue) (02/20/90)
In article <155@tacitus.tfic.bc.ca> clh@tfic.bc.ca (Chris Hermansen) writes: > Tessellating the sphere discussion.... It so happens that I am working on this right now (in my copious spare time). The geometry is well-known, and has been used by good ole Bucky Fuller for quite a few years. The method you suggest is basically correct. Take an octahedron, and subdivide into triangles. Project each intersection point out to a sphere (or spheroid, ellipsoid, or other superquadric). Convert back to Cartesian coordinates, and voila! You can also start with an icosahedron, and you get a better approximation, but structurally it acts quite different (I'm interested from the geodesic dome point of view). I have ray traced a 4-frequency octahedron, which looks quite nice....The code to generate is quite simple (I'm writing a paper on it right now for publication). Icosahedron is a bit more complex, having a more complicated arrangement of sides. Mike Pogue I speak for myself, not my company....
uselton@orville.nas.nasa.gov (Samuel P. Uselton) (02/21/90)
On Friday, Feb 16, Gyorgy Fekete of NASA Goddard, presented a paper at the SPIE/SPSE Electronic Imaging Workshop in Santa Clara. Unfortunately, the proceedings won't appear for a couple of months, so all I have is the abstract. He described a system in use at Goddard which started with an icosahedral initial decomposition, followed by a subdivision similar to the one in the referenced article: if more detail is needed, a triangle is divided into four, in the obvious way (split the edges at midpoints and connect). The title of the paper is "Sphere Quadtrees: A new Data Structure to Support the Visualization of Spherically Distributed Data". It is from the session "Extracting Meaning From Complex Data" (Vol 1259 for ordering purposes). He used a quadtree (obviously :-) ) and I don't remember a discussion of bit counts, but it could clearly be done that way. He probably has references in the paper and might send a preprint if you are in a hurry.
robert@victoria.esd.sgi.com (Robert Skinner) (02/23/90)
In article <271@dg.dg.com>, mpogue@dg.dg.com (Mike Pogue) writes: > In article <155@tacitus.tfic.bc.ca> clh@tfic.bc.ca (Chris Hermansen) writes: > > Tessellating the sphere discussion.... There is an article that talks about these things in the most recent issue of IEEE Computer Graphics and Applications: "Visualizing Functions Over a Sphere", by Foley, Lane, and Nielson. Jan, 1990. About the only differences are that they do the triangle tesselation on the unit sphere, after projection. That ensures that the triangles are closer to the same size. They also point out that recursively tesselating each triangle into four results in an exponential explosion of triangles: 4**k, starting w/ a tetrahedron (4), and doing k subdivisions. They found that 1000-8000 triangles were sufficiently dense for sampling their functions, but for k=5 you get 1024, k=6 yields 4096, and k=7 gives 16K triangles. In contrast, you can divide the tetrahedral triangles into k segments along each edge, then you get 4*k**2 triangles total. This grows much more slowly than the previous method. Robert Skinner robert@sgi.com Which is worse, ignorance or apathy? Who knows? Who cares?
bdiscoe@tybalt.caltech.edu (Ben W. Discoe) (02/24/90)
mpogue@dg.dg.com (Mike Pogue) writes: > It so happens that I am working on this right now (in my copious spare time). >The geometry is well-known, and has been used by good ole Bucky Fuller for >quite a few years. I have searched Bucky's books for any sign of REAL mathematics or useable formulas and remain empty-handed. The method of raising polyhedra to higher frequencies is not at all well-known, in fact I have access to extensive geometry/computer sciece media and have not found ANY instances of theory/code anywhere. I finally stumbled across a formula for distance along a geodesic between any two points, but still have no formula for the arc itself (necessary for adding the intermediary points -> frequency). If ANYONE on the net knows of such formula/algorithms I would be MOST grateful... >You can also start with an icosahedron, and you get a better approximation, but >structurally it acts quite different (I'm interested from the geodesic dome >point of view). I am also interested in the dome point of view... I asked for help in this group some months back and received no solid answers. Apparently we geodesic-types are few and far between in a cubical world. > I have ray traced a 4-frequency octahedron, which looks quite nice... > Icosahedron >is a bit more complex, having a more complicated arrangement of sides. Is it correct that a unit-edge-length tetrahedron's radius is slightly less than one? I think if it were 1.0 then it would be a "vector equilibrium." Sounds like you have running code - are you free to distribute it? >Mike Pogue >I speak for myself, not my company.... -Ben Discoe "Every 3 months we throw away enough aluminum to rebuild our commercial airfleet."
moran@p.cs.uiuc.edu (02/25/90)
A few months ago, I was looking for a way to generate a set of points which would be perfectly distributed on the face of a unit sphere. (Perfectly distributed meaning that all the solid angles between each point and its neighbors would be equal). The quantity needed to be in the range 1000 to about 4000. I came up with an idea similar to that described previously, starting with a tetrahedron, subdividing each face into four triangles, then normalizing all the new vertices so they are on the sphere. It was only after implementing this that I learned about Platonic solids and the fact that there is no perfect distribution for such a number of points. Anyhow, I have C code which takes one argument n and outputs 4**n points in spherical coordinates using the algorithm above. Interally, the program represents each face as the three cartesian points in three space. This isn't a very memory efficient to do it, but it makes for a simpler program. If anyone wants a copy, send me e-mail. Pat Moran University of Illinois at Urbana-Champaign moran@cs.uiuc.edu
rick@hanauma.stanford.edu (Richard Ottolini) (02/26/90)
In article <77100013@p.cs.uiuc.edu> moran@p.cs.uiuc.edu writes: > >A few months ago, I was looking for a way to generate a set of points >which would be perfectly distributed on the face of a unit sphere. Some mathematician proved that was impossible, but you can get very close. If you subtriangulate the triangles of a polyhedron most vertices will have six edges except some of those of the original polyhedron. A collegue of mine, chuck@hanauma.stanford.edu, propagated seismic waves on a spherical mesh derived from a subtriangulated icosahedron. The asymmetries of the original twelve vertices still caused numerical artifacts in the wave equation even when triangulated to 160K triangles. He significatly attenuated artifacts by equalizing triangular areas as a least squares problem even though the resulting movement of the vertices was miniscule.
mpogue@dg.dg.com (Mike Pogue) (02/27/90)
At this point, I am not free to distribute the code (I'm still working on the article), however, as soon as I can, I will post it (if there is interest). As several people who sent me personal replies mentioned, the code is relatively simple. Once you see what is going on, it's pretty simple to see how the code does it. The trick is to start thinking in geodesic geometry. The geodesic dome was extensively studied by Bucky Fuller, and he has patents on several major geodesic techniques (e.g. the "diamond" pattern you may have seen. Hard to describe, but suffice it to say that it is distinctive, and increases the strength of a dome by using the "skin" to create two "virtual skins", an inner and an outer skin.). My code avoids the easy way (generating coordinates directly from the plane equations), and goes through geodesic coordinates and then spherical coordinates first. In this way, you can easily apply the correction factors to make: a) a dome that uses the minimum number of different strut lengths b) a dome which is more densely tesselated near the sides, for greater strength c) ellipsoid and super-ellipsoid domes, for greater "headroom". I apologize for not answering mail directly, but my mailer is definitely broken, so I seem to be able to receive mail, but I can't reply. FOr those of you interested in domes, try "The DomeBook" and "DomeBook II". I don't know if these are still in print, and I don't remember the authors either. Mike Pogue Spekaing for myself, not my company.,...
gyuri@cvl.umd.edu (Dr. Gyorgy Fekete) (02/27/90)
I gave a paper on February 16th at the SPSE/SPIE Symposium on Electronic Imaging Science and Technology titled "Sphere quadtrees: a data structure to support the visualization of spherically distributed data". It discusses the quadtree based management of spherical data with an introduction of some algorithms for topological operations on trixels (small spherical triangles). I would be happy to send a hardcopy of the paper as it appears in the proceedings to anyone who asks. Unfortunately, the paper is rather short (there was a 12 page limit), and is not a full discussion of all the things that we have done, but there is enough there to motivate further discussion. Another paper is in the making. I will also e-mail the extended abstract (circa 300 words) to those who ask. Please e-mail to "gyuri@ncgl.gsfc.nasa.gov" or US-mail to (in case .signature falls off the end) Gyorgy Fekete NSSDC/Goddard Space Flight Center Code 634 Greenbelt, MD 20771
koziol@yoyodyne.ncsa.uiuc.edu (03/02/90)
I have been playing around with various 3-D objects and have come upon, probably not for the first time, the fact that a dodecahedron might be the best polyhedron to perform simulations on. Dodecahedrons seem to lend themselves to this because they have six-sided faces which can be broken down into six equilateral triangles, which themselves can be broken down with the quad-trees approach. The benefit of this is that all the intersections have six connections. This would seem to eliminate the artifacts generated on tetrahedron and octahedron surfaces. Quincey Koziol koziol@ncsa.uiuc.edu
tuna@athena.mit.edu (Kirk 'UhOh' Johnson) (03/03/90)
In article <18000002@yoyodyne> koziol@yoyodyne.ncsa.uiuc.edu writes:
--------------------
I have been playing around with various 3-D objects and have
come upon, probably not for the first time, the fact that a
dodecahedron might be the best polyhedron to perform simulations
on. Dodecahedrons seem to lend themselves to this because they
have six-sided faces which can be broken down into six
equilateral triangles, which themselves can be broken down with
the quad-trees approach.
--------------------
uh, if these are the same dodecahedrons i'm familiar with, i think you
might be mistaken. a dodecahedron has 12 _five-sided_ faces (as
opposed to the claimed _six-sided_ faces).
oh well. perhaps they are still useful.
--
-------------------------------------------------------------------------------
kirk johnson `Eat blue dogs
tuna@masala.lcs.mit.edu and dig life.'davidp@dbrmelb.dbrhi.oz (David Paterson) (03/05/90)
> I have been playing around with various 3-D objects and have come upon, > probably not for the first time, the fact that a dodecahedron might be the > best polyhedron to perform simulations on. Dodecahedrons seem to lend > themselves to this because they have six-sided faces which can be broken down > into six equilateral triangles, Ugh! Regular dodecahedrons have five-sided faces. Rhombic dodecahedrons have four-sided faces. > which themselves can be broken down with the > quad-trees approach. The benefit of this is that all the intersections have > six connections. This would seem to eliminate the artifacts generated on > tetrahedron and octahedron surfaces. You can never surface a sphere with triangles in such a way that all intersections have six connections. The best you can do (when you have more than 30 triangles) is to surface a sphere in such a way that all intersections have either n or m connections. Max(n,m) is greater than or equal to 6. Min(n,m) is less than 6. So you can have n=5,m=6 or n=5,m=7 or n=3,m=6 or n=3,m=12 etc. For instance. Start with a tetrahedron. Then cut each triangle up into 4,6,9,16,25 etc. triangles gives n=3,m=6. Or start with an icosahedron and cut each triangle up into 4,6,9,16,25 etc. triangles gives n=5,m=6. Or start with a dodecahedron, cut each face into 5 triangles and cut each triangle up into 4,6,9,16,25 etc. triangles also gives n=5,m=6. Solutions with n=5,m=6 have triangles that are most nearly equilateral but are harder to program than, say, cutting up the faces of an octahedron to get n=4,m=6. ----------------------------------------------------------------------------- David Paterson, CSIRO Division of Building, Construction and Engineering, Highett, Victoria, 3190, AUSTRALIA davidp@dbrmelb.dbrhi