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 |