/*
 * Copyright 2018 Google Inc.
 *
 * Use of this source code is governed by a BSD-style license that can be
 * found in the LICENSE file.
 */

#include "src/gpu/tessellate/GrStrokePatchBuilder.h"

#include "include/core/SkStrokeRec.h"
#include "include/private/SkNx.h"
#include "src/core/SkGeometry.h"
#include "src/core/SkMathPriv.h"
#include "src/core/SkPathPriv.h"
#include "src/gpu/tessellate/GrStrokeTessellateShader.h"
#include "src/gpu/tessellate/GrVectorXform.h"
#include "src/gpu/tessellate/GrWangsFormula.h"

// This is the maximum distance in pixels that we can stray from the edge of a stroke when
// converting it to flat line segments.
static constexpr float kLinearizationIntolerance = 8;  // 1/8 pixel.

constexpr static float kInternalRoundJoinType = GrStrokeTessellateShader::kInternalRoundJoinType;

static Sk2f lerp(const Sk2f& a, const Sk2f& b, float T) {
    SkASSERT(1 != T);  // The below does not guarantee lerp(a, b, 1) === b.
    return (b - a) * T + a;
}

static inline void transpose(const Sk2f& a, const Sk2f& b, Sk2f* X, Sk2f* Y) {
    float transpose[4];
    a.store(transpose);
    b.store(transpose+2);
    Sk2f::Load2(transpose, X, Y);
}

static inline float calc_curvature_costheta(const Sk2f& leftTan, const Sk2f& rightTan) {
    Sk2f X, Y;
    transpose(leftTan, rightTan, &X, &Y);
    Sk2f invlength = (X*X + Y*Y).rsqrt();
    Sk2f dotprod = leftTan * rightTan;
    return (dotprod[0] + dotprod[1]) * invlength[0] * invlength[1];
}

void GrStrokePatchBuilder::allocVertexChunk(int minVertexAllocCount) {
    VertexChunk* chunk = &fVertexChunkArray->push_back();
    fCurrChunkVertexData = (SkPoint*)fTarget->makeVertexSpaceAtLeast(
            sizeof(SkPoint), minVertexAllocCount, minVertexAllocCount, &chunk->fVertexBuffer,
            &chunk->fBaseVertex, &fCurrChunkVertexCapacity);
    fCurrChunkMinVertexAllocCount = minVertexAllocCount;
}

SkPoint* GrStrokePatchBuilder::reservePatch() {
    constexpr static int kNumVerticesPerPatch = GrStrokeTessellateShader::kNumVerticesPerPatch;
    if (fVertexChunkArray->back().fVertexCount + kNumVerticesPerPatch > fCurrChunkVertexCapacity) {
        // The current chunk is full. Time to allocate a new one. (And no need to put back vertices;
        // the buffer is full.)
        this->allocVertexChunk(fCurrChunkMinVertexAllocCount * 2);
    }
    if (!fCurrChunkVertexData) {
        SkDebugf("WARNING: Failed to allocate vertex buffer for tessellated stroke.");
        return nullptr;
    }
    SkASSERT(fVertexChunkArray->back().fVertexCount + kNumVerticesPerPatch <=
             fCurrChunkVertexCapacity);
    SkPoint* patch = fCurrChunkVertexData + fVertexChunkArray->back().fVertexCount;
    fVertexChunkArray->back().fVertexCount += kNumVerticesPerPatch;
    return patch;
}

void GrStrokePatchBuilder::writeCubicSegment(float leftJoinType, const SkPoint pts[4],
                                             float overrideNumSegments) {
    SkPoint c1 = (pts[1] == pts[0]) ? pts[2] : pts[1];
    SkPoint c2 = (pts[2] == pts[3]) ? pts[1] : pts[2];

    if (fHasPreviousSegment) {
        this->writeJoin(leftJoinType, pts[0], fLastControlPoint, c1);
    } else {
        fCurrContourFirstControlPoint = c1;
        fHasPreviousSegment = true;
    }

    if (SkPoint* patch = this->reservePatch()) {
        memcpy(patch, pts, sizeof(SkPoint) * 4);
        patch[4].set(overrideNumSegments, fCurrStrokeRadius);
    }

    fLastControlPoint = c2;
    fCurrentPoint = pts[3];
}

void GrStrokePatchBuilder::writeJoin(float joinType, const SkPoint& anchorPoint,
                                     const SkPoint& prevControlPoint,
                                     const SkPoint& nextControlPoint) {
    if (SkPoint* joinPatch = this->reservePatch()) {
        joinPatch[0] = anchorPoint;
        joinPatch[1] = prevControlPoint;
        joinPatch[2] = nextControlPoint;
        joinPatch[3] = anchorPoint;
        joinPatch[4].set(joinType, fCurrStrokeRadius);
    }
}

void GrStrokePatchBuilder::writeSquareCap(const SkPoint& endPoint, const SkPoint& controlPoint) {
    SkVector v = (endPoint - controlPoint);
    v.normalize();
    SkPoint capPoint = endPoint + v*fCurrStrokeRadius;
    // Construct a line that incorporates controlPoint so we get a water tight edge with the rest of
    // the stroke. The cubic will technically step outside the cap, but we will force it to only
    // have one segment, giving edges only at the endpoints.
    if (SkPoint* capPatch = this->reservePatch()) {
        capPatch[0] = endPoint;
        capPatch[1] = controlPoint;
        // Straddle the midpoint of the cap because the tessellated geometry emits a center point at
        // T=.5, and we need to ensure that point stays inside the cap.
        capPatch[2] = endPoint + capPoint - controlPoint;
        capPatch[3] = capPoint;
        capPatch[4].set(1, fCurrStrokeRadius);
    }
}

void GrStrokePatchBuilder::writeCaps() {
    if (!fHasPreviousSegment) {
        // We don't have any control points to orient the caps. In this case, square and round caps
        // are specified to be drawn as an axis-aligned square or circle respectively. Assign
        // default control points that achieve this.
        fCurrContourFirstControlPoint = fCurrContourStartPoint - SkPoint{1,0};
        fLastControlPoint = fCurrContourStartPoint + SkPoint{1,0};
        fCurrentPoint = fCurrContourStartPoint;
    }

    switch (fCurrStrokeCapType) {
        case SkPaint::kButt_Cap:
            break;
        case SkPaint::kRound_Cap:
            // A round cap is the same thing as a 180-degree round join.
            this->writeJoin(GrStrokeTessellateShader::kRoundJoinType, fCurrContourStartPoint,
                            fCurrContourFirstControlPoint, fCurrContourFirstControlPoint);
            this->writeJoin(GrStrokeTessellateShader::kRoundJoinType, fCurrentPoint,
                            fLastControlPoint, fLastControlPoint);
            break;
        case SkPaint::kSquare_Cap:
            this->writeSquareCap(fCurrContourStartPoint, fCurrContourFirstControlPoint);
            this->writeSquareCap(fCurrentPoint, fLastControlPoint);
            break;
    }
}

void GrStrokePatchBuilder::addPath(const SkPath& path, const SkStrokeRec& stroke) {
    this->beginPath(stroke);
    SkPathVerb previousVerb = SkPathVerb::kClose;
    for (auto [verb, rawPts, w] : SkPathPriv::Iterate(path)) {
        SkPoint pts[4];
        int numPtsInVerb = SkPathPriv::PtsInIter((unsigned)verb);
        for (int i = 0; i < numPtsInVerb; ++i) {
            // TEMPORORY: Scale all the points up front. SkFind*MaxCurvature and GrWangsFormula::*
            // both expect arrays of points. As we refine this class and its math, this scale will
            // hopefully be integrated more efficiently.
            pts[i] = rawPts[i] * fMatrixScale;
        }
        switch (verb) {
            case SkPathVerb::kMove:
                // "A subpath ... consisting of a single moveto shall not be stroked."
                // https://www.w3.org/TR/SVG11/painting.html#StrokeProperties
                if (previousVerb != SkPathVerb::kMove && previousVerb != SkPathVerb::kClose) {
                    this->writeCaps();
                }
                this->moveTo(pts[0]);
                break;
            case SkPathVerb::kClose:
                this->close();
                break;
            case SkPathVerb::kLine:
                SkASSERT(previousVerb != SkPathVerb::kClose);
                this->lineTo(pts[0], pts[1]);
                break;
            case SkPathVerb::kQuad:
                SkASSERT(previousVerb != SkPathVerb::kClose);
                this->quadraticTo(pts);
                break;
            case SkPathVerb::kCubic:
                SkASSERT(previousVerb != SkPathVerb::kClose);
                this->cubicTo(pts);
                break;
            case SkPathVerb::kConic:
                SkASSERT(previousVerb != SkPathVerb::kClose);
                SkUNREACHABLE;
        }
        previousVerb = verb;
    }
    if (previousVerb != SkPathVerb::kMove && previousVerb != SkPathVerb::kClose) {
        this->writeCaps();
    }
}

static float join_type_from_join(SkPaint::Join join) {
    switch (join) {
        case SkPaint::kBevel_Join:
            return GrStrokeTessellateShader::kBevelJoinType;
        case SkPaint::kMiter_Join:
            return GrStrokeTessellateShader::kMiterJoinType;
        case SkPaint::kRound_Join:
            return GrStrokeTessellateShader::kRoundJoinType;
    }
    SkUNREACHABLE;
}

void GrStrokePatchBuilder::beginPath(const SkStrokeRec& stroke) {
    // We don't support hairline strokes. For now, the client can transform the path into device
    // space and then use a stroke width of 1.
    SkASSERT(stroke.getWidth() > 0);

    fCurrStrokeRadius = stroke.getWidth()/2 * fMatrixScale;
    fCurrStrokeJoinType = join_type_from_join(stroke.getJoin());
    fCurrStrokeCapType = stroke.getCap();

    // Find the angle of curvature where the arc height above a simple line from point A to point B
    // is equal to 1/kLinearizationIntolerance. (The arc height is always the same no matter how
    // long the line is. What we are interested in is the difference in height between the part of
    // the stroke whose normal is orthogonal to the line, vs the heights at the endpoints.)
    float r = std::max(1 - 1/(fCurrStrokeRadius * kLinearizationIntolerance), 0.f);
    fMaxCurvatureCosTheta = 2*r*r - 1;

    fHasPreviousSegment = false;
}

void GrStrokePatchBuilder::moveTo(const SkPoint& pt) {
    fHasPreviousSegment = false;
    fCurrContourStartPoint = pt;
}

void GrStrokePatchBuilder::lineTo(const SkPoint& p0, const SkPoint& p1) {
    this->lineTo(fCurrStrokeJoinType, p0, p1);
}

void GrStrokePatchBuilder::lineTo(float leftJoinType, const SkPoint& pt0, const SkPoint& pt1) {
    Sk2f p0 = Sk2f::Load(&pt0);
    Sk2f p1 = Sk2f::Load(&pt1);
    if ((p0 == p1).allTrue()) {
        return;
    }
    this->writeCubicSegment(leftJoinType, p0, lerp(p0, p1, 1/3.f), lerp(p0, p1, 2/3.f), p1, 1);
}

void GrStrokePatchBuilder::quadraticTo(const SkPoint P[3]) {
    this->quadraticTo(fCurrStrokeJoinType, P, SkFindQuadMaxCurvature(P));
}

void GrStrokePatchBuilder::quadraticTo(float leftJoinType, const SkPoint P[3],
                                       float maxCurvatureT) {
    if (P[1] == P[0] || P[1] == P[2]) {
        this->lineTo(leftJoinType, P[0], P[2]);
        return;
    }

    // Decide a lower bound on the length (in parametric sense) of linear segments the curve will be
    // chopped into.
    int numSegments = 1 << GrWangsFormula::quadratic_log2(kLinearizationIntolerance, P);
    float segmentLength = SkScalarInvert(numSegments);

    Sk2f p0 = Sk2f::Load(P);
    Sk2f p1 = Sk2f::Load(P+1);
    Sk2f p2 = Sk2f::Load(P+2);

    Sk2f tan0 = p1 - p0;
    Sk2f tan1 = p2 - p1;

    // At + B gives a vector tangent to the quadratic.
    Sk2f A = p0 - p1*2 + p2;
    Sk2f B = p1 - p0;

    // Find a line segment that crosses max curvature.
    float leftT = maxCurvatureT - segmentLength/2;
    float rightT = maxCurvatureT + segmentLength/2;
    Sk2f leftTan, rightTan;
    if (leftT <= 0) {
        leftT = 0;
        leftTan = tan0;
        rightT = segmentLength;
        rightTan = A*rightT + B;
    } else if (rightT >= 1) {
        leftT = 1 - segmentLength;
        leftTan = A*leftT + B;
        rightT = 1;
        rightTan = tan1;
    } else {
        leftTan = A*leftT + B;
        rightTan = A*rightT + B;
    }

    // Check if curvature is too strong for a triangle strip on the line segment that crosses max
    // curvature. If it is, we will chop and convert the segment to a "lineTo" with round joins.
    //
    // FIXME: This is quite costly and the vast majority of curves only have moderate curvature. We
    // would benefit significantly from a quick reject that detects curves that don't need special
    // treatment for strong curvature.
    if (numSegments > 1 && calc_curvature_costheta(leftTan, rightTan) < fMaxCurvatureCosTheta) {
        SkPoint ptsBuffer[5];
        const SkPoint* currQuadratic = P;

        if (leftT > 0) {
            SkChopQuadAt(currQuadratic, ptsBuffer, leftT);
            this->quadraticTo(leftJoinType, ptsBuffer, /*maxCurvatureT=*/1);
            if (rightT < 1) {
                rightT = (rightT - leftT) / (1 - leftT);
            }
            currQuadratic = ptsBuffer + 2;
        } else {
            this->rotateTo(leftJoinType, currQuadratic[0], currQuadratic[1]);
        }

        if (rightT < 1) {
            SkChopQuadAt(currQuadratic, ptsBuffer, rightT);
            this->lineTo(kInternalRoundJoinType, ptsBuffer[0], ptsBuffer[2]);
            this->quadraticTo(kInternalRoundJoinType, ptsBuffer + 2, /*maxCurvatureT=*/0);
        } else {
            this->lineTo(kInternalRoundJoinType, currQuadratic[0], currQuadratic[2]);
            this->rotateTo(kInternalRoundJoinType, currQuadratic[2],
                           currQuadratic[2]*2 - currQuadratic[1]);
        }
        return;
    }
    if (numSegments > fMaxTessellationSegments) {
        SkPoint ptsBuffer[5];
        SkChopQuadAt(P, ptsBuffer, 0.5f);
        this->quadraticTo(leftJoinType, ptsBuffer, 0);
        this->quadraticTo(kInternalRoundJoinType, ptsBuffer + 3, 0);
        return;
    }

    this->writeCubicSegment(leftJoinType, p0, lerp(p0, p1, 2/3.f), lerp(p1, p2, 1/3.f), p2);
}

void GrStrokePatchBuilder::cubicTo(const SkPoint P[4]) {
    float roots[3];
    int numRoots = SkFindCubicMaxCurvature(P, roots);
    this->cubicTo(fCurrStrokeJoinType, P,
                  numRoots > 0 ? roots[numRoots/2] : 0,
                  numRoots > 1 ? roots[0] : kLeftMaxCurvatureNone,
                  numRoots > 2 ? roots[2] : kRightMaxCurvatureNone);
}

void GrStrokePatchBuilder::cubicTo(float leftJoinType, const SkPoint P[4], float maxCurvatureT,
                                   float leftMaxCurvatureT, float rightMaxCurvatureT) {
    if (P[1] == P[2] && (P[1] == P[0] || P[1] == P[3])) {
        this->lineTo(leftJoinType, P[0], P[3]);
        return;
    }

    // Decide a lower bound on the length (in parametric sense) of linear segments the curve will be
    // chopped into.
    int numSegments = 1 << GrWangsFormula::cubic_log2(kLinearizationIntolerance, P);
    float segmentLength = SkScalarInvert(numSegments);

    Sk2f p0 = Sk2f::Load(P);
    Sk2f p1 = Sk2f::Load(P+1);
    Sk2f p2 = Sk2f::Load(P+2);
    Sk2f p3 = Sk2f::Load(P+3);

    Sk2f tan0 = p1 - p0;
    Sk2f tan1 = p3 - p2;

    // At^2 + Bt + C gives a vector tangent to the cubic. (More specifically, it's the derivative
    // minus an irrelevant scale by 3, since all we care about is the direction.)
    Sk2f A = p3 + (p1 - p2)*3 - p0;
    Sk2f B = (p0 - p1*2 + p2)*2;
    Sk2f C = p1 - p0;

    // Find a line segment that crosses max curvature.
    float leftT = maxCurvatureT - segmentLength/2;
    float rightT = maxCurvatureT + segmentLength/2;
    Sk2f leftTan, rightTan;
    if (leftT <= 0) {
        leftT = 0;
        leftTan = tan0;
        rightT = segmentLength;
        rightTan = A*rightT*rightT + B*rightT + C;
    } else if (rightT >= 1) {
        leftT = 1 - segmentLength;
        leftTan = A*leftT*leftT + B*leftT + C;
        rightT = 1;
        rightTan = tan1;
    } else {
        leftTan = A*leftT*leftT + B*leftT + C;
        rightTan = A*rightT*rightT + B*rightT + C;
    }

    // Check if curvature is too strong for a triangle strip on the line segment that crosses max
    // curvature. If it is, we will chop and convert the segment to a "lineTo" with round joins.
    //
    // FIXME: This is quite costly and the vast majority of curves only have moderate curvature. We
    // would benefit significantly from a quick reject that detects curves that don't need special
    // treatment for strong curvature.
    if (numSegments > 1 && calc_curvature_costheta(leftTan, rightTan) < fMaxCurvatureCosTheta) {
        SkPoint ptsBuffer[7];
        p0.store(ptsBuffer);
        p1.store(ptsBuffer + 1);
        p2.store(ptsBuffer + 2);
        p3.store(ptsBuffer + 3);
        const SkPoint* currCubic = ptsBuffer;

        if (leftT > 0) {
            SkChopCubicAt(currCubic, ptsBuffer, leftT);
            this->cubicTo(leftJoinType, ptsBuffer, /*maxCurvatureT=*/1,
                          (kLeftMaxCurvatureNone != leftMaxCurvatureT)
                                  ? leftMaxCurvatureT/leftT : kLeftMaxCurvatureNone,
                          kRightMaxCurvatureNone);
            if (rightT < 1) {
                rightT = (rightT - leftT) / (1 - leftT);
            }
            if (rightMaxCurvatureT < 1 && kRightMaxCurvatureNone != rightMaxCurvatureT) {
                rightMaxCurvatureT = (rightMaxCurvatureT - leftT) / (1 - leftT);
            }
            currCubic = ptsBuffer + 3;
        } else {
            SkPoint c1 = (ptsBuffer[1] == ptsBuffer[0]) ? ptsBuffer[2] : ptsBuffer[1];
            this->rotateTo(leftJoinType, ptsBuffer[0], c1);
        }

        if (rightT < 1) {
            SkChopCubicAt(currCubic, ptsBuffer, rightT);
            this->lineTo(kInternalRoundJoinType, ptsBuffer[0], ptsBuffer[3]);
            currCubic = ptsBuffer + 3;
            this->cubicTo(kInternalRoundJoinType, currCubic, /*maxCurvatureT=*/0,
                          kLeftMaxCurvatureNone, kRightMaxCurvatureNone);
        } else {
            this->lineTo(kInternalRoundJoinType, currCubic[0], currCubic[3]);
            SkPoint c2 = (currCubic[2] == currCubic[3]) ? currCubic[1] : currCubic[2];
            this->rotateTo(kInternalRoundJoinType, currCubic[3], currCubic[3]*2 - c2);
        }
        return;
    }

    // Recurse and check the other two points of max curvature, if any.
    if (kRightMaxCurvatureNone != rightMaxCurvatureT) {
        this->cubicTo(leftJoinType, P, rightMaxCurvatureT, leftMaxCurvatureT,
                      kRightMaxCurvatureNone);
        return;
    }
    if (kLeftMaxCurvatureNone != leftMaxCurvatureT) {
        SkASSERT(kRightMaxCurvatureNone == rightMaxCurvatureT);
        this->cubicTo(leftJoinType, P, leftMaxCurvatureT, kLeftMaxCurvatureNone,
                      kRightMaxCurvatureNone);
        return;
    }
    if (numSegments > fMaxTessellationSegments) {
        SkPoint ptsBuffer[7];
        SkChopCubicAt(P, ptsBuffer, 0.5f);
        this->cubicTo(leftJoinType, ptsBuffer, 0, kLeftMaxCurvatureNone, kRightMaxCurvatureNone);
        this->cubicTo(kInternalRoundJoinType, ptsBuffer + 3, 0, kLeftMaxCurvatureNone,
                      kRightMaxCurvatureNone);
        return;
    }

    this->writeCubicSegment(leftJoinType, p0, p1, p2, p3);
}

void GrStrokePatchBuilder::rotateTo(float leftJoinType, const SkPoint& anchorPoint,
                                    const SkPoint& controlPoint) {
    // Effectively rotate the current normal by drawing a zero length, 1-segment cubic.
    // writeCubicSegment automatically adds the necessary join and the zero length cubic serves as
    // a glue that guarantees a water tight rasterized edge between the new join and the segment
    // that comes after the rotate.
    SkPoint pts[4] = {anchorPoint, controlPoint, anchorPoint*2 - controlPoint, anchorPoint};
    this->writeCubicSegment(leftJoinType, pts, 1);
}

void GrStrokePatchBuilder::close() {
    if (!fHasPreviousSegment) {
        // Draw caps instead of closing if the subpath is zero length:
        //
        //   "Any zero length subpath ...  shall be stroked if the 'stroke-linecap' property has a
        //   value of round or square producing respectively a circle or a square."
        //
        //   (https://www.w3.org/TR/SVG11/painting.html#StrokeProperties)
        //
        this->writeCaps();
        return;
    }

    // Draw a line back to the beginning. (This will be discarded if
    // fCurrentPoint == fCurrContourStartPoint.)
    this->lineTo(fCurrStrokeJoinType, fCurrentPoint, fCurrContourStartPoint);
    this->writeJoin(fCurrStrokeJoinType, fCurrContourStartPoint, fLastControlPoint,
                    fCurrContourFirstControlPoint);
}