/* * Copyright 2008 The Android Open Source Project * * Use of this source code is governed by a BSD-style license that can be * found in the LICENSE file. */ #include "SkStrokerPriv.h" #include "SkGeometry.h" #include "SkPath.h" #ifdef SK_QUAD_STROKE_APPROXIMATION enum { kTangent_RecursiveLimit, kCubic_RecursiveLimit, kConic_RecursiveLimit, kQuad_RecursiveLimit }; // quads with extreme widths (e.g. (0,1) (1,6) (0,3) width=5e7) recurse to point of failure // largest seen for normal cubics : 5, 26 // largest seen for normal quads : 11 static const int kRecursiveLimits[] = { 5*3, 26*3, 11*3, 11*3 }; // 3x limits seen in practice SK_COMPILE_ASSERT(0 == kTangent_RecursiveLimit, cubic_stroke_relies_on_tangent_equalling_zero); SK_COMPILE_ASSERT(1 == kCubic_RecursiveLimit, cubic_stroke_relies_on_cubic_equalling_one); SK_COMPILE_ASSERT(SK_ARRAY_COUNT(kRecursiveLimits) == kQuad_RecursiveLimit + 1, recursive_limits_mismatch); #ifdef SK_DEBUG int gMaxRecursion[SK_ARRAY_COUNT(kRecursiveLimits)] = { 0 }; #endif #ifndef DEBUG_QUAD_STROKER #define DEBUG_QUAD_STROKER 0 #endif #if DEBUG_QUAD_STROKER /* Enable to show the decisions made in subdividing the curve -- helpful when the resulting stroke has more than the optimal number of quadratics and lines */ #define STROKER_RESULT(resultType, depth, quadPts, format, ...) \ SkDebugf("[%d] %s " format "\n", depth, __FUNCTION__, __VA_ARGS__), \ SkDebugf(" " #resultType " t=(%g,%g)\n", quadPts->fStartT, quadPts->fEndT), \ resultType #define STROKER_DEBUG_PARAMS(...) , __VA_ARGS__ #else #define STROKER_RESULT(resultType, depth, quadPts, format, ...) \ resultType #define STROKER_DEBUG_PARAMS(...) #endif #endif #ifndef SK_QUAD_STROKE_APPROXIMATION #define kMaxQuadSubdivide 5 #define kMaxCubicSubdivide 7 #endif static inline bool degenerate_vector(const SkVector& v) { return !SkPoint::CanNormalize(v.fX, v.fY); } #ifndef SK_QUAD_STROKE_APPROXIMATION 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) { // if the dot-product is -1, then we are definitely too pinchy. We tweak // that by an epsilon to ensure we have significant bits in our test static const int kMinSigBitsForDot = 8; static const SkScalar kDotEpsilon = FLT_EPSILON * (1 << kMinSigBitsForDot); static const SkScalar kTooPinchyNormalDotProd = kDotEpsilon - 1; // just some sanity asserts to help document the expected range SkASSERT(kTooPinchyNormalDotProd >= -1); SkASSERT(kTooPinchyNormalDotProd < SkDoubleToScalar(-0.999)); SkScalar dot = SkPoint::DotProduct(norm0, norm1); return dot <= kTooPinchyNormalDotProd; } #endif static bool set_normal_unitnormal(const SkPoint& before, const SkPoint& after, SkScalar radius, SkVector* normal, SkVector* unitNormal) { if (!unitNormal->setNormalize(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->setNormalize(vec.fX, vec.fY)) { return false; } unitNormal->rotateCCW(); unitNormal->scale(radius, normal); return true; } /////////////////////////////////////////////////////////////////////////////// #ifdef SK_QUAD_STROKE_APPROXIMATION struct SkQuadConstruct { // The state of the quad stroke under construction. SkPoint fQuad[3]; // the stroked quad parallel to the original curve SkPoint fTangentStart; // a point tangent to fQuad[0] SkPoint fTangentEnd; // a point tangent to fQuad[2] SkScalar fStartT; // a segment of the original curve SkScalar fMidT; // " SkScalar fEndT; // " bool fStartSet; // state to share common points across structs bool fEndSet; // " // return false if start and end are too close to have a unique middle bool init(SkScalar start, SkScalar end) { fStartT = start; fMidT = (start + end) * SK_ScalarHalf; fEndT = end; fStartSet = fEndSet = false; return fStartT < fMidT && fMidT < fEndT; } bool initWithStart(SkQuadConstruct* parent) { if (!init(parent->fStartT, parent->fMidT)) { return false; } fQuad[0] = parent->fQuad[0]; fTangentStart = parent->fTangentStart; fStartSet = true; return true; } bool initWithEnd(SkQuadConstruct* parent) { if (!init(parent->fMidT, parent->fEndT)) { return false; } fQuad[2] = parent->fQuad[2]; fTangentEnd = parent->fTangentEnd; fEndSet = true; return true; } }; #endif class SkPathStroker { public: SkPathStroker(const SkPath& src, SkScalar radius, SkScalar miterLimit, SkPaint::Cap, SkPaint::Join, SkScalar resScale); void moveTo(const SkPoint&); void lineTo(const SkPoint&); void quadTo(const SkPoint&, const SkPoint&); #ifdef SK_QUAD_STROKE_APPROXIMATION void conicTo(const SkPoint&, const SkPoint&, SkScalar weight); #endif 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); } SkScalar getResScale() const { return fResScale; } private: SkScalar fRadius; SkScalar fInvMiterLimit; SkScalar fResScale; #ifdef SK_QUAD_STROKE_APPROXIMATION SkScalar fInvResScale; SkScalar fInvResScaleSquared; #endif 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 #ifdef SK_QUAD_STROKE_APPROXIMATION enum StrokeType { kOuter_StrokeType = 1, // use sign-opposite values later to flip perpendicular axis kInner_StrokeType = -1 } fStrokeType; enum ResultType { kSplit_ResultType, // the caller should split the quad stroke in two kDegenerate_ResultType, // the caller should add a line kQuad_ResultType, // the caller should (continue to try to) add a quad stroke kNormalError_ResultType, // the cubic's normal couldn't be computed -- abort }; enum ReductionType { kPoint_ReductionType, // all curve points are practically identical kLine_ReductionType, // the control point is on the line between the ends kQuad_ReductionType, // the control point is outside the line between the ends kDegenerate_ReductionType, // the control point is on the line but outside the ends kDegenerate2_ReductionType, // two control points are on the line but outside ends (cubic) kDegenerate3_ReductionType, // three areas of max curvature found (for cubic) }; enum IntersectRayType { kCtrlPt_RayType, kResultType_RayType, }; int fRecursionDepth; // track stack depth to abort if numerics run amok bool fFoundTangents; // do less work until tangents meet (cubic) void addDegenerateLine(const SkQuadConstruct* ); ReductionType CheckConicLinear(const SkConic& , SkPoint* reduction); ReductionType CheckCubicLinear(const SkPoint cubic[4], SkPoint reduction[3], const SkPoint** tanPtPtr); ReductionType CheckQuadLinear(const SkPoint quad[3], SkPoint* reduction); ResultType compareQuadConic(const SkConic& , SkQuadConstruct* ); ResultType compareQuadCubic(const SkPoint cubic[4], SkQuadConstruct* ); ResultType compareQuadQuad(const SkPoint quad[3], SkQuadConstruct* ); bool conicPerpRay(const SkConic& , SkScalar t, SkPoint* tPt, SkPoint* onPt, SkPoint* tangent) const; bool conicQuadEnds(const SkConic& , SkQuadConstruct* ); bool conicStroke(const SkConic& , SkQuadConstruct* ); bool cubicMidOnLine(const SkPoint cubic[4], const SkQuadConstruct* ) const; bool cubicPerpRay(const SkPoint cubic[4], SkScalar t, SkPoint* tPt, SkPoint* onPt, SkPoint* tangent) const; bool cubicQuadEnds(const SkPoint cubic[4], SkQuadConstruct* ); bool cubicQuadMid(const SkPoint cubic[4], const SkQuadConstruct* , SkPoint* mid) const; bool cubicStroke(const SkPoint cubic[4], SkQuadConstruct* ); void init(StrokeType strokeType, SkQuadConstruct* , SkScalar tStart, SkScalar tEnd); ResultType intersectRay(SkQuadConstruct* , IntersectRayType STROKER_DEBUG_PARAMS(int) ) const; bool ptInQuadBounds(const SkPoint quad[3], const SkPoint& pt) const; void quadPerpRay(const SkPoint quad[3], SkScalar t, SkPoint* tPt, SkPoint* onPt, SkPoint* tangent) const; bool quadStroke(const SkPoint quad[3], SkQuadConstruct* ); void setConicEndNormal(const SkConic& , const SkVector& normalAB, const SkVector& unitNormalAB, SkVector* normalBC, SkVector* unitNormalBC); void setCubicEndNormal(const SkPoint cubic[4], const SkVector& normalAB, const SkVector& unitNormalAB, SkVector* normalCD, SkVector* unitNormalCD); void setQuadEndNormal(const SkPoint quad[3], const SkVector& normalAB, const SkVector& unitNormalAB, SkVector* normalBC, SkVector* unitNormalBC); void setRayPts(const SkPoint& tPt, SkVector* dxy, SkPoint* onPt, SkPoint* tangent) const; static bool SlightAngle(SkQuadConstruct* ); ResultType strokeCloseEnough(const SkPoint stroke[3], const SkPoint ray[2], SkQuadConstruct* STROKER_DEBUG_PARAMS(int depth) ) const; ResultType tangentsMeet(const SkPoint cubic[4], SkQuadConstruct* ); #endif 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); #ifndef SK_QUAD_STROKE_APPROXIMATION 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); #endif }; /////////////////////////////////////////////////////////////////////////////// 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 : NULL); fOuter.reversePathTo(fInner); // cap the start fCapper(&fOuter, fFirstPt, -fFirstNormal, fFirstOuterPt, fPrevIsLine ? &fInner : NULL); fOuter.close(); } } // since we may re-use fInner, we rewind instead of reset, to save on // reallocating its internal storage. fInner.rewind(); fSegmentCount = -1; } /////////////////////////////////////////////////////////////////////////////// SkPathStroker::SkPathStroker(const SkPath& src, SkScalar radius, SkScalar miterLimit, SkPaint::Cap cap, SkPaint::Join join, SkScalar resScale) : fRadius(radius) , fResScale(resScale) { /* This is only used when join is miter_join, but we initialize it here so that it is always defined, to fis valgrind warnings. */ fInvMiterLimit = 0; 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; // Need some estimate of how large our final result (fOuter) // and our per-contour temp (fInner) will be, so we don't spend // extra time repeatedly growing these arrays. // // 3x for result == inner + outer + join (swag) // 1x for inner == 'wag' (worst contour length would be better guess) fOuter.incReserve(src.countPoints() * 3); fOuter.setIsVolatile(true); fInner.incReserve(src.countPoints()); fInner.setIsVolatile(true); #ifdef SK_QUAD_STROKE_APPROXIMATION // TODO : write a common error function used by stroking and filling // The '4' below matches the fill scan converter's error term fInvResScale = SkScalarInvert(resScale * 4); fInvResScaleSquared = fInvResScale * fInvResScale; fRecursionDepth = 0; #endif } 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 (SkPath::IsLineDegenerate(fPrevPt, currPt)) { return; } SkVector normal, unitNormal; this->preJoinTo(currPt, &normal, &unitNormal, true); this->line_to(currPt, normal); this->postJoinTo(currPt, normal, unitNormal); } #ifndef SK_QUAD_STROKE_APPROXIMATION 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; normalB = pts[2] - pts[0]; normalB.rotateCCW(); SkScalar dot = SkPoint::DotProduct(unitNormalAB, *unitNormalBC); SkAssertResult(normalB.setLength(SkScalarDiv(fRadius, SkScalarSqrt((SK_Scalar1 + dot)/2)))); 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); } } #endif #ifdef SK_QUAD_STROKE_APPROXIMATION void SkPathStroker::setQuadEndNormal(const SkPoint quad[3], const SkVector& normalAB, const SkVector& unitNormalAB, SkVector* normalBC, SkVector* unitNormalBC) { if (!set_normal_unitnormal(quad[1], quad[2], fRadius, normalBC, unitNormalBC)) { *normalBC = normalAB; *unitNormalBC = unitNormalAB; } } void SkPathStroker::setConicEndNormal(const SkConic& conic, const SkVector& normalAB, const SkVector& unitNormalAB, SkVector* normalBC, SkVector* unitNormalBC) { setQuadEndNormal(conic.fPts, normalAB, unitNormalAB, normalBC, unitNormalBC); } void SkPathStroker::setCubicEndNormal(const SkPoint cubic[4], const SkVector& normalAB, const SkVector& unitNormalAB, SkVector* normalCD, SkVector* unitNormalCD) { SkVector ab = cubic[1] - cubic[0]; SkVector cd = cubic[3] - cubic[2]; bool degenerateAB = degenerate_vector(ab); bool degenerateCD = degenerate_vector(cd); if (degenerateAB && degenerateCD) { goto DEGENERATE_NORMAL; } if (degenerateAB) { ab = cubic[2] - cubic[0]; degenerateAB = degenerate_vector(ab); } if (degenerateCD) { cd = cubic[3] - cubic[1]; degenerateCD = degenerate_vector(cd); } if (degenerateAB || degenerateCD) { DEGENERATE_NORMAL: *normalCD = normalAB; *unitNormalCD = unitNormalAB; return; } SkAssertResult(set_normal_unitnormal(cd, fRadius, normalCD, unitNormalCD)); } void SkPathStroker::init(StrokeType strokeType, SkQuadConstruct* quadPts, SkScalar tStart, SkScalar tEnd) { fStrokeType = strokeType; fFoundTangents = false; quadPts->init(tStart, tEnd); } // returns the distance squared from the point to the line static SkScalar pt_to_line(const SkPoint& pt, const SkPoint& lineStart, const SkPoint& lineEnd) { SkVector dxy = lineEnd - lineStart; if (degenerate_vector(dxy)) { return pt.distanceToSqd(lineStart); } SkVector ab0 = pt - lineStart; SkScalar numer = dxy.dot(ab0); SkScalar denom = dxy.dot(dxy); SkScalar t = numer / denom; SkPoint hit; hit.fX = lineStart.fX * (1 - t) + lineEnd.fX * t; hit.fY = lineStart.fY * (1 - t) + lineEnd.fY * t; return hit.distanceToSqd(pt); } /* Given a cubic, determine if all four points are in a line. Return true if the inner points is close to a line connecting the outermost points. Find the outermost point by looking for the largest difference in X or Y. Given the indices of the outermost points, and that outer_1 is greater than outer_2, this table shows the index of the smaller of the remaining points: outer_2 0 1 2 3 outer_1 ---------------- 0 | - 2 1 1 1 | - - 0 0 2 | - - - 0 3 | - - - - If outer_1 == 0 and outer_2 == 1, the smaller of the remaining indices (2 and 3) is 2. This table can be collapsed to: (1 + (2 >> outer_2)) >> outer_1 Given three indices (outer_1 outer_2 mid_1) from 0..3, the remaining index is: mid_2 == (outer_1 ^ outer_2 ^ mid_1) */ static bool cubic_in_line(const SkPoint cubic[4]) { SkScalar ptMax = -1; int outer1 SK_INIT_TO_AVOID_WARNING; int outer2 SK_INIT_TO_AVOID_WARNING; for (int index = 0; index < 3; ++index) { for (int inner = index + 1; inner < 4; ++inner) { SkVector testDiff = cubic[inner] - cubic[index]; SkScalar testMax = SkTMax(SkScalarAbs(testDiff.fX), SkScalarAbs(testDiff.fY)); if (ptMax < testMax) { outer1 = index; outer2 = inner; ptMax = testMax; } } } SkASSERT(outer1 >= 0 && outer1 <= 2); SkASSERT(outer2 >= 1 && outer2 <= 3); SkASSERT(outer1 < outer2); int mid1 = (1 + (2 >> outer2)) >> outer1; SkASSERT(mid1 >= 0 && mid1 <= 2); SkASSERT(outer1 != mid1 && outer2 != mid1); int mid2 = outer1 ^ outer2 ^ mid1; SkASSERT(mid2 >= 1 && mid2 <= 3); SkASSERT(mid2 != outer1 && mid2 != outer2 && mid2 != mid1); SkASSERT(((1 << outer1) | (1 << outer2) | (1 << mid1) | (1 << mid2)) == 0x0f); SkScalar lineSlop = ptMax * ptMax * 0.00001f; // this multiplier is pulled out of the air return pt_to_line(cubic[mid1], cubic[outer1], cubic[outer2]) <= lineSlop && pt_to_line(cubic[mid2], cubic[outer1], cubic[outer2]) <= lineSlop; } /* Given quad, see if all there points are in a line. Return true if the inside point is close to a line connecting the outermost points. Find the outermost point by looking for the largest difference in X or Y. Since the XOR of the indices is 3 (0 ^ 1 ^ 2) the missing index equals: outer_1 ^ outer_2 ^ 3 */ static bool quad_in_line(const SkPoint quad[3]) { SkScalar ptMax = -1; int outer1 SK_INIT_TO_AVOID_WARNING; int outer2 SK_INIT_TO_AVOID_WARNING; for (int index = 0; index < 2; ++index) { for (int inner = index + 1; inner < 3; ++inner) { SkVector testDiff = quad[inner] - quad[index]; SkScalar testMax = SkTMax(SkScalarAbs(testDiff.fX), SkScalarAbs(testDiff.fY)); if (ptMax < testMax) { outer1 = index; outer2 = inner; ptMax = testMax; } } } SkASSERT(outer1 >= 0 && outer1 <= 1); SkASSERT(outer2 >= 1 && outer2 <= 2); SkASSERT(outer1 < outer2); int mid = outer1 ^ outer2 ^ 3; SkScalar lineSlop = ptMax * ptMax * 0.00001f; // this multiplier is pulled out of the air return pt_to_line(quad[mid], quad[outer1], quad[outer2]) <= lineSlop; } static bool conic_in_line(const SkConic& conic) { return quad_in_line(conic.fPts); } SkPathStroker::ReductionType SkPathStroker::CheckCubicLinear(const SkPoint cubic[4], SkPoint reduction[3], const SkPoint** tangentPtPtr) { bool degenerateAB = degenerate_vector(cubic[1] - cubic[0]); bool degenerateBC = degenerate_vector(cubic[2] - cubic[1]); bool degenerateCD = degenerate_vector(cubic[3] - cubic[2]); if (degenerateAB & degenerateBC & degenerateCD) { return kPoint_ReductionType; } if (degenerateAB + degenerateBC + degenerateCD == 2) { return kLine_ReductionType; } if (!cubic_in_line(cubic)) { *tangentPtPtr = degenerateAB ? &cubic[2] : &cubic[1]; return kQuad_ReductionType; } SkScalar tValues[3]; int count = SkFindCubicMaxCurvature(cubic, tValues); if (count == 0) { return kLine_ReductionType; } for (int index = 0; index < count; ++index) { SkScalar t = tValues[index]; SkEvalCubicAt(cubic, t, &reduction[index], NULL, NULL); } SK_COMPILE_ASSERT(kQuad_ReductionType + 1 == kDegenerate_ReductionType, enum_out_of_whack); SK_COMPILE_ASSERT(kQuad_ReductionType + 2 == kDegenerate2_ReductionType, enum_out_of_whack); SK_COMPILE_ASSERT(kQuad_ReductionType + 3 == kDegenerate3_ReductionType, enum_out_of_whack); return (ReductionType) (kQuad_ReductionType + count); } SkPathStroker::ReductionType SkPathStroker::CheckConicLinear(const SkConic& conic, SkPoint* reduction) { bool degenerateAB = degenerate_vector(conic.fPts[1] - conic.fPts[0]); bool degenerateBC = degenerate_vector(conic.fPts[2] - conic.fPts[1]); if (degenerateAB & degenerateBC) { return kPoint_ReductionType; } if (degenerateAB | degenerateBC) { return kLine_ReductionType; } if (!conic_in_line(conic)) { return kQuad_ReductionType; } SkScalar t; if (!conic.findMaxCurvature(&t) || 0 == t) { return kLine_ReductionType; } conic.evalAt(t, reduction, NULL); return kDegenerate_ReductionType; } SkPathStroker::ReductionType SkPathStroker::CheckQuadLinear(const SkPoint quad[3], SkPoint* reduction) { bool degenerateAB = degenerate_vector(quad[1] - quad[0]); bool degenerateBC = degenerate_vector(quad[2] - quad[1]); if (degenerateAB & degenerateBC) { return kPoint_ReductionType; } if (degenerateAB | degenerateBC) { return kLine_ReductionType; } if (!quad_in_line(quad)) { return kQuad_ReductionType; } SkScalar t = SkFindQuadMaxCurvature(quad); if (0 == t) { return kLine_ReductionType; } SkEvalQuadAt(quad, t, reduction, NULL); return kDegenerate_ReductionType; } #else 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); #ifndef SK_IGNORE_CUBIC_STROKE_FIX if (--subDivide < 0) { goto DRAW_LINE; } #endif if (degenerateBC || normals_too_curvy(unitNormalAB, unitNormalBC) || normals_too_curvy(unitNormalBC, *unitNormalCD)) { #ifdef SK_IGNORE_CUBIC_STROKE_FIX // subdivide if we can if (--subDivide < 0) { goto DRAW_LINE; } #endif 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 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); } } #endif #ifdef SK_QUAD_STROKE_APPROXIMATION void SkPathStroker::conicTo(const SkPoint& pt1, const SkPoint& pt2, SkScalar weight) { const SkConic conic(fPrevPt, pt1, pt2, weight); SkPoint reduction; ReductionType reductionType = CheckConicLinear(conic, &reduction); if (kPoint_ReductionType == reductionType) { return; } if (kLine_ReductionType == reductionType) { this->lineTo(pt2); return; } if (kDegenerate_ReductionType == reductionType) { this->lineTo(reduction); SkStrokerPriv::JoinProc saveJoiner = fJoiner; fJoiner = SkStrokerPriv::JoinFactory(SkPaint::kRound_Join); this->lineTo(pt2); fJoiner = saveJoiner; return; } SkASSERT(kQuad_ReductionType == reductionType); SkVector normalAB, unitAB, normalBC, unitBC; this->preJoinTo(pt1, &normalAB, &unitAB, false); SkQuadConstruct quadPts; this->init(kOuter_StrokeType, &quadPts, 0, 1); if (!this->conicStroke(conic, &quadPts)) { return; } this->init(kInner_StrokeType, &quadPts, 0, 1); if (!this->conicStroke(conic, &quadPts)) { return; } this->setConicEndNormal(conic, normalAB, unitAB, &normalBC, &unitBC); this->postJoinTo(pt2, normalBC, unitBC); } #endif void SkPathStroker::quadTo(const SkPoint& pt1, const SkPoint& pt2) { #ifdef SK_QUAD_STROKE_APPROXIMATION const SkPoint quad[3] = { fPrevPt, pt1, pt2 }; SkPoint reduction; ReductionType reductionType = CheckQuadLinear(quad, &reduction); if (kPoint_ReductionType == reductionType) { return; } if (kLine_ReductionType == reductionType) { this->lineTo(pt2); return; } if (kDegenerate_ReductionType == reductionType) { this->lineTo(reduction); SkStrokerPriv::JoinProc saveJoiner = fJoiner; fJoiner = SkStrokerPriv::JoinFactory(SkPaint::kRound_Join); this->lineTo(pt2); fJoiner = saveJoiner; return; } SkASSERT(kQuad_ReductionType == reductionType); SkVector normalAB, unitAB, normalBC, unitBC; this->preJoinTo(pt1, &normalAB, &unitAB, false); SkQuadConstruct quadPts; this->init(kOuter_StrokeType, &quadPts, 0, 1); if (!this->quadStroke(quad, &quadPts)) { return; } this->init(kInner_StrokeType, &quadPts, 0, 1); if (!this->quadStroke(quad, &quadPts)) { return; } this->setQuadEndNormal(quad, normalAB, unitAB, &normalBC, &unitBC); #else bool degenerateAB = SkPath::IsLineDegenerate(fPrevPt, pt1); bool degenerateBC = SkPath::IsLineDegenerate(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.setNormalize(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); } } #endif this->postJoinTo(pt2, normalBC, unitBC); } #ifdef SK_QUAD_STROKE_APPROXIMATION // Given a point on the curve and its derivative, scale the derivative by the radius, and // compute the perpendicular point and its tangent. void SkPathStroker::setRayPts(const SkPoint& tPt, SkVector* dxy, SkPoint* onPt, SkPoint* tangent) const { SkPoint oldDxy = *dxy; if (!dxy->setLength(fRadius)) { // consider moving double logic into SkPoint::setLength double xx = oldDxy.fX; double yy = oldDxy.fY; double dscale = fRadius / sqrt(xx * xx + yy * yy); dxy->fX = SkDoubleToScalar(xx * dscale); dxy->fY = SkDoubleToScalar(yy * dscale); } SkScalar axisFlip = SkIntToScalar(fStrokeType); // go opposite ways for outer, inner onPt->fX = tPt.fX + axisFlip * dxy->fY; onPt->fY = tPt.fY - axisFlip * dxy->fX; if (tangent) { tangent->fX = onPt->fX + dxy->fX; tangent->fY = onPt->fY + dxy->fY; } } // Given a conic and t, return the point on curve, its perpendicular, and the perpendicular tangent. // Returns false if the perpendicular could not be computed (because the derivative collapsed to 0) bool SkPathStroker::conicPerpRay(const SkConic& conic, SkScalar t, SkPoint* tPt, SkPoint* onPt, SkPoint* tangent) const { SkVector dxy; conic.evalAt(t, tPt, &dxy); if (dxy.fX == 0 && dxy.fY == 0) { dxy = conic.fPts[2] - conic.fPts[0]; } setRayPts(*tPt, &dxy, onPt, tangent); return true; } // Given a conic and a t range, find the start and end if they haven't been found already. bool SkPathStroker::conicQuadEnds(const SkConic& conic, SkQuadConstruct* quadPts) { if (!quadPts->fStartSet) { SkPoint conicStartPt; if (!this->conicPerpRay(conic, quadPts->fStartT, &conicStartPt, &quadPts->fQuad[0], &quadPts->fTangentStart)) { return false; } quadPts->fStartSet = true; } if (!quadPts->fEndSet) { SkPoint conicEndPt; if (!this->conicPerpRay(conic, quadPts->fEndT, &conicEndPt, &quadPts->fQuad[2], &quadPts->fTangentEnd)) { return false; } quadPts->fEndSet = true; } return true; } // Given a cubic and t, return the point on curve, its perpendicular, and the perpendicular tangent. // Returns false if the perpendicular could not be computed (because the derivative collapsed to 0) bool SkPathStroker::cubicPerpRay(const SkPoint cubic[4], SkScalar t, SkPoint* tPt, SkPoint* onPt, SkPoint* tangent) const { SkVector dxy; SkEvalCubicAt(cubic, t, tPt, &dxy, NULL); if (dxy.fX == 0 && dxy.fY == 0) { if (SkScalarNearlyZero(t)) { dxy = cubic[2] - cubic[0]; } else if (SkScalarNearlyZero(1 - t)) { dxy = cubic[3] - cubic[1]; } else { return false; } if (dxy.fX == 0 && dxy.fY == 0) { dxy = cubic[3] - cubic[0]; } } setRayPts(*tPt, &dxy, onPt, tangent); return true; } // Given a cubic and a t range, find the start and end if they haven't been found already. bool SkPathStroker::cubicQuadEnds(const SkPoint cubic[4], SkQuadConstruct* quadPts) { if (!quadPts->fStartSet) { SkPoint cubicStartPt; if (!this->cubicPerpRay(cubic, quadPts->fStartT, &cubicStartPt, &quadPts->fQuad[0], &quadPts->fTangentStart)) { return false; } quadPts->fStartSet = true; } if (!quadPts->fEndSet) { SkPoint cubicEndPt; if (!this->cubicPerpRay(cubic, quadPts->fEndT, &cubicEndPt, &quadPts->fQuad[2], &quadPts->fTangentEnd)) { return false; } quadPts->fEndSet = true; } return true; } bool SkPathStroker::cubicQuadMid(const SkPoint cubic[4], const SkQuadConstruct* quadPts, SkPoint* mid) const { SkPoint cubicMidPt; return this->cubicPerpRay(cubic, quadPts->fMidT, &cubicMidPt, mid, NULL); } // Given a quad and t, return the point on curve, its perpendicular, and the perpendicular tangent. void SkPathStroker::quadPerpRay(const SkPoint quad[3], SkScalar t, SkPoint* tPt, SkPoint* onPt, SkPoint* tangent) const { SkVector dxy; SkEvalQuadAt(quad, t, tPt, &dxy); if (dxy.fX == 0 && dxy.fY == 0) { dxy = quad[2] - quad[0]; } setRayPts(*tPt, &dxy, onPt, tangent); } // Find the intersection of the stroke tangents to construct a stroke quad. // Return whether the stroke is a degenerate (a line), a quad, or must be split. // Optionally compute the quad's control point. SkPathStroker::ResultType SkPathStroker::intersectRay(SkQuadConstruct* quadPts, IntersectRayType intersectRayType STROKER_DEBUG_PARAMS(int depth)) const { const SkPoint& start = quadPts->fQuad[0]; const SkPoint& end = quadPts->fQuad[2]; SkVector aLen = quadPts->fTangentStart - start; SkVector bLen = quadPts->fTangentEnd - end; SkScalar denom = aLen.cross(bLen); SkVector ab0 = start - end; SkScalar numerA = bLen.cross(ab0); SkScalar numerB = aLen.cross(ab0); if (!SkScalarNearlyZero(denom)) { // if the perpendicular distances from the quad points to the opposite tangent line // are small, a straight line is good enough SkScalar dist1 = pt_to_line(start, end, quadPts->fTangentEnd); SkScalar dist2 = pt_to_line(end, start, quadPts->fTangentStart); if ((numerA >= 0) != (numerB >= 0)) { if (kCtrlPt_RayType == intersectRayType) { numerA /= denom; SkPoint* ctrlPt = &quadPts->fQuad[1]; ctrlPt->fX = start.fX * (1 - numerA) + quadPts->fTangentStart.fX * numerA; ctrlPt->fY = start.fY * (1 - numerA) + quadPts->fTangentStart.fY * numerA; } return STROKER_RESULT(kQuad_ResultType, depth, quadPts, "(numerA=%g >= 0) != (numerB=%g >= 0)", numerA, numerB); } if (SkTMax(dist1, dist2) <= fInvResScaleSquared) { return STROKER_RESULT(kDegenerate_ResultType, depth, quadPts, "SkTMax(dist1=%g, dist2=%g) <= fInvResScaleSquared", dist1, dist2); } return STROKER_RESULT(kSplit_ResultType, depth, quadPts, "(numerA=%g >= 0) == (numerB=%g >= 0)", numerA, numerB); } else { // if the lines are parallel, straight line is good enough return STROKER_RESULT(kDegenerate_ResultType, depth, quadPts, "SkScalarNearlyZero(denom=%g)", denom); } } // Given a cubic and a t-range, determine if the stroke can be described by a quadratic. SkPathStroker::ResultType SkPathStroker::tangentsMeet(const SkPoint cubic[4], SkQuadConstruct* quadPts) { if (!this->cubicQuadEnds(cubic, quadPts)) { return kNormalError_ResultType; } return intersectRay(quadPts, kResultType_RayType STROKER_DEBUG_PARAMS(fRecursionDepth)); } // Intersect the line with the quad and return the t values on the quad where the line crosses. static int intersect_quad_ray(const SkPoint line[2], const SkPoint quad[3], SkScalar roots[2]) { SkVector vec = line[1] - line[0]; SkScalar r[3]; for (int n = 0; n < 3; ++n) { r[n] = (quad[n].fY - line[0].fY) * vec.fX - (quad[n].fX - line[0].fX) * vec.fY; } SkScalar A = r[2]; SkScalar B = r[1]; SkScalar C = r[0]; A += C - 2 * B; // A = a - 2*b + c B -= C; // B = -(b - c) return SkFindUnitQuadRoots(A, 2 * B, C, roots); } // Return true if the point is close to the bounds of the quad. This is used as a quick reject. bool SkPathStroker::ptInQuadBounds(const SkPoint quad[3], const SkPoint& pt) const { SkScalar xMin = SkTMin(SkTMin(quad[0].fX, quad[1].fX), quad[2].fX); if (pt.fX + fInvResScale < xMin) { return false; } SkScalar xMax = SkTMax(SkTMax(quad[0].fX, quad[1].fX), quad[2].fX); if (pt.fX - fInvResScale > xMax) { return false; } SkScalar yMin = SkTMin(SkTMin(quad[0].fY, quad[1].fY), quad[2].fY); if (pt.fY + fInvResScale < yMin) { return false; } SkScalar yMax = SkTMax(SkTMax(quad[0].fY, quad[1].fY), quad[2].fY); if (pt.fY - fInvResScale > yMax) { return false; } return true; } static bool points_within_dist(const SkPoint& nearPt, const SkPoint& farPt, SkScalar limit) { return nearPt.distanceToSqd(farPt) <= limit * limit; } static bool sharp_angle(const SkPoint quad[3]) { SkVector smaller = quad[1] - quad[0]; SkVector larger = quad[1] - quad[2]; SkScalar smallerLen = smaller.lengthSqd(); SkScalar largerLen = larger.lengthSqd(); if (smallerLen > largerLen) { SkTSwap(smaller, larger); largerLen = smallerLen; } if (!smaller.setLength(largerLen)) { return false; } SkScalar dot = smaller.dot(larger); return dot > 0; } SkPathStroker::ResultType SkPathStroker::strokeCloseEnough(const SkPoint stroke[3], const SkPoint ray[2], SkQuadConstruct* quadPts STROKER_DEBUG_PARAMS(int depth)) const { SkPoint strokeMid; SkEvalQuadAt(stroke, SK_ScalarHalf, &strokeMid); // measure the distance from the curve to the quad-stroke midpoint, compare to radius if (points_within_dist(ray[0], strokeMid, fInvResScaleSquared)) { // if the difference is small if (sharp_angle(quadPts->fQuad)) { return STROKER_RESULT(kSplit_ResultType, depth, quadPts, "sharp_angle (1) =%g,%g, %g,%g, %g,%g", quadPts->fQuad[0].fX, quadPts->fQuad[0].fY, quadPts->fQuad[1].fX, quadPts->fQuad[1].fY, quadPts->fQuad[2].fX, quadPts->fQuad[2].fY); } return STROKER_RESULT(kQuad_ResultType, depth, quadPts, "points_within_dist(ray[0]=%g,%g, strokeMid=%g,%g, fInvResScaleSquared=%g)", ray[0].fX, ray[0].fY, strokeMid.fX, strokeMid.fY, fInvResScaleSquared); } // measure the distance to quad's bounds (quick reject) // an alternative : look for point in triangle if (!ptInQuadBounds(stroke, ray[0])) { // if far, subdivide return STROKER_RESULT(kSplit_ResultType, depth, quadPts, "!pt_in_quad_bounds(stroke=(%g,%g %g,%g %g,%g), ray[0]=%g,%g)", stroke[0].fX, stroke[0].fY, stroke[1].fX, stroke[1].fY, stroke[2].fX, stroke[2].fY, ray[0].fX, ray[0].fY); } // measure the curve ray distance to the quad-stroke SkScalar roots[2]; int rootCount = intersect_quad_ray(ray, stroke, roots); if (rootCount != 1) { return STROKER_RESULT(kSplit_ResultType, depth, quadPts, "rootCount=%d != 1", rootCount); } SkPoint quadPt; SkEvalQuadAt(stroke, roots[0], &quadPt); SkScalar error = fInvResScale * (SK_Scalar1 - SkScalarAbs(roots[0] - 0.5f) * 2); if (points_within_dist(ray[0], quadPt, error)) { // if the difference is small, we're done if (sharp_angle(quadPts->fQuad)) { return STROKER_RESULT(kSplit_ResultType, depth, quadPts, "sharp_angle (2) =%g,%g, %g,%g, %g,%g", quadPts->fQuad[0].fX, quadPts->fQuad[0].fY, quadPts->fQuad[1].fX, quadPts->fQuad[1].fY, quadPts->fQuad[2].fX, quadPts->fQuad[2].fY); } return STROKER_RESULT(kQuad_ResultType, depth, quadPts, "points_within_dist(ray[0]=%g,%g, quadPt=%g,%g, error=%g)", ray[0].fX, ray[0].fY, quadPt.fX, quadPt.fY, error); } // otherwise, subdivide return STROKER_RESULT(kSplit_ResultType, depth, quadPts, "%s", "fall through"); } SkPathStroker::ResultType SkPathStroker::compareQuadCubic(const SkPoint cubic[4], SkQuadConstruct* quadPts) { // get the quadratic approximation of the stroke if (!this->cubicQuadEnds(cubic, quadPts)) { return kNormalError_ResultType; } ResultType resultType = intersectRay(quadPts, kCtrlPt_RayType STROKER_DEBUG_PARAMS(fRecursionDepth) ); if (resultType != kQuad_ResultType) { return resultType; } // project a ray from the curve to the stroke SkPoint ray[2]; // points near midpoint on quad, midpoint on cubic if (!this->cubicPerpRay(cubic, quadPts->fMidT, &ray[1], &ray[0], NULL)) { return kNormalError_ResultType; } return strokeCloseEnough(quadPts->fQuad, ray, quadPts STROKER_DEBUG_PARAMS(fRecursionDepth)); } SkPathStroker::ResultType SkPathStroker::compareQuadConic(const SkConic& conic, SkQuadConstruct* quadPts) { // get the quadratic approximation of the stroke if (!this->conicQuadEnds(conic, quadPts)) { return kNormalError_ResultType; } ResultType resultType = intersectRay(quadPts, kCtrlPt_RayType STROKER_DEBUG_PARAMS(fRecursionDepth) ); if (resultType != kQuad_ResultType) { return resultType; } // project a ray from the curve to the stroke SkPoint ray[2]; // points near midpoint on quad, midpoint on conic if (!this->conicPerpRay(conic, quadPts->fMidT, &ray[1], &ray[0], NULL)) { return kNormalError_ResultType; } return strokeCloseEnough(quadPts->fQuad, ray, quadPts STROKER_DEBUG_PARAMS(fRecursionDepth)); } SkPathStroker::ResultType SkPathStroker::compareQuadQuad(const SkPoint quad[3], SkQuadConstruct* quadPts) { // get the quadratic approximation of the stroke if (!quadPts->fStartSet) { SkPoint quadStartPt; this->quadPerpRay(quad, quadPts->fStartT, &quadStartPt, &quadPts->fQuad[0], &quadPts->fTangentStart); quadPts->fStartSet = true; } if (!quadPts->fEndSet) { SkPoint quadEndPt; this->quadPerpRay(quad, quadPts->fEndT, &quadEndPt, &quadPts->fQuad[2], &quadPts->fTangentEnd); quadPts->fEndSet = true; } ResultType resultType = intersectRay(quadPts, kCtrlPt_RayType STROKER_DEBUG_PARAMS(fRecursionDepth)); if (resultType != kQuad_ResultType) { return resultType; } // project a ray from the curve to the stroke SkPoint ray[2]; this->quadPerpRay(quad, quadPts->fMidT, &ray[1], &ray[0], NULL); return strokeCloseEnough(quadPts->fQuad, ray, quadPts STROKER_DEBUG_PARAMS(fRecursionDepth)); } void SkPathStroker::addDegenerateLine(const SkQuadConstruct* quadPts) { const SkPoint* quad = quadPts->fQuad; SkPath* path = fStrokeType == kOuter_StrokeType ? &fOuter : &fInner; path->lineTo(quad[2].fX, quad[2].fY); } bool SkPathStroker::cubicMidOnLine(const SkPoint cubic[4], const SkQuadConstruct* quadPts) const { SkPoint strokeMid; if (!cubicQuadMid(cubic, quadPts, &strokeMid)) { return false; } SkScalar dist = pt_to_line(strokeMid, quadPts->fQuad[0], quadPts->fQuad[2]); return dist < fInvResScaleSquared; } bool SkPathStroker::cubicStroke(const SkPoint cubic[4], SkQuadConstruct* quadPts) { if (!fFoundTangents) { ResultType resultType = this->tangentsMeet(cubic, quadPts); if (kQuad_ResultType != resultType) { if (kNormalError_ResultType == resultType) { return false; } if ((kDegenerate_ResultType == resultType || points_within_dist(quadPts->fQuad[0], quadPts->fQuad[2], fInvResScaleSquared)) && cubicMidOnLine(cubic, quadPts)) { addDegenerateLine(quadPts); return true; } } else { fFoundTangents = true; } } if (fFoundTangents) { ResultType resultType = this->compareQuadCubic(cubic, quadPts); if (kQuad_ResultType == resultType) { SkPath* path = fStrokeType == kOuter_StrokeType ? &fOuter : &fInner; const SkPoint* stroke = quadPts->fQuad; path->quadTo(stroke[1].fX, stroke[1].fY, stroke[2].fX, stroke[2].fY); return true; } if (kDegenerate_ResultType == resultType) { addDegenerateLine(quadPts); return true; } if (kNormalError_ResultType == resultType) { return false; } } if (!SkScalarIsFinite(quadPts->fQuad[2].fX) || !SkScalarIsFinite(quadPts->fQuad[2].fY)) { return false; // just abort if projected quad isn't representable } SkDEBUGCODE(gMaxRecursion[fFoundTangents] = SkTMax(gMaxRecursion[fFoundTangents], fRecursionDepth + 1)); if (++fRecursionDepth > kRecursiveLimits[fFoundTangents]) { return false; // just abort if projected quad isn't representable } SkQuadConstruct half; if (!half.initWithStart(quadPts)) { addDegenerateLine(quadPts); return true; } if (!this->cubicStroke(cubic, &half)) { return false; } if (!half.initWithEnd(quadPts)) { addDegenerateLine(quadPts); return true; } if (!this->cubicStroke(cubic, &half)) { return false; } --fRecursionDepth; return true; } bool SkPathStroker::conicStroke(const SkConic& conic, SkQuadConstruct* quadPts) { ResultType resultType = this->compareQuadConic(conic, quadPts); if (kQuad_ResultType == resultType) { const SkPoint* stroke = quadPts->fQuad; SkPath* path = fStrokeType == kOuter_StrokeType ? &fOuter : &fInner; path->quadTo(stroke[1].fX, stroke[1].fY, stroke[2].fX, stroke[2].fY); return true; } if (kDegenerate_ResultType == resultType) { addDegenerateLine(quadPts); return true; } SkDEBUGCODE(gMaxRecursion[kConic_RecursiveLimit] = SkTMax(gMaxRecursion[kConic_RecursiveLimit], fRecursionDepth + 1)); if (++fRecursionDepth > kRecursiveLimits[kConic_RecursiveLimit]) { return false; // just abort if projected quad isn't representable } SkQuadConstruct half; (void) half.initWithStart(quadPts); if (!this->conicStroke(conic, &half)) { return false; } (void) half.initWithEnd(quadPts); if (!this->conicStroke(conic, &half)) { return false; } --fRecursionDepth; return true; } bool SkPathStroker::quadStroke(const SkPoint quad[3], SkQuadConstruct* quadPts) { ResultType resultType = this->compareQuadQuad(quad, quadPts); if (kQuad_ResultType == resultType) { const SkPoint* stroke = quadPts->fQuad; SkPath* path = fStrokeType == kOuter_StrokeType ? &fOuter : &fInner; path->quadTo(stroke[1].fX, stroke[1].fY, stroke[2].fX, stroke[2].fY); return true; } if (kDegenerate_ResultType == resultType) { addDegenerateLine(quadPts); return true; } SkDEBUGCODE(gMaxRecursion[kQuad_RecursiveLimit] = SkTMax(gMaxRecursion[kQuad_RecursiveLimit], fRecursionDepth + 1)); if (++fRecursionDepth > kRecursiveLimits[kQuad_RecursiveLimit]) { return false; // just abort if projected quad isn't representable } SkQuadConstruct half; (void) half.initWithStart(quadPts); if (!this->quadStroke(quad, &half)) { return false; } (void) half.initWithEnd(quadPts); if (!this->quadStroke(quad, &half)) { return false; } --fRecursionDepth; return true; } #endif void SkPathStroker::cubicTo(const SkPoint& pt1, const SkPoint& pt2, const SkPoint& pt3) { #ifdef SK_QUAD_STROKE_APPROXIMATION const SkPoint cubic[4] = { fPrevPt, pt1, pt2, pt3 }; SkPoint reduction[3]; const SkPoint* tangentPt; ReductionType reductionType = CheckCubicLinear(cubic, reduction, &tangentPt); if (kPoint_ReductionType == reductionType) { return; } if (kLine_ReductionType == reductionType) { this->lineTo(pt3); return; } if (kDegenerate_ReductionType <= reductionType && kDegenerate3_ReductionType >= reductionType) { this->lineTo(reduction[0]); SkStrokerPriv::JoinProc saveJoiner = fJoiner; fJoiner = SkStrokerPriv::JoinFactory(SkPaint::kRound_Join); if (kDegenerate2_ReductionType <= reductionType) { this->lineTo(reduction[1]); } if (kDegenerate3_ReductionType == reductionType) { this->lineTo(reduction[2]); } this->lineTo(pt3); fJoiner = saveJoiner; return; } SkASSERT(kQuad_ReductionType == reductionType); SkVector normalAB, unitAB, normalCD, unitCD; this->preJoinTo(*tangentPt, &normalAB, &unitAB, false); SkScalar tValues[2]; int count = SkFindCubicInflections(cubic, tValues); SkScalar lastT = 0; for (int index = 0; index <= count; ++index) { SkScalar nextT = index < count ? tValues[index] : 1; SkQuadConstruct quadPts; this->init(kOuter_StrokeType, &quadPts, lastT, nextT); if (!this->cubicStroke(cubic, &quadPts)) { break; } this->init(kInner_StrokeType, &quadPts, lastT, nextT); if (!this->cubicStroke(cubic, &quadPts)) { break; } lastT = nextT; } // emit the join even if one stroke succeeded but the last one failed // this avoids reversing an inner stroke with a partial path followed by another moveto this->setCubicEndNormal(cubic, normalAB, unitAB, &normalCD, &unitCD); #else bool degenerateAB = SkPath::IsLineDegenerate(fPrevPt, pt1); bool degenerateBC = SkPath::IsLineDegenerate(pt1, pt2); bool degenerateCD = SkPath::IsLineDegenerate(pt2, pt3); if (degenerateAB + degenerateBC + degenerateCD >= 2 || (degenerateAB && SkPath::IsLineDegenerate(fPrevPt, pt2))) { 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; count = SkChopCubicAtMaxCurvature(pts, tmp, tValues); 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; } } #endif this->postJoinTo(pt3, normalCD, unitCD); } /////////////////////////////////////////////////////////////////////////////// /////////////////////////////////////////////////////////////////////////////// #include "SkPaintDefaults.h" SkStroke::SkStroke() { fWidth = SK_Scalar1; fMiterLimit = SkPaintDefaults_MiterLimit; fCap = SkPaint::kDefault_Cap; fJoin = SkPaint::kDefault_Join; fDoFill = false; } SkStroke::SkStroke(const SkPaint& p) { fWidth = p.getStrokeWidth(); fMiterLimit = p.getStrokeMiter(); fCap = (uint8_t)p.getStrokeCap(); fJoin = (uint8_t)p.getStrokeJoin(); fDoFill = SkToU8(p.getStyle() == SkPaint::kStrokeAndFill_Style); } SkStroke::SkStroke(const SkPaint& p, SkScalar width) { fWidth = width; fMiterLimit = p.getStrokeMiter(); fCap = (uint8_t)p.getStrokeCap(); fJoin = (uint8_t)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); } /////////////////////////////////////////////////////////////////////////////// // If src==dst, then we use a tmp path to record the stroke, and then swap // its contents with src when we're done. class AutoTmpPath { public: AutoTmpPath(const SkPath& src, SkPath** dst) : fSrc(src) { if (&src == *dst) { *dst = &fTmpDst; fSwapWithSrc = true; } else { (*dst)->reset(); fSwapWithSrc = false; } } ~AutoTmpPath() { if (fSwapWithSrc) { fTmpDst.swap(*const_cast(&fSrc)); } } private: SkPath fTmpDst; const SkPath& fSrc; bool fSwapWithSrc; }; void SkStroke::strokePath(const SkPath& src, SkPath* dst) const { SkASSERT(&src != NULL && dst != NULL); SkScalar radius = SkScalarHalf(fWidth); AutoTmpPath tmp(src, &dst); if (radius <= 0) { return; } // If src is really a rect, call our specialty strokeRect() method { SkRect rect; bool isClosed; SkPath::Direction dir; if (src.isRect(&rect, &isClosed, &dir) && isClosed) { this->strokeRect(rect, dst, dir); // our answer should preserve the inverseness of the src if (src.isInverseFillType()) { SkASSERT(!dst->isInverseFillType()); dst->toggleInverseFillType(); } return; } } SkAutoConicToQuads converter; #ifndef SK_QUAD_STROKE_APPROXIMATION const SkScalar conicTol = SK_Scalar1 / 4 / fResScale; #endif SkPathStroker stroker(src, radius, fMiterLimit, this->getCap(), this->getJoin(), fResScale); SkPath::Iter iter(src, false); SkPath::Verb lastSegment = SkPath::kMove_Verb; for (;;) { SkPoint pts[4]; switch (iter.next(pts, false)) { case SkPath::kMove_Verb: stroker.moveTo(pts[0]); break; case SkPath::kLine_Verb: stroker.lineTo(pts[1]); lastSegment = SkPath::kLine_Verb; break; case SkPath::kQuad_Verb: stroker.quadTo(pts[1], pts[2]); lastSegment = SkPath::kQuad_Verb; break; case SkPath::kConic_Verb: { #ifdef SK_QUAD_STROKE_APPROXIMATION stroker.conicTo(pts[1], pts[2], iter.conicWeight()); lastSegment = SkPath::kConic_Verb; break; #else // todo: if we had maxcurvature for conics, perhaps we should // natively extrude the conic instead of converting to quads. const SkPoint* quadPts = converter.computeQuads(pts, iter.conicWeight(), conicTol); for (int i = 0; i < converter.countQuads(); ++i) { stroker.quadTo(quadPts[1], quadPts[2]); quadPts += 2; } lastSegment = SkPath::kQuad_Verb; #endif } break; case SkPath::kCubic_Verb: stroker.cubicTo(pts[1], pts[2], pts[3]); lastSegment = SkPath::kCubic_Verb; break; case SkPath::kClose_Verb: stroker.close(lastSegment == SkPath::kLine_Verb); break; case SkPath::kDone_Verb: goto DONE; } } DONE: stroker.done(dst, lastSegment == SkPath::kLine_Verb); if (fDoFill) { if (src.cheapIsDirection(SkPath::kCCW_Direction)) { dst->reverseAddPath(src); } else { dst->addPath(src); } } else { // Seems like we can assume that a 2-point src would always result in // a convex stroke, but testing has proved otherwise. // TODO: fix the stroker to make this assumption true (without making // it slower that the work that will be done in computeConvexity()) #if 0 // this test results in a non-convex stroke :( static void test(SkCanvas* canvas) { SkPoint pts[] = { 146.333328, 192.333328, 300.333344, 293.333344 }; SkPaint paint; paint.setStrokeWidth(7); paint.setStrokeCap(SkPaint::kRound_Cap); canvas->drawLine(pts[0].fX, pts[0].fY, pts[1].fX, pts[1].fY, paint); } #endif #if 0 if (2 == src.countPoints()) { dst->setIsConvex(true); } #endif } // our answer should preserve the inverseness of the src if (src.isInverseFillType()) { SkASSERT(!dst->isInverseFillType()); dst->toggleInverseFillType(); } } static SkPath::Direction reverse_direction(SkPath::Direction dir) { SkASSERT(SkPath::kUnknown_Direction != dir); return SkPath::kCW_Direction == dir ? SkPath::kCCW_Direction : SkPath::kCW_Direction; } static void addBevel(SkPath* path, const SkRect& r, const SkRect& outer, SkPath::Direction dir) { SkPoint pts[8]; if (SkPath::kCW_Direction == dir) { pts[0].set(r.fLeft, outer.fTop); pts[1].set(r.fRight, outer.fTop); pts[2].set(outer.fRight, r.fTop); pts[3].set(outer.fRight, r.fBottom); pts[4].set(r.fRight, outer.fBottom); pts[5].set(r.fLeft, outer.fBottom); pts[6].set(outer.fLeft, r.fBottom); pts[7].set(outer.fLeft, r.fTop); } else { pts[7].set(r.fLeft, outer.fTop); pts[6].set(r.fRight, outer.fTop); pts[5].set(outer.fRight, r.fTop); pts[4].set(outer.fRight, r.fBottom); pts[3].set(r.fRight, outer.fBottom); pts[2].set(r.fLeft, outer.fBottom); pts[1].set(outer.fLeft, r.fBottom); pts[0].set(outer.fLeft, r.fTop); } path->addPoly(pts, 8, true); } void SkStroke::strokeRect(const SkRect& origRect, SkPath* dst, SkPath::Direction dir) const { SkASSERT(dst != NULL); dst->reset(); SkScalar radius = SkScalarHalf(fWidth); if (radius <= 0) { return; } SkScalar rw = origRect.width(); SkScalar rh = origRect.height(); if ((rw < 0) ^ (rh < 0)) { dir = reverse_direction(dir); } SkRect rect(origRect); rect.sort(); // reassign these, now that we know they'll be >= 0 rw = rect.width(); rh = rect.height(); SkRect r(rect); r.outset(radius, radius); SkPaint::Join join = (SkPaint::Join)fJoin; if (SkPaint::kMiter_Join == join && fMiterLimit < SK_ScalarSqrt2) { join = SkPaint::kBevel_Join; } switch (join) { case SkPaint::kMiter_Join: dst->addRect(r, dir); break; case SkPaint::kBevel_Join: addBevel(dst, rect, r, dir); break; case SkPaint::kRound_Join: dst->addRoundRect(r, radius, radius, dir); break; default: break; } if (fWidth < SkMinScalar(rw, rh) && !fDoFill) { r = rect; r.inset(radius, radius); dst->addRect(r, reverse_direction(dir)); } }