From a3f40d0c0c906400439eeb25d50f39eac64327ef Mon Sep 17 00:00:00 2001 From: Chris Loer Date: Wed, 22 Mar 2017 14:27:06 -0700 Subject: Verbose commenting on getSegmentGlyphs (#8361) * Verbose commenting on getSegmentGlyphs This came out of @cloer and @anandthakker trying to figure out how getSegmentGlyphs actually worked. Goal is to use this commented version as the base for a refactor. * Refactor getSegmentGlyphs for clarity. * Add more documentation, inline helper functions * Initialize VirtualSegments directly * Fix virtual anchor diagram --- src/mbgl/text/quads.cpp | 238 ++++++++++++++++++++++++++++++++++++------------ 1 file changed, 180 insertions(+), 58 deletions(-) diff --git a/src/mbgl/text/quads.cpp b/src/mbgl/text/quads.cpp index a0742f5a4b..9427362081 100644 --- a/src/mbgl/text/quads.cpp +++ b/src/mbgl/text/quads.cpp @@ -5,6 +5,7 @@ #include #include #include +#include #include @@ -95,76 +96,195 @@ SymbolQuad getIconQuad(const Anchor& anchor, struct GlyphInstance { explicit GlyphInstance(Point anchorPoint_) : anchorPoint(std::move(anchorPoint_)) {} - explicit GlyphInstance(Point anchorPoint_, float offset_, float minScale_, float maxScale_, + explicit GlyphInstance(Point anchorPoint_, bool upsideDown_, float minScale_, float maxScale_, float angle_) - : anchorPoint(std::move(anchorPoint_)), offset(offset_), minScale(minScale_), maxScale(maxScale_), angle(angle_) {} + : anchorPoint(std::move(anchorPoint_)), upsideDown(upsideDown_), minScale(minScale_), maxScale(maxScale_), angle(angle_) {} const Point anchorPoint; - const float offset = 0.0f; + const bool upsideDown = false; const float minScale = globalMinScale; const float maxScale = std::numeric_limits::infinity(); const float angle = 0.0f; }; typedef std::vector GlyphInstances; + +struct VirtualSegment { + Point anchor; + Point end; + size_t index; + float minScale; + float maxScale; +}; + +inline void insertSegmentGlyph(std::back_insert_iterator glyphs, + const VirtualSegment& virtualSegment, + const bool glyphIsLogicallyForward, + const bool upsideDown) { + float segmentAngle = std::atan2(virtualSegment.end.y - virtualSegment.anchor.y, virtualSegment.end.x - virtualSegment.anchor.x); + // If !glyphIsLogicallyForward, we're iterating through the segments in reverse logical order as well, so we need to flip the segment angle + float glyphAngle = glyphIsLogicallyForward ? segmentAngle : segmentAngle + M_PI; + + // Insert a glyph rotated at this angle for display in the range from [scale, previous(larger) scale]. + glyphs = GlyphInstance{ + /* anchor */ virtualSegment.anchor, + /* upsideDown */ upsideDown, + /* minScale */ virtualSegment.minScale, + /* maxScale */ virtualSegment.maxScale, + /* angle */ static_cast(std::fmod((glyphAngle + 2.0 * M_PI), (2.0 * M_PI)))}; +} -void getSegmentGlyphs(std::back_insert_iterator glyphs, - Anchor& anchor, - float offset, - const GeometryCoordinates& line, - int segment, - bool forward) { - const bool upsideDown = !forward; - - if (offset < 0) - forward = !forward; - - if (forward) - segment++; - - assert((int)line.size() > segment); - Point end = convertPoint(line[segment]); - Point newAnchorPoint = anchor.point; - float prevscale = std::numeric_limits::infinity(); +/** + Given the distance along the line from the label anchor to the beginning of the current segment, + project a "virtual anchor" point at the same distance along the line extending out from this segment. + + B <-- beginning of current segment +* . . . . . . . *--------* E <-- end of current segment +VA | + / VA = "virtual segment anchor" + / + ---*-----` + A = label anchor + + Distance _along line_ from A to B == straight-line distance from VA to B. + */ +inline Point getVirtualSegmentAnchor(const Point& segmentBegin, const Point& segmentEnd, float distanceFromAnchorToSegmentBegin) { + Point segmentDirectionUnitVector = util::normal(segmentBegin, segmentEnd); + return segmentBegin - (segmentDirectionUnitVector * distanceFromAnchorToSegmentBegin); +} - offset = std::fabs(offset); +/* + Given the segment joining `segmentAnchor` and `segmentEnd` and a desired offset + `glyphDistanceFromAnchor` at which a glyph is to be placed, calculate the minimum + "scale" at which the glyph will fall on the segment (i.e., not past the end) + + "Scale" here refers to the ratio between the *rendered* zoom level and the text-layout + zoom level, which is 1 + (source tile's zoom level). `glyphDistanceFromAnchor`, although + passed in units consistent with the text-layout zoom level, is based on text size. So + when the tile is being rendered at z < text-layout zoom, the glyph's actual distance from + the anchor is larger relative to the segment's length than at layout time: + + + GLYPH + z == layout-zoom, scale == 1: segmentAnchor *--------------^-------------* segmentEnd + z == layout-zoom - 1, scale == 0.5: segmentAnchor *--------------^* segmentEnd + + <--------------> + Anchor-to-glyph distance stays visually fixed, + so it changes relative to the segment. +*/ +inline float getMinScaleForSegment(const float glyphDistanceFromAnchor, + const Point& segmentAnchor, + const Point& segmentEnd) { + const float distanceFromAnchorToEnd = util::dist(segmentAnchor, segmentEnd); + return glyphDistanceFromAnchor / distanceFromAnchorToEnd; +} - const float placementScale = anchor.scale; +inline Point getSegmentEnd(const bool glyphIsLogicallyForward, + const GeometryCoordinates& line, + const size_t segmentIndex) { + return convertPoint(glyphIsLogicallyForward ? line[segmentIndex+1] : line[segmentIndex]); +} +optional getNextVirtualSegment(const VirtualSegment& previousVirtualSegment, + const GeometryCoordinates& line, + const float glyphDistanceFromAnchor, + const bool glyphIsLogicallyForward) { + auto nextSegmentBegin = previousVirtualSegment.end; + + auto end = nextSegmentBegin; + size_t index = previousVirtualSegment.index; + + // skip duplicate nodes + while (end == nextSegmentBegin) { + // look ahead by 2 points in the line because the segment index refers to the beginning + // of the segment, and we need an endpoint too + if (glyphIsLogicallyForward && (index + 2 < line.size())) { + index += 1; + } else if (!glyphIsLogicallyForward && index != 0) { + index -= 1; + } else { + return {}; + } + + end = getSegmentEnd(glyphIsLogicallyForward, line, index); + } + + const auto anchor = getVirtualSegmentAnchor(nextSegmentBegin, end, + util::dist(previousVirtualSegment.anchor, + previousVirtualSegment.end)); + return VirtualSegment { + anchor, + end, + index, + getMinScaleForSegment(glyphDistanceFromAnchor, anchor, end), + previousVirtualSegment.minScale + }; +} + +/* + Given (1) a glyph positioned relative to an anchor point and (2) a line to follow, + calculates which segment of the line the glyph will fall on for each possible + scale range, and for each range produces a "virtual" anchor point and an angle that will + place the glyph on the right segment and rotated to the correct angle. + + Because one glyph quad is made ahead of time for each possible orientation, the + symbol_sdf shader can quickly handle changing layout as we zoom in and out + + If the "keepUpright" property is set, we call getLineGlyphs twice (once upright and + once "upside down"). This will generate two sets of glyphs following the line in opposite + directions. Later, SymbolLayout::place will look at the glyphs and based on the placement + angle determine if their original anchor was "upright" or not -- based on that, it throws + away one set of glyphs or the other (this work has to be done in the CPU, but it's just a + filter so it's fast) + */ +void getLineGlyphs(std::back_insert_iterator glyphs, + Anchor& anchor, + float glyphHorizontalOffsetFromAnchor, + const GeometryCoordinates& line, + size_t anchorSegment, + bool upsideDown) { + assert(line.size() > anchorSegment+1); + + // This is true if the glyph is "logically forward" of the anchor point, based on the ordering of line segments + // The actual angle of the line is irrelevant + // If "upsideDown" is set, everything is flipped + const bool glyphIsLogicallyForward = (glyphHorizontalOffsetFromAnchor >= 0) ^ upsideDown; + const float glyphDistanceFromAnchor = std::fabs(glyphHorizontalOffsetFromAnchor); + + VirtualSegment virtualSegment = { + anchor.point, + getSegmentEnd(glyphIsLogicallyForward, line, anchorSegment), + anchorSegment, + getMinScaleForSegment(glyphDistanceFromAnchor, virtualSegment.anchor, virtualSegment.end), + std::numeric_limits::infinity() + }; + while (true) { - const float dist = util::dist(newAnchorPoint, end); - const float scale = offset / dist; - float angle = std::atan2(end.y - newAnchorPoint.y, end.x - newAnchorPoint.x); - if (!forward) - angle += M_PI; - - glyphs = GlyphInstance{ - /* anchor */ newAnchorPoint, - /* offset */ static_cast(upsideDown ? M_PI : 0.0), - /* minScale */ scale, - /* maxScale */ prevscale, - /* angle */ static_cast(std::fmod((angle + 2.0 * M_PI), (2.0 * M_PI)))}; - - if (scale <= placementScale) - break; - - newAnchorPoint = end; - - // skip duplicate nodes - while (newAnchorPoint == end) { - segment += forward ? 1 : -1; - if ((int)line.size() <= segment || segment < 0) { - anchor.scale = scale; - return; - } - end = convertPoint(line[segment]); + insertSegmentGlyph(glyphs, + virtualSegment, + glyphIsLogicallyForward, + upsideDown); + + if (virtualSegment.minScale <= anchor.scale) { + // No need to calculate below the scale where the label starts showing + return; + } + + optional nextVirtualSegment = getNextVirtualSegment(virtualSegment, + line, + glyphDistanceFromAnchor, + glyphIsLogicallyForward); + if (!nextVirtualSegment) { + // There are no more segments, so we can't fit this glyph on the line at a lower scale + // This implies we can't show the label at all at lower scale, so we update the anchor's min scale + anchor.scale = virtualSegment.minScale; + return; + } else { + virtualSegment = *nextVirtualSegment; } - - Point normal = util::normal(newAnchorPoint, end) * dist; - newAnchorPoint = newAnchorPoint - normal; - - prevscale = scale; } + } SymbolQuads getGlyphQuads(Anchor& anchor, @@ -196,9 +316,9 @@ SymbolQuads getGlyphQuads(Anchor& anchor, GlyphInstances glyphInstances; if (placement == style::SymbolPlacementType::Line) { - getSegmentGlyphs(std::back_inserter(glyphInstances), anchor, centerX, line, anchor.segment, true); + getLineGlyphs(std::back_inserter(glyphInstances), anchor, centerX, line, anchor.segment, false); if (keepUpright) - getSegmentGlyphs(std::back_inserter(glyphInstances), anchor, centerX, line, anchor.segment, false); + getLineGlyphs(std::back_inserter(glyphInstances), anchor, centerX, line, anchor.segment, true); } else { glyphInstances.emplace_back(GlyphInstance{anchor.point}); } @@ -247,8 +367,10 @@ SymbolQuads getGlyphQuads(Anchor& anchor, // Prevent label from extending past the end of the line const float glyphMinScale = std::max(instance.minScale, anchor.scale); - const float anchorAngle = std::fmod((anchor.angle + instance.offset + 2 * M_PI), (2 * M_PI)); - const float glyphAngle = std::fmod((instance.angle + instance.offset + 2 * M_PI), (2 * M_PI)); + // All the glyphs for a label are tagged with either the "right side up" or "upside down" anchor angle, + // which is used at placement time to determine which set to show + const float anchorAngle = std::fmod((anchor.angle + (instance.upsideDown ? M_PI : 0.0) + 2 * M_PI), (2 * M_PI)); + const float glyphAngle = std::fmod((instance.angle + (instance.upsideDown ? M_PI : 0.0) + 2 * M_PI), (2 * M_PI)); quads.emplace_back(tl, tr, bl, br, rect, anchorAngle, glyphAngle, instance.anchorPoint, glyphMinScale, instance.maxScale, shapedText.writingMode); } } -- cgit v1.2.1