Chromium Code Reviews
chromiumcodereview-hr@appspot.gserviceaccount.com (chromiumcodereview-hr) | Please choose your nickname with Settings | Help | Chromium Project | Gerrit Changes | Sign out
(845)

Issues Search
    My Issues | Starred     Open | Closed | All

Unified Diff: src/pathops/SkAddIntersections.cpp

Issue 13094010: Add implementation of path ops (Closed) Base URL: http://skia.googlecode.com/svn/trunk/
Patch Set: Created 7 years, 9 months ago
Use n/p to move between diff chunks; N/P to move between comments. Draft comments are only viewable by you.
Jump to:
View side-by-side diff with in-line comments
Download patch
« no previous file with comments | « src/pathops/SkAddIntersections.h ('k') | src/pathops/SkIntersectionHelper.h » ('j') | no next file with comments »
Expand Comments ('e') | Collapse Comments ('c') | Show Comments Hide Comments ('s')
Index: src/pathops/SkAddIntersections.cpp
===================================================================
--- src/pathops/SkAddIntersections.cpp (revision 0)
+++ src/pathops/SkAddIntersections.cpp (revision 0)
@@ -0,0 +1,433 @@
+/*
+ * 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 "SkPathOpsBounds.h"
+
+#if DEBUG_ADD_INTERSECTING_TS
+
+static void debugShowLineIntersection(int pts, const SkIntersectionHelper& wt,
+ const SkIntersectionHelper& wn, const SkIntersections& i) {
+ SkASSERT(i.used() == pts);
+ if (!pts) {
+ SkDebugf("%s no intersect " LINE_DEBUG_STR " " LINE_DEBUG_STR "\n",
+ __FUNCTION__, LINE_DEBUG_DATA(wt.pts()), LINE_DEBUG_DATA(wn.pts()));
+ return;
+ }
+ SkDebugf("%s " T_DEBUG_STR(wtTs, 0) " " LINE_DEBUG_STR " " PT_DEBUG_STR, __FUNCTION__,
+ i[0][0], LINE_DEBUG_DATA(wt.pts()), PT_DEBUG_DATA(i, 0));
+ if (pts == 2) {
+ SkDebugf(" " T_DEBUG_STR(wtTs, 1) " " PT_DEBUG_STR, i[0][1], PT_DEBUG_DATA(i, 1));
+ }
+ SkDebugf(" wnTs[0]=%g " LINE_DEBUG_STR, i[1][0], LINE_DEBUG_DATA(wn.pts()));
+ if (pts == 2) {
+ SkDebugf(" " T_DEBUG_STR(wnTs, 1), i[1][1]);
+ }
+ SkDebugf("\n");
+}
+
+static void debugShowQuadLineIntersection(int pts, const SkIntersectionHelper& wt,
+ const SkIntersectionHelper& wn,
+ const SkIntersections& i) {
+ SkASSERT(i.used() == pts);
+ if (!pts) {
+ SkDebugf("%s no intersect " QUAD_DEBUG_STR " " LINE_DEBUG_STR "\n",
+ __FUNCTION__, QUAD_DEBUG_DATA(wt.pts()), LINE_DEBUG_DATA(wn.pts()));
+ return;
+ }
+ SkDebugf("%s " T_DEBUG_STR(wtTs, 0) " " QUAD_DEBUG_STR " " PT_DEBUG_STR, __FUNCTION__,
+ i[0][0], QUAD_DEBUG_DATA(wt.pts()), PT_DEBUG_DATA(i, 0));
+ for (int n = 1; n < pts; ++n) {
+ SkDebugf(" " TX_DEBUG_STR(wtTs) " " PT_DEBUG_STR, n, i[0][n], PT_DEBUG_DATA(i, n));
+ }
+ SkDebugf(" wnTs[0]=%g " LINE_DEBUG_STR, i[1][0], LINE_DEBUG_DATA(wn.pts()));
+ for (int n = 1; n < pts; ++n) {
+ SkDebugf(" " TX_DEBUG_STR(wnTs), n, i[1][n]);
+ }
+ SkDebugf("\n");
+}
+
+static void debugShowQuadIntersection(int pts, const SkIntersectionHelper& wt,
+ const SkIntersectionHelper& wn, const SkIntersections& i) {
+ SkASSERT(i.used() == pts);
+ if (!pts) {
+ SkDebugf("%s no intersect " QUAD_DEBUG_STR " " QUAD_DEBUG_STR "\n",
+ __FUNCTION__, QUAD_DEBUG_DATA(wt.pts()), QUAD_DEBUG_DATA(wn.pts()));
+ return;
+ }
+ SkDebugf("%s " T_DEBUG_STR(wtTs, 0) " " QUAD_DEBUG_STR " " PT_DEBUG_STR, __FUNCTION__,
+ i[0][0], QUAD_DEBUG_DATA(wt.pts()), PT_DEBUG_DATA(i, 0));
+ for (int n = 1; n < pts; ++n) {
+ SkDebugf(" " TX_DEBUG_STR(wtTs) " " PT_DEBUG_STR, n, i[0][n], PT_DEBUG_DATA(i, n));
+ }
+ SkDebugf(" wnTs[0]=%g " QUAD_DEBUG_STR, i[1][0], QUAD_DEBUG_DATA(wn.pts()));
+ for (int n = 1; n < pts; ++n) {
+ SkDebugf(" " TX_DEBUG_STR(wnTs), n, i[1][n]);
+ }
+ SkDebugf("\n");
+}
+
+static void debugShowCubicLineIntersection(int pts, const SkIntersectionHelper& wt,
+ const SkIntersectionHelper& wn, const SkIntersections& i) {
+ SkASSERT(i.used() == pts);
+ if (!pts) {
+ SkDebugf("%s no intersect " CUBIC_DEBUG_STR " " LINE_DEBUG_STR "\n",
+ __FUNCTION__, CUBIC_DEBUG_DATA(wt.pts()), LINE_DEBUG_DATA(wn.pts()));
+ return;
+ }
+ SkDebugf("%s " T_DEBUG_STR(wtTs, 0) " " CUBIC_DEBUG_STR " " PT_DEBUG_STR, __FUNCTION__,
+ i[0][0], CUBIC_DEBUG_DATA(wt.pts()), PT_DEBUG_DATA(i, 0));
+ for (int n = 1; n < pts; ++n) {
+ SkDebugf(" " TX_DEBUG_STR(wtTs) " " PT_DEBUG_STR, n, i[0][n], PT_DEBUG_DATA(i, n));
+ }
+ SkDebugf(" wnTs[0]=%g " LINE_DEBUG_STR, i[1][0], LINE_DEBUG_DATA(wn.pts()));
+ for (int n = 1; n < pts; ++n) {
+ SkDebugf(" " TX_DEBUG_STR(wnTs), n, i[1][n]);
+ }
+ SkDebugf("\n");
+}
+
+static void debugShowCubicQuadIntersection(int pts, const SkIntersectionHelper& wt,
+ const SkIntersectionHelper& wn, const SkIntersections& i) {
+ SkASSERT(i.used() == pts);
+ if (!pts) {
+ SkDebugf("%s no intersect " CUBIC_DEBUG_STR " " QUAD_DEBUG_STR "\n",
+ __FUNCTION__, CUBIC_DEBUG_DATA(wt.pts()), QUAD_DEBUG_DATA(wn.pts()));
+ return;
+ }
+ SkDebugf("%s " T_DEBUG_STR(wtTs, 0) " " CUBIC_DEBUG_STR " " PT_DEBUG_STR, __FUNCTION__,
+ i[0][0], CUBIC_DEBUG_DATA(wt.pts()), PT_DEBUG_DATA(i, 0));
+ for (int n = 1; n < pts; ++n) {
+ SkDebugf(" " TX_DEBUG_STR(wtTs) " " PT_DEBUG_STR, n, i[0][n], PT_DEBUG_DATA(i, n));
+ }
+ SkDebugf(" wnTs[0]=%g " QUAD_DEBUG_STR, i[1][0], QUAD_DEBUG_DATA(wn.pts()));
+ for (int n = 1; n < pts; ++n) {
+ SkDebugf(" " TX_DEBUG_STR(wnTs), n, i[1][n]);
+ }
+ SkDebugf("\n");
+}
+
+static void debugShowCubicIntersection(int pts, const SkIntersectionHelper& wt,
+ const SkIntersectionHelper& wn, const SkIntersections& i) {
+ SkASSERT(i.used() == pts);
+ if (!pts) {
+ SkDebugf("%s no intersect " CUBIC_DEBUG_STR " " CUBIC_DEBUG_STR "\n",
+ __FUNCTION__, CUBIC_DEBUG_DATA(wt.pts()), CUBIC_DEBUG_DATA(wn.pts()));
+ return;
+ }
+ SkDebugf("%s " T_DEBUG_STR(wtTs, 0) " " CUBIC_DEBUG_STR " " PT_DEBUG_STR, __FUNCTION__,
+ i[0][0], CUBIC_DEBUG_DATA(wt.pts()), PT_DEBUG_DATA(i, 0));
+ for (int n = 1; n < pts; ++n) {
+ SkDebugf(" " TX_DEBUG_STR(wtTs) " " PT_DEBUG_STR, n, i[0][n], PT_DEBUG_DATA(i, n));
+ }
+ SkDebugf(" wnTs[0]=%g " CUBIC_DEBUG_STR, i[1][0], CUBIC_DEBUG_DATA(wn.pts()));
+ for (int n = 1; n < pts; ++n) {
+ SkDebugf(" " TX_DEBUG_STR(wnTs), n, i[1][n]);
+ }
+ SkDebugf("\n");
+}
+
+static void debugShowCubicIntersection(int pts, const SkIntersectionHelper& wt, const SkIntersections& i) {
+ SkASSERT(i.used() == pts);
+ if (!pts) {
+ SkDebugf("%s no self intersect " CUBIC_DEBUG_STR "\n", __FUNCTION__,
+ CUBIC_DEBUG_DATA(wt.pts()));
+ return;
+ }
+ SkDebugf("%s " T_DEBUG_STR(wtTs, 0) " " CUBIC_DEBUG_STR " " PT_DEBUG_STR, __FUNCTION__,
+ i[0][0], CUBIC_DEBUG_DATA(wt.pts()), PT_DEBUG_DATA(i, 0));
+ SkDebugf(" " T_DEBUG_STR(wtTs, 1), i[1][0]);
+ SkDebugf("\n");
+}
+
+#else
+static void debugShowLineIntersection(int , const SkIntersectionHelper& , const SkIntersectionHelper& , const SkIntersections& ) {
+}
+
+static void debugShowQuadLineIntersection(int , const SkIntersectionHelper& , const SkIntersectionHelper& , const SkIntersections& ) {
+}
+
+static void debugShowQuadIntersection(int , const SkIntersectionHelper& , const SkIntersectionHelper& , const SkIntersections& ) {
+}
+
+static void debugShowCubicLineIntersection(int , const SkIntersectionHelper& , const SkIntersectionHelper& ,
+ const SkIntersections& ) {
+}
+
+static void debugShowCubicQuadIntersection(int , const SkIntersectionHelper& , const SkIntersectionHelper& ,
+ const SkIntersections& ) {
+}
+
+static void debugShowCubicIntersection(int , const SkIntersectionHelper& , const SkIntersectionHelper& , const SkIntersections& ) {
+}
+
+static void debugShowCubicIntersection(int , const SkIntersectionHelper& , const SkIntersections& ) {
+}
+#endif
+
+bool AddIntersectTs(SkOpContour* test, SkOpContour* next) {
+
+ if (test != next) {
+ if (test->bounds().fBottom < next->bounds().fTop) {
+ return false;
+ }
+ if (!SkPathOpsBounds::Intersects(test->bounds(), next->bounds())) {
+ return true;
+ }
+ }
+ SkIntersectionHelper wt;
+ wt.init(test);
+ bool foundCommonContour = test == next;
+ do {
+ SkIntersectionHelper wn;
+ wn.init(next);
+ if (test == next && !wn.startAfter(wt)) {
+ continue;
+ }
+ do {
+ if (!SkPathOpsBounds::Intersects(wt.bounds(), wn.bounds())) {
+ continue;
+ }
+ int pts;
+ SkIntersections ts;
+ bool swap = false;
+ switch (wt.segmentType()) {
+ case SkIntersectionHelper::kHorizontalLine_Segment:
+ swap = true;
+ switch (wn.segmentType()) {
+ case SkIntersectionHelper::kHorizontalLine_Segment:
+ case SkIntersectionHelper::kVerticalLine_Segment:
+ case SkIntersectionHelper::kLine_Segment: {
+ pts = ts.lineHorizontal(wn.pts(), wt.left(),
+ wt.right(), wt.y(), wt.xFlipped());
+ debugShowLineIntersection(pts, wt, wn, ts);
+ break;
+ }
+ case SkIntersectionHelper::kQuad_Segment: {
+ pts = ts.quadHorizontal(wn.pts(), wt.left(),
+ wt.right(), wt.y(), wt.xFlipped());
+ debugShowQuadLineIntersection(pts, wn, wt, ts);
+ break;
+ }
+ case SkIntersectionHelper::kCubic_Segment: {
+ pts = ts.cubicHorizontal(wn.pts(), wt.left(),
+ wt.right(), wt.y(), wt.xFlipped());
+ debugShowCubicLineIntersection(pts, wn, wt, ts);
+ break;
+ }
+ default:
+ SkASSERT(0);
+ }
+ break;
+ case SkIntersectionHelper::kVerticalLine_Segment:
+ swap = true;
+ switch (wn.segmentType()) {
+ case SkIntersectionHelper::kHorizontalLine_Segment:
+ case SkIntersectionHelper::kVerticalLine_Segment:
+ case SkIntersectionHelper::kLine_Segment: {
+ pts = ts.lineVertical(wn.pts(), wt.top(),
+ wt.bottom(), wt.x(), wt.yFlipped());
+ debugShowLineIntersection(pts, wt, wn, ts);
+ break;
+ }
+ case SkIntersectionHelper::kQuad_Segment: {
+ pts = ts.quadVertical(wn.pts(), wt.top(),
+ wt.bottom(), wt.x(), wt.yFlipped());
+ debugShowQuadLineIntersection(pts, wn, wt, ts);
+ break;
+ }
+ case SkIntersectionHelper::kCubic_Segment: {
+ pts = ts.cubicVertical(wn.pts(), wt.top(),
+ wt.bottom(), wt.x(), wt.yFlipped());
+ debugShowCubicLineIntersection(pts, wn, wt, ts);
+ break;
+ }
+ default:
+ SkASSERT(0);
+ }
+ break;
+ case SkIntersectionHelper::kLine_Segment:
+ switch (wn.segmentType()) {
+ case SkIntersectionHelper::kHorizontalLine_Segment:
+ pts = ts.lineHorizontal(wt.pts(), wn.left(),
+ wn.right(), wn.y(), wn.xFlipped());
+ debugShowLineIntersection(pts, wt, wn, ts);
+ break;
+ case SkIntersectionHelper::kVerticalLine_Segment:
+ pts = ts.lineVertical(wt.pts(), wn.top(),
+ wn.bottom(), wn.x(), wn.yFlipped());
+ debugShowLineIntersection(pts, wt, wn, ts);
+ break;
+ case SkIntersectionHelper::kLine_Segment: {
+ pts = ts.lineLine(wt.pts(), wn.pts());
+ debugShowLineIntersection(pts, wt, wn, ts);
+ break;
+ }
+ case SkIntersectionHelper::kQuad_Segment: {
+ swap = true;
+ pts = ts.quadLine(wn.pts(), wt.pts());
+ debugShowQuadLineIntersection(pts, wn, wt, ts);
+ break;
+ }
+ case SkIntersectionHelper::kCubic_Segment: {
+ swap = true;
+ pts = ts.cubicLine(wn.pts(), wt.pts());
+ debugShowCubicLineIntersection(pts, wn, wt, ts);
+ break;
+ }
+ default:
+ SkASSERT(0);
+ }
+ break;
+ case SkIntersectionHelper::kQuad_Segment:
+ switch (wn.segmentType()) {
+ case SkIntersectionHelper::kHorizontalLine_Segment:
+ pts = ts.quadHorizontal(wt.pts(), wn.left(),
+ wn.right(), wn.y(), wn.xFlipped());
+ debugShowQuadLineIntersection(pts, wt, wn, ts);
+ break;
+ case SkIntersectionHelper::kVerticalLine_Segment:
+ pts = ts.quadVertical(wt.pts(), wn.top(),
+ wn.bottom(), wn.x(), wn.yFlipped());
+ debugShowQuadLineIntersection(pts, wt, wn, ts);
+ break;
+ case SkIntersectionHelper::kLine_Segment: {
+ pts = ts.quadLine(wt.pts(), wn.pts());
+ debugShowQuadLineIntersection(pts, wt, wn, ts);
+ break;
+ }
+ case SkIntersectionHelper::kQuad_Segment: {
+ pts = ts.quadQuad(wt.pts(), wn.pts());
+ debugShowQuadIntersection(pts, wt, wn, ts);
+ break;
+ }
+ case SkIntersectionHelper::kCubic_Segment: {
+ swap = true;
+ pts = ts.cubicQuad(wn.pts(), wt.pts());
+ debugShowCubicQuadIntersection(pts, wn, wt, ts);
+ break;
+ }
+ default:
+ SkASSERT(0);
+ }
+ break;
+ case SkIntersectionHelper::kCubic_Segment:
+ switch (wn.segmentType()) {
+ case SkIntersectionHelper::kHorizontalLine_Segment:
+ pts = ts.cubicHorizontal(wt.pts(), wn.left(),
+ wn.right(), wn.y(), wn.xFlipped());
+ debugShowCubicLineIntersection(pts, wt, wn, ts);
+ break;
+ case SkIntersectionHelper::kVerticalLine_Segment:
+ pts = ts.cubicVertical(wt.pts(), wn.top(),
+ wn.bottom(), wn.x(), wn.yFlipped());
+ debugShowCubicLineIntersection(pts, wt, wn, ts);
+ break;
+ case SkIntersectionHelper::kLine_Segment: {
+ pts = ts.cubicLine(wt.pts(), wn.pts());
+ debugShowCubicLineIntersection(pts, wt, wn, ts);
+ break;
+ }
+ case SkIntersectionHelper::kQuad_Segment: {
+ pts = ts.cubicQuad(wt.pts(), wn.pts());
+ debugShowCubicQuadIntersection(pts, wt, wn, ts);
+ break;
+ }
+ case SkIntersectionHelper::kCubic_Segment: {
+ pts = ts.cubicCubic(wt.pts(), wn.pts());
+ debugShowCubicIntersection(pts, wt, wn, ts);
+ break;
+ }
+ default:
+ SkASSERT(0);
+ }
+ break;
+ default:
+ SkASSERT(0);
+ }
+ if (!foundCommonContour && pts > 0) {
+ test->addCross(next);
+ next->addCross(test);
+ foundCommonContour = true;
+ }
+ // in addition to recording T values, record matching segment
+ if (pts == 2) {
+ if (wn.segmentType() <= SkIntersectionHelper::kLine_Segment
+ && wt.segmentType() <= SkIntersectionHelper::kLine_Segment) {
+ wt.addCoincident(wn, ts, swap);
+ continue;
+ }
+ if (wn.segmentType() >= SkIntersectionHelper::kQuad_Segment
+ && wt.segmentType() >= SkIntersectionHelper::kQuad_Segment
+ && ts.isCoincident(0)) {
+ SkASSERT(ts.coincidentUsed() == 2);
+ wt.addCoincident(wn, ts, swap);
+ continue;
+ }
+
+ }
+ for (int pt = 0; pt < pts; ++pt) {
+ SkASSERT(ts[0][pt] >= 0 && ts[0][pt] <= 1);
+ SkASSERT(ts[1][pt] >= 0 && ts[1][pt] <= 1);
+ SkPoint point = ts.pt(pt).asSkPoint();
+ int testTAt = wt.addT(wn, point, ts[swap][pt]);
+ int nextTAt = wn.addT(wt, point, ts[!swap][pt]);
+ wt.addOtherT(testTAt, ts[!swap][pt], nextTAt);
+ wn.addOtherT(nextTAt, ts[swap][pt], testTAt);
+ }
+ } while (wn.advance());
+ } while (wt.advance());
+ return true;
+}
+
+void AddSelfIntersectTs(SkOpContour* test) {
+ SkIntersectionHelper wt;
+ wt.init(test);
+ do {
+ if (wt.segmentType() != SkIntersectionHelper::kCubic_Segment) {
+ continue;
+ }
+ SkIntersections ts;
+ int pts = ts.cubic(wt.pts());
+ debugShowCubicIntersection(pts, wt, ts);
+ if (!pts) {
+ continue;
+ }
+ SkASSERT(pts == 1);
+ SkASSERT(ts[0][0] >= 0 && ts[0][0] <= 1);
+ SkASSERT(ts[1][0] >= 0 && ts[1][0] <= 1);
+ SkPoint point = ts.pt(0).asSkPoint();
+ int testTAt = wt.addSelfT(wt, point, ts[0][0]);
+ int nextTAt = wt.addT(wt, point, ts[1][0]);
+ wt.addOtherT(testTAt, ts[1][0], nextTAt);
+ wt.addOtherT(nextTAt, ts[0][0], testTAt);
+ } while (wt.advance());
+}
+
+// resolve any coincident pairs found while intersecting, and
+// see if coincidence is formed by clipping non-concident segments
+void CoincidenceCheck(SkTDArray<SkOpContour*>& contourList, int total) {
+ int contourCount = contourList.count();
+#if ONE_PASS_COINCIDENCE_CHECK
+ for (int cIndex = 0; cIndex < contourCount; ++cIndex) {
+ SkOpContour* contour = contourList[cIndex];
+ contour->resolveCoincidence(contourList);
+ }
+#else
+ for (int cIndex = 0; cIndex < contourCount; ++cIndex) {
+ SkOpContour* contour = contourList[cIndex];
+ contour->addCoincidentPoints();
+ }
+ for (int cIndex = 0; cIndex < contourCount; ++cIndex) {
+ SkOpContour* contour = contourList[cIndex];
+ contour->calcCoincidentWinding();
+ }
+#endif
+ for (int cIndex = 0; cIndex < contourCount; ++cIndex) {
+ SkOpContour* contour = contourList[cIndex];
+ contour->findTooCloseToCall();
+ }
+}
« no previous file with comments | « src/pathops/SkAddIntersections.h ('k') | src/pathops/SkIntersectionHelper.h » ('j') | no next file with comments »

Powered by Google App Engine
This is Rietveld 408576698