GrPathUtils.cpp revision 972f9cd7a063d0544f8c919fd12b9a3adbd12b24
1152494aea24669a3d74460fa460a4ed45696bc75Guido van Rossum/* 2152494aea24669a3d74460fa460a4ed45696bc75Guido van Rossum * Copyright 2011 Google Inc. 3152494aea24669a3d74460fa460a4ed45696bc75Guido van Rossum * 4152494aea24669a3d74460fa460a4ed45696bc75Guido van Rossum * Use of this source code is governed by a BSD-style license that can be 5152494aea24669a3d74460fa460a4ed45696bc75Guido van Rossum * found in the LICENSE file. 6152494aea24669a3d74460fa460a4ed45696bc75Guido van Rossum */ 7152494aea24669a3d74460fa460a4ed45696bc75Guido van Rossum 8152494aea24669a3d74460fa460a4ed45696bc75Guido van Rossum#include "GrPathUtils.h" 9152494aea24669a3d74460fa460a4ed45696bc75Guido van Rossum 10152494aea24669a3d74460fa460a4ed45696bc75Guido van Rossum#include "GrPoint.h" 11a873b03ebb24076b3664ba694eeed4ab07d176d9Barry Warsaw#include "SkGeometry.h" 12a873b03ebb24076b3664ba694eeed4ab07d176d9Barry Warsaw 13a873b03ebb24076b3664ba694eeed4ab07d176d9Barry WarsawSkScalar GrPathUtils::scaleToleranceToSrc(SkScalar devTol, 14a873b03ebb24076b3664ba694eeed4ab07d176d9Barry Warsaw const SkMatrix& viewM, 15a873b03ebb24076b3664ba694eeed4ab07d176d9Barry Warsaw const SkRect& pathBounds) { 16a873b03ebb24076b3664ba694eeed4ab07d176d9Barry Warsaw // In order to tesselate the path we get a bound on how much the matrix can 17c5000dfc4098f8547461e790a91536a923124261Tim Peters // stretch when mapping to screen coordinates. 188a00abc0ff6544a7004a86b4c96e23ca23ac66dcNeil Schemenauer SkScalar stretch = viewM.getMaxStretch(); 1908fca5212528e073600c27c70a34eeef445f393bBarry Warsaw SkScalar srcTol = devTol; 2008fca5212528e073600c27c70a34eeef445f393bBarry Warsaw 219e9d4f8ed8d467d0558251f43c5decc754712d53Guido van Rossum if (stretch < 0) { 223b6d025d9bc6a0109e9a2ebd28a4864e8007193aBarry Warsaw // take worst case mapRadius amoung four corners. 230179a18034b2316a70655d0f05bfbb20a0881f17Skip Montanaro // (less than perfect) 24152494aea24669a3d74460fa460a4ed45696bc75Guido van Rossum for (int i = 0; i < 4; ++i) { 25152494aea24669a3d74460fa460a4ed45696bc75Guido van Rossum SkMatrix mat; 26152494aea24669a3d74460fa460a4ed45696bc75Guido van Rossum mat.setTranslate((i % 2) ? pathBounds.fLeft : pathBounds.fRight, 27152494aea24669a3d74460fa460a4ed45696bc75Guido van Rossum (i < 2) ? pathBounds.fTop : pathBounds.fBottom); 28f58ed2596706b97c16174a839c1ed6f6b1f87fa6Guido van Rossum mat.postConcat(viewM); 29a412220bbf8ef8391eb38b35d62520cfbc2fc039Guido van Rossum stretch = SkMaxScalar(stretch, mat.mapRadius(SK_Scalar1)); 30e11e3dee3e4f467d51c9d36e24b0b09e64eab295Barry Warsaw } 313b6d025d9bc6a0109e9a2ebd28a4864e8007193aBarry Warsaw } 323b6d025d9bc6a0109e9a2ebd28a4864e8007193aBarry Warsaw srcTol = SkScalarDiv(srcTol, stretch); 339e9d4f8ed8d467d0558251f43c5decc754712d53Guido van Rossum return srcTol; 349e9d4f8ed8d467d0558251f43c5decc754712d53Guido van Rossum} 359e9d4f8ed8d467d0558251f43c5decc754712d53Guido van Rossum 369e9d4f8ed8d467d0558251f43c5decc754712d53Guido van Rossumstatic const int MAX_POINTS_PER_CURVE = 1 << 10; 379e9d4f8ed8d467d0558251f43c5decc754712d53Guido van Rossumstatic const SkScalar gMinCurveTol = 0.0001f; 389e9d4f8ed8d467d0558251f43c5decc754712d53Guido van Rossum 399e9d4f8ed8d467d0558251f43c5decc754712d53Guido van Rossumuint32_t GrPathUtils::quadraticPointCount(const SkPoint points[], 40e11e3dee3e4f467d51c9d36e24b0b09e64eab295Barry Warsaw SkScalar tol) { 419e9d4f8ed8d467d0558251f43c5decc754712d53Guido van Rossum if (tol < gMinCurveTol) { 429e9d4f8ed8d467d0558251f43c5decc754712d53Guido van Rossum tol = gMinCurveTol; 439e9d4f8ed8d467d0558251f43c5decc754712d53Guido van Rossum } 449e9d4f8ed8d467d0558251f43c5decc754712d53Guido van Rossum SkASSERT(tol > 0); 45c5000dfc4098f8547461e790a91536a923124261Tim Peters 460179a18034b2316a70655d0f05bfbb20a0881f17Skip Montanaro SkScalar d = points[1].distanceToLineSegmentBetween(points[0], points[2]); 470179a18034b2316a70655d0f05bfbb20a0881f17Skip Montanaro if (d <= tol) { 480179a18034b2316a70655d0f05bfbb20a0881f17Skip Montanaro return 1; 490179a18034b2316a70655d0f05bfbb20a0881f17Skip Montanaro } else { 509e9d4f8ed8d467d0558251f43c5decc754712d53Guido van Rossum // Each time we subdivide, d should be cut in 4. So we need to 519e9d4f8ed8d467d0558251f43c5decc754712d53Guido van Rossum // subdivide x = log4(d/tol) times. x subdivisions creates 2^(x) 529e9d4f8ed8d467d0558251f43c5decc754712d53Guido van Rossum // points. 539e9d4f8ed8d467d0558251f43c5decc754712d53Guido van Rossum // 2^(log4(x)) = sqrt(x); 5408fca5212528e073600c27c70a34eeef445f393bBarry Warsaw int temp = SkScalarCeilToInt(SkScalarSqrt(SkScalarDiv(d, tol))); 553a15dace3606d6ea9d59486c5d080a1cb4192ff4Fred Drake int pow2 = GrNextPow2(temp); 563a15dace3606d6ea9d59486c5d080a1cb4192ff4Fred Drake // Because of NaNs & INFs we can wind up with a degenerate temp 57315aa361fc60d3328aad3a5dcfd42f08213c25fbGuido van Rossum // such that pow2 comes out negative. Also, our point generator 58315aa361fc60d3328aad3a5dcfd42f08213c25fbGuido van Rossum // will always output at least one pt. 59315aa361fc60d3328aad3a5dcfd42f08213c25fbGuido van Rossum if (pow2 < 1) { 60315aa361fc60d3328aad3a5dcfd42f08213c25fbGuido van Rossum pow2 = 1; 612158df0b4d8358b5efdcac3024e8cc6d6c92d981Andrew M. Kuchling } 622158df0b4d8358b5efdcac3024e8cc6d6c92d981Andrew M. Kuchling return SkTMin(pow2, MAX_POINTS_PER_CURVE); 631633a2e3452b40d0e9bb1f15ab16cd6b90f15a19Tim Peters } 649e9d4f8ed8d467d0558251f43c5decc754712d53Guido van Rossum} 659e9d4f8ed8d467d0558251f43c5decc754712d53Guido van Rossum 669e9d4f8ed8d467d0558251f43c5decc754712d53Guido van Rossumuint32_t GrPathUtils::generateQuadraticPoints(const SkPoint& p0, 6708fca5212528e073600c27c70a34eeef445f393bBarry Warsaw const SkPoint& p1, 689e9d4f8ed8d467d0558251f43c5decc754712d53Guido van Rossum const SkPoint& p2, 699e9d4f8ed8d467d0558251f43c5decc754712d53Guido van Rossum SkScalar tolSqd, 701c6b1a2b4ea38955a3f0514f4709bafd0be96c5eMartin v. Löwis SkPoint** points, 711c6b1a2b4ea38955a3f0514f4709bafd0be96c5eMartin v. Löwis uint32_t pointsLeft) { 721c6b1a2b4ea38955a3f0514f4709bafd0be96c5eMartin v. Löwis if (pointsLeft < 2 || 734dd0f7ef7a0a7e7abe2043bbf8804fde962a8de3Fred Drake (p1.distanceToLineSegmentBetweenSqd(p0, p2)) < tolSqd) { 747c85fa4a5203912aca564ce719a0fdd0fd5411e5Raymond Hettinger (*points)[0] = p2; 757c85fa4a5203912aca564ce719a0fdd0fd5411e5Raymond Hettinger *points += 1; 767c85fa4a5203912aca564ce719a0fdd0fd5411e5Raymond Hettinger return 1; 774dd0f7ef7a0a7e7abe2043bbf8804fde962a8de3Fred Drake } 784dd0f7ef7a0a7e7abe2043bbf8804fde962a8de3Fred Drake 794dd0f7ef7a0a7e7abe2043bbf8804fde962a8de3Fred Drake SkPoint q[] = { 80152494aea24669a3d74460fa460a4ed45696bc75Guido van Rossum { SkScalarAve(p0.fX, p1.fX), SkScalarAve(p0.fY, p1.fY) }, 81152494aea24669a3d74460fa460a4ed45696bc75Guido van Rossum { SkScalarAve(p1.fX, p2.fX), SkScalarAve(p1.fY, p2.fY) }, 82152494aea24669a3d74460fa460a4ed45696bc75Guido van Rossum }; 833b6d025d9bc6a0109e9a2ebd28a4864e8007193aBarry Warsaw SkPoint r = { SkScalarAve(q[0].fX, q[1].fX), SkScalarAve(q[0].fY, q[1].fY) }; 84152494aea24669a3d74460fa460a4ed45696bc75Guido van Rossum 85ab1c7918f683e540ae5651c1b585ecda16ae352dSkip Montanaro pointsLeft >>= 1; 86dc15c27f505930a69c73f8c2baf1f9caff9252efGuido van Rossum uint32_t a = generateQuadraticPoints(p0, q[0], r, tolSqd, points, pointsLeft); 873b6d025d9bc6a0109e9a2ebd28a4864e8007193aBarry Warsaw uint32_t b = generateQuadraticPoints(r, q[1], p2, tolSqd, points, pointsLeft); 883b6d025d9bc6a0109e9a2ebd28a4864e8007193aBarry Warsaw return a + b; 89dc15c27f505930a69c73f8c2baf1f9caff9252efGuido van Rossum} 90dc15c27f505930a69c73f8c2baf1f9caff9252efGuido van Rossum 91dc15c27f505930a69c73f8c2baf1f9caff9252efGuido van Rossumuint32_t GrPathUtils::cubicPointCount(const SkPoint points[], 9288b1defb6f770c4f74788e8296b88fc31c3936ceGuido van Rossum SkScalar tol) { 93dc15c27f505930a69c73f8c2baf1f9caff9252efGuido van Rossum if (tol < gMinCurveTol) { 94c34c4fc3ab497ec1dd4f8c921798927d1b6d13e2Guido van Rossum tol = gMinCurveTol; 95c34c4fc3ab497ec1dd4f8c921798927d1b6d13e2Guido van Rossum } 96c34c4fc3ab497ec1dd4f8c921798927d1b6d13e2Guido van Rossum SkASSERT(tol > 0); 97c34c4fc3ab497ec1dd4f8c921798927d1b6d13e2Guido van Rossum 98c34c4fc3ab497ec1dd4f8c921798927d1b6d13e2Guido van Rossum SkScalar d = SkTMax( 99152494aea24669a3d74460fa460a4ed45696bc75Guido van Rossum points[1].distanceToLineSegmentBetweenSqd(points[0], points[3]), 100bb48465273d2aa98fc7669e99b0d5fb1c57962deGuido van Rossum points[2].distanceToLineSegmentBetweenSqd(points[0], points[3])); 101bb48465273d2aa98fc7669e99b0d5fb1c57962deGuido van Rossum d = SkScalarSqrt(d); 102bb48465273d2aa98fc7669e99b0d5fb1c57962deGuido van Rossum if (d <= tol) { 103bb48465273d2aa98fc7669e99b0d5fb1c57962deGuido van Rossum return 1; 104bb48465273d2aa98fc7669e99b0d5fb1c57962deGuido van Rossum } else { 105bb48465273d2aa98fc7669e99b0d5fb1c57962deGuido van Rossum int temp = SkScalarCeilToInt(SkScalarSqrt(SkScalarDiv(d, tol))); 106bb48465273d2aa98fc7669e99b0d5fb1c57962deGuido van Rossum int pow2 = GrNextPow2(temp); 107bb48465273d2aa98fc7669e99b0d5fb1c57962deGuido van Rossum // Because of NaNs & INFs we can wind up with a degenerate temp 108bb48465273d2aa98fc7669e99b0d5fb1c57962deGuido van Rossum // such that pow2 comes out negative. Also, our point generator 109bb48465273d2aa98fc7669e99b0d5fb1c57962deGuido van Rossum // will always output at least one pt. 110bb48465273d2aa98fc7669e99b0d5fb1c57962deGuido van Rossum if (pow2 < 1) { 111bb48465273d2aa98fc7669e99b0d5fb1c57962deGuido van Rossum pow2 = 1; 112bb48465273d2aa98fc7669e99b0d5fb1c57962deGuido van Rossum } 113bb48465273d2aa98fc7669e99b0d5fb1c57962deGuido van Rossum return SkTMin(pow2, MAX_POINTS_PER_CURVE); 114bb48465273d2aa98fc7669e99b0d5fb1c57962deGuido van Rossum } 115bb48465273d2aa98fc7669e99b0d5fb1c57962deGuido van Rossum} 11604f357cffef6d764f2f0ff2671dabde75ec250d1Barry Warsaw 1173a15dace3606d6ea9d59486c5d080a1cb4192ff4Fred Drakeuint32_t GrPathUtils::generateCubicPoints(const SkPoint& p0, 1187c85fa4a5203912aca564ce719a0fdd0fd5411e5Raymond Hettinger const SkPoint& p1, 1197c85fa4a5203912aca564ce719a0fdd0fd5411e5Raymond Hettinger const SkPoint& p2, 1203a15dace3606d6ea9d59486c5d080a1cb4192ff4Fred Drake const SkPoint& p3, 1213a15dace3606d6ea9d59486c5d080a1cb4192ff4Fred Drake SkScalar tolSqd, 12208fca5212528e073600c27c70a34eeef445f393bBarry Warsaw SkPoint** points, 12308fca5212528e073600c27c70a34eeef445f393bBarry Warsaw uint32_t pointsLeft) { 12408fca5212528e073600c27c70a34eeef445f393bBarry Warsaw if (pointsLeft < 2 || 12508fca5212528e073600c27c70a34eeef445f393bBarry Warsaw (p1.distanceToLineSegmentBetweenSqd(p0, p3) < tolSqd && 12608fca5212528e073600c27c70a34eeef445f393bBarry Warsaw p2.distanceToLineSegmentBetweenSqd(p0, p3) < tolSqd)) { 12708fca5212528e073600c27c70a34eeef445f393bBarry Warsaw (*points)[0] = p3; 1283b6d025d9bc6a0109e9a2ebd28a4864e8007193aBarry Warsaw *points += 1; 1293b6d025d9bc6a0109e9a2ebd28a4864e8007193aBarry Warsaw return 1; 1300179a18034b2316a70655d0f05bfbb20a0881f17Skip Montanaro } 1316fd83b7b38d0b2a8c9ff5e5b553a1ea6f7306ef4Guido van Rossum SkPoint q[] = { 1326fd83b7b38d0b2a8c9ff5e5b553a1ea6f7306ef4Guido van Rossum { SkScalarAve(p0.fX, p1.fX), SkScalarAve(p0.fY, p1.fY) }, 1337e47402264cf87b9bbb61fc9ff610af08add7c7bThomas Wouters { SkScalarAve(p1.fX, p2.fX), SkScalarAve(p1.fY, p2.fY) }, 134004d5e6880940ddbb38460986ac62ee0f1bae97dFred Drake { SkScalarAve(p2.fX, p3.fX), SkScalarAve(p2.fY, p3.fY) } 1356fd83b7b38d0b2a8c9ff5e5b553a1ea6f7306ef4Guido van Rossum }; 1366fd83b7b38d0b2a8c9ff5e5b553a1ea6f7306ef4Guido van Rossum SkPoint r[] = { 1376fd83b7b38d0b2a8c9ff5e5b553a1ea6f7306ef4Guido van Rossum { SkScalarAve(q[0].fX, q[1].fX), SkScalarAve(q[0].fY, q[1].fY) }, 1386fd83b7b38d0b2a8c9ff5e5b553a1ea6f7306ef4Guido van Rossum { SkScalarAve(q[1].fX, q[2].fX), SkScalarAve(q[1].fY, q[2].fY) } 1396fd83b7b38d0b2a8c9ff5e5b553a1ea6f7306ef4Guido van Rossum }; 1406fd83b7b38d0b2a8c9ff5e5b553a1ea6f7306ef4Guido van Rossum SkPoint s = { SkScalarAve(r[0].fX, r[1].fX), SkScalarAve(r[0].fY, r[1].fY) }; 141004d5e6880940ddbb38460986ac62ee0f1bae97dFred Drake pointsLeft >>= 1; 1426fd83b7b38d0b2a8c9ff5e5b553a1ea6f7306ef4Guido van Rossum uint32_t a = generateCubicPoints(p0, q[0], r[0], s, tolSqd, points, pointsLeft); 1436fd83b7b38d0b2a8c9ff5e5b553a1ea6f7306ef4Guido van Rossum uint32_t b = generateCubicPoints(s, r[1], q[2], p3, tolSqd, points, pointsLeft); 1446fd83b7b38d0b2a8c9ff5e5b553a1ea6f7306ef4Guido van Rossum return a + b; 1456fd83b7b38d0b2a8c9ff5e5b553a1ea6f7306ef4Guido van Rossum} 146ab1c7918f683e540ae5651c1b585ecda16ae352dSkip Montanaro 1473b6d025d9bc6a0109e9a2ebd28a4864e8007193aBarry Warsawint GrPathUtils::worstCasePointCount(const SkPath& path, int* subpaths, 1483b6d025d9bc6a0109e9a2ebd28a4864e8007193aBarry Warsaw SkScalar tol) { 1493b6d025d9bc6a0109e9a2ebd28a4864e8007193aBarry Warsaw if (tol < gMinCurveTol) { 1503b6d025d9bc6a0109e9a2ebd28a4864e8007193aBarry Warsaw tol = gMinCurveTol; 1516fd83b7b38d0b2a8c9ff5e5b553a1ea6f7306ef4Guido van Rossum } 152004d5e6880940ddbb38460986ac62ee0f1bae97dFred Drake SkASSERT(tol > 0); 1538dee809410e2d433bb0be5d8a1699736b90db0b5Tim Peters 154152494aea24669a3d74460fa460a4ed45696bc75Guido van Rossum int pointCount = 0; 1550179a18034b2316a70655d0f05bfbb20a0881f17Skip Montanaro *subpaths = 1; 15608fca5212528e073600c27c70a34eeef445f393bBarry Warsaw 157c5000dfc4098f8547461e790a91536a923124261Tim Peters bool first = true; 1583b6d025d9bc6a0109e9a2ebd28a4864e8007193aBarry Warsaw 1590179a18034b2316a70655d0f05bfbb20a0881f17Skip Montanaro SkPath::Iter iter(path, false); 1603b6d025d9bc6a0109e9a2ebd28a4864e8007193aBarry Warsaw SkPath::Verb verb; 161152494aea24669a3d74460fa460a4ed45696bc75Guido van Rossum 16208fca5212528e073600c27c70a34eeef445f393bBarry Warsaw SkPoint pts[4]; 16308fca5212528e073600c27c70a34eeef445f393bBarry Warsaw while ((verb = iter.next(pts)) != SkPath::kDone_Verb) { 16408fca5212528e073600c27c70a34eeef445f393bBarry Warsaw 16508fca5212528e073600c27c70a34eeef445f393bBarry Warsaw switch (verb) { 16608fca5212528e073600c27c70a34eeef445f393bBarry Warsaw case SkPath::kLine_Verb: 167152494aea24669a3d74460fa460a4ed45696bc75Guido van Rossum pointCount += 1; 16808fca5212528e073600c27c70a34eeef445f393bBarry Warsaw break; 16908fca5212528e073600c27c70a34eeef445f393bBarry Warsaw case SkPath::kQuad_Verb: 17008fca5212528e073600c27c70a34eeef445f393bBarry Warsaw pointCount += quadraticPointCount(pts, tol); 17108fca5212528e073600c27c70a34eeef445f393bBarry Warsaw break; 17208fca5212528e073600c27c70a34eeef445f393bBarry Warsaw case SkPath::kCubic_Verb: 1733b6d025d9bc6a0109e9a2ebd28a4864e8007193aBarry Warsaw pointCount += cubicPointCount(pts, tol); 17408fca5212528e073600c27c70a34eeef445f393bBarry Warsaw break; 17508fca5212528e073600c27c70a34eeef445f393bBarry Warsaw case SkPath::kMove_Verb: 1763b6d025d9bc6a0109e9a2ebd28a4864e8007193aBarry Warsaw pointCount += 1; 17708fca5212528e073600c27c70a34eeef445f393bBarry Warsaw if (!first) { 1783b6d025d9bc6a0109e9a2ebd28a4864e8007193aBarry Warsaw ++(*subpaths); 17908fca5212528e073600c27c70a34eeef445f393bBarry Warsaw } 1803b6d025d9bc6a0109e9a2ebd28a4864e8007193aBarry Warsaw break; 18108fca5212528e073600c27c70a34eeef445f393bBarry Warsaw default: 1823b6d025d9bc6a0109e9a2ebd28a4864e8007193aBarry Warsaw break; 183c5000dfc4098f8547461e790a91536a923124261Tim Peters } 184c5000dfc4098f8547461e790a91536a923124261Tim Peters first = false; 18508fca5212528e073600c27c70a34eeef445f393bBarry Warsaw } 1863b6d025d9bc6a0109e9a2ebd28a4864e8007193aBarry Warsaw return pointCount; 1870179a18034b2316a70655d0f05bfbb20a0881f17Skip Montanaro} 1880179a18034b2316a70655d0f05bfbb20a0881f17Skip Montanaro 1899e9d4f8ed8d467d0558251f43c5decc754712d53Guido van Rossumvoid GrPathUtils::QuadUVMatrix::set(const SkPoint qPts[3]) { 1909e9d4f8ed8d467d0558251f43c5decc754712d53Guido van Rossum SkMatrix m; 1919e9d4f8ed8d467d0558251f43c5decc754712d53Guido van Rossum // We want M such that M * xy_pt = uv_pt 1923b6d025d9bc6a0109e9a2ebd28a4864e8007193aBarry Warsaw // We know M * control_pts = [0 1/2 1] 1933b6d025d9bc6a0109e9a2ebd28a4864e8007193aBarry Warsaw // [0 0 1] 19408fca5212528e073600c27c70a34eeef445f393bBarry Warsaw // [1 1 1] 195fe3f6969f54cfd3df24f54572a809e0deb47064fGuido van Rossum // And control_pts = [x0 x1 x2] 196fe3f6969f54cfd3df24f54572a809e0deb47064fGuido van Rossum // [y0 y1 y2] 1973a15dace3606d6ea9d59486c5d080a1cb4192ff4Fred Drake // [1 1 1 ] 1984dd0f7ef7a0a7e7abe2043bbf8804fde962a8de3Fred Drake // We invert the control pt matrix and post concat to both sides to get M. 1994dd0f7ef7a0a7e7abe2043bbf8804fde962a8de3Fred Drake // Using the known form of the control point matrix and the result, we can 2004dd0f7ef7a0a7e7abe2043bbf8804fde962a8de3Fred Drake // optimize and improve precision. 2014dd0f7ef7a0a7e7abe2043bbf8804fde962a8de3Fred Drake 2024dd0f7ef7a0a7e7abe2043bbf8804fde962a8de3Fred Drake double x0 = qPts[0].fX; 2034dd0f7ef7a0a7e7abe2043bbf8804fde962a8de3Fred Drake double y0 = qPts[0].fY; 2043a15dace3606d6ea9d59486c5d080a1cb4192ff4Fred Drake double x1 = qPts[1].fX; 2053a15dace3606d6ea9d59486c5d080a1cb4192ff4Fred Drake double y1 = qPts[1].fY; 2064dd0f7ef7a0a7e7abe2043bbf8804fde962a8de3Fred Drake double x2 = qPts[2].fX; 2074dd0f7ef7a0a7e7abe2043bbf8804fde962a8de3Fred Drake double y2 = qPts[2].fY; 2084dd0f7ef7a0a7e7abe2043bbf8804fde962a8de3Fred Drake double det = x0*y1 - y0*x1 + x2*y0 - y2*x0 + x1*y2 - y1*x2; 2094dd0f7ef7a0a7e7abe2043bbf8804fde962a8de3Fred Drake 210e41abab33b0b467acd6bdc7d73ce4b5cef4fd5bfAndrew MacIntyre if (!sk_float_isfinite(det) 211a412220bbf8ef8391eb38b35d62520cfbc2fc039Guido van Rossum || SkScalarNearlyZero((float)det, SK_ScalarNearlyZero * SK_ScalarNearlyZero)) { 21208fca5212528e073600c27c70a34eeef445f393bBarry Warsaw // The quad is degenerate. Hopefully this is rare. Find the pts that are 213c5000dfc4098f8547461e790a91536a923124261Tim Peters // farthest apart to compute a line (unless it is really a pt). 214c5000dfc4098f8547461e790a91536a923124261Tim Peters SkScalar maxD = qPts[0].distanceToSqd(qPts[1]); 21508fca5212528e073600c27c70a34eeef445f393bBarry Warsaw int maxEdge = 0; 216152494aea24669a3d74460fa460a4ed45696bc75Guido van Rossum SkScalar d = qPts[1].distanceToSqd(qPts[2]); 217152494aea24669a3d74460fa460a4ed45696bc75Guido van Rossum if (d > maxD) { 218152494aea24669a3d74460fa460a4ed45696bc75Guido van Rossum maxD = d; 2199a0db07c2ffd4e4b3ae75d5820dc6b4152b3582bFred Drake maxEdge = 1; 220e11e3dee3e4f467d51c9d36e24b0b09e64eab295Barry Warsaw } 221d569f23da94babd616751cd46eea38963e4edfa1Neil Schemenauer d = qPts[2].distanceToSqd(qPts[0]); 222a873b03ebb24076b3664ba694eeed4ab07d176d9Barry Warsaw if (d > maxD) { 223a873b03ebb24076b3664ba694eeed4ab07d176d9Barry Warsaw maxD = d; 224a873b03ebb24076b3664ba694eeed4ab07d176d9Barry Warsaw maxEdge = 2; 2258a00abc0ff6544a7004a86b4c96e23ca23ac66dcNeil Schemenauer } 2263b6d025d9bc6a0109e9a2ebd28a4864e8007193aBarry Warsaw // We could have a tolerance here, not sure if it would improve anything 227a873b03ebb24076b3664ba694eeed4ab07d176d9Barry Warsaw if (maxD > 0) { 2288a00abc0ff6544a7004a86b4c96e23ca23ac66dcNeil Schemenauer // Set the matrix to give (u = 0, v = distance_to_line) 2298a00abc0ff6544a7004a86b4c96e23ca23ac66dcNeil Schemenauer SkVector lineVec = qPts[(maxEdge + 1)%3] - qPts[maxEdge]; 2308a00abc0ff6544a7004a86b4c96e23ca23ac66dcNeil Schemenauer // when looking from the point 0 down the line we want positive 2318a00abc0ff6544a7004a86b4c96e23ca23ac66dcNeil Schemenauer // distances to be to the left. This matches the non-degenerate 232d569f23da94babd616751cd46eea38963e4edfa1Neil Schemenauer // case. 233a873b03ebb24076b3664ba694eeed4ab07d176d9Barry Warsaw lineVec.setOrthog(lineVec, SkPoint::kLeft_Side); 234e11e3dee3e4f467d51c9d36e24b0b09e64eab295Barry Warsaw lineVec.dot(qPts[0]); 235e11e3dee3e4f467d51c9d36e24b0b09e64eab295Barry Warsaw // first row 236e11e3dee3e4f467d51c9d36e24b0b09e64eab295Barry Warsaw fM[0] = 0; 237e11e3dee3e4f467d51c9d36e24b0b09e64eab295Barry Warsaw fM[1] = 0; 238e11e3dee3e4f467d51c9d36e24b0b09e64eab295Barry Warsaw fM[2] = 0; 239fc170b1fd5db978f4e8d4c23c138a7b59df681ecEric S. Raymond // second row 240e11e3dee3e4f467d51c9d36e24b0b09e64eab295Barry Warsaw fM[3] = lineVec.fX; 241e11e3dee3e4f467d51c9d36e24b0b09e64eab295Barry Warsaw fM[4] = lineVec.fY; 242e11e3dee3e4f467d51c9d36e24b0b09e64eab295Barry Warsaw fM[5] = -lineVec.dot(qPts[maxEdge]); 243e11e3dee3e4f467d51c9d36e24b0b09e64eab295Barry Warsaw } else { 244c5000dfc4098f8547461e790a91536a923124261Tim Peters // It's a point. It should cover zero area. Just set the matrix such 245c5000dfc4098f8547461e790a91536a923124261Tim Peters // that (u, v) will always be far away from the quad. 246c5000dfc4098f8547461e790a91536a923124261Tim Peters fM[0] = 0; fM[1] = 0; fM[2] = 100.f; 247c5000dfc4098f8547461e790a91536a923124261Tim Peters fM[3] = 0; fM[4] = 0; fM[5] = 100.f; 248c5000dfc4098f8547461e790a91536a923124261Tim Peters } 249c5000dfc4098f8547461e790a91536a923124261Tim Peters } else { 250c5000dfc4098f8547461e790a91536a923124261Tim Peters double scale = 1.0/det; 251c5000dfc4098f8547461e790a91536a923124261Tim Peters 252c5000dfc4098f8547461e790a91536a923124261Tim Peters // compute adjugate matrix 253c5000dfc4098f8547461e790a91536a923124261Tim Peters double a0, a1, a2, a3, a4, a5, a6, a7, a8; 254c5000dfc4098f8547461e790a91536a923124261Tim Peters a0 = y1-y2; 255c5000dfc4098f8547461e790a91536a923124261Tim Peters a1 = x2-x1; 256c5000dfc4098f8547461e790a91536a923124261Tim Peters a2 = x1*y2-x2*y1; 257c5000dfc4098f8547461e790a91536a923124261Tim Peters 258c5000dfc4098f8547461e790a91536a923124261Tim Peters a3 = y2-y0; 259c5000dfc4098f8547461e790a91536a923124261Tim Peters a4 = x0-x2; 2606c74fea07d42ac6bc3bc078fb13f903f6cdbbcb9Guido van Rossum a5 = x2*y0-x0*y2; 2616c74fea07d42ac6bc3bc078fb13f903f6cdbbcb9Guido van Rossum 262152494aea24669a3d74460fa460a4ed45696bc75Guido van Rossum a6 = y0-y1; 2636c74fea07d42ac6bc3bc078fb13f903f6cdbbcb9Guido van Rossum a7 = x1-x0; 2646c74fea07d42ac6bc3bc078fb13f903f6cdbbcb9Guido van Rossum a8 = x0*y1-x1*y0; 2656c74fea07d42ac6bc3bc078fb13f903f6cdbbcb9Guido van Rossum 2666c74fea07d42ac6bc3bc078fb13f903f6cdbbcb9Guido van Rossum // this performs the uv_pts*adjugate(control_pts) multiply, 26741360a4696f488e49e5409b3b1baf1fff6ae0044Guido van Rossum // then does the scale by 1/det afterwards to improve precision 268747e1cade657e1e15c0f51d898de901da723e6a2Guido van Rossum m[SkMatrix::kMScaleX] = (float)((0.5*a3 + a6)*scale); 269e11e3dee3e4f467d51c9d36e24b0b09e64eab295Barry Warsaw m[SkMatrix::kMSkewX] = (float)((0.5*a4 + a7)*scale); 270e11e3dee3e4f467d51c9d36e24b0b09e64eab295Barry Warsaw m[SkMatrix::kMTransX] = (float)((0.5*a5 + a8)*scale); 271ab1c7918f683e540ae5651c1b585ecda16ae352dSkip Montanaro 272ab1c7918f683e540ae5651c1b585ecda16ae352dSkip Montanaro m[SkMatrix::kMSkewY] = (float)(a6*scale); 2733b6d025d9bc6a0109e9a2ebd28a4864e8007193aBarry Warsaw m[SkMatrix::kMScaleY] = (float)(a7*scale); 2743b6d025d9bc6a0109e9a2ebd28a4864e8007193aBarry Warsaw m[SkMatrix::kMTransY] = (float)(a8*scale); 2753b6d025d9bc6a0109e9a2ebd28a4864e8007193aBarry Warsaw 2763b6d025d9bc6a0109e9a2ebd28a4864e8007193aBarry Warsaw m[SkMatrix::kMPersp0] = (float)((a0 + a3 + a6)*scale); 2773b6d025d9bc6a0109e9a2ebd28a4864e8007193aBarry Warsaw m[SkMatrix::kMPersp1] = (float)((a1 + a4 + a7)*scale); 27841360a4696f488e49e5409b3b1baf1fff6ae0044Guido van Rossum m[SkMatrix::kMPersp2] = (float)((a2 + a5 + a8)*scale); 27908fca5212528e073600c27c70a34eeef445f393bBarry Warsaw 2805796d26794eee634a4a06637d99d8d5c58da2bdbGuido van Rossum // The matrix should not have perspective. 281152494aea24669a3d74460fa460a4ed45696bc75Guido van Rossum SkDEBUGCODE(static const SkScalar gTOL = 1.f / 100.f); 28241360a4696f488e49e5409b3b1baf1fff6ae0044Guido van Rossum SkASSERT(SkScalarAbs(m.get(SkMatrix::kMPersp0)) < gTOL); 28341360a4696f488e49e5409b3b1baf1fff6ae0044Guido van Rossum SkASSERT(SkScalarAbs(m.get(SkMatrix::kMPersp1)) < gTOL); 2843cda93ebf60e501350f42fdab72c18eab54718fcGuido van Rossum 2853b6d025d9bc6a0109e9a2ebd28a4864e8007193aBarry Warsaw // It may not be normalized to have 1.0 in the bottom right 2863b6d025d9bc6a0109e9a2ebd28a4864e8007193aBarry Warsaw float m33 = m.get(SkMatrix::kMPersp2); 2873b6d025d9bc6a0109e9a2ebd28a4864e8007193aBarry Warsaw if (1.f != m33) { 2883b6d025d9bc6a0109e9a2ebd28a4864e8007193aBarry Warsaw m33 = 1.f / m33; 2893b6d025d9bc6a0109e9a2ebd28a4864e8007193aBarry Warsaw fM[0] = m33 * m.get(SkMatrix::kMScaleX); 29041360a4696f488e49e5409b3b1baf1fff6ae0044Guido van Rossum fM[1] = m33 * m.get(SkMatrix::kMSkewX); 2913b6d025d9bc6a0109e9a2ebd28a4864e8007193aBarry Warsaw fM[2] = m33 * m.get(SkMatrix::kMTransX); 2923b6d025d9bc6a0109e9a2ebd28a4864e8007193aBarry Warsaw fM[3] = m33 * m.get(SkMatrix::kMSkewY); 2933b6d025d9bc6a0109e9a2ebd28a4864e8007193aBarry Warsaw fM[4] = m33 * m.get(SkMatrix::kMScaleY); 2943b6d025d9bc6a0109e9a2ebd28a4864e8007193aBarry Warsaw fM[5] = m33 * m.get(SkMatrix::kMTransY); 2953b6d025d9bc6a0109e9a2ebd28a4864e8007193aBarry Warsaw } else { 2963b6d025d9bc6a0109e9a2ebd28a4864e8007193aBarry Warsaw fM[0] = m.get(SkMatrix::kMScaleX); 2973b6d025d9bc6a0109e9a2ebd28a4864e8007193aBarry Warsaw fM[1] = m.get(SkMatrix::kMSkewX); 2983b6d025d9bc6a0109e9a2ebd28a4864e8007193aBarry Warsaw fM[2] = m.get(SkMatrix::kMTransX); 2993b6d025d9bc6a0109e9a2ebd28a4864e8007193aBarry Warsaw fM[3] = m.get(SkMatrix::kMSkewY); 300d569f23da94babd616751cd46eea38963e4edfa1Neil Schemenauer fM[4] = m.get(SkMatrix::kMScaleY); 301d569f23da94babd616751cd46eea38963e4edfa1Neil Schemenauer fM[5] = m.get(SkMatrix::kMTransY); 302d569f23da94babd616751cd46eea38963e4edfa1Neil Schemenauer } 3038a00abc0ff6544a7004a86b4c96e23ca23ac66dcNeil Schemenauer } 3048a00abc0ff6544a7004a86b4c96e23ca23ac66dcNeil Schemenauer} 3058a00abc0ff6544a7004a86b4c96e23ca23ac66dcNeil Schemenauer 3068a00abc0ff6544a7004a86b4c96e23ca23ac66dcNeil Schemenauer//////////////////////////////////////////////////////////////////////////////// 307d569f23da94babd616751cd46eea38963e4edfa1Neil Schemenauer 308d569f23da94babd616751cd46eea38963e4edfa1Neil Schemenauer// k = (y2 - y0, x0 - x2, (x2 - x0)*y0 - (y2 - y0)*x0 ) 3095796d26794eee634a4a06637d99d8d5c58da2bdbGuido van Rossum// l = (2*w * (y1 - y0), 2*w * (x0 - x1), 2*w * (x1*y0 - x0*y1)) 3105796d26794eee634a4a06637d99d8d5c58da2bdbGuido van Rossum// m = (2*w * (y2 - y1), 2*w * (x1 - x2), 2*w * (x2*y1 - x1*y2)) 31151931144427faa001a6db3cfc37380526be256b6Guido van Rossumvoid GrPathUtils::getConicKLM(const SkPoint p[3], const SkScalar weight, SkScalar klm[9]) { 3125796d26794eee634a4a06637d99d8d5c58da2bdbGuido van Rossum const SkScalar w2 = 2.f * weight; 3137a1ea0e88034cdc03d546f0947fc8ecb30f4435fJeremy Hylton klm[0] = p[2].fY - p[0].fY; 3147a1ea0e88034cdc03d546f0947fc8ecb30f4435fJeremy Hylton klm[1] = p[0].fX - p[2].fX; 3157a1ea0e88034cdc03d546f0947fc8ecb30f4435fJeremy Hylton klm[2] = (p[2].fX - p[0].fX) * p[0].fY - (p[2].fY - p[0].fY) * p[0].fX; 3167a1ea0e88034cdc03d546f0947fc8ecb30f4435fJeremy Hylton 3177a1ea0e88034cdc03d546f0947fc8ecb30f4435fJeremy Hylton klm[3] = w2 * (p[1].fY - p[0].fY); 318e0c446bb4ad67294f42d4cb53b4ff28413bd8ddeTim Peters klm[4] = w2 * (p[0].fX - p[1].fX); 319152494aea24669a3d74460fa460a4ed45696bc75Guido van Rossum klm[5] = w2 * (p[1].fX * p[0].fY - p[0].fX * p[1].fY); 32041360a4696f488e49e5409b3b1baf1fff6ae0044Guido van Rossum 32141360a4696f488e49e5409b3b1baf1fff6ae0044Guido van Rossum klm[6] = w2 * (p[2].fY - p[1].fY); 32241360a4696f488e49e5409b3b1baf1fff6ae0044Guido van Rossum klm[7] = w2 * (p[1].fX - p[2].fX); 3231a4d77b2527ced1052b4faae3d176b125a764325Tim Peters klm[8] = w2 * (p[2].fX * p[1].fY - p[1].fX * p[2].fY); 324408b6d34de2b1a6ba690557def435adce9314184Barry Warsaw 325408b6d34de2b1a6ba690557def435adce9314184Barry Warsaw // scale the max absolute value of coeffs to 10 326152494aea24669a3d74460fa460a4ed45696bc75Guido van Rossum SkScalar scale = 0.f; 327a45da92484ceececf1cf32b4dfb16004945b001eTim Peters for (int i = 0; i < 9; ++i) { 328a45da92484ceececf1cf32b4dfb16004945b001eTim Peters scale = SkMaxScalar(scale, SkScalarAbs(klm[i])); 329152494aea24669a3d74460fa460a4ed45696bc75Guido van Rossum } 330a45da92484ceececf1cf32b4dfb16004945b001eTim Peters SkASSERT(scale > 0.f); 331a45da92484ceececf1cf32b4dfb16004945b001eTim Peters scale = 10.f / scale; 332e11e3dee3e4f467d51c9d36e24b0b09e64eab295Barry Warsaw for (int i = 0; i < 9; ++i) { 333b5b7b78414e5f1a42ab4205c110626c9cd7a79b9Tim Peters klm[i] *= scale; 334a2be2d624a47e420266606f0cb2a2e030797f650Tim Peters } 335b5b7b78414e5f1a42ab4205c110626c9cd7a79b9Tim Peters} 336a690a9967e715663b7a421c9ebdad91381cdf1e4Raymond Hettinger 337b5b7b78414e5f1a42ab4205c110626c9cd7a79b9Tim Peters//////////////////////////////////////////////////////////////////////////////// 338b5b7b78414e5f1a42ab4205c110626c9cd7a79b9Tim Peters 339a45da92484ceececf1cf32b4dfb16004945b001eTim Petersnamespace { 340a45da92484ceececf1cf32b4dfb16004945b001eTim Peters 341b5b7b78414e5f1a42ab4205c110626c9cd7a79b9Tim Peters// a is the first control point of the cubic. 342b5b7b78414e5f1a42ab4205c110626c9cd7a79b9Tim Peters// ab is the vector from a to the second control point. 343b5b7b78414e5f1a42ab4205c110626c9cd7a79b9Tim Peters// dc is the vector from the fourth to the third control point. 344b5b7b78414e5f1a42ab4205c110626c9cd7a79b9Tim Peters// d is the fourth control point. 345b5b7b78414e5f1a42ab4205c110626c9cd7a79b9Tim Peters// p is the candidate quadratic control point. 346b5b7b78414e5f1a42ab4205c110626c9cd7a79b9Tim Peters// this assumes that the cubic doesn't inflect and is simple 347e11e3dee3e4f467d51c9d36e24b0b09e64eab295Barry Warsawbool is_point_within_cubic_tangents(const SkPoint& a, 348e11e3dee3e4f467d51c9d36e24b0b09e64eab295Barry Warsaw const SkVector& ab, 349e11e3dee3e4f467d51c9d36e24b0b09e64eab295Barry Warsaw const SkVector& dc, 350e11e3dee3e4f467d51c9d36e24b0b09e64eab295Barry Warsaw const SkPoint& d, 351e11e3dee3e4f467d51c9d36e24b0b09e64eab295Barry Warsaw SkPath::Direction dir, 352e11e3dee3e4f467d51c9d36e24b0b09e64eab295Barry Warsaw const SkPoint p) { 353e11e3dee3e4f467d51c9d36e24b0b09e64eab295Barry Warsaw SkVector ap = p - a; 354e11e3dee3e4f467d51c9d36e24b0b09e64eab295Barry Warsaw SkScalar apXab = ap.cross(ab); 355e11e3dee3e4f467d51c9d36e24b0b09e64eab295Barry Warsaw if (SkPath::kCW_Direction == dir) { 356e11e3dee3e4f467d51c9d36e24b0b09e64eab295Barry Warsaw if (apXab > 0) { 357e11e3dee3e4f467d51c9d36e24b0b09e64eab295Barry Warsaw return false; 358e11e3dee3e4f467d51c9d36e24b0b09e64eab295Barry Warsaw } 359e11e3dee3e4f467d51c9d36e24b0b09e64eab295Barry Warsaw } else { 360e11e3dee3e4f467d51c9d36e24b0b09e64eab295Barry Warsaw SkASSERT(SkPath::kCCW_Direction == dir); 3613b6d025d9bc6a0109e9a2ebd28a4864e8007193aBarry Warsaw if (apXab < 0) { 3623b6d025d9bc6a0109e9a2ebd28a4864e8007193aBarry Warsaw return false; 3633b6d025d9bc6a0109e9a2ebd28a4864e8007193aBarry Warsaw } 3643b6d025d9bc6a0109e9a2ebd28a4864e8007193aBarry Warsaw } 3650179a18034b2316a70655d0f05bfbb20a0881f17Skip Montanaro 3660179a18034b2316a70655d0f05bfbb20a0881f17Skip Montanaro SkVector dp = p - d; 3670179a18034b2316a70655d0f05bfbb20a0881f17Skip Montanaro SkScalar dpXdc = dp.cross(dc); 3685943b4ac1067e5011b66697396d5df93b5ef9af0Tim Peters if (SkPath::kCW_Direction == dir) { 36908fca5212528e073600c27c70a34eeef445f393bBarry Warsaw if (dpXdc < 0) { 370152494aea24669a3d74460fa460a4ed45696bc75Guido van Rossum return false; 3716fd83b7b38d0b2a8c9ff5e5b553a1ea6f7306ef4Guido van Rossum } 372152494aea24669a3d74460fa460a4ed45696bc75Guido van Rossum } else { 373152494aea24669a3d74460fa460a4ed45696bc75Guido van Rossum SkASSERT(SkPath::kCCW_Direction == dir); 374152494aea24669a3d74460fa460a4ed45696bc75Guido van Rossum if (dpXdc > 0) { 375152494aea24669a3d74460fa460a4ed45696bc75Guido van Rossum return false; 376152494aea24669a3d74460fa460a4ed45696bc75Guido van Rossum } 377152494aea24669a3d74460fa460a4ed45696bc75Guido van Rossum } 378152494aea24669a3d74460fa460a4ed45696bc75Guido van Rossum return true; 379152494aea24669a3d74460fa460a4ed45696bc75Guido van Rossum} 3806fd83b7b38d0b2a8c9ff5e5b553a1ea6f7306ef4Guido van Rossum 381152494aea24669a3d74460fa460a4ed45696bc75Guido van Rossumvoid convert_noninflect_cubic_to_quads(const SkPoint p[4], 38262e2c7e3dfffd8465a54b99fc6d3c2a60acab350Jeremy Hylton SkScalar toleranceSqd, 38362e2c7e3dfffd8465a54b99fc6d3c2a60acab350Jeremy Hylton bool constrainWithinTangents, 3848471a35febdbfbfab51b9d4b5fe51694fe6ca536Jeremy Hylton SkPath::Direction dir, 385152494aea24669a3d74460fa460a4ed45696bc75Guido van Rossum SkTArray<SkPoint, true>* quads, 386152494aea24669a3d74460fa460a4ed45696bc75Guido van Rossum int sublevel = 0) { 3876fd83b7b38d0b2a8c9ff5e5b553a1ea6f7306ef4Guido van Rossum 388152494aea24669a3d74460fa460a4ed45696bc75Guido van Rossum // Notation: Point a is always p[0]. Point b is p[1] unless p[1] == p[0], in which case it is 3896fd83b7b38d0b2a8c9ff5e5b553a1ea6f7306ef4Guido van Rossum // p[2]. Point d is always p[3]. Point c is p[2] unless p[2] == p[3], in which case it is p[1]. 390152494aea24669a3d74460fa460a4ed45696bc75Guido van Rossum 391152494aea24669a3d74460fa460a4ed45696bc75Guido van Rossum SkVector ab = p[1] - p[0]; 392152494aea24669a3d74460fa460a4ed45696bc75Guido van Rossum SkVector dc = p[2] - p[3]; 393e2ae77b8b8a62e648bb1864a9b36ef3280984404Guido van Rossum 39441360a4696f488e49e5409b3b1baf1fff6ae0044Guido van Rossum if (ab.isZero()) { 39541360a4696f488e49e5409b3b1baf1fff6ae0044Guido van Rossum if (dc.isZero()) { 39641360a4696f488e49e5409b3b1baf1fff6ae0044Guido van Rossum SkPoint* degQuad = quads->push_back_n(3); 397152494aea24669a3d74460fa460a4ed45696bc75Guido van Rossum degQuad[0] = p[0]; 398152494aea24669a3d74460fa460a4ed45696bc75Guido van Rossum degQuad[1] = p[0]; 399152494aea24669a3d74460fa460a4ed45696bc75Guido van Rossum degQuad[2] = p[3]; 4003b6d025d9bc6a0109e9a2ebd28a4864e8007193aBarry Warsaw return; 4016fd83b7b38d0b2a8c9ff5e5b553a1ea6f7306ef4Guido van Rossum } 4026fd83b7b38d0b2a8c9ff5e5b553a1ea6f7306ef4Guido van Rossum ab = p[2] - p[0]; 4036fd83b7b38d0b2a8c9ff5e5b553a1ea6f7306ef4Guido van Rossum } 4046fd83b7b38d0b2a8c9ff5e5b553a1ea6f7306ef4Guido van Rossum if (dc.isZero()) { 4056fd83b7b38d0b2a8c9ff5e5b553a1ea6f7306ef4Guido van Rossum dc = p[1] - p[3]; 406f29f47b38beae54db959d0dd2f0800d5dd3fc174Trent Mick } 4076fd83b7b38d0b2a8c9ff5e5b553a1ea6f7306ef4Guido van Rossum 4086fd83b7b38d0b2a8c9ff5e5b553a1ea6f7306ef4Guido van Rossum // When the ab and cd tangents are nearly parallel with vector from d to a the constraint that 409152494aea24669a3d74460fa460a4ed45696bc75Guido van Rossum // the quad point falls between the tangents becomes hard to enforce and we are likely to hit 4103b6d025d9bc6a0109e9a2ebd28a4864e8007193aBarry Warsaw // the max subdivision count. However, in this case the cubic is approaching a line and the 4113b6d025d9bc6a0109e9a2ebd28a4864e8007193aBarry Warsaw // accuracy of the quad point isn't so important. We check if the two middle cubic control 412152494aea24669a3d74460fa460a4ed45696bc75Guido van Rossum // points are very close to the baseline vector. If so then we just pick quadratic points on the 413152494aea24669a3d74460fa460a4ed45696bc75Guido van Rossum // control polygon. 4149390cc15da5cd6920bd41bb4cd146d5d0601345fTim Peters 41541360a4696f488e49e5409b3b1baf1fff6ae0044Guido van Rossum if (constrainWithinTangents) { 4160fcca4e815e3dbb28c73108376079a94ad6ee8deGuido van Rossum SkVector da = p[0] - p[3]; 41774e67661a69ddb43a21a486c66965a052540cdd0Raymond Hettinger SkScalar invDALengthSqd = da.lengthSqd(); 418152494aea24669a3d74460fa460a4ed45696bc75Guido van Rossum if (invDALengthSqd > SK_ScalarNearlyZero) { 419342ca75d9552ff5c606c465d1392a32e44257fe5Tim Peters invDALengthSqd = SkScalarInvert(invDALengthSqd); 42041360a4696f488e49e5409b3b1baf1fff6ae0044Guido van Rossum // cross(ab, da)^2/length(da)^2 == sqd distance from b to line from d to a. 42141360a4696f488e49e5409b3b1baf1fff6ae0044Guido van Rossum // same goed for point c using vector cd. 42241360a4696f488e49e5409b3b1baf1fff6ae0044Guido van Rossum SkScalar detABSqd = ab.cross(da); 42341360a4696f488e49e5409b3b1baf1fff6ae0044Guido van Rossum detABSqd = SkScalarSquare(detABSqd); 424408b6d34de2b1a6ba690557def435adce9314184Barry Warsaw SkScalar detDCSqd = dc.cross(da); 425408b6d34de2b1a6ba690557def435adce9314184Barry Warsaw detDCSqd = SkScalarSquare(detDCSqd); 426408b6d34de2b1a6ba690557def435adce9314184Barry Warsaw if (SkScalarMul(detABSqd, invDALengthSqd) < toleranceSqd && 427408b6d34de2b1a6ba690557def435adce9314184Barry Warsaw SkScalarMul(detDCSqd, invDALengthSqd) < toleranceSqd) { 428408b6d34de2b1a6ba690557def435adce9314184Barry Warsaw SkPoint b = p[0] + ab; 429408b6d34de2b1a6ba690557def435adce9314184Barry Warsaw SkPoint c = p[3] + dc; 430408b6d34de2b1a6ba690557def435adce9314184Barry Warsaw SkPoint mid = b + c; 431d97422115e9ed6498bc7a6f792a0bf8f278f9097Tim Peters mid.scale(SK_ScalarHalf); 432d97422115e9ed6498bc7a6f792a0bf8f278f9097Tim Peters // Insert two quadratics to cover the case when ab points away from d and/or dc 433d97422115e9ed6498bc7a6f792a0bf8f278f9097Tim Peters // points away from a. 434d97422115e9ed6498bc7a6f792a0bf8f278f9097Tim Peters if (SkVector::DotProduct(da, dc) < 0 || SkVector::DotProduct(ab,da) > 0) { 435d97422115e9ed6498bc7a6f792a0bf8f278f9097Tim Peters SkPoint* qpts = quads->push_back_n(6); 436d97422115e9ed6498bc7a6f792a0bf8f278f9097Tim Peters qpts[0] = p[0]; 437d97422115e9ed6498bc7a6f792a0bf8f278f9097Tim Peters qpts[1] = b; 43841360a4696f488e49e5409b3b1baf1fff6ae0044Guido van Rossum qpts[2] = mid; 439342ca75d9552ff5c606c465d1392a32e44257fe5Tim Peters qpts[3] = mid; 4409a0db07c2ffd4e4b3ae75d5820dc6b4152b3582bFred Drake qpts[4] = c; 4419a0db07c2ffd4e4b3ae75d5820dc6b4152b3582bFred Drake qpts[5] = p[3]; 4429a0db07c2ffd4e4b3ae75d5820dc6b4152b3582bFred Drake } else { 4439a0db07c2ffd4e4b3ae75d5820dc6b4152b3582bFred Drake SkPoint* qpts = quads->push_back_n(3); 4449a0db07c2ffd4e4b3ae75d5820dc6b4152b3582bFred Drake qpts[0] = p[0]; 4453af826ebca80f8a6c782fb590c77ac210ae9e22dThomas Wouters qpts[1] = mid; 446f29f47b38beae54db959d0dd2f0800d5dd3fc174Trent Mick qpts[2] = p[3]; 447de4742b87f7775fc3d9fa76cd640e7cdd5ef69a2Fred Drake } 4483cda93ebf60e501350f42fdab72c18eab54718fcGuido van Rossum return; 44941360a4696f488e49e5409b3b1baf1fff6ae0044Guido van Rossum } 450fe5c22a85e6740012143cdbdc384bd2ebc788c27Fred Drake } 451fe5c22a85e6740012143cdbdc384bd2ebc788c27Fred Drake } 452152494aea24669a3d74460fa460a4ed45696bc75Guido van Rossum 45341360a4696f488e49e5409b3b1baf1fff6ae0044Guido van Rossum static const SkScalar kLengthScale = 3 * SK_Scalar1 / 2; 4543cda93ebf60e501350f42fdab72c18eab54718fcGuido van Rossum static const int kMaxSubdivs = 10; 45541360a4696f488e49e5409b3b1baf1fff6ae0044Guido van Rossum 4569e48b272b96aabf597b7aedd358ab890ddbf4c98Guido van Rossum ab.scale(kLengthScale); 45741360a4696f488e49e5409b3b1baf1fff6ae0044Guido van Rossum dc.scale(kLengthScale); 45827c4b39025eb9e20f9d7a36b6aa0bb9c97f9bba5Fred Drake 4593cda93ebf60e501350f42fdab72c18eab54718fcGuido van Rossum // e0 and e1 are extrapolations along vectors ab and dc. 46041360a4696f488e49e5409b3b1baf1fff6ae0044Guido van Rossum SkVector c0 = p[0]; 46141360a4696f488e49e5409b3b1baf1fff6ae0044Guido van Rossum c0 += ab; 4623cda93ebf60e501350f42fdab72c18eab54718fcGuido van Rossum SkVector c1 = p[3]; 46341360a4696f488e49e5409b3b1baf1fff6ae0044Guido van Rossum c1 += dc; 464152494aea24669a3d74460fa460a4ed45696bc75Guido van Rossum 4650fcca4e815e3dbb28c73108376079a94ad6ee8deGuido van Rossum SkScalar dSqd = sublevel > kMaxSubdivs ? 0 : c0.distanceToSqd(c1); 4660fcca4e815e3dbb28c73108376079a94ad6ee8deGuido van Rossum if (dSqd < toleranceSqd) { 4670fcca4e815e3dbb28c73108376079a94ad6ee8deGuido van Rossum SkPoint cAvg = c0; 468e51fe8d0a3d2a3fc83fd4f02521b0808c073bf50Fred Drake cAvg += c1; 469e51fe8d0a3d2a3fc83fd4f02521b0808c073bf50Fred Drake cAvg.scale(SK_ScalarHalf); 470e51fe8d0a3d2a3fc83fd4f02521b0808c073bf50Fred Drake 471e51fe8d0a3d2a3fc83fd4f02521b0808c073bf50Fred Drake bool subdivide = false; 472e51fe8d0a3d2a3fc83fd4f02521b0808c073bf50Fred Drake 473e51fe8d0a3d2a3fc83fd4f02521b0808c073bf50Fred Drake if (constrainWithinTangents && 474e51fe8d0a3d2a3fc83fd4f02521b0808c073bf50Fred Drake !is_point_within_cubic_tangents(p[0], ab, dc, p[3], dir, cAvg)) { 475e51fe8d0a3d2a3fc83fd4f02521b0808c073bf50Fred Drake // choose a new cAvg that is the intersection of the two tangent lines. 4760fcca4e815e3dbb28c73108376079a94ad6ee8deGuido van Rossum ab.setOrthog(ab); 4770fcca4e815e3dbb28c73108376079a94ad6ee8deGuido van Rossum SkScalar z0 = -ab.dot(p[0]); 4780fcca4e815e3dbb28c73108376079a94ad6ee8deGuido van Rossum dc.setOrthog(dc); 4790fcca4e815e3dbb28c73108376079a94ad6ee8deGuido van Rossum SkScalar z1 = -dc.dot(p[3]); 4800fcca4e815e3dbb28c73108376079a94ad6ee8deGuido van Rossum cAvg.fX = SkScalarMul(ab.fY, z1) - SkScalarMul(z0, dc.fY); 4810fcca4e815e3dbb28c73108376079a94ad6ee8deGuido van Rossum cAvg.fY = SkScalarMul(z0, dc.fX) - SkScalarMul(ab.fX, z1); 4820fcca4e815e3dbb28c73108376079a94ad6ee8deGuido van Rossum SkScalar z = SkScalarMul(ab.fX, dc.fY) - SkScalarMul(ab.fY, dc.fX); 4830fcca4e815e3dbb28c73108376079a94ad6ee8deGuido van Rossum z = SkScalarInvert(z); 4840fcca4e815e3dbb28c73108376079a94ad6ee8deGuido van Rossum cAvg.fX *= z; 4850fcca4e815e3dbb28c73108376079a94ad6ee8deGuido van Rossum cAvg.fY *= z; 4860fcca4e815e3dbb28c73108376079a94ad6ee8deGuido van Rossum if (sublevel <= kMaxSubdivs) { 4870fcca4e815e3dbb28c73108376079a94ad6ee8deGuido van Rossum SkScalar d0Sqd = c0.distanceToSqd(cAvg); 4880fcca4e815e3dbb28c73108376079a94ad6ee8deGuido van Rossum SkScalar d1Sqd = c1.distanceToSqd(cAvg); 4890fcca4e815e3dbb28c73108376079a94ad6ee8deGuido van Rossum // We need to subdivide if d0 + d1 > tolerance but we have the sqd values. We know 4900fcca4e815e3dbb28c73108376079a94ad6ee8deGuido van Rossum // the distances and tolerance can't be negative. 4910fcca4e815e3dbb28c73108376079a94ad6ee8deGuido van Rossum // (d0 + d1)^2 > toleranceSqd 4923cda93ebf60e501350f42fdab72c18eab54718fcGuido van Rossum // d0Sqd + 2*d0*d1 + d1Sqd > toleranceSqd 4930fcca4e815e3dbb28c73108376079a94ad6ee8deGuido van Rossum SkScalar d0d1 = SkScalarSqrt(SkScalarMul(d0Sqd, d1Sqd)); 4943cda93ebf60e501350f42fdab72c18eab54718fcGuido van Rossum subdivide = 2 * d0d1 + d0Sqd + d1Sqd > toleranceSqd; 4950fcca4e815e3dbb28c73108376079a94ad6ee8deGuido van Rossum } 4960fcca4e815e3dbb28c73108376079a94ad6ee8deGuido van Rossum } 4970fcca4e815e3dbb28c73108376079a94ad6ee8deGuido van Rossum if (!subdivide) { 4980fcca4e815e3dbb28c73108376079a94ad6ee8deGuido van Rossum SkPoint* pts = quads->push_back_n(3); 499c377b16d12ba325bb108eca575447d66f19294c0Tim Peters pts[0] = p[0]; 500c377b16d12ba325bb108eca575447d66f19294c0Tim Peters pts[1] = cAvg; 501c377b16d12ba325bb108eca575447d66f19294c0Tim Peters pts[2] = p[3]; 502cf691935bb1a59bd7ff680b26b0b0040b7e25449Guido van Rossum return; 503cf691935bb1a59bd7ff680b26b0b0040b7e25449Guido van Rossum } 504c377b16d12ba325bb108eca575447d66f19294c0Tim Peters } 505cf691935bb1a59bd7ff680b26b0b0040b7e25449Guido van Rossum SkPoint choppedPts[7]; 506c377b16d12ba325bb108eca575447d66f19294c0Tim Peters SkChopCubicAtHalf(p, choppedPts); 507cf691935bb1a59bd7ff680b26b0b0040b7e25449Guido van Rossum convert_noninflect_cubic_to_quads(choppedPts + 0, 508cf691935bb1a59bd7ff680b26b0b0040b7e25449Guido van Rossum toleranceSqd, 509c377b16d12ba325bb108eca575447d66f19294c0Tim Peters constrainWithinTangents, 510cf691935bb1a59bd7ff680b26b0b0040b7e25449Guido van Rossum dir, 511c377b16d12ba325bb108eca575447d66f19294c0Tim Peters quads, 512c377b16d12ba325bb108eca575447d66f19294c0Tim Peters sublevel + 1); 513cf691935bb1a59bd7ff680b26b0b0040b7e25449Guido van Rossum convert_noninflect_cubic_to_quads(choppedPts + 3, 514cf691935bb1a59bd7ff680b26b0b0040b7e25449Guido van Rossum toleranceSqd, 515cf691935bb1a59bd7ff680b26b0b0040b7e25449Guido van Rossum constrainWithinTangents, 516c377b16d12ba325bb108eca575447d66f19294c0Tim Peters dir, 517cf691935bb1a59bd7ff680b26b0b0040b7e25449Guido van Rossum quads, 518c377b16d12ba325bb108eca575447d66f19294c0Tim Peters sublevel + 1); 519cf691935bb1a59bd7ff680b26b0b0040b7e25449Guido van Rossum} 520c377b16d12ba325bb108eca575447d66f19294c0Tim Peters} 521c377b16d12ba325bb108eca575447d66f19294c0Tim Peters 522cf691935bb1a59bd7ff680b26b0b0040b7e25449Guido van Rossumvoid GrPathUtils::convertCubicToQuads(const SkPoint p[4], 523c377b16d12ba325bb108eca575447d66f19294c0Tim Peters SkScalar tolScale, 524c377b16d12ba325bb108eca575447d66f19294c0Tim Peters bool constrainWithinTangents, 525c377b16d12ba325bb108eca575447d66f19294c0Tim Peters SkPath::Direction dir, 526c377b16d12ba325bb108eca575447d66f19294c0Tim Peters SkTArray<SkPoint, true>* quads) { 527c377b16d12ba325bb108eca575447d66f19294c0Tim Peters SkPoint chopped[10]; 528cf691935bb1a59bd7ff680b26b0b0040b7e25449Guido van Rossum int count = SkChopCubicAtInflections(p, chopped); 529c377b16d12ba325bb108eca575447d66f19294c0Tim Peters 530c377b16d12ba325bb108eca575447d66f19294c0Tim Peters // base tolerance is 1 pixel. 531cf691935bb1a59bd7ff680b26b0b0040b7e25449Guido van Rossum static const SkScalar kTolerance = SK_Scalar1; 532c377b16d12ba325bb108eca575447d66f19294c0Tim Peters const SkScalar tolSqd = SkScalarSquare(SkScalarMul(tolScale, kTolerance)); 533c377b16d12ba325bb108eca575447d66f19294c0Tim Peters 534cf691935bb1a59bd7ff680b26b0b0040b7e25449Guido van Rossum for (int i = 0; i < count; ++i) { 535cf691935bb1a59bd7ff680b26b0b0040b7e25449Guido van Rossum SkPoint* cubic = chopped + 3*i; 536c377b16d12ba325bb108eca575447d66f19294c0Tim Peters convert_noninflect_cubic_to_quads(cubic, tolSqd, constrainWithinTangents, dir, quads); 5370fcca4e815e3dbb28c73108376079a94ad6ee8deGuido van Rossum } 538152494aea24669a3d74460fa460a4ed45696bc75Guido van Rossum 539152494aea24669a3d74460fa460a4ed45696bc75Guido van Rossum} 540152494aea24669a3d74460fa460a4ed45696bc75Guido van Rossum 54141360a4696f488e49e5409b3b1baf1fff6ae0044Guido van Rossum//////////////////////////////////////////////////////////////////////////////// 542152494aea24669a3d74460fa460a4ed45696bc75Guido van Rossum 54341360a4696f488e49e5409b3b1baf1fff6ae0044Guido van Rossumenum CubicType { 544152494aea24669a3d74460fa460a4ed45696bc75Guido van Rossum kSerpentine_CubicType, 545152494aea24669a3d74460fa460a4ed45696bc75Guido van Rossum kCusp_CubicType, 546152494aea24669a3d74460fa460a4ed45696bc75Guido van Rossum kLoop_CubicType, 547c5000dfc4098f8547461e790a91536a923124261Tim Peters kQuadratic_CubicType, 548c5000dfc4098f8547461e790a91536a923124261Tim Peters kLine_CubicType, 549c5000dfc4098f8547461e790a91536a923124261Tim Peters kPoint_CubicType 550c5000dfc4098f8547461e790a91536a923124261Tim Peters}; 551c5000dfc4098f8547461e790a91536a923124261Tim Peters 552152494aea24669a3d74460fa460a4ed45696bc75Guido van Rossum// discr(I) = d0^2 * (3*d1^2 - 4*d0*d2) 553152494aea24669a3d74460fa460a4ed45696bc75Guido van Rossum// Classification: 55441360a4696f488e49e5409b3b1baf1fff6ae0044Guido van Rossum// discr(I) > 0 Serpentine 555152494aea24669a3d74460fa460a4ed45696bc75Guido van Rossum// discr(I) = 0 Cusp 55641360a4696f488e49e5409b3b1baf1fff6ae0044Guido van Rossum// discr(I) < 0 Loop 557152494aea24669a3d74460fa460a4ed45696bc75Guido van Rossum// d0 = d1 = 0 Quadratic 558a45da92484ceececf1cf32b4dfb16004945b001eTim Peters// d0 = d1 = d2 = 0 Line 5597c7efe90737d4636633127a95a6cab1a55d57cf4Tim Peters// p0 = p1 = p2 = p3 Point 560a45da92484ceececf1cf32b4dfb16004945b001eTim Petersstatic CubicType classify_cubic(const SkPoint p[4], const SkScalar d[3]) { 561a45da92484ceececf1cf32b4dfb16004945b001eTim Peters if (p[0] == p[1] && p[0] == p[2] && p[0] == p[3]) { 562a45da92484ceececf1cf32b4dfb16004945b001eTim Peters return kPoint_CubicType; 563a45da92484ceececf1cf32b4dfb16004945b001eTim Peters } 564a45da92484ceececf1cf32b4dfb16004945b001eTim Peters const SkScalar discr = d[0] * d[0] * (3.f * d[1] * d[1] - 4.f * d[0] * d[2]); 565a45da92484ceececf1cf32b4dfb16004945b001eTim Peters if (discr > SK_ScalarNearlyZero) { 566ba78bc4a3216b51398bab59157572a51c38b9ef4Tim Peters return kSerpentine_CubicType; 567ba78bc4a3216b51398bab59157572a51c38b9ef4Tim Peters } else if (discr < -SK_ScalarNearlyZero) { 568ba78bc4a3216b51398bab59157572a51c38b9ef4Tim Peters return kLoop_CubicType; 569ba78bc4a3216b51398bab59157572a51c38b9ef4Tim Peters } else { 570a45da92484ceececf1cf32b4dfb16004945b001eTim Peters if (0.f == d[0] && 0.f == d[1]) { 571de14a30d1d70073d36f207fe432e4adad5178399Tim Peters return (0.f == d[2] ? kLine_CubicType : kQuadratic_CubicType); 572de14a30d1d70073d36f207fe432e4adad5178399Tim Peters } else { 5732a182dbf3f2520ad753792068391775d102b13dfTim Peters return kCusp_CubicType; 5742a182dbf3f2520ad753792068391775d102b13dfTim Peters } 5752a182dbf3f2520ad753792068391775d102b13dfTim Peters } 5762a182dbf3f2520ad753792068391775d102b13dfTim Peters} 5772a182dbf3f2520ad753792068391775d102b13dfTim Peters 5781b445d3fcfcc06e5360e83b978efdb9b1c980278Tim Peters// Assumes the third component of points is 1. 5791b445d3fcfcc06e5360e83b978efdb9b1c980278Tim Peters// Calcs p0 . (p1 x p2) 5801b445d3fcfcc06e5360e83b978efdb9b1c980278Tim Petersstatic SkScalar calc_dot_cross_cubic(const SkPoint& p0, const SkPoint& p1, const SkPoint& p2) { 5811babdfc48afc60afe5ae708f77dad8a641bf36ecTim Peters const SkScalar xComp = p0.fX * (p1.fY - p2.fY); 582b4ee4eb3b308d55bd0d8d5a1abb2015950934c77Tim Peters const SkScalar yComp = p0.fY * (p2.fX - p1.fX); 583b4ee4eb3b308d55bd0d8d5a1abb2015950934c77Tim Peters const SkScalar wComp = p1.fX * p2.fY - p1.fY * p2.fX; 584b4ee4eb3b308d55bd0d8d5a1abb2015950934c77Tim Peters return (xComp + yComp + wComp); 58555b61d21d8e8409fbb6ca23421f8a3a5c23f5513Neal Norwitz} 58655b61d21d8e8409fbb6ca23421f8a3a5c23f5513Neal Norwitz 58755b61d21d8e8409fbb6ca23421f8a3a5c23f5513Neal Norwitz// Solves linear system to extract klm 5883e2a30692085d32ac63f72b35da39158a471fc68Hye-Shik Chang// P.K = k (similarly for l, m) 5893e2a30692085d32ac63f72b35da39158a471fc68Hye-Shik Chang// Where P is matrix of control points 5903e2a30692085d32ac63f72b35da39158a471fc68Hye-Shik Chang// K is coefficients for the line K 5913e2a30692085d32ac63f72b35da39158a471fc68Hye-Shik Chang// k is vector of values of K evaluated at the control points 592de14a30d1d70073d36f207fe432e4adad5178399Tim Peters// Solving for K, thus K = P^(-1) . k 593f73e30c3e3ba6f2779eadf6bf4c21c6bf3e4c075Guido van Rossumstatic void calc_cubic_klm(const SkPoint p[4], const SkScalar controlK[4], 594f73e30c3e3ba6f2779eadf6bf4c21c6bf3e4c075Guido van Rossum const SkScalar controlL[4], const SkScalar controlM[4], 595f73e30c3e3ba6f2779eadf6bf4c21c6bf3e4c075Guido van Rossum SkScalar k[3], SkScalar l[3], SkScalar m[3]) { 596c7c516aa5140d255f18ffd2e8569434f0904f5dbTim Peters SkMatrix matrix; 597901dc983168d4ca706ed664a8f5134ee3add26edRaymond Hettinger matrix.setAll(p[0].fX, p[0].fY, 1.f, 598f73e30c3e3ba6f2779eadf6bf4c21c6bf3e4c075Guido van Rossum p[1].fX, p[1].fY, 1.f, 599823ba28b0d436f83ebfc5b9df0d475e60e8ae5eeSkip Montanaro p[2].fX, p[2].fY, 1.f); 60078e35f931128d017d5955841eac8c397ff32595cTim Peters SkMatrix inverse; 601f73e30c3e3ba6f2779eadf6bf4c21c6bf3e4c075Guido van Rossum if (matrix.invert(&inverse)) { 602f73e30c3e3ba6f2779eadf6bf4c21c6bf3e4c075Guido van Rossum inverse.mapHomogeneousPoints(k, controlK, 1); 603f73e30c3e3ba6f2779eadf6bf4c21c6bf3e4c075Guido van Rossum inverse.mapHomogeneousPoints(l, controlL, 1); 604f73e30c3e3ba6f2779eadf6bf4c21c6bf3e4c075Guido van Rossum inverse.mapHomogeneousPoints(m, controlM, 1); 605d703057752d52cef6082a920879a0b62cdeffacaTim Peters } 606f73e30c3e3ba6f2779eadf6bf4c21c6bf3e4c075Guido van Rossum 607f73e30c3e3ba6f2779eadf6bf4c21c6bf3e4c075Guido van Rossum} 608f73e30c3e3ba6f2779eadf6bf4c21c6bf3e4c075Guido van Rossum 609f73e30c3e3ba6f2779eadf6bf4c21c6bf3e4c075Guido van Rossumstatic void set_serp_klm(const SkScalar d[3], SkScalar k[4], SkScalar l[4], SkScalar m[4]) { 610f73e30c3e3ba6f2779eadf6bf4c21c6bf3e4c075Guido van Rossum SkScalar tempSqrt = SkScalarSqrt(9.f * d[1] * d[1] - 12.f * d[0] * d[2]); 611f73e30c3e3ba6f2779eadf6bf4c21c6bf3e4c075Guido van Rossum SkScalar ls = 3.f * d[1] - tempSqrt; 612f73e30c3e3ba6f2779eadf6bf4c21c6bf3e4c075Guido van Rossum SkScalar lt = 6.f * d[0]; 613f73e30c3e3ba6f2779eadf6bf4c21c6bf3e4c075Guido van Rossum SkScalar ms = 3.f * d[1] + tempSqrt; 614fd8e6e599051de07cdb8e9abc9dbadf37c5fca0cTim Peters SkScalar mt = 6.f * d[0]; 615f73e30c3e3ba6f2779eadf6bf4c21c6bf3e4c075Guido van Rossum 616f73e30c3e3ba6f2779eadf6bf4c21c6bf3e4c075Guido van Rossum k[0] = ls * ms; 617f73e30c3e3ba6f2779eadf6bf4c21c6bf3e4c075Guido van Rossum k[1] = (3.f * ls * ms - ls * mt - lt * ms) / 3.f; 618de14a30d1d70073d36f207fe432e4adad5178399Tim Peters k[2] = (lt * (mt - 2.f * ms) + ls * (3.f * ms - 2.f * mt)) / 3.f; 619f73e30c3e3ba6f2779eadf6bf4c21c6bf3e4c075Guido van Rossum k[3] = (lt - ls) * (mt - ms); 620f73e30c3e3ba6f2779eadf6bf4c21c6bf3e4c075Guido van Rossum 621efc4b121694888e00072f5a079de5496afecb05aTim Peters l[0] = ls * ls * ls; 622f73e30c3e3ba6f2779eadf6bf4c21c6bf3e4c075Guido van Rossum const SkScalar lt_ls = lt - ls; 623003eb3088283927e3155f2e2317d3d516edd9645Tim Peters l[1] = ls * ls * lt_ls * -1.f; 624f73e30c3e3ba6f2779eadf6bf4c21c6bf3e4c075Guido van Rossum l[2] = lt_ls * lt_ls * ls; 625f73e30c3e3ba6f2779eadf6bf4c21c6bf3e4c075Guido van Rossum l[3] = -1.f * lt_ls * lt_ls * lt_ls; 6261e33ffa5c719ec611e182681c4a5f2ceb62a08f5Tim Peters 627f73e30c3e3ba6f2779eadf6bf4c21c6bf3e4c075Guido van Rossum m[0] = ms * ms * ms; 628f73e30c3e3ba6f2779eadf6bf4c21c6bf3e4c075Guido van Rossum const SkScalar mt_ms = mt - ms; 629f73e30c3e3ba6f2779eadf6bf4c21c6bf3e4c075Guido van Rossum m[1] = ms * ms * mt_ms * -1.f; 630f73e30c3e3ba6f2779eadf6bf4c21c6bf3e4c075Guido van Rossum m[2] = mt_ms * mt_ms * ms; 631f73e30c3e3ba6f2779eadf6bf4c21c6bf3e4c075Guido van Rossum m[3] = -1.f * mt_ms * mt_ms * mt_ms; 632f73e30c3e3ba6f2779eadf6bf4c21c6bf3e4c075Guido van Rossum 633f73e30c3e3ba6f2779eadf6bf4c21c6bf3e4c075Guido van Rossum // If d0 < 0 we need to flip the orientation of our curve 634944a6c32d7f78445e3516636d9fcf1c62e1663ffGuido van Rossum // This is done by negating the k and l values 635823ba28b0d436f83ebfc5b9df0d475e60e8ae5eeSkip Montanaro // We want negative distance values to be on the inside 636f73e30c3e3ba6f2779eadf6bf4c21c6bf3e4c075Guido van Rossum if ( d[0] > 0) { 637f73e30c3e3ba6f2779eadf6bf4c21c6bf3e4c075Guido van Rossum for (int i = 0; i < 4; ++i) { 638f66dacdb017c7481c3ba4f0743d5446146de33c8Guido van Rossum k[i] = -k[i]; 639f73e30c3e3ba6f2779eadf6bf4c21c6bf3e4c075Guido van Rossum l[i] = -l[i]; 640f73e30c3e3ba6f2779eadf6bf4c21c6bf3e4c075Guido van Rossum } 641f73e30c3e3ba6f2779eadf6bf4c21c6bf3e4c075Guido van Rossum } 642f73e30c3e3ba6f2779eadf6bf4c21c6bf3e4c075Guido van Rossum} 6434507ec70cff35468f4b1767382f38ecebd4a29a2Guido van Rossum 644f73e30c3e3ba6f2779eadf6bf4c21c6bf3e4c075Guido van Rossumstatic void set_loop_klm(const SkScalar d[3], SkScalar k[4], SkScalar l[4], SkScalar m[4]) { 645f73e30c3e3ba6f2779eadf6bf4c21c6bf3e4c075Guido van Rossum SkScalar tempSqrt = SkScalarSqrt(4.f * d[0] * d[2] - 3.f * d[1] * d[1]); 6464507ec70cff35468f4b1767382f38ecebd4a29a2Guido van Rossum SkScalar ls = d[1] - tempSqrt; 647f73e30c3e3ba6f2779eadf6bf4c21c6bf3e4c075Guido van Rossum SkScalar lt = 2.f * d[0]; 648f73e30c3e3ba6f2779eadf6bf4c21c6bf3e4c075Guido van Rossum SkScalar ms = d[1] + tempSqrt; 64949a806edbb298f2a5be3598bd80c21392cb6968dJack Jansen SkScalar mt = 2.f * d[0]; 650aa78236636d62a07af4759b64ea89452c6690c7eGuido van Rossum 651aa78236636d62a07af4759b64ea89452c6690c7eGuido van Rossum k[0] = ls * ms; 652679751455798fab6425fda749a19e783e58b210eJack Jansen k[1] = (3.f * ls*ms - ls * mt - lt * ms) / 3.f; 653aa78236636d62a07af4759b64ea89452c6690c7eGuido van Rossum k[2] = (lt * (mt - 2.f * ms) + ls * (3.f * ms - 2.f * mt)) / 3.f; 654823ba28b0d436f83ebfc5b9df0d475e60e8ae5eeSkip Montanaro k[3] = (lt - ls) * (mt - ms); 655679751455798fab6425fda749a19e783e58b210eJack Jansen 656679751455798fab6425fda749a19e783e58b210eJack Jansen l[0] = ls * ls * ms; 657aa78236636d62a07af4759b64ea89452c6690c7eGuido van Rossum l[1] = (ls * (ls * (mt - 3.f * ms) + 2.f * lt * ms))/-3.f; 658aa78236636d62a07af4759b64ea89452c6690c7eGuido van Rossum l[2] = ((lt - ls) * (ls * (2.f * mt - 3.f * ms) + lt * ms))/3.f; 659aa78236636d62a07af4759b64ea89452c6690c7eGuido van Rossum l[3] = -1.f * (lt - ls) * (lt - ls) * (mt - ms); 660aa78236636d62a07af4759b64ea89452c6690c7eGuido van Rossum 661b3be216b41a4755556a887baa6ab440279fbe1dcJack Jansen m[0] = ls * ms * ms; 662aa78236636d62a07af4759b64ea89452c6690c7eGuido van Rossum m[1] = (ms * (ls * (2.f * mt - 3.f * ms) + lt * ms))/-3.f; 663aa78236636d62a07af4759b64ea89452c6690c7eGuido van Rossum m[2] = ((mt - ms) * (ls * (mt - 3.f * ms) + 2.f * lt * ms))/3.f; 664aa78236636d62a07af4759b64ea89452c6690c7eGuido van Rossum m[3] = -1.f * (lt - ls) * (mt - ms) * (mt - ms); 665aa78236636d62a07af4759b64ea89452c6690c7eGuido van Rossum 666aa78236636d62a07af4759b64ea89452c6690c7eGuido van Rossum 667aa78236636d62a07af4759b64ea89452c6690c7eGuido van Rossum // If (d0 < 0 && sign(k1) > 0) || (d0 > 0 && sign(k1) < 0), 668c4d6bdd58a58b365556abfe60c9f5b5f73c555f8Jack Jansen // we need to flip the orientation of our curve. 669aa78236636d62a07af4759b64ea89452c6690c7eGuido van Rossum // This is done by negating the k and l values 670aa78236636d62a07af4759b64ea89452c6690c7eGuido van Rossum if ( (d[0] < 0 && k[1] > 0) || (d[0] > 0 && k[1] < 0)) { 671aa78236636d62a07af4759b64ea89452c6690c7eGuido van Rossum for (int i = 0; i < 4; ++i) { 672aa78236636d62a07af4759b64ea89452c6690c7eGuido van Rossum k[i] = -k[i]; 673aa78236636d62a07af4759b64ea89452c6690c7eGuido van Rossum l[i] = -l[i]; 674679751455798fab6425fda749a19e783e58b210eJack Jansen } 675aa78236636d62a07af4759b64ea89452c6690c7eGuido van Rossum } 676aa78236636d62a07af4759b64ea89452c6690c7eGuido van Rossum} 677aa78236636d62a07af4759b64ea89452c6690c7eGuido van Rossum 678679751455798fab6425fda749a19e783e58b210eJack Jansenstatic void set_cusp_klm(const SkScalar d[3], SkScalar k[4], SkScalar l[4], SkScalar m[4]) { 679aa78236636d62a07af4759b64ea89452c6690c7eGuido van Rossum const SkScalar ls = d[2]; 680679751455798fab6425fda749a19e783e58b210eJack Jansen const SkScalar lt = 3.f * d[1]; 681aa78236636d62a07af4759b64ea89452c6690c7eGuido van Rossum 6825bb97e66dcbb110877ac17209c7d2641db6f6006Jack Jansen k[0] = ls; 683aa78236636d62a07af4759b64ea89452c6690c7eGuido van Rossum k[1] = ls - lt / 3.f; 684aa78236636d62a07af4759b64ea89452c6690c7eGuido van Rossum k[2] = ls - 2.f * lt / 3.f; 685679751455798fab6425fda749a19e783e58b210eJack Jansen k[3] = ls - lt; 686aa78236636d62a07af4759b64ea89452c6690c7eGuido van Rossum 687aa78236636d62a07af4759b64ea89452c6690c7eGuido van Rossum l[0] = ls * ls * ls; 688aa78236636d62a07af4759b64ea89452c6690c7eGuido van Rossum const SkScalar ls_lt = ls - lt; 689c4d6bdd58a58b365556abfe60c9f5b5f73c555f8Jack Jansen l[1] = ls * ls * ls_lt; 690aa78236636d62a07af4759b64ea89452c6690c7eGuido van Rossum l[2] = ls_lt * ls_lt * ls; 691aa78236636d62a07af4759b64ea89452c6690c7eGuido van Rossum l[3] = ls_lt * ls_lt * ls_lt; 69221ee4091e10c6f05360bbb60e49aa3639408a612Martin v. Löwis 6930ace326ed2ec73dfa515c89ad06fcddd6fafa4ceMartin v. Löwis m[0] = 1.f; 6940ace326ed2ec73dfa515c89ad06fcddd6fafa4ceMartin v. Löwis m[1] = 1.f; 695944a6c32d7f78445e3516636d9fcf1c62e1663ffGuido van Rossum m[2] = 1.f; 6960ace326ed2ec73dfa515c89ad06fcddd6fafa4ceMartin v. Löwis m[3] = 1.f; 697823ba28b0d436f83ebfc5b9df0d475e60e8ae5eeSkip Montanaro} 6980ace326ed2ec73dfa515c89ad06fcddd6fafa4ceMartin v. Löwis 6990ace326ed2ec73dfa515c89ad06fcddd6fafa4ceMartin v. Löwis// For the case when a cubic is actually a quadratic 7000ace326ed2ec73dfa515c89ad06fcddd6fafa4ceMartin v. Löwis// M = 7010ace326ed2ec73dfa515c89ad06fcddd6fafa4ceMartin v. Löwis// 0 0 0 7020ace326ed2ec73dfa515c89ad06fcddd6fafa4ceMartin v. Löwis// 1/3 0 1/3 7030ace326ed2ec73dfa515c89ad06fcddd6fafa4ceMartin v. Löwis// 2/3 1/3 2/3 7040ace326ed2ec73dfa515c89ad06fcddd6fafa4ceMartin v. Löwis// 1 1 1 7050ace326ed2ec73dfa515c89ad06fcddd6fafa4ceMartin v. Löwisstatic void set_quadratic_klm(const SkScalar d[3], SkScalar k[4], SkScalar l[4], SkScalar m[4]) { 7060ace326ed2ec73dfa515c89ad06fcddd6fafa4ceMartin v. Löwis k[0] = 0.f; 7070ace326ed2ec73dfa515c89ad06fcddd6fafa4ceMartin v. Löwis k[1] = 1.f/3.f; 7080ace326ed2ec73dfa515c89ad06fcddd6fafa4ceMartin v. Löwis k[2] = 2.f/3.f; 7090ace326ed2ec73dfa515c89ad06fcddd6fafa4ceMartin v. Löwis k[3] = 1.f; 7100ace326ed2ec73dfa515c89ad06fcddd6fafa4ceMartin v. Löwis 7110ace326ed2ec73dfa515c89ad06fcddd6fafa4ceMartin v. Löwis l[0] = 0.f; 7120ace326ed2ec73dfa515c89ad06fcddd6fafa4ceMartin v. Löwis l[1] = 0.f; 7130ace326ed2ec73dfa515c89ad06fcddd6fafa4ceMartin v. Löwis l[2] = 1.f/3.f; 71421ee4091e10c6f05360bbb60e49aa3639408a612Martin v. Löwis l[3] = 1.f; 71521ee4091e10c6f05360bbb60e49aa3639408a612Martin v. Löwis 71621ee4091e10c6f05360bbb60e49aa3639408a612Martin v. Löwis m[0] = 0.f; 717944a6c32d7f78445e3516636d9fcf1c62e1663ffGuido van Rossum m[1] = 1.f/3.f; 71821ee4091e10c6f05360bbb60e49aa3639408a612Martin v. Löwis m[2] = 2.f/3.f; 719823ba28b0d436f83ebfc5b9df0d475e60e8ae5eeSkip Montanaro m[3] = 1.f; 72021ee4091e10c6f05360bbb60e49aa3639408a612Martin v. Löwis 72121ee4091e10c6f05360bbb60e49aa3639408a612Martin v. Löwis // If d2 < 0 we need to flip the orientation of our curve 72221ee4091e10c6f05360bbb60e49aa3639408a612Martin v. Löwis // This is done by negating the k and l values 72321ee4091e10c6f05360bbb60e49aa3639408a612Martin v. Löwis if ( d[2] > 0) { 72421ee4091e10c6f05360bbb60e49aa3639408a612Martin v. Löwis for (int i = 0; i < 4; ++i) { 72521ee4091e10c6f05360bbb60e49aa3639408a612Martin v. Löwis k[i] = -k[i]; 72621ee4091e10c6f05360bbb60e49aa3639408a612Martin v. Löwis l[i] = -l[i]; 72721ee4091e10c6f05360bbb60e49aa3639408a612Martin v. Löwis } 72821ee4091e10c6f05360bbb60e49aa3639408a612Martin v. Löwis } 72921ee4091e10c6f05360bbb60e49aa3639408a612Martin v. Löwis} 73021ee4091e10c6f05360bbb60e49aa3639408a612Martin v. Löwis 73121ee4091e10c6f05360bbb60e49aa3639408a612Martin v. Löwis// Calc coefficients of I(s,t) where roots of I are inflection points of curve 73221ee4091e10c6f05360bbb60e49aa3639408a612Martin v. Löwis// I(s,t) = t*(3*d0*s^2 - 3*d1*s*t + d2*t^2) 73321ee4091e10c6f05360bbb60e49aa3639408a612Martin v. Löwis// d0 = a1 - 2*a2+3*a3 73421ee4091e10c6f05360bbb60e49aa3639408a612Martin v. Löwis// d1 = -a2 + 3*a3 73521ee4091e10c6f05360bbb60e49aa3639408a612Martin v. Löwis// d2 = 3*a3 73621ee4091e10c6f05360bbb60e49aa3639408a612Martin v. Löwis// a1 = p0 . (p3 x p2) 73721ee4091e10c6f05360bbb60e49aa3639408a612Martin v. Löwis// a2 = p1 . (p0 x p3) 73821ee4091e10c6f05360bbb60e49aa3639408a612Martin v. Löwis// a3 = p2 . (p1 x p0) 739944a6c32d7f78445e3516636d9fcf1c62e1663ffGuido van Rossum// Places the values of d1, d2, d3 in array d passed in 74021ee4091e10c6f05360bbb60e49aa3639408a612Martin v. Löwisstatic void calc_cubic_inflection_func(const SkPoint p[4], SkScalar d[3]) { 74121ee4091e10c6f05360bbb60e49aa3639408a612Martin v. Löwis SkScalar a1 = calc_dot_cross_cubic(p[0], p[3], p[2]); 742823ba28b0d436f83ebfc5b9df0d475e60e8ae5eeSkip Montanaro SkScalar a2 = calc_dot_cross_cubic(p[1], p[0], p[3]); 74321ee4091e10c6f05360bbb60e49aa3639408a612Martin v. Löwis SkScalar a3 = calc_dot_cross_cubic(p[2], p[1], p[0]); 74421ee4091e10c6f05360bbb60e49aa3639408a612Martin v. Löwis 74521ee4091e10c6f05360bbb60e49aa3639408a612Martin v. Löwis // need to scale a's or values in later calculations will grow to high 74621ee4091e10c6f05360bbb60e49aa3639408a612Martin v. Löwis SkScalar max = SkScalarAbs(a1); 74721ee4091e10c6f05360bbb60e49aa3639408a612Martin v. Löwis max = SkMaxScalar(max, SkScalarAbs(a2)); 74821ee4091e10c6f05360bbb60e49aa3639408a612Martin v. Löwis max = SkMaxScalar(max, SkScalarAbs(a3)); 74921ee4091e10c6f05360bbb60e49aa3639408a612Martin v. Löwis max = 1.f/max; 75021ee4091e10c6f05360bbb60e49aa3639408a612Martin v. Löwis a1 = a1 * max; 75121ee4091e10c6f05360bbb60e49aa3639408a612Martin v. Löwis a2 = a2 * max; 75221ee4091e10c6f05360bbb60e49aa3639408a612Martin v. Löwis a3 = a3 * max; 75321ee4091e10c6f05360bbb60e49aa3639408a612Martin v. Löwis 75421ee4091e10c6f05360bbb60e49aa3639408a612Martin v. Löwis d[2] = 3.f * a3; 75521ee4091e10c6f05360bbb60e49aa3639408a612Martin v. Löwis d[1] = d[2] - a2; 75621ee4091e10c6f05360bbb60e49aa3639408a612Martin v. Löwis d[0] = d[1] - a2 + a1; 75721ee4091e10c6f05360bbb60e49aa3639408a612Martin v. Löwis} 75821ee4091e10c6f05360bbb60e49aa3639408a612Martin v. Löwis 75921ee4091e10c6f05360bbb60e49aa3639408a612Martin v. Löwisint GrPathUtils::chopCubicAtLoopIntersection(const SkPoint src[4], SkPoint dst[10], SkScalar klm[9], 76021ee4091e10c6f05360bbb60e49aa3639408a612Martin v. Löwis SkScalar klm_rev[3]) { 76121ee4091e10c6f05360bbb60e49aa3639408a612Martin v. Löwis // Variable to store the two parametric values at the loop double point 76221ee4091e10c6f05360bbb60e49aa3639408a612Martin v. Löwis SkScalar smallS = 0.f; 76321ee4091e10c6f05360bbb60e49aa3639408a612Martin v. Löwis SkScalar largeS = 0.f; 76421ee4091e10c6f05360bbb60e49aa3639408a612Martin v. Löwis 76521ee4091e10c6f05360bbb60e49aa3639408a612Martin v. Löwis SkScalar d[3]; 76621ee4091e10c6f05360bbb60e49aa3639408a612Martin v. Löwis calc_cubic_inflection_func(src, d); 767e2ae77b8b8a62e648bb1864a9b36ef3280984404Guido van Rossum 768e2ae77b8b8a62e648bb1864a9b36ef3280984404Guido van Rossum CubicType cType = classify_cubic(src, d); 769e2ae77b8b8a62e648bb1864a9b36ef3280984404Guido van Rossum 770944a6c32d7f78445e3516636d9fcf1c62e1663ffGuido van Rossum int chop_count = 0; 771e2ae77b8b8a62e648bb1864a9b36ef3280984404Guido van Rossum if (kLoop_CubicType == cType) { 772a94568a7535de60f1144e4eea0d027b87017a4b4Martin v. Löwis SkScalar tempSqrt = SkScalarSqrt(4.f * d[0] * d[2] - 3.f * d[1] * d[1]); 773e2ae77b8b8a62e648bb1864a9b36ef3280984404Guido van Rossum SkScalar ls = d[1] - tempSqrt; 774823ba28b0d436f83ebfc5b9df0d475e60e8ae5eeSkip Montanaro SkScalar lt = 2.f * d[0]; 775a94568a7535de60f1144e4eea0d027b87017a4b4Martin v. Löwis SkScalar ms = d[1] + tempSqrt; 776e2ae77b8b8a62e648bb1864a9b36ef3280984404Guido van Rossum SkScalar mt = 2.f * d[0]; 777e2ae77b8b8a62e648bb1864a9b36ef3280984404Guido van Rossum ls = ls / lt; 778e2ae77b8b8a62e648bb1864a9b36ef3280984404Guido van Rossum ms = ms / mt; 779e2ae77b8b8a62e648bb1864a9b36ef3280984404Guido van Rossum // need to have t values sorted since this is what is expected by SkChopCubicAt 780e2ae77b8b8a62e648bb1864a9b36ef3280984404Guido van Rossum if (ls <= ms) { 781e2ae77b8b8a62e648bb1864a9b36ef3280984404Guido van Rossum smallS = ls; 782e2ae77b8b8a62e648bb1864a9b36ef3280984404Guido van Rossum largeS = ms; 783e2ae77b8b8a62e648bb1864a9b36ef3280984404Guido van Rossum } else { 784e2ae77b8b8a62e648bb1864a9b36ef3280984404Guido van Rossum smallS = ms; 785e2ae77b8b8a62e648bb1864a9b36ef3280984404Guido van Rossum largeS = ls; 786e2ae77b8b8a62e648bb1864a9b36ef3280984404Guido van Rossum } 787e2ae77b8b8a62e648bb1864a9b36ef3280984404Guido van Rossum 788e2ae77b8b8a62e648bb1864a9b36ef3280984404Guido van Rossum SkScalar chop_ts[2]; 789e2ae77b8b8a62e648bb1864a9b36ef3280984404Guido van Rossum if (smallS > 0.f && smallS < 1.f) { 790e2ae77b8b8a62e648bb1864a9b36ef3280984404Guido van Rossum chop_ts[chop_count++] = smallS; 791e2ae77b8b8a62e648bb1864a9b36ef3280984404Guido van Rossum } 792e2ae77b8b8a62e648bb1864a9b36ef3280984404Guido van Rossum if (largeS > 0.f && largeS < 1.f) { 793e2ae77b8b8a62e648bb1864a9b36ef3280984404Guido van Rossum chop_ts[chop_count++] = largeS; 794e2ae77b8b8a62e648bb1864a9b36ef3280984404Guido van Rossum } 795e2ae77b8b8a62e648bb1864a9b36ef3280984404Guido van Rossum if(dst) { 796e2ae77b8b8a62e648bb1864a9b36ef3280984404Guido van Rossum SkChopCubicAt(src, dst, chop_ts, chop_count); 797e2ae77b8b8a62e648bb1864a9b36ef3280984404Guido van Rossum } 798e2ae77b8b8a62e648bb1864a9b36ef3280984404Guido van Rossum } else { 799e2ae77b8b8a62e648bb1864a9b36ef3280984404Guido van Rossum if (dst) { 800e2ae77b8b8a62e648bb1864a9b36ef3280984404Guido van Rossum memcpy(dst, src, sizeof(SkPoint) * 4); 801e2ae77b8b8a62e648bb1864a9b36ef3280984404Guido van Rossum } 802e2ae77b8b8a62e648bb1864a9b36ef3280984404Guido van Rossum } 803e2ae77b8b8a62e648bb1864a9b36ef3280984404Guido van Rossum 804e2ae77b8b8a62e648bb1864a9b36ef3280984404Guido van Rossum if (klm && klm_rev) { 805e2ae77b8b8a62e648bb1864a9b36ef3280984404Guido van Rossum // Set klm_rev to to match the sub_section of cubic that needs to have its orientation 806e2ae77b8b8a62e648bb1864a9b36ef3280984404Guido van Rossum // flipped. This will always be the section that is the "loop" 807e2ae77b8b8a62e648bb1864a9b36ef3280984404Guido van Rossum if (2 == chop_count) { 8088a97f4a380a7a356730e48406f8269c3efe5e6ebJack Jansen klm_rev[0] = 1.f; 809398c236c1ba358a43a34137dc9ca670d76f7eb84Jack Jansen klm_rev[1] = -1.f; 8102bfb94c871caeae622174485264f407d9df354b9Brett Cannon klm_rev[2] = 1.f; 811398c236c1ba358a43a34137dc9ca670d76f7eb84Jack Jansen } else if (1 == chop_count) { 812acda3394bbfb1db3b22673a80cb2d7e3c68b3da9Jack Jansen if (smallS < 0.f) { 8139d4270070a5d0c3bcd381d52024d811f3b0a0e39Guido van Rossum klm_rev[0] = -1.f; 814398c236c1ba358a43a34137dc9ca670d76f7eb84Jack Jansen klm_rev[1] = 1.f; 815398c236c1ba358a43a34137dc9ca670d76f7eb84Jack Jansen } else { 816398c236c1ba358a43a34137dc9ca670d76f7eb84Jack Jansen klm_rev[0] = 1.f; 817398c236c1ba358a43a34137dc9ca670d76f7eb84Jack Jansen klm_rev[1] = -1.f; 818398c236c1ba358a43a34137dc9ca670d76f7eb84Jack Jansen } 819398c236c1ba358a43a34137dc9ca670d76f7eb84Jack Jansen } else { 820398c236c1ba358a43a34137dc9ca670d76f7eb84Jack Jansen if (smallS < 0.f && largeS > 1.f) { 821398c236c1ba358a43a34137dc9ca670d76f7eb84Jack Jansen klm_rev[0] = -1.f; 822398c236c1ba358a43a34137dc9ca670d76f7eb84Jack Jansen } else { 823acda3394bbfb1db3b22673a80cb2d7e3c68b3da9Jack Jansen klm_rev[0] = 1.f; 824398c236c1ba358a43a34137dc9ca670d76f7eb84Jack Jansen } 8259d4270070a5d0c3bcd381d52024d811f3b0a0e39Guido van Rossum } 826398c236c1ba358a43a34137dc9ca670d76f7eb84Jack Jansen SkScalar controlK[4]; 827398c236c1ba358a43a34137dc9ca670d76f7eb84Jack Jansen SkScalar controlL[4]; 828acda3394bbfb1db3b22673a80cb2d7e3c68b3da9Jack Jansen SkScalar controlM[4]; 829398c236c1ba358a43a34137dc9ca670d76f7eb84Jack Jansen 830398c236c1ba358a43a34137dc9ca670d76f7eb84Jack Jansen if (kSerpentine_CubicType == cType || (kCusp_CubicType == cType && 0.f != d[0])) { 831398c236c1ba358a43a34137dc9ca670d76f7eb84Jack Jansen set_serp_klm(d, controlK, controlL, controlM); 83211c3f0999f932e3697347dde15f99a8ad9f9216dGuido van Rossum } else if (kLoop_CubicType == cType) { 83311c3f0999f932e3697347dde15f99a8ad9f9216dGuido van Rossum set_loop_klm(d, controlK, controlL, controlM); 83411c3f0999f932e3697347dde15f99a8ad9f9216dGuido van Rossum } else if (kCusp_CubicType == cType) { 835944a6c32d7f78445e3516636d9fcf1c62e1663ffGuido van Rossum SkASSERT(0.f == d[0]); 83611c3f0999f932e3697347dde15f99a8ad9f9216dGuido van Rossum set_cusp_klm(d, controlK, controlL, controlM); 837823ba28b0d436f83ebfc5b9df0d475e60e8ae5eeSkip Montanaro } else if (kQuadratic_CubicType == cType) { 83811c3f0999f932e3697347dde15f99a8ad9f9216dGuido van Rossum set_quadratic_klm(d, controlK, controlL, controlM); 83911c3f0999f932e3697347dde15f99a8ad9f9216dGuido van Rossum } 84011c3f0999f932e3697347dde15f99a8ad9f9216dGuido van Rossum 84111c3f0999f932e3697347dde15f99a8ad9f9216dGuido van Rossum calc_cubic_klm(src, controlK, controlL, controlM, klm, &klm[3], &klm[6]); 84211c3f0999f932e3697347dde15f99a8ad9f9216dGuido van Rossum } 84311c3f0999f932e3697347dde15f99a8ad9f9216dGuido van Rossum return chop_count + 1; 84411c3f0999f932e3697347dde15f99a8ad9f9216dGuido van Rossum} 84511c3f0999f932e3697347dde15f99a8ad9f9216dGuido van Rossum 84611c3f0999f932e3697347dde15f99a8ad9f9216dGuido van Rossumvoid GrPathUtils::getCubicKLM(const SkPoint p[4], SkScalar klm[9]) { 84711c3f0999f932e3697347dde15f99a8ad9f9216dGuido van Rossum SkScalar d[3]; 84811c3f0999f932e3697347dde15f99a8ad9f9216dGuido van Rossum calc_cubic_inflection_func(p, d); 84911c3f0999f932e3697347dde15f99a8ad9f9216dGuido van Rossum 85011c3f0999f932e3697347dde15f99a8ad9f9216dGuido van Rossum CubicType cType = classify_cubic(p, d); 851ed375e18d10d37bfea1769aa1fe69795df6cbc10Jeremy Hylton 852b32302176e127a94b714f90c858b6e9c476fc7feSkip Montanaro SkScalar controlK[4]; 853b32302176e127a94b714f90c858b6e9c476fc7feSkip Montanaro SkScalar controlL[4]; 854b32302176e127a94b714f90c858b6e9c476fc7feSkip Montanaro SkScalar controlM[4]; 855944a6c32d7f78445e3516636d9fcf1c62e1663ffGuido van Rossum 856b32302176e127a94b714f90c858b6e9c476fc7feSkip Montanaro if (kSerpentine_CubicType == cType || (kCusp_CubicType == cType && 0.f != d[0])) { 857823ba28b0d436f83ebfc5b9df0d475e60e8ae5eeSkip Montanaro set_serp_klm(d, controlK, controlL, controlM); 858b32302176e127a94b714f90c858b6e9c476fc7feSkip Montanaro } else if (kLoop_CubicType == cType) { 859b32302176e127a94b714f90c858b6e9c476fc7feSkip Montanaro set_loop_klm(d, controlK, controlL, controlM); 860b32302176e127a94b714f90c858b6e9c476fc7feSkip Montanaro } else if (kCusp_CubicType == cType) { 861b32302176e127a94b714f90c858b6e9c476fc7feSkip Montanaro SkASSERT(0.f == d[0]); 862b32302176e127a94b714f90c858b6e9c476fc7feSkip Montanaro set_cusp_klm(d, controlK, controlL, controlM); 863b32302176e127a94b714f90c858b6e9c476fc7feSkip Montanaro } else if (kQuadratic_CubicType == cType) { 864b32302176e127a94b714f90c858b6e9c476fc7feSkip Montanaro set_quadratic_klm(d, controlK, controlL, controlM); 865b32302176e127a94b714f90c858b6e9c476fc7feSkip Montanaro } 866b32302176e127a94b714f90c858b6e9c476fc7feSkip Montanaro 867b32302176e127a94b714f90c858b6e9c476fc7feSkip Montanaro calc_cubic_klm(p, controlK, controlL, controlM, klm, &klm[3], &klm[6]); 868b32302176e127a94b714f90c858b6e9c476fc7feSkip Montanaro} 869b32302176e127a94b714f90c858b6e9c476fc7feSkip Montanaro