| OLD | NEW |
| 1 /* | 1 /* |
| 2 * Copyright 2014 Google Inc. | 2 * Copyright 2014 Google Inc. |
| 3 * | 3 * |
| 4 * Use of this source code is governed by a BSD-style license that can be | 4 * Use of this source code is governed by a BSD-style license that can be |
| 5 * found in the LICENSE file. | 5 * found in the LICENSE file. |
| 6 */ | 6 */ |
| 7 #ifndef SkPathOpsTSect_DEFINED | 7 #ifndef SkPathOpsTSect_DEFINED |
| 8 #define SkPathOpsTSect_DEFINED | 8 #define SkPathOpsTSect_DEFINED |
| 9 | 9 |
| 10 #include "SkChunkAlloc.h" | 10 #include "SkChunkAlloc.h" |
| (...skipping 864 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 875 | 875 |
| 876 template<typename TCurve, typename OppCurve> | 876 template<typename TCurve, typename OppCurve> |
| 877 bool SkTSect<TCurve, OppCurve>::binarySearchCoin(SkTSect<OppCurve, TCurve>* sect
2, double tStart, | 877 bool SkTSect<TCurve, OppCurve>::binarySearchCoin(SkTSect<OppCurve, TCurve>* sect
2, double tStart, |
| 878 double tStep, double* resultT, double* oppT) { | 878 double tStep, double* resultT, double* oppT) { |
| 879 SkTSpan<TCurve, OppCurve> work; | 879 SkTSpan<TCurve, OppCurve> work; |
| 880 double result = work.fStartT = work.fEndT = tStart; | 880 double result = work.fStartT = work.fEndT = tStart; |
| 881 SkDEBUGCODE(work.fDebugSect = this); | 881 SkDEBUGCODE(work.fDebugSect = this); |
| 882 SkDPoint last = fCurve.ptAtT(tStart); | 882 SkDPoint last = fCurve.ptAtT(tStart); |
| 883 SkDPoint oppPt; | 883 SkDPoint oppPt; |
| 884 bool flip = false; | 884 bool flip = false; |
| 885 bool contained = false; |
| 885 SkDEBUGCODE(bool down = tStep < 0); | 886 SkDEBUGCODE(bool down = tStep < 0); |
| 886 const OppCurve& opp = sect2->fCurve; | 887 const OppCurve& opp = sect2->fCurve; |
| 887 do { | 888 do { |
| 888 tStep *= 0.5; | 889 tStep *= 0.5; |
| 889 work.fStartT += tStep; | 890 work.fStartT += tStep; |
| 890 if (flip) { | 891 if (flip) { |
| 891 tStep = -tStep; | 892 tStep = -tStep; |
| 892 flip = false; | 893 flip = false; |
| 893 } | 894 } |
| 894 work.initBounds(fCurve); | 895 work.initBounds(fCurve); |
| 895 if (work.fCollapsed) { | 896 if (work.fCollapsed) { |
| 896 return false; | 897 return false; |
| 897 } | 898 } |
| 898 if (last.approximatelyEqual(work.fPart[0])) { | 899 if (last.approximatelyEqual(work.fPart[0])) { |
| 899 break; | 900 break; |
| 900 } | 901 } |
| 901 last = work.fPart[0]; | 902 last = work.fPart[0]; |
| 902 work.fCoinStart.setPerp(fCurve, work.fStartT, last, opp); | 903 work.fCoinStart.setPerp(fCurve, work.fStartT, last, opp); |
| 903 if (work.fCoinStart.isCoincident()) { | 904 if (work.fCoinStart.isCoincident()) { |
| 904 #if DEBUG_T_SECT | 905 #if DEBUG_T_SECT |
| 905 work.validatePerpPt(work.fCoinStart.perpT(), work.fCoinStart.perpPt(
)); | 906 work.validatePerpPt(work.fCoinStart.perpT(), work.fCoinStart.perpPt(
)); |
| 906 #endif | 907 #endif |
| 907 double oppTTest = work.fCoinStart.perpT(); | 908 double oppTTest = work.fCoinStart.perpT(); |
| 908 if (sect2->fHead->contains(oppTTest)) { | 909 if (sect2->fHead->contains(oppTTest)) { |
| 909 *oppT = oppTTest; | 910 *oppT = oppTTest; |
| 910 oppPt = work.fCoinStart.perpPt(); | 911 oppPt = work.fCoinStart.perpPt(); |
| 912 contained = true; |
| 911 SkASSERT(down ? result > work.fStartT : result < work.fStartT); | 913 SkASSERT(down ? result > work.fStartT : result < work.fStartT); |
| 912 result = work.fStartT; | 914 result = work.fStartT; |
| 913 continue; | 915 continue; |
| 914 } | 916 } |
| 915 } | 917 } |
| 916 tStep = -tStep; | 918 tStep = -tStep; |
| 917 flip = true; | 919 flip = true; |
| 918 } while (true); | 920 } while (true); |
| 921 if (!contained) { |
| 922 return false; |
| 923 } |
| 919 if (last.approximatelyEqual(fCurve[0])) { | 924 if (last.approximatelyEqual(fCurve[0])) { |
| 920 result = 0; | 925 result = 0; |
| 921 } else if (last.approximatelyEqual(fCurve[TCurve::kPointLast])) { | 926 } else if (last.approximatelyEqual(fCurve[TCurve::kPointLast])) { |
| 922 result = 1; | 927 result = 1; |
| 923 } | 928 } |
| 924 if (oppPt.approximatelyEqual(opp[0])) { | 929 if (oppPt.approximatelyEqual(opp[0])) { |
| 925 *oppT = 0; | 930 *oppT = 0; |
| 926 } else if (oppPt.approximatelyEqual(opp[OppCurve::kPointLast])) { | 931 } else if (oppPt.approximatelyEqual(opp[OppCurve::kPointLast])) { |
| 927 *oppT = 1; | 932 *oppT = 1; |
| 928 } | 933 } |
| (...skipping 987 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 1916 fC2Span = span2; | 1921 fC2Span = span2; |
| 1917 fC1StartT = span1->startT(); | 1922 fC1StartT = span1->startT(); |
| 1918 fC1EndT = span1->endT(); | 1923 fC1EndT = span1->endT(); |
| 1919 fC2StartT = span2->startT(); | 1924 fC2StartT = span2->startT(); |
| 1920 fC2EndT = span2->endT(); | 1925 fC2EndT = span2->endT(); |
| 1921 fC1Index = c1Index; | 1926 fC1Index = c1Index; |
| 1922 fC2Index = c2Index; | 1927 fC2Index = c2Index; |
| 1923 fClosest = dist; | 1928 fClosest = dist; |
| 1924 } | 1929 } |
| 1925 | 1930 |
| 1926 bool matesWith(const SkClosestRecord& mate) const { | 1931 bool matesWith(const SkClosestRecord& mate SkDEBUGPARAMS(SkIntersections* i
)) const { |
| 1927 SkASSERT(fC1Span == mate.fC1Span || fC1Span->endT() <= mate.fC1Span->sta
rtT() | 1932 SkASSERT(fC1Span == mate.fC1Span || fC1Span->endT() <= mate.fC1Span->sta
rtT() |
| 1928 || mate.fC1Span->endT() <= fC1Span->startT()); | 1933 || mate.fC1Span->endT() <= fC1Span->startT()); |
| 1929 SkASSERT(fC2Span == mate.fC2Span || fC2Span->endT() <= mate.fC2Span->sta
rtT() | 1934 SkOPOBJASSERT(i, fC2Span == mate.fC2Span || fC2Span->endT() <= mate.fC2S
pan->startT() |
| 1930 || mate.fC2Span->endT() <= fC2Span->startT()); | 1935 || mate.fC2Span->endT() <= fC2Span->startT()); |
| 1931 return fC1Span == mate.fC1Span || fC1Span->endT() == mate.fC1Span->start
T() | 1936 return fC1Span == mate.fC1Span || fC1Span->endT() == mate.fC1Span->start
T() |
| 1932 || fC1Span->startT() == mate.fC1Span->endT() | 1937 || fC1Span->startT() == mate.fC1Span->endT() |
| 1933 || fC2Span == mate.fC2Span | 1938 || fC2Span == mate.fC2Span |
| 1934 || fC2Span->endT() == mate.fC2Span->startT() | 1939 || fC2Span->endT() == mate.fC2Span->startT() |
| 1935 || fC2Span->startT() == mate.fC2Span->endT(); | 1940 || fC2Span->startT() == mate.fC2Span->endT(); |
| 1936 } | 1941 } |
| 1937 | 1942 |
| 1938 void merge(const SkClosestRecord& mate) { | 1943 void merge(const SkClosestRecord& mate) { |
| 1939 fC1Span = mate.fC1Span; | 1944 fC1Span = mate.fC1Span; |
| (...skipping 28 matching lines...) Expand all Loading... |
| 1968 int fC2Index; | 1973 int fC2Index; |
| 1969 }; | 1974 }; |
| 1970 | 1975 |
| 1971 template<typename TCurve, typename OppCurve> | 1976 template<typename TCurve, typename OppCurve> |
| 1972 struct SkClosestSect { | 1977 struct SkClosestSect { |
| 1973 SkClosestSect() | 1978 SkClosestSect() |
| 1974 : fUsed(0) { | 1979 : fUsed(0) { |
| 1975 fClosest.push_back().reset(); | 1980 fClosest.push_back().reset(); |
| 1976 } | 1981 } |
| 1977 | 1982 |
| 1978 bool find(const SkTSpan<TCurve, OppCurve>* span1, const SkTSpan<OppCurve, TC
urve>* span2) { | 1983 bool find(const SkTSpan<TCurve, OppCurve>* span1, const SkTSpan<OppCurve, TC
urve>* span2 |
| 1984 SkDEBUGPARAMS(SkIntersections* i)) { |
| 1979 SkClosestRecord<TCurve, OppCurve>* record = &fClosest[fUsed]; | 1985 SkClosestRecord<TCurve, OppCurve>* record = &fClosest[fUsed]; |
| 1980 record->findEnd(span1, span2, 0, 0); | 1986 record->findEnd(span1, span2, 0, 0); |
| 1981 record->findEnd(span1, span2, 0, OppCurve::kPointLast); | 1987 record->findEnd(span1, span2, 0, OppCurve::kPointLast); |
| 1982 record->findEnd(span1, span2, TCurve::kPointLast, 0); | 1988 record->findEnd(span1, span2, TCurve::kPointLast, 0); |
| 1983 record->findEnd(span1, span2, TCurve::kPointLast, OppCurve::kPointLast); | 1989 record->findEnd(span1, span2, TCurve::kPointLast, OppCurve::kPointLast); |
| 1984 if (record->fClosest == FLT_MAX) { | 1990 if (record->fClosest == FLT_MAX) { |
| 1985 return false; | 1991 return false; |
| 1986 } | 1992 } |
| 1987 for (int index = 0; index < fUsed; ++index) { | 1993 for (int index = 0; index < fUsed; ++index) { |
| 1988 SkClosestRecord<TCurve, OppCurve>* test = &fClosest[index]; | 1994 SkClosestRecord<TCurve, OppCurve>* test = &fClosest[index]; |
| 1989 if (test->matesWith(*record)) { | 1995 if (test->matesWith(*record SkDEBUGPARAMS(i))) { |
| 1990 if (test->fClosest > record->fClosest) { | 1996 if (test->fClosest > record->fClosest) { |
| 1991 test->merge(*record); | 1997 test->merge(*record); |
| 1992 } | 1998 } |
| 1993 test->update(*record); | 1999 test->update(*record); |
| 1994 record->reset(); | 2000 record->reset(); |
| 1995 return false; | 2001 return false; |
| 1996 } | 2002 } |
| 1997 } | 2003 } |
| 1998 ++fUsed; | 2004 ++fUsed; |
| 1999 fClosest.push_back().reset(); | 2005 fClosest.push_back().reset(); |
| (...skipping 205 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 2205 do { | 2211 do { |
| 2206 while (result1 && result1->fCoinStart.isCoincident() && result1->fCoinEn
d.isCoincident()) { | 2212 while (result1 && result1->fCoinStart.isCoincident() && result1->fCoinEn
d.isCoincident()) { |
| 2207 result1 = result1->fNext; | 2213 result1 = result1->fNext; |
| 2208 } | 2214 } |
| 2209 if (!result1) { | 2215 if (!result1) { |
| 2210 break; | 2216 break; |
| 2211 } | 2217 } |
| 2212 SkTSpan<OppCurve, TCurve>* result2 = sect2->fHead; | 2218 SkTSpan<OppCurve, TCurve>* result2 = sect2->fHead; |
| 2213 bool found = false; | 2219 bool found = false; |
| 2214 while (result2) { | 2220 while (result2) { |
| 2215 found |= closest.find(result1, result2); | 2221 found |= closest.find(result1, result2 SkDEBUGPARAMS(intersections)
); |
| 2216 result2 = result2->fNext; | 2222 result2 = result2->fNext; |
| 2217 } | 2223 } |
| 2218 } while ((result1 = result1->fNext)); | 2224 } while ((result1 = result1->fNext)); |
| 2219 closest.finish(intersections); | 2225 closest.finish(intersections); |
| 2220 // if there is more than one intersection and it isn't already coincident, c
heck | 2226 // if there is more than one intersection and it isn't already coincident, c
heck |
| 2221 int last = intersections->used() - 1; | 2227 int last = intersections->used() - 1; |
| 2222 for (int index = 0; index < last; ) { | 2228 for (int index = 0; index < last; ) { |
| 2223 if (intersections->isCoincident(index) && intersections->isCoincident(in
dex + 1)) { | 2229 if (intersections->isCoincident(index) && intersections->isCoincident(in
dex + 1)) { |
| 2224 ++index; | 2230 ++index; |
| 2225 continue; | 2231 continue; |
| (...skipping 15 matching lines...) Expand all Loading... |
| 2241 --last; | 2247 --last; |
| 2242 } else { | 2248 } else { |
| 2243 intersections->setCoincident(index++); | 2249 intersections->setCoincident(index++); |
| 2244 } | 2250 } |
| 2245 intersections->setCoincident(index); | 2251 intersections->setCoincident(index); |
| 2246 } | 2252 } |
| 2247 SkASSERT(intersections->used() <= TCurve::kMaxIntersections); | 2253 SkASSERT(intersections->used() <= TCurve::kMaxIntersections); |
| 2248 } | 2254 } |
| 2249 | 2255 |
| 2250 #endif | 2256 #endif |
| OLD | NEW |