From 1d474dd1941bfdfec7a5a005b37ddc96482a7706 Mon Sep 17 00:00:00 2001 From: Chris Dalton Date: Tue, 24 Jul 2018 01:08:31 -0600 Subject: Pin max curvature solutions to 0..1 Pins out-of-range solutions for cubic/quad max curvature instead of throwing them out. Code that wants to know the endpoint(s) closest to max curvature now has the information. Code not interested in these values can just ignore 0 and 1. Bug: skia: Change-Id: I8e7e2ef236b4ab963865dc049ac3e09d5396757d Reviewed-on: https://skia-review.googlesource.com/143041 Reviewed-by: Cary Clark Reviewed-by: Mike Reed Commit-Queue: Chris Dalton --- src/core/SkGeometry.cpp | 83 ++++++++++++++------------------ src/core/SkPathMeasure.cpp | 2 +- src/core/SkStroke.cpp | 8 +-- src/gpu/ops/GrAAHairLinePathRenderer.cpp | 2 +- src/pathops/SkOpEdgeBuilder.cpp | 2 +- 5 files changed, 43 insertions(+), 54 deletions(-) (limited to 'src') diff --git a/src/core/SkGeometry.cpp b/src/core/SkGeometry.cpp index ace8a7d4d8..ddf07b7a9d 100644 --- a/src/core/SkGeometry.cpp +++ b/src/core/SkGeometry.cpp @@ -32,10 +32,6 @@ static int is_not_monotonic(SkScalar a, SkScalar b, SkScalar c) { //////////////////////////////////////////////////////////////////////// -static bool is_unit_interval(SkScalar x) { - return x > 0 && x < SK_Scalar1; -} - static int valid_unit_divide(SkScalar numer, SkScalar denom, SkScalar* ratio) { SkASSERT(ratio); @@ -264,15 +260,27 @@ SkScalar SkFindQuadMaxCurvature(const SkPoint src[3]) { SkScalar Ay = src[1].fY - src[0].fY; SkScalar Bx = src[0].fX - src[1].fX - src[1].fX + src[2].fX; SkScalar By = src[0].fY - src[1].fY - src[1].fY + src[2].fY; - SkScalar t = 0; // 0 means don't chop - (void)valid_unit_divide(-(Ax * Bx + Ay * By), Bx * Bx + By * By, &t); + SkScalar numer = -(Ax * Bx + Ay * By); + SkScalar denom = Bx * Bx + By * By; + if (denom < 0) { + numer = -numer; + denom = -denom; + } + if (numer <= 0) { + return 0; + } + if (numer >= denom) { // Also catches denom=0. + return 1; + } + SkScalar t = numer / denom; + SkASSERT(0 <= t && t < 1); return t; } int SkChopQuadAtMaxCurvature(const SkPoint src[3], SkPoint dst[5]) { SkScalar t = SkFindQuadMaxCurvature(src); - if (t == 0) { + if (t == 0 || t == 1) { memcpy(dst, src, 3 * sizeof(SkPoint)); return 1; } else { @@ -421,8 +429,8 @@ void SkChopCubicAt(const SkPoint src[4], SkPoint dst[], { for (int i = 0; i < roots - 1; i++) { - SkASSERT(is_unit_interval(tValues[i])); - SkASSERT(is_unit_interval(tValues[i+1])); + SkASSERT(0 < tValues[i] && tValues[i] < 1); + SkASSERT(0 < tValues[i+1] && tValues[i+1] < 1); SkASSERT(tValues[i] < tValues[i+1]); } } @@ -759,34 +767,19 @@ static int solve_cubic_poly(const SkScalar coeff[4], SkScalar tValues[3]) { SkScalar R2MinusQ3 = R * R - Q3; SkScalar adiv3 = a / 3; - SkScalar* roots = tValues; - SkScalar r; - if (R2MinusQ3 < 0) { // we have 3 real roots // the divide/root can, due to finite precisions, be slightly outside of -1...1 SkScalar theta = SkScalarACos(SkScalarPin(R / SkScalarSqrt(Q3), -1, 1)); SkScalar neg2RootQ = -2 * SkScalarSqrt(Q); - r = neg2RootQ * SkScalarCos(theta/3) - adiv3; - if (is_unit_interval(r)) { - *roots++ = r; - } - r = neg2RootQ * SkScalarCos((theta + 2*SK_ScalarPI)/3) - adiv3; - if (is_unit_interval(r)) { - *roots++ = r; - } - r = neg2RootQ * SkScalarCos((theta - 2*SK_ScalarPI)/3) - adiv3; - if (is_unit_interval(r)) { - *roots++ = r; - } + tValues[0] = SkScalarPin(neg2RootQ * SkScalarCos(theta/3) - adiv3, 0, 1); + tValues[1] = SkScalarPin(neg2RootQ * SkScalarCos((theta + 2*SK_ScalarPI)/3) - adiv3, 0, 1); + tValues[2] = SkScalarPin(neg2RootQ * SkScalarCos((theta - 2*SK_ScalarPI)/3) - adiv3, 0, 1); SkDEBUGCODE(test_collaps_duplicates();) // now sort the roots - int count = (int)(roots - tValues); - SkASSERT((unsigned)count <= 3); - bubble_sort(tValues, count); - count = collaps_duplicates(tValues, count); - roots = tValues + count; // so we compute the proper count below + bubble_sort(tValues, 3); + return collaps_duplicates(tValues, 3); } else { // we have 1 real root SkScalar A = SkScalarAbs(R) + SkScalarSqrt(R2MinusQ3); A = SkScalarCubeRoot(A); @@ -796,13 +789,9 @@ static int solve_cubic_poly(const SkScalar coeff[4], SkScalar tValues[3]) { if (A != 0) { A += Q / A; } - r = A - adiv3; - if (is_unit_interval(r)) { - *roots++ = r; - } + tValues[0] = SkScalarPin(A - adiv3, 0, 1); + return 1; } - - return (int)(roots - tValues); } /* Looking for F' dot F'' == 0 @@ -849,19 +838,10 @@ int SkFindCubicMaxCurvature(const SkPoint src[4], SkScalar tValues[3]) { coeffX[i] += coeffY[i]; } - SkScalar t[3]; - int count = solve_cubic_poly(coeffX, t); - int maxCount = 0; - + int numRoots = solve_cubic_poly(coeffX, tValues); // now remove extrema where the curvature is zero (mins) // !!!! need a test for this !!!! - for (i = 0; i < count; i++) { - // if (not_min_curvature()) - if (t[i] > 0 && t[i] < SK_Scalar1) { - tValues[maxCount++] = t[i]; - } - } - return maxCount; + return numRoots; } int SkChopCubicAtMaxCurvature(const SkPoint src[4], SkPoint dst[13], @@ -872,7 +852,16 @@ int SkChopCubicAtMaxCurvature(const SkPoint src[4], SkPoint dst[13], tValues = t_storage; } - int count = SkFindCubicMaxCurvature(src, tValues); + SkScalar roots[3]; + int rootCount = SkFindCubicMaxCurvature(src, roots); + + // Throw out values not inside 0..1. + int count = 0; + for (int i = 0; i < rootCount; ++i) { + if (0 < roots[i] && roots[i] < 1) { + tValues[count++] = roots[i]; + } + } if (dst) { if (count == 0) { diff --git a/src/core/SkPathMeasure.cpp b/src/core/SkPathMeasure.cpp index 75e2bdf170..e2fdc180f3 100644 --- a/src/core/SkPathMeasure.cpp +++ b/src/core/SkPathMeasure.cpp @@ -182,7 +182,7 @@ static SkScalar quad_folded_len(const SkPoint pts[3]) { SkPoint pt = SkEvalQuadAt(pts, t); SkVector a = pts[2] - pt; SkScalar result = a.length(); - if (0 != t) { + if (0 != t && 1 != t) { SkVector b = pts[0] - pt; result += b.length(); } diff --git a/src/core/SkStroke.cpp b/src/core/SkStroke.cpp index b880c152da..92390a38dd 100644 --- a/src/core/SkStroke.cpp +++ b/src/core/SkStroke.cpp @@ -612,13 +612,13 @@ SkPathStroker::ReductionType SkPathStroker::CheckCubicLinear(const SkPoint cubic } SkScalar tValues[3]; int count = SkFindCubicMaxCurvature(cubic, tValues); - if (count == 0) { - return kLine_ReductionType; - } int rCount = 0; // Now loop over the t-values, and reject any that evaluate to either end-point for (int index = 0; index < count; ++index) { SkScalar t = tValues[index]; + if (0 >= t || t >= 1) { + continue; + } SkEvalCubicAt(cubic, t, &reduction[rCount], nullptr, nullptr); if (reduction[rCount] != cubic[0] && reduction[rCount] != cubic[3]) { ++rCount; @@ -679,7 +679,7 @@ SkPathStroker::ReductionType SkPathStroker::CheckQuadLinear(const SkPoint quad[3 return kQuad_ReductionType; } SkScalar t = SkFindQuadMaxCurvature(quad); - if (0 == t) { + if (0 == t || 1 == t) { return kLine_ReductionType; } *reduction = SkEvalQuadAt(quad, t); diff --git a/src/gpu/ops/GrAAHairLinePathRenderer.cpp b/src/gpu/ops/GrAAHairLinePathRenderer.cpp index d6f3c0664e..05f1fbd684 100644 --- a/src/gpu/ops/GrAAHairLinePathRenderer.cpp +++ b/src/gpu/ops/GrAAHairLinePathRenderer.cpp @@ -140,7 +140,7 @@ static int get_float_exp(float x) { // and dst[1] are the two new conics. static int split_conic(const SkPoint src[3], SkConic dst[2], const SkScalar weight) { SkScalar t = SkFindQuadMaxCurvature(src); - if (t == 0) { + if (t == 0 || t == 1) { if (dst) { dst[0].set(src, weight); } diff --git a/src/pathops/SkOpEdgeBuilder.cpp b/src/pathops/SkOpEdgeBuilder.cpp index 363933e0c5..2be3fddab7 100644 --- a/src/pathops/SkOpEdgeBuilder.cpp +++ b/src/pathops/SkOpEdgeBuilder.cpp @@ -242,7 +242,7 @@ bool SkOpEdgeBuilder::walk() { if (v1.dot(v2) < 0) { // FIXME: max curvature for conics hasn't been implemented; use placeholder SkScalar maxCurvature = SkFindQuadMaxCurvature(pointsPtr); - if (maxCurvature > 0) { + if (0 < maxCurvature && maxCurvature < 1) { SkConic conic(pointsPtr, weight); SkConic pair[2]; if (!conic.chopAt(maxCurvature, pair)) { -- cgit v1.2.3