Wednesday, December 31, 2008

2008: a long year

It's that time of year again, where we celebrate the significance of digit roll-over on a completely artificial counter for time - the New Year.

This year has (will) be a long one (BBC: New Year to arrive a tick later), and as is the custom I thought I betters have at least one resolution for the New Year:

  • Start doing more AI - this blog was meant to have more of this, but I seem to have spent most of the year learning technologies (Silverlight and OpenStreetMap - both fun of course!).
So next year I will have to dig out a good book on the subject (Artificial Intelligence in Geography)


And try and combine all three!

Thursday, December 18, 2008

OpenStreetMap rendering in Silverlight part XI

I had a look to see what was causing the serial drawing nature of the map, and it does appear to being caused by going via the Dispatcher. Silverlight supports multithreading, but any code that want to do UI work must do it in the main thread.

   // get the tile data
   quadrant = GetTileData();
   // we are creating UI elements, go via dispatcher
   map.Dispatcher.BeginInvoke(delegate()
   {
    Canvas canvas = new Canvas();

    Tile tile = new Tile(quadrant, canvas);

    // create instance of renderer
    ITileRenderer tileDrawer = RenderFactory.CreateRenderer(tile);

    // render the tile
    tileDrawer.Render();

    // tell the requester that the tile available to add to UI
    tileLoaded(quadrant.Path, tile);
   });
This means multithreading is great if you have complex calculations going in, and just need to update a simple UI. However for code where the complex work is the UI then you end up hitting a bottleneck. In the code for drawing London I am creating 24 tiles which in total contain about 60k poly-line/gons. I am effectively forced to create them in a serial fashion (my code is non-serial, but each tile has to wait for the last tile to stop using the Dispatcher).

On my PC it took about 30seconds to draw the map of London (once you have run it once all the data should be cached). I've made some changes to speed this up, so it now runs in 15 seconds. I updated the Silverlight Map demo to use this version (you may have to delete the XAP file from your cache to get the newer version)

For the production version I will not be trying to draw the whole of London like this, but it does suggest that progressive rendering will be needed to make the application more responsive. (Progressive as in only draw large items on the tile for the first pass, and then add detail in the subsequent background passes)

I'm not sure if this UI blocking issue will be a problem for other developers (most complex UIs are made using bitmap based tile operations so in this case they would only have 24 UI elements vs. my 60k) and for other non UI intensive applications the current threading model is fine. However it would be nice if this large block could be removed - for example only require the Dispatcher when the tile is added to a visible UI element...

Wednesday, December 17, 2008

OpenStreetMap rendering in Silverlight part X

Last few days were spent refactoring some of the design and data models. This has yielded some pretty impressive gains. Based on the UK data the following optimizations have been gained:

  • Original OSM data: 1.3gb
  • Import data into QuadStore: 367mb
  • QuadStore as binary: 97mb
  • QuadStore as compressed binary: 48mb
Yep that's right the whole of the OSM data for the UK has been compressed from 1.3gb into 48mb, or in other words its less than 5% of the original size. And the majority of this gain has delivered a geographically clustered data set, so it's fast as well.

I've also updated the map to cache data (it caches the compressed binary) into IsolatedStorage, though the default of 1mb is not enough for a mapping application, so it now requests the user to increase it to 10mb upfront. The nice thing about using the compressed binary is that we can cache twice us much as well!

To show the effect of all these optimizations I've changed the demo to show the whole of London (alá EastEnders)  on the fly:


The main bottle neck I have now is the requirement to go via the Dispatcher for drawing UI elements, this causes the "one at a time" display of tiles. I think I can get round this, but I will have to investigate further (it may just be my own code causing this!)

Given that the code is drawing a very detailed map of the whole of London it's very fast, however for a production version I would create lower resolution tiles first and replace them with higher resolutions in the background.

Friday, December 12, 2008

OpenStreetMap rendering in Silverlight part IX

From talking to people at the last London OSM meet it appears that large ways are not a good idea for performance reasons (the OSM database and editors). For example the River Thames is split into a number of ways, rather than being one big one.

Since I can cope with large ways, and there are performance gains and presentation gains from combining them I did a test applying two techniques.

The first was to "promote" low level tile feature that are deemed interesting at the time of OSM import. So for example I promoted all coastlines from level 12 to level 4, and major rivers from 12 to 9. The promotion level was gut feel.

I then applied the road junction method to coastline features. Then I applied this to the whole of the UK:


This reduced the draw data from 9k to 4k, with a smoother coastline. I applied the road junction method on the fly, however this would make more sense at the point of import for coastlines. This is because when drawing the map I want to know about the individuals roads, whilst for the coastline, rivers etc the split was artificial in the first place.

In the picture there are some lines outside the country which are mostly ferry routes, and the line of detail down the south-east of England is a tile border (there is also one horizontally in Scotland buts it's not so obvious). At this level of zoom the code needs to filter out such small features.

Wednesday, December 10, 2008

London is 80k polygons

Well I'll be, and I thought it was a city, instead its 80k polygons (actually its more than that, but some were optimized out)

Click to zoom:


[warning 500kb image!]

OpenStreetMap rendering in Silverlight part VIII

One of the issues that my current renderer has is that it's not as smooth as the raster versions used in the slippy map. One of the worst offenders was road junctions, where two roads meet. They looked something like this:


In the image you can see where the two roads meet there is a gap. This is due to my code drawing the two roads as separate polylines. I create a test renderer to see if this could be improved:


This version has joined the two roads together, drawing only one polyline for both of them. This results in a smooth join, and also a reduction in the number of objects. For example joining roads where they share a start and end point reduces the number of objects for south-west London from ~40k to ~30k. So not only does it create nicer looking maps, it makes them less memory intensive.

It occurs to me that this technique could be used for any Xaml consisting of multiple lines, as my findings suggest that Silverlight performs faster (one poly line with a 1,000 segments is faster than 1,000 single line segments)

My join algorithm is brute forced within a tile (creating an O(n2) complexity) which won't do for release code. So I will write a smarter version - hopefully of the order of O(3n).

I also spotted that a lot of ways within OSM are artificially split (the river Thames for example) I don't know if this is a feature of data collection or policy. My QuadStore design can cope with large entities like the river Thames quite easily - so applying this same technique at a higher level may generate smooth maps overall.

Tuesday, December 9, 2008

OpenStreetMap rendering in Silverlight part VII

I've been refactoring the application to tidy up handling of geography calculations and especially tile positioning, (drawing is now done using a visitor pattern). I've not released a new verison as it currently a step backwards (I've not yet worked out who should be reponsible for zoom and rotation, so I've left it out)

As a test of tile positioning I tried to render London at a high detail level, I used some simple colours (blue=water, green=leisure or natural, black for everything else). I manually selected the tiles, but the code places them correctly - what's nice about the picture is that it shows the high level of detail that is available due to everyone's contributions to OSM, (click to see detail)



see the previous zoom/rotation version of the Silverlight OpenStreetMap

Thursday, December 4, 2008

OpenStreetMap rendering in Silverlight part VI

I've spent some time looking at performance, using some of the tricks from Seema's blog - she also very helpfully sent me some helpful tips when trying to build applications with many complex shapes.

Changes to the version now include:
  • Speed/Memory improvement using feature clipping.
  • Tooltips tags for features, (mouse over a line or area to see)


The neeed for speed: performance investigation
This is where the ability to swap drawers has been helpful, I was able to create try out new ideas without having to worry about breaking the existing drawing system. One of the technique's I investigated was drawing using Silverlight's mini-language, this allows you to draw complex shapes using a LOGO like definition:

<Canvas>
<Path Stroke="Black" Fill="Gray"Data="M 10,100 C 10,300 300,-200 300,100" />
</Canvas>

Since I need to draw this dynamically I need to load the Path.Data from a string:

StringBuilder sb = new StringBuilder();
sb.Append("<Path xmlns=\"http://schemas.microsoft.com/winfx/2006/xaml/presentation\"");
sb.Append(" xmlns:x=\"http://schemas.microsoft.com/winfx/2006/xaml\"");
sb.Append(" Data=\"");
sb.Append("");

ShowWay(sb, tileBorder);
foreach (var gpp in quadrant.GeoPolyPoints)
DrawFeature(sb, gpp);

sb.Append("\"/>");

GeometryGroup gg = new GeometryGroup();
Path uiPath = (Path)System.Windows.Markup.XamlReader.Load(sb.ToString());

using a helper function to turn a set of points into a set of draw instructions:

private void DrawFeature(StringBuilder sb, GeoPolyPoint gpp)
  {

   bool isFirst = true;
   foreach (GeoPoint geoPoint in gpp.GeoPoints)
   {
    int y = geoPoint.GetScaledX(viewport);
    int x = geoPoint.GetScaledY(viewport);

    if (isFirst)
    {
     isFirst = false;
     sb.Append(" M ");
    }
    else
     sb.Append("L ");

    sb.Append(x);
    sb.Append(',');
    sb.Append(y);
   }
   if (gpp.PolyConstruct == PolyConstruct.Polygon)
    sb.Append("Z ");

   return count;
  }

I then timed this against my previous attempt, and found hardly any difference - and I also tried create PathFigures, Geometries etc - these were painfully slow (mainly due to the need to create lots of LineSegment objects). So I am sticking with creating Shapes (Polygon and Polyline) as both of these take a collection of points, so no need to create lots of lines.

I then had a look at Seema's blog again and had a play with
<param name="enableRedrawRegions" value="true" />

This showed that I was updating a vast region of the screen, this seems to be related to clipping not behaving as expected - I've asked Seema for some clarification on this. However I also knew my draw routine was pretty lazy - it did not check when drawing a feature if it would even be visible on the tile (for example to the left of the tile).

I was relying on Silverlight clipping to do all the work. So I put in a simple check to only draw features that actually appear in the tile. This reduced the New Malden draw set from 26,038 features to 7,979. This means my code is drawing 3 times less shapes - a massive memory and speed improvement (10% faster), but more importantly ~20,000 shapes that Silverlight does not have to calculate, rotate, clip for no visible effect.

Once I get an answer from Seema on the clipping issue things should get even quicker!

Wednesday, December 3, 2008

IIS7, creating new websites and HTTP 401

I've had this problem a few times now, and whilst it's user error it's not obvious.

When you create a new website in IIS7 and application pool with Anonymous Authentication enabled, and configure the application pool with a user that has permission to read the web site directory you *could* assume that it will work. And then you browse the site and get blank pages back, a bit later you look in the log and see lots of 401 returns.

The cause? Open Internet Information Services (IIS) Manager, and click on the website, then under the "IIS" section double-click on Authentication, then click on the "Anonymous Authentication" item and select "Edit.." (right click or menu on right hand side). Change the "Anonymous user identity:" to being "Application pool identity".

Problem hopefully solved...

Silverlight and cross-domain issues especially with SOAP

I keep having issues with this - mainly due to the examples on the internet and various blogs giving the wrong information. If you want to call a web-service then the root of the website must have a crossdomain.xml that contains:

<!DOCTYPE cross-domain-policy SYSTEM "http://www.macromedia.com/xml/dtds/cross-domain-policy.dtd">
<cross-domain-policy>
<allow-http-request-headers-from domain="*" headers="*"/>
</cross-domain-policy>


Note that lots of the examples have the wrong element name for the "allow..." bit.

Tuesday, December 2, 2008

OpenStreetMap rendering in Silverlight part V

Have released the first version of the map, its limited to just new malden and is still using a simple drawing plug-in.

You can play with it by clicking on the picture:

Its a very simple update from what I've been working with, but I spent most of the day fighting DNS, FTP, Visual Studio and my own stupidity ;-( However it now shows/does a number of things:
  • parallel downloading of tiles (still not predictively, but since you can see only new malden that's not going to hurt!). Tiles fade in for effect
  • fixed colour coding for tiles (red, green, blue and magenta for TR, TL, BL, BR tiles) and then colours the tiles according to size (small to large - orange, cyan, purple, brown and dark gray for everything else). This allows you to see how a tile is a mixture of data from different levels.
  • I extended the drawing to shade areas as its easier to work with the map (the non-shaded version was easy to get lost in)
  • drag and move: you can drag the map around
  • zoom: mouse wheel - you can zoom the map in and out
  • rotate: mouse wheen+ctrl - you can rotate the map (this is too slow at the moment I need to look at why, also there is some odd clipping going on if you turn clockwise)

Its all debug code, and we probably won't ever show tiles at this size and detail (i.e there's too much detail at this level of zoom). However there is certainly work to be done on improving the general speed of drawing...

Monday, December 1, 2008

OpenStreetMap rendering in Silverlight part IV

A critical part of be able to show the maps is putting tiles together, today the code base solved a number of problems:
  • downloading data asynchronously (though not yet predicatively, or in parallel)
  • reduced data set transmission sizes (from 367mb to 97mb for the UK) - no compression yet.
  • clipping of drawing to fit within tiles, (applying higher level data to tiles does not draw outside the tile) though this does not yet crop the drawing effort (performance to be gained here)
  • multi-tile support, the code can handle multiple tiles independently (though does not yet know how to stitch properly yet).
All of this yields a nice improvement in speed and appearance, hopefully I can post a live version tomorrow.


The colours above are used to show which level the data existed at (per tile, cross tile etc) so you can see how the image is made of four tiles, with large entities (i.e. across tiles) being in different colours.