/*
* 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"
#ifndef SK_LEGACY_STROKE_CURVES
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
#ifdef SK_LEGACY_STROKE_CURVES
#define kMaxQuadSubdivide 5
#define kMaxCubicSubdivide 7
#endif
static inline bool degenerate_vector(const SkVector& v) {
return !SkPoint::CanNormalize(v.fX, v.fY);
}
#ifdef SK_LEGACY_STROKE_CURVES
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;
}
///////////////////////////////////////////////////////////////////////////////
#ifndef SK_LEGACY_STROKE_CURVES
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&);
#ifndef SK_LEGACY_STROKE_CURVES
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;
#ifndef SK_LEGACY_STROKE_CURVES
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
#ifndef SK_LEGACY_STROKE_CURVES
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);
bool 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);
#ifdef SK_LEGACY_STROKE_CURVES
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
};
///////////////////////////////////////////////////////////////////////////////
bool SkPathStroker::preJoinTo(const SkPoint& currPt, SkVector* normal,
SkVector* unitNormal, bool currIsLine) {
SkASSERT(fSegmentCount >= 0);
SkScalar prevX = fPrevPt.fX;
SkScalar prevY = fPrevPt.fY;
if (!set_normal_unitnormal(fPrevPt, currPt, fRadius, normal, unitNormal)) {
return false;
}
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;
return true;
}
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);
#ifndef SK_LEGACY_STROKE_CURVES
// 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;
if (!this->preJoinTo(currPt, &normal, &unitNormal, true)) {
return;
}
this->line_to(currPt, normal);
this->postJoinTo(currPt, normal, unitNormal);
}
#ifdef SK_LEGACY_STROKE_CURVES
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(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
#ifndef SK_LEGACY_STROKE_CURVES
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(fRadius / SkScalarSqrt((SK_Scalar1 + dot)/2)));
dot = SkPoint::DotProduct(*unitNormalCD, unitBC);
SkAssertResult(normalC.setLength(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
#ifndef SK_LEGACY_STROKE_CURVES
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;
if (!this->preJoinTo(pt1, &normalAB, &unitAB, false)) {
this->lineTo(pt2);
return;
}
SkQuadConstruct quadPts;
this->init(kOuter_StrokeType, &quadPts, 0, 1);
(void) this->conicStroke(conic, &quadPts);
this->init(kInner_StrokeType, &quadPts, 0, 1);
(void) this->conicStroke(conic, &quadPts);
this->setConicEndNormal(conic, normalAB, unitAB, &normalBC, &unitBC);
this->postJoinTo(pt2, normalBC, unitBC);
}
#endif
void SkPathStroker::quadTo(const SkPoint& pt1, const SkPoint& pt2) {
#ifndef SK_LEGACY_STROKE_CURVES
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;
if (!this->preJoinTo(pt1, &normalAB, &unitAB, false)) {
this->lineTo(pt2);
return;
}
SkQuadConstruct quadPts;
this->init(kOuter_StrokeType, &quadPts, 0, 1);
(void) this->quadStroke(quad, &quadPts);
this->init(kInner_StrokeType, &quadPts, 0, 1);
(void) this->quadStroke(quad, &quadPts);
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);
}
#ifndef SK_LEGACY_STROKE_CURVES
// 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, fInvResScale)) { // 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, fInvResScale=%g)",
ray[0].fX, ray[0].fY, strokeMid.fX, strokeMid.fY, fInvResScale);
}
// 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],
fInvResScale)) && 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) {
#ifndef SK_LEGACY_STROKE_CURVES
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;
if (!this->preJoinTo(*tangentPt, &normalAB, &unitAB, false)) {
this->lineTo(pt3);
return;
}
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);
(void) this->cubicStroke(cubic, &quadPts);
this->init(kInner_StrokeType, &quadPts, lastT, nextT);
(void) this->cubicStroke(cubic, &quadPts);
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<SkPath*>(&fSrc));
}
}
private:
SkPath fTmpDst;
const SkPath& fSrc;
bool fSwapWithSrc;
};
void SkStroke::strokePath(const SkPath& src, SkPath* dst) const {
SkASSERT(dst);
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;
#ifdef SK_LEGACY_STROKE_CURVES
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: {
#ifndef SK_LEGACY_STROKE_CURVES
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));
}
}