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_Side
+ * of a segment to the kLeft_Side, the winding score should
+ * add 1.
+ * And winding score should subtract 1 if the scanline cross
+ * from kLeft_Side to kRight_Side.
+ * Always return kNA_Side 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 {

[bsalomon, 2016/02/02 18:03:48]

nit, we usually put the full name of the enum after the underscore so either

enum SegSide {
    kLeft_SegSide,
...
};

or 

enum Side {
    kLeft_Side,
...
};

[Joel.Liang, 2016/02/04 12:12:05]

Done.

+    kLeft_Side  = -1,
+    kOn_Side    =  0,
+    kRight_Side =  1,
+    kNA_Side    =  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 DMatrix
+ */
+
+// Scalar with double precision
+typedef double DScalar;

[mtklein, 2016/02/04 14:32:59]

We could probably just type "double".  SkScalar only exists to abstract away
whether it's float or double, but this one's always going to be double.

[Joel.Liang, 2016/02/05 10:10:55]

Done.

+
+// 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
+class DMatrix {

[bsalomon, 2016/02/02 18:03:48]

SkMatrix promotes itself to doubles for some operations (offhand not totally
sure which). I'm just wondering if you tried it and it didn't give sufficient
precision or the conversions were too expensive.

[Joel.Liang, 2016/02/04 12:12:04]

I just tried SkMatrix, it didn't give sufficient precision for this algorithm.
And we only use this matrix for affine transformation. So I did some
modifications here.

+public:
+    DScalar operator[](int index) const {
+        SkASSERT((unsigned)index < 9);
+        return fMat[index];
+    }
+
+    DScalar& operator[](int index) {
+        SkASSERT((unsigned)index < 9);
+        return fMat[index];
+    }
+
+    enum {
+        kMScaleX,
+        kMSkewX,
+        kMTransX,
+        kMSkewY,
+        kMScaleY,
+        kMTransY,
+        kMPersp0,
+        kMPersp1,
+        kMPersp2
+    };
+
+    void setAll(DScalar scaleX, DScalar skewX,  DScalar transX,
+                DScalar skewY,  DScalar scaleY, DScalar transY,
+                DScalar persp0, DScalar persp1, DScalar persp2) {
+        fMat[kMScaleX] = scaleX;
+        fMat[kMSkewX]  = skewX;
+        fMat[kMTransX] = transX;
+        fMat[kMSkewY]  = skewY;
+        fMat[kMScaleY] = scaleY;
+        fMat[kMTransY] = transY;
+        fMat[kMPersp0] = persp0;
+        fMat[kMPersp1] = persp1;
+        fMat[kMPersp2] = persp2;
+    }
+
+    /** Set the matrix to identity
+    */
+    void reset() {
+        fMat[kMScaleX] = fMat[kMScaleY] = fMat[kMPersp2] = 1.0;
+        fMat[kMSkewX]  = fMat[kMSkewY] =
+        fMat[kMTransX] = fMat[kMTransY] =
+        fMat[kMPersp0] = fMat[kMPersp1] = 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[kMScaleX] * src.x() + fMat[kMSkewY] * src.y() + fMat[kMPersp0],

[mtklein, 2016/02/04 14:32:59]

If you only use this matrix for affine transformations, why does it have 9
components, and why is this map points using the perspective components?

Typically we'd expect an affine transformation to take the form:
   x' = x*sx + y*kx + tx
   y' = y*sy + x*ky + ty,

where s == scale, k == skew, t == translate.  You appear to have written this as

   x' = x*sx + y*ky + p0
   y' = x*kx + y*sy + p1

I'm still not quite awake, but I think what you've written here is just the
transpose of what your terms say they mean.

Let's at least try relabeling the coefficients and removing unused coefficients.
 We might even try using SkMatrix again now that we've realized we were working
with the transpose...

[Wasim.Abbas, 2016/02/04 14:48:38]

In Patch Set 5 we have changed this matrix code. It only has 6 components now.
And I think we have answered your concerns of transpose as well.

+                            fMat[kMSkewX] * src.x() + fMat[kMScaleY] * src.y() + fMat[kMPersp1]);
+    }
+private:
+    DScalar fMat[9];
+};
+
+///////////////////////////////////////////////////////////////////////////////
+
+static const SkScalar kClose = (SK_Scalar1 / 16.0);
+static const SkScalar kCloseSqd = SkScalarMul(kClose, kClose);
+static const SkScalar kNearlyZero = (SK_Scalar1 / (1 << 15));
+
+static inline bool between_closed_open(double a, double b, double c,

[bsalomon, 2016/02/02 18:03:48]

Should these doubles be DScalars? (same for the constants above)

[Joel.Liang, 2016/02/04 12:12:05]

Done.

+                                       SkScalar 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(double a, double b, double c,
+                                  SkScalar 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(double x,
+                               SkScalar tolerance = kNearlyZero) {
+    SkASSERT(tolerance >= 0.f);
+    return fabs(x) <= tolerance;
+}
+
+static inline bool nearly_equal(double x, double y,
+                                SkScalar tolerance = kNearlyZero) {
+    SkASSERT(tolerance >= 0.f);
+    return fabs(x - y) <= tolerance;
+}
+
+static inline float sign_of(const float &val) {

[bsalomon, 2016/02/02 18:03:48]

Do we not have a helper for this already?

[Joel.Liang, 2016/02/04 12:12:04]

For input value 0.0, we need 1.0 return here. The helper SkScalarSignAsScalar we
have returns 0.0 in this case.

+    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  fB0T, fB2T;
+    DMatrix 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 b0 = DPoint::Make(this->fPts[0].x(), this->fPts[0].y());
+    const DPoint b2 = DPoint::Make(this->endPt().x(), this->endPt().y());
+    const DScalar b0x = b0.x();
+    const DScalar b0y = b0.y();
+    const DScalar b2x = b2.x();
+    const DScalar b2y = b2.y();
+
+    this->fBoundingBox.set(this->fPts[0], this->endPt());
+
+    if (this->fType == PathSegment::kLine) {
+        this->fScalingFactor = DPoint::Distance(b0, b2);
+
+        const DScalar cosTheta = (b2x - b0x) / this->fScalingFactor;
+        const DScalar sinTheta = (b2y - b0y) / this->fScalingFactor;
+
+        this->fXformMatrix.setAll(
+            cosTheta, -sinTheta, 0.0,
+            sinTheta, cosTheta, 0.0,
+            -(cosTheta * b0x) - (sinTheta * b0y), (sinTheta * b0x) - (cosTheta * b0y), 1.0
+        );

[Joel.Liang, 2016/02/04 12:12:04]

This matrix is a transposed matrix of general OpenGL/Skia matrix.
So I decided to transpose back in the next commit.

+    } else {
+        SkASSERT(this->fType == PathSegment::kQuad);
+
+        // Calculate bounding box
+        const SkPoint _P1mP0 = this->fPts[1] - this->fPts[0];
+        SkPoint t = _P1mP0 - this->fPts[2] + this->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 b1 = this->fPts[0] + t;
+        this->fBoundingBox.growToInclude(&b1, 1);
+
+        const DScalar cp1x = this->fPts[1].x();
+        const DScalar cp1y = this->fPts[1].y();
+
+
+        const double a = pow(b0y - (2.0 * cp1y) + b2y, 2.0);

[bsalomon, 2016/02/02 18:03:48]

DScalars?

[Joel.Liang, 2016/02/04 12:12:05]

Done.

+        const double h = -1.0 * (b0y - (2.0 * cp1y) + b2y) * (b0x - (2.0 * cp1x) + b2x);
+        const double b = pow(b0x - (2.0 * cp1x) + b2x, 2.0);

[bsalomon, 2016/02/02 18:03:48]

Are pow(<foo>, 2.0)s as fast as <foo>*<foo>? 

[Joel.Liang, 2016/02/04 12:12:04]

I done a performance test for pow and <foo>*<foo>, the latter one have better
performance.
So I decided change pow to <foo>*<foo>.

+        const double c = (pow(b0x, 2.0) * pow(b2y, 2.0)) - (4.0 * b0x * cp1x * cp1y * b2y)
+                - (2.0 * b0x * b2x * b0y * b2y) + (4.0 * b0x * b2x * pow(cp1y, 2.0))
+                + (4.0 * pow(cp1x, 2.0) * b0y * b2y) - (4.0 * cp1x * b2x * b0y * cp1y)
+                + (pow(b2x, 2.0) * pow(b0y, 2.0));
+        const double g = (b0x * b0y * b2y) - (2.0 * b0x * pow(cp1y, 2.0))
+                + (2.0 * b0x * cp1y * b2y) - (b0x * pow(b2y, 2.0))
+                + (2.0 * cp1x * b0y * cp1y) - (4.0 * cp1x * b0y * b2y)
+                + (2.0 * cp1x * cp1y * b2y) - (b2x * pow(b0y, 2.0))
+                + (2.0 * b2x * b0y * cp1y) + (b2x * b0y * b2y)
+                - (2.0 * b2x * pow(cp1y, 2.0));
+        const double f = -((pow(b0x, 2.0) * b2y) - (2.0 * b0x * cp1x * cp1y)
+                - (2.0 * b0x * cp1x * b2y) - (b0x * b2x * b0y)
+                + (4.0 * b0x * b2x * cp1y) - (b0x * b2x * b2y)
+                + (2.0 * pow(cp1x, 2.0) * b0y) + (2.0 * pow(cp1x, 2.0) * b2y)
+                - (2.0 * cp1x * b2x * b0y) - (2.0 * cp1x * b2x * cp1y)
+                + (pow(b2x, 2.0) * b0y));
+
+
+        const double cosTheta = sqrt(a / (a + b));
+        const double sinTheta = -1.0 * sign_of((a + b) * h) * sqrt(b / (a + b));
+
+        const double gDef = cosTheta * g - sinTheta * f;
+        const double fDef = sinTheta * g + cosTheta * f;
+
+
+        const double x0 = gDef / (a + b);
+        const double y0 = (1.0 / (2.0 * fDef)) * (c - (pow(gDef, 2.0) / (a + b)));
+
+
+        const double lambda = -1.0 * ((a + b) / (2.0 * fDef));
+        this->fScalingFactor = (1.0 / lambda);
+        this->fScalingFactor *= this->fScalingFactor;
+
+
+        this->fXformMatrix.setAll(
+            lambda * cosTheta, lambda * sinTheta, 0.0,
+            - lambda * sinTheta, lambda * cosTheta, 0.0,
+            lambda * x0, lambda * y0, 1.0
+        );

[Joel.Liang, 2016/02/04 12:12:04]

Transpose the matrix in the next commit.

+    }
+
+    this->fB0T = this->fXformMatrix.mapPoint(b0);
+    this->fB2T = this->fXformMatrix.mapPoint(b2);
+}
+
+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) {
+    #define THIRD float(0.33333333333f)

[bsalomon, 2016/02/02 18:03:48]

If you're only using these in this function maybe static const float?

[Joel.Liang, 2016/02/04 12:12:05]

Done.

+    #define TWENTYSEVENTH float(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 * TWENTYSEVENTH);
+
+    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 * THIRD) * (float)cos(phi * THIRD);
+            if (!between_closed(result, segment.fB0T.x(), segment.fB2T.x())) {
+                result = 2.f * (float)sqrt(-a * THIRD) * (float)cos((phi * THIRD) + (SK_ScalarPI * 2.f * THIRD));
+            }
+        } else {
+            result = 2.f * (float)sqrt(-a * THIRD) * (float)cos((phi * THIRD) + (SK_ScalarPI * 2.f * THIRD));
+            if (!between_closed(result, segment.fB0T.x(), segment.fB2T.x())) {
+                result = 2.f * (float)sqrt(-a * THIRD) * (float)cos(phi * THIRD);
+            }
+        }
+        return result;
+    }
+}
+
+struct RowData

[bsalomon, 2016/02/02 18:03:48]

Some comments on this struct might be useful (e.g. what fSignB0B2 is)

[Joel.Liang, 2016/02/04 12:12:05]

Done. I have changed some member variable name and added comments to them.

+{

[bsalomon, 2016/02/02 18:03:48]

{ on prev line

[Joel.Liang, 2016/02/04 12:12:04]

Done.

+    enum IntersectionType {
+        kNoIntersection,
+        kVerticalLine,
+        kTangentLine,
+        kTwoPointsIntersect
+    } fIntersectionType;
+    int fSignB0B2;
+    double fPow2x;

[bsalomon, 2016/02/02 18:03:48]

DScalars?

[Joel.Liang, 2016/02/04 12:12:04]

Done.

+    double fIntersectionPoint1;
+    double fIntersectionPoint2;
+};
+
+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->fSignB0B2 = sign_of(segment.fB2T.x() - segment.fB0T.x());
+
+    const double x1 = xFormPtLeft.x();

[bsalomon, 2016/02/02 18:03:48]

DScalars?

[Joel.Liang, 2016/02/04 12:12:04]

Done.

+    const double y1 = xFormPtLeft.y();
+    const double x2 = xFormPtRight.x();
+    const double y2 = xFormPtRight.y();
+
+    if (nearly_equal(x1, x2)) {
+        rowData->fIntersectionType = RowData::kVerticalLine;
+        rowData->fPow2x = pow(x1, 2.0);
+        return;
+    }
+
+    // Line y = mx + b
+    const double m = (y2 - y1) / (x2 - x1);
+    const double b = -m * x1 + y1;
+
+    const double c = pow(m, 2.0) + 4.0 * b;
+
+    if (nearly_zero(c, 4.0 * kNearlyZero * kNearlyZero)) {
+        rowData->fIntersectionType = RowData::kTangentLine;
+        rowData->fIntersectionPoint1 = m / 2.0;
+        rowData->fIntersectionPoint2 = m / 2.0;
+    } else if (c < 0.0) {
+        rowData->fIntersectionType = RowData::kNoIntersection;
+        return;
+    } else {
+        rowData->fIntersectionType = RowData::kTwoPointsIntersect;
+        const double d = sqrt(c);
+        rowData->fIntersectionPoint1 = (m + d) / 2.0;
+        rowData->fIntersectionPoint2 = (m - d) / 2.0;
+    }
+}
+
+SegSide calculate_side_of_quad(
+            const PathSegment& segment,
+            const SkPoint& point,
+            const DPoint& xFormPt,
+            const RowData& rowData) {
+    SegSide side = kNA_Side;
+
+    if (RowData::kVerticalLine == rowData.fIntersectionType) {
+        side = (SegSide)(int)(sign_of(rowData.fPow2x - xFormPt.y()) * rowData.fSignB0B2);
+    }
+    else if (RowData::kTwoPointsIntersect == rowData.fIntersectionType ||
+             RowData::kTangentLine == rowData.fIntersectionType) {
+        const double p1 = rowData.fIntersectionPoint1;
+        const double p2 = rowData.fIntersectionPoint2;
+
+        int signP1 = sign_of(p1 - xFormPt.x());
+        if (between_closed(p1, segment.fB0T.x(), segment.fB2T.x())) {
+            side = (SegSide)((-signP1) * rowData.fSignB0B2);
+        }
+        if (between_closed(p2, segment.fB0T.x(), segment.fB2T.x())) {
+            int signP2 = sign_of(p2 - xFormPt.x());
+            if (side == kNA_Side || signP2 == 1) {
+                side = (SegSide)(signP2 * rowData.fSignB0B2);
+            }
+        }
+
+        // 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.fB0T.x())) {
+                side = (SegSide)(side * (-signP1) * rowData.fSignB0B2);
+            }
+
+            // The path end at the tangent point.
+            if (nearly_equal(p1, segment.fB2T.x())) {
+                side = (SegSide)(side * signP1 * rowData.fSignB0B2);
+            }
+        }
+    }
+
+    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.fB0T.x(), segment.fB2T.x())) {
+            result = pow(xformPt.y(), 2.0);
+        } else if (xformPt.x() < segment.fB0T.x()) {
+            result = (pow(xformPt.x(), 2.0) + pow(xformPt.y(), 2.0));
+        } else {
+            result = (pow((xformPt.x() - segment.fB2T.x()), 2.0)
+                    + pow(xformPt.y(), 2.0));
+        }
+
+        if (between_closed_open(point.y(), segment.fBoundingBox.top(),
+                                segment.fBoundingBox.bottom())) {
+            *side = (SegSide)(int)sign_of(-xformPt.y());
+        } else {
+            *side = kNA_Side;
+        }
+        return result;
+    } else {
+        SkASSERT(segment.fType == PathSegment::kQuad);
+
+        const DPoint& xformPt = segment.fXformMatrix.mapPoint(point);
+        const float nearestPoint = calculate_nearest_point_for_quad(segment, xformPt);
+
+        float dist;
+
+        if (between_closed(nearestPoint, segment.fB0T.x(), segment.fB2T.x())) {
+            DPoint x = DPoint::Make(nearestPoint, nearestPoint * nearestPoint);
+            dist = xformPt.distanceToSqd(x);
+        } else {
+            const float distToB0T = xformPt.distanceToSqd(segment.fB0T);
+            const float distToB2T = xformPt.distanceToSqd(segment.fB2T);
+
+            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_Side;
+        }
+
+        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_Side;
+            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()

[bsalomon, 2016/02/02 18:03:48]

&& on prev line, looks like everything following && fits on one line (we use 100
col).

[Joel.Liang, 2016/02/04 12:12:04]

Not fits within 100 col. So I split it into 2 lines instead of 4 lines.

+                    .makeOutset(dilation, dilation)
+                    .contains(col, row)) {
+                    continue;
+                }
+
+                SegSide side = kNA_Side;
+                int     deltaWindingScore = 0;
+                float   currDistSq =
+                            distance_to_segment(point, segment, rowData, &side);
+                if (prevSide == kLeft_Side && side == kRight_Side) {
+                    deltaWindingScore = -1;
+                } else if (prevSide == kRight_Side && side == kLeft_Side) {
+                    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) {
+    if (dist <= -(distanceMagnitude * (1.0f - 1.0f / 128.0f))) {
+        return 255;
+    } else if (dist > distanceMagnitude) {
+        return 0;
+    } else {
+        return (unsigned char)((distanceMagnitude - dist) * 128.0f / distanceMagnitude);
+    }
+}
+
+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;
+}