2010-09-09 Kenneth Russell <kbr@google.com>
authorkbr@google.com <kbr@google.com@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Fri, 10 Sep 2010 02:32:07 +0000 (02:32 +0000)
committerkbr@google.com <kbr@google.com@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Fri, 10 Sep 2010 02:32:07 +0000 (02:32 +0000)
        Reviewed by James Robinson.

        Add math utilities for cubic curve processing
        https://bugs.webkit.org/show_bug.cgi?id=45251

        Adding mathematic utilities needed for the GPU accelerated path
        rendering algorithm from GPU Gems 3. No tests yet; will be tested
        in conjunction with later code.

        * platform/graphics/gpu/LoopBlinnMathUtils.cpp: Added.
        (WebCore::LoopBlinnMathUtils::roundToZero):
        (WebCore::LoopBlinnMathUtils::approxEqual):
        (WebCore::LoopBlinnMathUtils::linesIntersect):
        (WebCore::LoopBlinnMathUtils::pointInTriangle):
        (WebCore::LoopBlinnMathUtils::trianglesOverlap):
        (WebCore::LoopBlinnMathUtils::chopCubicAt):
        (WebCore::LoopBlinnMathUtils::xRayCrossesLine):
        (WebCore::LoopBlinnMathUtils::numXRayCrossingsForCubic):
        * platform/graphics/gpu/LoopBlinnMathUtils.h: Added.

git-svn-id: http://svn.webkit.org/repository/webkit/trunk@67150 268f45cc-cd09-0410-ab3c-d52691b4dbfc

WebCore/ChangeLog
WebCore/platform/graphics/gpu/LoopBlinnMathUtils.cpp [new file with mode: 0644]
WebCore/platform/graphics/gpu/LoopBlinnMathUtils.h [new file with mode: 0644]

index f300af92f104047a16d6806e17c9601ee286ae9e..a38418ef95213dcce372bac801d70c8804b395a0 100644 (file)
@@ -1,3 +1,25 @@
+2010-09-09  Kenneth Russell  <kbr@google.com>
+
+        Reviewed by James Robinson.
+
+        Add math utilities for cubic curve processing
+        https://bugs.webkit.org/show_bug.cgi?id=45251
+
+        Adding mathematic utilities needed for the GPU accelerated path
+        rendering algorithm from GPU Gems 3. No tests yet; will be tested
+        in conjunction with later code.
+
+        * platform/graphics/gpu/LoopBlinnMathUtils.cpp: Added.
+        (WebCore::LoopBlinnMathUtils::roundToZero):
+        (WebCore::LoopBlinnMathUtils::approxEqual):
+        (WebCore::LoopBlinnMathUtils::linesIntersect):
+        (WebCore::LoopBlinnMathUtils::pointInTriangle):
+        (WebCore::LoopBlinnMathUtils::trianglesOverlap):
+        (WebCore::LoopBlinnMathUtils::chopCubicAt):
+        (WebCore::LoopBlinnMathUtils::xRayCrossesLine):
+        (WebCore::LoopBlinnMathUtils::numXRayCrossingsForCubic):
+        * platform/graphics/gpu/LoopBlinnMathUtils.h: Added.
+
 2010-09-09  Kinuko Yasuda  <kinuko@chromium.org>
 
         Reviewed by Dumitru Daniliuc.
diff --git a/WebCore/platform/graphics/gpu/LoopBlinnMathUtils.cpp b/WebCore/platform/graphics/gpu/LoopBlinnMathUtils.cpp
new file mode 100644 (file)
index 0000000..61ebc9b
--- /dev/null
@@ -0,0 +1,565 @@
+/*
+ * Copyright (C) 2010 Google Inc. All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ *
+ * 1.  Redistributions of source code must retain the above copyright
+ *     notice, this list of conditions and the following disclaimer.
+ * 2.  Redistributions in binary form must reproduce the above copyright
+ *     notice, this list of conditions and the following disclaimer in the
+ *     documentation and/or other materials provided with the distribution.
+ *
+ * THIS SOFTWARE IS PROVIDED BY APPLE AND ITS CONTRIBUTORS "AS IS" AND ANY
+ * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
+ * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
+ * DISCLAIMED. IN NO EVENT SHALL APPLE OR ITS CONTRIBUTORS BE LIABLE FOR ANY
+ * DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
+ * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
+ * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
+ * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
+ * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
+ * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+ */
+
+#include "config.h"
+
+#include "LoopBlinnMathUtils.h"
+
+#include "FloatPoint.h"
+#include "MathExtras.h"
+#include <algorithm>
+#include <string.h> // for memcpy
+
+namespace WebCore {
+namespace LoopBlinnMathUtils {
+
+namespace {
+
+// Utility functions local to this file.
+int orientation(const FloatPoint& p1,
+                const FloatPoint& p2,
+                const FloatPoint& p3)
+{
+    float crossProduct = (p2.y() - p1.y()) * (p3.x() - p2.x()) - (p3.y() - p2.y()) * (p2.x() - p1.x());
+    return (crossProduct < 0.0f) ? -1 : ((crossProduct > 0.0f) ? 1 : 0);
+}
+
+bool edgeEdgeTest(const FloatSize& v0Delta,
+                  const FloatPoint& v0,
+                  const FloatPoint& u0,
+                  const FloatPoint& u1)
+{
+    // This edge to edge test is based on Franlin Antonio's gem: "Faster
+    // Line Segment Intersection", in Graphics Gems III, pp. 199-202.
+    float ax = v0Delta.width();
+    float ay = v0Delta.height();
+    float bx = u0.x() - u1.x();
+    float by = u0.y() - u1.y();
+    float cx = v0.x() - u0.x();
+    float cy = v0.y() - u0.y();
+    float f = ay * bx - ax * by;
+    float d = by * cx - bx * cy;
+    if ((f > 0 && d >= 0 && d <= f) || (f < 0 && d <= 0 && d >= f)) {
+        float e = ax * cy - ay * cx;
+
+        // This additional test avoids reporting coincident edges, which
+        // is the behavior we want.
+        if (approxEqual(e, 0) || approxEqual(f, 0) || approxEqual(e, f))
+            return false;
+
+        if (f > 0)
+            return e >= 0 && e <= f;
+
+        return e <= 0 && e >= f;
+    }
+    return false;
+}
+
+bool edgeAgainstTriangleEdges(const FloatPoint& v0,
+                              const FloatPoint& v1,
+                              const FloatPoint& u0,
+                              const FloatPoint& u1,
+                              const FloatPoint& u2)
+{
+    FloatSize delta = v1 - v0;
+    // Test edge u0, u1 against v0, v1.
+    if (edgeEdgeTest(delta, v0, u0, u1))
+        return true;
+    // Test edge u1, u2 against v0, v1.
+    if (edgeEdgeTest(delta, v0, u1, u2))
+        return true;
+    // Test edge u2, u1 against v0, v1.
+    if (edgeEdgeTest(delta, v0, u2, u0))
+        return true;
+    return false;
+}
+
+// A roundoff factor in the cubic classification and texture coordinate
+// generation algorithms. It primarily determines the handling of corner
+// cases during the classification process. Be careful when adjusting it;
+// it has been determined empirically to work well. When changing it, you
+// should look in particular at shapes that contain quadratic curves and
+// ensure they still look smooth. Once pixel tests are running against this
+// algorithm, they should provide sufficient coverage to ensure that
+// adjusting the constant won't break anything.
+const float Epsilon = 5.0e-4f;
+
+} // anonymous namespace
+
+// Exported routines
+
+float roundToZero(float val)
+{
+    if (val < Epsilon && val > -Epsilon)
+        return 0;
+    return val;
+}
+
+bool approxEqual(const FloatPoint& v0, const FloatPoint& v1)
+{
+    return (v0 - v1).diagonalLengthSquared() < Epsilon * Epsilon;
+}
+
+bool approxEqual(const FloatPoint3D& v0, const FloatPoint3D& v1)
+{
+    return (v0 - v1).lengthSquared() < Epsilon * Epsilon;
+}
+
+bool approxEqual(float f0, float f1)
+{
+    return fabsf(f0 - f1) < Epsilon;
+}
+
+bool linesIntersect(const FloatPoint& p1,
+                    const FloatPoint& q1,
+                    const FloatPoint& p2,
+                    const FloatPoint& q2)
+{
+    return (orientation(p1, q1, p2) != orientation(p1, q1, q2)
+            && orientation(p2, q2, p1) != orientation(p2, q2, q1));
+}
+
+bool pointInTriangle(const FloatPoint& point,
+                     const FloatPoint& a,
+                     const FloatPoint& b,
+                     const FloatPoint& c)
+{
+    // Algorithm from http://www.blackpawn.com/texts/pointinpoly/default.html
+    float x0 = c.x() - a.x();
+    float y0 = c.y() - a.y();
+    float x1 = b.x() - a.x();
+    float y1 = b.y() - a.y();
+    float x2 = point.x() - a.x();
+    float y2 = point.y() - a.y();
+
+    float dot00 = x0 * x0 + y0 * y0;
+    float dot01 = x0 * x1 + y0 * y1;
+    float dot02 = x0 * x2 + y0 * y2;
+    float dot11 = x1 * x1 + y1 * y1;
+    float dot12 = x1 * x2 + y1 * y2;
+    float denominator = dot00 * dot11 - dot01 * dot01;
+    if (!denominator)
+        // Triangle is zero-area. Treat query point as not being inside.
+        return false;
+    // Compute
+    float inverseDenominator = 1.0f / denominator;
+    float u = (dot11 * dot02 - dot01 * dot12) * inverseDenominator;
+    float v = (dot00 * dot12 - dot01 * dot02) * inverseDenominator;
+
+    return (u > 0.0f) && (v > 0.0f) && (u + v < 1.0f);
+}
+
+bool trianglesOverlap(const FloatPoint& a1,
+                      const FloatPoint& b1,
+                      const FloatPoint& c1,
+                      const FloatPoint& a2,
+                      const FloatPoint& b2,
+                      const FloatPoint& c2)
+{
+    // Derived from coplanar_tri_tri() at
+    // http://jgt.akpeters.com/papers/ShenHengTang03/tri_tri.html ,
+    // simplified for the 2D case and modified so that overlapping edges
+    // do not report overlapping triangles.
+
+    // Test all edges of triangle 1 against the edges of triangle 2.
+    if (edgeAgainstTriangleEdges(a1, b1, a2, b2, c2)
+        || edgeAgainstTriangleEdges(b1, c1, a2, b2, c2)
+        || edgeAgainstTriangleEdges(c1, a1, a2, b2, c2))
+        return true;
+    // Finally, test if tri1 is totally contained in tri2 or vice versa.
+    // The paper above only performs the first two point-in-triangle tests.
+    // Because we define that triangles sharing a vertex or edge don't
+    // overlap, we must perform additional tests to see whether one
+    // triangle is contained in the other.
+    if (pointInTriangle(a1, a2, b2, c2)
+        || pointInTriangle(a2, a1, b1, c1)
+        || pointInTriangle(b1, a2, b2, c2)
+        || pointInTriangle(b2, a1, b1, c1)
+        || pointInTriangle(c1, a2, b2, c2)
+        || pointInTriangle(c2, a1, b1, c1))
+        return true;
+    return false;
+}
+
+namespace {
+
+// Helper routines for public XRay queries below. All of this code
+// originated in Skia; see include/core/ and src/core/, SkScalar.h and
+// SkGeometry.{cpp,h}.
+
+const float NearlyZeroConstant = (1.0f / (1 << 12));
+
+bool nearlyZero(float x, float tolerance = NearlyZeroConstant)
+{
+    ASSERT(tolerance > 0.0f);
+    return ::fabsf(x) < tolerance;
+}
+
+// Linearly interpolate between a and b, based on t.
+// If t is 0, return a; if t is 1, return b; else interpolate.
+// t must be [0..1].
+float interpolate(float a, float b, float t)
+{
+    ASSERT(t >= 0 && t <= 1);
+    return a + (b - a) * t;
+}
+
+float evaluateCubic(float controlPoint0, float controlPoint1, float controlPoint2, float controlPoint3, float t)
+{
+    ASSERT(t >= 0 && t <= 1);
+
+    if (!t)
+        return controlPoint0;
+
+    float ab = interpolate(controlPoint0, controlPoint1, t);
+    float bc = interpolate(controlPoint1, controlPoint2, t);
+    float cd = interpolate(controlPoint2, controlPoint3, t);
+    float abc = interpolate(ab, bc, t);
+    float bcd = interpolate(bc, cd, t);
+    return interpolate(abc, bcd, t);
+}
+
+// Evaluates the point on the source cubic specified by t, 0 <= t <= 1.0.
+FloatPoint evaluateCubicAt(const FloatPoint cubic[4], float t)
+{
+    return FloatPoint(evaluateCubic(cubic[0].x(), cubic[1].x(), cubic[2].x(), cubic[3].x(), t),
+                      evaluateCubic(cubic[0].y(), cubic[1].y(), cubic[2].y(), cubic[3].y(), t));
+}
+
+bool xRayCrossesMonotonicCubic(const XRay& xRay, const FloatPoint cubic[4], bool& ambiguous)
+{
+    ambiguous = false;
+
+    // Find the minimum and maximum y of the extrema, which are the
+    // first and last points since this cubic is monotonic
+    float minY = std::min(cubic[0].y(), cubic[3].y());
+    float maxY = std::max(cubic[0].y(), cubic[3].y());
+
+    if (xRay.y() == cubic[0].y()
+        || xRay.y() < minY
+        || xRay.y() > maxY) {
+        // The query line definitely does not cross the curve
+        ambiguous = (xRay.y() == cubic[0].y());
+        return false;
+    }
+
+    const bool pointAtExtremum = (xRay.y() == cubic[3].y());
+
+    float minX = std::min(std::min(std::min(cubic[0].x(), cubic[1].x()),
+                                   cubic[2].x()),
+                          cubic[3].x());
+    if (xRay.x() < minX) {
+        // The query line definitely crosses the curve
+        ambiguous = pointAtExtremum;
+        return true;
+    }
+
+    float maxX = std::max(std::max(std::max(cubic[0].x(), cubic[1].x()),
+                                   cubic[2].x()),
+                          cubic[3].x());
+    if (xRay.x() > maxX)
+        // The query line definitely does not cross the curve
+        return false;
+
+    // Do a binary search to find the parameter value which makes y as
+    // close as possible to the query point. See whether the query
+    // line's origin is to the left of the associated x coordinate.
+
+    // MaxIterations is chosen as the number of mantissa bits for a float,
+    // since there's no way we are going to get more precision by
+    // iterating more times than that.
+    const int MaxIterations = 23;
+    FloatPoint evaluatedPoint;
+    int iter = 0;
+    float upperT;
+    float lowerT;
+    // Need to invert direction of t parameter if cubic goes up
+    // instead of down
+    if (cubic[3].y() > cubic[0].y()) {
+        upperT = 1;
+        lowerT = 0;
+    } else {
+        upperT = 0;
+        lowerT = 1;
+    }
+    do {
+        float t = 0.5f * (upperT + lowerT);
+        evaluatedPoint = evaluateCubicAt(cubic, t);
+        if (xRay.y() > evaluatedPoint.y())
+            lowerT = t;
+        else
+            upperT = t;
+    } while (++iter < MaxIterations && !nearlyZero(evaluatedPoint.y() - xRay.y()));
+
+    // FIXME: once we have more regression tests for this code,
+    // determine whether this should be using a fuzzy test.
+    if (xRay.x() <= evaluatedPoint.x()) {
+        ambiguous = pointAtExtremum;
+        return true;
+    }
+    return false;
+}
+
+// Divides the numerator by the denominator safely for the case where
+// the result must lie in the range (0..1). Result indicates whether
+// the result is valid.
+bool safeUnitDivide(float numerator, float denominator, float& ratio)
+{
+    if (numerator < 0) {
+        // Make the "numerator >= denominator" check below work.
+        numerator = -numerator;
+        denominator = -denominator;
+    }
+    if (!numerator || !denominator || numerator >= denominator)
+        return false;
+    float r = numerator / denominator;
+    if (isnan(r))
+        return false;
+    ASSERT(r >= 0 && r < 1);
+    if (!r) // catch underflow if numerator <<<< denominator
+        return false;
+    ratio = r;
+    return true;
+}
+
+// From Numerical Recipes in C.
+//
+//   q = -1/2 (b + sign(b) sqrt[b*b - 4*a*c])
+//   x1 = q / a
+//   x2 = c / q
+//
+// Returns the number of real roots of the equation [0..2]. Roots are
+// returned in sorted order, smaller root first.
+int findUnitQuadRoots(float a, float b, float c, float roots[2])
+{
+    if (!a)
+        return safeUnitDivide(-c, b, roots[0]) ? 1 : 0;
+
+    float discriminant = b*b - 4*a*c;
+    if (discriminant < 0 || isnan(discriminant)) // complex roots
+        return 0;
+    discriminant = sqrtf(discriminant);
+
+    float q = (b < 0) ? -(b - discriminant) / 2 : -(b + discriminant) / 2;
+    int numberOfRoots = 0;
+    if (safeUnitDivide(q, a, roots[numberOfRoots]))
+        ++numberOfRoots;
+    if (safeUnitDivide(c, q, roots[numberOfRoots]))
+        ++numberOfRoots;
+    if (numberOfRoots == 2) {
+        // Seemingly have two roots. Check for equality and sort.
+        if (roots[0] == roots[1])
+            return 1;
+        if (roots[0] > roots[1])
+            std::swap(roots[0], roots[1]);
+    }
+    return numberOfRoots;
+}
+
+// Cubic'(t) = pt^2 + qt + r, where
+//   p = 3(-a + 3(b - c) + d)
+//   q = 6(a - 2b + c)
+//   r = 3(b - a)
+// Solve for t, keeping only those that fit between 0 < t < 1.
+int findCubicExtrema(float a, float b, float c, float d, float tValues[2])
+{
+    // Divide p, q, and r by 3 to simplify the equations.
+    float p = d - a + 3*(b - c);
+    float q = 2*(a - b - b + c);
+    float r = b - a;
+
+    return findUnitQuadRoots(p, q, r, tValues);
+}
+
+void interpolateCubicCoords(float controlPoint0, float controlPoint1, float controlPoint2, float controlPoint3, float* dst, float t)
+{
+    float ab = interpolate(controlPoint0, controlPoint1, t);
+    float bc = interpolate(controlPoint1, controlPoint2, t);
+    float cd = interpolate(controlPoint2, controlPoint3, t);
+    float abc = interpolate(ab, bc, t);
+    float bcd = interpolate(bc, cd, t);
+    float abcd = interpolate(abc, bcd, t);
+
+    dst[0] = controlPoint0;
+    dst[2] = ab;
+    dst[4] = abc;
+    dst[6] = abcd;
+    dst[8] = bcd;
+    dst[10] = cd;
+    dst[12] = controlPoint3;
+}
+
+#ifndef NDEBUG
+bool isUnitInterval(float x)
+{
+    return x > 0 && x < 1;
+}
+#endif
+
+void chopCubicAtTValues(const FloatPoint src[4], FloatPoint dst[], const float tValues[], int roots)
+{
+#ifndef NDEBUG
+    for (int i = 0; i < roots - 1; ++i) {
+        ASSERT(isUnitInterval(tValues[i]));
+        ASSERT(isUnitInterval(tValues[i+1]));
+        ASSERT(tValues[i] < tValues[i+1]);
+    }
+#endif
+
+    if (!roots) {
+        // nothing to chop
+        for (int j = 0; j < 4; ++j)
+            dst[j] = src[j];
+        return;
+    }
+
+    float t = tValues[0];
+    FloatPoint tmp[4];
+    for (int j = 0; j < 4; ++j)
+        tmp[j] = src[j];
+
+    for (int i = 0; i < roots; ++i) {
+        chopCubicAt(tmp, dst, t);
+        if (i == roots - 1)
+            break;
+
+        dst += 3;
+        // Make tmp contain the remaining cubic (after the first chop).
+        for (int j = 0; j < 4; ++j)
+            tmp[j] = dst[j];
+
+        // Watch out for the case that the renormalized t isn't in range.
+        if (!safeUnitDivide(tValues[i+1] - tValues[i], 1.0f - tValues[i], t)) {
+            // If it isn't, just create a degenerate cubic.
+            dst[4] = dst[5] = dst[6] = tmp[3];
+            break;
+        }
+    }
+}
+
+void flattenDoubleCubicYExtrema(FloatPoint coords[7])
+{
+    coords[2].setY(coords[3].y());
+    coords[4].setY(coords[3].y());
+}
+
+int chopCubicAtYExtrema(const FloatPoint src[4], FloatPoint dst[10])
+{
+    float tValues[2];
+    int roots = findCubicExtrema(src[0].y(), src[1].y(), src[2].y(), src[3].y(), tValues);
+
+    chopCubicAtTValues(src, dst, tValues, roots);
+    if (roots) {
+        // we do some cleanup to ensure our Y extrema are flat
+        flattenDoubleCubicYExtrema(&dst[0]);
+        if (roots == 2)
+            flattenDoubleCubicYExtrema(&dst[3]);
+    }
+    return roots;
+}
+
+} // anonymous namespace
+
+// Public cubic operations.
+
+void chopCubicAt(const FloatPoint src[4], FloatPoint dst[7], float t)
+{
+    ASSERT(t >= 0 && t <= 1);
+
+    float output[14];
+    interpolateCubicCoords(src[0].x(), src[1].x(), src[2].x(), src[3].x(), &output[0], t);
+    interpolateCubicCoords(src[0].y(), src[1].y(), src[2].y(), src[3].y(), &output[1], t);
+    for (int i = 0; i < 7; i++)
+        dst[i].set(output[2 * i], output[2 * i + 1]);
+}
+
+// Public XRay queries.
+
+bool xRayCrossesLine(const XRay& xRay, const FloatPoint pts[2], bool& ambiguous)
+{
+    ambiguous = false;
+
+    // Determine quick discards.
+    // Consider query line going exactly through point 0 to not
+    // intersect, for symmetry with xRayCrossesMonotonicCubic.
+    if (xRay.y() == pts[0].y()) {
+        ambiguous = true;
+        return false;
+    }
+    if (xRay.y() < pts[0].y() && xRay.y() < pts[1].y())
+        return false;
+    if (xRay.y() > pts[0].y() && xRay.y() > pts[1].y())
+        return false;
+    if (xRay.x() > pts[0].x() && xRay.x() > pts[1].x())
+        return false;
+    // Determine degenerate cases
+    if (nearlyZero(pts[0].y() - pts[1].y()))
+        return false;
+    if (nearlyZero(pts[0].x() - pts[1].x())) {
+        // We've already determined the query point lies within the
+        // vertical range of the line segment.
+        if (xRay.x() <= pts[0].x()) {
+            ambiguous = (xRay.y() == pts[1].y());
+            return true;
+        }
+        return false;
+    }
+    // Ambiguity check
+    if (xRay.y() == pts[1].y()) {
+        if (xRay.x() <= pts[1].x()) {
+            ambiguous = true;
+            return true;
+        }
+        return false;
+    }
+    // Full line segment evaluation
+    float deltaY = pts[1].y() - pts[0].y();
+    float deltaX = pts[1].x() - pts[0].x();
+    float slope = deltaY / deltaX;
+    float b = pts[0].y() - slope * pts[0].x();
+    // Solve for x coordinate at y = xRay.y()
+    float x = (xRay.y() - b) / slope;
+    return xRay.x() <= x;
+}
+
+int numXRayCrossingsForCubic(const XRay& xRay, const FloatPoint cubic[4], bool& ambiguous)
+{
+    int numCrossings = 0;
+    FloatPoint monotonicCubics[10];
+    int numMonotonicCubics = 1 + chopCubicAtYExtrema(cubic, monotonicCubics);
+    ambiguous = false;
+    FloatPoint* monotonicCubicsPointer = &monotonicCubics[0];
+    for (int i = 0; i < numMonotonicCubics; ++i) {
+        if (xRayCrossesMonotonicCubic(xRay, monotonicCubicsPointer, ambiguous))
+            ++numCrossings;
+        if (ambiguous)
+            return 0;
+        monotonicCubicsPointer += 3;
+    }
+    return numCrossings;
+}
+
+} // namespace LoopBlinnMathUtils
+} // namespace WebCore
diff --git a/WebCore/platform/graphics/gpu/LoopBlinnMathUtils.h b/WebCore/platform/graphics/gpu/LoopBlinnMathUtils.h
new file mode 100644 (file)
index 0000000..b9d19c5
--- /dev/null
@@ -0,0 +1,108 @@
+/*
+ * Copyright (C) 2010 Google Inc. All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ *
+ * 1.  Redistributions of source code must retain the above copyright
+ *     notice, this list of conditions and the following disclaimer.
+ * 2.  Redistributions in binary form must reproduce the above copyright
+ *     notice, this list of conditions and the following disclaimer in the
+ *     documentation and/or other materials provided with the distribution.
+ *
+ * THIS SOFTWARE IS PROVIDED BY APPLE AND ITS CONTRIBUTORS "AS IS" AND ANY
+ * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
+ * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
+ * DISCLAIMED. IN NO EVENT SHALL APPLE OR ITS CONTRIBUTORS BE LIABLE FOR ANY
+ * DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
+ * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
+ * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
+ * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
+ * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
+ * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+ */
+
+#ifndef LoopBlinnMathUtils_h
+#define LoopBlinnMathUtils_h
+
+#include "FloatPoint.h"
+#include "FloatPoint3D.h"
+#include <math.h>
+
+namespace WebCore {
+
+// Use a namespace for these so we can easily import them.
+namespace LoopBlinnMathUtils {
+
+float roundToZero(float val);
+bool approxEqual(const FloatPoint& v0, const FloatPoint& v1);
+bool approxEqual(const FloatPoint3D& v0, const FloatPoint3D& v1);
+bool approxEqual(float f0, float f1);
+
+// Determines whether the line segment between (p1, q1) intersects
+// that between (p2, q2).
+bool linesIntersect(const FloatPoint& p1,
+                    const FloatPoint& q1,
+                    const FloatPoint& p2,
+                    const FloatPoint& q2);
+
+// Determines whether "point" is inside the 2D triangle defined by
+// vertices a, b, and c. This test defines that points exactly on an
+// edge are not considered to be inside the triangle.
+bool pointInTriangle(const FloatPoint& point,
+                     const FloatPoint& a,
+                     const FloatPoint& b,
+                     const FloatPoint& c);
+
+// Determines whether the triangles defined by the points (a1, b1, c1)
+// and (a2, b2, c2) overlap. The definition of this function is that
+// if the two triangles only share an adjacent edge or vertex, they
+// are not considered to overlap.
+bool trianglesOverlap(const FloatPoint& a1,
+                      const FloatPoint& b1,
+                      const FloatPoint& c1,
+                      const FloatPoint& a2,
+                      const FloatPoint& b2,
+                      const FloatPoint& c2);
+
+// Given a src cubic bezier, chops it at the specified t value,
+// where 0 < t < 1, and returns the two new cubics in dst[0..3]
+// and dst[3..6].
+void chopCubicAt(const FloatPoint src[4], FloatPoint dst[7], float t);
+
+// "X-Ray" queries. An XRay is a half-line originating at the given
+// point and extending to x=+infinity.
+typedef FloatPoint XRay;
+
+// Given an arbitrary cubic bezier, return the number of times an XRay
+// crosses the cubic. Valid return values are [0..3].
+//
+// By definition the cubic is open at the starting point; in other
+// words, if pt.fY is equivalent to cubic[0].fY, and pt.fX is to the
+// left of the curve, the line is not considered to cross the curve,
+// but if it is equal to cubic[3].fY then it is considered to
+// cross.
+//
+// Outgoing "ambiguous" argument indicates whether the answer is ambiguous
+// because the query occurred exactly at one of the endpoints' y
+// coordinates or at a tangent point, indicating that another query y
+// coordinate is preferred for robustness.
+int numXRayCrossingsForCubic(const XRay& xRay,
+                             const FloatPoint cubic[4],
+                             bool& ambiguous);
+
+// Given a line segment from lineEndpoints[0] to lineEndpoints[1], and an
+// XRay, returns true if they intersect. Outgoing "ambiguous" argument
+// indicates whether the answer is ambiguous because the query occurred
+// exactly at one of the endpoints' y coordinates, indicating that another
+// query y coordinate is preferred for robustness.
+bool xRayCrossesLine(const XRay& xRay,
+                     const FloatPoint lineEndpoints[2],
+                     bool& ambiguous);
+
+} // namespace LoopBlinnMathUtils
+
+} // namespace WebCore
+
+#endif // LoopBlinnMathUtils_h