Make RectanglesToContour more memory efficient (particularly for re-runs). # Description In the text input branch I realized I needed to re-use RectanglesToContour and that it would be called often when moving selection ranged cursors. The existing implementation closely matches our Dart one which is not very memory efficient, mostly due to it just being Dart. # Details - Try to store re-used containers on the RectanglesToContour class so allocation can happen less frequently when re-using the RectanglesToContour. - Try to avoid any forced heap allocation (although some is still bound to happen). - We had a lot of Vectors of Vectors. In almost all cases these got simplified to linear vectors or vectors of structs/classes. Because each vector does its own heap allocation, vector<vector<vector<...>>> can cause a lot of memory re-alloc when adding/removing elements. - The boolean inclusion vector got converted to a bitset which is also stored on the class so it can be re-used. - Nuke Rect as we have the same functionality in AABB. - Massaged the API a bit to have names match the updated API a little more closely. I'll add more comments inline below... Diffs= 5c4e83502f Make RectanglesToContour more memory efficient (particularly for re-runs). (#9438) Co-authored-by: Luigi Rosso <luigi-rosso@users.noreply.github.com>
diff --git a/.rive_head b/.rive_head index 4ada50d..3bbc7d7 100644 --- a/.rive_head +++ b/.rive_head
@@ -1 +1 @@ -922b445f217f1980f1d19255473c1c8ee469a642 +5c4e83502fbc0b462760991409f403a7910a7eba
diff --git a/include/rive/math/aabb.hpp b/include/rive/math/aabb.hpp index e437e07..8d661a9 100644 --- a/include/rive/math/aabb.hpp +++ b/include/rive/math/aabb.hpp
@@ -91,6 +91,8 @@ inline float right() const { return maxX; } inline float bottom() const { return maxY; } + Vec2D min() const { return Vec2D(minX, minY); } + Vec2D max() const { return Vec2D(maxX, maxY); } float width() const { return maxX - minX; } float height() const { return maxY - minY; } Vec2D size() const { return {width(), height()}; } @@ -157,6 +159,19 @@ } bool contains(Vec2D position) const; + + Vec2D operator[](size_t index) const + { + switch (index) + { + case 0: + return Vec2D(minX, minY); + case 1: + return Vec2D(maxX, maxY); + default: + RIVE_UNREACHABLE(); + } + } }; } // namespace rive
diff --git a/include/rive/math/rect.hpp b/include/rive/math/rect.hpp deleted file mode 100644 index b1aebdb..0000000 --- a/include/rive/math/rect.hpp +++ /dev/null
@@ -1,23 +0,0 @@ -#ifndef _RIVE_RECT_HPP_ -#define _RIVE_RECT_HPP_ - -namespace rive -{ -struct Rect -{ - float left, top, right, bottom; - - Rect(float l, float t, float r, float b) : - left(l), top(t), right(r), bottom(b) - {} - - float width() const { return right - left; } - float height() const { return bottom - top; } - - static Rect fromLTRB(float l, float t, float r, float b) - { - return Rect(l, t, r, b); - } -}; -} // namespace rive -#endif
diff --git a/include/rive/math/rectangles_to_contour.hpp b/include/rive/math/rectangles_to_contour.hpp index 27d8731..6a1581e 100644 --- a/include/rive/math/rectangles_to_contour.hpp +++ b/include/rive/math/rectangles_to_contour.hpp
@@ -2,36 +2,171 @@ #define _RIVE_RECTANGLES_TO_CONTOUR_HPP_ #include <vector> #include <unordered_set> +#include <unordered_map> #include "rive/math/mat2d.hpp" -#include "rive/math/rect.hpp" +#include "rive/math/aabb.hpp" namespace rive { -struct PolygonPoint +struct ContourPoint { Vec2D vec; int dir; // 0 for horizontal, 1 for vertical - PolygonPoint(const Vec2D& vec, int dir) : vec(vec), dir(dir) {} + ContourPoint(const Vec2D& vec, int dir) : vec(vec), dir(dir) {} - bool operator==(const PolygonPoint& other) const + bool operator==(const ContourPoint& other) const { return vec == other.vec && dir == other.dir; } }; -struct RectanglesToContour -{ -private: - std::unordered_set<Vec2D> uniquePoints; - std::vector<Rect> rects; - void addUniquePoint(const Vec2D& point); - void addRect(const Rect& rect); - std::vector<std::vector<Vec2D>> computeContours(); +class RectanglesToContour; +class Contour; +// A helper for iterating the points in a contour, lazily skipping points which +// have the same value. +class ContourPointItr +{ public: - static std::vector<std::vector<Vec2D>> makeSelectionContours( - const std::vector<Rect>& rects); + 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()); + } + +#ifdef TESTING + size_t size() const { return m_points.size(); } + Vec2D point(size_t index) const { return m_points[index].vec; } +#endif + +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; + std::unordered_map<Vec2D, Vec2D> m_edgesH; + std::unordered_map<Vec2D, Vec2D> 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
diff --git a/include/rive/math/vec2d.hpp b/include/rive/math/vec2d.hpp index 672a73a..597d912 100644 --- a/include/rive/math/vec2d.hpp +++ b/include/rive/math/vec2d.hpp
@@ -84,6 +84,19 @@ y -= v.y; return *this; } + + float operator[](size_t index) const + { + switch (index) + { + case 0: + return x; + case 1: + return y; + default: + RIVE_UNREACHABLE(); + } + } }; static_assert(std::is_pod<Vec2D>::value, "Vec2D must be plain-old-data");
diff --git a/include/rive/span.hpp b/include/rive/span.hpp index 1349503..b130277 100644 --- a/include/rive/span.hpp +++ b/include/rive/span.hpp
@@ -79,6 +79,15 @@ typedef T const* const_iterator; typedef std::ptrdiff_t difference_type; typedef size_t size_type; + + bool operator!=(const Span<T>& that) const + { + return m_Ptr != that.m_Ptr || m_Size != that.m_Size; + } + bool operator==(const Span<T>& that) const + { + return m_Ptr == that.m_Ptr && m_Size == that.m_Size; + } }; template <typename T> Span<T> make_span(T* ptr, size_t size)
diff --git a/include/rive/text/text.hpp b/include/rive/text/text.hpp index 5c92380..f05825d 100644 --- a/include/rive/text/text.hpp +++ b/include/rive/text/text.hpp
@@ -2,7 +2,6 @@ #define _RIVE_TEXT_CORE_HPP_ #include "rive/generated/text/text_base.hpp" #include "rive/math/aabb.hpp" -#include "rive/math/rect.hpp" #include "rive/text/text_value_run.hpp" #include "rive/text_engine.hpp" #include "rive/shapes/shape_paint_path.hpp" @@ -313,10 +312,8 @@ StyledText m_styledText; StyledText m_modifierStyledText; - GlyphLookup m_glyphLookup; - std::unordered_map<uint16_t, std::vector<Rect>> m_textValueRunToRects; void clearRenderStyles(); TextBoundsInfo computeBoundsInfo(); LineIter shouldDrawLine(float y, float totalHeight, const GlyphLine& line);
diff --git a/include/rive/text/text_value_run.hpp b/include/rive/text/text_value_run.hpp index d23c111..0397f37 100644 --- a/include/rive/text/text_value_run.hpp +++ b/include/rive/text/text_value_run.hpp
@@ -3,6 +3,7 @@ #include "rive/generated/text/text_value_run_base.hpp" #include "rive/animation/hittable.hpp" #include "rive/text/utf.hpp" +#include "rive/math/rectangles_to_contour.hpp" namespace rive { @@ -10,6 +11,8 @@ class Text; class TextValueRun : public TextValueRunBase, public Hittable { + friend class HitTextRun; + public: StatusCode onAddedClean(CoreContext* context) override; StatusCode onAddedDirty(CoreContext* context) override; @@ -33,19 +36,32 @@ } uint32_t offset() const; - // Hit testing - AABB m_localBounds; - std::vector<std::vector<Vec2D>> m_contours; - bool m_isHitTarget = false; - void resetHitTest(); // clear m_contours and m_localBounds + // Reset stored data for hit testing the run. + void resetHitTest(); + + // Add a rectangle (usually bounding a glyph) as a hit rect that will be + // used to compute contours when computeHitContours is called. + void addHitRect(const AABB& rect); + + // Compute the contours used for hit testing, call resetHitTest to start + // adding hit rects (via addHitRect) again. + void computeHitContours(); + bool hitTestAABB(const Vec2D& position) override; bool hitTestHiFi(const Vec2D& position, float hitRadius) override; + bool isHitTarget() const { return m_isHitTarget; } + void isHitTarget(bool value); + protected: void textChanged() override; void styleIdChanged() override; private: + std::unique_ptr<RectanglesToContour> m_rectanglesToContour; + AABB m_localBounds; + bool m_isHitTarget = false; + std::vector<AABB> m_glyphHitRects; TextStyle* m_style = nullptr; uint32_t m_length = -1; bool canHitTest() const;
diff --git a/src/animation/state_machine_instance.cpp b/src/animation/state_machine_instance.cpp index 9bc6383..25d00d2 100644 --- a/src/animation/state_machine_instance.cpp +++ b/src/animation/state_machine_instance.cpp
@@ -928,7 +928,7 @@ m_textValueRun = component; if (m_textValueRun) { - m_textValueRun->m_isHitTarget = true; + m_textValueRun->isHitTarget(true); } } @@ -936,7 +936,7 @@ { if (m_textValueRun != nullptr) { - m_textValueRun->m_isHitTarget = false; + m_textValueRun->isHitTarget(false); m_textValueRun->resetHitTest(); } }
diff --git a/src/math/rectangles_to_contour.cpp b/src/math/rectangles_to_contour.cpp index 13bd8f2..51e3087 100644 --- a/src/math/rectangles_to_contour.cpp +++ b/src/math/rectangles_to_contour.cpp
@@ -3,80 +3,110 @@ #include <unordered_map> using namespace rive; +using RectEvent = RectanglesToContour::RectEvent; -struct RectEvent +class SpanOffset { - int index = 0; - float size = 0; - int type = 0; - float x = 0; - float y = 0; +public: + size_t start; + size_t size; - float getValue(int axis) const { return axis == 0 ? x : y; } + Span<RectEvent> toSpan(Span<RectEvent> base) + { + return Span<RectEvent>(base.data() + start, size); + } }; -std::vector<Rect> subdivideRectangles(const std::vector<Rect>& rects) +// Returns SpanOffset relative to result so it can be called in succession +// (re-allocating) prior to accessing data. +static SpanOffset sortRectEvents(const std::vector<AABB>& rects, + std::vector<RectEvent>& result, + uint8_t axisA, + uint8_t axisB) { - if (rects.empty()) + size_t index = 0; + + size_t resultStart = result.size(); + + for (const AABB& rect : rects) { - return rects; - } - - std::vector<std::vector<std::vector<float>>> vrects; - for (const auto& rect : rects) - { - vrects.push_back({{rect.left, rect.top}, {rect.right, rect.bottom}}); - } - - auto sortEvents = [&](int axisA, int axisB) -> std::vector<RectEvent> { - std::vector<RectEvent> result; - int index = 0; - - for (const auto& rect : vrects) + for (size_t pointIndex = 0; pointIndex < 2; pointIndex++) { - int mindex = 0; - for (const auto& e : rect) - { - RectEvent event; - event.type = mindex; - event.index = index; - event.y = axisB == 0 ? e[axisA] : e[axisB]; - event.x = axisB == 0 ? e[axisB] : e[axisA]; - event.size = mindex++ == 0 ? rect[1][axisB] - e[axisB] - : e[axisB] - rect[0][axisB]; - result.push_back(event); - } - ++index; + Vec2D e = rect[pointIndex]; + RectEvent event; + event.type = (uint8_t)pointIndex; + event.index = index; + event.y = axisB == 0 ? e[axisA] : e[axisB]; + event.x = axisB == 0 ? e[axisB] : e[axisA]; + event.size = pointIndex == 0 ? rect[1][axisB] - e[axisB] + : e[axisB] - rect[0][axisB]; + result.push_back(event); } + ++index; + } - std::sort(result.begin(), - result.end(), - [&](const RectEvent& a, const RectEvent& b) { - return a.getValue(axisB) < b.getValue(axisB); - }); + std::sort(result.begin() + resultStart, + result.end(), + [&](const RectEvent& a, const RectEvent& b) { + return a.getValue(axisB) < b.getValue(axisB); + }); - std::sort(result.begin(), - result.end(), - [&](const RectEvent& a, const RectEvent& b) { - return a.getValue(axisA) < b.getValue(axisA); - }); + std::sort(result.begin() + resultStart, + result.end(), + [&](const RectEvent& a, const RectEvent& b) { + return a.getValue(axisA) < b.getValue(axisA); + }); - return result; - }; + return {resultStart, result.size() - resultStart}; +} - auto ev = sortEvents(0, 1); - auto eh = sortEvents(1, 0); - std::vector<bool> included(vrects.size(), false); - included[ev[0].index] = true; +bool RectanglesToContour::isRectIncluded(size_t rectIndex) +{ + return (m_rectInclusionBitset[rectIndex / 8] & (1 << (rectIndex % 8))) != 0; +} + +void RectanglesToContour::markRectIncluded(size_t rectIndex, bool isIt) +{ + if (isIt) + { + m_rectInclusionBitset[rectIndex / 8] |= 1 << (rectIndex % 8); + } + else + { + m_rectInclusionBitset[rectIndex / 8] &= ~(1 << (rectIndex % 8)); + } +} + +void RectanglesToContour::subdivideRectangles() +{ + m_subdividedRects.clear(); + m_uniquePoints.clear(); + m_rectEvents.clear(); + + if (m_rects.empty()) + { + return; + } + + auto evOffset = sortRectEvents(m_rects, m_rectEvents, 0, 1); + auto ehOffset = sortRectEvents(m_rects, m_rectEvents, 1, 0); + + auto ev = evOffset.toSpan(m_rectEvents); + auto eh = ehOffset.toSpan(m_rectEvents); + + size_t inclusionByteSize = m_rects.size() / 8 + 1; + m_rectInclusionBitset.resize(inclusionByteSize); + memset(m_rectInclusionBitset.data(), 0, inclusionByteSize); + markRectIncluded(ev[0].index, true); int opened = 0; float beginY = 0; - std::vector<Rect> result; + std::vector<AABB> result; for (size_t i = 0; i < ev.size() - 1; ++i) { const auto& eventV = ev[i]; - included[eventV.index] = (eventV.type == 0); + markRectIncluded(ev[0].index, eventV.type == 0); const auto& next = ev[i + 1]; float beginX = eventV.x; float endX = next.x; @@ -89,7 +119,7 @@ for (size_t j = 0; j < eh.size(); ++j) { const auto& eventH = eh[j]; - if (included[eventH.index]) + if (isRectIncluded(eventH.index)) { if (eventH.type == 0) { @@ -103,7 +133,8 @@ { --opened; size_t n = 1; - while (j + n < eh.size() && !included[eh[j + n].index]) + while (j + n < eh.size() && + !isRectIncluded(eh[j + n].index)) { ++n; } @@ -112,32 +143,32 @@ if (!next || (opened == 0 && next->y != eventH.y)) { float endY = eventH.y; - result.push_back( - Rect::fromLTRB(beginX, beginY, endX, endY)); + m_subdividedRects.push_back( + AABB(beginX, beginY, endX, endY)); } } } } } - - return result; } -void RectanglesToContour::addRect(const Rect& rect) +void RectanglesToContour::reset() { m_rects.clear(); } + +void RectanglesToContour::addRect(const AABB& rect) { - if (!rects.empty()) + if (!m_rects.empty()) { - auto& last = rects.back(); - if (last.top == rect.top && last.bottom == rect.bottom && - last.right == rect.left) + auto& last = m_rects.back(); + if (last.minY == rect.minY && last.maxY == rect.maxY && + last.maxX == rect.minX) { - rects.pop_back(); - rects.emplace_back( - Rect::fromLTRB(last.left, last.top, rect.right, last.bottom)); + m_rects.pop_back(); + m_rects.emplace_back( + AABB(last.minX, last.minY, rect.maxX, last.maxY)); return; } } - rects.push_back(rect); + m_rects.push_back(rect); } template <typename Compare> @@ -149,29 +180,33 @@ return sortedPoints; } -std::vector<std::vector<Vec2D>> extractPolygons( - std::unordered_map<Vec2D, Vec2D>& edgesH, - std::unordered_map<Vec2D, Vec2D>& edgesV) +// Build contours and append them into contourPoints delineated by +// contourOffsets. +void extractPolygons(std::vector<ContourPoint>& contourPoints, + std::vector<size_t>& contourOffsets, + std::unordered_map<Vec2D, Vec2D>& edgesH, + std::unordered_map<Vec2D, Vec2D>& edgesV) { - std::vector<std::vector<Vec2D>> polygons; while (!edgesH.empty()) { + size_t contourStartOffset = contourPoints.size(); Vec2D start = edgesH.begin()->first; edgesH.erase(start); - std::vector<PolygonPoint> polygon = {PolygonPoint(start, 0)}; + auto first = ContourPoint(start, 0); + contourPoints.push_back(first); while (true) { - auto& curr = polygon.back(); + auto& curr = contourPoints.back(); if (curr.dir == 0) { if (edgesV.find(curr.vec) != edgesV.end()) { auto next = edgesV[curr.vec]; edgesV.erase(curr.vec); - polygon.emplace_back(next, 1); + contourPoints.emplace_back(next, 1); } else { @@ -184,7 +219,7 @@ { auto next = edgesH[curr.vec]; edgesH.erase(curr.vec); - polygon.emplace_back(next, 0); + contourPoints.emplace_back(next, 0); } else { @@ -192,59 +227,60 @@ } } - if (polygon.front() == polygon.back()) + // Remove the last point if the first and last in the contour are + // the same. + if (first == contourPoints.back()) { - polygon.pop_back(); + contourPoints.pop_back(); break; } } - std::vector<Vec2D> poly; - std::transform(polygon.begin(), - polygon.end(), - std::back_inserter(poly), - [](const PolygonPoint& pp) { return pp.vec; }); - - polygons.push_back(poly); - for (const Vec2D& vertex : poly) + contourOffsets.push_back(contourPoints.size()); + for (size_t index = contourStartOffset; index < contourPoints.size(); + index++) { + Vec2D vertex = contourPoints[index].vec; edgesH.erase(vertex); edgesV.erase(vertex); } } - - return polygons; } -std::vector<std::vector<Vec2D>> RectanglesToContour::computeContours() +void RectanglesToContour::computeContours() { - auto subdividedRects = subdivideRectangles(rects); - - for (const auto& rect : subdividedRects) + subdivideRectangles(); + for (const auto& rect : m_subdividedRects) { - addUniquePoint(Vec2D(rect.left, rect.top)); - addUniquePoint(Vec2D(rect.right, rect.top)); - addUniquePoint(Vec2D(rect.right, rect.bottom)); - addUniquePoint(Vec2D(rect.left, rect.bottom)); + addUniquePoint(Vec2D(rect.minX, rect.minY)); + addUniquePoint(Vec2D(rect.maxX, rect.minY)); + addUniquePoint(Vec2D(rect.maxX, rect.maxY)); + addUniquePoint(Vec2D(rect.minX, rect.maxY)); } - auto sortX = sortPoints(uniquePoints, [](const Vec2D& a, const Vec2D& b) { + auto sortX = sortPoints(m_uniquePoints, [](const Vec2D& a, const Vec2D& b) { return a.x < b.x || (a.x == b.x && a.y < b.y); }); - auto sortY = sortPoints(uniquePoints, [](const Vec2D& a, const Vec2D& b) { + auto sortY = sortPoints(m_uniquePoints, [](const Vec2D& a, const Vec2D& b) { return a.y < b.y || (a.y == b.y && a.x < b.x); }); - std::unordered_map<Vec2D, Vec2D> edgesH, edgesV; + // std::unordered_map isn't guaranteed to reserve memory, so this clear + // is more in prep for when we allow using allocators. We could also + // experiment with a simple linear search in a vector as usually there + // are not a lot of edges to traverse. + m_edgesH.clear(); + m_edgesV.clear(); + size_t i = 0; while (i < sortY.size()) { float currY = sortY[i].y; while (i < sortY.size() && sortY[i].y == currY) { - edgesH[sortY[i]] = sortY[i + 1]; - edgesH[sortY[i + 1]] = sortY[i]; + m_edgesH[sortY[i]] = sortY[i + 1]; + m_edgesH[sortY[i + 1]] = sortY[i]; i += 2; } } @@ -255,58 +291,59 @@ float currX = sortX[i].x; while (i < sortX.size() && sortX[i].x == currX) { - edgesV[sortX[i]] = sortX[i + 1]; - edgesV[sortX[i + 1]] = sortX[i]; + m_edgesV[sortX[i]] = sortX[i + 1]; + m_edgesV[sortX[i + 1]] = sortX[i]; i += 2; } } - return extractPolygons(edgesH, edgesV); + m_contourPoints.clear(); + m_contourOffsets.clear(); + extractPolygons(m_contourPoints, m_contourOffsets, m_edgesH, m_edgesV); } void RectanglesToContour::addUniquePoint(const Vec2D& point) { - if (!uniquePoints.insert(point).second) + if (!m_uniquePoints.insert(point).second) { - uniquePoints.erase(point); + m_uniquePoints.erase(point); } } -std::vector<std::vector<Vec2D>> RectanglesToContour::makeSelectionContours( - const std::vector<Rect>& rects) +ContourItr& ContourItr::operator++() { - RectanglesToContour converter; - - // Add rectangles to the converter - for (const auto& rect : rects) - { - converter.addRect(rect); - } - - std::vector<std::vector<Vec2D>> renderContours; - auto contours = converter.computeContours(); - - // Process the contours to create renderContours - for (const auto& contour : contours) - { - if (contour.empty()) - { - continue; - } - - std::vector<Vec2D> renderContour = {contour.front()}; - - for (auto it = std::next(contour.begin()); it != contour.end(); ++it) - { - if (renderContour.back() == *it) - { - continue; - } - renderContour.push_back(*it); - } - - renderContours.push_back(renderContour); - } - - return renderContours; + m_contourIndex++; + return *this; } +Contour ContourItr::operator*() const +{ + return m_rectanglesToContour->contour(m_contourIndex); +} + +Contour RectanglesToContour::contour(size_t index) const +{ + assert(index < m_contourOffsets.size()); + size_t end = m_contourOffsets[index]; + size_t start = index == 0 ? 0 : m_contourOffsets[index - 1]; + const ContourPoint* data = m_contourPoints.data() + start; + size_t size = end - start; + return Contour(Span<const ContourPoint>(data, size)); +} + +ContourPointItr& ContourPointItr::operator++() +{ + Vec2D currentPoint = m_pointIndex < m_contour.size() ? *(*this) : Vec2D(); + m_pointIndex++; + while (m_pointIndex < m_contour.size()) + { + auto nextPoint = m_contour[m_pointIndex].vec; + if (nextPoint != currentPoint) + { + break; + } + m_pointIndex++; + } + return *this; +} + +Vec2D ContourPointItr::operator*() const { return m_contour[m_pointIndex].vec; }
diff --git a/src/text/text.cpp b/src/text/text.cpp index 50cc159..c189826 100644 --- a/src/text/text.cpp +++ b/src/text/text.cpp
@@ -314,15 +314,9 @@ } m_renderStyles.clear(); - m_textValueRunToRects.clear(); - for (uint16_t i = 0; i < m_runs.size(); i++) + for (TextValueRun* textValueRun : m_runs) { - TextValueRun* textValueRun = m_runs[i]; textValueRun->resetHitTest(); - if (textValueRun->m_isHitTarget) - { - m_textValueRunToRects[i] = {}; - } } } @@ -656,18 +650,15 @@ } // Bounds of the glyph - auto rectsItr = m_textValueRunToRects.find(run->styleId); - if (rectsItr != m_textValueRunToRects.end()) + if (textValueRun->isHitTarget()) { Vec2D topLeft = Vec2D(curX, curY + line.top); Vec2D bottomRight = Vec2D(curX + advance, curY + line.bottom); - AABB::expandTo(textValueRun->m_localBounds, topLeft); - AABB::expandTo(textValueRun->m_localBounds, bottomRight); - rectsItr->second.emplace_back(topLeft.x, + textValueRun->addHitRect(AABB(topLeft.x, topLeft.y, bottomRight.x, - bottomRight.y); + bottomRight.y)); } curX += advance; } @@ -742,12 +733,12 @@ #endif // Step 8: cleanup - for (auto it = m_textValueRunToRects.begin(); - it != m_textValueRunToRects.end(); - ++it) + for (TextValueRun* textValueRun : m_runs) { - m_runs[it->first]->m_contours = - RectanglesToContour::makeSelectionContours(it->second); + if (textValueRun->isHitTarget()) + { + textValueRun->computeHitContours(); + } } }
diff --git a/src/text/text_value_run.cpp b/src/text/text_value_run.cpp index 0965264..1a6845c 100644 --- a/src/text/text_value_run.cpp +++ b/src/text/text_value_run.cpp
@@ -89,10 +89,34 @@ void TextValueRun::resetHitTest() { - m_contours.clear(); + m_glyphHitRects.clear(); m_localBounds = AABB::forExpansion(); } +void TextValueRun::addHitRect(const AABB& rect) +{ + AABB::expandTo(m_localBounds, rect.min()); + AABB::expandTo(m_localBounds, rect.max()); + m_glyphHitRects.push_back(rect); +} + +void TextValueRun::computeHitContours() +{ + if (!m_rectanglesToContour) + { + m_rectanglesToContour = rivestd::make_unique<RectanglesToContour>(); + } + else + { + m_rectanglesToContour->reset(); + } + for (const AABB& rect : m_glyphHitRects) + { + m_rectanglesToContour->addRect(rect); + } + m_rectanglesToContour->computeContours(); +} + bool TextValueRun::hitTestAABB(const Vec2D& position) { if (!canHitTest()) @@ -141,14 +165,27 @@ HitTestCommandPath tester(hitArea); tester.setXform(textComponent()->worldTransform() * textComponent()->m_transform); - for (const std::vector<Vec2D>& contour : m_contours) + + assert(m_rectanglesToContour != nullptr); + for (auto contour : *m_rectanglesToContour) { - tester.moveTo(contour[0].x, contour[0].y); - for (auto i = 1; i < contour.size(); i++) + assert(contour.begin() != contour.end()); + auto pointItr = contour.begin(); + auto end = contour.end(); + + Vec2D firstPoint = *pointItr; + tester.moveTo(firstPoint.x, firstPoint.y); + + while (++pointItr != end) { - tester.lineTo(contour[i].x, contour[i].y); + Vec2D point = *pointItr; + tester.lineTo(point.x, point.y); } + tester.close(); } + return tester.wasHit(); } + +void TextValueRun::isHitTarget(bool value) { m_isHitTarget = value; } \ No newline at end of file
diff --git a/tests/include/rive_testing.hpp b/tests/include/rive_testing.hpp index 80a7764..a981e8e 100644 --- a/tests/include/rive_testing.hpp +++ b/tests/include/rive_testing.hpp
@@ -7,6 +7,11 @@ bool aboutEqual(const rive::Mat2D& a, const rive::Mat2D& b); +// StringMaker doesn't work for Vec2D. +#define CHECK_VEC2D(a, b) \ + CHECK(a.x == b.x); \ + CHECK(a.y == b.y); + namespace Catch { template <> struct StringMaker<rive::Mat2D>
diff --git a/tests/unit_tests/runtime/rectangles_to_contour_test.cpp b/tests/unit_tests/runtime/rectangles_to_contour_test.cpp new file mode 100644 index 0000000..366053d --- /dev/null +++ b/tests/unit_tests/runtime/rectangles_to_contour_test.cpp
@@ -0,0 +1,19 @@ +#include "rive/math/vec2d.hpp" +#include "rive_testing.hpp" +#include "rive/math/rectangles_to_contour.hpp" + +using namespace rive; + +TEST_CASE("RectanglesToContour generates correct contour", "[text]") +{ + RectanglesToContour rectanglesToContour; + rectanglesToContour.addRect(AABB(10.0f, 10.0f, 20.0f, 20.0f)); + rectanglesToContour.addRect(AABB(20.0f, 10.0f, 30.0f, 20.0f)); + rectanglesToContour.computeContours(); + CHECK(rectanglesToContour.contourCount() == 1); + CHECK(rectanglesToContour.contour(0).size() == 4); + CHECK_VEC2D(rectanglesToContour.contour(0).point(0), Vec2D(30.0f, 20.0f)); + CHECK_VEC2D(rectanglesToContour.contour(0).point(1), Vec2D(30.0f, 10.0f)); + CHECK_VEC2D(rectanglesToContour.contour(0).point(2), Vec2D(10.0f, 10.0f)); + CHECK_VEC2D(rectanglesToContour.contour(0).point(3), Vec2D(10.0f, 20.0f)); +} \ No newline at end of file