1ec3ed6a5ebf6f2c406d7bcf94b6bc34fcaeb976eepoger@google.com/* 2ec3ed6a5ebf6f2c406d7bcf94b6bc34fcaeb976eepoger@google.com * Copyright 2011 Google Inc. 3ec3ed6a5ebf6f2c406d7bcf94b6bc34fcaeb976eepoger@google.com * 4ec3ed6a5ebf6f2c406d7bcf94b6bc34fcaeb976eepoger@google.com * Use of this source code is governed by a BSD-style license that can be 5ec3ed6a5ebf6f2c406d7bcf94b6bc34fcaeb976eepoger@google.com * found in the LICENSE file. 69d18b7873ce9b44f130a41e0cbd0a3df76ab9adfsenorblanco@chromium.org */ 79d18b7873ce9b44f130a41e0cbd0a3df76ab9adfsenorblanco@chromium.org 89d18b7873ce9b44f130a41e0cbd0a3df76ab9adfsenorblanco@chromium.org#include "GrPathUtils.h" 9fd03d4a829efe2d77a712fd991927c55f59a2ffecommit-bot@chromium.org 10d537341e16524d1e22ac5e6c8b9c8f274ba1833crobertphillips#include "GrTypes.h" 1169cc6ad20ed03f35f9d3c8119a2c32187669a22bbsalomon@google.com#include "SkGeometry.h" 129d18b7873ce9b44f130a41e0cbd0a3df76ab9adfsenorblanco@chromium.org 1381712883419f76e25d2ffec38a9438284a45a48dbsalomon@google.comSkScalar GrPathUtils::scaleToleranceToSrc(SkScalar devTol, 14b9086a026844e4cfd08b219e49ce3f12294cba98bsalomon@google.com const SkMatrix& viewM, 15fd03d4a829efe2d77a712fd991927c55f59a2ffecommit-bot@chromium.org const SkRect& pathBounds) { 16181e9bd9484ece4132e0cc5cfcff602134e5489dbsalomon@google.com // In order to tesselate the path we get a bound on how much the matrix can 171878651990d7c9da72cf43481432232bbef3550dcommit-bot@chromium.org // scale when mapping to screen coordinates. 181878651990d7c9da72cf43481432232bbef3550dcommit-bot@chromium.org SkScalar stretch = viewM.getMaxScale(); 1981712883419f76e25d2ffec38a9438284a45a48dbsalomon@google.com SkScalar srcTol = devTol; 20181e9bd9484ece4132e0cc5cfcff602134e5489dbsalomon@google.com 21181e9bd9484ece4132e0cc5cfcff602134e5489dbsalomon@google.com if (stretch < 0) { 22383963280ddd13030331765fe88d2aefa3e32130bsalomon@google.com // take worst case mapRadius amoung four corners. 23383963280ddd13030331765fe88d2aefa3e32130bsalomon@google.com // (less than perfect) 24383963280ddd13030331765fe88d2aefa3e32130bsalomon@google.com for (int i = 0; i < 4; ++i) { 25b9086a026844e4cfd08b219e49ce3f12294cba98bsalomon@google.com SkMatrix mat; 26383963280ddd13030331765fe88d2aefa3e32130bsalomon@google.com mat.setTranslate((i % 2) ? pathBounds.fLeft : pathBounds.fRight, 27383963280ddd13030331765fe88d2aefa3e32130bsalomon@google.com (i < 2) ? pathBounds.fTop : pathBounds.fBottom); 28383963280ddd13030331765fe88d2aefa3e32130bsalomon@google.com mat.postConcat(viewM); 29383963280ddd13030331765fe88d2aefa3e32130bsalomon@google.com stretch = SkMaxScalar(stretch, mat.mapRadius(SK_Scalar1)); 30383963280ddd13030331765fe88d2aefa3e32130bsalomon@google.com } 31181e9bd9484ece4132e0cc5cfcff602134e5489dbsalomon@google.com } 3281712883419f76e25d2ffec38a9438284a45a48dbsalomon@google.com srcTol = SkScalarDiv(srcTol, stretch); 33181e9bd9484ece4132e0cc5cfcff602134e5489dbsalomon@google.com return srcTol; 34181e9bd9484ece4132e0cc5cfcff602134e5489dbsalomon@google.com} 35181e9bd9484ece4132e0cc5cfcff602134e5489dbsalomon@google.com 36b5b3168a645802f66233234a06dd5a3764f18018bsalomon@google.comstatic const int MAX_POINTS_PER_CURVE = 1 << 10; 374b413c8bb123e42ca4b9c7bfa6bc2167283cb84ccommit-bot@chromium.orgstatic const SkScalar gMinCurveTol = 0.0001f; 389d18b7873ce9b44f130a41e0cbd0a3df76ab9adfsenorblanco@chromium.org 39972f9cd7a063d0544f8c919fd12b9a3adbd12b24commit-bot@chromium.orguint32_t GrPathUtils::quadraticPointCount(const SkPoint points[], 4081712883419f76e25d2ffec38a9438284a45a48dbsalomon@google.com SkScalar tol) { 41c10a88825d119054a9f4e7b7af7a3f887e30ab6btomhudson@google.com if (tol < gMinCurveTol) { 42afec7ba75962517b17293799d3fc70d39fa7dbf2tomhudson@google.com tol = gMinCurveTol; 43c10a88825d119054a9f4e7b7af7a3f887e30ab6btomhudson@google.com } 44f6de475e5cbd143f348ff7738919e397b7fe7f57tfarina@chromium.org SkASSERT(tol > 0); 45c10a88825d119054a9f4e7b7af7a3f887e30ab6btomhudson@google.com 4681712883419f76e25d2ffec38a9438284a45a48dbsalomon@google.com SkScalar d = points[1].distanceToLineSegmentBetween(points[0], points[2]); 47c10a88825d119054a9f4e7b7af7a3f887e30ab6btomhudson@google.com if (d <= tol) { 489d18b7873ce9b44f130a41e0cbd0a3df76ab9adfsenorblanco@chromium.org return 1; 499d18b7873ce9b44f130a41e0cbd0a3df76ab9adfsenorblanco@chromium.org } else { 509d18b7873ce9b44f130a41e0cbd0a3df76ab9adfsenorblanco@chromium.org // Each time we subdivide, d should be cut in 4. So we need to 519d18b7873ce9b44f130a41e0cbd0a3df76ab9adfsenorblanco@chromium.org // subdivide x = log4(d/tol) times. x subdivisions creates 2^(x) 529d18b7873ce9b44f130a41e0cbd0a3df76ab9adfsenorblanco@chromium.org // points. 539d18b7873ce9b44f130a41e0cbd0a3df76ab9adfsenorblanco@chromium.org // 2^(log4(x)) = sqrt(x); 54e1ca705cac4b946993f6cbf798e2a0ba27e739f3reed@google.com int temp = SkScalarCeilToInt(SkScalarSqrt(SkScalarDiv(d, tol))); 5561f3bde1ba114e7b39b53411f4aa31ed0875d159bsalomon@google.com int pow2 = GrNextPow2(temp); 5661f3bde1ba114e7b39b53411f4aa31ed0875d159bsalomon@google.com // Because of NaNs & INFs we can wind up with a degenerate temp 5761f3bde1ba114e7b39b53411f4aa31ed0875d159bsalomon@google.com // such that pow2 comes out negative. Also, our point generator 5861f3bde1ba114e7b39b53411f4aa31ed0875d159bsalomon@google.com // will always output at least one pt. 5961f3bde1ba114e7b39b53411f4aa31ed0875d159bsalomon@google.com if (pow2 < 1) { 6061f3bde1ba114e7b39b53411f4aa31ed0875d159bsalomon@google.com pow2 = 1; 6161f3bde1ba114e7b39b53411f4aa31ed0875d159bsalomon@google.com } 62972f9cd7a063d0544f8c919fd12b9a3adbd12b24commit-bot@chromium.org return SkTMin(pow2, MAX_POINTS_PER_CURVE); 639d18b7873ce9b44f130a41e0cbd0a3df76ab9adfsenorblanco@chromium.org } 649d18b7873ce9b44f130a41e0cbd0a3df76ab9adfsenorblanco@chromium.org} 659d18b7873ce9b44f130a41e0cbd0a3df76ab9adfsenorblanco@chromium.org 66972f9cd7a063d0544f8c919fd12b9a3adbd12b24commit-bot@chromium.orguint32_t GrPathUtils::generateQuadraticPoints(const SkPoint& p0, 67972f9cd7a063d0544f8c919fd12b9a3adbd12b24commit-bot@chromium.org const SkPoint& p1, 68972f9cd7a063d0544f8c919fd12b9a3adbd12b24commit-bot@chromium.org const SkPoint& p2, 6981712883419f76e25d2ffec38a9438284a45a48dbsalomon@google.com SkScalar tolSqd, 70972f9cd7a063d0544f8c919fd12b9a3adbd12b24commit-bot@chromium.org SkPoint** points, 71c10a88825d119054a9f4e7b7af7a3f887e30ab6btomhudson@google.com uint32_t pointsLeft) { 729d18b7873ce9b44f130a41e0cbd0a3df76ab9adfsenorblanco@chromium.org if (pointsLeft < 2 || 739d18b7873ce9b44f130a41e0cbd0a3df76ab9adfsenorblanco@chromium.org (p1.distanceToLineSegmentBetweenSqd(p0, p2)) < tolSqd) { 749d18b7873ce9b44f130a41e0cbd0a3df76ab9adfsenorblanco@chromium.org (*points)[0] = p2; 759d18b7873ce9b44f130a41e0cbd0a3df76ab9adfsenorblanco@chromium.org *points += 1; 769d18b7873ce9b44f130a41e0cbd0a3df76ab9adfsenorblanco@chromium.org return 1; 779d18b7873ce9b44f130a41e0cbd0a3df76ab9adfsenorblanco@chromium.org } 789d18b7873ce9b44f130a41e0cbd0a3df76ab9adfsenorblanco@chromium.org 79972f9cd7a063d0544f8c919fd12b9a3adbd12b24commit-bot@chromium.org SkPoint q[] = { 8081712883419f76e25d2ffec38a9438284a45a48dbsalomon@google.com { SkScalarAve(p0.fX, p1.fX), SkScalarAve(p0.fY, p1.fY) }, 8181712883419f76e25d2ffec38a9438284a45a48dbsalomon@google.com { SkScalarAve(p1.fX, p2.fX), SkScalarAve(p1.fY, p2.fY) }, 829d18b7873ce9b44f130a41e0cbd0a3df76ab9adfsenorblanco@chromium.org }; 83972f9cd7a063d0544f8c919fd12b9a3adbd12b24commit-bot@chromium.org SkPoint r = { SkScalarAve(q[0].fX, q[1].fX), SkScalarAve(q[0].fY, q[1].fY) }; 849d18b7873ce9b44f130a41e0cbd0a3df76ab9adfsenorblanco@chromium.org 859d18b7873ce9b44f130a41e0cbd0a3df76ab9adfsenorblanco@chromium.org pointsLeft >>= 1; 869d18b7873ce9b44f130a41e0cbd0a3df76ab9adfsenorblanco@chromium.org uint32_t a = generateQuadraticPoints(p0, q[0], r, tolSqd, points, pointsLeft); 879d18b7873ce9b44f130a41e0cbd0a3df76ab9adfsenorblanco@chromium.org uint32_t b = generateQuadraticPoints(r, q[1], p2, tolSqd, points, pointsLeft); 889d18b7873ce9b44f130a41e0cbd0a3df76ab9adfsenorblanco@chromium.org return a + b; 899d18b7873ce9b44f130a41e0cbd0a3df76ab9adfsenorblanco@chromium.org} 909d18b7873ce9b44f130a41e0cbd0a3df76ab9adfsenorblanco@chromium.org 91972f9cd7a063d0544f8c919fd12b9a3adbd12b24commit-bot@chromium.orguint32_t GrPathUtils::cubicPointCount(const SkPoint points[], 9281712883419f76e25d2ffec38a9438284a45a48dbsalomon@google.com SkScalar tol) { 93c10a88825d119054a9f4e7b7af7a3f887e30ab6btomhudson@google.com if (tol < gMinCurveTol) { 94afec7ba75962517b17293799d3fc70d39fa7dbf2tomhudson@google.com tol = gMinCurveTol; 95c10a88825d119054a9f4e7b7af7a3f887e30ab6btomhudson@google.com } 96f6de475e5cbd143f348ff7738919e397b7fe7f57tfarina@chromium.org SkASSERT(tol > 0); 97c10a88825d119054a9f4e7b7af7a3f887e30ab6btomhudson@google.com 98972f9cd7a063d0544f8c919fd12b9a3adbd12b24commit-bot@chromium.org SkScalar d = SkTMax( 99c10a88825d119054a9f4e7b7af7a3f887e30ab6btomhudson@google.com points[1].distanceToLineSegmentBetweenSqd(points[0], points[3]), 100c10a88825d119054a9f4e7b7af7a3f887e30ab6btomhudson@google.com points[2].distanceToLineSegmentBetweenSqd(points[0], points[3])); 1012047f00e4698f83499ab91911999a65c21a951c9epoger@google.com d = SkScalarSqrt(d); 102c10a88825d119054a9f4e7b7af7a3f887e30ab6btomhudson@google.com if (d <= tol) { 1039d18b7873ce9b44f130a41e0cbd0a3df76ab9adfsenorblanco@chromium.org return 1; 1049d18b7873ce9b44f130a41e0cbd0a3df76ab9adfsenorblanco@chromium.org } else { 105e1ca705cac4b946993f6cbf798e2a0ba27e739f3reed@google.com int temp = SkScalarCeilToInt(SkScalarSqrt(SkScalarDiv(d, tol))); 10661f3bde1ba114e7b39b53411f4aa31ed0875d159bsalomon@google.com int pow2 = GrNextPow2(temp); 10761f3bde1ba114e7b39b53411f4aa31ed0875d159bsalomon@google.com // Because of NaNs & INFs we can wind up with a degenerate temp 10861f3bde1ba114e7b39b53411f4aa31ed0875d159bsalomon@google.com // such that pow2 comes out negative. Also, our point generator 10961f3bde1ba114e7b39b53411f4aa31ed0875d159bsalomon@google.com // will always output at least one pt. 11061f3bde1ba114e7b39b53411f4aa31ed0875d159bsalomon@google.com if (pow2 < 1) { 11161f3bde1ba114e7b39b53411f4aa31ed0875d159bsalomon@google.com pow2 = 1; 11261f3bde1ba114e7b39b53411f4aa31ed0875d159bsalomon@google.com } 113972f9cd7a063d0544f8c919fd12b9a3adbd12b24commit-bot@chromium.org return SkTMin(pow2, MAX_POINTS_PER_CURVE); 1149d18b7873ce9b44f130a41e0cbd0a3df76ab9adfsenorblanco@chromium.org } 1159d18b7873ce9b44f130a41e0cbd0a3df76ab9adfsenorblanco@chromium.org} 1169d18b7873ce9b44f130a41e0cbd0a3df76ab9adfsenorblanco@chromium.org 117972f9cd7a063d0544f8c919fd12b9a3adbd12b24commit-bot@chromium.orguint32_t GrPathUtils::generateCubicPoints(const SkPoint& p0, 118972f9cd7a063d0544f8c919fd12b9a3adbd12b24commit-bot@chromium.org const SkPoint& p1, 119972f9cd7a063d0544f8c919fd12b9a3adbd12b24commit-bot@chromium.org const SkPoint& p2, 120972f9cd7a063d0544f8c919fd12b9a3adbd12b24commit-bot@chromium.org const SkPoint& p3, 12181712883419f76e25d2ffec38a9438284a45a48dbsalomon@google.com SkScalar tolSqd, 122972f9cd7a063d0544f8c919fd12b9a3adbd12b24commit-bot@chromium.org SkPoint** points, 123c10a88825d119054a9f4e7b7af7a3f887e30ab6btomhudson@google.com uint32_t pointsLeft) { 1249d18b7873ce9b44f130a41e0cbd0a3df76ab9adfsenorblanco@chromium.org if (pointsLeft < 2 || 1259d18b7873ce9b44f130a41e0cbd0a3df76ab9adfsenorblanco@chromium.org (p1.distanceToLineSegmentBetweenSqd(p0, p3) < tolSqd && 1269d18b7873ce9b44f130a41e0cbd0a3df76ab9adfsenorblanco@chromium.org p2.distanceToLineSegmentBetweenSqd(p0, p3) < tolSqd)) { 1279d18b7873ce9b44f130a41e0cbd0a3df76ab9adfsenorblanco@chromium.org (*points)[0] = p3; 1289d18b7873ce9b44f130a41e0cbd0a3df76ab9adfsenorblanco@chromium.org *points += 1; 1299d18b7873ce9b44f130a41e0cbd0a3df76ab9adfsenorblanco@chromium.org return 1; 1309d18b7873ce9b44f130a41e0cbd0a3df76ab9adfsenorblanco@chromium.org } 131972f9cd7a063d0544f8c919fd12b9a3adbd12b24commit-bot@chromium.org SkPoint q[] = { 13281712883419f76e25d2ffec38a9438284a45a48dbsalomon@google.com { SkScalarAve(p0.fX, p1.fX), SkScalarAve(p0.fY, p1.fY) }, 13381712883419f76e25d2ffec38a9438284a45a48dbsalomon@google.com { SkScalarAve(p1.fX, p2.fX), SkScalarAve(p1.fY, p2.fY) }, 13481712883419f76e25d2ffec38a9438284a45a48dbsalomon@google.com { SkScalarAve(p2.fX, p3.fX), SkScalarAve(p2.fY, p3.fY) } 1359d18b7873ce9b44f130a41e0cbd0a3df76ab9adfsenorblanco@chromium.org }; 136972f9cd7a063d0544f8c919fd12b9a3adbd12b24commit-bot@chromium.org SkPoint r[] = { 13781712883419f76e25d2ffec38a9438284a45a48dbsalomon@google.com { SkScalarAve(q[0].fX, q[1].fX), SkScalarAve(q[0].fY, q[1].fY) }, 13881712883419f76e25d2ffec38a9438284a45a48dbsalomon@google.com { SkScalarAve(q[1].fX, q[2].fX), SkScalarAve(q[1].fY, q[2].fY) } 1399d18b7873ce9b44f130a41e0cbd0a3df76ab9adfsenorblanco@chromium.org }; 140972f9cd7a063d0544f8c919fd12b9a3adbd12b24commit-bot@chromium.org SkPoint s = { SkScalarAve(r[0].fX, r[1].fX), SkScalarAve(r[0].fY, r[1].fY) }; 1419d18b7873ce9b44f130a41e0cbd0a3df76ab9adfsenorblanco@chromium.org pointsLeft >>= 1; 1429d18b7873ce9b44f130a41e0cbd0a3df76ab9adfsenorblanco@chromium.org uint32_t a = generateCubicPoints(p0, q[0], r[0], s, tolSqd, points, pointsLeft); 1439d18b7873ce9b44f130a41e0cbd0a3df76ab9adfsenorblanco@chromium.org uint32_t b = generateCubicPoints(s, r[1], q[2], p3, tolSqd, points, pointsLeft); 1449d18b7873ce9b44f130a41e0cbd0a3df76ab9adfsenorblanco@chromium.org return a + b; 1459d18b7873ce9b44f130a41e0cbd0a3df76ab9adfsenorblanco@chromium.org} 1469d18b7873ce9b44f130a41e0cbd0a3df76ab9adfsenorblanco@chromium.org 1478d033a1b125886c62906d975b5cc28a382064526bsalomon@google.comint GrPathUtils::worstCasePointCount(const SkPath& path, int* subpaths, 14881712883419f76e25d2ffec38a9438284a45a48dbsalomon@google.com SkScalar tol) { 149c10a88825d119054a9f4e7b7af7a3f887e30ab6btomhudson@google.com if (tol < gMinCurveTol) { 150afec7ba75962517b17293799d3fc70d39fa7dbf2tomhudson@google.com tol = gMinCurveTol; 151c10a88825d119054a9f4e7b7af7a3f887e30ab6btomhudson@google.com } 152f6de475e5cbd143f348ff7738919e397b7fe7f57tfarina@chromium.org SkASSERT(tol > 0); 153c10a88825d119054a9f4e7b7af7a3f887e30ab6btomhudson@google.com 1549d18b7873ce9b44f130a41e0cbd0a3df76ab9adfsenorblanco@chromium.org int pointCount = 0; 1559d18b7873ce9b44f130a41e0cbd0a3df76ab9adfsenorblanco@chromium.org *subpaths = 1; 1569d18b7873ce9b44f130a41e0cbd0a3df76ab9adfsenorblanco@chromium.org 1579d18b7873ce9b44f130a41e0cbd0a3df76ab9adfsenorblanco@chromium.org bool first = true; 1589d18b7873ce9b44f130a41e0cbd0a3df76ab9adfsenorblanco@chromium.org 159129b8e3237b80b9d258a8f48e8f54c0073cafbdcsenorblanco@chromium.org SkPath::Iter iter(path, false); 16094b284d719ee5ccd3e2efbd1d7084ec554583bacbsalomon@google.com SkPath::Verb verb; 1619d18b7873ce9b44f130a41e0cbd0a3df76ab9adfsenorblanco@chromium.org 162972f9cd7a063d0544f8c919fd12b9a3adbd12b24commit-bot@chromium.org SkPoint pts[4]; 16394b284d719ee5ccd3e2efbd1d7084ec554583bacbsalomon@google.com while ((verb = iter.next(pts)) != SkPath::kDone_Verb) { 1649d18b7873ce9b44f130a41e0cbd0a3df76ab9adfsenorblanco@chromium.org 16594b284d719ee5ccd3e2efbd1d7084ec554583bacbsalomon@google.com switch (verb) { 16694b284d719ee5ccd3e2efbd1d7084ec554583bacbsalomon@google.com case SkPath::kLine_Verb: 1679d18b7873ce9b44f130a41e0cbd0a3df76ab9adfsenorblanco@chromium.org pointCount += 1; 1689d18b7873ce9b44f130a41e0cbd0a3df76ab9adfsenorblanco@chromium.org break; 16994b284d719ee5ccd3e2efbd1d7084ec554583bacbsalomon@google.com case SkPath::kQuad_Verb: 1709d18b7873ce9b44f130a41e0cbd0a3df76ab9adfsenorblanco@chromium.org pointCount += quadraticPointCount(pts, tol); 1719d18b7873ce9b44f130a41e0cbd0a3df76ab9adfsenorblanco@chromium.org break; 17294b284d719ee5ccd3e2efbd1d7084ec554583bacbsalomon@google.com case SkPath::kCubic_Verb: 1739d18b7873ce9b44f130a41e0cbd0a3df76ab9adfsenorblanco@chromium.org pointCount += cubicPointCount(pts, tol); 1749d18b7873ce9b44f130a41e0cbd0a3df76ab9adfsenorblanco@chromium.org break; 17594b284d719ee5ccd3e2efbd1d7084ec554583bacbsalomon@google.com case SkPath::kMove_Verb: 1769d18b7873ce9b44f130a41e0cbd0a3df76ab9adfsenorblanco@chromium.org pointCount += 1; 1779d18b7873ce9b44f130a41e0cbd0a3df76ab9adfsenorblanco@chromium.org if (!first) { 1789d18b7873ce9b44f130a41e0cbd0a3df76ab9adfsenorblanco@chromium.org ++(*subpaths); 1799d18b7873ce9b44f130a41e0cbd0a3df76ab9adfsenorblanco@chromium.org } 1809d18b7873ce9b44f130a41e0cbd0a3df76ab9adfsenorblanco@chromium.org break; 1819d18b7873ce9b44f130a41e0cbd0a3df76ab9adfsenorblanco@chromium.org default: 1829d18b7873ce9b44f130a41e0cbd0a3df76ab9adfsenorblanco@chromium.org break; 1839d18b7873ce9b44f130a41e0cbd0a3df76ab9adfsenorblanco@chromium.org } 1849d18b7873ce9b44f130a41e0cbd0a3df76ab9adfsenorblanco@chromium.org first = false; 1859d18b7873ce9b44f130a41e0cbd0a3df76ab9adfsenorblanco@chromium.org } 1869d18b7873ce9b44f130a41e0cbd0a3df76ab9adfsenorblanco@chromium.org return pointCount; 1879d18b7873ce9b44f130a41e0cbd0a3df76ab9adfsenorblanco@chromium.org} 18869cc6ad20ed03f35f9d3c8119a2c32187669a22bbsalomon@google.com 189972f9cd7a063d0544f8c919fd12b9a3adbd12b24commit-bot@chromium.orgvoid GrPathUtils::QuadUVMatrix::set(const SkPoint qPts[3]) { 1901971317bb43580330a9e7e9a1c09c5025fe84aacbsalomon@google.com SkMatrix m; 191dc3c78076ea279d4f6d502b3b42471e9b2bba48ebsalomon@google.com // We want M such that M * xy_pt = uv_pt 192dc3c78076ea279d4f6d502b3b42471e9b2bba48ebsalomon@google.com // We know M * control_pts = [0 1/2 1] 193dc3c78076ea279d4f6d502b3b42471e9b2bba48ebsalomon@google.com // [0 0 1] 194dc3c78076ea279d4f6d502b3b42471e9b2bba48ebsalomon@google.com // [1 1 1] 195f543fd9e8c162b65fd04d1d9439b60911f8eb4c0commit-bot@chromium.org // And control_pts = [x0 x1 x2] 196f543fd9e8c162b65fd04d1d9439b60911f8eb4c0commit-bot@chromium.org // [y0 y1 y2] 197f543fd9e8c162b65fd04d1d9439b60911f8eb4c0commit-bot@chromium.org // [1 1 1 ] 198dc3c78076ea279d4f6d502b3b42471e9b2bba48ebsalomon@google.com // We invert the control pt matrix and post concat to both sides to get M. 199f543fd9e8c162b65fd04d1d9439b60911f8eb4c0commit-bot@chromium.org // Using the known form of the control point matrix and the result, we can 200f543fd9e8c162b65fd04d1d9439b60911f8eb4c0commit-bot@chromium.org // optimize and improve precision. 201f543fd9e8c162b65fd04d1d9439b60911f8eb4c0commit-bot@chromium.org 202f543fd9e8c162b65fd04d1d9439b60911f8eb4c0commit-bot@chromium.org double x0 = qPts[0].fX; 203f543fd9e8c162b65fd04d1d9439b60911f8eb4c0commit-bot@chromium.org double y0 = qPts[0].fY; 204f543fd9e8c162b65fd04d1d9439b60911f8eb4c0commit-bot@chromium.org double x1 = qPts[1].fX; 205f543fd9e8c162b65fd04d1d9439b60911f8eb4c0commit-bot@chromium.org double y1 = qPts[1].fY; 206f543fd9e8c162b65fd04d1d9439b60911f8eb4c0commit-bot@chromium.org double x2 = qPts[2].fX; 207f543fd9e8c162b65fd04d1d9439b60911f8eb4c0commit-bot@chromium.org double y2 = qPts[2].fY; 208f543fd9e8c162b65fd04d1d9439b60911f8eb4c0commit-bot@chromium.org double det = x0*y1 - y0*x1 + x2*y0 - y2*x0 + x1*y2 - y1*x2; 209f543fd9e8c162b65fd04d1d9439b60911f8eb4c0commit-bot@chromium.org 2108491d24bdc3f48f67475c12c60babb9f9dba8047skia.committer@gmail.com if (!sk_float_isfinite(det) 211f543fd9e8c162b65fd04d1d9439b60911f8eb4c0commit-bot@chromium.org || SkScalarNearlyZero((float)det, SK_ScalarNearlyZero * SK_ScalarNearlyZero)) { 212dc3c78076ea279d4f6d502b3b42471e9b2bba48ebsalomon@google.com // The quad is degenerate. Hopefully this is rare. Find the pts that are 213dc3c78076ea279d4f6d502b3b42471e9b2bba48ebsalomon@google.com // farthest apart to compute a line (unless it is really a pt). 214dc3c78076ea279d4f6d502b3b42471e9b2bba48ebsalomon@google.com SkScalar maxD = qPts[0].distanceToSqd(qPts[1]); 215dc3c78076ea279d4f6d502b3b42471e9b2bba48ebsalomon@google.com int maxEdge = 0; 216dc3c78076ea279d4f6d502b3b42471e9b2bba48ebsalomon@google.com SkScalar d = qPts[1].distanceToSqd(qPts[2]); 217dc3c78076ea279d4f6d502b3b42471e9b2bba48ebsalomon@google.com if (d > maxD) { 218dc3c78076ea279d4f6d502b3b42471e9b2bba48ebsalomon@google.com maxD = d; 219dc3c78076ea279d4f6d502b3b42471e9b2bba48ebsalomon@google.com maxEdge = 1; 220dc3c78076ea279d4f6d502b3b42471e9b2bba48ebsalomon@google.com } 221dc3c78076ea279d4f6d502b3b42471e9b2bba48ebsalomon@google.com d = qPts[2].distanceToSqd(qPts[0]); 222dc3c78076ea279d4f6d502b3b42471e9b2bba48ebsalomon@google.com if (d > maxD) { 223dc3c78076ea279d4f6d502b3b42471e9b2bba48ebsalomon@google.com maxD = d; 224dc3c78076ea279d4f6d502b3b42471e9b2bba48ebsalomon@google.com maxEdge = 2; 225dc3c78076ea279d4f6d502b3b42471e9b2bba48ebsalomon@google.com } 226dc3c78076ea279d4f6d502b3b42471e9b2bba48ebsalomon@google.com // We could have a tolerance here, not sure if it would improve anything 227dc3c78076ea279d4f6d502b3b42471e9b2bba48ebsalomon@google.com if (maxD > 0) { 228dc3c78076ea279d4f6d502b3b42471e9b2bba48ebsalomon@google.com // Set the matrix to give (u = 0, v = distance_to_line) 229972f9cd7a063d0544f8c919fd12b9a3adbd12b24commit-bot@chromium.org SkVector lineVec = qPts[(maxEdge + 1)%3] - qPts[maxEdge]; 23020e542e00eccaf7b9e81964692a47086e6aaf568bsalomon@google.com // when looking from the point 0 down the line we want positive 23120e542e00eccaf7b9e81964692a47086e6aaf568bsalomon@google.com // distances to be to the left. This matches the non-degenerate 23220e542e00eccaf7b9e81964692a47086e6aaf568bsalomon@google.com // case. 233972f9cd7a063d0544f8c919fd12b9a3adbd12b24commit-bot@chromium.org lineVec.setOrthog(lineVec, SkPoint::kLeft_Side); 234dc3c78076ea279d4f6d502b3b42471e9b2bba48ebsalomon@google.com lineVec.dot(qPts[0]); 2351971317bb43580330a9e7e9a1c09c5025fe84aacbsalomon@google.com // first row 2361971317bb43580330a9e7e9a1c09c5025fe84aacbsalomon@google.com fM[0] = 0; 2371971317bb43580330a9e7e9a1c09c5025fe84aacbsalomon@google.com fM[1] = 0; 2381971317bb43580330a9e7e9a1c09c5025fe84aacbsalomon@google.com fM[2] = 0; 2391971317bb43580330a9e7e9a1c09c5025fe84aacbsalomon@google.com // second row 2401971317bb43580330a9e7e9a1c09c5025fe84aacbsalomon@google.com fM[3] = lineVec.fX; 2411971317bb43580330a9e7e9a1c09c5025fe84aacbsalomon@google.com fM[4] = lineVec.fY; 2421971317bb43580330a9e7e9a1c09c5025fe84aacbsalomon@google.com fM[5] = -lineVec.dot(qPts[maxEdge]); 243dc3c78076ea279d4f6d502b3b42471e9b2bba48ebsalomon@google.com } else { 244dc3c78076ea279d4f6d502b3b42471e9b2bba48ebsalomon@google.com // It's a point. It should cover zero area. Just set the matrix such 245dc3c78076ea279d4f6d502b3b42471e9b2bba48ebsalomon@google.com // that (u, v) will always be far away from the quad. 2461971317bb43580330a9e7e9a1c09c5025fe84aacbsalomon@google.com fM[0] = 0; fM[1] = 0; fM[2] = 100.f; 2471971317bb43580330a9e7e9a1c09c5025fe84aacbsalomon@google.com fM[3] = 0; fM[4] = 0; fM[5] = 100.f; 248dc3c78076ea279d4f6d502b3b42471e9b2bba48ebsalomon@google.com } 249dc3c78076ea279d4f6d502b3b42471e9b2bba48ebsalomon@google.com } else { 250f543fd9e8c162b65fd04d1d9439b60911f8eb4c0commit-bot@chromium.org double scale = 1.0/det; 251f543fd9e8c162b65fd04d1d9439b60911f8eb4c0commit-bot@chromium.org 252f543fd9e8c162b65fd04d1d9439b60911f8eb4c0commit-bot@chromium.org // compute adjugate matrix 253f543fd9e8c162b65fd04d1d9439b60911f8eb4c0commit-bot@chromium.org double a0, a1, a2, a3, a4, a5, a6, a7, a8; 254f543fd9e8c162b65fd04d1d9439b60911f8eb4c0commit-bot@chromium.org a0 = y1-y2; 255f543fd9e8c162b65fd04d1d9439b60911f8eb4c0commit-bot@chromium.org a1 = x2-x1; 256f543fd9e8c162b65fd04d1d9439b60911f8eb4c0commit-bot@chromium.org a2 = x1*y2-x2*y1; 257f543fd9e8c162b65fd04d1d9439b60911f8eb4c0commit-bot@chromium.org 258f543fd9e8c162b65fd04d1d9439b60911f8eb4c0commit-bot@chromium.org a3 = y2-y0; 259f543fd9e8c162b65fd04d1d9439b60911f8eb4c0commit-bot@chromium.org a4 = x0-x2; 260f543fd9e8c162b65fd04d1d9439b60911f8eb4c0commit-bot@chromium.org a5 = x2*y0-x0*y2; 261f543fd9e8c162b65fd04d1d9439b60911f8eb4c0commit-bot@chromium.org 262f543fd9e8c162b65fd04d1d9439b60911f8eb4c0commit-bot@chromium.org a6 = y0-y1; 263f543fd9e8c162b65fd04d1d9439b60911f8eb4c0commit-bot@chromium.org a7 = x1-x0; 264f543fd9e8c162b65fd04d1d9439b60911f8eb4c0commit-bot@chromium.org a8 = x0*y1-x1*y0; 265f543fd9e8c162b65fd04d1d9439b60911f8eb4c0commit-bot@chromium.org 2668491d24bdc3f48f67475c12c60babb9f9dba8047skia.committer@gmail.com // this performs the uv_pts*adjugate(control_pts) multiply, 267f543fd9e8c162b65fd04d1d9439b60911f8eb4c0commit-bot@chromium.org // then does the scale by 1/det afterwards to improve precision 268f543fd9e8c162b65fd04d1d9439b60911f8eb4c0commit-bot@chromium.org m[SkMatrix::kMScaleX] = (float)((0.5*a3 + a6)*scale); 269f543fd9e8c162b65fd04d1d9439b60911f8eb4c0commit-bot@chromium.org m[SkMatrix::kMSkewX] = (float)((0.5*a4 + a7)*scale); 270f543fd9e8c162b65fd04d1d9439b60911f8eb4c0commit-bot@chromium.org m[SkMatrix::kMTransX] = (float)((0.5*a5 + a8)*scale); 271f543fd9e8c162b65fd04d1d9439b60911f8eb4c0commit-bot@chromium.org 272f543fd9e8c162b65fd04d1d9439b60911f8eb4c0commit-bot@chromium.org m[SkMatrix::kMSkewY] = (float)(a6*scale); 273f543fd9e8c162b65fd04d1d9439b60911f8eb4c0commit-bot@chromium.org m[SkMatrix::kMScaleY] = (float)(a7*scale); 274f543fd9e8c162b65fd04d1d9439b60911f8eb4c0commit-bot@chromium.org m[SkMatrix::kMTransY] = (float)(a8*scale); 275f543fd9e8c162b65fd04d1d9439b60911f8eb4c0commit-bot@chromium.org 276f543fd9e8c162b65fd04d1d9439b60911f8eb4c0commit-bot@chromium.org m[SkMatrix::kMPersp0] = (float)((a0 + a3 + a6)*scale); 277f543fd9e8c162b65fd04d1d9439b60911f8eb4c0commit-bot@chromium.org m[SkMatrix::kMPersp1] = (float)((a1 + a4 + a7)*scale); 278f543fd9e8c162b65fd04d1d9439b60911f8eb4c0commit-bot@chromium.org m[SkMatrix::kMPersp2] = (float)((a2 + a5 + a8)*scale); 2791971317bb43580330a9e7e9a1c09c5025fe84aacbsalomon@google.com 2801971317bb43580330a9e7e9a1c09c5025fe84aacbsalomon@google.com // The matrix should not have perspective. 2814b413c8bb123e42ca4b9c7bfa6bc2167283cb84ccommit-bot@chromium.org SkDEBUGCODE(static const SkScalar gTOL = 1.f / 100.f); 282f6de475e5cbd143f348ff7738919e397b7fe7f57tfarina@chromium.org SkASSERT(SkScalarAbs(m.get(SkMatrix::kMPersp0)) < gTOL); 283f6de475e5cbd143f348ff7738919e397b7fe7f57tfarina@chromium.org SkASSERT(SkScalarAbs(m.get(SkMatrix::kMPersp1)) < gTOL); 2841971317bb43580330a9e7e9a1c09c5025fe84aacbsalomon@google.com 2851971317bb43580330a9e7e9a1c09c5025fe84aacbsalomon@google.com // It may not be normalized to have 1.0 in the bottom right 2861971317bb43580330a9e7e9a1c09c5025fe84aacbsalomon@google.com float m33 = m.get(SkMatrix::kMPersp2); 2871971317bb43580330a9e7e9a1c09c5025fe84aacbsalomon@google.com if (1.f != m33) { 2881971317bb43580330a9e7e9a1c09c5025fe84aacbsalomon@google.com m33 = 1.f / m33; 2891971317bb43580330a9e7e9a1c09c5025fe84aacbsalomon@google.com fM[0] = m33 * m.get(SkMatrix::kMScaleX); 2901971317bb43580330a9e7e9a1c09c5025fe84aacbsalomon@google.com fM[1] = m33 * m.get(SkMatrix::kMSkewX); 2911971317bb43580330a9e7e9a1c09c5025fe84aacbsalomon@google.com fM[2] = m33 * m.get(SkMatrix::kMTransX); 2921971317bb43580330a9e7e9a1c09c5025fe84aacbsalomon@google.com fM[3] = m33 * m.get(SkMatrix::kMSkewY); 2931971317bb43580330a9e7e9a1c09c5025fe84aacbsalomon@google.com fM[4] = m33 * m.get(SkMatrix::kMScaleY); 2941971317bb43580330a9e7e9a1c09c5025fe84aacbsalomon@google.com fM[5] = m33 * m.get(SkMatrix::kMTransY); 2951971317bb43580330a9e7e9a1c09c5025fe84aacbsalomon@google.com } else { 2961971317bb43580330a9e7e9a1c09c5025fe84aacbsalomon@google.com fM[0] = m.get(SkMatrix::kMScaleX); 2971971317bb43580330a9e7e9a1c09c5025fe84aacbsalomon@google.com fM[1] = m.get(SkMatrix::kMSkewX); 2981971317bb43580330a9e7e9a1c09c5025fe84aacbsalomon@google.com fM[2] = m.get(SkMatrix::kMTransX); 2991971317bb43580330a9e7e9a1c09c5025fe84aacbsalomon@google.com fM[3] = m.get(SkMatrix::kMSkewY); 3001971317bb43580330a9e7e9a1c09c5025fe84aacbsalomon@google.com fM[4] = m.get(SkMatrix::kMScaleY); 3011971317bb43580330a9e7e9a1c09c5025fe84aacbsalomon@google.com fM[5] = m.get(SkMatrix::kMTransY); 3021971317bb43580330a9e7e9a1c09c5025fe84aacbsalomon@google.com } 303dc3c78076ea279d4f6d502b3b42471e9b2bba48ebsalomon@google.com } 30469cc6ad20ed03f35f9d3c8119a2c32187669a22bbsalomon@google.com} 30569cc6ad20ed03f35f9d3c8119a2c32187669a22bbsalomon@google.com 306139484095f014ab08265c32337fddeeec6c0877dcommit-bot@chromium.org//////////////////////////////////////////////////////////////////////////////// 307139484095f014ab08265c32337fddeeec6c0877dcommit-bot@chromium.org 308139484095f014ab08265c32337fddeeec6c0877dcommit-bot@chromium.org// k = (y2 - y0, x0 - x2, (x2 - x0)*y0 - (y2 - y0)*x0 ) 309139484095f014ab08265c32337fddeeec6c0877dcommit-bot@chromium.org// l = (2*w * (y1 - y0), 2*w * (x0 - x1), 2*w * (x1*y0 - x0*y1)) 310139484095f014ab08265c32337fddeeec6c0877dcommit-bot@chromium.org// m = (2*w * (y2 - y1), 2*w * (x1 - x2), 2*w * (x2*y1 - x1*y2)) 311139484095f014ab08265c32337fddeeec6c0877dcommit-bot@chromium.orgvoid GrPathUtils::getConicKLM(const SkPoint p[3], const SkScalar weight, SkScalar klm[9]) { 312139484095f014ab08265c32337fddeeec6c0877dcommit-bot@chromium.org const SkScalar w2 = 2.f * weight; 313139484095f014ab08265c32337fddeeec6c0877dcommit-bot@chromium.org klm[0] = p[2].fY - p[0].fY; 314139484095f014ab08265c32337fddeeec6c0877dcommit-bot@chromium.org klm[1] = p[0].fX - p[2].fX; 315139484095f014ab08265c32337fddeeec6c0877dcommit-bot@chromium.org klm[2] = (p[2].fX - p[0].fX) * p[0].fY - (p[2].fY - p[0].fY) * p[0].fX; 316139484095f014ab08265c32337fddeeec6c0877dcommit-bot@chromium.org 317139484095f014ab08265c32337fddeeec6c0877dcommit-bot@chromium.org klm[3] = w2 * (p[1].fY - p[0].fY); 318139484095f014ab08265c32337fddeeec6c0877dcommit-bot@chromium.org klm[4] = w2 * (p[0].fX - p[1].fX); 319139484095f014ab08265c32337fddeeec6c0877dcommit-bot@chromium.org klm[5] = w2 * (p[1].fX * p[0].fY - p[0].fX * p[1].fY); 320139484095f014ab08265c32337fddeeec6c0877dcommit-bot@chromium.org 321139484095f014ab08265c32337fddeeec6c0877dcommit-bot@chromium.org klm[6] = w2 * (p[2].fY - p[1].fY); 322139484095f014ab08265c32337fddeeec6c0877dcommit-bot@chromium.org klm[7] = w2 * (p[1].fX - p[2].fX); 323139484095f014ab08265c32337fddeeec6c0877dcommit-bot@chromium.org klm[8] = w2 * (p[2].fX * p[1].fY - p[1].fX * p[2].fY); 324139484095f014ab08265c32337fddeeec6c0877dcommit-bot@chromium.org 325139484095f014ab08265c32337fddeeec6c0877dcommit-bot@chromium.org // scale the max absolute value of coeffs to 10 326139484095f014ab08265c32337fddeeec6c0877dcommit-bot@chromium.org SkScalar scale = 0.f; 327139484095f014ab08265c32337fddeeec6c0877dcommit-bot@chromium.org for (int i = 0; i < 9; ++i) { 328139484095f014ab08265c32337fddeeec6c0877dcommit-bot@chromium.org scale = SkMaxScalar(scale, SkScalarAbs(klm[i])); 329139484095f014ab08265c32337fddeeec6c0877dcommit-bot@chromium.org } 330139484095f014ab08265c32337fddeeec6c0877dcommit-bot@chromium.org SkASSERT(scale > 0.f); 331139484095f014ab08265c32337fddeeec6c0877dcommit-bot@chromium.org scale = 10.f / scale; 332139484095f014ab08265c32337fddeeec6c0877dcommit-bot@chromium.org for (int i = 0; i < 9; ++i) { 333139484095f014ab08265c32337fddeeec6c0877dcommit-bot@chromium.org klm[i] *= scale; 334139484095f014ab08265c32337fddeeec6c0877dcommit-bot@chromium.org } 335139484095f014ab08265c32337fddeeec6c0877dcommit-bot@chromium.org} 336139484095f014ab08265c32337fddeeec6c0877dcommit-bot@chromium.org 337139484095f014ab08265c32337fddeeec6c0877dcommit-bot@chromium.org//////////////////////////////////////////////////////////////////////////////// 338139484095f014ab08265c32337fddeeec6c0877dcommit-bot@chromium.org 33969cc6ad20ed03f35f9d3c8119a2c32187669a22bbsalomon@google.comnamespace { 340a51ab8416db9772a2eae3122f4f69801642daeb5bsalomon@google.com 341a51ab8416db9772a2eae3122f4f69801642daeb5bsalomon@google.com// a is the first control point of the cubic. 342a51ab8416db9772a2eae3122f4f69801642daeb5bsalomon@google.com// ab is the vector from a to the second control point. 343a51ab8416db9772a2eae3122f4f69801642daeb5bsalomon@google.com// dc is the vector from the fourth to the third control point. 344a51ab8416db9772a2eae3122f4f69801642daeb5bsalomon@google.com// d is the fourth control point. 345a51ab8416db9772a2eae3122f4f69801642daeb5bsalomon@google.com// p is the candidate quadratic control point. 346a51ab8416db9772a2eae3122f4f69801642daeb5bsalomon@google.com// this assumes that the cubic doesn't inflect and is simple 347a51ab8416db9772a2eae3122f4f69801642daeb5bsalomon@google.combool is_point_within_cubic_tangents(const SkPoint& a, 348a51ab8416db9772a2eae3122f4f69801642daeb5bsalomon@google.com const SkVector& ab, 349a51ab8416db9772a2eae3122f4f69801642daeb5bsalomon@google.com const SkVector& dc, 350a51ab8416db9772a2eae3122f4f69801642daeb5bsalomon@google.com const SkPoint& d, 351a51ab8416db9772a2eae3122f4f69801642daeb5bsalomon@google.com SkPath::Direction dir, 352a51ab8416db9772a2eae3122f4f69801642daeb5bsalomon@google.com const SkPoint p) { 353a51ab8416db9772a2eae3122f4f69801642daeb5bsalomon@google.com SkVector ap = p - a; 354a51ab8416db9772a2eae3122f4f69801642daeb5bsalomon@google.com SkScalar apXab = ap.cross(ab); 355a51ab8416db9772a2eae3122f4f69801642daeb5bsalomon@google.com if (SkPath::kCW_Direction == dir) { 356a51ab8416db9772a2eae3122f4f69801642daeb5bsalomon@google.com if (apXab > 0) { 357a51ab8416db9772a2eae3122f4f69801642daeb5bsalomon@google.com return false; 358a51ab8416db9772a2eae3122f4f69801642daeb5bsalomon@google.com } 359a51ab8416db9772a2eae3122f4f69801642daeb5bsalomon@google.com } else { 360f6de475e5cbd143f348ff7738919e397b7fe7f57tfarina@chromium.org SkASSERT(SkPath::kCCW_Direction == dir); 361a51ab8416db9772a2eae3122f4f69801642daeb5bsalomon@google.com if (apXab < 0) { 362a51ab8416db9772a2eae3122f4f69801642daeb5bsalomon@google.com return false; 363a51ab8416db9772a2eae3122f4f69801642daeb5bsalomon@google.com } 364a51ab8416db9772a2eae3122f4f69801642daeb5bsalomon@google.com } 365a51ab8416db9772a2eae3122f4f69801642daeb5bsalomon@google.com 366a51ab8416db9772a2eae3122f4f69801642daeb5bsalomon@google.com SkVector dp = p - d; 367a51ab8416db9772a2eae3122f4f69801642daeb5bsalomon@google.com SkScalar dpXdc = dp.cross(dc); 368a51ab8416db9772a2eae3122f4f69801642daeb5bsalomon@google.com if (SkPath::kCW_Direction == dir) { 369a51ab8416db9772a2eae3122f4f69801642daeb5bsalomon@google.com if (dpXdc < 0) { 370a51ab8416db9772a2eae3122f4f69801642daeb5bsalomon@google.com return false; 371a51ab8416db9772a2eae3122f4f69801642daeb5bsalomon@google.com } 372a51ab8416db9772a2eae3122f4f69801642daeb5bsalomon@google.com } else { 373f6de475e5cbd143f348ff7738919e397b7fe7f57tfarina@chromium.org SkASSERT(SkPath::kCCW_Direction == dir); 374a51ab8416db9772a2eae3122f4f69801642daeb5bsalomon@google.com if (dpXdc > 0) { 375a51ab8416db9772a2eae3122f4f69801642daeb5bsalomon@google.com return false; 376a51ab8416db9772a2eae3122f4f69801642daeb5bsalomon@google.com } 377a51ab8416db9772a2eae3122f4f69801642daeb5bsalomon@google.com } 378a51ab8416db9772a2eae3122f4f69801642daeb5bsalomon@google.com return true; 379a51ab8416db9772a2eae3122f4f69801642daeb5bsalomon@google.com} 380a51ab8416db9772a2eae3122f4f69801642daeb5bsalomon@google.com 38169cc6ad20ed03f35f9d3c8119a2c32187669a22bbsalomon@google.comvoid convert_noninflect_cubic_to_quads(const SkPoint p[4], 382a51ab8416db9772a2eae3122f4f69801642daeb5bsalomon@google.com SkScalar toleranceSqd, 383a51ab8416db9772a2eae3122f4f69801642daeb5bsalomon@google.com bool constrainWithinTangents, 384a51ab8416db9772a2eae3122f4f69801642daeb5bsalomon@google.com SkPath::Direction dir, 38569cc6ad20ed03f35f9d3c8119a2c32187669a22bbsalomon@google.com SkTArray<SkPoint, true>* quads, 38669cc6ad20ed03f35f9d3c8119a2c32187669a22bbsalomon@google.com int sublevel = 0) { 38754ad851361c55466f1e4950585afc2aa6cf173c5bsalomon@google.com 38854ad851361c55466f1e4950585afc2aa6cf173c5bsalomon@google.com // Notation: Point a is always p[0]. Point b is p[1] unless p[1] == p[0], in which case it is 38954ad851361c55466f1e4950585afc2aa6cf173c5bsalomon@google.com // 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]. 39054ad851361c55466f1e4950585afc2aa6cf173c5bsalomon@google.com 391a51ab8416db9772a2eae3122f4f69801642daeb5bsalomon@google.com SkVector ab = p[1] - p[0]; 392a51ab8416db9772a2eae3122f4f69801642daeb5bsalomon@google.com SkVector dc = p[2] - p[3]; 393a51ab8416db9772a2eae3122f4f69801642daeb5bsalomon@google.com 394a51ab8416db9772a2eae3122f4f69801642daeb5bsalomon@google.com if (ab.isZero()) { 395a51ab8416db9772a2eae3122f4f69801642daeb5bsalomon@google.com if (dc.isZero()) { 396a51ab8416db9772a2eae3122f4f69801642daeb5bsalomon@google.com SkPoint* degQuad = quads->push_back_n(3); 397a51ab8416db9772a2eae3122f4f69801642daeb5bsalomon@google.com degQuad[0] = p[0]; 398a51ab8416db9772a2eae3122f4f69801642daeb5bsalomon@google.com degQuad[1] = p[0]; 399a51ab8416db9772a2eae3122f4f69801642daeb5bsalomon@google.com degQuad[2] = p[3]; 400a51ab8416db9772a2eae3122f4f69801642daeb5bsalomon@google.com return; 401a51ab8416db9772a2eae3122f4f69801642daeb5bsalomon@google.com } 402a51ab8416db9772a2eae3122f4f69801642daeb5bsalomon@google.com ab = p[2] - p[0]; 403a51ab8416db9772a2eae3122f4f69801642daeb5bsalomon@google.com } 404a51ab8416db9772a2eae3122f4f69801642daeb5bsalomon@google.com if (dc.isZero()) { 405a51ab8416db9772a2eae3122f4f69801642daeb5bsalomon@google.com dc = p[1] - p[3]; 406a51ab8416db9772a2eae3122f4f69801642daeb5bsalomon@google.com } 407a51ab8416db9772a2eae3122f4f69801642daeb5bsalomon@google.com 4083935a7bfe64293edf9b06527f59d657ff4e280cbbsalomon // When the ab and cd tangents are degenerate or nearly parallel with vector from d to a the 4093935a7bfe64293edf9b06527f59d657ff4e280cbbsalomon // constraint that the quad point falls between the tangents becomes hard to enforce and we are 4103935a7bfe64293edf9b06527f59d657ff4e280cbbsalomon // likely to hit the max subdivision count. However, in this case the cubic is approaching a 4113935a7bfe64293edf9b06527f59d657ff4e280cbbsalomon // line and the accuracy of the quad point isn't so important. We check if the two middle cubic 4123935a7bfe64293edf9b06527f59d657ff4e280cbbsalomon // control points are very close to the baseline vector. If so then we just pick quadratic 4133935a7bfe64293edf9b06527f59d657ff4e280cbbsalomon // points on the control polygon. 41454ad851361c55466f1e4950585afc2aa6cf173c5bsalomon@google.com 41554ad851361c55466f1e4950585afc2aa6cf173c5bsalomon@google.com if (constrainWithinTangents) { 41654ad851361c55466f1e4950585afc2aa6cf173c5bsalomon@google.com SkVector da = p[0] - p[3]; 4173935a7bfe64293edf9b06527f59d657ff4e280cbbsalomon bool doQuads = dc.lengthSqd() < SK_ScalarNearlyZero || 4183935a7bfe64293edf9b06527f59d657ff4e280cbbsalomon ab.lengthSqd() < SK_ScalarNearlyZero; 4193935a7bfe64293edf9b06527f59d657ff4e280cbbsalomon if (!doQuads) { 4203935a7bfe64293edf9b06527f59d657ff4e280cbbsalomon SkScalar invDALengthSqd = da.lengthSqd(); 4213935a7bfe64293edf9b06527f59d657ff4e280cbbsalomon if (invDALengthSqd > SK_ScalarNearlyZero) { 4223935a7bfe64293edf9b06527f59d657ff4e280cbbsalomon invDALengthSqd = SkScalarInvert(invDALengthSqd); 4233935a7bfe64293edf9b06527f59d657ff4e280cbbsalomon // cross(ab, da)^2/length(da)^2 == sqd distance from b to line from d to a. 4243935a7bfe64293edf9b06527f59d657ff4e280cbbsalomon // same goes for point c using vector cd. 4253935a7bfe64293edf9b06527f59d657ff4e280cbbsalomon SkScalar detABSqd = ab.cross(da); 4263935a7bfe64293edf9b06527f59d657ff4e280cbbsalomon detABSqd = SkScalarSquare(detABSqd); 4273935a7bfe64293edf9b06527f59d657ff4e280cbbsalomon SkScalar detDCSqd = dc.cross(da); 4283935a7bfe64293edf9b06527f59d657ff4e280cbbsalomon detDCSqd = SkScalarSquare(detDCSqd); 4293935a7bfe64293edf9b06527f59d657ff4e280cbbsalomon if (SkScalarMul(detABSqd, invDALengthSqd) < toleranceSqd && 4303935a7bfe64293edf9b06527f59d657ff4e280cbbsalomon SkScalarMul(detDCSqd, invDALengthSqd) < toleranceSqd) { 4313935a7bfe64293edf9b06527f59d657ff4e280cbbsalomon doQuads = true; 43254ad851361c55466f1e4950585afc2aa6cf173c5bsalomon@google.com } 43354ad851361c55466f1e4950585afc2aa6cf173c5bsalomon@google.com } 43454ad851361c55466f1e4950585afc2aa6cf173c5bsalomon@google.com } 4353935a7bfe64293edf9b06527f59d657ff4e280cbbsalomon if (doQuads) { 4363935a7bfe64293edf9b06527f59d657ff4e280cbbsalomon SkPoint b = p[0] + ab; 4373935a7bfe64293edf9b06527f59d657ff4e280cbbsalomon SkPoint c = p[3] + dc; 4383935a7bfe64293edf9b06527f59d657ff4e280cbbsalomon SkPoint mid = b + c; 4393935a7bfe64293edf9b06527f59d657ff4e280cbbsalomon mid.scale(SK_ScalarHalf); 4403935a7bfe64293edf9b06527f59d657ff4e280cbbsalomon // Insert two quadratics to cover the case when ab points away from d and/or dc 4413935a7bfe64293edf9b06527f59d657ff4e280cbbsalomon // points away from a. 4423935a7bfe64293edf9b06527f59d657ff4e280cbbsalomon if (SkVector::DotProduct(da, dc) < 0 || SkVector::DotProduct(ab,da) > 0) { 4433935a7bfe64293edf9b06527f59d657ff4e280cbbsalomon SkPoint* qpts = quads->push_back_n(6); 4443935a7bfe64293edf9b06527f59d657ff4e280cbbsalomon qpts[0] = p[0]; 4453935a7bfe64293edf9b06527f59d657ff4e280cbbsalomon qpts[1] = b; 4463935a7bfe64293edf9b06527f59d657ff4e280cbbsalomon qpts[2] = mid; 4473935a7bfe64293edf9b06527f59d657ff4e280cbbsalomon qpts[3] = mid; 4483935a7bfe64293edf9b06527f59d657ff4e280cbbsalomon qpts[4] = c; 4493935a7bfe64293edf9b06527f59d657ff4e280cbbsalomon qpts[5] = p[3]; 4503935a7bfe64293edf9b06527f59d657ff4e280cbbsalomon } else { 4513935a7bfe64293edf9b06527f59d657ff4e280cbbsalomon SkPoint* qpts = quads->push_back_n(3); 4523935a7bfe64293edf9b06527f59d657ff4e280cbbsalomon qpts[0] = p[0]; 4533935a7bfe64293edf9b06527f59d657ff4e280cbbsalomon qpts[1] = mid; 4543935a7bfe64293edf9b06527f59d657ff4e280cbbsalomon qpts[2] = p[3]; 4553935a7bfe64293edf9b06527f59d657ff4e280cbbsalomon } 4563935a7bfe64293edf9b06527f59d657ff4e280cbbsalomon return; 4573935a7bfe64293edf9b06527f59d657ff4e280cbbsalomon } 45854ad851361c55466f1e4950585afc2aa6cf173c5bsalomon@google.com } 45954ad851361c55466f1e4950585afc2aa6cf173c5bsalomon@google.com 460a51ab8416db9772a2eae3122f4f69801642daeb5bsalomon@google.com static const SkScalar kLengthScale = 3 * SK_Scalar1 / 2; 46169cc6ad20ed03f35f9d3c8119a2c32187669a22bbsalomon@google.com static const int kMaxSubdivs = 10; 46269cc6ad20ed03f35f9d3c8119a2c32187669a22bbsalomon@google.com 463a51ab8416db9772a2eae3122f4f69801642daeb5bsalomon@google.com ab.scale(kLengthScale); 464a51ab8416db9772a2eae3122f4f69801642daeb5bsalomon@google.com dc.scale(kLengthScale); 46569cc6ad20ed03f35f9d3c8119a2c32187669a22bbsalomon@google.com 466a51ab8416db9772a2eae3122f4f69801642daeb5bsalomon@google.com // e0 and e1 are extrapolations along vectors ab and dc. 46769cc6ad20ed03f35f9d3c8119a2c32187669a22bbsalomon@google.com SkVector c0 = p[0]; 46869cc6ad20ed03f35f9d3c8119a2c32187669a22bbsalomon@google.com c0 += ab; 46969cc6ad20ed03f35f9d3c8119a2c32187669a22bbsalomon@google.com SkVector c1 = p[3]; 47069cc6ad20ed03f35f9d3c8119a2c32187669a22bbsalomon@google.com c1 += dc; 47169cc6ad20ed03f35f9d3c8119a2c32187669a22bbsalomon@google.com 47254ad851361c55466f1e4950585afc2aa6cf173c5bsalomon@google.com SkScalar dSqd = sublevel > kMaxSubdivs ? 0 : c0.distanceToSqd(c1); 473a51ab8416db9772a2eae3122f4f69801642daeb5bsalomon@google.com if (dSqd < toleranceSqd) { 47469cc6ad20ed03f35f9d3c8119a2c32187669a22bbsalomon@google.com SkPoint cAvg = c0; 47569cc6ad20ed03f35f9d3c8119a2c32187669a22bbsalomon@google.com cAvg += c1; 47669cc6ad20ed03f35f9d3c8119a2c32187669a22bbsalomon@google.com cAvg.scale(SK_ScalarHalf); 47769cc6ad20ed03f35f9d3c8119a2c32187669a22bbsalomon@google.com 478a51ab8416db9772a2eae3122f4f69801642daeb5bsalomon@google.com bool subdivide = false; 479a51ab8416db9772a2eae3122f4f69801642daeb5bsalomon@google.com 480a51ab8416db9772a2eae3122f4f69801642daeb5bsalomon@google.com if (constrainWithinTangents && 481a51ab8416db9772a2eae3122f4f69801642daeb5bsalomon@google.com !is_point_within_cubic_tangents(p[0], ab, dc, p[3], dir, cAvg)) { 48254ad851361c55466f1e4950585afc2aa6cf173c5bsalomon@google.com // choose a new cAvg that is the intersection of the two tangent lines. 483a51ab8416db9772a2eae3122f4f69801642daeb5bsalomon@google.com ab.setOrthog(ab); 484a51ab8416db9772a2eae3122f4f69801642daeb5bsalomon@google.com SkScalar z0 = -ab.dot(p[0]); 485a51ab8416db9772a2eae3122f4f69801642daeb5bsalomon@google.com dc.setOrthog(dc); 486a51ab8416db9772a2eae3122f4f69801642daeb5bsalomon@google.com SkScalar z1 = -dc.dot(p[3]); 487a51ab8416db9772a2eae3122f4f69801642daeb5bsalomon@google.com cAvg.fX = SkScalarMul(ab.fY, z1) - SkScalarMul(z0, dc.fY); 488a51ab8416db9772a2eae3122f4f69801642daeb5bsalomon@google.com cAvg.fY = SkScalarMul(z0, dc.fX) - SkScalarMul(ab.fX, z1); 489a51ab8416db9772a2eae3122f4f69801642daeb5bsalomon@google.com SkScalar z = SkScalarMul(ab.fX, dc.fY) - SkScalarMul(ab.fY, dc.fX); 490a51ab8416db9772a2eae3122f4f69801642daeb5bsalomon@google.com z = SkScalarInvert(z); 491a51ab8416db9772a2eae3122f4f69801642daeb5bsalomon@google.com cAvg.fX *= z; 492a51ab8416db9772a2eae3122f4f69801642daeb5bsalomon@google.com cAvg.fY *= z; 493a51ab8416db9772a2eae3122f4f69801642daeb5bsalomon@google.com if (sublevel <= kMaxSubdivs) { 494a51ab8416db9772a2eae3122f4f69801642daeb5bsalomon@google.com SkScalar d0Sqd = c0.distanceToSqd(cAvg); 495a51ab8416db9772a2eae3122f4f69801642daeb5bsalomon@google.com SkScalar d1Sqd = c1.distanceToSqd(cAvg); 49654ad851361c55466f1e4950585afc2aa6cf173c5bsalomon@google.com // We need to subdivide if d0 + d1 > tolerance but we have the sqd values. We know 49754ad851361c55466f1e4950585afc2aa6cf173c5bsalomon@google.com // the distances and tolerance can't be negative. 498a51ab8416db9772a2eae3122f4f69801642daeb5bsalomon@google.com // (d0 + d1)^2 > toleranceSqd 499a51ab8416db9772a2eae3122f4f69801642daeb5bsalomon@google.com // d0Sqd + 2*d0*d1 + d1Sqd > toleranceSqd 500a51ab8416db9772a2eae3122f4f69801642daeb5bsalomon@google.com SkScalar d0d1 = SkScalarSqrt(SkScalarMul(d0Sqd, d1Sqd)); 501a51ab8416db9772a2eae3122f4f69801642daeb5bsalomon@google.com subdivide = 2 * d0d1 + d0Sqd + d1Sqd > toleranceSqd; 502a51ab8416db9772a2eae3122f4f69801642daeb5bsalomon@google.com } 503a51ab8416db9772a2eae3122f4f69801642daeb5bsalomon@google.com } 504a51ab8416db9772a2eae3122f4f69801642daeb5bsalomon@google.com if (!subdivide) { 505a51ab8416db9772a2eae3122f4f69801642daeb5bsalomon@google.com SkPoint* pts = quads->push_back_n(3); 506a51ab8416db9772a2eae3122f4f69801642daeb5bsalomon@google.com pts[0] = p[0]; 507a51ab8416db9772a2eae3122f4f69801642daeb5bsalomon@google.com pts[1] = cAvg; 508a51ab8416db9772a2eae3122f4f69801642daeb5bsalomon@google.com pts[2] = p[3]; 509a51ab8416db9772a2eae3122f4f69801642daeb5bsalomon@google.com return; 510a51ab8416db9772a2eae3122f4f69801642daeb5bsalomon@google.com } 51169cc6ad20ed03f35f9d3c8119a2c32187669a22bbsalomon@google.com } 512a51ab8416db9772a2eae3122f4f69801642daeb5bsalomon@google.com SkPoint choppedPts[7]; 513a51ab8416db9772a2eae3122f4f69801642daeb5bsalomon@google.com SkChopCubicAtHalf(p, choppedPts); 514a51ab8416db9772a2eae3122f4f69801642daeb5bsalomon@google.com convert_noninflect_cubic_to_quads(choppedPts + 0, 515a51ab8416db9772a2eae3122f4f69801642daeb5bsalomon@google.com toleranceSqd, 516a51ab8416db9772a2eae3122f4f69801642daeb5bsalomon@google.com constrainWithinTangents, 517a51ab8416db9772a2eae3122f4f69801642daeb5bsalomon@google.com dir, 518a51ab8416db9772a2eae3122f4f69801642daeb5bsalomon@google.com quads, 519a51ab8416db9772a2eae3122f4f69801642daeb5bsalomon@google.com sublevel + 1); 520a51ab8416db9772a2eae3122f4f69801642daeb5bsalomon@google.com convert_noninflect_cubic_to_quads(choppedPts + 3, 521a51ab8416db9772a2eae3122f4f69801642daeb5bsalomon@google.com toleranceSqd, 522a51ab8416db9772a2eae3122f4f69801642daeb5bsalomon@google.com constrainWithinTangents, 523a51ab8416db9772a2eae3122f4f69801642daeb5bsalomon@google.com dir, 524a51ab8416db9772a2eae3122f4f69801642daeb5bsalomon@google.com quads, 525a51ab8416db9772a2eae3122f4f69801642daeb5bsalomon@google.com sublevel + 1); 52669cc6ad20ed03f35f9d3c8119a2c32187669a22bbsalomon@google.com} 52769cc6ad20ed03f35f9d3c8119a2c32187669a22bbsalomon@google.com} 52869cc6ad20ed03f35f9d3c8119a2c32187669a22bbsalomon@google.com 529972f9cd7a063d0544f8c919fd12b9a3adbd12b24commit-bot@chromium.orgvoid GrPathUtils::convertCubicToQuads(const SkPoint p[4], 53069cc6ad20ed03f35f9d3c8119a2c32187669a22bbsalomon@google.com SkScalar tolScale, 531a51ab8416db9772a2eae3122f4f69801642daeb5bsalomon@google.com bool constrainWithinTangents, 532a51ab8416db9772a2eae3122f4f69801642daeb5bsalomon@google.com SkPath::Direction dir, 53369cc6ad20ed03f35f9d3c8119a2c32187669a22bbsalomon@google.com SkTArray<SkPoint, true>* quads) { 53469cc6ad20ed03f35f9d3c8119a2c32187669a22bbsalomon@google.com SkPoint chopped[10]; 53569cc6ad20ed03f35f9d3c8119a2c32187669a22bbsalomon@google.com int count = SkChopCubicAtInflections(p, chopped); 53669cc6ad20ed03f35f9d3c8119a2c32187669a22bbsalomon@google.com 537a51ab8416db9772a2eae3122f4f69801642daeb5bsalomon@google.com // base tolerance is 1 pixel. 538a51ab8416db9772a2eae3122f4f69801642daeb5bsalomon@google.com static const SkScalar kTolerance = SK_Scalar1; 539a51ab8416db9772a2eae3122f4f69801642daeb5bsalomon@google.com const SkScalar tolSqd = SkScalarSquare(SkScalarMul(tolScale, kTolerance)); 540a51ab8416db9772a2eae3122f4f69801642daeb5bsalomon@google.com 54169cc6ad20ed03f35f9d3c8119a2c32187669a22bbsalomon@google.com for (int i = 0; i < count; ++i) { 54269cc6ad20ed03f35f9d3c8119a2c32187669a22bbsalomon@google.com SkPoint* cubic = chopped + 3*i; 543a51ab8416db9772a2eae3122f4f69801642daeb5bsalomon@google.com convert_noninflect_cubic_to_quads(cubic, tolSqd, constrainWithinTangents, dir, quads); 54469cc6ad20ed03f35f9d3c8119a2c32187669a22bbsalomon@google.com } 54569cc6ad20ed03f35f9d3c8119a2c32187669a22bbsalomon@google.com 54669cc6ad20ed03f35f9d3c8119a2c32187669a22bbsalomon@google.com} 547858638d8a5bef8f9940ccec2346a9bcc5f804979commit-bot@chromium.org 548858638d8a5bef8f9940ccec2346a9bcc5f804979commit-bot@chromium.org//////////////////////////////////////////////////////////////////////////////// 549858638d8a5bef8f9940ccec2346a9bcc5f804979commit-bot@chromium.org 550858638d8a5bef8f9940ccec2346a9bcc5f804979commit-bot@chromium.orgenum CubicType { 551858638d8a5bef8f9940ccec2346a9bcc5f804979commit-bot@chromium.org kSerpentine_CubicType, 552858638d8a5bef8f9940ccec2346a9bcc5f804979commit-bot@chromium.org kCusp_CubicType, 553858638d8a5bef8f9940ccec2346a9bcc5f804979commit-bot@chromium.org kLoop_CubicType, 554858638d8a5bef8f9940ccec2346a9bcc5f804979commit-bot@chromium.org kQuadratic_CubicType, 555858638d8a5bef8f9940ccec2346a9bcc5f804979commit-bot@chromium.org kLine_CubicType, 556858638d8a5bef8f9940ccec2346a9bcc5f804979commit-bot@chromium.org kPoint_CubicType 557858638d8a5bef8f9940ccec2346a9bcc5f804979commit-bot@chromium.org}; 558858638d8a5bef8f9940ccec2346a9bcc5f804979commit-bot@chromium.org 559858638d8a5bef8f9940ccec2346a9bcc5f804979commit-bot@chromium.org// discr(I) = d0^2 * (3*d1^2 - 4*d0*d2) 560858638d8a5bef8f9940ccec2346a9bcc5f804979commit-bot@chromium.org// Classification: 561858638d8a5bef8f9940ccec2346a9bcc5f804979commit-bot@chromium.org// discr(I) > 0 Serpentine 562858638d8a5bef8f9940ccec2346a9bcc5f804979commit-bot@chromium.org// discr(I) = 0 Cusp 563858638d8a5bef8f9940ccec2346a9bcc5f804979commit-bot@chromium.org// discr(I) < 0 Loop 564858638d8a5bef8f9940ccec2346a9bcc5f804979commit-bot@chromium.org// d0 = d1 = 0 Quadratic 565858638d8a5bef8f9940ccec2346a9bcc5f804979commit-bot@chromium.org// d0 = d1 = d2 = 0 Line 566858638d8a5bef8f9940ccec2346a9bcc5f804979commit-bot@chromium.org// p0 = p1 = p2 = p3 Point 567858638d8a5bef8f9940ccec2346a9bcc5f804979commit-bot@chromium.orgstatic CubicType classify_cubic(const SkPoint p[4], const SkScalar d[3]) { 568858638d8a5bef8f9940ccec2346a9bcc5f804979commit-bot@chromium.org if (p[0] == p[1] && p[0] == p[2] && p[0] == p[3]) { 569858638d8a5bef8f9940ccec2346a9bcc5f804979commit-bot@chromium.org return kPoint_CubicType; 570858638d8a5bef8f9940ccec2346a9bcc5f804979commit-bot@chromium.org } 571858638d8a5bef8f9940ccec2346a9bcc5f804979commit-bot@chromium.org const SkScalar discr = d[0] * d[0] * (3.f * d[1] * d[1] - 4.f * d[0] * d[2]); 572858638d8a5bef8f9940ccec2346a9bcc5f804979commit-bot@chromium.org if (discr > SK_ScalarNearlyZero) { 573858638d8a5bef8f9940ccec2346a9bcc5f804979commit-bot@chromium.org return kSerpentine_CubicType; 574858638d8a5bef8f9940ccec2346a9bcc5f804979commit-bot@chromium.org } else if (discr < -SK_ScalarNearlyZero) { 575858638d8a5bef8f9940ccec2346a9bcc5f804979commit-bot@chromium.org return kLoop_CubicType; 576858638d8a5bef8f9940ccec2346a9bcc5f804979commit-bot@chromium.org } else { 577858638d8a5bef8f9940ccec2346a9bcc5f804979commit-bot@chromium.org if (0.f == d[0] && 0.f == d[1]) { 578858638d8a5bef8f9940ccec2346a9bcc5f804979commit-bot@chromium.org return (0.f == d[2] ? kLine_CubicType : kQuadratic_CubicType); 579858638d8a5bef8f9940ccec2346a9bcc5f804979commit-bot@chromium.org } else { 580858638d8a5bef8f9940ccec2346a9bcc5f804979commit-bot@chromium.org return kCusp_CubicType; 581858638d8a5bef8f9940ccec2346a9bcc5f804979commit-bot@chromium.org } 582858638d8a5bef8f9940ccec2346a9bcc5f804979commit-bot@chromium.org } 583858638d8a5bef8f9940ccec2346a9bcc5f804979commit-bot@chromium.org} 584858638d8a5bef8f9940ccec2346a9bcc5f804979commit-bot@chromium.org 585858638d8a5bef8f9940ccec2346a9bcc5f804979commit-bot@chromium.org// Assumes the third component of points is 1. 586858638d8a5bef8f9940ccec2346a9bcc5f804979commit-bot@chromium.org// Calcs p0 . (p1 x p2) 587858638d8a5bef8f9940ccec2346a9bcc5f804979commit-bot@chromium.orgstatic SkScalar calc_dot_cross_cubic(const SkPoint& p0, const SkPoint& p1, const SkPoint& p2) { 588858638d8a5bef8f9940ccec2346a9bcc5f804979commit-bot@chromium.org const SkScalar xComp = p0.fX * (p1.fY - p2.fY); 589858638d8a5bef8f9940ccec2346a9bcc5f804979commit-bot@chromium.org const SkScalar yComp = p0.fY * (p2.fX - p1.fX); 590858638d8a5bef8f9940ccec2346a9bcc5f804979commit-bot@chromium.org const SkScalar wComp = p1.fX * p2.fY - p1.fY * p2.fX; 591858638d8a5bef8f9940ccec2346a9bcc5f804979commit-bot@chromium.org return (xComp + yComp + wComp); 592858638d8a5bef8f9940ccec2346a9bcc5f804979commit-bot@chromium.org} 593858638d8a5bef8f9940ccec2346a9bcc5f804979commit-bot@chromium.org 594858638d8a5bef8f9940ccec2346a9bcc5f804979commit-bot@chromium.org// Solves linear system to extract klm 595858638d8a5bef8f9940ccec2346a9bcc5f804979commit-bot@chromium.org// P.K = k (similarly for l, m) 596858638d8a5bef8f9940ccec2346a9bcc5f804979commit-bot@chromium.org// Where P is matrix of control points 597858638d8a5bef8f9940ccec2346a9bcc5f804979commit-bot@chromium.org// K is coefficients for the line K 598858638d8a5bef8f9940ccec2346a9bcc5f804979commit-bot@chromium.org// k is vector of values of K evaluated at the control points 599858638d8a5bef8f9940ccec2346a9bcc5f804979commit-bot@chromium.org// Solving for K, thus K = P^(-1) . k 600858638d8a5bef8f9940ccec2346a9bcc5f804979commit-bot@chromium.orgstatic void calc_cubic_klm(const SkPoint p[4], const SkScalar controlK[4], 601858638d8a5bef8f9940ccec2346a9bcc5f804979commit-bot@chromium.org const SkScalar controlL[4], const SkScalar controlM[4], 602858638d8a5bef8f9940ccec2346a9bcc5f804979commit-bot@chromium.org SkScalar k[3], SkScalar l[3], SkScalar m[3]) { 603858638d8a5bef8f9940ccec2346a9bcc5f804979commit-bot@chromium.org SkMatrix matrix; 604858638d8a5bef8f9940ccec2346a9bcc5f804979commit-bot@chromium.org matrix.setAll(p[0].fX, p[0].fY, 1.f, 605858638d8a5bef8f9940ccec2346a9bcc5f804979commit-bot@chromium.org p[1].fX, p[1].fY, 1.f, 606858638d8a5bef8f9940ccec2346a9bcc5f804979commit-bot@chromium.org p[2].fX, p[2].fY, 1.f); 607858638d8a5bef8f9940ccec2346a9bcc5f804979commit-bot@chromium.org SkMatrix inverse; 608858638d8a5bef8f9940ccec2346a9bcc5f804979commit-bot@chromium.org if (matrix.invert(&inverse)) { 609858638d8a5bef8f9940ccec2346a9bcc5f804979commit-bot@chromium.org inverse.mapHomogeneousPoints(k, controlK, 1); 610858638d8a5bef8f9940ccec2346a9bcc5f804979commit-bot@chromium.org inverse.mapHomogeneousPoints(l, controlL, 1); 611858638d8a5bef8f9940ccec2346a9bcc5f804979commit-bot@chromium.org inverse.mapHomogeneousPoints(m, controlM, 1); 612858638d8a5bef8f9940ccec2346a9bcc5f804979commit-bot@chromium.org } 613858638d8a5bef8f9940ccec2346a9bcc5f804979commit-bot@chromium.org 614858638d8a5bef8f9940ccec2346a9bcc5f804979commit-bot@chromium.org} 615858638d8a5bef8f9940ccec2346a9bcc5f804979commit-bot@chromium.org 616858638d8a5bef8f9940ccec2346a9bcc5f804979commit-bot@chromium.orgstatic void set_serp_klm(const SkScalar d[3], SkScalar k[4], SkScalar l[4], SkScalar m[4]) { 617858638d8a5bef8f9940ccec2346a9bcc5f804979commit-bot@chromium.org SkScalar tempSqrt = SkScalarSqrt(9.f * d[1] * d[1] - 12.f * d[0] * d[2]); 618858638d8a5bef8f9940ccec2346a9bcc5f804979commit-bot@chromium.org SkScalar ls = 3.f * d[1] - tempSqrt; 619858638d8a5bef8f9940ccec2346a9bcc5f804979commit-bot@chromium.org SkScalar lt = 6.f * d[0]; 620858638d8a5bef8f9940ccec2346a9bcc5f804979commit-bot@chromium.org SkScalar ms = 3.f * d[1] + tempSqrt; 621858638d8a5bef8f9940ccec2346a9bcc5f804979commit-bot@chromium.org SkScalar mt = 6.f * d[0]; 622858638d8a5bef8f9940ccec2346a9bcc5f804979commit-bot@chromium.org 623858638d8a5bef8f9940ccec2346a9bcc5f804979commit-bot@chromium.org k[0] = ls * ms; 624858638d8a5bef8f9940ccec2346a9bcc5f804979commit-bot@chromium.org k[1] = (3.f * ls * ms - ls * mt - lt * ms) / 3.f; 625858638d8a5bef8f9940ccec2346a9bcc5f804979commit-bot@chromium.org k[2] = (lt * (mt - 2.f * ms) + ls * (3.f * ms - 2.f * mt)) / 3.f; 626858638d8a5bef8f9940ccec2346a9bcc5f804979commit-bot@chromium.org k[3] = (lt - ls) * (mt - ms); 627858638d8a5bef8f9940ccec2346a9bcc5f804979commit-bot@chromium.org 628858638d8a5bef8f9940ccec2346a9bcc5f804979commit-bot@chromium.org l[0] = ls * ls * ls; 629858638d8a5bef8f9940ccec2346a9bcc5f804979commit-bot@chromium.org const SkScalar lt_ls = lt - ls; 630858638d8a5bef8f9940ccec2346a9bcc5f804979commit-bot@chromium.org l[1] = ls * ls * lt_ls * -1.f; 631858638d8a5bef8f9940ccec2346a9bcc5f804979commit-bot@chromium.org l[2] = lt_ls * lt_ls * ls; 632858638d8a5bef8f9940ccec2346a9bcc5f804979commit-bot@chromium.org l[3] = -1.f * lt_ls * lt_ls * lt_ls; 633858638d8a5bef8f9940ccec2346a9bcc5f804979commit-bot@chromium.org 634858638d8a5bef8f9940ccec2346a9bcc5f804979commit-bot@chromium.org m[0] = ms * ms * ms; 635858638d8a5bef8f9940ccec2346a9bcc5f804979commit-bot@chromium.org const SkScalar mt_ms = mt - ms; 636858638d8a5bef8f9940ccec2346a9bcc5f804979commit-bot@chromium.org m[1] = ms * ms * mt_ms * -1.f; 637858638d8a5bef8f9940ccec2346a9bcc5f804979commit-bot@chromium.org m[2] = mt_ms * mt_ms * ms; 638858638d8a5bef8f9940ccec2346a9bcc5f804979commit-bot@chromium.org m[3] = -1.f * mt_ms * mt_ms * mt_ms; 639858638d8a5bef8f9940ccec2346a9bcc5f804979commit-bot@chromium.org 640858638d8a5bef8f9940ccec2346a9bcc5f804979commit-bot@chromium.org // If d0 < 0 we need to flip the orientation of our curve 641858638d8a5bef8f9940ccec2346a9bcc5f804979commit-bot@chromium.org // This is done by negating the k and l values 642858638d8a5bef8f9940ccec2346a9bcc5f804979commit-bot@chromium.org // We want negative distance values to be on the inside 643858638d8a5bef8f9940ccec2346a9bcc5f804979commit-bot@chromium.org if ( d[0] > 0) { 644858638d8a5bef8f9940ccec2346a9bcc5f804979commit-bot@chromium.org for (int i = 0; i < 4; ++i) { 645858638d8a5bef8f9940ccec2346a9bcc5f804979commit-bot@chromium.org k[i] = -k[i]; 646858638d8a5bef8f9940ccec2346a9bcc5f804979commit-bot@chromium.org l[i] = -l[i]; 647858638d8a5bef8f9940ccec2346a9bcc5f804979commit-bot@chromium.org } 648858638d8a5bef8f9940ccec2346a9bcc5f804979commit-bot@chromium.org } 649858638d8a5bef8f9940ccec2346a9bcc5f804979commit-bot@chromium.org} 650858638d8a5bef8f9940ccec2346a9bcc5f804979commit-bot@chromium.org 651858638d8a5bef8f9940ccec2346a9bcc5f804979commit-bot@chromium.orgstatic void set_loop_klm(const SkScalar d[3], SkScalar k[4], SkScalar l[4], SkScalar m[4]) { 652858638d8a5bef8f9940ccec2346a9bcc5f804979commit-bot@chromium.org SkScalar tempSqrt = SkScalarSqrt(4.f * d[0] * d[2] - 3.f * d[1] * d[1]); 653858638d8a5bef8f9940ccec2346a9bcc5f804979commit-bot@chromium.org SkScalar ls = d[1] - tempSqrt; 654858638d8a5bef8f9940ccec2346a9bcc5f804979commit-bot@chromium.org SkScalar lt = 2.f * d[0]; 655858638d8a5bef8f9940ccec2346a9bcc5f804979commit-bot@chromium.org SkScalar ms = d[1] + tempSqrt; 656858638d8a5bef8f9940ccec2346a9bcc5f804979commit-bot@chromium.org SkScalar mt = 2.f * d[0]; 657858638d8a5bef8f9940ccec2346a9bcc5f804979commit-bot@chromium.org 658858638d8a5bef8f9940ccec2346a9bcc5f804979commit-bot@chromium.org k[0] = ls * ms; 659858638d8a5bef8f9940ccec2346a9bcc5f804979commit-bot@chromium.org k[1] = (3.f * ls*ms - ls * mt - lt * ms) / 3.f; 660858638d8a5bef8f9940ccec2346a9bcc5f804979commit-bot@chromium.org k[2] = (lt * (mt - 2.f * ms) + ls * (3.f * ms - 2.f * mt)) / 3.f; 661858638d8a5bef8f9940ccec2346a9bcc5f804979commit-bot@chromium.org k[3] = (lt - ls) * (mt - ms); 662858638d8a5bef8f9940ccec2346a9bcc5f804979commit-bot@chromium.org 663858638d8a5bef8f9940ccec2346a9bcc5f804979commit-bot@chromium.org l[0] = ls * ls * ms; 664858638d8a5bef8f9940ccec2346a9bcc5f804979commit-bot@chromium.org l[1] = (ls * (ls * (mt - 3.f * ms) + 2.f * lt * ms))/-3.f; 665858638d8a5bef8f9940ccec2346a9bcc5f804979commit-bot@chromium.org l[2] = ((lt - ls) * (ls * (2.f * mt - 3.f * ms) + lt * ms))/3.f; 666858638d8a5bef8f9940ccec2346a9bcc5f804979commit-bot@chromium.org l[3] = -1.f * (lt - ls) * (lt - ls) * (mt - ms); 667858638d8a5bef8f9940ccec2346a9bcc5f804979commit-bot@chromium.org 668858638d8a5bef8f9940ccec2346a9bcc5f804979commit-bot@chromium.org m[0] = ls * ms * ms; 669858638d8a5bef8f9940ccec2346a9bcc5f804979commit-bot@chromium.org m[1] = (ms * (ls * (2.f * mt - 3.f * ms) + lt * ms))/-3.f; 670858638d8a5bef8f9940ccec2346a9bcc5f804979commit-bot@chromium.org m[2] = ((mt - ms) * (ls * (mt - 3.f * ms) + 2.f * lt * ms))/3.f; 671858638d8a5bef8f9940ccec2346a9bcc5f804979commit-bot@chromium.org m[3] = -1.f * (lt - ls) * (mt - ms) * (mt - ms); 672858638d8a5bef8f9940ccec2346a9bcc5f804979commit-bot@chromium.org 673858638d8a5bef8f9940ccec2346a9bcc5f804979commit-bot@chromium.org 674858638d8a5bef8f9940ccec2346a9bcc5f804979commit-bot@chromium.org // If (d0 < 0 && sign(k1) > 0) || (d0 > 0 && sign(k1) < 0), 675858638d8a5bef8f9940ccec2346a9bcc5f804979commit-bot@chromium.org // we need to flip the orientation of our curve. 676858638d8a5bef8f9940ccec2346a9bcc5f804979commit-bot@chromium.org // This is done by negating the k and l values 67707e1c3fd5030869c480c15ff30d36bd161718262commit-bot@chromium.org if ( (d[0] < 0 && k[1] > 0) || (d[0] > 0 && k[1] < 0)) { 678858638d8a5bef8f9940ccec2346a9bcc5f804979commit-bot@chromium.org for (int i = 0; i < 4; ++i) { 679858638d8a5bef8f9940ccec2346a9bcc5f804979commit-bot@chromium.org k[i] = -k[i]; 680858638d8a5bef8f9940ccec2346a9bcc5f804979commit-bot@chromium.org l[i] = -l[i]; 681858638d8a5bef8f9940ccec2346a9bcc5f804979commit-bot@chromium.org } 682858638d8a5bef8f9940ccec2346a9bcc5f804979commit-bot@chromium.org } 683858638d8a5bef8f9940ccec2346a9bcc5f804979commit-bot@chromium.org} 684858638d8a5bef8f9940ccec2346a9bcc5f804979commit-bot@chromium.org 685858638d8a5bef8f9940ccec2346a9bcc5f804979commit-bot@chromium.orgstatic void set_cusp_klm(const SkScalar d[3], SkScalar k[4], SkScalar l[4], SkScalar m[4]) { 686858638d8a5bef8f9940ccec2346a9bcc5f804979commit-bot@chromium.org const SkScalar ls = d[2]; 687858638d8a5bef8f9940ccec2346a9bcc5f804979commit-bot@chromium.org const SkScalar lt = 3.f * d[1]; 688858638d8a5bef8f9940ccec2346a9bcc5f804979commit-bot@chromium.org 689858638d8a5bef8f9940ccec2346a9bcc5f804979commit-bot@chromium.org k[0] = ls; 690858638d8a5bef8f9940ccec2346a9bcc5f804979commit-bot@chromium.org k[1] = ls - lt / 3.f; 691858638d8a5bef8f9940ccec2346a9bcc5f804979commit-bot@chromium.org k[2] = ls - 2.f * lt / 3.f; 692858638d8a5bef8f9940ccec2346a9bcc5f804979commit-bot@chromium.org k[3] = ls - lt; 693858638d8a5bef8f9940ccec2346a9bcc5f804979commit-bot@chromium.org 694858638d8a5bef8f9940ccec2346a9bcc5f804979commit-bot@chromium.org l[0] = ls * ls * ls; 695858638d8a5bef8f9940ccec2346a9bcc5f804979commit-bot@chromium.org const SkScalar ls_lt = ls - lt; 696858638d8a5bef8f9940ccec2346a9bcc5f804979commit-bot@chromium.org l[1] = ls * ls * ls_lt; 697858638d8a5bef8f9940ccec2346a9bcc5f804979commit-bot@chromium.org l[2] = ls_lt * ls_lt * ls; 698858638d8a5bef8f9940ccec2346a9bcc5f804979commit-bot@chromium.org l[3] = ls_lt * ls_lt * ls_lt; 699858638d8a5bef8f9940ccec2346a9bcc5f804979commit-bot@chromium.org 700858638d8a5bef8f9940ccec2346a9bcc5f804979commit-bot@chromium.org m[0] = 1.f; 701858638d8a5bef8f9940ccec2346a9bcc5f804979commit-bot@chromium.org m[1] = 1.f; 702858638d8a5bef8f9940ccec2346a9bcc5f804979commit-bot@chromium.org m[2] = 1.f; 703858638d8a5bef8f9940ccec2346a9bcc5f804979commit-bot@chromium.org m[3] = 1.f; 704858638d8a5bef8f9940ccec2346a9bcc5f804979commit-bot@chromium.org} 705858638d8a5bef8f9940ccec2346a9bcc5f804979commit-bot@chromium.org 706858638d8a5bef8f9940ccec2346a9bcc5f804979commit-bot@chromium.org// For the case when a cubic is actually a quadratic 707858638d8a5bef8f9940ccec2346a9bcc5f804979commit-bot@chromium.org// M = 708858638d8a5bef8f9940ccec2346a9bcc5f804979commit-bot@chromium.org// 0 0 0 709858638d8a5bef8f9940ccec2346a9bcc5f804979commit-bot@chromium.org// 1/3 0 1/3 710858638d8a5bef8f9940ccec2346a9bcc5f804979commit-bot@chromium.org// 2/3 1/3 2/3 711858638d8a5bef8f9940ccec2346a9bcc5f804979commit-bot@chromium.org// 1 1 1 712858638d8a5bef8f9940ccec2346a9bcc5f804979commit-bot@chromium.orgstatic void set_quadratic_klm(const SkScalar d[3], SkScalar k[4], SkScalar l[4], SkScalar m[4]) { 713858638d8a5bef8f9940ccec2346a9bcc5f804979commit-bot@chromium.org k[0] = 0.f; 714858638d8a5bef8f9940ccec2346a9bcc5f804979commit-bot@chromium.org k[1] = 1.f/3.f; 715858638d8a5bef8f9940ccec2346a9bcc5f804979commit-bot@chromium.org k[2] = 2.f/3.f; 716858638d8a5bef8f9940ccec2346a9bcc5f804979commit-bot@chromium.org k[3] = 1.f; 717858638d8a5bef8f9940ccec2346a9bcc5f804979commit-bot@chromium.org 718858638d8a5bef8f9940ccec2346a9bcc5f804979commit-bot@chromium.org l[0] = 0.f; 719858638d8a5bef8f9940ccec2346a9bcc5f804979commit-bot@chromium.org l[1] = 0.f; 720858638d8a5bef8f9940ccec2346a9bcc5f804979commit-bot@chromium.org l[2] = 1.f/3.f; 721858638d8a5bef8f9940ccec2346a9bcc5f804979commit-bot@chromium.org l[3] = 1.f; 722858638d8a5bef8f9940ccec2346a9bcc5f804979commit-bot@chromium.org 723858638d8a5bef8f9940ccec2346a9bcc5f804979commit-bot@chromium.org m[0] = 0.f; 724858638d8a5bef8f9940ccec2346a9bcc5f804979commit-bot@chromium.org m[1] = 1.f/3.f; 725858638d8a5bef8f9940ccec2346a9bcc5f804979commit-bot@chromium.org m[2] = 2.f/3.f; 726858638d8a5bef8f9940ccec2346a9bcc5f804979commit-bot@chromium.org m[3] = 1.f; 727858638d8a5bef8f9940ccec2346a9bcc5f804979commit-bot@chromium.org 728858638d8a5bef8f9940ccec2346a9bcc5f804979commit-bot@chromium.org // If d2 < 0 we need to flip the orientation of our curve 729858638d8a5bef8f9940ccec2346a9bcc5f804979commit-bot@chromium.org // This is done by negating the k and l values 730858638d8a5bef8f9940ccec2346a9bcc5f804979commit-bot@chromium.org if ( d[2] > 0) { 731858638d8a5bef8f9940ccec2346a9bcc5f804979commit-bot@chromium.org for (int i = 0; i < 4; ++i) { 732858638d8a5bef8f9940ccec2346a9bcc5f804979commit-bot@chromium.org k[i] = -k[i]; 733858638d8a5bef8f9940ccec2346a9bcc5f804979commit-bot@chromium.org l[i] = -l[i]; 734858638d8a5bef8f9940ccec2346a9bcc5f804979commit-bot@chromium.org } 735858638d8a5bef8f9940ccec2346a9bcc5f804979commit-bot@chromium.org } 736858638d8a5bef8f9940ccec2346a9bcc5f804979commit-bot@chromium.org} 737858638d8a5bef8f9940ccec2346a9bcc5f804979commit-bot@chromium.org 738858638d8a5bef8f9940ccec2346a9bcc5f804979commit-bot@chromium.org// Calc coefficients of I(s,t) where roots of I are inflection points of curve 739858638d8a5bef8f9940ccec2346a9bcc5f804979commit-bot@chromium.org// I(s,t) = t*(3*d0*s^2 - 3*d1*s*t + d2*t^2) 740858638d8a5bef8f9940ccec2346a9bcc5f804979commit-bot@chromium.org// d0 = a1 - 2*a2+3*a3 741858638d8a5bef8f9940ccec2346a9bcc5f804979commit-bot@chromium.org// d1 = -a2 + 3*a3 742858638d8a5bef8f9940ccec2346a9bcc5f804979commit-bot@chromium.org// d2 = 3*a3 743858638d8a5bef8f9940ccec2346a9bcc5f804979commit-bot@chromium.org// a1 = p0 . (p3 x p2) 744858638d8a5bef8f9940ccec2346a9bcc5f804979commit-bot@chromium.org// a2 = p1 . (p0 x p3) 745858638d8a5bef8f9940ccec2346a9bcc5f804979commit-bot@chromium.org// a3 = p2 . (p1 x p0) 746858638d8a5bef8f9940ccec2346a9bcc5f804979commit-bot@chromium.org// Places the values of d1, d2, d3 in array d passed in 747858638d8a5bef8f9940ccec2346a9bcc5f804979commit-bot@chromium.orgstatic void calc_cubic_inflection_func(const SkPoint p[4], SkScalar d[3]) { 748858638d8a5bef8f9940ccec2346a9bcc5f804979commit-bot@chromium.org SkScalar a1 = calc_dot_cross_cubic(p[0], p[3], p[2]); 749858638d8a5bef8f9940ccec2346a9bcc5f804979commit-bot@chromium.org SkScalar a2 = calc_dot_cross_cubic(p[1], p[0], p[3]); 750858638d8a5bef8f9940ccec2346a9bcc5f804979commit-bot@chromium.org SkScalar a3 = calc_dot_cross_cubic(p[2], p[1], p[0]); 751858638d8a5bef8f9940ccec2346a9bcc5f804979commit-bot@chromium.org 752858638d8a5bef8f9940ccec2346a9bcc5f804979commit-bot@chromium.org // need to scale a's or values in later calculations will grow to high 753858638d8a5bef8f9940ccec2346a9bcc5f804979commit-bot@chromium.org SkScalar max = SkScalarAbs(a1); 754858638d8a5bef8f9940ccec2346a9bcc5f804979commit-bot@chromium.org max = SkMaxScalar(max, SkScalarAbs(a2)); 755858638d8a5bef8f9940ccec2346a9bcc5f804979commit-bot@chromium.org max = SkMaxScalar(max, SkScalarAbs(a3)); 756858638d8a5bef8f9940ccec2346a9bcc5f804979commit-bot@chromium.org max = 1.f/max; 757858638d8a5bef8f9940ccec2346a9bcc5f804979commit-bot@chromium.org a1 = a1 * max; 758858638d8a5bef8f9940ccec2346a9bcc5f804979commit-bot@chromium.org a2 = a2 * max; 759858638d8a5bef8f9940ccec2346a9bcc5f804979commit-bot@chromium.org a3 = a3 * max; 760858638d8a5bef8f9940ccec2346a9bcc5f804979commit-bot@chromium.org 761858638d8a5bef8f9940ccec2346a9bcc5f804979commit-bot@chromium.org d[2] = 3.f * a3; 762858638d8a5bef8f9940ccec2346a9bcc5f804979commit-bot@chromium.org d[1] = d[2] - a2; 763858638d8a5bef8f9940ccec2346a9bcc5f804979commit-bot@chromium.org d[0] = d[1] - a2 + a1; 764858638d8a5bef8f9940ccec2346a9bcc5f804979commit-bot@chromium.org} 765858638d8a5bef8f9940ccec2346a9bcc5f804979commit-bot@chromium.org 766858638d8a5bef8f9940ccec2346a9bcc5f804979commit-bot@chromium.orgint GrPathUtils::chopCubicAtLoopIntersection(const SkPoint src[4], SkPoint dst[10], SkScalar klm[9], 767858638d8a5bef8f9940ccec2346a9bcc5f804979commit-bot@chromium.org SkScalar klm_rev[3]) { 768858638d8a5bef8f9940ccec2346a9bcc5f804979commit-bot@chromium.org // Variable to store the two parametric values at the loop double point 769858638d8a5bef8f9940ccec2346a9bcc5f804979commit-bot@chromium.org SkScalar smallS = 0.f; 770858638d8a5bef8f9940ccec2346a9bcc5f804979commit-bot@chromium.org SkScalar largeS = 0.f; 771858638d8a5bef8f9940ccec2346a9bcc5f804979commit-bot@chromium.org 772858638d8a5bef8f9940ccec2346a9bcc5f804979commit-bot@chromium.org SkScalar d[3]; 773858638d8a5bef8f9940ccec2346a9bcc5f804979commit-bot@chromium.org calc_cubic_inflection_func(src, d); 774858638d8a5bef8f9940ccec2346a9bcc5f804979commit-bot@chromium.org 775858638d8a5bef8f9940ccec2346a9bcc5f804979commit-bot@chromium.org CubicType cType = classify_cubic(src, d); 776858638d8a5bef8f9940ccec2346a9bcc5f804979commit-bot@chromium.org 777858638d8a5bef8f9940ccec2346a9bcc5f804979commit-bot@chromium.org int chop_count = 0; 778858638d8a5bef8f9940ccec2346a9bcc5f804979commit-bot@chromium.org if (kLoop_CubicType == cType) { 779858638d8a5bef8f9940ccec2346a9bcc5f804979commit-bot@chromium.org SkScalar tempSqrt = SkScalarSqrt(4.f * d[0] * d[2] - 3.f * d[1] * d[1]); 780858638d8a5bef8f9940ccec2346a9bcc5f804979commit-bot@chromium.org SkScalar ls = d[1] - tempSqrt; 781858638d8a5bef8f9940ccec2346a9bcc5f804979commit-bot@chromium.org SkScalar lt = 2.f * d[0]; 782858638d8a5bef8f9940ccec2346a9bcc5f804979commit-bot@chromium.org SkScalar ms = d[1] + tempSqrt; 783858638d8a5bef8f9940ccec2346a9bcc5f804979commit-bot@chromium.org SkScalar mt = 2.f * d[0]; 784858638d8a5bef8f9940ccec2346a9bcc5f804979commit-bot@chromium.org ls = ls / lt; 785858638d8a5bef8f9940ccec2346a9bcc5f804979commit-bot@chromium.org ms = ms / mt; 786858638d8a5bef8f9940ccec2346a9bcc5f804979commit-bot@chromium.org // need to have t values sorted since this is what is expected by SkChopCubicAt 787858638d8a5bef8f9940ccec2346a9bcc5f804979commit-bot@chromium.org if (ls <= ms) { 788858638d8a5bef8f9940ccec2346a9bcc5f804979commit-bot@chromium.org smallS = ls; 789858638d8a5bef8f9940ccec2346a9bcc5f804979commit-bot@chromium.org largeS = ms; 790858638d8a5bef8f9940ccec2346a9bcc5f804979commit-bot@chromium.org } else { 791858638d8a5bef8f9940ccec2346a9bcc5f804979commit-bot@chromium.org smallS = ms; 792858638d8a5bef8f9940ccec2346a9bcc5f804979commit-bot@chromium.org largeS = ls; 793858638d8a5bef8f9940ccec2346a9bcc5f804979commit-bot@chromium.org } 794858638d8a5bef8f9940ccec2346a9bcc5f804979commit-bot@chromium.org 795858638d8a5bef8f9940ccec2346a9bcc5f804979commit-bot@chromium.org SkScalar chop_ts[2]; 796858638d8a5bef8f9940ccec2346a9bcc5f804979commit-bot@chromium.org if (smallS > 0.f && smallS < 1.f) { 797858638d8a5bef8f9940ccec2346a9bcc5f804979commit-bot@chromium.org chop_ts[chop_count++] = smallS; 798858638d8a5bef8f9940ccec2346a9bcc5f804979commit-bot@chromium.org } 799858638d8a5bef8f9940ccec2346a9bcc5f804979commit-bot@chromium.org if (largeS > 0.f && largeS < 1.f) { 800858638d8a5bef8f9940ccec2346a9bcc5f804979commit-bot@chromium.org chop_ts[chop_count++] = largeS; 801858638d8a5bef8f9940ccec2346a9bcc5f804979commit-bot@chromium.org } 802858638d8a5bef8f9940ccec2346a9bcc5f804979commit-bot@chromium.org if(dst) { 803858638d8a5bef8f9940ccec2346a9bcc5f804979commit-bot@chromium.org SkChopCubicAt(src, dst, chop_ts, chop_count); 804858638d8a5bef8f9940ccec2346a9bcc5f804979commit-bot@chromium.org } 805858638d8a5bef8f9940ccec2346a9bcc5f804979commit-bot@chromium.org } else { 806858638d8a5bef8f9940ccec2346a9bcc5f804979commit-bot@chromium.org if (dst) { 807858638d8a5bef8f9940ccec2346a9bcc5f804979commit-bot@chromium.org memcpy(dst, src, sizeof(SkPoint) * 4); 808858638d8a5bef8f9940ccec2346a9bcc5f804979commit-bot@chromium.org } 809858638d8a5bef8f9940ccec2346a9bcc5f804979commit-bot@chromium.org } 810858638d8a5bef8f9940ccec2346a9bcc5f804979commit-bot@chromium.org 811858638d8a5bef8f9940ccec2346a9bcc5f804979commit-bot@chromium.org if (klm && klm_rev) { 812858638d8a5bef8f9940ccec2346a9bcc5f804979commit-bot@chromium.org // Set klm_rev to to match the sub_section of cubic that needs to have its orientation 813858638d8a5bef8f9940ccec2346a9bcc5f804979commit-bot@chromium.org // flipped. This will always be the section that is the "loop" 814858638d8a5bef8f9940ccec2346a9bcc5f804979commit-bot@chromium.org if (2 == chop_count) { 815858638d8a5bef8f9940ccec2346a9bcc5f804979commit-bot@chromium.org klm_rev[0] = 1.f; 816858638d8a5bef8f9940ccec2346a9bcc5f804979commit-bot@chromium.org klm_rev[1] = -1.f; 817858638d8a5bef8f9940ccec2346a9bcc5f804979commit-bot@chromium.org klm_rev[2] = 1.f; 818858638d8a5bef8f9940ccec2346a9bcc5f804979commit-bot@chromium.org } else if (1 == chop_count) { 819858638d8a5bef8f9940ccec2346a9bcc5f804979commit-bot@chromium.org if (smallS < 0.f) { 820858638d8a5bef8f9940ccec2346a9bcc5f804979commit-bot@chromium.org klm_rev[0] = -1.f; 821858638d8a5bef8f9940ccec2346a9bcc5f804979commit-bot@chromium.org klm_rev[1] = 1.f; 822858638d8a5bef8f9940ccec2346a9bcc5f804979commit-bot@chromium.org } else { 823858638d8a5bef8f9940ccec2346a9bcc5f804979commit-bot@chromium.org klm_rev[0] = 1.f; 824858638d8a5bef8f9940ccec2346a9bcc5f804979commit-bot@chromium.org klm_rev[1] = -1.f; 825858638d8a5bef8f9940ccec2346a9bcc5f804979commit-bot@chromium.org } 826858638d8a5bef8f9940ccec2346a9bcc5f804979commit-bot@chromium.org } else { 827858638d8a5bef8f9940ccec2346a9bcc5f804979commit-bot@chromium.org if (smallS < 0.f && largeS > 1.f) { 828858638d8a5bef8f9940ccec2346a9bcc5f804979commit-bot@chromium.org klm_rev[0] = -1.f; 829858638d8a5bef8f9940ccec2346a9bcc5f804979commit-bot@chromium.org } else { 830858638d8a5bef8f9940ccec2346a9bcc5f804979commit-bot@chromium.org klm_rev[0] = 1.f; 831858638d8a5bef8f9940ccec2346a9bcc5f804979commit-bot@chromium.org } 832858638d8a5bef8f9940ccec2346a9bcc5f804979commit-bot@chromium.org } 833858638d8a5bef8f9940ccec2346a9bcc5f804979commit-bot@chromium.org SkScalar controlK[4]; 834858638d8a5bef8f9940ccec2346a9bcc5f804979commit-bot@chromium.org SkScalar controlL[4]; 835858638d8a5bef8f9940ccec2346a9bcc5f804979commit-bot@chromium.org SkScalar controlM[4]; 836858638d8a5bef8f9940ccec2346a9bcc5f804979commit-bot@chromium.org 837858638d8a5bef8f9940ccec2346a9bcc5f804979commit-bot@chromium.org if (kSerpentine_CubicType == cType || (kCusp_CubicType == cType && 0.f != d[0])) { 838858638d8a5bef8f9940ccec2346a9bcc5f804979commit-bot@chromium.org set_serp_klm(d, controlK, controlL, controlM); 839858638d8a5bef8f9940ccec2346a9bcc5f804979commit-bot@chromium.org } else if (kLoop_CubicType == cType) { 840858638d8a5bef8f9940ccec2346a9bcc5f804979commit-bot@chromium.org set_loop_klm(d, controlK, controlL, controlM); 841858638d8a5bef8f9940ccec2346a9bcc5f804979commit-bot@chromium.org } else if (kCusp_CubicType == cType) { 842858638d8a5bef8f9940ccec2346a9bcc5f804979commit-bot@chromium.org SkASSERT(0.f == d[0]); 843858638d8a5bef8f9940ccec2346a9bcc5f804979commit-bot@chromium.org set_cusp_klm(d, controlK, controlL, controlM); 844858638d8a5bef8f9940ccec2346a9bcc5f804979commit-bot@chromium.org } else if (kQuadratic_CubicType == cType) { 845858638d8a5bef8f9940ccec2346a9bcc5f804979commit-bot@chromium.org set_quadratic_klm(d, controlK, controlL, controlM); 846858638d8a5bef8f9940ccec2346a9bcc5f804979commit-bot@chromium.org } 847858638d8a5bef8f9940ccec2346a9bcc5f804979commit-bot@chromium.org 848858638d8a5bef8f9940ccec2346a9bcc5f804979commit-bot@chromium.org calc_cubic_klm(src, controlK, controlL, controlM, klm, &klm[3], &klm[6]); 849858638d8a5bef8f9940ccec2346a9bcc5f804979commit-bot@chromium.org } 850858638d8a5bef8f9940ccec2346a9bcc5f804979commit-bot@chromium.org return chop_count + 1; 851858638d8a5bef8f9940ccec2346a9bcc5f804979commit-bot@chromium.org} 852858638d8a5bef8f9940ccec2346a9bcc5f804979commit-bot@chromium.org 853858638d8a5bef8f9940ccec2346a9bcc5f804979commit-bot@chromium.orgvoid GrPathUtils::getCubicKLM(const SkPoint p[4], SkScalar klm[9]) { 854858638d8a5bef8f9940ccec2346a9bcc5f804979commit-bot@chromium.org SkScalar d[3]; 855858638d8a5bef8f9940ccec2346a9bcc5f804979commit-bot@chromium.org calc_cubic_inflection_func(p, d); 856858638d8a5bef8f9940ccec2346a9bcc5f804979commit-bot@chromium.org 857858638d8a5bef8f9940ccec2346a9bcc5f804979commit-bot@chromium.org CubicType cType = classify_cubic(p, d); 858858638d8a5bef8f9940ccec2346a9bcc5f804979commit-bot@chromium.org 859858638d8a5bef8f9940ccec2346a9bcc5f804979commit-bot@chromium.org SkScalar controlK[4]; 860858638d8a5bef8f9940ccec2346a9bcc5f804979commit-bot@chromium.org SkScalar controlL[4]; 861858638d8a5bef8f9940ccec2346a9bcc5f804979commit-bot@chromium.org SkScalar controlM[4]; 862858638d8a5bef8f9940ccec2346a9bcc5f804979commit-bot@chromium.org 863858638d8a5bef8f9940ccec2346a9bcc5f804979commit-bot@chromium.org if (kSerpentine_CubicType == cType || (kCusp_CubicType == cType && 0.f != d[0])) { 864858638d8a5bef8f9940ccec2346a9bcc5f804979commit-bot@chromium.org set_serp_klm(d, controlK, controlL, controlM); 865858638d8a5bef8f9940ccec2346a9bcc5f804979commit-bot@chromium.org } else if (kLoop_CubicType == cType) { 866858638d8a5bef8f9940ccec2346a9bcc5f804979commit-bot@chromium.org set_loop_klm(d, controlK, controlL, controlM); 867858638d8a5bef8f9940ccec2346a9bcc5f804979commit-bot@chromium.org } else if (kCusp_CubicType == cType) { 868858638d8a5bef8f9940ccec2346a9bcc5f804979commit-bot@chromium.org SkASSERT(0.f == d[0]); 869858638d8a5bef8f9940ccec2346a9bcc5f804979commit-bot@chromium.org set_cusp_klm(d, controlK, controlL, controlM); 870858638d8a5bef8f9940ccec2346a9bcc5f804979commit-bot@chromium.org } else if (kQuadratic_CubicType == cType) { 871858638d8a5bef8f9940ccec2346a9bcc5f804979commit-bot@chromium.org set_quadratic_klm(d, controlK, controlL, controlM); 872858638d8a5bef8f9940ccec2346a9bcc5f804979commit-bot@chromium.org } 873858638d8a5bef8f9940ccec2346a9bcc5f804979commit-bot@chromium.org 874858638d8a5bef8f9940ccec2346a9bcc5f804979commit-bot@chromium.org calc_cubic_klm(p, controlK, controlL, controlM, klm, &klm[3], &klm[6]); 875858638d8a5bef8f9940ccec2346a9bcc5f804979commit-bot@chromium.org} 876