[core] Auto-growable SpriteAtlas using shelf-pack

20 files changed, 75 insertions, 79 deletions

diff --git a/CMakeLists.txt b/CMakeLists.txt
index f0c7a2ac57..50e82553a4 100644
--- a/CMakeLists.txt
+++ b/CMakeLists.txt
@@ -56,6 +56,7 @@ mason_use(pixelmatch VERSION 0.10.0 HEADER_ONLY)
 mason_use(geojson VERSION 0.4.0 HEADER_ONLY)
 mason_use(polylabel VERSION 1.0.2 HEADER_ONLY)
 mason_use(wagyu VERSION 0.4.1 HEADER_ONLY)
+mason_use(shelf-pack VERSION 2.0.1 HEADER_ONLY)
 
 add_definitions(-DRAPIDJSON_HAS_STDSTRING=1)
 
diff --git a/cmake/core.cmake b/cmake/core.cmake
index 531edc092d..5671ab53b5 100644
--- a/cmake/core.cmake
+++ b/cmake/core.cmake
@@ -26,6 +26,7 @@ target_add_mason_package(mbgl-core PRIVATE earcut)
 target_add_mason_package(mbgl-core PRIVATE protozero)
 target_add_mason_package(mbgl-core PRIVATE polylabel)
 target_add_mason_package(mbgl-core PRIVATE wagyu)
+target_add_mason_package(mbgl-core PRIVATE shelf-pack)
 
 mbgl_platform_core()
 
diff --git a/cmake/test.cmake b/cmake/test.cmake
index 3c63f7bcf8..8a5233f5a5 100644
--- a/cmake/test.cmake
+++ b/cmake/test.cmake
@@ -35,6 +35,7 @@ target_add_mason_package(mbgl-test PRIVATE pixelmatch)
 target_add_mason_package(mbgl-test PRIVATE boost)
 target_add_mason_package(mbgl-test PRIVATE geojson)
 target_add_mason_package(mbgl-test PRIVATE geojsonvt)
+target_add_mason_package(mbgl-test PRIVATE shelf-pack)
 
 mbgl_platform_test()
 
diff --git a/src/mbgl/annotation/annotation_manager.cpp b/src/mbgl/annotation/annotation_manager.cpp
index a7f1c69f3b..f04a0bb3dc 100644
--- a/src/mbgl/annotation/annotation_manager.cpp
+++ b/src/mbgl/annotation/annotation_manager.cpp
@@ -20,8 +20,7 @@ using namespace style;
 const std::string AnnotationManager::SourceID = "com.mapbox.annotations";
 const std::string AnnotationManager::PointLayerID = "com.mapbox.annotations.points";
 
-AnnotationManager::AnnotationManager(float pixelRatio)
-        : spriteAtlas({ 1024, 1024 }, pixelRatio){
+AnnotationManager::AnnotationManager() {
     // This is a special atlas, holding only images added via addIcon, so we always treat it as
     // loaded.
     spriteAtlas.markAsLoaded();
diff --git a/src/mbgl/annotation/annotation_manager.hpp b/src/mbgl/annotation/annotation_manager.hpp
index 837827b75c..4d22ac81f6 100644
--- a/src/mbgl/annotation/annotation_manager.hpp
+++ b/src/mbgl/annotation/annotation_manager.hpp
@@ -26,7 +26,7 @@ class Image;
 
 class AnnotationManager : private util::noncopyable {
 public:
-    AnnotationManager(float pixelRatio);
+    AnnotationManager();
     ~AnnotationManager();
 
     AnnotationID addAnnotation(const Annotation&, const uint8_t maxZoom);
diff --git a/src/mbgl/map/map.cpp b/src/mbgl/map/map.cpp
index e994428bf1..14a2401ed5 100644
--- a/src/mbgl/map/map.cpp
+++ b/src/mbgl/map/map.cpp
@@ -153,7 +153,7 @@ Map::Impl::Impl(Map& map_,
       contextMode(contextMode_),
       pixelRatio(pixelRatio_),
       programCacheDir(std::move(programCacheDir_)),
-      annotationManager(std::make_unique<AnnotationManager>(pixelRatio)),
+      annotationManager(std::make_unique<AnnotationManager>()),
       asyncInvalidate([this] {
           if (mode == MapMode::Continuous) {
               backend.invalidate();
diff --git a/src/mbgl/sprite/sprite_atlas.cpp b/src/mbgl/sprite/sprite_atlas.cpp
index 57a5488105..d3f0072b20 100644
--- a/src/mbgl/sprite/sprite_atlas.cpp
+++ b/src/mbgl/sprite/sprite_atlas.cpp
@@ -20,22 +20,25 @@ namespace mbgl {
 // correct behavior of GL_LINEAR texture sampling mode.
 static constexpr uint16_t padding = 1;
 
-SpriteAtlasElement::SpriteAtlasElement(Rect<uint16_t> rect, const style::Image::Impl& image)
+SpriteAtlasElement::SpriteAtlasElement(const mapbox::Bin& bin, const style::Image::Impl& image)
     : sdf(image.sdf),
       pixelRatio(image.pixelRatio),
       textureRect(
-        rect.x + padding,
-        rect.y + padding,
-        rect.w - padding * 2,
-        rect.h - padding * 2
+        bin.x + padding,
+        bin.y + padding,
+        bin.w - padding * 2,
+        bin.h - padding * 2
       ) {
 }
 
-SpriteAtlas::SpriteAtlas(Size size, float pixelRatio)
-    : pixelSize(std::ceil(size.width * pixelRatio),
-                std::ceil(size.height * pixelRatio)),
-      bin(pixelSize.width, pixelSize.height),
-      dirty(true) {
+static mapbox::ShelfPack::ShelfPackOptions shelfPackOptions() {
+    mapbox::ShelfPack::ShelfPackOptions options;
+    options.autoResize = true;
+    return options;
+}
+
+SpriteAtlas::SpriteAtlas()
+    : shelfPack(64, 64, shelfPackOptions()) {
 }
 
 SpriteAtlas::~SpriteAtlas() = default;
@@ -64,12 +67,12 @@ void SpriteAtlas::addImage(Immutable<style::Image::Impl> image_) {
 
     entry.image = std::move(image_);
 
-    if (entry.iconRect) {
-        copy(entry, &Entry::iconRect);
+    if (entry.iconBin) {
+        copy(entry, &Entry::iconBin);
     }
 
-    if (entry.patternRect) {
-        copy(entry, &Entry::patternRect);
+    if (entry.patternBin) {
+        copy(entry, &Entry::patternBin);
     }
 }
 
@@ -81,12 +84,12 @@ void SpriteAtlas::removeImage(const std::string& id) {
 
     Entry& entry = it->second;
 
-    if (entry.iconRect) {
-        bin.release(*entry.iconRect);
+    if (entry.iconBin) {
+        shelfPack.unref(*entry.iconBin);
     }
 
-    if (entry.patternRect) {
-        bin.release(*entry.patternRect);
+    if (entry.patternBin) {
+        shelfPack.unref(*entry.patternBin);
     }
 
     entries.erase(it);
@@ -116,16 +119,14 @@ void SpriteAtlas::removeRequestor(IconRequestor& requestor) {
 }
 
 optional<SpriteAtlasElement> SpriteAtlas::getIcon(const std::string& id) {
-    return getImage(id, &Entry::iconRect);
+    return getImage(id, &Entry::iconBin);
 }
 
 optional<SpriteAtlasElement> SpriteAtlas::getPattern(const std::string& id) {
-    return getImage(id, &Entry::patternRect);
+    return getImage(id, &Entry::patternBin);
 }
 
-optional<SpriteAtlasElement> SpriteAtlas::getImage(const std::string& id,
-                                                   optional<Rect<uint16_t>> Entry::*entryRect) {
-
+optional<SpriteAtlasElement> SpriteAtlas::getImage(const std::string& id, mapbox::Bin* Entry::*entryBin) {
     auto it = entries.find(id);
     if (it == entries.end()) {
         if (!entries.empty()) {
@@ -136,10 +137,10 @@ optional<SpriteAtlasElement> SpriteAtlas::getImage(const std::string& id,
 
     Entry& entry = it->second;
 
-    if (entry.*entryRect) {
+    if (entry.*entryBin) {
         assert(entry.image.get());
         return SpriteAtlasElement {
-            *(entry.*entryRect),
+            *(entry.*entryBin),
             *entry.image
         };
     }
@@ -147,44 +148,51 @@ optional<SpriteAtlasElement> SpriteAtlas::getImage(const std::string& id,
     const uint16_t width = entry.image->image.size.width + padding * 2;
     const uint16_t height = entry.image->image.size.height + padding * 2;
 
-    Rect<uint16_t> rect = bin.allocate(width, height);
-    if (rect.w == 0) {
+    mapbox::Bin* bin = shelfPack.packOne(-1, width, height);
+    if (!bin) {
         if (debug::spriteWarnings) {
             Log::Warning(Event::Sprite, "sprite atlas bitmap overflow");
         }
         return {};
     }
 
-    entry.*entryRect = rect;
-    copy(entry, entryRect);
+    entry.*entryBin = bin;
+    copy(entry, entryBin);
 
     return SpriteAtlasElement {
-        rect,
+        *bin,
         *entry.image
     };
 }
 
 Size SpriteAtlas::getPixelSize() const {
-    return pixelSize;
+    return Size {
+        static_cast<uint32_t>(shelfPack.width()),
+        static_cast<uint32_t>(shelfPack.height())
+    };
 }
 
-void SpriteAtlas::copy(const Entry& entry, optional<Rect<uint16_t>> Entry::*entryRect) {
+void SpriteAtlas::copy(const Entry& entry, mapbox::Bin* Entry::*entryBin) {
     if (!image.valid()) {
         image = PremultipliedImage(getPixelSize());
         image.fill(0);
+    } else if (image.size != getPixelSize()) {
+        PremultipliedImage newImage(getPixelSize());
+        PremultipliedImage::copy(image, newImage, { 0, 0 }, { 0, 0 }, image.size);
+        image = std::move(newImage);
     }
 
     const PremultipliedImage& src = entry.image->image;
-    const Rect<uint16_t>& rect = *(entry.*entryRect);
+    const mapbox::Bin& bin = *(entry.*entryBin);
 
-    const uint32_t x = rect.x + padding;
-    const uint32_t y = rect.y + padding;
+    const uint32_t x = bin.x + padding;
+    const uint32_t y = bin.y + padding;
     const uint32_t w = src.size.width;
     const uint32_t h = src.size.height;
 
     PremultipliedImage::copy(src, image, { 0, 0 }, { x, y }, { w, h });
 
-    if (entryRect == &Entry::patternRect) {
+    if (entryBin == &Entry::patternBin) {
         // Add 1 pixel wrapped padding on each side of the image.
         PremultipliedImage::copy(src, image, { 0, h - 1 }, { x, y - 1 }, { w, 1 }); // T
         PremultipliedImage::copy(src, image, { 0,     0 }, { x, y + h }, { w, 1 }); // B
diff --git a/src/mbgl/sprite/sprite_atlas.hpp b/src/mbgl/sprite/sprite_atlas.hpp
index 3629ed6eb1..f5c7fd114a 100644
--- a/src/mbgl/sprite/sprite_atlas.hpp
+++ b/src/mbgl/sprite/sprite_atlas.hpp
@@ -1,11 +1,13 @@
 #pragma once
 
-#include <mbgl/geometry/binpack.hpp>
 #include <mbgl/gl/texture.hpp>
 #include <mbgl/util/noncopyable.hpp>
 #include <mbgl/util/optional.hpp>
+#include <mbgl/util/rect.hpp>
 #include <mbgl/style/image.hpp>
 
+#include <mapbox/shelf-pack.hpp>
+
 #include <string>
 #include <set>
 #include <unordered_map>
@@ -20,7 +22,7 @@ class Context;
 
 class SpriteAtlasElement {
 public:
-    SpriteAtlasElement(Rect<uint16_t>, const style::Image::Impl&);
+    SpriteAtlasElement(const mapbox::Bin&, const style::Image::Impl&);
 
     bool sdf;
     float pixelRatio;
@@ -59,7 +61,7 @@ public:
 
 class SpriteAtlas : public util::noncopyable {
 public:
-    SpriteAtlas(Size, float pixelRatio);
+    SpriteAtlas();
     ~SpriteAtlas();
 
     void onSpriteLoaded();
@@ -106,7 +108,6 @@ public:
     }
 
 private:
-    const Size pixelSize;
     bool loaded = false;
 
     struct Entry {
@@ -116,20 +117,20 @@ private:
         // it must have two distinct entries in the texture. The one for the icon image has
         // a single pixel transparent border, and the one for the pattern image has a single
         // pixel border wrapped from the opposite side.
-        optional<Rect<uint16_t>> iconRect;
-        optional<Rect<uint16_t>> patternRect;
+        mapbox::Bin* iconBin = nullptr;
+        mapbox::Bin* patternBin = nullptr;
     };
 
-    optional<SpriteAtlasElement> getImage(const std::string& name, optional<Rect<uint16_t>> Entry::*rect);
-    void copy(const Entry&, optional<Rect<uint16_t>> Entry::*rect);
+    optional<SpriteAtlasElement> getImage(const std::string& name, mapbox::Bin* Entry::*bin);
+    void copy(const Entry&, mapbox::Bin* Entry::*bin);
     
     IconMap buildIconMap();
 
     std::unordered_map<std::string, Entry> entries;
-    BinPack<uint16_t> bin;
+    mapbox::ShelfPack shelfPack;
     PremultipliedImage image;
     mbgl::optional<gl::Texture> texture;
-    bool dirty;
+    bool dirty = true;
     
     std::set<IconRequestor*> requestors;
     IconMap icons;
diff --git a/src/mbgl/style/style.cpp b/src/mbgl/style/style.cpp
index 84ee841c06..1a4cf0ca10 100644
--- a/src/mbgl/style/style.cpp
+++ b/src/mbgl/style/style.cpp
@@ -74,7 +74,7 @@ Style::Style(Scheduler& scheduler_, FileSource& fileSource_, float pixelRatio)
       fileSource(fileSource_),
       glyphAtlas(std::make_unique<GlyphAtlas>(Size{ 2048, 2048 }, fileSource)),
       spriteLoader(std::make_unique<SpriteLoader>(pixelRatio)),
-      spriteAtlas(std::make_unique<SpriteAtlas>(Size{ 1024, 1024 }, pixelRatio)),
+      spriteAtlas(std::make_unique<SpriteAtlas>()),
       lineAtlas(std::make_unique<LineAtlas>(Size{ 256, 512 })),
       light(std::make_unique<Light>()),
       renderLight(light->impl),
diff --git a/test/fixtures/sprite_atlas/basic/expected.png b/test/fixtures/sprite_atlas/basic/expected.png
index cd13d16df6..2960891c04 100644
--- a/test/fixtures/sprite_atlas/basic/expected.png
+++ b/test/fixtures/sprite_atlas/basic/expected.png
diff --git a/test/fixtures/sprite_atlas/size/expected.png b/test/fixtures/sprite_atlas/size/expected.png
index d9ae7dab47..5b08197a82 100644
--- a/test/fixtures/sprite_atlas/size/expected.png
+++ b/test/fixtures/sprite_atlas/size/expected.png
diff --git a/test/fixtures/sprite_atlas/updates_after/expected.png b/test/fixtures/sprite_atlas/updates_after/expected.png
index 3c850c0a25..626ceab58b 100644
--- a/test/fixtures/sprite_atlas/updates_after/expected.png
+++ b/test/fixtures/sprite_atlas/updates_after/expected.png
diff --git a/test/fixtures/sprite_atlas/updates_before/expected.png b/test/fixtures/sprite_atlas/updates_before/expected.png
index effcd38f1e..0858c19f05 100644
--- a/test/fixtures/sprite_atlas/updates_before/expected.png
+++ b/test/fixtures/sprite_atlas/updates_before/expected.png
diff --git a/test/sprite/sprite_atlas.test.cpp b/test/sprite/sprite_atlas.test.cpp
index c673c5ca0e..7a638a9ec5 100644
--- a/test/sprite/sprite_atlas.test.cpp
+++ b/test/sprite/sprite_atlas.test.cpp
@@ -18,7 +18,7 @@ using namespace mbgl;
 
 TEST(SpriteAtlas, Basic) {
     FixtureLog log;
-    SpriteAtlas atlas({ 63, 112 }, 1);
+    SpriteAtlas atlas;
 
     auto images = parseSprite(util::read_file("test/fixtures/annotations/emerald.png"),
                               util::read_file("test/fixtures/annotations/emerald.json"));
@@ -26,9 +26,6 @@ TEST(SpriteAtlas, Basic) {
         atlas.addImage(image->impl);
     }
 
-    EXPECT_EQ(63u, atlas.getPixelSize().width);
-    EXPECT_EQ(112u, atlas.getPixelSize().height);
-
     auto metro = *atlas.getIcon("metro");
     EXPECT_EQ(1, metro.tl()[0]);
     EXPECT_EQ(1, metro.tl()[1]);
@@ -38,8 +35,7 @@ TEST(SpriteAtlas, Basic) {
     EXPECT_EQ(18, metro.displaySize()[1]);
     EXPECT_EQ(1.0f, metro.pixelRatio);
 
-    EXPECT_EQ(63u, atlas.getAtlasImage().size.width);
-    EXPECT_EQ(112u, atlas.getAtlasImage().size.height);
+    EXPECT_EQ(atlas.getPixelSize(), atlas.getAtlasImage().size);
 
     auto missing = atlas.getIcon("doesnotexist");
     EXPECT_FALSE(missing);
@@ -62,7 +58,7 @@ TEST(SpriteAtlas, Basic) {
 }
 
 TEST(SpriteAtlas, Size) {
-    SpriteAtlas atlas({ 63, 112 }, 1.4);
+    SpriteAtlas atlas;
 
     auto images = parseSprite(util::read_file("test/fixtures/annotations/emerald.png"),
                               util::read_file("test/fixtures/annotations/emerald.json"));
@@ -70,9 +66,6 @@ TEST(SpriteAtlas, Size) {
         atlas.addImage(image->impl);
     }
 
-    EXPECT_EQ(89u, atlas.getPixelSize().width);
-    EXPECT_EQ(157u, atlas.getPixelSize().height);
-
     auto metro = *atlas.getIcon("metro");
     EXPECT_EQ(1, metro.tl()[0]);
     EXPECT_EQ(1, metro.tl()[1]);
@@ -86,10 +79,7 @@ TEST(SpriteAtlas, Size) {
 }
 
 TEST(SpriteAtlas, Updates) {
-    SpriteAtlas atlas({ 32, 32 }, 1);
-
-    EXPECT_EQ(32u, atlas.getPixelSize().width);
-    EXPECT_EQ(32u, atlas.getPixelSize().height);
+    SpriteAtlas atlas;
 
     atlas.addImage(makeMutable<style::Image::Impl>("one", PremultipliedImage({ 16, 12 }), 1));
     auto one = *atlas.getIcon("one");
@@ -101,10 +91,6 @@ TEST(SpriteAtlas, Updates) {
     EXPECT_EQ(12, one.displaySize()[1]);
     EXPECT_EQ(1.0f, one.pixelRatio);
 
-    // Now the image was created lazily.
-    EXPECT_EQ(32u, atlas.getAtlasImage().size.width);
-    EXPECT_EQ(32u, atlas.getAtlasImage().size.height);
-
     test::checkImage("test/fixtures/sprite_atlas/updates_before", atlas.getAtlasImage());
 
     // Update image
@@ -119,7 +105,7 @@ TEST(SpriteAtlas, Updates) {
 
 TEST(SpriteAtlas, AddRemove) {
     FixtureLog log;
-    SpriteAtlas atlas({ 32, 32 }, 1);
+    SpriteAtlas atlas;
 
     atlas.addImage(makeMutable<style::Image::Impl>("one", PremultipliedImage({ 16, 16 }), 2));
     atlas.addImage(makeMutable<style::Image::Impl>("two", PremultipliedImage({ 16, 16 }), 2));
@@ -148,8 +134,7 @@ TEST(SpriteAtlas, AddRemove) {
 
 TEST(SpriteAtlas, RemoveReleasesBinPackRect) {
     FixtureLog log;
-
-    SpriteAtlas atlas({ 36, 36 }, 1);
+    SpriteAtlas atlas;
 
     atlas.addImage(makeMutable<style::Image::Impl>("big", PremultipliedImage({ 32, 32 }), 1));
     EXPECT_TRUE(atlas.getIcon("big"));
diff --git a/test/style/source.test.cpp b/test/style/source.test.cpp
index 0473286c8b..880bcd986c 100644
--- a/test/style/source.test.cpp
+++ b/test/style/source.test.cpp
@@ -43,7 +43,7 @@ public:
     Transform transform;
     TransformState transformState;
     ThreadPool threadPool { 1 };
-    AnnotationManager annotationManager { 1.0 };
+    AnnotationManager annotationManager;
     style::Style style { threadPool, fileSource, 1.0 };
 
     TileParameters tileParameters {
diff --git a/test/text/quads.test.cpp b/test/text/quads.test.cpp
index 4c40b41a97..0a1dbbd1c9 100644
--- a/test/text/quads.test.cpp
+++ b/test/text/quads.test.cpp
@@ -13,7 +13,7 @@ TEST(getIconQuads, normal) {
     SymbolLayoutProperties::Evaluated layout;
     Anchor anchor(2.0, 3.0, 0.0, 0.5f, 0);
     SpriteAtlasElement image = {
-        Rect<uint16_t>( 0, 0, 15, 11 ),
+        mapbox::Bin(-1, 15, 11, 0, 0),
         style::Image::Impl("test", PremultipliedImage({1,1}), 1.0)
     };
 
@@ -43,7 +43,7 @@ TEST(getIconQuads, normal) {
 TEST(getIconQuads, style) {
     Anchor anchor(0.0, 0.0, 0.0, 0.5f, 0);
     SpriteAtlasElement image = {
-        Rect<uint16_t>( 0, 0, 20, 20 ),
+        mapbox::Bin(-1, 20, 20, 0, 0),
         style::Image::Impl("test", PremultipliedImage({1,1}), 1.0)
     };
 
diff --git a/test/tile/annotation_tile.test.cpp b/test/tile/annotation_tile.test.cpp
index 607a8cca17..05ce109766 100644
--- a/test/tile/annotation_tile.test.cpp
+++ b/test/tile/annotation_tile.test.cpp
@@ -23,7 +23,7 @@ public:
     TransformState transformState;
     util::RunLoop loop;
     ThreadPool threadPool { 1 };
-    AnnotationManager annotationManager { 1.0 };
+    AnnotationManager annotationManager;
     style::Style style { threadPool, fileSource, 1.0 };
 
     TileParameters tileParameters {
diff --git a/test/tile/geojson_tile.test.cpp b/test/tile/geojson_tile.test.cpp
index 8669c02dfd..dad4aef2ee 100644
--- a/test/tile/geojson_tile.test.cpp
+++ b/test/tile/geojson_tile.test.cpp
@@ -23,7 +23,7 @@ public:
     TransformState transformState;
     util::RunLoop loop;
     ThreadPool threadPool { 1 };
-    AnnotationManager annotationManager { 1.0 };
+    AnnotationManager annotationManager;
     style::Style style { threadPool, fileSource, 1.0 };
     Tileset tileset { { "https://example.com" }, { 0, 22 }, "none" };
 
diff --git a/test/tile/raster_tile.test.cpp b/test/tile/raster_tile.test.cpp
index e363b73609..ee6e31d845 100644
--- a/test/tile/raster_tile.test.cpp
+++ b/test/tile/raster_tile.test.cpp
@@ -19,7 +19,7 @@ public:
     TransformState transformState;
     util::RunLoop loop;
     ThreadPool threadPool { 1 };
-    AnnotationManager annotationManager { 1.0 };
+    AnnotationManager annotationManager;
     style::Style style { threadPool, fileSource, 1.0 };
     Tileset tileset { { "https://example.com" }, { 0, 22 }, "none" };
 
diff --git a/test/tile/vector_tile.test.cpp b/test/tile/vector_tile.test.cpp
index 03896199f4..205d001f72 100644
--- a/test/tile/vector_tile.test.cpp
+++ b/test/tile/vector_tile.test.cpp
@@ -25,7 +25,7 @@ public:
     TransformState transformState;
     util::RunLoop loop;
     ThreadPool threadPool { 1 };
-    AnnotationManager annotationManager { 1.0 };
+    AnnotationManager annotationManager;
     style::Style style { threadPool, fileSource, 1.0 };
     Tileset tileset { { "https://example.com" }, { 0, 22 }, "none" };