sdfutils.cc

Go to the documentation of this file.

#include "ion/text/sdfutils.h"

#include "ion/base/logging.h"
#include "ion/math/utils.h"
#include "ion/math/vector.h"
#include "ion/math/vectorutils.h"

namespace ion {
namespace text {

namespace {

using base::Array2;
using math::Vector2d;
using math::Vector2i;

typedef Array2<double> Grid;




class DistanceComputer {
 public:
  DistanceComputer() {}
  ~DistanceComputer() {}

  const Grid Compute(const Grid& image);

 private:
  struct Data {
    Data(const Grid& image_in, const Array2<Vector2d>& gradients_in)
        : image(image_in),
          gradients(gradients_in),
          cur_pixel(0, 0),
          any_distance_changed(false) {}

    void SetCurDistance(double dist) {
      distances.Set(cur_pixel[0], cur_pixel[1], dist);
    }
    double GetCurDistance() const {
      return distances.Get(cur_pixel[0], cur_pixel[1]);
    }
    void SetCurDistanceToEdge(const Vector2i& dist) {
      distances_to_edges.Set(cur_pixel[0], cur_pixel[1], dist);
    }
    const Vector2i& GetDistanceToEdge(const Vector2i& pixel) const {
      return distances_to_edges.Get(pixel[0], pixel[1]);
    }

    const Grid& image;
    const Array2<Vector2d>& gradients;
    Array2<Vector2i> distances_to_edges;
    Grid distances;
    Vector2i cur_pixel;
    bool any_distance_changed;
  };

  static const Array2<Vector2d> ComputeGradients(const Grid& image);

  static const Vector2d FilterPixel(const Grid& image, size_t x, size_t y);

  static const Grid InitializeDistanceGrid(
      const Grid& image, const Array2<Vector2d>& gradients);

  static double ApproximateDistanceToEdge(double value,
                                          const Vector2d& gradient);

  static void ComputeDistances(Data* data);

  static void UpdateDistance(Data* data, const Vector2i& offset, double* dist);

  static double ComputeDistanceToEdge(Data* data, const Vector2i& pixel,
                                      const Vector2d& vec_to_edge_pixel);

  static const double kLargeDistance;
};

const double DistanceComputer::kLargeDistance = 1e6;

const Grid DistanceComputer::Compute(const Grid& image) {
  const Array2<Vector2d> gradients = ComputeGradients(image);

  Data data(image, gradients);
  data.distances_to_edges =
      Array2<Vector2i>(image.GetWidth(), image.GetHeight(), Vector2i::Zero());
  data.distances = InitializeDistanceGrid(image, gradients);
  ComputeDistances(&data);

  return data.distances;
}

const Array2<Vector2d> DistanceComputer::ComputeGradients(const Grid& image) {
  const size_t h = image.GetHeight();
  const size_t w = image.GetWidth();

  Array2<Vector2d> gradients(w, h, Vector2d::Zero());


  for (size_t y = 1; y < h - 1; ++y) {
    for (size_t x = 1; x < w - 1; ++x) {
      const double value = image.Get(x, y);
      if (value > 0.0 && value < 1.0)
        gradients.Set(x, y, FilterPixel(image, x, y));
    }
  }
  return gradients;
}

const Vector2d DistanceComputer::FilterPixel(const Grid& image,
                                             size_t x, size_t y) {
  static const double kSqrt2 = sqrt(2.0);
  static const double kFilter[3][3] = {
    { -1.0,    0.0, 1.0    },
    { -kSqrt2, 0.0, kSqrt2 },
    { -1.0,    0.0, 1.0    },
  };

  Vector2d filtered(0.0, 0.0);
  for (int i = 0; i < 3; ++i) {
    for (int j = 0; j < 3; ++j) {
      const double val = image.Get(x + j - 1, y + i - 1);
      filtered[0] += kFilter[i][j] * val;
      filtered[1] += kFilter[j][i] * val;
    }
  }
  return math::Normalized(filtered);
}

const Grid DistanceComputer::InitializeDistanceGrid(
    const Grid& image, const Array2<Vector2d>& gradients) {
  const size_t h = image.GetHeight();
  const size_t w = image.GetWidth();
  Grid distances(w, h);
  for (size_t y = 0; y < h; ++y) {
    for (size_t x = 0; x < w; ++x) {
      const double v = image.Get(x, y);
      const double dist = v <= 0.0 ? kLargeDistance :
                          v >= 1.0 ? 0.0 :
                          ApproximateDistanceToEdge(v, gradients.Get(x, y));
      distances.Set(x, y, dist);
    }
  }
  return distances;
}

double DistanceComputer::ApproximateDistanceToEdge(
    double value, const Vector2d& gradient) {
  if (gradient[0] == 0.0 || gradient[1] == 0.0) {
    return 0.5 - value;
  } else {
    Vector2d g = math::Normalized(Vector2d(math::Abs(gradient[0]),
                                           math::Abs(gradient[1])));
    if (g[0] < g[1])
      std::swap(g[0], g[1]);
    const float gradient_value = static_cast<float>(0.5 * g[1] / g[0]);
    double dist;
    if (value < gradient_value) {
      dist = 0.5 * (g[0] + g[1]) - sqrt(2.0 * g[0] * g[1] * value);
    } else if (value < 1.0 - gradient_value) {
      dist = (0.5 - value) * g[0];
    } else {
      dist = -0.5 * (g[0] + g[1]) + sqrt(2.0 * g[0] * g[1] * (1.0 - value));
    }
    return dist;
  }
}

void DistanceComputer::ComputeDistances(Data* data) {
  const int height = static_cast<int>(data->image.GetHeight());
  const int width = static_cast<int>(data->image.GetWidth());

  do {
    data->any_distance_changed = false;

    for (int y = 1; y < height; ++y) {
      data->cur_pixel[1] = y;

      for (int x = 0; x < width; ++x) {
        data->cur_pixel[0] = x;
        double dist = data->GetCurDistance();
        if (dist > 0.0) {
          UpdateDistance(data, Vector2i(0, -1), &dist);
          if (x > 0) {
            UpdateDistance(data, Vector2i(-1, 0), &dist);
            UpdateDistance(data, Vector2i(-1, -1), &dist);
          }
          if (x < width - 1) {
            UpdateDistance(data, Vector2i(1, -1), &dist);
          }
        }
      }

      for (int x = width - 2; x >= 0; --x) {
        data->cur_pixel[0] = x;
        double dist = data->GetCurDistance();
        if (dist > 0.0) {
          UpdateDistance(data, Vector2i(1, 0), &dist);
        }
      }
    }

    for (int y = height - 2; y >= 0; --y) {
      data->cur_pixel[1] = y;

      for (int x = width - 1; x >= 0; --x) {
        data->cur_pixel[0] = x;
        double dist = data->GetCurDistance();
        if (dist > 0.0) {
          UpdateDistance(data, Vector2i(0, 1), &dist);
          if (x > 0) {
            UpdateDistance(data, Vector2i(-1, 1), &dist);
          }
          if (x < width - 1) {
            UpdateDistance(data, Vector2i(1, 0), &dist);
            UpdateDistance(data, Vector2i(1, 1), &dist);
          }
        }
      }

      for (int x = 1; x < width; ++x) {
        data->cur_pixel[0] = x;
        double dist = data->GetCurDistance();
        if (dist > 0.0) {
          UpdateDistance(data, Vector2i(-1, 0), &dist);
        }
      }
    }
  } while (data->any_distance_changed);

  for (int y = 0; y < height; ++y) {
    for (int x = 0; x < width; ++x) {
      data->distances.Set(x, y, std::max(0.0, data->distances.Get(x, y)));
    }
  }
}

void DistanceComputer::UpdateDistance(Data* data, const Vector2i& offset,
                                      double* dist) {
  const Vector2i test_pixel = data->cur_pixel + offset;
  const Vector2i& xy_dist = data->GetDistanceToEdge(test_pixel);
  const Vector2i edge_pixel = test_pixel - xy_dist;
  const Vector2i new_xy_dist = xy_dist - offset;
  const double new_dist = ComputeDistanceToEdge(data, edge_pixel,
                                                Vector2d(new_xy_dist));
  static const double kEpsilon = 1e-3;
  if (new_dist < *dist - kEpsilon) {
    data->SetCurDistance(new_dist);
    data->SetCurDistanceToEdge(new_xy_dist);
    *dist = new_dist;
    data->any_distance_changed = true;
  }
}

double DistanceComputer::ComputeDistanceToEdge(
    Data* data, const Vector2i& pixel, const Vector2d& vec_to_edge_pixel) {
  const double value = math::Clamp(data->image.Get(pixel[0], pixel[1]),
                                   0.0, 1.0);

  if (value == 0.0)
    return kLargeDistance;

  const double length = math::Length(vec_to_edge_pixel);
  const double dist =
      length > 0.0 ?
      ApproximateDistanceToEdge(value, vec_to_edge_pixel) :
      ApproximateDistanceToEdge(value, data->gradients.Get(pixel[0], pixel[1]));

  return length + dist;
}




static const Grid PadGrid(const Grid& grid, size_t padding) {
  const size_t width = grid.GetWidth();
  const size_t height = grid.GetHeight();
  Grid padded_grid(width + 2 * padding, height + 2 * padding, 0.0);
  for (size_t y = 0; y < height ; ++y) {
    for (size_t x = 0; x < width; ++x) {
      padded_grid.Set(padding + x, padding + y, grid.Get(x, y));
    }
  }
  return padded_grid;
}

static const Grid InvertGrid(const Grid& grid) {
  const size_t w = grid.GetWidth();
  const size_t h = grid.GetHeight();
  Grid inverted(w, h);
  for (size_t y = 0; y < h; ++y) {
    for (size_t x = 0; x < w; ++x) {
      inverted.Set(x, y, 1.0 - grid.Get(x, y));
    }
  }
  return inverted;
}

static const Grid BuildSdfGrid(const Grid& grid) {
  const size_t height = grid.GetHeight();
  const size_t width = grid.GetWidth();
  Grid sdf(width, height);
  if (height > 0 && width > 0) {
    DistanceComputer dc;
    const Grid bg_distances = dc.Compute(grid);
    const Grid fg_distances = dc.Compute(InvertGrid(grid));
    for (size_t y = 0; y < height; ++y) {
      for (size_t x = 0; x < width; ++x) {
        sdf.Set(x, y, bg_distances.Get(x, y) - fg_distances.Get(x, y));
      }
    }
  }
  return sdf;
}

}  // anonymous namespace




const Grid ComputeSdfGrid(const Grid& image_grid, size_t padding) {
  return BuildSdfGrid(PadGrid(image_grid, padding));
}

}  // namespace text
}  // namespace ion