Flutter Engine
The Flutter Engine
Loading...
Searching...
No Matches
Public Member Functions | Static Public Member Functions | Friends | List of all members
SkTSect Class Reference

#include <SkPathOpsTSect.h>

Public Member Functions

 SkTSect (const SkTCurve &c SkDEBUGPARAMS(SkOpGlobalState *) PATH_OPS_DEBUG_T_SECT_PARAMS(int id))
 
 SkDEBUGCODE (SkOpGlobalState *globalState() { return fDebugGlobalState;}) bool hasBounded(const SkTSpan *) const
 
const SkTSect * debugOpp () 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
 

Static Public Member Functions

static void BinarySearch (SkTSect *sect1, SkTSect *sect2, SkIntersections *intersections)
 

Friends

class SkTSpan
 

Detailed Description

Definition at line 249 of file SkPathOpsTSect.h.

Constructor & Destructor Documentation

◆ SkTSect()

SkTSect::SkTSect ( const SkTCurve &c   SkDEBUGPARAMSSkOpGlobalState *) PATH_OPS_DEBUG_T_SECT_PARAMS(int id)

Definition at line 513 of file SkPathOpsTSect.cpp.

516 : fCurve(c)
517 , fHeap(sizeof(SkTSpan) * 4)
518 , fCoincident(nullptr)
519 , fDeleted(nullptr)
520 , fActiveCount(0)
521 , fHung(false)
522 SkDEBUGPARAMS(fDebugGlobalState(debugGlobalState))
523 PATH_OPS_DEBUG_T_SECT_PARAMS(fID(id))
524 PATH_OPS_DEBUG_T_SECT_PARAMS(fDebugCount(0))
525 PATH_OPS_DEBUG_T_SECT_PARAMS(fDebugAllocatedCount(0))
526{
527 this->resetRemovedEnds();
528 fHead = this->addOne();
529 SkDEBUGCODE(fHead->debugSetGlobalState(debugGlobalState));
530 fHead->init(c);
531}
SkDEBUGCODE
#define SkDEBUGCODE(...)
Definition SkDebug.h:23
SkDEBUGPARAMS
#define SkDEBUGPARAMS(...)
Definition SkPathOpsDebug.h:122
PATH_OPS_DEBUG_T_SECT_PARAMS
#define PATH_OPS_DEBUG_T_SECT_PARAMS(...)
Definition SkPathOpsDebug.h:133
SkTSpan::init
void init(const SkTCurve &)
Definition SkPathOpsTSect.cpp:228

Member Function Documentation

◆ BinarySearch()

void SkTSect::BinarySearch ( SkTSect *  sect1,
SkTSect *  sect2,
SkIntersections *  intersections 
)
static

Definition at line 1791 of file SkPathOpsTSect.cpp.

1792 {
1793#if DEBUG_T_SECT_DUMP > 1
1794 gDumpTSectNum = 0;
1795#endif
1796 SkDEBUGCODE(sect1->fOppSect = sect2);
1797 SkDEBUGCODE(sect2->fOppSect = sect1);
1798 intersections->reset();
1799 intersections->setMax(sect1->fCurve.maxIntersections() + 4); // give extra for slop
1800 SkTSpan* span1 = sect1->fHead;
1801 SkTSpan* span2 = sect2->fHead;
1802 int oppSect, sect = sect1->intersects(span1, sect2, span2, &oppSect);
1803// SkASSERT(between(0, sect, 2));
1804 if (!sect) {
1805 return;
1806 }
1807 if (sect == 2 && oppSect == 2) {
1808 (void) EndsEqual(sect1, sect2, intersections);
1809 return;
1810 }
1811 span1->addBounded(span2, &sect1->fHeap);
1812 span2->addBounded(span1, &sect2->fHeap);
1813 const int kMaxCoinLoopCount = 8;
1814 int coinLoopCount = kMaxCoinLoopCount;
1815 double start1s SK_INIT_TO_AVOID_WARNING;
1816 double start1e SK_INIT_TO_AVOID_WARNING;
1817 do {
1818 // find the largest bounds
1819 SkTSpan* largest1 = sect1->boundsMax();
1820 if (!largest1) {
1821 if (sect1->fHung) {
1822 return;
1823 }
1824 break;
1825 }
1826 SkTSpan* largest2 = sect2->boundsMax();
1827 // split it
1828 if (!largest2 || (largest1 && (largest1->fBoundsMax > largest2->fBoundsMax
1829 || (!largest1->fCollapsed && largest2->fCollapsed)))) {
1830 if (sect2->fHung) {
1831 return;
1832 }
1833 if (largest1->fCollapsed) {
1834 break;
1835 }
1836 sect1->resetRemovedEnds();
1837 sect2->resetRemovedEnds();
1838 // trim parts that don't intersect the opposite
1839 SkTSpan* half1 = sect1->addOne();
1840 SkDEBUGCODE(half1->debugSetGlobalState(sect1->globalState()));
1841 if (!half1->split(largest1, &sect1->fHeap)) {
1842 break;
1843 }
1844 if (!sect1->trim(largest1, sect2)) {
1845 SkOPOBJASSERT(intersections, 0);
1846 return;
1847 }
1848 if (!sect1->trim(half1, sect2)) {
1849 SkOPOBJASSERT(intersections, 0);
1850 return;
1851 }
1852 } else {
1853 if (largest2->fCollapsed) {
1854 break;
1855 }
1856 sect1->resetRemovedEnds();
1857 sect2->resetRemovedEnds();
1858 // trim parts that don't intersect the opposite
1859 SkTSpan* half2 = sect2->addOne();
1860 SkDEBUGCODE(half2->debugSetGlobalState(sect2->globalState()));
1861 if (!half2->split(largest2, &sect2->fHeap)) {
1862 break;
1863 }
1864 if (!sect2->trim(largest2, sect1)) {
1865 SkOPOBJASSERT(intersections, 0);
1866 return;
1867 }
1868 if (!sect2->trim(half2, sect1)) {
1869 SkOPOBJASSERT(intersections, 0);
1870 return;
1871 }
1872 }
1873 sect1->validate();
1874 sect2->validate();
1875#if DEBUG_T_SECT_LOOP_COUNT
1876 intersections->debugBumpLoopCount(SkIntersections::kIterations_DebugLoop);
1877#endif
1878 // if there are 9 or more continuous spans on both sects, suspect coincidence
1879 if (sect1->fActiveCount >= COINCIDENT_SPAN_COUNT
1880 && sect2->fActiveCount >= COINCIDENT_SPAN_COUNT) {
1881 if (coinLoopCount == kMaxCoinLoopCount) {
1882 start1s = sect1->fHead->fStartT;
1883 start1e = sect1->tail()->fEndT;
1884 }
1885 if (!sect1->coincidentCheck(sect2)) {
1886 return;
1887 }
1888 sect1->validate();
1889 sect2->validate();
1890#if DEBUG_T_SECT_LOOP_COUNT
1891 intersections->debugBumpLoopCount(SkIntersections::kCoinCheck_DebugLoop);
1892#endif
1893 if (!--coinLoopCount && sect1->fHead && sect2->fHead) {
1894 /* All known working cases resolve in two tries. Sadly, cubicConicTests[0]
1895 gets stuck in a loop. It adds an extension to allow a coincident end
1896 perpendicular to track its intersection in the opposite curve. However,
1897 the bounding box of the extension does not intersect the original curve,
1898 so the extension is discarded, only to be added again the next time around. */
1899 sect1->coincidentForce(sect2, start1s, start1e);
1900 sect1->validate();
1901 sect2->validate();
1902 }
1903 }
1904 if (sect1->fActiveCount >= COINCIDENT_SPAN_COUNT
1905 && sect2->fActiveCount >= COINCIDENT_SPAN_COUNT) {
1906 if (!sect1->fHead) {
1907 return;
1908 }
1909 sect1->computePerpendiculars(sect2, sect1->fHead, sect1->tail());
1910 if (!sect2->fHead) {
1911 return;
1912 }
1913 sect2->computePerpendiculars(sect1, sect2->fHead, sect2->tail());
1914 if (!sect1->removeByPerpendicular(sect2)) {
1915 return;
1916 }
1917 sect1->validate();
1918 sect2->validate();
1919#if DEBUG_T_SECT_LOOP_COUNT
1920 intersections->debugBumpLoopCount(SkIntersections::kComputePerp_DebugLoop);
1921#endif
1922 if (sect1->collapsed() > sect1->fCurve.maxIntersections()) {
1923 break;
1924 }
1925 }
1926#if DEBUG_T_SECT_DUMP
1927 sect1->dumpBoth(sect2);
1928#endif
1929 if (!sect1->fHead || !sect2->fHead) {
1930 break;
1931 }
1932 } while (true);
1933 SkTSpan* coincident = sect1->fCoincident;
1934 if (coincident) {
1935 // if there is more than one coincident span, check loosely to see if they should be joined
1936 if (coincident->fNext) {
1937 sect1->mergeCoincidence(sect2);
1938 coincident = sect1->fCoincident;
1939 }
1940 SkASSERT(sect2->fCoincident); // courtesy check : coincidence only looks at sect 1
1941 do {
1942 if (!coincident) {
1943 return;
1944 }
1945 if (!coincident->fCoinStart.isMatch()) {
1946 continue;
1947 }
1948 if (!coincident->fCoinEnd.isMatch()) {
1949 continue;
1950 }
1951 double perpT = coincident->fCoinStart.perpT();
1952 if (perpT < 0) {
1953 return;
1954 }
1955 int index = intersections->insertCoincident(coincident->fStartT,
1956 perpT, coincident->pointFirst());
1957 if ((intersections->insertCoincident(coincident->fEndT,
1958 coincident->fCoinEnd.perpT(),
1959 coincident->pointLast()) < 0) && index >= 0) {
1960 intersections->clearCoincidence(index);
1961 }
1962 } while ((coincident = coincident->fNext));
1963 }
1964 int zeroOneSet = EndsEqual(sect1, sect2, intersections);
1965// if (!sect1->fHead || !sect2->fHead) {
1966 // if the final iteration contains an end (0 or 1),
1967 if (sect1->fRemovedStartT && !(zeroOneSet & kZeroS1Set)) {
1968 SkTCoincident perp; // intersect perpendicular with opposite curve
1969 perp.setPerp(sect1->fCurve, 0, sect1->fCurve[0], sect2->fCurve);
1970 if (perp.isMatch()) {
1971 intersections->insert(0, perp.perpT(), perp.perpPt());
1972 }
1973 }
1974 if (sect1->fRemovedEndT && !(zeroOneSet & kOneS1Set)) {
1975 SkTCoincident perp;
1976 perp.setPerp(sect1->fCurve, 1, sect1->pointLast(), sect2->fCurve);
1977 if (perp.isMatch()) {
1978 intersections->insert(1, perp.perpT(), perp.perpPt());
1979 }
1980 }
1981 if (sect2->fRemovedStartT && !(zeroOneSet & kZeroS2Set)) {
1982 SkTCoincident perp;
1983 perp.setPerp(sect2->fCurve, 0, sect2->fCurve[0], sect1->fCurve);
1984 if (perp.isMatch()) {
1985 intersections->insert(perp.perpT(), 0, perp.perpPt());
1986 }
1987 }
1988 if (sect2->fRemovedEndT && !(zeroOneSet & kOneS2Set)) {
1989 SkTCoincident perp;
1990 perp.setPerp(sect2->fCurve, 1, sect2->pointLast(), sect1->fCurve);
1991 if (perp.isMatch()) {
1992 intersections->insert(perp.perpT(), 1, perp.perpPt());
1993 }
1994 }
1995// }
1996 if (!sect1->fHead || !sect2->fHead) {
1997 return;
1998 }
1999 sect1->recoverCollapsed();
2000 sect2->recoverCollapsed();
2001 SkTSpan* result1 = sect1->fHead;
2002 // check heads and tails for zero and ones and insert them if we haven't already done so
2003 const SkTSpan* head1 = result1;
2004 if (!(zeroOneSet & kZeroS1Set) && approximately_less_than_zero(head1->fStartT)) {
2005 const SkDPoint& start1 = sect1->fCurve[0];
2006 if (head1->isBounded()) {
2007 double t = head1->closestBoundedT(start1);
2008 if (sect2->fCurve.ptAtT(t).approximatelyEqual(start1)) {
2009 intersections->insert(0, t, start1);
2010 }
2011 }
2012 }
2013 const SkTSpan* head2 = sect2->fHead;
2014 if (!(zeroOneSet & kZeroS2Set) && approximately_less_than_zero(head2->fStartT)) {
2015 const SkDPoint& start2 = sect2->fCurve[0];
2016 if (head2->isBounded()) {
2017 double t = head2->closestBoundedT(start2);
2018 if (sect1->fCurve.ptAtT(t).approximatelyEqual(start2)) {
2019 intersections->insert(t, 0, start2);
2020 }
2021 }
2022 }
2023 if (!(zeroOneSet & kOneS1Set)) {
2024 const SkTSpan* tail1 = sect1->tail();
2025 if (!tail1) {
2026 return;
2027 }
2028 if (approximately_greater_than_one(tail1->fEndT)) {
2029 const SkDPoint& end1 = sect1->pointLast();
2030 if (tail1->isBounded()) {
2031 double t = tail1->closestBoundedT(end1);
2032 if (sect2->fCurve.ptAtT(t).approximatelyEqual(end1)) {
2033 intersections->insert(1, t, end1);
2034 }
2035 }
2036 }
2037 }
2038 if (!(zeroOneSet & kOneS2Set)) {
2039 const SkTSpan* tail2 = sect2->tail();
2040 if (!tail2) {
2041 return;
2042 }
2043 if (approximately_greater_than_one(tail2->fEndT)) {
2044 const SkDPoint& end2 = sect2->pointLast();
2045 if (tail2->isBounded()) {
2046 double t = tail2->closestBoundedT(end2);
2047 if (sect1->fCurve.ptAtT(t).approximatelyEqual(end2)) {
2048 intersections->insert(t, 1, end2);
2049 }
2050 }
2051 }
2052 }
2053 SkClosestSect closest;
2054 do {
2055 while (result1 && result1->fCoinStart.isMatch() && result1->fCoinEnd.isMatch()) {
2056 result1 = result1->fNext;
2057 }
2058 if (!result1) {
2059 break;
2060 }
2061 SkTSpan* result2 = sect2->fHead;
2062 while (result2) {
2063 closest.find(result1, result2 SkDEBUGPARAMS(intersections));
2064 result2 = result2->fNext;
2065 }
2066 } while ((result1 = result1->fNext));
2067 closest.finish(intersections);
2068 // if there is more than one intersection and it isn't already coincident, check
2069 int last = intersections->used() - 1;
2070 for (int index = 0; index < last; ) {
2071 if (intersections->isCoincident(index) && intersections->isCoincident(index + 1)) {
2072 ++index;
2073 continue;
2074 }
2075 double midT = ((*intersections)[0][index] + (*intersections)[0][index + 1]) / 2;
2076 SkDPoint midPt = sect1->fCurve.ptAtT(midT);
2077 // intersect perpendicular with opposite curve
2078 SkTCoincident perp;
2079 perp.setPerp(sect1->fCurve, midT, midPt, sect2->fCurve);
2080 if (!perp.isMatch()) {
2081 ++index;
2082 continue;
2083 }
2084 if (intersections->isCoincident(index)) {
2085 intersections->removeOne(index);
2086 --last;
2087 } else if (intersections->isCoincident(index + 1)) {
2088 intersections->removeOne(index + 1);
2089 --last;
2090 } else {
2091 intersections->setCoincident(index++);
2092 }
2093 intersections->setCoincident(index);
2094 }
2095 SkOPOBJASSERT(intersections, intersections->used() <= sect1->fCurve.maxIntersections());
2096}
coincident
static bool coincident(const SkPoint &a, const SkPoint &b)
Definition GrTriangulator.cpp:464
gDumpTSectNum
int gDumpTSectNum
SkASSERT
#define SkASSERT(cond)
Definition SkAssert.h:116
SK_INIT_TO_AVOID_WARNING
#define SK_INIT_TO_AVOID_WARNING
Definition SkMacros.h:58
COINCIDENT_SPAN_COUNT
#define COINCIDENT_SPAN_COUNT
Definition SkPathOpsTSect.cpp:26
approximately_less_than_zero
bool approximately_less_than_zero(double x)
Definition SkPathOpsTypes.h:469
approximately_greater_than_one
bool approximately_greater_than_one(double x)
Definition SkPathOpsTypes.h:461
SkOPOBJASSERT
#define SkOPOBJASSERT(obj, cond)
Definition SkPathOpsTypes.h:229
SkIntersections::insert
int insert(double one, double two, const SkDPoint &pt)
Definition SkIntersections.cpp:36
SkIntersections::removeOne
void removeOne(int index)
Definition SkIntersections.cpp:162
SkIntersections::insertCoincident
int insertCoincident(double one, double two, const SkDPoint &pt)
Definition SkIntersections.cpp:118
SkIntersections::debugBumpLoopCount
void debugBumpLoopCount(DebugLoop)
SkIntersections::setCoincident
void setCoincident(int index)
Definition SkIntersections.cpp:126
SkIntersections::isCoincident
bool isCoincident(int index)
Definition SkIntersections.h:141
SkIntersections::clearCoincidence
void clearCoincidence(int index)
Definition SkIntersections.h:63
SkIntersections::setMax
void setMax(int max)
Definition SkIntersections.h:215
SkTCoincident::perpT
double perpT() const
Definition SkPathOpsTSect.h:76
SkTCoincident::isMatch
bool isMatch() const
Definition SkPathOpsTSect.h:54
SkTCoincident::perpPt
const SkDPoint & perpPt() const
Definition SkPathOpsTSect.h:72
SkTCoincident::setPerp
void setPerp(const SkTCurve &c1, double t, const SkDPoint &cPt, const SkTCurve &)
Definition SkPathOpsTSect.cpp:28
SkTCurve::ptAtT
virtual SkDPoint ptAtT(double t) const =0
SkTCurve::maxIntersections
virtual int maxIntersections() const =0
SkTSect::dumpBoth
void dumpBoth(SkTSect *) const
Definition PathOpsDebug.cpp:1233
SkTSpan::addBounded
void addBounded(SkTSpan *, SkArenaAlloc *)
Definition SkPathOpsTSect.cpp:63
SkTSpan::isBounded
bool isBounded() const
Definition SkPathOpsTSect.h:153
SkTSpan::split
bool split(SkTSpan *work, SkArenaAlloc *heap)
Definition SkPathOpsTSect.h:200
SkTSpan::closestBoundedT
double closestBoundedT(const SkDPoint &pt) const
Definition SkPathOpsTSect.cpp:118
skvx::half2
Vec< 2, uint16_t > half2
Definition SkVx.h:1175
SkClosestSect::find
bool find(const SkTSpan *span1, const SkTSpan *span2 SkDEBUGPARAMS(SkIntersections *i))
Definition SkPathOpsTSect.cpp:1745
SkClosestSect::finish
void finish(SkIntersections *intersections) const
Definition SkPathOpsTSect.cpp:1771
SkDPoint::approximatelyEqual
bool approximatelyEqual(const SkDPoint &a) const
Definition SkPathOpsPoint.h:177

◆ debugOpp()

const SkTSect * SkTSect::debugOpp ( ) const
inline

Definition at line 259 of file SkPathOpsTSect.h.

259 {
260 return SkDEBUGRELEASE(fOppSect, nullptr);
261 }
SkDEBUGRELEASE
#define SkDEBUGRELEASE(a, b)
Definition SkPathOpsDebug.h:121

◆ dump()

void SkTSect::dump ( ) const

Definition at line 1227 of file PathOpsDebug.cpp.

1227 {
1228 dumpCommon(fHead);
1229}

◆ dumpBoth()

void SkTSect::dumpBoth ( SkTSect *  opp) const

Definition at line 1233 of file PathOpsDebug.cpp.

1233 {
1234#if DEBUG_T_SECT_DUMP <= 2
1235#if DEBUG_T_SECT_DUMP == 2
1236 SkDebugf("%d ", ++gDumpTSectNum);
1237#endif
1238 this->dump();
1239 SkDebugf("\n");
1240 opp->dump();
1241 SkDebugf("\n");
1242#elif DEBUG_T_SECT_DUMP == 3
1243 SkDebugf("<div id=\"sect%d\">\n", ++gDumpTSectNum);
1244 if (this->fHead) {
1245 this->dumpCurves();
1246 }
1247 if (opp->fHead) {
1248 opp->dumpCurves();
1249 }
1250 SkDebugf("</div>\n\n");
1251#endif
1252}
SkDebugf
void SK_SPI SkDebugf(const char format[],...) SK_PRINTF_LIKE(1
SkTSect::dump
void dump() const
Definition PathOpsDebug.cpp:1227
SkTSect::dumpCurves
void dumpCurves() const
Definition PathOpsDebug.cpp:1307

◆ dumpBounded()

void SkTSect::dumpBounded ( int  id) const

Definition at line 1254 of file PathOpsDebug.cpp.

1254 {
1255#ifdef SK_DEBUG
1256 const SkTSpan* bounded = debugSpan(id);
1257 if (!bounded) {
1258 SkDebugf("no span matches %d\n", id);
1259 return;
1260 }
1261 const SkTSpan* test = bounded->debugOpp()->fHead;
1262 do {
1263 if (test->findOppSpan(bounded)) {
1264 test->dump();
1265 SkDebugf(" ");
1266 }
1267 } while ((test = test->next()));
1268 SkDebugf("\n");
1269#endif
1270}
SkTSpan::debugOpp
const SkTSect * debugOpp() const
Definition SkPathOpsTSect.cpp:163

◆ dumpBounds()

void SkTSect::dumpBounds ( ) const

Definition at line 1272 of file PathOpsDebug.cpp.

1272 {
1273 const SkTSpan* test = fHead;
1274 do {
1275 test->dumpBounds();
1276 } while ((test = test->next()));
1277}

◆ dumpCoin()

void SkTSect::dumpCoin ( ) const

Definition at line 1279 of file PathOpsDebug.cpp.

1279 {
1280 dumpCommon(fCoincident);
1281}

◆ dumpCoinCurves()

void SkTSect::dumpCoinCurves ( ) const

Definition at line 1283 of file PathOpsDebug.cpp.

1283 {
1284 dumpCommonCurves(fCoincident);
1285}

◆ dumpCurves()

void SkTSect::dumpCurves ( ) const

Definition at line 1307 of file PathOpsDebug.cpp.

1307 {
1308 dumpCommonCurves(fHead);
1309}

◆ SkDEBUGCODE()

SkTSect::SkDEBUGCODE ( SkOpGlobalState *globalState() { return fDebugGlobalState;}  ) const

Friends And Related Symbol Documentation

◆ SkTSpan

friend class SkTSpan
friend

Definition at line 375 of file SkPathOpsTSect.h.

The documentation for this class was generated from the following files:
Generated on Fri Apr 26 2024 06:20:24 for Flutter Engine by doxygen 1.9.8