From 20b87d28f1c0e4c71bd1f5254d66ad88c0fa6c28 Mon Sep 17 00:00:00 2001
From: Dan Vanderkam <danvdk@gmail.com>
Date: Tue, 11 Nov 2014 09:28:40 -0500
Subject: [PATCH] Speed up filled charts by down-sampling.

This is done by introducing a "fast canvas proxy", which elides
redundant moveTo and lineTo calls. This also reworks the order in which
the points are drawn to be more amenable to this optimization.
---
 auto_tests/misc/local.html               |   1 +
 auto_tests/tests/fast_canvas_proxy.js    |  99 ++++++++++++++++
 auto_tests/tests/step_plot_per_series.js |  13 ++-
 dygraph-canvas.js                        | 186 ++++++++++++++++++++++++++++---
 tests/dense-fill.html                    |  43 +++++++
 5 files changed, 323 insertions(+), 19 deletions(-)
 create mode 100644 auto_tests/tests/fast_canvas_proxy.js
 create mode 100644 tests/dense-fill.html

diff --git a/auto_tests/misc/local.html b/auto_tests/misc/local.html
index b3b4080..e419959 100644
--- a/auto_tests/misc/local.html
+++ b/auto_tests/misc/local.html
@@ -63,6 +63,7 @@
   <script type="text/javascript" src="../tests/two_digit_years.js"></script>
   <script type="text/javascript" src="../tests/hidpi.js"></script>
   <script type="text/javascript" src="../tests/smooth_plotter.js"></script>
+  <script type="text/javascript" src="../tests/fast_canvas_proxy.js"></script>
   <script type="text/javascript" src="../tests/update_options.js"></script>
   <script type="text/javascript" src="../tests/update_while_panning.js"></script>
   <script type="text/javascript" src="../tests/utils_test.js"></script>
diff --git a/auto_tests/tests/fast_canvas_proxy.js b/auto_tests/tests/fast_canvas_proxy.js
new file mode 100644
index 0000000..1e4bfaf
--- /dev/null
+++ b/auto_tests/tests/fast_canvas_proxy.js
@@ -0,0 +1,99 @@
+/**
+ * @fileoverview Tests for fastCanvasProxy, which drops superfluous segments.
+ *
+ * @author danvdk@gmail.com (Dan Vanderkam)
+ */
+var fastCanvasProxyTestCase = TestCase("fast-canvas-proxy");
+
+fastCanvasProxyTestCase.prototype.setUp = function() {
+};
+
+fastCanvasProxyTestCase.prototype.tearDown = function() {
+};
+
+var fakeCanvasContext = {
+  moveTo: function() {},
+  lineTo: function() {},
+  beginPath: function() {},
+  closePath: function() {},
+  fill: function() {},
+  stroke: function() {}
+}
+
+function extractMoveToAndLineToCalls(proxy) {
+  var calls = proxy.calls__;
+  var out = [];
+  for (var i = 0; i < calls.length; i++) {
+    var c = calls[i];
+    if (c.name == 'moveTo' || c.name == 'lineTo') {
+      out.push([c.name, c.args[0], c.args[1]]);
+    }
+  }
+  return out;
+}
+
+fastCanvasProxyTestCase.prototype.testExtraMoveTosElided = function() {
+  var htx = new Proxy(fakeCanvasContext);
+  var fastProxy = DygraphCanvasRenderer._fastCanvasProxy(htx);
+
+  fastProxy.moveTo(1, 1);
+  fastProxy.lineTo(2, 1);
+  fastProxy.moveTo(2, 1);
+  fastProxy.lineTo(3, 1);
+  fastProxy.moveTo(3, 1);
+  fastProxy.stroke();
+
+  assertEquals([['moveTo', 1, 1],
+                ['lineTo', 2, 1],
+                ['lineTo', 3, 1]], extractMoveToAndLineToCalls(htx));
+};
+
+fastCanvasProxyTestCase.prototype.testConsecutiveMoveTosElided = function() {
+  var htx = new Proxy(fakeCanvasContext);
+  var fastProxy = DygraphCanvasRenderer._fastCanvasProxy(htx);
+
+  fastProxy.moveTo(1, 1);
+  fastProxy.lineTo(2, 1);
+  fastProxy.moveTo(3, 1);
+  fastProxy.moveTo(3.1, 2);
+  fastProxy.moveTo(3.2, 3);
+  fastProxy.stroke();
+
+  assertEquals([['moveTo', 1, 1],
+                ['lineTo', 2, 1],
+                ['moveTo', 3.2, 3]], extractMoveToAndLineToCalls(htx));
+};
+
+fastCanvasProxyTestCase.prototype.testSuperfluousSegmentsElided = function() {
+  var htx = new Proxy(fakeCanvasContext);
+  var fastProxy = DygraphCanvasRenderer._fastCanvasProxy(htx);
+
+  fastProxy.moveTo(0.6, 1);
+  fastProxy.lineTo(0.7, 2);
+  fastProxy.lineTo(0.8, 3);
+  fastProxy.lineTo(0.9, 4);
+  fastProxy.lineTo(1.0, 5);  // max for Math.round(x) == 1
+  fastProxy.lineTo(1.1, 3);
+  fastProxy.lineTo(1.2, 0);  // min for Math.round(x) == 1
+  fastProxy.lineTo(1.3, 1);
+  fastProxy.lineTo(1.4, 2);
+  fastProxy.moveTo(1.4, 2);
+  fastProxy.lineTo(1.5, 2);  // rounding up to 2
+  fastProxy.moveTo(1.5, 2);
+  fastProxy.lineTo(1.6, 3);
+  fastProxy.moveTo(1.6, 3);
+  fastProxy.lineTo(1.7, 30);  // max for Math.round(x) == 2
+  fastProxy.moveTo(1.7, 30);
+  fastProxy.lineTo(1.8, -30);  // min for Math.round(x) == 2
+  fastProxy.moveTo(1.8, -30);
+  fastProxy.lineTo(1.9, 0);
+  fastProxy.moveTo(3, 0);  // dodge the "don't touch the last pixel" rule.
+  fastProxy.stroke();
+
+  assertEquals([['moveTo', 0.6, 1],
+                ['lineTo', 1.0, 5],
+                ['lineTo', 1.2, 0],
+                ['lineTo', 1.7, 30],
+                ['lineTo', 1.8, -30],
+                ['moveTo', 3, 0]], extractMoveToAndLineToCalls(htx));
+};
diff --git a/auto_tests/tests/step_plot_per_series.js b/auto_tests/tests/step_plot_per_series.js
index d1bf323..2364561 100644
--- a/auto_tests/tests/step_plot_per_series.js
+++ b/auto_tests/tests/step_plot_per_series.js
@@ -1,6 +1,11 @@
 /**
  * @fileoverview Test cases for the option "stepPlot" especially for the scenario where the option is not set for the whole graph but for single series.
  *
+ * TODO(danvk): delete this test once dpxdt screenshot tests are part of the
+ *     main dygraphs repo. The tests have extremely specific expectations about
+ *     how drawing is performed. It's more realistic to test the resulting
+ *     pixels.
+ *
  * @author julian.eichstaedt@ch.sauter-bc.com (Fr. Sauter AG)
  */
 var StepTestCase = TestCase("step-plot-per-series");
@@ -148,7 +153,7 @@ StepTestCase.prototype.testMixedModeStepAndLineStackedAndFilled = function() {
     CanvasAssertions.assertLineDrawn(htx, xy1, xy2, attrs);
     xy1 = xy2;
     xy2 = g.toDomCoords(x2, y2base);
-    CanvasAssertions.assertLineDrawn(htx, xy1, xy2, attrs);
+    // CanvasAssertions.assertLineDrawn(htx, xy1, xy2, attrs);
     xy1 = xy2;
     xy2 = g.toDomCoords(x1, y1base);
     CanvasAssertions.assertLineDrawn(htx, xy1, xy2, attrs);
@@ -172,7 +177,7 @@ StepTestCase.prototype.testMixedModeStepAndLineStackedAndFilled = function() {
     CanvasAssertions.assertLineDrawn(htx, xy1, xy2, attrs);
     xy1 = xy2;
     xy2 = g.toDomCoords(x2, y2base);
-    CanvasAssertions.assertLineDrawn(htx, xy1, xy2, attrs);
+    // CanvasAssertions.assertLineDrawn(htx, xy1, xy2, attrs);
     xy1 = xy2;
     xy2 = g.toDomCoords(x1, y1base);
     CanvasAssertions.assertLineDrawn(htx, xy1, xy2, attrs);
@@ -201,7 +206,7 @@ StepTestCase.prototype.testMixedModeStepAndLineStackedAndFilled = function() {
     CanvasAssertions.assertLineDrawn(htx, xy1, xy2, attrs);
     xy1 = xy2;
     xy2 = g.toDomCoords(x2, y2base);
-    CanvasAssertions.assertLineDrawn(htx, xy1, xy2, attrs);
+    // CanvasAssertions.assertLineDrawn(htx, xy1, xy2, attrs);
     xy1 = xy2;
     xy2 = g.toDomCoords(x1, y1base);
     CanvasAssertions.assertLineDrawn(htx, xy1, xy2, attrs);
@@ -225,7 +230,7 @@ StepTestCase.prototype.testMixedModeStepAndLineStackedAndFilled = function() {
     CanvasAssertions.assertLineDrawn(htx, xy1, xy2, attrs);
     xy1 = xy2;
     xy2 = g.toDomCoords(x2, y2base);
-    CanvasAssertions.assertLineDrawn(htx, xy1, xy2, attrs);
+    // CanvasAssertions.assertLineDrawn(htx, xy1, xy2, attrs);
     xy1 = xy2;
     xy2 = g.toDomCoords(x1, y1base);
     CanvasAssertions.assertLineDrawn(htx, xy1, xy2, attrs);
diff --git a/dygraph-canvas.js b/dygraph-canvas.js
index ea488ca..df8bfb5 100644
--- a/dygraph-canvas.js
+++ b/dygraph-canvas.js
@@ -626,6 +626,128 @@ DygraphCanvasRenderer._errorPlotter = function(e) {
   ctx.fill();
 };
 
+
+/**
+ * Proxy for CanvasRenderingContext2D which drops moveTo/lineTo calls which are
+ * superfluous. It accumulates all movements which haven't changed the x-value
+ * and only applies the two with the most extreme y-values.
+ * 
+ * Calls to lineTo/moveTo must have non-decreasing x-values.
+ */
+DygraphCanvasRenderer._fastCanvasProxy = function(context) {
+  var pendingActions = [];  // array of [type, x, y] tuples
+  var lastRoundedX = null;
+  var extremeYs = null;  // [minY, maxY] for lastRoundedX
+
+  var LINE_TO = 1,
+      MOVE_TO = 2;
+
+  var actionCount = 0;  // number of moveTos and lineTos passed to context.
+
+  // Drop superfluous motions
+  // Assumes all pendingActions have the same (rounded) x-value.
+  var compressActions = function(opt_losslessOnly) {
+    if (pendingActions.length <= 1) return;
+
+    // Lossless compression: drop inconsequential moveTos.
+    for (var i = pendingActions.length - 1; i > 0; i--) {
+      var action = pendingActions[i];
+      if (action[0] == MOVE_TO) {
+        var prevAction = pendingActions[i - 1];
+        if (prevAction[1] == action[1] && prevAction[2] == action[2]) {
+          pendingActions.splice(i, 1);
+        }
+      }
+    }
+
+    // Lossless compression: ... drop consecutive moveTos ...
+    for (var i = 0; i < pendingActions.length - 1; /* incremented internally */) {
+      var action = pendingActions[i];
+      if (action[0] == MOVE_TO && pendingActions[i + 1][0] == MOVE_TO) {
+        pendingActions.splice(i, 1);
+      } else {
+        i++;
+      }
+    }
+
+    // Lossy compression: ... drop all but the extreme y-values ...
+    if (pendingActions.length > 2 && !opt_losslessOnly) {
+      // keep an initial moveTo, but drop all others.
+      var startIdx = 0;
+      if (pendingActions[0][0] == MOVE_TO) startIdx++;
+      var minIdx = null, maxIdx = null;
+      for (var i = startIdx; i < pendingActions.length; i++) {
+        var action = pendingActions[i];
+        if (action[0] != LINE_TO) continue;
+        if (minIdx === null && maxIdx === null) {
+          minIdx = i;
+          maxIdx = i;
+        } else {
+          var y = action[2];
+          if (y < pendingActions[minIdx][2]) {
+            minIdx = i;
+          } else if (y > pendingActions[maxIdx][2]) {
+            maxIdx = i;
+          }
+        }
+      }
+      var minAction = pendingActions[minIdx],
+          maxAction = pendingActions[maxIdx];
+      pendingActions.splice(startIdx, pendingActions.length - startIdx);
+      if (minIdx < maxIdx) {
+        pendingActions.push(minAction);
+        pendingActions.push(maxAction);
+      } else if (minIdx > maxIdx) {
+        pendingActions.push(maxAction);
+        pendingActions.push(minAction);
+      } else {
+        pendingActions.push(minAction);
+      }
+    }
+  };
+
+  var flushActions = function(opt_noLossyCompression) {
+    compressActions(opt_noLossyCompression);
+    for (var i = 0, len = pendingActions.length; i < len; i++) {
+      var action = pendingActions[i];
+      if (action[0] == LINE_TO) {
+        context.lineTo(action[1], action[2]);
+      } else if (action[0] == MOVE_TO) {
+        context.moveTo(action[1], action[2]);
+      }
+    }
+    actionCount += pendingActions.length;
+    pendingActions = [];
+  };
+
+  var addAction = function(action, x, y) {
+    var rx = Math.round(x);
+    if (lastRoundedX === null || rx != lastRoundedX) {
+      flushActions();
+      lastRoundedX = rx;
+    }
+    pendingActions.push([action, x, y]);
+  };
+
+  return {
+    moveTo: function(x, y) {
+      addAction(MOVE_TO, x, y);
+    },
+    lineTo: function(x, y) {
+      addAction(LINE_TO, x, y);
+    },
+
+    // for major operations like stroke/fill, we skip compression to ensure
+    // that there are no artifacts at the right edge.
+    stroke:    function() { flushActions(true); context.stroke(); },
+    fill:      function() { flushActions(true); context.fill(); },
+    beginPath: function() { flushActions(true); context.beginPath(); },
+    closePath: function() { flushActions(true); context.closePath(); },
+
+    _count: function() { return actionCount; }
+  };
+}
+
 /**
  * Draws the shaded regions when "fillGraph" is set. Not to be confused with
  * error bars.
@@ -662,7 +784,6 @@ DygraphCanvasRenderer._fillPlotter = function(e) {
 
   if (!anySeriesFilled) return;
 
-  var ctx = e.drawingContext;
   var area = e.plotArea;
   var sets = e.allSeriesPoints;
   var setCount = sets.length;
@@ -684,9 +805,10 @@ DygraphCanvasRenderer._fillPlotter = function(e) {
 
   // process sets in reverse order (needed for stacked graphs)
   for (var setIdx = setCount - 1; setIdx >= 0; setIdx--) {
+    var ctx = e.drawingContext;
     var setName = setNames[setIdx];
     if (!g.getBooleanOption('fillGraph', setName)) continue;
-    
+
     var stepPlot = g.getBooleanOption('stepPlot', setName);
     var color = colors[setIdx];
     var axis = g.axisPropertiesForSeries(setName);
@@ -711,9 +833,37 @@ DygraphCanvasRenderer._fillPlotter = function(e) {
     ctx.fillStyle = err_color;
     ctx.beginPath();
     var last_x, is_first = true;
+
+    // If the point density is high enough, dropping segments on their way to
+    // the canvas justifies the overhead of doing so.
+    if (points.length > 2 * g.width_) {
+      ctx = DygraphCanvasRenderer._fastCanvasProxy(ctx);
+    }
+
+    // For filled charts, we draw points from left to right, then back along
+    // the x-axis to complete a shape for filling.
+    // For stacked plots, this "back path" is a more complex shape. This array
+    // stores the [x, y] values needed to trace that shape.
+    var pathBack = [];
+
+    var traceBackPath = function(baselineX, baselineY) {
+      ctx.lineTo(baselineX, baselineY);
+      if (stackedGraph) {
+        for (var i = pathBack.length - 1; i >= 0; i--) {
+          var pt = pathBack[i];
+          ctx.lineTo(pt[0], pt[1]);
+        }
+      }
+      pathBack = [];
+    };
+
+    // TODO(danvk): there are a lot of options at play in this loop.
+    //     The logic would be much clearer if some (e.g. stackGraph and
+    //     stepPlot) were split off into separate sub-plotters.
     while (iter.hasNext) {
       var point = iter.next();
       if (!Dygraph.isOK(point.y) && !stepPlot) {
+        traceBackPath(prevX, prevYs[1]);
         prevX = NaN;
         if (point.y_stacked !== null && !isNaN(point.y_stacked)) {
           baseline[point.canvasx] = area.h * point.y_stacked + area.y;
@@ -741,10 +891,10 @@ DygraphCanvasRenderer._fillPlotter = function(e) {
         }
         newYs = [ point.canvasy, lastY ];
 
-        if(stepPlot) {
+        if (stepPlot) {
           // Step plots must keep track of the top and bottom of
           // the baseline at each point.
-          if(prevYs[0] === -1) {
+          if (prevYs[0] === -1) {
             baseline[point.canvasx] = [ point.canvasy, axisY ];
           } else {
             baseline[point.canvasx] = [ point.canvasy, prevYs[0] ];
@@ -761,29 +911,35 @@ DygraphCanvasRenderer._fillPlotter = function(e) {
         }
       }
       if (!isNaN(prevX)) {
-        ctx.moveTo(prevX, prevYs[0]);
-        
         // Move to top fill point
         if (stepPlot) {
           ctx.lineTo(point.canvasx, prevYs[0]);
-        } else {
           ctx.lineTo(point.canvasx, newYs[0]);
-        }
-        // Move to bottom fill point
-        if (prevStepPlot && currBaseline) {
-          // Draw to the bottom of the baseline
-          ctx.lineTo(point.canvasx, currBaseline[1]);
         } else {
-          ctx.lineTo(point.canvasx, newYs[1]);
+          ctx.lineTo(point.canvasx, newYs[0]);
         }
 
-        ctx.lineTo(prevX, prevYs[1]);
-        ctx.closePath();
+        // Record the baseline for the reverse path.
+        if (stackedGraph) {
+          pathBack.push([prevX, prevYs[1]]);
+          if (prevStepPlot && currBaseline) {
+            // Draw to the bottom of the baseline
+            pathBack.push([point.canvasx, currBaseline[1]]);
+          } else {
+            pathBack.push([point.canvasx, newYs[1]]);
+          }
+        }
+      } else {
+        ctx.moveTo(point.canvasx, newYs[1]);
+        ctx.lineTo(point.canvasx, newYs[0]);
       }
       prevYs = newYs;
       prevX = point.canvasx;
     }
     prevStepPlot = stepPlot;
+    if (newYs) {
+      traceBackPath(point.canvasx, newYs[1]);
+    }
     ctx.fill();
   }
 };
diff --git a/tests/dense-fill.html b/tests/dense-fill.html
new file mode 100644
index 0000000..5d64998
--- /dev/null
+++ b/tests/dense-fill.html
@@ -0,0 +1,43 @@
+<!DOCTYPE html>
+<html>
+  <head>
+    <meta http-equiv="X-UA-Compatible" content="IE=EmulateIE7; IE=EmulateIE9">
+    <title>dense, filled plots</title>
+    <!--[if IE]>
+    <script type="text/javascript" src="../excanvas.js"></script>
+    <![endif]-->
+    <script type="text/javascript" src="../dygraph-dev.js"></script>
+    <style>
+    .chart {
+      width: 800px;
+      height: 500px;
+    }
+    </style>
+  </head>
+  <body>
+  <p>These charts are substantially sped up by <a href="https://github.com/danvk/dygraphs/pull/462/">down-sampling.</a></p>
+    <div class="chart" data-opts='{"fillGraph":true}'></div>
+
+    <p>step plot, filled</p>
+    <div class="chart" data-opts='{"fillGraph":true,"stepPlot":true}'></div>
+
+    <script>
+      var data = [];
+      for (var i = 0; i < 10000; i++) {
+        data.push([i, Math.sin(i/1000), Math.cos(i/1000)]);
+      }
+
+      var chartDivs = document.querySelectorAll('.chart');
+      for (var i = 0; i < chartDivs.length; i++) {
+        var chartDiv = chartDivs[i];
+        var opts = {labels: ['X', 'sin', 'cos'], animatedZooms: true};
+        var thisOpts = JSON.parse(chartDiv.getAttribute('data-opts'));
+        for (var k in thisOpts) {
+          opts[k] = thisOpts[k];
+        }
+
+        new Dygraph(chartDivs[i], data, opts);
+      }
+    </script>
+  </body>
+</html>
-- 
2.7.4