Initial implementation of debug collision circles

 - Naive copy-pasting of collision box code: should factor out more of the commonalities
 - "Used circle" logic seems to be working correctly
 - Rendering seems to break if there are too many circles (probably something to do with segment logic?)
[skip ci]

11 files changed, 187 insertions, 38 deletions

diff --git a/cmake/core-files.cmake b/cmake/core-files.cmake
index f9c3614f10..75d05317ef 100644
--- a/cmake/core-files.cmake
+++ b/cmake/core-files.cmake
@@ -255,6 +255,8 @@ set(MBGL_CORE_FILES
     src/mbgl/shaders/circle.hpp
     src/mbgl/shaders/collision_box.cpp
     src/mbgl/shaders/collision_box.hpp
+    src/mbgl/shaders/collision_circle.cpp
+    src/mbgl/shaders/collision_circle.hpp
     src/mbgl/shaders/debug.cpp
     src/mbgl/shaders/debug.hpp
     src/mbgl/shaders/extrusion_texture.cpp
diff --git a/src/mbgl/layout/symbol_instance.cpp b/src/mbgl/layout/symbol_instance.cpp
index 901200731e..1e67a96421 100644
--- a/src/mbgl/layout/symbol_instance.cpp
+++ b/src/mbgl/layout/symbol_instance.cpp
@@ -19,7 +19,7 @@ SymbolInstance::SymbolInstance(Anchor& anchor_,
                                const std::array<float, 2> textOffset_,
                                const float iconBoxScale,
                                const float iconPadding,
-                               const SymbolPlacementType iconPlacement,
+                               const SymbolPlacementType, // TODO: vestigial?
                                const std::array<float, 2> iconOffset_,
                                const GlyphPositionMap& positions,
                                const IndexedSubfeature& indexedFeature,
@@ -33,7 +33,7 @@ SymbolInstance::SymbolInstance(Anchor& anchor_,
 
     // Create the collision features that will be used to check whether this symbol instance can be placed
     textCollisionFeature(line_, anchor, shapedTextOrientations.second ?: shapedTextOrientations.first, textBoxScale, textPadding, textPlacement, indexedFeature),
-    iconCollisionFeature(line_, anchor, shapedIcon, iconBoxScale, iconPadding, iconPlacement, indexedFeature),
+    iconCollisionFeature(line_, anchor, shapedIcon, iconBoxScale, iconPadding, SymbolPlacementType::Point, indexedFeature),
     featureIndex(featureIndex_),
     textOffset(textOffset_),
     iconOffset(iconOffset_),
diff --git a/src/mbgl/layout/symbol_layout.cpp b/src/mbgl/layout/symbol_layout.cpp
index 60b1c61d20..358063021d 100644
--- a/src/mbgl/layout/symbol_layout.cpp
+++ b/src/mbgl/layout/symbol_layout.cpp
@@ -580,10 +580,11 @@ void SymbolLayout::addToDebugBuffers(CollisionTile& collisionTile, SymbolBucket&
 
     const float yStretch = collisionTile.yStretch;
 
-    auto& collisionBox = bucket.collisionBox;
-
     for (const SymbolInstance &symbolInstance : symbolInstances) {
         auto populateCollisionBox = [&](const auto& feature) {
+            SymbolBucket::CollisionBuffer& collisionBuffer = feature.alongLine ?
+                static_cast<SymbolBucket::CollisionBuffer&>(bucket.collisionCircle) :
+                static_cast<SymbolBucket::CollisionBuffer&>(bucket.collisionBox);
             for (const CollisionBox &box : feature.boxes) {
                 auto& anchor = box.anchor;
 
@@ -593,30 +594,35 @@ void SymbolLayout::addToDebugBuffers(CollisionTile& collisionTile, SymbolBucket&
                 Point<float> br{box.x2, box.y2 * yStretch};
 
                 static constexpr std::size_t vertexLength = 4;
-                static constexpr std::size_t indexLength = 8;
+                const std::size_t indexLength = feature.alongLine ? 4 : 8;
 
-                if (collisionBox.segments.empty() || collisionBox.segments.back().vertexLength + vertexLength > std::numeric_limits<uint16_t>::max()) {
-                    collisionBox.segments.emplace_back(collisionBox.vertices.vertexSize(), collisionBox.lines.indexSize());
+                if (collisionBuffer.segments.empty() || collisionBuffer.segments.back().vertexLength + vertexLength > std::numeric_limits<uint16_t>::max()) {
+                    collisionBuffer.segments.emplace_back(collisionBuffer.vertices.vertexSize(), bucket.collisionBox.lines.indexSize());
                 }
 
-                auto& segment = collisionBox.segments.back();
+                auto& segment = collisionBuffer.segments.back();
                 uint16_t index = segment.vertexLength;
 
-                collisionBox.vertices.emplace_back(CollisionBoxProgram::vertex(anchor, symbolInstance.anchor.point, tl));
-                collisionBox.vertices.emplace_back(CollisionBoxProgram::vertex(anchor, symbolInstance.anchor.point, tr));
-                collisionBox.vertices.emplace_back(CollisionBoxProgram::vertex(anchor, symbolInstance.anchor.point, br));
-                collisionBox.vertices.emplace_back(CollisionBoxProgram::vertex(anchor, symbolInstance.anchor.point, bl));
+                collisionBuffer.vertices.emplace_back(CollisionBoxProgram::vertex(anchor, symbolInstance.anchor.point, tl));
+                collisionBuffer.vertices.emplace_back(CollisionBoxProgram::vertex(anchor, symbolInstance.anchor.point, tr));
+                collisionBuffer.vertices.emplace_back(CollisionBoxProgram::vertex(anchor, symbolInstance.anchor.point, br));
+                collisionBuffer.vertices.emplace_back(CollisionBoxProgram::vertex(anchor, symbolInstance.anchor.point, bl));
 
                 auto opacityVertex = CollisionBoxOpacityAttributes::vertex(true, false); // TODO
-                collisionBox.opacityVertices.emplace_back(opacityVertex);
-                collisionBox.opacityVertices.emplace_back(opacityVertex);
-                collisionBox.opacityVertices.emplace_back(opacityVertex);
-                collisionBox.opacityVertices.emplace_back(opacityVertex);
-
-                collisionBox.lines.emplace_back(index + 0, index + 1);
-                collisionBox.lines.emplace_back(index + 1, index + 2);
-                collisionBox.lines.emplace_back(index + 2, index + 3);
-                collisionBox.lines.emplace_back(index + 3, index + 0);
+                collisionBuffer.opacityVertices.emplace_back(opacityVertex);
+                collisionBuffer.opacityVertices.emplace_back(opacityVertex);
+                collisionBuffer.opacityVertices.emplace_back(opacityVertex);
+                collisionBuffer.opacityVertices.emplace_back(opacityVertex);
+
+                if (feature.alongLine) {
+                    bucket.collisionCircle.triangles.emplace_back(index, index + 1, index + 2);
+                    bucket.collisionCircle.triangles.emplace_back(index, index + 2, index + 3);
+                } else {
+                    bucket.collisionBox.lines.emplace_back(index + 0, index + 1);
+                    bucket.collisionBox.lines.emplace_back(index + 1, index + 2);
+                    bucket.collisionBox.lines.emplace_back(index + 2, index + 3);
+                    bucket.collisionBox.lines.emplace_back(index + 3, index + 0);
+                }
 
                 segment.vertexLength += vertexLength;
                 segment.indexLength += indexLength;
diff --git a/src/mbgl/programs/collision_box_program.hpp b/src/mbgl/programs/collision_box_program.hpp
index 2547da9f18..062a7d8d61 100644
--- a/src/mbgl/programs/collision_box_program.hpp
+++ b/src/mbgl/programs/collision_box_program.hpp
@@ -4,6 +4,7 @@
 #include <mbgl/programs/attributes.hpp>
 #include <mbgl/programs/uniforms.hpp>
 #include <mbgl/shaders/collision_box.hpp>
+#include <mbgl/shaders/collision_circle.hpp>
 #include <mbgl/style/properties.hpp>
 #include <mbgl/util/geometry.hpp>
 
@@ -100,6 +101,83 @@ public:
 
 };
 
+
+class CollisionCircleProgram : public Program<
+    shaders::collision_circle,
+    gl::Triangle,
+    gl::ConcatenateAttributes<CollisionBoxLayoutAttributes, CollisionBoxOpacityAttributes>,
+    gl::Uniforms<
+        uniforms::u_matrix,
+        uniforms::u_extrude_scale,
+        uniforms::u_camera_to_center_distance>,
+    style::Properties<>>
+{
+public:
+    using Program::Program;
+
+    static CollisionBoxLayoutAttributes::Vertex vertex(Point<float> a, Point<float> anchor, Point<float> o) {
+        return CollisionBoxLayoutAttributes::Vertex {
+            {{
+                static_cast<int16_t>(a.x),
+                static_cast<int16_t>(a.y)
+            }},
+            {{
+                static_cast<int16_t>(anchor.x),
+                static_cast<int16_t>(anchor.y)
+            }},
+            {{
+                static_cast<int16_t>(::round(o.x)),
+                static_cast<int16_t>(::round(o.y))
+            }}
+        };
+    }
+
+    template <class DrawMode>
+        void draw(gl::Context& context,
+                DrawMode drawMode,
+                gl::DepthMode depthMode,
+                gl::StencilMode stencilMode,
+                gl::ColorMode colorMode,
+                const UniformValues& uniformValues,
+                const gl::VertexBuffer<CollisionBoxLayoutAttributes::Vertex>& layoutVertexBuffer,
+                const gl::VertexBuffer<CollisionBoxOpacityAttributes::Vertex>& opacityVertexBuffer,
+                const gl::IndexBuffer<DrawMode>& indexBuffer,
+                const SegmentVector<Attributes>& segments,
+                const PaintPropertyBinders& paintPropertyBinders,
+                const typename PaintProperties::PossiblyEvaluated& currentProperties,
+                float currentZoom,
+                const std::string& layerID) {
+            typename AllUniforms::Values allUniformValues = uniformValues
+                .concat(paintPropertyBinders.uniformValues(currentZoom, currentProperties));
+
+            typename Attributes::Bindings allAttributeBindings = CollisionBoxLayoutAttributes::bindings(layoutVertexBuffer)
+                .concat(CollisionBoxOpacityAttributes::bindings(opacityVertexBuffer))
+                .concat(paintPropertyBinders.attributeBindings(currentProperties));
+
+            for (auto& segment : segments) {
+                auto vertexArrayIt = segment.vertexArrays.find(layerID);
+
+                if (vertexArrayIt == segment.vertexArrays.end()) {
+                    vertexArrayIt = segment.vertexArrays.emplace(layerID, context.createVertexArray()).first;
+                }
+
+                program.draw(
+                        context,
+                        std::move(drawMode),
+                        std::move(depthMode),
+                        std::move(stencilMode),
+                        std::move(colorMode),
+                        allUniformValues,
+                        vertexArrayIt->second,
+                        Attributes::offsetBindings(allAttributeBindings, segment.vertexOffset),
+                        indexBuffer,
+                        segment.indexOffset,
+                        segment.indexLength);
+            }
+        }
+
+};
+
 using CollisionBoxVertex = CollisionBoxProgram::LayoutVertex;
 
 } // namespace mbgl
diff --git a/src/mbgl/programs/programs.hpp b/src/mbgl/programs/programs.hpp
index 37ced32745..d769defaaf 100644
--- a/src/mbgl/programs/programs.hpp
+++ b/src/mbgl/programs/programs.hpp
@@ -32,7 +32,8 @@ public:
           symbolIconSDF(context, programParameters),
           symbolGlyph(context, programParameters),
           debug(context, programParameters),
-          collisionBox(context, programParameters) {
+          collisionBox(context, programParameters),
+          collisionCircle(context, programParameters) {
     }
 
     ProgramMap<CircleProgram> circle;
@@ -53,6 +54,7 @@ public:
 
     DebugProgram debug;
     CollisionBoxProgram collisionBox;
+    CollisionCircleProgram collisionCircle;
 };
 
 } // namespace mbgl
diff --git a/src/mbgl/renderer/buckets/symbol_bucket.cpp b/src/mbgl/renderer/buckets/symbol_bucket.cpp
index 282663e755..a544394353 100644
--- a/src/mbgl/renderer/buckets/symbol_bucket.cpp
+++ b/src/mbgl/renderer/buckets/symbol_bucket.cpp
@@ -51,11 +51,17 @@ void SymbolBucket::upload(gl::Context& context) {
         icon.indexBuffer = context.createIndexBuffer(std::move(icon.triangles));
     }
 
-    if (!collisionBox.vertices.empty()) {
+    if (hasCollisionBoxData()) {
         collisionBox.vertexBuffer = context.createVertexBuffer(std::move(collisionBox.vertices));
         collisionBox.opacityVertexBuffer = context.createVertexBuffer(std::move(collisionBox.opacityVertices), gl::BufferUsage::StreamDraw);
         collisionBox.indexBuffer = context.createIndexBuffer(std::move(collisionBox.lines));
     }
+    
+    if (hasCollisionCircleData()) {
+        collisionCircle.vertexBuffer = context.createVertexBuffer(std::move(collisionCircle.vertices));
+        collisionCircle.opacityVertexBuffer = context.createVertexBuffer(std::move(collisionCircle.opacityVertices), gl::BufferUsage::StreamDraw);
+        collisionCircle.indexBuffer = context.createIndexBuffer(std::move(collisionCircle.triangles));
+    }
 
     for (auto& pair : paintPropertyBinders) {
         pair.second.first.upload(context);
@@ -81,4 +87,8 @@ bool SymbolBucket::hasCollisionBoxData() const {
     return !collisionBox.segments.empty();
 }
 
+bool SymbolBucket::hasCollisionCircleData() const {
+    return !collisionCircle.segments.empty();
+}
+
 } // namespace mbgl
diff --git a/src/mbgl/renderer/buckets/symbol_bucket.hpp b/src/mbgl/renderer/buckets/symbol_bucket.hpp
index 86de194ee9..0e797539e1 100644
--- a/src/mbgl/renderer/buckets/symbol_bucket.hpp
+++ b/src/mbgl/renderer/buckets/symbol_bucket.hpp
@@ -58,6 +58,7 @@ public:
     bool hasTextData() const;
     bool hasIconData() const;
     bool hasCollisionBoxData() const;
+    bool hasCollisionCircleData() const;
 
     const style::SymbolLayoutProperties::PossiblyEvaluated layout;
     const bool sdfIcons;
@@ -102,16 +103,24 @@ public:
         optional<gl::IndexBuffer<gl::Triangles>> indexBuffer;
     } icon;
 
-    struct CollisionBoxBuffer {
+    struct CollisionBuffer {
         gl::VertexVector<CollisionBoxLayoutAttributes::Vertex> vertices;
         gl::VertexVector<CollisionBoxOpacityAttributes::Vertex> opacityVertices;
-        gl::IndexVector<gl::Lines> lines;
         SegmentVector<CollisionBoxProgram::Attributes> segments;
 
         optional<gl::VertexBuffer<CollisionBoxLayoutAttributes::Vertex>> vertexBuffer;
         optional<gl::VertexBuffer<CollisionBoxOpacityAttributes::Vertex>> opacityVertexBuffer;
+    };
+
+    struct CollisionBoxBuffer : public CollisionBuffer {
+        gl::IndexVector<gl::Lines> lines;
         optional<gl::IndexBuffer<gl::Lines>> indexBuffer;
     } collisionBox;
+    
+    struct CollisionCircleBuffer : public CollisionBuffer {
+        gl::IndexVector<gl::Triangles> triangles;
+        optional<gl::IndexBuffer<gl::Triangles>> indexBuffer;
+    } collisionCircle;
 };
 
 } // namespace mbgl
diff --git a/src/mbgl/renderer/layers/render_symbol_layer.cpp b/src/mbgl/renderer/layers/render_symbol_layer.cpp
index 92aed48409..9f1d0b1c9d 100644
--- a/src/mbgl/renderer/layers/render_symbol_layer.cpp
+++ b/src/mbgl/renderer/layers/render_symbol_layer.cpp
@@ -233,7 +233,6 @@ void RenderSymbolLayer::render(PaintParameters& parameters, RenderSource*) {
                     parameters.pixelsToGLUnits[1] / (pixelRatio * scale)
                     
                 }};
-            
             parameters.programs.collisionBox.draw(
                 parameters.context,
                 gl::Lines { 1.0f },
@@ -255,6 +254,41 @@ void RenderSymbolLayer::render(PaintParameters& parameters, RenderSource*) {
                 getID()
             );
         }
+        if (bucket.hasCollisionCircleData()) {
+            static const style::Properties<>::PossiblyEvaluated properties {};
+            static const CollisionBoxProgram::PaintPropertyBinders paintAttributeData(properties, 0);
+
+            auto pixelRatio = tile.id.pixelsToTileUnits(1, parameters.state.getZoom());
+            auto scale = std::pow(2.0f, float(parameters.state.getZoom() - tile.tile.id.overscaledZ));
+            std::array<float,2> extrudeScale =
+                {{
+                    parameters.pixelsToGLUnits[0] / (pixelRatio * scale),
+                    parameters.pixelsToGLUnits[1] / (pixelRatio * scale)
+                    
+                }};
+
+            parameters.programs.collisionCircle.draw(
+                parameters.context,
+                gl::Triangles(),
+                gl::DepthMode::disabled(),
+                parameters.stencilModeForClipping(tile.clip),
+                parameters.colorModeForRenderPass(),
+                CollisionBoxProgram::UniformValues {
+                    uniforms::u_matrix::Value{ tile.matrix },
+                    uniforms::u_extrude_scale::Value{ extrudeScale },
+                    uniforms::u_camera_to_center_distance::Value{ parameters.state.getCameraToCenterDistance() }
+                },
+                *bucket.collisionCircle.vertexBuffer,
+                *bucket.collisionCircle.opacityVertexBuffer,
+                *bucket.collisionCircle.indexBuffer,
+                bucket.collisionCircle.segments,
+                paintAttributeData,
+                properties,
+                parameters.state.getZoom(),
+                getID()
+            );
+
+        }
     }
 }
 
diff --git a/src/mbgl/text/collision_feature.cpp b/src/mbgl/text/collision_feature.cpp
index 4c08d17422..72e2c726e0 100644
--- a/src/mbgl/text/collision_feature.cpp
+++ b/src/mbgl/text/collision_feature.cpp
@@ -124,7 +124,7 @@ void CollisionFeature::bboxifyLabel(const GeometryCoordinates& line, GeometryCoo
             0 :
             (boxDistanceToAnchor - firstBoxOffset) * 0.8;
 
-        boxes.emplace_back(boxAnchor, boxAnchor - convertPoint<float>(anchorPoint), -boxSize / 2, -boxSize / 2, boxSize / 2, boxSize / 2, paddedAnchorDistance);
+        boxes.emplace_back(boxAnchor, boxAnchor - convertPoint<float>(anchorPoint), -boxSize / 2, -boxSize / 2, boxSize / 2, boxSize / 2, paddedAnchorDistance, boxSize / 2);
     }
 }
 
diff --git a/src/mbgl/text/collision_feature.hpp b/src/mbgl/text/collision_feature.hpp
index 556ae1beac..edfaa924c9 100644
--- a/src/mbgl/text/collision_feature.hpp
+++ b/src/mbgl/text/collision_feature.hpp
@@ -11,8 +11,8 @@ namespace mbgl {
 
 class CollisionBox {
 public:
-    CollisionBox(Point<float> _anchor, Point<float> _offset, float _x1, float _y1, float _x2, float _y2, float _tileUnitDistanceToAnchor = 0) :
-        anchor(std::move(_anchor)), offset(_offset), x1(_x1), y1(_y1), x2(_x2), y2(_y2), used(true), tileUnitDistanceToAnchor(_tileUnitDistanceToAnchor) {}
+    CollisionBox(Point<float> _anchor, Point<float> _offset, float _x1, float _y1, float _x2, float _y2, float _tileUnitDistanceToAnchor = 0, float _radius = 0) :
+        anchor(std::move(_anchor)), offset(_offset), x1(_x1), y1(_y1), x2(_x2), y2(_y2), used(true), tileUnitDistanceToAnchor(_tileUnitDistanceToAnchor), radius(_radius) {}
 
     // the box is centered around the anchor point
     Point<float> anchor;
@@ -34,11 +34,10 @@ public:
     // Placeholder for center of circles (can be derived from bounding box)
     float px;
     float py;
-    float radius;
     bool used;
 
     float tileUnitDistanceToAnchor;
-
+    float radius;
     
     // TODO Placeholders for old collision tiles
     float maxScale;
diff --git a/src/mbgl/text/placement.cpp b/src/mbgl/text/placement.cpp
index 0583902932..d64d2698f9 100644
--- a/src/mbgl/text/placement.cpp
+++ b/src/mbgl/text/placement.cpp
@@ -199,6 +199,7 @@ void Placement::updateBucketOpacities(SymbolBucket& bucket, gl::Context& context
     if (bucket.hasTextData()) bucket.text.opacityVertices.clear();
     if (bucket.hasIconData()) bucket.icon.opacityVertices.clear();
     if (bucket.hasCollisionBoxData()) bucket.collisionBox.opacityVertices.clear();
+    if (bucket.hasCollisionCircleData()) bucket.collisionCircle.opacityVertices.clear();
 
     for (SymbolInstance& symbolInstance : bucket.symbolInstances) {
         auto opacityState = getOpacity(symbolInstance.crossTileID);
@@ -223,13 +224,20 @@ void Placement::updateBucketOpacities(SymbolBucket& bucket, gl::Context& context
         }
         
         auto updateCollisionBox = [&](const auto& feature, const bool placed) {
-            for (size_t i = 0; i < feature.boxes.size(); i++) {
-                auto opacityVertex = CollisionBoxOpacityAttributes::vertex(placed, false); // TODO
-                bucket.collisionBox.opacityVertices.emplace_back(opacityVertex);
-                bucket.collisionBox.opacityVertices.emplace_back(opacityVertex);
-                bucket.collisionBox.opacityVertices.emplace_back(opacityVertex);
-                bucket.collisionBox.opacityVertices.emplace_back(opacityVertex);
-
+            for (const CollisionBox& box : feature.boxes) {
+                if (feature.alongLine) {
+                   auto opacityVertex = CollisionBoxOpacityAttributes::vertex(placed, !box.used);
+                    bucket.collisionCircle.opacityVertices.emplace_back(opacityVertex);
+                    bucket.collisionCircle.opacityVertices.emplace_back(opacityVertex);
+                    bucket.collisionCircle.opacityVertices.emplace_back(opacityVertex);
+                    bucket.collisionCircle.opacityVertices.emplace_back(opacityVertex);
+                } else {
+                    auto opacityVertex = CollisionBoxOpacityAttributes::vertex(placed, false);
+                    bucket.collisionBox.opacityVertices.emplace_back(opacityVertex);
+                    bucket.collisionBox.opacityVertices.emplace_back(opacityVertex);
+                    bucket.collisionBox.opacityVertices.emplace_back(opacityVertex);
+                    bucket.collisionBox.opacityVertices.emplace_back(opacityVertex);
+                }
             }
         };
         updateCollisionBox(symbolInstance.textCollisionFeature, symbolInstance.placedText);
@@ -239,6 +247,7 @@ void Placement::updateBucketOpacities(SymbolBucket& bucket, gl::Context& context
     if (bucket.hasTextData()) context.updateVertexBuffer(*bucket.text.opacityVertexBuffer, std::move(bucket.text.opacityVertices));
     if (bucket.hasIconData()) context.updateVertexBuffer(*bucket.icon.opacityVertexBuffer, std::move(bucket.icon.opacityVertices));
     if (bucket.hasCollisionBoxData()) context.updateVertexBuffer(*bucket.collisionBox.opacityVertexBuffer, std::move(bucket.collisionBox.opacityVertices));
+    if (bucket.hasCollisionCircleData()) context.updateVertexBuffer(*bucket.collisionCircle.opacityVertexBuffer, std::move(bucket.collisionCircle.opacityVertices));
 }
 
 JointOpacityState Placement::getOpacity(uint32_t crossTileSymbolID) const {