blob: 4d84e3db6710e4da549c7a9ac913eb7913de1199 [file] [log] [blame]
* Copyright 2014 Google Inc.
* Use of this source code is governed by a BSD-style license that can be
* found in the LICENSE file.
#ifndef SkPathOpsTSect_DEFINED
#define SkPathOpsTSect_DEFINED
#include "include/private/SkMacros.h"
#include "src/core/SkArenaAlloc.h"
#include "src/pathops/SkIntersections.h"
#include "src/pathops/SkPathOpsBounds.h"
#include "src/pathops/SkPathOpsRect.h"
#include "src/pathops/SkPathOpsTCurve.h"
#include <utility>
#ifdef SK_DEBUG
typedef uint8_t SkOpDebugBool;
typedef bool SkOpDebugBool;
static inline bool SkDoubleIsNaN(double x) {
return x != x;
class SkTCoincident {
SkTCoincident() {
void debugInit() {
#ifdef SK_DEBUG
this->fPerpPt.fX = this->fPerpPt.fY = SK_ScalarNaN;
this->fPerpT = SK_ScalarNaN;
this->fMatch = 0xFF;
char dumpIsCoincidentStr() const;
void dump() const;
bool isMatch() const {
SkASSERT(!!fMatch == fMatch);
return SkToBool(fMatch);
void init() {
fPerpT = -1;
fMatch = false;
fPerpPt.fX = fPerpPt.fY = SK_ScalarNaN;
void markCoincident() {
if (!fMatch) {
fPerpT = -1;
fMatch = true;
const SkDPoint& perpPt() const {
return fPerpPt;
double perpT() const {
return fPerpT;
void setPerp(const SkTCurve& c1, double t, const SkDPoint& cPt, const SkTCurve& );
SkDPoint fPerpPt;
double fPerpT; // perpendicular intersection on opposite curve
SkOpDebugBool fMatch;
class SkTSect;
class SkTSpan;
struct SkTSpanBounded {
SkTSpan* fBounded;
SkTSpanBounded* fNext;
class SkTSpan {
SkTSpan(const SkTCurve& curve, SkArenaAlloc& heap) {
fPart = curve.make(heap);
void addBounded(SkTSpan* , SkArenaAlloc* );
double closestBoundedT(const SkDPoint& pt) const;
bool contains(double t) const;
void debugInit(const SkTCurve& curve, SkArenaAlloc& heap) {
#ifdef SK_DEBUG
SkTCurve* fake = curve.make(heap);
const SkTSect* debugOpp() const;
#ifdef SK_DEBUG
void debugSetGlobalState(SkOpGlobalState* state) {
fDebugGlobalState = state;
const SkTSpan* debugSpan(int ) const;
const SkTSpan* debugT(double t) const;
bool debugIsBefore(const SkTSpan* span) const;
void dump() const;
void dumpAll() const;
void dumpBounded(int id) const;
void dumpBounds() const;
void dumpCoin() const;
double endT() const {
return fEndT;
SkTSpan* findOppSpan(const SkTSpan* opp) const;
SkTSpan* findOppT(double t) const {
SkTSpan* result = oppT(t);
return result;
SkDEBUGCODE(SkOpGlobalState* globalState() const { return fDebugGlobalState; })
bool hasOppT(double t) const {
return SkToBool(oppT(t));
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* span);
double linearT(const SkDPoint& ) const;
void markCoincident() {
const SkTSpan* next() const {
return fNext;
bool onlyEndPointsInCommon(const SkTSpan* opp, bool* start,
bool* oppStart, bool* ptsInCommon);
const SkTCurve& part() const {
return *fPart;
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* opp);
void reset() {
fBounded = nullptr;
void resetBounds(const SkTCurve& curve) {
fIsLinear = fIsLine = false;
bool split(SkTSpan* work, SkArenaAlloc* heap) {
return splitAt(work, (work->fStartT + work->fEndT) * 0.5, heap);
bool splitAt(SkTSpan* work, double t, SkArenaAlloc* heap);
double startT() const {
return fStartT;
// implementation is for testing only
int debugID() const {
void dumpID() 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;
SkTCurve* fPart;
SkTCoincident fCoinStart;
SkTCoincident fCoinEnd;
SkTSpanBounded* fBounded;
SkTSpan* fPrev;
SkTSpan* fNext;
SkDRect fBounds;
double fStartT;
double fEndT;
double fBoundsMax;
SkOpDebugBool fCollapsed;
SkOpDebugBool fHasPerp;
SkOpDebugBool fIsLinear;
SkOpDebugBool fIsLine;
SkOpDebugBool fDeleted;
SkDEBUGCODE(SkOpGlobalState* fDebugGlobalState);
SkDEBUGCODE(SkTSect* fDebugSect);
friend class SkTSect;
class SkTSect {
SkTSect(const SkTCurve& c
static void BinarySearch(SkTSect* sect1, SkTSect* sect2,
SkIntersections* intersections);
SkDEBUGCODE(SkOpGlobalState* globalState() { return fDebugGlobalState; })
bool hasBounded(const SkTSpan* ) const;
const SkTSect* debugOpp() const {
return SkDEBUGRELEASE(fOppSect, nullptr);
#ifdef SK_DEBUG
const SkTSpan* debugSpan(int id) const;
const SkTSpan* debugT(double t) const;
void dump() const;
void dumpBoth(SkTSect* ) const;
void dumpBounded(int id) const;
void dumpBounds() const;
void dumpCoin() const;
void dumpCoinCurves() const;
void dumpCurves() const;
enum {
kZeroS1Set = 1,
kOneS1Set = 2,
kZeroS2Set = 4,
kOneS2Set = 8
SkTSpan* addFollowing(SkTSpan* prior);
void addForPerp(SkTSpan* span, double t);
SkTSpan* addOne();
SkTSpan* addSplitAt(SkTSpan* span, double t) {
SkTSpan* result = this->addOne();
result->splitAt(span, t, &fHeap);
return result;
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* sect2, SkTSpan* first,
SkTSpan* last);
int countConsecutiveSpans(SkTSpan* first,
SkTSpan** last) const;
int debugID() const {
bool deleteEmptySpans();
void dumpCommon(const SkTSpan* ) const;
void dumpCommonCurves(const SkTSpan* ) const;
static int EndsEqual(const SkTSect* sect1, const SkTSect* sect2,
SkIntersections* );
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* sect2);
const SkDPoint& pointLast() const {
return fCurve[fCurve.pointLast()];
SkTSpan* prev(SkTSpan* ) const;
bool removeByPerpendicular(SkTSect* opp);
void recoverCollapsed();
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* 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 SkTCurve& fCurve;
SkSTArenaAlloc<1024> fHeap;
SkTSpan* fHead;
SkTSpan* fCoincident;
SkTSpan* fDeleted;
int fActiveCount;
bool fRemovedStartT;
bool fRemovedEndT;
bool fHung;
SkDEBUGCODE(SkOpGlobalState* fDebugGlobalState);
SkDEBUGCODE(SkTSect* fOppSect);
int fDebugAllocatedCount;
friend class SkTSpan;