| /* | |
| * 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/pathops/SkPathWriter.h" | |
| #include "include/core/SkTypes.h" | |
| #include "include/private/base/SkMath.h" | |
| #include "src/base/SkTSort.h" | |
| #include "src/core/SkPathPriv.h" | |
| #include "src/pathops/SkOpSegment.h" | |
| #include "src/pathops/SkOpSpan.h" | |
| #include "src/pathops/SkPathOpsDebug.h" | |
| #include "src/pathops/SkPathOpsTypes.h" | |
| using namespace skia_private; | |
| SkPathWriter::SkPathWriter(SkPathFillType ft) : fBuilder(ft) { | |
| init(); | |
| } | |
| void SkPathWriter::close() { | |
| if (fCurrent.isEmpty()) { | |
| return; | |
| } | |
| SkASSERT(this->isClosed()); | |
| #if DEBUG_PATH_CONSTRUCTION | |
| SkDebugf("path.close();\n"); | |
| #endif | |
| fCurrent.close(); | |
| if (auto raw = SkPathPriv::Raw(fCurrent, SkResolveConvexity::kNo)) { | |
| fBuilder.addRaw(*raw); | |
| } | |
| init(); | |
| } | |
| void SkPathWriter::conicTo(const SkPoint& pt1, const SkOpPtT* pt2, SkScalar weight) { | |
| SkPoint pt2pt = this->update(pt2); | |
| #if DEBUG_PATH_CONSTRUCTION | |
| SkDebugf("path.conicTo(%1.9g,%1.9g, %1.9g,%1.9g, %1.9g);\n", | |
| pt1.fX, pt1.fY, pt2pt.fX, pt2pt.fY, weight); | |
| #endif | |
| fCurrent.conicTo(pt1, pt2pt, weight); | |
| } | |
| void SkPathWriter::cubicTo(const SkPoint& pt1, const SkPoint& pt2, const SkOpPtT* pt3) { | |
| SkPoint pt3pt = this->update(pt3); | |
| #if DEBUG_PATH_CONSTRUCTION | |
| SkDebugf("path.cubicTo(%1.9g,%1.9g, %1.9g,%1.9g, %1.9g,%1.9g);\n", | |
| pt1.fX, pt1.fY, pt2.fX, pt2.fY, pt3pt.fX, pt3pt.fY); | |
| #endif | |
| fCurrent.cubicTo(pt1, pt2, pt3pt); | |
| } | |
| bool SkPathWriter::deferredLine(const SkOpPtT* pt) { | |
| SkASSERT(fFirstPtT); | |
| SkASSERT(fDefer[0]); | |
| if (fDefer[0] == pt) { | |
| // FIXME: why we're adding a degenerate line? Caller should have preflighted this. | |
| return true; | |
| } | |
| if (pt->contains(fDefer[0])) { | |
| // FIXME: why we're adding a degenerate line? | |
| return true; | |
| } | |
| if (this->matchedLast(pt)) { | |
| return false; | |
| } | |
| if (fDefer[1] && this->changedSlopes(pt)) { | |
| this->lineTo(); | |
| fDefer[0] = fDefer[1]; | |
| } | |
| fDefer[1] = pt; | |
| return true; | |
| } | |
| void SkPathWriter::deferredMove(const SkOpPtT* pt) { | |
| if (!fDefer[1]) { | |
| fFirstPtT = fDefer[0] = pt; | |
| return; | |
| } | |
| SkASSERT(fDefer[0]); | |
| if (!this->matchedLast(pt)) { | |
| this->finishContour(); | |
| fFirstPtT = fDefer[0] = pt; | |
| } | |
| } | |
| void SkPathWriter::finishContour() { | |
| if (!this->matchedLast(fDefer[0])) { | |
| if (!fDefer[1]) { | |
| return; | |
| } | |
| this->lineTo(); | |
| } | |
| if (fCurrent.isEmpty()) { | |
| return; | |
| } | |
| if (this->isClosed()) { | |
| this->close(); | |
| } else { | |
| SkASSERT(fDefer[1]); | |
| fEndPtTs.push_back(fFirstPtT); | |
| fEndPtTs.push_back(fDefer[1]); | |
| fPartials.push_back(fCurrent); | |
| this->init(); | |
| } | |
| } | |
| void SkPathWriter::init() { | |
| fCurrent.reset(); | |
| fFirstPtT = fDefer[0] = fDefer[1] = nullptr; | |
| } | |
| bool SkPathWriter::isClosed() const { | |
| return this->matchedLast(fFirstPtT); | |
| } | |
| void SkPathWriter::lineTo() { | |
| if (fCurrent.isEmpty()) { | |
| this->moveTo(); | |
| } | |
| #if DEBUG_PATH_CONSTRUCTION | |
| SkDebugf("path.lineTo(%1.9g,%1.9g);\n", fDefer[1]->fPt.fX, fDefer[1]->fPt.fY); | |
| #endif | |
| fCurrent.lineTo(fDefer[1]->fPt); | |
| } | |
| bool SkPathWriter::matchedLast(const SkOpPtT* test) const { | |
| if (test == fDefer[1]) { | |
| return true; | |
| } | |
| if (!test) { | |
| return false; | |
| } | |
| if (!fDefer[1]) { | |
| return false; | |
| } | |
| return test->contains(fDefer[1]); | |
| } | |
| void SkPathWriter::moveTo() { | |
| #if DEBUG_PATH_CONSTRUCTION | |
| SkDebugf("path.moveTo(%1.9g,%1.9g);\n", fFirstPtT->fPt.fX, fFirstPtT->fPt.fY); | |
| #endif | |
| fCurrent.moveTo(fFirstPtT->fPt); | |
| } | |
| void SkPathWriter::quadTo(const SkPoint& pt1, const SkOpPtT* pt2) { | |
| SkPoint pt2pt = this->update(pt2); | |
| #if DEBUG_PATH_CONSTRUCTION | |
| SkDebugf("path.quadTo(%1.9g,%1.9g, %1.9g,%1.9g);\n", | |
| pt1.fX, pt1.fY, pt2pt.fX, pt2pt.fY); | |
| #endif | |
| fCurrent.quadTo(pt1, pt2pt); | |
| } | |
| // if last point to be written matches the current path's first point, alter the | |
| // last to avoid writing a degenerate lineTo when the path is closed | |
| SkPoint SkPathWriter::update(const SkOpPtT* pt) { | |
| if (!fDefer[1]) { | |
| this->moveTo(); | |
| } else if (!this->matchedLast(fDefer[0])) { | |
| this->lineTo(); | |
| } | |
| SkPoint result = pt->fPt; | |
| if (fFirstPtT && result != fFirstPtT->fPt && fFirstPtT->contains(pt)) { | |
| result = fFirstPtT->fPt; | |
| } | |
| fDefer[0] = fDefer[1] = pt; // set both to know that there is not a pending deferred line | |
| return result; | |
| } | |
| bool SkPathWriter::someAssemblyRequired() { | |
| this->finishContour(); | |
| return !fEndPtTs.empty(); | |
| } | |
| bool SkPathWriter::changedSlopes(const SkOpPtT* ptT) const { | |
| if (matchedLast(fDefer[0])) { | |
| return false; | |
| } | |
| SkVector deferDxdy = fDefer[1]->fPt - fDefer[0]->fPt; | |
| SkVector lineDxdy = ptT->fPt - fDefer[1]->fPt; | |
| return deferDxdy.fX * lineDxdy.fY != deferDxdy.fY * lineDxdy.fX; | |
| } | |
| class DistanceLessThan { | |
| public: | |
| DistanceLessThan(double* distances) : fDistances(distances) { } | |
| double* fDistances; | |
| bool operator()(const int one, const int two) const { | |
| return fDistances[one] < fDistances[two]; | |
| } | |
| }; | |
| /* | |
| check start and end of each contour | |
| if not the same, record them | |
| match them up | |
| connect closest | |
| reassemble contour pieces into new path | |
| */ | |
| void SkPathWriter::assemble() { | |
| if (!this->someAssemblyRequired()) { | |
| return; | |
| } | |
| #if DEBUG_PATH_CONSTRUCTION | |
| SkDebugf("%s\n", __FUNCTION__); | |
| #endif | |
| SkOpPtT const* const* runs = fEndPtTs.begin(); // starts, ends of partial contours | |
| int endCount = fEndPtTs.size(); // all starts and ends | |
| SkASSERT(endCount > 0); | |
| SkASSERT(endCount == fPartials.size() * 2); | |
| #if DEBUG_ASSEMBLE | |
| for (int index = 0; index < endCount; index += 2) { | |
| const SkOpPtT* eStart = runs[index]; | |
| const SkOpPtT* eEnd = runs[index + 1]; | |
| SkASSERT(eStart != eEnd); | |
| SkASSERT(!eStart->contains(eEnd)); | |
| SkDebugf("%s contour start=(%1.9g,%1.9g) end=(%1.9g,%1.9g)\n", __FUNCTION__, | |
| eStart->fPt.fX, eStart->fPt.fY, eEnd->fPt.fX, eEnd->fPt.fY); | |
| } | |
| #endif | |
| // lengthen any partial contour adjacent to a simple segment | |
| for (int pIndex = 0; pIndex < endCount; pIndex++) { | |
| SkOpPtT* opPtT = const_cast<SkOpPtT*>(runs[pIndex]); | |
| SkPathWriter partWriter(SkPathFillType::kDefault); | |
| do { | |
| if (!zero_or_one(opPtT->fT)) { | |
| break; | |
| } | |
| SkOpSpanBase* opSpanBase = opPtT->span(); | |
| SkOpSpanBase* start = opPtT->fT ? opSpanBase->prev() : opSpanBase->upCast()->next(); | |
| int step = opPtT->fT ? 1 : -1; | |
| const SkOpSegment* opSegment = opSpanBase->segment(); | |
| const SkOpSegment* nextSegment = opSegment->isSimple(&start, &step); | |
| if (!nextSegment) { | |
| break; | |
| } | |
| SkOpSpanBase* opSpanEnd = start->t() ? start->prev() : start->upCast()->next(); | |
| if (start->starter(opSpanEnd)->alreadyAdded()) { | |
| break; | |
| } | |
| nextSegment->addCurveTo(start, opSpanEnd, &partWriter); | |
| opPtT = opSpanEnd->ptT(); | |
| SkOpPtT** runsPtr = const_cast<SkOpPtT**>(&runs[pIndex]); | |
| *runsPtr = opPtT; | |
| } while (true); | |
| partWriter.finishContour(); | |
| const TArray<SkPathBuilder>& partPartials = partWriter.partials(); | |
| if (partPartials.empty()) { | |
| continue; | |
| } | |
| // if pIndex is even, reverse and prepend to fPartials; otherwise, append | |
| SkPathBuilder& partial = const_cast<SkPathBuilder&>(fPartials[pIndex >> 1]); | |
| const SkPath part = partPartials[0].snapshot(); | |
| if (pIndex & 1) { | |
| partial.addPath(part, SkPath::kExtend_AddPathMode); | |
| } else { | |
| SkPathBuilder reverse; | |
| SkPathPriv::ReverseAddPath(&reverse, part); | |
| reverse.addPath(partial.detach(), SkPath::kExtend_AddPathMode); | |
| partial = reverse; | |
| } | |
| } | |
| SkTDArray<int> sLink, eLink; | |
| int linkCount = endCount / 2; // number of partial contours | |
| sLink.append(linkCount); | |
| eLink.append(linkCount); | |
| int rIndex, iIndex; | |
| for (rIndex = 0; rIndex < linkCount; ++rIndex) { | |
| sLink[rIndex] = eLink[rIndex] = SK_MaxS32; | |
| } | |
| const int entries = endCount * (endCount - 1) / 2; // folded triangle | |
| STArray<8, double, true> distances(entries); | |
| STArray<8, int, true> sortedDist(entries); | |
| STArray<8, int, true> distLookup(entries); | |
| int rRow = 0; | |
| int dIndex = 0; | |
| for (rIndex = 0; rIndex < endCount - 1; ++rIndex) { | |
| const SkOpPtT* oPtT = runs[rIndex]; | |
| for (iIndex = rIndex + 1; iIndex < endCount; ++iIndex) { | |
| const SkOpPtT* iPtT = runs[iIndex]; | |
| double dx = iPtT->fPt.fX - oPtT->fPt.fX; | |
| double dy = iPtT->fPt.fY - oPtT->fPt.fY; | |
| double dist = dx * dx + dy * dy; | |
| distLookup.push_back(rRow + iIndex); | |
| distances.push_back(dist); // oStart distance from iStart | |
| sortedDist.push_back(dIndex++); | |
| } | |
| rRow += endCount; | |
| } | |
| SkASSERT(dIndex == entries); | |
| SkTQSort<int>(sortedDist.begin(), sortedDist.end(), DistanceLessThan(distances.begin())); | |
| int remaining = linkCount; // number of start/end pairs | |
| for (rIndex = 0; rIndex < entries; ++rIndex) { | |
| int pair = sortedDist[rIndex]; | |
| pair = distLookup[pair]; | |
| int row = pair / endCount; | |
| int col = pair - row * endCount; | |
| int ndxOne = row >> 1; | |
| bool endOne = row & 1; | |
| int* linkOne = endOne ? eLink.begin() : sLink.begin(); | |
| if (linkOne[ndxOne] != SK_MaxS32) { | |
| continue; | |
| } | |
| int ndxTwo = col >> 1; | |
| bool endTwo = col & 1; | |
| int* linkTwo = endTwo ? eLink.begin() : sLink.begin(); | |
| if (linkTwo[ndxTwo] != SK_MaxS32) { | |
| continue; | |
| } | |
| SkASSERT(&linkOne[ndxOne] != &linkTwo[ndxTwo]); | |
| bool flip = endOne == endTwo; | |
| linkOne[ndxOne] = flip ? ~ndxTwo : ndxTwo; | |
| linkTwo[ndxTwo] = flip ? ~ndxOne : ndxOne; | |
| if (!--remaining) { | |
| break; | |
| } | |
| } | |
| SkASSERT(!remaining); | |
| #if DEBUG_ASSEMBLE | |
| for (rIndex = 0; rIndex < linkCount; ++rIndex) { | |
| int s = sLink[rIndex]; | |
| int e = eLink[rIndex]; | |
| SkDebugf("%s %c%d <- s%d - e%d -> %c%d\n", __FUNCTION__, s < 0 ? 's' : 'e', | |
| s < 0 ? ~s : s, rIndex, rIndex, e < 0 ? 'e' : 's', e < 0 ? ~e : e); | |
| } | |
| #endif | |
| rIndex = 0; | |
| do { | |
| bool forward = true; | |
| bool first = true; | |
| int sIndex = sLink[rIndex]; | |
| SkASSERT(sIndex != SK_MaxS32); | |
| sLink[rIndex] = SK_MaxS32; | |
| int eIndex; | |
| if (sIndex < 0) { | |
| eIndex = sLink[~sIndex]; | |
| sLink[~sIndex] = SK_MaxS32; | |
| } else { | |
| eIndex = eLink[sIndex]; | |
| eLink[sIndex] = SK_MaxS32; | |
| } | |
| SkASSERT(eIndex != SK_MaxS32); | |
| #if DEBUG_ASSEMBLE | |
| SkDebugf("%s sIndex=%c%d eIndex=%c%d\n", __FUNCTION__, sIndex < 0 ? 's' : 'e', | |
| sIndex < 0 ? ~sIndex : sIndex, eIndex < 0 ? 's' : 'e', | |
| eIndex < 0 ? ~eIndex : eIndex); | |
| #endif | |
| do { | |
| SkPath contour = fPartials[rIndex].snapshot(); | |
| if (!first) { | |
| auto prior = fBuilder.getLastPt(); | |
| if (!prior) { | |
| return; | |
| } | |
| SkSpan<const SkPoint> contourPts = contour.points(); | |
| SkPoint next; | |
| if (forward) { | |
| next = contourPts.empty() ? SkPoint{0, 0} : contourPts.front(); | |
| } else { | |
| SkASSERT(!contourPts.empty()); | |
| next = contourPts.back(); | |
| } | |
| if (*prior != next) { | |
| /* TODO: if there is a gap between open path written so far and path to come, | |
| connect by following segments from one to the other, rather than introducing | |
| a diagonal to connect the two. | |
| */ | |
| } | |
| } | |
| if (forward) { | |
| fBuilder.addPath(contour, | |
| first ? SkPath::kAppend_AddPathMode : SkPath::kExtend_AddPathMode); | |
| } else { | |
| SkASSERT(!first); | |
| SkPathPriv::ReversePathTo(&fBuilder, contour); | |
| } | |
| if (first) { | |
| first = false; | |
| } | |
| #if DEBUG_ASSEMBLE | |
| SkDebugf("%s rIndex=%d eIndex=%s%d close=%d\n", __FUNCTION__, rIndex, | |
| eIndex < 0 ? "~" : "", eIndex < 0 ? ~eIndex : eIndex, | |
| sIndex == ((rIndex != eIndex) ^ forward ? eIndex : ~eIndex)); | |
| #endif | |
| if (sIndex == ((rIndex != eIndex) ^ forward ? eIndex : ~eIndex)) { | |
| fBuilder.close(); | |
| break; | |
| } | |
| if (forward) { | |
| eIndex = eLink[rIndex]; | |
| SkASSERT(eIndex != SK_MaxS32); | |
| eLink[rIndex] = SK_MaxS32; | |
| if (eIndex >= 0) { | |
| SkASSERT(sLink[eIndex] == rIndex); | |
| sLink[eIndex] = SK_MaxS32; | |
| } else { | |
| SkASSERT(eLink[~eIndex] == ~rIndex); | |
| eLink[~eIndex] = SK_MaxS32; | |
| } | |
| } else { | |
| eIndex = sLink[rIndex]; | |
| SkASSERT(eIndex != SK_MaxS32); | |
| sLink[rIndex] = SK_MaxS32; | |
| if (eIndex >= 0) { | |
| SkASSERT(eLink[eIndex] == rIndex); | |
| eLink[eIndex] = SK_MaxS32; | |
| } else { | |
| SkASSERT(sLink[~eIndex] == ~rIndex); | |
| sLink[~eIndex] = SK_MaxS32; | |
| } | |
| } | |
| rIndex = eIndex; | |
| if (rIndex < 0) { | |
| forward ^= 1; | |
| rIndex = ~rIndex; | |
| } | |
| } while (true); | |
| for (rIndex = 0; rIndex < linkCount; ++rIndex) { | |
| if (sLink[rIndex] != SK_MaxS32) { | |
| break; | |
| } | |
| } | |
| } while (rIndex < linkCount); | |
| #if DEBUG_ASSEMBLE | |
| for (rIndex = 0; rIndex < linkCount; ++rIndex) { | |
| SkASSERT(sLink[rIndex] == SK_MaxS32); | |
| SkASSERT(eLink[rIndex] == SK_MaxS32); | |
| } | |
| #endif | |
| } |