Better decisions about choosing AAA versus DAA

The Chrome perf regressions (817942, 819185) are
caused by the bad choices to use DAA instead of
AAA for stroking simple curves. (BTW, in my tests,
DAA is still faster than SAA so it's not too much
of a regression.)

We previously only considered the number of line segments,
but not the length of each segment. That leads to our
wrong judgement of the path complexity (the number of
intersections per scan line) when there are many short
line segments.

The change will bring the following performance change
to our nanobench:

    8.45% slower in clip_strategy_path_10
    8.39% slower in draw_stroke_bezier_quad_square_bevel_10
    3.91% slower in chart_aa
    3.76% faster in lines
    6.29% faster in path_stroke_big_oval
   22.81% faster in path_stroke_big_circle
   24.44% faster in giantdashline_vert_2

The two slower cases, clip_strategy_path_10
and draw_stroke_bezier_quad_square_bevel_10 are caused by
choosing AAA over DAA. Those two tests do seem to be simple
strokes. I'll later investigate why AAA is slower than DAA
for those two cases.

For now, I think that this change is sufficient to address
those chromium perf regresssions.

Bug: chromium:817942 chromium:819185
Change-Id: I1d13c968b17f257b4ede4c70e552db5016baf1ab
Reviewed-on: https://skia-review.googlesource.com/115583
Commit-Queue: Yuqian Li <liyuqian@google.com>
Reviewed-by: Cary Clark <caryclark@google.com>

1 files changed, 34 insertions, 0 deletions

diff --git a/src/core/SkScan_AntiPath.cpp b/src/core/SkScan_AntiPath.cpp
index 4be24efd6e..ad181a77f8 100644
--- a/src/core/SkScan_AntiPath.cpp
+++ b/src/core/SkScan_AntiPath.cpp
@@ -590,8 +590,42 @@ static bool ShouldUseDAA(const SkPath& path) {
     if (!gSkUseDeltaAA) {
         return false;
     }
+
+#ifdef SK_SUPPORT_LEGACY_AA_CHOICE
     const SkRect& bounds = path.getBounds();
     return !path.isConvex() && path.countPoints() >= SkTMax(bounds.width(), bounds.height()) / 8;
+#else
+    constexpr int kSampleSize = 8;
+    constexpr SkScalar kComplexityThreshold = 0.25;
+
+    int n = path.countPoints();
+    if (path.isConvex() || n < kSampleSize) {
+        return false;
+    }
+
+    SkScalar sumLength = 0;
+    SkPoint lastPoint = path.getPoint(0);
+    for(int i = 1; i < kSampleSize; ++i) {
+        SkPoint point = path.getPoint(i);
+        sumLength += SkPoint::Distance(lastPoint, point);
+        lastPoint = point;
+    }
+    SkScalar diagonal = SkPoint::Length(path.getBounds().width(), path.getBounds().height());
+
+    // On average, what's the distance between two consecutive points; the number is normalized
+    // to a range of [0, 1] where 1 corresponds to the maximum length of the diagonal.
+    SkScalar sampleSpan = sumLength / (kSampleSize - 1) / diagonal;
+
+
+    // If the path is consist of random line segments, the number of intersections should be
+    // proportional to (n * sampleSpan)^2
+    SkScalar intersections = (n * sampleSpan) * (n * sampleSpan);
+
+    // The number of intersections per scanline should be proportional to this number.
+    SkScalar complexity = intersections / path.getBounds().height();
+
+    return complexity >= kComplexityThreshold;
+#endif
 }
 
 static bool ShouldUseAAA(const SkPath& path) {