From a51ab8416db9772a2eae3122f4f69801642daeb5 Mon Sep 17 00:00:00 2001 From: "bsalomon@google.com" Date: Tue, 10 Jul 2012 19:53:34 +0000 Subject: Preserve convex control point polygon in cubic->quadratic approximation GM test modified, will require rebaselining. Review URL: http://codereview.appspot.com/6355088/ git-svn-id: http://skia.googlecode.com/svn/trunk@4518 2bbb7eff-a529-9590-31e7-b0007b416f81 --- gm/convexpaths.cpp | 22 ++++- src/gpu/GrAAConvexPathRenderer.cpp | 34 ++++---- src/gpu/GrAAHairLinePathRenderer.cpp | 10 ++- src/gpu/GrPathUtils.cpp | 150 ++++++++++++++++++++++++++++------- src/gpu/GrPathUtils.h | 11 +++ 5 files changed, 178 insertions(+), 49 deletions(-) diff --git a/gm/convexpaths.cpp b/gm/convexpaths.cpp index ebe715d866..d1c6aeeff0 100644 --- a/gm/convexpaths.cpp +++ b/gm/convexpaths.cpp @@ -134,7 +134,6 @@ protected: 100 * SK_Scalar1), 25 * SK_Scalar1, 130 * SK_Scalar1, false); */ - // cubics fPaths.push_back().cubicTo( 1 * SK_Scalar1, 1 * SK_Scalar1, 10 * SK_Scalar1, 90 * SK_Scalar1, @@ -143,6 +142,27 @@ protected: 20 * SK_Scalar1, 100 * SK_Scalar1, 0 * SK_Scalar1, 0 * SK_Scalar1); + // path that has a cubic with a repeated first control point and + // a repeated last control point. + fPaths.push_back().moveTo(SK_Scalar1 * 10, SK_Scalar1 * 10); + fPaths.back().cubicTo(10 * SK_Scalar1, 10 * SK_Scalar1, + 10 * SK_Scalar1, 0, + 20 * SK_Scalar1, 0); + fPaths.back().lineTo(40 * SK_Scalar1, 0); + fPaths.back().cubicTo(40 * SK_Scalar1, 0, + 50 * SK_Scalar1, 0, + 50 * SK_Scalar1, 10 * SK_Scalar1); + + // path that has two cubics with repeated middle control points. + fPaths.push_back().moveTo(SK_Scalar1 * 10, SK_Scalar1 * 10); + fPaths.back().cubicTo(10 * SK_Scalar1, 0, + 10 * SK_Scalar1, 0, + 20 * SK_Scalar1, 0); + fPaths.back().lineTo(40 * SK_Scalar1, 0); + fPaths.back().cubicTo(50 * SK_Scalar1, 0, + 50 * SK_Scalar1, 0, + 50 * SK_Scalar1, 10 * SK_Scalar1); + // triangle where one edge is a degenerate quad fPaths.push_back().moveTo(SkFloatToScalar(8.59375f), 45 * SK_Scalar1); fPaths.back().quadTo(SkFloatToScalar(16.9921875f), 45 * SK_Scalar1, diff --git a/src/gpu/GrAAConvexPathRenderer.cpp b/src/gpu/GrAAConvexPathRenderer.cpp index ae4a77337b..41ab2427e3 100644 --- a/src/gpu/GrAAConvexPathRenderer.cpp +++ b/src/gpu/GrAAConvexPathRenderer.cpp @@ -63,7 +63,7 @@ void center_of_mass(const SegmentArray& segments, SkPoint* c) { p0 = segments[0].endPt(); SkPoint pi; SkPoint pj; - // the first and last interation of the below loop would compute + // the first and last iteration of the below loop would compute // zeros since the starting / ending point is (0,0). So instead we start // at i=1 and make the last iteration i=count-2. pj = segments[1].endPt() - p0; @@ -200,24 +200,20 @@ void update_degenerate_test(DegenerateTestData* data, const GrPoint& pt) { } } -inline SkPath::Direction get_direction(const SkPath& path, const GrMatrix& m) { - SkPath::Direction dir; - GR_DEBUGCODE(bool succeeded = ) - path.cheapComputeDirection(&dir); - GrAssert(succeeded); +inline bool get_direction(const SkPath& path, const GrMatrix& m, SkPath::Direction* dir) { + if (!path.cheapComputeDirection(dir)) { + return false; + } // check whether m reverses the orientation GrAssert(!m.hasPerspective()); - GrScalar det2x2 = - GrMul(m.get(SkMatrix::kMScaleX), m.get(SkMatrix::kMScaleY)) - - GrMul(m.get(SkMatrix::kMSkewX), m.get(SkMatrix::kMSkewY)); + GrScalar det2x2 = GrMul(m.get(SkMatrix::kMScaleX), m.get(SkMatrix::kMScaleY)) - + GrMul(m.get(SkMatrix::kMSkewX), m.get(SkMatrix::kMSkewY)); if (det2x2 < 0) { - GR_STATIC_ASSERT(0 == SkPath::kCW_Direction || - 1 == SkPath::kCW_Direction); - GR_STATIC_ASSERT(0 == SkPath::kCCW_Direction || - 1 == SkPath::kCCW_Direction); - dir = static_cast(dir ^ 0x1); + GR_STATIC_ASSERT(0 == SkPath::kCW_Direction || 1 == SkPath::kCW_Direction); + GR_STATIC_ASSERT(0 == SkPath::kCCW_Direction || 1 == SkPath::kCCW_Direction); + *dir = static_cast(*dir ^ 0x1); } - return dir; + return true; } bool get_segments(const SkPath& path, @@ -235,6 +231,11 @@ bool get_segments(const SkPath& path, // line paths. We detect paths that are very close to a line (zero area) and // draw nothing. DegenerateTestData degenerateData; + SkPath::Direction dir; + // get_direction can fail for some degenerate paths. + if (!get_direction(path, m, &dir)) { + return false; + } for (;;) { GrPoint pts[4]; @@ -269,7 +270,7 @@ bool get_segments(const SkPath& path, // unlike quads and lines, the pts[0] will also be read (in // convertCubicToQuads). SkSTArray<15, SkPoint, true> quads; - GrPathUtils::convertCubicToQuads(pts, SK_Scalar1, &quads); + GrPathUtils::convertCubicToQuads(pts, SK_Scalar1, true, dir, &quads); int count = quads.count(); for (int q = 0; q < count; q += 3) { segments->push_back(); @@ -283,7 +284,6 @@ bool get_segments(const SkPath& path, if (degenerateData.isDegenerate()) { return false; } else { - SkPath::Direction dir = get_direction(path, m); compute_vectors(segments, fanPt, dir, vCount, iCount); return true; } diff --git a/src/gpu/GrAAHairLinePathRenderer.cpp b/src/gpu/GrAAHairLinePathRenderer.cpp index 8aed4b03db..1731db5fbb 100644 --- a/src/gpu/GrAAHairLinePathRenderer.cpp +++ b/src/gpu/GrAAHairLinePathRenderer.cpp @@ -255,7 +255,7 @@ int generate_lines_and_quads(const SkPath& path, totalQuadCount += 1 << subdiv; } } - break; + break; case kCubic_PathCmd: SkPoint::Offset(pts, 4, translate); m.mapPoints(devPts, pts, 4); @@ -264,15 +264,17 @@ int generate_lines_and_quads(const SkPath& path, bounds.roundOut(&ibounds); if (SkIRect::Intersects(clip, ibounds)) { PREALLOC_PTARRAY(32) q; + // we don't need a direction if we aren't constraining the subdivision + static const SkPath::Direction kDummyDir = SkPath::kCCW_Direction; // We convert cubics to quadratics (for now). // In perspective have to do conversion in src space. if (persp) { SkScalar tolScale = GrPathUtils::scaleToleranceToSrc(SK_Scalar1, m, path.getBounds()); - GrPathUtils::convertCubicToQuads(pts, tolScale, &q); + GrPathUtils::convertCubicToQuads(pts, tolScale, false, kDummyDir, &q); } else { - GrPathUtils::convertCubicToQuads(devPts, SK_Scalar1, &q); + GrPathUtils::convertCubicToQuads(devPts, SK_Scalar1, false, kDummyDir, &q); } for (int i = 0; i < q.count(); i += 3) { SkPoint* qInDevSpace; @@ -311,7 +313,7 @@ int generate_lines_and_quads(const SkPath& path, } } } - break; + break; case kClose_PathCmd: break; case kEnd_PathCmd: diff --git a/src/gpu/GrPathUtils.cpp b/src/gpu/GrPathUtils.cpp index 4e487fd076..53e5e13b4d 100644 --- a/src/gpu/GrPathUtils.cpp +++ b/src/gpu/GrPathUtils.cpp @@ -277,60 +277,156 @@ void GrPathUtils::QuadUVMatrix::set(const GrPoint qPts[3]) { } namespace { + +// a is the first control point of the cubic. +// ab is the vector from a to the second control point. +// dc is the vector from the fourth to the third control point. +// d is the fourth control point. +// p is the candidate quadratic control point. +// this assumes that the cubic doesn't inflect and is simple +bool is_point_within_cubic_tangents(const SkPoint& a, + const SkVector& ab, + const SkVector& dc, + const SkPoint& d, + SkPath::Direction dir, + const SkPoint p) { + SkVector ap = p - a; + SkScalar apXab = ap.cross(ab); + if (SkPath::kCW_Direction == dir) { + if (apXab > 0) { + return false; + } + } else { + GrAssert(SkPath::kCCW_Direction == dir); + if (apXab < 0) { + return false; + } + } + + SkVector dp = p - d; + SkScalar dpXdc = dp.cross(dc); + if (SkPath::kCW_Direction == dir) { + if (dpXdc < 0) { + return false; + } + } else { + GrAssert(SkPath::kCCW_Direction == dir); + if (dpXdc > 0) { + return false; + } + } + return true; +} + void convert_noninflect_cubic_to_quads(const SkPoint p[4], - SkScalar tolScale, + SkScalar toleranceSqd, + bool constrainWithinTangents, + SkPath::Direction dir, SkTArray* quads, int sublevel = 0) { - SkVector ab = p[1]; - ab -= p[0]; - SkVector dc = p[2]; - dc -= p[3]; - - static const SkScalar gLengthScale = 3 * SK_Scalar1 / 2; - // base tolerance is 2 pixels in dev coords. - const SkScalar distanceSqdTol = SkScalarMul(tolScale, 1 * SK_Scalar1); + SkVector ab = p[1] - p[0]; + SkVector dc = p[2] - p[3]; + + if (ab.isZero()) { + if (dc.isZero()) { + SkPoint* degQuad = quads->push_back_n(3); + degQuad[0] = p[0]; + degQuad[1] = p[0]; + degQuad[2] = p[3]; + return; + } + ab = p[2] - p[0]; + } + if (dc.isZero()) { + dc = p[1] - p[3]; + } + + static const SkScalar kLengthScale = 3 * SK_Scalar1 / 2; static const int kMaxSubdivs = 10; - ab.scale(gLengthScale); - dc.scale(gLengthScale); + ab.scale(kLengthScale); + dc.scale(kLengthScale); + // e0 and e1 are extrapolations along vectors ab and dc. SkVector c0 = p[0]; c0 += ab; SkVector c1 = p[3]; c1 += dc; - SkScalar dSqd = c0.distanceToSqd(c1); - if (sublevel > kMaxSubdivs || dSqd <= distanceSqdTol) { + SkScalar dSqd = sublevel > kMaxSubdivs ? toleranceSqd : c0.distanceToSqd(c1); + if (dSqd < toleranceSqd) { SkPoint cAvg = c0; cAvg += c1; cAvg.scale(SK_ScalarHalf); - SkPoint* pts = quads->push_back_n(3); - pts[0] = p[0]; - pts[1] = cAvg; - pts[2] = p[3]; - - return; - } else { - SkPoint choppedPts[7]; - SkChopCubicAtHalf(p, choppedPts); - convert_noninflect_cubic_to_quads(choppedPts + 0, tolScale, - quads, sublevel + 1); - convert_noninflect_cubic_to_quads(choppedPts + 3, tolScale, - quads, sublevel + 1); + bool subdivide = false; + + if (constrainWithinTangents && + !is_point_within_cubic_tangents(p[0], ab, dc, p[3], dir, cAvg)) { + // choose a new cAvg that is the intersection of the two tangent + // lines. + ab.setOrthog(ab); + SkScalar z0 = -ab.dot(p[0]); + dc.setOrthog(dc); + SkScalar z1 = -dc.dot(p[3]); + cAvg.fX = SkScalarMul(ab.fY, z1) - SkScalarMul(z0, dc.fY); + cAvg.fY = SkScalarMul(z0, dc.fX) - SkScalarMul(ab.fX, z1); + SkScalar z = SkScalarMul(ab.fX, dc.fY) - SkScalarMul(ab.fY, dc.fX); + z = SkScalarInvert(z); + cAvg.fX *= z; + cAvg.fY *= z; + if (sublevel <= kMaxSubdivs) { + SkScalar d0Sqd = c0.distanceToSqd(cAvg); + SkScalar d1Sqd = c1.distanceToSqd(cAvg); + // We need to subdivide if d0 + d1 > tolerance but we have the + // sqd values. We know the distances and tolerance can't be + // negative. + // (d0 + d1)^2 > toleranceSqd + // d0Sqd + 2*d0*d1 + d1Sqd > toleranceSqd + SkScalar d0d1 = SkScalarSqrt(SkScalarMul(d0Sqd, d1Sqd)); + subdivide = 2 * d0d1 + d0Sqd + d1Sqd > toleranceSqd; + } + } + if (!subdivide) { + SkPoint* pts = quads->push_back_n(3); + pts[0] = p[0]; + pts[1] = cAvg; + pts[2] = p[3]; + return; + } } + SkPoint choppedPts[7]; + SkChopCubicAtHalf(p, choppedPts); + convert_noninflect_cubic_to_quads(choppedPts + 0, + toleranceSqd, + constrainWithinTangents, + dir, + quads, + sublevel + 1); + convert_noninflect_cubic_to_quads(choppedPts + 3, + toleranceSqd, + constrainWithinTangents, + dir, + quads, + sublevel + 1); } } void GrPathUtils::convertCubicToQuads(const GrPoint p[4], SkScalar tolScale, + bool constrainWithinTangents, + SkPath::Direction dir, SkTArray* quads) { SkPoint chopped[10]; int count = SkChopCubicAtInflections(p, chopped); + // base tolerance is 1 pixel. + static const SkScalar kTolerance = SK_Scalar1; + const SkScalar tolSqd = SkScalarSquare(SkScalarMul(tolScale, kTolerance)); + for (int i = 0; i < count; ++i) { SkPoint* cubic = chopped + 3*i; - convert_noninflect_cubic_to_quads(cubic, tolScale, quads); + convert_noninflect_cubic_to_quads(cubic, tolSqd, constrainWithinTangents, dir, quads); } } diff --git a/src/gpu/GrPathUtils.h b/src/gpu/GrPathUtils.h index a1d0eb630b..31b639864e 100644 --- a/src/gpu/GrPathUtils.h +++ b/src/gpu/GrPathUtils.h @@ -96,12 +96,23 @@ namespace GrPathUtils { float fM[6]; }; + // Converts a cubic into a sequence of quads. If working in device space // use tolScale = 1, otherwise set based on stretchiness of the matrix. The // result is sets of 3 points in quads (TODO: share endpoints in returned // array) + // When we approximate a cubic {a,b,c,d} with a quadratic we may have to + // ensure that the new control point lies between the lines ab and cd. The + // convex path renderer requires this. It starts with a path where all the + // control points taken together form a convex polygon. It relies on this + // property and the quadratic approximation of cubics step cannot alter it. + // Setting constrainWithinTangents to true enforces this property. When this + // is true the cubic must be simple and dir must specify the orientation of + // the cubic. Otherwise, dir is ignored. void convertCubicToQuads(const GrPoint p[4], SkScalar tolScale, + bool constrainWithinTangents, + SkPath::Direction dir, SkTArray* quads); }; #endif -- cgit v1.2.3