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 "src/pathops/SkPathOpsQuad.h"
8
9 #include "src/pathops/SkIntersections.h"
10 #include "src/pathops/SkLineParameters.h"
11 #include "src/pathops/SkPathOpsConic.h"
12 #include "src/pathops/SkPathOpsCubic.h"
13 #include "src/pathops/SkPathOpsLine.h"
14 #include "src/pathops/SkPathOpsRect.h"
15 #include "src/pathops/SkPathOpsTypes.h"
16
17 #include <algorithm>
18 #include <cmath>
19
20 // from blackpawn.com/texts/pointinpoly
pointInTriangle(const SkDPoint fPts[3],const SkDPoint & test)21 static bool pointInTriangle(const SkDPoint fPts[3], const SkDPoint& test) {
22 SkDVector v0 = fPts[2] - fPts[0];
23 SkDVector v1 = fPts[1] - fPts[0];
24 SkDVector v2 = test - fPts[0];
25 double dot00 = v0.dot(v0);
26 double dot01 = v0.dot(v1);
27 double dot02 = v0.dot(v2);
28 double dot11 = v1.dot(v1);
29 double dot12 = v1.dot(v2);
30 // Compute barycentric coordinates
31 double denom = dot00 * dot11 - dot01 * dot01;
32 double u = dot11 * dot02 - dot01 * dot12;
33 double v = dot00 * dot12 - dot01 * dot02;
34 // Check if point is in triangle
35 if (denom >= 0) {
36 return u >= 0 && v >= 0 && u + v < denom;
37 }
38 return u <= 0 && v <= 0 && u + v > denom;
39 }
40
matchesEnd(const SkDPoint fPts[3],const SkDPoint & test)41 static bool matchesEnd(const SkDPoint fPts[3], const SkDPoint& test) {
42 return fPts[0] == test || fPts[2] == test;
43 }
44
45 /* started with at_most_end_pts_in_common from SkDQuadIntersection.cpp */
46 // Do a quick reject by rotating all points relative to a line formed by
47 // a pair of one quad's points. If the 2nd quad's points
48 // are on the line or on the opposite side from the 1st quad's 'odd man', the
49 // curves at most intersect at the endpoints.
50 /* if returning true, check contains true if quad's hull collapsed, making the cubic linear
51 if returning false, check contains true if the the quad pair have only the end point in common
52 */
hullIntersects(const SkDQuad & q2,bool * isLinear) const53 bool SkDQuad::hullIntersects(const SkDQuad& q2, bool* isLinear) const {
54 bool linear = true;
55 for (int oddMan = 0; oddMan < kPointCount; ++oddMan) {
56 const SkDPoint* endPt[2];
57 this->otherPts(oddMan, endPt);
58 double origX = endPt[0]->fX;
59 double origY = endPt[0]->fY;
60 double adj = endPt[1]->fX - origX;
61 double opp = endPt[1]->fY - origY;
62 double sign = (fPts[oddMan].fY - origY) * adj - (fPts[oddMan].fX - origX) * opp;
63 if (approximately_zero(sign)) {
64 continue;
65 }
66 linear = false;
67 bool foundOutlier = false;
68 for (int n = 0; n < kPointCount; ++n) {
69 double test = (q2[n].fY - origY) * adj - (q2[n].fX - origX) * opp;
70 if (test * sign > 0 && !precisely_zero(test)) {
71 foundOutlier = true;
72 break;
73 }
74 }
75 if (!foundOutlier) {
76 return false;
77 }
78 }
79 if (linear && !matchesEnd(fPts, q2.fPts[0]) && !matchesEnd(fPts, q2.fPts[2])) {
80 // if the end point of the opposite quad is inside the hull that is nearly a line,
81 // then representing the quad as a line may cause the intersection to be missed.
82 // Check to see if the endpoint is in the triangle.
83 if (pointInTriangle(fPts, q2.fPts[0]) || pointInTriangle(fPts, q2.fPts[2])) {
84 linear = false;
85 }
86 }
87 *isLinear = linear;
88 return true;
89 }
90
hullIntersects(const SkDConic & conic,bool * isLinear) const91 bool SkDQuad::hullIntersects(const SkDConic& conic, bool* isLinear) const {
92 return conic.hullIntersects(*this, isLinear);
93 }
94
hullIntersects(const SkDCubic & cubic,bool * isLinear) const95 bool SkDQuad::hullIntersects(const SkDCubic& cubic, bool* isLinear) const {
96 return cubic.hullIntersects(*this, isLinear);
97 }
98
99 /* bit twiddling for finding the off curve index (x&~m is the pair in [0,1,2] excluding oddMan)
100 oddMan opp x=oddMan^opp x=x-oddMan m=x>>2 x&~m
101 0 1 1 1 0 1
102 2 2 2 0 2
103 1 1 0 -1 -1 0
104 2 3 2 0 2
105 2 1 3 1 0 1
106 2 0 -2 -1 0
107 */
otherPts(int oddMan,const SkDPoint * endPt[2]) const108 void SkDQuad::otherPts(int oddMan, const SkDPoint* endPt[2]) const {
109 for (int opp = 1; opp < kPointCount; ++opp) {
110 int end = (oddMan ^ opp) - oddMan; // choose a value not equal to oddMan
111 end &= ~(end >> 2); // if the value went negative, set it to zero
112 endPt[opp - 1] = &fPts[end];
113 }
114 }
115
AddValidTs(double s[],int realRoots,double * t)116 int SkDQuad::AddValidTs(double s[], int realRoots, double* t) {
117 int foundRoots = 0;
118 for (int index = 0; index < realRoots; ++index) {
119 double tValue = s[index];
120 if (approximately_zero_or_more(tValue) && approximately_one_or_less(tValue)) {
121 if (approximately_less_than_zero(tValue)) {
122 tValue = 0;
123 } else if (approximately_greater_than_one(tValue)) {
124 tValue = 1;
125 }
126 for (int idx2 = 0; idx2 < foundRoots; ++idx2) {
127 if (approximately_equal(t[idx2], tValue)) {
128 goto nextRoot;
129 }
130 }
131 t[foundRoots++] = tValue;
132 }
133 nextRoot:
134 {}
135 }
136 return foundRoots;
137 }
138
139 // note: caller expects multiple results to be sorted smaller first
140 // note: http://en.wikipedia.org/wiki/Loss_of_significance has an interesting
141 // analysis of the quadratic equation, suggesting why the following looks at
142 // the sign of B -- and further suggesting that the greatest loss of precision
143 // is in b squared less two a c
RootsValidT(double A,double B,double C,double t[2])144 int SkDQuad::RootsValidT(double A, double B, double C, double t[2]) {
145 double s[2];
146 int realRoots = RootsReal(A, B, C, s);
147 int foundRoots = AddValidTs(s, realRoots, t);
148 return foundRoots;
149 }
150
handle_zero(const double B,const double C,double s[2])151 static int handle_zero(const double B, const double C, double s[2]) {
152 if (approximately_zero(B)) {
153 s[0] = 0;
154 return C == 0;
155 }
156 s[0] = -C / B;
157 return 1;
158 }
159
160 /*
161 Numeric Solutions (5.6) suggests to solve the quadratic by computing
162 Q = -1/2(B + sgn(B)Sqrt(B^2 - 4 A C))
163 and using the roots
164 t1 = Q / A
165 t2 = C / Q
166 */
167 // this does not discard real roots <= 0 or >= 1
168 // TODO(skbug.com/14063) Deduplicate with SkQuads::RootsReal
RootsReal(const double A,const double B,const double C,double s[2])169 int SkDQuad::RootsReal(const double A, const double B, const double C, double s[2]) {
170 if (!A) {
171 return handle_zero(B, C, s);
172 }
173 const double p = B / (2 * A);
174 const double q = C / A;
175 if (approximately_zero(A) && (approximately_zero_inverse(p) || approximately_zero_inverse(q))) {
176 return handle_zero(B, C, s);
177 }
178 /* normal form: x^2 + px + q = 0 */
179 const double p2 = p * p;
180 if (!AlmostDequalUlps(p2, q) && p2 < q) {
181 return 0;
182 }
183 double sqrt_D = 0;
184 if (p2 > q) {
185 sqrt_D = sqrt(p2 - q);
186 }
187 s[0] = sqrt_D - p;
188 s[1] = -sqrt_D - p;
189 return 1 + !AlmostDequalUlps(s[0], s[1]);
190 }
191
isLinear(int startIndex,int endIndex) const192 bool SkDQuad::isLinear(int startIndex, int endIndex) const {
193 SkLineParameters lineParameters;
194 lineParameters.quadEndPoints(*this, startIndex, endIndex);
195 // FIXME: maybe it's possible to avoid this and compare non-normalized
196 lineParameters.normalize();
197 double distance = lineParameters.controlPtDistance(*this);
198 double tiniest = std::min(std::min(std::min(std::min(std::min(fPts[0].fX, fPts[0].fY),
199 fPts[1].fX), fPts[1].fY), fPts[2].fX), fPts[2].fY);
200 double largest = std::max(std::max(std::max(std::max(std::max(fPts[0].fX, fPts[0].fY),
201 fPts[1].fX), fPts[1].fY), fPts[2].fX), fPts[2].fY);
202 largest = std::max(largest, -tiniest);
203 return approximately_zero_when_compared_to(distance, largest);
204 }
205
dxdyAtT(double t) const206 SkDVector SkDQuad::dxdyAtT(double t) const {
207 double a = t - 1;
208 double b = 1 - 2 * t;
209 double c = t;
210 SkDVector result = { a * fPts[0].fX + b * fPts[1].fX + c * fPts[2].fX,
211 a * fPts[0].fY + b * fPts[1].fY + c * fPts[2].fY };
212 if (result.fX == 0 && result.fY == 0) {
213 if (zero_or_one(t)) {
214 result = fPts[2] - fPts[0];
215 } else {
216 // incomplete
217 SkDebugf("!q");
218 }
219 }
220 return result;
221 }
222
223 // OPTIMIZE: assert if caller passes in t == 0 / t == 1 ?
ptAtT(double t) const224 SkDPoint SkDQuad::ptAtT(double t) const {
225 if (0 == t) {
226 return fPts[0];
227 }
228 if (1 == t) {
229 return fPts[2];
230 }
231 double one_t = 1 - t;
232 double a = one_t * one_t;
233 double b = 2 * one_t * t;
234 double c = t * t;
235 SkDPoint result = { a * fPts[0].fX + b * fPts[1].fX + c * fPts[2].fX,
236 a * fPts[0].fY + b * fPts[1].fY + c * fPts[2].fY };
237 return result;
238 }
239
interp_quad_coords(const double * src,double t)240 static double interp_quad_coords(const double* src, double t) {
241 if (0 == t) {
242 return src[0];
243 }
244 if (1 == t) {
245 return src[4];
246 }
247 double ab = SkDInterp(src[0], src[2], t);
248 double bc = SkDInterp(src[2], src[4], t);
249 double abc = SkDInterp(ab, bc, t);
250 return abc;
251 }
252
monotonicInX() const253 bool SkDQuad::monotonicInX() const {
254 return between(fPts[0].fX, fPts[1].fX, fPts[2].fX);
255 }
256
monotonicInY() const257 bool SkDQuad::monotonicInY() const {
258 return between(fPts[0].fY, fPts[1].fY, fPts[2].fY);
259 }
260
261 /*
262 Given a quadratic q, t1, and t2, find a small quadratic segment.
263
264 The new quadratic is defined by A, B, and C, where
265 A = c[0]*(1 - t1)*(1 - t1) + 2*c[1]*t1*(1 - t1) + c[2]*t1*t1
266 C = c[3]*(1 - t1)*(1 - t1) + 2*c[2]*t1*(1 - t1) + c[1]*t1*t1
267
268 To find B, compute the point halfway between t1 and t2:
269
270 q(at (t1 + t2)/2) == D
271
272 Next, compute where D must be if we know the value of B:
273
274 _12 = A/2 + B/2
275 12_ = B/2 + C/2
276 123 = A/4 + B/2 + C/4
277 = D
278
279 Group the known values on one side:
280
281 B = D*2 - A/2 - C/2
282 */
283
284 // OPTIMIZE? : special case t1 = 1 && t2 = 0
subDivide(double t1,double t2) const285 SkDQuad SkDQuad::subDivide(double t1, double t2) const {
286 if (0 == t1 && 1 == t2) {
287 return *this;
288 }
289 SkDQuad dst;
290 double ax = dst[0].fX = interp_quad_coords(&fPts[0].fX, t1);
291 double ay = dst[0].fY = interp_quad_coords(&fPts[0].fY, t1);
292 double dx = interp_quad_coords(&fPts[0].fX, (t1 + t2) / 2);
293 double dy = interp_quad_coords(&fPts[0].fY, (t1 + t2) / 2);
294 double cx = dst[2].fX = interp_quad_coords(&fPts[0].fX, t2);
295 double cy = dst[2].fY = interp_quad_coords(&fPts[0].fY, t2);
296 /* bx = */ dst[1].fX = 2 * dx - (ax + cx) / 2;
297 /* by = */ dst[1].fY = 2 * dy - (ay + cy) / 2;
298 return dst;
299 }
300
align(int endIndex,SkDPoint * dstPt) const301 void SkDQuad::align(int endIndex, SkDPoint* dstPt) const {
302 if (fPts[endIndex].fX == fPts[1].fX) {
303 dstPt->fX = fPts[endIndex].fX;
304 }
305 if (fPts[endIndex].fY == fPts[1].fY) {
306 dstPt->fY = fPts[endIndex].fY;
307 }
308 }
309
subDivide(const SkDPoint & a,const SkDPoint & c,double t1,double t2) const310 SkDPoint SkDQuad::subDivide(const SkDPoint& a, const SkDPoint& c, double t1, double t2) const {
311 SkASSERT(t1 != t2);
312 SkDPoint b;
313 SkDQuad sub = subDivide(t1, t2);
314 SkDLine b0 = {{a, sub[1] + (a - sub[0])}};
315 SkDLine b1 = {{c, sub[1] + (c - sub[2])}};
316 SkIntersections i;
317 i.intersectRay(b0, b1);
318 if (i.used() == 1 && i[0][0] >= 0 && i[1][0] >= 0) {
319 b = i.pt(0);
320 } else {
321 SkASSERT(i.used() <= 2);
322 return SkDPoint::Mid(b0[1], b1[1]);
323 }
324 if (t1 == 0 || t2 == 0) {
325 align(0, &b);
326 }
327 if (t1 == 1 || t2 == 1) {
328 align(2, &b);
329 }
330 if (AlmostBequalUlps(b.fX, a.fX)) {
331 b.fX = a.fX;
332 } else if (AlmostBequalUlps(b.fX, c.fX)) {
333 b.fX = c.fX;
334 }
335 if (AlmostBequalUlps(b.fY, a.fY)) {
336 b.fY = a.fY;
337 } else if (AlmostBequalUlps(b.fY, c.fY)) {
338 b.fY = c.fY;
339 }
340 return b;
341 }
342
343 /* classic one t subdivision */
interp_quad_coords(const double * src,double * dst,double t)344 static void interp_quad_coords(const double* src, double* dst, double t) {
345 double ab = SkDInterp(src[0], src[2], t);
346 double bc = SkDInterp(src[2], src[4], t);
347 dst[0] = src[0];
348 dst[2] = ab;
349 dst[4] = SkDInterp(ab, bc, t);
350 dst[6] = bc;
351 dst[8] = src[4];
352 }
353
chopAt(double t) const354 SkDQuadPair SkDQuad::chopAt(double t) const
355 {
356 SkDQuadPair dst;
357 interp_quad_coords(&fPts[0].fX, &dst.pts[0].fX, t);
358 interp_quad_coords(&fPts[0].fY, &dst.pts[0].fY, t);
359 return dst;
360 }
361
valid_unit_divide(double numer,double denom,double * ratio)362 static int valid_unit_divide(double numer, double denom, double* ratio)
363 {
364 if (numer < 0) {
365 numer = -numer;
366 denom = -denom;
367 }
368 if (denom == 0 || numer == 0 || numer >= denom) {
369 return 0;
370 }
371 double r = numer / denom;
372 if (r == 0) { // catch underflow if numer <<<< denom
373 return 0;
374 }
375 *ratio = r;
376 return 1;
377 }
378
379 /** Quad'(t) = At + B, where
380 A = 2(a - 2b + c)
381 B = 2(b - a)
382 Solve for t, only if it fits between 0 < t < 1
383 */
FindExtrema(const double src[],double tValue[1])384 int SkDQuad::FindExtrema(const double src[], double tValue[1]) {
385 /* At + B == 0
386 t = -B / A
387 */
388 double a = src[0];
389 double b = src[2];
390 double c = src[4];
391 return valid_unit_divide(a - b, a - b - b + c, tValue);
392 }
393
394 /* Parameterization form, given A*t*t + 2*B*t*(1-t) + C*(1-t)*(1-t)
395 *
396 * a = A - 2*B + C
397 * b = 2*B - 2*C
398 * c = C
399 */
SetABC(const double * quad,double * a,double * b,double * c)400 void SkDQuad::SetABC(const double* quad, double* a, double* b, double* c) {
401 *a = quad[0]; // a = A
402 *b = 2 * quad[2]; // b = 2*B
403 *c = quad[4]; // c = C
404 *b -= *c; // b = 2*B - C
405 *a -= *b; // a = A - 2*B + C
406 *b -= *c; // b = 2*B - 2*C
407 }
408
intersectRay(SkIntersections * i,const SkDLine & line) const409 int SkTQuad::intersectRay(SkIntersections* i, const SkDLine& line) const {
410 return i->intersectRay(fQuad, line);
411 }
412
hullIntersects(const SkDConic & conic,bool * isLinear) const413 bool SkTQuad::hullIntersects(const SkDConic& conic, bool* isLinear) const {
414 return conic.hullIntersects(fQuad, isLinear);
415 }
416
hullIntersects(const SkDCubic & cubic,bool * isLinear) const417 bool SkTQuad::hullIntersects(const SkDCubic& cubic, bool* isLinear) const {
418 return cubic.hullIntersects(fQuad, isLinear);
419 }
420
setBounds(SkDRect * rect) const421 void SkTQuad::setBounds(SkDRect* rect) const {
422 rect->setBounds(fQuad);
423 }
424