diff options
-rw-r--r-- | cmake/core-files.cmake | 2 | ||||
-rw-r--r-- | src/mbgl/text/cross_tile_symbol_index.cpp | 167 | ||||
-rw-r--r-- | src/mbgl/text/cross_tile_symbol_index.hpp | 67 |
3 files changed, 236 insertions, 0 deletions
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 <mbgl/text/cross_tile_symbol_index.hpp> +#include <mbgl/layout/symbol_instance.hpp> +#include <mbgl/renderer/buckets/symbol_bucket.hpp> +#include <mbgl/renderer/render_tile.hpp> +#include <mbgl/tile/tile.hpp> + +namespace mbgl { + + +TileLayerIndex::TileLayerIndex(OverscaledTileID coord_, std::vector<SymbolInstance>& symbolInstances, uint32_t bucketInstanceId_) + : coord(coord_), bucketInstanceId(bucketInstanceId_) { + for (SymbolInstance& symbolInstance : symbolInstances) { + indexedSymbolInstances[symbolInstance.key].emplace_back(symbolInstance.crossTileID, getScaledCoordinates(symbolInstance, coord)); + } + } + +Point<int64_t> 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<int64_t>(std::floor((childTileCoord.canonical.x * util::EXTENT + symbolInstance.anchor.point.x) * scale)), + static_cast<int64_t>(std::floor((childTileCoord.canonical.y * util::EXTENT + symbolInstance.anchor.point.y) * scale)) + }; +} + +void TileLayerIndex::findMatches(std::vector<SymbolInstance>& 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<uint32_t>& 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<uint32_t> currentBucketIDs; + + for (RenderTile& renderTile : symbolLayer.renderTiles) { + if (!renderTile.tile.isRenderable()) { + continue; + } + + auto bucket = renderTile.tile.getBucket(*symbolLayer.baseImpl); + assert(dynamic_cast<SymbolBucket*>(bucket)); + SymbolBucket& symbolBucket = *reinterpret_cast<SymbolBucket*>(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 <mbgl/tile/tile_id.hpp> +#include <mbgl/util/geometry.hpp> +#include <mbgl/util/constants.hpp> +#include <mbgl/util/optional.hpp> + +#include <map> +#include <vector> +#include <string> +#include <memory> +#include <unordered_set> + +namespace mbgl { + +class SymbolInstance; +class RenderSymbolLayer; +class SymbolBucket; + +class IndexEntry { + Point<float> anchorPoint; + +}; + +class IndexedSymbolInstance { + public: + IndexedSymbolInstance(uint32_t crossTileID_, Point<int64_t> coord_) + : crossTileID(crossTileID_), coord(coord_) {}; + uint32_t crossTileID; + Point<int64_t> coord; +}; + +class TileLayerIndex { + public: + TileLayerIndex(OverscaledTileID coord, std::vector<SymbolInstance>&, uint32_t bucketInstanceId); + + Point<int64_t> getScaledCoordinates(SymbolInstance&, const OverscaledTileID&); + void findMatches(std::vector<SymbolInstance>&, const OverscaledTileID&); + + OverscaledTileID coord; + uint32_t bucketInstanceId; + std::map<std::u16string,std::vector<IndexedSymbolInstance>> indexedSymbolInstances; +}; + +class CrossTileSymbolLayerIndex { + public: + CrossTileSymbolLayerIndex(); + void addBucket(const OverscaledTileID&, SymbolBucket&); + bool removeStaleBuckets(const std::unordered_set<uint32_t>& currentIDs); + private: + std::map<uint8_t,std::map<OverscaledTileID,TileLayerIndex>> indexes; + uint32_t maxBucketInstanceId = 0; + static uint32_t maxCrossTileID; +}; + +class CrossTileSymbolIndex { + public: + CrossTileSymbolIndex(); + + bool addLayer(RenderSymbolLayer&); + + void reset(); + private: + std::map<std::string,CrossTileSymbolLayerIndex> layerIndexes; +}; + +} // namespace mbgl |