Bug 45251 – Add math utilities for cubic curve processing

• Component: Layout and Rendering
• Status: RESOLVED FIXED

[Kenneth Russell]

As part of the GPU accelerated path rendering algorithm in https://bugs.webkit.org/show_bug.cgi?id=44729 , several mathematical utilities are needed, mainly involving queries and subdivision of cubic curve segments, and some geometric queries on triangles.

[Kenneth Russell]

Created attachment 66610 [details]
Patch

From the ChangeLog:

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.

[James Robinson]

Comment on attachment 66610 [details]
Patch

View in context: https://bugs.webkit.org/attachment.cgi?id=66610&action=prettypatch

> WebCore/platform/graphics/gpu/LoopBlinnMathUtils.cpp:129
> +    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;
Could this use FloatPoint's dot product?

> WebCore/platform/graphics/gpu/LoopBlinnMathUtils.cpp:177
> +// Helper routines for public XRay queries below.
Could you add a link to the original source of these routines (presumably skia)?

> WebCore/platform/graphics/gpu/LoopBlinnMathUtils.cpp:181
> +bool nearlyZero(float x, float tolerance = NearlyZeroConstant)
Seems redundant with approxEqual()

> WebCore/platform/graphics/gpu/LoopBlinnMathUtils.cpp:190
> +inline float interpolate(float a, float b, float t)
nit: drop the inline, I believe it'll be ignored.

> WebCore/platform/graphics/gpu/LoopBlinnMathUtils.cpp:196
> +float evaluateCubic(float s0, float s2, float s4, float s6, float t)
nit: rename s0, s2, s4, s6 to something else.

> WebCore/platform/graphics/gpu/LoopBlinnMathUtils.cpp:217
> +bool evaluateCubicAt(const FloatPoint cubic[4], float t, FloatPoint& pt)
> +{
> +    pt.set(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));
> +}
This should return a FloatPoint.

> WebCore/platform/graphics/gpu/LoopBlinnMathUtils.cpp:262
> +    FloatPoint evaluate;
evaluatedPoint? interpolatedPoint?

> WebCore/platform/graphics/gpu/LoopBlinnMathUtils.cpp:284
> +    if (xRay.x() <= evaluate.x()) {
Add a FIXME: here to check if this test should be fuzzy once we have more regression tests for this code.

> WebCore/platform/graphics/gpu/LoopBlinnMathUtils.cpp:291
> +int validUnitDivide(float numer, float denom, float* ratio)
numerator, denominator

> WebCore/platform/graphics/gpu/LoopBlinnMathUtils.cpp:337
> +        else if (roots[0] == roots[1]) // nearly-equal?
comment isn't a sentence.  Should this be a FIXME?

> WebCore/platform/graphics/gpu/LoopBlinnMathUtils.cpp:346
> +    Solve for t, keeping only those that fit betwee 0 < t < 1
typo: between

> WebCore/platform/graphics/gpu/LoopBlinnMathUtils.cpp:421
> +        memcpy(dst, src, 4*sizeof(FloatPoint));
should loop through here and do dst[i] = src[i] to invoke FloatPoint's copy constructor.

> WebCore/platform/graphics/gpu/LoopBlinnMathUtils.cpp:435
> +        memcpy(tmp, dst, 4 * sizeof(FloatPoint));
same as above

> WebCore/platform/graphics/gpu/LoopBlinnMathUtils.cpp:438
> +        // watch out in case the renormalized t isn't in range
Needs to be a sentence

> WebCore/platform/graphics/gpu/LoopBlinnMathUtils.cpp:440
> +                             1 - tValues[i], &t)) {
1.0f

> WebCore/platform/graphics/gpu/LoopBlinnMathUtils.cpp:442
> +            dst[4] = dst[5] = dst[6] = src[3];
check the values here, the dst indices look off.

> WebCore/platform/graphics/gpu/LoopBlinnMathUtils.cpp:460
> +    if (dst && roots > 0) {
the null check for dst isn't needed here.  Also, just check for 'roots' rather than 'roots > 0'

> WebCore/platform/graphics/gpu/LoopBlinnMathUtils.cpp:492
> +    // intersect, for symmetry with SkXRayCrossesMonotonicCubic.
SkXRayCross... -> xRayCross..

> WebCore/platform/graphics/gpu/LoopBlinnMathUtils.cpp:530
> +    return xRay.x() <= x;
add a FIXME here to check if this should be a fuzzy check

> WebCore/platform/graphics/gpu/LoopBlinnMathUtils.cpp:533
> +int numXRayCrossingsForCubic(const XRay& pt, const FloatPoint cubic[4], bool& ambiguous)
pt -> xRay

> WebCore/platform/graphics/gpu/LoopBlinnMathUtils.cpp:550
> +    if (xRayCrossesMonotonicCubic(pt, &monotonicCubics[0], locallyAmbiguous))
> +        ++numCrossings;
> +    ambiguous |= locallyAmbiguous;
> +    if (numMonotonicCubics > 0)
> +        if (xRayCrossesMonotonicCubic(pt, &monotonicCubics[3], locallyAmbiguous))
> +            ++numCrossings;
> +    ambiguous |= locallyAmbiguous;
> +    if (numMonotonicCubics > 1)
> +        if (xRayCrossesMonotonicCubic(pt, &monotonicCubics[6], locallyAmbiguous))
> +            ++numCrossings;
> +    ambiguous |= locallyAmbiguous;
Make this a loop over [0,numMonotonicCubics) and early-out if it detects ambiguity.

> WebCore/platform/graphics/gpu/LoopBlinnMathUtils.h:34
> +class FloatPoint;
This has to be pulled in via in #include explicitly rather than forward declared since we call functions on FloatPoints (like diagonalLengthSquared()).

> WebCore/platform/graphics/gpu/LoopBlinnMathUtils.h:43
> +const float Epsilon = 5.0e-4f;
I think this needs a storage declaration in the .cpp.

[Kenneth Russell]

Created attachment 67082 [details]
Revised patch

Revised patch addressing above code review feedback.

[Kenneth Russell]

(In reply to comment #2)
> (From update of attachment 66610 [details])
> View in context: https://bugs.webkit.org/attachment.cgi?id=66610&action=prettypatch
> 
> > WebCore/platform/graphics/gpu/LoopBlinnMathUtils.cpp:129
> > +    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;
> Could this use FloatPoint's dot product?

Unfortunately not easily, because FloatPoint - FloatPoint yields a "FloatSize" and FloatSize doesn't have a dot product operation.

> > WebCore/platform/graphics/gpu/LoopBlinnMathUtils.cpp:177
> > +// Helper routines for public XRay queries below.
> Could you add a link to the original source of these routines (presumably skia)?

Done.

> > WebCore/platform/graphics/gpu/LoopBlinnMathUtils.cpp:181
> > +bool nearlyZero(float x, float tolerance = NearlyZeroConstant)
> Seems redundant with approxEqual()

Agreed, but I do not want to change these two independent tolerances at this point.

> > WebCore/platform/graphics/gpu/LoopBlinnMathUtils.cpp:190
> > +inline float interpolate(float a, float b, float t)
> nit: drop the inline, I believe it'll be ignored.

Done.

> > WebCore/platform/graphics/gpu/LoopBlinnMathUtils.cpp:196
> > +float evaluateCubic(float s0, float s2, float s4, float s6, float t)
> nit: rename s0, s2, s4, s6 to something else.

Done.

> > WebCore/platform/graphics/gpu/LoopBlinnMathUtils.cpp:217
> > +bool evaluateCubicAt(const FloatPoint cubic[4], float t, FloatPoint& pt)
> > +{
> > +    pt.set(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));
> > +}
> This should return a FloatPoint.

Done.

> > WebCore/platform/graphics/gpu/LoopBlinnMathUtils.cpp:262
> > +    FloatPoint evaluate;
> evaluatedPoint? interpolatedPoint?

Changed to evaluatedPoint.

> > WebCore/platform/graphics/gpu/LoopBlinnMathUtils.cpp:284
> > +    if (xRay.x() <= evaluate.x()) {
> Add a FIXME: here to check if this test should be fuzzy once we have more regression tests for this code.

Done.

> > WebCore/platform/graphics/gpu/LoopBlinnMathUtils.cpp:291
> > +int validUnitDivide(float numer, float denom, float* ratio)
> numerator, denominator

Done.

> > WebCore/platform/graphics/gpu/LoopBlinnMathUtils.cpp:337
> > +        else if (roots[0] == roots[1]) // nearly-equal?
> comment isn't a sentence.  Should this be a FIXME?

Changed to be a sentence. I think this case is desired this way and does not warrant a FIXME.

> > WebCore/platform/graphics/gpu/LoopBlinnMathUtils.cpp:346
> > +    Solve for t, keeping only those that fit betwee 0 < t < 1
> typo: between

Fixed.

> > WebCore/platform/graphics/gpu/LoopBlinnMathUtils.cpp:421
> > +        memcpy(dst, src, 4*sizeof(FloatPoint));
> should loop through here and do dst[i] = src[i] to invoke FloatPoint's copy constructor.

Done.

> > WebCore/platform/graphics/gpu/LoopBlinnMathUtils.cpp:435
> > +        memcpy(tmp, dst, 4 * sizeof(FloatPoint));
> same as above

Done.

> > WebCore/platform/graphics/gpu/LoopBlinnMathUtils.cpp:438
> > +        // watch out in case the renormalized t isn't in range
> Needs to be a sentence

Fixed.

> > WebCore/platform/graphics/gpu/LoopBlinnMathUtils.cpp:440
> > +                             1 - tValues[i], &t)) {
> 1.0f

Done.

> > WebCore/platform/graphics/gpu/LoopBlinnMathUtils.cpp:442
> > +            dst[4] = dst[5] = dst[6] = src[3];
> check the values here, the dst indices look off.

I re-checked this against the original Skia sources and the indices have the same semantics, so I'm leaving these as is.

> > WebCore/platform/graphics/gpu/LoopBlinnMathUtils.cpp:460
> > +    if (dst && roots > 0) {
> the null check for dst isn't needed here.  Also, just check for 'roots' rather than 'roots > 0'

Done.

> > WebCore/platform/graphics/gpu/LoopBlinnMathUtils.cpp:492
> > +    // intersect, for symmetry with SkXRayCrossesMonotonicCubic.
> SkXRayCross... -> xRayCross..

Done.

> > WebCore/platform/graphics/gpu/LoopBlinnMathUtils.cpp:530
> > +    return xRay.x() <= x;
> add a FIXME here to check if this should be a fuzzy check

Done.

> > WebCore/platform/graphics/gpu/LoopBlinnMathUtils.cpp:533
> > +int numXRayCrossingsForCubic(const XRay& pt, const FloatPoint cubic[4], bool& ambiguous)
> pt -> xRay

Done.

> > WebCore/platform/graphics/gpu/LoopBlinnMathUtils.cpp:550
> > +    if (xRayCrossesMonotonicCubic(pt, &monotonicCubics[0], locallyAmbiguous))
> > +        ++numCrossings;
> > +    ambiguous |= locallyAmbiguous;
> > +    if (numMonotonicCubics > 0)
> > +        if (xRayCrossesMonotonicCubic(pt, &monotonicCubics[3], locallyAmbiguous))
> > +            ++numCrossings;
> > +    ambiguous |= locallyAmbiguous;
> > +    if (numMonotonicCubics > 1)
> > +        if (xRayCrossesMonotonicCubic(pt, &monotonicCubics[6], locallyAmbiguous))
> > +            ++numCrossings;
> > +    ambiguous |= locallyAmbiguous;
> Make this a loop over [0,numMonotonicCubics) and early-out if it detects ambiguity.

Done.

> > WebCore/platform/graphics/gpu/LoopBlinnMathUtils.h:34
> > +class FloatPoint;
> This has to be pulled in via in #include explicitly rather than forward declared since we call functions on FloatPoints (like diagonalLengthSquared()).

Done.

> > WebCore/platform/graphics/gpu/LoopBlinnMathUtils.h:43
> > +const float Epsilon = 5.0e-4f;
> I think this needs a storage declaration in the .cpp.

No, that causes a compilation failure. Since this constant is only referenced from this header I've renamed it ImplementationEpsilon and added a comment indicating that outside code shouldn't reference it, which should prevent problems on any platform.

[James Robinson]

Comment on attachment 67082 [details]
Revised patch

r- for various nits.  Overall, I want to make sure we feel really good about the math functions we check in regardless of what their history is.  We're going to have to maintain these indefinitely even if they did come from skia originally.

View in context: https://bugs.webkit.org/attachment.cgi?id=67082&action=prettypatch

> WebCore/platform/graphics/gpu/LoopBlinnMathUtils.cpp:137
> +    float denom = dot00 * dot11 - dot01 * dot01;
> +    if (!denom)
> +        // Triangle is zero-area. Treat query point as not being inside.
> +        return false;
> +    // Compute
> +    float invDenom = 1.0f / denom;
> +    float u = (dot11 * dot02 - dot01 * dot12) * invDenom;
> +    float v = (dot00 * dot12 - dot01 * dot02) * invDenom;
denom -> denominator, invDenom -> inverseDenimonator.  Or just divide by the denominator

> WebCore/platform/graphics/gpu/LoopBlinnMathUtils.cpp:171
> +    // Finally, test if tri1 is totally contained in tri2 or vice versa.
> +    if (pointInTriangle(a1, a2, b2, c2)
> +        || pointInTriangle(a2, a1, b1, c1))
> +        return true;
> +
> +    // Because we define that triangles sharing a vertex or edge don't
> +    // overlap, we must perform additional point-in-triangle tests to
> +    // see whether one triangle is contained in the other.
> +    if (pointInTriangle(b1, a2, b2, c2)
> +        || pointInTriangle(c1, a2, b2, c2)
> +        || pointInTriangle(b2, a1, b1, c1)
> +        || pointInTriangle(c2, a1, b1, c1))
> +        return true;
seems like it'd be cleaner to unify these two sets of tests with a preceeding comment explaining why it diverges from the akpeters.com paper

> WebCore/platform/graphics/gpu/LoopBlinnMathUtils.cpp:198
> +float evaluateCubic(float s0, float s2, float s4, float s6, float t)
s0, s2, s4, s6 still need a rename

> WebCore/platform/graphics/gpu/LoopBlinnMathUtils.cpp:200
> +    ASSERT(t >= 0 && t <= 1);
0.0f, 1.0f

> WebCore/platform/graphics/gpu/LoopBlinnMathUtils.cpp:275
> +        upperT = 1;
> +        lowerT = 0;
> +    } else {
> +        upperT = 0;
> +        lowerT = 1;
0.0f, 1.0f

> WebCore/platform/graphics/gpu/LoopBlinnMathUtils.cpp:278
> +        float t = 0.5 * (upperT + lowerT);
0.5f (0.5 is a double)

> WebCore/platform/graphics/gpu/LoopBlinnMathUtils.cpp:314
> +    if (!denominator || !numerator || numerator >= denominator)
> +        return 0;
> +
> +    float r = numerator / denominator;
> +    if (isnan(r))
> +        return 0;
> +    ASSERT(r >= 0 && r < 1);
> +    if (!r) // catch underflow if numerator <<<< denominator
> +        return 0;
> +    *ratio = r;
> +    return 1;
I can't get past how bizarre this function is.  I would strongly suggest rewriting this and the root finding section below.  If we discover bugs introduced by the rewrite later on that's fine, we will be able to fix them.  If we find bugs in this code I'm concerned that we'll just be SOL.

> WebCore/platform/graphics/gpu/LoopBlinnMathUtils.cpp:344
> +    float* r = roots;
> +
> +    float R = b*b - 4*a*c;
> +    if (R < 0 || isnan(R)) // complex roots
> +        return 0;
> +    R = sqrtf(R);
> +
> +    float Q = (b < 0) ? -(b - R) / 2 : -(b + R) / 2;
> +    r += validUnitDivide(Q, a, r);
> +    r += validUnitDivide(c, Q, r);
> +    if (r - roots == 2)
> +        if (roots[0] > roots[1])
> +            std::swap(roots[0], roots[1]);
> +        else if (roots[0] == roots[1]) // are the roots nearly equal?
> +            r -= 1; // skip the double root
> +    return (int)(r - roots);
> +}
This code is just insane.  I think it's correct, but it looks a long way from the simplest way to do this.

> WebCore/platform/graphics/gpu/LoopBlinnMathUtils.cpp:351
> +/** 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
> +*/
Wrong comment style for WebKit.

> WebCore/platform/graphics/gpu/LoopBlinnMathUtils.cpp:354
> +    // we divide p, q, and r by 3 to simplify
not a sentence and not very clear

> WebCore/platform/graphics/gpu/LoopBlinnMathUtils.cpp:357
> +    float p = d - a + 3*(b - c);
> +    float q = 2*(a - b - b + c);
> +    float r = b - a;
"- b - b" -> "-2.0f * b"
3 -> 3.0f
2 -> 2.0f

> WebCore/platform/graphics/gpu/LoopBlinnMathUtils.cpp:406
> +    This test code would fail when we didn't check the return result of
> +    valid_unit_divide in SkChopCubicAt(... tValues[], int roots). The reason is
> +    that after the first chop, the parameters to valid_unit_divide are equal
> +    (thanks to finite float precision and rounding in the subtracts). Thus
> +    even though the 2nd tValue looks < 1.0, after we renormalize it, we end
> +    up with 1.0, hence the need to check and just return the last cubic as
> +    a degenerate clump of 4 points in the same place.
> +
> +    static void test_cubic() {
> +        SkPoint src[4] = {
> +            { 556.25000, 523.03003 },
> +            { 556.23999, 522.96002 },
> +            { 556.21997, 522.89001 },
> +            { 556.21997, 522.82001 }
> +        };
> +        SkPoint dst[10];
> +        SkScalar tval[] = { 0.33333334f, 0.99999994f };
> +        SkChopCubicAt(src, dst, tval, 2);
This comment doesn't make sense any more in this context.  It looks like something that should be encoded in a unit test instead of a comment.

> WebCore/platform/graphics/gpu/LoopBlinnMathUtils.cpp:410
> +void chopCubicAt(const FloatPoint src[4], FloatPoint dst[], const float tValues[], int roots)
This function does something very different from what the other chopCubicAt() in this file does.  Maybe call it chopCubicAtRoots()?

> WebCore/platform/graphics/gpu/LoopBlinnMathUtils.cpp:422
> +    if (!dst)
> +        return;
> +
This is unnecessary (we never pass NULL in for this parameter in this file and it's not a public API)

> WebCore/platform/graphics/gpu/LoopBlinnMathUtils.cpp:442
> +        src = tmp;
This function mutates src as well?  That's a bit unexpected, and it means that the exposed function numXRayCrossingsForCubic() mutates its cubic parameter which seems suspicious.  I think this should only mutate temporaries

> WebCore/platform/graphics/gpu/LoopBlinnMathUtils.cpp:481
> +    ASSERT(t > 0 && t < 1);
0.0f, 1.0f.  Why aren't 0.0 and 1.0 valid inputs for this function?

> WebCore/platform/graphics/gpu/LoopBlinnMathUtils.h:71
> +// A roundoff factor in the cubic classification and texture coordinate
> +// generation algorithms. It is only an implementation detail and should
> +// not be referenced by code outside this namespace. It primarily
> +// determines the handling of corner cases during the classification
> +// process. Be careful when adjusting this; 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 ImplementationEpsilon = 5.0e-4f;
> +
> +// Returns zero if value is within +/-ImplementationEpsilon of zero.
> +inline float roundToZero(float val)
> +{
> +    if (val < ImplementationEpsilon && val > -ImplementationEpsilon)
> +        return 0;
> +    return val;
> +}
> +
> +inline bool approxEqual(const FloatPoint& v0, const FloatPoint& v1)
> +{
> +    return (v0 - v1).diagonalLengthSquared() < ImplementationEpsilon * ImplementationEpsilon;
> +}
> +
> +inline bool approxEqual(const FloatPoint3D& v0, const FloatPoint3D& v1)
> +{
> +    return (v0 - v1).lengthSquared() < ImplementationEpsilon * ImplementationEpsilon;
> +}
> +
> +inline bool approxEqual(float f0, float f1)
> +{
> +    return fabsf(f0 - f1) < ImplementationEpsilon;
> +}
Why not move the bodies of all of these functions over to the .cpp and not mention ImplementationEpsilon at all in the header?  The implementations will get inlined by an optimizing linker anyway.

[Kenneth Russell]

Created attachment 67126 [details]
Revised patch

Addressed code review feedback above.

[Kenneth Russell]

(In reply to comment #5)
> (From update of attachment 67082 [details])
> r- for various nits.  Overall, I want to make sure we feel really good about the math functions we check in regardless of what their history is.  We're going to have to maintain these indefinitely even if they did come from skia originally.
> 
> View in context: https://bugs.webkit.org/attachment.cgi?id=67082&action=prettypatch
> 
> > WebCore/platform/graphics/gpu/LoopBlinnMathUtils.cpp:137
> > +    float denom = dot00 * dot11 - dot01 * dot01;
> > +    if (!denom)
> > +        // Triangle is zero-area. Treat query point as not being inside.
> > +        return false;
> > +    // Compute
> > +    float invDenom = 1.0f / denom;
> > +    float u = (dot11 * dot02 - dot01 * dot12) * invDenom;
> > +    float v = (dot00 * dot12 - dot01 * dot02) * invDenom;
> denom -> denominator, invDenom -> inverseDenimonator.  Or just divide by the denominator

Renamed. Want to retain the reduced number of divisions in the code.

> > WebCore/platform/graphics/gpu/LoopBlinnMathUtils.cpp:171
> > +    // Finally, test if tri1 is totally contained in tri2 or vice versa.
> > +    if (pointInTriangle(a1, a2, b2, c2)
> > +        || pointInTriangle(a2, a1, b1, c1))
> > +        return true;
> > +
> > +    // Because we define that triangles sharing a vertex or edge don't
> > +    // overlap, we must perform additional point-in-triangle tests to
> > +    // see whether one triangle is contained in the other.
> > +    if (pointInTriangle(b1, a2, b2, c2)
> > +        || pointInTriangle(c1, a2, b2, c2)
> > +        || pointInTriangle(b2, a1, b1, c1)
> > +        || pointInTriangle(c2, a1, b1, c1))
> > +        return true;
> seems like it'd be cleaner to unify these two sets of tests with a preceeding comment explaining why it diverges from the akpeters.com paper

OK, done.

> > WebCore/platform/graphics/gpu/LoopBlinnMathUtils.cpp:198
> > +float evaluateCubic(float s0, float s2, float s4, float s6, float t)
> s0, s2, s4, s6 still need a rename

Oversight on my part. Done.

> > WebCore/platform/graphics/gpu/LoopBlinnMathUtils.cpp:200
> > +    ASSERT(t >= 0 && t <= 1);
> 0.0f, 1.0f

WebKit style specifies that when the floating-point suffix is not required on a floating-point constant, such as here, it should not be used. See "Floating point literals" on http://webkit.org/coding/coding-style.html . Left unchanged.

> > WebCore/platform/graphics/gpu/LoopBlinnMathUtils.cpp:275
> > +        upperT = 1;
> > +        lowerT = 0;
> > +    } else {
> > +        upperT = 0;
> > +        lowerT = 1;
> 0.0f, 1.0f

No, per above.

> > WebCore/platform/graphics/gpu/LoopBlinnMathUtils.cpp:278
> > +        float t = 0.5 * (upperT + lowerT);
> 0.5f (0.5 is a double)

This one I changed.

> > WebCore/platform/graphics/gpu/LoopBlinnMathUtils.cpp:314
> > +    if (!denominator || !numerator || numerator >= denominator)
> > +        return 0;
> > +
> > +    float r = numerator / denominator;
> > +    if (isnan(r))
> > +        return 0;
> > +    ASSERT(r >= 0 && r < 1);
> > +    if (!r) // catch underflow if numerator <<<< denominator
> > +        return 0;
> > +    *ratio = r;
> > +    return 1;
> I can't get past how bizarre this function is.  I would strongly suggest rewriting this and the root finding section below.  If we discover bugs introduced by the rewrite later on that's fine, we will be able to fix them.  If we find bugs in this code I'm concerned that we'll just be SOL.

I spent quite some time looking through Numerical Recipes in C and trying to simplify this and the root finding code below, but the conclusion I've come to is that having this general function is a good idea. I've renamed it to "safeUnitDivide" and made it more WebKit-style (bool return value, outgoing float& rather than float*. I hope you will find it more palatable because I do not see a way to get rid of it completely without rewriting all of the math in this file.

> > WebCore/platform/graphics/gpu/LoopBlinnMathUtils.cpp:344
> > +    float* r = roots;
> > +
> > +    float R = b*b - 4*a*c;
> > +    if (R < 0 || isnan(R)) // complex roots
> > +        return 0;
> > +    R = sqrtf(R);
> > +
> > +    float Q = (b < 0) ? -(b - R) / 2 : -(b + R) / 2;
> > +    r += validUnitDivide(Q, a, r);
> > +    r += validUnitDivide(c, Q, r);
> > +    if (r - roots == 2)
> > +        if (roots[0] > roots[1])
> > +            std::swap(roots[0], roots[1]);
> > +        else if (roots[0] == roots[1]) // are the roots nearly equal?
> > +            r -= 1; // skip the double root
> > +    return (int)(r - roots);
> > +}
> This code is just insane.  I think it's correct, but it looks a long way from the simplest way to do this.

After trying to rewrite this to be closer to the pure Numerical Recipes in C algorithm, there are good reasons for the logic in here, specifically that the roots of the quadratic equations solved in this file are always supposed to be between 0 and 1 because those are the valid "time" parameters for the incoming cubics. However this is not automatically the case; it is necessary to detect when the roots are out of range and squelch them. I have rewritten the logic in this function, and hopefully it should be easier to read, but the algorithm is basically unchanged and needs to be.

> > WebCore/platform/graphics/gpu/LoopBlinnMathUtils.cpp:351
> > +/** 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
> > +*/
> Wrong comment style for WebKit.

Changed.

> > WebCore/platform/graphics/gpu/LoopBlinnMathUtils.cpp:354
> > +    // we divide p, q, and r by 3 to simplify
> not a sentence and not very clear

Will upload another patch fixing this.

> > WebCore/platform/graphics/gpu/LoopBlinnMathUtils.cpp:357
> > +    float p = d - a + 3*(b - c);
> > +    float q = 2*(a - b - b + c);
> > +    float r = b - a;
> "- b - b" -> "-2.0f * b"
> 3 -> 3.0f
> 2 -> 2.0f

No, per above.

> > WebCore/platform/graphics/gpu/LoopBlinnMathUtils.cpp:406
> > +    This test code would fail when we didn't check the return result of
> > +    valid_unit_divide in SkChopCubicAt(... tValues[], int roots). The reason is
> > +    that after the first chop, the parameters to valid_unit_divide are equal
> > +    (thanks to finite float precision and rounding in the subtracts). Thus
> > +    even though the 2nd tValue looks < 1.0, after we renormalize it, we end
> > +    up with 1.0, hence the need to check and just return the last cubic as
> > +    a degenerate clump of 4 points in the same place.
> > +
> > +    static void test_cubic() {
> > +        SkPoint src[4] = {
> > +            { 556.25000, 523.03003 },
> > +            { 556.23999, 522.96002 },
> > +            { 556.21997, 522.89001 },
> > +            { 556.21997, 522.82001 }
> > +        };
> > +        SkPoint dst[10];
> > +        SkScalar tval[] = { 0.33333334f, 0.99999994f };
> > +        SkChopCubicAt(src, dst, tval, 2);
> This comment doesn't make sense any more in this context.  It looks like something that should be encoded in a unit test instead of a comment.

I've removed the comment since the logic is taking care of the originally failing case.

> > WebCore/platform/graphics/gpu/LoopBlinnMathUtils.cpp:410
> > +void chopCubicAt(const FloatPoint src[4], FloatPoint dst[], const float tValues[], int roots)
> This function does something very different from what the other chopCubicAt() in this file does.  Maybe call it chopCubicAtRoots()?

It actually chops at certain T values (the cubic extrema, not its roots) so I've renamed it to chopCubicAtTValues.

> > WebCore/platform/graphics/gpu/LoopBlinnMathUtils.cpp:422
> > +    if (!dst)
> > +        return;
> > +
> This is unnecessary (we never pass NULL in for this parameter in this file and it's not a public API)

OK, removed.

> > WebCore/platform/graphics/gpu/LoopBlinnMathUtils.cpp:442
> > +        src = tmp;
> This function mutates src as well?  That's a bit unexpected, and it means that the exposed function numXRayCrossingsForCubic() mutates its cubic parameter which seems suspicious.  I think this should only mutate temporaries

It doesn't actually mutate src; it makes src point to tmp so that the next iteration comes from tmp rather than src. However I agree that this is confusing so I've changed the code to always copy src to tmp and use tmp as the source in the loop, despite the fact that this may induce a copy where one isn't needed.

> > WebCore/platform/graphics/gpu/LoopBlinnMathUtils.cpp:481
> > +    ASSERT(t > 0 && t < 1);
> 0.0f, 1.0f.  Why aren't 0.0 and 1.0 valid inputs for this function?

Looking at the callees, 0 and 1 should be valid. I've changed the assert to use >= and <=, but left the constants alone per above.

> > WebCore/platform/graphics/gpu/LoopBlinnMathUtils.h:71
> > +// A roundoff factor in the cubic classification and texture coordinate
> > +// generation algorithms. It is only an implementation detail and should
> > +// not be referenced by code outside this namespace. It primarily
> > +// determines the handling of corner cases during the classification
> > +// process. Be careful when adjusting this; 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 ImplementationEpsilon = 5.0e-4f;
> > +
> > +// Returns zero if value is within +/-ImplementationEpsilon of zero.
> > +inline float roundToZero(float val)
> > +{
> > +    if (val < ImplementationEpsilon && val > -ImplementationEpsilon)
> > +        return 0;
> > +    return val;
> > +}
> > +
> > +inline bool approxEqual(const FloatPoint& v0, const FloatPoint& v1)
> > +{
> > +    return (v0 - v1).diagonalLengthSquared() < ImplementationEpsilon * ImplementationEpsilon;
> > +}
> > +
> > +inline bool approxEqual(const FloatPoint3D& v0, const FloatPoint3D& v1)
> > +{
> > +    return (v0 - v1).lengthSquared() < ImplementationEpsilon * ImplementationEpsilon;
> > +}
> > +
> > +inline bool approxEqual(float f0, float f1)
> > +{
> > +    return fabsf(f0 - f1) < ImplementationEpsilon;
> > +}
> Why not move the bodies of all of these functions over to the .cpp and not mention ImplementationEpsilon at all in the header?  The implementations will get inlined by an optimizing linker anyway.

OK, I've moved these to the .cpp.

[Kenneth Russell]

Created attachment 67128 [details]
Revised patch

Changed comment in findCubicExtrema per code review above.

[James Robinson]

Comment on attachment 67128 [details]
Revised patch

Almost there!

View in context: https://bugs.webkit.org/attachment.cgi?id=67128&action=prettypatch

> WebCore/platform/graphics/gpu/LoopBlinnMathUtils.cpp:80
> +bool edgeAgainstTriEdges(const FloatPoint& v0,
nit: edgeAgainstTriEdges -> edgeAgainstTriangleEdges() or something else without an abbreviation.

> WebCore/platform/graphics/gpu/LoopBlinnMathUtils.cpp:335
> +    if (numerator < 0) {
> +        // Make the "numerator >= denominator" check below work.
> +        numerator = -numerator;
> +        denominator = -denominator;
> +    }
> +    if (!numerator || !denominator || numerator >= denominator)
nit: maybe change the check to fabs(numerator) >= fabs(denominator) instead of flipping?

> WebCore/platform/graphics/gpu/LoopBlinnMathUtils.cpp:378
> +    float* r = roots;
> +    if (safeUnitDivide(q, a, *r))
> +        ++r;
> +    if (safeUnitDivide(c, q, *r))
> +        ++r;
> +    if (r - roots == 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 r - roots;
This section looks worlds better now - thanks for tackling it.  One more thing, thought: instead of having r be a float* and using pointer math, this would be done better by keeping a numRoots count and using that to index into roots[].  The pointer math logic is tricky and the result of (float* - float*) will not necessarily fit into an int on a system with 64 bit pointers and 32 bit ints, so this may generate warnings.

[Kenneth Russell]

Created attachment 67134 [details]
Revised patch

Addressed above review feedback.

[Kenneth Russell]

(In reply to comment #9)
> (From update of attachment 67128 [details])
> Almost there!
> 
> View in context: https://bugs.webkit.org/attachment.cgi?id=67128&action=prettypatch
> 
> > WebCore/platform/graphics/gpu/LoopBlinnMathUtils.cpp:80
> > +bool edgeAgainstTriEdges(const FloatPoint& v0,
> nit: edgeAgainstTriEdges -> edgeAgainstTriangleEdges() or something else without an abbreviation.

Renamed.

> > WebCore/platform/graphics/gpu/LoopBlinnMathUtils.cpp:335
> > +    if (numerator < 0) {
> > +        // Make the "numerator >= denominator" check below work.
> > +        numerator = -numerator;
> > +        denominator = -denominator;
> > +    }
> > +    if (!numerator || !denominator || numerator >= denominator)
> nit: maybe change the check to fabs(numerator) >= fabs(denominator) instead of flipping?

This is not the same test and would defeat some of the assertions. I'm leaving this as is.

> > WebCore/platform/graphics/gpu/LoopBlinnMathUtils.cpp:378
> > +    float* r = roots;
> > +    if (safeUnitDivide(q, a, *r))
> > +        ++r;
> > +    if (safeUnitDivide(c, q, *r))
> > +        ++r;
> > +    if (r - roots == 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 r - roots;
> This section looks worlds better now - thanks for tackling it.  One more thing, thought: instead of having r be a float* and using pointer math, this would be done better by keeping a numRoots count and using that to index into roots[].  The pointer math logic is tricky and the result of (float* - float*) will not necessarily fit into an int on a system with 64 bit pointers and 32 bit ints, so this may generate warnings.

OK, I've changed this to use an explicit "int numberOfRoots" local variable.

[James Robinson]

Comment on attachment 67134 [details]
Revised patch

R=me

[Kenneth Russell]

Committed r67150: <http://trac.webkit.org/changeset/67150>

[WebKit Review Bot]

http://trac.webkit.org/changeset/67150 might have broken Chromium Mac Release
The following changes are on the blame list:
http://trac.webkit.org/changeset/67152
http://trac.webkit.org/changeset/67149
http://trac.webkit.org/changeset/67150
http://trac.webkit.org/changeset/67151