bin/ui/sketchy/stroke/stroke_fitter.cc

// Copyright 2017 The Fuchsia 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 "garnet/bin/ui/sketchy/stroke/stroke_fitter.h"

#include "lib/fxl/logging.h"

namespace {

constexpr float kEpsilon = 6e-6;
constexpr float kErrorThreshold = 10;
// Minimum number of fitting points for a curve to be counted as stable.
constexpr int kMinStableSize = 12;

inline std::ostream& operator<<(std::ostream& os, const glm::vec2& pt) {
  return os << "(" << pt.x << "," << pt.y << ")";
}

}  // namespace

namespace sketchy_service {

StrokeFitter::StrokeFitter(glm::vec2 start_pt) {
  points_.push_back(start_pt);
  params_.push_back(0.f);
}

void StrokeFitter::Extend(const std::vector<glm::vec2>& sampled_pts) {
  for (const auto& pt : sampled_pts) {
    float dist = glm::distance(pt, points_.back());
    if (dist > kEpsilon) {
      points_.push_back(pt);
      params_.push_back(params_.back() + dist);
    }
  }
}

bool StrokeFitter::FitAndPop(StrokePath* path) {
  FXL_DCHECK(points_.size() == params_.size());
  if (points_.size() > 1) {
    // Pick as many as we can into the stable part.
    FitSampleRange(
        0, static_cast<int>(points_.size()) - 1, points_[1] - points_[0],
        points_[points_.size() - 1] - points_[points_.size() - 2], path);
    if (points_.size() > kMinStableSize) {
      // Pop the points and params, leaving two points for future fitting.
      auto point0 = points_[points_.size() - 2];
      auto point1 = points_[points_.size() - 1];
      points_.resize(2);
      points_[0] = point0;
      points_[1] = point1;
      auto param0 = params_[params_.size() - 2];
      auto param1 = params_[params_.size() - 1];
      params_.resize(2);
      params_[0] = param0;
      params_[1] = param1;
      return true;
    }
  }
  return false;
}

void StrokeFitter::FitSampleRange(int start_index, int end_index,
                                  glm::vec2 left_tangent,
                                  glm::vec2 right_tangent, StrokePath* path) {
  FXL_DCHECK(glm::length(left_tangent) > 0 && glm::length(right_tangent) > 0)
      << "  left: " << left_tangent << "  right: " << right_tangent;
  FXL_DCHECK(end_index > start_index);

  if (end_index - start_index == 1) {
    // Only two points... use a heuristic.
    // TODO: Double-check this heuristic (perhaps normalization needed?)
    // TODO: Perhaps this segment can be omitted entirely, e.g. by blending
    //       endpoints of the adjacent segments.
    CubicBezier2f line;
    line.pts[0] = points_[start_index];
    line.pts[3] = points_[end_index];
    line.pts[1] = line.pts[0] + (left_tangent * 0.25f);
    line.pts[2] = line.pts[3] + (right_tangent * 0.25f);
    FXL_DCHECK(!std::isnan(line.pts[0].x));
    FXL_DCHECK(!std::isnan(line.pts[0].y));
    FXL_DCHECK(!std::isnan(line.pts[1].x));
    FXL_DCHECK(!std::isnan(line.pts[1].y));
    FXL_DCHECK(!std::isnan(line.pts[2].x));
    FXL_DCHECK(!std::isnan(line.pts[2].y));
    FXL_DCHECK(!std::isnan(line.pts[3].x));
    FXL_DCHECK(!std::isnan(line.pts[3].y));
    path->ExtendWithCurve(line);
    return;
  }

  // Normalize cumulative length between 0.0 and 1.0.
  float param_shift = -params_[start_index];
  float param_scale = 1.f / (params_[end_index] + param_shift);

  CubicBezier2f curve =
      FitCubicBezier2f(&(points_[start_index]), end_index - start_index + 1,
                       &(params_[start_index]), param_shift, param_scale,
                       left_tangent, right_tangent);

  int split_index = (end_index + start_index + 1) / 2;
  float max_error = 0.f;
  for (int i = start_index; i <= end_index; ++i) {
    float t = (params_[i] + param_shift) * param_scale;
    glm::vec2 diff = points_[i] - curve.Evaluate(t);
    float error = glm::dot(diff, diff);
    if (error > max_error) {
      max_error = error;
      split_index = i;
    }
  }

  // The current fit is good enough... add it to the path and stop recursion.
  if (max_error < kErrorThreshold) {
    FXL_DCHECK(!std::isnan(curve.pts[0].x));
    FXL_DCHECK(!std::isnan(curve.pts[0].y));
    FXL_DCHECK(!std::isnan(curve.pts[1].x));
    FXL_DCHECK(!std::isnan(curve.pts[1].y));
    FXL_DCHECK(!std::isnan(curve.pts[2].x));
    FXL_DCHECK(!std::isnan(curve.pts[2].y));
    FXL_DCHECK(!std::isnan(curve.pts[3].x));
    FXL_DCHECK(!std::isnan(curve.pts[3].y));
    path->ExtendWithCurve(curve);
    return;
  }

  // Error is too large... split into two ranges and fit each.
  FXL_DCHECK(split_index > start_index && split_index < end_index);
  // Compute the tangent on each side of the split point.
  // TODO: some filtering may be desirable here.
  glm::vec2 right_middle_tangent =
      points_[split_index + 1] - points_[split_index];
  if (glm::length(right_middle_tangent) == 0.f) {
    // The two points on either side of the split point are identical: the
    // user's path doubled back upon itself.  Instead, compute the tangent using
    // the point at the split-index.
    right_middle_tangent = points_[split_index + 1] - points_[split_index];
  }
  glm::vec2 left_middle_tangent = right_middle_tangent * -1.f;
  FitSampleRange(start_index, split_index, left_tangent, left_middle_tangent,
                 path);
  FitSampleRange(split_index, end_index, right_middle_tangent, right_tangent,
                 path);
}

}  // namespace sketchy_service