From c0efad5de22e50a2f2d541a62a07b0786cde0202 Mon Sep 17 00:00:00 2001
From: =?UTF-8?q?Konstantin=20K=C3=A4fer?= <mail@kkaefer.com>
Date: Thu, 20 Jul 2017 14:49:56 +0200
Subject: [core] generate masks for raster tiles to avoid painting over
 children

---
 mapbox-gl-js                                       |   2 +-
 src/mbgl/gl/index_buffer.hpp                       |   1 +
 src/mbgl/gl/vertex_buffer.hpp                      |   1 +
 src/mbgl/renderer/buckets/raster_bucket.cpp        |  65 ++++++++-
 src/mbgl/renderer/buckets/raster_bucket.hpp        |   4 +
 src/mbgl/renderer/layers/render_raster_layer.cpp   |  17 ++-
 src/mbgl/renderer/render_tile.cpp                  |   4 +
 src/mbgl/renderer/render_tile.hpp                  |   2 +
 src/mbgl/renderer/sources/render_raster_source.cpp |   2 +
 src/mbgl/tile/raster_tile.cpp                      |   8 +-
 src/mbgl/tile/raster_tile.hpp                      |   7 +-
 src/mbgl/tile/tile.hpp                             |   2 +
 test/gl/bucket.test.cpp                            | 159 +++++++++++++++++++++
 13 files changed, 265 insertions(+), 9 deletions(-)

diff --git a/mapbox-gl-js b/mapbox-gl-js
index 31444a72c2..0c225291ab 160000
--- a/mapbox-gl-js
+++ b/mapbox-gl-js
@@ -1 +1 @@
-Subproject commit 31444a72c2dafdd7dba99dc3bf5428c155e07cf4
+Subproject commit 0c225291ab77c6aa5e4b4ca41168c1e501d94be1
diff --git a/src/mbgl/gl/index_buffer.hpp b/src/mbgl/gl/index_buffer.hpp
index 1e57fb11f2..01b6396e00 100644
--- a/src/mbgl/gl/index_buffer.hpp
+++ b/src/mbgl/gl/index_buffer.hpp
@@ -26,6 +26,7 @@ public:
     bool empty() const { return v.empty(); }
     void clear() { v.clear(); }
     const uint16_t* data() const { return v.data(); }
+    const std::vector<uint16_t>& vector() const { return v; }
 
 private:
     std::vector<uint16_t> v;
diff --git a/src/mbgl/gl/vertex_buffer.hpp b/src/mbgl/gl/vertex_buffer.hpp
index 4808803d00..9f8b156b25 100644
--- a/src/mbgl/gl/vertex_buffer.hpp
+++ b/src/mbgl/gl/vertex_buffer.hpp
@@ -28,6 +28,7 @@ public:
     bool empty() const { return v.empty(); }
     void clear() { v.clear(); }
     const Vertex* data() const { return v.data(); }
+    const std::vector<Vertex>& vector() const { return v; }
 
 private:
     std::vector<Vertex> v;
diff --git a/src/mbgl/renderer/buckets/raster_bucket.cpp b/src/mbgl/renderer/buckets/raster_bucket.cpp
index 3f5879262d..1a0409f456 100644
--- a/src/mbgl/renderer/buckets/raster_bucket.cpp
+++ b/src/mbgl/renderer/buckets/raster_bucket.cpp
@@ -22,7 +22,7 @@ void RasterBucket::upload(gl::Context& context) {
     if (!texture) {
         texture = context.createTexture(*image);
     }
-    if (!vertices.empty()) {
+    if (!segments.empty()) {
         vertexBuffer = context.createVertexBuffer(std::move(vertices));
         indexBuffer = context.createIndexBuffer(std::move(indices));
     }
@@ -45,6 +45,69 @@ void RasterBucket::setImage(std::shared_ptr<PremultipliedImage> image_) {
     uploaded = false;
 }
 
+void RasterBucket::setMask(TileMask&& mask_) {
+    if (mask == mask_) {
+        return;
+    }
+
+    mask = std::move(mask_);
+    clear();
+
+    if (mask == TileMask{ { 0, 0, 0 } }) {
+        // We want to render the full tile, and keeping the segments/vertices/indices empty means
+        // using the global shared buffers for covering the entire tile.
+        return;
+    }
+
+    // Create a new segment so that we will upload (empty) buffers even when there is nothing to
+    // draw for this tile.
+    segments.emplace_back(0, 0);
+
+    constexpr const uint16_t vertexLength = 4;
+
+    // Create the vertex buffer for the specified tile mask.
+    for (const auto& id : mask) {
+        // Create a quad for every masked tile.
+        const int32_t vertexExtent = util::EXTENT >> id.z;
+        const int32_t textureExtent = 32768 >> id.z;
+
+        const Point<int16_t> tlVertex = { static_cast<int16_t>(id.x * vertexExtent),
+                                          static_cast<int16_t>(id.y * vertexExtent) };
+        const Point<int16_t> brVertex = { static_cast<int16_t>(tlVertex.x + vertexExtent),
+                                          static_cast<int16_t>(tlVertex.y + vertexExtent) };
+        const Point<uint16_t> tlTexture = { static_cast<uint16_t>(id.x * textureExtent),
+                                            static_cast<uint16_t>(id.y * textureExtent) };
+        const Point<uint16_t> brTexture = { static_cast<uint16_t>(tlTexture.x + textureExtent),
+                                            static_cast<uint16_t>(tlTexture.y + textureExtent) };
+
+        if (segments.back().vertexLength + vertexLength > std::numeric_limits<uint16_t>::max()) {
+            // Move to a new segments because the old one can't hold the geometry.
+            segments.emplace_back(vertices.vertexSize(), indices.indexSize());
+        }
+
+        vertices.emplace_back(
+            RasterProgram::layoutVertex({ tlVertex.x, tlVertex.y }, { tlTexture.x, tlTexture.y }));
+        vertices.emplace_back(
+            RasterProgram::layoutVertex({ brVertex.x, tlVertex.y }, { brTexture.x, tlTexture.y }));
+        vertices.emplace_back(
+            RasterProgram::layoutVertex({ tlVertex.x, brVertex.y }, { tlTexture.x, brTexture.y }));
+        vertices.emplace_back(
+            RasterProgram::layoutVertex({ brVertex.x, brVertex.y }, { brTexture.x, brTexture.y }));
+
+        auto& segment = segments.back();
+        assert(segment.vertexLength <= std::numeric_limits<uint16_t>::max());
+        const uint16_t offset = segment.vertexLength;
+
+        // 0, 1, 2
+        // 1, 2, 3
+        indices.emplace_back(offset, offset + 1, offset + 2);
+        indices.emplace_back(offset + 1, offset + 2, offset + 3);
+
+        segment.vertexLength += vertexLength;
+        segment.indexLength += 6;
+    }
+}
+
 bool RasterBucket::hasData() const {
     return !!image;
 }
diff --git a/src/mbgl/renderer/buckets/raster_bucket.hpp b/src/mbgl/renderer/buckets/raster_bucket.hpp
index 0b8432eaaf..3800eadec8 100644
--- a/src/mbgl/renderer/buckets/raster_bucket.hpp
+++ b/src/mbgl/renderer/buckets/raster_bucket.hpp
@@ -5,6 +5,7 @@
 #include <mbgl/gl/vertex_buffer.hpp>
 #include <mbgl/programs/raster_program.hpp>
 #include <mbgl/renderer/bucket.hpp>
+#include <mbgl/renderer/tile_mask.hpp>
 #include <mbgl/util/image.hpp>
 #include <mbgl/util/mat4.hpp>
 #include <mbgl/util/optional.hpp>
@@ -21,8 +22,11 @@ public:
 
     void clear();
     void setImage(std::shared_ptr<PremultipliedImage>);
+    void setMask(TileMask&&);
+
     std::shared_ptr<PremultipliedImage> image;
     optional<gl::Texture> texture;
+    TileMask mask{ { 0, 0, 0 } };
 
     // Bucket specific vertices are used for Image Sources only
     // Raster Tile Sources use the default buffers from Painter
diff --git a/src/mbgl/renderer/layers/render_raster_layer.cpp b/src/mbgl/renderer/layers/render_raster_layer.cpp
index 367fd91fa5..06616d90e5 100644
--- a/src/mbgl/renderer/layers/render_raster_layer.cpp
+++ b/src/mbgl/renderer/layers/render_raster_layer.cpp
@@ -135,10 +135,19 @@ void RenderRasterLayer::render(PaintParameters& parameters, RenderSource* source
             parameters.context.bindTexture(*bucket.texture, 0, gl::TextureFilter::Linear);
             parameters.context.bindTexture(*bucket.texture, 1, gl::TextureFilter::Linear);
 
-            draw(tile.matrix,
-                 parameters.staticData.rasterVertexBuffer,
-                 parameters.staticData.quadTriangleIndexBuffer,
-                 parameters.staticData.rasterSegments);
+            if (bucket.vertexBuffer && bucket.indexBuffer && !bucket.segments.empty()) {
+                // Draw only the parts of the tile that aren't drawn by another tile in the layer.
+                draw(tile.matrix,
+                     *bucket.vertexBuffer,
+                     *bucket.indexBuffer,
+                     bucket.segments);
+            } else {
+                // Draw the full tile.
+                draw(tile.matrix,
+                     parameters.staticData.rasterVertexBuffer,
+                     parameters.staticData.quadTriangleIndexBuffer,
+                     parameters.staticData.rasterSegments);
+            }
         }
     }
 }
diff --git a/src/mbgl/renderer/render_tile.cpp b/src/mbgl/renderer/render_tile.cpp
index 4e924331cc..c9912f0563 100644
--- a/src/mbgl/renderer/render_tile.cpp
+++ b/src/mbgl/renderer/render_tile.cpp
@@ -52,6 +52,10 @@ mat4 RenderTile::translatedClipMatrix(const std::array<float, 2>& translation,
     return translateVtxMatrix(nearClippedMatrix, translation, anchor, state, false);
 }
 
+void RenderTile::setMask(TileMask&& mask) {
+    tile.setMask(std::move(mask));
+}
+
 void RenderTile::startRender(PaintParameters& parameters) {
     tile.upload(parameters.context);
 
diff --git a/src/mbgl/renderer/render_tile.hpp b/src/mbgl/renderer/render_tile.hpp
index d5ed4f0018..b498972f5c 100644
--- a/src/mbgl/renderer/render_tile.hpp
+++ b/src/mbgl/renderer/render_tile.hpp
@@ -4,6 +4,7 @@
 #include <mbgl/util/mat4.hpp>
 #include <mbgl/util/clip_id.hpp>
 #include <mbgl/style/types.hpp>
+#include <mbgl/renderer/tile_mask.hpp>
 
 #include <array>
 
@@ -36,6 +37,7 @@ public:
                               style::TranslateAnchorType anchor,
                               const TransformState&) const;
 
+    void setMask(TileMask&&);
     void startRender(PaintParameters&);
     void finishRender(PaintParameters&);
 
diff --git a/src/mbgl/renderer/sources/render_raster_source.cpp b/src/mbgl/renderer/sources/render_raster_source.cpp
index 910a812f05..cbd874f647 100644
--- a/src/mbgl/renderer/sources/render_raster_source.cpp
+++ b/src/mbgl/renderer/sources/render_raster_source.cpp
@@ -1,6 +1,7 @@
 #include <mbgl/renderer/sources/render_raster_source.hpp>
 #include <mbgl/renderer/render_tile.hpp>
 #include <mbgl/tile/raster_tile.hpp>
+#include <mbgl/algorithm/update_tile_masks.hpp>
 
 namespace mbgl {
 
@@ -57,6 +58,7 @@ void RenderRasterSource::update(Immutable<style::Source::Impl> baseImpl_,
 }
 
 void RenderRasterSource::startRender(PaintParameters& parameters) {
+    algorithm::updateTileMasks(tilePyramid.getRenderTiles());
     tilePyramid.startRender(parameters);
 }
 
diff --git a/src/mbgl/tile/raster_tile.cpp b/src/mbgl/tile/raster_tile.cpp
index 8a92c40e4a..1260fd1edd 100644
--- a/src/mbgl/tile/raster_tile.cpp
+++ b/src/mbgl/tile/raster_tile.cpp
@@ -41,7 +41,7 @@ void RasterTile::setData(std::shared_ptr<const std::string> data,
     worker.invoke(&RasterTileWorker::parse, data);
 }
 
-void RasterTile::onParsed(std::unique_ptr<Bucket> result) {
+void RasterTile::onParsed(std::unique_ptr<RasterBucket> result) {
     bucket = std::move(result);
     loaded = true;
     renderable = bucket ? true : false;
@@ -65,6 +65,12 @@ Bucket* RasterTile::getBucket(const style::Layer::Impl&) const {
     return bucket.get();
 }
 
+void RasterTile::setMask(TileMask&& mask) {
+    if (bucket) {
+        bucket->setMask(std::move(mask));
+    }
+}
+
 void RasterTile::setNecessity(Necessity necessity) {
     loader.setNecessity(necessity);
 }
diff --git a/src/mbgl/tile/raster_tile.hpp b/src/mbgl/tile/raster_tile.hpp
index 51075a2dbc..28a27b2b37 100644
--- a/src/mbgl/tile/raster_tile.hpp
+++ b/src/mbgl/tile/raster_tile.hpp
@@ -9,6 +9,7 @@ namespace mbgl {
 
 class Tileset;
 class TileParameters;
+class RasterBucket;
 
 namespace style {
 class Layer;
@@ -33,7 +34,9 @@ public:
     void upload(gl::Context&) override;
     Bucket* getBucket(const style::Layer::Impl&) const override;
 
-    void onParsed(std::unique_ptr<Bucket> result);
+    void setMask(TileMask&&) override;
+
+    void onParsed(std::unique_ptr<RasterBucket> result);
     void onError(std::exception_ptr);
 
 private:
@@ -44,7 +47,7 @@ private:
 
     // Contains the Bucket object for the tile. Buckets are render
     // objects and they get added by tile parsing operations.
-    std::unique_ptr<Bucket> bucket;
+    std::unique_ptr<RasterBucket> bucket;
 };
 
 } // namespace mbgl
diff --git a/src/mbgl/tile/tile.hpp b/src/mbgl/tile/tile.hpp
index 1898f76849..a1ab6a84b7 100644
--- a/src/mbgl/tile/tile.hpp
+++ b/src/mbgl/tile/tile.hpp
@@ -6,6 +6,7 @@
 #include <mbgl/util/feature.hpp>
 #include <mbgl/util/tile_coordinate.hpp>
 #include <mbgl/tile/tile_id.hpp>
+#include <mbgl/renderer/tile_mask.hpp>
 #include <mbgl/renderer/bucket.hpp>
 #include <mbgl/tile/geometry_tile_data.hpp>
 #include <mbgl/storage/resource.hpp>
@@ -54,6 +55,7 @@ public:
 
     virtual void setPlacementConfig(const PlacementConfig&) {}
     virtual void setLayers(const std::vector<Immutable<style::Layer::Impl>>&) {}
+    virtual void setMask(TileMask&&) {}
 
     virtual void queryRenderedFeatures(
             std::unordered_map<std::string, std::vector<Feature>>& result,
diff --git a/test/gl/bucket.test.cpp b/test/gl/bucket.test.cpp
index 7ff67f40d0..afdbd2a29b 100644
--- a/test/gl/bucket.test.cpp
+++ b/test/gl/bucket.test.cpp
@@ -12,6 +12,26 @@
 
 #include <mbgl/map/mode.hpp>
 
+namespace mbgl {
+
+template <class Attributes>
+bool operator==(const Segment<Attributes>& lhs, const Segment<Attributes>& rhs) {
+    return std::tie(lhs.vertexOffset, lhs.indexOffset, lhs.vertexLength, lhs.indexLength) ==
+           std::tie(rhs.vertexOffset, rhs.indexOffset, rhs.vertexLength, rhs.indexLength);
+}
+
+namespace gl {
+namespace detail {
+
+template <class A1, class A2>
+bool operator==(const Vertex<A1, A2>& lhs, const Vertex<A1, A2>& rhs) {
+    return std::tie(lhs.a1, lhs.a2) == std::tie(rhs.a1, rhs.a2);
+}
+
+} // namespace detail
+} // namespace gl
+} // namespace mbgl
+
 using namespace mbgl;
 
 namespace {
@@ -114,3 +134,142 @@ TEST(Buckets, RasterBucket) {
     bucket.clear();
     ASSERT_TRUE(bucket.needsUpload());
 }
+
+TEST(Buckets, RasterBucketMaskEmpty) {
+    RasterBucket bucket{ nullptr };
+    bucket.setMask({});
+    EXPECT_EQ((std::vector<RasterLayoutVertex>{}), bucket.vertices.vector());
+    EXPECT_EQ((std::vector<uint16_t>{}), bucket.indices.vector());
+    SegmentVector<RasterAttributes> expectedSegments;
+    expectedSegments.emplace_back(0, 0, 0, 0);
+    EXPECT_EQ(expectedSegments, bucket.segments);
+}
+
+TEST(Buckets, RasterBucketMaskNoChildren) {
+    RasterBucket bucket{ nullptr };
+    bucket.setMask({ CanonicalTileID{ 0, 0, 0 } });
+
+    // A mask of 0/0/0 doesn't produce buffers since we're instead using the global shared buffers.
+    EXPECT_EQ((std::vector<RasterLayoutVertex>{}), bucket.vertices.vector());
+    EXPECT_EQ((std::vector<uint16_t>{}), bucket.indices.vector());
+    EXPECT_EQ((SegmentVector<RasterAttributes>{}), bucket.segments);
+}
+
+ TEST(Buckets, RasterBucketMaskTwoChildren) {
+     RasterBucket bucket{ nullptr };
+     bucket.setMask(
+         { CanonicalTileID{ 1, 0, 0 }, CanonicalTileID{ 1, 1, 1 } });
+
+     EXPECT_EQ(
+         (std::vector<RasterLayoutVertex>{
+             // 1/0/1
+             RasterProgram::layoutVertex({ 0, 0 }, { 0, 0 }),
+             RasterProgram::layoutVertex({ 4096, 0 }, { 16384, 0 }),
+             RasterProgram::layoutVertex({ 0, 4096 }, { 0, 16384 }),
+             RasterProgram::layoutVertex({ 4096, 4096 }, { 16384, 16384 }),
+
+             // 1/1/1
+             RasterProgram::layoutVertex({ 4096, 4096 }, { 16384, 16384 }),
+             RasterProgram::layoutVertex({ 8192, 4096 }, { 32768, 16384 }),
+             RasterProgram::layoutVertex({ 4096, 8192 }, { 16384, 32768 }),
+             RasterProgram::layoutVertex({ 8192, 8192 }, { 32768, 32768 }),
+         }),
+         bucket.vertices.vector());
+
+     EXPECT_EQ(
+         (std::vector<uint16_t>{
+             // 1/0/1
+             0, 1, 2,
+             1, 2, 3,
+
+             // 1/1/1
+             4, 5, 6,
+             5, 6, 7,
+         }),
+         bucket.indices.vector());
+
+
+     SegmentVector<RasterAttributes> expectedSegments;
+     expectedSegments.emplace_back(0, 0, 8, 12);
+     EXPECT_EQ(expectedSegments, bucket.segments);
+ }
+
+ TEST(Buckets, RasterBucketMaskComplex) {
+     RasterBucket bucket{ nullptr };
+     bucket.setMask(
+         { CanonicalTileID{ 1, 0, 1 }, CanonicalTileID{ 1, 1, 0 }, CanonicalTileID{ 2, 2, 3 },
+           CanonicalTileID{ 2, 3, 2 }, CanonicalTileID{ 3, 6, 7 }, CanonicalTileID{ 3, 7, 6 } });
+
+     EXPECT_EQ(
+         (std::vector<RasterLayoutVertex>{
+             // 1/0/1
+             RasterProgram::layoutVertex({ 0, 4096 }, { 0, 16384 }),
+             RasterProgram::layoutVertex({ 4096, 4096 }, { 16384, 16384 }),
+             RasterProgram::layoutVertex({ 0, 8192 }, { 0, 32768 }),
+             RasterProgram::layoutVertex({ 4096, 8192 }, { 16384, 32768 }),
+
+             // 1/1/0
+             RasterProgram::layoutVertex({ 4096, 0 }, { 16384, 0 }),
+             RasterProgram::layoutVertex({ 8192, 0 }, { 32768, 0 }),
+             RasterProgram::layoutVertex({ 4096, 4096 }, { 16384, 16384 }),
+             RasterProgram::layoutVertex({ 8192, 4096 }, { 32768, 16384 }),
+
+             // 2/2/3
+             RasterProgram::layoutVertex({ 4096, 6144 }, { 16384, 24576 }),
+             RasterProgram::layoutVertex({ 6144, 6144 }, { 24576, 24576 }),
+             RasterProgram::layoutVertex({ 4096, 8192 }, { 16384, 32768 }),
+             RasterProgram::layoutVertex({ 6144, 8192 }, { 24576, 32768 }),
+
+             // 2/3/2
+             RasterProgram::layoutVertex({ 6144, 4096 }, { 24576, 16384 }),
+             RasterProgram::layoutVertex({ 8192, 4096 }, { 32768, 16384 }),
+             RasterProgram::layoutVertex({ 6144, 6144 }, { 24576, 24576 }),
+             RasterProgram::layoutVertex({ 8192, 6144 }, { 32768, 24576 }),
+
+             // 3/6/7
+             RasterProgram::layoutVertex({ 6144, 7168 }, { 24576, 28672 }),
+             RasterProgram::layoutVertex({ 7168, 7168 }, { 28672, 28672 }),
+             RasterProgram::layoutVertex({ 6144, 8192 }, { 24576, 32768 }),
+             RasterProgram::layoutVertex({ 7168, 8192 }, { 28672, 32768 }),
+
+             // 3/7/6
+             RasterProgram::layoutVertex({ 7168, 6144 }, { 28672, 24576 }),
+             RasterProgram::layoutVertex({ 8192, 6144 }, { 32768, 24576 }),
+             RasterProgram::layoutVertex({ 7168, 7168 }, { 28672, 28672 }),
+             RasterProgram::layoutVertex({ 8192, 7168 }, { 32768, 28672 }),
+         }),
+         bucket.vertices.vector());
+
+     EXPECT_EQ(
+         (std::vector<uint16_t>{
+             // 1/0/1
+             0, 1, 2,
+             1, 2, 3,
+
+             // 1/1/0
+             4, 5, 6,
+             5, 6, 7,
+
+             // 2/2/3
+             8, 9, 10,
+             9, 10, 11,
+
+             // 2/3/2
+             12, 13, 14,
+             13, 14, 15,
+
+             // 3/6/7
+             16, 17, 18,
+             17, 18, 19,
+
+             // 3/7/6
+             20, 21, 22,
+             21, 22, 23,
+         }),
+         bucket.indices.vector());
+
+
+     SegmentVector<RasterAttributes> expectedSegments;
+     expectedSegments.emplace_back(0, 0, 24, 36);
+     EXPECT_EQ(expectedSegments, bucket.segments);
+ }
-- 
cgit v1.2.1