From 21107e0c1add92fea4ba614dfed968c1c42f41c0 Mon Sep 17 00:00:00 2001 From: Karim Naaji Date: Tue, 11 Feb 2020 17:04:02 -0500 Subject: Port line-dasharray fix from gl-js * Fix artifact for zero-lenghted dash array Fixes issue https://github.com/mapbox/mapbox-gl-js/issues/9213 and add render test for coverage around 0-length dash arrays Update distance field generation for regular dashes as follows: 1. Compute the dash array ranges and stretch location along the distance field 2. Collapse any 0-length distance field range 3. Collapse neighbouring same-type parts into single part * combine consecutive dashes and parts https://github.com/mapbox/mapbox-gl-js/pull/9246 https://github.com/mapbox/mapbox-gl-native/issues/16181 --- src/mbgl/geometry/line_atlas.cpp | 178 ++++++++++++++++++++++++++------------- src/mbgl/geometry/line_atlas.hpp | 7 ++ 2 files changed, 126 insertions(+), 59 deletions(-) diff --git a/src/mbgl/geometry/line_atlas.cpp b/src/mbgl/geometry/line_atlas.cpp index f272101a5b..3b6d82c46c 100644 --- a/src/mbgl/geometry/line_atlas.cpp +++ b/src/mbgl/geometry/line_atlas.cpp @@ -1,3 +1,4 @@ +#include #include #include #include @@ -6,8 +7,6 @@ #include #include -#include - namespace mbgl { namespace { @@ -20,82 +19,143 @@ size_t getDashPatternHash(const std::vector& dasharray, const LinePattern return key; } -LinePatternPos addDashPattern(AlphaImage& image, - const int32_t yOffset, - const std::vector& dasharray, - const LinePatternCap patternCap) { - const uint8_t n = patternCap == LinePatternCap::Round ? 7 : 0; - constexpr const uint8_t offset = 128; +std::vector getDashRanges(const std::vector& dasharray, float stretch) { + // If dasharray has an odd length, both the first and last parts + // are dashes and should be joined seamlessly. + const bool oddDashArray = dasharray.size() % 2 == 1; - if (dasharray.size() < 2) { - Log::Warning(Event::ParseStyle, "line dasharray requires at least two elements"); - return LinePatternPos(); - } + float left = oddDashArray ? -dasharray.back() * stretch : 0.0f; + float right = dasharray.front() * stretch; + bool isDash = true; - float length = 0; - for (const float part : dasharray) { - length += part; + std::vector ranges; + ranges.reserve(dasharray.size()); + ranges.push_back({left, right, isDash, dasharray.front() == 0.0f}); + + float currentDashLength = dasharray.front(); + for (size_t i = 1; i < dasharray.size(); ++i) { + isDash = !isDash; + + const float dashLength = dasharray[i]; + left = currentDashLength * stretch; + currentDashLength += dashLength; + right = currentDashLength * stretch; + + ranges.push_back({left, right, isDash, dashLength == 0.0f}); } - float stretch = image.size.width / length; - float halfWidth = stretch * 0.5; - // If dasharray has an odd length, both the first and last parts - // are dashes and should be joined seamlessly. - bool oddLength = dasharray.size() % 2 == 1; + return ranges; +} + +void addRoundDash( + const std::vector& ranges, uint32_t yOffset, float stretch, const int n, AlphaImage& image) { + const float halfStretch = stretch * 0.5f; for (int y = -n; y <= n; y++) { int row = yOffset + n + y; - int index = image.size.width * row; + const uint32_t index = image.size.width * row; + uint32_t currIndex = 0; + DashRange range = ranges[currIndex]; - float left = 0; - float right = dasharray[0]; - unsigned int partIndex = 1; + for (uint32_t x = 0; x < image.size.width; x++) { + if (x / range.right > 1.0f) { + range = ranges[++currIndex]; + } - if (oddLength) { - left -= dasharray.back(); - } + float distLeft = fabsf(x - range.left); + float distRight = fabsf(x - range.right); + float minDist = fminf(distLeft, distRight); + float signedDistance; - for (uint32_t x = 0; x < image.size.width; x++) { - while (right < x / stretch) { - left = right; - if (partIndex >= dasharray.size()) { - return LinePatternPos(); - } - right = right + dasharray[partIndex]; - - if (oddLength && partIndex == dasharray.size() - 1) { - right += dasharray.front(); - } - - partIndex++; + float distMiddle = static_cast(y) / n * (halfStretch + 1.0f); + if (range.isDash) { + float distEdge = halfStretch - fabsf(distMiddle); + signedDistance = sqrtf(minDist * minDist + distEdge * distEdge); + } else { + signedDistance = halfStretch - sqrtf(minDist * minDist + distMiddle * distMiddle); } - float distLeft = fabs(x - left * stretch); - float distRight = fabs(x - right * stretch); - float dist = fmin(distLeft, distRight); - bool inside = (partIndex % 2) == 1; - int signedDistance; - - if (patternCap == LinePatternCap::Round) { - float distMiddle = n ? (float)y / n * (halfWidth + 1) : 0; - if (inside) { - float distEdge = halfWidth - fabs(distMiddle); - signedDistance = sqrt(dist * dist + distEdge * distEdge); - } else { - signedDistance = halfWidth - sqrt(dist * dist + distMiddle * distMiddle); - } + image.data[index + x] = static_cast(fmaxf(0.0f, fminf(255.0f, signedDistance + 128.0f))); + } + } +} +void addRegularDash(std::vector& ranges, uint32_t yOffset, AlphaImage& image) { + // Collapse any zero-length range + for (auto it = ranges.begin(); it != ranges.end();) { + if (it->isZeroLength) { + ranges.erase(it); + } else { + ++it; + } + } + + if (ranges.size() >= 2) { + // Collapse neighbouring same-type parts into a single part + for (auto curr = ranges.begin(), next = ranges.begin() + 1; curr != ranges.end() && next != ranges.end();) { + if (next->isDash == curr->isDash) { + next->left = curr->left; + ranges.erase(curr); } else { - signedDistance = int((inside ? 1 : -1) * dist); + ++curr; + ++next; } + } + } + + DashRange& first = ranges.front(); + DashRange& last = ranges.back(); + if (first.isDash == last.isDash) { + first.left = last.left - image.size.width; + last.right = first.right + image.size.width; + } + + const uint32_t index = image.size.width * yOffset; + uint32_t currIndex = 0; + DashRange range = ranges[currIndex]; - image.data[index + x] = fmax(0, fmin(255, signedDistance + offset)); + for (uint32_t x = 0; x < image.size.width; ++x) { + if (x / range.right > 1.0f) { + range = ranges[++currIndex]; } + + float distLeft = fabsf(x - range.left); + float distRight = fabsf(x - range.right); + float minDist = fminf(distLeft, distRight); + float signedDistance = range.isDash ? minDist : -minDist; + + image.data[index + x] = static_cast(fmaxf(0.0f, fminf(255.0f, signedDistance + 128.0f))); + } +} + +LinePatternPos addDashPattern(AlphaImage& image, + uint32_t yOffset, + const std::vector& dasharray, + const LinePatternCap patternCap) { + const uint8_t n = patternCap == LinePatternCap::Round ? 7 : 0; + + if (dasharray.size() < 2) { + Log::Warning(Event::ParseStyle, "line dasharray requires at least two elements"); + return LinePatternPos(); + } + + float length = 0; + for (const float part : dasharray) { + length += part; + } + + float stretch = image.size.width / length; + std::vector ranges = getDashRanges(dasharray, stretch); + + if (patternCap == LinePatternCap::Round) { + addRoundDash(ranges, yOffset, stretch, n, image); + } else { + addRegularDash(ranges, yOffset, image); } LinePatternPos position; - position.y = (0.5 + yOffset + n) / image.size.height; - position.height = (2.0 * n + 1) / image.size.height; + position.y = (0.5f + yOffset + n) / image.size.height; + position.height = (2.0f * n + 1) / image.size.height; position.width = length; return position; @@ -107,7 +167,7 @@ DashPatternTexture::DashPatternTexture(const std::vector& from_, const std::vector& to_, const LinePatternCap cap) { const bool patternsIdentical = from_ == to_; - const int32_t patternHeight = cap == LinePatternCap::Round ? 15 : 1; + const uint32_t patternHeight = cap == LinePatternCap::Round ? 15 : 1; const uint32_t height = (patternsIdentical ? 1 : 2) * patternHeight; // The OpenGL ES 2.0 spec, section 3.8.2 states: diff --git a/src/mbgl/geometry/line_atlas.hpp b/src/mbgl/geometry/line_atlas.hpp index 853305d138..1be7cbf073 100644 --- a/src/mbgl/geometry/line_atlas.hpp +++ b/src/mbgl/geometry/line_atlas.hpp @@ -27,6 +27,13 @@ enum class LinePatternCap : bool { Round = true, }; +struct DashRange { + float left; + float right; + bool isDash; + bool isZeroLength; +}; + class DashPatternTexture { public: DashPatternTexture(const std::vector& from, const std::vector& to, LinePatternCap); -- cgit v1.2.1