Wednesday, February 21, 2007

Global Grid: The Icosahedral Hexagonal Grid

I've been working with high resolution earth images for almost a decade now in various forms. In the late '90s I flew down to visit Tom Van Sant who is creator of the GeoSphere Project and the first person, to my knowlege, to have created a high resolution satellite composite of the entire earth without cloud cover. Early versions of EarthBrowser used the GeoSphere base map and was used in several museum kiosks around the world as part of the GeoSphere project. Since then EarthBrowser has moved on to higher resolution datasets, but the basic limitations that were present then remain.

The need to represent a sphere with a series of rectangles has offended my aesthetic senses for a long time. It seems simple enough, images are two dimensional and the surface of an ellipsoid is also two dimensional. The basic problem is that a planar representation of an ellipsoid requires distortion, generally around the poles. This isn't a huge problem since you can re-project the image to eliminate this distortion. The problem for me is that there is an unacceptable amount of waste. More data bins (pixels) have to be created via a resampling stretch near the poles only to be resampled down again when used. Yuck!

I've been obsessing about this for the past year and came up with what I thought was an elegant solution, and later discovered that others had been there before (of course!). The basic idea is that the plane can be tiled by only three of the fundamental polygons: the equilateral triangle, the square and the hexagon.

The basis of the EarthBrowser version 3 dataset will be the dodecahedron. From the dodecahedron you can surround each of the 12 pentagons with hexagons to generate a soccer ball-like solid (sometimes refered to as a bucky-ball). Higher and higher numbers of hexagons can be filled in between the 12 pentagons to give you a set of seamless spherical hexagons, plus the original 12 pentagons. This allows you to cover the globe at varying resolutions.

This solution is a very elegant one and is already beginning to be used in several areas like climate and ocean modeling. Getting away from the rectangular grid creates some real complexity issues with indexing, dataset management and data projection. However the benefits of minimizing cell to cell distortion often outweigh the extra complexity for certain uses.

For global earth viewers like EarthBrowser, Google Earth and World Wind, I'm not sure the extra complexity would normally be worth the savings in data size. The data tiles have to be in special map projections and are hard to edit and manage. However in EarthBrowser v3 I have created some tools and techniques within EarthBrowser that compliment it's hexagonal grid in such a way as to eliminate many of the problems and turn several negatives into positives. I'll save discussion of those components for future posts. Having a this global grid technology makes EarthBrowser very flexible for future enhancements that I hope will include the ability to perform data modeling on global datasets.

But best of all it satisfies my aesthetic sensibilities.


om said...

Bucky would be overjoyed to see your pretty pictures.

Peter said...

I posed the same question on the Google Earth Community forums:

I'd be interested to see a network link provcide the grid.

cjohnson said...

Also see
and download to use a hexagonal discrete global grid browser.

marko said...

When applying for any sort of advance with terrible credit, banks will acknowledge that corners can be turned. In this way, any sign that the financial assessment has been enhanced is warmly invited. cash advance