123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195 |
- /*
- * Copyright 2014 Google Inc.
- *
- * Use of this source code is governed by a BSD-style license that can be
- * found in the LICENSE file.
- */
- #include "include/core/SkMatrix.h"
- #include "include/pathops/SkPathOps.h"
- #include "src/core/SkArenaAlloc.h"
- #include "src/core/SkPathPriv.h"
- #include "src/pathops/SkOpEdgeBuilder.h"
- #include "src/pathops/SkPathOpsCommon.h"
- static bool one_contour(const SkPath& path) {
- SkSTArenaAlloc<256> allocator;
- int verbCount = path.countVerbs();
- uint8_t* verbs = (uint8_t*) allocator.makeArrayDefault<uint8_t>(verbCount);
- (void) path.getVerbs(verbs, verbCount);
- for (int index = 1; index < verbCount; ++index) {
- if (verbs[index] == SkPath::kMove_Verb) {
- return false;
- }
- }
- return true;
- }
- void SkOpBuilder::ReversePath(SkPath* path) {
- SkPath temp;
- SkPoint lastPt;
- SkAssertResult(path->getLastPt(&lastPt));
- temp.moveTo(lastPt);
- temp.reversePathTo(*path);
- temp.close();
- *path = temp;
- }
- bool SkOpBuilder::FixWinding(SkPath* path) {
- SkPath::FillType fillType = path->getFillType();
- if (fillType == SkPath::kInverseEvenOdd_FillType) {
- fillType = SkPath::kInverseWinding_FillType;
- } else if (fillType == SkPath::kEvenOdd_FillType) {
- fillType = SkPath::kWinding_FillType;
- }
- SkPathPriv::FirstDirection dir;
- if (one_contour(*path) && SkPathPriv::CheapComputeFirstDirection(*path, &dir)) {
- if (dir != SkPathPriv::kCCW_FirstDirection) {
- ReversePath(path);
- }
- path->setFillType(fillType);
- return true;
- }
- SkSTArenaAlloc<4096> allocator;
- SkOpContourHead contourHead;
- SkOpGlobalState globalState(&contourHead, &allocator SkDEBUGPARAMS(false)
- SkDEBUGPARAMS(nullptr));
- SkOpEdgeBuilder builder(*path, &contourHead, &globalState);
- if (builder.unparseable() || !builder.finish()) {
- return false;
- }
- if (!contourHead.count()) {
- return true;
- }
- if (!contourHead.next()) {
- return false;
- }
- contourHead.joinAllSegments();
- contourHead.resetReverse();
- bool writePath = false;
- SkOpSpan* topSpan;
- globalState.setPhase(SkOpPhase::kFixWinding);
- while ((topSpan = FindSortableTop(&contourHead))) {
- SkOpSegment* topSegment = topSpan->segment();
- SkOpContour* topContour = topSegment->contour();
- SkASSERT(topContour->isCcw() >= 0);
- #if DEBUG_WINDING
- SkDebugf("%s id=%d nested=%d ccw=%d\n", __FUNCTION__,
- topSegment->debugID(), globalState.nested(), topContour->isCcw());
- #endif
- if ((globalState.nested() & 1) != SkToBool(topContour->isCcw())) {
- topContour->setReverse();
- writePath = true;
- }
- topContour->markAllDone();
- globalState.clearNested();
- }
- if (!writePath) {
- path->setFillType(fillType);
- return true;
- }
- SkPath empty;
- SkPathWriter woundPath(empty);
- SkOpContour* test = &contourHead;
- do {
- if (!test->count()) {
- continue;
- }
- if (test->reversed()) {
- test->toReversePath(&woundPath);
- } else {
- test->toPath(&woundPath);
- }
- } while ((test = test->next()));
- *path = *woundPath.nativePath();
- path->setFillType(fillType);
- return true;
- }
- void SkOpBuilder::add(const SkPath& path, SkPathOp op) {
- if (0 == fOps.count() && op != kUnion_SkPathOp) {
- fPathRefs.push_back() = SkPath();
- *fOps.append() = kUnion_SkPathOp;
- }
- fPathRefs.push_back() = path;
- *fOps.append() = op;
- }
- void SkOpBuilder::reset() {
- fPathRefs.reset();
- fOps.reset();
- }
- /* OPTIMIZATION: Union doesn't need to be all-or-nothing. A run of three or more convex
- paths with union ops could be locally resolved and still improve over doing the
- ops one at a time. */
- bool SkOpBuilder::resolve(SkPath* result) {
- SkPath original = *result;
- int count = fOps.count();
- bool allUnion = true;
- SkPathPriv::FirstDirection firstDir = SkPathPriv::kUnknown_FirstDirection;
- for (int index = 0; index < count; ++index) {
- SkPath* test = &fPathRefs[index];
- if (kUnion_SkPathOp != fOps[index] || test->isInverseFillType()) {
- allUnion = false;
- break;
- }
- // If all paths are convex, track direction, reversing as needed.
- if (test->isConvex()) {
- SkPathPriv::FirstDirection dir;
- if (!SkPathPriv::CheapComputeFirstDirection(*test, &dir)) {
- allUnion = false;
- break;
- }
- if (firstDir == SkPathPriv::kUnknown_FirstDirection) {
- firstDir = dir;
- } else if (firstDir != dir) {
- ReversePath(test);
- }
- continue;
- }
- // If the path is not convex but its bounds do not intersect the others, simplify is enough.
- const SkRect& testBounds = test->getBounds();
- for (int inner = 0; inner < index; ++inner) {
- // OPTIMIZE: check to see if the contour bounds do not intersect other contour bounds?
- if (SkRect::Intersects(fPathRefs[inner].getBounds(), testBounds)) {
- allUnion = false;
- break;
- }
- }
- }
- if (!allUnion) {
- *result = fPathRefs[0];
- for (int index = 1; index < count; ++index) {
- if (!Op(*result, fPathRefs[index], fOps[index], result)) {
- reset();
- *result = original;
- return false;
- }
- }
- reset();
- return true;
- }
- SkPath sum;
- for (int index = 0; index < count; ++index) {
- if (!Simplify(fPathRefs[index], &fPathRefs[index])) {
- reset();
- *result = original;
- return false;
- }
- if (!fPathRefs[index].isEmpty()) {
- // convert the even odd result back to winding form before accumulating it
- if (!FixWinding(&fPathRefs[index])) {
- *result = original;
- return false;
- }
- sum.addPath(fPathRefs[index]);
- }
- }
- reset();
- bool success = Simplify(sum, result);
- if (!success) {
- *result = original;
- }
- return success;
- }
|