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

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

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]); };

 

   <!-- all mapbox dependency for tesselation of the polyline -->
 <script src="http://www.sumbera.com/gist/js/mapbox/pointGeometry.js"></script>
    <script src="http://www.sumbera.com/gist/js/mapbox/buffer.js"></script>
    <script src="http://www.sumbera.com/gist/js/mapbox/linevertexbuffer.js"></script>
    <script src="http://www.sumbera.com/gist/js/mapbox/lineelementbuffer.js"></script>
    <script src="http://www.sumbera.com/gist/js/mapbox/elementgroups.js"></script>
    <script src="http://www.sumbera.com/gist/js/mapbox/linebucket.js"></script>
    <script src="http://www.sumbera.com/gist/data/route.js" charset="utf-8"></script>
 // -- 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.

 

WebGL polygons fill with libtess.js

kraje

Update 1.6.2015: geojson-vt seems to do great job in tiling and simplifying polygons. Check this post.

Update 18.1.2015: Vladimir Agafonkin from MapBox released earcut.js – very fast and reliable triangulation library. Worth to check. Video available here:

 

 

Original post:

Brendan Kenny from Google showed  here how he made polygons using libtess.js on Google Maps, so I have tried that too with single large enough polygon on Leaflet with CZ districts.  libtess.js is port from C code . Neither plntri.js (update: see also comments for plntri v2.0 details)  nor PolyK.js were able to triangulate large set  of points as libtess.js.

Update:  I looked on poly2tri.js  too with following results:

I could run 2256 polygons (all together > 3M vertexes)  with poly2tri  16 701 ms  vs 127 834 ms (libtess), however I  had to dirty fix  other various errors from poly2tri (null triangles or “FLIP failed due to missing triangle…so some polygons were wrong..), while  libtess was fine for the  same data.

Here is  a test :  3 M vertexes with 1 M triangles have been by generated by libtess in 127s . poly2tri took 16s.  Drawing is still fine but it is ‘just enough’ for WebGL too.

 

 

key part is listed below:


tessy.gluTessNormal(0, 0, 1);
tessy.gluTessBeginPolygon(verts);

tessy.gluTessBeginContour();

//--see blog comment below on using Array.map&lt;/span&gt;&lt;/strong&gt;
data.features[0].geometry.coordinates[0].map(function (d, i) {
pixel = LatLongToPixelXY(d[1], d[0],0);
var coords = [pixel.x, pixel.y, 0];
tessy.gluTessVertex(coords, coords);
});

tessy.gluTessEndContour();
// finish polygon (and time triangulation process)
tessy.gluTessEndPolygon();

code available here: http://bl.ocks.org/sumbera/01cbd44a77b4283e6dcd

 

There is also EMSCRIPTEN version of the tesslib.c available on github, and I was curious whether this version would increase speed of  computation. I could run it but for large polygons (cca 120 verts of CZ boundary) I had to increase module memory to 64 MB for FireFox.  Tessellata 120T verts in  FF-30 took 21s, IE-11, Ch-36: failed  reporting out of stack memory :(

Getting back to version from Brendan  (no emscripten) I quickly measured same data on browsers: IE-11 21s, Ch-36: 31s,  FF-30: 27s .

Update Oct/2014: Polyline tessellation blog here

Leaflet WebGL many points rendering

WebGL is funny – programming in very low level style in JavaScript. This sample plots 86T points using this technology.  .

 

 

 

The code is very straightforward, the only thing is to how points are initially loaded and scaled (instead of reloading each time when map moves).

All points are initially transformed to tile size of 256 x 256 pixels at zoom level 0  and then re-scaled/re-shifted based on the current position of the map. drawingOnCanvas is called from L.CanvasOverlay each time map needs to be drawn (move, zoom)

 


function drawingOnCanvas(canvasOverlay, params) {
  gl.clear(gl.COLOR_BUFFER_BIT);
  // -- set base matrix to translate canvas pixel coordinates -> webgl coordinates
 mapMatrix.set(pixelsToWebGLMatrix);
  var bounds = leafletMap.getBounds();
  var topLeft = new L.LatLng(bounds.getNorth(), bounds.getWest());
  var offset = LatLongToPixelXY(topLeft.lat, topLeft.lng);
  // -- Scale to current zoom
  var scale = Math.pow(2, leafletMap.getZoom());
 scaleMatrix(mapMatrix, scale, scale);
 translateMatrix(mapMatrix, -offset.x, -offset.y);
  // -- attach matrix value to 'mapMatrix' uniform in shader
  gl.uniformMatrix4fv(u_matLoc, false, mapMatrix);
 gl.drawArrays(gl.POINTS, 0, numPoints);
}

More information and insipiration I took from this site

demo here: http://bl.ocks.org/sumbera/c6fed35c377a46ff74c3

For polygons rendering check here and for polyline rendering here

Some good intros to WebGL that might help you to understand the code: http://aerotwist.com/presentations/custom-filters/#/6

There is a nice intro book to WebGL  WebGL Programming Guide by Kouchi Matsuda and Rodger Lea

To illustrate how variables are passed from JavaScript to shaders used in above example, here are two figures from the book-  figure 5.7 on p. 149, and figure 5.3 on p.144.

strideoffset
Stride and Offset

This figure shows single buffer (interleaved)that is used fro both coordinates and size. In similar way single buffer is constructed in the example here:

 

 

 

var vertBuffer = gl.createBuffer();
var vertArray = new Float32Array(verts);
var fsize = vertArray.BYTES_PER_ELEMENT;

gl.bindBuffer(gl.ARRAY_BUFFER, vertBuffer);
gl.bufferData(gl.ARRAY_BUFFER, vertArray, gl.STATIC_DRAW);
gl.vertexAttribPointer(vertLoc, 2, gl.FLOAT, false,fsize*5,0);
gl.enableVertexAttribArray(vertLoc);
// -- offset for color buffer
gl.vertexAttribPointer(colorLoc, 3, gl.FLOAT, false, fsize*5, fsize*2);
gl.enableVertexAttribArray(colorLoc);

 

shadervariables2
behavior of a varying variable

Leaflet, WebGL / Canvas tiled vectors

Update June 2014: Simple point WebGL sample is here: https://blog.sumbera.com/2014/06/08/leaflet-webgl-many-points-rendering/
Cool WebGL and Canvas demo of vector drawing in Leaflet 0.8  !
WebGL: http://vector.io/vector-map/

leafletWebGL

Canvas : http://vector.io/vector-map/#canvas

GitHub project: https://github.com/bcamper/vector-map