[core, ios, macos, android, node] Heatmap layer (#11046)

Co-Authored-By: Konstantin Käfer <mail@kkaefer.com>
Co-Authored-By: Anand Thakker <anandthakker@users.noreply.github.com>
Co-Authored-By: Minh Nguyễn <1ec5@users.noreply.github.com>

6 files changed, 377 insertions, 1 deletions

diff --git a/src/mbgl/renderer/buckets/heatmap_bucket.cpp b/src/mbgl/renderer/buckets/heatmap_bucket.cpp
new file mode 100644
index 0000000000..a185e04ad2
--- /dev/null
+++ b/src/mbgl/renderer/buckets/heatmap_bucket.cpp
@@ -0,0 +1,98 @@
+#include <mbgl/renderer/buckets/heatmap_bucket.hpp>
+#include <mbgl/renderer/bucket_parameters.hpp>
+#include <mbgl/programs/heatmap_program.hpp>
+#include <mbgl/style/layers/heatmap_layer_impl.hpp>
+#include <mbgl/renderer/layers/render_heatmap_layer.hpp>
+#include <mbgl/util/constants.hpp>
+#include <mbgl/util/math.hpp>
+
+namespace mbgl {
+
+using namespace style;
+
+HeatmapBucket::HeatmapBucket(const BucketParameters& parameters, const std::vector<const RenderLayer*>& layers)
+    : mode(parameters.mode) {
+    for (const auto& layer : layers) {
+        paintPropertyBinders.emplace(
+            std::piecewise_construct,
+            std::forward_as_tuple(layer->getID()),
+            std::forward_as_tuple(
+                layer->as<RenderHeatmapLayer>()->evaluated,
+                parameters.tileID.overscaledZ));
+    }
+}
+
+void HeatmapBucket::upload(gl::Context& context) {
+    vertexBuffer = context.createVertexBuffer(std::move(vertices));
+    indexBuffer = context.createIndexBuffer(std::move(triangles));
+
+    for (auto& pair : paintPropertyBinders) {
+        pair.second.upload(context);
+    }
+
+    uploaded = true;
+}
+
+bool HeatmapBucket::hasData() const {
+    return !segments.empty();
+}
+
+void HeatmapBucket::addFeature(const GeometryTileFeature& feature,
+                              const GeometryCollection& geometry) {
+    constexpr const uint16_t vertexLength = 4;
+
+    for (auto& points : geometry) {
+        for(auto& point : points) {
+            auto x = point.x;
+            auto y = point.y;
+
+            // Do not include points that are outside the tile boundaries.
+            // Include all points in Still mode. You need to include points from
+            // neighbouring tiles so that they are not clipped at tile boundaries.
+            if ((mode == MapMode::Continuous) &&
+                (x < 0 || x >= util::EXTENT || y < 0 || y >= util::EXTENT)) continue;
+
+            if (segments.empty() || 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(), triangles.indexSize());
+            }
+
+            // this geometry will be of the Point type, and we'll derive
+            // two triangles from it.
+            //
+            // ┌─────────┐
+            // │ 4     3 │
+            // │         │
+            // │ 1     2 │
+            // └─────────┘
+            //
+            vertices.emplace_back(HeatmapProgram::vertex(point, -1, -1)); // 1
+            vertices.emplace_back(HeatmapProgram::vertex(point,  1, -1)); // 2
+            vertices.emplace_back(HeatmapProgram::vertex(point,  1,  1)); // 3
+            vertices.emplace_back(HeatmapProgram::vertex(point, -1,  1)); // 4
+
+            auto& segment = segments.back();
+            assert(segment.vertexLength <= std::numeric_limits<uint16_t>::max());
+            uint16_t index = segment.vertexLength;
+
+            // 1, 2, 3
+            // 1, 4, 3
+            triangles.emplace_back(index, index + 1, index + 2);
+            triangles.emplace_back(index, index + 3, index + 2);
+
+            segment.vertexLength += vertexLength;
+            segment.indexLength += 6;
+        }
+    }
+
+    for (auto& pair : paintPropertyBinders) {
+        pair.second.populateVertexVectors(feature, vertices.vertexSize());
+    }
+}
+
+float HeatmapBucket::getQueryRadius(const RenderLayer& layer) const {
+    (void)layer;
+    return 0;
+}
+
+} // namespace mbgl
diff --git a/src/mbgl/renderer/buckets/heatmap_bucket.hpp b/src/mbgl/renderer/buckets/heatmap_bucket.hpp
new file mode 100644
index 0000000000..3b9f1edb81
--- /dev/null
+++ b/src/mbgl/renderer/buckets/heatmap_bucket.hpp
@@ -0,0 +1,40 @@
+#pragma once
+
+#include <mbgl/renderer/bucket.hpp>
+#include <mbgl/map/mode.hpp>
+#include <mbgl/tile/geometry_tile_data.hpp>
+#include <mbgl/gl/vertex_buffer.hpp>
+#include <mbgl/gl/index_buffer.hpp>
+#include <mbgl/programs/segment.hpp>
+#include <mbgl/programs/heatmap_program.hpp>
+#include <mbgl/style/layers/heatmap_layer_properties.hpp>
+
+namespace mbgl {
+
+class BucketParameters;
+
+class HeatmapBucket : public Bucket {
+public:
+    HeatmapBucket(const BucketParameters&, const std::vector<const RenderLayer*>&);
+
+    void addFeature(const GeometryTileFeature&,
+                    const GeometryCollection&) override;
+    bool hasData() const override;
+
+    void upload(gl::Context&) override;
+
+    float getQueryRadius(const RenderLayer&) const override;
+
+    gl::VertexVector<HeatmapLayoutVertex> vertices;
+    gl::IndexVector<gl::Triangles> triangles;
+    SegmentVector<HeatmapAttributes> segments;
+
+    optional<gl::VertexBuffer<HeatmapLayoutVertex>> vertexBuffer;
+    optional<gl::IndexBuffer<gl::Triangles>> indexBuffer;
+
+    std::map<std::string, HeatmapProgram::PaintPropertyBinders> paintPropertyBinders;
+
+    const MapMode mode;
+};
+
+} // namespace mbgl
diff --git a/src/mbgl/renderer/layers/render_heatmap_layer.cpp b/src/mbgl/renderer/layers/render_heatmap_layer.cpp
new file mode 100644
index 0000000000..0f9e3239ef
--- /dev/null
+++ b/src/mbgl/renderer/layers/render_heatmap_layer.cpp
@@ -0,0 +1,178 @@
+#include <mbgl/renderer/layers/render_heatmap_layer.hpp>
+#include <mbgl/renderer/buckets/heatmap_bucket.hpp>
+#include <mbgl/renderer/render_tile.hpp>
+#include <mbgl/renderer/paint_parameters.hpp>
+#include <mbgl/renderer/render_static_data.hpp>
+#include <mbgl/programs/programs.hpp>
+#include <mbgl/programs/heatmap_program.hpp>
+#include <mbgl/tile/tile.hpp>
+#include <mbgl/style/layers/heatmap_layer.hpp>
+#include <mbgl/style/layers/heatmap_layer_impl.hpp>
+#include <mbgl/geometry/feature_index.hpp>
+#include <mbgl/util/math.hpp>
+#include <mbgl/util/intersection_tests.hpp>
+
+namespace mbgl {
+
+using namespace style;
+
+RenderHeatmapLayer::RenderHeatmapLayer(Immutable<style::HeatmapLayer::Impl> _impl)
+    : RenderLayer(style::LayerType::Heatmap, _impl),
+    unevaluated(impl().paint.untransitioned()), colorRamp({256, 1}) {
+}
+
+const style::HeatmapLayer::Impl& RenderHeatmapLayer::impl() const {
+    return static_cast<const style::HeatmapLayer::Impl&>(*baseImpl);
+}
+
+std::unique_ptr<Bucket> RenderHeatmapLayer::createBucket(const BucketParameters& parameters, const std::vector<const RenderLayer*>& layers) const {
+    return std::make_unique<HeatmapBucket>(parameters, layers);
+}
+
+void RenderHeatmapLayer::transition(const TransitionParameters& parameters) {
+    unevaluated = impl().paint.transitioned(parameters, std::move(unevaluated));
+}
+
+void RenderHeatmapLayer::evaluate(const PropertyEvaluationParameters& parameters) {
+    evaluated = unevaluated.evaluate(parameters);
+
+    passes = (evaluated.get<style::HeatmapOpacity>() > 0)
+            ? (RenderPass::Translucent | RenderPass::Pass3D)
+            : RenderPass::None;
+}
+
+bool RenderHeatmapLayer::hasTransition() const {
+    return unevaluated.hasTransition();
+}
+
+void RenderHeatmapLayer::render(PaintParameters& parameters, RenderSource*) {
+    if (parameters.pass == RenderPass::Opaque) {
+        return;
+    }
+
+    if (parameters.pass == RenderPass::Pass3D) {
+        const auto& viewportSize = parameters.staticData.backendSize;
+        const auto size = Size{viewportSize.width / 4, viewportSize.height / 4};
+
+        if (!renderTexture || renderTexture->getSize() != size) {
+            if (parameters.context.supportsHalfFloatTextures) {
+                renderTexture = OffscreenTexture(parameters.context, size, gl::TextureType::HalfFloat);
+
+                try {
+                    renderTexture->bind();
+                } catch (const std::runtime_error& ex) {
+                    // can't render to a half-float texture; falling back to unsigned byte one
+                    renderTexture = nullopt;
+                    parameters.context.supportsHalfFloatTextures = false;
+                }
+            }
+
+            if (!renderTexture) {
+                renderTexture = OffscreenTexture(parameters.context, size, gl::TextureType::UnsignedByte);
+                renderTexture->bind();
+            }
+
+        } else {
+            renderTexture->bind();
+        }
+
+        if (!colorRampTexture) {
+            colorRampTexture = parameters.context.createTexture(colorRamp, 1, gl::TextureType::UnsignedByte);
+        }
+
+        parameters.context.clear(Color{ 0.0f, 0.0f, 0.0f, 1.0f }, {}, {});
+
+        for (const RenderTile& tile : renderTiles) {
+            assert(dynamic_cast<HeatmapBucket*>(tile.tile.getBucket(*baseImpl)));
+            HeatmapBucket& bucket = *reinterpret_cast<HeatmapBucket*>(tile.tile.getBucket(*baseImpl));
+
+            const auto extrudeScale = tile.id.pixelsToTileUnits(1, parameters.state.getZoom());
+
+            const auto stencilMode = parameters.mapMode != MapMode::Continuous
+                ? parameters.stencilModeForClipping(tile.clip)
+                : gl::StencilMode::disabled();
+
+            parameters.programs.heatmap.get(evaluated).draw(
+                parameters.context,
+                gl::Triangles(),
+                parameters.depthModeForSublayer(0, gl::DepthMode::ReadOnly),
+                stencilMode,
+                gl::ColorMode::additive(),
+                HeatmapProgram::UniformValues {
+                    uniforms::u_intensity::Value{evaluated.get<style::HeatmapIntensity>()},
+                    uniforms::u_matrix::Value{tile.matrix},
+                    uniforms::heatmap::u_extrude_scale::Value{extrudeScale}
+                },
+                *bucket.vertexBuffer,
+                *bucket.indexBuffer,
+                bucket.segments,
+                bucket.paintPropertyBinders.at(getID()),
+                evaluated,
+                parameters.state.getZoom(),
+                getID()
+            );
+        }
+
+    } else if (parameters.pass == RenderPass::Translucent) {
+        parameters.context.bindTexture(renderTexture->getTexture(), 0, gl::TextureFilter::Linear);
+        parameters.context.bindTexture(*colorRampTexture, 1, gl::TextureFilter::Linear);
+
+        const auto& size = parameters.staticData.backendSize;
+
+        mat4 viewportMat;
+        matrix::ortho(viewportMat, 0, size.width, size.height, 0, 0, 1);
+
+        const Properties<>::PossiblyEvaluated properties;
+
+        parameters.programs.heatmapTexture.draw(
+            parameters.context, gl::Triangles(), gl::DepthMode::disabled(),
+            gl::StencilMode::disabled(), parameters.colorModeForRenderPass(),
+            HeatmapTextureProgram::UniformValues{
+                uniforms::u_matrix::Value{ viewportMat }, uniforms::u_world::Value{ size },
+                uniforms::u_image::Value{ 0 },
+                uniforms::u_color_ramp::Value{ 1 },
+                uniforms::u_opacity::Value{ evaluated.get<HeatmapOpacity>() } },
+            parameters.staticData.extrusionTextureVertexBuffer,
+            parameters.staticData.quadTriangleIndexBuffer,
+            parameters.staticData.extrusionTextureSegments,
+            HeatmapTextureProgram::PaintPropertyBinders{ properties, 0 }, properties,
+            parameters.state.getZoom(), getID());
+    }
+}
+
+void RenderHeatmapLayer::updateColorRamp() {
+    auto colorValue = unevaluated.get<HeatmapColor>().getValue();
+    if (colorValue.isUndefined()) {
+        colorValue = HeatmapLayer::getDefaultHeatmapColor();
+    }
+
+    const auto length = colorRamp.bytes();
+
+    for (uint32_t i = 0; i < length; i += 4) {
+        const auto color = colorValue.evaluate(static_cast<double>(i) / length);
+        colorRamp.data[i + 0] = std::floor(color.r * 255);
+        colorRamp.data[i + 1] = std::floor(color.g * 255);
+        colorRamp.data[i + 2] = std::floor(color.b * 255);
+        colorRamp.data[i + 3] = std::floor(color.a * 255);
+    }
+
+    if (colorRampTexture) {
+        colorRampTexture = nullopt;
+    }
+}
+
+bool RenderHeatmapLayer::queryIntersectsFeature(
+        const GeometryCoordinates& queryGeometry,
+        const GeometryTileFeature& feature,
+        const float zoom,
+        const float bearing,
+        const float pixelsToTileUnits) const {
+    (void) queryGeometry;
+    (void) feature;
+    (void) zoom;
+    (void) bearing;
+    (void) pixelsToTileUnits;
+    return false;
+}
+
+} // namespace mbgl
diff --git a/src/mbgl/renderer/layers/render_heatmap_layer.hpp b/src/mbgl/renderer/layers/render_heatmap_layer.hpp
new file mode 100644
index 0000000000..3f0b1f91b4
--- /dev/null
+++ b/src/mbgl/renderer/layers/render_heatmap_layer.hpp
@@ -0,0 +1,48 @@
+#pragma once
+
+#include <mbgl/renderer/render_layer.hpp>
+#include <mbgl/style/layers/heatmap_layer_impl.hpp>
+#include <mbgl/style/layers/heatmap_layer_properties.hpp>
+#include <mbgl/util/optional.hpp>
+#include <mbgl/util/offscreen_texture.hpp>
+
+namespace mbgl {
+
+class RenderHeatmapLayer: public RenderLayer {
+public:
+    RenderHeatmapLayer(Immutable<style::HeatmapLayer::Impl>);
+    ~RenderHeatmapLayer() final = default;
+
+    void transition(const TransitionParameters&) override;
+    void evaluate(const PropertyEvaluationParameters&) override;
+    bool hasTransition() const override;
+    void render(PaintParameters&, RenderSource*) override;
+
+    bool queryIntersectsFeature(
+            const GeometryCoordinates&,
+            const GeometryTileFeature&,
+            const float,
+            const float,
+            const float) const override;
+
+    void updateColorRamp();
+
+    std::unique_ptr<Bucket> createBucket(const BucketParameters&, const std::vector<const RenderLayer*>&) const override;
+
+    // Paint properties
+    style::HeatmapPaintProperties::Unevaluated unevaluated;
+    style::HeatmapPaintProperties::PossiblyEvaluated evaluated;
+
+    const style::HeatmapLayer::Impl& impl() const;
+
+    PremultipliedImage colorRamp;
+    optional<OffscreenTexture> renderTexture;
+    optional<gl::Texture> colorRampTexture;
+};
+
+template <>
+inline bool RenderLayer::is<RenderHeatmapLayer>() const {
+    return type == style::LayerType::Heatmap;
+}
+
+} // namespace mbgl
diff --git a/src/mbgl/renderer/render_layer.cpp b/src/mbgl/renderer/render_layer.cpp
index 248905f834..bcdc175f14 100644
--- a/src/mbgl/renderer/render_layer.cpp
+++ b/src/mbgl/renderer/render_layer.cpp
@@ -8,6 +8,7 @@
 #include <mbgl/renderer/layers/render_line_layer.hpp>
 #include <mbgl/renderer/layers/render_raster_layer.hpp>
 #include <mbgl/renderer/layers/render_symbol_layer.hpp>
+#include <mbgl/renderer/layers/render_heatmap_layer.hpp>
 #include <mbgl/style/types.hpp>
 #include <mbgl/renderer/render_tile.hpp>
 
@@ -35,6 +36,8 @@ std::unique_ptr<RenderLayer> RenderLayer::create(Immutable<Layer::Impl> impl) {
         return std::make_unique<RenderCustomLayer>(staticImmutableCast<CustomLayer::Impl>(impl));
     case LayerType::FillExtrusion:
         return std::make_unique<RenderFillExtrusionLayer>(staticImmutableCast<FillExtrusionLayer::Impl>(impl));
+    case LayerType::Heatmap:
+        return std::make_unique<RenderHeatmapLayer>(staticImmutableCast<HeatmapLayer::Impl>(impl));
     }
 
     // Not reachable, but placate GCC.
diff --git a/src/mbgl/renderer/renderer_impl.cpp b/src/mbgl/renderer/renderer_impl.cpp
index 26a07bb093..2ac714e122 100644
--- a/src/mbgl/renderer/renderer_impl.cpp
+++ b/src/mbgl/renderer/renderer_impl.cpp
@@ -14,6 +14,7 @@
 #include <mbgl/renderer/layers/render_background_layer.hpp>
 #include <mbgl/renderer/layers/render_custom_layer.hpp>
 #include <mbgl/renderer/layers/render_fill_extrusion_layer.hpp>
+#include <mbgl/renderer/layers/render_heatmap_layer.hpp>
 #include <mbgl/renderer/layers/render_hillshade_layer.hpp>
 #include <mbgl/renderer/style_diff.hpp>
 #include <mbgl/renderer/query.hpp>
@@ -185,6 +186,10 @@ void Renderer::Impl::render(const UpdateParameters& updateParameters) {
 
         if (layerAdded || layerChanged) {
             layer.transition(transitionParameters);
+
+            if (layer.is<RenderHeatmapLayer>()) {
+                layer.as<RenderHeatmapLayer>()->updateColorRamp();
+            }
         }
 
         if (layerAdded || layerChanged || zoomChanged || layer.hasTransition()) {
@@ -290,7 +295,11 @@ void Renderer::Impl::render(const UpdateParameters& updateParameters) {
         RenderLayer* layer = getRenderLayer(layerImpl->id);
         assert(layer);
 
-        if (!parameters.staticData.has3D && (layer->is<RenderFillExtrusionLayer>() || layer->is<RenderHillshadeLayer>())) {
+        if (!parameters.staticData.has3D && (
+                layer->is<RenderFillExtrusionLayer>() ||
+                layer->is<RenderHillshadeLayer>() ||
+                layer->is<RenderHeatmapLayer>())) {
+
             parameters.staticData.has3D = true;
         }