1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/gfx/skia/trunk/src/pathops/SkPathOpsSimplify.cpp Wed Dec 31 06:09:35 2014 +0100
1.3 @@ -0,0 +1,199 @@
1.4 +/*
1.5 + * Copyright 2012 Google Inc.
1.6 + *
1.7 + * Use of this source code is governed by a BSD-style license that can be
1.8 + * found in the LICENSE file.
1.9 + */
1.10 +#include "SkAddIntersections.h"
1.11 +#include "SkOpEdgeBuilder.h"
1.12 +#include "SkPathOpsCommon.h"
1.13 +#include "SkPathWriter.h"
1.14 +
1.15 +static bool bridgeWinding(SkTArray<SkOpContour*, true>& contourList, SkPathWriter* simple) {
1.16 + bool firstContour = true;
1.17 + bool unsortable = false;
1.18 + bool topUnsortable = false;
1.19 + SkPoint topLeft = {SK_ScalarMin, SK_ScalarMin};
1.20 + do {
1.21 + int index, endIndex;
1.22 + bool topDone;
1.23 + SkOpSegment* current = FindSortableTop(contourList, SkOpAngle::kUnaryWinding, &firstContour,
1.24 + &index, &endIndex, &topLeft, &topUnsortable, &topDone);
1.25 + if (!current) {
1.26 + if (topUnsortable || !topDone) {
1.27 + topUnsortable = false;
1.28 + SkASSERT(topLeft.fX != SK_ScalarMin && topLeft.fY != SK_ScalarMin);
1.29 + topLeft.fX = topLeft.fY = SK_ScalarMin;
1.30 + continue;
1.31 + }
1.32 + break;
1.33 + }
1.34 + SkTDArray<SkOpSpan*> chaseArray;
1.35 + do {
1.36 + if (current->activeWinding(index, endIndex)) {
1.37 + do {
1.38 + if (!unsortable && current->done()) {
1.39 + #if DEBUG_ACTIVE_SPANS
1.40 + DebugShowActiveSpans(contourList);
1.41 + #endif
1.42 + if (simple->isEmpty()) {
1.43 + simple->init();
1.44 + break;
1.45 + }
1.46 + }
1.47 + SkASSERT(unsortable || !current->done());
1.48 + int nextStart = index;
1.49 + int nextEnd = endIndex;
1.50 + SkOpSegment* next = current->findNextWinding(&chaseArray, &nextStart, &nextEnd,
1.51 + &unsortable);
1.52 + if (!next) {
1.53 + if (!unsortable && simple->hasMove()
1.54 + && current->verb() != SkPath::kLine_Verb
1.55 + && !simple->isClosed()) {
1.56 + current->addCurveTo(index, endIndex, simple, true);
1.57 + SkASSERT(simple->isClosed());
1.58 + }
1.59 + break;
1.60 + }
1.61 + #if DEBUG_FLOW
1.62 + SkDebugf("%s current id=%d from=(%1.9g,%1.9g) to=(%1.9g,%1.9g)\n", __FUNCTION__,
1.63 + current->debugID(), current->xyAtT(index).fX, current->xyAtT(index).fY,
1.64 + current->xyAtT(endIndex).fX, current->xyAtT(endIndex).fY);
1.65 + #endif
1.66 + current->addCurveTo(index, endIndex, simple, true);
1.67 + current = next;
1.68 + index = nextStart;
1.69 + endIndex = nextEnd;
1.70 + } while (!simple->isClosed() && (!unsortable
1.71 + || !current->done(SkMin32(index, endIndex))));
1.72 + if (current->activeWinding(index, endIndex) && !simple->isClosed()) {
1.73 + SkASSERT(unsortable || simple->isEmpty());
1.74 + int min = SkMin32(index, endIndex);
1.75 + if (!current->done(min)) {
1.76 + current->addCurveTo(index, endIndex, simple, true);
1.77 + current->markDoneUnary(min);
1.78 + }
1.79 + }
1.80 + simple->close();
1.81 + } else {
1.82 + SkOpSpan* last = current->markAndChaseDoneUnary(index, endIndex);
1.83 + if (last && !last->fLoop) {
1.84 + *chaseArray.append() = last;
1.85 + }
1.86 + }
1.87 + current = FindChase(chaseArray, index, endIndex);
1.88 + #if DEBUG_ACTIVE_SPANS
1.89 + DebugShowActiveSpans(contourList);
1.90 + #endif
1.91 + if (!current) {
1.92 + break;
1.93 + }
1.94 + } while (true);
1.95 + } while (true);
1.96 + return simple->someAssemblyRequired();
1.97 +}
1.98 +
1.99 +// returns true if all edges were processed
1.100 +static bool bridgeXor(SkTArray<SkOpContour*, true>& contourList, SkPathWriter* simple) {
1.101 + SkOpSegment* current;
1.102 + int start, end;
1.103 + bool unsortable = false;
1.104 + bool closable = true;
1.105 + while ((current = FindUndone(contourList, &start, &end))) {
1.106 + do {
1.107 + #if DEBUG_ACTIVE_SPANS
1.108 + if (!unsortable && current->done()) {
1.109 + DebugShowActiveSpans(contourList);
1.110 + }
1.111 + #endif
1.112 + SkASSERT(unsortable || !current->done());
1.113 + int nextStart = start;
1.114 + int nextEnd = end;
1.115 + SkOpSegment* next = current->findNextXor(&nextStart, &nextEnd, &unsortable);
1.116 + if (!next) {
1.117 + if (!unsortable && simple->hasMove()
1.118 + && current->verb() != SkPath::kLine_Verb
1.119 + && !simple->isClosed()) {
1.120 + current->addCurveTo(start, end, simple, true);
1.121 + SkASSERT(simple->isClosed());
1.122 + }
1.123 + break;
1.124 + }
1.125 + #if DEBUG_FLOW
1.126 + SkDebugf("%s current id=%d from=(%1.9g,%1.9g) to=(%1.9g,%1.9g)\n", __FUNCTION__,
1.127 + current->debugID(), current->xyAtT(start).fX, current->xyAtT(start).fY,
1.128 + current->xyAtT(end).fX, current->xyAtT(end).fY);
1.129 + #endif
1.130 + current->addCurveTo(start, end, simple, true);
1.131 + current = next;
1.132 + start = nextStart;
1.133 + end = nextEnd;
1.134 + } while (!simple->isClosed() && (!unsortable || !current->done(SkMin32(start, end))));
1.135 + if (!simple->isClosed()) {
1.136 + SkASSERT(unsortable);
1.137 + int min = SkMin32(start, end);
1.138 + if (!current->done(min)) {
1.139 + current->addCurveTo(start, end, simple, true);
1.140 + current->markDone(min, 1);
1.141 + }
1.142 + closable = false;
1.143 + }
1.144 + simple->close();
1.145 + #if DEBUG_ACTIVE_SPANS
1.146 + DebugShowActiveSpans(contourList);
1.147 + #endif
1.148 + }
1.149 + return closable;
1.150 +}
1.151 +
1.152 +// FIXME : add this as a member of SkPath
1.153 +bool Simplify(const SkPath& path, SkPath* result) {
1.154 +#if DEBUG_SORT || DEBUG_SWAP_TOP
1.155 + SkPathOpsDebug::gSortCount = SkPathOpsDebug::gSortCountDefault;
1.156 +#endif
1.157 + // returns 1 for evenodd, -1 for winding, regardless of inverse-ness
1.158 + SkPath::FillType fillType = path.isInverseFillType() ? SkPath::kInverseEvenOdd_FillType
1.159 + : SkPath::kEvenOdd_FillType;
1.160 +
1.161 + // turn path into list of segments
1.162 + SkTArray<SkOpContour> contours;
1.163 + SkOpEdgeBuilder builder(path, contours);
1.164 + if (!builder.finish()) {
1.165 + return false;
1.166 + }
1.167 + SkTArray<SkOpContour*, true> contourList;
1.168 + MakeContourList(contours, contourList, false, false);
1.169 + SkOpContour** currentPtr = contourList.begin();
1.170 + result->reset();
1.171 + result->setFillType(fillType);
1.172 + if (!currentPtr) {
1.173 + return true;
1.174 + }
1.175 + SkOpContour** listEnd = contourList.end();
1.176 + // find all intersections between segments
1.177 + do {
1.178 + SkOpContour** nextPtr = currentPtr;
1.179 + SkOpContour* current = *currentPtr++;
1.180 + if (current->containsCubics()) {
1.181 + AddSelfIntersectTs(current);
1.182 + }
1.183 + SkOpContour* next;
1.184 + do {
1.185 + next = *nextPtr++;
1.186 + } while (AddIntersectTs(current, next) && nextPtr != listEnd);
1.187 + } while (currentPtr != listEnd);
1.188 + HandleCoincidence(&contourList, 0);
1.189 + // construct closed contours
1.190 + SkPathWriter simple(*result);
1.191 + if (builder.xorMask() == kWinding_PathOpsMask ? bridgeWinding(contourList, &simple)
1.192 + : !bridgeXor(contourList, &simple))
1.193 + { // if some edges could not be resolved, assemble remaining fragments
1.194 + SkPath temp;
1.195 + temp.setFillType(fillType);
1.196 + SkPathWriter assembled(temp);
1.197 + Assemble(simple, &assembled);
1.198 + *result = *assembled.nativePath();
1.199 + result->setFillType(fillType);
1.200 + }
1.201 + return true;
1.202 +}
