blob: 8cd770dd54632b48da746bd95e7d60f2c0518d88 [file] [log] [blame]
/*
* 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 "SkAddIntersections.h"
#include "SkOpCoincidence.h"
#include "SkOpEdgeBuilder.h"
#include "SkPathOpsCommon.h"
#include "SkPathWriter.h"
static bool bridgeWinding(SkOpContourHead* contourList, SkPathWriter* simple) {
bool unsortable = false;
do {
SkOpSpan* span = FindSortableTop(contourList);
if (!span) {
break;
}
SkOpSegment* current = span->segment();
SkOpSpanBase* start = span->next();
SkOpSpanBase* end = span;
SkTDArray<SkOpSpanBase*> chase;
do {
if (current->activeWinding(start, end)) {
do {
if (!unsortable && current->done()) {
break;
}
SkASSERT(unsortable || !current->done());
SkOpSpanBase* nextStart = start;
SkOpSpanBase* nextEnd = end;
SkOpSegment* next = current->findNextWinding(&chase, &nextStart, &nextEnd,
&unsortable);
if (!next) {
break;
}
#if DEBUG_FLOW
SkDebugf("%s current id=%d from=(%1.9g,%1.9g) to=(%1.9g,%1.9g)\n", __FUNCTION__,
current->debugID(), start->pt().fX, start->pt().fY,
end->pt().fX, end->pt().fY);
#endif
if (!current->addCurveTo(start, end, simple)) {
return false;
}
current = next;
start = nextStart;
end = nextEnd;
} while (!simple->isClosed() && (!unsortable || !start->starter(end)->done()));
if (current->activeWinding(start, end) && !simple->isClosed()) {
SkOpSpan* spanStart = start->starter(end);
if (!spanStart->done()) {
if (!current->addCurveTo(start, end, simple)) {
return false;
}
current->markDone(spanStart);
}
}
simple->finishContour();
} else {
SkOpSpanBase* last = current->markAndChaseDone(start, end);
if (last && !last->chased()) {
last->setChased(true);
SkASSERT(!SkPathOpsDebug::ChaseContains(chase, last));
*chase.append() = last;
#if DEBUG_WINDING
SkDebugf("%s chase.append id=%d", __FUNCTION__, last->segment()->debugID());
if (!last->final()) {
SkDebugf(" windSum=%d", last->upCast()->windSum());
}
SkDebugf("\n");
#endif
}
}
current = FindChase(&chase, &start, &end);
SkPathOpsDebug::ShowActiveSpans(contourList);
if (!current) {
break;
}
} while (true);
} while (true);
return true;
}
// returns true if all edges were processed
static bool bridgeXor(SkOpContourHead* contourList, SkPathWriter* simple) {
SkOpSegment* current;
SkOpSpanBase* start;
SkOpSpanBase* end;
bool unsortable = false;
while ((current = FindUndone(contourList, &start, &end))) {
do {
if (!unsortable && current->done()) {
SkPathOpsDebug::ShowActiveSpans(contourList);
}
SkASSERT(unsortable || !current->done());
SkOpSpanBase* nextStart = start;
SkOpSpanBase* nextEnd = end;
SkOpSegment* next = current->findNextXor(&nextStart, &nextEnd, &unsortable);
if (!next) {
if (!unsortable && simple->hasMove()
&& current->verb() != SkPath::kLine_Verb
&& !simple->isClosed()) {
if (!current->addCurveTo(start, end, simple)) {
return false;
}
if (!simple->isClosed()) {
SkPathOpsDebug::ShowActiveSpans(contourList);
}
}
break;
}
#if DEBUG_FLOW
SkDebugf("%s current id=%d from=(%1.9g,%1.9g) to=(%1.9g,%1.9g)\n", __FUNCTION__,
current->debugID(), start->pt().fX, start->pt().fY,
end->pt().fX, end->pt().fY);
#endif
if (!current->addCurveTo(start, end, simple)) {
return false;
}
current = next;
start = nextStart;
end = nextEnd;
} while (!simple->isClosed() && (!unsortable || !start->starter(end)->done()));
if (!simple->isClosed()) {
SkASSERT(unsortable);
SkOpSpan* spanStart = start->starter(end);
if (!spanStart->done()) {
if (!current->addCurveTo(start, end, simple)) {
return false;
}
current->markDone(spanStart);
}
}
simple->finishContour();
SkPathOpsDebug::ShowActiveSpans(contourList);
}
return true;
}
// FIXME : add this as a member of SkPath
bool SimplifyDebug(const SkPath& path, SkPath* result
SkDEBUGPARAMS(bool skipAssert) SkDEBUGPARAMS(const char* testName)) {
// returns 1 for evenodd, -1 for winding, regardless of inverse-ness
SkPath::FillType fillType = path.isInverseFillType() ? SkPath::kInverseEvenOdd_FillType
: SkPath::kEvenOdd_FillType;
if (path.isConvex()) {
if (result != &path) {
*result = path;
}
result->setFillType(fillType);
return true;
}
// turn path into list of segments
SkChunkAlloc allocator(4096); // FIXME: constant-ize, tune
SkOpContour contour;
SkOpContourHead* contourList = static_cast<SkOpContourHead*>(&contour);
SkOpGlobalState globalState(contourList, &allocator
SkDEBUGPARAMS(skipAssert) SkDEBUGPARAMS(testName));
SkOpCoincidence coincidence(&globalState);
#if DEBUG_DUMP_VERIFY
#ifndef SK_DEBUG
const char* testName = "release";
#endif
if (SkPathOpsDebug::gDumpOp) {
SkPathOpsDebug::DumpSimplify(path, testName);
}
#endif
SkScalar scaleFactor = ScaleFactor(path);
SkPath scaledPath;
const SkPath* workingPath;
if (scaleFactor > SK_Scalar1) {
ScalePath(path, 1.f / scaleFactor, &scaledPath);
workingPath = &scaledPath;
} else {
workingPath = &path;
}
#if DEBUG_SORT
SkPathOpsDebug::gSortCount = SkPathOpsDebug::gSortCountDefault;
#endif
SkOpEdgeBuilder builder(*workingPath, contourList, &globalState);
if (!builder.finish()) {
return false;
}
#if DEBUG_DUMP_SEGMENTS
contour.dumpSegments();
#endif
if (!SortContourList(&contourList, false, false)) {
result->reset();
result->setFillType(fillType);
return true;
}
// find all intersections between segments
SkOpContour* current = contourList;
do {
SkOpContour* next = current;
while (AddIntersectTs(current, next, &coincidence)
&& (next = next->next()));
} while ((current = current->next()));
#if DEBUG_VALIDATE
globalState.setPhase(SkOpPhase::kWalking);
#endif
bool success = HandleCoincidence(contourList, &coincidence);
#if DEBUG_COIN
globalState.debugAddToGlobalCoinDicts();
#endif
if (!success) {
return false;
}
#if DEBUG_DUMP_ALIGNMENT
contour.dumpSegments("aligned");
#endif
// construct closed contours
result->reset();
result->setFillType(fillType);
SkPathWriter wrapper(*result);
if (builder.xorMask() == kWinding_PathOpsMask ? !bridgeWinding(contourList, &wrapper)
: !bridgeXor(contourList, &wrapper)) {
return false;
}
wrapper.assemble(); // if some edges could not be resolved, assemble remaining
if (scaleFactor > 1) {
ScalePath(*result, scaleFactor, result);
}
return true;
}
bool Simplify(const SkPath& path, SkPath* result) {
#if DEBUG_DUMP_VERIFY
if (SkPathOpsDebug::gVerifyOp) {
if (!SimplifyDebug(path, result SkDEBUGPARAMS(false) SkDEBUGPARAMS(nullptr))) {
SkPathOpsDebug::ReportSimplifyFail(path);
return false;
}
SkPathOpsDebug::VerifySimplify(path, *result);
return true;
}
#endif
return SimplifyDebug(path, result SkDEBUGPARAMS(true) SkDEBUGPARAMS(nullptr));
}