converting KML to 3D, part 1

the pdf version can be found here

Ok, so let’s put everything together into a workflow. We are setting out to create a fast way of creating real 3D worlds in Flex that can be playable within browser with Flash Player installed. We found Google Earth application as the most suitable form of providing data for our system. We want the user to be able to create a city - preserving real world coordinates, distances and building sizes in the fastest possible way. As we speculated before on the data - using Google Earth gives users ability to create polygons (using real world satellite image as a drawing layer) for any, I say any city found on the Google Earth surface. It can be part of New York City as well as clay houses in Bamako in Mali. So in fact it doesn’t matter if user wants to create a small village or University Campus of big city, it will take him the same amount of time (to be more specific it can be less than 10minutes!!!, it only depends on precision that user wants to achieve). Then after the polygons (and additional data such as height of buildings, placemarks, etc. – see KML reference in Technology chapter) are created we save them into KML file. This is the fastest and most intuitive way for normal user I found to create user customizable world data. KML is also commonly used as well among web society for showing users positions on the world for instance (Google Maps). What is more the polygon coordinates are not the only information that can be stored inside KML file, so we have more options to discover and make investigation on later. So how we are going to view the data from a KML file into a browser playable swf file? First of all to start, we will need something like a KML class that will serve as file parser and provide us with math to calculate the world positions from Google earth. That class will need to be implemented in ActionScript so that we can use it within Flex application that will produce that swf file. If we connect those two, then we can attach PV3D engine to the application and try to view the data. At that point we should have a 3D displayable KML data using swf file. Next we can create navigational system based on First Person Perspective camera (or like Windows Live Maps - Birds eye) and attach more options from KML files and other techs (like support for Collada files or using Web Services for instance) to the whole system. Ok, so let’s set sail into some ActionScript coding.

Before writing some code let’s consider a structure that we would like to have and that would be most universal for further functionality/extensions. The KML file structure as described earlier holds a tag coordinates, which is the most interesting data for us at the moment. Finding and getting a coordinates tag should not be a problem using E4X API in ActionScript 3.0. However we must take under consideration that users will draw more than one polygon for sure to achieve like a city representation. So what we are really interested in is getting all the polygon tags from the given KML file. So let’s have a look how exactly the coordinates tags are buried in the XML structure when more than one polygon is being saved.

see pdf ver.

That kind of structure can be repeated of course (multiple folders), and is marked with closing tags. There can be different numbers of placemarks inside each folder as well. We are at the moment not considering the children other than coordinates tag. However we want to have ability to add code later for manipulating data on other tags in an easy way (placemark->name tag for instance which can serve us as a name for mesh3D object). I think that the best way to construct the behavior like digging the whole structure and taking just those tags that are interesting for us, would be using a recursive loop. We would call the method like proccesNode for children of each child encountered on the way, analyze it and if we find that it fits one of the tags showed on the outline above then call the proccesNode method for the children of that child (recursion) until we dig to the desired coordinates tag. In that approach we won’t omit any coordinates tag and in addition we can easily add code for finding another tag. Now if the tag is found we take the coordinates data which is represented as String and slice it using blank space as a token. After that we have an array of Strings where each of them is a triple consisting of “longitude, latitude, height”. So again we slice it, now using “,” token and we have a point data to make calculations on it. Here is the outline algorithm of proccesNode method that in full size can be found in Kml.as source file.

function processNode(children:XMLList) {

1. Loop for all children.
2. Get child tag name.
3. if tag name equals coordinates or other that has data – calculate the data;
4. if tag name is parent tag which can possess the tag with data - execute the recursion by fetching the children of that child to processNode method;

We can easily add further pieces of code by placing another “case” statement for specific tag. So now if we have data of any given point (longitude and latitude), how to convert it to a local coordinates? To points like (120,34,10) for instance. The longitude and latitude values in coordinates tag are expressed by degrees. So for instance here you have the two points which are creating edge of the building drawn onto Google Earth raster layer. Points are represented in (DD,MM) format degrees.

-122.1079075592149, 37.40374393714917, 28
-122.1084678195176, 37.40306635543301, 28

As you probably noticed the differences between those points are counted approximately in values like 0.0001. So for instance let’s consider one polygon case, flat in addition (only x,y). We would set the first point encountered as a world pivot and set it to 0,0,0 (storing however his longitude and latitude values as let’s say real pivot) then from each next point that we find we would subtract the real pivot longitude, latitude values which will give us the translation vector values for that point. If we repeat that process for all points we will end up with array of points with values like 0,002345. Then we can multiply it by a specified scale value and here it is. We got the points translated into more readable coordinate system. Ok but let’s verify the actual results by drawing the both figures onto map. Let’s place the figure that we achieve from square placed in Berlin to area near equator (subtract without multiplication). The results can be seen on the images at the bottom.

see pdf ver.
Fig.1 : Square polygon drawn in the city of Berlin.

see pdf ver.
Fig.2 : The same polygon moved to equator area (0,0 – longitude, latitude). Subtraction used.

Now we didn’t expect that to happen, did we? This is called the distortion problem of world projection and is strictly connected with creating maps in old Cartesian way. If we want to handle that problem we have to look for the same ways that 2D maps are created. The way presented above with distortions is also used in some cases in cartography because of the simplicity of calculus. In other hand distortions on maps are something that will always be there, we can only diminish its influence, we will never be able to fully avoid them. So have that in mind as well.
So how actually the maps are created? What at first glance looks as a simple question after a while can turn into a more specific question “how the hell that can be done?”. Maps in the past times were “simple” to draw because people assumed that the world is flat. And it would be so much easier for our project if the fact that the world is a spheroid was never discovered.
We are interested in moving the chosen part of spheroid world to plane Cartesian local map. What we need is a conversion which is called a map projection system. The traditional maps are much more compact, they are also better for city calculations, better and easier to view on paper or computer screen. All that led to development of many advanced ways of calculating the real world to Cartesian plane. There are numerous map projection systems, and their usage depends on what we want to achieve, what district we want to make map for, what distortions we are able to accept. Those are questions that we need to answer. The most popular types are cylindrical map projections, which is as you probably expect a projection of a sphere onto cylinder (like turning on the bulb inside the sphere which is inside cylinder). While this projection can be found in many maps available, it is strongly advised not to use it because of the large distortions, especially with high latitudes. The equator areas are the ones where the distortions are minimal while the north and south poles areas cover even up to nine times larger fields than in reality. There are several types of cylindrical projections. The most famous is called a Mercator projection. It was discovered in 1569 by Flemish cartographer Gerardus Mercator and became the standard map projection for nautical purposes, especially because of its ability to represent line with constant bearing (better known us rhumb lines) as straight line segments, which is commonly used to steer the ship in sea navigation (the full name of the first Mercator map was “New augmented description of Earth corrected for the use of navigation”, and was precisely for navy purposes). It means that if you draw a straight line on the map which is Mercator projection, that line would fit the loxodrome (rhumb line) in the real world, which can be easily set as a sailing direction using compass. In that projection the meridians and parallels are straight and perpendicular to each other, creating a grid which represents the world. Farer we go from the equator, the greater the distortions are. Normally above the 70 degree of latitude the distortions cause the data to be practically unusable. In addition we will never be able to view properly North and South Poles with that projection for instance – since the projection goes to infinity in that case. It was adopted fully in 18th century. Mercator however was not the only one that contributing into that type of map projection, behind the stage there were few other mathematicians that made it possible. Here you have the mathematic equations for the projection.
The Cartesian pair x and y is given by these equations. Where λ is a longitude of a given point, θ is latitude and λ_0 is the longitude of central point on the map.

see pdf ver.

Mercator projection assumes that the equator is tangent to the surrounding cylinder. This is an old fashion way to translate world into two dimensions. How about the projections that are used these days for creating maps? What is the modern approach on that issue?
As I said before there is a whole bunch of map projections that can be used, it mostly depends on the circumstances that we are in. However among them there is one considered to be a standard. If we have a projection now that can be considered as a standard, countries can easily merge areas in-between and standardize cooperation on international level (air traffic for instance). The projection that I’m talking here about, I’m sure you’ve heard it somewhere, is UTM which stands for Universal Transverse Mercator and as you probably figured it out it is an extended version of Mercator described previously. If you can imagine the simple Mercator, what would you change to make it more suitable for your specific purposes? For instance, if making map of the Leningrad area, the most suitable for you would be to move it exactly to equator area (minimal distortions). You can achieve that by moving the tangent circle to be not the equator but the meridian of your choice. That map projection onto cylinder with switchable tangent meridian is called Transverse Mercator. When using this kind of projection you will get a narrow area along the meridian of your choice with minimal distortions. That solution is much better in reality because although it diminishes the area that can be projected (North/South Poles are projected very well if using meridian, but some of the areas corresponding to normal poles position are not), it actually gives you choice which part of the world you can translate into Cartesian coordinates with minimal distortions (not only the equator areas). It’s really useful while projecting maps for countries like Chile. Distances like 5 degrees from meridian are giving 0.4% larger scale, for 10 degrees the value is 1.54%. This method based on Mercator of course, was first presented in 1772 by Johann Heinrich Lambert (with the spherical basis) and later by Carl Friedrich Gauss in 1822 using ellipsoid as a basis. Ok, now that you know what a Transverse Mercator is, let’s go further with it so that you see in outline how UTM (Universal Transverse Mercator) was founded. So hundreds of years passed again and the more sophisticated navigation systems for measuring distances needed to be invented, especially for military purposes. In 1947 United States Army develop UTM which is a type of grid based projection which means that it is a bunch of individual projections packed into one graphic representation. The UTM is separated into 60 individual parts (cylindrical projections) each encapsulating areas from latitude 84 degrees North to 80 degrees South and each of them 6 degrees wide (longitude). These zones are numbered from one to sixty. First is bounded by longitude 180-174 and centered on 177th West meridian. Zone numbers increase to east. As you probably expect each of these stripes is individual Transverse Mercator Projection, which used only in 6 degrees wide area gives us very little distortions and what is more they are diminished much more by taking the scale factor in the central meridian to 0.9996 so that the distortions are really minimal in the whole area. Notation of that system is based on the zone number and latitude letter. While the zone number is an easy guess, the latitude letter is a letter given from English alphabet. Each letter corresponds to area 8 degrees high starting from North Pole. Letters O, I are omitted because of the similarity to 0,1 values and the last X is extended by 4 degrees. The nice trick to remember is that N stands for first area of south hemisphere. A position referenced in the UTM system is as follows: UTM longitude zone, easting/northing coordinate pair. The easting is the distance from zone meridian while northing is distance from equator. To avoid dealing with negative numbers, easting for each zone is valued 500.000 meters on the centre, decrements to the west and increments to the east. The northing is valued 0 on the equator and increases to the north till 9,328,000 meters on the 84th parallel. As you go south form equator the northings decrease starting from 10,000,000. That way none of the points will have negative values and we have the way of translating the longitude and latitude to Cartesian map that we need. Let’s now have a look at the equations:

see pdf ver.

Where x, y is a pair of Cartesian coordinates after conversion, θ is latitude and λ is longitude. Now how to implement the UTM system to our solution? We would have to calculate it using the equations then use some parsing for getting the correct zones – but let me say something. If you look a bit deeper it’s too much, maybe not complicated but advanced and still possess some distortions if we consider distances like 2 feet long. So after all maybe using UTM would not be such a good solution for us, as it is mainly for representing large scale maps with minimal distortions. In our solution we want to get a representation of cities, university campuses, etc, in other words not the whole world or areas of country size. It would be good to stick with UTM standard, but as for now, with limitations that we are given with 3D in browser we should satisfy and focus ourselves with cities and therefore some other more specific projection type. However UTM can be implemented and used to represent world in 3D for purposes like route 3D map on airlines website. It would only consist of simple plane (UTM country or world map) and some boxes (airports) plus aircraft collada model for example, all visualized in a very fancy manner. So what I suggest is this time to use some projection that is based on a local area rather than on meridians, equators etc. I didn’t have to look far to find it, because such a projection is probably one of the oldest existing map projections and it’s reasonably simple as well. Let me introduce you to the gnomic projection.
Gnomon is an ancient Greek word meaning “indicator”. That name was given to the part of sun-dial that casts the shadow. Now try to correlate it with map projections, use your creativity and you get an idea what gnomonic projection is. Thales used his imagination and founded this oldest known map projection in 6th century BC. Ok, imagine the plane tangent to the sphere in only one point. The map is obtained by projecting the points laying on the sphere surface from the sphere centre onto the plane surface. As you can see on the picture below the projection can be used only for one hemisphere at once (if not - antipodal points would lay one on another). The tangent point can be set wherever we want it to be, which is exactly what we were looking for. Imagine now for instance that we are going to set it as a first point ever found in KML file. That way, distortions would be almost none in our local area (city size map). The specific thing about gnomonic projection is that it always will show great circles as straight lines, and because of that ability it is commonly used in fields like seismology or military (seismic waves and radio signals tend to travel along great circles). The projected map has huge distortions if you would look at its full hemisphere view. It is exactly like looking through spherical lens. However if you want it to project a map for country size region (not Russia or US of course) you can go for it. Just place the tangent point in the center and you will have a pretty realistic projection. And as you remember, we are mainly interested in city size maps, so in other words we will have huge space reserves for our local city and really minimal distortions in addition. It would be perfect for us with its simplicity as well. Here is some math for gnomonic projection:

see pdf ver.

Where x, y corresponds to Cartesian coordinates after conversion; θ, λ is latitude and longitude of given point; θ_0, λ_0 are latitude and longitude of central point; c is an angular distance between actually measured point and the central point of projection, its value is given by equation:

see pdf ver.

There are again variety of modifications with that plane projection (plane intersecting the sphere, gnomon point in infinity), but we really don’t need to make things more complex, that one is more than enough for our calculations and if you check the shapes that you get from that projection you won’t see a difference.

by Marcin Czech