ash: Add basic prediction code to the laser pointer.

ash/laser/laser_pointer_view.cc

 // Copyright 2016 The Chromium Authors. All rights reserved.
 // Use of this source code is governed by a BSD-style license that can be
 // found in the LICENSE file.
 
 #include "ash/laser/laser_pointer_view.h"
 
 #include <GLES2/gl2.h>
 #include <GLES2/gl2ext.h>
 #include <GLES2/gl2extchromium.h>
 
+#include <algorithm>
+#include <array>
+#include <cmath>
 #include <memory>
 
 #include "ash/laser/laser_pointer_points.h"
 #include "ash/laser/laser_segment_utils.h"
 #include "ash/public/cpp/shell_window_ids.h"
 #include "ash/shell.h"
+#include "base/containers/adapters.h"
 #include "base/threading/thread_task_runner_handle.h"
 #include "base/timer/timer.h"
 #include "base/trace_event/trace_event.h"
 #include "cc/output/context_provider.h"
 #include "cc/quads/texture_draw_quad.h"
 #include "cc/resources/transferable_resource.h"
 #include "cc/surfaces/surface.h"
 #include "cc/surfaces/surface_manager.h"
 #include "gpu/command_buffer/client/context_support.h"
 #include "gpu/command_buffer/client/gles2_interface.h"
@@ skipping 11 matching lines @@
 
 namespace ash {
 namespace {
 
 // Variables for rendering the laser. Radius in DIP.
 const float kPointInitialRadius = 5.0f;
 const float kPointFinalRadius = 0.25f;
 const int kPointInitialOpacity = 200;
 const int kPointFinalOpacity = 10;
 const SkColor kPointColor = SkColorSetRGB(255, 0, 0);
+// Change this to a debug prediction code.
+const SkColor kPredictionPointColor = SkColorSetRGB(255, 0, 0);

[Daniele Castagna, 2017/03/15 19:07:28]

nit: you could initialize this to kPointColor to make it clear it has to be the
same if not for debug purposes.

[reveman, 2017/03/16 12:57:28]

Done.

 
 float DistanceBetweenPoints(const gfx::PointF& point1,
                             const gfx::PointF& point2) {
   return (point1 - point2).Length();
 }
 
 float LinearInterpolate(float initial_value,
                         float final_value,
                         float progress) {
   return initial_value + (final_value - initial_value) * progress;
@@ skipping 131 matching lines @@
     }
   }
   scoped_refptr<cc::ContextProvider> context_provider;
   uint32_t texture = 0;
   uint32_t image = 0;
   gpu::Mailbox mailbox;
 };
 
 // LaserPointerView
 LaserPointerView::LaserPointerView(base::TimeDelta life_duration,
+                                   base::TimeDelta presentation_delay,
                                    aura::Window* root_window)
     : laser_points_(life_duration),
+      predicted_laser_points_(life_duration),
+      presentation_delay_(presentation_delay),
       frame_sink_id_(aura::Env::GetInstance()
                          ->context_factory_private()
                          ->AllocateFrameSinkId()),
       frame_sink_support_(this,
                           aura::Env::GetInstance()
                               ->context_factory_private()
                               ->GetSurfaceManager(),
                           frame_sink_id_,
                           false /* is_root */,
                           true /* handles_frame_sink_id_invalidation */,
@@ skipping 24 matching lines @@
 
 LaserPointerView::~LaserPointerView() {
   // Make sure GPU memory buffer is unmapped before being destroyed.
   if (gpu_memory_buffer_)
     gpu_memory_buffer_->Unmap();
 }
 
 void LaserPointerView::Stop() {
   buffer_damage_rect_.Union(GetBoundingBox());
   laser_points_.Clear();
+  predicted_laser_points_.Clear();
   OnPointsUpdated();
 }
 
-void LaserPointerView::AddNewPoint(const gfx::PointF& new_point) {
+void LaserPointerView::AddNewPoint(const gfx::PointF& new_point,
+                                   const base::TimeTicks& new_time) {
+  TRACE_EVENT1("ui", "LaserPointerView::AddNewPoint", "new_point",
+               new_point.ToString());
+  TRACE_COUNTER1(
+      "ui", "LaserPointerPredictionError",
+      predicted_laser_points_.GetNumberOfPoints()
+          ? std::round((new_point -
+                        predicted_laser_points_.laser_points().front().location)
+                           .Length())
+          : 0);
+
   buffer_damage_rect_.Union(GetBoundingBox());
-  laser_points_.AddPoint(new_point);
+  laser_points_.AddPoint(new_point, new_time);
+
+  // Current time is needed to determine presentation time and the number of
+  // predicted points to add.
+  base::TimeTicks current_time = base::TimeTicks::Now();
+
+  // Create a new set of predicted points based on the last four points added.
+  // We add enough predicted points to fill the time between the new point and
+  // the expected presentation time. Note that estimated presentation time is
+  // based on current time and inefficient rendering of points can result in an
+  // actual presentation time that is later.
+  predicted_laser_points_.Clear();

[Daniele Castagna, 2017/03/15 19:07:28]

This probably creates a lot of discontinuity, since we forget completely about
the previous predictions.

It might be interesting in the future to keep these around and use them to guide
the new prediction, or maybe we could just keep around speed,acc and jerk.

[reveman, 2017/03/16 12:57:29]

Yes, there's definitely room for improvement here. I just want to land this
initial code and make sure it's easy to understand how it works so someone
interesting in improving it can do that relatively easily.

+
+  // Normalize all coordinates to screen size.
+  gfx::Size screen_size = widget_->GetNativeView()->GetBoundsInScreen().size();
+  gfx::Vector2dF scale(1.0f / screen_size.width(), 1.0f / screen_size.height());
+
+  // TODO(reveman): Determine interval based on history when event time stamps
+  // are accurate. b/36137953
+  const float kPredictionIntervalMs = 5.0f;
+  const float kMaxPointIntervalMs = 10.0f;
+  base::TimeDelta prediction_interval =
+      base::TimeDelta::FromMilliseconds(kPredictionIntervalMs);
+  base::TimeDelta max_point_interval =
+      base::TimeDelta::FromMilliseconds(kMaxPointIntervalMs);
+  base::TimeTicks last_point_time = current_time;
+
+  // Use the last four points for prediction.
+  using PositionArray = std::array<gfx::PointF, 4>;
+  PositionArray position;

[Daniele Castagna, 2017/03/15 19:07:28]

nit: positions?

[reveman, 2017/03/16 12:57:28]

then it should be velocities and accelerations too but fine with me if you
prefer that?

+  PositionArray::iterator it = position.begin();
+  for (auto& point : base::Reversed(laser_points_.laser_points())) {
+    // Stop adding positons if interval between points is too large to provide
+    // an accurate history for prediction.
+    if ((last_point_time - point.time) > max_point_interval)
+      break;
+
+    *it++ = gfx::ScalePoint(point.location, scale.x(), scale.y());
+    last_point_time = point.time;
+
+    // Stop when no more positions are needed.
+    if (it == position.end())
+      break;
+  }
+  // Pad with last point if needed.
+  std::fill(it, position.end(), *(it - 1));
+
+  // Calculate velocity.
+  gfx::Vector2dF velocity[3];
+  for (size_t i = 0; i < arraysize(velocity); ++i)
+    velocity[i] = position[i] - position[i + 1];

[Daniele Castagna, 2017/03/15 19:07:28]

It's really weird to see a velocity defined as delta pos. Should we divide this
deltaT, even if we set it to 1 for now?

[reveman, 2017/03/16 12:57:28]

I agree. Added a comment and about this for now. We'll fix this and use proper
calculations when b/36137953 has been fixed.

+
+  // Calculate acceleration.
+  gfx::Vector2dF acceleration[2];
+  for (size_t i = 0; i < arraysize(acceleration); ++i)
+    acceleration[i] = velocity[i] - velocity[i + 1];
+
+  // Calculate jerk.
+  gfx::Vector2dF jerk = acceleration[0] - acceleration[1];
+
+  // Adjust max prediction time based on speed as prediction data is not great
+  // at lower speeds.
+  const float kMaxPredictionScaleSpeed = 1e-5;
+  double speed = velocity[0].LengthSquared();
+  base::TimeTicks max_prediction_time =
+      current_time +
+      std::min(presentation_delay_ * (speed / kMaxPredictionScaleSpeed),
+               presentation_delay_);
+
+  // Add predicted points until we reach the max prediction time.
+  gfx::PointF location = position[0];
+  for (base::TimeTicks time = new_time + prediction_interval;
+       time < max_prediction_time; time += prediction_interval) {
+    velocity[0] += acceleration[0];

[Daniele Castagna, 2017/03/15 19:07:28]

Again, kinda weird to see a velocity incremented by an acceleration. Should we
multiply acceleration by deltaT?

[reveman, 2017/03/16 12:57:28]

Added a comment for now.

+    acceleration[0] += jerk;

[Daniele Castagna, 2017/03/15 19:07:28]

Have you tried dampening jerk and acceleration at each iteration?
It could help for cases with small velocity and big acceleration/jerk.

[reveman, 2017/03/16 12:57:29]

I considered that and suspect that it can help make the prediction even better
but I figured it would be better to leave that as a follow up.

+    location += velocity[0];
+
+    predicted_laser_points_.AddPoint(
+        gfx::ScalePoint(location, screen_size.width(), screen_size.height()),
+        time);
+
+    // Always stop at three predicted points as a four point history doesn't
+    // provide accurate prediction of more points.
+    if (predicted_laser_points_.GetNumberOfPoints() == 3)
+      break;
+  }
+
+  // Move forward to next presentation time.
+  base::TimeTicks next_presentation_time = current_time + presentation_delay_;
+  laser_points_.MoveForwardToTime(next_presentation_time);
+  predicted_laser_points_.MoveForwardToTime(next_presentation_time);
+
   buffer_damage_rect_.Union(GetBoundingBox());
   OnPointsUpdated();
 }
 
 void LaserPointerView::UpdateTime() {
   buffer_damage_rect_.Union(GetBoundingBox());
   // Do not add the point but advance the time if the view is in process of
   // fading away.
-  laser_points_.MoveForwardToTime(base::Time::Now());
+  base::TimeTicks next_presentation_time =
+      base::TimeTicks::Now() + presentation_delay_;
+  laser_points_.MoveForwardToTime(next_presentation_time);
+  predicted_laser_points_.MoveForwardToTime(next_presentation_time);
   buffer_damage_rect_.Union(GetBoundingBox());
   OnPointsUpdated();
 }
 
 void LaserPointerView::SetNeedsBeginFrame(bool needs_begin_frame) {
   frame_sink_support_.SetNeedsBeginFrame(needs_begin_frame);
 }
 
 void LaserPointerView::SubmitCompositorFrame(
     const cc::LocalSurfaceId& local_surface_id,
@@ skipping 25 matching lines @@
     gles2->WaitSyncTokenCHROMIUM(resources.front().sync_token.GetConstData());
 
   if (!resources.front().lost)
     returned_resources_.push_back(std::move(resource));
 }
 
 gfx::Rect LaserPointerView::GetBoundingBox() {
   // Expand the bounding box so that it includes the radius of the points on the
   // edges and antialiasing.
   gfx::Rect bounding_box = laser_points_.GetBoundingBox();
+  bounding_box.Union(predicted_laser_points_.GetBoundingBox());
   const int kOutsetForAntialiasing = 1;
   int outset = kPointInitialRadius + kOutsetForAntialiasing;
   bounding_box.Inset(-outset, -outset);
   return bounding_box;
 }
 
 void LaserPointerView::OnPointsUpdated() {
   if (pending_update_buffer_)
     return;
 
   pending_update_buffer_ = true;
   base::ThreadTaskRunnerHandle::Get()->PostTask(
       FROM_HERE, base::Bind(&LaserPointerView::UpdateBuffer,
                             weak_ptr_factory_.GetWeakPtr()));
 }
 
 void LaserPointerView::UpdateBuffer() {
-  TRACE_EVENT2("ui", "LaserPointerView::UpdatedBuffer", "damage",
-               buffer_damage_rect_.ToString(), "points",
-               laser_points_.GetNumberOfPoints());
+  TRACE_EVENT1("ui", "LaserPointerView::UpdatedBuffer", "damage",
+               buffer_damage_rect_.ToString());
 
   DCHECK(pending_update_buffer_);
   pending_update_buffer_ = false;
 
   gfx::Rect screen_bounds = widget_->GetNativeView()->GetBoundsInScreen();
   gfx::Rect update_rect = buffer_damage_rect_;
   buffer_damage_rect_ = gfx::Rect();
 
   // Create and map a single GPU memory buffer. The laser pointer will be
   // written into this buffer without any buffering. The result is that we
@@ skipping 37 matching lines @@
 
   cc::PaintFlags flags;
   flags.setStyle(cc::PaintFlags::kFill_Style);
   flags.setAntiAlias(true);
 
   // Compute the offset of the current widget.
   gfx::Vector2d widget_offset(
       widget_->GetNativeView()->GetBoundsInRootWindow().origin().x(),
       widget_->GetNativeView()->GetBoundsInRootWindow().origin().y());
 
-  int num_points = laser_points_.GetNumberOfPoints();
+  int num_points = laser_points_.GetNumberOfPoints() +
+                   predicted_laser_points_.GetNumberOfPoints();
   if (num_points) {
     LaserPointerPoints::LaserPoint previous_point = laser_points_.GetOldest();
     previous_point.location -= widget_offset + update_rect.OffsetFromOrigin();
     LaserPointerPoints::LaserPoint current_point;
     std::vector<gfx::PointF> previous_segment_points;
     float previous_radius;
     int current_opacity;
 
     for (int i = 0; i < num_points; ++i) {
-      current_point = laser_points_.laser_points()[i];
+      if (i < laser_points_.GetNumberOfPoints()) {
+        current_point = laser_points_.laser_points()[i];
+      } else {
+        current_point =
+            predicted_laser_points_
+                .laser_points()[i - laser_points_.GetNumberOfPoints()];
+      }
       current_point.location -= widget_offset + update_rect.OffsetFromOrigin();
 
       // Set the radius and opacity based on the distance.
       float current_radius = LinearInterpolate(
           kPointInitialRadius, kPointFinalRadius, current_point.age);
       current_opacity = int{LinearInterpolate(
           kPointInitialOpacity, kPointFinalOpacity, current_point.age)};
 
       // If we draw laser_points_ that are within a stroke width of each other,
       // the result will be very jagged, unless we are on the last point, then
       // we draw regardless.
       float distance_threshold = current_radius * 2.0f;
       if (DistanceBetweenPoints(previous_point.location,
                                 current_point.location) <= distance_threshold &&
           i != num_points - 1) {
         continue;
       }
 
       LaserSegment current_segment(
           previous_segment_points, gfx::PointF(previous_point.location),
           gfx::PointF(current_point.location), previous_radius, current_radius,
           i == num_points - 1);
 
       SkPath path = current_segment.path();
-      flags.setColor(SkColorSetA(kPointColor, current_opacity));
+      if (i < laser_points_.GetNumberOfPoints())
+        flags.setColor(SkColorSetA(kPointColor, current_opacity));
+      else
+        flags.setColor(SkColorSetA(kPredictionPointColor, current_opacity));
       canvas.DrawPath(path, flags);
 
       previous_segment_points = current_segment.path_points();
       previous_radius = current_radius;
       previous_point = current_point;
     }
 
     // Draw the last point as a circle.
-    flags.setColor(SkColorSetA(kPointColor, current_opacity));
     flags.setStyle(cc::PaintFlags::kFill_Style);
     canvas.DrawCircle(current_point.location, kPointInitialRadius, flags);
   }
 
   // Copy result to GPU memory buffer. This is effectiely a memcpy and unlike
   // drawing to the buffer directly this ensures that the buffer is never in a
   // state that would result in flicker.
   {
     TRACE_EVENT0("ui", "LaserPointerView::OnPointsUpdated::Copy");
 
@@ skipping 147 matching lines @@
   pending_draw_surface_ = true;
 }
 
 void LaserPointerView::OnDidDrawSurface() {
   pending_draw_surface_ = false;
   if (needs_update_surface_)
     UpdateSurface();
 }
 
 }  // namespace ash