Add base types for path ops
Paths contain lines, quads, and cubics, which are
collectively curves.
To work with path intersections, intermediary curves
are constructed. For now, those intermediates use
doubles to guarantee sufficient precision.
The DVector, DPoint, DLine, DQuad, and DCubic
structs encapsulate these intermediate curves.
The DRect and DTriangle structs are created to
describe intersectable areas of interest.
The Bounds struct inherits from SkRect to create
a SkScalar-based rectangle that intersects shared
edges.
This also includes common math equalities and
debugging that the remainder of path ops builds on,
as well as a temporary top-level interface in
include/pathops/SkPathOps.h.
Review URL: https://codereview.chromium.org/12827020
git-svn-id: http://skia.googlecode.com/svn/trunk@8551 2bbb7eff-a529-9590-31e7-b0007b416f81
diff --git a/src/pathops/SkOpContour.cpp b/src/pathops/SkOpContour.cpp
new file mode 100644
index 0000000..e68341c
--- /dev/null
+++ b/src/pathops/SkOpContour.cpp
@@ -0,0 +1,265 @@
+/*
+* Copyright 2013 Google Inc.
+*
+* Use of this source code is governed by a BSD-style license that can be
+* found in the LICENSE file.
+*/
+#include "SkIntersections.h"
+#include "SkOpContour.h"
+#include "SkPathWriter.h"
+#include "TSearch.h"
+
+void SkOpContour::addCoincident(int index, SkOpContour* other, int otherIndex,
+ const SkIntersections& ts, bool swap) {
+ SkCoincidence& coincidence = *fCoincidences.append();
+ coincidence.fContours[0] = this; // FIXME: no need to store
+ coincidence.fContours[1] = other;
+ coincidence.fSegments[0] = index;
+ coincidence.fSegments[1] = otherIndex;
+ coincidence.fTs[swap][0] = ts[0][0];
+ coincidence.fTs[swap][1] = ts[0][1];
+ coincidence.fTs[!swap][0] = ts[1][0];
+ coincidence.fTs[!swap][1] = ts[1][1];
+ coincidence.fPts[0] = ts.pt(0).asSkPoint();
+ coincidence.fPts[1] = ts.pt(1).asSkPoint();
+}
+
+SkOpSegment* SkOpContour::nonVerticalSegment(int* start, int* end) {
+ int segmentCount = fSortedSegments.count();
+ SkASSERT(segmentCount > 0);
+ for (int sortedIndex = fFirstSorted; sortedIndex < segmentCount; ++sortedIndex) {
+ SkOpSegment* testSegment = fSortedSegments[sortedIndex];
+ if (testSegment->done()) {
+ continue;
+ }
+ *start = *end = 0;
+ while (testSegment->nextCandidate(start, end)) {
+ if (!testSegment->isVertical(*start, *end)) {
+ return testSegment;
+ }
+ }
+ }
+ return NULL;
+}
+
+// first pass, add missing T values
+// second pass, determine winding values of overlaps
+void SkOpContour::addCoincidentPoints() {
+ int count = fCoincidences.count();
+ for (int index = 0; index < count; ++index) {
+ SkCoincidence& coincidence = fCoincidences[index];
+ SkASSERT(coincidence.fContours[0] == this);
+ int thisIndex = coincidence.fSegments[0];
+ SkOpSegment& thisOne = fSegments[thisIndex];
+ SkOpContour* otherContour = coincidence.fContours[1];
+ int otherIndex = coincidence.fSegments[1];
+ SkOpSegment& other = otherContour->fSegments[otherIndex];
+ if ((thisOne.done() || other.done()) && thisOne.complete() && other.complete()) {
+ // OPTIMIZATION: remove from array
+ continue;
+ }
+ #if DEBUG_CONCIDENT
+ thisOne.debugShowTs();
+ other.debugShowTs();
+ #endif
+ double startT = coincidence.fTs[0][0];
+ double endT = coincidence.fTs[0][1];
+ bool cancelers;
+ if ((cancelers = startT > endT)) {
+ SkTSwap(startT, endT);
+ SkTSwap(coincidence.fPts[0], coincidence.fPts[1]);
+ }
+ SkASSERT(!approximately_negative(endT - startT));
+ double oStartT = coincidence.fTs[1][0];
+ double oEndT = coincidence.fTs[1][1];
+ if (oStartT > oEndT) {
+ SkTSwap<double>(oStartT, oEndT);
+ cancelers ^= true;
+ }
+ SkASSERT(!approximately_negative(oEndT - oStartT));
+ bool opp = fOperand ^ otherContour->fOperand;
+ if (cancelers && !opp) {
+ // make sure startT and endT have t entries
+ if (startT > 0 || oEndT < 1
+ || thisOne.isMissing(startT) || other.isMissing(oEndT)) {
+ thisOne.addTPair(startT, &other, oEndT, true, coincidence.fPts[0]);
+ }
+ if (oStartT > 0 || endT < 1
+ || thisOne.isMissing(endT) || other.isMissing(oStartT)) {
+ other.addTPair(oStartT, &thisOne, endT, true, coincidence.fPts[1]);
+ }
+ } else {
+ if (startT > 0 || oStartT > 0
+ || thisOne.isMissing(startT) || other.isMissing(oStartT)) {
+ thisOne.addTPair(startT, &other, oStartT, true, coincidence.fPts[0]);
+ }
+ if (endT < 1 || oEndT < 1
+ || thisOne.isMissing(endT) || other.isMissing(oEndT)) {
+ other.addTPair(oEndT, &thisOne, endT, true, coincidence.fPts[1]);
+ }
+ }
+ #if DEBUG_CONCIDENT
+ thisOne.debugShowTs();
+ other.debugShowTs();
+ #endif
+ }
+}
+
+void SkOpContour::calcCoincidentWinding() {
+ int count = fCoincidences.count();
+ for (int index = 0; index < count; ++index) {
+ SkCoincidence& coincidence = fCoincidences[index];
+ SkASSERT(coincidence.fContours[0] == this);
+ int thisIndex = coincidence.fSegments[0];
+ SkOpSegment& thisOne = fSegments[thisIndex];
+ if (thisOne.done()) {
+ continue;
+ }
+ SkOpContour* otherContour = coincidence.fContours[1];
+ int otherIndex = coincidence.fSegments[1];
+ SkOpSegment& other = otherContour->fSegments[otherIndex];
+ if (other.done()) {
+ continue;
+ }
+ double startT = coincidence.fTs[0][0];
+ double endT = coincidence.fTs[0][1];
+ bool cancelers;
+ if ((cancelers = startT > endT)) {
+ SkTSwap<double>(startT, endT);
+ }
+ SkASSERT(!approximately_negative(endT - startT));
+ double oStartT = coincidence.fTs[1][0];
+ double oEndT = coincidence.fTs[1][1];
+ if (oStartT > oEndT) {
+ SkTSwap<double>(oStartT, oEndT);
+ cancelers ^= true;
+ }
+ SkASSERT(!approximately_negative(oEndT - oStartT));
+ bool opp = fOperand ^ otherContour->fOperand;
+ if (cancelers && !opp) {
+ // make sure startT and endT have t entries
+ if (!thisOne.done() && !other.done()) {
+ thisOne.addTCancel(startT, endT, &other, oStartT, oEndT);
+ }
+ } else {
+ if (!thisOne.done() && !other.done()) {
+ thisOne.addTCoincident(startT, endT, &other, oStartT, oEndT);
+ }
+ }
+ #if DEBUG_CONCIDENT
+ thisOne.debugShowTs();
+ other.debugShowTs();
+ #endif
+ }
+}
+
+void SkOpContour::sortSegments() {
+ int segmentCount = fSegments.count();
+ fSortedSegments.setReserve(segmentCount);
+ for (int test = 0; test < segmentCount; ++test) {
+ *fSortedSegments.append() = &fSegments[test];
+ }
+ QSort<SkOpSegment>(fSortedSegments.begin(), fSortedSegments.end() - 1);
+ fFirstSorted = 0;
+}
+
+void SkOpContour::toPath(SkPathWriter* path) const {
+ int segmentCount = fSegments.count();
+ const SkPoint& pt = fSegments.front().pts()[0];
+ path->deferredMove(pt);
+ for (int test = 0; test < segmentCount; ++test) {
+ fSegments[test].addCurveTo(0, 1, path, true);
+ }
+ path->close();
+}
+
+void SkOpContour::topSortableSegment(const SkPoint& topLeft, SkPoint* bestXY,
+ SkOpSegment** topStart) {
+ int segmentCount = fSortedSegments.count();
+ SkASSERT(segmentCount > 0);
+ int sortedIndex = fFirstSorted;
+ fDone = true; // may be cleared below
+ for ( ; sortedIndex < segmentCount; ++sortedIndex) {
+ SkOpSegment* testSegment = fSortedSegments[sortedIndex];
+ if (testSegment->done()) {
+ if (sortedIndex == fFirstSorted) {
+ ++fFirstSorted;
+ }
+ continue;
+ }
+ fDone = false;
+ SkPoint testXY = testSegment->activeLeftTop(true, NULL);
+ if (*topStart) {
+ if (testXY.fY < topLeft.fY) {
+ continue;
+ }
+ if (testXY.fY == topLeft.fY && testXY.fX < topLeft.fX) {
+ continue;
+ }
+ if (bestXY->fY < testXY.fY) {
+ continue;
+ }
+ if (bestXY->fY == testXY.fY && bestXY->fX < testXY.fX) {
+ continue;
+ }
+ }
+ *topStart = testSegment;
+ *bestXY = testXY;
+ }
+}
+
+SkOpSegment* SkOpContour::undoneSegment(int* start, int* end) {
+ int segmentCount = fSegments.count();
+ for (int test = 0; test < segmentCount; ++test) {
+ SkOpSegment* testSegment = &fSegments[test];
+ if (testSegment->done()) {
+ continue;
+ }
+ testSegment->undoneSpan(start, end);
+ return testSegment;
+ }
+ return NULL;
+}
+
+#if DEBUG_SHOW_WINDING
+int SkOpContour::debugShowWindingValues(int totalSegments, int ofInterest) {
+ int count = fSegments.count();
+ int sum = 0;
+ for (int index = 0; index < count; ++index) {
+ sum += fSegments[index].debugShowWindingValues(totalSegments, ofInterest);
+ }
+// SkDebugf("%s sum=%d\n", __FUNCTION__, sum);
+ return sum;
+}
+
+static void SkOpContour::debugShowWindingValues(const SkTDArray<SkOpContour*>& contourList) {
+// int ofInterest = 1 << 1 | 1 << 5 | 1 << 9 | 1 << 13;
+// int ofInterest = 1 << 4 | 1 << 8 | 1 << 12 | 1 << 16;
+ int ofInterest = 1 << 5 | 1 << 8;
+ int total = 0;
+ int index;
+ for (index = 0; index < contourList.count(); ++index) {
+ total += contourList[index]->segments().count();
+ }
+ int sum = 0;
+ for (index = 0; index < contourList.count(); ++index) {
+ sum += contourList[index]->debugShowWindingValues(total, ofInterest);
+ }
+// SkDebugf("%s total=%d\n", __FUNCTION__, sum);
+}
+#endif
+
+void SkOpContour::setBounds() {
+ int count = fSegments.count();
+ if (count == 0) {
+ SkDebugf("%s empty contour\n", __FUNCTION__);
+ SkASSERT(0);
+ // FIXME: delete empty contour?
+ return;
+ }
+ fBounds = fSegments.front().bounds();
+ for (int index = 1; index < count; ++index) {
+ fBounds.add(fSegments[index].bounds());
+ }
+}
+