consider combining multiple tile buffers into one buffer

[ansis]

Moving the cost of having multiple separate tiles from render-time to preprocessing should increase framerate at the cost of a bit more tile loading latency.

I'm not sure if combining the buffers of all tiles is something we should be trying anytime soon, but it could help us eliminate our rendering cpu bottleneck and avoid the cost of using the stencil buffer for tile clipping.

---

currently

Each tile currently has it's own set of buffers. When drawing a layer, each tile is drawn and clipped separately. With this approach the data for a tile gets uploaded once and never changed.

why combine

Each draw call and state change has a cost. If we joined all the tiles for the current view into one buffer we could draw each layer with one call, instead of one per tile. This would reduce the cpu cost of rendering and make it constant relative to the number of tiles, instead of linear as it is now.

We have less than 16ms to render each frame and when we exceed that we start dropping frames. Large maps with many tiles and complex styles often push this over the edge. There is very little breathing room so style recalculation, updating tile cover and garbage collection push it over the time limit. Reducing the cpu cost of rendering a frame should help remove this bottleneck so that we drop less frames.

cost of combining

Combining wouldn't eliminate the cost, it would just move it elsewhere. Each time a new tile is loaded the tile's data would be combined the data of other visible tiles and then the entire buffer would be uploaded to the gpu. The uploading step is fast enough. Some quick tests show that if we double buffer the data buffers we can upload a ton of data without bottlenecking anything. Actually combining the buffers before uploading would the main performance cost. Vertex coordinates would need to be scaled/offset and element indices would need to be rewritten. I'm not sure how slow this would be, but it would be done in the workers so it would just add tile loading latency.

clipping

If buffers are combined we can't clip each tile separately with the stencil buffer. When processing the data into buffers the geometries would need to be clipped exactly to the tile boundaries so that they can just be drawn without any render-time clipping. This would make processing the data more expensive and complicated, but it would also eliminate the cost and complexity of using the stencil buffer. We wouldn't have to draw the clipping masks, or compare against them which could help us since we are also fillrate limited.

We also need a way of clipping within a tile (if a parent tile is partially covered by a child). We could tile tiles into multiple smaller subtiles. When combining the buffers of the visible tiles, only the subtiles from the area that isn't covered by the child tile would be used. This starts getting a bit complicated though.

I just wanted to dump this idea in a ticket. What do you think @kkaefer ?

[mourner]

Interesting. Seems like a pretty big effort, but sounds promising. I think clipping features in the worker shouldn't take too much time, since most of the features would be trivial rejects, and rect-clipping algorithms are very fast (Leaflet uses Sutherland-Hodgeman one which is O(n)). Clipping can also serve double purpose by fixing weak polygons that fail to triangulate (like the second one here).

[mourner]

Ha, turns out clipping for this use case isn't as easy — we can't use Sutherland-Hodgeman because it introduces artifacts like this. The only good algorithm that allows clipping without any problems including non-simple polygons and weakly simple polygons is Vatti, which is pretty complex (and probably much slower), and implemented by Clipper.

[mourner]

BTW, found a simple clipping algorithm that claims to solve the degenerate edges issue. Certainly looks much easier than Vatti.

[springmeyer]

cool research. /cc @artemp who I know also has a few algorithms he's researched and considered implementing.

[mourner]

When processing the data into buffers the geometries would need to be clipped exactly to the tile boundaries so that they can just be drawn without any render-time clipping.

@ansis btw, in this case, how would you clip stroked fills so that stroke isn't rendered on boundaries? Would you need to clip triangulated stroke geometries separately from fill geometries? This would make things more complicated...

[artemp]

The best book on geometry clipping I found : http://www.amazon.co.uk/Computer-Graphics-Geometric-Modelling-Implementation/dp/B00F44JGIO/ref=sr_1_2?ie=UTF8&qid=1408616500&sr=8-2&keywords=Max+K+Agoston

It has description of following polygon clipping algorithms

• Sutherland-Hodgman
• Weiler
• Liang-Barsky (used in AGG)
• Mailot
• Vatti (Clipper)
• Greiner-Hormann (which is similar to Weiler but simpler and authors claim it to be x2 faster than Vatti)

@mourner - I can't access link you posted above, wondering which algorithm is mentioned there ?

/cc @DennisOSRM - did you dig any of these?

[mourner]

@artemp thanks for the tip! The algorithm mentioned is Glassner, A., ''Clipping a Concave Polygon'' , in Graphics Gems V, A. Paeth, ed., Academic Press, Cambridge, 1995 (although I didn't find a full description as a downloadable pdf anywhere).

An important requirement for the algorithm in this case is being able to handle degenerate cases like intersecting and overlapping edges. Unless it gets fixed on the mapnik VT side (I really hope so).

[tdihp]

Will exact clipping compromise polygon edge line rendering?

I'm not expert javascript developer nor expert webgl developer, the (amazing looking)
debug style does less than 350 draw calls among over 3500 gl calls on my notebook.

I think there could be less status change if painter can render multiple tiles in a roll,
with only buffer changes for each tile. But I'm not sure how it will affect performance.

Here's how:

1. render multiple tile's stencil masks (e.g. 1-64 for 63 tiles use 6-bit stencil mask)
2. for each layer:
   1. setup program
   2. for each tile:
   3. change buffer and stencil func
   4. draw
3. clear stencil masks and repeat 1 for next batch of tiles

Sorry for interrupting.

[ansis]

@tdihp thanks for taking the time to dig in and respond! Your suggested approach sounds much better and way less complex. mapbox-gl-native already does something similar and it seems to be working well. The next step is switching to that here in -js

Will exact clipping compromise polygon edge line rendering?

I think it wouldn't, but its likely I'm missing something

[kkaefer]

When packing multiple tiles into one buffer, we also have to do some sort of simplification for tiles that are rendered a lot smaller than intended (e.g. when zooming out, we retain a few tiles that are the going to be rendered at high resolution). This could be a easy as scaling down (we only have integer scaling factors) and dropping duplicate consecutive points.

[mourner]

Will exact clipping compromise polygon edge line rendering?

I think it wouldn't, but its likely I'm missing something

The problem here is that with exact clipping by tile boundaries, the fill outline will be rendered on the boundary. Stumbled upon this again when trying to come up with an efficient GeoJSON tiling algorithm. #464

[kkaefer]

@incanus also note that we don't necessarily have to replicate iOS behavior 100% every time.

[ansis]

Nothing actionable here. closing