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
diff --git a/gm/convexpaths.cpp b/gm/convexpaths.cpp
index ebe715d..d1c6aee 100644
--- a/gm/convexpaths.cpp
+++ b/gm/convexpaths.cpp
@@ -134,7 +134,6 @@
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 @@
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 ae4a773..41ab242 100644
--- a/src/gpu/GrAAConvexPathRenderer.cpp
+++ b/src/gpu/GrAAConvexPathRenderer.cpp
@@ -63,7 +63,7 @@
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 @@
}
}
-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<SkPath::Direction>(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<SkPath::Direction>(*dir ^ 0x1);
}
- return dir;
+ return true;
}
bool get_segments(const SkPath& path,
@@ -235,6 +231,11 @@
// 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 @@
// 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 @@
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 8aed4b0..1731db5 100644
--- a/src/gpu/GrAAHairLinePathRenderer.cpp
+++ b/src/gpu/GrAAHairLinePathRenderer.cpp
@@ -255,7 +255,7 @@
totalQuadCount += 1 << subdiv;
}
}
- break;
+ break;
case kCubic_PathCmd:
SkPoint::Offset(pts, 4, translate);
m.mapPoints(devPts, pts, 4);
@@ -264,15 +264,17 @@
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 @@
}
}
}
- break;
+ break;
case kClose_PathCmd:
break;
case kEnd_PathCmd:
diff --git a/src/gpu/GrPathUtils.cpp b/src/gpu/GrPathUtils.cpp
index 4e487fd..53e5e13 100644
--- a/src/gpu/GrPathUtils.cpp
+++ b/src/gpu/GrPathUtils.cpp
@@ -277,60 +277,156 @@
}
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<SkPoint, true>* quads,
int sublevel = 0) {
- SkVector ab = p[1];
- ab -= p[0];
- SkVector dc = p[2];
- dc -= p[3];
+ SkVector ab = p[1] - p[0];
+ SkVector dc = p[2] - 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);
+ 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];
+ bool subdivide = false;
- 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);
+ 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<SkPoint, true>* 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 a1d0eb6..31b6398 100644
--- a/src/gpu/GrPathUtils.h
+++ b/src/gpu/GrPathUtils.h
@@ -96,12 +96,23 @@
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<SkPoint, true>* quads);
};
#endif