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

Advertisements