Generate Signed Distance Field directly from vector path

src/gpu/GrDistanceFieldGenFromVector.cpp

+/*
+ * Copyright 2016 ARM Ltd.
+ *
+ * Use of this source code is governed by a BSD-style license that can be
+ * found in the LICENSE file.
+ */
+
+#include "GrDistanceFieldGenFromVector.h"
+#include "SkPoint.h"
+#include "SkGeometry.h"
+#include "GrPathUtils.h"
+#include "GrConfig.h"
+
+/**
+ * If a scanline (a row of texel) cross from the kRight_SegSide
+ * of a segment to the kLeft_SegSide, the winding score should
+ * add 1.
+ * And winding score should subtract 1 if the scanline cross
+ * from kLeft_SegSide to kRight_SegSide.
+ * Always return kNA_SegSide if the scanline does not cross over
+ * the segment. Winding score should be zero in this case.
+ * You can get the winding number for each texel of the scanline
+ * by adding the winding score from left to right.
+ * Assuming we always start from outside, so the winding number
+ * should always start from zero.
+ *      ________         ________
+ *     |        |       |        |
+ * ...R|L......L|R.....L|R......R|L..... <= Scanline & side of segment
+ *     |+1      |-1     |-1      |+1     <= Winding score
+ *   0 |   1    ^   0   ^  -1    |0      <= Winding number
+ *     |________|       |________|
+ *
+ * .......NA................NA..........
+ *         0                 0
+ */
+enum SegSide {
+    kLeft_SegSide  = -1,
+    kOn_SegSide    =  0,
+    kRight_SegSide =  1,
+    kNA_SegSide    =  2,
+};
+
+struct DFData {
+    float fDistSq;            // distance squared to nearest (so far) edge
+    int   fDeltaWindingScore; // +1 or -1 whenever a scanline cross over a segment
+};
+
+///////////////////////////////////////////////////////////////////////////////
+
+/*
+ * Type definition for double precision DScalar, DPoint and DAffineMatrix
+ */
+
+// Scalar with double precision
+typedef double DScalar;
+
+// Point with double precision
+struct DPoint {
+    DScalar fX, fY;
+
+    static DPoint Make(DScalar x, DScalar y) {
+        DPoint pt;
+        pt.set(x, y);
+        return pt;
+    }
+
+    DScalar x() const { return fX; }
+    DScalar y() const { return fY; }
+
+    void set(DScalar x, DScalar y) { fX = x; fY = y; }
+
+    /** Returns the euclidian distance from (0,0) to (x,y)
+    */
+    static DScalar Length(DScalar x, DScalar y) {
+        return sqrt(x * x + y * y);
+    }
+
+    /** Returns the euclidian distance between a and b
+    */
+    static DScalar Distance(const DPoint& a, const DPoint& b) {
+        return Length(a.fX - b.fX, a.fY - b.fY);
+    }
+
+    DScalar distanceToSqd(const DPoint& pt) const {
+        DScalar dx = fX - pt.fX;
+        DScalar dy = fY - pt.fY;
+        return dx * dx + dy * dy;
+    }
+};
+
+// Matrix with double precision for affine transformation.
+// We don't store row 3 because its always (0, 0, 1).
+class DAffineMatrix {
+public:
+    DScalar operator[](int index) const {
+        SkASSERT((unsigned)index < 6);
+        return fMat[index];
+    }
+
+    DScalar& operator[](int index) {
+        SkASSERT((unsigned)index < 6);
+        return fMat[index];
+    }
+
+    void setAffine(DScalar m11, DScalar m12, DScalar m13,
+                   DScalar m21, DScalar m22, DScalar m23) {
+        fMat[0] = m11;
+        fMat[1] = m12;
+        fMat[2] = m13;
+        fMat[3] = m21;
+        fMat[4] = m22;
+        fMat[5] = m23;
+    }
+
+    /** Set the matrix to identity
+    */
+    void reset() {
+        fMat[0] = fMat[4] = 1.0;
+        fMat[1] = fMat[3] =
+        fMat[2] = fMat[5] = 0.0;
+    }
+
+    // alias for reset()
+    void setIdentity() { this->reset(); }
+
+    DPoint mapPoint(const SkPoint& src) const {
+        DPoint pt = DPoint::Make(src.x(), src.y());
+        return this->mapPoint(pt);
+    }
+
+    DPoint mapPoint(const DPoint& src) const {
+        return DPoint::Make(fMat[0] * src.x() + fMat[1] * src.y() + fMat[2],
+                            fMat[3] * src.x() + fMat[4] * src.y() + fMat[5]);
+    }
+private:
+    DScalar fMat[6];
+};
+
+///////////////////////////////////////////////////////////////////////////////
+
+static const DScalar kClose = (SK_Scalar1 / 16.0);
+static const DScalar kCloseSqd = SkScalarMul(kClose, kClose);
+static const DScalar kNearlyZero = (SK_Scalar1 / (1 << 15));
+
+static inline bool between_closed_open(DScalar a, DScalar b, DScalar c,
+                                       DScalar tolerance = kNearlyZero) {
+    SkASSERT(tolerance >= 0.f);
+    return b < c ? (a >= b - tolerance && a < c - tolerance) :
+                   (a >= c - tolerance && a < b - tolerance);
+}
+
+static inline bool between_closed(DScalar a, DScalar b, DScalar c,
+                                  DScalar tolerance = kNearlyZero) {
+    SkASSERT(tolerance >= 0.f);
+    return b < c ? (a >= b - tolerance && a <= c + tolerance) :
+                   (a >= c - tolerance && a <= b + tolerance);
+}
+
+static inline bool nearly_zero(DScalar x, DScalar tolerance = kNearlyZero) {
+    SkASSERT(tolerance >= 0.f);
+    return fabs(x) <= tolerance;
+}
+
+static inline bool nearly_equal(DScalar x, DScalar y, DScalar tolerance = kNearlyZero) {
+    SkASSERT(tolerance >= 0.f);
+    return fabs(x - y) <= tolerance;
+}
+
+static inline float sign_of(const float &val) {
+    return (val < 0.f) ? -1.f : 1.f;
+}
+
+static bool is_colinear(const SkPoint pts[3]) {
+    return nearly_zero((pts[1].y() - pts[0].y()) * (pts[1].x() - pts[2].x()) -
+                       (pts[1].y() - pts[2].y()) * (pts[1].x() - pts[0].x()));
+}
+
+class PathSegment {
+public:
+    enum {
+        // These enum values are assumed in member functions below.
+        kLine = 0,
+        kQuad = 1,
+    } fType;
+
+    // line uses 2 pts, quad uses 3 pts
+    SkPoint fPts[3];
+
+    DPoint  fP0T, fP2T;
+    DAffineMatrix fXformMatrix;
+    DScalar fScalingFactor;
+    SkRect  fBoundingBox;
+
+    void init();
+
+    int countPoints() {
+        GR_STATIC_ASSERT(0 == kLine && 1 == kQuad);
+        return fType + 2;
+    }
+
+    const SkPoint& endPt() const {
+        GR_STATIC_ASSERT(0 == kLine && 1 == kQuad);
+        return fPts[fType + 1];
+    };
+};
+
+typedef SkTArray<PathSegment, true> PathSegmentArray;
+
+void PathSegment::init() {
+    const DPoint p0 = DPoint::Make(fPts[0].x(), fPts[0].y());
+    const DPoint p2 = DPoint::Make(this->endPt().x(), this->endPt().y());
+    const DScalar p0x = p0.x();
+    const DScalar p0y = p0.y();
+    const DScalar p2x = p2.x();
+    const DScalar p2y = p2.y();
+
+    fBoundingBox.set(fPts[0], this->endPt());
+
+    if (fType == PathSegment::kLine) {
+        fScalingFactor = DPoint::Distance(p0, p2);
+
+        const DScalar cosTheta = (p2x - p0x) / fScalingFactor;
+        const DScalar sinTheta = (p2y - p0y) / fScalingFactor;
+
+        fXformMatrix.setAffine(
+            cosTheta, sinTheta, -(cosTheta * p0x) - (sinTheta * p0y),
+            -sinTheta, cosTheta, (sinTheta * p0x) - (cosTheta * p0y)
+        );
+    } else {
+        SkASSERT(fType == PathSegment::kQuad);
+
+        // Calculate bounding box
+        const SkPoint _P1mP0 = fPts[1] - fPts[0];
+        SkPoint t = _P1mP0 - fPts[2] + fPts[1];
+        t.fX = _P1mP0.x() / t.x();
+        t.fY = _P1mP0.y() / t.y();
+        t.fX = SkScalarClampMax(t.x(), 1.0);
+        t.fY = SkScalarClampMax(t.y(), 1.0);
+        t.fX = _P1mP0.x() * t.x();
+        t.fY = _P1mP0.y() * t.y();
+        const SkPoint m = fPts[0] + t;
+        fBoundingBox.growToInclude(&m, 1);
+
+        const DScalar p1x = fPts[1].x();
+        const DScalar p1y = fPts[1].y();
+
+        const DScalar p0xSqd = p0x * p0x;
+        const DScalar p0ySqd = p0y * p0y;
+        const DScalar p2xSqd = p2x * p2x;
+        const DScalar p2ySqd = p2y * p2y;
+        const DScalar p1xSqd = p1x * p1x;
+        const DScalar p1ySqd = p1y * p1y;
+
+        const DScalar p01xProd = p0x * p1x;
+        const DScalar p02xProd = p0x * p2x;
+        const DScalar b12xProd = p1x * p2x;
+        const DScalar p01yProd = p0y * p1y;
+        const DScalar p02yProd = p0y * p2y;
+        const DScalar b12yProd = p1y * p2y;
+
+        const DScalar sqrtA = p0y - (2.0 * p1y) + p2y;
+        const DScalar a = sqrtA * sqrtA;
+        const DScalar h = -1.0 * (p0y - (2.0 * p1y) + p2y) * (p0x - (2.0 * p1x) + p2x);
+        const DScalar sqrtB = p0x - (2.0 * p1x) + p2x;
+        const DScalar b = sqrtB * sqrtB;
+        const DScalar c = (p0xSqd * p2ySqd) - (4.0 * p01xProd * b12yProd)
+                - (2.0 * p02xProd * p02yProd) + (4.0 * p02xProd * p1ySqd)
+                + (4.0 * p1xSqd * p02yProd) - (4.0 * b12xProd * p01yProd)
+                + (p2xSqd * p0ySqd);
+        const DScalar g = (p0x * p02yProd) - (2.0 * p0x * p1ySqd)
+                + (2.0 * p0x * b12yProd) - (p0x * p2ySqd)
+                + (2.0 * p1x * p01yProd) - (4.0 * p1x * p02yProd)
+                + (2.0 * p1x * b12yProd) - (p2x * p0ySqd)
+                + (2.0 * p2x * p01yProd) + (p2x * p02yProd)
+                - (2.0 * p2x * p1ySqd);
+        const DScalar f = -((p0xSqd * p2y) - (2.0 * p01xProd * p1y)
+                - (2.0 * p01xProd * p2y) - (p02xProd * p0y)
+                + (4.0 * p02xProd * p1y) - (p02xProd * p2y)
+                + (2.0 * p1xSqd * p0y) + (2.0 * p1xSqd * p2y)
+                - (2.0 * b12xProd * p0y) - (2.0 * b12xProd * p1y)
+                + (p2xSqd * p0y));
+
+        const DScalar cosTheta = sqrt(a / (a + b));
+        const DScalar sinTheta = -1.0 * sign_of((a + b) * h) * sqrt(b / (a + b));
+
+        const DScalar gDef = cosTheta * g - sinTheta * f;
+        const DScalar fDef = sinTheta * g + cosTheta * f;
+
+
+        const DScalar x0 = gDef / (a + b);
+        const DScalar y0 = (1.0 / (2.0 * fDef)) * (c - (gDef * gDef / (a + b)));
+
+
+        const DScalar lambda = -1.0 * ((a + b) / (2.0 * fDef));
+        fScalingFactor = (1.0 / lambda);
+        fScalingFactor *= fScalingFactor;
+
+        const DScalar lambda_cosTheta = lambda * cosTheta;
+        const DScalar lambda_sinTheta = lambda * sinTheta;
+
+        fXformMatrix.setAffine(
+            lambda_cosTheta, -lambda_sinTheta, lambda * x0,
+            lambda_sinTheta, lambda_cosTheta, lambda * y0
+        );
+    }
+
+    fP0T = fXformMatrix.mapPoint(p0);
+    fP2T = fXformMatrix.mapPoint(p2);
+}
+
+static void init_distances(DFData* data, int size) {
+    DFData* currData = data;
+
+    for (int i = 0; i < size; ++i) {
+        // init distance to "far away"
+        currData->fDistSq = SK_DistanceFieldMagnitude * SK_DistanceFieldMagnitude;
+        currData->fDeltaWindingScore = 0;
+        ++currData;
+    }
+}
+
+static inline bool get_direction(const SkPath& path, const SkMatrix& m,
+                                 SkPathPriv::FirstDirection* dir) {
+    if (!SkPathPriv::CheapComputeFirstDirection(path, dir)) {
+        return false;
+    }
+
+    // check whether m reverses the orientation
+    SkASSERT(!m.hasPerspective());
+    SkScalar det2x2 = SkScalarMul(m.get(SkMatrix::kMScaleX), m.get(SkMatrix::kMScaleY)) -
+                      SkScalarMul(m.get(SkMatrix::kMSkewX), m.get(SkMatrix::kMSkewY));
+
+    if (det2x2 < 0) {
+        *dir = SkPathPriv::OppositeFirstDirection(*dir);
+    }
+    return true;
+}
+
+static inline void add_line_to_segment(const SkPoint pts[2],
+                                       PathSegmentArray* segments) {
+    segments->push_back();
+    segments->back().fType = PathSegment::kLine;
+    segments->back().fPts[0] = pts[0];
+    segments->back().fPts[1] = pts[1];
+
+    segments->back().init();
+}
+
+static inline void add_quad_segment(const SkPoint pts[3],
+                                    PathSegmentArray* segments) {
+    if (pts[0].distanceToSqd(pts[1]) < kCloseSqd ||
+        pts[1].distanceToSqd(pts[2]) < kCloseSqd ||
+        is_colinear(pts)) {
+        if (pts[0] != pts[2]) {
+            SkPoint line_pts[2];
+            line_pts[0] = pts[0];
+            line_pts[1] = pts[2];
+            add_line_to_segment(line_pts, segments);
+        }
+    } else {
+        segments->push_back();
+        segments->back().fType = PathSegment::kQuad;
+        segments->back().fPts[0] = pts[0];
+        segments->back().fPts[1] = pts[1];
+        segments->back().fPts[2] = pts[2];
+
+        segments->back().init();
+    }
+}
+
+static inline void add_cubic_segments(const SkPoint pts[4],
+                                      SkPathPriv::FirstDirection dir,
+                                      PathSegmentArray* segments) {
+    SkSTArray<15, SkPoint, true> quads;
+    GrPathUtils::convertCubicToQuads(pts, SK_Scalar1, true, dir, &quads);
+    int count = quads.count();
+    for (int q = 0; q < count; q += 3) {
+        add_quad_segment(&quads[q], segments);
+    }
+}
+
+static float calculate_nearest_point_for_quad(
+                const PathSegment& segment,
+                const DPoint &xFormPt) {
+    static const float kThird = 0.33333333333f;
+    static const float kTwentySeventh = 0.037037037f;
+
+    const float a = 0.5f - xFormPt.y();
+    const float b = -0.5f * xFormPt.x();
+
+    const float a3 = a * a * a;
+    const float b2 = b * b;
+
+    const float c = (b2 * 0.25f) + (a3 * kTwentySeventh);
+
+    if (c >= 0.f) {
+        const float sqrtC = sqrt(c);
+        const float result = (float)cbrt((-b * 0.5f) + sqrtC) + (float)cbrt((-b * 0.5f) - sqrtC);
+        return result;
+    } else {
+        const float cosPhi = (float)sqrt((b2 * 0.25f) * (-27.f / a3)) * ((b > 0) ? -1.f : 1.f);
+        const float phi = (float)acos(cosPhi);
+        float result;
+        if (xFormPt.x() > 0.f) {
+            result = 2.f * (float)sqrt(-a * kThird) * (float)cos(phi * kThird);
+            if (!between_closed(result, segment.fP0T.x(), segment.fP2T.x())) {
+                result = 2.f * (float)sqrt(-a * kThird) * (float)cos((phi * kThird) + (SK_ScalarPI * 2.f * kThird));
+            }
+        } else {
+            result = 2.f * (float)sqrt(-a * kThird) * (float)cos((phi * kThird) + (SK_ScalarPI * 2.f * kThird));
+            if (!between_closed(result, segment.fP0T.x(), segment.fP2T.x())) {
+                result = 2.f * (float)sqrt(-a * kThird) * (float)cos(phi * kThird);
+            }
+        }
+        return result;
+    }
+}
+
+// This structure contains some intermediate values shared by the same row.
+// It is used to calculate segment side of a quadratic bezier.
+struct RowData {
+    // The intersection type of a scanline and y = x * x parabola in canonical space.
+    enum IntersectionType {
+        kNoIntersection,
+        kVerticalLine,
+        kTangentLine,
+        kTwoPointsIntersect
+    } fIntersectionType;
+
+    // The direction of the quadratic segment in the canonical space.
+    //  1: The quadratic segment going from negative x-axis to positive x-axis.
+    // -1: The quadratic segment going from positive x-axis to negative x-axis.
+    int fQuadXDirection;
+
+    // The y-value(equal to x*x) of intersection point for the kVerticalLine intersection type.
+    DScalar fYAtIntersection;
+
+    // The x-value for two intersection points.
+    DScalar fXAtIntersection1;
+    DScalar fXAtIntersection2;
+};
+
+void precomputation_for_row(
+            RowData *rowData,
+            const PathSegment& segment,
+            const SkPoint& pointLeft,
+            const SkPoint& pointRight
+            ) {
+    if (segment.fType != PathSegment::kQuad) {
+        return;
+    }
+
+    const DPoint& xFormPtLeft = segment.fXformMatrix.mapPoint(pointLeft);
+    const DPoint& xFormPtRight = segment.fXformMatrix.mapPoint(pointRight);;
+
+    rowData->fQuadXDirection = sign_of(segment.fP2T.x() - segment.fP0T.x());
+
+    const DScalar x1 = xFormPtLeft.x();
+    const DScalar y1 = xFormPtLeft.y();
+    const DScalar x2 = xFormPtRight.x();
+    const DScalar y2 = xFormPtRight.y();
+
+    if (nearly_equal(x1, x2)) {
+        rowData->fIntersectionType = RowData::kVerticalLine;
+        rowData->fYAtIntersection = x1 * x1;
+        return;
+    }
+
+    // Line y = mx + b
+    const DScalar m = (y2 - y1) / (x2 - x1);
+    const DScalar b = -m * x1 + y1;
+
+    const DScalar c = m * m + 4.0 * b;
+
+    if (nearly_zero(c, 4.0 * kNearlyZero * kNearlyZero)) {
+        rowData->fIntersectionType = RowData::kTangentLine;
+        rowData->fXAtIntersection1 = m / 2.0;
+        rowData->fXAtIntersection2 = m / 2.0;
+    } else if (c < 0.0) {
+        rowData->fIntersectionType = RowData::kNoIntersection;
+        return;
+    } else {
+        rowData->fIntersectionType = RowData::kTwoPointsIntersect;
+        const DScalar d = sqrt(c);
+        rowData->fXAtIntersection1 = (m + d) / 2.0;
+        rowData->fXAtIntersection2 = (m - d) / 2.0;
+    }
+}
+
+SegSide calculate_side_of_quad(
+            const PathSegment& segment,
+            const SkPoint& point,
+            const DPoint& xFormPt,
+            const RowData& rowData) {
+    SegSide side = kNA_SegSide;
+
+    if (RowData::kVerticalLine == rowData.fIntersectionType) {
+        side = (SegSide)(int)(sign_of(rowData.fYAtIntersection - xFormPt.y()) * rowData.fQuadXDirection);
+    }
+    else if (RowData::kTwoPointsIntersect == rowData.fIntersectionType ||
+             RowData::kTangentLine == rowData.fIntersectionType) {
+        const DScalar p1 = rowData.fXAtIntersection1;
+        const DScalar p2 = rowData.fXAtIntersection2;
+
+        int signP1 = sign_of(p1 - xFormPt.x());
+        if (between_closed(p1, segment.fP0T.x(), segment.fP2T.x())) {
+            side = (SegSide)((-signP1) * rowData.fQuadXDirection);
+        }
+        if (between_closed(p2, segment.fP0T.x(), segment.fP2T.x())) {
+            int signP2 = sign_of(p2 - xFormPt.x());
+            if (side == kNA_SegSide || signP2 == 1) {
+                side = (SegSide)(signP2 * rowData.fQuadXDirection);
+            }
+        }
+
+        // The scanline is the tangent line of current quadratic segment.
+        if (RowData::kTangentLine == rowData.fIntersectionType) {
+            // The path start at the tangent point.
+            if (nearly_equal(p1, segment.fP0T.x())) {
+                side = (SegSide)(side * (-signP1) * rowData.fQuadXDirection);
+            }
+
+            // The path end at the tangent point.
+            if (nearly_equal(p1, segment.fP2T.x())) {
+                side = (SegSide)(side * signP1 * rowData.fQuadXDirection);
+            }
+        }
+    }
+
+    return side;
+}
+
+static float distance_to_segment(const SkPoint& point,
+                                 const PathSegment& segment,
+                                 const RowData& rowData,
+                                 SegSide* side) {
+    SkASSERT(side);
+
+    const DPoint xformPt = segment.fXformMatrix.mapPoint(point);
+
+    if (segment.fType == PathSegment::kLine) {
+        float result = SK_DistanceFieldPad * SK_DistanceFieldPad;
+
+        if (between_closed(xformPt.x(), segment.fP0T.x(), segment.fP2T.x())) {
+            result = xformPt.y() * xformPt.y();
+        } else if (xformPt.x() < segment.fP0T.x()) {
+            result = (xformPt.x() * xformPt.x() + xformPt.y() * xformPt.y());
+        } else {
+            result = ((xformPt.x() - segment.fP2T.x()) * (xformPt.x() - segment.fP2T.x())
+                     + xformPt.y() * xformPt.y());
+        }
+
+        if (between_closed_open(point.y(), segment.fBoundingBox.top(),
+                                segment.fBoundingBox.bottom())) {
+            *side = (SegSide)(int)sign_of(-xformPt.y());
+        } else {
+            *side = kNA_SegSide;
+        }
+        return result;
+    } else {
+        SkASSERT(segment.fType == PathSegment::kQuad);
+
+        const float nearestPoint = calculate_nearest_point_for_quad(segment, xformPt);
+
+        float dist;
+
+        if (between_closed(nearestPoint, segment.fP0T.x(), segment.fP2T.x())) {
+            DPoint x = DPoint::Make(nearestPoint, nearestPoint * nearestPoint);
+            dist = xformPt.distanceToSqd(x);
+        } else {
+            const float distToB0T = xformPt.distanceToSqd(segment.fP0T);
+            const float distToB2T = xformPt.distanceToSqd(segment.fP2T);
+
+            if (distToB0T < distToB2T) {
+                dist = distToB0T;
+            } else {
+                dist = distToB2T;
+            }
+        }
+
+        if (between_closed_open(point.y(), segment.fBoundingBox.top(),
+                                segment.fBoundingBox.bottom())) {
+            *side = calculate_side_of_quad(segment, point, xformPt, rowData);
+        } else {
+            *side = kNA_SegSide;
+        }
+
+        return dist * segment.fScalingFactor;
+    }
+}
+
+static void calculate_distance_field_data(PathSegmentArray* segments,
+                                          DFData* dataPtr,
+                                          int width, int height) {
+    int count = segments->count();
+    for (int a = 0; a < count; ++a) {
+        PathSegment& segment = (*segments)[a];
+        const SkRect& segBB = segment.fBoundingBox.makeOutset(
+                                SK_DistanceFieldPad, SK_DistanceFieldPad);
+        int startColumn = segBB.left();
+        int endColumn = segBB.right() + 1;
+
+        int startRow = segBB.top();
+        int endRow = segBB.bottom() + 1;
+
+        SkASSERT((startColumn >= 0) && "StartColumn < 0!");
+        SkASSERT((endColumn <= width) && "endColumn > width!");
+        SkASSERT((startRow >= 0) && "StartRow < 0!");
+        SkASSERT((endRow <= height) && "EndRow > height!");
+
+        for (int row = startRow; row < endRow; ++row) {
+            SegSide prevSide = kNA_SegSide;
+            const float pY = row + 0.5f;
+            RowData rowData;
+
+            const SkPoint pointLeft = SkPoint::Make(startColumn, pY);
+            const SkPoint pointRight = SkPoint::Make(endColumn, pY);
+
+            precomputation_for_row(&rowData, segment, pointLeft, pointRight);
+
+            for (int col = startColumn; col < endColumn; ++col) {
+                int idx = (row * width) + col;
+
+                const float pX = col + 0.5f;
+                const SkPoint point = SkPoint::Make(pX, pY);
+
+                const float distSq = dataPtr[idx].fDistSq;
+                int dilation = distSq < 1.5 * 1.5 ? 1 :
+                               distSq < 2.5 * 2.5 ? 2 :
+                               distSq < 3.5 * 3.5 ? 3 : SK_DistanceFieldPad;
+                if (dilation > SK_DistanceFieldPad) {
+                    dilation = SK_DistanceFieldPad;
+                }
+
+                // Optimisation for not calculating some points.
+                if (dilation != SK_DistanceFieldPad && !segment.fBoundingBox.roundOut()
+                    .makeOutset(dilation, dilation).contains(col, row)) {
+                    continue;
+                }
+
+                SegSide side = kNA_SegSide;
+                int     deltaWindingScore = 0;
+                float   currDistSq = distance_to_segment(point, segment, rowData, &side);
+                if (prevSide == kLeft_SegSide && side == kRight_SegSide) {
+                    deltaWindingScore = -1;
+                } else if (prevSide == kRight_SegSide && side == kLeft_SegSide) {
+                    deltaWindingScore = 1;
+                }
+
+                prevSide = side;
+
+                if (currDistSq < distSq) {
+                    dataPtr[idx].fDistSq = currDistSq;
+                }
+
+                dataPtr[idx].fDeltaWindingScore += deltaWindingScore;
+            }
+        }
+    }
+}
+
+static unsigned char pack_distance_field_val(float dist, float distanceMagnitude) {
+    // The distance field is constructed as unsigned char values, so that the zero value is at 128,
+    // Beside 128, we have 128 values in range [0, 128), but only 127 values in range (128, 255].
+    // So we multiply distanceMagnitude by 127/128 at the latter range to avoid overflow.
+    dist = SkScalarPin(-dist, -distanceMagnitude, distanceMagnitude * 127.0f / 128.0f);
+
+    // Scale into the positive range for unsigned distance
+    dist += distanceMagnitude;
+
+    // Scale into unsigned char range
+    return (unsigned char)(dist / (2 * distanceMagnitude) * 256.0f);
+}
+
+bool GrGenerateDistanceFieldFromPath(unsigned char* distanceField,
+                                     const SkPath& path, const SkMatrix& drawMatrix,
+                                     int width, int height, size_t rowBytes) {
+    SkASSERT(distanceField);
+
+    SkMatrix m = drawMatrix;
+    m.postTranslate(SK_DistanceFieldPad, SK_DistanceFieldPad);
+
+    // create temp data
+    size_t dataSize = width * height * sizeof(DFData);
+    SkAutoSMalloc<1024> dfStorage(dataSize);
+    DFData* dataPtr = (DFData*) dfStorage.get();
+
+    // create initial distance data
+    init_distances(dataPtr, width * height);
+
+    SkPath::Iter iter(path, true);
+    SkSTArray<15, PathSegment, true> segments;
+
+    SkPathPriv::FirstDirection dir;
+    // get_direction can fail for some degenerate paths.
+    if (path.getSegmentMasks() & SkPath::kCubic_SegmentMask &&
+        !get_direction(path, m, &dir)) {
+        return false;
+    }
+
+    for (;;) {
+        SkPoint pts[4];
+        SkPath::Verb verb = iter.next(pts);
+        switch (verb) {
+            case SkPath::kMove_Verb:
+                // m.mapPoints(pts, 1);
+                break;
+            case SkPath::kLine_Verb: {
+                m.mapPoints(pts, 2);
+                add_line_to_segment(pts, &segments);
+                break;
+            }
+            case SkPath::kQuad_Verb:
+                m.mapPoints(pts, 3);
+                add_quad_segment(pts, &segments);
+                break;
+            case SkPath::kConic_Verb: {
+                m.mapPoints(pts, 3);
+                SkScalar weight = iter.conicWeight();
+                SkAutoConicToQuads converter;
+                const SkPoint* quadPts = converter.computeQuads(pts, weight, 0.5f);
+                for (int i = 0; i < converter.countQuads(); ++i) {
+                    add_quad_segment(quadPts + 2*i, &segments);
+                }
+                break;
+            }
+            case SkPath::kCubic_Verb: {
+                m.mapPoints(pts, 4);
+                add_cubic_segments(pts, dir, &segments);
+                break;
+            };
+            default:
+                break;
+        }
+        if (verb == SkPath::kDone_Verb) {
+            break;
+        }
+    }
+
+    calculate_distance_field_data(&segments, dataPtr, width, height);
+
+    for (int row = 0; row < height; ++row) {
+        int windingNumber = 0; // Winding number start from zero for each scanline
+        for (int col = 0; col < width; ++col) {
+            int idx = (row * width) + col;
+            windingNumber += dataPtr[idx].fDeltaWindingScore;
+
+            enum DFSign {
+                kInside = -1,
+                kOutside = 1
+            } dfSign;
+
+            if (path.getFillType() == SkPath::kWinding_FillType) {
+                dfSign = windingNumber ? kInside : kOutside;
+            } else if (path.getFillType() == SkPath::kInverseWinding_FillType) {
+                dfSign = windingNumber ? kOutside : kInside;
+            } else if (path.getFillType() == SkPath::kEvenOdd_FillType) {
+                dfSign = (windingNumber % 2) ? kInside : kOutside;
+            } else {
+                SkASSERT(path.getFillType() == SkPath::kInverseEvenOdd_FillType);
+                dfSign = (windingNumber % 2) ? kOutside : kInside;
+            }
+
+            // The winding number at the end of a scanline should be zero.
+            if ((col == width - 1) && (windingNumber != 0)) {
+                SkASSERT(0 && "Winding number should be zero at the end of a scan line.");
+                return false;
+            }
+
+            const float miniDist = sqrt(dataPtr[idx].fDistSq);
+            const float dist = dfSign * miniDist;
+
+            unsigned char pixelVal =
+                pack_distance_field_val(dist, (float)SK_DistanceFieldMagnitude);
+
+            distanceField[(row * rowBytes) + col] = pixelVal;
+        }
+    }
+    return true;
+}