| /* |
| * Copyright 2012 Google Inc. |
| * |
| * Use of this source code is governed by a BSD-style license that can be |
| * found in the LICENSE file. |
| */ |
| #ifndef SkIntersections_DEFINE |
| #define SkIntersections_DEFINE |
| |
| #include "include/core/SkPoint.h" |
| #include "include/core/SkScalar.h" |
| #include "include/core/SkTypes.h" |
| #include "include/private/base/SkDebug.h" |
| #include "include/private/base/SkMalloc.h" |
| #include "src/pathops/SkPathOpsConic.h" |
| #include "src/pathops/SkPathOpsCubic.h" |
| #include "src/pathops/SkPathOpsDebug.h" |
| #include "src/pathops/SkPathOpsLine.h" |
| #include "src/pathops/SkPathOpsPoint.h" |
| #include "src/pathops/SkPathOpsQuad.h" |
| #include "src/pathops/SkPathOpsTCurve.h" |
| #include "src/pathops/SkPathOpsTypes.h" |
| |
| #include <array> |
| #include <cstdint> |
| |
| struct SkDRect; |
| |
| class SkIntersections { |
| public: |
| SkIntersections(SkDEBUGCODE(SkOpGlobalState* globalState = nullptr)) |
| : fSwap(0) |
| #ifdef SK_DEBUG |
| SkDEBUGPARAMS(fDebugGlobalState(globalState)) |
| , fDepth(0) |
| #endif |
| { |
| sk_bzero(fPt, sizeof(fPt)); |
| sk_bzero(fPt2, sizeof(fPt2)); |
| sk_bzero(fT, sizeof(fT)); |
| sk_bzero(fNearlySame, sizeof(fNearlySame)); |
| #if DEBUG_T_SECT_LOOP_COUNT |
| sk_bzero(fDebugLoopCount, sizeof(fDebugLoopCount)); |
| #endif |
| reset(); |
| fMax = 0; // require that the caller set the max |
| } |
| |
| class TArray { |
| public: |
| explicit TArray(const double ts[10]) : fTArray(ts) {} |
| double operator[](int n) const { |
| return fTArray[n]; |
| } |
| const double* fTArray; |
| }; |
| TArray operator[](int n) const { return TArray(fT[n]); } |
| |
| void allowNear(bool nearAllowed) { |
| fAllowNear = nearAllowed; |
| } |
| |
| void clearCoincidence(int index) { |
| SkASSERT(index >= 0); |
| int bit = 1 << index; |
| fIsCoincident[0] &= ~bit; |
| fIsCoincident[1] &= ~bit; |
| } |
| |
| int conicHorizontal(const SkPoint a[3], SkScalar weight, SkScalar left, SkScalar right, |
| SkScalar y, bool flipped) { |
| SkDConic conic; |
| conic.set(a, weight); |
| fMax = 2; |
| return horizontal(conic, left, right, y, flipped); |
| } |
| |
| int conicVertical(const SkPoint a[3], SkScalar weight, SkScalar top, SkScalar bottom, |
| SkScalar x, bool flipped) { |
| SkDConic conic; |
| conic.set(a, weight); |
| fMax = 2; |
| return vertical(conic, top, bottom, x, flipped); |
| } |
| |
| int conicLine(const SkPoint a[3], SkScalar weight, const SkPoint b[2]) { |
| SkDConic conic; |
| conic.set(a, weight); |
| SkDLine line; |
| line.set(b); |
| fMax = 3; // 2; permit small coincident segment + non-coincident intersection |
| return intersect(conic, line); |
| } |
| |
| int cubicHorizontal(const SkPoint a[4], SkScalar left, SkScalar right, SkScalar y, |
| bool flipped) { |
| SkDCubic cubic; |
| cubic.set(a); |
| fMax = 3; |
| return horizontal(cubic, left, right, y, flipped); |
| } |
| |
| int cubicVertical(const SkPoint a[4], SkScalar top, SkScalar bottom, SkScalar x, bool flipped) { |
| SkDCubic cubic; |
| cubic.set(a); |
| fMax = 3; |
| return vertical(cubic, top, bottom, x, flipped); |
| } |
| |
| int cubicLine(const SkPoint a[4], const SkPoint b[2]) { |
| SkDCubic cubic; |
| cubic.set(a); |
| SkDLine line; |
| line.set(b); |
| fMax = 3; |
| return intersect(cubic, line); |
| } |
| |
| #ifdef SK_DEBUG |
| SkOpGlobalState* globalState() const { return fDebugGlobalState; } |
| #endif |
| |
| bool hasT(double t) const { |
| SkASSERT(t == 0 || t == 1); |
| return fUsed > 0 && (t == 0 ? fT[0][0] == 0 : fT[0][fUsed - 1] == 1); |
| } |
| |
| bool hasOppT(double t) const { |
| SkASSERT(t == 0 || t == 1); |
| return fUsed > 0 && (fT[1][0] == t || fT[1][fUsed - 1] == t); |
| } |
| |
| int insertSwap(double one, double two, const SkDPoint& pt) { |
| if (fSwap) { |
| return insert(two, one, pt); |
| } else { |
| return insert(one, two, pt); |
| } |
| } |
| |
| bool isCoincident(int index) { |
| return (fIsCoincident[0] & 1 << index) != 0; |
| } |
| |
| int lineHorizontal(const SkPoint a[2], SkScalar left, SkScalar right, SkScalar y, |
| bool flipped) { |
| SkDLine line; |
| line.set(a); |
| fMax = 2; |
| return horizontal(line, left, right, y, flipped); |
| } |
| |
| int lineVertical(const SkPoint a[2], SkScalar top, SkScalar bottom, SkScalar x, bool flipped) { |
| SkDLine line; |
| line.set(a); |
| fMax = 2; |
| return vertical(line, top, bottom, x, flipped); |
| } |
| |
| int lineLine(const SkPoint a[2], const SkPoint b[2]) { |
| SkDLine aLine, bLine; |
| aLine.set(a); |
| bLine.set(b); |
| fMax = 2; |
| return intersect(aLine, bLine); |
| } |
| |
| bool nearlySame(int index) const { |
| SkASSERT(index == 0 || index == 1); |
| return fNearlySame[index]; |
| } |
| |
| const SkDPoint& pt(int index) const { |
| return fPt[index]; |
| } |
| |
| const SkDPoint& pt2(int index) const { |
| return fPt2[index]; |
| } |
| |
| int quadHorizontal(const SkPoint a[3], SkScalar left, SkScalar right, SkScalar y, |
| bool flipped) { |
| SkDQuad quad; |
| quad.set(a); |
| fMax = 2; |
| return horizontal(quad, left, right, y, flipped); |
| } |
| |
| int quadVertical(const SkPoint a[3], SkScalar top, SkScalar bottom, SkScalar x, bool flipped) { |
| SkDQuad quad; |
| quad.set(a); |
| fMax = 2; |
| return vertical(quad, top, bottom, x, flipped); |
| } |
| |
| int quadLine(const SkPoint a[3], const SkPoint b[2]) { |
| SkDQuad quad; |
| quad.set(a); |
| SkDLine line; |
| line.set(b); |
| return intersect(quad, line); |
| } |
| |
| // leaves swap, max alone |
| void reset() { |
| fAllowNear = true; |
| fUsed = 0; |
| sk_bzero(fIsCoincident, sizeof(fIsCoincident)); |
| } |
| |
| void set(bool swap, int tIndex, double t) { |
| fT[(int) swap][tIndex] = t; |
| } |
| |
| void setMax(int max) { |
| SkASSERT(max <= (int) std::size(fPt)); |
| fMax = max; |
| } |
| |
| void swap() { |
| fSwap ^= true; |
| } |
| |
| bool swapped() const { |
| return fSwap; |
| } |
| |
| int used() const { |
| return fUsed; |
| } |
| |
| void downDepth() { |
| SkASSERT(--fDepth >= 0); |
| } |
| |
| bool unBumpT(int index) { |
| SkASSERT(fUsed == 1); |
| fT[0][index] = fT[0][index] * (1 + BUMP_EPSILON * 2) - BUMP_EPSILON; |
| if (!between(0, fT[0][index], 1)) { |
| fUsed = 0; |
| return false; |
| } |
| return true; |
| } |
| |
| void upDepth() { |
| SkASSERT(++fDepth < 16); |
| } |
| |
| void alignQuadPts(const SkPoint a[3], const SkPoint b[3]); |
| int cleanUpCoincidence(); |
| int closestTo(double rangeStart, double rangeEnd, const SkDPoint& testPt, double* dist) const; |
| void cubicInsert(double one, double two, const SkDPoint& pt, const SkDCubic& c1, |
| const SkDCubic& c2); |
| void flip(); |
| int horizontal(const SkDLine&, double left, double right, double y, bool flipped); |
| int horizontal(const SkDQuad&, double left, double right, double y, bool flipped); |
| int horizontal(const SkDQuad&, double left, double right, double y, double tRange[2]); |
| int horizontal(const SkDCubic&, double y, double tRange[3]); |
| int horizontal(const SkDConic&, double left, double right, double y, bool flipped); |
| int horizontal(const SkDCubic&, double left, double right, double y, bool flipped); |
| int horizontal(const SkDCubic&, double left, double right, double y, double tRange[3]); |
| static double HorizontalIntercept(const SkDLine& line, double y); |
| static int HorizontalIntercept(const SkDQuad& quad, SkScalar y, double* roots); |
| static int HorizontalIntercept(const SkDConic& conic, SkScalar y, double* roots); |
| // FIXME : does not respect swap |
| int insert(double one, double two, const SkDPoint& pt); |
| void insertNear(double one, double two, const SkDPoint& pt1, const SkDPoint& pt2); |
| // start if index == 0 : end if index == 1 |
| int insertCoincident(double one, double two, const SkDPoint& pt); |
| int intersect(const SkDLine&, const SkDLine&); |
| int intersect(const SkDQuad&, const SkDLine&); |
| int intersect(const SkDQuad&, const SkDQuad&); |
| int intersect(const SkDConic&, const SkDLine&); |
| int intersect(const SkDConic&, const SkDQuad&); |
| int intersect(const SkDConic&, const SkDConic&); |
| int intersect(const SkDCubic&, const SkDLine&); |
| int intersect(const SkDCubic&, const SkDQuad&); |
| int intersect(const SkDCubic&, const SkDConic&); |
| int intersect(const SkDCubic&, const SkDCubic&); |
| int intersectRay(const SkDLine&, const SkDLine&); |
| int intersectRay(const SkDQuad&, const SkDLine&); |
| int intersectRay(const SkDConic&, const SkDLine&); |
| int intersectRay(const SkDCubic&, const SkDLine&); |
| int intersectRay(const SkTCurve& tCurve, const SkDLine& line) { |
| return tCurve.intersectRay(this, line); |
| } |
| |
| void merge(const SkIntersections& , int , const SkIntersections& , int ); |
| int mostOutside(double rangeStart, double rangeEnd, const SkDPoint& origin) const; |
| void removeOne(int index); |
| void setCoincident(int index); |
| int vertical(const SkDLine&, double top, double bottom, double x, bool flipped); |
| int vertical(const SkDQuad&, double top, double bottom, double x, bool flipped); |
| int vertical(const SkDConic&, double top, double bottom, double x, bool flipped); |
| int vertical(const SkDCubic&, double top, double bottom, double x, bool flipped); |
| static double VerticalIntercept(const SkDLine& line, double x); |
| static int VerticalIntercept(const SkDQuad& quad, SkScalar x, double* roots); |
| static int VerticalIntercept(const SkDConic& conic, SkScalar x, double* roots); |
| |
| int depth() const { |
| #ifdef SK_DEBUG |
| return fDepth; |
| #else |
| return 0; |
| #endif |
| } |
| |
| enum DebugLoop { |
| kIterations_DebugLoop, |
| kCoinCheck_DebugLoop, |
| kComputePerp_DebugLoop, |
| }; |
| |
| void debugBumpLoopCount(DebugLoop ); |
| int debugCoincidentUsed() const; |
| int debugLoopCount(DebugLoop ) const; |
| void debugResetLoopCount(); |
| void dump() const; // implemented for testing only |
| |
| private: |
| bool cubicCheckCoincidence(const SkDCubic& c1, const SkDCubic& c2); |
| bool cubicExactEnd(const SkDCubic& cubic1, bool start, const SkDCubic& cubic2); |
| void cubicNearEnd(const SkDCubic& cubic1, bool start, const SkDCubic& cubic2, const SkDRect& ); |
| void cleanUpParallelLines(bool parallel); |
| void computePoints(const SkDLine& line, int used); |
| |
| SkDPoint fPt[13]; // FIXME: since scans store points as SkPoint, this should also |
| SkDPoint fPt2[2]; // used by nearly same to store alternate intersection point |
| double fT[2][13]; |
| uint16_t fIsCoincident[2]; // bit set for each curve's coincident T |
| bool fNearlySame[2]; // true if end points nearly match |
| unsigned char fUsed; |
| unsigned char fMax; |
| bool fAllowNear; |
| bool fSwap; |
| #ifdef SK_DEBUG |
| SkOpGlobalState* fDebugGlobalState; |
| int fDepth; |
| #endif |
| #if DEBUG_T_SECT_LOOP_COUNT |
| int fDebugLoopCount[3]; |
| #endif |
| }; |
| |
| #endif |