diff options
author | Chris Loer <chris.loer@gmail.com> | 2017-10-25 12:03:56 -0700 |
---|---|---|
committer | Chris Loer <chris.loer@mapbox.com> | 2017-10-25 12:09:53 -0700 |
commit | 6a62f902413e29b139fc218865d5f67e8a90ba72 (patch) | |
tree | c7373ffbda5bce0b32a324b13ac190ebbb68a771 | |
parent | c63fb6041b71f6e6938609f9e020b0e26b7e2242 (diff) | |
download | qtlocation-mapboxgl-6a62f902413e29b139fc218865d5f67e8a90ba72.tar.gz |
Move CollisionIndex to use GridIndex instead of boost::rtree.
- Stops crash on inserting line labels
- Breaks queryRenderedSymbols for now.
[skip ci]
-rw-r--r-- | src/mbgl/text/collision_feature.hpp | 1 | ||||
-rw-r--r-- | src/mbgl/text/collision_index.cpp | 151 | ||||
-rw-r--r-- | src/mbgl/text/collision_index.hpp | 43 | ||||
-rw-r--r-- | src/mbgl/util/grid_index.cpp | 6 | ||||
-rw-r--r-- | src/mbgl/util/grid_index.hpp | 2 |
5 files changed, 130 insertions, 73 deletions
diff --git a/src/mbgl/text/collision_feature.hpp b/src/mbgl/text/collision_feature.hpp index 011f5b45f3..556ae1beac 100644 --- a/src/mbgl/text/collision_feature.hpp +++ b/src/mbgl/text/collision_feature.hpp @@ -34,6 +34,7 @@ public: // Placeholder for center of circles (can be derived from bounding box) float px; float py; + float radius; bool used; float tileUnitDistanceToAnchor; diff --git a/src/mbgl/text/collision_index.cpp b/src/mbgl/text/collision_index.cpp index 232aa23a8d..9f3d7d203f 100644 --- a/src/mbgl/text/collision_index.cpp +++ b/src/mbgl/text/collision_index.cpp @@ -25,7 +25,10 @@ namespace mbgl { // stability, but it's expensive. static const float viewportPadding = 100; -CollisionIndex::CollisionIndex(const TransformState& transformState_) : transformState(transformState_) { +CollisionIndex::CollisionIndex(const TransformState& transformState_) + : transformState(transformState_) + , collisionGrid(transformState.getSize().width, transformState.getSize().height, 30) + , ignoredGrid(transformState.getSize().width, transformState.getSize().height, 30) { pitchFactor = std::cos(transformState.getPitch()) * transformState.getCameraToCenterDistance(); } @@ -49,12 +52,6 @@ float CollisionIndex::approximateTileDistance(const TileDistance& tileDistance, (incidenceStretch - 1) * lastSegmentTile * std::abs(std::sin(lastSegmentAngle)); } -Box CollisionIndex::getTreeBox(const CollisionBox& box) const { - return Box{ - CollisionPoint{ box.px1, box.py1 }, - CollisionPoint{ box.px2, box.py2 } - }; -} bool CollisionIndex::placeFeature(CollisionFeature& feature, const mat4& posMatrix, @@ -70,13 +67,13 @@ bool CollisionIndex::placeFeature(CollisionFeature& feature, CollisionBox& box = feature.boxes.front(); const auto projectedPoint = projectAndGetPerspectiveRatio(posMatrix, box.anchor); const float tileToViewport = textPixelRatio * projectedPoint.second; - box.px1 = box.x1 / tileToViewport + projectedPoint.first.x; - box.py1 = box.y1 / tileToViewport + projectedPoint.first.y; - box.px2 = box.x2 / tileToViewport + projectedPoint.first.x; - box.py2 = box.y2 / tileToViewport + projectedPoint.first.y; - + GridUnit px1 = box.px1 = box.x1 / tileToViewport + projectedPoint.first.x; + GridUnit py1 = box.py1 = box.y1 / tileToViewport + projectedPoint.first.y; + GridUnit px2 = box.px2 = box.x2 / tileToViewport + projectedPoint.first.x; + GridUnit py2 = box.py2 = box.y2 / tileToViewport + projectedPoint.first.y; + if (!allowOverlap) { - if (tree.qbegin(bgi::intersects(getTreeBox(box))) != tree.qend()) { + if (collisionGrid.hitTest({{ px1, py1 }, { px2, py2 }})) { return false; } } @@ -183,9 +180,13 @@ bool CollisionIndex::placeLineFeature(CollisionFeature& feature, circle.py2 = projectedPoint.y + radius; circle.used = true; + + GridUnit px = circle.px = projectedPoint.x; + GridUnit py = circle.py = projectedPoint.y; + GridUnit r = circle.radius = radius; if (!allowOverlap) { - if (tree.qbegin(bgi::intersects(getTreeBox(circle))) != tree.qend()) { + if (collisionGrid.hitTest({{px, py}, r})) { if (!collisionDebug) { return false; } else { @@ -202,32 +203,119 @@ bool CollisionIndex::placeLineFeature(CollisionFeature& feature, void CollisionIndex::insertFeature(CollisionFeature& feature, bool ignorePlacement) { - std::vector<CollisionTreeBox> treeBoxes; - for (auto& box : feature.boxes) { - treeBoxes.emplace_back(getTreeBox(box), box, feature.indexedFeature); - } - - if (ignorePlacement) { - ignoredTree.insert(treeBoxes.begin(), treeBoxes.end()); + if (feature.alongLine) { + for (auto& box : feature.boxes) { + GridUnit px = box.px; + GridUnit py = box.py; + GridUnit radius = box.radius; + if (ignorePlacement) { + // TODO: revisit whether GridIndex should move vs. copy on insert + ignoredGrid.insert(IndexedSubfeature(feature.indexedFeature), {{ px, py }, radius}); + } else { + collisionGrid.insert(IndexedSubfeature(feature.indexedFeature), {{ px, py }, radius}); + } + } } else { - tree.insert(treeBoxes.begin(), treeBoxes.end()); + for (auto& box : feature.boxes) { + // TODO: Iteration is vestigial, there should be only one box + GridUnit px1 = box.px1; + GridUnit py1 = box.py1; + GridUnit px2 = box.px2; + GridUnit py2 = box.py2; + if (ignorePlacement) { + // TODO: revisit whether GridIndex should move vs. copy on insert + ignoredGrid.insert(IndexedSubfeature(feature.indexedFeature), {{ px1, py1 }, { px2, py2 }}); + } else { + collisionGrid.insert(IndexedSubfeature(feature.indexedFeature), {{ px1, py1 }, { px2, py2 }}); + } + } } } -std::vector<IndexedSubfeature> CollisionIndex::queryRenderedSymbols(const GeometryCoordinates& queryGeometry, const UnwrappedTileID& tileID, const float textPixelRatio) const { +std::vector<IndexedSubfeature> CollisionIndex::queryRenderedSymbols(const GeometryCoordinates& queryGeometry, const UnwrappedTileID&, const float) const { std::vector<IndexedSubfeature> result; - if (queryGeometry.empty() || (tree.empty() && ignoredTree.empty())) { + if (true || queryGeometry.empty() || (collisionGrid.empty() && ignoredGrid.empty())) { return result; } - + + // TODO: reimplement queryRenderedSymbols +/* mat4 posMatrix; transformState.matrixFor(posMatrix, tileID); GeometryCoordinates polygon; + auto minX = std::numeric_limits<GridUnit>::max(); + auto minY = std::numeric_limits<GridUnit>::max(); + auto maxX = std::numeric_limits<GridUnit>::min(); + auto maxY = std::numeric_limits<GridUnit>::min(); + for (const auto& point : queryGeometry) { auto projected = projectPoint(posMatrix, convertPoint<float>(point)); + GridUnit px = projected.x; + GridUnit py = projected.y; + minX = std::min(minX, px); + minY = std::min(minY, py); + maxX = std::max(maxX, px); + maxY = std::max(maxY, py); polygon.push_back(convertPoint<int16_t>(projected)); } + + std::vector<IndexedSubfeature> thisTileFeatures; + std::vector<IndexedSubfeature> features = collisionGrid.query({{minX, minY}, {maxX, maxY}}); + // TODO: reimplement "thisTileFeatures" filter + // onst tileID = tileCoord.id; + for (auto& feature : features) { + //if (features[i].tileID === tileID) { + thisTileFeatures.push_back(feature); + //} + } + + std::vector<IndexedSubfeature> ignoredFeatures = ignoredGrid.query({{minX, minY}, {maxX, maxY}}); + // TODO: reimplement "thisTileFeatures" filter + // onst tileID = tileCoord.id; + for (auto& feature : ignoredFeatures) { + //if (features[i].tileID === tileID) { + thisTileFeatures.push_back(feature); + //} + } + + for (auto& feature : thisTileFeatures) { + for (let i = 0; i < thisTileFeatures.length; i++) { + const blocking = collisionBoxArray.get(thisTileFeatures[i]); + const sourceLayer = blocking.sourceLayerIndex; + const featureIndex = blocking.featureIndex; + + // Skip already seen features. + if (sourceLayerFeatures[sourceLayer] === undefined) { + sourceLayerFeatures[sourceLayer] = {}; + } + if (sourceLayerFeatures[sourceLayer][featureIndex]) continue; + + + // Check if query intersects with the feature box + // "Collision Circles" for line labels are treated as boxes here + // Since there's no actual collision taking place, the circle vs. square + // distinction doesn't matter as much, and box geometry is easier + // to work with. + const projectedPoint = this.projectAndGetPerspectiveRatio(posMatrix, blocking.anchorPointX, blocking.anchorPointY); + const tileToViewport = textPixelRatio * projectedPoint.perspectiveRatio; + const x1 = blocking.x1 / tileToViewport + projectedPoint.point.x; + const y1 = blocking.y1 / tileToViewport + projectedPoint.point.y; + const x2 = blocking.x2 / tileToViewport + projectedPoint.point.x; + const y2 = blocking.y2 / tileToViewport + projectedPoint.point.y; + const bbox = [ + new Point(x1, y1), + new Point(x2, y1), + new Point(x2, y2), + new Point(x1, y2) + ]; + if (!intersectionTests.polygonIntersectsPolygon(query, bbox)) continue; + + sourceLayerFeatures[sourceLayer][featureIndex] = true; + result.push(thisTileFeatures[i]); + } + + return result; // Predicate for ruling out already seen features. std::unordered_map<std::string, std::unordered_set<std::size_t>> sourceLayerFeatures; @@ -256,19 +344,8 @@ std::vector<IndexedSubfeature> CollisionIndex::queryRenderedSymbols(const Geomet auto predicates = bgi::satisfies(seenFeature) && bgi::satisfies(intersectsAtScale); - auto queryTree = [&](const auto& tree_) { - for (auto it = tree_.qbegin(predicates); it != tree_.qend(); ++it) { - const IndexedSubfeature& feature = std::get<2>(*it); - auto& seenFeatures = sourceLayerFeatures[feature.sourceLayerName]; - seenFeatures.insert(feature.index); - result.push_back(feature); - } - }; - - queryTree(tree); - queryTree(ignoredTree); - return result; + */ } std::pair<float,float> CollisionIndex::projectAnchor(const mat4& posMatrix, const Point<float>& point) const { diff --git a/src/mbgl/text/collision_index.hpp b/src/mbgl/text/collision_index.hpp index e75661a3a5..65bd5baf2b 100644 --- a/src/mbgl/text/collision_index.hpp +++ b/src/mbgl/text/collision_index.hpp @@ -1,50 +1,23 @@ #pragma once +#include <mbgl/geometry/feature_index.hpp> #include <mbgl/text/collision_feature.hpp> #include <mbgl/text/placement_config.hpp> #include <mbgl/tile/geometry_tile_data.hpp> - -#pragma GCC diagnostic push -#pragma GCC diagnostic ignored "-Wunused-function" -#pragma GCC diagnostic ignored "-Wunused-parameter" -#pragma GCC diagnostic ignored "-Wunused-variable" -#pragma GCC diagnostic ignored "-Wshadow" -#ifdef __clang__ -#pragma GCC diagnostic ignored "-Wunknown-pragmas" -#endif -#pragma GCC diagnostic ignored "-Wpragmas" -#pragma GCC diagnostic ignored "-Wdeprecated-register" -#pragma GCC diagnostic ignored "-Wshorten-64-to-32" -#pragma GCC diagnostic ignored "-Wunused-local-typedefs" -#ifndef __clang__ -#pragma GCC diagnostic ignored "-Wmaybe-uninitialized" -#pragma GCC diagnostic ignored "-Wmisleading-indentation" -#endif -#include <boost/geometry.hpp> -#include <boost/geometry/geometries/point.hpp> -#include <boost/geometry/geometries/box.hpp> -#include <boost/geometry/index/rtree.hpp> -#pragma GCC diagnostic pop - +#include <mbgl/util/grid_index.hpp> #include <mbgl/map/transform_state.hpp> namespace mbgl { -namespace bg = boost::geometry; -namespace bgm = bg::model; -namespace bgi = bg::index; -using CollisionPoint = bgm::point<float, 2, bg::cs::cartesian>; -using Box = bgm::box<CollisionPoint>; -using CollisionTreeBox = std::tuple<Box, CollisionBox, IndexedSubfeature>; -using Tree = bgi::rtree<CollisionTreeBox, bgi::linear<16, 4>>; - -class IndexedSubfeature; class PlacedSymbol; struct TileDistance; class CollisionIndex { public: + using CollisionGrid = GridIndex<IndexedSubfeature>; + using GridUnit = int16_t; + explicit CollisionIndex(const TransformState&); bool placeFeature(CollisionFeature& feature, @@ -74,8 +47,6 @@ private: const bool allowOverlap, const bool pitchWithMap, const bool collisionDebug); - - Box getTreeBox(const CollisionBox& box) const; float approximateTileDistance(const TileDistance& tileDistance, const float lastSegmentAngle, const float pixelsToTileUnits, const float cameraToAnchorDistance, const bool pitchWithMap); @@ -86,8 +57,8 @@ private: TransformState transformState; float pitchFactor; - Tree tree; - Tree ignoredTree; + CollisionGrid collisionGrid; + CollisionGrid ignoredGrid; }; } // namespace mbgl diff --git a/src/mbgl/util/grid_index.cpp b/src/mbgl/util/grid_index.cpp index 351c5e5aea..ee1be32352 100644 --- a/src/mbgl/util/grid_index.cpp +++ b/src/mbgl/util/grid_index.cpp @@ -246,6 +246,12 @@ bool GridIndex<T>::circleAndBoxCollide(const BCircle& circle, const BBox& box) c return (dx * dx + dy * dy) <= (circle.radius * circle.radius); } +template <class T> +bool GridIndex<T>::empty() const { + return boxElements.empty() && circleElements.empty(); +} + + template class GridIndex<IndexedSubfeature>; } // namespace mbgl diff --git a/src/mbgl/util/grid_index.hpp b/src/mbgl/util/grid_index.hpp index 772aec6e38..d7f9bf14f1 100644 --- a/src/mbgl/util/grid_index.hpp +++ b/src/mbgl/util/grid_index.hpp @@ -70,6 +70,8 @@ public: bool hitTest(const BBox&) const; bool hitTest(const BCircle&) const; + + bool empty() const; private: |