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" 114dbbd04314cc0606f8d3bafe515c97e52c180f73halcanary#include "SkMathPriv.h" 129d18b7873ce9b44f130a41e0cbd0a3df76ab9adfsenorblanco@chromium.org 1325294d76b1c5ca34ba6cc7033ee42af6484b046bBrian Osmanstatic const SkScalar gMinCurveTol = 0.0001f; 1425294d76b1c5ca34ba6cc7033ee42af6484b046bBrian Osman 1581712883419f76e25d2ffec38a9438284a45a48dbsalomon@google.comSkScalar GrPathUtils::scaleToleranceToSrc(SkScalar devTol, 16b9086a026844e4cfd08b219e49ce3f12294cba98bsalomon@google.com const SkMatrix& viewM, 17fd03d4a829efe2d77a712fd991927c55f59a2ffecommit-bot@chromium.org const SkRect& pathBounds) { 18181e9bd9484ece4132e0cc5cfcff602134e5489dbsalomon@google.com // In order to tesselate the path we get a bound on how much the matrix can 191878651990d7c9da72cf43481432232bbef3550dcommit-bot@chromium.org // scale when mapping to screen coordinates. 201878651990d7c9da72cf43481432232bbef3550dcommit-bot@chromium.org SkScalar stretch = viewM.getMaxScale(); 21181e9bd9484ece4132e0cc5cfcff602134e5489dbsalomon@google.com 22181e9bd9484ece4132e0cc5cfcff602134e5489dbsalomon@google.com if (stretch < 0) { 23383963280ddd13030331765fe88d2aefa3e32130bsalomon@google.com // take worst case mapRadius amoung four corners. 24383963280ddd13030331765fe88d2aefa3e32130bsalomon@google.com // (less than perfect) 25383963280ddd13030331765fe88d2aefa3e32130bsalomon@google.com for (int i = 0; i < 4; ++i) { 26b9086a026844e4cfd08b219e49ce3f12294cba98bsalomon@google.com SkMatrix mat; 27383963280ddd13030331765fe88d2aefa3e32130bsalomon@google.com mat.setTranslate((i % 2) ? pathBounds.fLeft : pathBounds.fRight, 28383963280ddd13030331765fe88d2aefa3e32130bsalomon@google.com (i < 2) ? pathBounds.fTop : pathBounds.fBottom); 29383963280ddd13030331765fe88d2aefa3e32130bsalomon@google.com mat.postConcat(viewM); 30383963280ddd13030331765fe88d2aefa3e32130bsalomon@google.com stretch = SkMaxScalar(stretch, mat.mapRadius(SK_Scalar1)); 31383963280ddd13030331765fe88d2aefa3e32130bsalomon@google.com } 32181e9bd9484ece4132e0cc5cfcff602134e5489dbsalomon@google.com } 3325294d76b1c5ca34ba6cc7033ee42af6484b046bBrian Osman SkScalar srcTol = devTol / stretch; 3425294d76b1c5ca34ba6cc7033ee42af6484b046bBrian Osman if (srcTol < gMinCurveTol) { 3525294d76b1c5ca34ba6cc7033ee42af6484b046bBrian Osman srcTol = gMinCurveTol; 3625294d76b1c5ca34ba6cc7033ee42af6484b046bBrian Osman } 3725294d76b1c5ca34ba6cc7033ee42af6484b046bBrian Osman return srcTol; 38181e9bd9484ece4132e0cc5cfcff602134e5489dbsalomon@google.com} 39181e9bd9484ece4132e0cc5cfcff602134e5489dbsalomon@google.com 40b712a85aea212cf5bfe5514a4fefc184545a8d3cRobert Phillipsuint32_t GrPathUtils::quadraticPointCount(const SkPoint points[], SkScalar tol) { 4125294d76b1c5ca34ba6cc7033ee42af6484b046bBrian Osman // You should have called scaleToleranceToSrc, which guarantees this 4225294d76b1c5ca34ba6cc7033ee42af6484b046bBrian Osman SkASSERT(tol >= gMinCurveTol); 43c10a88825d119054a9f4e7b7af7a3f887e30ab6btomhudson@google.com 4481712883419f76e25d2ffec38a9438284a45a48dbsalomon@google.com SkScalar d = points[1].distanceToLineSegmentBetween(points[0], points[2]); 45b6a40b83f36b905cf85e2e3dcd88d6423938b505senorblanco if (!SkScalarIsFinite(d)) { 4649b7b6f38fc9d6cbcfa5865db364ff79c3ed7bfeBrian Osman return kMaxPointsPerCurve; 47b6a40b83f36b905cf85e2e3dcd88d6423938b505senorblanco } else 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); 5480ea19ca4bdd68c1493666a5fe7e4ce9d43ded8breed SkScalar divSqrt = SkScalarSqrt(d / tol); 555a23a14b1fbc7503bdeff83e4b45ae7c258c6e96egdaniel if (((SkScalar)SK_MaxS32) <= divSqrt) { 5649b7b6f38fc9d6cbcfa5865db364ff79c3ed7bfeBrian Osman return kMaxPointsPerCurve; 575a23a14b1fbc7503bdeff83e4b45ae7c258c6e96egdaniel } else { 585a23a14b1fbc7503bdeff83e4b45ae7c258c6e96egdaniel int temp = SkScalarCeilToInt(divSqrt); 595a23a14b1fbc7503bdeff83e4b45ae7c258c6e96egdaniel int pow2 = GrNextPow2(temp); 605a23a14b1fbc7503bdeff83e4b45ae7c258c6e96egdaniel // Because of NaNs & INFs we can wind up with a degenerate temp 615a23a14b1fbc7503bdeff83e4b45ae7c258c6e96egdaniel // such that pow2 comes out negative. Also, our point generator 625a23a14b1fbc7503bdeff83e4b45ae7c258c6e96egdaniel // will always output at least one pt. 635a23a14b1fbc7503bdeff83e4b45ae7c258c6e96egdaniel if (pow2 < 1) { 645a23a14b1fbc7503bdeff83e4b45ae7c258c6e96egdaniel pow2 = 1; 655a23a14b1fbc7503bdeff83e4b45ae7c258c6e96egdaniel } 6649b7b6f38fc9d6cbcfa5865db364ff79c3ed7bfeBrian Osman return SkTMin(pow2, kMaxPointsPerCurve); 6761f3bde1ba114e7b39b53411f4aa31ed0875d159bsalomon@google.com } 689d18b7873ce9b44f130a41e0cbd0a3df76ab9adfsenorblanco@chromium.org } 699d18b7873ce9b44f130a41e0cbd0a3df76ab9adfsenorblanco@chromium.org} 709d18b7873ce9b44f130a41e0cbd0a3df76ab9adfsenorblanco@chromium.org 71972f9cd7a063d0544f8c919fd12b9a3adbd12b24commit-bot@chromium.orguint32_t GrPathUtils::generateQuadraticPoints(const SkPoint& p0, 72972f9cd7a063d0544f8c919fd12b9a3adbd12b24commit-bot@chromium.org const SkPoint& p1, 73972f9cd7a063d0544f8c919fd12b9a3adbd12b24commit-bot@chromium.org const SkPoint& p2, 7481712883419f76e25d2ffec38a9438284a45a48dbsalomon@google.com SkScalar tolSqd, 75972f9cd7a063d0544f8c919fd12b9a3adbd12b24commit-bot@chromium.org SkPoint** points, 76c10a88825d119054a9f4e7b7af7a3f887e30ab6btomhudson@google.com uint32_t pointsLeft) { 779d18b7873ce9b44f130a41e0cbd0a3df76ab9adfsenorblanco@chromium.org if (pointsLeft < 2 || 789d18b7873ce9b44f130a41e0cbd0a3df76ab9adfsenorblanco@chromium.org (p1.distanceToLineSegmentBetweenSqd(p0, p2)) < tolSqd) { 799d18b7873ce9b44f130a41e0cbd0a3df76ab9adfsenorblanco@chromium.org (*points)[0] = p2; 809d18b7873ce9b44f130a41e0cbd0a3df76ab9adfsenorblanco@chromium.org *points += 1; 819d18b7873ce9b44f130a41e0cbd0a3df76ab9adfsenorblanco@chromium.org return 1; 829d18b7873ce9b44f130a41e0cbd0a3df76ab9adfsenorblanco@chromium.org } 839d18b7873ce9b44f130a41e0cbd0a3df76ab9adfsenorblanco@chromium.org 84972f9cd7a063d0544f8c919fd12b9a3adbd12b24commit-bot@chromium.org SkPoint q[] = { 8581712883419f76e25d2ffec38a9438284a45a48dbsalomon@google.com { SkScalarAve(p0.fX, p1.fX), SkScalarAve(p0.fY, p1.fY) }, 8681712883419f76e25d2ffec38a9438284a45a48dbsalomon@google.com { SkScalarAve(p1.fX, p2.fX), SkScalarAve(p1.fY, p2.fY) }, 879d18b7873ce9b44f130a41e0cbd0a3df76ab9adfsenorblanco@chromium.org }; 88972f9cd7a063d0544f8c919fd12b9a3adbd12b24commit-bot@chromium.org SkPoint r = { SkScalarAve(q[0].fX, q[1].fX), SkScalarAve(q[0].fY, q[1].fY) }; 899d18b7873ce9b44f130a41e0cbd0a3df76ab9adfsenorblanco@chromium.org 909d18b7873ce9b44f130a41e0cbd0a3df76ab9adfsenorblanco@chromium.org pointsLeft >>= 1; 919d18b7873ce9b44f130a41e0cbd0a3df76ab9adfsenorblanco@chromium.org uint32_t a = generateQuadraticPoints(p0, q[0], r, tolSqd, points, pointsLeft); 929d18b7873ce9b44f130a41e0cbd0a3df76ab9adfsenorblanco@chromium.org uint32_t b = generateQuadraticPoints(r, q[1], p2, tolSqd, points, pointsLeft); 939d18b7873ce9b44f130a41e0cbd0a3df76ab9adfsenorblanco@chromium.org return a + b; 949d18b7873ce9b44f130a41e0cbd0a3df76ab9adfsenorblanco@chromium.org} 959d18b7873ce9b44f130a41e0cbd0a3df76ab9adfsenorblanco@chromium.org 96972f9cd7a063d0544f8c919fd12b9a3adbd12b24commit-bot@chromium.orguint32_t GrPathUtils::cubicPointCount(const SkPoint points[], 9781712883419f76e25d2ffec38a9438284a45a48dbsalomon@google.com SkScalar tol) { 9825294d76b1c5ca34ba6cc7033ee42af6484b046bBrian Osman // You should have called scaleToleranceToSrc, which guarantees this 9925294d76b1c5ca34ba6cc7033ee42af6484b046bBrian Osman SkASSERT(tol >= gMinCurveTol); 100c10a88825d119054a9f4e7b7af7a3f887e30ab6btomhudson@google.com 101972f9cd7a063d0544f8c919fd12b9a3adbd12b24commit-bot@chromium.org SkScalar d = SkTMax( 102c10a88825d119054a9f4e7b7af7a3f887e30ab6btomhudson@google.com points[1].distanceToLineSegmentBetweenSqd(points[0], points[3]), 103c10a88825d119054a9f4e7b7af7a3f887e30ab6btomhudson@google.com points[2].distanceToLineSegmentBetweenSqd(points[0], points[3])); 1042047f00e4698f83499ab91911999a65c21a951c9epoger@google.com d = SkScalarSqrt(d); 105b6a40b83f36b905cf85e2e3dcd88d6423938b505senorblanco if (!SkScalarIsFinite(d)) { 10649b7b6f38fc9d6cbcfa5865db364ff79c3ed7bfeBrian Osman return kMaxPointsPerCurve; 107b6a40b83f36b905cf85e2e3dcd88d6423938b505senorblanco } else if (d <= tol) { 1089d18b7873ce9b44f130a41e0cbd0a3df76ab9adfsenorblanco@chromium.org return 1; 1099d18b7873ce9b44f130a41e0cbd0a3df76ab9adfsenorblanco@chromium.org } else { 11080ea19ca4bdd68c1493666a5fe7e4ce9d43ded8breed SkScalar divSqrt = SkScalarSqrt(d / tol); 1115a23a14b1fbc7503bdeff83e4b45ae7c258c6e96egdaniel if (((SkScalar)SK_MaxS32) <= divSqrt) { 11249b7b6f38fc9d6cbcfa5865db364ff79c3ed7bfeBrian Osman return kMaxPointsPerCurve; 1135a23a14b1fbc7503bdeff83e4b45ae7c258c6e96egdaniel } else { 11480ea19ca4bdd68c1493666a5fe7e4ce9d43ded8breed int temp = SkScalarCeilToInt(SkScalarSqrt(d / tol)); 1155a23a14b1fbc7503bdeff83e4b45ae7c258c6e96egdaniel int pow2 = GrNextPow2(temp); 1165a23a14b1fbc7503bdeff83e4b45ae7c258c6e96egdaniel // Because of NaNs & INFs we can wind up with a degenerate temp 1175a23a14b1fbc7503bdeff83e4b45ae7c258c6e96egdaniel // such that pow2 comes out negative. Also, our point generator 1185a23a14b1fbc7503bdeff83e4b45ae7c258c6e96egdaniel // will always output at least one pt. 1195a23a14b1fbc7503bdeff83e4b45ae7c258c6e96egdaniel if (pow2 < 1) { 1205a23a14b1fbc7503bdeff83e4b45ae7c258c6e96egdaniel pow2 = 1; 1215a23a14b1fbc7503bdeff83e4b45ae7c258c6e96egdaniel } 12249b7b6f38fc9d6cbcfa5865db364ff79c3ed7bfeBrian Osman return SkTMin(pow2, kMaxPointsPerCurve); 12361f3bde1ba114e7b39b53411f4aa31ed0875d159bsalomon@google.com } 1249d18b7873ce9b44f130a41e0cbd0a3df76ab9adfsenorblanco@chromium.org } 1259d18b7873ce9b44f130a41e0cbd0a3df76ab9adfsenorblanco@chromium.org} 1269d18b7873ce9b44f130a41e0cbd0a3df76ab9adfsenorblanco@chromium.org 127972f9cd7a063d0544f8c919fd12b9a3adbd12b24commit-bot@chromium.orguint32_t GrPathUtils::generateCubicPoints(const SkPoint& p0, 128972f9cd7a063d0544f8c919fd12b9a3adbd12b24commit-bot@chromium.org const SkPoint& p1, 129972f9cd7a063d0544f8c919fd12b9a3adbd12b24commit-bot@chromium.org const SkPoint& p2, 130972f9cd7a063d0544f8c919fd12b9a3adbd12b24commit-bot@chromium.org const SkPoint& p3, 13181712883419f76e25d2ffec38a9438284a45a48dbsalomon@google.com SkScalar tolSqd, 132972f9cd7a063d0544f8c919fd12b9a3adbd12b24commit-bot@chromium.org SkPoint** points, 133c10a88825d119054a9f4e7b7af7a3f887e30ab6btomhudson@google.com uint32_t pointsLeft) { 1349d18b7873ce9b44f130a41e0cbd0a3df76ab9adfsenorblanco@chromium.org if (pointsLeft < 2 || 1359d18b7873ce9b44f130a41e0cbd0a3df76ab9adfsenorblanco@chromium.org (p1.distanceToLineSegmentBetweenSqd(p0, p3) < tolSqd && 1369d18b7873ce9b44f130a41e0cbd0a3df76ab9adfsenorblanco@chromium.org p2.distanceToLineSegmentBetweenSqd(p0, p3) < tolSqd)) { 137f08ce6cd53c5607ed068f755036b062a8693a8dcrobertphillips (*points)[0] = p3; 138f08ce6cd53c5607ed068f755036b062a8693a8dcrobertphillips *points += 1; 139f08ce6cd53c5607ed068f755036b062a8693a8dcrobertphillips return 1; 140f08ce6cd53c5607ed068f755036b062a8693a8dcrobertphillips } 141972f9cd7a063d0544f8c919fd12b9a3adbd12b24commit-bot@chromium.org SkPoint q[] = { 14281712883419f76e25d2ffec38a9438284a45a48dbsalomon@google.com { SkScalarAve(p0.fX, p1.fX), SkScalarAve(p0.fY, p1.fY) }, 14381712883419f76e25d2ffec38a9438284a45a48dbsalomon@google.com { SkScalarAve(p1.fX, p2.fX), SkScalarAve(p1.fY, p2.fY) }, 14481712883419f76e25d2ffec38a9438284a45a48dbsalomon@google.com { SkScalarAve(p2.fX, p3.fX), SkScalarAve(p2.fY, p3.fY) } 1459d18b7873ce9b44f130a41e0cbd0a3df76ab9adfsenorblanco@chromium.org }; 146972f9cd7a063d0544f8c919fd12b9a3adbd12b24commit-bot@chromium.org SkPoint r[] = { 14781712883419f76e25d2ffec38a9438284a45a48dbsalomon@google.com { SkScalarAve(q[0].fX, q[1].fX), SkScalarAve(q[0].fY, q[1].fY) }, 14881712883419f76e25d2ffec38a9438284a45a48dbsalomon@google.com { SkScalarAve(q[1].fX, q[2].fX), SkScalarAve(q[1].fY, q[2].fY) } 1499d18b7873ce9b44f130a41e0cbd0a3df76ab9adfsenorblanco@chromium.org }; 150972f9cd7a063d0544f8c919fd12b9a3adbd12b24commit-bot@chromium.org SkPoint s = { SkScalarAve(r[0].fX, r[1].fX), SkScalarAve(r[0].fY, r[1].fY) }; 1519d18b7873ce9b44f130a41e0cbd0a3df76ab9adfsenorblanco@chromium.org pointsLeft >>= 1; 1529d18b7873ce9b44f130a41e0cbd0a3df76ab9adfsenorblanco@chromium.org uint32_t a = generateCubicPoints(p0, q[0], r[0], s, tolSqd, points, pointsLeft); 1539d18b7873ce9b44f130a41e0cbd0a3df76ab9adfsenorblanco@chromium.org uint32_t b = generateCubicPoints(s, r[1], q[2], p3, tolSqd, points, pointsLeft); 1549d18b7873ce9b44f130a41e0cbd0a3df76ab9adfsenorblanco@chromium.org return a + b; 1559d18b7873ce9b44f130a41e0cbd0a3df76ab9adfsenorblanco@chromium.org} 1569d18b7873ce9b44f130a41e0cbd0a3df76ab9adfsenorblanco@chromium.org 157b712a85aea212cf5bfe5514a4fefc184545a8d3cRobert Phillipsint GrPathUtils::worstCasePointCount(const SkPath& path, int* subpaths, SkScalar tol) { 15825294d76b1c5ca34ba6cc7033ee42af6484b046bBrian Osman // You should have called scaleToleranceToSrc, which guarantees this 15925294d76b1c5ca34ba6cc7033ee42af6484b046bBrian Osman SkASSERT(tol >= gMinCurveTol); 160c10a88825d119054a9f4e7b7af7a3f887e30ab6btomhudson@google.com 1619d18b7873ce9b44f130a41e0cbd0a3df76ab9adfsenorblanco@chromium.org int pointCount = 0; 1629d18b7873ce9b44f130a41e0cbd0a3df76ab9adfsenorblanco@chromium.org *subpaths = 1; 1639d18b7873ce9b44f130a41e0cbd0a3df76ab9adfsenorblanco@chromium.org 1649d18b7873ce9b44f130a41e0cbd0a3df76ab9adfsenorblanco@chromium.org bool first = true; 1659d18b7873ce9b44f130a41e0cbd0a3df76ab9adfsenorblanco@chromium.org 166129b8e3237b80b9d258a8f48e8f54c0073cafbdcsenorblanco@chromium.org SkPath::Iter iter(path, false); 16794b284d719ee5ccd3e2efbd1d7084ec554583bacbsalomon@google.com SkPath::Verb verb; 1689d18b7873ce9b44f130a41e0cbd0a3df76ab9adfsenorblanco@chromium.org 169972f9cd7a063d0544f8c919fd12b9a3adbd12b24commit-bot@chromium.org SkPoint pts[4]; 17094b284d719ee5ccd3e2efbd1d7084ec554583bacbsalomon@google.com while ((verb = iter.next(pts)) != SkPath::kDone_Verb) { 1719d18b7873ce9b44f130a41e0cbd0a3df76ab9adfsenorblanco@chromium.org 17294b284d719ee5ccd3e2efbd1d7084ec554583bacbsalomon@google.com switch (verb) { 17394b284d719ee5ccd3e2efbd1d7084ec554583bacbsalomon@google.com case SkPath::kLine_Verb: 1749d18b7873ce9b44f130a41e0cbd0a3df76ab9adfsenorblanco@chromium.org pointCount += 1; 1759d18b7873ce9b44f130a41e0cbd0a3df76ab9adfsenorblanco@chromium.org break; 176af18a09d13611526c4217656c98947f9067cb07aegdaniel case SkPath::kConic_Verb: { 177af18a09d13611526c4217656c98947f9067cb07aegdaniel SkScalar weight = iter.conicWeight(); 178af18a09d13611526c4217656c98947f9067cb07aegdaniel SkAutoConicToQuads converter; 179b712a85aea212cf5bfe5514a4fefc184545a8d3cRobert Phillips const SkPoint* quadPts = converter.computeQuads(pts, weight, tol); 180af18a09d13611526c4217656c98947f9067cb07aegdaniel for (int i = 0; i < converter.countQuads(); ++i) { 181af18a09d13611526c4217656c98947f9067cb07aegdaniel pointCount += quadraticPointCount(quadPts + 2*i, tol); 182af18a09d13611526c4217656c98947f9067cb07aegdaniel } 183af18a09d13611526c4217656c98947f9067cb07aegdaniel } 18494b284d719ee5ccd3e2efbd1d7084ec554583bacbsalomon@google.com case SkPath::kQuad_Verb: 1859d18b7873ce9b44f130a41e0cbd0a3df76ab9adfsenorblanco@chromium.org pointCount += quadraticPointCount(pts, tol); 1869d18b7873ce9b44f130a41e0cbd0a3df76ab9adfsenorblanco@chromium.org break; 18794b284d719ee5ccd3e2efbd1d7084ec554583bacbsalomon@google.com case SkPath::kCubic_Verb: 1889d18b7873ce9b44f130a41e0cbd0a3df76ab9adfsenorblanco@chromium.org pointCount += cubicPointCount(pts, tol); 1899d18b7873ce9b44f130a41e0cbd0a3df76ab9adfsenorblanco@chromium.org break; 19094b284d719ee5ccd3e2efbd1d7084ec554583bacbsalomon@google.com case SkPath::kMove_Verb: 1919d18b7873ce9b44f130a41e0cbd0a3df76ab9adfsenorblanco@chromium.org pointCount += 1; 1929d18b7873ce9b44f130a41e0cbd0a3df76ab9adfsenorblanco@chromium.org if (!first) { 1939d18b7873ce9b44f130a41e0cbd0a3df76ab9adfsenorblanco@chromium.org ++(*subpaths); 1949d18b7873ce9b44f130a41e0cbd0a3df76ab9adfsenorblanco@chromium.org } 1959d18b7873ce9b44f130a41e0cbd0a3df76ab9adfsenorblanco@chromium.org break; 1969d18b7873ce9b44f130a41e0cbd0a3df76ab9adfsenorblanco@chromium.org default: 1979d18b7873ce9b44f130a41e0cbd0a3df76ab9adfsenorblanco@chromium.org break; 1989d18b7873ce9b44f130a41e0cbd0a3df76ab9adfsenorblanco@chromium.org } 1999d18b7873ce9b44f130a41e0cbd0a3df76ab9adfsenorblanco@chromium.org first = false; 2009d18b7873ce9b44f130a41e0cbd0a3df76ab9adfsenorblanco@chromium.org } 2019d18b7873ce9b44f130a41e0cbd0a3df76ab9adfsenorblanco@chromium.org return pointCount; 2029d18b7873ce9b44f130a41e0cbd0a3df76ab9adfsenorblanco@chromium.org} 20369cc6ad20ed03f35f9d3c8119a2c32187669a22bbsalomon@google.com 204972f9cd7a063d0544f8c919fd12b9a3adbd12b24commit-bot@chromium.orgvoid GrPathUtils::QuadUVMatrix::set(const SkPoint qPts[3]) { 2051971317bb43580330a9e7e9a1c09c5025fe84aacbsalomon@google.com SkMatrix m; 206dc3c78076ea279d4f6d502b3b42471e9b2bba48ebsalomon@google.com // We want M such that M * xy_pt = uv_pt 207dc3c78076ea279d4f6d502b3b42471e9b2bba48ebsalomon@google.com // We know M * control_pts = [0 1/2 1] 208dc3c78076ea279d4f6d502b3b42471e9b2bba48ebsalomon@google.com // [0 0 1] 209dc3c78076ea279d4f6d502b3b42471e9b2bba48ebsalomon@google.com // [1 1 1] 210f543fd9e8c162b65fd04d1d9439b60911f8eb4c0commit-bot@chromium.org // And control_pts = [x0 x1 x2] 211f543fd9e8c162b65fd04d1d9439b60911f8eb4c0commit-bot@chromium.org // [y0 y1 y2] 212f543fd9e8c162b65fd04d1d9439b60911f8eb4c0commit-bot@chromium.org // [1 1 1 ] 213dc3c78076ea279d4f6d502b3b42471e9b2bba48ebsalomon@google.com // We invert the control pt matrix and post concat to both sides to get M. 214f543fd9e8c162b65fd04d1d9439b60911f8eb4c0commit-bot@chromium.org // Using the known form of the control point matrix and the result, we can 215f543fd9e8c162b65fd04d1d9439b60911f8eb4c0commit-bot@chromium.org // optimize and improve precision. 216f543fd9e8c162b65fd04d1d9439b60911f8eb4c0commit-bot@chromium.org 217f543fd9e8c162b65fd04d1d9439b60911f8eb4c0commit-bot@chromium.org double x0 = qPts[0].fX; 218f543fd9e8c162b65fd04d1d9439b60911f8eb4c0commit-bot@chromium.org double y0 = qPts[0].fY; 219f543fd9e8c162b65fd04d1d9439b60911f8eb4c0commit-bot@chromium.org double x1 = qPts[1].fX; 220f543fd9e8c162b65fd04d1d9439b60911f8eb4c0commit-bot@chromium.org double y1 = qPts[1].fY; 221f543fd9e8c162b65fd04d1d9439b60911f8eb4c0commit-bot@chromium.org double x2 = qPts[2].fX; 222f543fd9e8c162b65fd04d1d9439b60911f8eb4c0commit-bot@chromium.org double y2 = qPts[2].fY; 223f543fd9e8c162b65fd04d1d9439b60911f8eb4c0commit-bot@chromium.org double det = x0*y1 - y0*x1 + x2*y0 - y2*x0 + x1*y2 - y1*x2; 224f543fd9e8c162b65fd04d1d9439b60911f8eb4c0commit-bot@chromium.org 2258491d24bdc3f48f67475c12c60babb9f9dba8047skia.committer@gmail.com if (!sk_float_isfinite(det) 226f543fd9e8c162b65fd04d1d9439b60911f8eb4c0commit-bot@chromium.org || SkScalarNearlyZero((float)det, SK_ScalarNearlyZero * SK_ScalarNearlyZero)) { 227dc3c78076ea279d4f6d502b3b42471e9b2bba48ebsalomon@google.com // The quad is degenerate. Hopefully this is rare. Find the pts that are 228dc3c78076ea279d4f6d502b3b42471e9b2bba48ebsalomon@google.com // farthest apart to compute a line (unless it is really a pt). 229dc3c78076ea279d4f6d502b3b42471e9b2bba48ebsalomon@google.com SkScalar maxD = qPts[0].distanceToSqd(qPts[1]); 230dc3c78076ea279d4f6d502b3b42471e9b2bba48ebsalomon@google.com int maxEdge = 0; 231dc3c78076ea279d4f6d502b3b42471e9b2bba48ebsalomon@google.com SkScalar d = qPts[1].distanceToSqd(qPts[2]); 232dc3c78076ea279d4f6d502b3b42471e9b2bba48ebsalomon@google.com if (d > maxD) { 233dc3c78076ea279d4f6d502b3b42471e9b2bba48ebsalomon@google.com maxD = d; 234dc3c78076ea279d4f6d502b3b42471e9b2bba48ebsalomon@google.com maxEdge = 1; 235dc3c78076ea279d4f6d502b3b42471e9b2bba48ebsalomon@google.com } 236dc3c78076ea279d4f6d502b3b42471e9b2bba48ebsalomon@google.com d = qPts[2].distanceToSqd(qPts[0]); 237dc3c78076ea279d4f6d502b3b42471e9b2bba48ebsalomon@google.com if (d > maxD) { 238dc3c78076ea279d4f6d502b3b42471e9b2bba48ebsalomon@google.com maxD = d; 239dc3c78076ea279d4f6d502b3b42471e9b2bba48ebsalomon@google.com maxEdge = 2; 240dc3c78076ea279d4f6d502b3b42471e9b2bba48ebsalomon@google.com } 241dc3c78076ea279d4f6d502b3b42471e9b2bba48ebsalomon@google.com // We could have a tolerance here, not sure if it would improve anything 242dc3c78076ea279d4f6d502b3b42471e9b2bba48ebsalomon@google.com if (maxD > 0) { 243dc3c78076ea279d4f6d502b3b42471e9b2bba48ebsalomon@google.com // Set the matrix to give (u = 0, v = distance_to_line) 244972f9cd7a063d0544f8c919fd12b9a3adbd12b24commit-bot@chromium.org SkVector lineVec = qPts[(maxEdge + 1)%3] - qPts[maxEdge]; 24520e542e00eccaf7b9e81964692a47086e6aaf568bsalomon@google.com // when looking from the point 0 down the line we want positive 24620e542e00eccaf7b9e81964692a47086e6aaf568bsalomon@google.com // distances to be to the left. This matches the non-degenerate 24720e542e00eccaf7b9e81964692a47086e6aaf568bsalomon@google.com // case. 248972f9cd7a063d0544f8c919fd12b9a3adbd12b24commit-bot@chromium.org lineVec.setOrthog(lineVec, SkPoint::kLeft_Side); 2491971317bb43580330a9e7e9a1c09c5025fe84aacbsalomon@google.com // first row 2501971317bb43580330a9e7e9a1c09c5025fe84aacbsalomon@google.com fM[0] = 0; 2511971317bb43580330a9e7e9a1c09c5025fe84aacbsalomon@google.com fM[1] = 0; 2521971317bb43580330a9e7e9a1c09c5025fe84aacbsalomon@google.com fM[2] = 0; 2531971317bb43580330a9e7e9a1c09c5025fe84aacbsalomon@google.com // second row 2541971317bb43580330a9e7e9a1c09c5025fe84aacbsalomon@google.com fM[3] = lineVec.fX; 2551971317bb43580330a9e7e9a1c09c5025fe84aacbsalomon@google.com fM[4] = lineVec.fY; 2561971317bb43580330a9e7e9a1c09c5025fe84aacbsalomon@google.com fM[5] = -lineVec.dot(qPts[maxEdge]); 257dc3c78076ea279d4f6d502b3b42471e9b2bba48ebsalomon@google.com } else { 258dc3c78076ea279d4f6d502b3b42471e9b2bba48ebsalomon@google.com // It's a point. It should cover zero area. Just set the matrix such 259dc3c78076ea279d4f6d502b3b42471e9b2bba48ebsalomon@google.com // that (u, v) will always be far away from the quad. 2601971317bb43580330a9e7e9a1c09c5025fe84aacbsalomon@google.com fM[0] = 0; fM[1] = 0; fM[2] = 100.f; 2611971317bb43580330a9e7e9a1c09c5025fe84aacbsalomon@google.com fM[3] = 0; fM[4] = 0; fM[5] = 100.f; 262dc3c78076ea279d4f6d502b3b42471e9b2bba48ebsalomon@google.com } 263dc3c78076ea279d4f6d502b3b42471e9b2bba48ebsalomon@google.com } else { 264f543fd9e8c162b65fd04d1d9439b60911f8eb4c0commit-bot@chromium.org double scale = 1.0/det; 265f543fd9e8c162b65fd04d1d9439b60911f8eb4c0commit-bot@chromium.org 266f543fd9e8c162b65fd04d1d9439b60911f8eb4c0commit-bot@chromium.org // compute adjugate matrix 26787a223401d8575d398eb369f7be7afdabbdfab08robertphillips double a2, a3, a4, a5, a6, a7, a8; 268f543fd9e8c162b65fd04d1d9439b60911f8eb4c0commit-bot@chromium.org a2 = x1*y2-x2*y1; 269f543fd9e8c162b65fd04d1d9439b60911f8eb4c0commit-bot@chromium.org 270f543fd9e8c162b65fd04d1d9439b60911f8eb4c0commit-bot@chromium.org a3 = y2-y0; 271f543fd9e8c162b65fd04d1d9439b60911f8eb4c0commit-bot@chromium.org a4 = x0-x2; 272f543fd9e8c162b65fd04d1d9439b60911f8eb4c0commit-bot@chromium.org a5 = x2*y0-x0*y2; 273f543fd9e8c162b65fd04d1d9439b60911f8eb4c0commit-bot@chromium.org 274f543fd9e8c162b65fd04d1d9439b60911f8eb4c0commit-bot@chromium.org a6 = y0-y1; 275f543fd9e8c162b65fd04d1d9439b60911f8eb4c0commit-bot@chromium.org a7 = x1-x0; 276f543fd9e8c162b65fd04d1d9439b60911f8eb4c0commit-bot@chromium.org a8 = x0*y1-x1*y0; 277f543fd9e8c162b65fd04d1d9439b60911f8eb4c0commit-bot@chromium.org 2788491d24bdc3f48f67475c12c60babb9f9dba8047skia.committer@gmail.com // this performs the uv_pts*adjugate(control_pts) multiply, 279f543fd9e8c162b65fd04d1d9439b60911f8eb4c0commit-bot@chromium.org // then does the scale by 1/det afterwards to improve precision 280f543fd9e8c162b65fd04d1d9439b60911f8eb4c0commit-bot@chromium.org m[SkMatrix::kMScaleX] = (float)((0.5*a3 + a6)*scale); 281f543fd9e8c162b65fd04d1d9439b60911f8eb4c0commit-bot@chromium.org m[SkMatrix::kMSkewX] = (float)((0.5*a4 + a7)*scale); 282f543fd9e8c162b65fd04d1d9439b60911f8eb4c0commit-bot@chromium.org m[SkMatrix::kMTransX] = (float)((0.5*a5 + a8)*scale); 283f543fd9e8c162b65fd04d1d9439b60911f8eb4c0commit-bot@chromium.org 284f543fd9e8c162b65fd04d1d9439b60911f8eb4c0commit-bot@chromium.org m[SkMatrix::kMSkewY] = (float)(a6*scale); 285f543fd9e8c162b65fd04d1d9439b60911f8eb4c0commit-bot@chromium.org m[SkMatrix::kMScaleY] = (float)(a7*scale); 286f543fd9e8c162b65fd04d1d9439b60911f8eb4c0commit-bot@chromium.org m[SkMatrix::kMTransY] = (float)(a8*scale); 287f543fd9e8c162b65fd04d1d9439b60911f8eb4c0commit-bot@chromium.org 28887a223401d8575d398eb369f7be7afdabbdfab08robertphillips // kMPersp0 & kMPersp1 should algebraically be zero 28987a223401d8575d398eb369f7be7afdabbdfab08robertphillips m[SkMatrix::kMPersp0] = 0.0f; 29087a223401d8575d398eb369f7be7afdabbdfab08robertphillips m[SkMatrix::kMPersp1] = 0.0f; 291f543fd9e8c162b65fd04d1d9439b60911f8eb4c0commit-bot@chromium.org m[SkMatrix::kMPersp2] = (float)((a2 + a5 + a8)*scale); 2921971317bb43580330a9e7e9a1c09c5025fe84aacbsalomon@google.com 2931971317bb43580330a9e7e9a1c09c5025fe84aacbsalomon@google.com // It may not be normalized to have 1.0 in the bottom right 2941971317bb43580330a9e7e9a1c09c5025fe84aacbsalomon@google.com float m33 = m.get(SkMatrix::kMPersp2); 2951971317bb43580330a9e7e9a1c09c5025fe84aacbsalomon@google.com if (1.f != m33) { 2961971317bb43580330a9e7e9a1c09c5025fe84aacbsalomon@google.com m33 = 1.f / m33; 2971971317bb43580330a9e7e9a1c09c5025fe84aacbsalomon@google.com fM[0] = m33 * m.get(SkMatrix::kMScaleX); 2981971317bb43580330a9e7e9a1c09c5025fe84aacbsalomon@google.com fM[1] = m33 * m.get(SkMatrix::kMSkewX); 2991971317bb43580330a9e7e9a1c09c5025fe84aacbsalomon@google.com fM[2] = m33 * m.get(SkMatrix::kMTransX); 3001971317bb43580330a9e7e9a1c09c5025fe84aacbsalomon@google.com fM[3] = m33 * m.get(SkMatrix::kMSkewY); 3011971317bb43580330a9e7e9a1c09c5025fe84aacbsalomon@google.com fM[4] = m33 * m.get(SkMatrix::kMScaleY); 3021971317bb43580330a9e7e9a1c09c5025fe84aacbsalomon@google.com fM[5] = m33 * m.get(SkMatrix::kMTransY); 3031971317bb43580330a9e7e9a1c09c5025fe84aacbsalomon@google.com } else { 3041971317bb43580330a9e7e9a1c09c5025fe84aacbsalomon@google.com fM[0] = m.get(SkMatrix::kMScaleX); 3051971317bb43580330a9e7e9a1c09c5025fe84aacbsalomon@google.com fM[1] = m.get(SkMatrix::kMSkewX); 3061971317bb43580330a9e7e9a1c09c5025fe84aacbsalomon@google.com fM[2] = m.get(SkMatrix::kMTransX); 3071971317bb43580330a9e7e9a1c09c5025fe84aacbsalomon@google.com fM[3] = m.get(SkMatrix::kMSkewY); 3081971317bb43580330a9e7e9a1c09c5025fe84aacbsalomon@google.com fM[4] = m.get(SkMatrix::kMScaleY); 3091971317bb43580330a9e7e9a1c09c5025fe84aacbsalomon@google.com fM[5] = m.get(SkMatrix::kMTransY); 3101971317bb43580330a9e7e9a1c09c5025fe84aacbsalomon@google.com } 311dc3c78076ea279d4f6d502b3b42471e9b2bba48ebsalomon@google.com } 31269cc6ad20ed03f35f9d3c8119a2c32187669a22bbsalomon@google.com} 31369cc6ad20ed03f35f9d3c8119a2c32187669a22bbsalomon@google.com 314139484095f014ab08265c32337fddeeec6c0877dcommit-bot@chromium.org//////////////////////////////////////////////////////////////////////////////// 315139484095f014ab08265c32337fddeeec6c0877dcommit-bot@chromium.org 3163b830a9ea3bce9eba663ab95486cf153831cd29cDean McNamee// k = (y2 - y0, x0 - x2, x2*y0 - x0*y2) 3173b830a9ea3bce9eba663ab95486cf153831cd29cDean McNamee// l = (y1 - y0, x0 - x1, x1*y0 - x0*y1) * 2*w 3183b830a9ea3bce9eba663ab95486cf153831cd29cDean McNamee// m = (y2 - y1, x1 - x2, x2*y1 - x1*y2) * 2*w 319cc26127920069cbd83e92cca3c69bb56cb165bcccsmartdaltonvoid GrPathUtils::getConicKLM(const SkPoint p[3], const SkScalar weight, SkMatrix* out) { 320cc26127920069cbd83e92cca3c69bb56cb165bcccsmartdalton SkMatrix& klm = *out; 321139484095f014ab08265c32337fddeeec6c0877dcommit-bot@chromium.org const SkScalar w2 = 2.f * weight; 322139484095f014ab08265c32337fddeeec6c0877dcommit-bot@chromium.org klm[0] = p[2].fY - p[0].fY; 323139484095f014ab08265c32337fddeeec6c0877dcommit-bot@chromium.org klm[1] = p[0].fX - p[2].fX; 3243b830a9ea3bce9eba663ab95486cf153831cd29cDean McNamee klm[2] = p[2].fX * p[0].fY - p[0].fX * p[2].fY; 325139484095f014ab08265c32337fddeeec6c0877dcommit-bot@chromium.org 326139484095f014ab08265c32337fddeeec6c0877dcommit-bot@chromium.org klm[3] = w2 * (p[1].fY - p[0].fY); 327139484095f014ab08265c32337fddeeec6c0877dcommit-bot@chromium.org klm[4] = w2 * (p[0].fX - p[1].fX); 328139484095f014ab08265c32337fddeeec6c0877dcommit-bot@chromium.org klm[5] = w2 * (p[1].fX * p[0].fY - p[0].fX * p[1].fY); 329139484095f014ab08265c32337fddeeec6c0877dcommit-bot@chromium.org 330139484095f014ab08265c32337fddeeec6c0877dcommit-bot@chromium.org klm[6] = w2 * (p[2].fY - p[1].fY); 331139484095f014ab08265c32337fddeeec6c0877dcommit-bot@chromium.org klm[7] = w2 * (p[1].fX - p[2].fX); 332139484095f014ab08265c32337fddeeec6c0877dcommit-bot@chromium.org klm[8] = w2 * (p[2].fX * p[1].fY - p[1].fX * p[2].fY); 333139484095f014ab08265c32337fddeeec6c0877dcommit-bot@chromium.org 334139484095f014ab08265c32337fddeeec6c0877dcommit-bot@chromium.org // scale the max absolute value of coeffs to 10 335139484095f014ab08265c32337fddeeec6c0877dcommit-bot@chromium.org SkScalar scale = 0.f; 336139484095f014ab08265c32337fddeeec6c0877dcommit-bot@chromium.org for (int i = 0; i < 9; ++i) { 337139484095f014ab08265c32337fddeeec6c0877dcommit-bot@chromium.org scale = SkMaxScalar(scale, SkScalarAbs(klm[i])); 338139484095f014ab08265c32337fddeeec6c0877dcommit-bot@chromium.org } 339139484095f014ab08265c32337fddeeec6c0877dcommit-bot@chromium.org SkASSERT(scale > 0.f); 340139484095f014ab08265c32337fddeeec6c0877dcommit-bot@chromium.org scale = 10.f / scale; 341139484095f014ab08265c32337fddeeec6c0877dcommit-bot@chromium.org for (int i = 0; i < 9; ++i) { 342139484095f014ab08265c32337fddeeec6c0877dcommit-bot@chromium.org klm[i] *= scale; 343139484095f014ab08265c32337fddeeec6c0877dcommit-bot@chromium.org } 344139484095f014ab08265c32337fddeeec6c0877dcommit-bot@chromium.org} 345139484095f014ab08265c32337fddeeec6c0877dcommit-bot@chromium.org 346139484095f014ab08265c32337fddeeec6c0877dcommit-bot@chromium.org//////////////////////////////////////////////////////////////////////////////// 347139484095f014ab08265c32337fddeeec6c0877dcommit-bot@chromium.org 34869cc6ad20ed03f35f9d3c8119a2c32187669a22bbsalomon@google.comnamespace { 349a51ab8416db9772a2eae3122f4f69801642daeb5bsalomon@google.com 350a51ab8416db9772a2eae3122f4f69801642daeb5bsalomon@google.com// a is the first control point of the cubic. 351a51ab8416db9772a2eae3122f4f69801642daeb5bsalomon@google.com// ab is the vector from a to the second control point. 352a51ab8416db9772a2eae3122f4f69801642daeb5bsalomon@google.com// dc is the vector from the fourth to the third control point. 353a51ab8416db9772a2eae3122f4f69801642daeb5bsalomon@google.com// d is the fourth control point. 354a51ab8416db9772a2eae3122f4f69801642daeb5bsalomon@google.com// p is the candidate quadratic control point. 355a51ab8416db9772a2eae3122f4f69801642daeb5bsalomon@google.com// this assumes that the cubic doesn't inflect and is simple 356a51ab8416db9772a2eae3122f4f69801642daeb5bsalomon@google.combool is_point_within_cubic_tangents(const SkPoint& a, 357a51ab8416db9772a2eae3122f4f69801642daeb5bsalomon@google.com const SkVector& ab, 358a51ab8416db9772a2eae3122f4f69801642daeb5bsalomon@google.com const SkVector& dc, 359a51ab8416db9772a2eae3122f4f69801642daeb5bsalomon@google.com const SkPoint& d, 360026beb52a29a620290fcfb24f1e7e9e75547b80freed SkPathPriv::FirstDirection dir, 361a51ab8416db9772a2eae3122f4f69801642daeb5bsalomon@google.com const SkPoint p) { 362a51ab8416db9772a2eae3122f4f69801642daeb5bsalomon@google.com SkVector ap = p - a; 363a51ab8416db9772a2eae3122f4f69801642daeb5bsalomon@google.com SkScalar apXab = ap.cross(ab); 364026beb52a29a620290fcfb24f1e7e9e75547b80freed if (SkPathPriv::kCW_FirstDirection == dir) { 365a51ab8416db9772a2eae3122f4f69801642daeb5bsalomon@google.com if (apXab > 0) { 366a51ab8416db9772a2eae3122f4f69801642daeb5bsalomon@google.com return false; 367a51ab8416db9772a2eae3122f4f69801642daeb5bsalomon@google.com } 368a51ab8416db9772a2eae3122f4f69801642daeb5bsalomon@google.com } else { 369026beb52a29a620290fcfb24f1e7e9e75547b80freed SkASSERT(SkPathPriv::kCCW_FirstDirection == dir); 370a51ab8416db9772a2eae3122f4f69801642daeb5bsalomon@google.com if (apXab < 0) { 371a51ab8416db9772a2eae3122f4f69801642daeb5bsalomon@google.com return false; 372a51ab8416db9772a2eae3122f4f69801642daeb5bsalomon@google.com } 373a51ab8416db9772a2eae3122f4f69801642daeb5bsalomon@google.com } 374a51ab8416db9772a2eae3122f4f69801642daeb5bsalomon@google.com 375a51ab8416db9772a2eae3122f4f69801642daeb5bsalomon@google.com SkVector dp = p - d; 376a51ab8416db9772a2eae3122f4f69801642daeb5bsalomon@google.com SkScalar dpXdc = dp.cross(dc); 377026beb52a29a620290fcfb24f1e7e9e75547b80freed if (SkPathPriv::kCW_FirstDirection == dir) { 378a51ab8416db9772a2eae3122f4f69801642daeb5bsalomon@google.com if (dpXdc < 0) { 379a51ab8416db9772a2eae3122f4f69801642daeb5bsalomon@google.com return false; 380a51ab8416db9772a2eae3122f4f69801642daeb5bsalomon@google.com } 381a51ab8416db9772a2eae3122f4f69801642daeb5bsalomon@google.com } else { 382026beb52a29a620290fcfb24f1e7e9e75547b80freed SkASSERT(SkPathPriv::kCCW_FirstDirection == dir); 383a51ab8416db9772a2eae3122f4f69801642daeb5bsalomon@google.com if (dpXdc > 0) { 384a51ab8416db9772a2eae3122f4f69801642daeb5bsalomon@google.com return false; 385a51ab8416db9772a2eae3122f4f69801642daeb5bsalomon@google.com } 386a51ab8416db9772a2eae3122f4f69801642daeb5bsalomon@google.com } 387a51ab8416db9772a2eae3122f4f69801642daeb5bsalomon@google.com return true; 388a51ab8416db9772a2eae3122f4f69801642daeb5bsalomon@google.com} 389a51ab8416db9772a2eae3122f4f69801642daeb5bsalomon@google.com 39069cc6ad20ed03f35f9d3c8119a2c32187669a22bbsalomon@google.comvoid convert_noninflect_cubic_to_quads(const SkPoint p[4], 391a51ab8416db9772a2eae3122f4f69801642daeb5bsalomon@google.com SkScalar toleranceSqd, 392a51ab8416db9772a2eae3122f4f69801642daeb5bsalomon@google.com bool constrainWithinTangents, 393026beb52a29a620290fcfb24f1e7e9e75547b80freed SkPathPriv::FirstDirection dir, 39469cc6ad20ed03f35f9d3c8119a2c32187669a22bbsalomon@google.com SkTArray<SkPoint, true>* quads, 39569cc6ad20ed03f35f9d3c8119a2c32187669a22bbsalomon@google.com int sublevel = 0) { 39654ad851361c55466f1e4950585afc2aa6cf173c5bsalomon@google.com 39754ad851361c55466f1e4950585afc2aa6cf173c5bsalomon@google.com // Notation: Point a is always p[0]. Point b is p[1] unless p[1] == p[0], in which case it is 39854ad851361c55466f1e4950585afc2aa6cf173c5bsalomon@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]. 39954ad851361c55466f1e4950585afc2aa6cf173c5bsalomon@google.com 400a51ab8416db9772a2eae3122f4f69801642daeb5bsalomon@google.com SkVector ab = p[1] - p[0]; 401a51ab8416db9772a2eae3122f4f69801642daeb5bsalomon@google.com SkVector dc = p[2] - p[3]; 402a51ab8416db9772a2eae3122f4f69801642daeb5bsalomon@google.com 403f08ce6cd53c5607ed068f755036b062a8693a8dcrobertphillips if (ab.lengthSqd() < SK_ScalarNearlyZero) { 404f08ce6cd53c5607ed068f755036b062a8693a8dcrobertphillips if (dc.lengthSqd() < SK_ScalarNearlyZero) { 405a51ab8416db9772a2eae3122f4f69801642daeb5bsalomon@google.com SkPoint* degQuad = quads->push_back_n(3); 406a51ab8416db9772a2eae3122f4f69801642daeb5bsalomon@google.com degQuad[0] = p[0]; 407a51ab8416db9772a2eae3122f4f69801642daeb5bsalomon@google.com degQuad[1] = p[0]; 408a51ab8416db9772a2eae3122f4f69801642daeb5bsalomon@google.com degQuad[2] = p[3]; 409a51ab8416db9772a2eae3122f4f69801642daeb5bsalomon@google.com return; 410a51ab8416db9772a2eae3122f4f69801642daeb5bsalomon@google.com } 411a51ab8416db9772a2eae3122f4f69801642daeb5bsalomon@google.com ab = p[2] - p[0]; 412a51ab8416db9772a2eae3122f4f69801642daeb5bsalomon@google.com } 413f08ce6cd53c5607ed068f755036b062a8693a8dcrobertphillips if (dc.lengthSqd() < SK_ScalarNearlyZero) { 414a51ab8416db9772a2eae3122f4f69801642daeb5bsalomon@google.com dc = p[1] - p[3]; 415a51ab8416db9772a2eae3122f4f69801642daeb5bsalomon@google.com } 416a51ab8416db9772a2eae3122f4f69801642daeb5bsalomon@google.com 4173935a7bfe64293edf9b06527f59d657ff4e280cbbsalomon // When the ab and cd tangents are degenerate or nearly parallel with vector from d to a the 4183935a7bfe64293edf9b06527f59d657ff4e280cbbsalomon // constraint that the quad point falls between the tangents becomes hard to enforce and we are 4193935a7bfe64293edf9b06527f59d657ff4e280cbbsalomon // likely to hit the max subdivision count. However, in this case the cubic is approaching a 4203935a7bfe64293edf9b06527f59d657ff4e280cbbsalomon // line and the accuracy of the quad point isn't so important. We check if the two middle cubic 4213935a7bfe64293edf9b06527f59d657ff4e280cbbsalomon // control points are very close to the baseline vector. If so then we just pick quadratic 4223935a7bfe64293edf9b06527f59d657ff4e280cbbsalomon // points on the control polygon. 42354ad851361c55466f1e4950585afc2aa6cf173c5bsalomon@google.com 42454ad851361c55466f1e4950585afc2aa6cf173c5bsalomon@google.com if (constrainWithinTangents) { 42554ad851361c55466f1e4950585afc2aa6cf173c5bsalomon@google.com SkVector da = p[0] - p[3]; 4263935a7bfe64293edf9b06527f59d657ff4e280cbbsalomon bool doQuads = dc.lengthSqd() < SK_ScalarNearlyZero || 4273935a7bfe64293edf9b06527f59d657ff4e280cbbsalomon ab.lengthSqd() < SK_ScalarNearlyZero; 4283935a7bfe64293edf9b06527f59d657ff4e280cbbsalomon if (!doQuads) { 4293935a7bfe64293edf9b06527f59d657ff4e280cbbsalomon SkScalar invDALengthSqd = da.lengthSqd(); 4303935a7bfe64293edf9b06527f59d657ff4e280cbbsalomon if (invDALengthSqd > SK_ScalarNearlyZero) { 4313935a7bfe64293edf9b06527f59d657ff4e280cbbsalomon invDALengthSqd = SkScalarInvert(invDALengthSqd); 4323935a7bfe64293edf9b06527f59d657ff4e280cbbsalomon // cross(ab, da)^2/length(da)^2 == sqd distance from b to line from d to a. 4333935a7bfe64293edf9b06527f59d657ff4e280cbbsalomon // same goes for point c using vector cd. 4343935a7bfe64293edf9b06527f59d657ff4e280cbbsalomon SkScalar detABSqd = ab.cross(da); 4353935a7bfe64293edf9b06527f59d657ff4e280cbbsalomon detABSqd = SkScalarSquare(detABSqd); 4363935a7bfe64293edf9b06527f59d657ff4e280cbbsalomon SkScalar detDCSqd = dc.cross(da); 4373935a7bfe64293edf9b06527f59d657ff4e280cbbsalomon detDCSqd = SkScalarSquare(detDCSqd); 4388be952ad8c9deefe19cff36f9ad217563400f817Mike Reed if (detABSqd * invDALengthSqd < toleranceSqd && 4398be952ad8c9deefe19cff36f9ad217563400f817Mike Reed detDCSqd * invDALengthSqd < toleranceSqd) 4408be952ad8c9deefe19cff36f9ad217563400f817Mike Reed { 4413935a7bfe64293edf9b06527f59d657ff4e280cbbsalomon doQuads = true; 44254ad851361c55466f1e4950585afc2aa6cf173c5bsalomon@google.com } 44354ad851361c55466f1e4950585afc2aa6cf173c5bsalomon@google.com } 44454ad851361c55466f1e4950585afc2aa6cf173c5bsalomon@google.com } 4453935a7bfe64293edf9b06527f59d657ff4e280cbbsalomon if (doQuads) { 4463935a7bfe64293edf9b06527f59d657ff4e280cbbsalomon SkPoint b = p[0] + ab; 4473935a7bfe64293edf9b06527f59d657ff4e280cbbsalomon SkPoint c = p[3] + dc; 4483935a7bfe64293edf9b06527f59d657ff4e280cbbsalomon SkPoint mid = b + c; 4493935a7bfe64293edf9b06527f59d657ff4e280cbbsalomon mid.scale(SK_ScalarHalf); 4503935a7bfe64293edf9b06527f59d657ff4e280cbbsalomon // Insert two quadratics to cover the case when ab points away from d and/or dc 4513935a7bfe64293edf9b06527f59d657ff4e280cbbsalomon // points away from a. 4523935a7bfe64293edf9b06527f59d657ff4e280cbbsalomon if (SkVector::DotProduct(da, dc) < 0 || SkVector::DotProduct(ab,da) > 0) { 4533935a7bfe64293edf9b06527f59d657ff4e280cbbsalomon SkPoint* qpts = quads->push_back_n(6); 4543935a7bfe64293edf9b06527f59d657ff4e280cbbsalomon qpts[0] = p[0]; 4553935a7bfe64293edf9b06527f59d657ff4e280cbbsalomon qpts[1] = b; 4563935a7bfe64293edf9b06527f59d657ff4e280cbbsalomon qpts[2] = mid; 4573935a7bfe64293edf9b06527f59d657ff4e280cbbsalomon qpts[3] = mid; 4583935a7bfe64293edf9b06527f59d657ff4e280cbbsalomon qpts[4] = c; 4593935a7bfe64293edf9b06527f59d657ff4e280cbbsalomon qpts[5] = p[3]; 4603935a7bfe64293edf9b06527f59d657ff4e280cbbsalomon } else { 4613935a7bfe64293edf9b06527f59d657ff4e280cbbsalomon SkPoint* qpts = quads->push_back_n(3); 4623935a7bfe64293edf9b06527f59d657ff4e280cbbsalomon qpts[0] = p[0]; 4633935a7bfe64293edf9b06527f59d657ff4e280cbbsalomon qpts[1] = mid; 4643935a7bfe64293edf9b06527f59d657ff4e280cbbsalomon qpts[2] = p[3]; 4653935a7bfe64293edf9b06527f59d657ff4e280cbbsalomon } 4663935a7bfe64293edf9b06527f59d657ff4e280cbbsalomon return; 4673935a7bfe64293edf9b06527f59d657ff4e280cbbsalomon } 46854ad851361c55466f1e4950585afc2aa6cf173c5bsalomon@google.com } 46954ad851361c55466f1e4950585afc2aa6cf173c5bsalomon@google.com 470a51ab8416db9772a2eae3122f4f69801642daeb5bsalomon@google.com static const SkScalar kLengthScale = 3 * SK_Scalar1 / 2; 47169cc6ad20ed03f35f9d3c8119a2c32187669a22bbsalomon@google.com static const int kMaxSubdivs = 10; 47269cc6ad20ed03f35f9d3c8119a2c32187669a22bbsalomon@google.com 473a51ab8416db9772a2eae3122f4f69801642daeb5bsalomon@google.com ab.scale(kLengthScale); 474a51ab8416db9772a2eae3122f4f69801642daeb5bsalomon@google.com dc.scale(kLengthScale); 47569cc6ad20ed03f35f9d3c8119a2c32187669a22bbsalomon@google.com 476a51ab8416db9772a2eae3122f4f69801642daeb5bsalomon@google.com // e0 and e1 are extrapolations along vectors ab and dc. 47769cc6ad20ed03f35f9d3c8119a2c32187669a22bbsalomon@google.com SkVector c0 = p[0]; 47869cc6ad20ed03f35f9d3c8119a2c32187669a22bbsalomon@google.com c0 += ab; 47969cc6ad20ed03f35f9d3c8119a2c32187669a22bbsalomon@google.com SkVector c1 = p[3]; 48069cc6ad20ed03f35f9d3c8119a2c32187669a22bbsalomon@google.com c1 += dc; 48169cc6ad20ed03f35f9d3c8119a2c32187669a22bbsalomon@google.com 48254ad851361c55466f1e4950585afc2aa6cf173c5bsalomon@google.com SkScalar dSqd = sublevel > kMaxSubdivs ? 0 : c0.distanceToSqd(c1); 483a51ab8416db9772a2eae3122f4f69801642daeb5bsalomon@google.com if (dSqd < toleranceSqd) { 48469cc6ad20ed03f35f9d3c8119a2c32187669a22bbsalomon@google.com SkPoint cAvg = c0; 48569cc6ad20ed03f35f9d3c8119a2c32187669a22bbsalomon@google.com cAvg += c1; 48669cc6ad20ed03f35f9d3c8119a2c32187669a22bbsalomon@google.com cAvg.scale(SK_ScalarHalf); 48769cc6ad20ed03f35f9d3c8119a2c32187669a22bbsalomon@google.com 488a51ab8416db9772a2eae3122f4f69801642daeb5bsalomon@google.com bool subdivide = false; 489a51ab8416db9772a2eae3122f4f69801642daeb5bsalomon@google.com 490a51ab8416db9772a2eae3122f4f69801642daeb5bsalomon@google.com if (constrainWithinTangents && 491a51ab8416db9772a2eae3122f4f69801642daeb5bsalomon@google.com !is_point_within_cubic_tangents(p[0], ab, dc, p[3], dir, cAvg)) { 49254ad851361c55466f1e4950585afc2aa6cf173c5bsalomon@google.com // choose a new cAvg that is the intersection of the two tangent lines. 493a51ab8416db9772a2eae3122f4f69801642daeb5bsalomon@google.com ab.setOrthog(ab); 494a51ab8416db9772a2eae3122f4f69801642daeb5bsalomon@google.com SkScalar z0 = -ab.dot(p[0]); 495a51ab8416db9772a2eae3122f4f69801642daeb5bsalomon@google.com dc.setOrthog(dc); 496a51ab8416db9772a2eae3122f4f69801642daeb5bsalomon@google.com SkScalar z1 = -dc.dot(p[3]); 4978be952ad8c9deefe19cff36f9ad217563400f817Mike Reed cAvg.fX = ab.fY * z1 - z0 * dc.fY; 4988be952ad8c9deefe19cff36f9ad217563400f817Mike Reed cAvg.fY = z0 * dc.fX - ab.fX * z1; 4998be952ad8c9deefe19cff36f9ad217563400f817Mike Reed SkScalar z = ab.fX * dc.fY - ab.fY * dc.fX; 500a51ab8416db9772a2eae3122f4f69801642daeb5bsalomon@google.com z = SkScalarInvert(z); 501a51ab8416db9772a2eae3122f4f69801642daeb5bsalomon@google.com cAvg.fX *= z; 502a51ab8416db9772a2eae3122f4f69801642daeb5bsalomon@google.com cAvg.fY *= z; 503a51ab8416db9772a2eae3122f4f69801642daeb5bsalomon@google.com if (sublevel <= kMaxSubdivs) { 504a51ab8416db9772a2eae3122f4f69801642daeb5bsalomon@google.com SkScalar d0Sqd = c0.distanceToSqd(cAvg); 505a51ab8416db9772a2eae3122f4f69801642daeb5bsalomon@google.com SkScalar d1Sqd = c1.distanceToSqd(cAvg); 50654ad851361c55466f1e4950585afc2aa6cf173c5bsalomon@google.com // We need to subdivide if d0 + d1 > tolerance but we have the sqd values. We know 50754ad851361c55466f1e4950585afc2aa6cf173c5bsalomon@google.com // the distances and tolerance can't be negative. 508a51ab8416db9772a2eae3122f4f69801642daeb5bsalomon@google.com // (d0 + d1)^2 > toleranceSqd 509a51ab8416db9772a2eae3122f4f69801642daeb5bsalomon@google.com // d0Sqd + 2*d0*d1 + d1Sqd > toleranceSqd 5108be952ad8c9deefe19cff36f9ad217563400f817Mike Reed SkScalar d0d1 = SkScalarSqrt(d0Sqd * d1Sqd); 511a51ab8416db9772a2eae3122f4f69801642daeb5bsalomon@google.com subdivide = 2 * d0d1 + d0Sqd + d1Sqd > toleranceSqd; 512a51ab8416db9772a2eae3122f4f69801642daeb5bsalomon@google.com } 513a51ab8416db9772a2eae3122f4f69801642daeb5bsalomon@google.com } 514a51ab8416db9772a2eae3122f4f69801642daeb5bsalomon@google.com if (!subdivide) { 515a51ab8416db9772a2eae3122f4f69801642daeb5bsalomon@google.com SkPoint* pts = quads->push_back_n(3); 516a51ab8416db9772a2eae3122f4f69801642daeb5bsalomon@google.com pts[0] = p[0]; 517a51ab8416db9772a2eae3122f4f69801642daeb5bsalomon@google.com pts[1] = cAvg; 518a51ab8416db9772a2eae3122f4f69801642daeb5bsalomon@google.com pts[2] = p[3]; 519a51ab8416db9772a2eae3122f4f69801642daeb5bsalomon@google.com return; 520a51ab8416db9772a2eae3122f4f69801642daeb5bsalomon@google.com } 52169cc6ad20ed03f35f9d3c8119a2c32187669a22bbsalomon@google.com } 522a51ab8416db9772a2eae3122f4f69801642daeb5bsalomon@google.com SkPoint choppedPts[7]; 523a51ab8416db9772a2eae3122f4f69801642daeb5bsalomon@google.com SkChopCubicAtHalf(p, choppedPts); 524a51ab8416db9772a2eae3122f4f69801642daeb5bsalomon@google.com convert_noninflect_cubic_to_quads(choppedPts + 0, 525a51ab8416db9772a2eae3122f4f69801642daeb5bsalomon@google.com toleranceSqd, 526a51ab8416db9772a2eae3122f4f69801642daeb5bsalomon@google.com constrainWithinTangents, 527a51ab8416db9772a2eae3122f4f69801642daeb5bsalomon@google.com dir, 528a51ab8416db9772a2eae3122f4f69801642daeb5bsalomon@google.com quads, 529a51ab8416db9772a2eae3122f4f69801642daeb5bsalomon@google.com sublevel + 1); 530a51ab8416db9772a2eae3122f4f69801642daeb5bsalomon@google.com convert_noninflect_cubic_to_quads(choppedPts + 3, 531a51ab8416db9772a2eae3122f4f69801642daeb5bsalomon@google.com toleranceSqd, 532a51ab8416db9772a2eae3122f4f69801642daeb5bsalomon@google.com constrainWithinTangents, 533a51ab8416db9772a2eae3122f4f69801642daeb5bsalomon@google.com dir, 534a51ab8416db9772a2eae3122f4f69801642daeb5bsalomon@google.com quads, 535a51ab8416db9772a2eae3122f4f69801642daeb5bsalomon@google.com sublevel + 1); 53669cc6ad20ed03f35f9d3c8119a2c32187669a22bbsalomon@google.com} 53769cc6ad20ed03f35f9d3c8119a2c32187669a22bbsalomon@google.com} 53869cc6ad20ed03f35f9d3c8119a2c32187669a22bbsalomon@google.com 539972f9cd7a063d0544f8c919fd12b9a3adbd12b24commit-bot@chromium.orgvoid GrPathUtils::convertCubicToQuads(const SkPoint p[4], 54069cc6ad20ed03f35f9d3c8119a2c32187669a22bbsalomon@google.com SkScalar tolScale, 54169cc6ad20ed03f35f9d3c8119a2c32187669a22bbsalomon@google.com SkTArray<SkPoint, true>* quads) { 54269cc6ad20ed03f35f9d3c8119a2c32187669a22bbsalomon@google.com SkPoint chopped[10]; 54369cc6ad20ed03f35f9d3c8119a2c32187669a22bbsalomon@google.com int count = SkChopCubicAtInflections(p, chopped); 54469cc6ad20ed03f35f9d3c8119a2c32187669a22bbsalomon@google.com 54518fab30d7c4858ef2521e0380573aac5a21b2ed9bsalomon const SkScalar tolSqd = SkScalarSquare(tolScale); 546a51ab8416db9772a2eae3122f4f69801642daeb5bsalomon@google.com 54769cc6ad20ed03f35f9d3c8119a2c32187669a22bbsalomon@google.com for (int i = 0; i < count; ++i) { 54869cc6ad20ed03f35f9d3c8119a2c32187669a22bbsalomon@google.com SkPoint* cubic = chopped + 3*i; 54918fab30d7c4858ef2521e0380573aac5a21b2ed9bsalomon // The direction param is ignored if the third param is false. 55018fab30d7c4858ef2521e0380573aac5a21b2ed9bsalomon convert_noninflect_cubic_to_quads(cubic, tolSqd, false, 55118fab30d7c4858ef2521e0380573aac5a21b2ed9bsalomon SkPathPriv::kCCW_FirstDirection, quads); 55269cc6ad20ed03f35f9d3c8119a2c32187669a22bbsalomon@google.com } 55318fab30d7c4858ef2521e0380573aac5a21b2ed9bsalomon} 55418fab30d7c4858ef2521e0380573aac5a21b2ed9bsalomon 55518fab30d7c4858ef2521e0380573aac5a21b2ed9bsalomonvoid GrPathUtils::convertCubicToQuadsConstrainToTangents(const SkPoint p[4], 55618fab30d7c4858ef2521e0380573aac5a21b2ed9bsalomon SkScalar tolScale, 55718fab30d7c4858ef2521e0380573aac5a21b2ed9bsalomon SkPathPriv::FirstDirection dir, 55818fab30d7c4858ef2521e0380573aac5a21b2ed9bsalomon SkTArray<SkPoint, true>* quads) { 55918fab30d7c4858ef2521e0380573aac5a21b2ed9bsalomon SkPoint chopped[10]; 56018fab30d7c4858ef2521e0380573aac5a21b2ed9bsalomon int count = SkChopCubicAtInflections(p, chopped); 56169cc6ad20ed03f35f9d3c8119a2c32187669a22bbsalomon@google.com 56218fab30d7c4858ef2521e0380573aac5a21b2ed9bsalomon const SkScalar tolSqd = SkScalarSquare(tolScale); 56318fab30d7c4858ef2521e0380573aac5a21b2ed9bsalomon 56418fab30d7c4858ef2521e0380573aac5a21b2ed9bsalomon for (int i = 0; i < count; ++i) { 56518fab30d7c4858ef2521e0380573aac5a21b2ed9bsalomon SkPoint* cubic = chopped + 3*i; 56618fab30d7c4858ef2521e0380573aac5a21b2ed9bsalomon convert_noninflect_cubic_to_quads(cubic, tolSqd, true, dir, quads); 56718fab30d7c4858ef2521e0380573aac5a21b2ed9bsalomon } 56869cc6ad20ed03f35f9d3c8119a2c32187669a22bbsalomon@google.com} 569858638d8a5bef8f9940ccec2346a9bcc5f804979commit-bot@chromium.org 570858638d8a5bef8f9940ccec2346a9bcc5f804979commit-bot@chromium.org//////////////////////////////////////////////////////////////////////////////// 571858638d8a5bef8f9940ccec2346a9bcc5f804979commit-bot@chromium.org 572cc26127920069cbd83e92cca3c69bb56cb165bcccsmartdalton/** 573cc26127920069cbd83e92cca3c69bb56cb165bcccsmartdalton * Computes an SkMatrix that can find the cubic KLM functionals as follows: 574cc26127920069cbd83e92cca3c69bb56cb165bcccsmartdalton * 575cc26127920069cbd83e92cca3c69bb56cb165bcccsmartdalton * | ..K.. | | ..kcoeffs.. | 576cc26127920069cbd83e92cca3c69bb56cb165bcccsmartdalton * | ..L.. | = | ..lcoeffs.. | * inverse_transpose_power_basis_matrix 577cc26127920069cbd83e92cca3c69bb56cb165bcccsmartdalton * | ..M.. | | ..mcoeffs.. | 578cc26127920069cbd83e92cca3c69bb56cb165bcccsmartdalton * 579cc26127920069cbd83e92cca3c69bb56cb165bcccsmartdalton * 'kcoeffs' are the power basis coefficients to a scalar valued cubic function that returns the 580cc26127920069cbd83e92cca3c69bb56cb165bcccsmartdalton * signed distance to line K from a given point on the curve: 581cc26127920069cbd83e92cca3c69bb56cb165bcccsmartdalton * 582cc26127920069cbd83e92cca3c69bb56cb165bcccsmartdalton * k(t,s) = C(t,s) * K [C(t,s) is defined in the following comment] 583cc26127920069cbd83e92cca3c69bb56cb165bcccsmartdalton * 584cc26127920069cbd83e92cca3c69bb56cb165bcccsmartdalton * The same applies for lcoeffs and mcoeffs. These are found separately, depending on the type of 585cc26127920069cbd83e92cca3c69bb56cb165bcccsmartdalton * curve. There are 4 coefficients but 3 rows in the matrix, so in order to do this calculation the 586cc26127920069cbd83e92cca3c69bb56cb165bcccsmartdalton * caller must first remove a specific column of coefficients. 587cc26127920069cbd83e92cca3c69bb56cb165bcccsmartdalton * 588cc26127920069cbd83e92cca3c69bb56cb165bcccsmartdalton * @return which column of klm coefficients to exclude from the calculation. 589cc26127920069cbd83e92cca3c69bb56cb165bcccsmartdalton */ 590cc26127920069cbd83e92cca3c69bb56cb165bcccsmartdaltonstatic int calc_inverse_transpose_power_basis_matrix(const SkPoint pts[4], SkMatrix* out) { 591cc26127920069cbd83e92cca3c69bb56cb165bcccsmartdalton using SkScalar4 = SkNx<4, SkScalar>; 592cc26127920069cbd83e92cca3c69bb56cb165bcccsmartdalton 593cc26127920069cbd83e92cca3c69bb56cb165bcccsmartdalton // First we convert the bezier coordinates 'pts' to power basis coefficients X,Y,W=[0 0 0 1]. 594cc26127920069cbd83e92cca3c69bb56cb165bcccsmartdalton // M3 is the matrix that does this conversion. The homogeneous equation for the cubic becomes: 595cc26127920069cbd83e92cca3c69bb56cb165bcccsmartdalton // 596cc26127920069cbd83e92cca3c69bb56cb165bcccsmartdalton // | X Y 0 | 597cc26127920069cbd83e92cca3c69bb56cb165bcccsmartdalton // C(t,s) = [t^3 t^2*s t*s^2 s^3] * | . . 0 | 598cc26127920069cbd83e92cca3c69bb56cb165bcccsmartdalton // | . . 0 | 599cc26127920069cbd83e92cca3c69bb56cb165bcccsmartdalton // | . . 1 | 600cc26127920069cbd83e92cca3c69bb56cb165bcccsmartdalton // 601cc26127920069cbd83e92cca3c69bb56cb165bcccsmartdalton const SkScalar4 M3[3] = {SkScalar4(-1, 3, -3, 1), 602cc26127920069cbd83e92cca3c69bb56cb165bcccsmartdalton SkScalar4(3, -6, 3, 0), 603cc26127920069cbd83e92cca3c69bb56cb165bcccsmartdalton SkScalar4(-3, 3, 0, 0)}; 604cc26127920069cbd83e92cca3c69bb56cb165bcccsmartdalton // 4th column of M3 = SkScalar4(1, 0, 0, 0)}; 605cc26127920069cbd83e92cca3c69bb56cb165bcccsmartdalton SkScalar4 X(pts[3].x(), 0, 0, 0); 606cc26127920069cbd83e92cca3c69bb56cb165bcccsmartdalton SkScalar4 Y(pts[3].y(), 0, 0, 0); 607cc26127920069cbd83e92cca3c69bb56cb165bcccsmartdalton for (int i = 2; i >= 0; --i) { 608cc26127920069cbd83e92cca3c69bb56cb165bcccsmartdalton X += M3[i] * pts[i].x(); 609cc26127920069cbd83e92cca3c69bb56cb165bcccsmartdalton Y += M3[i] * pts[i].y(); 610858638d8a5bef8f9940ccec2346a9bcc5f804979commit-bot@chromium.org } 611858638d8a5bef8f9940ccec2346a9bcc5f804979commit-bot@chromium.org 612cc26127920069cbd83e92cca3c69bb56cb165bcccsmartdalton // The matrix is 3x4. In order to invert it, we first need to make it square by throwing out one 6130f47a25cac5ceaa172f4db1cc50c36868527ff84csmartdalton // of the top three rows. We toss the row that leaves us with the largest absolute determinant. 6140f47a25cac5ceaa172f4db1cc50c36868527ff84csmartdalton // Since the right column will be [0 0 1], the determinant reduces to x0*y1 - y0*x1. 6150f47a25cac5ceaa172f4db1cc50c36868527ff84csmartdalton SkScalar absDet[4]; 6160f47a25cac5ceaa172f4db1cc50c36868527ff84csmartdalton const SkScalar4 DETX1 = SkNx_shuffle<1,0,0,3>(X), DETY1 = SkNx_shuffle<1,0,0,3>(Y); 6170f47a25cac5ceaa172f4db1cc50c36868527ff84csmartdalton const SkScalar4 DETX2 = SkNx_shuffle<2,2,1,3>(X), DETY2 = SkNx_shuffle<2,2,1,3>(Y); 6180f47a25cac5ceaa172f4db1cc50c36868527ff84csmartdalton const SkScalar4 DET = DETX1 * DETY2 - DETY1 * DETX2; 6190f47a25cac5ceaa172f4db1cc50c36868527ff84csmartdalton DET.abs().store(absDet); 6200f47a25cac5ceaa172f4db1cc50c36868527ff84csmartdalton const int skipRow = absDet[0] > absDet[2] ? (absDet[0] > absDet[1] ? 0 : 1) 6210f47a25cac5ceaa172f4db1cc50c36868527ff84csmartdalton : (absDet[1] > absDet[2] ? 1 : 2); 6220f47a25cac5ceaa172f4db1cc50c36868527ff84csmartdalton const SkScalar rdet = 1 / DET[skipRow]; 623cc26127920069cbd83e92cca3c69bb56cb165bcccsmartdalton const int row0 = (0 != skipRow) ? 0 : 1; 624cc26127920069cbd83e92cca3c69bb56cb165bcccsmartdalton const int row1 = (2 == skipRow) ? 1 : 2; 625cc26127920069cbd83e92cca3c69bb56cb165bcccsmartdalton 626cc26127920069cbd83e92cca3c69bb56cb165bcccsmartdalton // Compute the inverse-transpose of the power basis matrix with the 'skipRow'th row removed. 627cc26127920069cbd83e92cca3c69bb56cb165bcccsmartdalton // Since W=[0 0 0 1], it follows that our corresponding solution will be equal to: 628cc26127920069cbd83e92cca3c69bb56cb165bcccsmartdalton // 629cc26127920069cbd83e92cca3c69bb56cb165bcccsmartdalton // | y1 -x1 x1*y2 - y1*x2 | 630cc26127920069cbd83e92cca3c69bb56cb165bcccsmartdalton // 1/det * | -y0 x0 -x0*y2 + y0*x2 | 631cc26127920069cbd83e92cca3c69bb56cb165bcccsmartdalton // | 0 0 det | 632cc26127920069cbd83e92cca3c69bb56cb165bcccsmartdalton // 633cc26127920069cbd83e92cca3c69bb56cb165bcccsmartdalton const SkScalar4 R(rdet, rdet, rdet, 1); 634cc26127920069cbd83e92cca3c69bb56cb165bcccsmartdalton X *= R; 635cc26127920069cbd83e92cca3c69bb56cb165bcccsmartdalton Y *= R; 636cc26127920069cbd83e92cca3c69bb56cb165bcccsmartdalton 637cc26127920069cbd83e92cca3c69bb56cb165bcccsmartdalton SkScalar x[4], y[4], z[4]; 638cc26127920069cbd83e92cca3c69bb56cb165bcccsmartdalton X.store(x); 639cc26127920069cbd83e92cca3c69bb56cb165bcccsmartdalton Y.store(y); 640cc26127920069cbd83e92cca3c69bb56cb165bcccsmartdalton (X * SkNx_shuffle<3,3,3,3>(Y) - Y * SkNx_shuffle<3,3,3,3>(X)).store(z); 641cc26127920069cbd83e92cca3c69bb56cb165bcccsmartdalton 642cc26127920069cbd83e92cca3c69bb56cb165bcccsmartdalton out->setAll( y[row1], -x[row1], z[row1], 643cc26127920069cbd83e92cca3c69bb56cb165bcccsmartdalton -y[row0], x[row0], -z[row0], 644cc26127920069cbd83e92cca3c69bb56cb165bcccsmartdalton 0, 0, 1); 645cc26127920069cbd83e92cca3c69bb56cb165bcccsmartdalton 646cc26127920069cbd83e92cca3c69bb56cb165bcccsmartdalton return skipRow; 647858638d8a5bef8f9940ccec2346a9bcc5f804979commit-bot@chromium.org} 648858638d8a5bef8f9940ccec2346a9bcc5f804979commit-bot@chromium.org 6497f5af0c2832e8a9682aff9521684c27e1368b6eeChristopher Daltonstatic void calc_serp_klm(const SkPoint pts[4], SkScalar tl, SkScalar sl, SkScalar tm, SkScalar sm, 6507f5af0c2832e8a9682aff9521684c27e1368b6eeChristopher Dalton SkMatrix* klm) { 651cc26127920069cbd83e92cca3c69bb56cb165bcccsmartdalton SkMatrix CIT; 652cc26127920069cbd83e92cca3c69bb56cb165bcccsmartdalton int skipCol = calc_inverse_transpose_power_basis_matrix(pts, &CIT); 653cc26127920069cbd83e92cca3c69bb56cb165bcccsmartdalton 654cc26127920069cbd83e92cca3c69bb56cb165bcccsmartdalton SkMatrix klmCoeffs; 655cc26127920069cbd83e92cca3c69bb56cb165bcccsmartdalton int col = 0; 656cc26127920069cbd83e92cca3c69bb56cb165bcccsmartdalton if (0 != skipCol) { 657cc26127920069cbd83e92cca3c69bb56cb165bcccsmartdalton klmCoeffs[0] = 0; 658cc26127920069cbd83e92cca3c69bb56cb165bcccsmartdalton klmCoeffs[3] = -sl * sl * sl; 659cc26127920069cbd83e92cca3c69bb56cb165bcccsmartdalton klmCoeffs[6] = -sm * sm * sm; 660cc26127920069cbd83e92cca3c69bb56cb165bcccsmartdalton ++col; 661cc26127920069cbd83e92cca3c69bb56cb165bcccsmartdalton } 662cc26127920069cbd83e92cca3c69bb56cb165bcccsmartdalton if (1 != skipCol) { 663cc26127920069cbd83e92cca3c69bb56cb165bcccsmartdalton klmCoeffs[col + 0] = sl * sm; 664cc26127920069cbd83e92cca3c69bb56cb165bcccsmartdalton klmCoeffs[col + 3] = 3 * sl * sl * tl; 665cc26127920069cbd83e92cca3c69bb56cb165bcccsmartdalton klmCoeffs[col + 6] = 3 * sm * sm * tm; 666cc26127920069cbd83e92cca3c69bb56cb165bcccsmartdalton ++col; 667cc26127920069cbd83e92cca3c69bb56cb165bcccsmartdalton } 668cc26127920069cbd83e92cca3c69bb56cb165bcccsmartdalton if (2 != skipCol) { 669cc26127920069cbd83e92cca3c69bb56cb165bcccsmartdalton klmCoeffs[col + 0] = -tl * sm - tm * sl; 670cc26127920069cbd83e92cca3c69bb56cb165bcccsmartdalton klmCoeffs[col + 3] = -3 * sl * tl * tl; 671cc26127920069cbd83e92cca3c69bb56cb165bcccsmartdalton klmCoeffs[col + 6] = -3 * sm * tm * tm; 672cc26127920069cbd83e92cca3c69bb56cb165bcccsmartdalton ++col; 673cc26127920069cbd83e92cca3c69bb56cb165bcccsmartdalton } 674cc26127920069cbd83e92cca3c69bb56cb165bcccsmartdalton 675cc26127920069cbd83e92cca3c69bb56cb165bcccsmartdalton SkASSERT(2 == col); 676cc26127920069cbd83e92cca3c69bb56cb165bcccsmartdalton klmCoeffs[2] = tl * tm; 677cc26127920069cbd83e92cca3c69bb56cb165bcccsmartdalton klmCoeffs[5] = tl * tl * tl; 678cc26127920069cbd83e92cca3c69bb56cb165bcccsmartdalton klmCoeffs[8] = tm * tm * tm; 679cc26127920069cbd83e92cca3c69bb56cb165bcccsmartdalton 680cc26127920069cbd83e92cca3c69bb56cb165bcccsmartdalton klm->setConcat(klmCoeffs, CIT); 681858638d8a5bef8f9940ccec2346a9bcc5f804979commit-bot@chromium.org} 682858638d8a5bef8f9940ccec2346a9bcc5f804979commit-bot@chromium.org 6837f5af0c2832e8a9682aff9521684c27e1368b6eeChristopher Daltonstatic void calc_loop_klm(const SkPoint pts[4], SkScalar td, SkScalar sd, SkScalar te, SkScalar se, 6847f5af0c2832e8a9682aff9521684c27e1368b6eeChristopher Dalton SkMatrix* klm) { 685cc26127920069cbd83e92cca3c69bb56cb165bcccsmartdalton SkMatrix CIT; 686cc26127920069cbd83e92cca3c69bb56cb165bcccsmartdalton int skipCol = calc_inverse_transpose_power_basis_matrix(pts, &CIT); 687cc26127920069cbd83e92cca3c69bb56cb165bcccsmartdalton 688cc26127920069cbd83e92cca3c69bb56cb165bcccsmartdalton const SkScalar tdse = td * se; 689febbffad1c24136f041d7fc2d5ffcd50e47a047fChris Dalton const SkScalar tesd = te * sd; 690cc26127920069cbd83e92cca3c69bb56cb165bcccsmartdalton 691cc26127920069cbd83e92cca3c69bb56cb165bcccsmartdalton SkMatrix klmCoeffs; 692cc26127920069cbd83e92cca3c69bb56cb165bcccsmartdalton int col = 0; 693cc26127920069cbd83e92cca3c69bb56cb165bcccsmartdalton if (0 != skipCol) { 694cc26127920069cbd83e92cca3c69bb56cb165bcccsmartdalton klmCoeffs[0] = 0; 695cc26127920069cbd83e92cca3c69bb56cb165bcccsmartdalton klmCoeffs[3] = -sd * sd * se; 696cc26127920069cbd83e92cca3c69bb56cb165bcccsmartdalton klmCoeffs[6] = -se * se * sd; 697cc26127920069cbd83e92cca3c69bb56cb165bcccsmartdalton ++col; 698cc26127920069cbd83e92cca3c69bb56cb165bcccsmartdalton } 699cc26127920069cbd83e92cca3c69bb56cb165bcccsmartdalton if (1 != skipCol) { 700cc26127920069cbd83e92cca3c69bb56cb165bcccsmartdalton klmCoeffs[col + 0] = sd * se; 701cc26127920069cbd83e92cca3c69bb56cb165bcccsmartdalton klmCoeffs[col + 3] = sd * (2 * tdse + tesd); 702cc26127920069cbd83e92cca3c69bb56cb165bcccsmartdalton klmCoeffs[col + 6] = se * (2 * tesd + tdse); 703cc26127920069cbd83e92cca3c69bb56cb165bcccsmartdalton ++col; 704cc26127920069cbd83e92cca3c69bb56cb165bcccsmartdalton } 705cc26127920069cbd83e92cca3c69bb56cb165bcccsmartdalton if (2 != skipCol) { 706cc26127920069cbd83e92cca3c69bb56cb165bcccsmartdalton klmCoeffs[col + 0] = -tdse - tesd; 707cc26127920069cbd83e92cca3c69bb56cb165bcccsmartdalton klmCoeffs[col + 3] = -td * (tdse + 2 * tesd); 708cc26127920069cbd83e92cca3c69bb56cb165bcccsmartdalton klmCoeffs[col + 6] = -te * (tesd + 2 * tdse); 709cc26127920069cbd83e92cca3c69bb56cb165bcccsmartdalton ++col; 710cc26127920069cbd83e92cca3c69bb56cb165bcccsmartdalton } 711858638d8a5bef8f9940ccec2346a9bcc5f804979commit-bot@chromium.org 712cc26127920069cbd83e92cca3c69bb56cb165bcccsmartdalton SkASSERT(2 == col); 713cc26127920069cbd83e92cca3c69bb56cb165bcccsmartdalton klmCoeffs[2] = td * te; 714cc26127920069cbd83e92cca3c69bb56cb165bcccsmartdalton klmCoeffs[5] = td * td * te; 715cc26127920069cbd83e92cca3c69bb56cb165bcccsmartdalton klmCoeffs[8] = te * te * td; 716858638d8a5bef8f9940ccec2346a9bcc5f804979commit-bot@chromium.org 717cc26127920069cbd83e92cca3c69bb56cb165bcccsmartdalton klm->setConcat(klmCoeffs, CIT); 718858638d8a5bef8f9940ccec2346a9bcc5f804979commit-bot@chromium.org} 719858638d8a5bef8f9940ccec2346a9bcc5f804979commit-bot@chromium.org 720cc26127920069cbd83e92cca3c69bb56cb165bcccsmartdalton// For the case when we have a cusp at a parameter value of infinity (discr == 0, d1 == 0). 7217f5af0c2832e8a9682aff9521684c27e1368b6eeChristopher Daltonstatic void calc_inf_cusp_klm(const SkPoint pts[4], SkScalar tn, SkScalar sn, SkMatrix* klm) { 722cc26127920069cbd83e92cca3c69bb56cb165bcccsmartdalton SkMatrix CIT; 723cc26127920069cbd83e92cca3c69bb56cb165bcccsmartdalton int skipCol = calc_inverse_transpose_power_basis_matrix(pts, &CIT); 724cc26127920069cbd83e92cca3c69bb56cb165bcccsmartdalton 725cc26127920069cbd83e92cca3c69bb56cb165bcccsmartdalton SkMatrix klmCoeffs; 726cc26127920069cbd83e92cca3c69bb56cb165bcccsmartdalton int col = 0; 727cc26127920069cbd83e92cca3c69bb56cb165bcccsmartdalton if (0 != skipCol) { 728cc26127920069cbd83e92cca3c69bb56cb165bcccsmartdalton klmCoeffs[0] = 0; 729cc26127920069cbd83e92cca3c69bb56cb165bcccsmartdalton klmCoeffs[3] = -sn * sn * sn; 730cc26127920069cbd83e92cca3c69bb56cb165bcccsmartdalton ++col; 731cc26127920069cbd83e92cca3c69bb56cb165bcccsmartdalton } 732cc26127920069cbd83e92cca3c69bb56cb165bcccsmartdalton if (1 != skipCol) { 733cc26127920069cbd83e92cca3c69bb56cb165bcccsmartdalton klmCoeffs[col + 0] = 0; 734cc26127920069cbd83e92cca3c69bb56cb165bcccsmartdalton klmCoeffs[col + 3] = 3 * sn * sn * tn; 735cc26127920069cbd83e92cca3c69bb56cb165bcccsmartdalton ++col; 736cc26127920069cbd83e92cca3c69bb56cb165bcccsmartdalton } 737cc26127920069cbd83e92cca3c69bb56cb165bcccsmartdalton if (2 != skipCol) { 738cc26127920069cbd83e92cca3c69bb56cb165bcccsmartdalton klmCoeffs[col + 0] = -sn; 739cc26127920069cbd83e92cca3c69bb56cb165bcccsmartdalton klmCoeffs[col + 3] = -3 * sn * tn * tn; 740cc26127920069cbd83e92cca3c69bb56cb165bcccsmartdalton ++col; 741cc26127920069cbd83e92cca3c69bb56cb165bcccsmartdalton } 742cc26127920069cbd83e92cca3c69bb56cb165bcccsmartdalton 743cc26127920069cbd83e92cca3c69bb56cb165bcccsmartdalton SkASSERT(2 == col); 744cc26127920069cbd83e92cca3c69bb56cb165bcccsmartdalton klmCoeffs[2] = tn; 745cc26127920069cbd83e92cca3c69bb56cb165bcccsmartdalton klmCoeffs[5] = tn * tn * tn; 746cc26127920069cbd83e92cca3c69bb56cb165bcccsmartdalton 747cc26127920069cbd83e92cca3c69bb56cb165bcccsmartdalton klmCoeffs[6] = 0; 748cc26127920069cbd83e92cca3c69bb56cb165bcccsmartdalton klmCoeffs[7] = 0; 749cc26127920069cbd83e92cca3c69bb56cb165bcccsmartdalton klmCoeffs[8] = 1; 750cc26127920069cbd83e92cca3c69bb56cb165bcccsmartdalton 751cc26127920069cbd83e92cca3c69bb56cb165bcccsmartdalton klm->setConcat(klmCoeffs, CIT); 752858638d8a5bef8f9940ccec2346a9bcc5f804979commit-bot@chromium.org} 753858638d8a5bef8f9940ccec2346a9bcc5f804979commit-bot@chromium.org 754cc26127920069cbd83e92cca3c69bb56cb165bcccsmartdalton// For the case when a cubic bezier is actually a quadratic. We duplicate k in l so that the 755cc26127920069cbd83e92cca3c69bb56cb165bcccsmartdalton// implicit becomes: 756cc26127920069cbd83e92cca3c69bb56cb165bcccsmartdalton// 757cc26127920069cbd83e92cca3c69bb56cb165bcccsmartdalton// k^3 - l*m == k^3 - l*k == k * (k^2 - l) 758cc26127920069cbd83e92cca3c69bb56cb165bcccsmartdalton// 759cc26127920069cbd83e92cca3c69bb56cb165bcccsmartdalton// In the quadratic case we can simply assign fixed values at each control point: 760cc26127920069cbd83e92cca3c69bb56cb165bcccsmartdalton// 761cc26127920069cbd83e92cca3c69bb56cb165bcccsmartdalton// | ..K.. | | pts[0] pts[1] pts[2] pts[3] | | 0 1/3 2/3 1 | 762cc26127920069cbd83e92cca3c69bb56cb165bcccsmartdalton// | ..L.. | * | . . . . | == | 0 0 1/3 1 | 763cc26127920069cbd83e92cca3c69bb56cb165bcccsmartdalton// | ..K.. | | 1 1 1 1 | | 0 1/3 2/3 1 | 764cc26127920069cbd83e92cca3c69bb56cb165bcccsmartdalton// 765390f6cd6f9f9ddd8a53da804cee3eff60cd2e2b4Chris Daltonstatic void calc_quadratic_klm(const SkPoint pts[4], double d3, SkMatrix* klm) { 766cc26127920069cbd83e92cca3c69bb56cb165bcccsmartdalton SkMatrix klmAtPts; 767cc26127920069cbd83e92cca3c69bb56cb165bcccsmartdalton klmAtPts.setAll(0, 1.f/3, 1, 768cc26127920069cbd83e92cca3c69bb56cb165bcccsmartdalton 0, 0, 1, 769cc26127920069cbd83e92cca3c69bb56cb165bcccsmartdalton 0, 1.f/3, 1); 770cc26127920069cbd83e92cca3c69bb56cb165bcccsmartdalton 771cc26127920069cbd83e92cca3c69bb56cb165bcccsmartdalton SkMatrix inversePts; 772cc26127920069cbd83e92cca3c69bb56cb165bcccsmartdalton inversePts.setAll(pts[0].x(), pts[1].x(), pts[3].x(), 773cc26127920069cbd83e92cca3c69bb56cb165bcccsmartdalton pts[0].y(), pts[1].y(), pts[3].y(), 774cc26127920069cbd83e92cca3c69bb56cb165bcccsmartdalton 1, 1, 1); 775cc26127920069cbd83e92cca3c69bb56cb165bcccsmartdalton SkAssertResult(inversePts.invert(&inversePts)); 776cc26127920069cbd83e92cca3c69bb56cb165bcccsmartdalton 777cc26127920069cbd83e92cca3c69bb56cb165bcccsmartdalton klm->setConcat(klmAtPts, inversePts); 778cc26127920069cbd83e92cca3c69bb56cb165bcccsmartdalton 779cc26127920069cbd83e92cca3c69bb56cb165bcccsmartdalton // If d3 > 0 we need to flip the orientation of our curve 780cc26127920069cbd83e92cca3c69bb56cb165bcccsmartdalton // This is done by negating the k and l values 781cc26127920069cbd83e92cca3c69bb56cb165bcccsmartdalton if (d3 > 0) { 7827f5af0c2832e8a9682aff9521684c27e1368b6eeChristopher Dalton klm->postScale(-1, -1); 783858638d8a5bef8f9940ccec2346a9bcc5f804979commit-bot@chromium.org } 784858638d8a5bef8f9940ccec2346a9bcc5f804979commit-bot@chromium.org} 785858638d8a5bef8f9940ccec2346a9bcc5f804979commit-bot@chromium.org 786cc26127920069cbd83e92cca3c69bb56cb165bcccsmartdalton// For the case when a cubic bezier is actually a line. We set K=0, L=1, M=-line, which results in 787cc26127920069cbd83e92cca3c69bb56cb165bcccsmartdalton// the following implicit: 788cc26127920069cbd83e92cca3c69bb56cb165bcccsmartdalton// 789cc26127920069cbd83e92cca3c69bb56cb165bcccsmartdalton// k^3 - l*m == 0^3 - 1*(-line) == -(-line) == line 790cc26127920069cbd83e92cca3c69bb56cb165bcccsmartdalton// 791cc26127920069cbd83e92cca3c69bb56cb165bcccsmartdaltonstatic void calc_line_klm(const SkPoint pts[4], SkMatrix* klm) { 792cc26127920069cbd83e92cca3c69bb56cb165bcccsmartdalton SkScalar ny = pts[0].x() - pts[3].x(); 793cc26127920069cbd83e92cca3c69bb56cb165bcccsmartdalton SkScalar nx = pts[3].y() - pts[0].y(); 794cc26127920069cbd83e92cca3c69bb56cb165bcccsmartdalton SkScalar k = nx * pts[0].x() + ny * pts[0].y(); 795cc26127920069cbd83e92cca3c69bb56cb165bcccsmartdalton klm->setAll( 0, 0, 0, 796cc26127920069cbd83e92cca3c69bb56cb165bcccsmartdalton 0, 0, 1, 797cc26127920069cbd83e92cca3c69bb56cb165bcccsmartdalton -nx, -ny, k); 798cc26127920069cbd83e92cca3c69bb56cb165bcccsmartdalton} 799cc26127920069cbd83e92cca3c69bb56cb165bcccsmartdalton 800390f6cd6f9f9ddd8a53da804cee3eff60cd2e2b4Chris DaltonSkCubicType GrPathUtils::getCubicKLM(const SkPoint src[4], SkMatrix* klm, double t[2], 801390f6cd6f9f9ddd8a53da804cee3eff60cd2e2b4Chris Dalton double s[2]) { 802390f6cd6f9f9ddd8a53da804cee3eff60cd2e2b4Chris Dalton double d[4]; 803febbffad1c24136f041d7fc2d5ffcd50e47a047fChris Dalton SkCubicType type = SkClassifyCubic(src, t, s, d); 804390f6cd6f9f9ddd8a53da804cee3eff60cd2e2b4Chris Dalton 805390f6cd6f9f9ddd8a53da804cee3eff60cd2e2b4Chris Dalton const SkScalar tt[2] = {static_cast<SkScalar>(t[0]), static_cast<SkScalar>(t[1])}; 806390f6cd6f9f9ddd8a53da804cee3eff60cd2e2b4Chris Dalton const SkScalar ss[2] = {static_cast<SkScalar>(s[0]), static_cast<SkScalar>(s[1])}; 807390f6cd6f9f9ddd8a53da804cee3eff60cd2e2b4Chris Dalton 808febbffad1c24136f041d7fc2d5ffcd50e47a047fChris Dalton switch (type) { 809febbffad1c24136f041d7fc2d5ffcd50e47a047fChris Dalton case SkCubicType::kSerpentine: 810390f6cd6f9f9ddd8a53da804cee3eff60cd2e2b4Chris Dalton calc_serp_klm(src, tt[0], ss[0], tt[1], ss[1], klm); 811febbffad1c24136f041d7fc2d5ffcd50e47a047fChris Dalton break; 812febbffad1c24136f041d7fc2d5ffcd50e47a047fChris Dalton case SkCubicType::kLoop: 813390f6cd6f9f9ddd8a53da804cee3eff60cd2e2b4Chris Dalton calc_loop_klm(src, tt[0], ss[0], tt[1], ss[1], klm); 814febbffad1c24136f041d7fc2d5ffcd50e47a047fChris Dalton break; 815febbffad1c24136f041d7fc2d5ffcd50e47a047fChris Dalton case SkCubicType::kLocalCusp: 816390f6cd6f9f9ddd8a53da804cee3eff60cd2e2b4Chris Dalton calc_serp_klm(src, tt[0], ss[0], tt[1], ss[1], klm); 817febbffad1c24136f041d7fc2d5ffcd50e47a047fChris Dalton break; 818febbffad1c24136f041d7fc2d5ffcd50e47a047fChris Dalton case SkCubicType::kCuspAtInfinity: 819390f6cd6f9f9ddd8a53da804cee3eff60cd2e2b4Chris Dalton calc_inf_cusp_klm(src, tt[0], ss[0], klm); 820febbffad1c24136f041d7fc2d5ffcd50e47a047fChris Dalton break; 821febbffad1c24136f041d7fc2d5ffcd50e47a047fChris Dalton case SkCubicType::kQuadratic: 822febbffad1c24136f041d7fc2d5ffcd50e47a047fChris Dalton calc_quadratic_klm(src, d[3], klm); 823febbffad1c24136f041d7fc2d5ffcd50e47a047fChris Dalton break; 824febbffad1c24136f041d7fc2d5ffcd50e47a047fChris Dalton case SkCubicType::kLineOrPoint: 825febbffad1c24136f041d7fc2d5ffcd50e47a047fChris Dalton calc_line_klm(src, klm); 826febbffad1c24136f041d7fc2d5ffcd50e47a047fChris Dalton break; 827febbffad1c24136f041d7fc2d5ffcd50e47a047fChris Dalton } 828febbffad1c24136f041d7fc2d5ffcd50e47a047fChris Dalton 829febbffad1c24136f041d7fc2d5ffcd50e47a047fChris Dalton return type; 830febbffad1c24136f041d7fc2d5ffcd50e47a047fChris Dalton} 831febbffad1c24136f041d7fc2d5ffcd50e47a047fChris Dalton 832cc26127920069cbd83e92cca3c69bb56cb165bcccsmartdaltonint GrPathUtils::chopCubicAtLoopIntersection(const SkPoint src[4], SkPoint dst[10], SkMatrix* klm, 8338199d94c0812a05320064f5f864b4208ffb25dbaGreg Daniel int* loopIndex) { 834febbffad1c24136f041d7fc2d5ffcd50e47a047fChris Dalton SkSTArray<2, SkScalar> chops; 835febbffad1c24136f041d7fc2d5ffcd50e47a047fChris Dalton *loopIndex = -1; 836858638d8a5bef8f9940ccec2346a9bcc5f804979commit-bot@chromium.org 837390f6cd6f9f9ddd8a53da804cee3eff60cd2e2b4Chris Dalton double t[2], s[2]; 838febbffad1c24136f041d7fc2d5ffcd50e47a047fChris Dalton if (SkCubicType::kLoop == GrPathUtils::getCubicKLM(src, klm, t, s)) { 839390f6cd6f9f9ddd8a53da804cee3eff60cd2e2b4Chris Dalton SkScalar t0 = static_cast<SkScalar>(t[0] / s[0]); 840390f6cd6f9f9ddd8a53da804cee3eff60cd2e2b4Chris Dalton SkScalar t1 = static_cast<SkScalar>(t[1] / s[1]); 841390f6cd6f9f9ddd8a53da804cee3eff60cd2e2b4Chris Dalton SkASSERT(t0 <= t1); // Technically t0 != t1 in a loop, but there may be FP error. 842858638d8a5bef8f9940ccec2346a9bcc5f804979commit-bot@chromium.org 843390f6cd6f9f9ddd8a53da804cee3eff60cd2e2b4Chris Dalton if (t0 < 1 && t1 > 0) { 844b58194a90ee788f0da8daffcc444ea74237f4b79Chris Dalton *loopIndex = 0; 845390f6cd6f9f9ddd8a53da804cee3eff60cd2e2b4Chris Dalton if (t0 > 0) { 846390f6cd6f9f9ddd8a53da804cee3eff60cd2e2b4Chris Dalton chops.push_back(t0); 847b58194a90ee788f0da8daffcc444ea74237f4b79Chris Dalton *loopIndex = 1; 848b58194a90ee788f0da8daffcc444ea74237f4b79Chris Dalton } 849390f6cd6f9f9ddd8a53da804cee3eff60cd2e2b4Chris Dalton if (t1 < 1) { 850390f6cd6f9f9ddd8a53da804cee3eff60cd2e2b4Chris Dalton chops.push_back(t1); 851b58194a90ee788f0da8daffcc444ea74237f4b79Chris Dalton *loopIndex = chops.count() - 1; 852b58194a90ee788f0da8daffcc444ea74237f4b79Chris Dalton } 853858638d8a5bef8f9940ccec2346a9bcc5f804979commit-bot@chromium.org } 8548199d94c0812a05320064f5f864b4208ffb25dbaGreg Daniel } 855858638d8a5bef8f9940ccec2346a9bcc5f804979commit-bot@chromium.org 856febbffad1c24136f041d7fc2d5ffcd50e47a047fChris Dalton SkChopCubicAt(src, dst, chops.begin(), chops.count()); 857febbffad1c24136f041d7fc2d5ffcd50e47a047fChris Dalton return chops.count() + 1; 858858638d8a5bef8f9940ccec2346a9bcc5f804979commit-bot@chromium.org} 859