summaryrefslogtreecommitdiff
path: root/core/math
diff options
context:
space:
mode:
Diffstat (limited to 'core/math')
-rw-r--r--core/math/math_2d.cpp5
-rw-r--r--core/math/math_2d.h1
-rw-r--r--core/math/math_funcs.cpp15
-rw-r--r--core/math/math_funcs.h14
-rw-r--r--core/math/triangulate.cpp42
-rw-r--r--core/math/triangulate.h5
6 files changed, 49 insertions, 33 deletions
diff --git a/core/math/math_2d.cpp b/core/math/math_2d.cpp
index d2e4101999..3767d298a1 100644
--- a/core/math/math_2d.cpp
+++ b/core/math/math_2d.cpp
@@ -98,11 +98,6 @@ real_t Vector2::cross(const Vector2 &p_other) const {
return x * p_other.y - y * p_other.x;
}
-Vector2 Vector2::cross(real_t p_other) const {
-
- return Vector2(p_other * y, -p_other * x);
-}
-
Vector2 Vector2::floor() const {
return Vector2(Math::floor(x), Math::floor(y));
diff --git a/core/math/math_2d.h b/core/math/math_2d.h
index 8928349a44..02d921b67e 100644
--- a/core/math/math_2d.h
+++ b/core/math/math_2d.h
@@ -104,7 +104,6 @@ struct Vector2 {
real_t dot(const Vector2 &p_other) const;
real_t cross(const Vector2 &p_other) const;
- Vector2 cross(real_t p_other) const;
Vector2 project(const Vector2 &p_vec) const;
Vector2 plane_project(real_t p_d, const Vector2 &p_vec) const;
diff --git a/core/math/math_funcs.cpp b/core/math/math_funcs.cpp
index f060a8e4ab..5c8512d8bd 100644
--- a/core/math/math_funcs.cpp
+++ b/core/math/math_funcs.cpp
@@ -177,18 +177,3 @@ float Math::random(float from, float to) {
float ret = (float)r / (float)RANDOM_MAX;
return (ret) * (to - from) + from;
}
-
-int Math::wrapi(int value, int min, int max) {
- --max;
- int rng = max - min + 1;
- value = ((value - min) % rng);
- if (value < 0)
- return max + 1 + value;
- else
- return min + value;
-}
-
-float Math::wrapf(float value, float min, float max) {
- float rng = max - min;
- return min + (value - min) - (rng * floor((value - min) / rng));
-}
diff --git a/core/math/math_funcs.h b/core/math/math_funcs.h
index e15abc6b50..26e87f009b 100644
--- a/core/math/math_funcs.h
+++ b/core/math/math_funcs.h
@@ -209,8 +209,18 @@ public:
static _ALWAYS_INLINE_ double round(double p_val) { return (p_val >= 0) ? Math::floor(p_val + 0.5) : -Math::floor(-p_val + 0.5); }
static _ALWAYS_INLINE_ float round(float p_val) { return (p_val >= 0) ? Math::floor(p_val + 0.5) : -Math::floor(-p_val + 0.5); }
- static int wrapi(int value, int min, int max);
- static float wrapf(float value, float min, float max);
+ static _ALWAYS_INLINE_ int wrapi(int value, int min, int max) {
+ int rng = max - min;
+ return min + ((((value - min) % rng) + rng) % rng);
+ }
+ static _ALWAYS_INLINE_ double wrapf(double value, double min, double max) {
+ double rng = max - min;
+ return min + (value - min) - (rng * Math::floor((value - min) / rng));
+ }
+ static _ALWAYS_INLINE_ float wrapf(float value, float min, float max) {
+ float rng = max - min;
+ return min + (value - min) - (rng * Math::floor((value - min) / rng));
+ }
// double only, as these functions are mainly used by the editor and not performance-critical,
static double ease(double p_x, double p_c);
diff --git a/core/math/triangulate.cpp b/core/math/triangulate.cpp
index 5bae74ac7e..563ba7268f 100644
--- a/core/math/triangulate.cpp
+++ b/core/math/triangulate.cpp
@@ -51,7 +51,8 @@ real_t Triangulate::get_area(const Vector<Vector2> &contour) {
bool Triangulate::is_inside_triangle(real_t Ax, real_t Ay,
real_t Bx, real_t By,
real_t Cx, real_t Cy,
- real_t Px, real_t Py)
+ real_t Px, real_t Py,
+ bool include_edges)
{
real_t ax, ay, bx, by, cx, cy, apx, apy, bpx, bpy, cpx, cpy;
@@ -74,10 +75,14 @@ bool Triangulate::is_inside_triangle(real_t Ax, real_t Ay,
cCROSSap = cx * apy - cy * apx;
bCROSScp = bx * cpy - by * cpx;
- return ((aCROSSbp > 0.0) && (bCROSScp > 0.0) && (cCROSSap > 0.0));
+ if (include_edges) {
+ return ((aCROSSbp > 0.0) && (bCROSScp > 0.0) && (cCROSSap > 0.0));
+ } else {
+ return ((aCROSSbp >= 0.0) && (bCROSScp >= 0.0) && (cCROSSap >= 0.0));
+ }
};
-bool Triangulate::snip(const Vector<Vector2> &p_contour, int u, int v, int w, int n, const Vector<int> &V) {
+bool Triangulate::snip(const Vector<Vector2> &p_contour, int u, int v, int w, int n, const Vector<int> &V, bool relaxed) {
int p;
real_t Ax, Ay, Bx, By, Cx, Cy, Px, Py;
const Vector2 *contour = &p_contour[0];
@@ -91,13 +96,20 @@ bool Triangulate::snip(const Vector<Vector2> &p_contour, int u, int v, int w, in
Cx = contour[V[w]].x;
Cy = contour[V[w]].y;
- if (CMP_EPSILON > (((Bx - Ax) * (Cy - Ay)) - ((By - Ay) * (Cx - Ax)))) return false;
+ // It can happen that the triangulation ends up with three aligned vertices to deal with.
+ // In this scenario, making the check below strict may reject the possibility of
+ // forming a last triangle with these aligned vertices, preventing the triangulatiom
+ // from completing.
+ // To avoid that we allow zero-area triangles if all else failed.
+ float threshold = relaxed ? -CMP_EPSILON : CMP_EPSILON;
+
+ if (threshold > (((Bx - Ax) * (Cy - Ay)) - ((By - Ay) * (Cx - Ax)))) return false;
for (p = 0; p < n; p++) {
if ((p == u) || (p == v) || (p == w)) continue;
Px = contour[V[p]].x;
Py = contour[V[p]].y;
- if (is_inside_triangle(Ax, Ay, Bx, By, Cx, Cy, Px, Py)) return false;
+ if (is_inside_triangle(Ax, Ay, Bx, By, Cx, Cy, Px, Py, relaxed)) return false;
}
return true;
@@ -121,6 +133,8 @@ bool Triangulate::triangulate(const Vector<Vector2> &contour, Vector<int> &resul
for (int v = 0; v < n; v++)
V[v] = (n - 1) - v;
+ bool relaxed = false;
+
int nv = n;
/* remove nv-2 Vertices, creating 1 triangle every time */
@@ -129,8 +143,20 @@ bool Triangulate::triangulate(const Vector<Vector2> &contour, Vector<int> &resul
for (int v = nv - 1; nv > 2;) {
/* if we loop, it is probably a non-simple polygon */
if (0 >= (count--)) {
- //** Triangulate: ERROR - probable bad polygon!
- return false;
+ if (relaxed) {
+ //** Triangulate: ERROR - probable bad polygon!
+ return false;
+ } else {
+ // There may be aligned vertices that the strict
+ // checks prevent from triangulating. In this situation
+ // we are better off adding flat triangles than
+ // failing, so we relax the checks and try one last
+ // round.
+ // Only relaxing the constraints as a last resort avoids
+ // degenerate triangles when they aren't necessary.
+ count = 2 * nv;
+ relaxed = true;
+ }
}
/* three consecutive vertices in current polygon, <u,v,w> */
@@ -141,7 +167,7 @@ bool Triangulate::triangulate(const Vector<Vector2> &contour, Vector<int> &resul
int w = v + 1;
if (nv <= w) w = 0; /* next */
- if (snip(contour, u, v, w, nv, V)) {
+ if (snip(contour, u, v, w, nv, V, relaxed)) {
int a, b, c, s, t;
/* true names of the vertices */
diff --git a/core/math/triangulate.h b/core/math/triangulate.h
index e336dc5756..b1a583d0c5 100644
--- a/core/math/triangulate.h
+++ b/core/math/triangulate.h
@@ -51,10 +51,11 @@ public:
static bool is_inside_triangle(real_t Ax, real_t Ay,
real_t Bx, real_t By,
real_t Cx, real_t Cy,
- real_t Px, real_t Py);
+ real_t Px, real_t Py,
+ bool include_edges);
private:
- static bool snip(const Vector<Vector2> &p_contour, int u, int v, int w, int n, const Vector<int> &V);
+ static bool snip(const Vector<Vector2> &p_contour, int u, int v, int w, int n, const Vector<int> &V, bool relaxed);
};
#endif
generated by cgit v1.2.3 (git 2.25.1) at 2025-04-08 13:39:37 +0000