Saturday, February 18, 2012

Bing Maps and HTML5 (Part 4 - Final optimization)


In Part 3 of this "Bing Maps and HTML5" series I optimized the drawing of the Canvas quite a bit. The time taken to draw the canvas with 140.000 points was cut from 800ms to 75ms.

Anyway, and as I said previously, my target was (and is) the 40ms mark (1000/25) for a full canvas render with all the points. Why? Because I want the data to be continuously drawn while the map is zoomed/panned, and it has to be fluid.
After profiling my code, the bottleneck is still the function where wgs84 coordinates are converted to pixel coordinates.

Update 26/07/2012: I've added a working example here. I've also added a zip file with the project here.
I modified the demo so that the data is not fetched from a node.js but from a separate js file instead.



Let's check the code:
function latLongToPixelXY(latitude, longitude, mapWidth) {

    var sinLatitude = Math.sin(latitude * Math.PI / 180);
    var pixelX = ((longitude + 180) / 360) * 256 * Math.pow(2, mapWidth) ;
    var pixelY = (0.5 - Math.log((1 + sinLatitude) / (1 - sinLatitude)) 
                                                   / (4 * Math.PI)) * mapWidth;

    var pixel = new Object();
    
    pixel.x = (0.5 + pixelX) | 0;
    pixel.y = (0.5 + pixelY) | 0;

    return pixel;
}
This function is being called for each coordinate in each frame, so every redundant operation has a lot of weight in the total time.

Optimization #1: Replace the PI operations with precalculated constants

This was suggested in the comments section of my previous post. Simple enough, instead of having Math.PI / 180 and Math.PI * 4, replace it with the corresponding constant values.

It thus becomes:
function latLongToPixelXY(latitude, longitude, mapWidth) {

    var sinLatitude = Math.sin(latitude * pi_180);
    var pixelX = ((longitude + 180) / 360) * 256 * Math.pow(2, mapWidth) ;
    var pixelY = (0.5 - Math.log((1 + sinLatitude) / (1 - sinLatitude)) 
                                                   / (pi_4)) * mapWidth;

    var pixel = new Object();
    
    pixel.x = (0.5 + pixelX) | 0;
    pixel.y = (0.5 + pixelY) | 0;

    return pixel;
}

Optimization #2: Instead of storing the coordinates, store a pixel "factor"

First, lets change the method a little bit so that it's easier to refactor it
function latLongToPixelXY(latitude, longitude, mapWidth) {

    var sinLatitude = Math.sin(latitude * pi_180);

    var pixelYFactor = (0.5 - Math.log((1 + sinLatitude) / (1 - sinLatitude)) 
                                                         / (pi_4));
    var pixelXFactor = ((longitude + 180) / 360);

    var pixelY = pixelYFactor * mapWidth;
    var pixelX = pixelXFactor * mapWidth;

    var pixel = new Object();
    pixel.x = (0.5 + pixelX) | 0;
    pixel.y = (0.5 + pixelY) | 0;

    return pixel;
}

The variable in the process is the zoom level (mapWidth) so, if we store the PixelFactors instead of the coordinates, our method becomes:
function latLongToPixelXY(pixelFactor, mapWidth) {

    var pixelY = pixelFactor.Y * mapWidth;
    var pixelX = pixelFactor.X * mapWidth;

    var pixel = new Object();
    pixel.x = (0.5 + pixelX) | 0;
    pixel.y = (0.5 + pixelY) | 0;

    return }
Well, isn't it nicer? No we just need to do the previous calculations when the points are loaded. The difference is that this operation is only done once for each coordinate.
var socket = io.connect('http://localhost:88');
socket.on('coordinates', function (items) {

    points = items;
    pixelFactors = new Array();

    for (var i = 0; i < points.length; i++) {

        var pixelFactor = new Object();

        var sinLatitude = Math.sin(points[i].lat * pi_180);

        pixelFactor.Y = (0.5 - Math.log((1 + sinLatitude) / (1 - sinLatitude)) 
                                                          / (pi_4));
        pixelFactor.X = ((points[i].lon + 180) / 360);
        pixelFactors.push(pixelFactor);
    }    
    loadCanvas();
});
Let's see if this improved the drawing speed.

Not bad at all. Time to try this baby out.

I've uploaded a video capture that I did directly on my PC to show the drawing being done continuously without interruption. Also, I've modified the algorithm a little bit so that at closer zoom levels the points appear larger. 


Although this concludes this series I've got much more to try out regarding maps and HTML5.

18 comments:

  1. Wow, impressive results! I would never have thought that such amounts of data could be drawn that fast. This certainly opens up new opportunities for visualising my data in pure javascript.

    There's one optimisation to be made in your code: instead of saving the pixelfactors as fractions, you could save the pixel coordinates for the highest zoom level in 32 bits and divide by two (i.e. shift right) for every lower zoom level. The conversion will be as simple as:
    coord.X = factor.X >>> (MAXZOOM - zoom + 1);
    coord.Y = factor.Y >>> (MAXZOOM - zoom + 1);

    Testing in Chrome, this calculation is about ten times faster than multiplying the fraction by the map width. (The initial calculations for the pixel coordinates will be just as slow.)
    Note: I found out the hard way that javascript will convert numbers to 32-bit *signed* integers for bitwise operations, so you have to make sure you're not generating negative pixel coordinates!

    ReplyDelete
  2. HH, that's a pretty brilliant piece of advice. Unfortunately it can't be used in this case. As you can see in the video, the drawing is done for every view change, including between zoom levels. Thus, the zoom level is sometimes a fractional number, therefore I can't use the shift trick to divide by 2.
    I guess I could probably use your method conditionally if the zoom level is an integer, which should be useful for the panning operations...

    ReplyDelete
  3. Ahh, I see. I never realised that fractional zoom levels existed, because I was only experimenting with the Bing Maps "changeviewstart" and "changeviewend" events. I guess you also do a complete redraw on the "changeview" event. On my processor this is not feasible.
    Instead of redrawing I tried to keep the original canvas around and stretch/translate, but then I found out in your Leaflet post that Leaflet does exactly that. From now on I will use Leaflet!

    Anyway, nice series of articles! It inspired me to pick up some old spatial project and experiment with HTML5.

    ReplyDelete
  4. Pedro,

    Great set of posts!

    I am having some problems using the final optimized code in Part 4.
    I was able to load my data using the code in Part 3 - Client code (approx. 172,000 points - American fastfood restaurants over a US Bing map). However, my points although outlined correctly is shifted, so I know there is some mis-communication between the underlying map and the pixel offsets on the canvas.
    I thought first that it had something to do with the longitude (being negative west of the prime meridian- Greenwich, London - so the offset was off, but I don't think that is the problem anymore.

    I am using a SQL server stored procedure via an .ashx handler to load the data from the server, but I have problems with the Client code.

    Do you think you can you post the Complete final Client code you used in your UTube video above?

    I would like to take this example to next level and switch to pushpins with additional tooltip info when the number of points has been sufficiently reduced.

    But I have to get the code to work first.

    Any help would be greatly appreciated.

    Thanks, and keep up the great work you are doing.

    :)

    ReplyDelete
  5. tsorli,

    The full client code is posted on my previous post. Just use that and replace the methods that were optimized on this post.

    ReplyDelete
  6. Pedro,

    thanks for getting back to me so quick.

    I managed to get the code to work up to the final optimization - where you store the Lat-Longs as pixelfactors.

    I am stuck on the drawPoints() function.

    For example - how to use the new LatLongToPixelXY(pixelFactor, mapWidth) to determine the offsetX and offsetY variables.

    var topLeftCorner = LatLongToPixelXY(northwest.latitude, northwest.longitude, map.getZoom());
    var zoomLevel = map.getZoom();

    var offsetX = topLeftCorner.x;
    var offsetY = topLeftCorner.y;


    and in the for loop I am trying the following, but it does seem work.


    for (var i = 0; i < points.length; i++) {

    var loc = points[i];

    //discard coordinates outside the current map view
    if (loc.lat >= minLatitude && loc.lat <= maxLatitude &&
    loc.lon >= minLongitude && loc.lon <= maxLongitude) {

    pointsDrawn++;

    var point = LatLongToPixelXY(pixelFactors[i], map.getZoom());
    // var point = LatLongToPixelXY(loc.lat, loc.lon, map.getZoom());
    var x = pixelFactors[i].x - offsetX;
    var y = pixelFactors[i].y - offsetY;

    setPixel(imageData, x, y, 255, 0, 0, 255);
    }
    }

    Finally, I am new to HTML5 and drawing with the Canvas, so I was wondering, as you zoom in on the map your pixels get larger, are you drawing "surronding" pixels (much like a buffer would be to a point in Geospatial) to the actual latlong pixel, to make it look larger?

    Any feedback would be greatly appreciated.

    Thanks again,

    :)

    ReplyDelete
  7. Hi,

    I don't have the code with me, but I'll gladly send it to you when I get to my home pc.

    Better yet, I'm going to update my post with a link to a zip file with the whole thing.

    Regarding the pixel "enlargement" in closer zoom levels, you're right. I draw larger pixels as the zoom level increases :)

    ReplyDelete
  8. Thanks Pedro, that will be very helpful.

    :)

    ReplyDelete
  9. Tsorli, I found the problem. The optimized "LatLongToPixelXY", the one with the pixel factors, expects a "map width" parameter, and not the zoom level. Thus, it should be:

    var mapWidth = 256 * Math.pow(2, map.getZoom());

    and then:

    var point = LatLongToPixelXY(pixelFactors[i], mapWidth);

    Anyway, I'm working right now on putting a sample online. I couldn't find my old code, but heck, should be similar enough.

    ReplyDelete
  10. Tsorli, I've added both an online sample and a zip with the downloadable code.

    ReplyDelete
  11. Pedro, Fantastic!

    I got the sample up and running using my own data in no time. Really cool. I already started working on the code to switch to pushpis when a small enough number of points (pixels) are shown on the map (i.e. 100).

    Thanks for your help.

    :)

    ReplyDelete
  12. This description and example code has been really useful but I see its specific to javascript 1.4.2.

    I'm guessing the problem in later javascript versions taht Google Maps users are facing is the same here.(see http://stackoverflow.com/questions/15236658/google-maps-fails-when-we-upgrade-our-applications-jquery-library)

    Would there me a modification needed to the code to get it to work under js 1.9.2?

    ReplyDelete
  13. Actually jQuery is just an afterthought on this demo, and I just use it for small things like the counters and such. I'm not sure if newer jQuery versions break some Bing or Google Maps... For this particular demo any version should work, although not sure if requiring some special changes, as 1.4.2 is pretty old.

    ReplyDelete
  14. Very cool Pedro!

    Am i missing something, but if i create a simple asp.net project and insert the source from your html file the asp.net solution is MUCH slower. The draw speed in the asp.net solution is around 1300 ms. There is nothing else added to the asp.net project other than the javascript calls and the html from your source.

    Any ideas?

    ReplyDelete
  15. Get real, html5 streaming on youtube is buggy as hell and on windows xp/7 it drains battery like a lemon.
    html5

    ReplyDelete
  16. Many thanks Pedro for this excellent tutorial, as the other ones !

    But I've found a small error: during horizontal spanning, each point before to disappear completely is displayed partially on the opposite side.

    This behaviour is more visible when the zoom value is increased till the maximum and this is due to the increasing width of each pixel drawn...

    a simple correction is to assign canvas-width = mapWidth + pixelWidth later in the code, just after the calculus of pixelWidth !

    Kind regards and keep those excellent tutorials coming,
    Germain
    http://ADtlas.com

    ReplyDelete
    Replies
    1. Oups, it is canvas.width, not canvas-width :-)

      Delete