aboutsummaryrefslogtreecommitdiffhomepage
path: root/src/pathops
diff options
context:
space:
mode:
Diffstat (limited to 'src/pathops')
-rw-r--r--src/pathops/SkAddIntersections.cpp3
-rwxr-xr-xsrc/pathops/SkOpCoincidence.cpp3
-rw-r--r--src/pathops/SkOpContour.cpp6
-rw-r--r--src/pathops/SkOpContour.h2
-rw-r--r--src/pathops/SkOpEdgeBuilder.cpp140
-rw-r--r--src/pathops/SkOpSegment.cpp2
-rw-r--r--src/pathops/SkPathOpsDebug.cpp2
-rw-r--r--src/pathops/SkPathOpsDebug.h4
-rw-r--r--src/pathops/SkPathOpsOp.cpp2
-rw-r--r--src/pathops/SkPathOpsTSect.h3
-rw-r--r--src/pathops/SkReduceOrder.cpp7
-rw-r--r--src/pathops/SkReduceOrder.h4
12 files changed, 117 insertions, 61 deletions
diff --git a/src/pathops/SkAddIntersections.cpp b/src/pathops/SkAddIntersections.cpp
index 2abf67a09d..b3a82cdeca 100644
--- a/src/pathops/SkAddIntersections.cpp
+++ b/src/pathops/SkAddIntersections.cpp
@@ -542,7 +542,8 @@ bool AddIntersectTs(SkOpContour* test, SkOpContour* next, SkOpCoincidence* coinc
SkTSwap(coinPtT[0], coinPtT[1]);
SkTSwap(testTAt, nextTAt);
}
- SkASSERT(coinPtT[0]->span()->t() < testTAt->span()->t());
+ SkASSERT(coincidence->globalState()->debugSkipAssert()
+ || coinPtT[0]->span()->t() < testTAt->span()->t());
if (coinPtT[0]->span()->deleted()) {
coinIndex = -1;
continue;
diff --git a/src/pathops/SkOpCoincidence.cpp b/src/pathops/SkOpCoincidence.cpp
index 1bbb82a9e0..d2874c3c5e 100755
--- a/src/pathops/SkOpCoincidence.cpp
+++ b/src/pathops/SkOpCoincidence.cpp
@@ -334,6 +334,9 @@ bool SkOpCoincidence::addEndMovedSpans(const SkOpSpan* base, const SkOpSpanBase*
}
SkOpSegment* writableSeg = const_cast<SkOpSegment*>(testSeg);
SkOpPtT* oppStart = writableSeg->addT(t);
+ if (oppStart == testPtT) {
+ continue;
+ }
SkOpSpan* writableBase = const_cast<SkOpSpan*>(base);
oppStart->span()->addOpp(writableBase);
if (oppStart->deleted()) {
diff --git a/src/pathops/SkOpContour.cpp b/src/pathops/SkOpContour.cpp
index 3b2318c306..981bd29573 100644
--- a/src/pathops/SkOpContour.cpp
+++ b/src/pathops/SkOpContour.cpp
@@ -10,7 +10,7 @@
#include "SkReduceOrder.h"
#include "SkTSort.h"
-SkOpSegment* SkOpContour::addCurve(SkPath::Verb verb, const SkPoint pts[4]) {
+SkOpSegment* SkOpContour::addCurve(SkPath::Verb verb, const SkPoint pts[4], SkScalar weight) {
SkChunkAlloc* allocator = this->globalState()->allocator();
switch (verb) {
case SkPath::kLine_Verb: {
@@ -24,7 +24,9 @@ SkOpSegment* SkOpContour::addCurve(SkPath::Verb verb, const SkPoint pts[4]) {
return appendSegment().addQuad(ptStorage, this);
} break;
case SkPath::kConic_Verb: {
- SkASSERT(0); // the original curve is a cubic, which will never reduce to a conic
+ SkPoint* ptStorage = SkOpTAllocator<SkPoint>::AllocateArray(allocator, 3);
+ memcpy(ptStorage, pts, sizeof(SkPoint) * 3);
+ return appendSegment().addConic(ptStorage, weight, this);
} break;
case SkPath::kCubic_Verb: {
SkPoint* ptStorage = SkOpTAllocator<SkPoint>::AllocateArray(allocator, 4);
diff --git a/src/pathops/SkOpContour.h b/src/pathops/SkOpContour.h
index acc6744f2a..4390fe4e1f 100644
--- a/src/pathops/SkOpContour.h
+++ b/src/pathops/SkOpContour.h
@@ -41,7 +41,7 @@ public:
appendSegment().addCubic(pts, this);
}
- SkOpSegment* addCurve(SkPath::Verb verb, const SkPoint pts[4]);
+ SkOpSegment* addCurve(SkPath::Verb verb, const SkPoint pts[4], SkScalar weight = 1);
SkOpSegment* addLine(SkPoint pts[2]) {
SkASSERT(pts[0] != pts[1]);
diff --git a/src/pathops/SkOpEdgeBuilder.cpp b/src/pathops/SkOpEdgeBuilder.cpp
index 36fc9ed161..d67ed44ddc 100644
--- a/src/pathops/SkOpEdgeBuilder.cpp
+++ b/src/pathops/SkOpEdgeBuilder.cpp
@@ -17,6 +17,26 @@ void SkOpEdgeBuilder::init() {
fSecondHalf = preFetch();
}
+// very tiny points cause numerical instability : don't allow them
+static void force_small_to_zero(SkPoint* pt) {
+ if (SkScalarAbs(pt->fX) < FLT_EPSILON_ORDERABLE_ERR) {
+ pt->fX = 0;
+ }
+ if (SkScalarAbs(pt->fY) < FLT_EPSILON_ORDERABLE_ERR) {
+ pt->fY = 0;
+ }
+}
+
+static bool can_add_curve(SkPath::Verb verb, SkPoint* curve) {
+ if (SkPath::kMove_Verb == verb) {
+ return false;
+ }
+ for (int index = 0; index < SkPathOpsVerbToPoints(verb); ++index) {
+ force_small_to_zero(&curve[index]);
+ }
+ return SkPath::kLine_Verb != verb || !SkDPoint::ApproximatelyEqual(curve[0], curve[1]);
+}
+
void SkOpEdgeBuilder::addOperand(const SkPath& path) {
SkASSERT(fPathVerbs.count() > 0 && fPathVerbs.end()[-1] == SkPath::kDone_Verb);
fPathVerbs.pop();
@@ -48,16 +68,6 @@ void SkOpEdgeBuilder::closeContour(const SkPoint& curveEnd, const SkPoint& curve
*fPathVerbs.append() = SkPath::kClose_Verb;
}
-// very tiny points cause numerical instability : don't allow them
-static void force_small_to_zero(SkPoint* pt) {
- if (SkScalarAbs(pt->fX) < FLT_EPSILON_ORDERABLE_ERR) {
- pt->fX = 0;
- }
- if (SkScalarAbs(pt->fY) < FLT_EPSILON_ORDERABLE_ERR) {
- pt->fY = 0;
- }
-}
-
int SkOpEdgeBuilder::preFetch() {
if (!fPath->isFinite()) {
fUnparseable = true;
@@ -107,8 +117,10 @@ int SkOpEdgeBuilder::preFetch() {
force_small_to_zero(&pts[2]);
curve[1] = pts[1];
curve[2] = pts[2];
- verb = SkReduceOrder::Conic(curve, iter.conicWeight(), pts);
- if (verb == SkPath::kMove_Verb) {
+ verb = SkReduceOrder::Quad(curve, pts);
+ if (SkPath::kQuad_Verb == verb && 1 != iter.conicWeight()) {
+ verb = SkPath::kConic_Verb;
+ } else if (verb == SkPath::kMove_Verb) {
continue; // skip degenerate points
}
break;
@@ -183,49 +195,83 @@ bool SkOpEdgeBuilder::walk() {
fCurrentContour->addLine(pointsPtr);
break;
case SkPath::kQuad_Verb:
- fCurrentContour->addQuad(pointsPtr);
- break;
- case SkPath::kConic_Verb:
- fCurrentContour->addConic(pointsPtr, *weightPtr++);
- break;
- case SkPath::kCubic_Verb: {
- // Split complex cubics (such as self-intersecting curves or
- // ones with difficult curvature) in two before proceeding.
- // This can be required for intersection to succeed.
- SkScalar splitT;
- if (SkDCubic::ComplexBreak(pointsPtr, &splitT)) {
- SkPoint cubicPair[7];
- SkChopCubicAt(pointsPtr, cubicPair, splitT);
- if (!SkScalarsAreFinite(&cubicPair[0].fX, SK_ARRAY_COUNT(cubicPair) * 2)) {
- return false;
- }
- SkPoint cStorage[2][4];
- SkPath::Verb v1 = SkReduceOrder::Cubic(&cubicPair[0], cStorage[0]);
- SkPath::Verb v2 = SkReduceOrder::Cubic(&cubicPair[3], cStorage[1]);
- if (v1 != SkPath::kMove_Verb && v2 != SkPath::kMove_Verb) {
- SkPoint* curve1 = v1 == SkPath::kCubic_Verb ? &cubicPair[0] : cStorage[0];
- SkPoint* curve2 = v2 == SkPath::kCubic_Verb ? &cubicPair[3] : cStorage[1];
- for (int index = 0; index < SkPathOpsVerbToPoints(v1); ++index) {
- force_small_to_zero(&curve1[index]);
+ {
+ SkVector v1 = pointsPtr[1] - pointsPtr[0];
+ SkVector v2 = pointsPtr[2] - pointsPtr[1];
+ if (v1.dot(v2) < 0) {
+ SkPoint pair[5];
+ if (SkChopQuadAtMaxCurvature(pointsPtr, pair) == 1) {
+ goto addOneQuad;
}
- for (int index = 0; index < SkPathOpsVerbToPoints(v2); ++index) {
- force_small_to_zero(&curve2[index]);
+ if (!SkScalarsAreFinite(&pair[0].fX, SK_ARRAY_COUNT(pair) * 2)) {
+ return false;
}
- if (SkPath::kLine_Verb != v1 ||
- !SkDPoint::ApproximatelyEqual(curve1[0], curve1[1])) {
+ SkPoint cStorage[2][2];
+ SkPath::Verb v1 = SkReduceOrder::Quad(&pair[0], cStorage[0]);
+ SkPath::Verb v2 = SkReduceOrder::Quad(&pair[2], cStorage[1]);
+ SkPoint* curve1 = v1 == SkPath::kQuad_Verb ? &pair[0] : cStorage[0];
+ SkPoint* curve2 = v2 == SkPath::kQuad_Verb ? &pair[2] : cStorage[1];
+ if (can_add_curve(v1, curve1) && can_add_curve(v2, curve2)) {
fCurrentContour->addCurve(v1, curve1);
- }
- if (SkPath::kLine_Verb != v2 ||
- !SkDPoint::ApproximatelyEqual(curve2[0], curve2[1])) {
fCurrentContour->addCurve(v2, curve2);
+ break;
}
- } else {
- fCurrentContour->addCubic(pointsPtr);
}
- } else {
- fCurrentContour->addCubic(pointsPtr);
}
+ addOneQuad:
+ fCurrentContour->addQuad(pointsPtr);
+ break;
+ case SkPath::kConic_Verb: {
+ SkVector v1 = pointsPtr[1] - pointsPtr[0];
+ SkVector v2 = pointsPtr[2] - pointsPtr[1];
+ SkScalar weight = *weightPtr++;
+ if (v1.dot(v2) < 0) {
+ // FIXME: max curvature for conics hasn't been implemented; use placeholder
+ SkScalar maxCurvature = SkFindQuadMaxCurvature(pointsPtr);
+ if (maxCurvature > 0) {
+ SkConic conic(pointsPtr, weight);
+ SkConic pair[2];
+ conic.chopAt(maxCurvature, pair);
+ SkPoint cStorage[2][3];
+ SkPath::Verb v1 = SkReduceOrder::Conic(pair[0], cStorage[0]);
+ SkPath::Verb v2 = SkReduceOrder::Conic(pair[1], cStorage[1]);
+ SkPoint* curve1 = v1 == SkPath::kConic_Verb ? pair[0].fPts : cStorage[0];
+ SkPoint* curve2 = v2 == SkPath::kConic_Verb ? pair[1].fPts : cStorage[1];
+ if (can_add_curve(v1, curve1) && can_add_curve(v2, curve2)) {
+ fCurrentContour->addCurve(v1, curve1, pair[0].fW);
+ fCurrentContour->addCurve(v2, curve2, pair[1].fW);
+ break;
+ }
+ }
+ }
+ fCurrentContour->addConic(pointsPtr, weight);
} break;
+ case SkPath::kCubic_Verb:
+ {
+ // Split complex cubics (such as self-intersecting curves or
+ // ones with difficult curvature) in two before proceeding.
+ // This can be required for intersection to succeed.
+ SkScalar splitT;
+ if (SkDCubic::ComplexBreak(pointsPtr, &splitT)) {
+ SkPoint pair[7];
+ SkChopCubicAt(pointsPtr, pair, splitT);
+ if (!SkScalarsAreFinite(&pair[0].fX, SK_ARRAY_COUNT(pair) * 2)) {
+ return false;
+ }
+ SkPoint cStorage[2][4];
+ SkPath::Verb v1 = SkReduceOrder::Cubic(&pair[0], cStorage[0]);
+ SkPath::Verb v2 = SkReduceOrder::Cubic(&pair[3], cStorage[1]);
+ SkPoint* curve1 = v1 == SkPath::kCubic_Verb ? &pair[0] : cStorage[0];
+ SkPoint* curve2 = v2 == SkPath::kCubic_Verb ? &pair[3] : cStorage[1];
+ if (can_add_curve(v1, curve1) && can_add_curve(v2, curve2)) {
+ fCurrentContour->addCurve(v1, curve1);
+ fCurrentContour->addCurve(v2, curve2);
+ break;
+ }
+ }
+ }
+ fCurrentContour->addCubic(pointsPtr);
+ break;
case SkPath::kClose_Verb:
SkASSERT(fCurrentContour);
if (!close()) {
diff --git a/src/pathops/SkOpSegment.cpp b/src/pathops/SkOpSegment.cpp
index 1a965c2474..9ab240d2cb 100644
--- a/src/pathops/SkOpSegment.cpp
+++ b/src/pathops/SkOpSegment.cpp
@@ -249,7 +249,7 @@ SkOpPtT* SkOpSegment::addT(double t) {
SkOpSpanBase* spanBase = &fHead;
do {
SkOpPtT* result = spanBase->ptT();
- if (t == result->fT || this->match(result, this, t, pt)) {
+ if (t == result->fT || (!zero_or_one(t) && this->match(result, this, t, pt))) {
spanBase->bumpSpanAdds();
return result;
}
diff --git a/src/pathops/SkPathOpsDebug.cpp b/src/pathops/SkPathOpsDebug.cpp
index 67bcee4070..5326addf8d 100644
--- a/src/pathops/SkPathOpsDebug.cpp
+++ b/src/pathops/SkPathOpsDebug.cpp
@@ -1876,7 +1876,7 @@ static void DebugValidate(const SkOpSpanBase* next, const SkOpSpanBase* end,
do {
const SkOpPtT* ptT = next->ptT();
int index = 0;
- bool somethingBetween;
+ bool somethingBetween = false;
do {
++index;
ptT = ptT->next();
diff --git a/src/pathops/SkPathOpsDebug.h b/src/pathops/SkPathOpsDebug.h
index e390b91b56..f0e384a7e3 100644
--- a/src/pathops/SkPathOpsDebug.h
+++ b/src/pathops/SkPathOpsDebug.h
@@ -19,6 +19,8 @@
#define FORCE_RELEASE 1 // set force release to 1 for multiple thread -- no debugging
#endif
+#define DEBUG_UNDER_DEVELOPMENT 1
+
#define ONE_OFF_DEBUG 0
#define ONE_OFF_DEBUG_MATHEMATICA 0
@@ -37,8 +39,6 @@
if (!SkPathOpsDebug::ValidWind(x)) strcpy(x##Str, "?"); \
else SK_SNPRINTF(x##Str, sizeof(x##Str), "%d", x)
-#define DEBUG_UNDER_DEVELOPMENT 1
-
#if FORCE_RELEASE
#define DEBUG_ACTIVE_OP 0
diff --git a/src/pathops/SkPathOpsOp.cpp b/src/pathops/SkPathOpsOp.cpp
index 0f4415bec1..d34c0579e4 100644
--- a/src/pathops/SkPathOpsOp.cpp
+++ b/src/pathops/SkPathOpsOp.cpp
@@ -207,7 +207,7 @@ static void dump_path(FILE* file, const SkPath& path, bool force, bool dumpAsHex
SkDynamicMemoryWStream wStream;
path.dump(&wStream, force, dumpAsHex);
sk_sp<SkData> data(wStream.detachAsData());
- fprintf(file, "%.*s\n", (int) data->size(), data->data());
+ fprintf(file, "%.*s\n", (int) data->size(), (char*) data->data());
}
static int dumpID = 0;
diff --git a/src/pathops/SkPathOpsTSect.h b/src/pathops/SkPathOpsTSect.h
index 6ae6ee528f..f84aaaa6b7 100644
--- a/src/pathops/SkPathOpsTSect.h
+++ b/src/pathops/SkPathOpsTSect.h
@@ -1531,7 +1531,8 @@ int SkTSect<TCurve, OppCurve>::linesIntersect(SkTSpan<TCurve, OppCurve>* span,
workT += tStep;
workPt = fCurve.ptAtT(workT);
coinW.setPerp(fCurve, workT, workPt, opp->fCurve);
- if (coinW.perpT() < 0) {
+ double perpT = coinW.perpT();
+ if (coinW.isCoincident() ? !between(oppSpan->fStartT, perpT, oppSpan->fEndT) : perpT < 0) {
continue;
}
SkDVector perpW = workPt - coinW.perpPt();
diff --git a/src/pathops/SkReduceOrder.cpp b/src/pathops/SkReduceOrder.cpp
index 48624baee9..7f7ea11d3b 100644
--- a/src/pathops/SkReduceOrder.cpp
+++ b/src/pathops/SkReduceOrder.cpp
@@ -4,6 +4,7 @@
* Use of this source code is governed by a BSD-style license that can be
* found in the LICENSE file.
*/
+#include "SkGeometry.h"
#include "SkReduceOrder.h"
int SkReduceOrder::reduce(const SkDLine& line) {
@@ -255,9 +256,9 @@ SkPath::Verb SkReduceOrder::Quad(const SkPoint a[3], SkPoint* reducePts) {
return SkPathOpsPointsToVerb(order - 1);
}
-SkPath::Verb SkReduceOrder::Conic(const SkPoint a[3], SkScalar weight, SkPoint* reducePts) {
- SkPath::Verb verb = SkReduceOrder::Quad(a, reducePts);
- if (verb > SkPath::kLine_Verb && weight == 1) {
+SkPath::Verb SkReduceOrder::Conic(const SkConic& c, SkPoint* reducePts) {
+ SkPath::Verb verb = SkReduceOrder::Quad(c.fPts, reducePts);
+ if (verb > SkPath::kLine_Verb && c.fW == 1) {
return SkPath::kQuad_Verb;
}
return verb == SkPath::kQuad_Verb ? SkPath::kConic_Verb : verb;
diff --git a/src/pathops/SkReduceOrder.h b/src/pathops/SkReduceOrder.h
index e9e4090deb..7efb71d4fe 100644
--- a/src/pathops/SkReduceOrder.h
+++ b/src/pathops/SkReduceOrder.h
@@ -11,6 +11,8 @@
#include "SkPathOpsLine.h"
#include "SkPathOpsQuad.h"
+struct SkConic;
+
union SkReduceOrder {
enum Quadratics {
kNo_Quadratics,
@@ -21,7 +23,7 @@ union SkReduceOrder {
int reduce(const SkDLine& line);
int reduce(const SkDQuad& quad);
- static SkPath::Verb Conic(const SkPoint pts[3], SkScalar weight, SkPoint* reducePts);
+ static SkPath::Verb Conic(const SkConic& conic, SkPoint* reducePts);
static SkPath::Verb Cubic(const SkPoint pts[4], SkPoint* reducePts);
static SkPath::Verb Quad(const SkPoint pts[3], SkPoint* reducePts);
generated by cgit v1.2.3 (git 2.39.1) at 2024-12-15 15:48:07 +0000