Move shared path types into shared header
diff --git a/include/rive/command_path.hpp b/include/rive/command_path.hpp index 6da63dd..5108df3 100644 --- a/include/rive/command_path.hpp +++ b/include/rive/command_path.hpp
@@ -2,10 +2,9 @@ #define _RIVE_COMMAND_PATH_HPP_ #include "rive/math/mat2d.hpp" +#include "rive/math/path_types.hpp" namespace rive { - enum class FillRule { nonZero, evenOdd }; - class RenderPath; /// Abstract path used to build up commands used for rendering.
diff --git a/include/rive/hittest_command_path.hpp b/include/rive/hittest_command_path.hpp new file mode 100644 index 0000000..2301449 --- /dev/null +++ b/include/rive/hittest_command_path.hpp
@@ -0,0 +1,42 @@ +/* + * Copyright 2022 Rive + */ + +#ifndef _RIVE_HITTEST_COMMAND_PATH_HPP_ +#define _RIVE_HITTEST_COMMAND_PATH_HPP_ + +#include "rive/command_path.hpp" +#include "rive/math/hit_test.hpp" + +namespace rive { + class HitTester; + + class HitTestCommandPath : public CommandPath { + HitTester m_Tester; + Mat2D m_Xform; + IAABB m_Area; + FillRule m_FillRule = FillRule::nonZero; + + public: + + HitTestCommandPath(const IAABB& area); + + // can call this between calls to move/line/etc. + void setXform(const Mat2D& xform) { m_Xform = xform; } + + bool wasHit(); + + // These 4 are not a good for the hit-tester + void reset() override; + void fillRule(FillRule value) override; + void addPath(CommandPath* path, const Mat2D& transform) override; + RenderPath* renderPath() override; + + void moveTo(float x, float y) override; + void lineTo(float x, float y) override; + void + cubicTo(float ox, float oy, float ix, float iy, float x, float y) override; + void close() override; + }; +} // namespace rive +#endif
diff --git a/include/rive/math/hit_test.hpp b/include/rive/math/hit_test.hpp new file mode 100644 index 0000000..1e30bde --- /dev/null +++ b/include/rive/math/hit_test.hpp
@@ -0,0 +1,49 @@ +/* + * Copyright 2022 Rive + */ + +#ifndef _RIVE_HITTEST_HPP_ +#define _RIVE_HITTEST_HPP_ + +#include "rive/math/aabb.hpp" +#include "rive/math/path_types.hpp" +#include "rive/math/vec2d.hpp" + +#include <cstdint> +#include <vector> + +namespace rive { + +class HitTester { + std::vector<int> m_DW; // width * height delta-windings + Vec2D m_First, m_Prev; + Vec2D m_offset; + float m_height; + int m_IWidth, m_IHeight; + int m_WindingMask; + bool m_ExpectsMove; + + void recurse_cubic(Vec2D b, Vec2D c, Vec2D d, int count); + +public: + HitTester() {} + HitTester(const IAABB& area) { reset(area); } + + void reset(); + void reset(const IAABB& area, FillRule = rive::FillRule::nonZero); + + void move(Vec2D); + void line(Vec2D); + void quad(Vec2D, Vec2D); + void cubic(Vec2D, Vec2D, Vec2D); + void close(); + + void addRect(const AABB&, const Mat2D&, PathDirection = PathDirection::ccw); + + bool test(); // calls reset() afterwards +}; + +} + +#endif +
diff --git a/include/rive/math/path_types.hpp b/include/rive/math/path_types.hpp new file mode 100644 index 0000000..d5f7846 --- /dev/null +++ b/include/rive/math/path_types.hpp
@@ -0,0 +1,35 @@ +/* + * Copyright 2022 Rive + */ + +#ifndef _RIVE_PATH_TYPES_HPP_ +#define _RIVE_PATH_TYPES_HPP_ + +#include "rive/rive_types.hpp" + +namespace rive { + +enum class FillRule { + nonZero, + evenOdd, +}; + +enum class PathDirection { + cw, + ccw, + // aliases + clockwise = cw, + counterclockwise = ccw, +}; + +enum class PathVerb : uint8_t { + move, + line, + quad, + conic_unused, // so we match skia's order + cubic, + close, +}; + +} +#endif
diff --git a/include/rive/math/raw_path.hpp b/include/rive/math/raw_path.hpp index 2ac9709..26b8ddb 100644 --- a/include/rive/math/raw_path.hpp +++ b/include/rive/math/raw_path.hpp
@@ -8,6 +8,7 @@ #include "rive/span.hpp" #include "rive/math/aabb.hpp" #include "rive/math/mat2d.hpp" +#include "rive/math/path_types.hpp" #include "rive/math/vec2d.hpp" #include <cmath> @@ -17,23 +18,6 @@ namespace rive { -enum class PathDirection { - cw, - ccw, - // aliases - clockwise = cw, - counterclockwise = ccw, -}; - -enum class PathVerb : uint8_t { - move, - line, - quad, - conic_unused, // so we match skia's order - cubic, - close, -}; - class RawPath { public: std::vector<Vec2D> m_Points;
diff --git a/src/hittest_command_path.cpp b/src/hittest_command_path.cpp new file mode 100644 index 0000000..0b51de7 --- /dev/null +++ b/src/hittest_command_path.cpp
@@ -0,0 +1,52 @@ +/* + * Copyright 2022 Rive + */ + +#include "rive/hittest_command_path.hpp" + +using namespace rive; + +HitTestCommandPath::HitTestCommandPath(const IAABB& area) : m_Area(area) { + m_Tester.reset(m_Area); +} + +bool HitTestCommandPath::wasHit() { + return m_Tester.test(); +} + +void HitTestCommandPath::reset() { + m_Tester.reset(m_Area); +} + +void HitTestCommandPath::fillRule(FillRule value) { + m_FillRule = value; +} + +void HitTestCommandPath::addPath(CommandPath* path, const Mat2D& transform) { + assert(false); + // not supported +} + +RenderPath* HitTestCommandPath::renderPath() { + assert(false); + // not supported + return nullptr; +} + +void HitTestCommandPath::moveTo(float x, float y) { + m_Tester.move(m_Xform * Vec2D(x, y)); +} + +void HitTestCommandPath::lineTo(float x, float y) { + m_Tester.line(m_Xform * Vec2D(x, y)); +} + +void HitTestCommandPath::cubicTo(float ox, float oy, float ix, float iy, float x, float y) { + m_Tester.cubic(m_Xform * Vec2D(ox, oy), + m_Xform * Vec2D(ix, iy), + m_Xform * Vec2D( x, y)); +} + +void HitTestCommandPath::close() { + m_Tester.close(); +}
diff --git a/src/math/hit_test.cpp b/src/math/hit_test.cpp new file mode 100644 index 0000000..2463f1a --- /dev/null +++ b/src/math/hit_test.cpp
@@ -0,0 +1,339 @@ +/* + * Copyright 2022 Rive + */ + +#include "rive/math/hit_test.hpp" + +#include <algorithm> +#include <assert.h> +#include <cmath> + +using namespace rive; + +static inline float graphics_roundf(float x) { + return std::floor(x + 0.5f); +} + +static inline int graphics_round(float x) { + return (int)graphics_roundf(x); +} + +struct Point { + float x, y; + + Point() {} + Point(float xx, float yy) : x(xx), y(yy) {} + Point(const Vec2D& src) : x(src.x()), y(src.y()) {} + + Point operator+(Point v) const { + return { x + v.x, y + v.y }; + } + Point operator-(Point v) const { + return { x - v.x, y - v.y }; + } + + Point& operator+=(Point v) { + *this = *this + v; + return *this; + } + Point& operator-=(Point v) { + *this = *this - v; + return *this; + } + + friend Point operator*(Point v, float s) { + return { v.x * s, v.y * s }; + } + friend Point operator*(float s, Point v) { + return { v.x * s, v.y * s }; + } +}; + +template <typename T> T lerp(T a, T b, float t) { + return a + (b - a) * t; +} + +template <typename T> T ave(T a, T b) { + return lerp(a, b, 0.5f); +} + +static void append_line(const float height, Point p0, Point p1, float m, + int winding, int delta[], int iwidth) { + assert(winding == 1 || winding == -1); + + int top = graphics_round(p0.y); + int bottom = graphics_round(p1.y); + if (top == bottom) { + return; + } + + assert(top < bottom); + assert(top >= 0); + assert((float)bottom <= height); + + // we add 0.5 at the end to pre-round the values + float x = p0.x + m * (top - p0.y + 0.5f) + 0.5f; + + int* row = delta + top * iwidth; + for (int y = top; y < bottom; ++y) { + int ix = (int)std::max(x, 0.0f); + if (ix < iwidth) { + row[ix] += winding; + } + x += m; + row += iwidth; + } +} + +static void clip_line(const float height, Point p0, Point p1, int delta[], const int iwidth) { + if (p0.y == p1.y) { + return; + } + + int winding = 1; + if (p0.y > p1.y) { + winding = -1; + std::swap(p0, p1); + } + // now we're monotonic in Y: p0 <= p1 + if (p1.y <= 0 || p0.y >= height) { + return; + } + + const float m = (float)(p1.x - p0.x) / (p1.y - p0.y); + if (p0.y < 0) { + p0.x += m * (0 - p0.y); + p0.y = 0; + } + if (p1.y > height) { + p1.x += m * (height - p1.y); + p1.y = height; + } + + assert(p0.y <= p1.y); + assert(p0.y >= 0); + assert(p1.y <= height); + + append_line(height, p0, p1, m, winding, delta, iwidth); +} + +#define MAX_CURVE_SEGMENTS (1 << 8) + +static int compute_cubic_segments(Point a, Point b, Point c, Point d) { + Point abc = a - b - b + c; + Point bcd = b - c - c + d; + float dx = std::max(std::abs(abc.x), std::abs(bcd.x)); + float dy = std::max(std::abs(abc.y), std::abs(bcd.y)); + float dist = sqrtf(dx*dx + dy*dy); + // count = sqrt(6*dist / 8*tol) + // tol = 0.25 + // count = sqrt(3*dist) + float count = sqrtf(3*dist); + return std::max(1, std::min((int)ceilf(count), MAX_CURVE_SEGMENTS)); +} + +// cubic a(1-t)^3 + 3bt(1-t)^2 + 3c(1-t)t^2 + dt^3 +// becomes +// At^3 + Bt^2 + Ct + D +// +struct CubicCoeff { + Point A, B, C, D; + + // a(1-t)^3 + 3bt(1-t)^2 + 3ct^2(1-t) + dt^3 + // a - 3at + 3at^2 - at^3 a(1 - 3t + 3t^2 - t^3) + // 3bt - 6bt^2 + 3bt^3 3b( t - 2t^2 + t^3) + // 3ct^2 - 3ct^3 3c( t^2 - t^3) + // dt^3 d( t^3) + // ... + // D + Ct + Bt^2 + At^3 + // + CubicCoeff(Point a, Point b, Point c, Point d) { + A = (d - a) + 3.0f*(b - c); + B = 3.0f*((c - b) + (a - b)); + C = 3.0f*(b - a); + D = a; + } + + Point eval(float t) const { + return ((A*t + B)*t + C)*t + D; + } +}; + +//////////////////////////////////////////// + +void HitTester::reset() { + m_DW.clear(); +} + +void HitTester::reset(const IAABB& clip, FillRule rule) { + m_offset = Vec2D{ (float)clip.left, (float)clip.top }; + m_height = (float)clip.height(); + + m_WindingMask = (rule == rive::FillRule::nonZero) ? -1 : 1; + + m_IWidth = clip.width(); + m_IHeight = clip.height(); + m_DW.resize(m_IWidth * m_IHeight); + for (size_t i = 0; i < m_DW.size(); ++i) { + m_DW[i] = 0; + } + + m_ExpectsMove = true; +} + +void HitTester::move(Vec2D v) { + if (!m_ExpectsMove) { + this->close(); + } + m_First = m_Prev = v - m_offset; + m_ExpectsMove = false; +} + +void HitTester::line(Vec2D v) { + assert(!m_ExpectsMove); + + v = v - m_offset; + clip_line(m_height, m_Prev, v, m_DW.data(), m_IWidth); + m_Prev = v; +} + +void HitTester::quad(Vec2D b, Vec2D c) { + assert(!m_ExpectsMove); + + + m_Prev = c; +} + +static bool quickRejectCubic(float height, Point a, Point b, Point c, Point d) { + const float h = height; + return (a.y <= 0 && b.y <= 0 && c.y <= 0 && d.y <= 0) || + (a.y >= h && b.y >= h && c.y >= h && d.y >= h); +} + +struct CubicChop { + Vec2D storage[7]; + + CubicChop(Vec2D a, Vec2D b, Vec2D c, Vec2D d) { + auto ab = ave(a, b); + auto bc = ave(b, c); + auto cd = ave(c, d); + auto abc = ave(ab, bc); + auto bcd = ave(bc, cd); + + storage[0] = a; + storage[1] = ab; + storage[2] = abc; + storage[3] = ave(abc, bcd); + storage[4] = bcd; + storage[5] = cd; + storage[6] = d; + } + + Vec2D operator[](unsigned index) const { + assert(index < 7); + return storage[index]; + } +}; + +// Trial and error to pick a good value for this. +// +// Subdivision and recursion have their own cost, so at some point +// just evaluating the cubic (count) times is cheaper than continuing +// to chop. +// +// The key win is quickRejectCubic. This is how we save time over just +// evaluating the cubic up front. +// +#define MAX_LOCAL_SEGMENTS 16 + +void HitTester::recurse_cubic(Vec2D b, Vec2D c, Vec2D d, int count) { + if (quickRejectCubic(m_height, m_Prev, b, c, d)) { + m_Prev = d; + return; + } + + if (count > MAX_LOCAL_SEGMENTS) { + CubicChop chop(m_Prev, b, c, d); + const int newCount = (count + 1) >> 1; + assert(newCount < count); + this->recurse_cubic(chop[1], chop[2], chop[3], newCount); + this->recurse_cubic(chop[4], chop[5], chop[6], newCount); + } else { + const float dt = 1.0f / (float)count; + float t = dt; + + CubicCoeff cube(m_Prev, b, c, d); + // we don't need the first point eval(0) or the last eval(1) + Point prev = m_Prev; + for (int i = 1; i < count - 1; ++i) { + auto next = cube.eval(t); + clip_line(m_height, prev, next, m_DW.data(), m_IWidth); + prev = next; + t += dt; + } + clip_line(m_height, prev, d, m_DW.data(), m_IWidth); + m_Prev = d; + } +} +void HitTester::cubic(Vec2D b, Vec2D c, Vec2D d) { + assert(!m_ExpectsMove); + + b = b - m_offset; + c = c - m_offset; + d = d - m_offset; + + if (quickRejectCubic(m_height, m_Prev, b, c, d)) { + m_Prev = d; + return; + } + + const int count = compute_cubic_segments(m_Prev, b, c, d); + + this->recurse_cubic(b, c, d, count); +} + +void HitTester::close() { + assert(!m_ExpectsMove); + + clip_line(m_height, m_Prev, m_First, m_DW.data(), m_IWidth); + m_ExpectsMove = true; +} + +void HitTester::addRect(const AABB& rect, const Mat2D& xform, PathDirection dir) { + const Vec2D pts[] = { + xform * Vec2D{rect.left(), rect.top()}, + xform * Vec2D{rect.right(), rect.top()}, + xform * Vec2D{rect.right(), rect.bottom()}, + xform * Vec2D{rect.left(), rect.bottom()}, + }; + + move(pts[0]); + if (dir == PathDirection::clockwise) { + line(pts[1]); + line(pts[2]); + line(pts[3]); + } else { + line(pts[3]); + line(pts[2]); + line(pts[1]); + } + close(); +} + +bool HitTester::test() { + if (!m_ExpectsMove) { + this->close(); + } + + const int* row = m_DW.data(); + int winding = 0; + for (int y = 0; y < m_IHeight; ++y) { + int w = 0; + for (int x = 0; x < m_IWidth; ++x) { + w += *row++; + winding |= w & m_WindingMask; + } + } + this->reset(); + return winding != 0; +}