/* * Copyright (c) 2021 - 2026 ThorVG project. All rights reserved. * Permission is hereby granted, free of charge, to any person obtaining a copy * of this software and associated documentation files (the "Software"), to deal * in the Software without restriction, including without limitation the rights * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell * copies of the Software, and to permit persons to whom the Software is * furnished to do so, subject to the following conditions: * The above copyright notice and this permission notice shall be included in all * copies or substantial portions of the Software. * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE * SOFTWARE. */ #ifndef _TVG_MATH_H_ #define _TVG_MATH_H_ #define _USE_MATH_DEFINES #include #include #include "tvgCommon.h" namespace tvg { #define MATH_PI 3.14159265358979323846f #define MATH_PI2 1.57079632679489661923f #define FLOAT_EPSILON 1.0e-06f //1.192092896e-07f #define PATH_KAPPA 0.552284f /************************************************************************/ /* General functions */ /************************************************************************/ float atan2(float y, float x); float length(const PathCommand* cmds, uint32_t cmdsCnt, const Point* pts, uint32_t ptsCnt); static inline float deg2rad(float degree) { return degree * (MATH_PI / 180.0f); } static inline float rad2deg(float radian) { return radian * (180.0f / MATH_PI); } static inline bool zero(float a) { return (fabsf(a) <= FLOAT_EPSILON) ? true : false; } static inline bool equal(float a, float b) { return tvg::zero(a - b); } template static inline constexpr const T& clamp(const T& v, const T& min, const T& max) { if (v < min) return min; else if (v > max) return max; return v; } /************************************************************************/ /* Matrix functions */ /************************************************************************/ void rotate(Matrix* m, float degree); bool inverse(const Matrix* m, Matrix* out); bool identity(const Matrix* m); Matrix operator*(const Matrix& lhs, const Matrix& rhs); bool operator==(const Matrix& lhs, const Matrix& rhs); static inline float radian(const Matrix& m) { return fabsf(tvg::atan2(m.e21, m.e11)); } static inline bool rightAngle(const Matrix& m) { auto radian = tvg::radian(m); if (tvg::zero(radian) || tvg::zero(radian - MATH_PI2) || tvg::zero(radian - MATH_PI)) return true; return false; } static inline bool skewed(const Matrix& m) { return !tvg::zero(m.e21 + m.e12); } static inline void identity(Matrix* m) { m->e11 = 1.0f; m->e12 = 0.0f; m->e13 = 0.0f; m->e21 = 0.0f; m->e22 = 1.0f; m->e23 = 0.0f; m->e31 = 0.0f; m->e32 = 0.0f; m->e33 = 1.0f; } static inline constexpr const Matrix identity() { return {1.0f, 0.0f, 0.0f, 0.0f, 1.0f, 0.0f, 0.0f, 0.0f, 1.0f}; } static inline float scaling(const Matrix& m) { return sqrtf(m.e11 * m.e11 + m.e21 * m.e21); } static inline void scale(Matrix* m, const Point& p) { m->e11 *= p.x; m->e22 *= p.y; } static inline void scaleR(Matrix* m, const Point& p) { if (p.x != 1.0f) { m->e11 *= p.x; m->e21 *= p.x; } if (p.y != 1.0f) { m->e22 *= p.y; m->e12 *= p.y; } } static inline void translate(Matrix* m, const Point& p) { m->e13 += p.x; m->e23 += p.y; } static inline void translateR(Matrix* m, const Point& p) { if (p.x == 0.0f && p.y == 0.0f) return; m->e13 += (p.x * m->e11 + p.y * m->e12); m->e23 += (p.x * m->e21 + p.y * m->e22); } static inline bool operator!=(const Matrix& lhs, const Matrix& rhs) { return !(lhs == rhs); } static inline void operator*=(Matrix& lhs, const Matrix& rhs) { lhs = lhs * rhs; } static inline Matrix operator*(const Matrix* lhs, const Matrix& rhs) { if (lhs) return *lhs * rhs; return rhs; } static inline void log(const Matrix& m) { TVGLOG("COMMON", "Matrix: [%f %f %f] [%f %f %f] [%f %f %f]", m.e11, m.e12, m.e13, m.e21, m.e22, m.e23, m.e31, m.e32, m.e33); } /************************************************************************/ /* Point functions */ /************************************************************************/ void operator*=(Point& pt, const Matrix& m); Point operator*(const Point& pt, const Matrix& m); Point normal(const Point& p1, const Point& p2); void normalize(Point& pt); static inline constexpr const Point operator*=(Point& pt, const Matrix* m) { if (m) pt *= *m; return pt; } static inline Point operator*(const Point& pt, const Matrix* m) { if (m) return pt * *m; return pt; } static inline Point min(const Point& lhs, const Point& rhs) { return {std::min(lhs.x, rhs.x), std::min(lhs.y, rhs.y)}; } static inline Point max(const Point& lhs, const Point& rhs) { return {std::max(lhs.x, rhs.x), std::max(lhs.y, rhs.y)}; } static inline float dot(const Point& lhs, const Point& rhs) { return lhs.x * rhs.x + lhs.y * rhs.y; } static inline float cross(const Point& lhs, const Point& rhs) { return lhs.x * rhs.y - rhs.x * lhs.y; } static inline bool zero(const Point& p) { return tvg::zero(p.x) && tvg::zero(p.y); } static inline float length(const Point& a, const Point& b) { auto x = b.x - a.x; auto y = b.y - a.y; if (x < 0) x = -x; if (y < 0) y = -y; return (x > y) ? (x + 0.375f * y) : (y + 0.375f * x); } static inline float length(const Point& a) { return sqrtf(a.x * a.x + a.y * a.y); } static inline float length2(const Point& a) { return a.x * a.x + a.y * a.y; }; static inline bool operator==(const Point& lhs, const Point& rhs) { return tvg::equal(lhs.x, rhs.x) && tvg::equal(lhs.y, rhs.y); } static inline bool operator!=(const Point& lhs, const Point& rhs) { return !(lhs == rhs); } static inline Point operator-(const Point& lhs, const Point& rhs) { return {lhs.x - rhs.x, lhs.y - rhs.y}; } static inline Point operator-(const Point& lhs, const float rhs) { return {lhs.x - rhs, lhs.y - rhs}; } static inline Point operator+(const Point& lhs, const Point& rhs) { return {lhs.x + rhs.x, lhs.y + rhs.y}; } static inline Point operator+(const Point& lhs, const float rhs) { return {lhs.x + rhs, lhs.y + rhs}; } static inline void operator+=(Point& lhs, const Point& rhs) { lhs.x += rhs.x; lhs.y += rhs.y; } static inline Point operator*(const Point& lhs, const Point& rhs) { return {lhs.x * rhs.x, lhs.y * rhs.y}; } static inline void operator*=(Point& lhs, const Point& rhs) { lhs.x *= rhs.x; lhs.y *= rhs.y; } static inline Point operator*(const Point& lhs, const float rhs) { return {lhs.x * rhs, lhs.y * rhs}; } static inline void operator*=(Point& lhs, const float rhs) { lhs.x *= rhs; lhs.y *= rhs; } static inline Point operator*(const float& lhs, const Point& rhs) { return {lhs * rhs.x, lhs * rhs.y}; } static inline Point operator/(const Point& lhs, const Point& rhs) { return {lhs.x / rhs.x, lhs.y / rhs.y}; } static inline Point operator/(const Point& lhs, const float rhs) { return {lhs.x / rhs, lhs.y / rhs}; } static inline Point operator-(const Point& a) { return {-a.x, -a.y}; } enum class Orientation { Linear = 0, Clockwise, CounterClockwise, }; static inline Orientation orientation(const Point& p1, const Point& p2, const Point& p3) { auto val = cross(p2 - p1, p3 - p1); if (zero(val)) return Orientation::Linear; else return val > 0 ? Orientation::Clockwise : Orientation::CounterClockwise; } static inline void log(const Point& pt) { TVGLOG("COMMON", "Point: [%f %f]", pt.x, pt.y); } static inline bool closed(const Point& lhs, const Point& rhs, float tolerance) { float dx = lhs.x - rhs.x; float dy = lhs.y - rhs.y; return (dx * dx + dy * dy) < (tolerance * tolerance); } /************************************************************************/ /* Line functions */ /************************************************************************/ struct Line { Point pt1; Point pt2; void split(float at, Line& left, Line& right) const; float length() const; }; /************************************************************************/ /* Geometry functions */ /************************************************************************/ struct BBox { Point min, max; void init() { min = {FLT_MAX, FLT_MAX}; max = {-FLT_MAX, -FLT_MAX}; } }; static inline uint32_t arcSegmentsCnt(float arcAngle, float pixelRadius) { if (pixelRadius < FLOAT_EPSILON) return 2; static constexpr auto PX_TOLERANCE = 0.25f; // Sagitta-based formula Approximation: 1 - cos(θ/2) ≈ (θ/2)²/2, so θ ≈ 2 * sqrt(2 * s/r) auto segmentAngle = 2.0f * sqrtf(2.0f * PX_TOLERANCE / pixelRadius); return static_cast(ceilf(fabsf(arcAngle) / segmentAngle)) + 1; } /************************************************************************/ /* Bezier functions */ /************************************************************************/ struct Bezier { Point start; Point ctrl1; Point ctrl2; Point end; Bezier() {} Bezier(const Point& p0, const Point& p1, const Point& p2, const Point& p3): start(p0), ctrl1(p1), ctrl2(p2), end(p3) {} // Constructor that approximates a quarter-circle segment of arc between 'start' and 'end' points // using a cubic Bezier curve with a given 'radius'. Bezier(const Point& start, const Point& end, float radius); void split(float t, Bezier& left); void split(Bezier& left, Bezier& right) const; void split(float at, Bezier& left, Bezier& right) const; float length() const; float lengthApprox() const; float at(float at, float length) const; float atApprox(float at, float length) const; Point at(float t) const; float angle(float t) const; bool flatten() const; uint32_t segments() const; Bezier operator*(const Matrix& m); static void bounds(BBox& box, const Point& start, const Point& ctrl1, const Point& ctrl2, const Point& end); }; static inline bool edgesCross(const Point& p0, const Point& p1, const Point& p2, const Point& p3) { auto orientSign = [](const Point& a, const Point& b, const Point& c) { auto value = cross(b - a, c - a); if (zero(value)) return int8_t{0}; return (value > 0.0f) ? int8_t{1} : int8_t{-1}; }; auto straddlesLine = [&](const Point& a, const Point& b, const Point& c, const Point& d) { return orientSign(a, b, c) * orientSign(a, b, d) < 0; }; return straddlesLine(p0, p1, p2, p3) && straddlesLine(p2, p3, p0, p1); } // Conservative triangle-fan safety check // The fill is emitted as (v0,v1,v2), (v0,v2,v3), (v0,v3,v4), ... // Usage: // 1. Setup: default-construct `ConvexProbe probe` for one tessellation pass. // 2. Feed one contour at a time: call `nextContour()` on MoveTo, then stream // each contour edge with `addEdge(curr - prev)`, and finish with // `addContourClose(first - prev)` on Close. For cubic segments, callers may // pre-reject looping control polygons with `edgesCross(start, ctrl1, ctrl2, end)`. // 3. Read `probe.convex` as the result. `true` means the contour stayed within // the cheap triangle-fan fast-path assumptions; `false` means fall back. // Cost: O(1) work per edge and O(1) memory. struct ConvexProbe { bool convex = true; int8_t winding = 0; Point firstEdge = {}; Point prevEdge = {}; int8_t prevXDir = 0; int8_t prevYDir = 0; uint8_t xDirChanges = 0; uint8_t yDirChanges = 0; uint8_t reversals = 0; bool contourHasEdges = false; void nextContour() { if (contourHasEdges) convex = false; resetContour(); } void addEdge(const Point& edge) { if (zero(edge)) return; contourHasEdges = true; if (!convex) return; if (zero(firstEdge)) firstEdge = edge; updateDir(edge.x, prevXDir, xDirChanges); updateDir(edge.y, prevYDir, yDirChanges); if (!convex) return; if (zero(prevEdge)) { prevEdge = edge; return; } auto turn = cross(prevEdge, edge); if (zero(turn)) { if (dot(prevEdge, edge) < 0.0f && ++reversals > MaxCollinearReversals) convex = false; } else { auto sign = (turn > 0.0f) ? int8_t{1} : int8_t{-1}; if (winding == 0) winding = sign; else if (sign != winding) convex = false; } prevEdge = edge; } void addContourClose(const Point& edge) { addEdge(edge); if (convex && !zero(firstEdge)) addEdge(firstEdge); } private: enum : uint8_t { MaxAxisDirChanges = 3, MaxCollinearReversals = 2 }; void resetContour() { firstEdge = {}; prevEdge = {}; prevXDir = prevYDir = 0; xDirChanges = yDirChanges = 0; reversals = 0; contourHasEdges = false; } void updateDir(float value, int8_t& prevDir, uint8_t& changes) { int8_t dir = 0; if (!zero(value)) dir = (value > 0.0f) ? int8_t{1} : int8_t{-1}; if (dir == 0 || !convex) return; if (prevDir != 0 && prevDir != dir && ++changes > MaxAxisDirChanges) { convex = false; return; } prevDir = dir; } }; /************************************************************************/ /* Interpolation functions */ /************************************************************************/ template static inline T lerp(const T &start, const T &end, float t) { return static_cast(start + (end - start) * t); } uint8_t lerp(const uint8_t &start, const uint8_t &end, float t); } #endif //_TVG_MATH_H_