187b8e645865f9633f410c02252a0fd3feb18f09bDerek Sollenberger 21cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger/* 31cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger * Copyright 2011 Google Inc. 41cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger * 51cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger * Use of this source code is governed by a BSD-style license that can be 61cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger * found in the LICENSE file. 787b8e645865f9633f410c02252a0fd3feb18f09bDerek Sollenberger */ 887b8e645865f9633f410c02252a0fd3feb18f09bDerek Sollenberger 91cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger 1087b8e645865f9633f410c02252a0fd3feb18f09bDerek Sollenberger#include "GrPathUtils.h" 1187b8e645865f9633f410c02252a0fd3feb18f09bDerek Sollenberger#include "GrPoint.h" 124f1dae40e24d57d647db01443b8bf2410514b8b5Derek Sollenberger#include "SkGeometry.h" 1387b8e645865f9633f410c02252a0fd3feb18f09bDerek Sollenberger 141cab2921ab279367f8206cdadc9259d12e603548Derek SollenbergerGrScalar GrPathUtils::scaleToleranceToSrc(GrScalar devTol, 151cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger const GrMatrix& viewM, 161cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger const GrRect& pathBounds) { 171cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger // In order to tesselate the path we get a bound on how much the matrix can 181cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger // stretch when mapping to screen coordinates. 191cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger GrScalar stretch = viewM.getMaxStretch(); 201cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger GrScalar srcTol = devTol; 211cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger 221cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger if (stretch < 0) { 231cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger // take worst case mapRadius amoung four corners. 241cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger // (less than perfect) 251cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger for (int i = 0; i < 4; ++i) { 261cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger GrMatrix mat; 271cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger mat.setTranslate((i % 2) ? pathBounds.fLeft : pathBounds.fRight, 281cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger (i < 2) ? pathBounds.fTop : pathBounds.fBottom); 291cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger mat.postConcat(viewM); 301cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger stretch = SkMaxScalar(stretch, mat.mapRadius(SK_Scalar1)); 311cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger } 321cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger } 331cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger srcTol = GrScalarDiv(srcTol, stretch); 341cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger return srcTol; 351cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger} 3687b8e645865f9633f410c02252a0fd3feb18f09bDerek Sollenberger 371cab2921ab279367f8206cdadc9259d12e603548Derek Sollenbergerstatic const int MAX_POINTS_PER_CURVE = 1 << 10; 381cab2921ab279367f8206cdadc9259d12e603548Derek Sollenbergerstatic const GrScalar gMinCurveTol = GrFloatToScalar(0.0001f); 3987b8e645865f9633f410c02252a0fd3feb18f09bDerek Sollenberger 4087b8e645865f9633f410c02252a0fd3feb18f09bDerek Sollenbergeruint32_t GrPathUtils::quadraticPointCount(const GrPoint points[], 411cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger GrScalar tol) { 421cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger if (tol < gMinCurveTol) { 431cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger tol = gMinCurveTol; 441cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger } 451cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger GrAssert(tol > 0); 461cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger 4787b8e645865f9633f410c02252a0fd3feb18f09bDerek Sollenberger GrScalar d = points[1].distanceToLineSegmentBetween(points[0], points[2]); 481cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger if (d <= tol) { 4987b8e645865f9633f410c02252a0fd3feb18f09bDerek Sollenberger return 1; 5087b8e645865f9633f410c02252a0fd3feb18f09bDerek Sollenberger } else { 5187b8e645865f9633f410c02252a0fd3feb18f09bDerek Sollenberger // Each time we subdivide, d should be cut in 4. So we need to 5287b8e645865f9633f410c02252a0fd3feb18f09bDerek Sollenberger // subdivide x = log4(d/tol) times. x subdivisions creates 2^(x) 5387b8e645865f9633f410c02252a0fd3feb18f09bDerek Sollenberger // points. 5487b8e645865f9633f410c02252a0fd3feb18f09bDerek Sollenberger // 2^(log4(x)) = sqrt(x); 550b15698a8c76bb8abc1b555c1d91892669b4118fDerek Sollenberger int temp = SkScalarCeil(SkScalarSqrt(SkScalarDiv(d, tol))); 561cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger int pow2 = GrNextPow2(temp); 571cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger // Because of NaNs & INFs we can wind up with a degenerate temp 581cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger // such that pow2 comes out negative. Also, our point generator 591cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger // will always output at least one pt. 601cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger if (pow2 < 1) { 611cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger pow2 = 1; 621cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger } 631cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger return GrMin(pow2, MAX_POINTS_PER_CURVE); 6487b8e645865f9633f410c02252a0fd3feb18f09bDerek Sollenberger } 6587b8e645865f9633f410c02252a0fd3feb18f09bDerek Sollenberger} 6687b8e645865f9633f410c02252a0fd3feb18f09bDerek Sollenberger 6787b8e645865f9633f410c02252a0fd3feb18f09bDerek Sollenbergeruint32_t GrPathUtils::generateQuadraticPoints(const GrPoint& p0, 681cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger const GrPoint& p1, 691cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger const GrPoint& p2, 701cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger GrScalar tolSqd, 711cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger GrPoint** points, 721cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger uint32_t pointsLeft) { 7387b8e645865f9633f410c02252a0fd3feb18f09bDerek Sollenberger if (pointsLeft < 2 || 7487b8e645865f9633f410c02252a0fd3feb18f09bDerek Sollenberger (p1.distanceToLineSegmentBetweenSqd(p0, p2)) < tolSqd) { 7587b8e645865f9633f410c02252a0fd3feb18f09bDerek Sollenberger (*points)[0] = p2; 7687b8e645865f9633f410c02252a0fd3feb18f09bDerek Sollenberger *points += 1; 7787b8e645865f9633f410c02252a0fd3feb18f09bDerek Sollenberger return 1; 7887b8e645865f9633f410c02252a0fd3feb18f09bDerek Sollenberger } 7987b8e645865f9633f410c02252a0fd3feb18f09bDerek Sollenberger 8087b8e645865f9633f410c02252a0fd3feb18f09bDerek Sollenberger GrPoint q[] = { 8135e2e62b55598210f6999fc2ea26ff8f41446ffeDerek Sollenberger { GrScalarAve(p0.fX, p1.fX), GrScalarAve(p0.fY, p1.fY) }, 8235e2e62b55598210f6999fc2ea26ff8f41446ffeDerek Sollenberger { GrScalarAve(p1.fX, p2.fX), GrScalarAve(p1.fY, p2.fY) }, 8387b8e645865f9633f410c02252a0fd3feb18f09bDerek Sollenberger }; 8435e2e62b55598210f6999fc2ea26ff8f41446ffeDerek Sollenberger GrPoint r = { GrScalarAve(q[0].fX, q[1].fX), GrScalarAve(q[0].fY, q[1].fY) }; 8587b8e645865f9633f410c02252a0fd3feb18f09bDerek Sollenberger 8687b8e645865f9633f410c02252a0fd3feb18f09bDerek Sollenberger pointsLeft >>= 1; 8787b8e645865f9633f410c02252a0fd3feb18f09bDerek Sollenberger uint32_t a = generateQuadraticPoints(p0, q[0], r, tolSqd, points, pointsLeft); 8887b8e645865f9633f410c02252a0fd3feb18f09bDerek Sollenberger uint32_t b = generateQuadraticPoints(r, q[1], p2, tolSqd, points, pointsLeft); 8987b8e645865f9633f410c02252a0fd3feb18f09bDerek Sollenberger return a + b; 9087b8e645865f9633f410c02252a0fd3feb18f09bDerek Sollenberger} 9187b8e645865f9633f410c02252a0fd3feb18f09bDerek Sollenberger 9287b8e645865f9633f410c02252a0fd3feb18f09bDerek Sollenbergeruint32_t GrPathUtils::cubicPointCount(const GrPoint points[], 9387b8e645865f9633f410c02252a0fd3feb18f09bDerek Sollenberger GrScalar tol) { 941cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger if (tol < gMinCurveTol) { 951cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger tol = gMinCurveTol; 961cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger } 971cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger GrAssert(tol > 0); 981cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger 991cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger GrScalar d = GrMax( 1001cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger points[1].distanceToLineSegmentBetweenSqd(points[0], points[3]), 1011cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger points[2].distanceToLineSegmentBetweenSqd(points[0], points[3])); 1020b15698a8c76bb8abc1b555c1d91892669b4118fDerek Sollenberger d = SkScalarSqrt(d); 1031cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger if (d <= tol) { 10487b8e645865f9633f410c02252a0fd3feb18f09bDerek Sollenberger return 1; 10587b8e645865f9633f410c02252a0fd3feb18f09bDerek Sollenberger } else { 1060b15698a8c76bb8abc1b555c1d91892669b4118fDerek Sollenberger int temp = SkScalarCeil(SkScalarSqrt(SkScalarDiv(d, tol))); 1071cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger int pow2 = GrNextPow2(temp); 1081cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger // Because of NaNs & INFs we can wind up with a degenerate temp 1091cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger // such that pow2 comes out negative. Also, our point generator 1101cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger // will always output at least one pt. 1111cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger if (pow2 < 1) { 1121cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger pow2 = 1; 1131cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger } 1141cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger return GrMin(pow2, MAX_POINTS_PER_CURVE); 11587b8e645865f9633f410c02252a0fd3feb18f09bDerek Sollenberger } 11687b8e645865f9633f410c02252a0fd3feb18f09bDerek Sollenberger} 11787b8e645865f9633f410c02252a0fd3feb18f09bDerek Sollenberger 11887b8e645865f9633f410c02252a0fd3feb18f09bDerek Sollenbergeruint32_t GrPathUtils::generateCubicPoints(const GrPoint& p0, 1191cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger const GrPoint& p1, 1201cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger const GrPoint& p2, 1211cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger const GrPoint& p3, 1221cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger GrScalar tolSqd, 1231cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger GrPoint** points, 1241cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger uint32_t pointsLeft) { 12587b8e645865f9633f410c02252a0fd3feb18f09bDerek Sollenberger if (pointsLeft < 2 || 12687b8e645865f9633f410c02252a0fd3feb18f09bDerek Sollenberger (p1.distanceToLineSegmentBetweenSqd(p0, p3) < tolSqd && 12787b8e645865f9633f410c02252a0fd3feb18f09bDerek Sollenberger p2.distanceToLineSegmentBetweenSqd(p0, p3) < tolSqd)) { 12887b8e645865f9633f410c02252a0fd3feb18f09bDerek Sollenberger (*points)[0] = p3; 12987b8e645865f9633f410c02252a0fd3feb18f09bDerek Sollenberger *points += 1; 13087b8e645865f9633f410c02252a0fd3feb18f09bDerek Sollenberger return 1; 13187b8e645865f9633f410c02252a0fd3feb18f09bDerek Sollenberger } 13287b8e645865f9633f410c02252a0fd3feb18f09bDerek Sollenberger GrPoint q[] = { 13335e2e62b55598210f6999fc2ea26ff8f41446ffeDerek Sollenberger { GrScalarAve(p0.fX, p1.fX), GrScalarAve(p0.fY, p1.fY) }, 13435e2e62b55598210f6999fc2ea26ff8f41446ffeDerek Sollenberger { GrScalarAve(p1.fX, p2.fX), GrScalarAve(p1.fY, p2.fY) }, 13535e2e62b55598210f6999fc2ea26ff8f41446ffeDerek Sollenberger { GrScalarAve(p2.fX, p3.fX), GrScalarAve(p2.fY, p3.fY) } 13687b8e645865f9633f410c02252a0fd3feb18f09bDerek Sollenberger }; 13787b8e645865f9633f410c02252a0fd3feb18f09bDerek Sollenberger GrPoint r[] = { 13835e2e62b55598210f6999fc2ea26ff8f41446ffeDerek Sollenberger { GrScalarAve(q[0].fX, q[1].fX), GrScalarAve(q[0].fY, q[1].fY) }, 13935e2e62b55598210f6999fc2ea26ff8f41446ffeDerek Sollenberger { GrScalarAve(q[1].fX, q[2].fX), GrScalarAve(q[1].fY, q[2].fY) } 14087b8e645865f9633f410c02252a0fd3feb18f09bDerek Sollenberger }; 14135e2e62b55598210f6999fc2ea26ff8f41446ffeDerek Sollenberger GrPoint s = { GrScalarAve(r[0].fX, r[1].fX), GrScalarAve(r[0].fY, r[1].fY) }; 14287b8e645865f9633f410c02252a0fd3feb18f09bDerek Sollenberger pointsLeft >>= 1; 14387b8e645865f9633f410c02252a0fd3feb18f09bDerek Sollenberger uint32_t a = generateCubicPoints(p0, q[0], r[0], s, tolSqd, points, pointsLeft); 14487b8e645865f9633f410c02252a0fd3feb18f09bDerek Sollenberger uint32_t b = generateCubicPoints(s, r[1], q[2], p3, tolSqd, points, pointsLeft); 14587b8e645865f9633f410c02252a0fd3feb18f09bDerek Sollenberger return a + b; 14687b8e645865f9633f410c02252a0fd3feb18f09bDerek Sollenberger} 14787b8e645865f9633f410c02252a0fd3feb18f09bDerek Sollenberger 1480b15698a8c76bb8abc1b555c1d91892669b4118fDerek Sollenbergerint GrPathUtils::worstCasePointCount(const GrPath& path, int* subpaths, 1490b15698a8c76bb8abc1b555c1d91892669b4118fDerek Sollenberger GrScalar tol) { 1501cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger if (tol < gMinCurveTol) { 1511cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger tol = gMinCurveTol; 1521cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger } 1531cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger GrAssert(tol > 0); 1541cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger 15587b8e645865f9633f410c02252a0fd3feb18f09bDerek Sollenberger int pointCount = 0; 15687b8e645865f9633f410c02252a0fd3feb18f09bDerek Sollenberger *subpaths = 1; 15787b8e645865f9633f410c02252a0fd3feb18f09bDerek Sollenberger 15887b8e645865f9633f410c02252a0fd3feb18f09bDerek Sollenberger bool first = true; 15987b8e645865f9633f410c02252a0fd3feb18f09bDerek Sollenberger 1601cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger SkPath::Iter iter(path, false); 16187b8e645865f9633f410c02252a0fd3feb18f09bDerek Sollenberger GrPathCmd cmd; 16287b8e645865f9633f410c02252a0fd3feb18f09bDerek Sollenberger 16387b8e645865f9633f410c02252a0fd3feb18f09bDerek Sollenberger GrPoint pts[4]; 1640b15698a8c76bb8abc1b555c1d91892669b4118fDerek Sollenberger while ((cmd = (GrPathCmd)iter.next(pts)) != kEnd_PathCmd) { 16587b8e645865f9633f410c02252a0fd3feb18f09bDerek Sollenberger 16687b8e645865f9633f410c02252a0fd3feb18f09bDerek Sollenberger switch (cmd) { 16787b8e645865f9633f410c02252a0fd3feb18f09bDerek Sollenberger case kLine_PathCmd: 16887b8e645865f9633f410c02252a0fd3feb18f09bDerek Sollenberger pointCount += 1; 16987b8e645865f9633f410c02252a0fd3feb18f09bDerek Sollenberger break; 17087b8e645865f9633f410c02252a0fd3feb18f09bDerek Sollenberger case kQuadratic_PathCmd: 17187b8e645865f9633f410c02252a0fd3feb18f09bDerek Sollenberger pointCount += quadraticPointCount(pts, tol); 17287b8e645865f9633f410c02252a0fd3feb18f09bDerek Sollenberger break; 17387b8e645865f9633f410c02252a0fd3feb18f09bDerek Sollenberger case kCubic_PathCmd: 17487b8e645865f9633f410c02252a0fd3feb18f09bDerek Sollenberger pointCount += cubicPointCount(pts, tol); 17587b8e645865f9633f410c02252a0fd3feb18f09bDerek Sollenberger break; 17687b8e645865f9633f410c02252a0fd3feb18f09bDerek Sollenberger case kMove_PathCmd: 17787b8e645865f9633f410c02252a0fd3feb18f09bDerek Sollenberger pointCount += 1; 17887b8e645865f9633f410c02252a0fd3feb18f09bDerek Sollenberger if (!first) { 17987b8e645865f9633f410c02252a0fd3feb18f09bDerek Sollenberger ++(*subpaths); 18087b8e645865f9633f410c02252a0fd3feb18f09bDerek Sollenberger } 18187b8e645865f9633f410c02252a0fd3feb18f09bDerek Sollenberger break; 18287b8e645865f9633f410c02252a0fd3feb18f09bDerek Sollenberger default: 18387b8e645865f9633f410c02252a0fd3feb18f09bDerek Sollenberger break; 18487b8e645865f9633f410c02252a0fd3feb18f09bDerek Sollenberger } 18587b8e645865f9633f410c02252a0fd3feb18f09bDerek Sollenberger first = false; 18687b8e645865f9633f410c02252a0fd3feb18f09bDerek Sollenberger } 18787b8e645865f9633f410c02252a0fd3feb18f09bDerek Sollenberger return pointCount; 18887b8e645865f9633f410c02252a0fd3feb18f09bDerek Sollenberger} 1894f1dae40e24d57d647db01443b8bf2410514b8b5Derek Sollenberger 1904f1dae40e24d57d647db01443b8bf2410514b8b5Derek Sollenbergernamespace { 1914f1dae40e24d57d647db01443b8bf2410514b8b5Derek Sollenberger// The matrix computed for quadDesignSpaceToUVCoordsMatrix should never really 1924f1dae40e24d57d647db01443b8bf2410514b8b5Derek Sollenberger// have perspective and we really want to avoid perspective matrix muls. 1934f1dae40e24d57d647db01443b8bf2410514b8b5Derek Sollenberger// However, the first two entries of the perspective row may be really close to 1944f1dae40e24d57d647db01443b8bf2410514b8b5Derek Sollenberger// 0 and the third may not be 1 due to a scale on the entire matrix. 1954f1dae40e24d57d647db01443b8bf2410514b8b5Derek Sollenbergerinline void fixup_matrix(GrMatrix* mat) { 1964f1dae40e24d57d647db01443b8bf2410514b8b5Derek Sollenberger#ifndef SK_SCALAR_IS_FLOAT 1974f1dae40e24d57d647db01443b8bf2410514b8b5Derek Sollenberger GrCrash("Expected scalar is float."); 1984f1dae40e24d57d647db01443b8bf2410514b8b5Derek Sollenberger#endif 1994f1dae40e24d57d647db01443b8bf2410514b8b5Derek Sollenberger static const GrScalar gTOL = 1.f / 100.f; 2004f1dae40e24d57d647db01443b8bf2410514b8b5Derek Sollenberger GrAssert(GrScalarAbs(mat->get(SkMatrix::kMPersp0)) < gTOL); 2014f1dae40e24d57d647db01443b8bf2410514b8b5Derek Sollenberger GrAssert(GrScalarAbs(mat->get(SkMatrix::kMPersp1)) < gTOL); 2024f1dae40e24d57d647db01443b8bf2410514b8b5Derek Sollenberger float m33 = mat->get(SkMatrix::kMPersp2); 2034f1dae40e24d57d647db01443b8bf2410514b8b5Derek Sollenberger if (1.f != m33) { 2044f1dae40e24d57d647db01443b8bf2410514b8b5Derek Sollenberger m33 = 1.f / m33; 2054f1dae40e24d57d647db01443b8bf2410514b8b5Derek Sollenberger mat->setAll(m33 * mat->get(SkMatrix::kMScaleX), 2064f1dae40e24d57d647db01443b8bf2410514b8b5Derek Sollenberger m33 * mat->get(SkMatrix::kMSkewX), 2074f1dae40e24d57d647db01443b8bf2410514b8b5Derek Sollenberger m33 * mat->get(SkMatrix::kMTransX), 2084f1dae40e24d57d647db01443b8bf2410514b8b5Derek Sollenberger m33 * mat->get(SkMatrix::kMSkewY), 2094f1dae40e24d57d647db01443b8bf2410514b8b5Derek Sollenberger m33 * mat->get(SkMatrix::kMScaleY), 2104f1dae40e24d57d647db01443b8bf2410514b8b5Derek Sollenberger m33 * mat->get(SkMatrix::kMTransY), 2114f1dae40e24d57d647db01443b8bf2410514b8b5Derek Sollenberger 0.f, 0.f, 1.f); 2124f1dae40e24d57d647db01443b8bf2410514b8b5Derek Sollenberger } else { 2134f1dae40e24d57d647db01443b8bf2410514b8b5Derek Sollenberger mat->setPerspX(0); 2144f1dae40e24d57d647db01443b8bf2410514b8b5Derek Sollenberger mat->setPerspY(0); 2154f1dae40e24d57d647db01443b8bf2410514b8b5Derek Sollenberger } 2164f1dae40e24d57d647db01443b8bf2410514b8b5Derek Sollenberger} 2174f1dae40e24d57d647db01443b8bf2410514b8b5Derek Sollenberger} 2184f1dae40e24d57d647db01443b8bf2410514b8b5Derek Sollenberger 2194f1dae40e24d57d647db01443b8bf2410514b8b5Derek Sollenberger// Compute a matrix that goes from the 2d space coordinates to UV space where 2204f1dae40e24d57d647db01443b8bf2410514b8b5Derek Sollenberger// u^2-v = 0 specifies the quad. 2214f1dae40e24d57d647db01443b8bf2410514b8b5Derek Sollenbergervoid GrPathUtils::quadDesignSpaceToUVCoordsMatrix(const SkPoint qPts[3], 2224f1dae40e24d57d647db01443b8bf2410514b8b5Derek Sollenberger GrMatrix* matrix) { 2234f1dae40e24d57d647db01443b8bf2410514b8b5Derek Sollenberger // can't make this static, no cons :( 2244f1dae40e24d57d647db01443b8bf2410514b8b5Derek Sollenberger SkMatrix UVpts; 2254f1dae40e24d57d647db01443b8bf2410514b8b5Derek Sollenberger#ifndef SK_SCALAR_IS_FLOAT 2264f1dae40e24d57d647db01443b8bf2410514b8b5Derek Sollenberger GrCrash("Expected scalar is float."); 2274f1dae40e24d57d647db01443b8bf2410514b8b5Derek Sollenberger#endif 2284f1dae40e24d57d647db01443b8bf2410514b8b5Derek Sollenberger // We want M such that M * xy_pt = uv_pt 2294f1dae40e24d57d647db01443b8bf2410514b8b5Derek Sollenberger // We know M * control_pts = [0 1/2 1] 2304f1dae40e24d57d647db01443b8bf2410514b8b5Derek Sollenberger // [0 0 1] 2314f1dae40e24d57d647db01443b8bf2410514b8b5Derek Sollenberger // [1 1 1] 2324f1dae40e24d57d647db01443b8bf2410514b8b5Derek Sollenberger // We invert the control pt matrix and post concat to both sides to get M. 2334f1dae40e24d57d647db01443b8bf2410514b8b5Derek Sollenberger UVpts.setAll(0, 0.5f, 1.f, 2344f1dae40e24d57d647db01443b8bf2410514b8b5Derek Sollenberger 0, 0, 1.f, 2354f1dae40e24d57d647db01443b8bf2410514b8b5Derek Sollenberger 1.f, 1.f, 1.f); 2364f1dae40e24d57d647db01443b8bf2410514b8b5Derek Sollenberger matrix->setAll(qPts[0].fX, qPts[1].fX, qPts[2].fX, 2374f1dae40e24d57d647db01443b8bf2410514b8b5Derek Sollenberger qPts[0].fY, qPts[1].fY, qPts[2].fY, 2384f1dae40e24d57d647db01443b8bf2410514b8b5Derek Sollenberger 1.f, 1.f, 1.f); 2394f1dae40e24d57d647db01443b8bf2410514b8b5Derek Sollenberger if (!matrix->invert(matrix)) { 2404f1dae40e24d57d647db01443b8bf2410514b8b5Derek Sollenberger // The quad is degenerate. Hopefully this is rare. Find the pts that are 2414f1dae40e24d57d647db01443b8bf2410514b8b5Derek Sollenberger // farthest apart to compute a line (unless it is really a pt). 2424f1dae40e24d57d647db01443b8bf2410514b8b5Derek Sollenberger SkScalar maxD = qPts[0].distanceToSqd(qPts[1]); 2434f1dae40e24d57d647db01443b8bf2410514b8b5Derek Sollenberger int maxEdge = 0; 2444f1dae40e24d57d647db01443b8bf2410514b8b5Derek Sollenberger SkScalar d = qPts[1].distanceToSqd(qPts[2]); 2454f1dae40e24d57d647db01443b8bf2410514b8b5Derek Sollenberger if (d > maxD) { 2464f1dae40e24d57d647db01443b8bf2410514b8b5Derek Sollenberger maxD = d; 2474f1dae40e24d57d647db01443b8bf2410514b8b5Derek Sollenberger maxEdge = 1; 2484f1dae40e24d57d647db01443b8bf2410514b8b5Derek Sollenberger } 2494f1dae40e24d57d647db01443b8bf2410514b8b5Derek Sollenberger d = qPts[2].distanceToSqd(qPts[0]); 2504f1dae40e24d57d647db01443b8bf2410514b8b5Derek Sollenberger if (d > maxD) { 2514f1dae40e24d57d647db01443b8bf2410514b8b5Derek Sollenberger maxD = d; 2524f1dae40e24d57d647db01443b8bf2410514b8b5Derek Sollenberger maxEdge = 2; 2534f1dae40e24d57d647db01443b8bf2410514b8b5Derek Sollenberger } 2544f1dae40e24d57d647db01443b8bf2410514b8b5Derek Sollenberger // We could have a tolerance here, not sure if it would improve anything 2554f1dae40e24d57d647db01443b8bf2410514b8b5Derek Sollenberger if (maxD > 0) { 2564f1dae40e24d57d647db01443b8bf2410514b8b5Derek Sollenberger // Set the matrix to give (u = 0, v = distance_to_line) 2574f1dae40e24d57d647db01443b8bf2410514b8b5Derek Sollenberger GrVec lineVec = qPts[(maxEdge + 1)%3] - qPts[maxEdge]; 2584f1dae40e24d57d647db01443b8bf2410514b8b5Derek Sollenberger // when looking from the point 0 down the line we want positive 2594f1dae40e24d57d647db01443b8bf2410514b8b5Derek Sollenberger // distances to be to the left. This matches the non-degenerate 2604f1dae40e24d57d647db01443b8bf2410514b8b5Derek Sollenberger // case. 2614f1dae40e24d57d647db01443b8bf2410514b8b5Derek Sollenberger lineVec.setOrthog(lineVec, GrPoint::kLeft_Side); 2624f1dae40e24d57d647db01443b8bf2410514b8b5Derek Sollenberger lineVec.dot(qPts[0]); 2634f1dae40e24d57d647db01443b8bf2410514b8b5Derek Sollenberger matrix->setAll(0, 0, 0, 2644f1dae40e24d57d647db01443b8bf2410514b8b5Derek Sollenberger lineVec.fX, lineVec.fY, -lineVec.dot(qPts[maxEdge]), 2654f1dae40e24d57d647db01443b8bf2410514b8b5Derek Sollenberger 0, 0, 1.f); 2664f1dae40e24d57d647db01443b8bf2410514b8b5Derek Sollenberger } else { 2674f1dae40e24d57d647db01443b8bf2410514b8b5Derek Sollenberger // It's a point. It should cover zero area. Just set the matrix such 2684f1dae40e24d57d647db01443b8bf2410514b8b5Derek Sollenberger // that (u, v) will always be far away from the quad. 2694f1dae40e24d57d647db01443b8bf2410514b8b5Derek Sollenberger matrix->setAll(0, 0, 100 * SK_Scalar1, 2704f1dae40e24d57d647db01443b8bf2410514b8b5Derek Sollenberger 0, 0, 100 * SK_Scalar1, 2714f1dae40e24d57d647db01443b8bf2410514b8b5Derek Sollenberger 0, 0, 1.f); 2724f1dae40e24d57d647db01443b8bf2410514b8b5Derek Sollenberger } 2734f1dae40e24d57d647db01443b8bf2410514b8b5Derek Sollenberger } else { 2744f1dae40e24d57d647db01443b8bf2410514b8b5Derek Sollenberger matrix->postConcat(UVpts); 2754f1dae40e24d57d647db01443b8bf2410514b8b5Derek Sollenberger fixup_matrix(matrix); 2764f1dae40e24d57d647db01443b8bf2410514b8b5Derek Sollenberger } 2774f1dae40e24d57d647db01443b8bf2410514b8b5Derek Sollenberger} 2784f1dae40e24d57d647db01443b8bf2410514b8b5Derek Sollenberger 2794f1dae40e24d57d647db01443b8bf2410514b8b5Derek Sollenbergernamespace { 2804f1dae40e24d57d647db01443b8bf2410514b8b5Derek Sollenbergervoid convert_noninflect_cubic_to_quads(const SkPoint p[4], 2814f1dae40e24d57d647db01443b8bf2410514b8b5Derek Sollenberger SkScalar tolScale, 2824f1dae40e24d57d647db01443b8bf2410514b8b5Derek Sollenberger SkTArray<SkPoint, true>* quads, 2834f1dae40e24d57d647db01443b8bf2410514b8b5Derek Sollenberger int sublevel = 0) { 2844f1dae40e24d57d647db01443b8bf2410514b8b5Derek Sollenberger SkVector ab = p[1]; 2854f1dae40e24d57d647db01443b8bf2410514b8b5Derek Sollenberger ab -= p[0]; 2864f1dae40e24d57d647db01443b8bf2410514b8b5Derek Sollenberger SkVector dc = p[2]; 2874f1dae40e24d57d647db01443b8bf2410514b8b5Derek Sollenberger dc -= p[3]; 2884f1dae40e24d57d647db01443b8bf2410514b8b5Derek Sollenberger 2894f1dae40e24d57d647db01443b8bf2410514b8b5Derek Sollenberger static const SkScalar gLengthScale = 3 * SK_Scalar1 / 2; 2904f1dae40e24d57d647db01443b8bf2410514b8b5Derek Sollenberger // base tolerance is 2 pixels in dev coords. 2914f1dae40e24d57d647db01443b8bf2410514b8b5Derek Sollenberger const SkScalar distanceSqdTol = SkScalarMul(tolScale, 1 * SK_Scalar1); 2924f1dae40e24d57d647db01443b8bf2410514b8b5Derek Sollenberger static const int kMaxSubdivs = 10; 2934f1dae40e24d57d647db01443b8bf2410514b8b5Derek Sollenberger 2944f1dae40e24d57d647db01443b8bf2410514b8b5Derek Sollenberger ab.scale(gLengthScale); 2954f1dae40e24d57d647db01443b8bf2410514b8b5Derek Sollenberger dc.scale(gLengthScale); 2964f1dae40e24d57d647db01443b8bf2410514b8b5Derek Sollenberger 2974f1dae40e24d57d647db01443b8bf2410514b8b5Derek Sollenberger SkVector c0 = p[0]; 2984f1dae40e24d57d647db01443b8bf2410514b8b5Derek Sollenberger c0 += ab; 2994f1dae40e24d57d647db01443b8bf2410514b8b5Derek Sollenberger SkVector c1 = p[3]; 3004f1dae40e24d57d647db01443b8bf2410514b8b5Derek Sollenberger c1 += dc; 3014f1dae40e24d57d647db01443b8bf2410514b8b5Derek Sollenberger 3024f1dae40e24d57d647db01443b8bf2410514b8b5Derek Sollenberger SkScalar dSqd = c0.distanceToSqd(c1); 3034f1dae40e24d57d647db01443b8bf2410514b8b5Derek Sollenberger if (sublevel > kMaxSubdivs || dSqd <= distanceSqdTol) { 3044f1dae40e24d57d647db01443b8bf2410514b8b5Derek Sollenberger SkPoint cAvg = c0; 3054f1dae40e24d57d647db01443b8bf2410514b8b5Derek Sollenberger cAvg += c1; 3064f1dae40e24d57d647db01443b8bf2410514b8b5Derek Sollenberger cAvg.scale(SK_ScalarHalf); 3074f1dae40e24d57d647db01443b8bf2410514b8b5Derek Sollenberger 3084f1dae40e24d57d647db01443b8bf2410514b8b5Derek Sollenberger SkPoint* pts = quads->push_back_n(3); 3094f1dae40e24d57d647db01443b8bf2410514b8b5Derek Sollenberger pts[0] = p[0]; 3104f1dae40e24d57d647db01443b8bf2410514b8b5Derek Sollenberger pts[1] = cAvg; 3114f1dae40e24d57d647db01443b8bf2410514b8b5Derek Sollenberger pts[2] = p[3]; 3124f1dae40e24d57d647db01443b8bf2410514b8b5Derek Sollenberger 3134f1dae40e24d57d647db01443b8bf2410514b8b5Derek Sollenberger return; 3144f1dae40e24d57d647db01443b8bf2410514b8b5Derek Sollenberger } else { 3154f1dae40e24d57d647db01443b8bf2410514b8b5Derek Sollenberger SkPoint choppedPts[7]; 3164f1dae40e24d57d647db01443b8bf2410514b8b5Derek Sollenberger SkChopCubicAtHalf(p, choppedPts); 3174f1dae40e24d57d647db01443b8bf2410514b8b5Derek Sollenberger convert_noninflect_cubic_to_quads(choppedPts + 0, tolScale, 3184f1dae40e24d57d647db01443b8bf2410514b8b5Derek Sollenberger quads, sublevel + 1); 3194f1dae40e24d57d647db01443b8bf2410514b8b5Derek Sollenberger convert_noninflect_cubic_to_quads(choppedPts + 3, tolScale, 3204f1dae40e24d57d647db01443b8bf2410514b8b5Derek Sollenberger quads, sublevel + 1); 3214f1dae40e24d57d647db01443b8bf2410514b8b5Derek Sollenberger } 3224f1dae40e24d57d647db01443b8bf2410514b8b5Derek Sollenberger} 3234f1dae40e24d57d647db01443b8bf2410514b8b5Derek Sollenberger} 3244f1dae40e24d57d647db01443b8bf2410514b8b5Derek Sollenberger 3254f1dae40e24d57d647db01443b8bf2410514b8b5Derek Sollenbergervoid GrPathUtils::convertCubicToQuads(const GrPoint p[4], 3264f1dae40e24d57d647db01443b8bf2410514b8b5Derek Sollenberger SkScalar tolScale, 3274f1dae40e24d57d647db01443b8bf2410514b8b5Derek Sollenberger SkTArray<SkPoint, true>* quads) { 3284f1dae40e24d57d647db01443b8bf2410514b8b5Derek Sollenberger SkPoint chopped[10]; 3294f1dae40e24d57d647db01443b8bf2410514b8b5Derek Sollenberger int count = SkChopCubicAtInflections(p, chopped); 3304f1dae40e24d57d647db01443b8bf2410514b8b5Derek Sollenberger 3314f1dae40e24d57d647db01443b8bf2410514b8b5Derek Sollenberger for (int i = 0; i < count; ++i) { 3324f1dae40e24d57d647db01443b8bf2410514b8b5Derek Sollenberger SkPoint* cubic = chopped + 3*i; 3334f1dae40e24d57d647db01443b8bf2410514b8b5Derek Sollenberger convert_noninflect_cubic_to_quads(cubic, tolScale, quads); 3344f1dae40e24d57d647db01443b8bf2410514b8b5Derek Sollenberger } 3354f1dae40e24d57d647db01443b8bf2410514b8b5Derek Sollenberger 3364f1dae40e24d57d647db01443b8bf2410514b8b5Derek Sollenberger} 337