code.vuplus.com Git - vuplus_webkit/blob - Source/WebCore/platform/graphics/gpu/LoopBlinnMathUtils.cpp

   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 USE(ACCELERATED_COMPOSITING) || 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@inf.ethz.ch, fred@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