Line data Source code
1 : /*
2 : * Copyright 2015 Google Inc.
3 : *
4 : * Use of this source code is governed by a BSD-style license that can be
5 : * found in the LICENSE file.
6 : */
7 :
8 : // given a prospective edge, compute its initial winding by projecting a ray
9 : // if the ray hits another edge
10 : // if the edge doesn't have a winding yet, hop up to that edge and start over
11 : // concern : check for hops forming a loop
12 : // if the edge is unsortable, or
13 : // the intersection is nearly at the ends, or
14 : // the tangent at the intersection is nearly coincident to the ray,
15 : // choose a different ray and try again
16 : // concern : if it is unable to succeed after N tries, try another edge? direction?
17 : // if no edge is hit, compute the winding directly
18 :
19 : // given the top span, project the most perpendicular ray and look for intersections
20 : // let's try up and then down. What the hey
21 :
22 : // bestXY is initialized by caller with basePt
23 :
24 : #include "SkOpContour.h"
25 : #include "SkOpSegment.h"
26 : #include "SkPathOpsCurve.h"
27 :
28 : enum class SkOpRayDir {
29 : kLeft,
30 : kTop,
31 : kRight,
32 : kBottom,
33 : };
34 :
35 : #if DEBUG_WINDING
36 : const char* gDebugRayDirName[] = {
37 : "kLeft",
38 : "kTop",
39 : "kRight",
40 : "kBottom"
41 : };
42 : #endif
43 :
44 0 : static int xy_index(SkOpRayDir dir) {
45 0 : return static_cast<int>(dir) & 1;
46 : }
47 :
48 0 : static SkScalar pt_xy(const SkPoint& pt, SkOpRayDir dir) {
49 0 : return (&pt.fX)[xy_index(dir)];
50 : }
51 :
52 0 : static SkScalar pt_yx(const SkPoint& pt, SkOpRayDir dir) {
53 0 : return (&pt.fX)[!xy_index(dir)];
54 : }
55 :
56 0 : static double pt_dxdy(const SkDVector& v, SkOpRayDir dir) {
57 0 : return (&v.fX)[xy_index(dir)];
58 : }
59 :
60 0 : static double pt_dydx(const SkDVector& v, SkOpRayDir dir) {
61 0 : return (&v.fX)[!xy_index(dir)];
62 : }
63 :
64 0 : static SkScalar rect_side(const SkRect& r, SkOpRayDir dir) {
65 0 : return (&r.fLeft)[static_cast<int>(dir)];
66 : }
67 :
68 0 : static bool sideways_overlap(const SkRect& rect, const SkPoint& pt, SkOpRayDir dir) {
69 0 : int i = !xy_index(dir);
70 0 : return approximately_between((&rect.fLeft)[i], (&pt.fX)[i], (&rect.fRight)[i]);
71 : }
72 :
73 0 : static bool less_than(SkOpRayDir dir) {
74 0 : return static_cast<bool>((static_cast<int>(dir) & 2) == 0);
75 : }
76 :
77 0 : static bool ccw_dxdy(const SkDVector& v, SkOpRayDir dir) {
78 0 : bool vPartPos = pt_dydx(v, dir) > 0;
79 0 : bool leftBottom = ((static_cast<int>(dir) + 1) & 2) != 0;
80 0 : return vPartPos == leftBottom;
81 : }
82 :
83 : struct SkOpRayHit {
84 0 : SkOpRayDir makeTestBase(SkOpSpan* span, double t) {
85 0 : fNext = nullptr;
86 0 : fSpan = span;
87 0 : fT = span->t() * (1 - t) + span->next()->t() * t;
88 0 : SkOpSegment* segment = span->segment();
89 0 : fSlope = segment->dSlopeAtT(fT);
90 0 : fPt = segment->ptAtT(fT);
91 0 : fValid = true;
92 0 : return fabs(fSlope.fX) < fabs(fSlope.fY) ? SkOpRayDir::kLeft : SkOpRayDir::kTop;
93 : }
94 :
95 : SkOpRayHit* fNext;
96 : SkOpSpan* fSpan;
97 : SkPoint fPt;
98 : double fT;
99 : SkDVector fSlope;
100 : bool fValid;
101 : };
102 :
103 0 : void SkOpContour::rayCheck(const SkOpRayHit& base, SkOpRayDir dir, SkOpRayHit** hits,
104 : SkArenaAlloc* allocator) {
105 : // if the bounds extreme is outside the best, we're done
106 0 : SkScalar baseXY = pt_xy(base.fPt, dir);
107 0 : SkScalar boundsXY = rect_side(fBounds, dir);
108 0 : bool checkLessThan = less_than(dir);
109 0 : if (!approximately_equal(baseXY, boundsXY) && (baseXY < boundsXY) == checkLessThan) {
110 0 : return;
111 : }
112 0 : SkOpSegment* testSegment = &fHead;
113 0 : do {
114 0 : testSegment->rayCheck(base, dir, hits, allocator);
115 : } while ((testSegment = testSegment->next()));
116 : }
117 :
118 0 : void SkOpSegment::rayCheck(const SkOpRayHit& base, SkOpRayDir dir, SkOpRayHit** hits,
119 : SkArenaAlloc* allocator) {
120 0 : if (!sideways_overlap(fBounds, base.fPt, dir)) {
121 0 : return;
122 : }
123 0 : SkScalar baseXY = pt_xy(base.fPt, dir);
124 0 : SkScalar boundsXY = rect_side(fBounds, dir);
125 0 : bool checkLessThan = less_than(dir);
126 0 : if (!approximately_equal(baseXY, boundsXY) && (baseXY < boundsXY) == checkLessThan) {
127 0 : return;
128 : }
129 : double tVals[3];
130 0 : SkScalar baseYX = pt_yx(base.fPt, dir);
131 0 : int roots = (*CurveIntercept[fVerb * 2 + xy_index(dir)])(fPts, fWeight, baseYX, tVals);
132 0 : for (int index = 0; index < roots; ++index) {
133 0 : double t = tVals[index];
134 0 : if (base.fSpan->segment() == this && approximately_equal(base.fT, t)) {
135 0 : continue;
136 : }
137 : SkDVector slope;
138 : SkPoint pt;
139 0 : SkDEBUGCODE(sk_bzero(&slope, sizeof(slope)));
140 0 : bool valid = false;
141 0 : if (approximately_zero(t)) {
142 0 : pt = fPts[0];
143 0 : } else if (approximately_equal(t, 1)) {
144 0 : pt = fPts[SkPathOpsVerbToPoints(fVerb)];
145 : } else {
146 0 : SkASSERT(between(0, t, 1));
147 0 : pt = this->ptAtT(t);
148 0 : if (SkDPoint::ApproximatelyEqual(pt, base.fPt)) {
149 0 : if (base.fSpan->segment() == this) {
150 0 : continue;
151 : }
152 : } else {
153 0 : SkScalar ptXY = pt_xy(pt, dir);
154 0 : if (!approximately_equal(baseXY, ptXY) && (baseXY < ptXY) == checkLessThan) {
155 0 : continue;
156 : }
157 0 : slope = this->dSlopeAtT(t);
158 0 : if (fVerb == SkPath::kCubic_Verb && base.fSpan->segment() == this
159 0 : && roughly_equal(base.fT, t)
160 0 : && SkDPoint::RoughlyEqual(pt, base.fPt)) {
161 : #if DEBUG_WINDING
162 : SkDebugf("%s (rarely expect this)\n", __FUNCTION__);
163 : #endif
164 0 : continue;
165 : }
166 0 : if (fabs(pt_dydx(slope, dir) * 10000) > fabs(pt_dxdy(slope, dir))) {
167 0 : valid = true;
168 : }
169 : }
170 : }
171 0 : SkOpSpan* span = this->windingSpanAtT(t);
172 0 : if (!span) {
173 0 : valid = false;
174 0 : } else if (!span->windValue() && !span->oppValue()) {
175 0 : continue;
176 : }
177 0 : SkOpRayHit* newHit = SkOpTAllocator<SkOpRayHit>::Allocate(allocator);
178 0 : newHit->fNext = *hits;
179 0 : newHit->fPt = pt;
180 0 : newHit->fSlope = slope;
181 0 : newHit->fSpan = span;
182 0 : newHit->fT = t;
183 0 : newHit->fValid = valid;
184 0 : *hits = newHit;
185 : }
186 : }
187 :
188 0 : SkOpSpan* SkOpSegment::windingSpanAtT(double tHit) {
189 0 : SkOpSpan* span = &fHead;
190 : SkOpSpanBase* next;
191 0 : do {
192 0 : next = span->next();
193 0 : if (approximately_equal(tHit, next->t())) {
194 0 : return nullptr;
195 : }
196 0 : if (tHit < next->t()) {
197 0 : return span;
198 : }
199 0 : } while (!next->final() && (span = next->upCast()));
200 0 : return nullptr;
201 : }
202 :
203 0 : static bool hit_compare_x(const SkOpRayHit* a, const SkOpRayHit* b) {
204 0 : return a->fPt.fX < b->fPt.fX;
205 : }
206 :
207 0 : static bool reverse_hit_compare_x(const SkOpRayHit* a, const SkOpRayHit* b) {
208 0 : return b->fPt.fX < a->fPt.fX;
209 : }
210 :
211 0 : static bool hit_compare_y(const SkOpRayHit* a, const SkOpRayHit* b) {
212 0 : return a->fPt.fY < b->fPt.fY;
213 : }
214 :
215 0 : static bool reverse_hit_compare_y(const SkOpRayHit* a, const SkOpRayHit* b) {
216 0 : return b->fPt.fY < a->fPt.fY;
217 : }
218 :
219 0 : static double get_t_guess(int tTry, int* dirOffset) {
220 0 : double t = 0.5;
221 0 : *dirOffset = tTry & 1;
222 0 : int tBase = tTry >> 1;
223 0 : int tBits = 0;
224 0 : while (tTry >>= 1) {
225 0 : t /= 2;
226 0 : ++tBits;
227 : }
228 0 : if (tBits) {
229 0 : int tIndex = (tBase - 1) & ((1 << tBits) - 1);
230 0 : t += t * 2 * tIndex;
231 : }
232 0 : return t;
233 : }
234 :
235 0 : bool SkOpSpan::sortableTop(SkOpContour* contourHead) {
236 : char storage[1024];
237 0 : SkArenaAlloc allocator(storage);
238 : int dirOffset;
239 0 : double t = get_t_guess(fTopTTry++, &dirOffset);
240 : SkOpRayHit hitBase;
241 0 : SkOpRayDir dir = hitBase.makeTestBase(this, t);
242 0 : if (hitBase.fSlope.fX == 0 && hitBase.fSlope.fY == 0) {
243 0 : return false;
244 : }
245 0 : SkOpRayHit* hitHead = &hitBase;
246 0 : dir = static_cast<SkOpRayDir>(static_cast<int>(dir) + dirOffset);
247 0 : if (hitBase.fSpan && hitBase.fSpan->segment()->verb() > SkPath::kLine_Verb
248 0 : && !pt_yx(hitBase.fSlope.asSkVector(), dir)) {
249 0 : return false;
250 : }
251 0 : SkOpContour* contour = contourHead;
252 0 : do {
253 0 : if (!contour->count()) {
254 0 : continue;
255 : }
256 0 : contour->rayCheck(hitBase, dir, &hitHead, &allocator);
257 : } while ((contour = contour->next()));
258 : // sort hits
259 0 : SkSTArray<1, SkOpRayHit*> sorted;
260 0 : SkOpRayHit* hit = hitHead;
261 0 : while (hit) {
262 0 : sorted.push_back(hit);
263 0 : hit = hit->fNext;
264 : }
265 0 : int count = sorted.count();
266 0 : SkTQSort(sorted.begin(), sorted.end() - 1, xy_index(dir)
267 0 : ? less_than(dir) ? hit_compare_y : reverse_hit_compare_y
268 0 : : less_than(dir) ? hit_compare_x : reverse_hit_compare_x);
269 : // verify windings
270 : #if DEBUG_WINDING
271 : SkDebugf("%s dir=%s seg=%d t=%1.9g pt=(%1.9g,%1.9g)\n", __FUNCTION__,
272 : gDebugRayDirName[static_cast<int>(dir)], hitBase.fSpan->segment()->debugID(),
273 : hitBase.fT, hitBase.fPt.fX, hitBase.fPt.fY);
274 : for (int index = 0; index < count; ++index) {
275 : hit = sorted[index];
276 : SkOpSpan* span = hit->fSpan;
277 : SkOpSegment* hitSegment = span ? span->segment() : nullptr;
278 : bool operand = span ? hitSegment->operand() : false;
279 : bool ccw = ccw_dxdy(hit->fSlope, dir);
280 : SkDebugf("%s [%d] valid=%d operand=%d span=%d ccw=%d ", __FUNCTION__, index,
281 : hit->fValid, operand, span ? span->debugID() : -1, ccw);
282 : if (span) {
283 : hitSegment->dumpPtsInner();
284 : }
285 : SkDebugf(" t=%1.9g pt=(%1.9g,%1.9g) slope=(%1.9g,%1.9g)\n", hit->fT,
286 : hit->fPt.fX, hit->fPt.fY, hit->fSlope.fX, hit->fSlope.fY);
287 : }
288 : #endif
289 0 : const SkPoint* last = nullptr;
290 0 : int wind = 0;
291 0 : int oppWind = 0;
292 0 : for (int index = 0; index < count; ++index) {
293 0 : hit = sorted[index];
294 0 : if (!hit->fValid) {
295 0 : return false;
296 : }
297 0 : bool ccw = ccw_dxdy(hit->fSlope, dir);
298 : // SkASSERT(!approximately_zero(hit->fT) || !hit->fValid);
299 0 : SkOpSpan* span = hit->fSpan;
300 0 : if (!span) {
301 0 : return false;
302 : }
303 0 : SkOpSegment* hitSegment = span->segment();
304 0 : if (span->windValue() == 0 && span->oppValue() == 0) {
305 0 : continue;
306 : }
307 0 : if (last && SkDPoint::ApproximatelyEqual(*last, hit->fPt)) {
308 0 : return false;
309 : }
310 0 : if (index < count - 1) {
311 0 : const SkPoint& next = sorted[index + 1]->fPt;
312 0 : if (SkDPoint::ApproximatelyEqual(next, hit->fPt)) {
313 0 : return false;
314 : }
315 : }
316 0 : bool operand = hitSegment->operand();
317 0 : if (operand) {
318 0 : SkTSwap(wind, oppWind);
319 : }
320 0 : int lastWind = wind;
321 0 : int lastOpp = oppWind;
322 0 : int windValue = ccw ? -span->windValue() : span->windValue();
323 0 : int oppValue = ccw ? -span->oppValue() : span->oppValue();
324 0 : wind += windValue;
325 0 : oppWind += oppValue;
326 0 : bool sumSet = false;
327 0 : int spanSum = span->windSum();
328 0 : int windSum = SkOpSegment::UseInnerWinding(lastWind, wind) ? wind : lastWind;
329 0 : if (spanSum == SK_MinS32) {
330 0 : span->setWindSum(windSum);
331 0 : sumSet = true;
332 : } else {
333 : // the need for this condition suggests that UseInnerWinding is flawed
334 : // happened when last = 1 wind = -1
335 : #if 0
336 : SkASSERT((hitSegment->isXor() ? (windSum & 1) == (spanSum & 1) : windSum == spanSum)
337 : || (abs(wind) == abs(lastWind)
338 : && (windSum ^ wind ^ lastWind) == spanSum));
339 : #endif
340 : }
341 0 : int oSpanSum = span->oppSum();
342 0 : int oppSum = SkOpSegment::UseInnerWinding(lastOpp, oppWind) ? oppWind : lastOpp;
343 0 : if (oSpanSum == SK_MinS32) {
344 0 : span->setOppSum(oppSum);
345 : } else {
346 : #if 0
347 : SkASSERT(hitSegment->oppXor() ? (oppSum & 1) == (oSpanSum & 1) : oppSum == oSpanSum
348 : || (abs(oppWind) == abs(lastOpp)
349 : && (oppSum ^ oppWind ^ lastOpp) == oSpanSum));
350 : #endif
351 : }
352 0 : if (sumSet) {
353 0 : if (this->globalState()->phase() == SkOpPhase::kFixWinding) {
354 0 : hitSegment->contour()->setCcw(ccw);
355 : } else {
356 0 : (void) hitSegment->markAndChaseWinding(span, span->next(), windSum, oppSum, nullptr);
357 0 : (void) hitSegment->markAndChaseWinding(span->next(), span, windSum, oppSum, nullptr);
358 : }
359 : }
360 0 : if (operand) {
361 0 : SkTSwap(wind, oppWind);
362 : }
363 0 : last = &hit->fPt;
364 0 : this->globalState()->bumpNested();
365 : }
366 0 : return true;
367 : }
368 :
369 0 : SkOpSpan* SkOpSegment::findSortableTop(SkOpContour* contourHead) {
370 0 : SkOpSpan* span = &fHead;
371 : SkOpSpanBase* next;
372 0 : do {
373 0 : next = span->next();
374 0 : if (span->done()) {
375 0 : continue;
376 : }
377 0 : if (span->windSum() != SK_MinS32) {
378 0 : return span;
379 : }
380 0 : if (span->sortableTop(contourHead)) {
381 0 : return span;
382 : }
383 0 : } while (!next->final() && (span = next->upCast()));
384 0 : return nullptr;
385 : }
386 :
387 0 : SkOpSpan* SkOpContour::findSortableTop(SkOpContour* contourHead) {
388 0 : bool allDone = true;
389 0 : if (fCount) {
390 0 : SkOpSegment* testSegment = &fHead;
391 0 : do {
392 0 : if (testSegment->done()) {
393 0 : continue;
394 : }
395 0 : allDone = false;
396 0 : SkOpSpan* result = testSegment->findSortableTop(contourHead);
397 0 : if (result) {
398 0 : return result;
399 : }
400 : } while ((testSegment = testSegment->next()));
401 : }
402 0 : if (allDone) {
403 0 : fDone = true;
404 : }
405 0 : return nullptr;
406 : }
407 :
408 0 : SkOpSpan* FindSortableTop(SkOpContourHead* contourHead) {
409 0 : for (int index = 0; index < SkOpGlobalState::kMaxWindingTries; ++index) {
410 0 : SkOpContour* contour = contourHead;
411 0 : do {
412 0 : if (contour->done()) {
413 0 : continue;
414 : }
415 0 : SkOpSpan* result = contour->findSortableTop(contourHead);
416 0 : if (result) {
417 0 : return result;
418 : }
419 : } while ((contour = contour->next()));
420 : }
421 0 : return nullptr;
422 : }
|
