The Tor Browser / file comparison

comparison: gfx/skia/trunk/src/pathops/SkOpAngle.cpp

gfx/skia/trunk/src/pathops/SkOpAngle.cpp

branch
TOR_BUG_3246
changeset 7
129ffea94266
equal deleted inserted replaced
-1:000000000000 0:364d2b9049bd
1 /*
2 * Copyright 2012 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 #include "SkIntersections.h"
8 #include "SkOpAngle.h"
9 #include "SkOpSegment.h"
10 #include "SkPathOpsCurve.h"
11 #include "SkTSort.h"
12
13 #if DEBUG_ANGLE
14 #include "SkString.h"
15
16 static const char funcName[] = "SkOpSegment::operator<";
17 static const int bugChar = strlen(funcName) + 1;
18 #endif
19
20 /* Angles are sorted counterclockwise. The smallest angle has a positive x and the smallest
21 positive y. The largest angle has a positive x and a zero y. */
22
23 #if DEBUG_ANGLE
24 static bool CompareResult(SkString* bugOut, const char* append, bool compare) {
25 bugOut->appendf("%s", append);
26 bugOut->writable_str()[bugChar] = "><"[compare];
27 SkDebugf("%s\n", bugOut->c_str());
28 return compare;
29 }
30
31 #define COMPARE_RESULT(append, compare) CompareResult(&bugOut, append, compare)
32 #else
33 #define COMPARE_RESULT(append, compare) compare
34 #endif
35
36 bool SkOpAngle::calcSlop(double x, double y, double rx, double ry, bool* result) const{
37 double absX = fabs(x);
38 double absY = fabs(y);
39 double length = absX < absY ? absX / 2 + absY : absX + absY / 2;
40 int exponent;
41 (void) frexp(length, &exponent);
42 double epsilon = ldexp(FLT_EPSILON, exponent);
43 SkPath::Verb verb = fSegment->verb();
44 SkASSERT(verb == SkPath::kQuad_Verb || verb == SkPath::kCubic_Verb);
45 // FIXME: the quad and cubic factors are made up ; determine actual values
46 double slop = verb == SkPath::kQuad_Verb ? 4 * epsilon : 512 * epsilon;
47 double xSlop = slop;
48 double ySlop = x * y < 0 ? -xSlop : xSlop; // OPTIMIZATION: use copysign / _copysign ?
49 double x1 = x - xSlop;
50 double y1 = y + ySlop;
51 double x_ry1 = x1 * ry;
52 double rx_y1 = rx * y1;
53 *result = x_ry1 < rx_y1;
54 double x2 = x + xSlop;
55 double y2 = y - ySlop;
56 double x_ry2 = x2 * ry;
57 double rx_y2 = rx * y2;
58 bool less2 = x_ry2 < rx_y2;
59 return *result == less2;
60 }
61
62 /*
63 for quads and cubics, set up a parameterized line (e.g. LineParameters )
64 for points [0] to [1]. See if point [2] is on that line, or on one side
65 or the other. If it both quads' end points are on the same side, choose
66 the shorter tangent. If the tangents are equal, choose the better second
67 tangent angle
68
69 FIXME: maybe I could set up LineParameters lazily
70 */
71 bool SkOpAngle::operator<(const SkOpAngle& rh) const { // this/lh: left-hand; rh: right-hand
72 double y = dy();
73 double ry = rh.dy();
74 #if DEBUG_ANGLE
75 SkString bugOut;
76 bugOut.printf("%s _ id=%d segId=%d tStart=%1.9g tEnd=%1.9g"
77 " | id=%d segId=%d tStart=%1.9g tEnd=%1.9g ", funcName,
78 fID, fSegment->debugID(), fSegment->t(fStart), fSegment->t(fEnd),
79 rh.fID, rh.fSegment->debugID(), rh.fSegment->t(rh.fStart), rh.fSegment->t(rh.fEnd));
80 #endif
81 double y_ry = y * ry;
82 if (y_ry < 0) { // if y's are opposite signs, we can do a quick return
83 return COMPARE_RESULT("1 y * ry < 0", y < 0);
84 }
85 // at this point, both y's must be the same sign, or one (or both) is zero
86 double x = dx();
87 double rx = rh.dx();
88 if (x * rx < 0) { // if x's are opposite signs, use y to determine first or second half
89 if (y < 0 && ry < 0) { // if y's are negative, lh x is smaller if positive
90 return COMPARE_RESULT("2 x_rx < 0 && y < 0 ...", x > 0);
91 }
92 if (y >= 0 && ry >= 0) { // if y's are zero or positive, lh x is smaller if negative
93 return COMPARE_RESULT("3 x_rx < 0 && y >= 0 ...", x < 0);
94 }
95 SkASSERT((y == 0) ^ (ry == 0)); // if one y is zero and one is negative, neg y is smaller
96 return COMPARE_RESULT("4 x_rx < 0 && y == 0 ...", y < 0);
97 }
98 // at this point, both x's must be the same sign, or one (or both) is zero
99 if (y_ry == 0) { // if either y is zero
100 if (y + ry < 0) { // if the other y is less than zero, it must be smaller
101 return COMPARE_RESULT("5 y_ry == 0 && y + ry < 0", y < 0);
102 }
103 if (y + ry > 0) { // if a y is greater than zero and an x is positive, non zero is smaller
104 return COMPARE_RESULT("6 y_ry == 0 && y + ry > 0", (x + rx > 0) ^ (y == 0));
105 }
106 // at this point, both y's are zero, so lines are coincident or one is degenerate
107 SkASSERT(x * rx != 0); // and a degenerate line should haven't gotten this far
108 }
109 // see if either curve can be lengthened before trying the tangent
110 if (fSegment->other(fEnd) != rh.fSegment // tangents not absolutely identical
111 && rh.fSegment->other(rh.fEnd) != fSegment
112 && y != -DBL_EPSILON
113 && ry != -DBL_EPSILON) { // and not intersecting
114 SkOpAngle longer = *this;
115 SkOpAngle rhLonger = rh;
116 if ((longer.lengthen(rh) | rhLonger.lengthen(*this)) // lengthen both
117 && (fUnorderable || !longer.fUnorderable)
118 && (rh.fUnorderable || !rhLonger.fUnorderable)) {
119 #if DEBUG_ANGLE
120 bugOut.prepend(" ");
121 #endif
122 return COMPARE_RESULT("10 longer.lengthen(rh) ...", longer < rhLonger);
123 }
124 }
125 SkPath::Verb verb = fSegment->verb();
126 SkPath::Verb rVerb = rh.fSegment->verb();
127 if (y_ry != 0) { // if they aren't coincident, look for a stable cross product
128 // at this point, y's are the same sign, neither is zero
129 // and x's are the same sign, or one (or both) is zero
130 double x_ry = x * ry;
131 double rx_y = rx * y;
132 if (!fComputed && !rh.fComputed) {
133 if (!SkDLine::NearRay(x, y, rx, ry) && x_ry != rx_y) {
134 return COMPARE_RESULT("7 !fComputed && !rh.fComputed", x_ry < rx_y);
135 }
136 if (fSide2 == 0 && rh.fSide2 == 0) {
137 return COMPARE_RESULT("7a !fComputed && !rh.fComputed", x_ry < rx_y);
138 }
139 } else {
140 // if the vector was a result of subdividing a curve, see if it is stable
141 bool sloppy1 = x_ry < rx_y;
142 bool sloppy2 = !sloppy1;
143 if ((!fComputed || calcSlop(x, y, rx, ry, &sloppy1))
144 && (!rh.fComputed || rh.calcSlop(rx, ry, x, y, &sloppy2))
145 && sloppy1 != sloppy2) {
146 return COMPARE_RESULT("8 CalcSlop(x, y ...", sloppy1);
147 }
148 }
149 }
150 if (fSide2 * rh.fSide2 == 0) { // one is zero
151 #if DEBUG_ANGLE
152 if (fSide2 == rh.fSide2 && y_ry) { // both is zero; coincidence was undetected
153 SkDebugf("%s coincidence!\n", __FUNCTION__);
154 }
155 #endif
156 return COMPARE_RESULT("9a fSide2 * rh.fSide2 == 0 ...", fSide2 < rh.fSide2);
157 }
158 // at this point, the initial tangent line is nearly coincident
159 // see if edges curl away from each other
160 if (fSide * rh.fSide < 0 && (!approximately_zero(fSide) || !approximately_zero(rh.fSide))) {
161 return COMPARE_RESULT("9b fSide * rh.fSide < 0 ...", fSide < rh.fSide);
162 }
163 if (fUnsortable || rh.fUnsortable) {
164 // even with no solution, return a stable sort
165 return COMPARE_RESULT("11 fUnsortable || rh.fUnsortable", this < &rh);
166 }
167 if ((verb == SkPath::kLine_Verb && approximately_zero(y) && approximately_zero(x))
168 || (rVerb == SkPath::kLine_Verb
169 && approximately_zero(ry) && approximately_zero(rx))) {
170 // See general unsortable comment below. This case can happen when
171 // one line has a non-zero change in t but no change in x and y.
172 fUnsortable = true;
173 return COMPARE_RESULT("12 verb == SkPath::kLine_Verb ...", this < &rh);
174 }
175 if (fSegment->isTiny(this) || rh.fSegment->isTiny(&rh)) {
176 fUnsortable = true;
177 return COMPARE_RESULT("13 verb == fSegment->isTiny(this) ...", this < &rh);
178 }
179 SkASSERT(verb >= SkPath::kQuad_Verb);
180 SkASSERT(rVerb >= SkPath::kQuad_Verb);
181 // FIXME: until I can think of something better, project a ray from the
182 // end of the shorter tangent to midway between the end points
183 // through both curves and use the resulting angle to sort
184 // FIXME: some of this setup can be moved to set() if it works, or cached if it's expensive
185 double len = fTangentPart.normalSquared();
186 double rlen = rh.fTangentPart.normalSquared();
187 SkDLine ray;
188 SkIntersections i, ri;
189 int roots, rroots;
190 bool flip = false;
191 bool useThis;
192 bool leftLessThanRight = fSide > 0;
193 do {
194 useThis = (len < rlen) ^ flip;
195 const SkDCubic& part = useThis ? fCurvePart : rh.fCurvePart;
196 SkPath::Verb partVerb = useThis ? verb : rVerb;
197 ray[0] = partVerb == SkPath::kCubic_Verb && part[0].approximatelyEqual(part[1]) ?
198 part[2] : part[1];
199 ray[1] = SkDPoint::Mid(part[0], part[SkPathOpsVerbToPoints(partVerb)]);
200 SkASSERT(ray[0] != ray[1]);
201 roots = (i.*CurveRay[SkPathOpsVerbToPoints(verb)])(fSegment->pts(), ray);
202 rroots = (ri.*CurveRay[SkPathOpsVerbToPoints(rVerb)])(rh.fSegment->pts(), ray);
203 } while ((roots == 0 || rroots == 0) && (flip ^= true));
204 if (roots == 0 || rroots == 0) {
205 // FIXME: we don't have a solution in this case. The interim solution
206 // is to mark the edges as unsortable, exclude them from this and
207 // future computations, and allow the returned path to be fragmented
208 fUnsortable = true;
209 return COMPARE_RESULT("roots == 0 || rroots == 0", this < &rh);
210 }
211 SkASSERT(fSide != 0 && rh.fSide != 0);
212 if (fSide * rh.fSide < 0) {
213 fUnsortable = true;
214 return COMPARE_RESULT("14 fSide * rh.fSide < 0", this < &rh);
215 }
216 SkDPoint lLoc;
217 double best = SK_ScalarInfinity;
218 #if DEBUG_SORT
219 SkDebugf("lh=%d rh=%d use-lh=%d ray={{%1.9g,%1.9g}, {%1.9g,%1.9g}} %c\n",
220 fSegment->debugID(), rh.fSegment->debugID(), useThis, ray[0].fX, ray[0].fY,
221 ray[1].fX, ray[1].fY, "-+"[fSide > 0]);
222 #endif
223 for (int index = 0; index < roots; ++index) {
224 SkDPoint loc = i.pt(index);
225 SkDVector dxy = loc - ray[0];
226 double dist = dxy.lengthSquared();
227 #if DEBUG_SORT
228 SkDebugf("best=%1.9g dist=%1.9g loc={%1.9g,%1.9g} dxy={%1.9g,%1.9g}\n",
229 best, dist, loc.fX, loc.fY, dxy.fX, dxy.fY);
230 #endif
231 if (best > dist) {
232 lLoc = loc;
233 best = dist;
234 }
235 }
236 flip = false;
237 SkDPoint rLoc;
238 for (int index = 0; index < rroots; ++index) {
239 rLoc = ri.pt(index);
240 SkDVector dxy = rLoc - ray[0];
241 double dist = dxy.lengthSquared();
242 #if DEBUG_SORT
243 SkDebugf("best=%1.9g dist=%1.9g %c=(fSide < 0) rLoc={%1.9g,%1.9g} dxy={%1.9g,%1.9g}\n",
244 best, dist, "><"[fSide < 0], rLoc.fX, rLoc.fY, dxy.fX, dxy.fY);
245 #endif
246 if (best > dist) {
247 flip = true;
248 break;
249 }
250 }
251 if (flip) {
252 leftLessThanRight = !leftLessThanRight;
253 }
254 return COMPARE_RESULT("15 leftLessThanRight", leftLessThanRight);
255 }
256
257 bool SkOpAngle::isHorizontal() const {
258 return dy() == 0 && fSegment->verb() == SkPath::kLine_Verb;
259 }
260
261 // lengthen cannot cross opposite angle
262 bool SkOpAngle::lengthen(const SkOpAngle& opp) {
263 if (fSegment->other(fEnd) == opp.fSegment) {
264 return false;
265 }
266 // FIXME: make this a while loop instead and make it as large as possible?
267 int newEnd = fEnd;
268 if (fStart < fEnd ? ++newEnd < fSegment->count() : --newEnd >= 0) {
269 fEnd = newEnd;
270 setSpans();
271 return true;
272 }
273 return false;
274 }
275
276 void SkOpAngle::set(const SkOpSegment* segment, int start, int end) {
277 fSegment = segment;
278 fStart = start;
279 fEnd = end;
280 setSpans();
281 }
282
283 void SkOpAngle::setSpans() {
284 fUnorderable = fSegment->isTiny(this);
285 fLastMarked = NULL;
286 fUnsortable = false;
287 const SkPoint* pts = fSegment->pts();
288 if (fSegment->verb() != SkPath::kLine_Verb) {
289 fComputed = fSegment->subDivide(fStart, fEnd, &fCurvePart);
290 fSegment->subDivide(fStart, fStart < fEnd ? fSegment->count() - 1 : 0, &fCurveHalf);
291 }
292 // FIXME: slight errors in subdivision cause sort trouble later on. As an experiment, try
293 // rounding the curve part to float precision here
294 // fCurvePart.round(fSegment->verb());
295 switch (fSegment->verb()) {
296 case SkPath::kLine_Verb: {
297 SkASSERT(fStart != fEnd);
298 fCurvePart[0].set(pts[fStart > fEnd]);
299 fCurvePart[1].set(pts[fStart < fEnd]);
300 fComputed = false;
301 // OPTIMIZATION: for pure line compares, we never need fTangentPart.c
302 fTangentPart.lineEndPoints(*SkTCast<SkDLine*>(&fCurvePart));
303 fSide = 0;
304 fSide2 = 0;
305 } break;
306 case SkPath::kQuad_Verb: {
307 fSide2 = -fTangentHalf.quadPart(*SkTCast<SkDQuad*>(&fCurveHalf));
308 SkDQuad& quad = *SkTCast<SkDQuad*>(&fCurvePart);
309 fTangentPart.quadEndPoints(quad);
310 fSide = -fTangentPart.pointDistance(fCurvePart[2]); // not normalized -- compare sign only
311 if (fComputed && dx() > 0 && approximately_zero(dy())) {
312 SkDCubic origCurve; // can't use segment's curve in place since it may be flipped
313 int last = fSegment->count() - 1;
314 fSegment->subDivide(fStart < fEnd ? 0 : last, fStart < fEnd ? last : 0, &origCurve);
315 SkLineParameters origTan;
316 origTan.quadEndPoints(*SkTCast<SkDQuad*>(&origCurve));
317 if (origTan.dx() <= 0
318 || (dy() != origTan.dy() && dy() * origTan.dy() <= 0)) { // signs match?
319 fUnorderable = true;
320 return;
321 }
322 }
323 } break;
324 case SkPath::kCubic_Verb: {
325 double startT = fSegment->t(fStart);
326 fSide2 = -fTangentHalf.cubicPart(fCurveHalf);
327 fTangentPart.cubicEndPoints(fCurvePart);
328 double testTs[4];
329 // OPTIMIZATION: keep inflections precomputed with cubic segment?
330 int testCount = SkDCubic::FindInflections(pts, testTs);
331 double endT = fSegment->t(fEnd);
332 double limitT = endT;
333 int index;
334 for (index = 0; index < testCount; ++index) {
335 if (!between(startT, testTs[index], limitT)) {
336 testTs[index] = -1;
337 }
338 }
339 testTs[testCount++] = startT;
340 testTs[testCount++] = endT;
341 SkTQSort<double>(testTs, &testTs[testCount - 1]);
342 double bestSide = 0;
343 int testCases = (testCount << 1) - 1;
344 index = 0;
345 while (testTs[index] < 0) {
346 ++index;
347 }
348 index <<= 1;
349 for (; index < testCases; ++index) {
350 int testIndex = index >> 1;
351 double testT = testTs[testIndex];
352 if (index & 1) {
353 testT = (testT + testTs[testIndex + 1]) / 2;
354 }
355 // OPTIMIZE: could avoid call for t == startT, endT
356 SkDPoint pt = dcubic_xy_at_t(pts, testT);
357 double testSide = fTangentPart.pointDistance(pt);
358 if (fabs(bestSide) < fabs(testSide)) {
359 bestSide = testSide;
360 }
361 }
362 fSide = -bestSide; // compare sign only
363 SkASSERT(fSide == 0 || fSide2 != 0);
364 if (fComputed && dx() > 0 && approximately_zero(dy())) {
365 SkDCubic origCurve; // can't use segment's curve in place since it may be flipped
366 int last = fSegment->count() - 1;
367 fSegment->subDivide(fStart < fEnd ? 0 : last, fStart < fEnd ? last : 0, &origCurve);
368 SkDCubicPair split = origCurve.chopAt(startT);
369 SkLineParameters splitTan;
370 splitTan.cubicEndPoints(fStart < fEnd ? split.second() : split.first());
371 if (splitTan.dx() <= 0) {
372 fUnorderable = true;
373 fUnsortable = fSegment->isTiny(this);
374 return;
375 }
376 // if one is < 0 and the other is >= 0
377 if (dy() * splitTan.dy() < 0) {
378 fUnorderable = true;
379 fUnsortable = fSegment->isTiny(this);
380 return;
381 }
382 }
383 } break;
384 default:
385 SkASSERT(0);
386 }
387 if ((fUnsortable = approximately_zero(dx()) && approximately_zero(dy()))) {
388 return;
389 }
390 if (fSegment->verb() == SkPath::kLine_Verb) {
391 return;
392 }
393 SkASSERT(fStart != fEnd);
394 int smaller = SkMin32(fStart, fEnd);
395 int larger = SkMax32(fStart, fEnd);
396 while (smaller < larger && fSegment->span(smaller).fTiny) {
397 ++smaller;
398 }
399 if (precisely_equal(fSegment->span(smaller).fT, fSegment->span(larger).fT)) {
400 #if DEBUG_UNSORTABLE
401 SkPoint iPt = fSegment->xyAtT(fStart);
402 SkPoint ePt = fSegment->xyAtT(fEnd);
403 SkDebugf("%s all tiny unsortable [%d] (%1.9g,%1.9g) [%d] (%1.9g,%1.9g)\n", __FUNCTION__,
404 fStart, iPt.fX, iPt.fY, fEnd, ePt.fX, ePt.fY);
405 #endif
406 fUnsortable = true;
407 return;
408 }
409 fUnsortable = fStart < fEnd ? fSegment->span(smaller).fUnsortableStart
410 : fSegment->span(larger).fUnsortableEnd;
411 #if DEBUG_UNSORTABLE
412 if (fUnsortable) {
413 SkPoint iPt = fSegment->xyAtT(smaller);
414 SkPoint ePt = fSegment->xyAtT(larger);
415 SkDebugf("%s unsortable [%d] (%1.9g,%1.9g) [%d] (%1.9g,%1.9g)\n", __FUNCTION__,
416 smaller, iPt.fX, iPt.fY, fEnd, ePt.fX, ePt.fY);
417 }
418 #endif
419 return;
420 }
421
422 #ifdef SK_DEBUG
423 void SkOpAngle::dump() const {
424 const SkOpSpan& spanStart = fSegment->span(fStart);
425 const SkOpSpan& spanEnd = fSegment->span(fEnd);
426 const SkOpSpan& spanMin = fStart < fEnd ? spanStart : spanEnd;
427 SkDebugf("id=%d (%1.9g,%1.9g) start=%d (%1.9g) end=%d (%1.9g) sumWind=",
428 fSegment->debugID(), fSegment->xAtT(fStart), fSegment->yAtT(fStart),
429 fStart, spanStart.fT, fEnd, spanEnd.fT);
430 SkPathOpsDebug::WindingPrintf(spanMin.fWindSum);
431 SkDebugf(" oppWind=");
432 SkPathOpsDebug::WindingPrintf(spanMin.fOppSum),
433 SkDebugf(" done=%d\n", spanMin.fDone);
434 }
435 #endif

Mercurial Repository: The Tor Browser

Europalab SCM Repository Server

mercurial