1818b0cc1b8b0c4acc565e8e2cb8b0b61aa5a300ecaryclark@google.com/* 2818b0cc1b8b0c4acc565e8e2cb8b0b61aa5a300ecaryclark@google.com * Copyright 2012 Google Inc. 3818b0cc1b8b0c4acc565e8e2cb8b0b61aa5a300ecaryclark@google.com * 4818b0cc1b8b0c4acc565e8e2cb8b0b61aa5a300ecaryclark@google.com * Use of this source code is governed by a BSD-style license that can be 5818b0cc1b8b0c4acc565e8e2cb8b0b61aa5a300ecaryclark@google.com * found in the LICENSE file. 6818b0cc1b8b0c4acc565e8e2cb8b0b61aa5a300ecaryclark@google.com */ 7818b0cc1b8b0c4acc565e8e2cb8b0b61aa5a300ecaryclark@google.com#include "PathOpsTestCommon.h" 88d0a524a4847bc7e1cc63a93b78922739466c201caryclark@google.com#include "SkPathOpsBounds.h" 9818b0cc1b8b0c4acc565e8e2cb8b0b61aa5a300ecaryclark@google.com#include "SkPathOpsCubic.h" 108d0a524a4847bc7e1cc63a93b78922739466c201caryclark@google.com#include "SkPathOpsLine.h" 118d0a524a4847bc7e1cc63a93b78922739466c201caryclark@google.com#include "SkPathOpsQuad.h" 128d0a524a4847bc7e1cc63a93b78922739466c201caryclark@google.com#include "SkPathOpsTriangle.h" 13818b0cc1b8b0c4acc565e8e2cb8b0b61aa5a300ecaryclark@google.com 14d892bd8ba676d34d4ce4a73ac7aad88e102fad70caryclark@google.comvoid CubicToQuads(const SkDCubic& cubic, double precision, SkTArray<SkDQuad, true>& quads) { 15d892bd8ba676d34d4ce4a73ac7aad88e102fad70caryclark@google.com SkTArray<double, true> ts; 16818b0cc1b8b0c4acc565e8e2cb8b0b61aa5a300ecaryclark@google.com cubic.toQuadraticTs(precision, &ts); 17cffbcc3b9665f2c928544b6fc6b8a0e22a4210fbcaryclark@google.com if (ts.count() <= 0) { 18818b0cc1b8b0c4acc565e8e2cb8b0b61aa5a300ecaryclark@google.com SkDQuad quad = cubic.toQuad(); 19d892bd8ba676d34d4ce4a73ac7aad88e102fad70caryclark@google.com quads.push_back(quad); 20818b0cc1b8b0c4acc565e8e2cb8b0b61aa5a300ecaryclark@google.com return; 21818b0cc1b8b0c4acc565e8e2cb8b0b61aa5a300ecaryclark@google.com } 22818b0cc1b8b0c4acc565e8e2cb8b0b61aa5a300ecaryclark@google.com double tStart = 0; 23818b0cc1b8b0c4acc565e8e2cb8b0b61aa5a300ecaryclark@google.com for (int i1 = 0; i1 <= ts.count(); ++i1) { 24818b0cc1b8b0c4acc565e8e2cb8b0b61aa5a300ecaryclark@google.com const double tEnd = i1 < ts.count() ? ts[i1] : 1; 25818b0cc1b8b0c4acc565e8e2cb8b0b61aa5a300ecaryclark@google.com SkDCubic part = cubic.subDivide(tStart, tEnd); 26818b0cc1b8b0c4acc565e8e2cb8b0b61aa5a300ecaryclark@google.com SkDQuad quad = part.toQuad(); 27d892bd8ba676d34d4ce4a73ac7aad88e102fad70caryclark@google.com quads.push_back(quad); 28818b0cc1b8b0c4acc565e8e2cb8b0b61aa5a300ecaryclark@google.com tStart = tEnd; 29818b0cc1b8b0c4acc565e8e2cb8b0b61aa5a300ecaryclark@google.com } 30818b0cc1b8b0c4acc565e8e2cb8b0b61aa5a300ecaryclark@google.com} 318d0a524a4847bc7e1cc63a93b78922739466c201caryclark@google.com 32e4097e3a0b10bb0047a45b6949ca01826f0807a7caryclarkvoid CubicPathToQuads(const SkPath& cubicPath, SkPath* quadPath) { 33e4097e3a0b10bb0047a45b6949ca01826f0807a7caryclark quadPath->reset(); 34e4097e3a0b10bb0047a45b6949ca01826f0807a7caryclark SkDCubic cubic; 35e4097e3a0b10bb0047a45b6949ca01826f0807a7caryclark SkTArray<SkDQuad, true> quads; 36e4097e3a0b10bb0047a45b6949ca01826f0807a7caryclark SkPath::RawIter iter(cubicPath); 37e4097e3a0b10bb0047a45b6949ca01826f0807a7caryclark uint8_t verb; 38e4097e3a0b10bb0047a45b6949ca01826f0807a7caryclark SkPoint pts[4]; 39e4097e3a0b10bb0047a45b6949ca01826f0807a7caryclark while ((verb = iter.next(pts)) != SkPath::kDone_Verb) { 40e4097e3a0b10bb0047a45b6949ca01826f0807a7caryclark switch (verb) { 41e4097e3a0b10bb0047a45b6949ca01826f0807a7caryclark case SkPath::kMove_Verb: 42e4097e3a0b10bb0047a45b6949ca01826f0807a7caryclark quadPath->moveTo(pts[0].fX, pts[0].fY); 43e4097e3a0b10bb0047a45b6949ca01826f0807a7caryclark continue; 44e4097e3a0b10bb0047a45b6949ca01826f0807a7caryclark case SkPath::kLine_Verb: 45e4097e3a0b10bb0047a45b6949ca01826f0807a7caryclark quadPath->lineTo(pts[1].fX, pts[1].fY); 46e4097e3a0b10bb0047a45b6949ca01826f0807a7caryclark break; 47e4097e3a0b10bb0047a45b6949ca01826f0807a7caryclark case SkPath::kQuad_Verb: 48e4097e3a0b10bb0047a45b6949ca01826f0807a7caryclark quadPath->quadTo(pts[1].fX, pts[1].fY, pts[2].fX, pts[2].fY); 49e4097e3a0b10bb0047a45b6949ca01826f0807a7caryclark break; 50e4097e3a0b10bb0047a45b6949ca01826f0807a7caryclark case SkPath::kCubic_Verb: 51e4097e3a0b10bb0047a45b6949ca01826f0807a7caryclark quads.reset(); 52e4097e3a0b10bb0047a45b6949ca01826f0807a7caryclark cubic.set(pts); 53e4097e3a0b10bb0047a45b6949ca01826f0807a7caryclark CubicToQuads(cubic, cubic.calcPrecision(), quads); 54e4097e3a0b10bb0047a45b6949ca01826f0807a7caryclark for (int index = 0; index < quads.count(); ++index) { 55e4097e3a0b10bb0047a45b6949ca01826f0807a7caryclark SkPoint qPts[2] = { 56e4097e3a0b10bb0047a45b6949ca01826f0807a7caryclark quads[index][1].asSkPoint(), 57e4097e3a0b10bb0047a45b6949ca01826f0807a7caryclark quads[index][2].asSkPoint() 58e4097e3a0b10bb0047a45b6949ca01826f0807a7caryclark }; 59e4097e3a0b10bb0047a45b6949ca01826f0807a7caryclark quadPath->quadTo(qPts[0].fX, qPts[0].fY, qPts[1].fX, qPts[1].fY); 60e4097e3a0b10bb0047a45b6949ca01826f0807a7caryclark } 61e4097e3a0b10bb0047a45b6949ca01826f0807a7caryclark break; 62e4097e3a0b10bb0047a45b6949ca01826f0807a7caryclark case SkPath::kClose_Verb: 63e4097e3a0b10bb0047a45b6949ca01826f0807a7caryclark quadPath->close(); 64e4097e3a0b10bb0047a45b6949ca01826f0807a7caryclark break; 65e4097e3a0b10bb0047a45b6949ca01826f0807a7caryclark default: 66e4097e3a0b10bb0047a45b6949ca01826f0807a7caryclark SkDEBUGFAIL("bad verb"); 67e4097e3a0b10bb0047a45b6949ca01826f0807a7caryclark return; 68e4097e3a0b10bb0047a45b6949ca01826f0807a7caryclark } 69e4097e3a0b10bb0047a45b6949ca01826f0807a7caryclark } 70e4097e3a0b10bb0047a45b6949ca01826f0807a7caryclark} 71e4097e3a0b10bb0047a45b6949ca01826f0807a7caryclark 72e4097e3a0b10bb0047a45b6949ca01826f0807a7caryclarkvoid CubicPathToSimple(const SkPath& cubicPath, SkPath* simplePath) { 73e4097e3a0b10bb0047a45b6949ca01826f0807a7caryclark simplePath->reset(); 74e4097e3a0b10bb0047a45b6949ca01826f0807a7caryclark SkDCubic cubic; 75e4097e3a0b10bb0047a45b6949ca01826f0807a7caryclark SkPath::RawIter iter(cubicPath); 76e4097e3a0b10bb0047a45b6949ca01826f0807a7caryclark uint8_t verb; 77e4097e3a0b10bb0047a45b6949ca01826f0807a7caryclark SkPoint pts[4]; 78e4097e3a0b10bb0047a45b6949ca01826f0807a7caryclark while ((verb = iter.next(pts)) != SkPath::kDone_Verb) { 79e4097e3a0b10bb0047a45b6949ca01826f0807a7caryclark switch (verb) { 80e4097e3a0b10bb0047a45b6949ca01826f0807a7caryclark case SkPath::kMove_Verb: 81e4097e3a0b10bb0047a45b6949ca01826f0807a7caryclark simplePath->moveTo(pts[0].fX, pts[0].fY); 82e4097e3a0b10bb0047a45b6949ca01826f0807a7caryclark continue; 83e4097e3a0b10bb0047a45b6949ca01826f0807a7caryclark case SkPath::kLine_Verb: 84e4097e3a0b10bb0047a45b6949ca01826f0807a7caryclark simplePath->lineTo(pts[1].fX, pts[1].fY); 85e4097e3a0b10bb0047a45b6949ca01826f0807a7caryclark break; 86e4097e3a0b10bb0047a45b6949ca01826f0807a7caryclark case SkPath::kQuad_Verb: 87e4097e3a0b10bb0047a45b6949ca01826f0807a7caryclark simplePath->quadTo(pts[1].fX, pts[1].fY, pts[2].fX, pts[2].fY); 88e4097e3a0b10bb0047a45b6949ca01826f0807a7caryclark break; 89e4097e3a0b10bb0047a45b6949ca01826f0807a7caryclark case SkPath::kCubic_Verb: { 90e4097e3a0b10bb0047a45b6949ca01826f0807a7caryclark cubic.set(pts); 91e4097e3a0b10bb0047a45b6949ca01826f0807a7caryclark double tInflects[2]; 92e4097e3a0b10bb0047a45b6949ca01826f0807a7caryclark int inflections = cubic.findInflections(tInflects); 93e4097e3a0b10bb0047a45b6949ca01826f0807a7caryclark if (inflections > 1 && tInflects[0] > tInflects[1]) { 94e4097e3a0b10bb0047a45b6949ca01826f0807a7caryclark SkTSwap(tInflects[0], tInflects[1]); 95e4097e3a0b10bb0047a45b6949ca01826f0807a7caryclark } 96e4097e3a0b10bb0047a45b6949ca01826f0807a7caryclark double lo = 0; 97e4097e3a0b10bb0047a45b6949ca01826f0807a7caryclark for (int index = 0; index <= inflections; ++index) { 98e4097e3a0b10bb0047a45b6949ca01826f0807a7caryclark double hi = index < inflections ? tInflects[index] : 1; 99e4097e3a0b10bb0047a45b6949ca01826f0807a7caryclark SkDCubic part = cubic.subDivide(lo, hi); 100e4097e3a0b10bb0047a45b6949ca01826f0807a7caryclark SkPoint cPts[3]; 101e4097e3a0b10bb0047a45b6949ca01826f0807a7caryclark cPts[0] = part[1].asSkPoint(); 102e4097e3a0b10bb0047a45b6949ca01826f0807a7caryclark cPts[1] = part[2].asSkPoint(); 103e4097e3a0b10bb0047a45b6949ca01826f0807a7caryclark cPts[2] = part[3].asSkPoint(); 104e4097e3a0b10bb0047a45b6949ca01826f0807a7caryclark simplePath->cubicTo(cPts[0].fX, cPts[0].fY, cPts[1].fX, cPts[1].fY, 105e4097e3a0b10bb0047a45b6949ca01826f0807a7caryclark cPts[2].fX, cPts[2].fY); 106e4097e3a0b10bb0047a45b6949ca01826f0807a7caryclark lo = hi; 107e4097e3a0b10bb0047a45b6949ca01826f0807a7caryclark } 108e4097e3a0b10bb0047a45b6949ca01826f0807a7caryclark break; 109e4097e3a0b10bb0047a45b6949ca01826f0807a7caryclark } 110e4097e3a0b10bb0047a45b6949ca01826f0807a7caryclark case SkPath::kClose_Verb: 111e4097e3a0b10bb0047a45b6949ca01826f0807a7caryclark simplePath->close(); 112e4097e3a0b10bb0047a45b6949ca01826f0807a7caryclark break; 113e4097e3a0b10bb0047a45b6949ca01826f0807a7caryclark default: 114e4097e3a0b10bb0047a45b6949ca01826f0807a7caryclark SkDEBUGFAIL("bad verb"); 115e4097e3a0b10bb0047a45b6949ca01826f0807a7caryclark return; 116e4097e3a0b10bb0047a45b6949ca01826f0807a7caryclark } 117e4097e3a0b10bb0047a45b6949ca01826f0807a7caryclark } 118e4097e3a0b10bb0047a45b6949ca01826f0807a7caryclark} 119e4097e3a0b10bb0047a45b6949ca01826f0807a7caryclark 1208d0a524a4847bc7e1cc63a93b78922739466c201caryclark@google.comstatic bool SkDoubleIsNaN(double x) { 1218d0a524a4847bc7e1cc63a93b78922739466c201caryclark@google.com return x != x; 1228d0a524a4847bc7e1cc63a93b78922739466c201caryclark@google.com} 1238d0a524a4847bc7e1cc63a93b78922739466c201caryclark@google.com 1248d0a524a4847bc7e1cc63a93b78922739466c201caryclark@google.combool ValidBounds(const SkPathOpsBounds& bounds) { 1258d0a524a4847bc7e1cc63a93b78922739466c201caryclark@google.com if (SkScalarIsNaN(bounds.fLeft)) { 1268d0a524a4847bc7e1cc63a93b78922739466c201caryclark@google.com return false; 1278d0a524a4847bc7e1cc63a93b78922739466c201caryclark@google.com } 1288d0a524a4847bc7e1cc63a93b78922739466c201caryclark@google.com if (SkScalarIsNaN(bounds.fTop)) { 1298d0a524a4847bc7e1cc63a93b78922739466c201caryclark@google.com return false; 1308d0a524a4847bc7e1cc63a93b78922739466c201caryclark@google.com } 1318d0a524a4847bc7e1cc63a93b78922739466c201caryclark@google.com if (SkScalarIsNaN(bounds.fRight)) { 1328d0a524a4847bc7e1cc63a93b78922739466c201caryclark@google.com return false; 1338d0a524a4847bc7e1cc63a93b78922739466c201caryclark@google.com } 1348d0a524a4847bc7e1cc63a93b78922739466c201caryclark@google.com return !SkScalarIsNaN(bounds.fBottom); 1358d0a524a4847bc7e1cc63a93b78922739466c201caryclark@google.com} 1368d0a524a4847bc7e1cc63a93b78922739466c201caryclark@google.com 1378d0a524a4847bc7e1cc63a93b78922739466c201caryclark@google.combool ValidCubic(const SkDCubic& cubic) { 1388d0a524a4847bc7e1cc63a93b78922739466c201caryclark@google.com for (int index = 0; index < 4; ++index) { 1398d0a524a4847bc7e1cc63a93b78922739466c201caryclark@google.com if (!ValidPoint(cubic[index])) { 1408d0a524a4847bc7e1cc63a93b78922739466c201caryclark@google.com return false; 1418d0a524a4847bc7e1cc63a93b78922739466c201caryclark@google.com } 1428d0a524a4847bc7e1cc63a93b78922739466c201caryclark@google.com } 1438d0a524a4847bc7e1cc63a93b78922739466c201caryclark@google.com return true; 1448d0a524a4847bc7e1cc63a93b78922739466c201caryclark@google.com} 1458d0a524a4847bc7e1cc63a93b78922739466c201caryclark@google.com 1468d0a524a4847bc7e1cc63a93b78922739466c201caryclark@google.combool ValidLine(const SkDLine& line) { 1478d0a524a4847bc7e1cc63a93b78922739466c201caryclark@google.com for (int index = 0; index < 2; ++index) { 1488d0a524a4847bc7e1cc63a93b78922739466c201caryclark@google.com if (!ValidPoint(line[index])) { 1498d0a524a4847bc7e1cc63a93b78922739466c201caryclark@google.com return false; 1508d0a524a4847bc7e1cc63a93b78922739466c201caryclark@google.com } 1518d0a524a4847bc7e1cc63a93b78922739466c201caryclark@google.com } 1528d0a524a4847bc7e1cc63a93b78922739466c201caryclark@google.com return true; 1538d0a524a4847bc7e1cc63a93b78922739466c201caryclark@google.com} 1548d0a524a4847bc7e1cc63a93b78922739466c201caryclark@google.com 1558d0a524a4847bc7e1cc63a93b78922739466c201caryclark@google.combool ValidPoint(const SkDPoint& pt) { 1568d0a524a4847bc7e1cc63a93b78922739466c201caryclark@google.com if (SkDoubleIsNaN(pt.fX)) { 1578d0a524a4847bc7e1cc63a93b78922739466c201caryclark@google.com return false; 1588d0a524a4847bc7e1cc63a93b78922739466c201caryclark@google.com } 159eebe6f4a59c9ff99df3c8f0de37192e080ae7f94skia.committer@gmail.com return !SkDoubleIsNaN(pt.fY); 1608d0a524a4847bc7e1cc63a93b78922739466c201caryclark@google.com} 1618d0a524a4847bc7e1cc63a93b78922739466c201caryclark@google.com 1628d0a524a4847bc7e1cc63a93b78922739466c201caryclark@google.combool ValidPoints(const SkPoint* pts, int count) { 1638d0a524a4847bc7e1cc63a93b78922739466c201caryclark@google.com for (int index = 0; index < count; ++index) { 1648d0a524a4847bc7e1cc63a93b78922739466c201caryclark@google.com if (SkScalarIsNaN(pts[index].fX)) { 1658d0a524a4847bc7e1cc63a93b78922739466c201caryclark@google.com return false; 1668d0a524a4847bc7e1cc63a93b78922739466c201caryclark@google.com } 1678d0a524a4847bc7e1cc63a93b78922739466c201caryclark@google.com if (SkScalarIsNaN(pts[index].fY)) { 1688d0a524a4847bc7e1cc63a93b78922739466c201caryclark@google.com return false; 1698d0a524a4847bc7e1cc63a93b78922739466c201caryclark@google.com } 1708d0a524a4847bc7e1cc63a93b78922739466c201caryclark@google.com } 1718d0a524a4847bc7e1cc63a93b78922739466c201caryclark@google.com return true; 1728d0a524a4847bc7e1cc63a93b78922739466c201caryclark@google.com} 1738d0a524a4847bc7e1cc63a93b78922739466c201caryclark@google.com 1748d0a524a4847bc7e1cc63a93b78922739466c201caryclark@google.combool ValidQuad(const SkDQuad& quad) { 1758d0a524a4847bc7e1cc63a93b78922739466c201caryclark@google.com for (int index = 0; index < 3; ++index) { 1768d0a524a4847bc7e1cc63a93b78922739466c201caryclark@google.com if (!ValidPoint(quad[index])) { 1778d0a524a4847bc7e1cc63a93b78922739466c201caryclark@google.com return false; 1788d0a524a4847bc7e1cc63a93b78922739466c201caryclark@google.com } 1798d0a524a4847bc7e1cc63a93b78922739466c201caryclark@google.com } 1808d0a524a4847bc7e1cc63a93b78922739466c201caryclark@google.com return true; 1818d0a524a4847bc7e1cc63a93b78922739466c201caryclark@google.com} 1828d0a524a4847bc7e1cc63a93b78922739466c201caryclark@google.com 1838d0a524a4847bc7e1cc63a93b78922739466c201caryclark@google.combool ValidTriangle(const SkDTriangle& triangle) { 1848d0a524a4847bc7e1cc63a93b78922739466c201caryclark@google.com for (int index = 0; index < 3; ++index) { 1858d0a524a4847bc7e1cc63a93b78922739466c201caryclark@google.com if (!ValidPoint(triangle.fPts[index])) { 1868d0a524a4847bc7e1cc63a93b78922739466c201caryclark@google.com return false; 1878d0a524a4847bc7e1cc63a93b78922739466c201caryclark@google.com } 1888d0a524a4847bc7e1cc63a93b78922739466c201caryclark@google.com } 1898d0a524a4847bc7e1cc63a93b78922739466c201caryclark@google.com return true; 1908d0a524a4847bc7e1cc63a93b78922739466c201caryclark@google.com} 1918d0a524a4847bc7e1cc63a93b78922739466c201caryclark@google.com 1928d0a524a4847bc7e1cc63a93b78922739466c201caryclark@google.combool ValidVector(const SkDVector& v) { 1938d0a524a4847bc7e1cc63a93b78922739466c201caryclark@google.com if (SkDoubleIsNaN(v.fX)) { 1948d0a524a4847bc7e1cc63a93b78922739466c201caryclark@google.com return false; 1958d0a524a4847bc7e1cc63a93b78922739466c201caryclark@google.com } 196eebe6f4a59c9ff99df3c8f0de37192e080ae7f94skia.committer@gmail.com return !SkDoubleIsNaN(v.fY); 1978d0a524a4847bc7e1cc63a93b78922739466c201caryclark@google.com} 198