GPU accelerated visual analytics

Recent months I had lot of fun working   on WebGL component called “mGL” for visualizing and filtering large amount of data in the browser. It has been used  for Incident Analyzer and Area Analyzer Smart M.Apps. Here are  2 videos of the testing app of the mGL that shows its potential.  Most interesting is the filtering part that takes place in the fragment shader. mGL itself has API that can connect to crossfilter to control filtering  or has adapter to be used with dc.js.

First video shows 400k parcels in Cincinaty  and second   400k road network in North Caroline. Both  with fast cross-filtering on several attributes. You can switch between dimensions represented by charts by clicking on their label. Map (road network) will reflects chart’s color and immediately response to changing filters on either chart or on map.second video shows 400k parcels in Cincinaty with the same behavior.

 

 

Advertisements

SVG fast scaled overlay on Leaflet 1.0 and 0.7

SVGScaled SVG can be drawn on map in much more faster way than traditional approaches, at least for points. Traditional approach re-position each element to fit into the view of the map, however SVG is “scalable” so we can use it and it performs much more faster for zoom-in/out.

Few considerations:

  1. SVG itself define viewport by its coordinate space, all outside of this viewport is usually  clipped, so it is important to keep SVG viewport in-line with the viewport of the map. There are approaches that resizes SVG as you zoom-in (here), and while it works, it has a problems in deep-zooms when you need to move on map (actually you move  giant SVG based on the zoom )
  2. translating LatLon to absolute pixel values (like here used for WebGL) is possible solution, however IE and FF has problems with large numbers for transoform (>1 M), So we need to get SVG elements in view coordinates and translate them.
  3. Having some track of bounding box of all elements like again used here should be avoided (SVG or its group element knows about extension of the elements it holds)
  4. So while we keep SVG in the viewport, we need to compensate any shift and zoom by translating <g> (group) of all elements.
  5. So in leaflet when map  moves, SVG is translated back to its original position while <g> is translated forward to reflect the map movement
  6. We need to keep track of LatLon position of either map center or one of the corner – we use topLeft corner.
  7. Leaflet doesn’t do  precise enlargement and rounds view points because of some CSS troubles on some devices (noted here). We need to patch two translating functions in Leaflet to get this right (so SVG enlargement will be aligned with map)… but I need to look on this again, best would be to not patch Leaflet of course.

most important things happen in moveEnd event:

 


 var bounds = this._map.getBounds(); // -- latLng bounds of map viewport
 var topLeftLatLng = new L.LatLng(bounds.getNorth(), bounds.getWest()); // -- topLeft corner of the viewport
 var topLeftLayerPoint = this._map.latLngToLayerPoint(topLeftLatLng); // -- translating to view coord
 var lastLeftLayerPoint = this._map.latLngToLayerPoint(this._lastTopLeftlatLng); 

 var zoom = this._map.getZoom();
 var scaleDelta = this._map.getZoomScale(zoom, this._lastZoom); // -- amount of scale from previous state e.g. 0.5 or 2
 var scaleDiff = this.getScaleDiff(zoom); // -- diff of how far we are from initial scale 

 this._lastZoom = zoom; // -- we need to keep track of last zoom
 var delta = lastLeftLayerPoint.subtract(topLeftLayerPoint); // -- get incremental delta in view coord

 this._lastTopLeftlatLng = topLeftLatLng; // -- we need to keep track of last top left corner, with this we do not need to track center of enlargement
 L.DomUtil.setPosition(this._svg, topLeftLayerPoint); // -- reset svg to keep it inside map viewport

 this._shift._multiplyBy(scaleDelta)._add(delta); // -- compute new relative shift from initial position
 // -- set group element to compensate for svg translation, and scale</pre>
 this._g.setAttribute("transform", "translate(" + this._shift.x + "," + this._shift.y + ") scale(" + scaleDiff + ")");

Test page / Gist : http://bl.ocks.org/Sumbera/7e8e57368175a1433791

To better illustrate movement of SVG inside the map, here is a small diagram of basic SVG states:svgpositioning

Smart M.App

  Recent months I have been authoring  “Green Space Analyzer” web app that shows modern  approach to visualize and  query   multi temporal geospatial data.  User see information in a form he can interact with and discover new patterns, phenomena or information just by very fast ‘feed-back’ of the UI response on the user input.  When user selects for example certain area, all graphs instantly animates transition to reflect selection made, this helps to  better  understand  dynamics of the change. Animation can be seen everywhere – from labels on bar chart, through colors change of the choropleth up to title summary. it creates subtle feeling of control or knowing what has changed and how it has changed. At HxGN 15 conference in   hexagon geospatial keynote, CEO Mladen Stojic showcased it as part of the  vision  called Smart M.App, worth to look at (at 52:40 starts Smart M.App demo):

 

my Smart M.App  ‘world tour’:

 

 

 

geojson-vt on leaflet

update Sept 2015: nice explanation of how geojson-vt works here

Mapbox technologies used in their webgl and opengl libraries are being extracted into standalone pieces. Vladimir Agafonkin,creator of leaflet.js, earcut.js provided slicing and polygon simplification library for geojson called Goejson-vt.Geojson-vt can slice geosjon into tiles aka mapbox tiles.
Quick test and sample of using geojson-vt on leaflet with canvas drawing available here: http://bl.ocks.org/sumbera/c67e5551b21c68dc8299

2 videos:

Overview of various geojson samples

 

folowing video shows 280 MB large geojson !

 

for comparison here is WebGL version on the same data. This version is loading all data into GPU and leaves everything on WebGL (no optimization). It also takes slightly more time to tessellate all polygons, but once done all seems to run fine. Code used is available here

WMS overlay with MapBox-gl-js 0.5.2

alt textQuick and dirty test of the WMS capabilities of the new MapBox-gl-js 0.5.2 API. First of all, yes ! it is possible to overlay (legacy) WMS over the vector WebGL rendered base map … however the way is not straightforward:

 

  • Needs some ‘hacks’ as current version of the API doesn’t have enough events to supply custom URL before it is loaded. But check latest version of mapbox, it might have better support for this.
  • Another issue is that WMS server has to provide HTTP header with Access-Control-Allow-Origin:* to avoid WebGL CORS failure when loading image (gl.texImage2D). Usually WMS servers don’t care about this, as for normal img tags CORS doesn’t apply. Here WebGL has access to raw image data so WMS provider has to explicitly agree with this.
  • Build process of mapbox-gl-js tend to be as many other large js projects complicated, slow, complex. And specifically on Windows platform it is more difficult to get mapbox-gl-js install and build running then on Mac.

Code is documented to guide you through the process, few highlights:


 // -- rutine originaly found in GlobalMercator.js, simplified
 // -- calculates spherical mercator coordinates from tile coordinates
 function tileBounds(tx, ty, zoom, tileSize) {
    function pixelsToMeters(px, py, zoom) {
     var res = (2 * Math.PI * 6378137 / 256) / Math.pow(2, zoom),
         originShift = 2 * Math.PI * 6378137 / 2,
         x = px * res - originShift,
         y = py * res - originShift;
     return [Math.abs(x), Math.abs(y)];
     };
   var min = pixelsToMeters(tx * tileSize, ty * tileSize, zoom),
         max = pixelsToMeters((tx + 1) * tileSize, (ty + 1) * tileSize, zoom);
return min.concat(max);
}

 
]

// -- save orig _loadTile function so we can call it later
 // -- there was no good pre-load event at mapbox API to get hooked and patch url
// -- we need to use undocumented _loadTile
 var origFunc = sourceObj._loadTile;
    // -- replace _loadTile with own implementation
 sourceObj._loadTile = function (id) {
    // -- we have to patch sourceObj.url, dirty !
    // -- we basically change url on the fly with correct BBOX coordinates
    // -- and leave rest on original _loadTile processing
     var origUrl =sourceObj.tiles[0]
                      .substring(0,sourceObj.tiles[0].indexOf('&amp;BBOX'));
     var origUrl = origUrl +"&amp;BBOX={mleft},{mbottom},{mright},{mtop}";
     sourceObj.tiles[0] = patchUrl(id, [origUrl]);
     // -- call original method
     return  origFunc.call(sourceObj, id);
 }

 

 

gist available here

WebGL polyline tessellation with MapBox-GL-JS

update 09/20015 : test of tesspathy.js library here . Other sources to look:

  1.  http://mattdesl.svbtle.com/drawing-lines-is-hard
  2.  https://github.com/mattdesl/extrude-polyline
  3. https://forum.libcinder.org/topic/smooth-thick-lines-using-geometry-shader

*** original post ***

This post attempted to use pixi.js tessellation of the polyline, this time let’s look on how mapbox-gl-js can do this. In short much more better than pixi.js.

it took slightly more time to get the right routines from mapbox-gl-js and find-out where the tessellation is calculated and drawn. It is actually on two places – in LinBucket.js  and in line shader. FireFox shader editor helped a lot to simplify and extract needed calculations and bring it into the JavaScript (for simplification, note however that shader based approach is the right one as you can influence dynamically thickness of lines, while having precaluclated mesh means each time you need to change thickness of line you have to recalculate whol e mesh and update buffers )

 

// — module require mockups so we can use orig files unmodified
 module = {};
 reqMap = {
‘./elementgroups.js’: ‘ElementGroups’,
‘./buffer.js’ : ‘Buffer’
};
require = function (jsFile) { return eval(reqMap[jsFile]); };

 

   &lt;!-- all mapbox dependency for tesselation of the polyline --&gt;
 &lt;script src=&quot;http://www.sumbera.com/gist/js/mapbox/pointGeometry.js&quot;&gt;&lt;/script&gt;
    &lt;script src=&quot;http://www.sumbera.com/gist/js/mapbox/buffer.js&quot;&gt;&lt;/script&gt;
    &lt;script src=&quot;http://www.sumbera.com/gist/js/mapbox/linevertexbuffer.js&quot;&gt;&lt;/script&gt;
    &lt;script src=&quot;http://www.sumbera.com/gist/js/mapbox/lineelementbuffer.js&quot;&gt;&lt;/script&gt;
    &lt;script src=&quot;http://www.sumbera.com/gist/js/mapbox/elementgroups.js&quot;&gt;&lt;/script&gt;
    &lt;script src=&quot;http://www.sumbera.com/gist/js/mapbox/linebucket.js&quot;&gt;&lt;/script&gt;
    &lt;script src=&quot;http://www.sumbera.com/gist/data/route.js&quot; charset=&quot;utf-8&quot;&gt;&lt;/script&gt;
 // -- we don't use these buffers, override them later, just set them for addLine func
 var bucket = new LineBucket({}, {
 lineVertex: (LineVertexBuffer.prototype.defaultLength = 16, new LineVertexBuffer()),
 lineElement: (LineElementBuffer.prototype.defaultLength = 16, new LineElementBuffer())
 });

var u_linewidth = { x: 0.00015 };
// override .add to get calculated points
LineVertexBuffer.prototype.add = function (point, extrude, tx, ty, linesofar) {
    point.x = point.x + (u_linewidth.x * LineVertexBuffer.extrudeScale * extrude.x * 0.015873);
    point.y = point.y + (u_linewidth.x * LineVertexBuffer.extrudeScale * extrude.y * 0.015873);
    verts.push( point.x, point.y);
    return this.index;
};

// — pass vertexes into the addLine func that will calculate points
bucket.addLine(rawVerts,“miter”,“butt”,2,1);

prototype  code posted here

 

WebGL polyline tessellation with pixi.js

update 09/2015  : another triangulation methods (mapbox, tesspathy) mentioned here

pixi.js is a 2D open source library for gaming that includes WebGL support for primitives rendering. Why not to utilize it for polyline renderings on map ? It turned out, however, that the  tesselation of the polylines is not handled well.

most important code snippets:

<script src="Pixi.js"></script>
<script src="Point.js"></script>
<script src="WebGLGraphics.js"></script>

//--data
<script src="route.js" charset="utf-8"></script>

var graphicsData = {
 points: verts,
 lineWidth: 0.00015,
 lineColor: 0x33FF00,
 lineAlpha: 0.8
};
var webGLData = {
   points: [],
   indices: []
 };
 // -- from pixi/utils
 PIXI.hex2rgb = function (hex) {
   return [(hex >> 16 & 0xFF) / 255,
           (hex >> 8 & 0xFF) / 255,
           (hex & 0xFF) / 255];
  };

PIXI.WebGLGraphics.buildLine(graphicsData, webGLData);

I have put sample here:

Another implementaiton of polyline tessellation (seems like more functional) is in mapbox-gl-js  in LineBucket  .Mapbox-gl-js code took quite more time to get it running and debug on Windows platform,I  had to run npm install  from VS command shell and read carefully what all the npm errors are saying (e.g. Python version should be < 3). Then FireFox for some reason haven’t triggered breakpoint on LineBucket.addLine, this took another time to find out that I should debug thiOstravaRailwayss rather in Chrome.   See the blog here.Anyway good  experience with all the messy npm modules, their install requirements and unnecessary complexity. Also all the npm modules takes more than 200 MB, but some of them are optional in the install.

After all basic LINE draw in WebGL (without the thicknes and styling) is useful too, as on picture above you can see railways in CZ city Ostrava.