converting KML to 3D, part 2

As you remember we access the longitude and latitude values using a recursion loop. The third value in spliced string found in coordinates tag is altitude which is counted in meters and doesn’t need to be calculated in any specific way. For extruded polygon we will find latitude, longitude and altitude in KML file. The thing worth noticing here is fact that the coordinates tag doesn’t possess basis vertices of the polygon (longitude, latitude, 0) so we have to make a copy of them so that they stick to the ground somehow. For storing the polygons we will use dynamic array which will store arrays of vertices, that way we will have easy access to every single vertex (which can be useful in future for UV mapping for instance). Ok, to revise, at the moment we have a POLYGONS array which has a number of elements equal to coordinates tag found in KML file. Each POLYGONS element is array of vertices that build up the polygon found.
As you might notice we do all the measurements from local pivot (first vertex of polygon is its local pivot). If we find another coordinates tag, we do all the calculations again from 0,0 point. So if we put into KML dozen of polygons we will end up with polygons but placed one on another. To avoid that, we need to set a WORLD PIVOT and store the POLYGON vector translations from it. WORLD PIVOT will be the first local pivot ever found (which is first vertex ever found). The translations will be stored in POLYGON TRANSLATIONS array and their indices will be corresponding to the ones found in POLYGONS array. Calculations for these translation vectors are easy. We store the latitude, longitude pair of WORLD PIVOT and if the algorithm finds another polygon (coordinates tag), it will subtract its local pivot (first vertex) from WORLD PIVOT and store it in POLYGONS TRANSLATIONS array as a Number3D object. That way we store the data in much more customizable manner (model and its world position are independent objects).
The next thing is giving a volume for polygons (they are flat at the moment). We search the POLYGONS arrays and check if vertices have z value greater than 0. If so, it means that they are extruded. If not we leave them like that (can be used for streets for instance). The whole process for extruded polygons would be copying the vertices which changed “z” value to 0 and adding it to that POLYGON item. In other words, the extruded polygons vertices arrays length should be doubled and filled with modified copies of existing vertices. Now if we done that are ready to create faces for 3D meshes? Not yet, we have to scale the all vertices so that they will be more usable later. The default WORLD SCALE for x,y is 100,000,000 and it is different from the WORLD SCALE for z which is 10. This is of course because they are calculated differently: x,y are calculated from latitude and longitude while z is just the altitude parameter set in Google Earth. We scale by multiplying all vertex values by WORLD SCALE parameter that can be found inside KML class.
3D Face is a triangle made of three vertices. Faces comprise for a Mesh structure (triangulated 3D model) and actually make it visible on screen. By default only one side of face is visible, that gives better performance. If you look at Papervision3D structure you will see that to create mesh we need two things. First of them is a vertices package that will be used in that 3D model, in other words an array of vertices. The second one is the array of faces for that mesh. We already have the first ingredient, which are the items of POLYGONS array. The second one needs to be developed. Then we have to project a loop that will be going through all polygons found in POLYGONS array and create mesh objects for each of them and store them into MESH array.
To achieve faces array from vertices array we need to loop again, through all vertices this time, group them in thirds and push new face on the fly to temporary faces array, then use both arrays (vertices and faces) and create new mesh. The problem here is that we cannot take vertices just like that to create faces. It is connected with polygon triangulation algorithms which include advanced math. Let’s revise quickly our situation here. First of all we don’t need to implement advanced 3D triangulation algorithms like Delaunay triangulation algorithm because we are dealing here with 2D polygons or objects which always will be extruded polygons. The polygon triangulation algorithm would be really nice here, but let us limit at the moment to convex polygons, and I tell you why. Primarily we can write a simple triangulation algorithm without involving advanced calculations. Secondly, keep in mind that PV3D supports Collada models which we would like to use as well later for more complex models, so I suggest spending time somewhere else with coding and write just a triangulation for convex polygons. The native Collada class in PV3D for instance doesn’t need the triangulation algorithm because the models are already triangulated when exported from 3D modeling application. The vertices that we have in POLYGON array are sorted in a poly line (same sequence that we put in Google Earth). Taking that fact under consideration, the algorithm goes as follows:

1. Set index to 1.
2. Take the first vertex of polygon and mark it as main (vertices [0]).
3. Take vertices from array, “vertices [index]” and “vertices [index +1]”.
4. Create a 3D Face object from these three vertices.
5. Push the face to temporary array.
6. If vertices [index +1] is equal to main vertex, break the loop.
7. If not increment index and go to step 2.
8. Create a Mesh 3D object using vertices array and temporary faces array.
9. Store the Mesh in MESH array.
10. Take another polygon (vertices array) if found and go to step 1.

That way we have triangulated the roof of the cubic model into Mesh 3D model, if calculated polygon has some height or simple polygon if not. One thing more that we have to do here is to create faces for side walls of our models in a simple loop using copied vertices. Another thing to remember is to fetch vertices in clockwise order while creating faces, in order to be able to see them later (if you still can’t see them, try fetching them in other direction). After all these steps we should end up with MESH array and POLYGONS TRANSLATIONS array, both available from within KML class, ready to connect with Flex application and PaperVision 3D. Here are the most important parts of KML class body (more detailed information can be found in KML class Documentation provided).
Properties:
• KML_FILE : XML - *.kml files are nothing more than a specific XML files. This structure holds its structure inside KML class so that we can process it using E4X.
• POLYGONS : Array – each of its elements is another array consisting of vertex3D objects, parsed from KML_FILE structure and coordinates tag.
• MESH_TRANSLAITON : Array - preserves the translation of each mesh, calculated using local pivot and world pivot. Its order (array index) is equal to index in POLYGONS array.
• WORLD_PIVOT : Number3D – First vertex ever parsed is considered as the 0,0,0 point in world created. All the mesh translation values are calculated from that main point. Its values are latitude, longitude of first vertex and z = 0. There is also a Vertex3D version available.
• MESH_ARRAY : Array – Final array of Mesh3D objects created from POLYGONS array and temporary faces array.

Methods:

Kml(filename:String) – class constructor. Sets the KML_FILE object and starts the whole process of world creation.

calculateTranslation(world:Vertex3D, local:Vertex3D):Vertex3D – calculates the distance between given local pivot and world pivot. Returns a Vertex3D object as a result. The results are stored in MESH_TRANSLATION array.

gnomonicProjection(lambda:Number, fi:Number, z:Number, localPivot:Number3D, scaleXY:Number, scaleZ:Number):Vertex3D – method calculates the given longitude (lambda), latitude (fi) into a Cartesian x,y coordinates using the algorithm and equations described earlier. Additionally it scales the results automatically (put “1” for orginal values). Returns a Vertex3D object that can be used straight in 3D applications.

triangulatePolygonVertices(vertices:Array):Array – triangulates given array of vertices using gnomonic projection algorithm described before. Returns a faces array based on those vertices so that they can be used to create a Mesh. Used in createMeshes method.

createMeshes():void – takes the POLYGONS array and using latter triangulation method fills the MESH array with new objects, ready to use in PV3D.

Now that we have a class to represent the data, we can actually start creating an application which will be the home for our KML pet. Let’s go then.