tesselate polygons instead of rendering with stencil buffer

[ansis]

We should draw polygons by tesselating them instead of using the stencil buffer trick. Native already does this. https://github.com/mapbox/mapbox-gl-js/commit/7b353122b46503b57e6d5073184883c1c2e21404 is a first attempt that uses libtess.js. Rendering is faster but the tesselation is slow. The buildings layer can take up to 500ms to tesselate.

• take a look at poly2tri.js (which only accepts simple polygons)
• revisit tesselating polygons in the tiles

[mourner]

After looking further into FIST, I think I can implement its bad polygon handling and holed polygons splitting approach in a couple days. After this, we will have an algorithm that's very fast for most data while being robust.

This means we will be able to punt on https://github.com/mapbox/mapnik-vector-tile/issues/53 for now, and the only real VT blocker remaining will be https://github.com/mapbox/mapnik-vector-tile/issues/59 since it's the only way to differentiate between multipolygons and holed polygons (which is required for the algorithm). It's not an issue for GeoJSON data since we have the differentiation there. cc @jfirebaugh @springmeyer @flippmoke

@ljbade poly2tri uses Constrained Delaunay Triangulation algorithm which produces optimal triangulation, but at the expense of performance and robustness. It can't handle degenerate/bad polygons, which is critical. Thin triangles may be bad for GPU but they're not a bottleneck in JS. The bottleneck is triangulation speed.

So the chosen algorithm needs to be very fast for practical OSM polygons but also handle stuff like self-intersections, colinear edges, twisted polygons etc. Thus the tough research.

[ansis]

After looking further into FIST, I think I can implement its bad polygon handling and holed polygons splitting approach in a couple days. After this, we will have an algorithm that's very fast for most data while being robust.

Sounds like a great plan!

only real VT blocker remaining will be mapbox/mapnik-vector-tile#59 (polygon winding order)

I think it should be possible to recover this accurately enough for our uses by checking if a ring is contained within another ring. Cases where two rings intersect each other are a bit ambiguous, but we could count a ring as a hole if at least half of the ring's vertices we check are within the other ring. It wouldn't be perfect, but it would probably be good enough, especially for degenerates caused by simplification.

[mourner]

Hmm, sounds like a good idea. It will be slower since it's O(n1 * n2) for each ring but will work.

[mourner]

OK, great progress here! With https://github.com/mapbox/mapbox-gl-js/commit/eb7b769a5bbee735b1ac07db969e39c0f4de884b, the earcut algorithm now handles bad data pretty well. What's changed:

• there's a preprocessing step that removes all clipping-induced colinear points (vertical or horizontal)
• when the simple earcut algorithm can't find an ear to slice off, it finds a diagonal that divides the remaining polygon into two, relinks the vertices list into two lists and launches earcut on each half
• if we can't find a diagonal, stop the algorithm — we've likely extracted all useful triangles possible for the data

So far I wasn't able to find a noticeable artifact, crash or infinite loop after the change. If you find a bad polygon, send it to me and I'll patch the algorithm.

For the same dense DC test view I mentioned https://github.com/mapbox/mapbox-gl-js/issues/682#issuecomment-60642374, updated earcut processes all non-holed and non-multi-ring polygons in 70ms. Libtess does the same in 220ms.

Now what's left is implementing FIST holed polygon conversion routine and we're ready to ditch libtess and land this in master, unless we discover major rendering artifacts.

[mourner]

I think it should be possible to recover this accurately enough for our uses by checking if a ring is contained within another ring.

On a second thought, this could be too slow. Due to the fact that multipolygons have multiple polygons, each potentially with multiple holes, we need to compare each ring with each other ring. For each comparison, we need to loop one ring for each point of the other ring. This may be too much. And big polygons with lots of holes are pretty common — e.g. water.

[ansis]

For each comparison, we need to loop one ring for each point of the other ring.

You could check a constant number of points or a fraction of the points and guess based on that. For, example if you look at 10 points you would be able to say either "at least 5 vertices of this ring are contained in the other ring, let's treat it as a hole" or "at least 5 vertices of this ring are outside the other ring, let's treat it as an outer ring". Less accurate, but maybe good enough if the only errors are from simplification.

Or maybe some other way to short-circuit in the default case, like stopping after x points aren't contained.

[mourner]

Managed to considerably improve the quality of triangulation with little cost (takes ~10% more time). Before & after:

It also now removes all colinear points (not only horizontal/vertical).

[brendankenny]

@mourner how can I access the test data you mention in https://github.com/mapbox/mapbox-gl-js/issues/682#issuecomment-60642374? The link you give is a localhost:3000 link :) so I assume I need to clone something and run it to try it out.

I'm still neck deep in a few other projects but I'd like to get back to speeding up libtess for bad cases in the next week or two.

[mourner]

@brendankenny awesome! See https://github.com/mapbox/mapbox-gl-js#setup. The code with tesselation is in the earcut branch now.

[ljbade]

@mourner awesome, it would be nice to be able to somehow benchmark the two to see if GPU speedup is worth the 10% CPU slowdown

[mourner]

@ljbade yeah, I don't know how to measure this since it heavily depends on the platform. But 8-10% is probably not going to make much difference because it will probably be fast enough to not be a bottleneck compared to other things that happen when processing a tile (populating buffers, label placement etc.).

[mourner]

Triangulation algorithms are driving me crazy again... Implemented hole support in triangulation itself (no hole detection from VT yet), works great! Now trying to get around noticeable artifacts from self-intersections, like this:

[mourner]

Returning from the abyss of madness and despair, just published the algorithm as mapbox/earcut. Made it support holes, fixed some pretty hard to track bugs and hopefully made it more robust. We'll see how it copes on real data again after I implement outer/inner rings classification.

Sample output on a really crappy OSM water polygon with holes:

Benchmarks:

typical OSM building (15 vertices):
earcut x 575,766 ops/sec ±0.81% (95 runs sampled)
libtess x 28,217 ops/sec ±1.07% (93 runs sampled)
earcut is 1940% faster than libtess

dude shape (94 vertices):
earcut x 21,908 ops/sec ±0.83% (97 runs sampled)
libtess x 5,738 ops/sec ±1.19% (95 runs sampled)
earcut is 282% faster than libtess

dude shape with holes (104 vertices):
earcut x 9,697 ops/sec ±1.19% (95 runs sampled)
libtess x 5,120 ops/sec ±0.77% (96 runs sampled)
earcut is 89% faster than libtess

complex OSM water (2523 vertices):
earcut x 33.52 ops/sec ±1.07% (60 runs sampled)
libtess x 71.17 ops/sec ±2.77% (77 runs sampled)
libtess is 112% faster than earcut

@brendankenny after updating libtess version, it suddenly got like 50% faster! Really awesome, keep it up. Looks like there's a good room for optimization for simple shapes with low number of vertices.

[bcamper]

@mourner this is awesome! Thank you for extracting and publishing the module. Would love to see more competition from @brendankenny too ;) (I probably won't embarrass myself trying.)

[mourner]

@bcamper yeah! It'll be fun to run earcut on Mapzen libtess benchmarks, and run more tests to see how bad it is on cramped OSM data with lots of self-intersections — I'm afraid it will fail hard in some cases. :)

[Sumbera]

@mourner thanks for earcut ! unbelievable, just quick tested it on my geo dataset ( 2256 polygons with 3 328 794 vertexes):

Browser	Earcut [s]	Poly2Tri [s]:
Chrome	5.1	7.2
Firefox	4.9	6.6
IE11	144.4 (!)	43.2

[mourner]

@Sumbera what! How can IE11 be 30 times faster than Chrome? There are still some optimizations that I could try so it may get even faster btw... I'm also concerned about robustness. Did it triangulate everything correctly in your case?

[Sumbera]

... measured in [s] as seconds, time taken, not [ops/sec]... so IE11 is 30 times slower. a brief visual inspection didn't reveal any problems. check here : http://youtu.be/Cl07z93ImqE

[mourner]

Yeah, I meant slower. :) Glad to see that it's working!

[mourner]

Sorry for spamming again — this is already turning into memoirs... So, I wrote the rings classification code that seems to sorta work for now (takes maybe ~5-20% of the tessellation time), so finally I was able to see how earcut copes with all the VT data on a live map.

On high zoom levels, it works wonderfully — no noticeable artifacts in dense city areas at all and very fast, which got me very optimistic at first. But the more you zoom out, the more complex water polygons with lots of holes start to appear, and the more simplification kicks in introducing all sorts of weird self-intersections and degeneracies, and it starts to get really really bad:

Spen5 a lot of time on trying to deduce the degenerate cases that break to maybe find a workaround but started to fall into the abyss of madness and despair again. Debugging bad data triangulation is really, really hard. Who knew this task would be so damn difficult to solve, especially when working on this alone. :(

By the way, to be fair, even libtess breaks on some cramped data. I'll try to find some examples to provide to @brendankenny which produce garbled triangulation.

[mourner]

@brendankenny here's the fun libtess result:

[ljbade]

Oh man that really sucks. A simplification algorithm that doesn't produce bad polygons? Perhaps too much work.

[mourner]

Managed to get a reduced test case of a bug in hole elimination that produces at least some part of the earcut artifacts, so hopefully we'll get a step closer once it's fixed:

[brendankenny]

yeah, that's rough :( Errors in our libraries aside, though, the triangulation can only do so much without specific knowledge about the geometry.

One of the buildings @bcamper gave me for a Mapzen test is a good example -- open the libtess.js expectations viewer and switch the test geometry to Mapzen single builidng - OSM. If you switch through the winding rules you can see various possibly-reasonable interpretations, but even as a human I have no idea what's going on with those building outlines without going there in person or asking the original author what they were thinking.

The original libtess description just promises to be robust in the face of degeneracies and to provide a "reasonable tesselation" given the input, which is really the best we can aim for. I think you're right to look to earlier stages of geometry input and processing for a full fix for these issues.

[ljbade]

So how come these bad polygons don't cause problems with normal rasterisation?

[mourner]

OK, now we're getting somewhere!

After hours of crazy debugging and a bunch of earcut point releases fixing different race conditions, I can't seem to find any glaring degeneracies browsing the map on zoom 7+. It handles everything pretty well. The only minor issue is sometimes seeing tiny sliver triangles on the more simplified shapes, like on the image below, but they're hardly noticeable:

I also found out what is the issue on lower zoom levels. Turns out it's not triangulation — Mapnik VT returns lots of degenerate clipped squares the size of the tile, which lead to ring classification code thinking that the hole square is water with lots of islands when it's in fact all US/Canada land. Generally ring classification is a trap and we should get https://github.com/mapbox/mapnik-vector-tile/issues/59 as soon as possible.

[mourner]

Released earcut 1.1.0 today with faster hole handling and more robustness. The library turned out to be pretty awesome. While there's still room for improvement on polygons with lots of points, it's good enough for now.

For a typical dense map view of DC mentioned above, triangulation of 6 tiles takes ~50ms. For a lower zoom view with lots of water, 4 tiles take ~390ms, with half of that spent on classifying rings. Once this need is gone, we're ready to merge.

[mourner]

FYI I managed to optimize Earcut with a clever hashing technique using z-order curve and also much better hole elimination algorithm, so it's now pretty fast even on complex polygons with lots of points (plenty of them on lower zoom levels with water/parks). Latest benchmarks:

(ops/sec)	pts	earcut	libtess	poly2tri	pnltri
OSM building	15	580,351	27,832	28,151	216,352
dude shape	94	29,848	6,194	3,575	13,027
holed dude shape	104	18,688	5,428	3,378	2,264
complex OSM water	2523	445	63.72	failure	failure
huge OSM water	5667	80.09	23.73	failure	failure

[Sumbera]

Browser	Earcut 1.0 [s]	Earcut 1.2 [s]:
Chrome	5.1	3.3
IE11	144.4	24.0

awesome 'era'cut ! thanks !

[jfirebaugh]

⇢ #1606