libs/graphics/sgl/SkStroke.cpp

/* libs/graphics/sgl/SkStroke.cpp
**
** Copyright 2006, Google Inc.
**
** Licensed under the Apache License, Version 2.0 (the "License"); 
** you may not use this file except in compliance with the License. 
** You may obtain a copy of the License at 
**
**     http://www.apache.org/licenses/LICENSE-2.0 
**
** Unless required by applicable law or agreed to in writing, software 
** distributed under the License is distributed on an "AS IS" BASIS, 
** WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 
** See the License for the specific language governing permissions and 
** limitations under the License.
*/

#include "SkStrokerPriv.h"
#include "SkGeometry.h"
#include "SkPath.h"

#define kMaxQuadSubdivide   5
#define kMaxCubicSubdivide  4

static inline bool degenerate_vector(const SkVector& v)
{
    return SkScalarNearlyZero(v.fX) && SkScalarNearlyZero(v.fY);
}

static inline bool degenerate_line(const SkPoint& a, const SkPoint& b, SkScalar tolerance = SK_ScalarNearlyZero)
{
    return SkScalarNearlyZero(a.fX - b.fX, tolerance) && SkScalarNearlyZero(a.fY - b.fY, tolerance);
}

static inline bool normals_too_curvy(const SkVector& norm0, SkVector& norm1)
{
    /*  root2/2 is a 45-degree angle
        make this constant bigger for more subdivisions (but not >= 1)
    */
    static const SkScalar kFlatEnoughNormalDotProd = SK_ScalarSqrt2/2 + SK_Scalar1/10;

    SkASSERT(kFlatEnoughNormalDotProd > 0 && kFlatEnoughNormalDotProd < SK_Scalar1);

    return SkPoint::DotProduct(norm0, norm1) <= kFlatEnoughNormalDotProd;
}

static inline bool normals_too_pinchy(const SkVector& norm0, SkVector& norm1)
{
    static const SkScalar kTooPinchyNormalDotProd = -SK_Scalar1 * 999 / 1000;

    return SkPoint::DotProduct(norm0, norm1) <= kTooPinchyNormalDotProd;
}

static bool set_normal_unitnormal(const SkPoint& before, const SkPoint& after,
                                  SkScalar radius,
                                  SkVector* normal, SkVector* unitNormal)
{
    if (!unitNormal->setUnit(after.fX - before.fX, after.fY - before.fY))
        return false;

    unitNormal->rotateCCW();
    unitNormal->scale(radius, normal);
    return true;
}

static bool set_normal_unitnormal(const SkVector& vec,
                                  SkScalar radius,
                                  SkVector* normal, SkVector* unitNormal)
{
    if (!unitNormal->setUnit(vec.fX, vec.fY))
        return false;

    unitNormal->rotateCCW();
    unitNormal->scale(radius, normal);
    return true;
}

//////////////////////////////////////////////////////////////////////////////////////////

class SkPathStroker {
public:
    SkPathStroker(SkScalar radius, SkScalar miterLimit, SkPaint::Cap cap, SkPaint::Join join);

    void    moveTo(const SkPoint&);
    void    lineTo(const SkPoint&);
    void    quadTo(const SkPoint&, const SkPoint&);
    void    cubicTo(const SkPoint&, const SkPoint&, const SkPoint&);
    void    close(bool isLine) { this->finishContour(true, isLine); }

    void    done(SkPath* dst, bool isLine)
    {
        this->finishContour(false, isLine);
        fOuter.addPath(fExtra);
        dst->swap(fOuter);
    }

private:
    SkScalar    fRadius;
    SkScalar    fInvMiterLimit;

    SkVector    fFirstNormal, fPrevNormal, fFirstUnitNormal, fPrevUnitNormal;
    SkPoint     fFirstPt, fPrevPt;  // on original path
    SkPoint     fFirstOuterPt;
    int         fSegmentCount;
    bool        fPrevIsLine;

    SkStrokerPriv::CapProc  fCapper;
    SkStrokerPriv::JoinProc fJoiner;

    SkPath  fInner, fOuter; // outer is our working answer, inner is temp
    SkPath  fExtra;         // added as extra complete contours

    void    finishContour(bool close, bool isLine);
    void    preJoinTo(const SkPoint&, SkVector* normal, SkVector* unitNormal, bool isLine);
    void    postJoinTo(const SkPoint&, const SkVector& normal, const SkVector& unitNormal);

    void    line_to(const SkPoint& currPt, const SkVector& normal);
    void    quad_to(const SkPoint pts[3],
                    const SkVector& normalAB, const SkVector& unitNormalAB,
                    SkVector* normalBC, SkVector* unitNormalBC,
                    int subDivide);
    void    cubic_to(const SkPoint pts[4],
                    const SkVector& normalAB, const SkVector& unitNormalAB,
                    SkVector* normalCD, SkVector* unitNormalCD,
                    int subDivide);
};

////////////////////////////////////////////////////////////////////////////

void SkPathStroker::preJoinTo(const SkPoint& currPt, SkVector* normal, SkVector* unitNormal, bool currIsLine)
{
    SkASSERT(fSegmentCount >= 0);

    SkScalar    prevX = fPrevPt.fX;
    SkScalar    prevY = fPrevPt.fY;

    SkAssertResult(set_normal_unitnormal(fPrevPt, currPt, fRadius, normal, unitNormal));

    if (fSegmentCount == 0)
    {
        fFirstNormal = *normal;
        fFirstUnitNormal = *unitNormal;
        fFirstOuterPt.set(prevX + normal->fX, prevY + normal->fY);

        fOuter.moveTo(fFirstOuterPt.fX, fFirstOuterPt.fY);
        fInner.moveTo(prevX - normal->fX, prevY - normal->fY);
    }
    else    // we have a previous segment
    {
        fJoiner(&fOuter, &fInner, fPrevUnitNormal, fPrevPt, *unitNormal, fRadius, fInvMiterLimit,
                fPrevIsLine, currIsLine);
    }
    fPrevIsLine = currIsLine;
}

void SkPathStroker::postJoinTo(const SkPoint& currPt, const SkVector& normal, const SkVector& unitNormal)
{
    fPrevPt = currPt;
    fPrevUnitNormal = unitNormal;
    fPrevNormal = normal;
    fSegmentCount += 1;
}

void SkPathStroker::finishContour(bool close, bool currIsLine)
{
    if (fSegmentCount > 0)
    {
        SkPoint pt;

        if (close)
        {
            fJoiner(&fOuter, &fInner, fPrevUnitNormal, fPrevPt, fFirstUnitNormal,
                    fRadius, fInvMiterLimit, fPrevIsLine, currIsLine);
            fOuter.close();
            // now add fInner as its own contour
            fInner.getLastPt(&pt);
            fOuter.moveTo(pt.fX, pt.fY);
            fOuter.reversePathTo(fInner);
            fOuter.close();
        }
        else    // add caps to start and end
        {
            // cap the end
            fInner.getLastPt(&pt);
            fCapper(&fOuter, fPrevPt, fPrevNormal, pt, currIsLine ? &fInner : nil);
            fOuter.reversePathTo(fInner);
            // cap the start
            fCapper(&fOuter, fFirstPt, -fFirstNormal, fFirstOuterPt, fPrevIsLine ? &fInner : nil);
            fOuter.close();
        }
    }
    fInner.reset();
    fSegmentCount = -1;
}

////////////////////////////////////////////////////////////////////////////

SkPathStroker::SkPathStroker(SkScalar radius, SkScalar miterLimit, SkPaint::Cap cap, SkPaint::Join join)
    : fRadius(radius)
{
    if (join == SkPaint::kMiter_Join)
    {
        if (miterLimit <= SK_Scalar1)
            join = SkPaint::kBevel_Join;
        else
            fInvMiterLimit = SkScalarInvert(miterLimit);
    }
    fCapper = SkStrokerPriv::CapFactory(cap);
    fJoiner = SkStrokerPriv::JoinFactory(join);
    fSegmentCount = -1;
    fPrevIsLine = false;
}

void SkPathStroker::moveTo(const SkPoint& pt)
{
    if (fSegmentCount > 0)
        this->finishContour(false, false);

    fSegmentCount = 0;
    fFirstPt = fPrevPt = pt;
}

void SkPathStroker::line_to(const SkPoint& currPt, const SkVector& normal)
{
    fOuter.lineTo(currPt.fX + normal.fX, currPt.fY + normal.fY);
    fInner.lineTo(currPt.fX - normal.fX, currPt.fY - normal.fY);
}

void SkPathStroker::lineTo(const SkPoint& currPt)
{
    if (degenerate_line(fPrevPt, currPt))
        return;

    SkVector    normal, unitNormal;

    this->preJoinTo(currPt, &normal, &unitNormal, true);
    this->line_to(currPt, normal);
    this->postJoinTo(currPt, normal, unitNormal);
}

void SkPathStroker::quad_to(const SkPoint pts[3],
                      const SkVector& normalAB, const SkVector& unitNormalAB,
                      SkVector* normalBC, SkVector* unitNormalBC,
                      int subDivide)
{
    if (!set_normal_unitnormal(pts[1], pts[2], fRadius, normalBC, unitNormalBC))
    {
        // pts[1] nearly equals pts[2], so just draw a line to pts[2]
        this->line_to(pts[2], normalAB);
        *normalBC = normalAB;
        *unitNormalBC = unitNormalAB;
        return;
    }

    if (--subDivide >= 0 && normals_too_curvy(unitNormalAB, *unitNormalBC))
    {
        SkPoint     tmp[5];
        SkVector    norm, unit;

        SkChopQuadAtHalf(pts, tmp);
        this->quad_to(&tmp[0], normalAB, unitNormalAB, &norm, &unit, subDivide);
        this->quad_to(&tmp[2], norm, unit, normalBC, unitNormalBC, subDivide);
    }
    else
    {
        SkVector    normalB, unitB;
        SkAssertResult(set_normal_unitnormal(pts[0], pts[2], fRadius, &normalB, &unitB));

        fOuter.quadTo(  pts[1].fX + normalB.fX, pts[1].fY + normalB.fY,
                        pts[2].fX + normalBC->fX, pts[2].fY + normalBC->fY);
        fInner.quadTo(  pts[1].fX - normalB.fX, pts[1].fY - normalB.fY,
                        pts[2].fX - normalBC->fX, pts[2].fY - normalBC->fY);
    }
}

void SkPathStroker::cubic_to(const SkPoint pts[4],
                      const SkVector& normalAB, const SkVector& unitNormalAB,
                      SkVector* normalCD, SkVector* unitNormalCD,
                      int subDivide)
{
    SkVector    ab = pts[1] - pts[0];
    SkVector    cd = pts[3] - pts[2];
    SkVector    normalBC, unitNormalBC;

    bool    degenerateAB = degenerate_vector(ab);
    bool    degenerateCD = degenerate_vector(cd);

    if (degenerateAB && degenerateCD)
    {
DRAW_LINE:
        this->line_to(pts[3], normalAB);
        *normalCD = normalAB;
        *unitNormalCD = unitNormalAB;
        return;
    }

    if (degenerateAB)
    {
        ab = pts[2] - pts[0];
        degenerateAB = degenerate_vector(ab);
    }
    if (degenerateCD)
    {
        cd = pts[3] - pts[1];
        degenerateCD = degenerate_vector(cd);
    }
    if (degenerateAB || degenerateCD)
        goto DRAW_LINE;

    SkAssertResult(set_normal_unitnormal(cd, fRadius, normalCD, unitNormalCD));
    bool degenerateBC = !set_normal_unitnormal(pts[1], pts[2], fRadius, &normalBC, &unitNormalBC);

    if (--subDivide >= 0 &&
        (degenerateBC || normals_too_curvy(unitNormalAB, unitNormalBC) || normals_too_curvy(unitNormalBC, *unitNormalCD)))
    {
        SkPoint     tmp[7];
        SkVector    norm, unit, dummy, unitDummy;

        SkChopCubicAtHalf(pts, tmp);
        this->cubic_to(&tmp[0], normalAB, unitNormalAB, &norm, &unit, subDivide);
        // we use dummys since we already have a valid (and more accurate) normals for CD
        this->cubic_to(&tmp[3], norm, unit, &dummy, &unitDummy, subDivide);
    }
    else
    {
        SkVector    normalB, normalC;
        
        // need normals to inset/outset the off-curve pts B and C

        if (0)// this is normal to the line between our adjacent pts
        {
            normalB = pts[2] - pts[0];
            normalB.rotateCCW();
            SkAssertResult(normalB.setLength(fRadius));

            normalC = pts[3] - pts[1];
            normalC.rotateCCW();
            SkAssertResult(normalC.setLength(fRadius));
        }
        else    // miter-join
        {
            SkVector    unitBC = pts[2] - pts[1];
            unitBC.normalize();
            unitBC.rotateCCW();

            normalB = unitNormalAB + unitBC;
            normalC = *unitNormalCD + unitBC;

            SkScalar dot = SkPoint::DotProduct(unitNormalAB, unitBC);
            SkAssertResult(normalB.setLength(SkScalarDiv(fRadius, SkScalarSqrt((SK_Scalar1 + dot)/2))));
            dot = SkPoint::DotProduct(*unitNormalCD, unitBC);
            SkAssertResult(normalC.setLength(SkScalarDiv(fRadius, SkScalarSqrt((SK_Scalar1 + dot)/2))));
        }

        fOuter.cubicTo( pts[1].fX + normalB.fX, pts[1].fY + normalB.fY,
                        pts[2].fX + normalC.fX, pts[2].fY + normalC.fY,
                        pts[3].fX + normalCD->fX, pts[3].fY + normalCD->fY);

        fInner.cubicTo( pts[1].fX - normalB.fX, pts[1].fY - normalB.fY,
                        pts[2].fX - normalC.fX, pts[2].fY - normalC.fY,
                        pts[3].fX - normalCD->fX, pts[3].fY - normalCD->fY);
    }
}

void SkPathStroker::quadTo(const SkPoint& pt1, const SkPoint& pt2)
{
    bool    degenerateAB = degenerate_line(fPrevPt, pt1);
    bool    degenerateBC = degenerate_line(pt1, pt2);

    if (degenerateAB | degenerateBC)
    {
        if (degenerateAB ^ degenerateBC)
            this->lineTo(pt2);
        return;
    }

    SkVector    normalAB, unitAB, normalBC, unitBC;

    this->preJoinTo(pt1, &normalAB, &unitAB, false);

    {
        SkPoint pts[3], tmp[5];
        pts[0] = fPrevPt;
        pts[1] = pt1;
        pts[2] = pt2;

        if (SkChopQuadAtMaxCurvature(pts, tmp) == 2)
        {
            unitBC.setUnit(pts[2].fX - pts[1].fX, pts[2].fY - pts[1].fY);
            unitBC.rotateCCW();
            if (normals_too_pinchy(unitAB, unitBC))
            {
                normalBC = unitBC;
                normalBC.scale(fRadius);

                fOuter.lineTo(tmp[2].fX + normalAB.fX, tmp[2].fY + normalAB.fY);
                fOuter.lineTo(tmp[2].fX + normalBC.fX, tmp[2].fY + normalBC.fY);
                fOuter.lineTo(tmp[4].fX + normalBC.fX, tmp[4].fY + normalBC.fY);

                fInner.lineTo(tmp[2].fX - normalAB.fX, tmp[2].fY - normalAB.fY);
                fInner.lineTo(tmp[2].fX - normalBC.fX, tmp[2].fY - normalBC.fY);
                fInner.lineTo(tmp[4].fX - normalBC.fX, tmp[4].fY - normalBC.fY);

                fExtra.addCircle(tmp[2].fX, tmp[2].fY, fRadius, SkPath::kCW_Direction);
            }
            else
            {
                this->quad_to(&tmp[0], normalAB, unitAB, &normalBC, &unitBC, kMaxQuadSubdivide);
                SkVector n = normalBC;
                SkVector u = unitBC;
                this->quad_to(&tmp[2], n, u, &normalBC, &unitBC, kMaxQuadSubdivide);
            }
        }
        else
            this->quad_to(pts, normalAB, unitAB, &normalBC, &unitBC, kMaxQuadSubdivide);
    }

    this->postJoinTo(pt2, normalBC, unitBC);
}

void SkPathStroker::cubicTo(const SkPoint& pt1, const SkPoint& pt2, const SkPoint& pt3)
{
    bool    degenerateAB = degenerate_line(fPrevPt, pt1);
    bool    degenerateBC = degenerate_line(pt1, pt2);
    bool    degenerateCD = degenerate_line(pt2, pt3);

    if (degenerateAB + degenerateBC + degenerateCD >= 2)
    {
        this->lineTo(pt3);
        return;
    }

    SkVector    normalAB, unitAB, normalCD, unitCD;

    // find the first tangent (which might be pt1 or pt2
    {
        const SkPoint*  nextPt = &pt1;
        if (degenerateAB)
            nextPt = &pt2;
        this->preJoinTo(*nextPt, &normalAB, &unitAB, false);
    }

    {
        SkPoint pts[4], tmp[13];
        int         i, count;
        SkVector    n, u;
        SkScalar    tValues[3];

        pts[0] = fPrevPt;
        pts[1] = pt1;
        pts[2] = pt2;
        pts[3] = pt3;

#if 1
        count = SkChopCubicAtMaxCurvature(pts, tmp, tValues);
#else
        count = 1;
        memcpy(tmp, pts, 4 * sizeof(SkPoint));
#endif
        n = normalAB;
        u = unitAB;
        for (i = 0; i < count; i++)
        {
            this->cubic_to(&tmp[i * 3], n, u, &normalCD, &unitCD, kMaxCubicSubdivide);
            if (i == count - 1)
                break;
            n = normalCD;
            u = unitCD;

        }

        // check for too pinchy
        for (i = 1; i < count; i++)
        {
            SkPoint p;
            SkVector    v, c;

            SkEvalCubicAt(pts, tValues[i - 1], &p, &v, &c);

            SkScalar    dot = SkPoint::DotProduct(c, c);
            v.scale(SkScalarInvert(dot));

            if (SkScalarNearlyZero(v.fX) && SkScalarNearlyZero(v.fY))
            {
                fExtra.addCircle(p.fX, p.fY, fRadius, SkPath::kCW_Direction);
            }
        }

    }

    this->postJoinTo(pt3, normalCD, unitCD);
}

/////////////////////////////////////////////////////////////////////////////////
/////////////////////////////////////////////////////////////////////////////////

#include "SkPaint.h"

SkStroke::SkStroke()
{
    fWidth      = SK_DefaultStrokeWidth;
    fMiterLimit = SK_DefaultMiterLimit;
    fCap        = SkPaint::kDefault_Cap;
    fJoin       = SkPaint::kDefault_Join;
    fDoFill     = false;
}

SkStroke::SkStroke(const SkPaint& p)
{
    fWidth      = p.getStrokeWidth();
    fMiterLimit = p.getStrokeMiter();
    fCap        = (U8)p.getStrokeCap();
    fJoin       = (U8)p.getStrokeJoin();
    fDoFill     = SkToU8(p.getStyle() == SkPaint::kStrokeAndFill_Style);
}

SkStroke::SkStroke(const SkPaint& p, SkScalar width)
{
    fWidth      = width;
    fMiterLimit = p.getStrokeMiter();
    fCap        = (U8)p.getStrokeCap();
    fJoin       = (U8)p.getStrokeJoin();
    fDoFill     = SkToU8(p.getStyle() == SkPaint::kStrokeAndFill_Style);
}

void SkStroke::setWidth(SkScalar width)
{
    SkASSERT(width >= 0);
    fWidth = width;
}

void SkStroke::setMiterLimit(SkScalar miterLimit)
{
    SkASSERT(miterLimit >= 0);
    fMiterLimit = miterLimit;
}

void SkStroke::setCap(SkPaint::Cap cap)
{
    SkASSERT((unsigned)cap < SkPaint::kCapCount);
    fCap = SkToU8(cap);
}

void SkStroke::setJoin(SkPaint::Join join)
{
    SkASSERT((unsigned)join < SkPaint::kJoinCount);
    fJoin = SkToU8(join);
}

void SkStroke::strokePath(const SkPath& src, SkPath* dst) const
{
    SkASSERT(&src != nil && dst != nil);

    dst->reset();
    if (SkScalarHalf(fWidth) <= 0)
        return;

    SkPathStroker   stroker(SkScalarHalf(fWidth), fMiterLimit, this->getCap(), this->getJoin());

    SkPath::Iter    iter(src, false);
    SkPoint         pts[4];
    SkPath::Verb    verb, lastSegment = SkPath::kMove_Verb;

    while ((verb = iter.next(pts)) != SkPath::kDone_Verb)
    {
        switch (verb) {
        case SkPath::kMove_Verb:
            stroker.moveTo(pts[0]);
            break;
        case SkPath::kLine_Verb:
            stroker.lineTo(pts[1]);
            lastSegment = verb;
            break;
        case SkPath::kQuad_Verb:
            stroker.quadTo(pts[1], pts[2]);
            lastSegment = verb;
            break;
        case SkPath::kCubic_Verb:
            stroker.cubicTo(pts[1], pts[2], pts[3]);
            lastSegment = verb;
            break;
        case SkPath::kClose_Verb:
            stroker.close(lastSegment == SkPath::kLine_Verb);
            break;
        default:
            break;
        }
    }
    stroker.done(dst, lastSegment == SkPath::kLine_Verb);

    if (fDoFill)
        dst->addPath(src);
}

void SkStroke::strokeLine(const SkPoint& p0, const SkPoint& p1, SkPath* dst) const
{
    SkPath  tmp;

    tmp.moveTo(p0);
    tmp.lineTo(p1);
    this->strokePath(tmp, dst);
}