include/rive/math/rectangles_to_contour.hpp

#ifndef _RIVE_RECTANGLES_TO_CONTOUR_HPP_
#define _RIVE_RECTANGLES_TO_CONTOUR_HPP_
#include <vector>
#include <unordered_set>

#include "rive/math/mat2d.hpp"
#include "rive/math/aabb.hpp"

#ifdef TESTING
// When building for testing we use an ordered map for the EdgeMap so we can get
// crossplatform stable order of contours. Visually this doesn't matter but for
// testing across results across different platforms, it does.
#include <map>
struct EdgeMapTesting
{
  bool operator()(const rive::Vec2D& a, const rive::Vec2D& b) const
  {
    return a.x < b.x || (a.x == b.x && a.y < b.y);
  }
};
using EdgeMap = std::map<rive::Vec2D, rive::Vec2D, EdgeMapTesting>;
#else
#include <unordered_map>
using EdgeMap = std::unordered_map<rive::Vec2D, rive::Vec2D>;
#endif

namespace rive
{
struct ContourPoint
{
  Vec2D vec;
  int dir; // 0 for horizontal, 1 for vertical

  ContourPoint(const Vec2D& vec, int dir) : vec(vec), dir(dir) {}

  bool operator==(const ContourPoint& other) const
  {
    return vec == other.vec && dir == other.dir;
  }
};

class RectanglesToContour;
class Contour;

// A helper for iterating the points in a contour, lazily skipping points which
// have the same value.
class ContourPointItr
{
public:
  ContourPointItr() = default;
  ContourPointItr(const Span<const ContourPoint> contour, size_t pointIndex)
      : m_contour(contour)
      , m_pointIndex(pointIndex)
  {}

  bool operator!=(const ContourPointItr& that) const
  {
    return m_pointIndex != that.m_pointIndex || m_contour != that.m_contour;
  }
  bool operator==(const ContourPointItr& that) const
  {
    return m_pointIndex == that.m_pointIndex && m_contour == that.m_contour;
  }

  ContourPointItr& operator++();

  Vec2D operator*() const;

private:
  const Span<const ContourPoint> m_contour;
  size_t m_pointIndex;
};

class Contour
{
public:
  Contour(Span<const ContourPoint> points) : m_points(points) {}
  ContourPointItr begin() const { return ContourPointItr(m_points, 0); }
  ContourPointItr end() const
  {
    return ContourPointItr(m_points, m_points.size());
  }

  size_t size() const { return m_points.size(); }
  Vec2D point(size_t index) const { return m_points[index].vec; }
  Vec2D point(size_t index, bool reversed) const
  {
    if (reversed)
    {
      return m_points[m_points.size() - 1 - index].vec;
    }
    return m_points[index].vec;
  }
  bool isClockwise() const;

private:
  Span<const ContourPoint> m_points;
};

// A helper for iterating the contours computed by RectanglesToContour. This
// allows RectanglesToContour to store a linear array of contour points for all
// contours.
class ContourItr
{
public:
  ContourItr() = default;
  ContourItr(
      const RectanglesToContour* rectanglesToContour,
      size_t contourIndex)
      : m_rectanglesToContour(rectanglesToContour)
      , m_contourIndex(contourIndex)
  {}

  bool operator!=(const ContourItr& that) const
  {
    return m_contourIndex != that.m_contourIndex ||
           m_rectanglesToContour != that.m_rectanglesToContour;
  }
  bool operator==(const ContourItr& that) const
  {
    return m_contourIndex == that.m_contourIndex &&
           m_rectanglesToContour == that.m_rectanglesToContour;
  }

  ContourItr& operator++();

  Contour operator*() const;

private:
  const RectanglesToContour* m_rectanglesToContour;
  size_t m_contourIndex;
};

class RectanglesToContour
{
public:
  // Add a rectangle to the contour computation.
  void addRect(const AABB& rect);
  // Compute the contours once all rects have been added.
  void computeContours();
  // Reset everything to start adding rects again.
  void reset();

  // Results can be queried via the utilities below.
  //
  // For example you can iterate the result:
  //   for (auto contour : converter)
  //   {
  //       for (auto point : contour)
  //       {
  //           printf("contour point: %f %f\n", point.x, point.y);
  //       }
  //   }
  size_t contourCount() const { return m_contourOffsets.size(); }
  Contour contour(size_t index) const;

  ContourItr begin() const { return ContourItr(this, 0); }
  ContourItr end() const { return ContourItr(this, m_contourOffsets.size()); }

  struct RectEvent
  {
    size_t index = 0;
    float size = 0;
    uint8_t type = 0;
    float x = 0;
    float y = 0;

    float getValue(uint8_t axis) const { return axis == 0 ? x : y; }
  };

private:
  // These arrays and maps are built up accumulating temporary data used to
  // build the contours from the rectangles. We store them on the
  // RectanglesToContour class to leverage re-using their reserved memory on
  // re-runs. For this reason it's encouraged to keep the RectanglesToContour
  // around when you know you'll need to recompute the contour from a set of
  // rectangles often/in rapid succession.
  std::vector<RectEvent> m_rectEvents;
  EdgeMap m_edgesH;
  EdgeMap m_edgesV;
  std::unordered_set<Vec2D> m_uniquePoints;
  std::vector<AABB> m_rects;
  std::vector<AABB> m_subdividedRects;
  std::vector<uint8_t> m_rectInclusionBitset;
  std::vector<Vec2D> m_sortedPointsX;
  std::vector<Vec2D> m_sortedPointsY;

  // The entire set of contour points where each contour is tightly packed
  // after the previous at offsets defined in m_contourOffsets.
  std::vector<ContourPoint> m_contourPoints;
  std::vector<size_t> m_contourOffsets;

  bool isRectIncluded(size_t rectIndex);
  void markRectIncluded(size_t rectIndex, bool isIt);

  void addUniquePoint(const Vec2D& point);
  void subdivideRectangles();
};
} // namespace rive
#endif