In my previous post I've created an example where about 140.000 points are retrieved from a MongoDB database and drawn on top of a Bing Maps using Html5 canvas.
If you recall, it took about 800+ ms to create and display the canvas above the map when all the points were visible. For the current scenario it's acceptable, as the drawing only occurs after the view changed event has ended. The problem is that I would like to have the drawing being continuously drawn during the view changed events. So, and for the motion to be fluid, each canvas image has to be drawn in less than 40 ms(1000/25).
Obviously it depends on the CPU of the client machine. My laptop is pretty average, so it will be a realistic benchmark. I'll post my attempts to achieve the 40ms target on my computer, starting with the current post, where I try to solve the most problematic operation.
First bottleneck : The conversion from geographical coordinates to pixel coordinates
Currently I'm using the function tryLocationToPixel from the Map class of Bing Maps. It works as expected (result wise) but could be probably faster. I'm going to rewrite it.
At the Bing Maps Tile Reference page the following formula is provided to convert geographic coordinates to pixels:
sinLatitude = sin(latitude * pi/180) pixelX = ((longitude + 180) / 360) * 256 * 2^level pixelY = (0.5 – log((1 + sinLatitude)/(1 – sinLatitude))/(4 * pi))* 256*2^levelThe corresponding Javascript function should be something like this:
function LatLongToPixelXY(latitude, longitude, levelOfDetail) {
var sinLatitude = Math.sin(latitude * Math.PI/180);
var pixelX = ((longitude + 180) / 360) * 256 * (2 << (levelOfDetail-1)) ;
var pixelY = (0.5 - Math.log((1 + sinLatitude) / (1 - sinLatitude))
/ (4 * Math.PI)) * 256 * (2 << (levelOfDetail-1));
var pixel = new Object();
pixel.x = (0.5 + pixelX) | 0;
pixel.y = (0.5 + pixelY) | 0;
return pixel;
}
Note: the bitwise shift operator (<<) is used instead of
Math.pow(2, levelOfDetail) because it's much faster. var bounds = map.getBounds();
var northwest = bounds.getNorthwest();
var topLeftCorner = LatLongToPixelXY(
northwest.latitude, northwest.longitude, map.getZoom());
var offsetX = topLeftCorner.x;
var offsetY = topLeftCorner.y;
Then, the correct pixel coordinates is just a simple:
var point = LatLongToPixelXY(
loc.lat, loc.lon, map.getZoom());
var x = point.x - offsetX;
var y = point.y - offsetY;
Let's try the prototype again with this optimization.
Why is it that much faster? Because some of the code (mainly the offset calculation) is only done once. Also, we could probably optimize this even further if we stored the coordinates in Javascript semi-calculated, like storing the "sinLatitude". Also, we could speed up the array iteration if we had two sorted arrays, one for longitudes and one for latitudes. Then, using a binary search, we would find the visible intervals and avoid a visibility check for each coordinate. That would also give the nice side-effect of knowing before-hand how many coordinates we would draw, and conditionally apply different draw strategies... For example, if less than 100 then draw pushpins instead of using Canvas
I'll revisit this prototype later to do some more performance tweaks.
The full source-code for the client is:
<html>
<head>
<meta http-equiv="Content-Type" content="text/html; charset=utf-8"/>
<title>NodeJS + WebSockets (using socket.io)</title>
<style type="text/css">
.map
{
width: 400px;
height: 400px;
position:relative;
}
ul
{
list-style: none;
font-size:10px;
}
</style>
<script type="text/javascript" src="socket.io.js"></script>
<script type="text/javascript" src="jquery-1.4.2.js"></script>
<script type="text/javascript">
var canvas;
var points;
var MM;
var map;
var bingMapsURL =
'http://ecn.dev.virtualearth.net/mapcontrol/mapcontrol.ashx?v=7.0';
$(function () {
addMessage("Loading map...");
var date1 = new Date().getTime();
$.ajax({
url: bingMapsURL,
dataType: 'jsonp',
jsonp: 'onscriptload',
success: function (data) {
MM = Microsoft.Maps;
map = new MM.Map($('#mapDiv')[0], {
credentials: "BING MAPS KEY GOES HERE",
showCopyright: false,
showDashboard: false,
mapTypeId: Microsoft.Maps.MapTypeId.road,
showLogo: false,
showMapTypeSelector: false,
showScalebar: false,
center: new Microsoft.Maps.Location(39.5, -8.5),
zoom: 6
});
var date2 = new Date().getTime();
addMessage("Map Loaded", date2 - date1);
addMessage("Loading Points...");
var socket = io.connect('http://localhost:88');
socket.on('coordinates', function (items) {
points = items;
var date3 = new Date().getTime();
addMessage(points.length + " Points Loaded",
date3 - date2);
loadCanvas();
});
}
});
});
function loadCanvas() {
canvas = document.createElement('canvas');
canvas.id = 'pointscanvas'
canvas.style.position = 'relative';
canvas.height = map.getHeight();
canvas.width = map.getWidth();
var mapDiv = map.getRootElement();
mapDiv.parentNode.lastChild.appendChild(canvas);
MM.Events.addHandler(map, 'viewchangestart', clearCanvas);
MM.Events.addHandler(map, 'viewchangeend', drawPoints);
}
function clearCanvas() {
var context = canvas.getContext("2d");
context.clearRect(0, 0, canvas.width, canvas.height);
}
function drawPoints() {
var date1 = new Date().getTime();
var context = canvas.getContext("2d");
var bounds = map.getBounds();
var maxLatitude = bounds.getNorth();
var minLatitude = bounds.getSouth();
var maxLongitude = bounds.getEast();
var minLongitude = bounds.getWest();
var northwest = bounds.getNorthwest();
var topLeftCorner = LatLongToPixelXY(
northwest.latitude, northwest.longitude, map.getZoom());
var offsetX = topLeftCorner.x;
var offsetY = topLeftCorner.y;
var imageData = context.createImageData(
canvas.width, canvas.height);
var pointsDrawn = 0;
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(
loc.lat, loc.lon, map.getZoom());
var x = point.x - offsetX;
var y = point.y - offsetY;
setPixel(imageData, x, y, 255, 0, 0, 255);
}
}
var date2 = new Date().getTime();
addMessage(pointsDrawn + " Points Drawn", date2 - date1);
context.putImageData(imageData, 0, 0);
}
function setPixel(imageData, x, y, r, g, b, a) {
//find index based on the pixel coordinates
index = (x + y * imageData.width) * 4;
//set pixel
imageData.data[index + 0] = r;
imageData.data[index + 1] = g;
imageData.data[index + 2] = b;
imageData.data[index + 3] = a;
}
function LatLongToPixelXY(latitude, longitude, levelOfDetail) {
var sinLatitude = Math.sin(latitude * Math.PI/180);
var pixelX = ((longitude + 180) / 360) *
256 * (2 << (levelOfDetail-1)) ;
var pixelY = (0.5 - Math.log((1 + sinLatitude) / (1 - sinLatitude))
/(4 * Math.PI)) * 256 * (2 << (levelOfDetail-1));
var pixel = new Object();
pixel.x = (0.5 + pixelX) | 0;
pixel.y = (0.5 + pixelY) | 0;
return pixel;
}
/*
* Add a new log message
*/
function addMessage(message, milliseconds) {
if (milliseconds === undefined) {
}
else {
message = message + ' [' + milliseconds.toString() + ' ms]';
}
$("#lblStatus").append('<li>' + message + '</li>');
}
</script>
</head>
<body>
<div id="mapDiv" class="map"/>
<ul id="lblStatus" style="float:left; margin-left:420px; width: 300px"/>
</body>
</html>
Go to Part 4
What if you used pre-computed constant divisions, like for Math.PI / 2?
ReplyDeleteIt certainly helps :)
ReplyDelete