Starting on sorting.upstream/start-collision-sort

7 files changed, 115 insertions, 10 deletions

diff --git a/src/mbgl/gl/context.cpp b/src/mbgl/gl/context.cpp
index d0c538efb0..925baa07cb 100644
--- a/src/mbgl/gl/context.cpp
+++ b/src/mbgl/gl/context.cpp
@@ -226,16 +226,22 @@ void Context::updateVertexBuffer(UniqueBuffer& buffer, const void* data, std::si
     MBGL_CHECK_ERROR(glBufferSubData(GL_ARRAY_BUFFER, 0, size, data));
 }
 
-UniqueBuffer Context::createIndexBuffer(const void* data, std::size_t size) {
+UniqueBuffer Context::createIndexBuffer(const void* data, std::size_t size, const BufferUsage usage) {
     BufferID id = 0;
     MBGL_CHECK_ERROR(glGenBuffers(1, &id));
     UniqueBuffer result { std::move(id), { this } };
     bindVertexArray = 0;
     globalVertexArrayState.indexBuffer = result;
-    MBGL_CHECK_ERROR(glBufferData(GL_ELEMENT_ARRAY_BUFFER, size, data, GL_STATIC_DRAW));
+    MBGL_CHECK_ERROR(glBufferData(GL_ELEMENT_ARRAY_BUFFER, size, data, static_cast<GLenum>(usage)));
     return result;
 }
 
+void Context::updateIndexBuffer(UniqueBuffer& buffer, const void* data, std::size_t size) {
+    globalVertexArrayState.indexBuffer = buffer;
+    MBGL_CHECK_ERROR(glBufferSubData(GL_ELEMENT_ARRAY_BUFFER, 0, size, data));
+}
+
+
 UniqueTexture Context::createTexture() {
     if (pooledTextures.empty()) {
         pooledTextures.resize(TextureMax);
diff --git a/src/mbgl/gl/context.hpp b/src/mbgl/gl/context.hpp
index 528113cbba..0ef6bc1a3a 100644
--- a/src/mbgl/gl/context.hpp
+++ b/src/mbgl/gl/context.hpp
@@ -75,11 +75,18 @@ public:
     }
 
     template <class DrawMode>
-    IndexBuffer<DrawMode> createIndexBuffer(IndexVector<DrawMode>&& v) {
+    IndexBuffer<DrawMode> createIndexBuffer(IndexVector<DrawMode>&& v, const BufferUsage usage=BufferUsage::StaticDraw) {
         return IndexBuffer<DrawMode> {
-            createIndexBuffer(v.data(), v.byteSize())
+            v.indexSize(),
+            createIndexBuffer(v.data(), v.byteSize(), usage)
         };
     }
+    
+    template <class DrawMode>
+    void updateIndexBuffer(IndexBuffer<DrawMode>& buffer, IndexVector<DrawMode>&& v) {
+        assert(v.indexSize() == buffer.indexCount);
+        updateIndexBuffer(buffer.buffer, v.data(), v.byteSize());
+    }
 
     template <RenderbufferType type>
     Renderbuffer<type> createRenderbuffer(const Size size) {
@@ -250,7 +257,8 @@ private:
 
     UniqueBuffer createVertexBuffer(const void* data, std::size_t size, const BufferUsage usage);
     void updateVertexBuffer(UniqueBuffer& buffer, const void* data, std::size_t size);
-    UniqueBuffer createIndexBuffer(const void* data, std::size_t size);
+    UniqueBuffer createIndexBuffer(const void* data, std::size_t size, const BufferUsage usage);
+    void updateIndexBuffer(UniqueBuffer& buffer, const void* data, std::size_t size);
     UniqueTexture createTexture(Size size, const void* data, TextureFormat, TextureUnit);
     void updateTexture(TextureID, Size size, const void* data, TextureFormat, TextureUnit);
     UniqueFramebuffer createFramebuffer();
diff --git a/src/mbgl/gl/index_buffer.hpp b/src/mbgl/gl/index_buffer.hpp
index 01b6396e00..87bfb6068f 100644
--- a/src/mbgl/gl/index_buffer.hpp
+++ b/src/mbgl/gl/index_buffer.hpp
@@ -35,6 +35,7 @@ private:
 template <class DrawMode>
 class IndexBuffer {
 public:
+    std::size_t indexCount;
     UniqueBuffer buffer;
 };
 
diff --git a/src/mbgl/layout/symbol_layout.cpp b/src/mbgl/layout/symbol_layout.cpp
index f74f2fb8b6..925abeb651 100644
--- a/src/mbgl/layout/symbol_layout.cpp
+++ b/src/mbgl/layout/symbol_layout.cpp
@@ -417,7 +417,10 @@ std::vector<float> CalculateTileDistances(const GeometryCoordinates& line, const
 }
 
 std::unique_ptr<SymbolBucket> SymbolLayout::place(const bool showCollisionBoxes) {
-    auto bucket = std::make_unique<SymbolBucket>(layout, layerPaintProperties, textSize, iconSize, zoom, sdfIcons, iconsNeedLinear, symbolInstances);
+    const bool mayOverlap = layout.get<TextAllowOverlap>() || layout.get<IconAllowOverlap>() ||
+        layout.get<TextIgnorePlacement>() || layout.get<IconIgnorePlacement>();
+    
+    auto bucket = std::make_unique<SymbolBucket>(layout, layerPaintProperties, textSize, iconSize, zoom, sdfIcons, iconsNeedLinear, mayOverlap, symbolInstances);
 
     // this iterates over the *bucket's* symbol instances so that it can set the placedsymbol index. TODO cleanup
     for (SymbolInstance &symbolInstance : bucket->symbolInstances) {
@@ -502,6 +505,7 @@ void SymbolLayout::addSymbol(Buffer& buffer,
     auto& segment = buffer.segments.back();
     assert(segment.vertexLength <= std::numeric_limits<uint16_t>::max());
     uint16_t index = segment.vertexLength;
+    placedSymbol.vertexStartIndex = index;
 
     // coordinates (2 triangles)
     buffer.vertices.emplace_back(SymbolLayoutAttributes::vertex(labelAnchor.point, tl, symbol.glyphOffset.y, tex.x, tex.y, sizeData));
diff --git a/src/mbgl/renderer/buckets/symbol_bucket.cpp b/src/mbgl/renderer/buckets/symbol_bucket.cpp
index 592c29eb15..cf8120739a 100644
--- a/src/mbgl/renderer/buckets/symbol_bucket.cpp
+++ b/src/mbgl/renderer/buckets/symbol_bucket.cpp
@@ -17,10 +17,12 @@ SymbolBucket::SymbolBucket(style::SymbolLayoutProperties::PossiblyEvaluated layo
                            float zoom,
                            bool sdfIcons_,
                            bool iconsNeedLinear_,
+                           bool sortFeaturesByY_,
                            const std::vector<SymbolInstance>& symbolInstances_)
     : layout(std::move(layout_)),
       sdfIcons(sdfIcons_),
       iconsNeedLinear(iconsNeedLinear_ || iconSize.isDataDriven() || !iconSize.isZoomConstant()),
+      sortFeaturesByY(sortFeaturesByY_),
       symbolInstances(symbolInstances_), // TODO maybe not copy
       textSizeBinder(SymbolSizeBinder::create(zoom, textSize, TextSize::defaultValue())),
       iconSizeBinder(SymbolSizeBinder::create(zoom, iconSize, IconSize::defaultValue())) {
@@ -39,9 +41,12 @@ SymbolBucket::SymbolBucket(style::SymbolLayoutProperties::PossiblyEvaluated layo
 void SymbolBucket::upload(gl::Context& context) {
     if (hasTextData()) {
         if (!staticUploaded) {
-            text.indexBuffer = context.createIndexBuffer(std::move(text.triangles));
+            text.indexBuffer = context.createIndexBuffer(std::move(text.triangles), sortFeaturesByY ? gl::BufferUsage::StreamDraw : gl::BufferUsage::StaticDraw);
             text.vertexBuffer = context.createVertexBuffer(std::move(text.vertices));
+        } else if (!sortUploaded) {
+            context.updateIndexBuffer(*text.indexBuffer, std::move(text.triangles));
         }
+        
         if (!dynamicUploaded) {
             text.dynamicVertexBuffer = context.createVertexBuffer(std::move(text.dynamicVertices), gl::BufferUsage::StreamDraw);
         }
@@ -56,8 +61,10 @@ void SymbolBucket::upload(gl::Context& context) {
 
     if (hasIconData()) {
         if (!staticUploaded) {
-            icon.indexBuffer = context.createIndexBuffer(std::move(icon.triangles));
+            icon.indexBuffer = context.createIndexBuffer(std::move(icon.triangles), sortFeaturesByY ? gl::BufferUsage::StreamDraw : gl::BufferUsage::StaticDraw);
             icon.vertexBuffer = context.createVertexBuffer(std::move(icon.vertices));
+        } else if (!sortUploaded) {
+            context.updateIndexBuffer(*icon.indexBuffer, std::move(icon.triangles));
         }
         if (!dynamicUploaded) {
             icon.dynamicVertexBuffer = context.createVertexBuffer(std::move(icon.dynamicVertices), gl::BufferUsage::StreamDraw);
@@ -105,11 +112,12 @@ void SymbolBucket::upload(gl::Context& context) {
             pair.second.second.upload(context);
         }
     }
-
+    
     uploaded = true;
     staticUploaded = true;
     opacityUploaded = true;
     dynamicUploaded = true;
+    sortUploaded = true;
 }
 
 bool SymbolBucket::hasData() const {
@@ -137,4 +145,73 @@ void SymbolBucket::updateOpacity() {
     uploaded = false;
 }
 
+void SymbolBucket::sortFeatures(const float angle) {
+    if (!sortFeaturesByY) {
+        return;
+    }
+
+    if (sortedAngle == angle) {
+        return;
+    }
+    
+    sortedAngle = angle;
+
+    // The current approach to sorting doesn't sort across segments so don't try.
+    // Sorting within segments separately seemed not to be worth the complexity.
+    if (text.segments.size() > 1 || icon.segments.size() > 1) {
+        return;
+    }
+    
+    sortUploaded = false;
+    uploaded = false;
+
+    // If the symbols are allowed to overlap sort them by their vertical screen position.
+    // The index array buffer is rewritten to reference the (unchanged) vertices in the
+    // sorted order.
+
+    // To avoid sorting the actual symbolInstance array we sort an array of indexes.
+    std::vector<size_t> symbolInstanceIndexes;
+    for (size_t i = 0; i < symbolInstances.size(); i++) {
+        symbolInstanceIndexes.push_back(i);
+    }
+    
+    const float sin = std::sin(angle);
+    const float cos = std::cos(angle);
+
+    std::sort(symbolInstanceIndexes.begin(), symbolInstanceIndexes.end(), [sin, cos, this](size_t &aIndex, size_t &bIndex) {
+        const SymbolInstance& a = symbolInstances[aIndex];
+        const SymbolInstance& b = symbolInstances[bIndex];
+        const int32_t aRotated = sin * a.anchor.point.x + cos * a.anchor.point.y;
+        const int32_t bRotated = sin * b.anchor.point.x + cos * b.anchor.point.y;
+        return aRotated != bRotated ?
+            aRotated < bRotated :
+            a.index > b.index;
+    });
+
+    text.triangles.clear();
+    icon.triangles.clear();
+
+    for (auto i : symbolInstanceIndexes) {
+        const SymbolInstance& symbolInstance = symbolInstances[i];
+
+        for (auto& placedTextSymbolIndex : symbolInstance.placedTextIndices) {
+            const PlacedSymbol& placedSymbol = text.placedSymbols[placedTextSymbolIndex];
+
+            auto endIndex = placedSymbol.vertexStartIndex + placedSymbol.glyphOffsets.size() * 4;
+            for (auto vertexIndex = placedSymbol.vertexStartIndex; vertexIndex < endIndex; vertexIndex += 4) {
+                text.triangles.emplace_back(vertexIndex + 0, vertexIndex + 1, vertexIndex + 2);
+                text.triangles.emplace_back(vertexIndex + 1, vertexIndex + 2, vertexIndex + 3);
+            }
+        }
+
+        for (auto& placedIconSymbolIndex : symbolInstance.placedIconIndices) { // TODO: This iteration is an awkward way to say "if the symbol has an icon"
+            const PlacedSymbol& placedIcon = icon.placedSymbols[placedIconSymbolIndex];
+            
+            const auto vertexIndex = placedIcon.vertexStartIndex;
+            icon.triangles.emplace_back(vertexIndex + 0, vertexIndex + 1, vertexIndex + 2);
+            icon.triangles.emplace_back(vertexIndex + 1, vertexIndex + 2, vertexIndex + 3);
+        }
+    }
+}
+
 } // namespace mbgl
diff --git a/src/mbgl/renderer/buckets/symbol_bucket.hpp b/src/mbgl/renderer/buckets/symbol_bucket.hpp
index 131ee72c43..81053b3307 100644
--- a/src/mbgl/renderer/buckets/symbol_bucket.hpp
+++ b/src/mbgl/renderer/buckets/symbol_bucket.hpp
@@ -21,7 +21,7 @@ public:
     PlacedSymbol(Point<float> anchorPoint_, uint16_t segment_, float lowerSize_, float upperSize_,
             std::array<float, 2> lineOffset_, WritingModeType writingModes_, const GeometryCoordinates& line_, const std::vector<float>& tileDistances_) :
         anchorPoint(anchorPoint_), segment(segment_), lowerSize(lowerSize_), upperSize(upperSize_),
-        lineOffset(lineOffset_), writingModes(writingModes_), line(line_), tileDistances(tileDistances_), hidden(false)
+        lineOffset(lineOffset_), writingModes(writingModes_), line(line_), tileDistances(tileDistances_), hidden(false), vertexStartIndex(0)
     {
     }
     Point<float> anchorPoint;
@@ -34,6 +34,7 @@ public:
     std::vector<float> tileDistances;
     std::vector<float> glyphOffsets;
     bool hidden;
+    size_t vertexStartIndex;
 };
 
 class SymbolBucket : public Bucket {
@@ -45,6 +46,7 @@ public:
                  float zoom,
                  bool sdfIcons,
                  bool iconsNeedLinear,
+                 bool sortFeaturesByY,
                  const std::vector<SymbolInstance>&);
 
     void upload(gl::Context&) override;
@@ -53,15 +55,21 @@ public:
     bool hasIconData() const;
     bool hasCollisionBoxData() const;
     bool hasCollisionCircleData() const;
+    
     void updateOpacity();
+    void sortFeatures(const float angle);
 
     const style::SymbolLayoutProperties::PossiblyEvaluated layout;
     const bool sdfIcons;
     const bool iconsNeedLinear;
+    const bool sortFeaturesByY;
+    
+    float sortedAngle = 0;
 
     bool staticUploaded = false;
     bool opacityUploaded = false;
     bool dynamicUploaded = false;
+    bool sortUploaded = false;
 
     std::vector<SymbolInstance> symbolInstances;
 
diff --git a/src/mbgl/text/placement.cpp b/src/mbgl/text/placement.cpp
index bfdb6136a1..e3110d5401 100644
--- a/src/mbgl/text/placement.cpp
+++ b/src/mbgl/text/placement.cpp
@@ -265,6 +265,7 @@ void Placement::updateBucketOpacities(SymbolBucket& bucket) {
     }
 
     bucket.updateOpacity();
+    bucket.sortFeatures(state.getAngle());
 }
 
 JointOpacityState Placement::getOpacity(uint32_t crossTileSymbolID) const {