diff options
| -rw-r--r-- | cmake/core-files.cmake | 1 | ||||
| -rw-r--r-- | cmake/test-files.cmake | 3 | ||||
| -rw-r--r-- | src/mbgl/geometry/binpack.hpp | 101 | ||||
| -rw-r--r-- | test/geometry/binpack.test.cpp | 51 |
4 files changed, 0 insertions, 156 deletions
diff --git a/cmake/core-files.cmake b/cmake/core-files.cmake index 9c4c730765..2700cdee1e 100644 --- a/cmake/core-files.cmake +++ b/cmake/core-files.cmake @@ -41,7 +41,6 @@ set(MBGL_CORE_FILES # geometry src/mbgl/geometry/anchor.hpp - src/mbgl/geometry/binpack.hpp src/mbgl/geometry/debug_font_data.hpp src/mbgl/geometry/feature_index.cpp src/mbgl/geometry/feature_index.hpp diff --git a/cmake/test-files.cmake b/cmake/test-files.cmake index ed84c679fb..edbf100fe2 100644 --- a/cmake/test-files.cmake +++ b/cmake/test-files.cmake @@ -19,9 +19,6 @@ set(MBGL_TEST_FILES test/api/render_missing.test.cpp test/api/repeated_render.test.cpp - # geometry - test/geometry/binpack.test.cpp - # gl test/gl/bucket.test.cpp test/gl/object.test.cpp diff --git a/src/mbgl/geometry/binpack.hpp b/src/mbgl/geometry/binpack.hpp deleted file mode 100644 index b715cbc2be..0000000000 --- a/src/mbgl/geometry/binpack.hpp +++ /dev/null @@ -1,101 +0,0 @@ -#pragma once - -#include <mbgl/util/noncopyable.hpp> -#include <mbgl/util/rect.hpp> -#include <cstdint> -#include <list> - -namespace mbgl { - -template <typename T> -class BinPack : private util::noncopyable { -public: - BinPack(T width, T height) - : free(1, Rect<uint16_t>{ 0, 0, width, height }) {} -public: - Rect<T> allocate(T width, T height) { - // Find the smallest free rect angle - auto smallest = free.end(); - for (auto it = free.begin(); it != free.end(); ++it) { - const Rect<T>& ref = *it; - const Rect<T>& rect = *smallest; - if (width <= ref.w && height <= ref.h) { - if (smallest == free.end() || (ref.y <= rect.y && ref.x <= rect.x)) { - smallest = it; - } else { - // Our current "smallest" rect is already closer to 0/0. - } - } else { - // The rect in the free list is not big enough. - } - } - - if (smallest == free.end()) { - // There's no space left for this char. - return Rect<uint16_t>{ 0, 0, 0, 0 }; - } else { - Rect<T> rect = *smallest; - free.erase(smallest); - - // Shorter/Longer Axis Split Rule (SAS) - // http://clb.demon.fi/files/RectangleBinPack.pdf p. 15 - // Ignore the dimension of R and just split long the shorter dimension - // See Also: http://www.cs.princeton.edu/~chazelle/pubs/blbinpacking.pdf - if (rect.w < rect.h) { - // split horizontally - // +--+---+ - // |__|___| <-- b1 - // +------+ <-- b2 - if (rect.w > width) free.emplace_back(rect.x + width, rect.y, rect.w - width, height); - if (rect.h > height) free.emplace_back(rect.x, rect.y + height, rect.w, rect.h - height); - } else { - // split vertically - // +--+---+ - // |__| | <-- b1 - // +--|---+ <-- b2 - if (rect.w > width) free.emplace_back(rect.x + width, rect.y, rect.w - width, rect.h); - if (rect.h > height) free.emplace_back(rect.x, rect.y + height, width, rect.h - height); - } - - return Rect<uint16_t>{ rect.x, rect.y, width, height }; - } - } - - - void release(Rect<T> rect) { - // Simple algorithm to recursively merge the newly released cell with its - // neighbor. This doesn't merge more than two cells at a time, and fails - // for complicated merges. - for (auto it = free.begin(); it != free.end(); ++it) { - Rect<T> ref = *it; - if (ref.y == rect.y && ref.h == rect.h && ref.x + ref.w == rect.x) { - ref.w += rect.w; - } - else if (ref.x == rect.x && ref.w == rect.w && ref.y + ref.h == rect.y) { - ref.h += rect.h; - } - else if (rect.y == ref.y && rect.h == ref.h && rect.x + rect.w == ref.x) { - ref.x = rect.x; - ref.w += rect.w; - } - else if (rect.x == ref.x && rect.w == ref.w && rect.y + rect.h == ref.y) { - ref.y = rect.y; - ref.h += rect.h; - } else { - continue; - } - - free.erase(it); - release(ref); - return; - - } - - free.emplace_back(rect); - }; - -private: - std::list<Rect<T>> free; -}; - -} // namespace mbgl diff --git a/test/geometry/binpack.test.cpp b/test/geometry/binpack.test.cpp deleted file mode 100644 index 0b74df7fa9..0000000000 --- a/test/geometry/binpack.test.cpp +++ /dev/null @@ -1,51 +0,0 @@ -#include <mbgl/test/util.hpp> - -#include <mbgl/geometry/binpack.hpp> - -#include <iosfwd> -#include <array> - -namespace mbgl { -template <typename T> ::std::ostream& operator<<(::std::ostream& os, const Rect<T>& t) { - return os << "Rect { " << t.x << ", " << t.y << ", " << t.w << ", " << t.h << " }"; -} -} // namespace mbgl - -TEST(BinPack, Allocating) { - mbgl::BinPack<uint16_t> bin(128, 128); - std::array<mbgl::Rect<uint16_t>, 4> rects; - - rects[0] = bin.allocate(32, 48); - ASSERT_EQ(mbgl::Rect<uint16_t>(0, 0, 32, 48), rects[0]); - rects[1] = bin.allocate(8, 17); - ASSERT_EQ(mbgl::Rect<uint16_t>(32, 0, 8, 17), rects[1]); - rects[2] = bin.allocate(8, 17); - ASSERT_EQ(mbgl::Rect<uint16_t>(0, 48, 8, 17), rects[2]); - - bin.release(rects[0]); - rects[0] = bin.allocate(32, 24); - ASSERT_EQ(mbgl::Rect<uint16_t>(0, 0, 32, 24), rects[0]); - rects[3] = bin.allocate(32, 24); - ASSERT_EQ(mbgl::Rect<uint16_t>(32, 17, 32, 24), rects[3]); -} - - -TEST(BinPack, Full) { - mbgl::BinPack<uint16_t> bin(128, 128); - std::vector<mbgl::Rect<uint16_t>> rects; - - for (int j = 0; j < 3; j++) { - for (int i = 0; i < 256; i++) { - auto rect = bin.allocate(8, 8); - ASSERT_TRUE(rect.hasArea()); - rects.push_back(rect); - } - - ASSERT_FALSE(bin.allocate(8, 8).hasArea()); - - for (auto& rect: rects) { - bin.release(rect); - } - rects.clear(); - } -} |