remove pathop template
(fixing msan/asan/ubsan failure)
Pathops used templates for curve intersection.
Since only one template is required if curves share
an abstract base, remove the template altogether.
This makes the code easier to read, and incidentally
makes it slightly smaller and much faster.
This also removes debugging code specific to templates,
and removes Simplify code which isn't covered by tests
or fuzz.
This shaves the execution time of
pathops_unittest -V -x from 6m to 3m23s.
R=kjlubick@google.com
Bug: skia:
Change-Id: I3392df98244083d0327ce9c787dfe24d326ef4ed
Reviewed-on: https://skia-review.googlesource.com/c/162742
Commit-Queue: Cary Clark <caryclark@skia.org>
Reviewed-by: Kevin Lubick <kjlubick@google.com>
diff --git a/src/pathops/SkIntersections.h b/src/pathops/SkIntersections.h
index fe70284..9a7cdd0 100644
--- a/src/pathops/SkIntersections.h
+++ b/src/pathops/SkIntersections.h
@@ -269,11 +269,10 @@
int intersectRay(const SkDQuad&, const SkDLine&);
int intersectRay(const SkDConic&, const SkDLine&);
int intersectRay(const SkDCubic&, const SkDLine&);
-#if PATH_OP_COMPILE_FOR_SIZE
int intersectRay(const SkTCurve& tCurve, const SkDLine& line) {
return tCurve.intersectRay(this, line);
}
-#endif
+
void merge(const SkIntersections& , int , const SkIntersections& , int );
int mostOutside(double rangeStart, double rangeEnd, const SkDPoint& origin) const;
void removeOne(int index);
diff --git a/src/pathops/SkOpSegment.cpp b/src/pathops/SkOpSegment.cpp
index ff83f4f..e35f6d0 100644
--- a/src/pathops/SkOpSegment.cpp
+++ b/src/pathops/SkOpSegment.cpp
@@ -985,15 +985,17 @@
return false;
}
#if DEBUG_WINDING
- SkOpSpanBase* last = *result;
- if (last) {
- SkDebugf("%s last segment=%d span=%d", __FUNCTION__,
- last->segment()->debugID(), last->debugID());
- if (!last->final()) {
- SkDebugf(" windSum=");
- SkPathOpsDebug::WindingPrintf(last->upCast()->windSum());
+ if (result) {
+ SkOpSpanBase* last = *result;
+ if (last) {
+ SkDebugf("%s last segment=%d span=%d", __FUNCTION__,
+ last->segment()->debugID(), last->debugID());
+ if (!last->final()) {
+ SkDebugf(" windSum=");
+ SkPathOpsDebug::WindingPrintf(last->upCast()->windSum());
+ }
+ SkDebugf(" \n");
}
- SkDebugf(" \n");
}
#endif
return true;
diff --git a/src/pathops/SkPathOpsConic.cpp b/src/pathops/SkPathOpsConic.cpp
index e1940a0..ffcaaa7 100644
--- a/src/pathops/SkPathOpsConic.cpp
+++ b/src/pathops/SkPathOpsConic.cpp
@@ -173,22 +173,18 @@
return chopped[1];
}
-#if PATH_OP_COMPILE_FOR_SIZE
+int SkTConic::intersectRay(SkIntersections* i, const SkDLine& line) const {
+ return i->intersectRay(fConic, line);
+}
- int SkTConic::intersectRay(SkIntersections* i, const SkDLine& line) const {
- return i->intersectRay(fConic, line);
- }
+bool SkTConic::hullIntersects(const SkDQuad& quad, bool* isLinear) const {
+ return quad.hullIntersects(fConic, isLinear);
+}
- bool SkTConic::hullIntersects(const SkDQuad& quad, bool* isLinear) const {
- return quad.hullIntersects(fConic, isLinear);
- }
+bool SkTConic::hullIntersects(const SkDCubic& cubic, bool* isLinear) const {
+ return cubic.hullIntersects(fConic, isLinear);
+}
- bool SkTConic::hullIntersects(const SkDCubic& cubic, bool* isLinear) const {
- return cubic.hullIntersects(fConic, isLinear);
- }
-
- void SkTConic::setBounds(SkDRect* rect) const {
- rect->setBounds(fConic);
- }
-
-#endif
+void SkTConic::setBounds(SkDRect* rect) const {
+ rect->setBounds(fConic);
+}
diff --git a/src/pathops/SkPathOpsConic.h b/src/pathops/SkPathOpsConic.h
index 88a234f..277f997 100644
--- a/src/pathops/SkPathOpsConic.h
+++ b/src/pathops/SkPathOpsConic.h
@@ -8,7 +8,6 @@
#ifndef SkPathOpsConic_DEFINED
#define SkPathOpsConic_DEFINED
-#include "SkPathOpsPoint.h"
#include "SkPathOpsQuad.h"
struct SkDConic {
@@ -29,6 +28,7 @@
void debugInit() {
fPts.debugInit();
+ fWeight = 0;
}
void debugSet(const SkDPoint* pts, SkScalar weight);
@@ -133,11 +133,6 @@
};
-#if PATH_OP_COMPILE_FOR_SIZE
-
-#include "SkArenaAlloc.h"
-#include "SkPathOpsTCurve.h"
-
class SkTConic : public SkTCurve {
public:
SkDConic fConic;
@@ -156,6 +151,9 @@
bool collapsed() const override { return fConic.collapsed(); }
bool controlsInside() const override { return fConic.controlsInside(); }
void debugInit() override { return fConic.debugInit(); }
+#if DEBUG_T_SECT
+ void dumpID(int id) const override { return fConic.dumpID(id); }
+#endif
SkDVector dxdyAtT(double t) const override { return fConic.dxdyAtT(t); }
#ifdef SK_DEBUG
SkOpGlobalState* globalState() const override { return fConic.globalState(); }
@@ -192,5 +190,4 @@
}
};
-#endif // PATH_OP_COMPILE_FOR_SIZE
#endif
diff --git a/src/pathops/SkPathOpsCubic.cpp b/src/pathops/SkPathOpsCubic.cpp
index b3a10cd..0156b8c 100644
--- a/src/pathops/SkPathOpsCubic.cpp
+++ b/src/pathops/SkPathOpsCubic.cpp
@@ -733,22 +733,18 @@
return topT;
}
-#if PATH_OP_COMPILE_FOR_SIZE
+int SkTCubic::intersectRay(SkIntersections* i, const SkDLine& line) const {
+ return i->intersectRay(fCubic, line);
+}
- int SkTCubic::intersectRay(SkIntersections* i, const SkDLine& line) const {
- return i->intersectRay(fCubic, line);
- }
+bool SkTCubic::hullIntersects(const SkDQuad& quad, bool* isLinear) const {
+ return quad.hullIntersects(fCubic, isLinear);
+}
- bool SkTCubic::hullIntersects(const SkDQuad& quad, bool* isLinear) const {
- return quad.hullIntersects(fCubic, isLinear);
- }
+bool SkTCubic::hullIntersects(const SkDConic& conic, bool* isLinear) const {
+ return conic.hullIntersects(fCubic, isLinear);
+}
- bool SkTCubic::hullIntersects(const SkDConic& conic, bool* isLinear) const {
- return conic.hullIntersects(fCubic, isLinear);
- }
-
- void SkTCubic::setBounds(SkDRect* rect) const {
- rect->setBounds(fCubic);
- }
-
-#endif
+void SkTCubic::setBounds(SkDRect* rect) const {
+ rect->setBounds(fCubic);
+}
diff --git a/src/pathops/SkPathOpsCubic.h b/src/pathops/SkPathOpsCubic.h
index 4f043fd..bc45677 100644
--- a/src/pathops/SkPathOpsCubic.h
+++ b/src/pathops/SkPathOpsCubic.h
@@ -8,8 +8,9 @@
#ifndef SkPathOpsCubic_DEFINED
#define SkPathOpsCubic_DEFINED
+#include "SkArenaAlloc.h"
#include "SkPath.h"
-#include "SkPathOpsPoint.h"
+#include "SkPathOpsTCurve.h"
struct SkDCubicPair;
@@ -180,11 +181,6 @@
SkDPoint pts[7];
};
-#if PATH_OP_COMPILE_FOR_SIZE
-
-#include "SkArenaAlloc.h"
-#include "SkPathOpsTCurve.h"
-
class SkTCubic : public SkTCurve {
public:
SkDCubic fCubic;
@@ -203,6 +199,9 @@
bool collapsed() const override { return fCubic.collapsed(); }
bool controlsInside() const override { return fCubic.controlsInside(); }
void debugInit() override { return fCubic.debugInit(); }
+#if DEBUG_T_SECT
+ void dumpID(int id) const override { return fCubic.dumpID(id); }
+#endif
SkDVector dxdyAtT(double t) const override { return fCubic.dxdyAtT(t); }
#ifdef SK_DEBUG
SkOpGlobalState* globalState() const override { return fCubic.globalState(); }
@@ -238,6 +237,4 @@
}
};
-#endif // PATH_OP_COMPILE_FOR_SIZE
-
#endif
diff --git a/src/pathops/SkPathOpsDebug.h b/src/pathops/SkPathOpsDebug.h
index 035ab14..57f158e 100644
--- a/src/pathops/SkPathOpsDebug.h
+++ b/src/pathops/SkPathOpsDebug.h
@@ -29,7 +29,7 @@
struct SkDQuad;
struct SkDConic;
struct SkDCubic;
-template<typename TCurve, typename OppCurve> class SkTSect;
+class SkTSect;
// dummy classes to fool msvs Visual Studio 2018 Immediate Window
#define DummyClasses(a, b) \
@@ -114,7 +114,7 @@
#define DEBUG_ASSEMBLE 1
#define DEBUG_COINCIDENCE 1
#define DEBUG_COINCIDENCE_DUMP 0
-#define DEBUG_COINCIDENCE_ORDER 0 // tight arc quads may generate out-of-order coincdence spans
+#define DEBUG_COINCIDENCE_ORDER 0 // tight arc quads may generate out-of-order coincidence spans
#define DEBUG_COINCIDENCE_VERBOSE 1
#define DEBUG_CUBIC_BINARY_SEARCH 0
#define DEBUG_CUBIC_SPLIT 1
@@ -379,136 +379,107 @@
};
// Visual Studio 2017 does not permit calling member functions from the Immediate Window.
-// Global functions work fine, however. Use globals within a namespace rather than
-// static members inside a class.
-namespace SkOpDebug {
- const SkOpAngle* AngleAngle(const SkOpAngle*, int id);
- SkOpContour* AngleContour(SkOpAngle*, int id);
- const SkOpPtT* AnglePtT(const SkOpAngle*, int id);
- const SkOpSegment* AngleSegment(const SkOpAngle*, int id);
- const SkOpSpanBase* AngleSpan(const SkOpAngle*, int id);
+// Global functions work fine, however. Use globals rather than static members inside a class.
+const SkOpAngle* AngleAngle(const SkOpAngle*, int id);
+SkOpContour* AngleContour(SkOpAngle*, int id);
+const SkOpPtT* AnglePtT(const SkOpAngle*, int id);
+const SkOpSegment* AngleSegment(const SkOpAngle*, int id);
+const SkOpSpanBase* AngleSpan(const SkOpAngle*, int id);
- const SkOpAngle* ContourAngle(SkOpContour*, int id);
- SkOpContour* ContourContour(SkOpContour*, int id);
- const SkOpPtT* ContourPtT(SkOpContour*, int id);
- const SkOpSegment* ContourSegment(SkOpContour*, int id);
- const SkOpSpanBase* ContourSpan(SkOpContour*, int id);
+const SkOpAngle* ContourAngle(SkOpContour*, int id);
+SkOpContour* ContourContour(SkOpContour*, int id);
+const SkOpPtT* ContourPtT(SkOpContour*, int id);
+const SkOpSegment* ContourSegment(SkOpContour*, int id);
+const SkOpSpanBase* ContourSpan(SkOpContour*, int id);
- const SkOpAngle* CoincidenceAngle(SkOpCoincidence*, int id);
- SkOpContour* CoincidenceContour(SkOpCoincidence*, int id);
- const SkOpPtT* CoincidencePtT(SkOpCoincidence*, int id);
- const SkOpSegment* CoincidenceSegment(SkOpCoincidence*, int id);
- const SkOpSpanBase* CoincidenceSpan(SkOpCoincidence*, int id);
+const SkOpAngle* CoincidenceAngle(SkOpCoincidence*, int id);
+SkOpContour* CoincidenceContour(SkOpCoincidence*, int id);
+const SkOpPtT* CoincidencePtT(SkOpCoincidence*, int id);
+const SkOpSegment* CoincidenceSegment(SkOpCoincidence*, int id);
+const SkOpSpanBase* CoincidenceSpan(SkOpCoincidence*, int id);
- const SkOpAngle* PtTAngle(const SkOpPtT*, int id);
- SkOpContour* PtTContour(SkOpPtT*, int id);
- const SkOpPtT* PtTPtT(const SkOpPtT*, int id);
- const SkOpSegment* PtTSegment(const SkOpPtT*, int id);
- const SkOpSpanBase* PtTSpan(const SkOpPtT*, int id);
+const SkOpAngle* PtTAngle(const SkOpPtT*, int id);
+SkOpContour* PtTContour(SkOpPtT*, int id);
+const SkOpPtT* PtTPtT(const SkOpPtT*, int id);
+const SkOpSegment* PtTSegment(const SkOpPtT*, int id);
+const SkOpSpanBase* PtTSpan(const SkOpPtT*, int id);
- const SkOpAngle* SegmentAngle(const SkOpSegment*, int id);
- SkOpContour* SegmentContour(SkOpSegment*, int id);
- const SkOpPtT* SegmentPtT(const SkOpSegment*, int id);
- const SkOpSegment* SegmentSegment(const SkOpSegment*, int id);
- const SkOpSpanBase* SegmentSpan(const SkOpSegment*, int id);
+const SkOpAngle* SegmentAngle(const SkOpSegment*, int id);
+SkOpContour* SegmentContour(SkOpSegment*, int id);
+const SkOpPtT* SegmentPtT(const SkOpSegment*, int id);
+const SkOpSegment* SegmentSegment(const SkOpSegment*, int id);
+const SkOpSpanBase* SegmentSpan(const SkOpSegment*, int id);
- const SkOpAngle* SpanAngle(const SkOpSpanBase*, int id);
- SkOpContour* SpanContour(SkOpSpanBase*, int id);
- const SkOpPtT* SpanPtT(const SkOpSpanBase*, int id);
- const SkOpSegment* SpanSegment(const SkOpSpanBase*, int id);
- const SkOpSpanBase* SpanSpan(const SkOpSpanBase*, int id);
+const SkOpAngle* SpanAngle(const SkOpSpanBase*, int id);
+SkOpContour* SpanContour(SkOpSpanBase*, int id);
+const SkOpPtT* SpanPtT(const SkOpSpanBase*, int id);
+const SkOpSegment* SpanSegment(const SkOpSpanBase*, int id);
+const SkOpSpanBase* SpanSpan(const SkOpSpanBase*, int id);
#if DEBUG_DUMP_VERIFY
- void DumpOp(const SkPath& one, const SkPath& two, SkPathOp op,
- const char* testName);
- void DumpOp(FILE* file, const SkPath& one, const SkPath& two, SkPathOp op,
- const char* testName);
- void DumpSimplify(const SkPath& path, const char* testName);
- void DumpSimplify(FILE* file, const SkPath& path, const char* testName);
- void ReportOpFail(const SkPath& one, const SkPath& two, SkPathOp op);
- void ReportSimplifyFail(const SkPath& path);
- void VerifyOp(const SkPath& one, const SkPath& two, SkPathOp op,
- const SkPath& result);
- void VerifySimplify(const SkPath& path, const SkPath& result);
+void DumpOp(const SkPath& one, const SkPath& two, SkPathOp op,
+ const char* testName);
+void DumpOp(FILE* file, const SkPath& one, const SkPath& two, SkPathOp op,
+ const char* testName);
+void DumpSimplify(const SkPath& path, const char* testName);
+void DumpSimplify(FILE* file, const SkPath& path, const char* testName);
+void ReportOpFail(const SkPath& one, const SkPath& two, SkPathOp op);
+void ReportSimplifyFail(const SkPath& path);
+void VerifyOp(const SkPath& one, const SkPath& two, SkPathOp op,
+ const SkPath& result);
+void VerifySimplify(const SkPath& path, const SkPath& result);
#endif
- // global path dumps for msvs Visual Studio 17 to use from Immediate Window
- void Dump(const SkOpContour& );
- void DumpAll(const SkOpContour& );
- void DumpAngles(const SkOpContour& );
- void DumpContours(const SkOpContour& );
- void DumpContoursAll(const SkOpContour& );
- void DumpContoursAngles(const SkOpContour& );
- void DumpContoursPts(const SkOpContour& );
- void DumpContoursPt(const SkOpContour& , int segmentID);
- void DumpContoursSegment(const SkOpContour& , int segmentID);
- void DumpContoursSpan(const SkOpContour& , int segmentID);
- void DumpContoursSpans(const SkOpContour& );
- void DumpPt(const SkOpContour& , int );
- void DumpPts(const SkOpContour& , const char* prefix = "seg");
- void DumpSegment(const SkOpContour& , int );
- void DumpSegments(const SkOpContour& , const char* prefix = "seg", SkPathOp op = (SkPathOp) -1);
- void DumpSpan(const SkOpContour& , int );
- void DumpSpans(const SkOpContour& );
+// global path dumps for msvs Visual Studio 17 to use from Immediate Window
+void Dump(const SkOpContour& );
+void DumpAll(const SkOpContour& );
+void DumpAngles(const SkOpContour& );
+void DumpContours(const SkOpContour& );
+void DumpContoursAll(const SkOpContour& );
+void DumpContoursAngles(const SkOpContour& );
+void DumpContoursPts(const SkOpContour& );
+void DumpContoursPt(const SkOpContour& , int segmentID);
+void DumpContoursSegment(const SkOpContour& , int segmentID);
+void DumpContoursSpan(const SkOpContour& , int segmentID);
+void DumpContoursSpans(const SkOpContour& );
+void DumpPt(const SkOpContour& , int );
+void DumpPts(const SkOpContour& , const char* prefix = "seg");
+void DumpSegment(const SkOpContour& , int );
+void DumpSegments(const SkOpContour& , const char* prefix = "seg", SkPathOp op = (SkPathOp) -1);
+void DumpSpan(const SkOpContour& , int );
+void DumpSpans(const SkOpContour& );
- void Dump(const SkOpSegment& );
- void DumpAll(const SkOpSegment& );
- void DumpAngles(const SkOpSegment& );
- void DumpCoin(const SkOpSegment& );
- void DumpPts(const SkOpSegment& , const char* prefix = "seg");
+void Dump(const SkOpSegment& );
+void DumpAll(const SkOpSegment& );
+void DumpAngles(const SkOpSegment& );
+void DumpCoin(const SkOpSegment& );
+void DumpPts(const SkOpSegment& , const char* prefix = "seg");
- void Dump(const SkOpPtT& );
- void DumpAll(const SkOpPtT& );
+void Dump(const SkOpPtT& );
+void DumpAll(const SkOpPtT& );
- void Dump(const SkOpSpanBase& );
- void DumpCoin(const SkOpSpanBase& );
- void DumpAll(const SkOpSpanBase& );
+void Dump(const SkOpSpanBase& );
+void DumpCoin(const SkOpSpanBase& );
+void DumpAll(const SkOpSpanBase& );
- void DumpCoin(const SkOpSpan& );
- bool DumpSpan(const SkOpSpan& );
+void DumpCoin(const SkOpSpan& );
+bool DumpSpan(const SkOpSpan& );
- void Dump(const SkDConic& );
- void DumpID(const SkDConic& , int id);
+void Dump(const SkDConic& );
+void DumpID(const SkDConic& , int id);
- void Dump(const SkDCubic& );
- void DumpID(const SkDCubic& , int id);
+void Dump(const SkDCubic& );
+void DumpID(const SkDCubic& , int id);
- void Dump(const SkDLine& );
- void DumpID(const SkDLine& , int id);
+void Dump(const SkDLine& );
+void DumpID(const SkDLine& , int id);
- void Dump(const SkDQuad& );
- void DumpID(const SkDQuad& , int id);
+void Dump(const SkDQuad& );
+void DumpID(const SkDQuad& , int id);
- void Dump(const SkDPoint& );
+void Dump(const SkDPoint& );
- void Dump(const SkOpAngle& );
-
-// dummy declarations to fool msvs Visual Studio 2018 Immediate Window
-#define DummyDeclarations(a, b) \
- void Dump(const SkDebugTCoincident##a##b& ); \
- \
- void Dump(const SkDebugTSect##a##b& ); \
- void DumpBoth(const SkDebugTSect##a##b& , SkDebugTSect##a##b* ); \
- void DumpBounded(const SkDebugTSect##a##b& , int id); \
- void DumpBounds(const SkDebugTSect##a##b& ); \
- void DumpCoin(const SkDebugTSect##a##b& ); \
- void DumpCoinCurves(const SkDebugTSect##a##b& ); \
- void DumpCurves(const SkDebugTSect##a##b& ); \
- \
- void Dump(const SkDebugTSpan##a##b& ); \
- void DumpAll(const SkDebugTSpan##a##b& ); \
- void DumpBounded(const SkDebugTSpan##a##b& , int id); \
- void DumpBounds(const SkDebugTSpan##a##b& ); \
- void DumpCoin(const SkDebugTSpan##a##b& )
-
- DummyDeclarations(Quad, Quad);
- DummyDeclarations(Conic, Quad);
- DummyDeclarations(Conic, Conic);
- DummyDeclarations(Cubic, Quad);
- DummyDeclarations(Cubic, Conic);
- DummyDeclarations(Cubic, Cubic);
-#undef DummyDeclarations
-}
+void Dump(const SkOpAngle& );
// generates tools/path_sorter.htm and path_visualizer.htm compatible data
void DumpQ(const SkDQuad& quad1, const SkDQuad& quad2, int testNo);
diff --git a/src/pathops/SkPathOpsQuad.cpp b/src/pathops/SkPathOpsQuad.cpp
index bcc894e..af842fb 100644
--- a/src/pathops/SkPathOpsQuad.cpp
+++ b/src/pathops/SkPathOpsQuad.cpp
@@ -399,22 +399,18 @@
*b -= *c; // b = 2*B - 2*C
}
-#if PATH_OP_COMPILE_FOR_SIZE
+int SkTQuad::intersectRay(SkIntersections* i, const SkDLine& line) const {
+ return i->intersectRay(fQuad, line);
+}
- int SkTQuad::intersectRay(SkIntersections* i, const SkDLine& line) const {
- return i->intersectRay(fQuad, line);
- }
+bool SkTQuad::hullIntersects(const SkDConic& conic, bool* isLinear) const {
+ return conic.hullIntersects(fQuad, isLinear);
+}
- bool SkTQuad::hullIntersects(const SkDConic& conic, bool* isLinear) const {
- return conic.hullIntersects(fQuad, isLinear);
- }
+bool SkTQuad::hullIntersects(const SkDCubic& cubic, bool* isLinear) const {
+ return cubic.hullIntersects(fQuad, isLinear);
+}
- bool SkTQuad::hullIntersects(const SkDCubic& cubic, bool* isLinear) const {
- return cubic.hullIntersects(fQuad, isLinear);
- }
-
- void SkTQuad::setBounds(SkDRect* rect) const {
- rect->setBounds(fQuad);
- }
-
-#endif
+void SkTQuad::setBounds(SkDRect* rect) const {
+ rect->setBounds(fQuad);
+}
diff --git a/src/pathops/SkPathOpsQuad.h b/src/pathops/SkPathOpsQuad.h
index 2de1422..94d1b38 100644
--- a/src/pathops/SkPathOpsQuad.h
+++ b/src/pathops/SkPathOpsQuad.h
@@ -8,7 +8,8 @@
#ifndef SkPathOpsQuad_DEFINED
#define SkPathOpsQuad_DEFINED
-#include "SkPathOpsPoint.h"
+#include "SkArenaAlloc.h"
+#include "SkPathOpsTCurve.h"
struct SkOpCurve;
@@ -122,10 +123,6 @@
SkDEBUGCODE(SkOpGlobalState* fDebugGlobalState);
};
-#if PATH_OP_COMPILE_FOR_SIZE
-
-#include "SkArenaAlloc.h"
-#include "SkPathOpsTCurve.h"
class SkTQuad : public SkTCurve {
public:
@@ -145,6 +142,9 @@
bool collapsed() const override { return fQuad.collapsed(); }
bool controlsInside() const override { return fQuad.controlsInside(); }
void debugInit() override { return fQuad.debugInit(); }
+#if DEBUG_T_SECT
+ void dumpID(int id) const override { return fQuad.dumpID(id); }
+#endif
SkDVector dxdyAtT(double t) const override { return fQuad.dxdyAtT(t); }
#ifdef SK_DEBUG
SkOpGlobalState* globalState() const override { return fQuad.globalState(); }
@@ -181,6 +181,4 @@
}
};
-#endif // PATH_OP_COMPILE_FOR_SIZE
-
#endif
diff --git a/src/pathops/SkPathOpsRect.cpp b/src/pathops/SkPathOpsRect.cpp
index 18a1a0b..f691af5 100644
--- a/src/pathops/SkPathOpsRect.cpp
+++ b/src/pathops/SkPathOpsRect.cpp
@@ -61,10 +61,6 @@
}
}
-#if PATH_OP_COMPILE_FOR_SIZE
-
- void SkDRect::setBounds(const SkTCurve& curve) {
- curve.setBounds(this);
- }
-
-#endif
+void SkDRect::setBounds(const SkTCurve& curve) {
+ curve.setBounds(this);
+}
diff --git a/src/pathops/SkPathOpsSimplify.cpp b/src/pathops/SkPathOpsSimplify.cpp
index 8e5f279..86b2c06 100644
--- a/src/pathops/SkPathOpsSimplify.cpp
+++ b/src/pathops/SkPathOpsSimplify.cpp
@@ -50,18 +50,14 @@
if (current->activeWinding(start, end) && !writer->isClosed()) {
SkOpSpan* spanStart = start->starter(end);
if (!spanStart->done()) {
- if (!current->addCurveTo(start, end, writer)) {
- return false;
- }
+ SkAssertResult(current->addCurveTo(start, end, writer));
current->markDone(spanStart);
}
}
writer->finishContour();
} else {
SkOpSpanBase* last;
- if (!current->markAndChaseDone(start, end, &last)) {
- return false;
- }
+ SkAssertResult(current->markAndChaseDone(start, end, &last));
if (last && !last->chased()) {
last->setChased(true);
SkASSERT(!SkPathOpsDebug::ChaseContains(chase, last));
@@ -124,15 +120,12 @@
start = nextStart;
end = nextEnd;
} while (!writer->isClosed() && (!unsortable || !start->starter(end)->done()));
+#ifdef SK_DEBUG
if (!writer->isClosed()) {
SkOpSpan* spanStart = start->starter(end);
- if (!spanStart->done()) {
- if (!current->addCurveTo(start, end, writer)) {
- return false;
- }
- current->markDone(spanStart);
- }
+ SkASSERT(spanStart->done());
}
+#endif
writer->finishContour();
SkPathOpsDebug::ShowActiveSpans(contourList);
} while (true);
diff --git a/src/pathops/SkPathOpsTCurve.h b/src/pathops/SkPathOpsTCurve.h
index 4981dea..4637cb6 100644
--- a/src/pathops/SkPathOpsTCurve.h
+++ b/src/pathops/SkPathOpsTCurve.h
@@ -22,6 +22,9 @@
virtual bool collapsed() const = 0;
virtual bool controlsInside() const = 0;
virtual void debugInit() = 0;
+#if DEBUG_T_SECT
+ virtual void dumpID(int id) const = 0;
+#endif
virtual SkDVector dxdyAtT(double t) const = 0;
virtual bool hullIntersects(const SkDQuad& , bool* isLinear) const = 0;
virtual bool hullIntersects(const SkDConic& , bool* isLinear) const = 0;
diff --git a/src/pathops/SkPathOpsTSect.cpp b/src/pathops/SkPathOpsTSect.cpp
index e765c21..6149bc5 100644
--- a/src/pathops/SkPathOpsTSect.cpp
+++ b/src/pathops/SkPathOpsTSect.cpp
@@ -7,60 +7,2101 @@
#include "SkPathOpsTSect.h"
-#if PATH_OP_COMPILE_FOR_SIZE
+#define COINCIDENT_SPAN_COUNT 9
+
+void SkTCoincident::setPerp(const SkTCurve& c1, double t,
+ const SkDPoint& cPt, const SkTCurve& c2) {
+ SkDVector dxdy = c1.dxdyAtT(t);
+ SkDLine perp = {{ cPt, {cPt.fX + dxdy.fY, cPt.fY - dxdy.fX} }};
+ SkIntersections i SkDEBUGCODE((c1.globalState()));
+ int used = i.intersectRay(c2, perp);
+ // only keep closest
+ if (used == 0 || used == 3) {
+ this->init();
+ return;
+ }
+ fPerpT = i[0][0];
+ fPerpPt = i.pt(0);
+ SkASSERT(used <= 2);
+ if (used == 2) {
+ double distSq = (fPerpPt - cPt).lengthSquared();
+ double dist2Sq = (i.pt(1) - cPt).lengthSquared();
+ if (dist2Sq < distSq) {
+ fPerpT = i[0][1];
+ fPerpPt = i.pt(1);
+ }
+ }
+#if DEBUG_T_SECT
+ SkDebugf("setPerp t=%1.9g cPt=(%1.9g,%1.9g) %s oppT=%1.9g fPerpPt=(%1.9g,%1.9g)\n",
+ t, cPt.fX, cPt.fY,
+ cPt.approximatelyEqual(fPerpPt) ? "==" : "!=", fPerpT, fPerpPt.fX, fPerpPt.fY);
+#endif
+ fMatch = cPt.approximatelyEqual(fPerpPt);
+#if DEBUG_T_SECT
+ if (fMatch) {
+ SkDebugf(""); // allow setting breakpoint
+ }
+#endif
+}
+
+void SkTSpan::addBounded(SkTSpan* span, SkArenaAlloc* heap) {
+ SkTSpanBounded* bounded = heap->make<SkTSpanBounded>();
+ bounded->fBounded = span;
+ bounded->fNext = fBounded;
+ fBounded = bounded;
+}
+
+SkTSpan* SkTSect::addFollowing(
+ SkTSpan* prior) {
+ SkTSpan* result = this->addOne();
+ SkDEBUGCODE(result->debugSetGlobalState(this->globalState()));
+ result->fStartT = prior ? prior->fEndT : 0;
+ SkTSpan* next = prior ? prior->fNext : fHead;
+ result->fEndT = next ? next->fStartT : 1;
+ result->fPrev = prior;
+ result->fNext = next;
+ if (prior) {
+ prior->fNext = result;
+ } else {
+ fHead = result;
+ }
+ if (next) {
+ next->fPrev = result;
+ }
+ result->resetBounds(fCurve);
+ // world may not be consistent to call validate here
+ result->validate();
+ return result;
+}
+
+void SkTSect::addForPerp(SkTSpan* span, double t) {
+ if (!span->hasOppT(t)) {
+ SkTSpan* priorSpan;
+ SkTSpan* opp = this->spanAtT(t, &priorSpan);
+ if (!opp) {
+ opp = this->addFollowing(priorSpan);
+#if DEBUG_PERP
+ SkDebugf("%s priorSpan=%d t=%1.9g opp=%d\n", __FUNCTION__, priorSpan ?
+ priorSpan->debugID() : -1, t, opp->debugID());
+#endif
+ }
+#if DEBUG_PERP
+ opp->dump(); SkDebugf("\n");
+ SkDebugf("%s addBounded span=%d opp=%d\n", __FUNCTION__, priorSpan ?
+ priorSpan->debugID() : -1, opp->debugID());
+#endif
+ opp->addBounded(span, &fHeap);
+ span->addBounded(opp, &fHeap);
+ }
+ this->validate();
+#if DEBUG_T_SECT
+ span->validatePerpT(t);
+#endif
+}
+
+double SkTSpan::closestBoundedT(const SkDPoint& pt) const {
+ double result = -1;
+ double closest = DBL_MAX;
+ const SkTSpanBounded* testBounded = fBounded;
+ while (testBounded) {
+ const SkTSpan* test = testBounded->fBounded;
+ double startDist = test->pointFirst().distanceSquared(pt);
+ if (closest > startDist) {
+ closest = startDist;
+ result = test->fStartT;
+ }
+ double endDist = test->pointLast().distanceSquared(pt);
+ if (closest > endDist) {
+ closest = endDist;
+ result = test->fEndT;
+ }
+ testBounded = testBounded->fNext;
+ }
+ SkASSERT(between(0, result, 1));
+ return result;
+}
+
+#ifdef SK_DEBUG
+
+bool SkTSpan::debugIsBefore(const SkTSpan* span) const {
+ const SkTSpan* work = this;
+ do {
+ if (span == work) {
+ return true;
+ }
+ } while ((work = work->fNext));
+ return false;
+}
+#endif
+
+bool SkTSpan::contains(double t) const {
+ const SkTSpan* work = this;
+ do {
+ if (between(work->fStartT, t, work->fEndT)) {
+ return true;
+ }
+ } while ((work = work->fNext));
+ return false;
+}
+
+const SkTSect* SkTSpan::debugOpp() const {
+ return SkDEBUGRELEASE(fDebugSect->debugOpp(), nullptr);
+}
+
+SkTSpan* SkTSpan::findOppSpan(
+ const SkTSpan* opp) const {
+ SkTSpanBounded* bounded = fBounded;
+ while (bounded) {
+ SkTSpan* test = bounded->fBounded;
+ if (opp == test) {
+ return test;
+ }
+ bounded = bounded->fNext;
+ }
+ return nullptr;
+}
+
+// returns 0 if no hull intersection
+// 1 if hulls intersect
+// 2 if hulls only share a common endpoint
+// -1 if linear and further checking is required
+
+int SkTSpan::hullCheck(const SkTSpan* opp,
+ bool* start, bool* oppStart) {
+ if (fIsLinear) {
+ return -1;
+ }
+ bool ptsInCommon;
+ if (onlyEndPointsInCommon(opp, start, oppStart, &ptsInCommon)) {
+ SkASSERT(ptsInCommon);
+ return 2;
+ }
+ bool linear;
+ if (fPart->hullIntersects(*opp->fPart, &linear)) {
+ if (!linear) { // check set true if linear
+ return 1;
+ }
+ fIsLinear = true;
+ fIsLine = fPart->controlsInside();
+ return ptsInCommon ? 1 : -1;
+ } else { // hull is not linear; check set true if intersected at the end points
+ return ((int) ptsInCommon) << 1; // 0 or 2
+ }
+ return 0;
+}
+
+// OPTIMIZE ? If at_most_end_pts_in_common detects that one quad is near linear,
+// use line intersection to guess a better split than 0.5
+// OPTIMIZE Once at_most_end_pts_in_common detects linear, mark span so all future splits are linear
+
+int SkTSpan::hullsIntersect(SkTSpan* opp,
+ bool* start, bool* oppStart) {
+ if (!fBounds.intersects(opp->fBounds)) {
+ return 0;
+ }
+ int hullSect = this->hullCheck(opp, start, oppStart);
+ if (hullSect >= 0) {
+ return hullSect;
+ }
+ hullSect = opp->hullCheck(this, oppStart, start);
+ if (hullSect >= 0) {
+ return hullSect;
+ }
+ return -1;
+}
+
+void SkTSpan::init(const SkTCurve& c) {
+ fPrev = fNext = nullptr;
+ fStartT = 0;
+ fEndT = 1;
+ fBounded = nullptr;
+ resetBounds(c);
+}
+
+bool SkTSpan::initBounds(const SkTCurve& c) {
+ if (SkDoubleIsNaN(fStartT) || SkDoubleIsNaN(fEndT)) {
+ return false;
+ }
+ c.subDivide(fStartT, fEndT, fPart);
+ fBounds.setBounds(*fPart);
+ fCoinStart.init();
+ fCoinEnd.init();
+ fBoundsMax = SkTMax(fBounds.width(), fBounds.height());
+ fCollapsed = fPart->collapsed();
+ fHasPerp = false;
+ fDeleted = false;
+#if DEBUG_T_SECT
+ if (fCollapsed) {
+ SkDebugf(""); // for convenient breakpoints
+ }
+#endif
+ return fBounds.valid();
+}
+
+bool SkTSpan::linearsIntersect(SkTSpan* span) {
+ int result = this->linearIntersects(*span->fPart);
+ if (result <= 1) {
+ return SkToBool(result);
+ }
+ SkASSERT(span->fIsLinear);
+ result = span->linearIntersects(*fPart);
+// SkASSERT(result <= 1);
+ return SkToBool(result);
+}
+
+double SkTSpan::linearT(const SkDPoint& pt) const {
+ SkDVector len = this->pointLast() - this->pointFirst();
+ return fabs(len.fX) > fabs(len.fY)
+ ? (pt.fX - this->pointFirst().fX) / len.fX
+ : (pt.fY - this->pointFirst().fY) / len.fY;
+}
+
+int SkTSpan::linearIntersects(const SkTCurve& q2) const {
+ // looks like q1 is near-linear
+ int start = 0, end = fPart->pointLast(); // the outside points are usually the extremes
+ if (!fPart->controlsInside()) {
+ double dist = 0; // if there's any question, compute distance to find best outsiders
+ for (int outer = 0; outer < this->pointCount() - 1; ++outer) {
+ for (int inner = outer + 1; inner < this->pointCount(); ++inner) {
+ double test = ((*fPart)[outer] - (*fPart)[inner]).lengthSquared();
+ if (dist > test) {
+ continue;
+ }
+ dist = test;
+ start = outer;
+ end = inner;
+ }
+ }
+ }
+ // see if q2 is on one side of the line formed by the extreme points
+ double origX = (*fPart)[start].fX;
+ double origY = (*fPart)[start].fY;
+ double adj = (*fPart)[end].fX - origX;
+ double opp = (*fPart)[end].fY - origY;
+ double maxPart = SkTMax(fabs(adj), fabs(opp));
+ double sign = 0; // initialization to shut up warning in release build
+ for (int n = 0; n < q2.pointCount(); ++n) {
+ double dx = q2[n].fY - origY;
+ double dy = q2[n].fX - origX;
+ double maxVal = SkTMax(maxPart, SkTMax(fabs(dx), fabs(dy)));
+ double test = (q2[n].fY - origY) * adj - (q2[n].fX - origX) * opp;
+ if (precisely_zero_when_compared_to(test, maxVal)) {
+ return 1;
+ }
+ if (approximately_zero_when_compared_to(test, maxVal)) {
+ return 3;
+ }
+ if (n == 0) {
+ sign = test;
+ continue;
+ }
+ if (test * sign < 0) {
+ return 1;
+ }
+ }
+ return 0;
+}
+
+bool SkTSpan::onlyEndPointsInCommon(const SkTSpan* opp,
+ bool* start, bool* oppStart, bool* ptsInCommon) {
+ if (opp->pointFirst() == this->pointFirst()) {
+ *start = *oppStart = true;
+ } else if (opp->pointFirst() == this->pointLast()) {
+ *start = false;
+ *oppStart = true;
+ } else if (opp->pointLast() == this->pointFirst()) {
+ *start = true;
+ *oppStart = false;
+ } else if (opp->pointLast() == this->pointLast()) {
+ *start = *oppStart = false;
+ } else {
+ *ptsInCommon = false;
+ return false;
+ }
+ *ptsInCommon = true;
+ const SkDPoint* otherPts[4], * oppOtherPts[4];
+// const SkDPoint* otherPts[this->pointCount() - 1], * oppOtherPts[opp->pointCount() - 1];
+ int baseIndex = *start ? 0 : fPart->pointLast();
+ fPart->otherPts(baseIndex, otherPts);
+ opp->fPart->otherPts(*oppStart ? 0 : opp->fPart->pointLast(), oppOtherPts);
+ const SkDPoint& base = (*fPart)[baseIndex];
+ for (int o1 = 0; o1 < this->pointCount() - 1; ++o1) {
+ SkDVector v1 = *otherPts[o1] - base;
+ for (int o2 = 0; o2 < opp->pointCount() - 1; ++o2) {
+ SkDVector v2 = *oppOtherPts[o2] - base;
+ if (v2.dot(v1) >= 0) {
+ return false;
+ }
+ }
+ }
+ return true;
+}
+
+SkTSpan* SkTSpan::oppT(double t) const {
+ SkTSpanBounded* bounded = fBounded;
+ while (bounded) {
+ SkTSpan* test = bounded->fBounded;
+ if (between(test->fStartT, t, test->fEndT)) {
+ return test;
+ }
+ bounded = bounded->fNext;
+ }
+ return nullptr;
+}
+
+bool SkTSpan::removeAllBounded() {
+ bool deleteSpan = false;
+ SkTSpanBounded* bounded = fBounded;
+ while (bounded) {
+ SkTSpan* opp = bounded->fBounded;
+ deleteSpan |= opp->removeBounded(this);
+ bounded = bounded->fNext;
+ }
+ return deleteSpan;
+}
+
+bool SkTSpan::removeBounded(const SkTSpan* opp) {
+ if (fHasPerp) {
+ bool foundStart = false;
+ bool foundEnd = false;
+ SkTSpanBounded* bounded = fBounded;
+ while (bounded) {
+ SkTSpan* test = bounded->fBounded;
+ if (opp != test) {
+ foundStart |= between(test->fStartT, fCoinStart.perpT(), test->fEndT);
+ foundEnd |= between(test->fStartT, fCoinEnd.perpT(), test->fEndT);
+ }
+ bounded = bounded->fNext;
+ }
+ if (!foundStart || !foundEnd) {
+ fHasPerp = false;
+ fCoinStart.init();
+ fCoinEnd.init();
+ }
+ }
+ SkTSpanBounded* bounded = fBounded;
+ SkTSpanBounded* prev = nullptr;
+ while (bounded) {
+ SkTSpanBounded* boundedNext = bounded->fNext;
+ if (opp == bounded->fBounded) {
+ if (prev) {
+ prev->fNext = boundedNext;
+ return false;
+ } else {
+ fBounded = boundedNext;
+ return fBounded == nullptr;
+ }
+ }
+ prev = bounded;
+ bounded = boundedNext;
+ }
+ SkOPASSERT(0);
+ return false;
+}
+
+bool SkTSpan::splitAt(SkTSpan* work, double t, SkArenaAlloc* heap) {
+ fStartT = t;
+ fEndT = work->fEndT;
+ if (fStartT == fEndT) {
+ fCollapsed = true;
+ return false;
+ }
+ work->fEndT = t;
+ if (work->fStartT == work->fEndT) {
+ work->fCollapsed = true;
+ return false;
+ }
+ fPrev = work;
+ fNext = work->fNext;
+ fIsLinear = work->fIsLinear;
+ fIsLine = work->fIsLine;
+
+ work->fNext = this;
+ if (fNext) {
+ fNext->fPrev = this;
+ }
+ this->validate();
+ SkTSpanBounded* bounded = work->fBounded;
+ fBounded = nullptr;
+ while (bounded) {
+ this->addBounded(bounded->fBounded, heap);
+ bounded = bounded->fNext;
+ }
+ bounded = fBounded;
+ while (bounded) {
+ bounded->fBounded->addBounded(this, heap);
+ bounded = bounded->fNext;
+ }
+ return true;
+}
+
+void SkTSpan::validate() const {
+#if DEBUG_VALIDATE
+ SkASSERT(this != fPrev);
+ SkASSERT(this != fNext);
+ SkASSERT(fNext == nullptr || fNext != fPrev);
+ SkASSERT(fNext == nullptr || this == fNext->fPrev);
+ SkASSERT(fPrev == nullptr || this == fPrev->fNext);
+ this->validateBounded();
+#endif
+#if DEBUG_T_SECT
+ SkASSERT(fBounds.width() || fBounds.height() || fCollapsed);
+ SkASSERT(fBoundsMax == SkTMax(fBounds.width(), fBounds.height()) || fCollapsed == 0xFF);
+ SkASSERT(0 <= fStartT);
+ SkASSERT(fEndT <= 1);
+ SkASSERT(fStartT <= fEndT);
+ SkASSERT(fBounded || fCollapsed == 0xFF);
+ if (fHasPerp) {
+ if (fCoinStart.isMatch()) {
+ validatePerpT(fCoinStart.perpT());
+ validatePerpPt(fCoinStart.perpT(), fCoinStart.perpPt());
+ }
+ if (fCoinEnd.isMatch()) {
+ validatePerpT(fCoinEnd.perpT());
+ validatePerpPt(fCoinEnd.perpT(), fCoinEnd.perpPt());
+ }
+ }
+#endif
+}
+
+void SkTSpan::validateBounded() const {
+#if DEBUG_VALIDATE
+ const SkTSpanBounded* testBounded = fBounded;
+ while (testBounded) {
+ SkDEBUGCODE(const SkTSpan* overlap = testBounded->fBounded);
+ SkASSERT(!overlap->fDeleted);
+#if DEBUG_T_SECT
+ SkASSERT(((this->debugID() ^ overlap->debugID()) & 1) == 1);
+ SkASSERT(overlap->findOppSpan(this));
+#endif
+ testBounded = testBounded->fNext;
+ }
+#endif
+}
+
+void SkTSpan::validatePerpT(double oppT) const {
+ const SkTSpanBounded* testBounded = fBounded;
+ while (testBounded) {
+ const SkTSpan* overlap = testBounded->fBounded;
+ if (precisely_between(overlap->fStartT, oppT, overlap->fEndT)) {
+ return;
+ }
+ testBounded = testBounded->fNext;
+ }
+ SkASSERT(0);
+}
+
+void SkTSpan::validatePerpPt(double t, const SkDPoint& pt) const {
+ SkASSERT(fDebugSect->fOppSect->fCurve.ptAtT(t) == pt);
+}
+
+SkTSect::SkTSect(const SkTCurve& c
+ SkDEBUGPARAMS(SkOpGlobalState* debugGlobalState)
+ PATH_OPS_DEBUG_T_SECT_PARAMS(int id))
+ : fCurve(c)
+ , fHeap(sizeof(SkTSpan) * 4)
+ , fCoincident(nullptr)
+ , fDeleted(nullptr)
+ , fActiveCount(0)
+ , fHung(false)
+ SkDEBUGPARAMS(fDebugGlobalState(debugGlobalState))
+ PATH_OPS_DEBUG_T_SECT_PARAMS(fID(id))
+ PATH_OPS_DEBUG_T_SECT_PARAMS(fDebugCount(0))
+ PATH_OPS_DEBUG_T_SECT_PARAMS(fDebugAllocatedCount(0))
+{
+ this->resetRemovedEnds();
+ fHead = this->addOne();
+ SkDEBUGCODE(fHead->debugSetGlobalState(debugGlobalState));
+ fHead->init(c);
+}
+
+SkTSpan* SkTSect::addOne() {
+ SkTSpan* result;
+ if (fDeleted) {
+ result = fDeleted;
+ fDeleted = result->fNext;
+ } else {
+ result = fHeap.make<SkTSpan>(fCurve, fHeap);
+#if DEBUG_T_SECT
+ ++fDebugAllocatedCount;
+#endif
+ }
+ result->reset();
+ result->fHasPerp = false;
+ result->fDeleted = false;
+ ++fActiveCount;
+ PATH_OPS_DEBUG_T_SECT_CODE(result->fID = fDebugCount++ * 2 + fID);
+ SkDEBUGCODE(result->fDebugSect = this);
+#ifdef SK_DEBUG
+ result->debugInit(fCurve, fHeap);
+ result->fCoinStart.debugInit();
+ result->fCoinEnd.debugInit();
+ result->fPrev = result->fNext = nullptr;
+ result->fBounds.debugInit();
+ result->fStartT = result->fEndT = result->fBoundsMax = SK_ScalarNaN;
+ result->fCollapsed = result->fIsLinear = result->fIsLine = 0xFF;
+#endif
+ return result;
+}
+
+bool SkTSect::binarySearchCoin(SkTSect* sect2, double tStart,
+ double tStep, double* resultT, double* oppT, SkTSpan** oppFirst) {
+ SkTSpan work(fCurve, fHeap);
+ double result = work.fStartT = work.fEndT = tStart;
+ SkDEBUGCODE(work.fDebugSect = this);
+ SkDPoint last = fCurve.ptAtT(tStart);
+ SkDPoint oppPt;
+ bool flip = false;
+ bool contained = false;
+ bool down = tStep < 0;
+ const SkTCurve& opp = sect2->fCurve;
+ do {
+ tStep *= 0.5;
+ work.fStartT += tStep;
+ if (flip) {
+ tStep = -tStep;
+ flip = false;
+ }
+ work.initBounds(fCurve);
+ if (work.fCollapsed) {
+ return false;
+ }
+ if (last.approximatelyEqual(work.pointFirst())) {
+ break;
+ }
+ last = work.pointFirst();
+ work.fCoinStart.setPerp(fCurve, work.fStartT, last, opp);
+ if (work.fCoinStart.isMatch()) {
+#if DEBUG_T_SECT
+ work.validatePerpPt(work.fCoinStart.perpT(), work.fCoinStart.perpPt());
+#endif
+ double oppTTest = work.fCoinStart.perpT();
+ if (sect2->fHead->contains(oppTTest)) {
+ *oppT = oppTTest;
+ oppPt = work.fCoinStart.perpPt();
+ contained = true;
+ if (down ? result <= work.fStartT : result >= work.fStartT) {
+ *oppFirst = nullptr; // signal caller to fail
+ return false;
+ }
+ result = work.fStartT;
+ continue;
+ }
+ }
+ tStep = -tStep;
+ flip = true;
+ } while (true);
+ if (!contained) {
+ return false;
+ }
+ if (last.approximatelyEqual(fCurve[0])) {
+ result = 0;
+ } else if (last.approximatelyEqual(this->pointLast())) {
+ result = 1;
+ }
+ if (oppPt.approximatelyEqual(opp[0])) {
+ *oppT = 0;
+ } else if (oppPt.approximatelyEqual(sect2->pointLast())) {
+ *oppT = 1;
+ }
+ *resultT = result;
+ return true;
+}
+
+// OPTIMIZE ? keep a sorted list of sizes in the form of a doubly-linked list in quad span
+// so that each quad sect has a pointer to the largest, and can update it as spans
+// are split
+
+SkTSpan* SkTSect::boundsMax() {
+ SkTSpan* test = fHead;
+ SkTSpan* largest = fHead;
+ bool lCollapsed = largest->fCollapsed;
+ int safetyNet = 10000;
+ while ((test = test->fNext)) {
+ if (!--safetyNet) {
+ fHung = true;
+ return nullptr;
+ }
+ bool tCollapsed = test->fCollapsed;
+ if ((lCollapsed && !tCollapsed) || (lCollapsed == tCollapsed &&
+ largest->fBoundsMax < test->fBoundsMax)) {
+ largest = test;
+ lCollapsed = test->fCollapsed;
+ }
+ }
+ return largest;
+}
+
+bool SkTSect::coincidentCheck(SkTSect* sect2) {
+ SkTSpan* first = fHead;
+ if (!first) {
+ return false;
+ }
+ SkTSpan* last, * next;
+ do {
+ int consecutive = this->countConsecutiveSpans(first, &last);
+ next = last->fNext;
+ if (consecutive < COINCIDENT_SPAN_COUNT) {
+ continue;
+ }
+ this->validate();
+ sect2->validate();
+ this->computePerpendiculars(sect2, first, last);
+ this->validate();
+ sect2->validate();
+ // check to see if a range of points are on the curve
+ SkTSpan* coinStart = first;
+ do {
+ bool success = this->extractCoincident(sect2, coinStart, last, &coinStart);
+ if (!success) {
+ return false;
+ }
+ } while (coinStart && !last->fDeleted);
+ if (!fHead || !sect2->fHead) {
+ break;
+ }
+ if (!next || next->fDeleted) {
+ break;
+ }
+ } while ((first = next));
+ return true;
+}
+
+void SkTSect::coincidentForce(SkTSect* sect2,
+ double start1s, double start1e) {
+ SkTSpan* first = fHead;
+ SkTSpan* last = this->tail();
+ SkTSpan* oppFirst = sect2->fHead;
+ SkTSpan* oppLast = sect2->tail();
+ bool deleteEmptySpans = this->updateBounded(first, last, oppFirst);
+ deleteEmptySpans |= sect2->updateBounded(oppFirst, oppLast, first);
+ this->removeSpanRange(first, last);
+ sect2->removeSpanRange(oppFirst, oppLast);
+ first->fStartT = start1s;
+ first->fEndT = start1e;
+ first->resetBounds(fCurve);
+ first->fCoinStart.setPerp(fCurve, start1s, fCurve[0], sect2->fCurve);
+ first->fCoinEnd.setPerp(fCurve, start1e, this->pointLast(), sect2->fCurve);
+ bool oppMatched = first->fCoinStart.perpT() < first->fCoinEnd.perpT();
+ double oppStartT = first->fCoinStart.perpT() == -1 ? 0 : SkTMax(0., first->fCoinStart.perpT());
+ double oppEndT = first->fCoinEnd.perpT() == -1 ? 1 : SkTMin(1., first->fCoinEnd.perpT());
+ if (!oppMatched) {
+ using std::swap;
+ swap(oppStartT, oppEndT);
+ }
+ oppFirst->fStartT = oppStartT;
+ oppFirst->fEndT = oppEndT;
+ oppFirst->resetBounds(sect2->fCurve);
+ this->removeCoincident(first, false);
+ sect2->removeCoincident(oppFirst, true);
+ if (deleteEmptySpans) {
+ this->deleteEmptySpans();
+ sect2->deleteEmptySpans();
+ }
+}
+
+bool SkTSect::coincidentHasT(double t) {
+ SkTSpan* test = fCoincident;
+ while (test) {
+ if (between(test->fStartT, t, test->fEndT)) {
+ return true;
+ }
+ test = test->fNext;
+ }
+ return false;
+}
+
+int SkTSect::collapsed() const {
+ int result = 0;
+ const SkTSpan* test = fHead;
+ while (test) {
+ if (test->fCollapsed) {
+ ++result;
+ }
+ test = test->next();
+ }
+ return result;
+}
+
+void SkTSect::computePerpendiculars(SkTSect* sect2,
+ SkTSpan* first, SkTSpan* last) {
+ const SkTCurve& opp = sect2->fCurve;
+ SkTSpan* work = first;
+ SkTSpan* prior = nullptr;
+ do {
+ if (!work->fHasPerp && !work->fCollapsed) {
+ if (prior) {
+ work->fCoinStart = prior->fCoinEnd;
+ } else {
+ work->fCoinStart.setPerp(fCurve, work->fStartT, work->pointFirst(), opp);
+ }
+ if (work->fCoinStart.isMatch()) {
+ double perpT = work->fCoinStart.perpT();
+ if (sect2->coincidentHasT(perpT)) {
+ work->fCoinStart.init();
+ } else {
+ sect2->addForPerp(work, perpT);
+ }
+ }
+ work->fCoinEnd.setPerp(fCurve, work->fEndT, work->pointLast(), opp);
+ if (work->fCoinEnd.isMatch()) {
+ double perpT = work->fCoinEnd.perpT();
+ if (sect2->coincidentHasT(perpT)) {
+ work->fCoinEnd.init();
+ } else {
+ sect2->addForPerp(work, perpT);
+ }
+ }
+ work->fHasPerp = true;
+ }
+ if (work == last) {
+ break;
+ }
+ prior = work;
+ work = work->fNext;
+ SkASSERT(work);
+ } while (true);
+}
+
+int SkTSect::countConsecutiveSpans(SkTSpan* first,
+ SkTSpan** lastPtr) const {
+ int consecutive = 1;
+ SkTSpan* last = first;
+ do {
+ SkTSpan* next = last->fNext;
+ if (!next) {
+ break;
+ }
+ if (next->fStartT > last->fEndT) {
+ break;
+ }
+ ++consecutive;
+ last = next;
+ } while (true);
+ *lastPtr = last;
+ return consecutive;
+}
+
+bool SkTSect::hasBounded(const SkTSpan* span) const {
+ const SkTSpan* test = fHead;
+ if (!test) {
+ return false;
+ }
+ do {
+ if (test->findOppSpan(span)) {
+ return true;
+ }
+ } while ((test = test->next()));
+ return false;
+}
+
+bool SkTSect::deleteEmptySpans() {
+ SkTSpan* test;
+ SkTSpan* next = fHead;
+ int safetyHatch = 1000;
+ while ((test = next)) {
+ next = test->fNext;
+ if (!test->fBounded) {
+ if (!this->removeSpan(test)) {
+ return false;
+ }
+ }
+ if (--safetyHatch < 0) {
+ return false;
+ }
+ }
+ return true;
+}
+
+bool SkTSect::extractCoincident(
+ SkTSect* sect2,
+ SkTSpan* first, SkTSpan* last,
+ SkTSpan** result) {
+ first = findCoincidentRun(first, &last);
+ if (!first || !last) {
+ *result = nullptr;
+ return true;
+ }
+ // march outwards to find limit of coincidence from here to previous and next spans
+ double startT = first->fStartT;
+ double oppStartT SK_INIT_TO_AVOID_WARNING;
+ double oppEndT SK_INIT_TO_AVOID_WARNING;
+ SkTSpan* prev = first->fPrev;
+ SkASSERT(first->fCoinStart.isMatch());
+ SkTSpan* oppFirst = first->findOppT(first->fCoinStart.perpT());
+ SkOPASSERT(last->fCoinEnd.isMatch());
+ bool oppMatched = first->fCoinStart.perpT() < first->fCoinEnd.perpT();
+ double coinStart;
+ SkDEBUGCODE(double coinEnd);
+ SkTSpan* cutFirst;
+ if (prev && prev->fEndT == startT
+ && this->binarySearchCoin(sect2, startT, prev->fStartT - startT, &coinStart,
+ &oppStartT, &oppFirst)
+ && prev->fStartT < coinStart && coinStart < startT
+ && (cutFirst = prev->oppT(oppStartT))) {
+ oppFirst = cutFirst;
+ first = this->addSplitAt(prev, coinStart);
+ first->markCoincident();
+ prev->fCoinEnd.markCoincident();
+ if (oppFirst->fStartT < oppStartT && oppStartT < oppFirst->fEndT) {
+ SkTSpan* oppHalf = sect2->addSplitAt(oppFirst, oppStartT);
+ if (oppMatched) {
+ oppFirst->fCoinEnd.markCoincident();
+ oppHalf->markCoincident();
+ oppFirst = oppHalf;
+ } else {
+ oppFirst->markCoincident();
+ oppHalf->fCoinStart.markCoincident();
+ }
+ }
+ } else {
+ if (!oppFirst) {
+ return false;
+ }
+ SkDEBUGCODE(coinStart = first->fStartT);
+ SkDEBUGCODE(oppStartT = oppMatched ? oppFirst->fStartT : oppFirst->fEndT);
+ }
+ // FIXME: incomplete : if we're not at the end, find end of coin
+ SkTSpan* oppLast;
+ SkOPASSERT(last->fCoinEnd.isMatch());
+ oppLast = last->findOppT(last->fCoinEnd.perpT());
+ SkDEBUGCODE(coinEnd = last->fEndT);
+#ifdef SK_DEBUG
+ if (!this->globalState() || !this->globalState()->debugSkipAssert()) {
+ oppEndT = oppMatched ? oppLast->fEndT : oppLast->fStartT;
+ }
+#endif
+ if (!oppMatched) {
+ using std::swap;
+ swap(oppFirst, oppLast);
+ swap(oppStartT, oppEndT);
+ }
+ SkOPASSERT(oppStartT < oppEndT);
+ SkASSERT(coinStart == first->fStartT);
+ SkASSERT(coinEnd == last->fEndT);
+ SkOPASSERT(oppStartT == oppFirst->fStartT);
+ SkOPASSERT(oppEndT == oppLast->fEndT);
+ if (!oppFirst) {
+ *result = nullptr;
+ return true;
+ }
+ if (!oppLast) {
+ *result = nullptr;
+ return true;
+ }
+ // reduce coincident runs to single entries
+ this->validate();
+ sect2->validate();
+ bool deleteEmptySpans = this->updateBounded(first, last, oppFirst);
+ deleteEmptySpans |= sect2->updateBounded(oppFirst, oppLast, first);
+ this->removeSpanRange(first, last);
+ sect2->removeSpanRange(oppFirst, oppLast);
+ first->fEndT = last->fEndT;
+ first->resetBounds(this->fCurve);
+ first->fCoinStart.setPerp(fCurve, first->fStartT, first->pointFirst(), sect2->fCurve);
+ first->fCoinEnd.setPerp(fCurve, first->fEndT, first->pointLast(), sect2->fCurve);
+ oppStartT = first->fCoinStart.perpT();
+ oppEndT = first->fCoinEnd.perpT();
+ if (between(0, oppStartT, 1) && between(0, oppEndT, 1)) {
+ if (!oppMatched) {
+ using std::swap;
+ swap(oppStartT, oppEndT);
+ }
+ oppFirst->fStartT = oppStartT;
+ oppFirst->fEndT = oppEndT;
+ oppFirst->resetBounds(sect2->fCurve);
+ }
+ this->validateBounded();
+ sect2->validateBounded();
+ last = first->fNext;
+ if (!this->removeCoincident(first, false)) {
+ return false;
+ }
+ if (!sect2->removeCoincident(oppFirst, true)) {
+ return false;
+ }
+ if (deleteEmptySpans) {
+ if (!this->deleteEmptySpans() || !sect2->deleteEmptySpans()) {
+ *result = nullptr;
+ return false;
+ }
+ }
+ this->validate();
+ sect2->validate();
+ *result = last && !last->fDeleted && fHead && sect2->fHead ? last : nullptr;
+ return true;
+}
+
+SkTSpan* SkTSect::findCoincidentRun(
+ SkTSpan* first, SkTSpan** lastPtr) {
+ SkTSpan* work = first;
+ SkTSpan* lastCandidate = nullptr;
+ first = nullptr;
+ // find the first fully coincident span
+ do {
+ if (work->fCoinStart.isMatch()) {
+#if DEBUG_T_SECT
+ work->validatePerpT(work->fCoinStart.perpT());
+ work->validatePerpPt(work->fCoinStart.perpT(), work->fCoinStart.perpPt());
+#endif
+ SkOPASSERT(work->hasOppT(work->fCoinStart.perpT()));
+ if (!work->fCoinEnd.isMatch()) {
+ break;
+ }
+ lastCandidate = work;
+ if (!first) {
+ first = work;
+ }
+ } else if (first && work->fCollapsed) {
+ *lastPtr = lastCandidate;
+ return first;
+ } else {
+ lastCandidate = nullptr;
+ SkOPASSERT(!first);
+ }
+ if (work == *lastPtr) {
+ return first;
+ }
+ work = work->fNext;
+ if (!work) {
+ return nullptr;
+ }
+ } while (true);
+ if (lastCandidate) {
+ *lastPtr = lastCandidate;
+ }
+ return first;
+}
+
+int SkTSect::intersects(SkTSpan* span,
+ SkTSect* opp,
+ SkTSpan* oppSpan, int* oppResult) {
+ bool spanStart, oppStart;
+ int hullResult = span->hullsIntersect(oppSpan, &spanStart, &oppStart);
+ if (hullResult >= 0) {
+ if (hullResult == 2) { // hulls have one point in common
+ if (!span->fBounded || !span->fBounded->fNext) {
+ SkASSERT(!span->fBounded || span->fBounded->fBounded == oppSpan);
+ if (spanStart) {
+ span->fEndT = span->fStartT;
+ } else {
+ span->fStartT = span->fEndT;
+ }
+ } else {
+ hullResult = 1;
+ }
+ if (!oppSpan->fBounded || !oppSpan->fBounded->fNext) {
+ SkASSERT(!oppSpan->fBounded || oppSpan->fBounded->fBounded == span);
+ if (oppStart) {
+ oppSpan->fEndT = oppSpan->fStartT;
+ } else {
+ oppSpan->fStartT = oppSpan->fEndT;
+ }
+ *oppResult = 2;
+ } else {
+ *oppResult = 1;
+ }
+ } else {
+ *oppResult = 1;
+ }
+ return hullResult;
+ }
+ if (span->fIsLine && oppSpan->fIsLine) {
+ SkIntersections i;
+ int sects = this->linesIntersect(span, opp, oppSpan, &i);
+ if (sects == 2) {
+ return *oppResult = 1;
+ }
+ if (!sects) {
+ return -1;
+ }
+ this->removedEndCheck(span);
+ span->fStartT = span->fEndT = i[0][0];
+ opp->removedEndCheck(oppSpan);
+ oppSpan->fStartT = oppSpan->fEndT = i[1][0];
+ return *oppResult = 2;
+ }
+ if (span->fIsLinear || oppSpan->fIsLinear) {
+ return *oppResult = (int) span->linearsIntersect(oppSpan);
+ }
+ return *oppResult = 1;
+}
+
+template<typename SkTCurve>
+static bool is_parallel(const SkDLine& thisLine, const SkTCurve& opp) {
+ if (!opp.IsConic()) {
+ return false; // FIXME : breaks a lot of stuff now
+ }
+ int finds = 0;
+ SkDLine thisPerp;
+ thisPerp.fPts[0].fX = thisLine.fPts[1].fX + (thisLine.fPts[1].fY - thisLine.fPts[0].fY);
+ thisPerp.fPts[0].fY = thisLine.fPts[1].fY + (thisLine.fPts[0].fX - thisLine.fPts[1].fX);
+ thisPerp.fPts[1] = thisLine.fPts[1];
+ SkIntersections perpRayI;
+ perpRayI.intersectRay(opp, thisPerp);
+ for (int pIndex = 0; pIndex < perpRayI.used(); ++pIndex) {
+ finds += perpRayI.pt(pIndex).approximatelyEqual(thisPerp.fPts[1]);
+ }
+ thisPerp.fPts[1].fX = thisLine.fPts[0].fX + (thisLine.fPts[1].fY - thisLine.fPts[0].fY);
+ thisPerp.fPts[1].fY = thisLine.fPts[0].fY + (thisLine.fPts[0].fX - thisLine.fPts[1].fX);
+ thisPerp.fPts[0] = thisLine.fPts[0];
+ perpRayI.intersectRay(opp, thisPerp);
+ for (int pIndex = 0; pIndex < perpRayI.used(); ++pIndex) {
+ finds += perpRayI.pt(pIndex).approximatelyEqual(thisPerp.fPts[0]);
+ }
+ return finds >= 2;
+}
+
+// while the intersection points are sufficiently far apart:
+// construct the tangent lines from the intersections
+// find the point where the tangent line intersects the opposite curve
+
+int SkTSect::linesIntersect(SkTSpan* span,
+ SkTSect* opp,
+ SkTSpan* oppSpan, SkIntersections* i) {
+ SkIntersections thisRayI SkDEBUGCODE((span->fDebugGlobalState));
+ SkIntersections oppRayI SkDEBUGCODE((span->fDebugGlobalState));
+ SkDLine thisLine = {{ span->pointFirst(), span->pointLast() }};
+ SkDLine oppLine = {{ oppSpan->pointFirst(), oppSpan->pointLast() }};
+ int loopCount = 0;
+ double bestDistSq = DBL_MAX;
+ if (!thisRayI.intersectRay(opp->fCurve, thisLine)) {
+ return 0;
+ }
+ if (!oppRayI.intersectRay(this->fCurve, oppLine)) {
+ return 0;
+ }
+ // if the ends of each line intersect the opposite curve, the lines are coincident
+ if (thisRayI.used() > 1) {
+ int ptMatches = 0;
+ for (int tIndex = 0; tIndex < thisRayI.used(); ++tIndex) {
+ for (int lIndex = 0; lIndex < (int) SK_ARRAY_COUNT(thisLine.fPts); ++lIndex) {
+ ptMatches += thisRayI.pt(tIndex).approximatelyEqual(thisLine.fPts[lIndex]);
+ }
+ }
+ if (ptMatches == 2 || is_parallel(thisLine, opp->fCurve)) {
+ return 2;
+ }
+ }
+ if (oppRayI.used() > 1) {
+ int ptMatches = 0;
+ for (int oIndex = 0; oIndex < oppRayI.used(); ++oIndex) {
+ for (int lIndex = 0; lIndex < (int) SK_ARRAY_COUNT(oppLine.fPts); ++lIndex) {
+ ptMatches += oppRayI.pt(oIndex).approximatelyEqual(oppLine.fPts[lIndex]);
+ }
+ }
+ if (ptMatches == 2|| is_parallel(oppLine, this->fCurve)) {
+ return 2;
+ }
+ }
+ do {
+ // pick the closest pair of points
+ double closest = DBL_MAX;
+ int closeIndex SK_INIT_TO_AVOID_WARNING;
+ int oppCloseIndex SK_INIT_TO_AVOID_WARNING;
+ for (int index = 0; index < oppRayI.used(); ++index) {
+ if (!roughly_between(span->fStartT, oppRayI[0][index], span->fEndT)) {
+ continue;
+ }
+ for (int oIndex = 0; oIndex < thisRayI.used(); ++oIndex) {
+ if (!roughly_between(oppSpan->fStartT, thisRayI[0][oIndex], oppSpan->fEndT)) {
+ continue;
+ }
+ double distSq = thisRayI.pt(index).distanceSquared(oppRayI.pt(oIndex));
+ if (closest > distSq) {
+ closest = distSq;
+ closeIndex = index;
+ oppCloseIndex = oIndex;
+ }
+ }
+ }
+ if (closest == DBL_MAX) {
+ break;
+ }
+ const SkDPoint& oppIPt = thisRayI.pt(oppCloseIndex);
+ const SkDPoint& iPt = oppRayI.pt(closeIndex);
+ if (between(span->fStartT, oppRayI[0][closeIndex], span->fEndT)
+ && between(oppSpan->fStartT, thisRayI[0][oppCloseIndex], oppSpan->fEndT)
+ && oppIPt.approximatelyEqual(iPt)) {
+ i->merge(oppRayI, closeIndex, thisRayI, oppCloseIndex);
+ return i->used();
+ }
+ double distSq = oppIPt.distanceSquared(iPt);
+ if (bestDistSq < distSq || ++loopCount > 5) {
+ return 0;
+ }
+ bestDistSq = distSq;
+ double oppStart = oppRayI[0][closeIndex];
+ thisLine[0] = fCurve.ptAtT(oppStart);
+ thisLine[1] = thisLine[0] + fCurve.dxdyAtT(oppStart);
+ if (!thisRayI.intersectRay(opp->fCurve, thisLine)) {
+ break;
+ }
+ double start = thisRayI[0][oppCloseIndex];
+ oppLine[0] = opp->fCurve.ptAtT(start);
+ oppLine[1] = oppLine[0] + opp->fCurve.dxdyAtT(start);
+ if (!oppRayI.intersectRay(this->fCurve, oppLine)) {
+ break;
+ }
+ } while (true);
+ // convergence may fail if the curves are nearly coincident
+ SkTCoincident oCoinS, oCoinE;
+ oCoinS.setPerp(opp->fCurve, oppSpan->fStartT, oppSpan->pointFirst(), fCurve);
+ oCoinE.setPerp(opp->fCurve, oppSpan->fEndT, oppSpan->pointLast(), fCurve);
+ double tStart = oCoinS.perpT();
+ double tEnd = oCoinE.perpT();
+ bool swap = tStart > tEnd;
+ if (swap) {
+ using std::swap;
+ swap(tStart, tEnd);
+ }
+ tStart = SkTMax(tStart, span->fStartT);
+ tEnd = SkTMin(tEnd, span->fEndT);
+ if (tStart > tEnd) {
+ return 0;
+ }
+ SkDVector perpS, perpE;
+ if (tStart == span->fStartT) {
+ SkTCoincident coinS;
+ coinS.setPerp(fCurve, span->fStartT, span->pointFirst(), opp->fCurve);
+ perpS = span->pointFirst() - coinS.perpPt();
+ } else if (swap) {
+ perpS = oCoinE.perpPt() - oppSpan->pointLast();
+ } else {
+ perpS = oCoinS.perpPt() - oppSpan->pointFirst();
+ }
+ if (tEnd == span->fEndT) {
+ SkTCoincident coinE;
+ coinE.setPerp(fCurve, span->fEndT, span->pointLast(), opp->fCurve);
+ perpE = span->pointLast() - coinE.perpPt();
+ } else if (swap) {
+ perpE = oCoinS.perpPt() - oppSpan->pointFirst();
+ } else {
+ perpE = oCoinE.perpPt() - oppSpan->pointLast();
+ }
+ if (perpS.dot(perpE) >= 0) {
+ return 0;
+ }
+ SkTCoincident coinW;
+ double workT = tStart;
+ double tStep = tEnd - tStart;
+ SkDPoint workPt;
+ do {
+ tStep *= 0.5;
+ if (precisely_zero(tStep)) {
+ return 0;
+ }
+ workT += tStep;
+ workPt = fCurve.ptAtT(workT);
+ coinW.setPerp(fCurve, workT, workPt, opp->fCurve);
+ double perpT = coinW.perpT();
+ if (coinW.isMatch() ? !between(oppSpan->fStartT, perpT, oppSpan->fEndT) : perpT < 0) {
+ continue;
+ }
+ SkDVector perpW = workPt - coinW.perpPt();
+ if ((perpS.dot(perpW) >= 0) == (tStep < 0)) {
+ tStep = -tStep;
+ }
+ if (workPt.approximatelyEqual(coinW.perpPt())) {
+ break;
+ }
+ } while (true);
+ double oppTTest = coinW.perpT();
+ if (!opp->fHead->contains(oppTTest)) {
+ return 0;
+ }
+ i->setMax(1);
+ i->insert(workT, oppTTest, workPt);
+ return 1;
+}
+
+bool SkTSect::markSpanGone(SkTSpan* span) {
+ if (--fActiveCount < 0) {
+ return false;
+ }
+ span->fNext = fDeleted;
+ fDeleted = span;
+ SkOPASSERT(!span->fDeleted);
+ span->fDeleted = true;
+ return true;
+}
+
+bool SkTSect::matchedDirection(double t, const SkTSect* sect2,
+ double t2) const {
+ SkDVector dxdy = this->fCurve.dxdyAtT(t);
+ SkDVector dxdy2 = sect2->fCurve.dxdyAtT(t2);
+ return dxdy.dot(dxdy2) >= 0;
+}
+
+void SkTSect::matchedDirCheck(double t, const SkTSect* sect2,
+ double t2, bool* calcMatched, bool* oppMatched) const {
+ if (*calcMatched) {
+ SkASSERT(*oppMatched == this->matchedDirection(t, sect2, t2));
+ } else {
+ *oppMatched = this->matchedDirection(t, sect2, t2);
+ *calcMatched = true;
+ }
+}
+
+void SkTSect::mergeCoincidence(SkTSect* sect2) {
+ double smallLimit = 0;
+ do {
+ // find the smallest unprocessed span
+ SkTSpan* smaller = nullptr;
+ SkTSpan* test = fCoincident;
+ do {
+ if (!test) {
+ return;
+ }
+ if (test->fStartT < smallLimit) {
+ continue;
+ }
+ if (smaller && smaller->fEndT < test->fStartT) {
+ continue;
+ }
+ smaller = test;
+ } while ((test = test->fNext));
+ if (!smaller) {
+ return;
+ }
+ smallLimit = smaller->fEndT;
+ // find next larger span
+ SkTSpan* prior = nullptr;
+ SkTSpan* larger = nullptr;
+ SkTSpan* largerPrior = nullptr;
+ test = fCoincident;
+ do {
+ if (test->fStartT < smaller->fEndT) {
+ continue;
+ }
+ SkOPASSERT(test->fStartT != smaller->fEndT);
+ if (larger && larger->fStartT < test->fStartT) {
+ continue;
+ }
+ largerPrior = prior;
+ larger = test;
+ } while ((void) (prior = test), (test = test->fNext));
+ if (!larger) {
+ continue;
+ }
+ // check middle t value to see if it is coincident as well
+ double midT = (smaller->fEndT + larger->fStartT) / 2;
+ SkDPoint midPt = fCurve.ptAtT(midT);
+ SkTCoincident coin;
+ coin.setPerp(fCurve, midT, midPt, sect2->fCurve);
+ if (coin.isMatch()) {
+ smaller->fEndT = larger->fEndT;
+ smaller->fCoinEnd = larger->fCoinEnd;
+ if (largerPrior) {
+ largerPrior->fNext = larger->fNext;
+ largerPrior->validate();
+ } else {
+ fCoincident = larger->fNext;
+ }
+ }
+ } while (true);
+}
+
+SkTSpan* SkTSect::prev(
+ SkTSpan* span) const {
+ SkTSpan* result = nullptr;
+ SkTSpan* test = fHead;
+ while (span != test) {
+ result = test;
+ test = test->fNext;
+ SkASSERT(test);
+ }
+ return result;
+}
+
+void SkTSect::recoverCollapsed() {
+ SkTSpan* deleted = fDeleted;
+ while (deleted) {
+ SkTSpan* delNext = deleted->fNext;
+ if (deleted->fCollapsed) {
+ SkTSpan** spanPtr = &fHead;
+ while (*spanPtr && (*spanPtr)->fEndT <= deleted->fStartT) {
+ spanPtr = &(*spanPtr)->fNext;
+ }
+ deleted->fNext = *spanPtr;
+ *spanPtr = deleted;
+ }
+ deleted = delNext;
+ }
+}
+
+void SkTSect::removeAllBut(const SkTSpan* keep,
+ SkTSpan* span, SkTSect* opp) {
+ const SkTSpanBounded* testBounded = span->fBounded;
+ while (testBounded) {
+ SkTSpan* bounded = testBounded->fBounded;
+ const SkTSpanBounded* next = testBounded->fNext;
+ // may have been deleted when opp did 'remove all but'
+ if (bounded != keep && !bounded->fDeleted) {
+ SkAssertResult(SkDEBUGCODE(!) span->removeBounded(bounded));
+ if (bounded->removeBounded(span)) {
+ opp->removeSpan(bounded);
+ }
+ }
+ testBounded = next;
+ }
+ SkASSERT(!span->fDeleted);
+ SkASSERT(span->findOppSpan(keep));
+ SkASSERT(keep->findOppSpan(span));
+}
+
+bool SkTSect::removeByPerpendicular(SkTSect* opp) {
+ SkTSpan* test = fHead;
+ SkTSpan* next;
+ do {
+ next = test->fNext;
+ if (test->fCoinStart.perpT() < 0 || test->fCoinEnd.perpT() < 0) {
+ continue;
+ }
+ SkDVector startV = test->fCoinStart.perpPt() - test->pointFirst();
+ SkDVector endV = test->fCoinEnd.perpPt() - test->pointLast();
+#if DEBUG_T_SECT
+ SkDebugf("%s startV=(%1.9g,%1.9g) endV=(%1.9g,%1.9g) dot=%1.9g\n", __FUNCTION__,
+ startV.fX, startV.fY, endV.fX, endV.fY, startV.dot(endV));
+#endif
+ if (startV.dot(endV) <= 0) {
+ continue;
+ }
+ if (!this->removeSpans(test, opp)) {
+ return false;
+ }
+ } while ((test = next));
+ return true;
+}
+
+bool SkTSect::removeCoincident(SkTSpan* span, bool isBetween) {
+ if (!this->unlinkSpan(span)) {
+ return false;
+ }
+ if (isBetween || between(0, span->fCoinStart.perpT(), 1)) {
+ --fActiveCount;
+ span->fNext = fCoincident;
+ fCoincident = span;
+ } else {
+ this->markSpanGone(span);
+ }
+ return true;
+}
+
+void SkTSect::removedEndCheck(SkTSpan* span) {
+ if (!span->fStartT) {
+ fRemovedStartT = true;
+ }
+ if (1 == span->fEndT) {
+ fRemovedEndT = true;
+ }
+}
+
+bool SkTSect::removeSpan(SkTSpan* span) {\
+ this->removedEndCheck(span);
+ if (!this->unlinkSpan(span)) {
+ return false;
+ }
+ return this->markSpanGone(span);
+}
+
+void SkTSect::removeSpanRange(SkTSpan* first,
+ SkTSpan* last) {
+ if (first == last) {
+ return;
+ }
+ SkTSpan* span = first;
+ SkASSERT(span);
+ SkTSpan* final = last->fNext;
+ SkTSpan* next = span->fNext;
+ while ((span = next) && span != final) {
+ next = span->fNext;
+ this->markSpanGone(span);
+ }
+ if (final) {
+ final->fPrev = first;
+ }
+ first->fNext = final;
+ // world may not be ready for validation here
+ first->validate();
+}
+
+bool SkTSect::removeSpans(SkTSpan* span,
+ SkTSect* opp) {
+ SkTSpanBounded* bounded = span->fBounded;
+ while (bounded) {
+ SkTSpan* spanBounded = bounded->fBounded;
+ SkTSpanBounded* next = bounded->fNext;
+ if (span->removeBounded(spanBounded)) { // shuffles last into position 0
+ this->removeSpan(span);
+ }
+ if (spanBounded->removeBounded(span)) {
+ opp->removeSpan(spanBounded);
+ }
+ if (span->fDeleted && opp->hasBounded(span)) {
+ return false;
+ }
+ bounded = next;
+ }
+ return true;
+}
+
+SkTSpan* SkTSect::spanAtT(double t,
+ SkTSpan** priorSpan) {
+ SkTSpan* test = fHead;
+ SkTSpan* prev = nullptr;
+ while (test && test->fEndT < t) {
+ prev = test;
+ test = test->fNext;
+ }
+ *priorSpan = prev;
+ return test && test->fStartT <= t ? test : nullptr;
+}
+
+SkTSpan* SkTSect::tail() {
+ SkTSpan* result = fHead;
+ SkTSpan* next = fHead;
+ while ((next = next->fNext)) {
+ if (next->fEndT > result->fEndT) {
+ result = next;
+ }
+ }
+ return result;
+}
+
+/* Each span has a range of opposite spans it intersects. After the span is split in two,
+ adjust the range to its new size */
+
+bool SkTSect::trim(SkTSpan* span,
+ SkTSect* opp) {
+ FAIL_IF(!span->initBounds(fCurve));
+ const SkTSpanBounded* testBounded = span->fBounded;
+ while (testBounded) {
+ SkTSpan* test = testBounded->fBounded;
+ const SkTSpanBounded* next = testBounded->fNext;
+ int oppSects, sects = this->intersects(span, opp, test, &oppSects);
+ if (sects >= 1) {
+ if (oppSects == 2) {
+ test->initBounds(opp->fCurve);
+ opp->removeAllBut(span, test, this);
+ }
+ if (sects == 2) {
+ span->initBounds(fCurve);
+ this->removeAllBut(test, span, opp);
+ return true;
+ }
+ } else {
+ if (span->removeBounded(test)) {
+ this->removeSpan(span);
+ }
+ if (test->removeBounded(span)) {
+ opp->removeSpan(test);
+ }
+ }
+ testBounded = next;
+ }
+ return true;
+}
+
+bool SkTSect::unlinkSpan(SkTSpan* span) {
+ SkTSpan* prev = span->fPrev;
+ SkTSpan* next = span->fNext;
+ if (prev) {
+ prev->fNext = next;
+ if (next) {
+ next->fPrev = prev;
+ if (next->fStartT > next->fEndT) {
+ return false;
+ }
+ // world may not be ready for validate here
+ next->validate();
+ }
+ } else {
+ fHead = next;
+ if (next) {
+ next->fPrev = nullptr;
+ }
+ }
+ return true;
+}
+
+bool SkTSect::updateBounded(SkTSpan* first,
+ SkTSpan* last, SkTSpan* oppFirst) {
+ SkTSpan* test = first;
+ const SkTSpan* final = last->next();
+ bool deleteSpan = false;
+ do {
+ deleteSpan |= test->removeAllBounded();
+ } while ((test = test->fNext) != final && test);
+ first->fBounded = nullptr;
+ first->addBounded(oppFirst, &fHeap);
+ // cannot call validate until remove span range is called
+ return deleteSpan;
+}
+
+void SkTSect::validate() const {
+#if DEBUG_VALIDATE
+ int count = 0;
+ double last = 0;
+ if (fHead) {
+ const SkTSpan* span = fHead;
+ SkASSERT(!span->fPrev);
+ const SkTSpan* next;
+ do {
+ span->validate();
+ SkASSERT(span->fStartT >= last);
+ last = span->fEndT;
+ ++count;
+ next = span->fNext;
+ SkASSERT(next != span);
+ } while ((span = next) != nullptr);
+ }
+ SkASSERT(count == fActiveCount);
+#endif
+#if DEBUG_T_SECT
+ SkASSERT(fActiveCount <= fDebugAllocatedCount);
+ int deletedCount = 0;
+ const SkTSpan* deleted = fDeleted;
+ while (deleted) {
+ ++deletedCount;
+ deleted = deleted->fNext;
+ }
+ const SkTSpan* coincident = fCoincident;
+ while (coincident) {
+ ++deletedCount;
+ coincident = coincident->fNext;
+ }
+ SkASSERT(fActiveCount + deletedCount == fDebugAllocatedCount);
+#endif
+}
+
+void SkTSect::validateBounded() const {
+#if DEBUG_VALIDATE
+ if (!fHead) {
+ return;
+ }
+ const SkTSpan* span = fHead;
+ do {
+ span->validateBounded();
+ } while ((span = span->fNext) != nullptr);
+#endif
+}
+
+int SkTSect::EndsEqual(const SkTSect* sect1,
+ const SkTSect* sect2, SkIntersections* intersections) {
+ int zeroOneSet = 0;
+ if (sect1->fCurve[0] == sect2->fCurve[0]) {
+ zeroOneSet |= kZeroS1Set | kZeroS2Set;
+ intersections->insert(0, 0, sect1->fCurve[0]);
+ }
+ if (sect1->fCurve[0] == sect2->pointLast()) {
+ zeroOneSet |= kZeroS1Set | kOneS2Set;
+ intersections->insert(0, 1, sect1->fCurve[0]);
+ }
+ if (sect1->pointLast() == sect2->fCurve[0]) {
+ zeroOneSet |= kOneS1Set | kZeroS2Set;
+ intersections->insert(1, 0, sect1->pointLast());
+ }
+ if (sect1->pointLast() == sect2->pointLast()) {
+ zeroOneSet |= kOneS1Set | kOneS2Set;
+ intersections->insert(1, 1, sect1->pointLast());
+ }
+ // check for zero
+ if (!(zeroOneSet & (kZeroS1Set | kZeroS2Set))
+ && sect1->fCurve[0].approximatelyEqual(sect2->fCurve[0])) {
+ zeroOneSet |= kZeroS1Set | kZeroS2Set;
+ intersections->insertNear(0, 0, sect1->fCurve[0], sect2->fCurve[0]);
+ }
+ if (!(zeroOneSet & (kZeroS1Set | kOneS2Set))
+ && sect1->fCurve[0].approximatelyEqual(sect2->pointLast())) {
+ zeroOneSet |= kZeroS1Set | kOneS2Set;
+ intersections->insertNear(0, 1, sect1->fCurve[0], sect2->pointLast());
+ }
+ // check for one
+ if (!(zeroOneSet & (kOneS1Set | kZeroS2Set))
+ && sect1->pointLast().approximatelyEqual(sect2->fCurve[0])) {
+ zeroOneSet |= kOneS1Set | kZeroS2Set;
+ intersections->insertNear(1, 0, sect1->pointLast(), sect2->fCurve[0]);
+ }
+ if (!(zeroOneSet & (kOneS1Set | kOneS2Set))
+ && sect1->pointLast().approximatelyEqual(sect2->pointLast())) {
+ zeroOneSet |= kOneS1Set | kOneS2Set;
+ intersections->insertNear(1, 1, sect1->pointLast(), sect2->pointLast());
+ }
+ return zeroOneSet;
+}
+
+struct SkClosestRecord {
+ bool operator<(const SkClosestRecord& rh) const {
+ return fClosest < rh.fClosest;
+ }
+
+ void addIntersection(SkIntersections* intersections) const {
+ double r1t = fC1Index ? fC1Span->endT() : fC1Span->startT();
+ double r2t = fC2Index ? fC2Span->endT() : fC2Span->startT();
+ intersections->insert(r1t, r2t, fC1Span->part()[fC1Index]);
+ }
+
+ void findEnd(const SkTSpan* span1, const SkTSpan* span2,
+ int c1Index, int c2Index) {
+ const SkTCurve& c1 = span1->part();
+ const SkTCurve& c2 = span2->part();
+ if (!c1[c1Index].approximatelyEqual(c2[c2Index])) {
+ return;
+ }
+ double dist = c1[c1Index].distanceSquared(c2[c2Index]);
+ if (fClosest < dist) {
+ return;
+ }
+ fC1Span = span1;
+ fC2Span = span2;
+ fC1StartT = span1->startT();
+ fC1EndT = span1->endT();
+ fC2StartT = span2->startT();
+ fC2EndT = span2->endT();
+ fC1Index = c1Index;
+ fC2Index = c2Index;
+ fClosest = dist;
+ }
+
+ bool matesWith(const SkClosestRecord& mate SkDEBUGPARAMS(SkIntersections* i)) const {
+ SkOPOBJASSERT(i, fC1Span == mate.fC1Span || fC1Span->endT() <= mate.fC1Span->startT()
+ || mate.fC1Span->endT() <= fC1Span->startT());
+ SkOPOBJASSERT(i, fC2Span == mate.fC2Span || fC2Span->endT() <= mate.fC2Span->startT()
+ || mate.fC2Span->endT() <= fC2Span->startT());
+ return fC1Span == mate.fC1Span || fC1Span->endT() == mate.fC1Span->startT()
+ || fC1Span->startT() == mate.fC1Span->endT()
+ || fC2Span == mate.fC2Span
+ || fC2Span->endT() == mate.fC2Span->startT()
+ || fC2Span->startT() == mate.fC2Span->endT();
+ }
+
+ void merge(const SkClosestRecord& mate) {
+ fC1Span = mate.fC1Span;
+ fC2Span = mate.fC2Span;
+ fClosest = mate.fClosest;
+ fC1Index = mate.fC1Index;
+ fC2Index = mate.fC2Index;
+ }
+
+ void reset() {
+ fClosest = FLT_MAX;
+ SkDEBUGCODE(fC1Span = nullptr);
+ SkDEBUGCODE(fC2Span = nullptr);
+ SkDEBUGCODE(fC1Index = fC2Index = -1);
+ }
+
+ void update(const SkClosestRecord& mate) {
+ fC1StartT = SkTMin(fC1StartT, mate.fC1StartT);
+ fC1EndT = SkTMax(fC1EndT, mate.fC1EndT);
+ fC2StartT = SkTMin(fC2StartT, mate.fC2StartT);
+ fC2EndT = SkTMax(fC2EndT, mate.fC2EndT);
+ }
+
+ const SkTSpan* fC1Span;
+ const SkTSpan* fC2Span;
+ double fC1StartT;
+ double fC1EndT;
+ double fC2StartT;
+ double fC2EndT;
+ double fClosest;
+ int fC1Index;
+ int fC2Index;
+};
+
+struct SkClosestSect {
+ SkClosestSect()
+ : fUsed(0) {
+ fClosest.push_back().reset();
+ }
+
+ bool find(const SkTSpan* span1, const SkTSpan* span2
+ SkDEBUGPARAMS(SkIntersections* i)) {
+ SkClosestRecord* record = &fClosest[fUsed];
+ record->findEnd(span1, span2, 0, 0);
+ record->findEnd(span1, span2, 0, span2->part().pointLast());
+ record->findEnd(span1, span2, span1->part().pointLast(), 0);
+ record->findEnd(span1, span2, span1->part().pointLast(), span2->part().pointLast());
+ if (record->fClosest == FLT_MAX) {
+ return false;
+ }
+ for (int index = 0; index < fUsed; ++index) {
+ SkClosestRecord* test = &fClosest[index];
+ if (test->matesWith(*record SkDEBUGPARAMS(i))) {
+ if (test->fClosest > record->fClosest) {
+ test->merge(*record);
+ }
+ test->update(*record);
+ record->reset();
+ return false;
+ }
+ }
+ ++fUsed;
+ fClosest.push_back().reset();
+ return true;
+ }
+
+ void finish(SkIntersections* intersections) const {
+ SkSTArray<SkDCubic::kMaxIntersections * 3,
+ const SkClosestRecord*, true> closestPtrs;
+ for (int index = 0; index < fUsed; ++index) {
+ closestPtrs.push_back(&fClosest[index]);
+ }
+ SkTQSort<const SkClosestRecord >(closestPtrs.begin(), closestPtrs.end()
+ - 1);
+ for (int index = 0; index < fUsed; ++index) {
+ const SkClosestRecord* test = closestPtrs[index];
+ test->addIntersection(intersections);
+ }
+ }
+
+ // this is oversized so that an extra records can merge into final one
+ SkSTArray<SkDCubic::kMaxIntersections * 2, SkClosestRecord, true> fClosest;
+ int fUsed;
+};
+
+// returns true if the rect is too small to consider
+
+void SkTSect::BinarySearch(SkTSect* sect1,
+ SkTSect* sect2, SkIntersections* intersections) {
+#if DEBUG_T_SECT_DUMP > 1
+ gDumpTSectNum = 0;
+#endif
+ SkDEBUGCODE(sect1->fOppSect = sect2);
+ SkDEBUGCODE(sect2->fOppSect = sect1);
+ intersections->reset();
+ intersections->setMax(sect1->fCurve.maxIntersections() + 4); // give extra for slop
+ SkTSpan* span1 = sect1->fHead;
+ SkTSpan* span2 = sect2->fHead;
+ int oppSect, sect = sect1->intersects(span1, sect2, span2, &oppSect);
+// SkASSERT(between(0, sect, 2));
+ if (!sect) {
+ return;
+ }
+ if (sect == 2 && oppSect == 2) {
+ (void) EndsEqual(sect1, sect2, intersections);
+ return;
+ }
+ span1->addBounded(span2, §1->fHeap);
+ span2->addBounded(span1, §2->fHeap);
+ const int kMaxCoinLoopCount = 8;
+ int coinLoopCount = kMaxCoinLoopCount;
+ double start1s SK_INIT_TO_AVOID_WARNING;
+ double start1e SK_INIT_TO_AVOID_WARNING;
+ do {
+ // find the largest bounds
+ SkTSpan* largest1 = sect1->boundsMax();
+ if (!largest1) {
+ if (sect1->fHung) {
+ return;
+ }
+ break;
+ }
+ SkTSpan* largest2 = sect2->boundsMax();
+ // split it
+ if (!largest2 || (largest1 && (largest1->fBoundsMax > largest2->fBoundsMax
+ || (!largest1->fCollapsed && largest2->fCollapsed)))) {
+ if (sect2->fHung) {
+ return;
+ }
+ if (largest1->fCollapsed) {
+ break;
+ }
+ sect1->resetRemovedEnds();
+ sect2->resetRemovedEnds();
+ // trim parts that don't intersect the opposite
+ SkTSpan* half1 = sect1->addOne();
+ SkDEBUGCODE(half1->debugSetGlobalState(sect1->globalState()));
+ if (!half1->split(largest1, §1->fHeap)) {
+ break;
+ }
+ if (!sect1->trim(largest1, sect2)) {
+ SkOPOBJASSERT(intersections, 0);
+ return;
+ }
+ if (!sect1->trim(half1, sect2)) {
+ SkOPOBJASSERT(intersections, 0);
+ return;
+ }
+ } else {
+ if (largest2->fCollapsed) {
+ break;
+ }
+ sect1->resetRemovedEnds();
+ sect2->resetRemovedEnds();
+ // trim parts that don't intersect the opposite
+ SkTSpan* half2 = sect2->addOne();
+ SkDEBUGCODE(half2->debugSetGlobalState(sect2->globalState()));
+ if (!half2->split(largest2, §2->fHeap)) {
+ break;
+ }
+ if (!sect2->trim(largest2, sect1)) {
+ SkOPOBJASSERT(intersections, 0);
+ return;
+ }
+ if (!sect2->trim(half2, sect1)) {
+ SkOPOBJASSERT(intersections, 0);
+ return;
+ }
+ }
+ sect1->validate();
+ sect2->validate();
+#if DEBUG_T_SECT_LOOP_COUNT
+ intersections->debugBumpLoopCount(SkIntersections::kIterations_DebugLoop);
+#endif
+ // if there are 9 or more continuous spans on both sects, suspect coincidence
+ if (sect1->fActiveCount >= COINCIDENT_SPAN_COUNT
+ && sect2->fActiveCount >= COINCIDENT_SPAN_COUNT) {
+ if (coinLoopCount == kMaxCoinLoopCount) {
+ start1s = sect1->fHead->fStartT;
+ start1e = sect1->tail()->fEndT;
+ }
+ if (!sect1->coincidentCheck(sect2)) {
+ return;
+ }
+ sect1->validate();
+ sect2->validate();
+#if DEBUG_T_SECT_LOOP_COUNT
+ intersections->debugBumpLoopCount(SkIntersections::kCoinCheck_DebugLoop);
+#endif
+ if (!--coinLoopCount && sect1->fHead && sect2->fHead) {
+ /* All known working cases resolve in two tries. Sadly, cubicConicTests[0]
+ gets stuck in a loop. It adds an extension to allow a coincident end
+ perpendicular to track its intersection in the opposite curve. However,
+ the bounding box of the extension does not intersect the original curve,
+ so the extension is discarded, only to be added again the next time around. */
+ sect1->coincidentForce(sect2, start1s, start1e);
+ sect1->validate();
+ sect2->validate();
+ }
+ }
+ if (sect1->fActiveCount >= COINCIDENT_SPAN_COUNT
+ && sect2->fActiveCount >= COINCIDENT_SPAN_COUNT) {
+ if (!sect1->fHead) {
+ return;
+ }
+ sect1->computePerpendiculars(sect2, sect1->fHead, sect1->tail());
+ if (!sect2->fHead) {
+ return;
+ }
+ sect2->computePerpendiculars(sect1, sect2->fHead, sect2->tail());
+ if (!sect1->removeByPerpendicular(sect2)) {
+ return;
+ }
+ sect1->validate();
+ sect2->validate();
+#if DEBUG_T_SECT_LOOP_COUNT
+ intersections->debugBumpLoopCount(SkIntersections::kComputePerp_DebugLoop);
+#endif
+ if (sect1->collapsed() > sect1->fCurve.maxIntersections()) {
+ break;
+ }
+ }
+#if DEBUG_T_SECT_DUMP
+ sect1->dumpBoth(sect2);
+#endif
+ if (!sect1->fHead || !sect2->fHead) {
+ break;
+ }
+ } while (true);
+ SkTSpan* coincident = sect1->fCoincident;
+ if (coincident) {
+ // if there is more than one coincident span, check loosely to see if they should be joined
+ if (coincident->fNext) {
+ sect1->mergeCoincidence(sect2);
+ coincident = sect1->fCoincident;
+ }
+ SkASSERT(sect2->fCoincident); // courtesy check : coincidence only looks at sect 1
+ do {
+ if (!coincident) {
+ return;
+ }
+ if (!coincident->fCoinStart.isMatch()) {
+ continue;
+ }
+ if (!coincident->fCoinEnd.isMatch()) {
+ continue;
+ }
+ double perpT = coincident->fCoinStart.perpT();
+ if (perpT < 0) {
+ return;
+ }
+ int index = intersections->insertCoincident(coincident->fStartT,
+ perpT, coincident->pointFirst());
+ if ((intersections->insertCoincident(coincident->fEndT,
+ coincident->fCoinEnd.perpT(),
+ coincident->pointLast()) < 0) && index >= 0) {
+ intersections->clearCoincidence(index);
+ }
+ } while ((coincident = coincident->fNext));
+ }
+ int zeroOneSet = EndsEqual(sect1, sect2, intersections);
+// if (!sect1->fHead || !sect2->fHead) {
+ // if the final iteration contains an end (0 or 1),
+ if (sect1->fRemovedStartT && !(zeroOneSet & kZeroS1Set)) {
+ SkTCoincident perp; // intersect perpendicular with opposite curve
+ perp.setPerp(sect1->fCurve, 0, sect1->fCurve[0], sect2->fCurve);
+ if (perp.isMatch()) {
+ intersections->insert(0, perp.perpT(), perp.perpPt());
+ }
+ }
+ if (sect1->fRemovedEndT && !(zeroOneSet & kOneS1Set)) {
+ SkTCoincident perp;
+ perp.setPerp(sect1->fCurve, 1, sect1->pointLast(), sect2->fCurve);
+ if (perp.isMatch()) {
+ intersections->insert(1, perp.perpT(), perp.perpPt());
+ }
+ }
+ if (sect2->fRemovedStartT && !(zeroOneSet & kZeroS2Set)) {
+ SkTCoincident perp;
+ perp.setPerp(sect2->fCurve, 0, sect2->fCurve[0], sect1->fCurve);
+ if (perp.isMatch()) {
+ intersections->insert(perp.perpT(), 0, perp.perpPt());
+ }
+ }
+ if (sect2->fRemovedEndT && !(zeroOneSet & kOneS2Set)) {
+ SkTCoincident perp;
+ perp.setPerp(sect2->fCurve, 1, sect2->pointLast(), sect1->fCurve);
+ if (perp.isMatch()) {
+ intersections->insert(perp.perpT(), 1, perp.perpPt());
+ }
+ }
+// }
+ if (!sect1->fHead || !sect2->fHead) {
+ return;
+ }
+ sect1->recoverCollapsed();
+ sect2->recoverCollapsed();
+ SkTSpan* result1 = sect1->fHead;
+ // check heads and tails for zero and ones and insert them if we haven't already done so
+ const SkTSpan* head1 = result1;
+ if (!(zeroOneSet & kZeroS1Set) && approximately_less_than_zero(head1->fStartT)) {
+ const SkDPoint& start1 = sect1->fCurve[0];
+ if (head1->isBounded()) {
+ double t = head1->closestBoundedT(start1);
+ if (sect2->fCurve.ptAtT(t).approximatelyEqual(start1)) {
+ intersections->insert(0, t, start1);
+ }
+ }
+ }
+ const SkTSpan* head2 = sect2->fHead;
+ if (!(zeroOneSet & kZeroS2Set) && approximately_less_than_zero(head2->fStartT)) {
+ const SkDPoint& start2 = sect2->fCurve[0];
+ if (head2->isBounded()) {
+ double t = head2->closestBoundedT(start2);
+ if (sect1->fCurve.ptAtT(t).approximatelyEqual(start2)) {
+ intersections->insert(t, 0, start2);
+ }
+ }
+ }
+ const SkTSpan* tail1 = sect1->tail();
+ if (!(zeroOneSet & kOneS1Set) && approximately_greater_than_one(tail1->fEndT)) {
+ const SkDPoint& end1 = sect1->pointLast();
+ if (tail1->isBounded()) {
+ double t = tail1->closestBoundedT(end1);
+ if (sect2->fCurve.ptAtT(t).approximatelyEqual(end1)) {
+ intersections->insert(1, t, end1);
+ }
+ }
+ }
+ const SkTSpan* tail2 = sect2->tail();
+ if (!(zeroOneSet & kOneS2Set) && approximately_greater_than_one(tail2->fEndT)) {
+ const SkDPoint& end2 = sect2->pointLast();
+ if (tail2->isBounded()) {
+ double t = tail2->closestBoundedT(end2);
+ if (sect1->fCurve.ptAtT(t).approximatelyEqual(end2)) {
+ intersections->insert(t, 1, end2);
+ }
+ }
+ }
+ SkClosestSect closest;
+ do {
+ while (result1 && result1->fCoinStart.isMatch() && result1->fCoinEnd.isMatch()) {
+ result1 = result1->fNext;
+ }
+ if (!result1) {
+ break;
+ }
+ SkTSpan* result2 = sect2->fHead;
+ bool found = false;
+ while (result2) {
+ found |= closest.find(result1, result2 SkDEBUGPARAMS(intersections));
+ result2 = result2->fNext;
+ }
+ } while ((result1 = result1->fNext));
+ closest.finish(intersections);
+ // if there is more than one intersection and it isn't already coincident, check
+ int last = intersections->used() - 1;
+ for (int index = 0; index < last; ) {
+ if (intersections->isCoincident(index) && intersections->isCoincident(index + 1)) {
+ ++index;
+ continue;
+ }
+ double midT = ((*intersections)[0][index] + (*intersections)[0][index + 1]) / 2;
+ SkDPoint midPt = sect1->fCurve.ptAtT(midT);
+ // intersect perpendicular with opposite curve
+ SkTCoincident perp;
+ perp.setPerp(sect1->fCurve, midT, midPt, sect2->fCurve);
+ if (!perp.isMatch()) {
+ ++index;
+ continue;
+ }
+ if (intersections->isCoincident(index)) {
+ intersections->removeOne(index);
+ --last;
+ } else if (intersections->isCoincident(index + 1)) {
+ intersections->removeOne(index + 1);
+ --last;
+ } else {
+ intersections->setCoincident(index++);
+ }
+ intersections->setCoincident(index);
+ }
+ SkOPOBJASSERT(intersections, intersections->used() <= sect1->fCurve.maxIntersections());
+}
int SkIntersections::intersect(const SkDQuad& q1, const SkDQuad& q2) {
SkTQuad quad1(q1);
SkTQuad quad2(q2);
- SkTSect<SkTCurve, SkTCurve> sect1(quad1
- SkDEBUGPARAMS(globalState()) PATH_OPS_DEBUG_T_SECT_PARAMS(1));
- SkTSect<SkTCurve, SkTCurve> sect2(quad2
- SkDEBUGPARAMS(globalState()) PATH_OPS_DEBUG_T_SECT_PARAMS(2));
- SkTSect<SkTCurve, SkTCurve>::BinarySearch(§1, §2, this);
+ SkTSect sect1(quad1 SkDEBUGPARAMS(globalState()) PATH_OPS_DEBUG_T_SECT_PARAMS(1));
+ SkTSect sect2(quad2 SkDEBUGPARAMS(globalState()) PATH_OPS_DEBUG_T_SECT_PARAMS(2));
+ SkTSect::BinarySearch(§1, §2, this);
return used();
}
int SkIntersections::intersect(const SkDConic& c, const SkDQuad& q) {
SkTConic conic(c);
SkTQuad quad(q);
- SkTSect<SkTCurve, SkTCurve> sect1(conic
- SkDEBUGPARAMS(globalState()) PATH_OPS_DEBUG_T_SECT_PARAMS(1));
- SkTSect<SkTCurve, SkTCurve> sect2(quad
- SkDEBUGPARAMS(globalState()) PATH_OPS_DEBUG_T_SECT_PARAMS(2));
- SkTSect<SkTCurve, SkTCurve>::BinarySearch(§1, §2, this);
+ SkTSect sect1(conic SkDEBUGPARAMS(globalState()) PATH_OPS_DEBUG_T_SECT_PARAMS(1));
+ SkTSect sect2(quad SkDEBUGPARAMS(globalState()) PATH_OPS_DEBUG_T_SECT_PARAMS(2));
+ SkTSect::BinarySearch(§1, §2, this);
return used();
}
int SkIntersections::intersect(const SkDConic& c1, const SkDConic& c2) {
SkTConic conic1(c1);
SkTConic conic2(c2);
- SkTSect<SkTCurve, SkTCurve> sect1(conic1
- SkDEBUGPARAMS(globalState()) PATH_OPS_DEBUG_T_SECT_PARAMS(1));
- SkTSect<SkTCurve, SkTCurve> sect2(conic2
- SkDEBUGPARAMS(globalState()) PATH_OPS_DEBUG_T_SECT_PARAMS(2));
- SkTSect<SkTCurve, SkTCurve>::BinarySearch(§1, §2, this);
+ SkTSect sect1(conic1 SkDEBUGPARAMS(globalState()) PATH_OPS_DEBUG_T_SECT_PARAMS(1));
+ SkTSect sect2(conic2 SkDEBUGPARAMS(globalState()) PATH_OPS_DEBUG_T_SECT_PARAMS(2));
+ SkTSect::BinarySearch(§1, §2, this);
return used();
}
int SkIntersections::intersect(const SkDCubic& c, const SkDQuad& q) {
SkTCubic cubic(c);
SkTQuad quad(q);
- SkTSect<SkTCurve, SkTCurve> sect1(cubic
- SkDEBUGPARAMS(globalState()) PATH_OPS_DEBUG_T_SECT_PARAMS(1));
- SkTSect<SkTCurve, SkTCurve> sect2(quad
- SkDEBUGPARAMS(globalState()) PATH_OPS_DEBUG_T_SECT_PARAMS(2));
- SkTSect<SkTCurve, SkTCurve>::BinarySearch(§1, §2, this);
+ SkTSect sect1(cubic SkDEBUGPARAMS(globalState()) PATH_OPS_DEBUG_T_SECT_PARAMS(1));
+ SkTSect sect2(quad SkDEBUGPARAMS(globalState()) PATH_OPS_DEBUG_T_SECT_PARAMS(2));
+ SkTSect::BinarySearch(§1, §2, this);
return used();
}
int SkIntersections::intersect(const SkDCubic& cu, const SkDConic& co) {
SkTCubic cubic(cu);
SkTConic conic(co);
- SkTSect<SkTCurve, SkTCurve> sect1(cubic
- SkDEBUGPARAMS(globalState()) PATH_OPS_DEBUG_T_SECT_PARAMS(1));
- SkTSect<SkTCurve, SkTCurve> sect2(conic
- SkDEBUGPARAMS(globalState()) PATH_OPS_DEBUG_T_SECT_PARAMS(2));
- SkTSect<SkTCurve, SkTCurve>::BinarySearch(§1, §2, this);
+ SkTSect sect1(cubic SkDEBUGPARAMS(globalState()) PATH_OPS_DEBUG_T_SECT_PARAMS(1));
+ SkTSect sect2(conic SkDEBUGPARAMS(globalState()) PATH_OPS_DEBUG_T_SECT_PARAMS(2));
+ SkTSect::BinarySearch(§1, §2, this);
return used();
}
@@ -68,69 +2109,8 @@
int SkIntersections::intersect(const SkDCubic& c1, const SkDCubic& c2) {
SkTCubic cubic1(c1);
SkTCubic cubic2(c2);
- SkTSect<SkTCurve, SkTCurve> sect1(cubic1
- SkDEBUGPARAMS(globalState()) PATH_OPS_DEBUG_T_SECT_PARAMS(1));
- SkTSect<SkTCurve, SkTCurve> sect2(cubic2
- SkDEBUGPARAMS(globalState()) PATH_OPS_DEBUG_T_SECT_PARAMS(2));
- SkTSect<SkTCurve, SkTCurve>::BinarySearch(§1, §2, this);
+ SkTSect sect1(cubic1 SkDEBUGPARAMS(globalState()) PATH_OPS_DEBUG_T_SECT_PARAMS(1));
+ SkTSect sect2(cubic2 SkDEBUGPARAMS(globalState()) PATH_OPS_DEBUG_T_SECT_PARAMS(2));
+ SkTSect::BinarySearch(§1, §2, this);
return used();
}
-
-#else
-
-int SkIntersections::intersect(const SkDQuad& quad1, const SkDQuad& quad2) {
- SkTSect<SkDQuad, SkDQuad> sect1(quad1
- SkDEBUGPARAMS(globalState()) PATH_OPS_DEBUG_T_SECT_PARAMS(1));
- SkTSect<SkDQuad, SkDQuad> sect2(quad2
- SkDEBUGPARAMS(globalState()) PATH_OPS_DEBUG_T_SECT_PARAMS(2));
- SkTSect<SkDQuad, SkDQuad>::BinarySearch(§1, §2, this);
- return used();
-}
-
-int SkIntersections::intersect(const SkDConic& conic, const SkDQuad& quad) {
- SkTSect<SkDConic, SkDQuad> sect1(conic
- SkDEBUGPARAMS(globalState()) PATH_OPS_DEBUG_T_SECT_PARAMS(1));
- SkTSect<SkDQuad, SkDConic> sect2(quad
- SkDEBUGPARAMS(globalState()) PATH_OPS_DEBUG_T_SECT_PARAMS(2));
- SkTSect<SkDConic, SkDQuad>::BinarySearch(§1, §2, this);
- return used();
-}
-
-int SkIntersections::intersect(const SkDConic& conic1, const SkDConic& conic2) {
- SkTSect<SkDConic, SkDConic> sect1(conic1
- SkDEBUGPARAMS(globalState()) PATH_OPS_DEBUG_T_SECT_PARAMS(1));
- SkTSect<SkDConic, SkDConic> sect2(conic2
- SkDEBUGPARAMS(globalState()) PATH_OPS_DEBUG_T_SECT_PARAMS(2));
- SkTSect<SkDConic, SkDConic>::BinarySearch(§1, §2, this);
- return used();
-}
-
-int SkIntersections::intersect(const SkDCubic& cubic, const SkDQuad& quad) {
- SkTSect<SkDCubic, SkDQuad> sect1(cubic
- SkDEBUGPARAMS(globalState()) PATH_OPS_DEBUG_T_SECT_PARAMS(1));
- SkTSect<SkDQuad, SkDCubic> sect2(quad
- SkDEBUGPARAMS(globalState()) PATH_OPS_DEBUG_T_SECT_PARAMS(2));
- SkTSect<SkDCubic, SkDQuad>::BinarySearch(§1, §2, this);
- return used();
-}
-
-int SkIntersections::intersect(const SkDCubic& cubic, const SkDConic& conic) {
- SkTSect<SkDCubic, SkDConic> sect1(cubic
- SkDEBUGPARAMS(globalState()) PATH_OPS_DEBUG_T_SECT_PARAMS(1));
- SkTSect<SkDConic, SkDCubic> sect2(conic
- SkDEBUGPARAMS(globalState()) PATH_OPS_DEBUG_T_SECT_PARAMS(2));
- SkTSect<SkDCubic, SkDConic>::BinarySearch(§1, §2, this);
- return used();
-}
-
-int SkIntersections::intersect(const SkDCubic& cubic1, const SkDCubic& cubic2) {
- SkTSect<SkDCubic, SkDCubic> sect1(cubic1
- SkDEBUGPARAMS(globalState()) PATH_OPS_DEBUG_T_SECT_PARAMS(1));
- SkTSect<SkDCubic, SkDCubic> sect2(cubic2
- SkDEBUGPARAMS(globalState()) PATH_OPS_DEBUG_T_SECT_PARAMS(2));
- SkTSect<SkDCubic, SkDCubic>::BinarySearch(§1, §2, this);
- return used();
-}
-
-#endif
-
diff --git a/src/pathops/SkPathOpsTSect.h b/src/pathops/SkPathOpsTSect.h
index 1bf4f7f..8cf7ad3 100644
--- a/src/pathops/SkPathOpsTSect.h
+++ b/src/pathops/SkPathOpsTSect.h
@@ -12,6 +12,7 @@
#include "SkMacros.h"
#include "SkPathOpsBounds.h"
#include "SkPathOpsRect.h"
+#include "SkPathOpsTCurve.h"
#include "SkTSort.h"
#include <utility>
@@ -26,8 +27,6 @@
return x != x;
}
-/* TCurve and OppCurve are one of { SkDQuadratic, SkDConic, SkDCubic } */
-template<typename TCurve, typename OppCurve>
class SkTCoincident {
public:
SkTCoincident() {
@@ -71,7 +70,7 @@
return fPerpT;
}
- void setPerp(const TCurve& c1, double t, const SkDPoint& cPt, const OppCurve& );
+ void setPerp(const SkTCurve& c1, double t, const SkDPoint& cPt, const SkTCurve& );
private:
SkDPoint fPerpPt;
@@ -79,51 +78,44 @@
SkOpDebugBool fMatch;
};
-template<typename TCurve, typename OppCurve> class SkTSect;
-template<typename TCurve, typename OppCurve> class SkTSpan;
+class SkTSect;
+class SkTSpan;
-template<typename TCurve, typename OppCurve>
struct SkTSpanBounded {
- SkTSpan<TCurve, OppCurve>* fBounded;
+ SkTSpan* fBounded;
SkTSpanBounded* fNext;
};
-/* Curve is either TCurve or SkDCubic */
-template<typename TCurve, typename OppCurve>
class SkTSpan {
public:
- SkTSpan(const TCurve& curve, SkArenaAlloc& heap) {
-#if PATH_OP_COMPILE_FOR_SIZE
+ SkTSpan(const SkTCurve& curve, SkArenaAlloc& heap) {
fPart = curve.make(heap);
-#endif
}
- void addBounded(SkTSpan<OppCurve, TCurve>* , SkArenaAlloc* );
+ void addBounded(SkTSpan* , SkArenaAlloc* );
double closestBoundedT(const SkDPoint& pt) const;
bool contains(double t) const;
- void debugInit() {
-#if !PATH_OP_COMPILE_FOR_SIZE
- TCurve dummy;
- dummy.debugInit();
- init(dummy);
- initBounds(dummy);
+ void debugInit(const SkTCurve& curve, SkArenaAlloc& heap) {
+#ifdef SK_DEBUG
+ SkTCurve* dummy = curve.make(heap);
+ dummy->debugInit();
+ init(*dummy);
+ initBounds(*dummy);
fCoinStart.init();
fCoinEnd.init();
#endif
}
- const SkTSect<OppCurve, TCurve>* debugOpp() const;
+ const SkTSect* debugOpp() const;
#ifdef SK_DEBUG
void debugSetGlobalState(SkOpGlobalState* state) {
fDebugGlobalState = state;
}
-#endif
const SkTSpan* debugSpan(int ) const;
const SkTSpan* debugT(double t) const;
-#ifdef SK_DEBUG
bool debugIsBefore(const SkTSpan* span) const;
#endif
void dump() const;
@@ -136,10 +128,10 @@
return fEndT;
}
- SkTSpan<OppCurve, TCurve>* findOppSpan(const SkTSpan<OppCurve, TCurve>* opp) const;
+ SkTSpan* findOppSpan(const SkTSpan* opp) const;
- SkTSpan<OppCurve, TCurve>* findOppT(double t) const {
- SkTSpan<OppCurve, TCurve>* result = oppT(t);
+ SkTSpan* findOppT(double t) const {
+ SkTSpan* result = oppT(t);
SkOPASSERT(result);
return result;
}
@@ -150,15 +142,15 @@
return SkToBool(oppT(t));
}
- int hullsIntersect(SkTSpan<OppCurve, TCurve>* span, bool* start, bool* oppStart);
- void init(const TCurve& );
- bool initBounds(const TCurve& );
+ int hullsIntersect(SkTSpan* span, bool* start, bool* oppStart);
+ void init(const SkTCurve& );
+ bool initBounds(const SkTCurve& );
bool isBounded() const {
return fBounded != nullptr;
}
- bool linearsIntersect(SkTSpan<OppCurve, TCurve>* span);
+ bool linearsIntersect(SkTSpan* span);
double linearT(const SkDPoint& ) const;
void markCoincident() {
@@ -170,33 +162,33 @@
return fNext;
}
- bool onlyEndPointsInCommon(const SkTSpan<OppCurve, TCurve>* opp, bool* start,
+ bool onlyEndPointsInCommon(const SkTSpan* opp, bool* start,
bool* oppStart, bool* ptsInCommon);
- TCurve& part() {
-#if PATH_OP_COMPILE_FOR_SIZE
+ const SkTCurve& part() const {
return *fPart;
-#else
- return fPart;
-#endif
}
- const TCurve& part() const {
-#if PATH_OP_COMPILE_FOR_SIZE
- return *fPart;
-#else
- return fPart;
-#endif
+ int pointCount() const {
+ return fPart->pointCount();
+ }
+
+ const SkDPoint& pointFirst() const {
+ return (*fPart)[0];
+ }
+
+ const SkDPoint& pointLast() const {
+ return (*fPart)[fPart->pointLast()];
}
bool removeAllBounded();
- bool removeBounded(const SkTSpan<OppCurve, TCurve>* opp);
+ bool removeBounded(const SkTSpan* opp);
void reset() {
fBounded = nullptr;
}
- void resetBounds(const TCurve& curve) {
+ void resetBounds(const SkTCurve& curve) {
fIsLinear = fIsLine = false;
initBounds(curve);
}
@@ -220,23 +212,19 @@
void dumpID() const;
- int hullCheck(const SkTSpan<OppCurve, TCurve>* opp, bool* start, bool* oppStart);
- int linearIntersects(const OppCurve& ) const;
- SkTSpan<OppCurve, TCurve>* oppT(double t) const;
+ int hullCheck(const SkTSpan* opp, bool* start, bool* oppStart);
+ int linearIntersects(const SkTCurve& ) const;
+ SkTSpan* oppT(double t) const;
void validate() const;
void validateBounded() const;
void validatePerpT(double oppT) const;
void validatePerpPt(double t, const SkDPoint& ) const;
-#if PATH_OP_COMPILE_FOR_SIZE
- TCurve* fPart;
-#else
- TCurve fPart;
-#endif
- SkTCoincident<TCurve, OppCurve> fCoinStart;
- SkTCoincident<TCurve, OppCurve> fCoinEnd;
- SkTSpanBounded<OppCurve, TCurve>* fBounded;
+ SkTCurve* fPart;
+ SkTCoincident fCoinStart;
+ SkTCoincident fCoinEnd;
+ SkTSpanBounded* fBounded;
SkTSpan* fPrev;
SkTSpan* fNext;
SkDRect fBounds;
@@ -249,31 +237,31 @@
SkOpDebugBool fIsLine;
SkOpDebugBool fDeleted;
SkDEBUGCODE(SkOpGlobalState* fDebugGlobalState);
- SkDEBUGCODE(SkTSect<TCurve, OppCurve>* fDebugSect);
+ SkDEBUGCODE(SkTSect* fDebugSect);
PATH_OPS_DEBUG_T_SECT_CODE(int fID);
- friend class SkTSect<TCurve, OppCurve>;
- friend class SkTSect<OppCurve, TCurve>;
- friend class SkTSpan<OppCurve, TCurve>;
+ friend class SkTSect;
};
-template<typename TCurve, typename OppCurve>
class SkTSect {
public:
- SkTSect(const TCurve& c SkDEBUGPARAMS(SkOpGlobalState* ) PATH_OPS_DEBUG_T_SECT_PARAMS(int id));
- static void BinarySearch(SkTSect* sect1, SkTSect<OppCurve, TCurve>* sect2,
+ SkTSect(const SkTCurve& c
+ SkDEBUGPARAMS(SkOpGlobalState* ) PATH_OPS_DEBUG_T_SECT_PARAMS(int id));
+ static void BinarySearch(SkTSect* sect1, SkTSect* sect2,
SkIntersections* intersections);
SkDEBUGCODE(SkOpGlobalState* globalState() { return fDebugGlobalState; })
- bool hasBounded(const SkTSpan<OppCurve, TCurve>* ) const;
+ bool hasBounded(const SkTSpan* ) const;
- const SkTSect<OppCurve, TCurve>* debugOpp() const {
+ const SkTSect* debugOpp() const {
return SkDEBUGRELEASE(fOppSect, nullptr);
}
- const SkTSpan<TCurve, OppCurve>* debugSpan(int id) const;
- const SkTSpan<TCurve, OppCurve>* debugT(double t) const;
+#ifdef SK_DEBUG
+ const SkTSpan* debugSpan(int id) const;
+ const SkTSpan* debugT(double t) const;
+#endif
void dump() const;
- void dumpBoth(SkTSect<OppCurve, TCurve>* ) const;
+ void dumpBoth(SkTSect* ) const;
void dumpBounded(int id) const;
void dumpBounds() const;
void dumpCoin() const;
@@ -288,12 +276,12 @@
kOneS2Set = 8
};
- SkTSpan<TCurve, OppCurve>* addFollowing(SkTSpan<TCurve, OppCurve>* prior);
- void addForPerp(SkTSpan<OppCurve, TCurve>* span, double t);
- SkTSpan<TCurve, OppCurve>* addOne();
+ SkTSpan* addFollowing(SkTSpan* prior);
+ void addForPerp(SkTSpan* span, double t);
+ SkTSpan* addOne();
- SkTSpan<TCurve, OppCurve>* addSplitAt(SkTSpan<TCurve, OppCurve>* span, double t) {
- SkTSpan<TCurve, OppCurve>* result = this->addOne();
+ SkTSpan* addSplitAt(SkTSpan* span, double t) {
+ SkTSpan* result = this->addOne();
SkDEBUGCODE(result->debugSetGlobalState(this->globalState()));
result->splitAt(span, t, &fHeap);
result->initBounds(fCurve);
@@ -301,2202 +289,86 @@
return result;
}
- bool binarySearchCoin(SkTSect<OppCurve, TCurve>* , double tStart, double tStep, double* t,
- double* oppT, SkTSpan<OppCurve, TCurve>** oppFirst);
- SkTSpan<TCurve, OppCurve>* boundsMax();
- bool coincidentCheck(SkTSect<OppCurve, TCurve>* sect2);
- void coincidentForce(SkTSect<OppCurve, TCurve>* sect2, double start1s, double start1e);
+ bool binarySearchCoin(SkTSect* , double tStart, double tStep, double* t,
+ double* oppT, SkTSpan** oppFirst);
+ SkTSpan* boundsMax();
+ bool coincidentCheck(SkTSect* sect2);
+ void coincidentForce(SkTSect* sect2, double start1s, double start1e);
bool coincidentHasT(double t);
int collapsed() const;
- void computePerpendiculars(SkTSect<OppCurve, TCurve>* sect2, SkTSpan<TCurve, OppCurve>* first,
- SkTSpan<TCurve, OppCurve>* last);
- int countConsecutiveSpans(SkTSpan<TCurve, OppCurve>* first,
- SkTSpan<TCurve, OppCurve>** last) const;
+ void computePerpendiculars(SkTSect* sect2, SkTSpan* first,
+ SkTSpan* last);
+ int countConsecutiveSpans(SkTSpan* first,
+ SkTSpan** last) const;
int debugID() const {
return PATH_OPS_DEBUG_T_SECT_RELEASE(fID, -1);
}
bool deleteEmptySpans();
- void dumpCommon(const SkTSpan<TCurve, OppCurve>* ) const;
- void dumpCommonCurves(const SkTSpan<TCurve, OppCurve>* ) const;
- static int EndsEqual(const SkTSect* sect1, const SkTSect<OppCurve, TCurve>* sect2,
+ void dumpCommon(const SkTSpan* ) const;
+ void dumpCommonCurves(const SkTSpan* ) const;
+ static int EndsEqual(const SkTSect* sect1, const SkTSect* sect2,
SkIntersections* );
- bool extractCoincident(SkTSect<OppCurve, TCurve>* sect2, SkTSpan<TCurve, OppCurve>* first,
- SkTSpan<TCurve, OppCurve>* last, SkTSpan<TCurve, OppCurve>** result);
- SkTSpan<TCurve, OppCurve>* findCoincidentRun(SkTSpan<TCurve, OppCurve>* first,
- SkTSpan<TCurve, OppCurve>** lastPtr);
- int intersects(SkTSpan<TCurve, OppCurve>* span, SkTSect<OppCurve, TCurve>* opp,
- SkTSpan<OppCurve, TCurve>* oppSpan, int* oppResult);
- bool isParallel(const SkDLine& thisLine, const SkTSect<OppCurve, TCurve>* opp) const;
- int linesIntersect(SkTSpan<TCurve, OppCurve>* span, SkTSect<OppCurve, TCurve>* opp,
- SkTSpan<OppCurve, TCurve>* oppSpan, SkIntersections* );
- bool markSpanGone(SkTSpan<TCurve, OppCurve>* span);
- bool matchedDirection(double t, const SkTSect<OppCurve, TCurve>* sect2, double t2) const;
- void matchedDirCheck(double t, const SkTSect<OppCurve, TCurve>* sect2, double t2,
+ bool extractCoincident(SkTSect* sect2, SkTSpan* first,
+ SkTSpan* last, SkTSpan** result);
+ SkTSpan* findCoincidentRun(SkTSpan* first, SkTSpan** lastPtr);
+ int intersects(SkTSpan* span, SkTSect* opp,
+ SkTSpan* oppSpan, int* oppResult);
+ bool isParallel(const SkDLine& thisLine, const SkTSect* opp) const;
+ int linesIntersect(SkTSpan* span, SkTSect* opp,
+ SkTSpan* oppSpan, SkIntersections* );
+ bool markSpanGone(SkTSpan* span);
+ bool matchedDirection(double t, const SkTSect* sect2, double t2) const;
+ void matchedDirCheck(double t, const SkTSect* sect2, double t2,
bool* calcMatched, bool* oppMatched) const;
- void mergeCoincidence(SkTSect<OppCurve, TCurve>* sect2);
- SkTSpan<TCurve, OppCurve>* prev(SkTSpan<TCurve, OppCurve>* ) const;
- bool removeByPerpendicular(SkTSect<OppCurve, TCurve>* opp);
+ void mergeCoincidence(SkTSect* sect2);
+
+ const SkDPoint& pointLast() const {
+ return fCurve[fCurve.pointLast()];
+ }
+
+ SkTSpan* prev(SkTSpan* ) const;
+ bool removeByPerpendicular(SkTSect* opp);
void recoverCollapsed();
- bool removeCoincident(SkTSpan<TCurve, OppCurve>* span, bool isBetween);
- void removeAllBut(const SkTSpan<OppCurve, TCurve>* keep, SkTSpan<TCurve, OppCurve>* span,
- SkTSect<OppCurve, TCurve>* opp);
- bool removeSpan(SkTSpan<TCurve, OppCurve>* span);
- void removeSpanRange(SkTSpan<TCurve, OppCurve>* first, SkTSpan<TCurve, OppCurve>* last);
- bool removeSpans(SkTSpan<TCurve, OppCurve>* span, SkTSect<OppCurve, TCurve>* opp);
- void removedEndCheck(SkTSpan<TCurve, OppCurve>* span);
+ bool removeCoincident(SkTSpan* span, bool isBetween);
+ void removeAllBut(const SkTSpan* keep, SkTSpan* span,
+ SkTSect* opp);
+ bool removeSpan(SkTSpan* span);
+ void removeSpanRange(SkTSpan* first, SkTSpan* last);
+ bool removeSpans(SkTSpan* span, SkTSect* opp);
+ void removedEndCheck(SkTSpan* span);
void resetRemovedEnds() {
fRemovedStartT = fRemovedEndT = false;
}
- SkTSpan<TCurve, OppCurve>* spanAtT(double t, SkTSpan<TCurve, OppCurve>** priorSpan);
- SkTSpan<TCurve, OppCurve>* tail();
- bool trim(SkTSpan<TCurve, OppCurve>* span, SkTSect<OppCurve, TCurve>* opp);
- bool unlinkSpan(SkTSpan<TCurve, OppCurve>* span);
- bool updateBounded(SkTSpan<TCurve, OppCurve>* first, SkTSpan<TCurve, OppCurve>* last,
- SkTSpan<OppCurve, TCurve>* oppFirst);
+ SkTSpan* spanAtT(double t, SkTSpan** priorSpan);
+ SkTSpan* tail();
+ bool trim(SkTSpan* span, SkTSect* opp);
+ bool unlinkSpan(SkTSpan* span);
+ bool updateBounded(SkTSpan* first, SkTSpan* last,
+ SkTSpan* oppFirst);
void validate() const;
void validateBounded() const;
- const TCurve& fCurve;
+ const SkTCurve& fCurve;
SkArenaAlloc fHeap;
- SkTSpan<TCurve, OppCurve>* fHead;
- SkTSpan<TCurve, OppCurve>* fCoincident;
- SkTSpan<TCurve, OppCurve>* fDeleted;
+ SkTSpan* fHead;
+ SkTSpan* fCoincident;
+ SkTSpan* fDeleted;
int fActiveCount;
bool fRemovedStartT;
bool fRemovedEndT;
bool fHung;
SkDEBUGCODE(SkOpGlobalState* fDebugGlobalState);
- SkDEBUGCODE(SkTSect<OppCurve, TCurve>* fOppSect);
+ SkDEBUGCODE(SkTSect* fOppSect);
PATH_OPS_DEBUG_T_SECT_CODE(int fID);
PATH_OPS_DEBUG_T_SECT_CODE(int fDebugCount);
#if DEBUG_T_SECT
int fDebugAllocatedCount;
#endif
- friend class SkTSpan<TCurve, OppCurve>;
- friend class SkTSpan<OppCurve, TCurve>;
- friend class SkTSect<OppCurve, TCurve>;
+ friend class SkTSpan;
};
-#define COINCIDENT_SPAN_COUNT 9
-
-template<typename TCurve, typename OppCurve>
-void SkTCoincident<TCurve, OppCurve>::setPerp(const TCurve& c1, double t,
- const SkDPoint& cPt, const OppCurve& c2) {
- SkDVector dxdy = c1.dxdyAtT(t);
- SkDLine perp = {{ cPt, {cPt.fX + dxdy.fY, cPt.fY - dxdy.fX} }};
- SkIntersections i SkDEBUGCODE((c1.globalState()));
- int used = i.intersectRay(c2, perp);
- // only keep closest
- if (used == 0 || used == 3) {
- this->init();
- return;
- }
- fPerpT = i[0][0];
- fPerpPt = i.pt(0);
- SkASSERT(used <= 2);
- if (used == 2) {
- double distSq = (fPerpPt - cPt).lengthSquared();
- double dist2Sq = (i.pt(1) - cPt).lengthSquared();
- if (dist2Sq < distSq) {
- fPerpT = i[0][1];
- fPerpPt = i.pt(1);
- }
- }
-#if DEBUG_T_SECT
- SkDebugf("setPerp t=%1.9g cPt=(%1.9g,%1.9g) %s oppT=%1.9g fPerpPt=(%1.9g,%1.9g)\n",
- t, cPt.fX, cPt.fY,
- cPt.approximatelyEqual(fPerpPt) ? "==" : "!=", fPerpT, fPerpPt.fX, fPerpPt.fY);
-#endif
- fMatch = cPt.approximatelyEqual(fPerpPt);
-#if DEBUG_T_SECT
- if (fMatch) {
- SkDebugf(""); // allow setting breakpoint
- }
-#endif
-}
-
-template<typename TCurve, typename OppCurve>
-void SkTSpan<TCurve, OppCurve>::addBounded(SkTSpan<OppCurve, TCurve>* span, SkArenaAlloc* heap) {
- SkTSpanBounded<OppCurve, TCurve>* bounded = heap->make<SkTSpanBounded<OppCurve, TCurve>>();
- bounded->fBounded = span;
- bounded->fNext = fBounded;
- fBounded = bounded;
-}
-
-template<typename TCurve, typename OppCurve>
-SkTSpan<TCurve, OppCurve>* SkTSect<TCurve, OppCurve>::addFollowing(
- SkTSpan<TCurve, OppCurve>* prior) {
- SkTSpan<TCurve, OppCurve>* result = this->addOne();
- SkDEBUGCODE(result->debugSetGlobalState(this->globalState()));
- result->fStartT = prior ? prior->fEndT : 0;
- SkTSpan<TCurve, OppCurve>* next = prior ? prior->fNext : fHead;
- result->fEndT = next ? next->fStartT : 1;
- result->fPrev = prior;
- result->fNext = next;
- if (prior) {
- prior->fNext = result;
- } else {
- fHead = result;
- }
- if (next) {
- next->fPrev = result;
- }
- result->resetBounds(fCurve);
- // world may not be consistent to call validate here
- result->validate();
- return result;
-}
-
-template<typename TCurve, typename OppCurve>
-void SkTSect<TCurve, OppCurve>::addForPerp(SkTSpan<OppCurve, TCurve>* span, double t) {
- if (!span->hasOppT(t)) {
- SkTSpan<TCurve, OppCurve>* priorSpan;
- SkTSpan<TCurve, OppCurve>* opp = this->spanAtT(t, &priorSpan);
- if (!opp) {
- opp = this->addFollowing(priorSpan);
-#if DEBUG_PERP
- SkDebugf("%s priorSpan=%d t=%1.9g opp=%d\n", __FUNCTION__, priorSpan ?
- priorSpan->debugID() : -1, t, opp->debugID());
-#endif
- }
-#if DEBUG_PERP
- opp->dump(); SkDebugf("\n");
- SkDebugf("%s addBounded span=%d opp=%d\n", __FUNCTION__, priorSpan ?
- priorSpan->debugID() : -1, opp->debugID());
-#endif
- opp->addBounded(span, &fHeap);
- span->addBounded(opp, &fHeap);
- }
- this->validate();
-#if DEBUG_T_SECT
- span->validatePerpT(t);
-#endif
-}
-
-template<typename TCurve, typename OppCurve>
-double SkTSpan<TCurve, OppCurve>::closestBoundedT(const SkDPoint& pt) const {
- double result = -1;
- double closest = DBL_MAX;
- const SkTSpanBounded<OppCurve, TCurve>* testBounded = fBounded;
- while (testBounded) {
- const SkTSpan<OppCurve, TCurve>* test = testBounded->fBounded;
- double startDist = test->part()[0].distanceSquared(pt);
- if (closest > startDist) {
- closest = startDist;
- result = test->fStartT;
- }
- double endDist = test->part()[test->part().pointLast()].distanceSquared(pt);
- if (closest > endDist) {
- closest = endDist;
- result = test->fEndT;
- }
- testBounded = testBounded->fNext;
- }
- SkASSERT(between(0, result, 1));
- return result;
-}
-
-#ifdef SK_DEBUG
-template<typename TCurve, typename OppCurve>
-bool SkTSpan<TCurve, OppCurve>::debugIsBefore(const SkTSpan* span) const {
- const SkTSpan* work = this;
- do {
- if (span == work) {
- return true;
- }
- } while ((work = work->fNext));
- return false;
-}
-#endif
-
-template<typename TCurve, typename OppCurve>
-bool SkTSpan<TCurve, OppCurve>::contains(double t) const {
- const SkTSpan* work = this;
- do {
- if (between(work->fStartT, t, work->fEndT)) {
- return true;
- }
- } while ((work = work->fNext));
- return false;
-}
-
-template<typename TCurve, typename OppCurve>
-const SkTSect<OppCurve, TCurve>* SkTSpan<TCurve, OppCurve>::debugOpp() const {
- return SkDEBUGRELEASE(fDebugSect->debugOpp(), nullptr);
-}
-
-template<typename TCurve, typename OppCurve>
-SkTSpan<OppCurve, TCurve>* SkTSpan<TCurve, OppCurve>::findOppSpan(
- const SkTSpan<OppCurve, TCurve>* opp) const {
- SkTSpanBounded<OppCurve, TCurve>* bounded = fBounded;
- while (bounded) {
- SkTSpan<OppCurve, TCurve>* test = bounded->fBounded;
- if (opp == test) {
- return test;
- }
- bounded = bounded->fNext;
- }
- return nullptr;
-}
-
-// returns 0 if no hull intersection
-// 1 if hulls intersect
-// 2 if hulls only share a common endpoint
-// -1 if linear and further checking is required
-template<typename TCurve, typename OppCurve>
-int SkTSpan<TCurve, OppCurve>::hullCheck(const SkTSpan<OppCurve, TCurve>* opp,
- bool* start, bool* oppStart) {
- if (fIsLinear) {
- return -1;
- }
- bool ptsInCommon;
- if (onlyEndPointsInCommon(opp, start, oppStart, &ptsInCommon)) {
- SkASSERT(ptsInCommon);
- return 2;
- }
- bool linear;
- if (part().hullIntersects(opp->part(), &linear)) {
- if (!linear) { // check set true if linear
- return 1;
- }
- fIsLinear = true;
- fIsLine = part().controlsInside();
- return ptsInCommon ? 1 : -1;
- } else { // hull is not linear; check set true if intersected at the end points
- return ((int) ptsInCommon) << 1; // 0 or 2
- }
- return 0;
-}
-
-// OPTIMIZE ? If at_most_end_pts_in_common detects that one quad is near linear,
-// use line intersection to guess a better split than 0.5
-// OPTIMIZE Once at_most_end_pts_in_common detects linear, mark span so all future splits are linear
-template<typename TCurve, typename OppCurve>
-int SkTSpan<TCurve, OppCurve>::hullsIntersect(SkTSpan<OppCurve, TCurve>* opp,
- bool* start, bool* oppStart) {
- if (!fBounds.intersects(opp->fBounds)) {
- return 0;
- }
- int hullSect = this->hullCheck(opp, start, oppStart);
- if (hullSect >= 0) {
- return hullSect;
- }
- hullSect = opp->hullCheck(this, oppStart, start);
- if (hullSect >= 0) {
- return hullSect;
- }
- return -1;
-}
-
-template<typename TCurve, typename OppCurve>
-void SkTSpan<TCurve, OppCurve>::init(const TCurve& c) {
- fPrev = fNext = nullptr;
- fStartT = 0;
- fEndT = 1;
- fBounded = nullptr;
- resetBounds(c);
-}
-
-template<typename TCurve, typename OppCurve>
-bool SkTSpan<TCurve, OppCurve>::initBounds(const TCurve& c) {
- if (SkDoubleIsNaN(fStartT) || SkDoubleIsNaN(fEndT)) {
- return false;
- }
- c.subDivide(fStartT, fEndT, &part());
- fBounds.setBounds(part());
- fCoinStart.init();
- fCoinEnd.init();
- fBoundsMax = SkTMax(fBounds.width(), fBounds.height());
- fCollapsed = part().collapsed();
- fHasPerp = false;
- fDeleted = false;
-#if DEBUG_T_SECT
- if (fCollapsed) {
- SkDebugf(""); // for convenient breakpoints
- }
-#endif
- return fBounds.valid();
-}
-
-template<typename TCurve, typename OppCurve>
-bool SkTSpan<TCurve, OppCurve>::linearsIntersect(SkTSpan<OppCurve, TCurve>* span) {
- int result = this->linearIntersects(span->part());
- if (result <= 1) {
- return SkToBool(result);
- }
- SkASSERT(span->fIsLinear);
- result = span->linearIntersects(this->part());
-// SkASSERT(result <= 1);
- return SkToBool(result);
-}
-
-template<typename TCurve, typename OppCurve>
-double SkTSpan<TCurve, OppCurve>::linearT(const SkDPoint& pt) const {
- SkDVector len = part()[part().pointLast()] - part()[0];
- return fabs(len.fX) > fabs(len.fY)
- ? (pt.fX - part()[0].fX) / len.fX
- : (pt.fY - part()[0].fY) / len.fY;
-}
-
-template<typename TCurve, typename OppCurve>
-int SkTSpan<TCurve, OppCurve>::linearIntersects(const OppCurve& q2) const {
- // looks like q1 is near-linear
- int start = 0, end = part().pointLast(); // the outside points are usually the extremes
- if (!part().controlsInside()) {
- double dist = 0; // if there's any question, compute distance to find best outsiders
- for (int outer = 0; outer < part().pointCount() - 1; ++outer) {
- for (int inner = outer + 1; inner < part().pointCount(); ++inner) {
- double test = (part()[outer] - part()[inner]).lengthSquared();
- if (dist > test) {
- continue;
- }
- dist = test;
- start = outer;
- end = inner;
- }
- }
- }
- // see if q2 is on one side of the line formed by the extreme points
- double origX = part()[start].fX;
- double origY = part()[start].fY;
- double adj = part()[end].fX - origX;
- double opp = part()[end].fY - origY;
- double maxPart = SkTMax(fabs(adj), fabs(opp));
- double sign = 0; // initialization to shut up warning in release build
- for (int n = 0; n < q2.pointCount(); ++n) {
- double dx = q2[n].fY - origY;
- double dy = q2[n].fX - origX;
- double maxVal = SkTMax(maxPart, SkTMax(fabs(dx), fabs(dy)));
- double test = (q2[n].fY - origY) * adj - (q2[n].fX - origX) * opp;
- if (precisely_zero_when_compared_to(test, maxVal)) {
- return 1;
- }
- if (approximately_zero_when_compared_to(test, maxVal)) {
- return 3;
- }
- if (n == 0) {
- sign = test;
- continue;
- }
- if (test * sign < 0) {
- return 1;
- }
- }
- return 0;
-}
-
-template<typename TCurve, typename OppCurve>
-bool SkTSpan<TCurve, OppCurve>::onlyEndPointsInCommon(const SkTSpan<OppCurve, TCurve>* opp,
- bool* start, bool* oppStart, bool* ptsInCommon) {
- if (opp->part()[0] == part()[0]) {
- *start = *oppStart = true;
- } else if (opp->part()[0] == part()[part().pointLast()]) {
- *start = false;
- *oppStart = true;
- } else if (opp->part()[opp->part().pointLast()] == part()[0]) {
- *start = true;
- *oppStart = false;
- } else if (opp->part()[opp->part().pointLast()] == part()[part().pointLast()]) {
- *start = *oppStart = false;
- } else {
- *ptsInCommon = false;
- return false;
- }
- *ptsInCommon = true;
- const SkDPoint* otherPts[4], * oppOtherPts[4];
-// const SkDPoint* otherPts[part().pointCount() - 1], * oppOtherPts[opp->part().pointCount() - 1];
- int baseIndex = *start ? 0 : part().pointLast();
- part().otherPts(baseIndex, otherPts);
- opp->part().otherPts(*oppStart ? 0 : opp->part().pointLast(), oppOtherPts);
- const SkDPoint& base = part()[baseIndex];
- for (int o1 = 0; o1 < part().pointCount() - 1; ++o1) {
- SkDVector v1 = *otherPts[o1] - base;
- for (int o2 = 0; o2 < opp->part().pointCount() - 1; ++o2) {
- SkDVector v2 = *oppOtherPts[o2] - base;
- if (v2.dot(v1) >= 0) {
- return false;
- }
- }
- }
- return true;
-}
-
-template<typename TCurve, typename OppCurve>
-SkTSpan<OppCurve, TCurve>* SkTSpan<TCurve, OppCurve>::oppT(double t) const {
- SkTSpanBounded<OppCurve, TCurve>* bounded = fBounded;
- while (bounded) {
- SkTSpan<OppCurve, TCurve>* test = bounded->fBounded;
- if (between(test->fStartT, t, test->fEndT)) {
- return test;
- }
- bounded = bounded->fNext;
- }
- return nullptr;
-}
-
-template<typename TCurve, typename OppCurve>
-bool SkTSpan<TCurve, OppCurve>::removeAllBounded() {
- bool deleteSpan = false;
- SkTSpanBounded<OppCurve, TCurve>* bounded = fBounded;
- while (bounded) {
- SkTSpan<OppCurve, TCurve>* opp = bounded->fBounded;
- deleteSpan |= opp->removeBounded(this);
- bounded = bounded->fNext;
- }
- return deleteSpan;
-}
-
-template<typename TCurve, typename OppCurve>
-bool SkTSpan<TCurve, OppCurve>::removeBounded(const SkTSpan<OppCurve, TCurve>* opp) {
- if (fHasPerp) {
- bool foundStart = false;
- bool foundEnd = false;
- SkTSpanBounded<OppCurve, TCurve>* bounded = fBounded;
- while (bounded) {
- SkTSpan<OppCurve, TCurve>* test = bounded->fBounded;
- if (opp != test) {
- foundStart |= between(test->fStartT, fCoinStart.perpT(), test->fEndT);
- foundEnd |= between(test->fStartT, fCoinEnd.perpT(), test->fEndT);
- }
- bounded = bounded->fNext;
- }
- if (!foundStart || !foundEnd) {
- fHasPerp = false;
- fCoinStart.init();
- fCoinEnd.init();
- }
- }
- SkTSpanBounded<OppCurve, TCurve>* bounded = fBounded;
- SkTSpanBounded<OppCurve, TCurve>* prev = nullptr;
- while (bounded) {
- SkTSpanBounded<OppCurve, TCurve>* boundedNext = bounded->fNext;
- if (opp == bounded->fBounded) {
- if (prev) {
- prev->fNext = boundedNext;
- return false;
- } else {
- fBounded = boundedNext;
- return fBounded == nullptr;
- }
- }
- prev = bounded;
- bounded = boundedNext;
- }
- SkOPASSERT(0);
- return false;
-}
-
-template<typename TCurve, typename OppCurve>
-bool SkTSpan<TCurve, OppCurve>::splitAt(SkTSpan* work, double t, SkArenaAlloc* heap) {
- fStartT = t;
- fEndT = work->fEndT;
- if (fStartT == fEndT) {
- fCollapsed = true;
- return false;
- }
- work->fEndT = t;
- if (work->fStartT == work->fEndT) {
- work->fCollapsed = true;
- return false;
- }
- fPrev = work;
- fNext = work->fNext;
- fIsLinear = work->fIsLinear;
- fIsLine = work->fIsLine;
-
- work->fNext = this;
- if (fNext) {
- fNext->fPrev = this;
- }
- this->validate();
- SkTSpanBounded<OppCurve, TCurve>* bounded = work->fBounded;
- fBounded = nullptr;
- while (bounded) {
- this->addBounded(bounded->fBounded, heap);
- bounded = bounded->fNext;
- }
- bounded = fBounded;
- while (bounded) {
- bounded->fBounded->addBounded(this, heap);
- bounded = bounded->fNext;
- }
- return true;
-}
-
-template<typename TCurve, typename OppCurve>
-void SkTSpan<TCurve, OppCurve>::validate() const {
-#if DEBUG_VALIDATE
- SkASSERT(this != fPrev);
- SkASSERT(this != fNext);
- SkASSERT(fNext == nullptr || fNext != fPrev);
- SkASSERT(fNext == nullptr || this == fNext->fPrev);
- SkASSERT(fPrev == nullptr || this == fPrev->fNext);
- this->validateBounded();
-#endif
-#if DEBUG_T_SECT
- SkASSERT(fBounds.width() || fBounds.height() || fCollapsed);
- SkASSERT(fBoundsMax == SkTMax(fBounds.width(), fBounds.height()) || fCollapsed == 0xFF);
- SkASSERT(0 <= fStartT);
- SkASSERT(fEndT <= 1);
- SkASSERT(fStartT <= fEndT);
- SkASSERT(fBounded || fCollapsed == 0xFF);
- if (fHasPerp) {
- if (fCoinStart.isMatch()) {
- validatePerpT(fCoinStart.perpT());
- validatePerpPt(fCoinStart.perpT(), fCoinStart.perpPt());
- }
- if (fCoinEnd.isMatch()) {
- validatePerpT(fCoinEnd.perpT());
- validatePerpPt(fCoinEnd.perpT(), fCoinEnd.perpPt());
- }
- }
-#endif
-}
-
-template<typename TCurve, typename OppCurve>
-void SkTSpan<TCurve, OppCurve>::validateBounded() const {
-#if DEBUG_VALIDATE
- const SkTSpanBounded<OppCurve, TCurve>* testBounded = fBounded;
- while (testBounded) {
- SkDEBUGCODE(const SkTSpan<OppCurve, TCurve>* overlap = testBounded->fBounded);
- SkASSERT(!overlap->fDeleted);
-#if DEBUG_T_SECT
- SkASSERT(((this->debugID() ^ overlap->debugID()) & 1) == 1);
- SkASSERT(overlap->findOppSpan(this));
-#endif
- testBounded = testBounded->fNext;
- }
-#endif
-}
-
-template<typename TCurve, typename OppCurve>
-void SkTSpan<TCurve, OppCurve>::validatePerpT(double oppT) const {
- const SkTSpanBounded<OppCurve, TCurve>* testBounded = fBounded;
- while (testBounded) {
- const SkTSpan<OppCurve, TCurve>* overlap = testBounded->fBounded;
- if (precisely_between(overlap->fStartT, oppT, overlap->fEndT)) {
- return;
- }
- testBounded = testBounded->fNext;
- }
- SkASSERT(0);
-}
-
-template<typename TCurve, typename OppCurve>
-void SkTSpan<TCurve, OppCurve>::validatePerpPt(double t, const SkDPoint& pt) const {
- SkASSERT(fDebugSect->fOppSect->fCurve.ptAtT(t) == pt);
-}
-
-
-template<typename TCurve, typename OppCurve>
-SkTSect<TCurve, OppCurve>::SkTSect(const TCurve& c
- SkDEBUGPARAMS(SkOpGlobalState* debugGlobalState)
- PATH_OPS_DEBUG_T_SECT_PARAMS(int id))
- : fCurve(c)
- , fHeap(sizeof(SkTSpan<TCurve, OppCurve>) * 4)
- , fCoincident(nullptr)
- , fDeleted(nullptr)
- , fActiveCount(0)
- , fHung(false)
- SkDEBUGPARAMS(fDebugGlobalState(debugGlobalState))
- PATH_OPS_DEBUG_T_SECT_PARAMS(fID(id))
- PATH_OPS_DEBUG_T_SECT_PARAMS(fDebugCount(0))
- PATH_OPS_DEBUG_T_SECT_PARAMS(fDebugAllocatedCount(0))
-{
- this->resetRemovedEnds();
- fHead = this->addOne();
- SkDEBUGCODE(fHead->debugSetGlobalState(debugGlobalState));
- fHead->init(c);
-}
-
-template<typename TCurve, typename OppCurve>
-SkTSpan<TCurve, OppCurve>* SkTSect<TCurve, OppCurve>::addOne() {
- SkTSpan<TCurve, OppCurve>* result;
- if (fDeleted) {
- result = fDeleted;
- fDeleted = result->fNext;
- } else {
- result = fHeap.make<SkTSpan<TCurve, OppCurve>>(fCurve, fHeap);
-#if DEBUG_T_SECT
- ++fDebugAllocatedCount;
-#endif
- }
- result->reset();
- result->fHasPerp = false;
- result->fDeleted = false;
- ++fActiveCount;
- PATH_OPS_DEBUG_T_SECT_CODE(result->fID = fDebugCount++ * 2 + fID);
- SkDEBUGCODE(result->fDebugSect = this);
-#ifdef SK_DEBUG
-#if !PATH_OP_COMPILE_FOR_SIZE
- result->debugInit();
-#endif
- result->fCoinStart.debugInit();
- result->fCoinEnd.debugInit();
- result->fPrev = result->fNext = nullptr;
- result->fBounds.debugInit();
- result->fStartT = result->fEndT = result->fBoundsMax = SK_ScalarNaN;
- result->fCollapsed = result->fIsLinear = result->fIsLine = 0xFF;
-#endif
- return result;
-}
-
-template<typename TCurve, typename OppCurve>
-bool SkTSect<TCurve, OppCurve>::binarySearchCoin(SkTSect<OppCurve, TCurve>* sect2, double tStart,
- double tStep, double* resultT, double* oppT, SkTSpan<OppCurve, TCurve>** oppFirst) {
- SkTSpan<TCurve, OppCurve> work(fCurve, fHeap);
- double result = work.fStartT = work.fEndT = tStart;
- SkDEBUGCODE(work.fDebugSect = this);
- SkDPoint last = fCurve.ptAtT(tStart);
- SkDPoint oppPt;
- bool flip = false;
- bool contained = false;
- bool down = tStep < 0;
- const OppCurve& opp = sect2->fCurve;
- do {
- tStep *= 0.5;
- work.fStartT += tStep;
- if (flip) {
- tStep = -tStep;
- flip = false;
- }
- work.initBounds(fCurve);
- if (work.fCollapsed) {
- return false;
- }
- if (last.approximatelyEqual(work.part()[0])) {
- break;
- }
- last = work.part()[0];
- work.fCoinStart.setPerp(fCurve, work.fStartT, last, opp);
- if (work.fCoinStart.isMatch()) {
-#if DEBUG_T_SECT
- work.validatePerpPt(work.fCoinStart.perpT(), work.fCoinStart.perpPt());
-#endif
- double oppTTest = work.fCoinStart.perpT();
- if (sect2->fHead->contains(oppTTest)) {
- *oppT = oppTTest;
- oppPt = work.fCoinStart.perpPt();
- contained = true;
- if (down ? result <= work.fStartT : result >= work.fStartT) {
- *oppFirst = nullptr; // signal caller to fail
- return false;
- }
- result = work.fStartT;
- continue;
- }
- }
- tStep = -tStep;
- flip = true;
- } while (true);
- if (!contained) {
- return false;
- }
- if (last.approximatelyEqual(fCurve[0])) {
- result = 0;
- } else if (last.approximatelyEqual(fCurve[fCurve.pointLast()])) {
- result = 1;
- }
- if (oppPt.approximatelyEqual(opp[0])) {
- *oppT = 0;
- } else if (oppPt.approximatelyEqual(opp[sect2->fCurve.pointLast()])) {
- *oppT = 1;
- }
- *resultT = result;
- return true;
-}
-
-// OPTIMIZE ? keep a sorted list of sizes in the form of a doubly-linked list in quad span
-// so that each quad sect has a pointer to the largest, and can update it as spans
-// are split
-template<typename TCurve, typename OppCurve>
-SkTSpan<TCurve, OppCurve>* SkTSect<TCurve, OppCurve>::boundsMax() {
- SkTSpan<TCurve, OppCurve>* test = fHead;
- SkTSpan<TCurve, OppCurve>* largest = fHead;
- bool lCollapsed = largest->fCollapsed;
- int safetyNet = 10000;
- while ((test = test->fNext)) {
- if (!--safetyNet) {
- fHung = true;
- return nullptr;
- }
- bool tCollapsed = test->fCollapsed;
- if ((lCollapsed && !tCollapsed) || (lCollapsed == tCollapsed &&
- largest->fBoundsMax < test->fBoundsMax)) {
- largest = test;
- lCollapsed = test->fCollapsed;
- }
- }
- return largest;
-}
-
-template<typename TCurve, typename OppCurve>
-bool SkTSect<TCurve, OppCurve>::coincidentCheck(SkTSect<OppCurve, TCurve>* sect2) {
- SkTSpan<TCurve, OppCurve>* first = fHead;
- if (!first) {
- return false;
- }
- SkTSpan<TCurve, OppCurve>* last, * next;
- do {
- int consecutive = this->countConsecutiveSpans(first, &last);
- next = last->fNext;
- if (consecutive < COINCIDENT_SPAN_COUNT) {
- continue;
- }
- this->validate();
- sect2->validate();
- this->computePerpendiculars(sect2, first, last);
- this->validate();
- sect2->validate();
- // check to see if a range of points are on the curve
- SkTSpan<TCurve, OppCurve>* coinStart = first;
- do {
- bool success = this->extractCoincident(sect2, coinStart, last, &coinStart);
- if (!success) {
- return false;
- }
- } while (coinStart && !last->fDeleted);
- if (!fHead || !sect2->fHead) {
- break;
- }
- if (!next || next->fDeleted) {
- break;
- }
- } while ((first = next));
- return true;
-}
-
-template<typename TCurve, typename OppCurve>
-void SkTSect<TCurve, OppCurve>::coincidentForce(SkTSect<OppCurve, TCurve>* sect2,
- double start1s, double start1e) {
- SkTSpan<TCurve, OppCurve>* first = fHead;
- SkTSpan<TCurve, OppCurve>* last = this->tail();
- SkTSpan<OppCurve, TCurve>* oppFirst = sect2->fHead;
- SkTSpan<OppCurve, TCurve>* oppLast = sect2->tail();
- bool deleteEmptySpans = this->updateBounded(first, last, oppFirst);
- deleteEmptySpans |= sect2->updateBounded(oppFirst, oppLast, first);
- this->removeSpanRange(first, last);
- sect2->removeSpanRange(oppFirst, oppLast);
- first->fStartT = start1s;
- first->fEndT = start1e;
- first->resetBounds(fCurve);
- first->fCoinStart.setPerp(fCurve, start1s, fCurve[0], sect2->fCurve);
- first->fCoinEnd.setPerp(fCurve, start1e, fCurve[fCurve.pointLast()], sect2->fCurve);
- bool oppMatched = first->fCoinStart.perpT() < first->fCoinEnd.perpT();
- double oppStartT = first->fCoinStart.perpT() == -1 ? 0 : SkTMax(0., first->fCoinStart.perpT());
- double oppEndT = first->fCoinEnd.perpT() == -1 ? 1 : SkTMin(1., first->fCoinEnd.perpT());
- if (!oppMatched) {
- using std::swap;
- swap(oppStartT, oppEndT);
- }
- oppFirst->fStartT = oppStartT;
- oppFirst->fEndT = oppEndT;
- oppFirst->resetBounds(sect2->fCurve);
- this->removeCoincident(first, false);
- sect2->removeCoincident(oppFirst, true);
- if (deleteEmptySpans) {
- this->deleteEmptySpans();
- sect2->deleteEmptySpans();
- }
-}
-
-template<typename TCurve, typename OppCurve>
-bool SkTSect<TCurve, OppCurve>::coincidentHasT(double t) {
- SkTSpan<TCurve, OppCurve>* test = fCoincident;
- while (test) {
- if (between(test->fStartT, t, test->fEndT)) {
- return true;
- }
- test = test->fNext;
- }
- return false;
-}
-
-template<typename TCurve, typename OppCurve>
-int SkTSect<TCurve, OppCurve>::collapsed() const {
- int result = 0;
- const SkTSpan<TCurve, OppCurve>* test = fHead;
- while (test) {
- if (test->fCollapsed) {
- ++result;
- }
- test = test->next();
- }
- return result;
-}
-
-template<typename TCurve, typename OppCurve>
-void SkTSect<TCurve, OppCurve>::computePerpendiculars(SkTSect<OppCurve, TCurve>* sect2,
- SkTSpan<TCurve, OppCurve>* first, SkTSpan<TCurve, OppCurve>* last) {
- const OppCurve& opp = sect2->fCurve;
- SkTSpan<TCurve, OppCurve>* work = first;
- SkTSpan<TCurve, OppCurve>* prior = nullptr;
- do {
- if (!work->fHasPerp && !work->fCollapsed) {
- if (prior) {
- work->fCoinStart = prior->fCoinEnd;
- } else {
- work->fCoinStart.setPerp(fCurve, work->fStartT, work->part()[0], opp);
- }
- if (work->fCoinStart.isMatch()) {
- double perpT = work->fCoinStart.perpT();
- if (sect2->coincidentHasT(perpT)) {
- work->fCoinStart.init();
- } else {
- sect2->addForPerp(work, perpT);
- }
- }
- work->fCoinEnd.setPerp(fCurve, work->fEndT, work->part()[fCurve.pointLast()], opp);
- if (work->fCoinEnd.isMatch()) {
- double perpT = work->fCoinEnd.perpT();
- if (sect2->coincidentHasT(perpT)) {
- work->fCoinEnd.init();
- } else {
- sect2->addForPerp(work, perpT);
- }
- }
- work->fHasPerp = true;
- }
- if (work == last) {
- break;
- }
- prior = work;
- work = work->fNext;
- SkASSERT(work);
- } while (true);
-}
-
-template<typename TCurve, typename OppCurve>
-int SkTSect<TCurve, OppCurve>::countConsecutiveSpans(SkTSpan<TCurve, OppCurve>* first,
- SkTSpan<TCurve, OppCurve>** lastPtr) const {
- int consecutive = 1;
- SkTSpan<TCurve, OppCurve>* last = first;
- do {
- SkTSpan<TCurve, OppCurve>* next = last->fNext;
- if (!next) {
- break;
- }
- if (next->fStartT > last->fEndT) {
- break;
- }
- ++consecutive;
- last = next;
- } while (true);
- *lastPtr = last;
- return consecutive;
-}
-
-template<typename TCurve, typename OppCurve>
-bool SkTSect<TCurve, OppCurve>::hasBounded(const SkTSpan<OppCurve, TCurve>* span) const {
- const SkTSpan<TCurve, OppCurve>* test = fHead;
- if (!test) {
- return false;
- }
- do {
- if (test->findOppSpan(span)) {
- return true;
- }
- } while ((test = test->next()));
- return false;
-}
-
-template<typename TCurve, typename OppCurve>
-bool SkTSect<TCurve, OppCurve>::deleteEmptySpans() {
- SkTSpan<TCurve, OppCurve>* test;
- SkTSpan<TCurve, OppCurve>* next = fHead;
- int safetyHatch = 1000;
- while ((test = next)) {
- next = test->fNext;
- if (!test->fBounded) {
- if (!this->removeSpan(test)) {
- return false;
- }
- }
- if (--safetyHatch < 0) {
- return false;
- }
- }
- return true;
-}
-
-template<typename TCurve, typename OppCurve>
-bool SkTSect<TCurve, OppCurve>::extractCoincident(
- SkTSect<OppCurve, TCurve>* sect2,
- SkTSpan<TCurve, OppCurve>* first, SkTSpan<TCurve, OppCurve>* last,
- SkTSpan<TCurve, OppCurve>** result) {
- first = findCoincidentRun(first, &last);
- if (!first || !last) {
- *result = nullptr;
- return true;
- }
- // march outwards to find limit of coincidence from here to previous and next spans
- double startT = first->fStartT;
- double oppStartT SK_INIT_TO_AVOID_WARNING;
- double oppEndT SK_INIT_TO_AVOID_WARNING;
- SkTSpan<TCurve, OppCurve>* prev = first->fPrev;
- SkASSERT(first->fCoinStart.isMatch());
- SkTSpan<OppCurve, TCurve>* oppFirst = first->findOppT(first->fCoinStart.perpT());
- SkOPASSERT(last->fCoinEnd.isMatch());
- bool oppMatched = first->fCoinStart.perpT() < first->fCoinEnd.perpT();
- double coinStart;
- SkDEBUGCODE(double coinEnd);
- SkTSpan<OppCurve, TCurve>* cutFirst;
- if (prev && prev->fEndT == startT
- && this->binarySearchCoin(sect2, startT, prev->fStartT - startT, &coinStart,
- &oppStartT, &oppFirst)
- && prev->fStartT < coinStart && coinStart < startT
- && (cutFirst = prev->oppT(oppStartT))) {
- oppFirst = cutFirst;
- first = this->addSplitAt(prev, coinStart);
- first->markCoincident();
- prev->fCoinEnd.markCoincident();
- if (oppFirst->fStartT < oppStartT && oppStartT < oppFirst->fEndT) {
- SkTSpan<OppCurve, TCurve>* oppHalf = sect2->addSplitAt(oppFirst, oppStartT);
- if (oppMatched) {
- oppFirst->fCoinEnd.markCoincident();
- oppHalf->markCoincident();
- oppFirst = oppHalf;
- } else {
- oppFirst->markCoincident();
- oppHalf->fCoinStart.markCoincident();
- }
- }
- } else {
- if (!oppFirst) {
- return false;
- }
- SkDEBUGCODE(coinStart = first->fStartT);
- SkDEBUGCODE(oppStartT = oppMatched ? oppFirst->fStartT : oppFirst->fEndT);
- }
- // FIXME: incomplete : if we're not at the end, find end of coin
- SkTSpan<OppCurve, TCurve>* oppLast;
- SkOPASSERT(last->fCoinEnd.isMatch());
- oppLast = last->findOppT(last->fCoinEnd.perpT());
- SkDEBUGCODE(coinEnd = last->fEndT);
-#ifdef SK_DEBUG
- if (!this->globalState() || !this->globalState()->debugSkipAssert()) {
- oppEndT = oppMatched ? oppLast->fEndT : oppLast->fStartT;
- }
-#endif
- if (!oppMatched) {
- using std::swap;
- swap(oppFirst, oppLast);
- swap(oppStartT, oppEndT);
- }
- SkOPASSERT(oppStartT < oppEndT);
- SkASSERT(coinStart == first->fStartT);
- SkASSERT(coinEnd == last->fEndT);
- SkOPASSERT(oppStartT == oppFirst->fStartT);
- SkOPASSERT(oppEndT == oppLast->fEndT);
- if (!oppFirst) {
- *result = nullptr;
- return true;
- }
- if (!oppLast) {
- *result = nullptr;
- return true;
- }
- // reduce coincident runs to single entries
- this->validate();
- sect2->validate();
- bool deleteEmptySpans = this->updateBounded(first, last, oppFirst);
- deleteEmptySpans |= sect2->updateBounded(oppFirst, oppLast, first);
- this->removeSpanRange(first, last);
- sect2->removeSpanRange(oppFirst, oppLast);
- first->fEndT = last->fEndT;
- first->resetBounds(this->fCurve);
- first->fCoinStart.setPerp(fCurve, first->fStartT, first->part()[0], sect2->fCurve);
- first->fCoinEnd.setPerp(fCurve, first->fEndT, first->part()[fCurve.pointLast()], sect2->fCurve);
- oppStartT = first->fCoinStart.perpT();
- oppEndT = first->fCoinEnd.perpT();
- if (between(0, oppStartT, 1) && between(0, oppEndT, 1)) {
- if (!oppMatched) {
- using std::swap;
- swap(oppStartT, oppEndT);
- }
- oppFirst->fStartT = oppStartT;
- oppFirst->fEndT = oppEndT;
- oppFirst->resetBounds(sect2->fCurve);
- }
- this->validateBounded();
- sect2->validateBounded();
- last = first->fNext;
- if (!this->removeCoincident(first, false)) {
- return false;
- }
- if (!sect2->removeCoincident(oppFirst, true)) {
- return false;
- }
- if (deleteEmptySpans) {
- if (!this->deleteEmptySpans() || !sect2->deleteEmptySpans()) {
- *result = nullptr;
- return false;
- }
- }
- this->validate();
- sect2->validate();
- *result = last && !last->fDeleted && fHead && sect2->fHead ? last : nullptr;
- return true;
-}
-
-template<typename TCurve, typename OppCurve>
-SkTSpan<TCurve, OppCurve>* SkTSect<TCurve, OppCurve>::findCoincidentRun(
- SkTSpan<TCurve, OppCurve>* first, SkTSpan<TCurve, OppCurve>** lastPtr) {
- SkTSpan<TCurve, OppCurve>* work = first;
- SkTSpan<TCurve, OppCurve>* lastCandidate = nullptr;
- first = nullptr;
- // find the first fully coincident span
- do {
- if (work->fCoinStart.isMatch()) {
-#if DEBUG_T_SECT
- work->validatePerpT(work->fCoinStart.perpT());
- work->validatePerpPt(work->fCoinStart.perpT(), work->fCoinStart.perpPt());
-#endif
- SkOPASSERT(work->hasOppT(work->fCoinStart.perpT()));
- if (!work->fCoinEnd.isMatch()) {
- break;
- }
- lastCandidate = work;
- if (!first) {
- first = work;
- }
- } else if (first && work->fCollapsed) {
- *lastPtr = lastCandidate;
- return first;
- } else {
- lastCandidate = nullptr;
- SkOPASSERT(!first);
- }
- if (work == *lastPtr) {
- return first;
- }
- work = work->fNext;
- if (!work) {
- return nullptr;
- }
- } while (true);
- if (lastCandidate) {
- *lastPtr = lastCandidate;
- }
- return first;
-}
-
-template<typename TCurve, typename OppCurve>
-int SkTSect<TCurve, OppCurve>::intersects(SkTSpan<TCurve, OppCurve>* span,
- SkTSect<OppCurve, TCurve>* opp,
- SkTSpan<OppCurve, TCurve>* oppSpan, int* oppResult) {
- bool spanStart, oppStart;
- int hullResult = span->hullsIntersect(oppSpan, &spanStart, &oppStart);
- if (hullResult >= 0) {
- if (hullResult == 2) { // hulls have one point in common
- if (!span->fBounded || !span->fBounded->fNext) {
- SkASSERT(!span->fBounded || span->fBounded->fBounded == oppSpan);
- if (spanStart) {
- span->fEndT = span->fStartT;
- } else {
- span->fStartT = span->fEndT;
- }
- } else {
- hullResult = 1;
- }
- if (!oppSpan->fBounded || !oppSpan->fBounded->fNext) {
- SkASSERT(!oppSpan->fBounded || oppSpan->fBounded->fBounded == span);
- if (oppStart) {
- oppSpan->fEndT = oppSpan->fStartT;
- } else {
- oppSpan->fStartT = oppSpan->fEndT;
- }
- *oppResult = 2;
- } else {
- *oppResult = 1;
- }
- } else {
- *oppResult = 1;
- }
- return hullResult;
- }
- if (span->fIsLine && oppSpan->fIsLine) {
- SkIntersections i;
- int sects = this->linesIntersect(span, opp, oppSpan, &i);
- if (sects == 2) {
- return *oppResult = 1;
- }
- if (!sects) {
- return -1;
- }
- this->removedEndCheck(span);
- span->fStartT = span->fEndT = i[0][0];
- opp->removedEndCheck(oppSpan);
- oppSpan->fStartT = oppSpan->fEndT = i[1][0];
- return *oppResult = 2;
- }
- if (span->fIsLinear || oppSpan->fIsLinear) {
- return *oppResult = (int) span->linearsIntersect(oppSpan);
- }
- return *oppResult = 1;
-}
-
-template<typename TCurve>
-static bool is_parallel(const SkDLine& thisLine, const TCurve& opp) {
- if (!opp.IsConic()) {
- return false; // FIXME : breaks a lot of stuff now
- }
- int finds = 0;
- SkDLine thisPerp;
- thisPerp.fPts[0].fX = thisLine.fPts[1].fX + (thisLine.fPts[1].fY - thisLine.fPts[0].fY);
- thisPerp.fPts[0].fY = thisLine.fPts[1].fY + (thisLine.fPts[0].fX - thisLine.fPts[1].fX);
- thisPerp.fPts[1] = thisLine.fPts[1];
- SkIntersections perpRayI;
- perpRayI.intersectRay(opp, thisPerp);
- for (int pIndex = 0; pIndex < perpRayI.used(); ++pIndex) {
- finds += perpRayI.pt(pIndex).approximatelyEqual(thisPerp.fPts[1]);
- }
- thisPerp.fPts[1].fX = thisLine.fPts[0].fX + (thisLine.fPts[1].fY - thisLine.fPts[0].fY);
- thisPerp.fPts[1].fY = thisLine.fPts[0].fY + (thisLine.fPts[0].fX - thisLine.fPts[1].fX);
- thisPerp.fPts[0] = thisLine.fPts[0];
- perpRayI.intersectRay(opp, thisPerp);
- for (int pIndex = 0; pIndex < perpRayI.used(); ++pIndex) {
- finds += perpRayI.pt(pIndex).approximatelyEqual(thisPerp.fPts[0]);
- }
- return finds >= 2;
-}
-
-// while the intersection points are sufficiently far apart:
-// construct the tangent lines from the intersections
-// find the point where the tangent line intersects the opposite curve
-template<typename TCurve, typename OppCurve>
-int SkTSect<TCurve, OppCurve>::linesIntersect(SkTSpan<TCurve, OppCurve>* span,
- SkTSect<OppCurve, TCurve>* opp,
- SkTSpan<OppCurve, TCurve>* oppSpan, SkIntersections* i) {
- SkIntersections thisRayI SkDEBUGCODE((span->fDebugGlobalState));
- SkIntersections oppRayI SkDEBUGCODE((span->fDebugGlobalState));
- SkDLine thisLine = {{ span->part()[0], span->part()[fCurve.pointLast()] }};
- SkDLine oppLine = {{ oppSpan->part()[0], oppSpan->part()[opp->fCurve.pointLast()] }};
- int loopCount = 0;
- double bestDistSq = DBL_MAX;
- if (!thisRayI.intersectRay(opp->fCurve, thisLine)) {
- return 0;
- }
- if (!oppRayI.intersectRay(this->fCurve, oppLine)) {
- return 0;
- }
- // if the ends of each line intersect the opposite curve, the lines are coincident
- if (thisRayI.used() > 1) {
- int ptMatches = 0;
- for (int tIndex = 0; tIndex < thisRayI.used(); ++tIndex) {
- for (int lIndex = 0; lIndex < (int) SK_ARRAY_COUNT(thisLine.fPts); ++lIndex) {
- ptMatches += thisRayI.pt(tIndex).approximatelyEqual(thisLine.fPts[lIndex]);
- }
- }
- if (ptMatches == 2 || is_parallel(thisLine, opp->fCurve)) {
- return 2;
- }
- }
- if (oppRayI.used() > 1) {
- int ptMatches = 0;
- for (int oIndex = 0; oIndex < oppRayI.used(); ++oIndex) {
- for (int lIndex = 0; lIndex < (int) SK_ARRAY_COUNT(oppLine.fPts); ++lIndex) {
- ptMatches += oppRayI.pt(oIndex).approximatelyEqual(oppLine.fPts[lIndex]);
- }
- }
- if (ptMatches == 2|| is_parallel(oppLine, this->fCurve)) {
- return 2;
- }
- }
- do {
- // pick the closest pair of points
- double closest = DBL_MAX;
- int closeIndex SK_INIT_TO_AVOID_WARNING;
- int oppCloseIndex SK_INIT_TO_AVOID_WARNING;
- for (int index = 0; index < oppRayI.used(); ++index) {
- if (!roughly_between(span->fStartT, oppRayI[0][index], span->fEndT)) {
- continue;
- }
- for (int oIndex = 0; oIndex < thisRayI.used(); ++oIndex) {
- if (!roughly_between(oppSpan->fStartT, thisRayI[0][oIndex], oppSpan->fEndT)) {
- continue;
- }
- double distSq = thisRayI.pt(index).distanceSquared(oppRayI.pt(oIndex));
- if (closest > distSq) {
- closest = distSq;
- closeIndex = index;
- oppCloseIndex = oIndex;
- }
- }
- }
- if (closest == DBL_MAX) {
- break;
- }
- const SkDPoint& oppIPt = thisRayI.pt(oppCloseIndex);
- const SkDPoint& iPt = oppRayI.pt(closeIndex);
- if (between(span->fStartT, oppRayI[0][closeIndex], span->fEndT)
- && between(oppSpan->fStartT, thisRayI[0][oppCloseIndex], oppSpan->fEndT)
- && oppIPt.approximatelyEqual(iPt)) {
- i->merge(oppRayI, closeIndex, thisRayI, oppCloseIndex);
- return i->used();
- }
- double distSq = oppIPt.distanceSquared(iPt);
- if (bestDistSq < distSq || ++loopCount > 5) {
- return 0;
- }
- bestDistSq = distSq;
- double oppStart = oppRayI[0][closeIndex];
- thisLine[0] = fCurve.ptAtT(oppStart);
- thisLine[1] = thisLine[0] + fCurve.dxdyAtT(oppStart);
- if (!thisRayI.intersectRay(opp->fCurve, thisLine)) {
- break;
- }
- double start = thisRayI[0][oppCloseIndex];
- oppLine[0] = opp->fCurve.ptAtT(start);
- oppLine[1] = oppLine[0] + opp->fCurve.dxdyAtT(start);
- if (!oppRayI.intersectRay(this->fCurve, oppLine)) {
- break;
- }
- } while (true);
- // convergence may fail if the curves are nearly coincident
- SkTCoincident<OppCurve, TCurve> oCoinS, oCoinE;
- oCoinS.setPerp(opp->fCurve, oppSpan->fStartT, oppSpan->part()[0], fCurve);
- oCoinE.setPerp(opp->fCurve, oppSpan->fEndT, oppSpan->part()[opp->fCurve.pointLast()], fCurve);
- double tStart = oCoinS.perpT();
- double tEnd = oCoinE.perpT();
- bool swap = tStart > tEnd;
- if (swap) {
- using std::swap;
- swap(tStart, tEnd);
- }
- tStart = SkTMax(tStart, span->fStartT);
- tEnd = SkTMin(tEnd, span->fEndT);
- if (tStart > tEnd) {
- return 0;
- }
- SkDVector perpS, perpE;
- if (tStart == span->fStartT) {
- SkTCoincident<TCurve, OppCurve> coinS;
- coinS.setPerp(fCurve, span->fStartT, span->part()[0], opp->fCurve);
- perpS = span->part()[0] - coinS.perpPt();
- } else if (swap) {
- perpS = oCoinE.perpPt() - oppSpan->part()[opp->fCurve.pointLast()];
- } else {
- perpS = oCoinS.perpPt() - oppSpan->part()[0];
- }
- if (tEnd == span->fEndT) {
- SkTCoincident<TCurve, OppCurve> coinE;
- coinE.setPerp(fCurve, span->fEndT, span->part()[fCurve.pointLast()], opp->fCurve);
- perpE = span->part()[fCurve.pointLast()] - coinE.perpPt();
- } else if (swap) {
- perpE = oCoinS.perpPt() - oppSpan->part()[0];
- } else {
- perpE = oCoinE.perpPt() - oppSpan->part()[opp->fCurve.pointLast()];
- }
- if (perpS.dot(perpE) >= 0) {
- return 0;
- }
- SkTCoincident<TCurve, OppCurve> coinW;
- double workT = tStart;
- double tStep = tEnd - tStart;
- SkDPoint workPt;
- do {
- tStep *= 0.5;
- if (precisely_zero(tStep)) {
- return 0;
- }
- workT += tStep;
- workPt = fCurve.ptAtT(workT);
- coinW.setPerp(fCurve, workT, workPt, opp->fCurve);
- double perpT = coinW.perpT();
- if (coinW.isMatch() ? !between(oppSpan->fStartT, perpT, oppSpan->fEndT) : perpT < 0) {
- continue;
- }
- SkDVector perpW = workPt - coinW.perpPt();
- if ((perpS.dot(perpW) >= 0) == (tStep < 0)) {
- tStep = -tStep;
- }
- if (workPt.approximatelyEqual(coinW.perpPt())) {
- break;
- }
- } while (true);
- double oppTTest = coinW.perpT();
- if (!opp->fHead->contains(oppTTest)) {
- return 0;
- }
- i->setMax(1);
- i->insert(workT, oppTTest, workPt);
- return 1;
-}
-
-
-template<typename TCurve, typename OppCurve>
-bool SkTSect<TCurve, OppCurve>::markSpanGone(SkTSpan<TCurve, OppCurve>* span) {
- if (--fActiveCount < 0) {
- return false;
- }
- span->fNext = fDeleted;
- fDeleted = span;
- SkOPASSERT(!span->fDeleted);
- span->fDeleted = true;
- return true;
-}
-
-template<typename TCurve, typename OppCurve>
-bool SkTSect<TCurve, OppCurve>::matchedDirection(double t, const SkTSect<OppCurve, TCurve>* sect2,
- double t2) const {
- SkDVector dxdy = this->fCurve.dxdyAtT(t);
- SkDVector dxdy2 = sect2->fCurve.dxdyAtT(t2);
- return dxdy.dot(dxdy2) >= 0;
-}
-
-template<typename TCurve, typename OppCurve>
-void SkTSect<TCurve, OppCurve>::matchedDirCheck(double t, const SkTSect<OppCurve, TCurve>* sect2,
- double t2, bool* calcMatched, bool* oppMatched) const {
- if (*calcMatched) {
- SkASSERT(*oppMatched == this->matchedDirection(t, sect2, t2));
- } else {
- *oppMatched = this->matchedDirection(t, sect2, t2);
- *calcMatched = true;
- }
-}
-
-template<typename TCurve, typename OppCurve>
-void SkTSect<TCurve, OppCurve>::mergeCoincidence(SkTSect<OppCurve, TCurve>* sect2) {
- double smallLimit = 0;
- do {
- // find the smallest unprocessed span
- SkTSpan<TCurve, OppCurve>* smaller = nullptr;
- SkTSpan<TCurve, OppCurve>* test = fCoincident;
- do {
- if (!test) {
- return;
- }
- if (test->fStartT < smallLimit) {
- continue;
- }
- if (smaller && smaller->fEndT < test->fStartT) {
- continue;
- }
- smaller = test;
- } while ((test = test->fNext));
- if (!smaller) {
- return;
- }
- smallLimit = smaller->fEndT;
- // find next larger span
- SkTSpan<TCurve, OppCurve>* prior = nullptr;
- SkTSpan<TCurve, OppCurve>* larger = nullptr;
- SkTSpan<TCurve, OppCurve>* largerPrior = nullptr;
- test = fCoincident;
- do {
- if (test->fStartT < smaller->fEndT) {
- continue;
- }
- SkOPASSERT(test->fStartT != smaller->fEndT);
- if (larger && larger->fStartT < test->fStartT) {
- continue;
- }
- largerPrior = prior;
- larger = test;
- } while ((prior = test), (test = test->fNext));
- if (!larger) {
- continue;
- }
- // check middle t value to see if it is coincident as well
- double midT = (smaller->fEndT + larger->fStartT) / 2;
- SkDPoint midPt = fCurve.ptAtT(midT);
- SkTCoincident<TCurve, OppCurve> coin;
- coin.setPerp(fCurve, midT, midPt, sect2->fCurve);
- if (coin.isMatch()) {
- smaller->fEndT = larger->fEndT;
- smaller->fCoinEnd = larger->fCoinEnd;
- if (largerPrior) {
- largerPrior->fNext = larger->fNext;
- largerPrior->validate();
- } else {
- fCoincident = larger->fNext;
- }
- }
- } while (true);
-}
-
-template<typename TCurve, typename OppCurve>
-SkTSpan<TCurve, OppCurve>* SkTSect<TCurve, OppCurve>::prev(
- SkTSpan<TCurve, OppCurve>* span) const {
- SkTSpan<TCurve, OppCurve>* result = nullptr;
- SkTSpan<TCurve, OppCurve>* test = fHead;
- while (span != test) {
- result = test;
- test = test->fNext;
- SkASSERT(test);
- }
- return result;
-}
-
-template<typename TCurve, typename OppCurve>
-void SkTSect<TCurve, OppCurve>::recoverCollapsed() {
- SkTSpan<TCurve, OppCurve>* deleted = fDeleted;
- while (deleted) {
- SkTSpan<TCurve, OppCurve>* delNext = deleted->fNext;
- if (deleted->fCollapsed) {
- SkTSpan<TCurve, OppCurve>** spanPtr = &fHead;
- while (*spanPtr && (*spanPtr)->fEndT <= deleted->fStartT) {
- spanPtr = &(*spanPtr)->fNext;
- }
- deleted->fNext = *spanPtr;
- *spanPtr = deleted;
- }
- deleted = delNext;
- }
-}
-
-template<typename TCurve, typename OppCurve>
-void SkTSect<TCurve, OppCurve>::removeAllBut(const SkTSpan<OppCurve, TCurve>* keep,
- SkTSpan<TCurve, OppCurve>* span, SkTSect<OppCurve, TCurve>* opp) {
- const SkTSpanBounded<OppCurve, TCurve>* testBounded = span->fBounded;
- while (testBounded) {
- SkTSpan<OppCurve, TCurve>* bounded = testBounded->fBounded;
- const SkTSpanBounded<OppCurve, TCurve>* next = testBounded->fNext;
- // may have been deleted when opp did 'remove all but'
- if (bounded != keep && !bounded->fDeleted) {
- SkAssertResult(SkDEBUGCODE(!) span->removeBounded(bounded));
- if (bounded->removeBounded(span)) {
- opp->removeSpan(bounded);
- }
- }
- testBounded = next;
- }
- SkASSERT(!span->fDeleted);
- SkASSERT(span->findOppSpan(keep));
- SkASSERT(keep->findOppSpan(span));
-}
-
-template<typename TCurve, typename OppCurve>
-bool SkTSect<TCurve, OppCurve>::removeByPerpendicular(SkTSect<OppCurve, TCurve>* opp) {
- SkTSpan<TCurve, OppCurve>* test = fHead;
- SkTSpan<TCurve, OppCurve>* next;
- do {
- next = test->fNext;
- if (test->fCoinStart.perpT() < 0 || test->fCoinEnd.perpT() < 0) {
- continue;
- }
- SkDVector startV = test->fCoinStart.perpPt() - test->part()[0];
- SkDVector endV = test->fCoinEnd.perpPt() - test->part()[fCurve.pointLast()];
-#if DEBUG_T_SECT
- SkDebugf("%s startV=(%1.9g,%1.9g) endV=(%1.9g,%1.9g) dot=%1.9g\n", __FUNCTION__,
- startV.fX, startV.fY, endV.fX, endV.fY, startV.dot(endV));
-#endif
- if (startV.dot(endV) <= 0) {
- continue;
- }
- if (!this->removeSpans(test, opp)) {
- return false;
- }
- } while ((test = next));
- return true;
-}
-
-template<typename TCurve, typename OppCurve>
-bool SkTSect<TCurve, OppCurve>::removeCoincident(SkTSpan<TCurve, OppCurve>* span, bool isBetween) {
- if (!this->unlinkSpan(span)) {
- return false;
- }
- if (isBetween || between(0, span->fCoinStart.perpT(), 1)) {
- --fActiveCount;
- span->fNext = fCoincident;
- fCoincident = span;
- } else {
- this->markSpanGone(span);
- }
- return true;
-}
-
-template<typename TCurve, typename OppCurve>
-void SkTSect<TCurve, OppCurve>::removedEndCheck(SkTSpan<TCurve, OppCurve>* span) {
- if (!span->fStartT) {
- fRemovedStartT = true;
- }
- if (1 == span->fEndT) {
- fRemovedEndT = true;
- }
-}
-
-template<typename TCurve, typename OppCurve>
-bool SkTSect<TCurve, OppCurve>::removeSpan(SkTSpan<TCurve, OppCurve>* span) {\
- this->removedEndCheck(span);
- if (!this->unlinkSpan(span)) {
- return false;
- }
- return this->markSpanGone(span);
-}
-
-template<typename TCurve, typename OppCurve>
-void SkTSect<TCurve, OppCurve>::removeSpanRange(SkTSpan<TCurve, OppCurve>* first,
- SkTSpan<TCurve, OppCurve>* last) {
- if (first == last) {
- return;
- }
- SkTSpan<TCurve, OppCurve>* span = first;
- SkASSERT(span);
- SkTSpan<TCurve, OppCurve>* final = last->fNext;
- SkTSpan<TCurve, OppCurve>* next = span->fNext;
- while ((span = next) && span != final) {
- next = span->fNext;
- this->markSpanGone(span);
- }
- if (final) {
- final->fPrev = first;
- }
- first->fNext = final;
- // world may not be ready for validation here
- first->validate();
-}
-
-template<typename TCurve, typename OppCurve>
-bool SkTSect<TCurve, OppCurve>::removeSpans(SkTSpan<TCurve, OppCurve>* span,
- SkTSect<OppCurve, TCurve>* opp) {
- SkTSpanBounded<OppCurve, TCurve>* bounded = span->fBounded;
- while (bounded) {
- SkTSpan<OppCurve, TCurve>* spanBounded = bounded->fBounded;
- SkTSpanBounded<OppCurve, TCurve>* next = bounded->fNext;
- if (span->removeBounded(spanBounded)) { // shuffles last into position 0
- this->removeSpan(span);
- }
- if (spanBounded->removeBounded(span)) {
- opp->removeSpan(spanBounded);
- }
- if (span->fDeleted && opp->hasBounded(span)) {
- return false;
- }
- bounded = next;
- }
- return true;
-}
-
-template<typename TCurve, typename OppCurve>
-SkTSpan<TCurve, OppCurve>* SkTSect<TCurve, OppCurve>::spanAtT(double t,
- SkTSpan<TCurve, OppCurve>** priorSpan) {
- SkTSpan<TCurve, OppCurve>* test = fHead;
- SkTSpan<TCurve, OppCurve>* prev = nullptr;
- while (test && test->fEndT < t) {
- prev = test;
- test = test->fNext;
- }
- *priorSpan = prev;
- return test && test->fStartT <= t ? test : nullptr;
-}
-
-template<typename TCurve, typename OppCurve>
-SkTSpan<TCurve, OppCurve>* SkTSect<TCurve, OppCurve>::tail() {
- SkTSpan<TCurve, OppCurve>* result = fHead;
- SkTSpan<TCurve, OppCurve>* next = fHead;
- while ((next = next->fNext)) {
- if (next->fEndT > result->fEndT) {
- result = next;
- }
- }
- return result;
-}
-
-/* Each span has a range of opposite spans it intersects. After the span is split in two,
- adjust the range to its new size */
-template<typename TCurve, typename OppCurve>
-bool SkTSect<TCurve, OppCurve>::trim(SkTSpan<TCurve, OppCurve>* span,
- SkTSect<OppCurve, TCurve>* opp) {
- FAIL_IF(!span->initBounds(fCurve));
- const SkTSpanBounded<OppCurve, TCurve>* testBounded = span->fBounded;
- while (testBounded) {
- SkTSpan<OppCurve, TCurve>* test = testBounded->fBounded;
- const SkTSpanBounded<OppCurve, TCurve>* next = testBounded->fNext;
- int oppSects, sects = this->intersects(span, opp, test, &oppSects);
- if (sects >= 1) {
- if (oppSects == 2) {
- test->initBounds(opp->fCurve);
- opp->removeAllBut(span, test, this);
- }
- if (sects == 2) {
- span->initBounds(fCurve);
- this->removeAllBut(test, span, opp);
- return true;
- }
- } else {
- if (span->removeBounded(test)) {
- this->removeSpan(span);
- }
- if (test->removeBounded(span)) {
- opp->removeSpan(test);
- }
- }
- testBounded = next;
- }
- return true;
-}
-
-template<typename TCurve, typename OppCurve>
-bool SkTSect<TCurve, OppCurve>::unlinkSpan(SkTSpan<TCurve, OppCurve>* span) {
- SkTSpan<TCurve, OppCurve>* prev = span->fPrev;
- SkTSpan<TCurve, OppCurve>* next = span->fNext;
- if (prev) {
- prev->fNext = next;
- if (next) {
- next->fPrev = prev;
- if (next->fStartT > next->fEndT) {
- return false;
- }
- // world may not be ready for validate here
- next->validate();
- }
- } else {
- fHead = next;
- if (next) {
- next->fPrev = nullptr;
- }
- }
- return true;
-}
-
-template<typename TCurve, typename OppCurve>
-bool SkTSect<TCurve, OppCurve>::updateBounded(SkTSpan<TCurve, OppCurve>* first,
- SkTSpan<TCurve, OppCurve>* last, SkTSpan<OppCurve, TCurve>* oppFirst) {
- SkTSpan<TCurve, OppCurve>* test = first;
- const SkTSpan<TCurve, OppCurve>* final = last->next();
- bool deleteSpan = false;
- do {
- deleteSpan |= test->removeAllBounded();
- } while ((test = test->fNext) != final && test);
- first->fBounded = nullptr;
- first->addBounded(oppFirst, &fHeap);
- // cannot call validate until remove span range is called
- return deleteSpan;
-}
-
-
-template<typename TCurve, typename OppCurve>
-void SkTSect<TCurve, OppCurve>::validate() const {
-#if DEBUG_VALIDATE
- int count = 0;
- double last = 0;
- if (fHead) {
- const SkTSpan<TCurve, OppCurve>* span = fHead;
- SkASSERT(!span->fPrev);
- const SkTSpan<TCurve, OppCurve>* next;
- do {
- span->validate();
- SkASSERT(span->fStartT >= last);
- last = span->fEndT;
- ++count;
- next = span->fNext;
- SkASSERT(next != span);
- } while ((span = next) != nullptr);
- }
- SkASSERT(count == fActiveCount);
-#endif
-#if DEBUG_T_SECT
- SkASSERT(fActiveCount <= fDebugAllocatedCount);
- int deletedCount = 0;
- const SkTSpan<TCurve, OppCurve>* deleted = fDeleted;
- while (deleted) {
- ++deletedCount;
- deleted = deleted->fNext;
- }
- const SkTSpan<TCurve, OppCurve>* coincident = fCoincident;
- while (coincident) {
- ++deletedCount;
- coincident = coincident->fNext;
- }
- SkASSERT(fActiveCount + deletedCount == fDebugAllocatedCount);
-#endif
-}
-
-template<typename TCurve, typename OppCurve>
-void SkTSect<TCurve, OppCurve>::validateBounded() const {
-#if DEBUG_VALIDATE
- if (!fHead) {
- return;
- }
- const SkTSpan<TCurve, OppCurve>* span = fHead;
- do {
- span->validateBounded();
- } while ((span = span->fNext) != nullptr);
-#endif
-}
-
-template<typename TCurve, typename OppCurve>
-int SkTSect<TCurve, OppCurve>::EndsEqual(const SkTSect<TCurve, OppCurve>* sect1,
- const SkTSect<OppCurve, TCurve>* sect2, SkIntersections* intersections) {
- int zeroOneSet = 0;
- if (sect1->fCurve[0] == sect2->fCurve[0]) {
- zeroOneSet |= kZeroS1Set | kZeroS2Set;
- intersections->insert(0, 0, sect1->fCurve[0]);
- }
- if (sect1->fCurve[0] == sect2->fCurve[sect2->fCurve.pointLast()]) {
- zeroOneSet |= kZeroS1Set | kOneS2Set;
- intersections->insert(0, 1, sect1->fCurve[0]);
- }
- if (sect1->fCurve[sect1->fCurve.pointLast()] == sect2->fCurve[0]) {
- zeroOneSet |= kOneS1Set | kZeroS2Set;
- intersections->insert(1, 0, sect1->fCurve[sect1->fCurve.pointLast()]);
- }
- if (sect1->fCurve[sect1->fCurve.pointLast()] == sect2->fCurve[sect2->fCurve.pointLast()]) {
- zeroOneSet |= kOneS1Set | kOneS2Set;
- intersections->insert(1, 1, sect1->fCurve[sect1->fCurve.pointLast()]);
- }
- // check for zero
- if (!(zeroOneSet & (kZeroS1Set | kZeroS2Set))
- && sect1->fCurve[0].approximatelyEqual(sect2->fCurve[0])) {
- zeroOneSet |= kZeroS1Set | kZeroS2Set;
- intersections->insertNear(0, 0, sect1->fCurve[0], sect2->fCurve[0]);
- }
- if (!(zeroOneSet & (kZeroS1Set | kOneS2Set))
- && sect1->fCurve[0].approximatelyEqual(sect2->fCurve[sect2->fCurve.pointLast()])) {
- zeroOneSet |= kZeroS1Set | kOneS2Set;
- intersections->insertNear(0, 1, sect1->fCurve[0], sect2->fCurve[sect2->fCurve.pointLast()]);
- }
- // check for one
- if (!(zeroOneSet & (kOneS1Set | kZeroS2Set))
- && sect1->fCurve[sect1->fCurve.pointLast()].approximatelyEqual(sect2->fCurve[0])) {
- zeroOneSet |= kOneS1Set | kZeroS2Set;
- intersections->insertNear(1, 0, sect1->fCurve[sect1->fCurve.pointLast()], sect2->fCurve[0]);
- }
- if (!(zeroOneSet & (kOneS1Set | kOneS2Set))
- && sect1->fCurve[sect1->fCurve.pointLast()].approximatelyEqual(sect2->fCurve[
- sect2->fCurve.pointLast()])) {
- zeroOneSet |= kOneS1Set | kOneS2Set;
- intersections->insertNear(1, 1, sect1->fCurve[sect1->fCurve.pointLast()],
- sect2->fCurve[sect2->fCurve.pointLast()]);
- }
- return zeroOneSet;
-}
-
-template<typename TCurve, typename OppCurve>
-struct SkClosestRecord {
- bool operator<(const SkClosestRecord& rh) const {
- return fClosest < rh.fClosest;
- }
-
- void addIntersection(SkIntersections* intersections) const {
- double r1t = fC1Index ? fC1Span->endT() : fC1Span->startT();
- double r2t = fC2Index ? fC2Span->endT() : fC2Span->startT();
- intersections->insert(r1t, r2t, fC1Span->part()[fC1Index]);
- }
-
- void findEnd(const SkTSpan<TCurve, OppCurve>* span1, const SkTSpan<OppCurve, TCurve>* span2,
- int c1Index, int c2Index) {
- const TCurve& c1 = span1->part();
- const OppCurve& c2 = span2->part();
- if (!c1[c1Index].approximatelyEqual(c2[c2Index])) {
- return;
- }
- double dist = c1[c1Index].distanceSquared(c2[c2Index]);
- if (fClosest < dist) {
- return;
- }
- fC1Span = span1;
- fC2Span = span2;
- fC1StartT = span1->startT();
- fC1EndT = span1->endT();
- fC2StartT = span2->startT();
- fC2EndT = span2->endT();
- fC1Index = c1Index;
- fC2Index = c2Index;
- fClosest = dist;
- }
-
- bool matesWith(const SkClosestRecord& mate SkDEBUGPARAMS(SkIntersections* i)) const {
- SkOPOBJASSERT(i, fC1Span == mate.fC1Span || fC1Span->endT() <= mate.fC1Span->startT()
- || mate.fC1Span->endT() <= fC1Span->startT());
- SkOPOBJASSERT(i, fC2Span == mate.fC2Span || fC2Span->endT() <= mate.fC2Span->startT()
- || mate.fC2Span->endT() <= fC2Span->startT());
- return fC1Span == mate.fC1Span || fC1Span->endT() == mate.fC1Span->startT()
- || fC1Span->startT() == mate.fC1Span->endT()
- || fC2Span == mate.fC2Span
- || fC2Span->endT() == mate.fC2Span->startT()
- || fC2Span->startT() == mate.fC2Span->endT();
- }
-
- void merge(const SkClosestRecord& mate) {
- fC1Span = mate.fC1Span;
- fC2Span = mate.fC2Span;
- fClosest = mate.fClosest;
- fC1Index = mate.fC1Index;
- fC2Index = mate.fC2Index;
- }
-
- void reset() {
- fClosest = FLT_MAX;
- SkDEBUGCODE(fC1Span = nullptr);
- SkDEBUGCODE(fC2Span = nullptr);
- SkDEBUGCODE(fC1Index = fC2Index = -1);
- }
-
- void update(const SkClosestRecord& mate) {
- fC1StartT = SkTMin(fC1StartT, mate.fC1StartT);
- fC1EndT = SkTMax(fC1EndT, mate.fC1EndT);
- fC2StartT = SkTMin(fC2StartT, mate.fC2StartT);
- fC2EndT = SkTMax(fC2EndT, mate.fC2EndT);
- }
-
- const SkTSpan<TCurve, OppCurve>* fC1Span;
- const SkTSpan<OppCurve, TCurve>* fC2Span;
- double fC1StartT;
- double fC1EndT;
- double fC2StartT;
- double fC2EndT;
- double fClosest;
- int fC1Index;
- int fC2Index;
-};
-
-template<typename TCurve, typename OppCurve>
-struct SkClosestSect {
- SkClosestSect()
- : fUsed(0) {
- fClosest.push_back().reset();
- }
-
- bool find(const SkTSpan<TCurve, OppCurve>* span1, const SkTSpan<OppCurve, TCurve>* span2
- SkDEBUGPARAMS(SkIntersections* i)) {
- SkClosestRecord<TCurve, OppCurve>* record = &fClosest[fUsed];
- record->findEnd(span1, span2, 0, 0);
- record->findEnd(span1, span2, 0, span2->part().pointLast());
- record->findEnd(span1, span2, span1->part().pointLast(), 0);
- record->findEnd(span1, span2, span1->part().pointLast(), span2->part().pointLast());
- if (record->fClosest == FLT_MAX) {
- return false;
- }
- for (int index = 0; index < fUsed; ++index) {
- SkClosestRecord<TCurve, OppCurve>* test = &fClosest[index];
- if (test->matesWith(*record SkDEBUGPARAMS(i))) {
- if (test->fClosest > record->fClosest) {
- test->merge(*record);
- }
- test->update(*record);
- record->reset();
- return false;
- }
- }
- ++fUsed;
- fClosest.push_back().reset();
- return true;
- }
-
- void finish(SkIntersections* intersections) const {
- SkSTArray<SkDCubic::kMaxIntersections * 3,
- const SkClosestRecord<TCurve, OppCurve>*, true> closestPtrs;
- for (int index = 0; index < fUsed; ++index) {
- closestPtrs.push_back(&fClosest[index]);
- }
- SkTQSort<const SkClosestRecord<TCurve, OppCurve> >(closestPtrs.begin(), closestPtrs.end()
- - 1);
- for (int index = 0; index < fUsed; ++index) {
- const SkClosestRecord<TCurve, OppCurve>* test = closestPtrs[index];
- test->addIntersection(intersections);
- }
- }
-
- // this is oversized so that an extra records can merge into final one
- SkSTArray<SkDCubic::kMaxIntersections * 2, SkClosestRecord<TCurve, OppCurve>, true> fClosest;
- int fUsed;
-};
-
-// returns true if the rect is too small to consider
-template<typename TCurve, typename OppCurve>
-void SkTSect<TCurve, OppCurve>::BinarySearch(SkTSect<TCurve, OppCurve>* sect1,
- SkTSect<OppCurve, TCurve>* sect2, SkIntersections* intersections) {
-#if DEBUG_T_SECT_DUMP > 1
- gDumpTSectNum = 0;
-#endif
- SkDEBUGCODE(sect1->fOppSect = sect2);
- SkDEBUGCODE(sect2->fOppSect = sect1);
- intersections->reset();
- intersections->setMax(sect1->fCurve.maxIntersections() + 4); // give extra for slop
- SkTSpan<TCurve, OppCurve>* span1 = sect1->fHead;
- SkTSpan<OppCurve, TCurve>* span2 = sect2->fHead;
- int oppSect, sect = sect1->intersects(span1, sect2, span2, &oppSect);
-// SkASSERT(between(0, sect, 2));
- if (!sect) {
- return;
- }
- if (sect == 2 && oppSect == 2) {
- (void) EndsEqual(sect1, sect2, intersections);
- return;
- }
- span1->addBounded(span2, §1->fHeap);
- span2->addBounded(span1, §2->fHeap);
- const int kMaxCoinLoopCount = 8;
- int coinLoopCount = kMaxCoinLoopCount;
- double start1s SK_INIT_TO_AVOID_WARNING;
- double start1e SK_INIT_TO_AVOID_WARNING;
- do {
- // find the largest bounds
- SkTSpan<TCurve, OppCurve>* largest1 = sect1->boundsMax();
- if (!largest1) {
- if (sect1->fHung) {
- return;
- }
- break;
- }
- SkTSpan<OppCurve, TCurve>* largest2 = sect2->boundsMax();
- // split it
- if (!largest2 || (largest1 && (largest1->fBoundsMax > largest2->fBoundsMax
- || (!largest1->fCollapsed && largest2->fCollapsed)))) {
- if (sect2->fHung) {
- return;
- }
- if (largest1->fCollapsed) {
- break;
- }
- sect1->resetRemovedEnds();
- sect2->resetRemovedEnds();
- // trim parts that don't intersect the opposite
- SkTSpan<TCurve, OppCurve>* half1 = sect1->addOne();
- SkDEBUGCODE(half1->debugSetGlobalState(sect1->globalState()));
- if (!half1->split(largest1, §1->fHeap)) {
- break;
- }
- if (!sect1->trim(largest1, sect2)) {
- SkOPOBJASSERT(intersections, 0);
- return;
- }
- if (!sect1->trim(half1, sect2)) {
- SkOPOBJASSERT(intersections, 0);
- return;
- }
- } else {
- if (largest2->fCollapsed) {
- break;
- }
- sect1->resetRemovedEnds();
- sect2->resetRemovedEnds();
- // trim parts that don't intersect the opposite
- SkTSpan<OppCurve, TCurve>* half2 = sect2->addOne();
- SkDEBUGCODE(half2->debugSetGlobalState(sect2->globalState()));
- if (!half2->split(largest2, §2->fHeap)) {
- break;
- }
- if (!sect2->trim(largest2, sect1)) {
- SkOPOBJASSERT(intersections, 0);
- return;
- }
- if (!sect2->trim(half2, sect1)) {
- SkOPOBJASSERT(intersections, 0);
- return;
- }
- }
- sect1->validate();
- sect2->validate();
-#if DEBUG_T_SECT_LOOP_COUNT
- intersections->debugBumpLoopCount(SkIntersections::kIterations_DebugLoop);
-#endif
- // if there are 9 or more continuous spans on both sects, suspect coincidence
- if (sect1->fActiveCount >= COINCIDENT_SPAN_COUNT
- && sect2->fActiveCount >= COINCIDENT_SPAN_COUNT) {
- if (coinLoopCount == kMaxCoinLoopCount) {
- start1s = sect1->fHead->fStartT;
- start1e = sect1->tail()->fEndT;
- }
- if (!sect1->coincidentCheck(sect2)) {
- return;
- }
- sect1->validate();
- sect2->validate();
-#if DEBUG_T_SECT_LOOP_COUNT
- intersections->debugBumpLoopCount(SkIntersections::kCoinCheck_DebugLoop);
-#endif
- if (!--coinLoopCount && sect1->fHead && sect2->fHead) {
- /* All known working cases resolve in two tries. Sadly, cubicConicTests[0]
- gets stuck in a loop. It adds an extension to allow a coincident end
- perpendicular to track its intersection in the opposite curve. However,
- the bounding box of the extension does not intersect the original curve,
- so the extension is discarded, only to be added again the next time around. */
- sect1->coincidentForce(sect2, start1s, start1e);
- sect1->validate();
- sect2->validate();
- }
- }
- if (sect1->fActiveCount >= COINCIDENT_SPAN_COUNT
- && sect2->fActiveCount >= COINCIDENT_SPAN_COUNT) {
- if (!sect1->fHead) {
- return;
- }
- sect1->computePerpendiculars(sect2, sect1->fHead, sect1->tail());
- if (!sect2->fHead) {
- return;
- }
- sect2->computePerpendiculars(sect1, sect2->fHead, sect2->tail());
- if (!sect1->removeByPerpendicular(sect2)) {
- return;
- }
- sect1->validate();
- sect2->validate();
-#if DEBUG_T_SECT_LOOP_COUNT
- intersections->debugBumpLoopCount(SkIntersections::kComputePerp_DebugLoop);
-#endif
- if (sect1->collapsed() > sect1->fCurve.maxIntersections()) {
- break;
- }
- }
-#if DEBUG_T_SECT_DUMP
- sect1->dumpBoth(sect2);
-#endif
- if (!sect1->fHead || !sect2->fHead) {
- break;
- }
- } while (true);
- SkTSpan<TCurve, OppCurve>* coincident = sect1->fCoincident;
- if (coincident) {
- // if there is more than one coincident span, check loosely to see if they should be joined
- if (coincident->fNext) {
- sect1->mergeCoincidence(sect2);
- coincident = sect1->fCoincident;
- }
- SkASSERT(sect2->fCoincident); // courtesy check : coincidence only looks at sect 1
- do {
- if (!coincident) {
- return;
- }
- if (!coincident->fCoinStart.isMatch()) {
- continue;
- }
- if (!coincident->fCoinEnd.isMatch()) {
- continue;
- }
- double perpT = coincident->fCoinStart.perpT();
- if (perpT < 0) {
- return;
- }
- int index = intersections->insertCoincident(coincident->fStartT,
- perpT, coincident->part()[0]);
- if ((intersections->insertCoincident(coincident->fEndT,
- coincident->fCoinEnd.perpT(),
- coincident->part()[coincident->part().pointLast()]) < 0) && index >= 0) {
- intersections->clearCoincidence(index);
- }
- } while ((coincident = coincident->fNext));
- }
- int zeroOneSet = EndsEqual(sect1, sect2, intersections);
-// if (!sect1->fHead || !sect2->fHead) {
- // if the final iteration contains an end (0 or 1),
- if (sect1->fRemovedStartT && !(zeroOneSet & kZeroS1Set)) {
- SkTCoincident<TCurve, OppCurve> perp; // intersect perpendicular with opposite curve
- perp.setPerp(sect1->fCurve, 0, sect1->fCurve[0], sect2->fCurve);
- if (perp.isMatch()) {
- intersections->insert(0, perp.perpT(), perp.perpPt());
- }
- }
- if (sect1->fRemovedEndT && !(zeroOneSet & kOneS1Set)) {
- SkTCoincident<TCurve, OppCurve> perp;
- perp.setPerp(sect1->fCurve, 1, sect1->fCurve[sect1->fCurve.pointLast()], sect2->fCurve);
- if (perp.isMatch()) {
- intersections->insert(1, perp.perpT(), perp.perpPt());
- }
- }
- if (sect2->fRemovedStartT && !(zeroOneSet & kZeroS2Set)) {
- SkTCoincident<OppCurve, TCurve> perp;
- perp.setPerp(sect2->fCurve, 0, sect2->fCurve[0], sect1->fCurve);
- if (perp.isMatch()) {
- intersections->insert(perp.perpT(), 0, perp.perpPt());
- }
- }
- if (sect2->fRemovedEndT && !(zeroOneSet & kOneS2Set)) {
- SkTCoincident<OppCurve, TCurve> perp;
- perp.setPerp(sect2->fCurve, 1, sect2->fCurve[sect2->fCurve.pointLast()], sect1->fCurve);
- if (perp.isMatch()) {
- intersections->insert(perp.perpT(), 1, perp.perpPt());
- }
- }
-// }
- if (!sect1->fHead || !sect2->fHead) {
- return;
- }
- sect1->recoverCollapsed();
- sect2->recoverCollapsed();
- SkTSpan<TCurve, OppCurve>* result1 = sect1->fHead;
- // check heads and tails for zero and ones and insert them if we haven't already done so
- const SkTSpan<TCurve, OppCurve>* head1 = result1;
- if (!(zeroOneSet & kZeroS1Set) && approximately_less_than_zero(head1->fStartT)) {
- const SkDPoint& start1 = sect1->fCurve[0];
- if (head1->isBounded()) {
- double t = head1->closestBoundedT(start1);
- if (sect2->fCurve.ptAtT(t).approximatelyEqual(start1)) {
- intersections->insert(0, t, start1);
- }
- }
- }
- const SkTSpan<OppCurve, TCurve>* head2 = sect2->fHead;
- if (!(zeroOneSet & kZeroS2Set) && approximately_less_than_zero(head2->fStartT)) {
- const SkDPoint& start2 = sect2->fCurve[0];
- if (head2->isBounded()) {
- double t = head2->closestBoundedT(start2);
- if (sect1->fCurve.ptAtT(t).approximatelyEqual(start2)) {
- intersections->insert(t, 0, start2);
- }
- }
- }
- const SkTSpan<TCurve, OppCurve>* tail1 = sect1->tail();
- if (!(zeroOneSet & kOneS1Set) && approximately_greater_than_one(tail1->fEndT)) {
- const SkDPoint& end1 = sect1->fCurve[sect1->fCurve.pointLast()];
- if (tail1->isBounded()) {
- double t = tail1->closestBoundedT(end1);
- if (sect2->fCurve.ptAtT(t).approximatelyEqual(end1)) {
- intersections->insert(1, t, end1);
- }
- }
- }
- const SkTSpan<OppCurve, TCurve>* tail2 = sect2->tail();
- if (!(zeroOneSet & kOneS2Set) && approximately_greater_than_one(tail2->fEndT)) {
- const SkDPoint& end2 = sect2->fCurve[sect2->fCurve.pointLast()];
- if (tail2->isBounded()) {
- double t = tail2->closestBoundedT(end2);
- if (sect1->fCurve.ptAtT(t).approximatelyEqual(end2)) {
- intersections->insert(t, 1, end2);
- }
- }
- }
- SkClosestSect<TCurve, OppCurve> closest;
- do {
- while (result1 && result1->fCoinStart.isMatch() && result1->fCoinEnd.isMatch()) {
- result1 = result1->fNext;
- }
- if (!result1) {
- break;
- }
- SkTSpan<OppCurve, TCurve>* result2 = sect2->fHead;
- bool found = false;
- while (result2) {
- found |= closest.find(result1, result2 SkDEBUGPARAMS(intersections));
- result2 = result2->fNext;
- }
- } while ((result1 = result1->fNext));
- closest.finish(intersections);
- // if there is more than one intersection and it isn't already coincident, check
- int last = intersections->used() - 1;
- for (int index = 0; index < last; ) {
- if (intersections->isCoincident(index) && intersections->isCoincident(index + 1)) {
- ++index;
- continue;
- }
- double midT = ((*intersections)[0][index] + (*intersections)[0][index + 1]) / 2;
- SkDPoint midPt = sect1->fCurve.ptAtT(midT);
- // intersect perpendicular with opposite curve
- SkTCoincident<TCurve, OppCurve> perp;
- perp.setPerp(sect1->fCurve, midT, midPt, sect2->fCurve);
- if (!perp.isMatch()) {
- ++index;
- continue;
- }
- if (intersections->isCoincident(index)) {
- intersections->removeOne(index);
- --last;
- } else if (intersections->isCoincident(index + 1)) {
- intersections->removeOne(index + 1);
- --last;
- } else {
- intersections->setCoincident(index++);
- }
- intersections->setCoincident(index);
- }
- SkOPOBJASSERT(intersections, intersections->used() <= sect1->fCurve.maxIntersections());
-}
-
#endif
diff --git a/src/pathops/SkPathOpsTypes.h b/src/pathops/SkPathOpsTypes.h
index 7e4be6f..2fef826 100644
--- a/src/pathops/SkPathOpsTypes.h
+++ b/src/pathops/SkPathOpsTypes.h
@@ -16,8 +16,6 @@
#include "SkSafe_math.h" // for fabs, sqrt
#include "SkScalar.h"
-#define PATH_OP_COMPILE_FOR_SIZE 1
-
enum SkPathOpsMask {
kWinding_PathOpsMask = -1,
kNo_PathOpsMask = 0,