1 /* 2 * Copyright (C) 2010 Google Inc. All rights reserved. 3 * 4 * Redistribution and use in source and binary forms, with or without 5 * modification, are permitted provided that the following conditions 6 * are met: 7 * 8 * 1. Redistributions of source code must retain the above copyright 9 * notice, this list of conditions and the following disclaimer. 10 * 2. Redistributions in binary form must reproduce the above copyright 11 * notice, this list of conditions and the following disclaimer in the 12 * documentation and/or other materials provided with the distribution. 13 * 14 * THIS SOFTWARE IS PROVIDED BY APPLE AND ITS CONTRIBUTORS "AS IS" AND ANY 15 * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED 16 * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE 17 * DISCLAIMED. IN NO EVENT SHALL APPLE OR ITS CONTRIBUTORS BE LIABLE FOR ANY 18 * DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES 19 * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; 20 * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND 21 * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 22 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF 23 * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 24 */ 25 26 #include "config.h" 27 28 #if ENABLE(ACCELERATED_2D_CANVAS) 29 30 #include "LoopBlinnMathUtils.h" 31 32 #include "FloatPoint.h" 33 #include <algorithm> 34 #include <wtf/MathExtras.h> 35 36 namespace WebCore { 37 namespace LoopBlinnMathUtils { 38 39 namespace { 40 41 // Utility functions local to this file. 42 int orientation(const FloatPoint& p1, 43 const FloatPoint& p2, 44 const FloatPoint& p3) 45 { 46 float crossProduct = (p2.y() - p1.y()) * (p3.x() - p2.x()) - (p3.y() - p2.y()) * (p2.x() - p1.x()); 47 return (crossProduct < 0.0f) ? -1 : ((crossProduct > 0.0f) ? 1 : 0); 48 } 49 50 bool edgeEdgeTest(const FloatSize& v0Delta, 51 const FloatPoint& v0, 52 const FloatPoint& u0, 53 const FloatPoint& u1) 54 { 55 // This edge to edge test is based on Franlin Antonio's gem: "Faster 56 // Line Segment Intersection", in Graphics Gems III, pp. 199-202. 57 float ax = v0Delta.width(); 58 float ay = v0Delta.height(); 59 float bx = u0.x() - u1.x(); 60 float by = u0.y() - u1.y(); 61 float cx = v0.x() - u0.x(); 62 float cy = v0.y() - u0.y(); 63 float f = ay * bx - ax * by; 64 float d = by * cx - bx * cy; 65 if ((f > 0 && d >= 0 && d <= f) || (f < 0 && d <= 0 && d >= f)) { 66 float e = ax * cy - ay * cx; 67 68 // This additional test avoids reporting coincident edges, which 69 // is the behavior we want. 70 if (approxEqual(e, 0) || approxEqual(f, 0) || approxEqual(e, f)) 71 return false; 72 73 if (f > 0) 74 return e >= 0 && e <= f; 75 76 return e <= 0 && e >= f; 77 } 78 return false; 79 } 80 81 bool edgeAgainstTriangleEdges(const FloatPoint& v0, 82 const FloatPoint& v1, 83 const FloatPoint& u0, 84 const FloatPoint& u1, 85 const FloatPoint& u2) 86 { 87 FloatSize delta = v1 - v0; 88 // Test edge u0, u1 against v0, v1. 89 if (edgeEdgeTest(delta, v0, u0, u1)) 90 return true; 91 // Test edge u1, u2 against v0, v1. 92 if (edgeEdgeTest(delta, v0, u1, u2)) 93 return true; 94 // Test edge u2, u1 against v0, v1. 95 if (edgeEdgeTest(delta, v0, u2, u0)) 96 return true; 97 return false; 98 } 99 100 // A roundoff factor in the cubic classification and texture coordinate 101 // generation algorithms. It primarily determines the handling of corner 102 // cases during the classification process. Be careful when adjusting it; 103 // it has been determined empirically to work well. When changing it, you 104 // should look in particular at shapes that contain quadratic curves and 105 // ensure they still look smooth. Once pixel tests are running against this 106 // algorithm, they should provide sufficient coverage to ensure that 107 // adjusting the constant won't break anything. 108 const float Epsilon = 5.0e-4f; 109 110 } // anonymous namespace 111 112 // Exported routines 113 114 float roundToZero(float val) 115 { 116 if (val < Epsilon && val > -Epsilon) 117 return 0; 118 return val; 119 } 120 121 bool approxEqual(const FloatPoint& v0, const FloatPoint& v1) 122 { 123 return (v0 - v1).diagonalLengthSquared() < Epsilon * Epsilon; 124 } 125 126 bool approxEqual(const FloatPoint3D& v0, const FloatPoint3D& v1) 127 { 128 return (v0 - v1).lengthSquared() < Epsilon * Epsilon; 129 } 130 131 bool approxEqual(float f0, float f1) 132 { 133 return fabsf(f0 - f1) < Epsilon; 134 } 135 136 bool linesIntersect(const FloatPoint& p1, 137 const FloatPoint& q1, 138 const FloatPoint& p2, 139 const FloatPoint& q2) 140 { 141 return (orientation(p1, q1, p2) != orientation(p1, q1, q2) 142 && orientation(p2, q2, p1) != orientation(p2, q2, q1)); 143 } 144 145 bool pointInTriangle(const FloatPoint& point, 146 const FloatPoint& a, 147 const FloatPoint& b, 148 const FloatPoint& c) 149 { 150 // Algorithm from http://www.blackpawn.com/texts/pointinpoly/default.html 151 float x0 = c.x() - a.x(); 152 float y0 = c.y() - a.y(); 153 float x1 = b.x() - a.x(); 154 float y1 = b.y() - a.y(); 155 float x2 = point.x() - a.x(); 156 float y2 = point.y() - a.y(); 157 158 float dot00 = x0 * x0 + y0 * y0; 159 float dot01 = x0 * x1 + y0 * y1; 160 float dot02 = x0 * x2 + y0 * y2; 161 float dot11 = x1 * x1 + y1 * y1; 162 float dot12 = x1 * x2 + y1 * y2; 163 float denominator = dot00 * dot11 - dot01 * dot01; 164 if (!denominator) 165 // Triangle is zero-area. Treat query point as not being inside. 166 return false; 167 // Compute 168 float inverseDenominator = 1.0f / denominator; 169 float u = (dot11 * dot02 - dot01 * dot12) * inverseDenominator; 170 float v = (dot00 * dot12 - dot01 * dot02) * inverseDenominator; 171 172 return (u > 0.0f) && (v > 0.0f) && (u + v < 1.0f); 173 } 174 175 bool trianglesOverlap(const FloatPoint& a1, 176 const FloatPoint& b1, 177 const FloatPoint& c1, 178 const FloatPoint& a2, 179 const FloatPoint& b2, 180 const FloatPoint& c2) 181 { 182 // Derived from coplanar_tri_tri() at 183 // http://jgt.akpeters.com/papers/ShenHengTang03/tri_tri.html , 184 // simplified for the 2D case and modified so that overlapping edges 185 // do not report overlapping triangles. 186 187 // Test all edges of triangle 1 against the edges of triangle 2. 188 if (edgeAgainstTriangleEdges(a1, b1, a2, b2, c2) 189 || edgeAgainstTriangleEdges(b1, c1, a2, b2, c2) 190 || edgeAgainstTriangleEdges(c1, a1, a2, b2, c2)) 191 return true; 192 // Finally, test if tri1 is totally contained in tri2 or vice versa. 193 // The paper above only performs the first two point-in-triangle tests. 194 // Because we define that triangles sharing a vertex or edge don't 195 // overlap, we must perform additional tests to see whether one 196 // triangle is contained in the other. 197 if (pointInTriangle(a1, a2, b2, c2) 198 || pointInTriangle(a2, a1, b1, c1) 199 || pointInTriangle(b1, a2, b2, c2) 200 || pointInTriangle(b2, a1, b1, c1) 201 || pointInTriangle(c1, a2, b2, c2) 202 || pointInTriangle(c2, a1, b1, c1)) 203 return true; 204 return false; 205 } 206 207 namespace { 208 209 // Helper routines for public XRay queries below. All of this code 210 // originated in Skia; see include/core/ and src/core/, SkScalar.h and 211 // SkGeometry.{cpp,h}. 212 213 const float NearlyZeroConstant = (1.0f / (1 << 12)); 214 215 bool nearlyZero(float x, float tolerance = NearlyZeroConstant) 216 { 217 ASSERT(tolerance > 0.0f); 218 return ::fabsf(x) < tolerance; 219 } 220 221 // Linearly interpolate between a and b, based on t. 222 // If t is 0, return a; if t is 1, return b; else interpolate. 223 // t must be [0..1]. 224 float interpolate(float a, float b, float t) 225 { 226 ASSERT(t >= 0 && t <= 1); 227 return a + (b - a) * t; 228 } 229 230 float evaluateCubic(float controlPoint0, float controlPoint1, float controlPoint2, float controlPoint3, float t) 231 { 232 ASSERT(t >= 0 && t <= 1); 233 234 if (!t) 235 return controlPoint0; 236 237 float ab = interpolate(controlPoint0, controlPoint1, t); 238 float bc = interpolate(controlPoint1, controlPoint2, t); 239 float cd = interpolate(controlPoint2, controlPoint3, t); 240 float abc = interpolate(ab, bc, t); 241 float bcd = interpolate(bc, cd, t); 242 return interpolate(abc, bcd, t); 243 } 244 245 // Evaluates the point on the source cubic specified by t, 0 <= t <= 1.0. 246 FloatPoint evaluateCubicAt(const FloatPoint cubic[4], float t) 247 { 248 return FloatPoint(evaluateCubic(cubic[0].x(), cubic[1].x(), cubic[2].x(), cubic[3].x(), t), 249 evaluateCubic(cubic[0].y(), cubic[1].y(), cubic[2].y(), cubic[3].y(), t)); 250 } 251 252 bool xRayCrossesMonotonicCubic(const XRay& xRay, const FloatPoint cubic[4], bool& ambiguous) 253 { 254 ambiguous = false; 255 256 // Find the minimum and maximum y of the extrema, which are the 257 // first and last points since this cubic is monotonic 258 float minY = std::min(cubic[0].y(), cubic[3].y()); 259 float maxY = std::max(cubic[0].y(), cubic[3].y()); 260 261 if (xRay.y() == cubic[0].y() 262 || xRay.y() < minY 263 || xRay.y() > maxY) { 264 // The query line definitely does not cross the curve 265 ambiguous = (xRay.y() == cubic[0].y()); 266 return false; 267 } 268 269 const bool pointAtExtremum = (xRay.y() == cubic[3].y()); 270 271 float minX = std::min(std::min(std::min(cubic[0].x(), cubic[1].x()), 272 cubic[2].x()), 273 cubic[3].x()); 274 if (xRay.x() < minX) { 275 // The query line definitely crosses the curve 276 ambiguous = pointAtExtremum; 277 return true; 278 } 279 280 float maxX = std::max(std::max(std::max(cubic[0].x(), cubic[1].x()), 281 cubic[2].x()), 282 cubic[3].x()); 283 if (xRay.x() > maxX) 284 // The query line definitely does not cross the curve 285 return false; 286 287 // Do a binary search to find the parameter value which makes y as 288 // close as possible to the query point. See whether the query 289 // line's origin is to the left of the associated x coordinate. 290 291 // MaxIterations is chosen as the number of mantissa bits for a float, 292 // since there's no way we are going to get more precision by 293 // iterating more times than that. 294 const int MaxIterations = 23; 295 FloatPoint evaluatedPoint; 296 int iter = 0; 297 float upperT; 298 float lowerT; 299 // Need to invert direction of t parameter if cubic goes up 300 // instead of down 301 if (cubic[3].y() > cubic[0].y()) { 302 upperT = 1; 303 lowerT = 0; 304 } else { 305 upperT = 0; 306 lowerT = 1; 307 } 308 do { 309 float t = 0.5f * (upperT + lowerT); 310 evaluatedPoint = evaluateCubicAt(cubic, t); 311 if (xRay.y() > evaluatedPoint.y()) 312 lowerT = t; 313 else 314 upperT = t; 315 } while (++iter < MaxIterations && !nearlyZero(evaluatedPoint.y() - xRay.y())); 316 317 // FIXME: once we have more regression tests for this code, 318 // determine whether this should be using a fuzzy test. 319 if (xRay.x() <= evaluatedPoint.x()) { 320 ambiguous = pointAtExtremum; 321 return true; 322 } 323 return false; 324 } 325 326 // Divides the numerator by the denominator safely for the case where 327 // the result must lie in the range (0..1). Result indicates whether 328 // the result is valid. 329 bool safeUnitDivide(float numerator, float denominator, float& ratio) 330 { 331 if (numerator < 0) { 332 // Make the "numerator >= denominator" check below work. 333 numerator = -numerator; 334 denominator = -denominator; 335 } 336 if (!numerator || !denominator || numerator >= denominator) 337 return false; 338 float r = numerator / denominator; 339 if (isnan(r)) 340 return false; 341 ASSERT(r >= 0 && r < 1); 342 if (!r) // catch underflow if numerator <<<< denominator 343 return false; 344 ratio = r; 345 return true; 346 } 347 348 // From Numerical Recipes in C. 349 // 350 // q = -1/2 (b + sign(b) sqrt[b*b - 4*a*c]) 351 // x1 = q / a 352 // x2 = c / q 353 // 354 // Returns the number of real roots of the equation [0..2]. Roots are 355 // returned in sorted order, smaller root first. 356 int findUnitQuadRoots(float a, float b, float c, float roots[2]) 357 { 358 if (!a) 359 return safeUnitDivide(-c, b, roots[0]) ? 1 : 0; 360 361 float discriminant = b*b - 4*a*c; 362 if (discriminant < 0 || isnan(discriminant)) // complex roots 363 return 0; 364 discriminant = sqrtf(discriminant); 365 366 float q = (b < 0) ? -(b - discriminant) / 2 : -(b + discriminant) / 2; 367 int numberOfRoots = 0; 368 if (safeUnitDivide(q, a, roots[numberOfRoots])) 369 ++numberOfRoots; 370 if (safeUnitDivide(c, q, roots[numberOfRoots])) 371 ++numberOfRoots; 372 if (numberOfRoots == 2) { 373 // Seemingly have two roots. Check for equality and sort. 374 if (roots[0] == roots[1]) 375 return 1; 376 if (roots[0] > roots[1]) 377 std::swap(roots[0], roots[1]); 378 } 379 return numberOfRoots; 380 } 381 382 // Cubic'(t) = pt^2 + qt + r, where 383 // p = 3(-a + 3(b - c) + d) 384 // q = 6(a - 2b + c) 385 // r = 3(b - a) 386 // Solve for t, keeping only those that fit between 0 < t < 1. 387 int findCubicExtrema(float a, float b, float c, float d, float tValues[2]) 388 { 389 // Divide p, q, and r by 3 to simplify the equations. 390 float p = d - a + 3*(b - c); 391 float q = 2*(a - b - b + c); 392 float r = b - a; 393 394 return findUnitQuadRoots(p, q, r, tValues); 395 } 396 397 void interpolateCubicCoords(float controlPoint0, float controlPoint1, float controlPoint2, float controlPoint3, float* dst, float t) 398 { 399 float ab = interpolate(controlPoint0, controlPoint1, t); 400 float bc = interpolate(controlPoint1, controlPoint2, t); 401 float cd = interpolate(controlPoint2, controlPoint3, t); 402 float abc = interpolate(ab, bc, t); 403 float bcd = interpolate(bc, cd, t); 404 float abcd = interpolate(abc, bcd, t); 405 406 dst[0] = controlPoint0; 407 dst[2] = ab; 408 dst[4] = abc; 409 dst[6] = abcd; 410 dst[8] = bcd; 411 dst[10] = cd; 412 dst[12] = controlPoint3; 413 } 414 415 #ifndef NDEBUG 416 bool isUnitInterval(float x) 417 { 418 return x > 0 && x < 1; 419 } 420 #endif 421 422 void chopCubicAtTValues(const FloatPoint src[4], FloatPoint dst[], const float tValues[], int roots) 423 { 424 #ifndef NDEBUG 425 for (int i = 0; i < roots - 1; ++i) { 426 ASSERT(isUnitInterval(tValues[i])); 427 ASSERT(isUnitInterval(tValues[i+1])); 428 ASSERT(tValues[i] < tValues[i+1]); 429 } 430 #endif 431 432 if (!roots) { 433 // nothing to chop 434 for (int j = 0; j < 4; ++j) 435 dst[j] = src[j]; 436 return; 437 } 438 439 float t = tValues[0]; 440 FloatPoint tmp[4]; 441 for (int j = 0; j < 4; ++j) 442 tmp[j] = src[j]; 443 444 for (int i = 0; i < roots; ++i) { 445 chopCubicAt(tmp, dst, t); 446 if (i == roots - 1) 447 break; 448 449 dst += 3; 450 // Make tmp contain the remaining cubic (after the first chop). 451 for (int j = 0; j < 4; ++j) 452 tmp[j] = dst[j]; 453 454 // Watch out for the case that the renormalized t isn't in range. 455 if (!safeUnitDivide(tValues[i+1] - tValues[i], 1.0f - tValues[i], t)) { 456 // If it isn't, just create a degenerate cubic. 457 dst[4] = dst[5] = dst[6] = tmp[3]; 458 break; 459 } 460 } 461 } 462 463 void flattenDoubleCubicYExtrema(FloatPoint coords[7]) 464 { 465 coords[2].setY(coords[3].y()); 466 coords[4].setY(coords[3].y()); 467 } 468 469 int chopCubicAtYExtrema(const FloatPoint src[4], FloatPoint dst[10]) 470 { 471 float tValues[2]; 472 int roots = findCubicExtrema(src[0].y(), src[1].y(), src[2].y(), src[3].y(), tValues); 473 474 chopCubicAtTValues(src, dst, tValues, roots); 475 if (roots) { 476 // we do some cleanup to ensure our Y extrema are flat 477 flattenDoubleCubicYExtrema(&dst[0]); 478 if (roots == 2) 479 flattenDoubleCubicYExtrema(&dst[3]); 480 } 481 return roots; 482 } 483 484 } // anonymous namespace 485 486 // Public cubic operations. 487 488 void chopCubicAt(const FloatPoint src[4], FloatPoint dst[7], float t) 489 { 490 ASSERT(t >= 0 && t <= 1); 491 492 float output[14]; 493 interpolateCubicCoords(src[0].x(), src[1].x(), src[2].x(), src[3].x(), &output[0], t); 494 interpolateCubicCoords(src[0].y(), src[1].y(), src[2].y(), src[3].y(), &output[1], t); 495 for (int i = 0; i < 7; i++) 496 dst[i].set(output[2 * i], output[2 * i + 1]); 497 } 498 499 // Public XRay queries. 500 501 bool xRayCrossesLine(const XRay& xRay, const FloatPoint pts[2], bool& ambiguous) 502 { 503 ambiguous = false; 504 505 // Determine quick discards. 506 // Consider query line going exactly through point 0 to not 507 // intersect, for symmetry with xRayCrossesMonotonicCubic. 508 if (xRay.y() == pts[0].y()) { 509 ambiguous = true; 510 return false; 511 } 512 if (xRay.y() < pts[0].y() && xRay.y() < pts[1].y()) 513 return false; 514 if (xRay.y() > pts[0].y() && xRay.y() > pts[1].y()) 515 return false; 516 if (xRay.x() > pts[0].x() && xRay.x() > pts[1].x()) 517 return false; 518 // Determine degenerate cases 519 if (nearlyZero(pts[0].y() - pts[1].y())) 520 return false; 521 if (nearlyZero(pts[0].x() - pts[1].x())) { 522 // We've already determined the query point lies within the 523 // vertical range of the line segment. 524 if (xRay.x() <= pts[0].x()) { 525 ambiguous = (xRay.y() == pts[1].y()); 526 return true; 527 } 528 return false; 529 } 530 // Ambiguity check 531 if (xRay.y() == pts[1].y()) { 532 if (xRay.x() <= pts[1].x()) { 533 ambiguous = true; 534 return true; 535 } 536 return false; 537 } 538 // Full line segment evaluation 539 float deltaY = pts[1].y() - pts[0].y(); 540 float deltaX = pts[1].x() - pts[0].x(); 541 float slope = deltaY / deltaX; 542 float b = pts[0].y() - slope * pts[0].x(); 543 // Solve for x coordinate at y = xRay.y() 544 float x = (xRay.y() - b) / slope; 545 return xRay.x() <= x; 546 } 547 548 int numXRayCrossingsForCubic(const XRay& xRay, const FloatPoint cubic[4], bool& ambiguous) 549 { 550 int numCrossings = 0; 551 FloatPoint monotonicCubics[10]; 552 int numMonotonicCubics = 1 + chopCubicAtYExtrema(cubic, monotonicCubics); 553 ambiguous = false; 554 FloatPoint* monotonicCubicsPointer = &monotonicCubics[0]; 555 for (int i = 0; i < numMonotonicCubics; ++i) { 556 if (xRayCrossesMonotonicCubic(xRay, monotonicCubicsPointer, ambiguous)) 557 ++numCrossings; 558 if (ambiguous) 559 return 0; 560 monotonicCubicsPointer += 3; 561 } 562 return numCrossings; 563 } 564 565 /* 566 * Based on C code from the article 567 * "Testing the Convexity of a Polygon" 568 * by Peter Schorn and Frederick Fisher, 569 * (schorn (at) inf.ethz.ch, fred (at) kpc.com) 570 * in "Graphics Gems IV", Academic Press, 1994 571 */ 572 573 static inline int convexCompare(const FloatSize& delta) 574 { 575 return (delta.width() > 0) ? -1 : /* x coord diff, second pt > first pt */ 576 (delta.width() < 0) ? 1 : /* x coord diff, second pt < first pt */ 577 (delta.height() > 0) ? -1 : /* x coord same, second pt > first pt */ 578 (delta.height() < 0) ? 1 : /* x coord same, second pt > first pt */ 579 0; /* second pt equals first point */ 580 } 581 582 static inline float convexCross(const FloatSize& p, const FloatSize& q) 583 { 584 return p.width() * q.height() - p.height() * q.width(); 585 } 586 587 static inline bool convexCheckTriple(const FloatSize& dcur, const FloatSize& dprev, int* curDir, int* dirChanges, int* angleSign) 588 { 589 int thisDir = convexCompare(dcur); 590 if (thisDir == -*curDir) 591 ++*dirChanges; 592 *curDir = thisDir; 593 float cross = convexCross(dprev, dcur); 594 if (cross > 0) { 595 if (*angleSign == -1) 596 return false; 597 *angleSign = 1; 598 } else if (cross < 0) { 599 if (*angleSign == 1) 600 return false; 601 *angleSign = -1; 602 } 603 return true; 604 } 605 606 bool isConvex(const FloatPoint* vertices, int nVertices) 607 { 608 int dirChanges = 0, angleSign = 0; 609 FloatPoint second, third; 610 FloatSize dprev, dcur; 611 612 /* Get different point, return if less than 3 diff points. */ 613 if (nVertices < 3) 614 return false; 615 int i = 1; 616 while (true) { 617 second = vertices[i++]; 618 dprev = second - vertices[0]; 619 if (dprev.width() || dprev.height()) 620 break; 621 /* Check if out of points. Check here to avoid slowing down cases 622 * without repeated points. 623 */ 624 if (i >= nVertices) 625 return false; 626 } 627 FloatPoint saveSecond = second; 628 int curDir = convexCompare(dprev); /* Find initial direction */ 629 while (i < nVertices) { 630 /* Get different point, break if no more points */ 631 third = vertices[i++]; 632 dcur = third - second; 633 if (!dcur.width() && !dcur.height()) 634 continue; 635 636 /* Check current three points */ 637 if (!convexCheckTriple(dcur, dprev, &curDir, &dirChanges, &angleSign)) 638 return false; 639 second = third; /* Remember ptr to current point. */ 640 dprev = dcur; /* Remember current delta. */ 641 } 642 643 /* Must check for direction changes from last vertex back to first */ 644 third = vertices[0]; /* Prepare for 'ConvexCheckTriple' */ 645 dcur = third - second; 646 if (convexCompare(dcur)) { 647 if (!convexCheckTriple(dcur, dprev, &curDir, &dirChanges, &angleSign)) 648 return false; 649 second = third; /* Remember ptr to current point. */ 650 dprev = dcur; /* Remember current delta. */ 651 } 652 653 /* and check for direction changes back to second vertex */ 654 dcur = saveSecond - second; 655 if (!convexCheckTriple(dcur, dprev, &curDir, &dirChanges, &angleSign)) 656 return false; 657 658 /* Decide on polygon type given accumulated status */ 659 if (dirChanges > 2) 660 return false; 661 662 if (angleSign > 0 || angleSign < 0) 663 return true; 664 return false; 665 } 666 667 } // namespace LoopBlinnMathUtils 668 } // namespace WebCore 669 670 #endif 671