123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331 |
- /*
- * Copyright 2012 Google Inc.
- *
- * Use of this source code is governed by a BSD-style license that can be
- * found in the LICENSE file.
- */
- #include "src/core/SkTSort.h"
- #include "src/pathops/SkPathOpsBounds.h"
- #include "src/pathops/SkPathOpsConic.h"
- #include "src/pathops/SkPathOpsCubic.h"
- #include "src/pathops/SkPathOpsLine.h"
- #include "src/pathops/SkPathOpsQuad.h"
- #include "src/pathops/SkPathOpsTSect.h"
- #include "src/pathops/SkReduceOrder.h"
- #include "tests/PathOpsTestCommon.h"
- #include <utility>
- static double calc_t_div(const SkDCubic& cubic, double precision, double start) {
- const double adjust = sqrt(3.) / 36;
- SkDCubic sub;
- const SkDCubic* cPtr;
- if (start == 0) {
- cPtr = &cubic;
- } else {
- // OPTIMIZE: special-case half-split ?
- sub = cubic.subDivide(start, 1);
- cPtr = ⊂
- }
- const SkDCubic& c = *cPtr;
- double dx = c[3].fX - 3 * (c[2].fX - c[1].fX) - c[0].fX;
- double dy = c[3].fY - 3 * (c[2].fY - c[1].fY) - c[0].fY;
- double dist = sqrt(dx * dx + dy * dy);
- double tDiv3 = precision / (adjust * dist);
- double t = SkDCubeRoot(tDiv3);
- if (start > 0) {
- t = start + (1 - start) * t;
- }
- return t;
- }
- static bool add_simple_ts(const SkDCubic& cubic, double precision, SkTArray<double, true>* ts) {
- double tDiv = calc_t_div(cubic, precision, 0);
- if (tDiv >= 1) {
- return true;
- }
- if (tDiv >= 0.5) {
- ts->push_back(0.5);
- return true;
- }
- return false;
- }
- static void addTs(const SkDCubic& cubic, double precision, double start, double end,
- SkTArray<double, true>* ts) {
- double tDiv = calc_t_div(cubic, precision, 0);
- double parts = ceil(1.0 / tDiv);
- for (double index = 0; index < parts; ++index) {
- double newT = start + (index / parts) * (end - start);
- if (newT > 0 && newT < 1) {
- ts->push_back(newT);
- }
- }
- }
- static void toQuadraticTs(const SkDCubic* cubic, double precision, SkTArray<double, true>* ts) {
- SkReduceOrder reducer;
- int order = reducer.reduce(*cubic, SkReduceOrder::kAllow_Quadratics);
- if (order < 3) {
- return;
- }
- double inflectT[5];
- int inflections = cubic->findInflections(inflectT);
- SkASSERT(inflections <= 2);
- if (!cubic->endsAreExtremaInXOrY()) {
- inflections += cubic->findMaxCurvature(&inflectT[inflections]);
- SkASSERT(inflections <= 5);
- }
- SkTQSort<double>(inflectT, &inflectT[inflections - 1]);
- // OPTIMIZATION: is this filtering common enough that it needs to be pulled out into its
- // own subroutine?
- while (inflections && approximately_less_than_zero(inflectT[0])) {
- memmove(inflectT, &inflectT[1], sizeof(inflectT[0]) * --inflections);
- }
- int start = 0;
- int next = 1;
- while (next < inflections) {
- if (!approximately_equal(inflectT[start], inflectT[next])) {
- ++start;
- ++next;
- continue;
- }
- memmove(&inflectT[start], &inflectT[next], sizeof(inflectT[0]) * (--inflections - start));
- }
- while (inflections && approximately_greater_than_one(inflectT[inflections - 1])) {
- --inflections;
- }
- SkDCubicPair pair;
- if (inflections == 1) {
- pair = cubic->chopAt(inflectT[0]);
- int orderP1 = reducer.reduce(pair.first(), SkReduceOrder::kNo_Quadratics);
- if (orderP1 < 2) {
- --inflections;
- } else {
- int orderP2 = reducer.reduce(pair.second(), SkReduceOrder::kNo_Quadratics);
- if (orderP2 < 2) {
- --inflections;
- }
- }
- }
- if (inflections == 0 && add_simple_ts(*cubic, precision, ts)) {
- return;
- }
- if (inflections == 1) {
- pair = cubic->chopAt(inflectT[0]);
- addTs(pair.first(), precision, 0, inflectT[0], ts);
- addTs(pair.second(), precision, inflectT[0], 1, ts);
- return;
- }
- if (inflections > 1) {
- SkDCubic part = cubic->subDivide(0, inflectT[0]);
- addTs(part, precision, 0, inflectT[0], ts);
- int last = inflections - 1;
- for (int idx = 0; idx < last; ++idx) {
- part = cubic->subDivide(inflectT[idx], inflectT[idx + 1]);
- addTs(part, precision, inflectT[idx], inflectT[idx + 1], ts);
- }
- part = cubic->subDivide(inflectT[last], 1);
- addTs(part, precision, inflectT[last], 1, ts);
- return;
- }
- addTs(*cubic, precision, 0, 1, ts);
- }
- void CubicToQuads(const SkDCubic& cubic, double precision, SkTArray<SkDQuad, true>& quads) {
- SkTArray<double, true> ts;
- toQuadraticTs(&cubic, precision, &ts);
- if (ts.count() <= 0) {
- SkDQuad quad = cubic.toQuad();
- quads.push_back(quad);
- return;
- }
- double tStart = 0;
- for (int i1 = 0; i1 <= ts.count(); ++i1) {
- const double tEnd = i1 < ts.count() ? ts[i1] : 1;
- SkDRect bounds;
- bounds.setBounds(cubic);
- SkDCubic part = cubic.subDivide(tStart, tEnd);
- SkDQuad quad = part.toQuad();
- if (quad[1].fX < bounds.fLeft) {
- quad[1].fX = bounds.fLeft;
- } else if (quad[1].fX > bounds.fRight) {
- quad[1].fX = bounds.fRight;
- }
- if (quad[1].fY < bounds.fTop) {
- quad[1].fY = bounds.fTop;
- } else if (quad[1].fY > bounds.fBottom) {
- quad[1].fY = bounds.fBottom;
- }
- quads.push_back(quad);
- tStart = tEnd;
- }
- }
- void CubicPathToQuads(const SkPath& cubicPath, SkPath* quadPath) {
- quadPath->reset();
- SkDCubic cubic;
- SkTArray<SkDQuad, true> quads;
- SkPath::RawIter iter(cubicPath);
- uint8_t verb;
- SkPoint pts[4];
- while ((verb = iter.next(pts)) != SkPath::kDone_Verb) {
- switch (verb) {
- case SkPath::kMove_Verb:
- quadPath->moveTo(pts[0].fX, pts[0].fY);
- continue;
- case SkPath::kLine_Verb:
- quadPath->lineTo(pts[1].fX, pts[1].fY);
- break;
- case SkPath::kQuad_Verb:
- quadPath->quadTo(pts[1].fX, pts[1].fY, pts[2].fX, pts[2].fY);
- break;
- case SkPath::kCubic_Verb:
- quads.reset();
- cubic.set(pts);
- CubicToQuads(cubic, cubic.calcPrecision(), quads);
- for (int index = 0; index < quads.count(); ++index) {
- SkPoint qPts[2] = {
- quads[index][1].asSkPoint(),
- quads[index][2].asSkPoint()
- };
- quadPath->quadTo(qPts[0].fX, qPts[0].fY, qPts[1].fX, qPts[1].fY);
- }
- break;
- case SkPath::kClose_Verb:
- quadPath->close();
- break;
- default:
- SkDEBUGFAIL("bad verb");
- return;
- }
- }
- }
- void CubicPathToSimple(const SkPath& cubicPath, SkPath* simplePath) {
- simplePath->reset();
- SkDCubic cubic;
- SkPath::RawIter iter(cubicPath);
- uint8_t verb;
- SkPoint pts[4];
- while ((verb = iter.next(pts)) != SkPath::kDone_Verb) {
- switch (verb) {
- case SkPath::kMove_Verb:
- simplePath->moveTo(pts[0].fX, pts[0].fY);
- continue;
- case SkPath::kLine_Verb:
- simplePath->lineTo(pts[1].fX, pts[1].fY);
- break;
- case SkPath::kQuad_Verb:
- simplePath->quadTo(pts[1].fX, pts[1].fY, pts[2].fX, pts[2].fY);
- break;
- case SkPath::kCubic_Verb: {
- cubic.set(pts);
- double tInflects[2];
- int inflections = cubic.findInflections(tInflects);
- if (inflections > 1 && tInflects[0] > tInflects[1]) {
- using std::swap;
- swap(tInflects[0], tInflects[1]);
- }
- double lo = 0;
- for (int index = 0; index <= inflections; ++index) {
- double hi = index < inflections ? tInflects[index] : 1;
- SkDCubic part = cubic.subDivide(lo, hi);
- SkPoint cPts[3];
- cPts[0] = part[1].asSkPoint();
- cPts[1] = part[2].asSkPoint();
- cPts[2] = part[3].asSkPoint();
- simplePath->cubicTo(cPts[0].fX, cPts[0].fY, cPts[1].fX, cPts[1].fY,
- cPts[2].fX, cPts[2].fY);
- lo = hi;
- }
- break;
- }
- case SkPath::kClose_Verb:
- simplePath->close();
- break;
- default:
- SkDEBUGFAIL("bad verb");
- return;
- }
- }
- }
- bool ValidBounds(const SkPathOpsBounds& bounds) {
- if (SkScalarIsNaN(bounds.fLeft)) {
- return false;
- }
- if (SkScalarIsNaN(bounds.fTop)) {
- return false;
- }
- if (SkScalarIsNaN(bounds.fRight)) {
- return false;
- }
- return !SkScalarIsNaN(bounds.fBottom);
- }
- bool ValidConic(const SkDConic& conic) {
- for (int index = 0; index < SkDConic::kPointCount; ++index) {
- if (!ValidPoint(conic[index])) {
- return false;
- }
- }
- if (SkDoubleIsNaN(conic.fWeight)) {
- return false;
- }
- return true;
- }
- bool ValidCubic(const SkDCubic& cubic) {
- for (int index = 0; index < 4; ++index) {
- if (!ValidPoint(cubic[index])) {
- return false;
- }
- }
- return true;
- }
- bool ValidLine(const SkDLine& line) {
- for (int index = 0; index < 2; ++index) {
- if (!ValidPoint(line[index])) {
- return false;
- }
- }
- return true;
- }
- bool ValidPoint(const SkDPoint& pt) {
- if (SkDoubleIsNaN(pt.fX)) {
- return false;
- }
- return !SkDoubleIsNaN(pt.fY);
- }
- bool ValidPoints(const SkPoint* pts, int count) {
- for (int index = 0; index < count; ++index) {
- if (SkScalarIsNaN(pts[index].fX)) {
- return false;
- }
- if (SkScalarIsNaN(pts[index].fY)) {
- return false;
- }
- }
- return true;
- }
- bool ValidQuad(const SkDQuad& quad) {
- for (int index = 0; index < 3; ++index) {
- if (!ValidPoint(quad[index])) {
- return false;
- }
- }
- return true;
- }
- bool ValidVector(const SkDVector& v) {
- if (SkDoubleIsNaN(v.fX)) {
- return false;
- }
- return !SkDoubleIsNaN(v.fY);
- }
|