From 31f0f47195ae7d4a6f96b1c64cd39e1268fdfc8d Mon Sep 17 00:00:00 2001 From: Chris Loer Date: Thu, 9 Nov 2017 13:24:25 -0800 Subject: [core] Add CrossTileSymbolIndex. This class is responsible for tracking which symbols are "the same" between tiles at different zoom levels, so that symbol opacities (fade animations) can be copied smoothly between tiles. --- cmake/core-files.cmake | 2 + src/mbgl/text/cross_tile_symbol_index.cpp | 167 ++++++++++++++++++++++++++++++ src/mbgl/text/cross_tile_symbol_index.hpp | 67 ++++++++++++ 3 files changed, 236 insertions(+) create mode 100644 src/mbgl/text/cross_tile_symbol_index.cpp create mode 100644 src/mbgl/text/cross_tile_symbol_index.hpp diff --git a/cmake/core-files.cmake b/cmake/core-files.cmake index f70bbb943f..c6b951c237 100644 --- a/cmake/core-files.cmake +++ b/cmake/core-files.cmake @@ -531,6 +531,8 @@ set(MBGL_CORE_FILES src/mbgl/text/collision_feature.hpp src/mbgl/text/collision_tile.cpp src/mbgl/text/collision_tile.hpp + src/mbgl/text/cross_tile_symbol_index.cpp + src/mbgl/text/cross_tile_symbol_index.hpp src/mbgl/text/get_anchors.cpp src/mbgl/text/get_anchors.hpp src/mbgl/text/glyph.cpp diff --git a/src/mbgl/text/cross_tile_symbol_index.cpp b/src/mbgl/text/cross_tile_symbol_index.cpp new file mode 100644 index 0000000000..779bec283c --- /dev/null +++ b/src/mbgl/text/cross_tile_symbol_index.cpp @@ -0,0 +1,167 @@ +#include +#include +#include +#include +#include + +namespace mbgl { + + +TileLayerIndex::TileLayerIndex(OverscaledTileID coord_, std::vector& symbolInstances, uint32_t bucketInstanceId_) + : coord(coord_), bucketInstanceId(bucketInstanceId_) { + for (SymbolInstance& symbolInstance : symbolInstances) { + indexedSymbolInstances[symbolInstance.key].emplace_back(symbolInstance.crossTileID, getScaledCoordinates(symbolInstance, coord)); + } + } + +Point TileLayerIndex::getScaledCoordinates(SymbolInstance& symbolInstance, const OverscaledTileID& childTileCoord) { + // Round anchor positions to roughly 4 pixel grid + const double roundingFactor = 512.0 / util::EXTENT / 2.0; + const double scale = roundingFactor / std::pow(2, childTileCoord.canonical.z - coord.canonical.z); + return { + static_cast(std::floor((childTileCoord.canonical.x * util::EXTENT + symbolInstance.anchor.point.x) * scale)), + static_cast(std::floor((childTileCoord.canonical.y * util::EXTENT + symbolInstance.anchor.point.y) * scale)) + }; +} + +void TileLayerIndex::findMatches(std::vector& symbolInstances, const OverscaledTileID& newCoord) { + float tolerance = coord.canonical.z < newCoord.canonical.z ? 1 : std::pow(2, coord.canonical.z - newCoord.canonical.z); + + for (auto& symbolInstance : symbolInstances) { + if (symbolInstance.crossTileID) { + // already has a match, skip + continue; + } + + auto it = indexedSymbolInstances.find(symbolInstance.key); + if (it == indexedSymbolInstances.end()) { + // No symbol with this key in this bucket + continue; + } + + auto scaledSymbolCoord = getScaledCoordinates(symbolInstance, newCoord); + + for (IndexedSymbolInstance& thisTileSymbol: it->second) { + // Return any symbol with the same keys whose coordinates are within 1 + // grid unit. (with a 4px grid, this covers a 12px by 12px area) + if (std::abs(thisTileSymbol.coord.x - scaledSymbolCoord.x) <= tolerance && + std::abs(thisTileSymbol.coord.y - scaledSymbolCoord.y) <= tolerance) { + + symbolInstance.crossTileID = thisTileSymbol.crossTileID; + break; + } + } + } +} + +CrossTileSymbolLayerIndex::CrossTileSymbolLayerIndex() { +} + +uint32_t CrossTileSymbolLayerIndex::maxCrossTileID = 0; + +void CrossTileSymbolLayerIndex::addBucket(const OverscaledTileID& coord, SymbolBucket& bucket) { + if (bucket.bucketInstanceId) return; + bucket.bucketInstanceId = ++maxBucketInstanceId; + + uint8_t minZoom = 25; + uint8_t maxZoom = 0; + for (auto& it : indexes) { + auto z = it.first; + minZoom = std::min(minZoom, z); + maxZoom = std::max(maxZoom, z); + } + + + // make all higher-res child tiles block duplicate labels in this tile + for (auto z = maxZoom; z > coord.overscaledZ; z--) { + auto zoomIndexes = indexes.find(z); + if (zoomIndexes != indexes.end()) { + for (auto& childIndex : zoomIndexes->second) { + if (!childIndex.second.coord.isChildOf(coord)) { + continue; + } + childIndex.second.findMatches(bucket.symbolInstances, coord); + } + } + if (z == 0) { + break; + } + } + + // make this tile block duplicate labels in lower-res parent tiles + for (auto z = coord.overscaledZ; z >= minZoom; z--) { + auto parentCoord = coord.scaledTo(z); + auto zoomIndexes = indexes.find(z); + if (zoomIndexes != indexes.end()) { + auto parentIndex = zoomIndexes->second.find(parentCoord); + if (parentIndex != zoomIndexes->second.end()) { + parentIndex->second.findMatches(bucket.symbolInstances, coord); + } + } + if (z == 0) { + break; + } + } + + for (auto& symbolInstance : bucket.symbolInstances) { + if (!symbolInstance.crossTileID) { + // symbol did not match any known symbol, assign a new id + symbolInstance.crossTileID = ++maxCrossTileID; + } + } + + indexes[coord.overscaledZ].emplace(coord, TileLayerIndex(coord, bucket.symbolInstances, bucket.bucketInstanceId)); +} + +bool CrossTileSymbolLayerIndex::removeStaleBuckets(const std::unordered_set& currentIDs) { + bool tilesChanged = false; + for (auto& zoomIndexes : indexes) { + for (auto it = zoomIndexes.second.begin(); it != zoomIndexes.second.end();) { + if (!currentIDs.count(it->second.bucketInstanceId)) { + it = zoomIndexes.second.erase(it); + tilesChanged = true; + } else { + ++it; + } + } + } + return tilesChanged; +} + +CrossTileSymbolIndex::CrossTileSymbolIndex() {} + +bool CrossTileSymbolIndex::addLayer(RenderSymbolLayer& symbolLayer) { + + auto& layerIndex = layerIndexes[symbolLayer.getID()]; + + bool symbolBucketsChanged = false; + std::unordered_set currentBucketIDs; + + for (RenderTile& renderTile : symbolLayer.renderTiles) { + if (!renderTile.tile.isRenderable()) { + continue; + } + + auto bucket = renderTile.tile.getBucket(*symbolLayer.baseImpl); + assert(dynamic_cast(bucket)); + SymbolBucket& symbolBucket = *reinterpret_cast(bucket); + + if (!symbolBucket.bucketInstanceId) { + symbolBucketsChanged = true; + } + layerIndex.addBucket(renderTile.tile.id, symbolBucket); + currentBucketIDs.insert(symbolBucket.bucketInstanceId); + } + + if (layerIndex.removeStaleBuckets(currentBucketIDs)) { + symbolBucketsChanged = true; + } + return symbolBucketsChanged; +} + +void CrossTileSymbolIndex::reset() { + layerIndexes.clear(); +} + +} // namespace mbgl + diff --git a/src/mbgl/text/cross_tile_symbol_index.hpp b/src/mbgl/text/cross_tile_symbol_index.hpp new file mode 100644 index 0000000000..0b8c5c4780 --- /dev/null +++ b/src/mbgl/text/cross_tile_symbol_index.hpp @@ -0,0 +1,67 @@ +#pragma once + +#include +#include +#include +#include + +#include +#include +#include +#include +#include + +namespace mbgl { + +class SymbolInstance; +class RenderSymbolLayer; +class SymbolBucket; + +class IndexEntry { + Point anchorPoint; + +}; + +class IndexedSymbolInstance { + public: + IndexedSymbolInstance(uint32_t crossTileID_, Point coord_) + : crossTileID(crossTileID_), coord(coord_) {}; + uint32_t crossTileID; + Point coord; +}; + +class TileLayerIndex { + public: + TileLayerIndex(OverscaledTileID coord, std::vector&, uint32_t bucketInstanceId); + + Point getScaledCoordinates(SymbolInstance&, const OverscaledTileID&); + void findMatches(std::vector&, const OverscaledTileID&); + + OverscaledTileID coord; + uint32_t bucketInstanceId; + std::map> indexedSymbolInstances; +}; + +class CrossTileSymbolLayerIndex { + public: + CrossTileSymbolLayerIndex(); + void addBucket(const OverscaledTileID&, SymbolBucket&); + bool removeStaleBuckets(const std::unordered_set& currentIDs); + private: + std::map> indexes; + uint32_t maxBucketInstanceId = 0; + static uint32_t maxCrossTileID; +}; + +class CrossTileSymbolIndex { + public: + CrossTileSymbolIndex(); + + bool addLayer(RenderSymbolLayer&); + + void reset(); + private: + std::map layerIndexes; +}; + +} // namespace mbgl -- cgit v1.2.1