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</span></strong>
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

This entry was posted in Code, Data Visualization, Leaflet, WebGL and tagged , , . Bookmark the permalink.

13 Responses to WebGL polygons fill with libtess.js

  1. I’d recommend not using Array.map for iterating huge arrays — it’s really slow. Rewrite this part using simple loops and it should get faster.

  2. Stanislav says:

    couldn’t get this faster for small dataset, following change showed me cca 3000 ms slower then Array.map for 120 186 points in Chrome:

    for ( i = 0; i < data.features[0].geometry.coordinates[0][0].length; i++) {
    var d = data.features[0].geometry.coordinates[0][0][i];
    pixel = LatLongToPixelXY(d[1], d[0], 0);
    var coords = [pixel.x, pixel.y, 0];
    tessy.gluTessVertex(coords, [pixel.x, pixel.y, 0]);
    }
    however for large data difference is really huge, thanks !

  3. Could you give me a hint what went wrong with PnlTri.js ?
    From the date of your entry I guess you used version 1.X which didn’t handle all cases of touching edges and points. Rev 2.0 should handle everything except non-adjacent duplicate points and line intersections. I will start working on them soon.

    • Stanislav says:

      I have tried version 2.0, thanks for pointing on this, I tried to run following polygon: http://www.sumbera.com/gist/data/CZBorderSimple.js
      and algorithm doesn’t return in reasonable time from loop on line 555 in plntri.js. For simpler polygon (like this http://www.sumbera.com/gist/data/simpleBorder.js ) it runs, however.
      you can process data samples by simply including it as script and process as :
      var rawVerts = [];
      for (var i = 0; i < data.features[0].geometry.coordinates[0].length; i++) {
      var d = data.features[0].geometry.coordinates[0][i];
      rawVerts.push({ x: d[0], y: d[1] });
      }
      rawVerts.pop(); // remove last repeating point

      var myTriangulator = new PNLTRI.Triangulator();
      var triangList = myTriangulator.triangulate_polygon([rawVerts]);

  4. Any Idea why? I’m no JS expert.
    Chrome is about 1.5 times faster than FF on my Linux server and I noticed that profiling on FF and Chrome had different results, but I never experienced such a crazy slowdown.

  5. Hi!

    I just stumbled across your blog. Excited to see people try out libtess.js

    After I released the library not a lot of interest developed initially, so I left quite a few potential performance improvements untouched.

    As you wrote, one of the benefits of libtess is that it handles even the messiest of data, and publicly-available geo data is usually some of the messiest data there is (this is why I chose to port libtess in the first place), so even though there are faster algorithms for guaranteed-clean data, I think there will still be a place for the emscripten port of libtess or my own for quite a while.

    Interest seems to be picking up recently, and I’d like to improve performance. If this is public data, I’d love to add it as a particular problem case to the set of benchmarks we want to improve (8x poly2tri’s speed is way too slow!). You can comment here, if you’d like:

    https://github.com/brendankenny/libtess.js/issues/4

  6. Stanislav says:

    Hi Brendan,
    thanks for great work on making this lib available ! I am also curious why EMSCRIPTEN version is not significantly faster (while larger and requesting more memory). Does this imply that carefully ported lib is worth over EMSCRIPTEN ?
    Looking forward for your next port (any polylines ? http://sourceforge.net/p/vaserenderer/code/ci/master/tree/include/
    http://artgrammer.blogspot.co.uk/2011/07/drawing-polylines-by-tessellation.html
    http://hal.inria.fr/docs/00/90/73/26/PDF/paper.pdf. )

  7. I started using your wonderful work in a library for leaflet complete with clicking, eventually with edit. https://github.com/robertleeplummerjr/Leaflet.glify, pronounced gl-ify

    It makes using as simple as:
    points: `L.gliphy.points({map: map, data: points});`
    shapes: `L.gliphy.shapes({map: map, data: features});`

    Thanks for your hard work!

    webgl rocks.

  8. This article was a huge help. Here is a version of the code that includes picking with readPixels from an offscreen buffer: https://github.com/unicef/webgl-picking-geo-polygons, based on Brenden Kenny’s “Google Maps + HTML5 + Spatial Data Visualization” video.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s