[webkit-reviews] review denied: [Bug 45251] Add math utilities for cubic curve processing : [Attachment 67082] Revised patch
bugzilla-daemon at webkit.org
bugzilla-daemon at webkit.org
Thu Sep 9 14:55:25 PDT 2010
James Robinson <jamesr at chromium.org> has denied Kenneth Russell
<kbr at google.com>'s request for review:
Bug 45251: Add math utilities for cubic curve processing
https://bugs.webkit.org/show_bug.cgi?id=45251
Attachment 67082: Revised patch
https://bugs.webkit.org/attachment.cgi?id=67082&action=review
------- Additional Comments from James Robinson <jamesr at chromium.org>
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.
More information about the webkit-reviews
mailing list