diff options
29 files changed, 450 insertions, 582 deletions
diff --git a/common/platform_default.cpp b/common/platform_default.cpp new file mode 100644 index 0000000000..1acbfa8508 --- /dev/null +++ b/common/platform_default.cpp @@ -0,0 +1,25 @@ +#include <mbgl/platform/platform.hpp> + +#include <locale> + +namespace mbgl { +namespace platform { + +std::string uppercase(const std::string& string) { + // TODO: Use a proper Unicode Special Casing-aware algorithm. + const auto &convert = std::use_facet<std::ctype<char>>(std::locale()); + std::string converted = string; + convert.toupper(&converted[0], &converted[0] + converted.size()); + return converted; +} + +std::string lowercase(const std::string& string) { + // TODO: Use a proper Unicode Special Casing-aware algorithm. + const auto &convert = std::use_facet<std::ctype<char>>(std::locale()); + std::string converted = string; + convert.tolower(&converted[0], &converted[0] + converted.size()); + return converted; +} + +} +} diff --git a/common/platform_nsstring.mm b/common/platform_nsstring.mm new file mode 100644 index 0000000000..9119f2a8fe --- /dev/null +++ b/common/platform_nsstring.mm @@ -0,0 +1,21 @@ +#import <Foundation/Foundation.h> + +#include <mbgl/platform/platform.hpp> + +namespace mbgl { +namespace platform { + +std::string uppercase(const std::string &string) { + NSString *nsstring = [[NSString alloc] initWithBytesNoCopy:const_cast<char *>(string.data()) length:string.size() encoding:NSUTF8StringEncoding freeWhenDone:NO]; + nsstring = [nsstring uppercaseString]; + return { [nsstring cStringUsingEncoding:NSUTF8StringEncoding], [nsstring lengthOfBytesUsingEncoding:NSUTF8StringEncoding] }; +} + +std::string lowercase(const std::string &string) { + NSString *nsstring = [[NSString alloc] initWithBytesNoCopy:const_cast<char *>(string.data()) length:string.size() encoding:NSUTF8StringEncoding freeWhenDone:NO]; + nsstring = [nsstring lowercaseString]; + return { [nsstring cStringUsingEncoding:NSUTF8StringEncoding], [nsstring lengthOfBytesUsingEncoding:NSUTF8StringEncoding] }; +} + +} +}
\ No newline at end of file diff --git a/include/mbgl/map/source.hpp b/include/mbgl/map/source.hpp index 5b51268bfe..4bc4c86dd0 100644 --- a/include/mbgl/map/source.hpp +++ b/include/mbgl/map/source.hpp @@ -38,6 +38,7 @@ public: void finishRender(Painter &painter); std::forward_list<Tile::ID> getIDs() const; + std::forward_list<Tile *> getLoadedTiles() const; void updateClipIDs(const std::map<Tile::ID, ClipID> &mapping); private: diff --git a/include/mbgl/map/tile.hpp b/include/mbgl/map/tile.hpp index 9cf5ff5341..24845c81a0 100644 --- a/include/mbgl/map/tile.hpp +++ b/include/mbgl/map/tile.hpp @@ -18,11 +18,15 @@ namespace mbgl { class TileData; struct ClipID { - explicit ClipID() {} - explicit ClipID(const std::bitset<8> &mask, uint8_t length) : mask(mask), length(length) {} - explicit ClipID(const std::string &mask, uint8_t length) : mask(mask), length(length) {} + inline ClipID() {} + inline ClipID(const std::string &mask_, const std::string &reference_) : mask(mask_), reference(reference_) {} + std::bitset<8> mask; - uint8_t length = 0; + std::bitset<8> reference; + + inline bool operator==(const ClipID &other) const { + return mask == other.mask && reference == other.reference; + } }; class Tile : private util::noncopyable { @@ -47,6 +51,10 @@ public: return w == rhs.w && z == rhs.z && x == rhs.x && y == rhs.y; } + inline bool operator!=(const ID& rhs) const { + return !operator==(rhs); + } + inline bool operator<(const ID &rhs) const { if (w != rhs.w) return w < rhs.w; if (z != rhs.z) return z < rhs.z; diff --git a/include/mbgl/map/tile_data.hpp b/include/mbgl/map/tile_data.hpp index 3e639fcea1..9aaef84e04 100644 --- a/include/mbgl/map/tile_data.hpp +++ b/include/mbgl/map/tile_data.hpp @@ -49,6 +49,10 @@ public: void reparse(); const std::string toString() const; + inline bool ready() const { + return state == State::parsed; + } + // Override this in the child class. virtual void beforeParse(); virtual void parse() = 0; diff --git a/include/mbgl/platform/platform.hpp b/include/mbgl/platform/platform.hpp index 43c6ce4f5e..22405a4cfd 100644 --- a/include/mbgl/platform/platform.hpp +++ b/include/mbgl/platform/platform.hpp @@ -28,6 +28,12 @@ std::shared_ptr<Request> request_http(const std::string &url, std::function<void(Response *)> callback, std::shared_ptr<uv::loop> loop = nullptr); +// Uppercase a string, potentially using platform-specific routines. +std::string uppercase(const std::string &string); + +// Lowercase a string, potentially using platform-specific routines. +std::string lowercase(const std::string &string); + // Cancels an HTTP request. void cancel_request_http(const std::shared_ptr<Request> &req); diff --git a/include/mbgl/text/collision.hpp b/include/mbgl/text/collision.hpp index 7e65e979da..8eec30f216 100644 --- a/include/mbgl/text/collision.hpp +++ b/include/mbgl/text/collision.hpp @@ -5,8 +5,9 @@ #pragma GCC diagnostic push #pragma GCC diagnostic ignored "-Wunused-parameter" +#ifdef __clang__ #pragma GCC diagnostic ignored "-Wdeprecated-register" -#ifndef __clang__ +#else #pragma GCC diagnostic ignored "-Wunused-local-typedefs" #pragma GCC diagnostic ignored "-Wmaybe-uninitialized" #endif diff --git a/include/mbgl/text/types.hpp b/include/mbgl/text/types.hpp index e2539bff62..dbb483ea8f 100644 --- a/include/mbgl/text/types.hpp +++ b/include/mbgl/text/types.hpp @@ -101,7 +101,7 @@ struct PlacementProperty { : zoom(zoom), rotationRange(rotationRange) {} inline operator bool() const { - return !isnan(zoom) && zoom != std::numeric_limits<float>::infinity() && + return !std::isnan(zoom) && zoom != std::numeric_limits<float>::infinity() && rotationRange[0] != rotationRange[1]; } diff --git a/include/mbgl/util/clip_ids.hpp b/include/mbgl/util/clip_ids.hpp index 748d3d8f5f..5855b16af7 100644 --- a/include/mbgl/util/clip_ids.hpp +++ b/include/mbgl/util/clip_ids.hpp @@ -4,15 +4,34 @@ #include <mbgl/map/tile.hpp> #include <list> #include <set> +#include <vector> +#include <forward_list> #include <map> namespace mbgl { -static constexpr uint8_t clipMask[9] { 0x00, 0x80, 0xC0, 0xE0, 0xF0, 0xF8, 0xFC, 0xFE, 0xFF }; +class ClipIDGenerator { +private: + struct Leaf { + Leaf(Tile &tile); + void add(const Tile::ID &p); + bool operator==(const Leaf &other) const; -void updateClipIDs(const std::list<Tile *> &array); + Tile &tile; + std::forward_list<Tile::ID> children; + }; + + typedef std::vector<Leaf> Pool; + std::forward_list<Pool> pools; + uint8_t bit_offset = 0; + +private: + bool reuseExisting(Leaf &leaf); + +public: + void update(std::forward_list<Tile *> tiles); +}; -std::map<Tile::ID, ClipID> computeClipIDs(std::forward_list<Tile::ID> array); } diff --git a/include/mbgl/util/math.hpp b/include/mbgl/util/math.hpp index fde2a4720b..2bef5b18e2 100644 --- a/include/mbgl/util/math.hpp +++ b/include/mbgl/util/math.hpp @@ -104,6 +104,10 @@ T smoothstep(T edge0, T edge1, T x) { return t * t * (T(3) - T(2) * t); } +// Computes the log2(x) rounded up to the next integer. +// (== number of bits required to store x) +uint32_t ceil_log2(uint64_t x); + } } diff --git a/include/mbgl/util/threadpool.hpp b/include/mbgl/util/threadpool.hpp deleted file mode 100644 index 497d4e3083..0000000000 --- a/include/mbgl/util/threadpool.hpp +++ /dev/null @@ -1,45 +0,0 @@ -#ifndef MBGL_UTIL_THREADPOOL -#define MBGL_UTIL_THREADPOOL - -#include <pthread.h> -#include <forward_list> -#include <queue> - -namespace mbgl { -namespace util { - -class Threadpool { -private: - class Worker { - public: - Worker(Threadpool& pool); - ~Worker(); - static void *loop(void *ptr); - - private: - Threadpool& pool; - pthread_t thread; - }; - -public: - Threadpool(int max_workers = 4); - typedef void (*Callback)(void *); - void add(Callback callback, void *data); - -private: - typedef std::pair<Callback, void *> Task; - const int max_workers; - pthread_mutex_t mutex = PTHREAD_MUTEX_INITIALIZER; - pthread_cond_t condition = PTHREAD_COND_INITIALIZER; - std::forward_list<Worker> workers; - int worker_count = 0; - std::queue<Task> tasks; -}; - -extern std::unique_ptr<Threadpool> threadpool; - -} -} - -#endif - diff --git a/include/mbgl/util/utf.hpp b/include/mbgl/util/utf.hpp index 5dfc4ad2d1..bb63179123 100644 --- a/include/mbgl/util/utf.hpp +++ b/include/mbgl/util/utf.hpp @@ -4,14 +4,13 @@ #include <memory> // g++/libstdc++ is missing c++11 codecvt support -#ifdef __linux__ +#if ! defined(__clang__) || defined(__linux__) #pragma GCC diagnostic push -#ifndef __clang__ #pragma GCC diagnostic ignored "-Wunused-local-typedefs" -#endif #include <boost/locale.hpp> #pragma GCC diagnostic pop #else +// Assume that codecvt is present on clang on non-linux systems #include <codecvt> #include <locale> #endif @@ -20,7 +19,7 @@ namespace mbgl { namespace util { -#ifdef __linux__ +#if ! defined(__clang__) || defined(__linux__) class utf8_to_utf32 { public: diff --git a/include/mbgl/util/vec.hpp b/include/mbgl/util/vec.hpp index 0b9bf63d53..a5fbee477b 100644 --- a/include/mbgl/util/vec.hpp +++ b/include/mbgl/util/vec.hpp @@ -71,7 +71,7 @@ struct vec2 { template<typename U = T, typename std::enable_if<std::numeric_limits<U>::has_quiet_NaN, int>::type = 0> inline operator bool() const { - return !isnan(x) && !isnan(y); + return !std::isnan(x) && !std::isnan(y); } template<typename U = T, typename std::enable_if<!std::numeric_limits<U>::has_quiet_NaN, int>::type = 0> diff --git a/linux/mapboxgl-app.gyp b/linux/mapboxgl-app.gyp index 7b703ed75c..e19768caf9 100644 --- a/linux/mapboxgl-app.gyp +++ b/linux/mapboxgl-app.gyp @@ -12,6 +12,7 @@ './main.cpp', '../common/settings_json.cpp', '../common/settings_json.hpp', + '../common/platform_default.cpp', '../common/glfw_view.hpp', '../common/glfw_view.cpp', '../common/curl_request.cpp', diff --git a/macosx/mapboxgl-app.gyp b/macosx/mapboxgl-app.gyp index 480dc2a114..da5c68ea35 100644 --- a/macosx/mapboxgl-app.gyp +++ b/macosx/mapboxgl-app.gyp @@ -12,6 +12,7 @@ './main.mm', '../common/settings_nsuserdefaults.hpp', '../common/settings_nsuserdefaults.mm', + '../common/platform_nsstring.mm', '../common/glfw_view.hpp', '../common/glfw_view.cpp', '../common/foundation_request.h', diff --git a/scripts/travis_script.sh b/scripts/travis_script.sh index 4f02c5b7e5..f8325e41cc 100755 --- a/scripts/travis_script.sh +++ b/scripts/travis_script.sh @@ -10,17 +10,19 @@ if [[ ${TRAVIS_OS_NAME} == "linux" ]]; then make linux -j4 BUILDTYPE=${BUILDTYPE} make test -j4 BUILDTYPE=${BUILDTYPE} ./scripts/run_tests.sh - (cd ./node_modules/mapbox-gl-test-suite/ && (./bin/compare_images.js || true; ./bin/deploy_results.sh)) + (cd ./node_modules/mapbox-gl-test-suite/ && (./bin/compare_images.js || true; [[ $TRAVIS_PULL_REQUEST = "false" ]] && ./bin/deploy_results.sh)) + elif [[ ${TRAVIS_OS_NAME} == "osx" ]]; then # # build OS X # make xproj-cli - xcodebuild -project ./build/macosx/mapboxgl-app.xcodeproj + xcodebuild -project ./build/macosx/mapboxgl-app.xcodeproj -jobs 4 # # build iOS # - git clone --depth 1 https://github.com/mapbox/mapbox-gl-cocoa ios/mapbox-gl-cocoa + git submodule init + git submodule update make iproj-cli - xcodebuild -project ./build/ios/mapbox-gl-cocoa/app/mapboxgl-app.xcodeproj -sdk iphonesimulator ONLY_ACTIVE_ARCH=NO + xcodebuild -project ./build/ios/mapbox-gl-cocoa/app/mapboxgl-app.xcodeproj -sdk iphonesimulator ONLY_ACTIVE_ARCH=NO -jobs 4 fi diff --git a/setup-libraries.sh b/setup-libraries.sh index bcf318ae81..e442333f49 100755 --- a/setup-libraries.sh +++ b/setup-libraries.sh @@ -51,7 +51,8 @@ set -u NODE=$(which node) NPM=$(which npm) -MP_HASH="c07b197" +MP_HASH="e741a075d28812e5d16b581e1540248fe19c52ce" +DIR_HASH=$(echo `pwd` | git hash-object --stdin) if [ ! -d 'mapnik-packaging/' ]; then git clone https://github.com/mapnik/mapnik-packaging.git fi @@ -66,9 +67,9 @@ export CXX11=true if [ ${UNAME} = 'Darwin' ]; then if [ ! -z "${TRAVIS:-}" ]; then - if aws s3 cp s3://${AWS_S3_BUCKET}/dependencies/build-cpp11-libcpp-universal_${MP_HASH}.tar.gz ./out/ ; then + if aws s3 cp s3://${AWS_S3_BUCKET}/dependencies/build-cpp11-libcpp-universal_${MP_HASH}_${DIR_HASH}.tar.gz ./out/ ; then rm -rf out/build-cpp11-libcpp-universal - tar -xzf out/build-cpp11-libcpp-universal_${MP_HASH}.tar.gz + tar -xzf out/build-cpp11-libcpp-universal_${MP_HASH}_${DIR_HASH}.tar.gz fi fi @@ -82,14 +83,14 @@ export LIBUV_VERSION=0.10.28 source iPhoneOSs.sh export LIBUV_VERSION=0.10.28 - if [ ! -f out/build-cpp11-libcpp-armv7s-iphoneos/lib/libpng.a ] ; then ./scripts/build_png.sh ; fi - if [ ! -f out/build-cpp11-libcpp-armv7s-iphoneos/lib/libuv.a ] ; then ./scripts/build_libuv.sh ; fi + if [ ! -f out/build-cpp11-libcpp-armv7s-iphoneoss/lib/libpng.a ] ; then ./scripts/build_png.sh ; fi + if [ ! -f out/build-cpp11-libcpp-armv7s-iphoneoss/lib/libuv.a ] ; then ./scripts/build_libuv.sh ; fi echo ' ...done' source iPhoneOS64.sh export LIBUV_VERSION=0.10.28 - if [ ! -f out/build-cpp11-libcpp-arm64-iphoneos/lib/libpng.a ] ; then ./scripts/build_png.sh ; fi - if [ ! -f out/build-cpp11-libcpp-arm64-iphoneos/lib/libuv.a ] ; then ./scripts/build_libuv.sh ; fi + if [ ! -f out/build-cpp11-libcpp-arm64-iphoneos64/lib/libpng.a ] ; then ./scripts/build_png.sh ; fi + if [ ! -f out/build-cpp11-libcpp-arm64-iphoneos64/lib/libuv.a ] ; then ./scripts/build_libuv.sh ; fi echo ' ...done' source iPhoneSimulator.sh @@ -117,9 +118,9 @@ export LIBUV_VERSION=0.10.28 ./scripts/make_universal.sh -if [ ! -z "${TRAVIS:-}" ]; then - tar -zcf out/build-cpp11-libcpp-universal_${MP_HASH}.tar.gz out/build-cpp11-libcpp-universal - aws s3 cp out/build-cpp11-libcpp-universal_${MP_HASH}.tar.gz s3://${AWS_S3_BUCKET}/dependencies/ +if [[ $TRAVIS_PULL_REQUEST = "false" ]]; then + tar -zcf out/build-cpp11-libcpp-universal_${MP_HASH}_${DIR_HASH}.tar.gz out/build-cpp11-libcpp-universal + aws s3 cp --acl public-read out/build-cpp11-libcpp-universal_${MP_HASH}_${DIR_HASH}.tar.gz s3://${AWS_S3_BUCKET}/dependencies/ fi fi @@ -149,10 +150,10 @@ export LIBUV_VERSION=0.10.28 if [ ! -f out/build-cpp11-libstdcpp-gcc-x86_64-linux/lib/libcurl.a ] ; then ./scripts/build_curl.sh ; fi if [ ! -f out/build-cpp11-libstdcpp-gcc-x86_64-linux/lib/libboost_regex.a ] ; then ./scripts/build_boost.sh --with-regex ; fi -if [ ! -z "${TRAVIS:-}" ]; then +if [[ $TRAVIS_PULL_REQUEST = "false" ]]; then if ! tar --compare -zf out/build-cpp11-libstdcpp-gcc-x86_64-linux.tar.gz ; then tar -zcf out/build-cpp11-libstdcpp-gcc-x86_64-linux.tar.gz out/build-cpp11-libstdcpp-gcc-x86_64-linux - aws s3 cp out/build-cpp11-libstdcpp-gcc-x86_64-linux.tar.gz s3://${AWS_S3_BUCKET}/dependencies/ + aws s3 cp --acl public-read out/build-cpp11-libstdcpp-gcc-x86_64-linux.tar.gz s3://${AWS_S3_BUCKET}/dependencies/ fi fi diff --git a/src/map/map.cpp b/src/map/map.cpp index 8590b464bb..b657ab6890 100644 --- a/src/map/map.cpp +++ b/src/map/map.cpp @@ -511,18 +511,12 @@ void Map::updateTiles() { } void Map::updateRenderState() { - std::forward_list<Tile::ID> ids; - + // Update all clipping IDs. + ClipIDGenerator generator; for (const std::shared_ptr<StyleSource> &source : getActiveSources()) { - ids.splice_after(ids.before_begin(), source->source->getIDs()); + generator.update(source->source->getLoadedTiles()); source->source->updateMatrices(painter.projMatrix, state); } - - const std::map<Tile::ID, ClipID> clipIDs = computeClipIDs(ids); - - for (const std::shared_ptr<StyleSource> &source : getActiveSources()) { - source->source->updateClipIDs(clipIDs); - } } void Map::prepare() { diff --git a/src/map/source.cpp b/src/map/source.cpp index b83384f25f..3fe5bf42fa 100644 --- a/src/map/source.cpp +++ b/src/map/source.cpp @@ -121,7 +121,6 @@ void Source::finishRender(Painter &painter) { } } - std::forward_list<Tile::ID> Source::getIDs() const { std::forward_list<Tile::ID> ptrs; @@ -132,6 +131,18 @@ std::forward_list<Tile::ID> Source::getIDs() const { return ptrs; } +std::forward_list<Tile *> Source::getLoadedTiles() const { + std::forward_list<Tile *> ptrs; + auto it = ptrs.before_begin(); + for (const auto &pair : tiles) { + if (pair.second->data->ready()) { + it = ptrs.insert_after(it, pair.second.get()); + } + } + return ptrs; +} + + TileData::State Source::hasTile(const Tile::ID& id) { auto it = tiles.find(id); if (it != tiles.end()) { diff --git a/src/renderer/painter.cpp b/src/renderer/painter.cpp index e813ad24eb..240aff6887 100644 --- a/src/renderer/painter.cpp +++ b/src/renderer/painter.cpp @@ -169,9 +169,9 @@ void Painter::setStrata(float value) { } void Painter::prepareTile(const Tile& tile) { - GLint id = (GLint)tile.clip.mask.to_ulong(); - GLuint mask = clipMask[tile.clip.length]; - glStencilFunc(GL_EQUAL, id, mask); + const GLint ref = (GLint)tile.clip.reference.to_ulong(); + const GLuint mask = (GLuint)tile.clip.mask.to_ulong(); + glStencilFunc(GL_EQUAL, ref, mask); } void Painter::renderTileLayer(const Tile& tile, std::shared_ptr<StyleLayer> layer_desc, const mat4 &matrix) { diff --git a/src/renderer/painter_clipping.cpp b/src/renderer/painter_clipping.cpp index e94646d922..d8fa3693bd 100644 --- a/src/renderer/painter_clipping.cpp +++ b/src/renderer/painter_clipping.cpp @@ -14,7 +14,6 @@ void Painter::drawClippingMasks(const std::set<std::shared_ptr<StyleSource>> &so depthMask(false); glColorMask(false, false, false, false); depthRange(1.0f, 1.0f); - glStencilMask(0xFF); coveringPlainArray.bind(*plainShader, tileStencilBuffer, BUFFER_OFFSET(0)); @@ -31,9 +30,10 @@ void Painter::drawClippingMasks(const std::set<std::shared_ptr<StyleSource>> &so void Painter::drawClippingMask(const mat4& matrix, const ClipID &clip) { plainShader->setMatrix(matrix); - GLint id = static_cast<GLint>(clip.mask.to_ulong()); - GLuint mask = clipMask[clip.length]; - glStencilFunc(GL_ALWAYS, id, mask); + const GLint ref = (GLint)(clip.reference.to_ulong()); + const GLuint mask = (GLuint)(clip.mask.to_ulong()); + glStencilFunc(GL_ALWAYS, ref, mask); + glStencilMask(mask); glDrawArrays(GL_TRIANGLES, 0, (GLsizei)tileStencilBuffer.index()); } diff --git a/src/renderer/symbol_bucket.cpp b/src/renderer/symbol_bucket.cpp index e8c0fd1829..fd89315096 100644 --- a/src/renderer/symbol_bucket.cpp +++ b/src/renderer/symbol_bucket.cpp @@ -75,11 +75,10 @@ std::vector<SymbolFeature> SymbolBucket::processFeatures(const VectorTileLayer & if (text) { std::string u8string = util::replaceTokens(properties.text.field, feature.properties); - auto &convert = std::use_facet<std::ctype<char>>(std::locale()); if (properties.text.transform == TextTransformType::Uppercase) { - convert.toupper(&u8string[0], &u8string[0] + u8string.size()); + u8string = platform::uppercase(u8string); } else if (properties.text.transform == TextTransformType::Lowercase) { - convert.tolower(&u8string[0], &u8string[0] + u8string.size()); + u8string = platform::lowercase(u8string); } ft.label = ucs4conv.convert(u8string); @@ -296,7 +295,7 @@ void SymbolBucket::addFeature(const std::vector<Coordinate> &line, const Shaping } // Insert final placement into collision tree and add glyphs/icons to buffers - if (glyphScale) { + if (glyphScale && std::isfinite(glyphScale)) { if (!properties.text.ignore_placement) { collision.insert(glyphPlacement.boxes, anchor, glyphScale, glyphRange, horizontalText); @@ -304,7 +303,7 @@ void SymbolBucket::addFeature(const std::vector<Coordinate> &line, const Shaping if (inside) addSymbols(text, glyphPlacement.shapes, glyphScale, glyphRange); } - if (iconScale) { + if (iconScale && std::isfinite(iconScale)) { if (!properties.icon.ignore_placement) { collision.insert(iconPlacement.boxes, anchor, iconScale, iconRange, horizontalIcon); } diff --git a/src/text/collision.cpp b/src/text/collision.cpp index 89e91d6844..6326bea825 100644 --- a/src/text/collision.cpp +++ b/src/text/collision.cpp @@ -166,10 +166,10 @@ float Collision::getPlacementScale(const GlyphBoxes &glyphs, float minPlacementS float s4 = (ob.br.y - nb.tl.y + padding) / (na.y - oa.y); // scale at which new box is to the bottom of old box - if (isnan(s1) || isnan(s2)) { + if (std::isnan(s1) || std::isnan(s2)) { s1 = s2 = 1; } - if (isnan(s3) || isnan(s4)) { + if (std::isnan(s3) || std::isnan(s4)) { s3 = s4 = 1; } diff --git a/src/text/rotation_range.cpp b/src/text/rotation_range.cpp index 3ebdfe91cb..664ea9c709 100644 --- a/src/text/rotation_range.cpp +++ b/src/text/rotation_range.cpp @@ -95,7 +95,7 @@ rotatingRotatingCollisions(const CollisionRect &a, const CollisionRect &b, std::vector<float> f; for (size_t i = 0; i < c.size(); i++) { // Check if they are close enough to collide - if (!isnan(c[i]) && d_sq <= e[i]) { + if (!std::isnan(c[i]) && d_sq <= e[i]) { // So far, angles have been calulated as relative to the vector // between anchors. // Convert the angles to angles from north. diff --git a/src/util/clip_ids.cpp b/src/util/clip_ids.cpp index d815876a06..9c391c38ad 100644 --- a/src/util/clip_ids.cpp +++ b/src/util/clip_ids.cpp @@ -12,187 +12,85 @@ namespace mbgl { -struct TileHierarchy { - TileHierarchy(Tile::ID id, std::list<TileHierarchy> &&children) - : id(id), children(std::move(children)) {} - - const Tile::ID id; - ClipID clip; - std::list<TileHierarchy> children; -}; - -std::list<TileHierarchy> partition(std::forward_list<Tile::ID> &&array) { - if (array.empty()) { - // We don't have to update the clipping mask because there are no tiles - // anyway. - return {}; - } - - int8_t minZ = array.begin()->z; - - std::list<TileHierarchy> result; - std::forward_list<Tile::ID> remainder; - auto remainder_it = remainder.before_begin(); - - while (!array.empty()) { - const Tile::ID id = array.front(); - array.pop_front(); - if (id.z == minZ) { - std::forward_list<Tile::ID> children; - auto children_it = children.before_begin(); - - array.remove_if([&id, &children, &children_it](const Tile::ID &child) { - if (child.isChildOf(id)) { - children_it = children.insert_after(children_it, child); - return true; - } else { - return false; - } - }); - - result.emplace_back(id, partition(std::move(children))); - } else { - remainder_it = remainder.insert_after(remainder_it, id); +ClipIDGenerator::Leaf::Leaf(Tile &tile_) : tile(tile_) {} + +void ClipIDGenerator::Leaf::add(const Tile::ID &p) { + if (p.isChildOf(tile.id)) { + // Ensure that no already present child is a parent of the new p. + for (const Tile::ID &child : children) { + if (p.isChildOf(child)) + return; } + children.push_front(p); } - - // Concatenate the remainder. - if (!remainder.empty()) { - result.splice(result.begin(), partition(std::move(remainder))); - } - - return result; } -uint8_t prefix(std::list<TileHierarchy> &array, TileHierarchy *parent = nullptr) { - if (array.empty()) { - return 0; - } - - bool all_children_are_immediate = true; - uint8_t max_child_prefix_length = 0; - - struct Huffman { - explicit Huffman(int prefix_length, TileHierarchy *item) - : prefix_length(prefix_length), children(1, item) {} - uint8_t prefix_length; - std::vector<TileHierarchy *> children; - }; - - // Create a temporary structure that we use for sorting the prefix tree. - std::list<Huffman> huffman; - std::transform(array.begin(), array.end(), std::back_inserter(huffman), [parent, &all_children_are_immediate, &max_child_prefix_length](TileHierarchy &item) { - uint8_t prefix_length = prefix(item.children, &item); +bool ClipIDGenerator::Leaf::operator==(const Leaf &other) const { + return tile.id == other.tile.id && children == other.children; +} - if (prefix_length > max_child_prefix_length) { - max_child_prefix_length = prefix_length; +bool ClipIDGenerator::reuseExisting(Leaf &leaf) { + for (const std::vector<Leaf> &pool : pools) { + auto existing = std::find(pool.begin(), pool.end(), leaf); + if (existing != pool.end()) { + leaf.tile.clip = existing->tile.clip; + return true; } + } + return false; +} - if (!parent || item.id.z != parent->id.z + 1) { - all_children_are_immediate = false; - } +void ClipIDGenerator::update(std::forward_list<Tile *> tiles) { + Pool pool; - return Huffman { prefix_length + 1, &item }; + tiles.sort([](const Tile *a, const Tile *b) { + return a->id < b->id; }); - while (huffman.size() > 1) { - huffman.sort([](const Huffman &a, const Huffman &b) { - return a.prefix_length < b.prefix_length; - }); - - Huffman &first = *huffman.begin(); - Huffman &second = *(++huffman.begin()); - - assert(&first != &second); - - // Prefix with 0 - std::for_each(first.children.begin(), first.children.end(), [](TileHierarchy *child) { - child->clip.mask >>= 1; - child->clip.mask.set(7, false); // noop - child->clip.length++; - }); - first.prefix_length++; - - // Prefix with 1 - std::for_each(second.children.begin(), second.children.end(), [](TileHierarchy *child) { - child->clip.mask >>= 1; - child->clip.mask.set(7, true); - child->clip.length++; - }); - second.prefix_length++; - - second.children.insert(second.children.end(), first.children.begin(), first.children.end()); - second.prefix_length = first.prefix_length + second.prefix_length; - - // Remove the first child as we've just merged it into the second version. - huffman.erase(huffman.begin()); - } - - uint8_t prefix_length = 0; + const auto end = tiles.end(); + for (auto it = tiles.begin(); it != end; it++) { + if (!*it) { + // Handle null pointers. + continue; + } - // Filter out all-zero bits - bool filter_zero = !all_children_are_immediate || array.size() != 4; + Tile &tile = **it; + Leaf clip { tile }; - for (TileHierarchy &item : array) { - if (filter_zero && !item.clip.mask.any()) { - // Make sure we don't have a prefix that is all zeros. - // item.clip.mask |= (0x80 >> item.length); - item.clip.mask.set(7 - item.clip.length); - item.clip.length++; + // Try to add all remaining ids as children. We sorted the tile list + // by z earlier, so all preceding items cannot be children of the current + // tile. + for (auto child_it = std::next(it); child_it != end; child_it++) { + clip.add((*child_it)->id); } + clip.children.sort(); - if (item.clip.length > prefix_length) { - prefix_length = item.clip.length; + // Loop through all existing pools and try to find a matching ClipID. + if (!reuseExisting(clip)) { + // We haven't found an existing clip ID + pool.push_back(std::move(clip)); } } - return max_child_prefix_length + prefix_length; -} - -void propagate(std::map<Tile::ID, ClipID> &mapping, std::list<TileHierarchy> &array, const ClipID &parent = ClipID{}) { - for (auto &item : array) { - item.clip.mask >>= parent.length; - item.clip.mask |= parent.mask; - item.clip.length += parent.length; -#if defined(DEBUG) - auto result = mapping.emplace(item.id, item.clip); - assert("Tried to insert a duplicate item" && result.second == true); -#else - mapping.emplace(item.id, item.clip); -#endif - propagate(mapping, item.children, const_cast<const ClipID &>(item.clip)); - }; -} - -void updateClipIDs(const std::list<Tile *> &array) { - std::forward_list<Tile::ID> ids; - std::transform(array.begin(), array.end(), std::front_inserter(ids), [](Tile *item) { - return item->id; - }); + if (pool.size()) { + const uint32_t bit_count = util::ceil_log2(pool.size() + 1); + const std::bitset<8> mask = uint64_t(((1 << bit_count) - 1) << bit_offset); - const std::map<Tile::ID, ClipID> mapping = computeClipIDs(ids); - - std::for_each(array.begin(), array.end(), [&mapping](Tile *item) { - auto it = mapping.find(item->id); - if (it != mapping.end()) { - item->clip = it->second; - } else { - item->clip = ClipID {}; + // We are starting our count with 1 since we need at least 1 bit set to distinguish between + // areas without any tiles whatsoever and the current area. + uint8_t count = 1; + for (Leaf &leaf : pool) { + leaf.tile.clip.mask = mask; + leaf.tile.clip.reference = count++ << bit_offset; } - }); -} -std::map<Tile::ID, ClipID> computeClipIDs(std::forward_list<Tile::ID> array) { - // Sort by zoom level and make sure that we don't have duplicate elements. - array.sort(); - array.unique(); - - std::list<TileHierarchy> hierarchy = partition(std::move(array)); - prefix(hierarchy); + bit_offset += bit_count; + pools.push_front(std::move(pool)); + } - std::map<Tile::ID, ClipID> mapping; - propagate(mapping, hierarchy); - return mapping; + if (bit_offset > 8) { + fprintf(stderr, "stencil mask overflow\n"); + } } } diff --git a/src/util/math.cpp b/src/util/math.cpp new file mode 100644 index 0000000000..a7eab2d771 --- /dev/null +++ b/src/util/math.cpp @@ -0,0 +1,25 @@ +#include <mbgl/util/math.hpp> + +namespace mbgl { +namespace util { + +// From http://stackoverflow.com/questions/3272424/compute-fast-log-base-2-ceiling +uint32_t ceil_log2(uint64_t x) { + static const uint64_t t[6] = {0xFFFFFFFF00000000, 0x00000000FFFF0000, + 0x000000000000FF00, 0x00000000000000F0, + 0x000000000000000C, 0x0000000000000002}; + uint32_t y = (((x & (x - 1)) == 0) ? 0 : 1); + uint32_t j = 32; + + for (int32_t i = 0; i < 6; i++) { + const uint32_t k = (((x & t[i]) == 0) ? 0 : j); + y += k; + x >>= k; + j >>= 1; + } + + return y; +} + +} +}
\ No newline at end of file diff --git a/src/util/threadpool.cpp b/src/util/threadpool.cpp deleted file mode 100644 index f19032ee01..0000000000 --- a/src/util/threadpool.cpp +++ /dev/null @@ -1,54 +0,0 @@ -#include <mbgl/util/threadpool.hpp> -#include <mbgl/util/std.hpp> -#include <thread> -#include <memory> - -using namespace mbgl::util; - -std::unique_ptr<Threadpool> mbgl::util::threadpool = std::make_unique<Threadpool>(std::thread::hardware_concurrency()); - -Threadpool::Threadpool(int max_workers) - : max_workers(max_workers) { -} - -void Threadpool::add(Callback callback, void *data) { - if (worker_count < max_workers) { - worker_count++; - workers.emplace_front(*this); - } - - pthread_mutex_lock(&mutex); - tasks.push(std::make_pair(callback, data)); - pthread_mutex_unlock(&mutex); - pthread_cond_signal(&condition); -} - -Threadpool::Worker::Worker(Threadpool& pool) - : pool(pool) { - pthread_create(&thread, nullptr, loop, (void *)this); -} - -Threadpool::Worker::~Worker() { - pthread_cancel(thread); -} - - -void *Threadpool::Worker::loop(void *ptr) { - Worker *worker = static_cast<Worker *>(ptr); - Threadpool& pool = worker->pool; - - pthread_mutex_lock(&pool.mutex); - while (true) { - if (pool.tasks.size()) { - Threadpool::Task task = pool.tasks.front(); - pool.tasks.pop(); - pthread_mutex_unlock(&pool.mutex); - task.first(task.second); - pthread_mutex_lock(&pool.mutex); - } else { - pthread_cond_wait(&pool.condition, &pool.mutex); - } - } - - return nullptr; -} diff --git a/test/clip_ids.cpp b/test/clip_ids.cpp index f2e8be98bc..18ef9658e5 100644 --- a/test/clip_ids.cpp +++ b/test/clip_ids.cpp @@ -8,298 +8,244 @@ using namespace mbgl; -TEST(ClipIDs, ClipMasks) { - ASSERT_EQ(0, clipMask[0]); - ASSERT_EQ(0x80, clipMask[1]); - ASSERT_EQ(0xC0, clipMask[2]); - ASSERT_EQ(0xE0, clipMask[3]); - ASSERT_EQ(0xF0, clipMask[4]); - ASSERT_EQ(0xF8, clipMask[5]); - ASSERT_EQ(0xFC, clipMask[6]); - ASSERT_EQ(0xFE, clipMask[7]); - ASSERT_EQ(0xFF, clipMask[8]); +template <typename T> void generate(const T &sources) { + ClipIDGenerator generator; + + for (size_t j = 0; j < sources.size(); j++) { + std::forward_list<Tile *> tile_ptrs; + std::transform(sources[j].begin(), sources[j].end(), std::front_inserter(tile_ptrs), [](const std::shared_ptr<Tile> &tile) { return tile.get(); }); + generator.update(tile_ptrs); + } } +template <typename T> void print(const T &sources) { + for (size_t j = 0; j < sources.size(); j++) { + for (size_t i = 0; i < sources[j].size(); i++) { + std::cout << " ASSERT_EQ(ClipID(\"" << sources[j][i]->clip.mask << "\", \"" << sources[j][i]->clip.reference << "\"), sources[" << j << "][" << i << "]->clip);\n"; + } + } +} TEST(ClipIDs, ParentAndFourChildren) { - std::array<std::unique_ptr<Tile>, 5> tiles {{ - std::make_unique<Tile>(Tile::ID { 1, 0, 0 }), // 1/0/0: 11000000 (3) - std::make_unique<Tile>(Tile::ID { 1, 0, 1 }), // 1/0/1: 11100000 (3) - std::make_unique<Tile>(Tile::ID { 1, 1, 0 }), // 1/1/0: 10000000 (3) - std::make_unique<Tile>(Tile::ID { 1, 1, 1 }), // 1/1/1: 10100000 (3) - std::make_unique<Tile>(Tile::ID { 0, 0, 0 }), // 0/0/0: 10000000 (1) - }}; - - std::list<Tile *> tile_ptrs; - std::transform(tiles.begin(), tiles.end(), std::back_inserter(tile_ptrs), [](std::unique_ptr<Tile> &tile) { return tile.get(); }); - - updateClipIDs(tile_ptrs); - - // for (const auto &it : tiles) { - // std::cout << std::string(it->id) << ": " << it->clip.mask << " (" << (int)it->clip.length << ")" << std::endl; - // } - - ASSERT_EQ(std::bitset<8>("11000000"), tiles[0]->clip.mask); ASSERT_EQ(3, tiles[0]->clip.length); - ASSERT_EQ(std::bitset<8>("11100000"), tiles[1]->clip.mask); ASSERT_EQ(3, tiles[1]->clip.length); - ASSERT_EQ(std::bitset<8>("10000000"), tiles[2]->clip.mask); ASSERT_EQ(3, tiles[2]->clip.length); - ASSERT_EQ(std::bitset<8>("10100000"), tiles[3]->clip.mask); ASSERT_EQ(3, tiles[3]->clip.length); - ASSERT_EQ(std::bitset<8>("10000000"), tiles[4]->clip.mask); ASSERT_EQ(1, tiles[4]->clip.length); + const std::vector<std::vector<std::shared_ptr<Tile>>> sources = { + { + std::make_shared<Tile>(Tile::ID { 1, 0, 0 }), + std::make_shared<Tile>(Tile::ID { 1, 0, 1 }), + std::make_shared<Tile>(Tile::ID { 1, 1, 0 }), + std::make_shared<Tile>(Tile::ID { 1, 1, 1 }), + std::make_shared<Tile>(Tile::ID { 0, 0, 0 }), + }, + }; + + generate(sources); + // print(sources); + + ASSERT_EQ(ClipID("00000111", "00000010"), sources[0][0]->clip); + ASSERT_EQ(ClipID("00000111", "00000011"), sources[0][1]->clip); + ASSERT_EQ(ClipID("00000111", "00000100"), sources[0][2]->clip); + ASSERT_EQ(ClipID("00000111", "00000101"), sources[0][3]->clip); + ASSERT_EQ(ClipID("00000111", "00000001"), sources[0][4]->clip); } TEST(ClipIDs, ParentAndFourChildrenNegative) { - std::array<std::unique_ptr<Tile>, 5> tiles {{ - std::make_unique<Tile>(Tile::ID { 1, -2, 0 }), // 1/0/0: 11000000 (3) - std::make_unique<Tile>(Tile::ID { 1, -2, 1 }), // 1/0/1: 11100000 (3) - std::make_unique<Tile>(Tile::ID { 1, -1, 0 }), // 1/1/0: 10000000 (3) - std::make_unique<Tile>(Tile::ID { 1, -1, 1 }), // 1/1/1: 10100000 (3) - std::make_unique<Tile>(Tile::ID { 0, -1, 0 }), // 0/0/0: 10000000 (1) - }}; - - std::list<Tile *> tile_ptrs; - std::transform(tiles.begin(), tiles.end(), std::back_inserter(tile_ptrs), [](std::unique_ptr<Tile> &tile) { return tile.get(); }); - - updateClipIDs(tile_ptrs); - - // for (const auto &it : tiles) { - // std::cout << std::string(it->id) << ": " << it->clip.mask << " (" << (int)it->clip.length << ")" << std::endl; - // } - - ASSERT_EQ(std::bitset<8>("11000000"), tiles[0]->clip.mask); ASSERT_EQ(3, tiles[0]->clip.length); - ASSERT_EQ(std::bitset<8>("11100000"), tiles[1]->clip.mask); ASSERT_EQ(3, tiles[1]->clip.length); - ASSERT_EQ(std::bitset<8>("10000000"), tiles[2]->clip.mask); ASSERT_EQ(3, tiles[2]->clip.length); - ASSERT_EQ(std::bitset<8>("10100000"), tiles[3]->clip.mask); ASSERT_EQ(3, tiles[3]->clip.length); - ASSERT_EQ(std::bitset<8>("10000000"), tiles[4]->clip.mask); ASSERT_EQ(1, tiles[4]->clip.length); + const std::vector<std::vector<std::shared_ptr<Tile>>> sources = { + { + std::make_shared<Tile>(Tile::ID { 1, -2, 0 }), + std::make_shared<Tile>(Tile::ID { 1, -2, 1 }), + std::make_shared<Tile>(Tile::ID { 1, -1, 0 }), + std::make_shared<Tile>(Tile::ID { 1, -1, 1 }), + std::make_shared<Tile>(Tile::ID { 0, -1, 0 }), + }, + }; + + generate(sources); + // print(sources); + + ASSERT_EQ(ClipID("00000111", "00000010"), sources[0][0]->clip); + ASSERT_EQ(ClipID("00000111", "00000011"), sources[0][1]->clip); + ASSERT_EQ(ClipID("00000111", "00000100"), sources[0][2]->clip); + ASSERT_EQ(ClipID("00000111", "00000101"), sources[0][3]->clip); + ASSERT_EQ(ClipID("00000111", "00000001"), sources[0][4]->clip); } TEST(ClipIDs, NegativeParentAndMissingLevel) { - std::array<std::unique_ptr<Tile>, 5> tiles {{ - std::make_unique<Tile>(Tile::ID { 1, -1, 0 }), // 1/-1/0: 10000000 (1) - std::make_unique<Tile>(Tile::ID { 2, -1, 0 }), // 2/-1/0: 10000000 (3) - std::make_unique<Tile>(Tile::ID { 2, -2, 1 }), // 2/-2/1: 11100000 (3) - std::make_unique<Tile>(Tile::ID { 2, -1, 1 }), // 2/-1/1: 10100000 (3) - std::make_unique<Tile>(Tile::ID { 2, -2, 0 }), // 2/-2/0: 11000000 (3) - }}; - - std::list<Tile *> tile_ptrs; - std::transform(tiles.begin(), tiles.end(), std::back_inserter(tile_ptrs), [](std::unique_ptr<Tile> &tile) { return tile.get(); }); - - updateClipIDs(tile_ptrs); - - // for (const auto &it : tiles) { - // std::cout << std::string(it->id) << ": " << it->clip.mask << " (" << (int)it->clip.length << ")" << std::endl; - // } - - ASSERT_EQ(std::bitset<8>("10000000"), tiles[0]->clip.mask); ASSERT_EQ(1, tiles[0]->clip.length); - ASSERT_EQ(std::bitset<8>("10000000"), tiles[1]->clip.mask); ASSERT_EQ(3, tiles[1]->clip.length); - ASSERT_EQ(std::bitset<8>("11100000"), tiles[2]->clip.mask); ASSERT_EQ(3, tiles[2]->clip.length); - ASSERT_EQ(std::bitset<8>("10100000"), tiles[3]->clip.mask); ASSERT_EQ(3, tiles[3]->clip.length); - ASSERT_EQ(std::bitset<8>("11000000"), tiles[4]->clip.mask); ASSERT_EQ(3, tiles[4]->clip.length); + const std::vector<std::vector<std::shared_ptr<Tile>>> sources = { + { + std::make_shared<Tile>(Tile::ID { 1, -1, 0 }), + std::make_shared<Tile>(Tile::ID { 2, -1, 0 }), + std::make_shared<Tile>(Tile::ID { 2, -2, 1 }), + std::make_shared<Tile>(Tile::ID { 2, -1, 1 }), + std::make_shared<Tile>(Tile::ID { 2, -2, 0 }), + }, + }; + + generate(sources); + // print(sources); + + ASSERT_EQ(ClipID("00000111", "00000001"), sources[0][0]->clip); + ASSERT_EQ(ClipID("00000111", "00000100"), sources[0][1]->clip); + ASSERT_EQ(ClipID("00000111", "00000011"), sources[0][2]->clip); + ASSERT_EQ(ClipID("00000111", "00000101"), sources[0][3]->clip); + ASSERT_EQ(ClipID("00000111", "00000010"), sources[0][4]->clip); } TEST(ClipIDs, SevenOnSameLevel) { - std::array<std::unique_ptr<Tile>, 7> tiles {{ - std::make_unique<Tile>(Tile::ID { 2, 0, 0 }), // 2/0/0: 11000000 (3) - std::make_unique<Tile>(Tile::ID { 2, 0, 1 }), // 2/0/1: 11100000 (3) - std::make_unique<Tile>(Tile::ID { 2, 0, 2 }), // 2/0/2: 10000000 (3) - std::make_unique<Tile>(Tile::ID { 2, 1, 0 }), // 2/1/0: 10100000 (3) - std::make_unique<Tile>(Tile::ID { 2, 1, 1 }), // 2/1/1: 01000000 (3) - std::make_unique<Tile>(Tile::ID { 2, 1, 2 }), // 2/1/2: 01100000 (3) - std::make_unique<Tile>(Tile::ID { 2, 2, 0 }), // 2/2/0: 00100000 (3) - }}; - - std::list<Tile *> tile_ptrs; - std::transform(tiles.begin(), tiles.end(), std::back_inserter(tile_ptrs), [](std::unique_ptr<Tile> &tile) { return tile.get(); }); - - updateClipIDs(tile_ptrs); - - // for (const auto &it : tiles) { - // std::cout << std::string(it->id) << ": " << it->clip.mask << " (" << (int)it->clip.length << ")" << std::endl; - // } - - ASSERT_EQ(std::bitset<8>("11000000"), tiles[0]->clip.mask); ASSERT_EQ(3, tiles[0]->clip.length); - ASSERT_EQ(std::bitset<8>("11100000"), tiles[1]->clip.mask); ASSERT_EQ(3, tiles[1]->clip.length); - ASSERT_EQ(std::bitset<8>("10000000"), tiles[2]->clip.mask); ASSERT_EQ(3, tiles[2]->clip.length); - ASSERT_EQ(std::bitset<8>("10100000"), tiles[3]->clip.mask); ASSERT_EQ(3, tiles[3]->clip.length); - ASSERT_EQ(std::bitset<8>("01000000"), tiles[4]->clip.mask); ASSERT_EQ(3, tiles[4]->clip.length); - ASSERT_EQ(std::bitset<8>("01100000"), tiles[5]->clip.mask); ASSERT_EQ(3, tiles[5]->clip.length); - ASSERT_EQ(std::bitset<8>("00100000"), tiles[6]->clip.mask); ASSERT_EQ(3, tiles[6]->clip.length); + const std::vector<std::vector<std::shared_ptr<Tile>>> sources = { + { + std::make_shared<Tile>(Tile::ID { 2, 0, 0 }), + std::make_shared<Tile>(Tile::ID { 2, 0, 1 }), + std::make_shared<Tile>(Tile::ID { 2, 0, 2 }), + std::make_shared<Tile>(Tile::ID { 2, 1, 0 }), + std::make_shared<Tile>(Tile::ID { 2, 1, 1 }), + std::make_shared<Tile>(Tile::ID { 2, 1, 2 }), + std::make_shared<Tile>(Tile::ID { 2, 2, 0 }), + }, + }; + + generate(sources); + // print(sources); + + ASSERT_EQ(ClipID("00000111", "00000001"), sources[0][0]->clip); + ASSERT_EQ(ClipID("00000111", "00000010"), sources[0][1]->clip); + ASSERT_EQ(ClipID("00000111", "00000011"), sources[0][2]->clip); + ASSERT_EQ(ClipID("00000111", "00000100"), sources[0][3]->clip); + ASSERT_EQ(ClipID("00000111", "00000101"), sources[0][4]->clip); + ASSERT_EQ(ClipID("00000111", "00000110"), sources[0][5]->clip); + ASSERT_EQ(ClipID("00000111", "00000111"), sources[0][6]->clip); } TEST(ClipIDs, MultipleLevels) { - std::array<std::unique_ptr<Tile>, 12> tiles {{ - std::make_unique<Tile>(Tile::ID { 2, 0, 0 }), // 2/0/0: 10000000 (1) - std::make_unique<Tile>(Tile::ID { 3, 0, 0 }), // 3/0/0: 10000000 (3) - std::make_unique<Tile>(Tile::ID { 3, 0, 1 }), // 3/0/1: 11100000 (3) - std::make_unique<Tile>(Tile::ID { 4, 0, 2 }), // 4/0/2: 11110000 (5) - std::make_unique<Tile>(Tile::ID { 4, 1, 2 }), // 4/0/3: 11111000 (5) - std::make_unique<Tile>(Tile::ID { 4, 0, 3 }), // 4/1/2: 11100000 (5) - std::make_unique<Tile>(Tile::ID { 4, 1, 3 }), // 4/1/3: 11101000 (5) - std::make_unique<Tile>(Tile::ID { 3, 1, 0 }), // 3/1/0: 10100000 (3) - std::make_unique<Tile>(Tile::ID { 3, 1, 1 }), // 3/1/1: 11000000 (3) - std::make_unique<Tile>(Tile::ID { 2, 1, 0 }), // 2/1/0: 01000000 (2) - std::make_unique<Tile>(Tile::ID { 3, 2, 0 }), // 3/2/0: 01010000 (4) - std::make_unique<Tile>(Tile::ID { 3, 2, 1 }), // 3/2/1: 01100000 (3) - }}; - - // Use a random order to verify that the result of this algorithm is independent of the - std::random_shuffle(tiles.begin(), tiles.end()); - - std::list<Tile *> tile_ptrs; - std::transform(tiles.begin(), tiles.end(), std::back_inserter(tile_ptrs), [](std::unique_ptr<Tile> &tile) { return tile.get(); }); - - updateClipIDs(tile_ptrs); - - // Sort them by tile ID so that we know what order we have to test in. - std::sort(tiles.begin(), tiles.end(), [](const std::unique_ptr<Tile> &a, const std::unique_ptr<Tile> &b) { - return a->id < b->id; - }); - - // for (const auto &it : tiles) { - // std::cout << std::string(it->id) << ": " << it->clip.mask << " (" << (int)it->clip.length << ")" << std::endl; - // } - - ASSERT_EQ(std::string("2/0/0"), std::string(tiles[0]->id)); - ASSERT_EQ(std::bitset<8>("10000000"), tiles[0]->clip.mask); - ASSERT_EQ(1, tiles[0]->clip.length); - - ASSERT_EQ(std::string("2/1/0"), std::string(tiles[1]->id)); - ASSERT_EQ(std::bitset<8>("01000000"), tiles[1]->clip.mask); - ASSERT_EQ(2, tiles[1]->clip.length); - - ASSERT_EQ(std::string("3/0/0"), std::string(tiles[2]->id)); - ASSERT_EQ(std::bitset<8>("10000000"), tiles[2]->clip.mask); - ASSERT_EQ(3, tiles[2]->clip.length); - - ASSERT_EQ(std::string("3/0/1"), std::string(tiles[3]->id)); - ASSERT_EQ(std::bitset<8>("11100000"), tiles[3]->clip.mask); - ASSERT_EQ(3, tiles[3]->clip.length); - - ASSERT_EQ(std::string("3/1/0"), std::string(tiles[4]->id)); - ASSERT_EQ(std::bitset<8>("10100000"), tiles[4]->clip.mask); - ASSERT_EQ(3, tiles[4]->clip.length); - - ASSERT_EQ(std::string("3/1/1"), std::string(tiles[5]->id)); - ASSERT_EQ(std::bitset<8>("11000000"), tiles[5]->clip.mask); - ASSERT_EQ(3, tiles[5]->clip.length); - - ASSERT_EQ(std::string("3/2/0"), std::string(tiles[6]->id)); - ASSERT_EQ(std::bitset<8>("01010000"), tiles[6]->clip.mask); - ASSERT_EQ(4, tiles[6]->clip.length); - - ASSERT_EQ(std::string("3/2/1"), std::string(tiles[7]->id)); - ASSERT_EQ(std::bitset<8>("01100000"), tiles[7]->clip.mask); - ASSERT_EQ(3, tiles[7]->clip.length); - - ASSERT_EQ(std::string("4/0/2"), std::string(tiles[8]->id)); - ASSERT_EQ(std::bitset<8>("11110000"), tiles[8]->clip.mask); - ASSERT_EQ(5, tiles[8]->clip.length); - - ASSERT_EQ(std::string("4/0/3"), std::string(tiles[9]->id)); - ASSERT_EQ(std::bitset<8>("11111000"), tiles[9]->clip.mask); - ASSERT_EQ(5, tiles[9]->clip.length); - - ASSERT_EQ(std::string("4/1/2"), std::string(tiles[10]->id)); - ASSERT_EQ(std::bitset<8>("11100000"), tiles[10]->clip.mask); - ASSERT_EQ(5, tiles[10]->clip.length); - - ASSERT_EQ(std::string("4/1/3"), std::string(tiles[11]->id)); - ASSERT_EQ(std::bitset<8>("11101000"), tiles[11]->clip.mask); - ASSERT_EQ(5, tiles[11]->clip.length); + const std::vector<std::vector<std::shared_ptr<Tile>>> sources = { + { + std::make_shared<Tile>(Tile::ID { 2, 0, 0 }), + std::make_shared<Tile>(Tile::ID { 3, 0, 0 }), + std::make_shared<Tile>(Tile::ID { 3, 0, 1 }), + std::make_shared<Tile>(Tile::ID { 4, 0, 2 }), + std::make_shared<Tile>(Tile::ID { 4, 1, 2 }), + std::make_shared<Tile>(Tile::ID { 4, 0, 3 }), + std::make_shared<Tile>(Tile::ID { 4, 1, 3 }), + std::make_shared<Tile>(Tile::ID { 3, 1, 0 }), + std::make_shared<Tile>(Tile::ID { 3, 1, 1 }), + std::make_shared<Tile>(Tile::ID { 2, 1, 0 }), + std::make_shared<Tile>(Tile::ID { 3, 2, 0 }), + std::make_shared<Tile>(Tile::ID { 3, 2, 1 }), + }, + }; + + generate(sources); + // print(sources); + + ASSERT_EQ(ClipID("00001111", "00000001"), sources[0][0]->clip); + ASSERT_EQ(ClipID("00001111", "00000011"), sources[0][1]->clip); + ASSERT_EQ(ClipID("00001111", "00000100"), sources[0][2]->clip); + ASSERT_EQ(ClipID("00001111", "00001001"), sources[0][3]->clip); + ASSERT_EQ(ClipID("00001111", "00001011"), sources[0][4]->clip); + ASSERT_EQ(ClipID("00001111", "00001010"), sources[0][5]->clip); + ASSERT_EQ(ClipID("00001111", "00001100"), sources[0][6]->clip); + ASSERT_EQ(ClipID("00001111", "00000101"), sources[0][7]->clip); + ASSERT_EQ(ClipID("00001111", "00000110"), sources[0][8]->clip); + ASSERT_EQ(ClipID("00001111", "00000010"), sources[0][9]->clip); + ASSERT_EQ(ClipID("00001111", "00000111"), sources[0][10]->clip); + ASSERT_EQ(ClipID("00001111", "00001000"), sources[0][11]->clip); } TEST(ClipIDs, Bug206) { - std::array<std::unique_ptr<Tile>, 11> tiles {{ - std::make_unique<Tile>(Tile::ID { 10, 162, 395 }), // 10/162/395: 10000000 (3) - std::make_unique<Tile>(Tile::ID { 10, 162, 396 }), // 10/162/396: 10100000 (3) - std::make_unique<Tile>(Tile::ID { 10, 163, 395 }), // 10/163/395: 11000000 (2) - std::make_unique<Tile>(Tile::ID { 11, 326, 791 }), // 11/326/791: 11100000 (4) - std::make_unique<Tile>(Tile::ID { 12, 654, 1582 }), // 12/654/1582: 11001000 (5) - std::make_unique<Tile>(Tile::ID { 12, 654, 1583 }), // 12/654/1583: 11010000 (4) - std::make_unique<Tile>(Tile::ID { 12, 655, 1582 }), // 12/655/1582: 11110000 (5) - std::make_unique<Tile>(Tile::ID { 12, 655, 1583 }), // 12/655/1583: 11111000 (5) - std::make_unique<Tile>(Tile::ID { 10, 163, 396 }), // 10/163/396: 01000000 (3) - std::make_unique<Tile>(Tile::ID { 10, 164, 395 }), // 10/164/395: 01100000 (3) - std::make_unique<Tile>(Tile::ID { 10, 164, 396 }), // 10/164/396: 00100000 (3) - }}; - - std::list<Tile *> tile_ptrs; - std::transform(tiles.begin(), tiles.end(), std::back_inserter(tile_ptrs), [](std::unique_ptr<Tile> &tile) { return tile.get(); }); - - updateClipIDs(tile_ptrs); - - // for (const auto &it : tiles) { - // std::cout << std::string(it->id) << ": " << it->clip.mask << " (" << (int)it->clip.length << ")" << std::endl; - // } - - ASSERT_EQ(std::string("10/162/395"), std::string(tiles[0]->id)); - ASSERT_EQ(std::bitset<8>("10000000"), tiles[0]->clip.mask); - ASSERT_EQ(3, tiles[0]->clip.length); - - ASSERT_EQ(std::string("10/162/396"), std::string(tiles[1]->id)); - ASSERT_EQ(std::bitset<8>("10100000"), tiles[1]->clip.mask); - ASSERT_EQ(3, tiles[1]->clip.length); - - ASSERT_EQ(std::string("10/163/395"), std::string(tiles[2]->id)); - ASSERT_EQ(std::bitset<8>("11000000"), tiles[2]->clip.mask); - ASSERT_EQ(2, tiles[2]->clip.length); - - ASSERT_EQ(std::string("11/326/791"), std::string(tiles[3]->id)); - ASSERT_EQ(std::bitset<8>("11100000"), tiles[3]->clip.mask); - ASSERT_EQ(4, tiles[3]->clip.length); - - ASSERT_EQ(std::string("12/654/1582"), std::string(tiles[4]->id)); - ASSERT_EQ(std::bitset<8>("11001000"), tiles[4]->clip.mask); - ASSERT_EQ(5, tiles[4]->clip.length); - - ASSERT_EQ(std::string("12/654/1583"), std::string(tiles[5]->id)); - ASSERT_EQ(std::bitset<8>("11010000"), tiles[5]->clip.mask); - ASSERT_EQ(4, tiles[5]->clip.length); - - ASSERT_EQ(std::string("12/655/1582"), std::string(tiles[6]->id)); - ASSERT_EQ(std::bitset<8>("11110000"), tiles[6]->clip.mask); - ASSERT_EQ(5, tiles[6]->clip.length); - - ASSERT_EQ(std::string("12/655/1583"), std::string(tiles[7]->id)); - ASSERT_EQ(std::bitset<8>("11111000"), tiles[7]->clip.mask); - ASSERT_EQ(5, tiles[7]->clip.length); - - ASSERT_EQ(std::string("10/163/396"), std::string(tiles[8]->id)); - ASSERT_EQ(std::bitset<8>("01000000"), tiles[8]->clip.mask); - ASSERT_EQ(3, tiles[8]->clip.length); - - ASSERT_EQ(std::string("10/164/395"), std::string(tiles[9]->id)); - ASSERT_EQ(std::bitset<8>("01100000"), tiles[9]->clip.mask); - ASSERT_EQ(3, tiles[9]->clip.length); - - ASSERT_EQ(std::string("10/164/396"), std::string(tiles[10]->id)); - ASSERT_EQ(std::bitset<8>("00100000"), tiles[10]->clip.mask); - ASSERT_EQ(3, tiles[10]->clip.length); - + const std::vector<std::vector<std::shared_ptr<Tile>>> sources = { + { + std::make_shared<Tile>(Tile::ID { 10, 162, 395 }), + std::make_shared<Tile>(Tile::ID { 10, 162, 396 }), + std::make_shared<Tile>(Tile::ID { 10, 163, 395 }), + std::make_shared<Tile>(Tile::ID { 11, 326, 791 }), + std::make_shared<Tile>(Tile::ID { 12, 654, 1582 }), + std::make_shared<Tile>(Tile::ID { 12, 654, 1583 }), + std::make_shared<Tile>(Tile::ID { 12, 655, 1582 }), + std::make_shared<Tile>(Tile::ID { 12, 655, 1583 }), + std::make_shared<Tile>(Tile::ID { 10, 163, 396 }), + std::make_shared<Tile>(Tile::ID { 10, 164, 395 }), + std::make_shared<Tile>(Tile::ID { 10, 164, 396 }), + }, + }; + + generate(sources); + // print(sources); + + ASSERT_EQ(ClipID("00001111", "00000001"), sources[0][0]->clip); + ASSERT_EQ(ClipID("00001111", "00000010"), sources[0][1]->clip); + ASSERT_EQ(ClipID("00001111", "00000011"), sources[0][2]->clip); + ASSERT_EQ(ClipID("00001111", "00000111"), sources[0][3]->clip); + ASSERT_EQ(ClipID("00001111", "00001000"), sources[0][4]->clip); + ASSERT_EQ(ClipID("00001111", "00001001"), sources[0][5]->clip); + ASSERT_EQ(ClipID("00001111", "00001010"), sources[0][6]->clip); + ASSERT_EQ(ClipID("00001111", "00001011"), sources[0][7]->clip); + ASSERT_EQ(ClipID("00001111", "00000100"), sources[0][8]->clip); + ASSERT_EQ(ClipID("00001111", "00000101"), sources[0][9]->clip); + ASSERT_EQ(ClipID("00001111", "00000110"), sources[0][10]->clip); } -TEST(ClipIDs, DuplicateIDs) { - - std::forward_list<Tile::ID> tiles {{ - Tile::ID { 2, 0, 0 }, - Tile::ID { 2, 0, 1 }, - Tile::ID { 2, 0, 0 }, - Tile::ID { 2, 0, 1 }, - Tile::ID { 2, 0, 1 }, - }}; - std::map<Tile::ID, ClipID> mapping = computeClipIDs(tiles); - - ASSERT_EQ(2ull, mapping.size()); - - // for (const auto &it : mapping) { - // std::cout << std::string(it.first) << "(" << it.first << ")" << ": " << it.second.mask << " (" << (int)it.second.length << ")" << std::endl; - // } +TEST(ClipIDs, MultipleSources) { + const std::vector<std::vector<std::shared_ptr<Tile>>> sources = { + { + std::make_shared<Tile>(Tile::ID { 0, 0, 0 }), + std::make_shared<Tile>(Tile::ID { 1, 1, 1 }), + std::make_shared<Tile>(Tile::ID { 2, 2, 1 }), + std::make_shared<Tile>(Tile::ID { 2, 2, 2 }), + }, + { + std::make_shared<Tile>(Tile::ID { 0, 0, 0 }), + std::make_shared<Tile>(Tile::ID { 1, 1, 1 }), + std::make_shared<Tile>(Tile::ID { 2, 1, 1 }), + std::make_shared<Tile>(Tile::ID { 2, 2, 2 }), + }, + { + std::make_shared<Tile>(Tile::ID { 1, 0, 0 }), + std::make_shared<Tile>(Tile::ID { 1, 0, 1 }), + std::make_shared<Tile>(Tile::ID { 1, 1, 0 }), + std::make_shared<Tile>(Tile::ID { 1, 1, 1 }), + std::make_shared<Tile>(Tile::ID { 2, 1, 1 }), + }, + }; + + generate(sources); + // print(sources); + + ASSERT_EQ(ClipID("00000111", "00000001"), sources[0][0]->clip); + ASSERT_EQ(ClipID("00000111", "00000010"), sources[0][1]->clip); + ASSERT_EQ(ClipID("00000111", "00000011"), sources[0][2]->clip); + ASSERT_EQ(ClipID("00000111", "00000100"), sources[0][3]->clip); + ASSERT_EQ(ClipID("00011000", "00001000"), sources[1][0]->clip); + ASSERT_EQ(ClipID("00000111", "00000010"), sources[1][1]->clip); + ASSERT_EQ(ClipID("00011000", "00010000"), sources[1][2]->clip); + ASSERT_EQ(ClipID("00000111", "00000100"), sources[1][3]->clip); + ASSERT_EQ(ClipID("11100000", "00100000"), sources[2][0]->clip); + ASSERT_EQ(ClipID("11100000", "01000000"), sources[2][1]->clip); + ASSERT_EQ(ClipID("11100000", "01100000"), sources[2][2]->clip); + ASSERT_EQ(ClipID("11100000", "10000000"), sources[2][3]->clip); + ASSERT_EQ(ClipID("00011000", "00010000"), sources[2][4]->clip); +} - ASSERT_EQ(std::bitset<8>("01000000"), mapping[Tile::ID(2, 0, 0)].mask); - ASSERT_EQ(2, mapping[Tile::ID(2, 0, 0)].length); - ASSERT_EQ(std::bitset<8>("10000000"), mapping[Tile::ID(2, 0, 1)].mask); - ASSERT_EQ(1, mapping[Tile::ID(2, 0, 1)].length); +TEST(ClipIDs, DuplicateIDs) { + const std::vector<std::vector<std::shared_ptr<Tile>>> sources = { + { + std::make_shared<Tile>(Tile::ID { 2, 0, 0 }), + std::make_shared<Tile>(Tile::ID { 2, 0, 1 }), + }, + { + std::make_shared<Tile>(Tile::ID { 2, 0, 0 }), + std::make_shared<Tile>(Tile::ID { 2, 0, 1 }), + std::make_shared<Tile>(Tile::ID { 2, 0, 1 }), + } + }; + + generate(sources); + // print(sources); + + ASSERT_EQ(ClipID("00000011", "00000001"), sources[0][0]->clip); + ASSERT_EQ(ClipID("00000011", "00000010"), sources[0][1]->clip); + ASSERT_EQ(ClipID("00000011", "00000001"), sources[1][0]->clip); + ASSERT_EQ(ClipID("00000011", "00000010"), sources[1][1]->clip); + ASSERT_EQ(ClipID("00000011", "00000010"), sources[1][2]->clip); } diff --git a/test/test.gyp b/test/test.gyp index 07709ecc86..fd7725bb03 100644 --- a/test/test.gyp +++ b/test/test.gyp @@ -201,6 +201,7 @@ "./headless.cpp", "../common/headless_view.hpp", "../common/headless_view.cpp", + "../common/platform_default.cpp", "./fixtures/fixture_request.cpp", "./fixtures/fixture_log.hpp", "./fixtures/fixture_log.cpp", |