diff options
author | caryclark <caryclark@google.com> | 2016-01-19 08:07:49 -0800 |
---|---|---|
committer | Commit bot <commit-bot@chromium.org> | 2016-01-19 08:07:50 -0800 |
commit | b6474dd1a530a543ae799c3822e8bc60180761c0 (patch) | |
tree | 2e42f77ea502e31ac7473806437adb6be680bd33 /src | |
parent | a913275bda105fd545af471b724d7e8c1dacb9ae (diff) |
fix circular dashing
Path measure cannot use the same code approach for quadratics
and cubics. Subdividing cubics repeatedly does not result in
subdivided t values, e.g. a quarter circle cubic divided in
half twice does not have a t value equivalent to 1/4.
Instead, always compute the cubic segment from a pair of
t values.
When finding the length of the cubic through recursive measures,
it is enough to carry the point at a given t to the next
subdivision.
(Chrome suppression has landed already.)
R=reed@google.com
GOLD_TRYBOT_URL= https://gold.skia.org/search2?unt=true&query=source_type%3Dgm&master=false&issue=1602153002
Review URL: https://codereview.chromium.org/1602153002
Diffstat (limited to 'src')
-rw-r--r-- | src/core/SkGeometry.cpp | 44 | ||||
-rw-r--r-- | src/core/SkGeometry.h | 109 | ||||
-rw-r--r-- | src/core/SkPathMeasure.cpp | 119 |
3 files changed, 234 insertions, 38 deletions
diff --git a/src/core/SkGeometry.cpp b/src/core/SkGeometry.cpp index c25e18641a..2ea3095198 100644 --- a/src/core/SkGeometry.cpp +++ b/src/core/SkGeometry.cpp @@ -9,18 +9,6 @@ #include "SkMatrix.h" #include "SkNx.h" -#if 0 -static Sk2s from_point(const SkPoint& point) { - return Sk2s::Load(&point.fX); -} - -static SkPoint to_point(const Sk2s& x) { - SkPoint point; - x.store(&point.fX); - return point; -} -#endif - static SkVector to_vector(const Sk2s& x) { SkVector vector; x.store(&vector.fX); @@ -220,7 +208,7 @@ void SkChopQuadAt(const SkPoint src[3], SkPoint dst[5], SkScalar t) { } void SkChopQuadAtHalf(const SkPoint src[3], SkPoint dst[5]) { - SkChopQuadAt(src, dst, 0.5f); return; + SkChopQuadAt(src, dst, 0.5f); } /** Quad'(t) = At + B, where @@ -1246,8 +1234,34 @@ void SkConic::chopAt(SkScalar t, SkConic dst[2]) const { dst[1].fW = tmp2[2].fZ / root; } -static Sk2s times_2(const Sk2s& value) { - return value + value; +void SkConic::chopAt(SkScalar t1, SkScalar t2, SkConic* dst) const { + if (0 == t1 || 1 == t2) { + if (0 == t1 && 1 == t2) { + *dst = *this; + } else { + SkConic pair[2]; + this->chopAt(t1 ? t1 : t2, pair); + *dst = pair[SkToBool(t1)]; + } + return; + } + SkConicCoeff coeff(*this); + Sk2s tt1(t1); + Sk2s aXY = coeff.fNumer.eval(tt1); + Sk2s aZZ = coeff.fDenom.eval(tt1); + Sk2s midTT((t1 + t2) / 2); + Sk2s dXY = coeff.fNumer.eval(midTT); + Sk2s dZZ = coeff.fDenom.eval(midTT); + Sk2s tt2(t2); + Sk2s cXY = coeff.fNumer.eval(tt2); + Sk2s cZZ = coeff.fDenom.eval(tt2); + Sk2s bXY = times_2(dXY) - (aXY + cXY) * Sk2s(0.5f); + Sk2s bZZ = times_2(dZZ) - (aZZ + cZZ) * Sk2s(0.5f); + dst->fPts[0] = to_point(aXY / aZZ); + dst->fPts[1] = to_point(bXY / bZZ); + dst->fPts[2] = to_point(cXY / cZZ); + Sk2s ww = bZZ / (aZZ * cZZ).sqrt(); + dst->fW = ww.kth<0>(); } SkPoint SkConic::evalAt(SkScalar t) const { diff --git a/src/core/SkGeometry.h b/src/core/SkGeometry.h index 79cad2eee0..0fd5a61711 100644 --- a/src/core/SkGeometry.h +++ b/src/core/SkGeometry.h @@ -23,7 +23,11 @@ static inline SkPoint to_point(const Sk2s& x) { static inline Sk2s sk2s_cubic_eval(const Sk2s& A, const Sk2s& B, const Sk2s& C, const Sk2s& D, const Sk2s& t) { - return ((A * t + B) * t + C) * t + D; + return ((A * t + B) * t + C) * t + D; +} + +static Sk2s times_2(const Sk2s& value) { + return value + value; } /** Given a quadratic equation Ax^2 + Bx + C = 0, return 0, 1, 2 roots for the @@ -42,10 +46,10 @@ SkPoint SkEvalQuadTangentAt(const SkPoint src[3], SkScalar t); void SkEvalQuadAt(const SkPoint src[3], SkScalar t, SkPoint* pt, SkVector* tangent = nullptr); /** - * output is : eval(t) == coeff[0] * t^2 + coeff[1] * t + coeff[2] - */ + * output is : eval(t) == coeff[0] * t^2 + coeff[1] * t + coeff[2] + */ void SkQuadToCoeff(const SkPoint pts[3], SkPoint coeff[3]); - + /** * output is : eval(t) == coeff[0] * t^3 + coeff[1] * t^2 + coeff[2] * t + coeff[3] */ @@ -241,6 +245,7 @@ struct SkConic { */ void evalAt(SkScalar t, SkPoint* pos, SkVector* tangent = nullptr) const; void chopAt(SkScalar t, SkConic dst[2]) const; + void chopAt(SkScalar t1, SkScalar t2, SkConic* dst) const; void chop(SkConic dst[2]) const; SkPoint evalAt(SkScalar t) const; @@ -287,6 +292,102 @@ struct SkConic { const SkMatrix*, SkConic conics[kMaxConicsForArc]); }; +// inline helpers are contained in a namespace to avoid external leakage to fragile SkNx members +namespace { + +/** + * use for : eval(t) == A * t^2 + B * t + C + */ +struct SkQuadCoeff { + SkQuadCoeff() {} + + SkQuadCoeff(const Sk2s& A, const Sk2s& B, const Sk2s& C) + : fA(A) + , fB(B) + , fC(C) + { + } + + SkQuadCoeff(const SkPoint src[3]) { + fC = from_point(src[0]); + Sk2s P1 = from_point(src[1]); + Sk2s P2 = from_point(src[2]); + fB = times_2(P1 - fC); + fA = P2 - times_2(P1) + fC; + } + + Sk2s eval(SkScalar t) { + Sk2s tt(t); + return eval(tt); + } + + Sk2s eval(const Sk2s& tt) { + return (fA * tt + fB) * tt + fC; + } + + Sk2s fA; + Sk2s fB; + Sk2s fC; +}; + +struct SkConicCoeff { + SkConicCoeff(const SkConic& conic) { + Sk2s p0 = from_point(conic.fPts[0]); + Sk2s p1 = from_point(conic.fPts[1]); + Sk2s p2 = from_point(conic.fPts[2]); + Sk2s ww(conic.fW); + + Sk2s p1w = p1 * ww; + fNumer.fC = p0; + fNumer.fA = p2 - times_2(p1w) + p0; + fNumer.fB = times_2(p1w - p0); + + fDenom.fC = Sk2s(1); + fDenom.fB = times_2(ww - fDenom.fC); + fDenom.fA = Sk2s(0) - fDenom.fB; + } + + Sk2s eval(SkScalar t) { + Sk2s tt(t); + Sk2s numer = fNumer.eval(tt); + Sk2s denom = fDenom.eval(tt); + return numer / denom; + } + + SkQuadCoeff fNumer; + SkQuadCoeff fDenom; +}; + +struct SkCubicCoeff { + SkCubicCoeff(const SkPoint src[4]) { + Sk2s P0 = from_point(src[0]); + Sk2s P1 = from_point(src[1]); + Sk2s P2 = from_point(src[2]); + Sk2s P3 = from_point(src[3]); + Sk2s three(3); + fA = P3 + three * (P1 - P2) - P0; + fB = three * (P2 - times_2(P1) + P0); + fC = three * (P1 - P0); + fD = P0; + } + + Sk2s eval(SkScalar t) { + Sk2s tt(t); + return eval(tt); + } + + Sk2s eval(const Sk2s& t) { + return ((fA * t + fB) * t + fC) * t + fD; + } + + Sk2s fA; + Sk2s fB; + Sk2s fC; + Sk2s fD; +}; + +} + #include "SkTemplates.h" /** diff --git a/src/core/SkPathMeasure.cpp b/src/core/SkPathMeasure.cpp index eb80cf3b83..bc5350373c 100644 --- a/src/core/SkPathMeasure.cpp +++ b/src/core/SkPathMeasure.cpp @@ -73,6 +73,15 @@ static bool quad_too_curvy(const SkPoint pts[3]) { return dist > CHEAP_DIST_LIMIT; } +static bool conic_too_curvy(const SkPoint& firstPt, const SkPoint& midTPt, + const SkPoint& lastPt) { + SkPoint midEnds = firstPt + lastPt; + midEnds *= 0.5f; + SkVector dxy = midTPt - midEnds; + SkScalar dist = SkMaxScalar(SkScalarAbs(dxy.fX), SkScalarAbs(dxy.fY)); + return dist > CHEAP_DIST_LIMIT; +} + static bool cheap_dist_exceeds_limit(const SkPoint& pt, SkScalar x, SkScalar y) { SkScalar dist = SkMaxScalar(SkScalarAbs(x - pt.fX), SkScalarAbs(y - pt.fY)); @@ -90,28 +99,58 @@ static bool cubic_too_curvy(const SkPoint pts[4]) { SkScalarInterp(pts[0].fY, pts[3].fY, SK_Scalar1*2/3)); } +static SkScalar quad_folded_len(const SkPoint pts[3]) { + SkScalar t = SkFindQuadMaxCurvature(pts); + SkPoint pt = SkEvalQuadAt(pts, t); + SkVector a = pts[2] - pt; + SkScalar result = a.length(); + if (0 != t) { + SkVector b = pts[0] - pt; + result += b.length(); + } + SkASSERT(SkScalarIsFinite(result)); + return result; +} + /* from http://www.malczak.linuxpl.com/blog/quadratic-bezier-curve-length/ */ +/* This works -- more needs to be done to see if it is performant on all platforms. + To use this to measure parts of quads requires recomputing everything -- perhaps + a chop-like interface can start from a larger measurement and get two new measurements + with one call here. + */ static SkScalar compute_quad_len(const SkPoint pts[3]) { - SkPoint a,b; - a.fX = pts[0].fX - 2 * pts[1].fX + pts[2].fX; - a.fY = pts[0].fY - 2 * pts[1].fY + pts[2].fY; - b.fX = 2 * (pts[1].fX - pts[0].fX); - b.fY = 2 * (pts[1].fY - pts[0].fY); - SkScalar A = 4 * (a.fX * a.fX + a.fY * a.fY); - SkScalar B = 4 * (a.fX * b.fX + a.fY * b.fY); - SkScalar C = b.fX * b.fX + b.fY * b.fY; - - SkScalar Sabc = 2 * SkScalarSqrt(A + B + C); - SkScalar A_2 = SkScalarSqrt(A); - SkScalar A_32 = 2 * A * A_2; - SkScalar C_2 = 2 * SkScalarSqrt(C); - SkScalar BA = B / A_2; - - return (A_32 * Sabc + A_2 * B * (Sabc - C_2) + - (4 * C * A - B * B) * SkScalarLog((2 * A_2 + BA + Sabc) / (BA + C_2))) / (4 * A_32); + SkPoint a,b; + a.fX = pts[0].fX - 2 * pts[1].fX + pts[2].fX; + a.fY = pts[0].fY - 2 * pts[1].fY + pts[2].fY; + SkScalar A = 4 * (a.fX * a.fX + a.fY * a.fY); + if (0 == A) { + a = pts[2] - pts[0]; + return a.length(); + } + b.fX = 2 * (pts[1].fX - pts[0].fX); + b.fY = 2 * (pts[1].fY - pts[0].fY); + SkScalar B = 4 * (a.fX * b.fX + a.fY * b.fY); + SkScalar C = b.fX * b.fX + b.fY * b.fY; + SkScalar Sabc = 2 * SkScalarSqrt(A + B + C); + SkScalar A_2 = SkScalarSqrt(A); + SkScalar A_32 = 2 * A * A_2; + SkScalar C_2 = 2 * SkScalarSqrt(C); + SkScalar BA = B / A_2; + if (0 == BA + C_2) { + return quad_folded_len(pts); + } + SkScalar J = A_32 * Sabc + A_2 * B * (Sabc - C_2); + SkScalar K = 4 * C * A - B * B; + SkScalar L = (2 * A_2 + BA + Sabc) / (BA + C_2); + if (L <= 0) { + return quad_folded_len(pts); + } + SkScalar M = SkScalarLog(L); + SkScalar result = (J + K * M) / (4 * A_32); + SkASSERT(SkScalarIsFinite(result)); + return result; } - SkScalar SkPathMeasure::compute_quad_segs(const SkPoint pts[3], SkScalar distance, int mint, int maxt, int ptIndex) { if (tspan_big_enough(maxt - mint) && quad_too_curvy(pts)) { @@ -136,6 +175,7 @@ SkScalar SkPathMeasure::compute_quad_segs(const SkPoint pts[3], return distance; } +#ifdef SK_SUPPORT_LEGACY_CONIC_MEASURE SkScalar SkPathMeasure::compute_conic_segs(const SkConic& conic, SkScalar distance, int mint, int maxt, int ptIndex) { if (tspan_big_enough(maxt - mint) && quad_too_curvy(conic.fPts)) { @@ -159,6 +199,30 @@ SkScalar SkPathMeasure::compute_conic_segs(const SkConic& conic, } return distance; } +#else +SkScalar SkPathMeasure::compute_conic_segs(const SkConic& conic, SkScalar distance, + int mint, const SkPoint& minPt, + int maxt, const SkPoint& maxPt, int ptIndex) { + int halft = (mint + maxt) >> 1; + SkPoint halfPt = conic.evalAt(tValue2Scalar(halft)); + if (tspan_big_enough(maxt - mint) && conic_too_curvy(minPt, halfPt, maxPt)) { + distance = this->compute_conic_segs(conic, distance, mint, minPt, halft, halfPt, ptIndex); + distance = this->compute_conic_segs(conic, distance, halft, halfPt, maxt, maxPt, ptIndex); + } else { + SkScalar d = SkPoint::Distance(minPt, maxPt); + SkScalar prevD = distance; + distance += d; + if (distance > prevD) { + Segment* seg = fSegments.append(); + seg->fDistance = distance; + seg->fPtIndex = ptIndex; + seg->fType = kConic_SegType; + seg->fTValue = maxt; + } + } + return distance; +} +#endif SkScalar SkPathMeasure::compute_cubic_segs(const SkPoint pts[4], SkScalar distance, int mint, int maxt, int ptIndex) { @@ -253,7 +317,12 @@ void SkPathMeasure::buildSegments() { case SkPath::kConic_Verb: { const SkConic conic(pts, fIter.conicWeight()); SkScalar prevD = distance; +#ifdef SK_SUPPORT_LEGACY_CONIC_MEASURE distance = this->compute_conic_segs(conic, distance, 0, kMaxTValue, ptIndex); +#else + distance = this->compute_conic_segs(conic, distance, 0, conic.fPts[0], + kMaxTValue, conic.fPts[2], ptIndex); +#endif if (distance > prevD) { // we store the conic weight in our next point, followed by the last 2 pts // thus to reconstitue a conic, you'd need to say @@ -406,7 +475,8 @@ static void seg_to(const SkPoint pts[], int segType, dst->conicTo(tmp[0].fPts[1], tmp[0].fPts[2], tmp[0].fW); } } else { - SkConic tmp1[2]; +#ifdef SK_SUPPORT_LEGACY_CONIC_MEASURE + SkConic tmp1[2]; conic.chopAt(startT, tmp1); if (SK_Scalar1 == stopT) { dst->conicTo(tmp1[1].fPts[1], tmp1[1].fPts[2], tmp1[1].fW); @@ -415,6 +485,17 @@ static void seg_to(const SkPoint pts[], int segType, tmp1[1].chopAt((stopT - startT) / (SK_Scalar1 - startT), tmp2); dst->conicTo(tmp2[0].fPts[1], tmp2[0].fPts[2], tmp2[0].fW); } +#else + if (SK_Scalar1 == stopT) { + SkConic tmp1[2]; + conic.chopAt(startT, tmp1); + dst->conicTo(tmp1[1].fPts[1], tmp1[1].fPts[2], tmp1[1].fW); + } else { + SkConic tmp; + conic.chopAt(startT, stopT, &tmp); + dst->conicTo(tmp.fPts[1], tmp.fPts[2], tmp.fW); + } +#endif } } break; case kCubic_SegType: |