ccpr: Improve CPU checks for collinear points
Bug: skia:
Change-Id: I1373b5e9740538b2bc5c1b33644b7ec5dfadc95c
Reviewed-on: https://skia-review.googlesource.com/119982
Commit-Queue: Chris Dalton <csmartdalton@google.com>
Reviewed-by: Brian Salomon <bsalomon@google.com>
diff --git a/src/gpu/ccpr/GrCCGeometry.cpp b/src/gpu/ccpr/GrCCGeometry.cpp
index c289c40..5d7fc69 100644
--- a/src/gpu/ccpr/GrCCGeometry.cpp
+++ b/src/gpu/ccpr/GrCCGeometry.cpp
@@ -58,20 +58,58 @@
return product[0] + product[1];
}
-static inline bool are_collinear(const Sk2f& p0, const Sk2f& p1, const Sk2f& p2) {
- static constexpr float kFlatnessTolerance = 4; // 1/4 of a pixel.
+static inline bool are_collinear(const Sk2f& p0, const Sk2f& p1, const Sk2f& p2,
+ float tolerance = 1/16.f) { // 1/16 of a pixel.
+ Sk2f l = p2 - p0; // Line from p0 -> p2.
- // Area (times 2) of the triangle.
- Sk2f a = (p0 - p1) * SkNx_shuffle<1,0>(p1 - p2);
- a = (a - SkNx_shuffle<1,0>(a)).abs();
+ // lwidth = Manhattan width of l.
+ Sk2f labs = l.abs();
+ float lwidth = labs[0] + labs[1];
- // Bounding box of the triangle.
- Sk2f bbox0 = Sk2f::Min(Sk2f::Min(p0, p1), p2);
- Sk2f bbox1 = Sk2f::Max(Sk2f::Max(p0, p1), p2);
+ // d = |p1 - p0| dot | l.y|
+ // |-l.x| = distance from p1 to l.
+ Sk2f dd = (p1 - p0) * SkNx_shuffle<1,0>(l);
+ float d = dd[0] - dd[1];
- // The triangle is linear if its area is within a fraction of the largest bounding box
- // dimension, or else if its area is within a fraction of a pixel.
- return (a * (kFlatnessTolerance/2) < Sk2f::Max(bbox1 - bbox0, 1)).anyTrue();
+ // We are collinear if a box with radius "tolerance", centered on p1, touches the line l.
+ // To decide this, we check if the distance from p1 to the line is less than the distance from
+ // p1 to the far corner of this imaginary box, along that same normal vector.
+ // The far corner of the box can be found at "p1 + sign(n) * tolerance", where n is normal to l:
+ //
+ // abs(dot(p1 - p0, n)) <= dot(sign(n) * tolerance, n)
+ //
+ // Which reduces to:
+ //
+ // abs(d) <= (n.x * sign(n.x) + n.y * sign(n.y)) * tolerance
+ // abs(d) <= (abs(n.x) + abs(n.y)) * tolerance
+ //
+ // Use "<=" in case l == 0.
+ return std::abs(d) <= lwidth * tolerance;
+}
+
+static inline bool are_collinear(const SkPoint P[4], float tolerance = 1/16.f) { // 1/16 of a pixel.
+ Sk4f Px, Py; // |Px Py| |p0 - p3|
+ Sk4f::Load2(P, &Px, &Py); // |. . | = |p1 - p3|
+ Px -= Px[3]; // |. . | |p2 - p3|
+ Py -= Py[3]; // |. . | | 0 |
+
+ // Find [lx, ly] = the line from p3 to the furthest-away point from p3.
+ Sk4f Pwidth = Px.abs() + Py.abs(); // Pwidth = Manhattan width of each point.
+ int lidx = Pwidth[0] > Pwidth[1] ? 0 : 1;
+ lidx = Pwidth[lidx] > Pwidth[2] ? lidx : 2;
+ float lx = Px[lidx], ly = Py[lidx];
+ float lwidth = Pwidth[lidx]; // lwidth = Manhattan width of [lx, ly].
+
+ // |Px Py|
+ // d = |. . | * | ly| = distances from each point to l (two of the distances will be zero).
+ // |. . | |-lx|
+ // |. . |
+ Sk4f d = Px*ly - Py*lx;
+
+ // We are collinear if boxes with radius "tolerance", centered on all 4 points all touch line l.
+ // (See the rationale for this formula in the above, 3-point version of this function.)
+ // Use "<=" in case l == 0.
+ return (d.abs() <= lwidth * tolerance).allTrue();
}
// Returns whether the (convex) curve segment is monotonic with respect to [endPt - startPt].
@@ -293,20 +331,19 @@
void GrCCGeometry::cubicTo(const SkPoint P[4], float inflectPad, float loopIntersectPad) {
SkASSERT(fBuildingContour);
SkASSERT(P[0] == fPoints.back());
+
+ // Don't crunch on the curve or inflate geometry if it is nearly flat (or just very small).
+ // Flat curves can break the math below.
+ if (are_collinear(P)) {
+ this->lineTo(P[3]);
+ return;
+ }
+
Sk2f p0 = Sk2f::Load(P);
Sk2f p1 = Sk2f::Load(P+1);
Sk2f p2 = Sk2f::Load(P+2);
Sk2f p3 = Sk2f::Load(P+3);
- // Don't crunch on the curve or inflate geometry if it is nearly flat (or just very small).
- // Flat curves can break the math below.
- if (are_collinear(p0, p1, p2) &&
- are_collinear(p1, p2, p3) &&
- are_collinear(p0, (p1 + p2) * .5f, p3)) {
- this->appendLine(p3);
- return;
- }
-
// Also detect near-quadratics ahead of time.
Sk2f tan0, tan1, c;
if (is_cubic_nearly_quadratic(p0, p1, p2, p3, tan0, tan1, c)) {