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.

Tuesday, February 20, 2007

More on GPU processing

Things are moving rapidly in the Graphics Processing Unit (GPU) programming arena. NVIDIA just released CUDA a GPU compiler that will allow applications to offload work to the GPU. Most GPUs run about 10 times faster than their host CPU and are ideal for running uniform mathematical operations on large sets of data.

NVIDIA is adding a nice compiler that does the hard work of translating your math into GPU assembly code. All you have to do is provide the source code of the program, compile it and upload the program and data to the graphics processor and get the results. ATI is apparently going with a much more barebones approach and allowing you to program the GPU in assembly code directly. That is more flexible, but requires someone else to develop and support the toolset. I like NVIDIA's solution better, but I don't think that they allow you direct access to assembly so it is a little less flexible.

GPU programming is going to become a big deal in scientific computing in the next few years.