WebGL polygons fill with libtess.js

14 Replies

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

14 thoughts on “WebGL polygons fill with libtess.js”

  2. Stanislav Post author

    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 !

    Reply ↓
  3. Jürgen Ahting

    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.

    Reply ↓
    1. Stanislav Post author

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

      Reply ↓
      1. Jürgen Ahting

        Unfortunately I could not reproduce your problem on CZBorderSimple.js with Firefox on Windows.

        For polygons without holes PnlTri.js defaults to an ear clipping algorithm which is usually quite fast – not in this case: 8 seconds within qunit (http://www.ameco.tv/rawdata/CZBorderSimple_EarClip.png). You can force PnlTri.js to use Seidel’s algorithm with a second parameter “`true“` to “`triangulate_polygon“`: 3 seconds within qunit (http://www.ameco.tv/rawdata/CZBorderSimple_Seidel.png). Both create 19413 triangles.

        Stragely the loop at line 555 you mention (inside ear clipping) has an additional safeguard against endless looping :-( .

      2. Stanislav Post author

        Thanks for testing ! please try the bug on IE 11, I can confirm on FF it runs. Correction : on IE11 it runs too, but takes so much time that is looks like deadlock, but is not.

  4. Jürgen Ahting

    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.

    Reply ↓
  5. Brendan Kenny

    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

    Reply ↓
  6. Stanislav Post author

    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. )

    Reply ↓

Leave a comment

This site uses Akismet to reduce spam. Learn how your comment data is processed.