add helper to create fancy underlines

Add a couple of utility functions to SkPaint that return the bounds
of glyphs between a pair of lines.

The common use case envisioned generates the edges of descenders
between the top and bottom bounds of an underline to allow computing
a stroke that skips those descenders.

The implementation stores a linked list in each glyph containing
the bounds of the lines parallel to the advance and the outermost
intersections within those bounds.

When the glyph cache is constructed, the glyph path is intersected
with the bounds and the extreme min and max values within the bounds
is added to an intercept.

Share the text to path iter to construct the data.

Make a half-hearted attempt to support vertical text; while the
vertical implementation is complete; surrounding code (e.g. paint
align) has short-comings with vertical.

R=fmalita@chromium.org, reed@google.com

GOLD_TRYBOT_URL= https://gold.skia.org/search2?unt=true&query=source_type%3Dgm&master=false&issue=1654883003

Review URL: https://codereview.chromium.org/1654883003

9 files changed, 581 insertions, 35 deletions

diff --git a/gm/texteffects.cpp b/gm/texteffects.cpp
index 2eb76efa19..6ad3d23bf2 100644
--- a/gm/texteffects.cpp
+++ b/gm/texteffects.cpp
@@ -228,3 +228,163 @@ DEF_SIMPLE_GM(textunderstrike, canvas, 460, 680) {
     paint.setStyle(SkPaint::kFill_Style);
     canvas->drawText("Hello", 5, 100, 50, paint);
 }
+
+static SkPath create_underline(const SkTDArray<SkScalar>& intersections,
+        SkScalar last, SkScalar finalPos,
+        SkScalar uPos, SkScalar uWidth, SkScalar textSize) {
+    SkPath underline;
+    SkScalar end = last;
+    for (int index = 0; index < intersections.count(); index += 2) {
+        SkScalar start = intersections[index] - uWidth;;
+        end = intersections[index + 1] + uWidth;
+        if (start > last && last + textSize / 12 < start) {
+            underline.moveTo(last, uPos);
+            underline.lineTo(start, uPos);
+        }
+        last = end;
+    }
+    if (end < finalPos) {
+        underline.moveTo(end, uPos);
+        underline.lineTo(finalPos, uPos);
+    }
+    return underline;
+}
+
+static void find_intercepts(const char* test, size_t len, SkScalar x, SkScalar y,
+        const SkPaint& paint, SkScalar uWidth, SkTDArray<SkScalar>* intersections) {
+    SkScalar uPos = y + uWidth;
+    SkScalar bounds[2] = { uPos - uWidth / 2, uPos + uWidth / 2 };
+    int count = paint.getTextIntercepts(test, len, x, y, bounds, nullptr);
+    SkASSERT(!(count % 2));
+    if (count) {
+        intersections->setCount(count);
+        paint.getTextIntercepts(test, len, x, y, bounds, intersections->begin());
+    }
+}
+
+DEF_SIMPLE_GM(fancyunderline, canvas, 900, 1350) {
+    SkPaint paint;
+    paint.setAntiAlias(true);
+    const char* fam[] = { "sans-serif", "serif", "monospace" };
+    const char test[] = "aAjJgGyY_|{-(~[,]qQ}pP}zZ";
+    SkPoint textPt = { 10, 80 };
+    for (int font = 0; font < 3; ++font) {
+        sk_tool_utils::set_portable_typeface(&paint, fam[font], SkTypeface::kNormal);
+        for (SkScalar textSize = 100; textSize > 10; textSize -= 20) {
+            paint.setTextSize(textSize);
+            const SkScalar uWidth = textSize / 15;
+            paint.setStrokeWidth(uWidth);
+            paint.setStyle(SkPaint::kFill_Style);
+            canvas->drawText(test, sizeof(test) - 1, textPt.fX, textPt.fY, paint);
+
+            SkTDArray<SkScalar> intersections;
+            find_intercepts(test, sizeof(test) - 1, textPt.fX, textPt.fY, paint, uWidth,
+                &intersections);
+
+            SkScalar start = textPt.fX;
+            SkScalar end = paint.measureText(test, sizeof(test) - 1) + textPt.fX;
+            SkScalar uPos = textPt.fY + uWidth;
+            SkPath underline = create_underline(intersections, start, end, uPos, uWidth, textSize);
+            paint.setStyle(SkPaint::kStroke_Style);
+            canvas->drawPath(underline, paint);
+
+            canvas->translate(0, textSize * 1.3f);
+        }
+        canvas->translate(0, 60);
+    }
+}
+
+static void find_intercepts(const char* test, size_t len, const SkPoint* pos, const SkPaint& paint,
+        SkScalar uWidth, SkTDArray<SkScalar>* intersections) {
+    SkScalar uPos = pos[0].fY + uWidth;
+    SkScalar bounds[2] = { uPos - uWidth / 2, uPos + uWidth / 2 };
+    int count = paint.getPosTextIntercepts(test, len, pos, bounds, nullptr);
+    SkASSERT(!(count % 2));
+    if (count) {
+        intersections->setCount(count);
+        paint.getPosTextIntercepts(test, len, pos, bounds, intersections->begin());
+    }
+}
+
+DEF_SIMPLE_GM(fancyposunderline, canvas, 900, 1350) {
+    SkPaint paint;
+    paint.setAntiAlias(true);
+    const char* fam[] = { "sans-serif", "serif", "monospace" };
+    const char test[] = "aAjJgGyY_|{-(~[,]qQ}pP}zZ";
+    SkPoint textPt = { 10, 80 };
+    for (int font = 0; font < 3; ++font) {
+        sk_tool_utils::set_portable_typeface(&paint, fam[font], SkTypeface::kNormal);
+        for (SkScalar textSize = 100; textSize > 10; textSize -= 20) {
+            paint.setTextSize(textSize);
+            const SkScalar uWidth = textSize / 15;
+            paint.setStrokeWidth(uWidth);
+            paint.setStyle(SkPaint::kFill_Style);
+            int widthCount = paint.getTextWidths(test, sizeof(test) - 1, nullptr);
+            SkTDArray<SkScalar> widths;
+            widths.setCount(widthCount);
+            (void) paint.getTextWidths(test, sizeof(test) - 1, widths.begin());
+            SkTDArray<SkPoint> pos;
+            pos.setCount(widthCount);
+            SkScalar posX = textPt.fX;
+            for (int index = 0; index < widthCount; ++index) {
+                pos[index].fX = posX;
+                posX += widths[index];
+                pos[index].fY = textPt.fY + (textSize / 25) * (index % 4);
+            }
+            canvas->drawPosText(test, sizeof(test) - 1, pos.begin(), paint);
+
+            SkTDArray<SkScalar> intersections;
+            find_intercepts(test, sizeof(test) - 1, pos.begin(), paint, uWidth, &intersections);
+
+            SkScalar start = textPt.fX;
+            SkScalar end = posX;
+            SkScalar uPos = textPt.fY + uWidth;
+            SkPath underline = create_underline(intersections, start, end, uPos, uWidth, textSize);
+            paint.setStyle(SkPaint::kStroke_Style);
+            canvas->drawPath(underline, paint);
+
+            canvas->translate(0, textSize * 1.3f);
+        }
+        canvas->translate(0, 60);
+    }
+}
+
+DEF_SIMPLE_GM(fancyunderlinebars, canvas, 1500, 460) {
+    SkPaint paint;
+    paint.setAntiAlias(true);
+    const char test[] = " .}]_ .}]_ .}]_ .}]_ .}]_ .}]_ .}]_ .}]_ .}]_ .}]_ .}]_ .}]_ .}]_";
+    SkPoint textPt = { 10, 80 };
+    sk_tool_utils::set_portable_typeface(&paint, "serif");
+    for (SkScalar textSize = 100; textSize > 10; textSize -= 20) {
+        paint.setTextSize(textSize);
+        SkScalar uWidth = textSize / 15;
+        paint.setStrokeWidth(uWidth);
+        paint.setStyle(SkPaint::kFill_Style);
+        int widthCount = paint.getTextWidths(test, sizeof(test) - 1, nullptr);
+        SkTDArray<SkScalar> widths;
+        widths.setCount(widthCount);
+        (void) paint.getTextWidths(test, sizeof(test) - 1, widths.begin());
+        SkTDArray<SkPoint> pos;
+        pos.setCount(widthCount);
+        SkScalar posX = textPt.fX;
+        pos[0] = textPt;
+        posX += widths[0];
+        for (int index = 1; index < widthCount; ++index) {
+            pos[index].fX = posX;
+            posX += widths[index];
+            pos[index].fY = textPt.fY - (textSize / 50) * (index / 5) + textSize / 50 * 4;
+        }
+        canvas->drawPosText(test, sizeof(test) - 1, pos.begin(), paint);
+
+        SkTDArray<SkScalar> intersections;
+        find_intercepts(test, sizeof(test) - 1, pos.begin(), paint, uWidth, &intersections);
+
+        SkScalar start = textPt.fX;
+        SkScalar end = posX;
+        SkScalar uPos = pos[0].fY + uWidth;
+        SkPath underline = create_underline(intersections, start, end, uPos, uWidth, textSize);
+        paint.setStyle(SkPaint::kStroke_Style);
+        canvas->drawPath(underline, paint);
+        canvas->translate(0, textSize * 1.3f);
+    }
+}
diff --git a/include/core/SkPaint.h b/include/core/SkPaint.h
index a0def42f12..cd170bc94f 100644
--- a/include/core/SkPaint.h
+++ b/include/core/SkPaint.h
@@ -885,15 +885,67 @@ public:
                       SkRect bounds[] = NULL) const;
 
     /** Return the path (outline) for the specified text.
-        Note: just like SkCanvas::drawText, this will respect the Align setting
-              in the paint.
-    */
+     *  Note: just like SkCanvas::drawText, this will respect the Align setting
+     *        in the paint.
+     *
+     *  @param text         the text
+     *  @param length       number of bytes of text
+     *  @param x            The x-coordinate of the origin of the text.
+     *  @param y            The y-coordinate of the origin of the text.
+     *  @param path         The outline of the text.
+     */
     void getTextPath(const void* text, size_t length, SkScalar x, SkScalar y,
                      SkPath* path) const;
 
+    /** Return the path (outline) for the specified text.
+     *  Note: just like SkCanvas::drawText, this will respect the Align setting
+     *        in the paint.
+     *
+     *  @param text         the text
+     *  @param length       number of bytes of text
+     *  @param pos          array of positions, used to position each character
+     *  @param path         The outline of the text.
+     */
     void getPosTextPath(const void* text, size_t length,
                         const SkPoint pos[], SkPath* path) const;
 
+    /** Return the number of intervals that intersect the intercept along the axis of the advance.
+     *  The return count is zero or a multiple of two, and is at most the number of glyphs * 2 in
+     *  the string. The caller may pass nullptr for intervals to determine the size of the interval
+     *  array, or may conservatively pre-allocate an array with length * 2 entries. The computed
+     *  intervals are cached by glyph to improve performance for multiple calls.
+     *  This permits constructing an underline that skips the descenders. 
+     *
+     *  @param text         the text
+     *  @param length       number of bytes of text
+     *  @param x            The x-coordinate of the origin of the text.
+     *  @param y            The y-coordinate of the origin of the text.
+     *  @param bounds       The lower and upper line parallel to the advance.
+     *  @param array        If not null, the found intersections.
+     *
+     *  @return             The number of intersections, which may be zero.
+     */
+    int getTextIntercepts(const void* text, size_t length, SkScalar x, SkScalar y,
+                          const SkScalar bounds[2], SkScalar* intervals) const;
+
+    /** Return the number of intervals that intersect the intercept along the axis of the advance.
+     *  The return count is zero or a multiple of two, and is at most the number of glyphs * 2 in
+     *  string. The caller may pass nullptr for intervals to determine the size of the interval
+     *  array, or may conservatively pre-allocate an array with length * 2 entries. The computed
+     *  intervals are cached by glyph to improve performance for multiple calls.
+     *  This permits constructing an underline that skips the descenders. 
+     *
+     *  @param text         the text
+     *  @param length       number of bytes of text
+     *  @param pos          array of positions, used to position each character
+     *  @param bounds       The lower and upper line parallel to the advance.
+     *  @param array        If not null, the glyph bounds contained by the advance parallel lines.
+     *
+     *  @return             The number of intersections, which may be zero.
+     */
+    int getPosTextIntercepts(const void* text, size_t length, const SkPoint pos[],
+                             const SkScalar bounds[2], SkScalar* intervals) const;
+
     /**
      *  Return a rectangle that represents the union of the bounds of all
      *  of the glyphs, but each one positioned at (0,0). This may be conservatively large, and
@@ -1091,7 +1143,7 @@ private:
     friend class GrTextUtils;
     friend class GrGLPathRendering;
     friend class SkScalerContext;
-    friend class SkTextToPathIter;
+    friend class SkTextBaseIter;
     friend class SkCanonicalizePaint;
 };
 
diff --git a/src/core/SkGlyph.h b/src/core/SkGlyph.h
index 92f974bc2c..f9b94a0268 100644
--- a/src/core/SkGlyph.h
+++ b/src/core/SkGlyph.h
@@ -34,12 +34,28 @@ class SkGlyph {
         kSubShiftY = 0
     };
 
- public:
+    // Support horizontal and vertical skipping strike-through / underlines.
+    // The caller walks the linked list looking for a match. For a horizontal underline,
+    // the fBounds contains the top and bottom of the underline. The fInterval pair contains the
+    // beginning and end of of the intersection of the bounds and the glyph's path.
+    // If interval[0] >= interval[1], no intesection was found.
+    struct Intercept {
+        Intercept* fNext;
+        SkScalar   fBounds[2];    // for horz underlines, the boundaries in Y
+        SkScalar   fInterval[2];  // the outside intersections of the axis and the glyph
+    };
+
+    struct PathData {
+        Intercept* fIntercept;
+        SkPath*    fPath;
+    };
+
+public:
     static const SkFixed kSubpixelRound = SK_FixedHalf >> SkGlyph::kSubBits;
     // A value that can never be generated by MakeID.
     static const uint32_t kImpossibleID = ~0;
     void*       fImage;
-    SkPath*     fPath;
+    PathData*   fPathData;
     SkFixed     fAdvanceX, fAdvanceY;
 
     uint16_t    fWidth, fHeight;
@@ -133,7 +149,7 @@ class SkGlyph {
     void initCommon(uint32_t id) {
         fID             = id;
         fImage          = nullptr;
-        fPath           = nullptr;
+        fPathData       = nullptr;
         fMaskFormat     = MASK_FORMAT_UNKNOWN;
         fForceBW        = 0;
     }
@@ -176,7 +192,7 @@ class SkGlyph {
         return ID;
     }
 
-  // FIXME - This is needed because the Android frame work directly
+    // FIXME - This is needed because the Android frame work directly
   // accesses fID. Remove when fID accesses are cleaned up.
 #ifdef SK_BUILD_FOR_ANDROID_FRAMEWORK
   public:
diff --git a/src/core/SkGlyphCache.cpp b/src/core/SkGlyphCache.cpp
index 1512dbf0e5..93d48a3d15 100644
--- a/src/core/SkGlyphCache.cpp
+++ b/src/core/SkGlyphCache.cpp
@@ -53,7 +53,10 @@ SkGlyphCache::SkGlyphCache(SkTypeface* typeface, const SkDescriptor* desc, SkSca
 }
 
 SkGlyphCache::~SkGlyphCache() {
-    fGlyphMap.foreach ([](SkGlyph* g) { delete g->fPath; });
+    fGlyphMap.foreach ([](SkGlyph* g) { 
+        if (g->fPathData) {
+            delete g->fPathData->fPath;
+        } } );
     SkDescriptor::Free(fDesc);
     delete fScalerContext;
     this->invokeAndRemoveAuxProcs();
@@ -214,14 +217,185 @@ const void* SkGlyphCache::findImage(const SkGlyph& glyph) {
 
 const SkPath* SkGlyphCache::findPath(const SkGlyph& glyph) {
     if (glyph.fWidth) {
-        if (glyph.fPath == nullptr) {
-            const_cast<SkGlyph&>(glyph).fPath = new SkPath;
-            fScalerContext->getPath(glyph, glyph.fPath);
-            fMemoryUsed += sizeof(SkPath) +
-                    glyph.fPath->countPoints() * sizeof(SkPoint);
+        if (glyph.fPathData == nullptr) {
+            SkGlyph::PathData* pathData =
+                    (SkGlyph::PathData* ) fGlyphAlloc.allocThrow(sizeof(SkGlyph::PathData));
+            const_cast<SkGlyph&>(glyph).fPathData = pathData;
+            pathData->fIntercept = nullptr;
+            SkPath* path = pathData->fPath = new SkPath;
+            fScalerContext->getPath(glyph, path);
+            fMemoryUsed += sizeof(SkPath) + path->countPoints() * sizeof(SkPoint);
         }
     }
-    return glyph.fPath;
+    return glyph.fPathData ? glyph.fPathData->fPath : nullptr;
+}
+
+#include "../pathops/SkPathOpsCubic.h"
+#include "../pathops/SkPathOpsQuad.h"
+
+static bool quad_in_bounds(const SkScalar* pts, const SkScalar bounds[2]) {
+    SkScalar min = SkTMin(SkTMin(pts[0], pts[2]), pts[4]);
+    if (bounds[1] < min) {
+        return false;
+    }
+    SkScalar max = SkTMax(SkTMax(pts[0], pts[2]), pts[4]);
+    return bounds[0] < max;
+}
+
+static bool cubic_in_bounds(const SkScalar* pts, const SkScalar bounds[2]) {
+    SkScalar min = SkTMin(SkTMin(SkTMin(pts[0], pts[2]), pts[4]), pts[6]);
+    if (bounds[1] < min) {
+        return false;
+    }
+    SkScalar max = SkTMax(SkTMax(SkTMax(pts[0], pts[2]), pts[4]), pts[6]);
+    return bounds[0] < max;
+}
+
+void SkGlyphCache::OffsetResults(const SkGlyph::Intercept* intercept, SkScalar scale,
+                                 SkScalar xPos, SkScalar* array, int* count) {
+    if (array) {
+        array += *count;
+        for (int index = 0; index < 2; index++) {
+            *array++ = intercept->fInterval[index] * scale + xPos;
+        }
+    }
+    *count += 2;
+}
+
+void SkGlyphCache::AddInterval(SkScalar val, SkGlyph::Intercept* intercept) {
+    intercept->fInterval[0] = SkTMin(intercept->fInterval[0], val);
+    intercept->fInterval[1] = SkTMax(intercept->fInterval[1], val);
+}
+
+void SkGlyphCache::AddPoints(const SkPoint* pts, int ptCount, const SkScalar bounds[2], 
+        bool yAxis, SkGlyph::Intercept* intercept) {
+    for (int i = 0; i < ptCount; ++i) {
+        SkScalar val = *(&pts[i].fY - yAxis);
+        if (bounds[0] < val && val < bounds[1]) {
+            AddInterval(*(&pts[i].fX + yAxis), intercept);
+        }
+    }
+}
+
+void SkGlyphCache::AddLine(const SkPoint pts[2], SkScalar axis, bool yAxis,
+                     SkGlyph::Intercept* intercept) {
+    SkScalar t = yAxis ? (axis - pts[0].fX) / (pts[1].fX - pts[0].fX)
+            : (axis - pts[0].fY) / (pts[1].fY - pts[0].fY);
+    if (0 <= t && t < 1) {   // this handles divide by zero above
+        AddInterval(yAxis ? pts[0].fY + t * (pts[1].fY - pts[0].fY)
+            : pts[0].fX + t * (pts[1].fX - pts[0].fX), intercept);
+    }
+}
+
+void SkGlyphCache::AddQuad(const SkPoint pts[2], SkScalar axis, bool yAxis,
+                     SkGlyph::Intercept* intercept) {
+    SkDQuad quad;
+    quad.set(pts);
+    double roots[2];
+    int count = yAxis ? quad.verticalIntersect(axis, roots)
+            : quad.horizontalIntersect(axis, roots);
+    while (--count >= 0) {
+        SkPoint pt = quad.ptAtT(roots[count]).asSkPoint();
+        AddInterval(*(&pt.fX + yAxis), intercept);
+    }
+}
+
+void SkGlyphCache::AddCubic(const SkPoint pts[3], SkScalar axis, bool yAxis,
+                      SkGlyph::Intercept* intercept) {
+    SkDCubic cubic;
+    cubic.set(pts);
+    double roots[3];
+    int count = yAxis ? cubic.verticalIntersect(axis, roots)
+            : cubic.horizontalIntersect(axis, roots);
+    while (--count >= 0) {
+        SkPoint pt = cubic.ptAtT(roots[count]).asSkPoint();
+        AddInterval(*(&pt.fX + yAxis), intercept);
+    }
+}
+
+const SkGlyph::Intercept* SkGlyphCache::MatchBounds(const SkGlyph* glyph,
+                                                    const SkScalar bounds[2]) {
+    if (!glyph->fPathData) {
+        return nullptr;
+    }
+    const SkGlyph::Intercept* intercept = glyph->fPathData->fIntercept;
+    while (intercept) {
+        if (bounds[0] == intercept->fBounds[0] && bounds[1] == intercept->fBounds[1]) {
+            return intercept;
+        }
+        intercept = intercept->fNext;
+    }
+    return nullptr;
+}
+
+void SkGlyphCache::findIntercepts(const SkScalar bounds[2], SkScalar scale, SkScalar xPos,
+        bool yAxis, SkGlyph* glyph, SkScalar* array, int* count) {
+    const SkGlyph::Intercept* match = MatchBounds(glyph, bounds);
+
+    if (match) {
+        if (match->fInterval[0] < match->fInterval[1]) {
+            OffsetResults(match, scale, xPos, array, count);
+        }
+        return;
+    }
+
+    SkGlyph::Intercept* intercept =
+            (SkGlyph::Intercept* ) fGlyphAlloc.allocThrow(sizeof(SkGlyph::Intercept));
+    intercept->fNext = glyph->fPathData->fIntercept;
+    intercept->fBounds[0] = bounds[0];
+    intercept->fBounds[1] = bounds[1];
+    intercept->fInterval[0] = SK_ScalarMax;
+    intercept->fInterval[1] = SK_ScalarMin;
+    glyph->fPathData->fIntercept = intercept;
+    const SkPath* path = glyph->fPathData->fPath;
+    const SkRect& pathBounds = path->getBounds();
+    if (*(&pathBounds.fBottom - yAxis) < bounds[0] || bounds[1] < *(&pathBounds.fTop - yAxis)) {
+        return;
+    }
+    SkPath::Iter iter(*path, false);
+    SkPoint pts[4];
+    SkPath::Verb verb;
+    while (SkPath::kDone_Verb != (verb = iter.next(pts))) {
+        switch (verb) {
+            case SkPath::kMove_Verb:
+                break;
+            case SkPath::kLine_Verb:
+                AddLine(pts, bounds[0], yAxis, intercept);
+                AddLine(pts, bounds[1], yAxis, intercept);
+                AddPoints(pts, 2, bounds, yAxis, intercept);
+                break;
+            case SkPath::kQuad_Verb:
+                if (!quad_in_bounds(&pts[0].fY - yAxis, bounds)) {
+                    break;
+                }
+                AddQuad(pts, bounds[0], yAxis, intercept);
+                AddQuad(pts, bounds[1], yAxis, intercept);
+                AddPoints(pts, 3, bounds, yAxis, intercept);
+                break;
+            case SkPath::kConic_Verb:
+                SkASSERT(0);  // no support for text composed of conics
+                break;
+            case SkPath::kCubic_Verb:
+                if (!cubic_in_bounds(&pts[0].fY - yAxis, bounds)) {
+                    break;
+                }
+                AddCubic(pts, bounds[0], yAxis, intercept);
+                AddCubic(pts, bounds[1], yAxis, intercept);
+                AddPoints(pts, 4, bounds, yAxis, intercept);
+                break;
+            case SkPath::kClose_Verb:
+                break;
+            default:
+                SkASSERT(0);
+                break;
+        }
+    }
+    if (intercept->fInterval[0] >= intercept->fInterval[1]) {
+        intercept->fInterval[0] = SK_ScalarMax;
+        intercept->fInterval[1] = SK_ScalarMin;
+        return;
+    }
+    OffsetResults(intercept, scale, xPos, array, count);
 }
 
 void SkGlyphCache::dump() const {
diff --git a/src/core/SkGlyphCache.h b/src/core/SkGlyphCache.h
index 2f1f417250..cd0b05c6e9 100644
--- a/src/core/SkGlyphCache.h
+++ b/src/core/SkGlyphCache.h
@@ -77,6 +77,12 @@ public:
     */
     const void* findImage(const SkGlyph&);
 
+    /** If the advance axis intersects the glyph's path, append the positions scaled and offset
+        to the array (if non-null), and set the count to the updated array length.
+    */
+    void findIntercepts(const SkScalar bounds[2], SkScalar scale, SkScalar xPos,
+                        bool yAxis, SkGlyph* , SkScalar* array, int* count);
+
     /** Return the Path associated with the glyph. If it has not been generated this will trigger
         that.
     */
@@ -232,6 +238,20 @@ private:
 
     inline static SkGlyphCache* FindTail(SkGlyphCache* head);
 
+    static void OffsetResults(const SkGlyph::Intercept* intercept, SkScalar scale,
+                              SkScalar xPos, SkScalar* array, int* count);
+    static void AddInterval(SkScalar val, SkGlyph::Intercept* intercept);
+    static void AddPoints(const SkPoint* pts, int ptCount, const SkScalar bounds[2], 
+                          bool yAxis, SkGlyph::Intercept* intercept);
+    static void AddLine(const SkPoint pts[2], SkScalar axis, bool yAxis,
+                        SkGlyph::Intercept* intercept);
+    static void AddQuad(const SkPoint pts[2], SkScalar axis, bool yAxis,
+                        SkGlyph::Intercept* intercept);
+    static void AddCubic(const SkPoint pts[3], SkScalar axis, bool yAxis,
+                         SkGlyph::Intercept* intercept);
+    static const SkGlyph::Intercept* MatchBounds(const SkGlyph* glyph,
+                                                 const SkScalar bounds[2]);
+
     SkGlyphCache*          fNext;
     SkGlyphCache*          fPrev;
     SkDescriptor* const    fDesc;
diff --git a/src/core/SkPaint.cpp b/src/core/SkPaint.cpp
index b9f5cedc15..cea3d0fc8d 100644
--- a/src/core/SkPaint.cpp
+++ b/src/core/SkPaint.cpp
@@ -1259,6 +1259,23 @@ void SkPaint::getTextPath(const void* textData, size_t length,
     }
 }
 
+int SkPaint::getTextIntercepts(const void* textData, size_t length,
+                               SkScalar x, SkScalar y, const SkScalar bounds[2], 
+                               SkScalar* array) const {
+    SkASSERT(length == 0 || textData != nullptr);
+    if (!length) {
+        return 0;
+    }
+
+    const char* text = (const char*) textData;
+    SkTextInterceptsIter iter(text, length, *this, bounds, x, y,
+            SkTextInterceptsIter::TextType::kText);
+    int count = 0;
+    while (iter.next(array, &count)) {
+    }
+    return count;
+}
+
 void SkPaint::getPosTextPath(const void* textData, size_t length,
                              const SkPoint pos[], SkPath* path) const {
     SkASSERT(length == 0 || textData != nullptr);
@@ -1288,6 +1305,25 @@ void SkPaint::getPosTextPath(const void* textData, size_t length,
     }
 }
 
+int SkPaint::getPosTextIntercepts(const void* textData, size_t length, const SkPoint pos[],
+                                  const SkScalar bounds[2], SkScalar* array) const {
+    SkASSERT(length == 0 || textData != nullptr);
+    if (!length) {
+        return 0;
+    }
+
+    const char* text = (const char*) textData;
+    SkTextInterceptsIter iter(text, length, *this, bounds, pos[0].fX, pos[0].fY,
+            SkTextInterceptsIter::TextType::kPosText);
+    int i = 0;
+    int count = 0;
+    while (iter.next(array, &count)) {
+        i++;
+        iter.setPosition(pos[i].fX, pos[i].fY);
+    }
+    return count;
+}
+
 SkRect SkPaint::getFontBounds() const {
     SkMatrix m;
     m.setScale(fTextSize * fTextScaleX, fTextSize);
@@ -2352,7 +2388,7 @@ static bool has_thick_frame(const SkPaint& paint) {
             paint.getStyle() != SkPaint::kFill_Style;
 }
 
-SkTextToPathIter::SkTextToPathIter(const char text[], size_t length,
+SkTextBaseIter::SkTextBaseIter(const char text[], size_t length,
                                    const SkPaint& paint,
                                    bool applyStrokeAndPathEffects)
     : fPaint(paint) {
@@ -2415,7 +2451,7 @@ SkTextToPathIter::SkTextToPathIter(const char text[], size_t length,
     fXYIndex = paint.isVerticalText() ? 1 : 0;
 }
 
-SkTextToPathIter::~SkTextToPathIter() {
+SkTextBaseIter::~SkTextBaseIter() {
     SkGlyphCache::AttachCache(fCache);
 }
 
@@ -2443,6 +2479,17 @@ bool SkTextToPathIter::next(const SkPath** path, SkScalar* xpos) {
     return false;
 }
 
+bool SkTextInterceptsIter::next(SkScalar* array, int* count) {
+    const SkGlyph& glyph = fGlyphCacheProc(fCache, &fText);
+    fXPos += SkScalarMul(SkFixedToScalar(fPrevAdvance + fAutoKern.adjust(glyph)), fScale);
+    fPrevAdvance = advance(glyph, fXYIndex);   // + fPaint.getTextTracking();
+    if (fCache->findPath(glyph)) {
+        fCache->findIntercepts(fBounds, fScale, fXPos, SkToBool(fXYIndex),
+                const_cast<SkGlyph*>(&glyph), array, count);
+    }
+    return fText < fStop;
+}
+
 ///////////////////////////////////////////////////////////////////////////////
 
 // return true if the filter exists, and may affect alpha
diff --git a/src/core/SkTextToPathIter.h b/src/core/SkTextToPathIter.h
index e98d6d9370..e299552327 100644
--- a/src/core/SkTextToPathIter.h
+++ b/src/core/SkTextToPathIter.h
@@ -13,37 +13,91 @@
 
 class SkGlyphCache;
 
-class SkTextToPathIter {
+class SkTextBaseIter {
+protected:
+    SkTextBaseIter(const char text[], size_t length, const SkPaint& paint,
+                   bool applyStrokeAndPathEffects);
+    ~SkTextBaseIter();
+
+    SkGlyphCache*   fCache;
+    SkPaint         fPaint;
+    SkScalar        fScale;
+    SkFixed         fPrevAdvance;
+    const char*     fText;
+    const char*     fStop;
+    SkMeasureCacheProc fGlyphCacheProc;
+
+    SkScalar        fXPos;      // accumulated xpos, returned in next
+    SkAutoKern      fAutoKern;
+    int             fXYIndex;   // cache for horizontal -vs- vertical text
+};
+
+class SkTextToPathIter : SkTextBaseIter {
 public:
     SkTextToPathIter(const char text[], size_t length, const SkPaint& paint,
-                     bool applyStrokeAndPathEffects);
-    ~SkTextToPathIter();
+                     bool applyStrokeAndPathEffects)
+                     : SkTextBaseIter(text, length, paint, applyStrokeAndPathEffects) {
+    }
 
     const SkPaint&  getPaint() const { return fPaint; }
     SkScalar        getPathScale() const { return fScale; }
 
-    struct Rec {
-        const SkPath*   fPath;  // may be null for "whitespace" glyphs
-        SkScalar        fXPos;
+    /**
+     *  Returns false when all of the text has been consumed
+     */
+    bool next(const SkPath** path, SkScalar* xpos);
+};
+
+class SkTextInterceptsIter : SkTextBaseIter {
+public:
+    enum class TextType {
+        kText,
+        kPosText
     };
 
+    SkTextInterceptsIter(const char text[], size_t length, const SkPaint& paint,
+                         const SkScalar bounds[2], SkScalar x, SkScalar y, TextType textType)
+                         : SkTextBaseIter(text, length, paint, false)
+                         , fTextType(textType) {
+        fBoundsBase[0] = bounds[0];
+        fBoundsBase[1] = bounds[1];
+        this->setPosition(x, y);
+    }
+
     /**
      *  Returns false when all of the text has been consumed
      */
-    bool next(const SkPath** path, SkScalar* xpos);
+    bool next(SkScalar* array, int* count);
 
-private:
-    SkGlyphCache*   fCache;
-    SkPaint         fPaint;
-    SkScalar        fScale;
-    SkFixed         fPrevAdvance;
-    const char*     fText;
-    const char*     fStop;
-    SkMeasureCacheProc fGlyphCacheProc;
+    void setPosition(SkScalar x, SkScalar y) {
+        SkScalar xOffset = TextType::kText == fTextType && fXYIndex ? fXPos : 0;
+        if (TextType::kPosText == fTextType
+                && fPaint.getTextAlign() != SkPaint::kLeft_Align) { // need to measure first
+            const char* text = fText;
+            const SkGlyph& glyph = fGlyphCacheProc(fCache, &text);
+            SkScalar width = SkScalarMul(SkFixedToScalar((&glyph.fAdvanceX)[0]), fScale);
+            if (fPaint.getTextAlign() == SkPaint::kCenter_Align) {
+                width = SkScalarHalf(width);
+            }
+            xOffset = width;
+        }
 
-    SkScalar        fXPos;      // accumulated xpos, returned in next
-    SkAutoKern      fAutoKern;
-    int             fXYIndex;   // cache for horizontal -vs- vertical text
+        for (int i = 0; i < (int) SK_ARRAY_COUNT(fBounds); ++i) {
+            SkScalar bound = fBoundsBase[i] - (fXYIndex ? x : y);
+            if (fXYIndex) {
+                bound += xOffset;
+            }
+            fBounds[i] = bound / fScale;
+        }
+
+        fXPos = xOffset + (fXYIndex ? y : x);
+        fPrevAdvance = 0;
+    }
+
+private:
+    SkScalar fBounds[2];
+    SkScalar fBoundsBase[2];
+    TextType fTextType;
 };
 
 #endif
diff --git a/src/pathops/SkDQuadLineIntersection.cpp b/src/pathops/SkDQuadLineIntersection.cpp
index 64eb86848e..a3d10bc9ff 100644
--- a/src/pathops/SkDQuadLineIntersection.cpp
+++ b/src/pathops/SkDQuadLineIntersection.cpp
@@ -442,3 +442,13 @@ int SkIntersections::VerticalIntercept(const SkDQuad& quad, SkScalar x, double*
     LineQuadraticIntersections q(quad);
     return q.verticalIntersect(x, roots);
 }
+
+// SkDQuad accessors to Intersection utilities
+
+int SkDQuad::horizontalIntersect(double yIntercept, double roots[2]) const {
+    return SkIntersections::HorizontalIntercept(*this, yIntercept, roots);
+}
+
+int SkDQuad::verticalIntersect(double xIntercept, double roots[2]) const {
+    return SkIntersections::VerticalIntercept(*this, xIntercept, roots);
+}
diff --git a/src/pathops/SkPathOpsQuad.h b/src/pathops/SkPathOpsQuad.h
index f20bf6faea..32cfe58ecf 100644
--- a/src/pathops/SkPathOpsQuad.h
+++ b/src/pathops/SkPathOpsQuad.h
@@ -62,6 +62,13 @@ struct SkDQuad {
     SkDQuadPair chopAt(double t) const;
     SkDVector dxdyAtT(double t) const;
     static int FindExtrema(const double src[], double tValue[1]);
+
+    /**
+     *  Return the number of valid roots (0 < root < 1) for this cubic intersecting the
+     *  specified horizontal line.
+     */
+    int horizontalIntersect(double yIntercept, double roots[2]) const;
+
     bool hullIntersects(const SkDQuad& , bool* isLinear) const;
     bool hullIntersects(const SkDConic& , bool* isLinear) const;
     bool hullIntersects(const SkDCubic& , bool* isLinear) const;
@@ -87,6 +94,12 @@ struct SkDQuad {
         return quad.subDivide(a, c, t1, t2);
     }
 
+    /**
+     *  Return the number of valid roots (0 < root < 1) for this cubic intersecting the
+     *  specified vertical line.
+     */
+    int verticalIntersect(double xIntercept, double roots[2]) const;
+
     SkDCubic debugToCubic() const;
     // utilities callable by the user from the debugger when the implementation code is linked in
     void dump() const;