summaryrefslogtreecommitdiff
path: root/core/math
diff options
context:
space:
mode:
Diffstat (limited to 'core/math')
-rw-r--r--core/math/geometry.h28
-rw-r--r--core/math/math_2d.cpp13
-rw-r--r--core/math/math_2d.h5
-rw-r--r--core/math/math_funcs.cpp15
-rw-r--r--core/math/math_funcs.h14
-rw-r--r--core/math/matrix3.cpp63
-rw-r--r--core/math/matrix3.h15
-rw-r--r--core/math/quat.cpp2
-rw-r--r--core/math/quick_hull.cpp2
-rw-r--r--core/math/transform.cpp4
-rw-r--r--core/math/triangulate.cpp42
-rw-r--r--core/math/triangulate.h5
-rw-r--r--core/math/vector3.h6
13 files changed, 167 insertions, 47 deletions
diff --git a/core/math/geometry.h b/core/math/geometry.h
index ca4363e129..be998aef0b 100644
--- a/core/math/geometry.h
+++ b/core/math/geometry.h
@@ -502,16 +502,15 @@ public:
}
static bool is_point_in_triangle(const Vector2 &s, const Vector2 &a, const Vector2 &b, const Vector2 &c) {
- int as_x = s.x - a.x;
- int as_y = s.y - a.y;
+ Vector2 an = a - s;
+ Vector2 bn = b - s;
+ Vector2 cn = c - s;
- bool s_ab = (b.x - a.x) * as_y - (b.y - a.y) * as_x > 0;
+ bool orientation = an.cross(bn) > 0;
- if (((c.x - a.x) * as_y - (c.y - a.y) * as_x > 0) == s_ab) return false;
+ if ((bn.cross(cn) > 0) != orientation) return false;
- if (((c.x - b.x) * (s.y - b.y) - (c.y - b.y) * (s.x - b.x) > 0) != s_ab) return false;
-
- return true;
+ return (cn.cross(an) > 0) == orientation;
}
static bool is_point_in_polygon(const Vector2 &p_point, const Vector<Vector2> &p_polygon);
@@ -530,6 +529,21 @@ public:
return p_segment[0] + n * d; // inside
}
+ static bool line_intersects_line_2d(const Vector2 &p_from_a, const Vector2 &p_dir_a, const Vector2 &p_from_b, const Vector2 &p_dir_b, Vector2 &r_result) {
+
+ // see http://paulbourke.net/geometry/pointlineplane/
+
+ const real_t denom = p_dir_b.y * p_dir_a.x - p_dir_b.x * p_dir_a.y;
+ if (Math::abs(denom) < CMP_EPSILON) { // parallel?
+ return false;
+ }
+
+ const Vector2 v = p_from_a - p_from_b;
+ const real_t t = (p_dir_b.x * v.y - p_dir_b.y * v.x) / denom;
+ r_result = p_from_a + t * p_dir_a;
+ return true;
+ }
+
static bool segment_intersects_segment_2d(const Vector2 &p_from_a, const Vector2 &p_to_a, const Vector2 &p_from_b, const Vector2 &p_to_b, Vector2 *r_result) {
Vector2 B = p_to_a - p_from_a;
diff --git a/core/math/math_2d.cpp b/core/math/math_2d.cpp
index d2e4101999..a053ffbd93 100644
--- a/core/math/math_2d.cpp
+++ b/core/math/math_2d.cpp
@@ -98,14 +98,19 @@ 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 {
+Vector2 Vector2::floor() const {
- return Vector2(p_other * y, -p_other * x);
+ return Vector2(Math::floor(x), Math::floor(y));
}
-Vector2 Vector2::floor() const {
+Vector2 Vector2::ceil() const {
- return Vector2(Math::floor(x), Math::floor(y));
+ return Vector2(Math::ceil(x), Math::ceil(y));
+}
+
+Vector2 Vector2::round() const {
+
+ return Vector2(Math::round(x), Math::round(y));
}
Vector2 Vector2::rotated(real_t p_by) const {
diff --git a/core/math/math_2d.h b/core/math/math_2d.h
index 8928349a44..611d47e3ff 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;
@@ -163,6 +162,8 @@ struct Vector2 {
}
Vector2 floor() const;
+ Vector2 ceil() const;
+ Vector2 round() const;
Vector2 snapped(const Vector2 &p_by) const;
real_t aspect() const { return width / height; }
@@ -304,7 +305,7 @@ struct Rect2 {
inline real_t distance_to(const Vector2 &p_point) const {
- real_t dist;
+ real_t dist = 0.0;
bool inside = true;
if (p_point.x < position.x) {
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..20001bb9a6 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 value - (rng * Math::floor((value - min) / rng));
+ }
+ static _ALWAYS_INLINE_ float wrapf(float value, float min, float max) {
+ float rng = max - min;
+ return value - (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/matrix3.cpp b/core/math/matrix3.cpp
index 189b1ef9b3..b0b05d1ec8 100644
--- a/core/math/matrix3.cpp
+++ b/core/math/matrix3.cpp
@@ -254,7 +254,7 @@ void Basis::set_scale(const Vector3 &p_scale) {
set_axis(2, get_axis(2).normalized() * p_scale.z);
}
-Vector3 Basis::get_scale() const {
+Vector3 Basis::get_scale_abs() const {
return Vector3(
Vector3(elements[0][0], elements[1][0], elements[2][0]).length(),
@@ -262,7 +262,13 @@ Vector3 Basis::get_scale() const {
Vector3(elements[0][2], elements[1][2], elements[2][2]).length());
}
-Vector3 Basis::get_signed_scale() const {
+Vector3 Basis::get_scale_local() const {
+ real_t det_sign = determinant() > 0 ? 1 : -1;
+ return det_sign * Vector3(elements[0].length(), elements[1].length(), elements[2].length());
+}
+
+// get_scale works with get_rotation, use get_scale_abs if you need to enforce positive signature.
+Vector3 Basis::get_scale() const {
// FIXME: We are assuming M = R.S (R is rotation and S is scaling), and use polar decomposition to extract R and S.
// A polar decomposition is M = O.P, where O is an orthogonal matrix (meaning rotation and reflection) and
// P is a positive semi-definite matrix (meaning it contains absolute values of scaling along its diagonal).
@@ -342,6 +348,14 @@ void Basis::rotate(const Vector3 &p_euler) {
*this = rotated(p_euler);
}
+Basis Basis::rotated(const Quat &p_quat) const {
+ return Basis(p_quat) * (*this);
+}
+
+void Basis::rotate(const Quat &p_quat) {
+ *this = rotated(p_quat);
+}
+
// TODO: rename this to get_rotation_euler
Vector3 Basis::get_rotation() const {
// Assumes that the matrix can be decomposed into a proper rotation and scaling matrix as M = R.S,
@@ -371,6 +385,22 @@ void Basis::get_rotation_axis_angle(Vector3 &p_axis, real_t &p_angle) const {
m.get_axis_angle(p_axis, p_angle);
}
+void Basis::get_rotation_axis_angle_local(Vector3 &p_axis, real_t &p_angle) const {
+ // Assumes that the matrix can be decomposed into a proper rotation and scaling matrix as M = R.S,
+ // and returns the Euler angles corresponding to the rotation part, complementing get_scale().
+ // See the comment in get_scale() for further information.
+ Basis m = transposed();
+ m.orthonormalize();
+ real_t det = m.determinant();
+ if (det < 0) {
+ // Ensure that the determinant is 1, such that result is a proper rotation matrix which can be represented by Euler angles.
+ m.scale(Vector3(-1, -1, -1));
+ }
+
+ m.get_axis_angle(p_axis, p_angle);
+ p_angle = -p_angle;
+}
+
// get_euler_xyz returns a vector containing the Euler angles in the format
// (a1,a2,a3), where a3 is the angle of the first rotation, and a1 is the last
// (following the convention they are commonly defined in the literature).
@@ -767,3 +797,32 @@ void Basis::set_axis_angle(const Vector3 &p_axis, real_t p_phi) {
elements[2][1] = p_axis.y * p_axis.z * (1.0 - cosine) + p_axis.x * sine;
elements[2][2] = axis_sq.z + cosine * (1.0 - axis_sq.z);
}
+
+void Basis::set_axis_angle_scale(const Vector3 &p_axis, real_t p_phi, const Vector3 &p_scale) {
+ set_diagonal(p_scale);
+ rotate(p_axis, p_phi);
+}
+
+void Basis::set_euler_scale(const Vector3 &p_euler, const Vector3 &p_scale) {
+ set_diagonal(p_scale);
+ rotate(p_euler);
+}
+
+void Basis::set_quat_scale(const Quat &p_quat, const Vector3 &p_scale) {
+ set_diagonal(p_scale);
+ rotate(p_quat);
+}
+
+void Basis::set_diagonal(const Vector3 p_diag) {
+ elements[0][0] = p_diag.x;
+ elements[0][1] = 0;
+ elements[0][2] = 0;
+
+ elements[1][0] = 0;
+ elements[1][1] = p_diag.y;
+ elements[1][2] = 0;
+
+ elements[2][0] = 0;
+ elements[2][1] = 0;
+ elements[2][2] = p_diag.z;
+}
diff --git a/core/math/matrix3.h b/core/math/matrix3.h
index c426435729..fd383fc673 100644
--- a/core/math/matrix3.h
+++ b/core/math/matrix3.h
@@ -81,8 +81,12 @@ public:
void rotate(const Vector3 &p_euler);
Basis rotated(const Vector3 &p_euler) const;
+ void rotate(const Quat &p_quat);
+ Basis rotated(const Quat &p_quat) const;
+
Vector3 get_rotation() const;
void get_rotation_axis_angle(Vector3 &p_axis, real_t &p_angle) const;
+ void get_rotation_axis_angle_local(Vector3 &p_axis, real_t &p_angle) const;
Vector3 rotref_posscale_decomposition(Basis &rotref) const;
@@ -108,7 +112,12 @@ public:
void set_scale(const Vector3 &p_scale);
Vector3 get_scale() const;
- Vector3 get_signed_scale() const;
+ Vector3 get_scale_abs() const;
+ Vector3 get_scale_local() const;
+
+ void set_axis_angle_scale(const Vector3 &p_axis, real_t p_phi, const Vector3 &p_scale);
+ void set_euler_scale(const Vector3 &p_euler, const Vector3 &p_scale);
+ void set_quat_scale(const Quat &p_quat, const Vector3 &p_scale);
// transposed dot products
_FORCE_INLINE_ real_t tdotx(const Vector3 &v) const {
@@ -140,6 +149,8 @@ public:
int get_orthogonal_index() const;
void set_orthogonal_index(int p_index);
+ void set_diagonal(const Vector3 p_diag);
+
bool is_orthogonal() const;
bool is_diagonal() const;
bool is_rotation() const;
@@ -219,6 +230,8 @@ public:
Basis(const Quat &p_quat) { set_quat(p_quat); };
Basis(const Vector3 &p_euler) { set_euler(p_euler); }
Basis(const Vector3 &p_axis, real_t p_phi) { set_axis_angle(p_axis, p_phi); }
+ Basis(const Vector3 &p_axis, real_t p_phi, const Vector3 &p_scale) { set_axis_angle_scale(p_axis, p_phi, p_scale); }
+ Basis(const Quat &p_quat, const Vector3 &p_scale) { set_quat_scale(p_quat, p_scale); }
_FORCE_INLINE_ Basis(const Vector3 &row0, const Vector3 &row1, const Vector3 &row2) {
elements[0] = row0;
diff --git a/core/math/quat.cpp b/core/math/quat.cpp
index 9aa8b537d2..4f61401ac7 100644
--- a/core/math/quat.cpp
+++ b/core/math/quat.cpp
@@ -89,7 +89,7 @@ void Quat::set_euler_yxz(const Vector3 &p_euler) {
set(sin_a1 * cos_a2 * sin_a3 + cos_a1 * sin_a2 * cos_a3,
sin_a1 * cos_a2 * cos_a3 - cos_a1 * sin_a2 * sin_a3,
- -sin_a1 * sin_a2 * cos_a3 + cos_a1 * sin_a2 * sin_a3,
+ -sin_a1 * sin_a2 * cos_a3 + cos_a1 * cos_a2 * sin_a3,
sin_a1 * sin_a2 * sin_a3 + cos_a1 * cos_a2 * cos_a3);
}
diff --git a/core/math/quick_hull.cpp b/core/math/quick_hull.cpp
index 102e454e02..fc90417413 100644
--- a/core/math/quick_hull.cpp
+++ b/core/math/quick_hull.cpp
@@ -74,7 +74,7 @@ Error QuickHull::build(const Vector<Vector3> &p_points, Geometry::MeshData &r_me
int longest_axis = aabb.get_longest_axis_index();
//first two vertices are the most distant
- int simplex[4];
+ int simplex[4] = { 0 };
{
real_t max = 0, min = 0;
diff --git a/core/math/transform.cpp b/core/math/transform.cpp
index f727d00e30..7cd186ca60 100644
--- a/core/math/transform.cpp
+++ b/core/math/transform.cpp
@@ -119,11 +119,11 @@ Transform Transform::interpolate_with(const Transform &p_transform, real_t p_c)
/* not sure if very "efficient" but good enough? */
- Vector3 src_scale = basis.get_signed_scale();
+ Vector3 src_scale = basis.get_scale();
Quat src_rot = basis.orthonormalized();
Vector3 src_loc = origin;
- Vector3 dst_scale = p_transform.basis.get_signed_scale();
+ Vector3 dst_scale = p_transform.basis.get_scale();
Quat dst_rot = p_transform.basis;
Vector3 dst_loc = p_transform.origin;
diff --git a/core/math/triangulate.cpp b/core/math/triangulate.cpp
index 957e16f92c..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
diff --git a/core/math/vector3.h b/core/math/vector3.h
index 10ec4f5641..3bbfd7627c 100644
--- a/core/math/vector3.h
+++ b/core/math/vector3.h
@@ -103,6 +103,7 @@ struct Vector3 {
_FORCE_INLINE_ Vector3 floor() const;
_FORCE_INLINE_ Vector3 sign() const;
_FORCE_INLINE_ Vector3 ceil() const;
+ _FORCE_INLINE_ Vector3 round() const;
_FORCE_INLINE_ real_t distance_to(const Vector3 &p_b) const;
_FORCE_INLINE_ real_t distance_squared_to(const Vector3 &p_b) const;
@@ -204,6 +205,11 @@ Vector3 Vector3::ceil() const {
return Vector3(Math::ceil(x), Math::ceil(y), Math::ceil(z));
}
+Vector3 Vector3::round() const {
+
+ return Vector3(Math::round(x), Math::round(y), Math::round(z));
+}
+
Vector3 Vector3::linear_interpolate(const Vector3 &p_b, real_t p_t) const {
return Vector3(
generated by cgit v1.2.3 (git 2.25.1) at 2025-01-21 03:26:53 +0000