summaryrefslogtreecommitdiff
path: root/core/math
diff options
context:
space:
mode:
Diffstat (limited to 'core/math')
-rw-r--r--core/math/a_star.cpp18
-rw-r--r--core/math/aabb.h6
-rw-r--r--core/math/basis.cpp216
-rw-r--r--core/math/basis.h13
-rw-r--r--core/math/camera_matrix.cpp18
-rw-r--r--core/math/expression.cpp54
-rw-r--r--core/math/face3.cpp6
-rw-r--r--core/math/geometry_2d.cpp384
-rw-r--r--core/math/geometry_2d.h398
-rw-r--r--core/math/geometry_3d.cpp (renamed from core/math/geometry.cpp)395
-rw-r--r--core/math/geometry_3d.h (renamed from core/math/geometry.h)382
-rw-r--r--core/math/octree.h4
-rw-r--r--core/math/plane.cpp4
-rw-r--r--core/math/plane.h1
-rw-r--r--core/math/quick_hull.cpp18
-rw-r--r--core/math/quick_hull.h6
-rw-r--r--core/math/rect2.h4
-rw-r--r--core/math/transform_2d.cpp7
-rw-r--r--core/math/triangulate.cpp2
-rw-r--r--core/math/vector2.cpp13
-rw-r--r--core/math/vector2.h13
21 files changed, 1114 insertions, 848 deletions
diff --git a/core/math/a_star.cpp b/core/math/a_star.cpp
index 45c4a207c3..30f712b2c3 100644
--- a/core/math/a_star.cpp
+++ b/core/math/a_star.cpp
@@ -30,7 +30,7 @@
#include "a_star.h"
-#include "core/math/geometry.h"
+#include "core/math/geometry_3d.h"
#include "core/script_language.h"
#include "scene/scene_string_names.h"
@@ -280,10 +280,16 @@ int AStar::get_closest_point(const Vector3 &p_point, bool p_include_disabled) co
continue; // Disabled points should not be considered.
}
+ // Keep the closest point's ID, and in case of multiple closest IDs,
+ // the smallest one (makes it deterministic).
real_t d = p_point.distance_squared_to((*it.value)->pos);
- if (closest_id < 0 || d < closest_dist) {
+ int id = *(it.key);
+ if (d <= closest_dist) {
+ if (d == closest_dist && id > closest_id) { // Keep lowest ID.
+ continue;
+ }
closest_dist = d;
- closest_id = *(it.key);
+ closest_id = id;
}
}
@@ -291,7 +297,6 @@ int AStar::get_closest_point(const Vector3 &p_point, bool p_include_disabled) co
}
Vector3 AStar::get_closest_position_in_segment(const Vector3 &p_point) const {
- bool found = false;
real_t closest_dist = 1e20;
Vector3 closest_point;
@@ -309,12 +314,11 @@ Vector3 AStar::get_closest_position_in_segment(const Vector3 &p_point) const {
to_point->pos,
};
- Vector3 p = Geometry::get_closest_point_to_segment(p_point, segment);
+ Vector3 p = Geometry3D::get_closest_point_to_segment(p_point, segment);
real_t d = p_point.distance_squared_to(p);
- if (!found || d < closest_dist) {
+ if (d < closest_dist) {
closest_point = p;
closest_dist = d;
- found = true;
}
}
diff --git a/core/math/aabb.h b/core/math/aabb.h
index 9bbedfe59c..bd1f3a1a36 100644
--- a/core/math/aabb.h
+++ b/core/math/aabb.h
@@ -99,6 +99,10 @@ public:
_FORCE_INLINE_ void project_range_in_plane(const Plane &p_plane, real_t &r_min, real_t &r_max) const;
_FORCE_INLINE_ void expand_to(const Vector3 &p_vector); /** expand to contain a point if necessary */
+ _FORCE_INLINE_ AABB abs() const {
+ return AABB(Vector3(position.x + MIN(size.x, 0), position.y + MIN(size.y, 0), position.z + MIN(size.z, 0)), size.abs());
+ }
+
operator String() const;
_FORCE_INLINE_ AABB() {}
@@ -198,7 +202,7 @@ Vector3 AABB::get_endpoint(int p_point) const {
return Vector3(position.x + size.x, position.y + size.y, position.z);
case 7:
return Vector3(position.x + size.x, position.y + size.y, position.z + size.z);
- };
+ }
ERR_FAIL_V(Vector3());
}
diff --git a/core/math/basis.cpp b/core/math/basis.cpp
index cbfd09810c..dd38e25bb1 100644
--- a/core/math/basis.cpp
+++ b/core/math/basis.cpp
@@ -428,12 +428,9 @@ Vector3 Basis::get_euler_xyz() const {
// -cx*cz*sy+sx*sz cz*sx+cx*sy*sz cx*cy
Vector3 euler;
-#ifdef MATH_CHECKS
- ERR_FAIL_COND_V(!is_rotation(), euler);
-#endif
real_t sy = elements[0][2];
- if (sy < 1.0) {
- if (sy > -1.0) {
+ if (sy < (1.0 - CMP_EPSILON)) {
+ if (sy > -(1.0 - CMP_EPSILON)) {
// is this a pure Y rotation?
if (elements[1][0] == 0.0 && elements[0][1] == 0.0 && elements[1][2] == 0 && elements[2][1] == 0 && elements[1][1] == 1) {
// return the simplest form (human friendlier in editor and scripts)
@@ -446,12 +443,12 @@ Vector3 Basis::get_euler_xyz() const {
euler.z = Math::atan2(-elements[0][1], elements[0][0]);
}
} else {
- euler.x = -Math::atan2(elements[0][1], elements[1][1]);
+ euler.x = Math::atan2(elements[2][1], elements[1][1]);
euler.y = -Math_PI / 2.0;
euler.z = 0.0;
}
} else {
- euler.x = Math::atan2(elements[0][1], elements[1][1]);
+ euler.x = Math::atan2(elements[2][1], elements[1][1]);
euler.y = Math_PI / 2.0;
euler.z = 0.0;
}
@@ -481,15 +478,106 @@ void Basis::set_euler_xyz(const Vector3 &p_euler) {
*this = xmat * (ymat * zmat);
}
+Vector3 Basis::get_euler_xzy() const {
+ // Euler angles in XZY convention.
+ // See https://en.wikipedia.org/wiki/Euler_angles#Rotation_matrix
+ //
+ // rot = cz*cy -sz cz*sy
+ // sx*sy+cx*cy*sz cx*cz cx*sz*sy-cy*sx
+ // cy*sx*sz cz*sx cx*cy+sx*sz*sy
+
+ Vector3 euler;
+ real_t sz = elements[0][1];
+ if (sz < (1.0 - CMP_EPSILON)) {
+ if (sz > -(1.0 - CMP_EPSILON)) {
+ euler.x = Math::atan2(elements[2][1], elements[1][1]);
+ euler.y = Math::atan2(elements[0][2], elements[0][0]);
+ euler.z = Math::asin(-sz);
+ } else {
+ // It's -1
+ euler.x = -Math::atan2(elements[1][2], elements[2][2]);
+ euler.y = 0.0;
+ euler.z = Math_PI / 2.0;
+ }
+ } else {
+ // It's 1
+ euler.x = -Math::atan2(elements[1][2], elements[2][2]);
+ euler.y = 0.0;
+ euler.z = -Math_PI / 2.0;
+ }
+ return euler;
+}
+
+void Basis::set_euler_xzy(const Vector3 &p_euler) {
+ real_t c, s;
+
+ c = Math::cos(p_euler.x);
+ s = Math::sin(p_euler.x);
+ Basis xmat(1.0, 0.0, 0.0, 0.0, c, -s, 0.0, s, c);
+
+ c = Math::cos(p_euler.y);
+ s = Math::sin(p_euler.y);
+ Basis ymat(c, 0.0, s, 0.0, 1.0, 0.0, -s, 0.0, c);
+
+ c = Math::cos(p_euler.z);
+ s = Math::sin(p_euler.z);
+ Basis zmat(c, -s, 0.0, s, c, 0.0, 0.0, 0.0, 1.0);
+
+ *this = xmat * zmat * ymat;
+}
+
+Vector3 Basis::get_euler_yzx() const {
+ // Euler angles in YZX convention.
+ // See https://en.wikipedia.org/wiki/Euler_angles#Rotation_matrix
+ //
+ // rot = cy*cz sy*sx-cy*cx*sz cx*sy+cy*sz*sx
+ // sz cz*cx -cz*sx
+ // -cz*sy cy*sx+cx*sy*sz cy*cx-sy*sz*sx
+
+ Vector3 euler;
+ real_t sz = elements[1][0];
+ if (sz < (1.0 - CMP_EPSILON)) {
+ if (sz > -(1.0 - CMP_EPSILON)) {
+ euler.x = Math::atan2(-elements[1][2], elements[1][1]);
+ euler.y = Math::atan2(-elements[2][0], elements[0][0]);
+ euler.z = Math::asin(sz);
+ } else {
+ // It's -1
+ euler.x = Math::atan2(elements[2][1], elements[2][2]);
+ euler.y = 0.0;
+ euler.z = -Math_PI / 2.0;
+ }
+ } else {
+ // It's 1
+ euler.x = Math::atan2(elements[2][1], elements[2][2]);
+ euler.y = 0.0;
+ euler.z = Math_PI / 2.0;
+ }
+ return euler;
+}
+
+void Basis::set_euler_yzx(const Vector3 &p_euler) {
+ real_t c, s;
+
+ c = Math::cos(p_euler.x);
+ s = Math::sin(p_euler.x);
+ Basis xmat(1.0, 0.0, 0.0, 0.0, c, -s, 0.0, s, c);
+
+ c = Math::cos(p_euler.y);
+ s = Math::sin(p_euler.y);
+ Basis ymat(c, 0.0, s, 0.0, 1.0, 0.0, -s, 0.0, c);
+
+ c = Math::cos(p_euler.z);
+ s = Math::sin(p_euler.z);
+ Basis zmat(c, -s, 0.0, s, c, 0.0, 0.0, 0.0, 1.0);
+
+ *this = ymat * zmat * xmat;
+}
+
// get_euler_yxz returns a vector containing the Euler angles in the YXZ convention,
// as in first-Z, then-X, last-Y. The angles for X, Y, and Z rotations are returned
// as the x, y, and z components of a Vector3 respectively.
Vector3 Basis::get_euler_yxz() const {
- /* checking this is a bad idea, because obtaining from scaled transform is a valid use case
-#ifdef MATH_CHECKS
- ERR_FAIL_COND(!is_rotation());
-#endif
-*/
// Euler angles in YXZ convention.
// See https://en.wikipedia.org/wiki/Euler_angles#Rotation_matrix
//
@@ -501,8 +589,8 @@ Vector3 Basis::get_euler_yxz() const {
real_t m12 = elements[1][2];
- if (m12 < 1) {
- if (m12 > -1) {
+ if (m12 < (1 - CMP_EPSILON)) {
+ if (m12 > -(1 - CMP_EPSILON)) {
// is this a pure X rotation?
if (elements[1][0] == 0 && elements[0][1] == 0 && elements[0][2] == 0 && elements[2][0] == 0 && elements[0][0] == 1) {
// return the simplest form (human friendlier in editor and scripts)
@@ -516,12 +604,12 @@ Vector3 Basis::get_euler_yxz() const {
}
} else { // m12 == -1
euler.x = Math_PI * 0.5;
- euler.y = -atan2(-elements[0][1], elements[0][0]);
+ euler.y = atan2(elements[0][1], elements[0][0]);
euler.z = 0;
}
} else { // m12 == 1
euler.x = -Math_PI * 0.5;
- euler.y = -atan2(-elements[0][1], elements[0][0]);
+ euler.y = -atan2(elements[0][1], elements[0][0]);
euler.z = 0;
}
@@ -551,6 +639,100 @@ void Basis::set_euler_yxz(const Vector3 &p_euler) {
*this = ymat * xmat * zmat;
}
+Vector3 Basis::get_euler_zxy() const {
+ // Euler angles in ZXY convention.
+ // See https://en.wikipedia.org/wiki/Euler_angles#Rotation_matrix
+ //
+ // rot = cz*cy-sz*sx*sy -cx*sz cz*sy+cy*sz*sx
+ // cy*sz+cz*sx*sy cz*cx sz*sy-cz*cy*sx
+ // -cx*sy sx cx*cy
+ Vector3 euler;
+ real_t sx = elements[2][1];
+ if (sx < (1.0 - CMP_EPSILON)) {
+ if (sx > -(1.0 - CMP_EPSILON)) {
+ euler.x = Math::asin(sx);
+ euler.y = Math::atan2(-elements[2][0], elements[2][2]);
+ euler.z = Math::atan2(-elements[0][1], elements[1][1]);
+ } else {
+ // It's -1
+ euler.x = -Math_PI / 2.0;
+ euler.y = Math::atan2(elements[0][2], elements[0][0]);
+ euler.z = 0;
+ }
+ } else {
+ // It's 1
+ euler.x = Math_PI / 2.0;
+ euler.y = Math::atan2(elements[0][2], elements[0][0]);
+ euler.z = 0;
+ }
+ return euler;
+}
+
+void Basis::set_euler_zxy(const Vector3 &p_euler) {
+ real_t c, s;
+
+ c = Math::cos(p_euler.x);
+ s = Math::sin(p_euler.x);
+ Basis xmat(1.0, 0.0, 0.0, 0.0, c, -s, 0.0, s, c);
+
+ c = Math::cos(p_euler.y);
+ s = Math::sin(p_euler.y);
+ Basis ymat(c, 0.0, s, 0.0, 1.0, 0.0, -s, 0.0, c);
+
+ c = Math::cos(p_euler.z);
+ s = Math::sin(p_euler.z);
+ Basis zmat(c, -s, 0.0, s, c, 0.0, 0.0, 0.0, 1.0);
+
+ *this = zmat * xmat * ymat;
+}
+
+Vector3 Basis::get_euler_zyx() const {
+ // Euler angles in ZYX convention.
+ // See https://en.wikipedia.org/wiki/Euler_angles#Rotation_matrix
+ //
+ // rot = cz*cy cz*sy*sx-cx*sz sz*sx+cz*cx*cy
+ // cy*sz cz*cx+sz*sy*sx cx*sz*sy-cz*sx
+ // -sy cy*sx cy*cx
+ Vector3 euler;
+ real_t sy = elements[2][0];
+ if (sy < (1.0 - CMP_EPSILON)) {
+ if (sy > -(1.0 - CMP_EPSILON)) {
+ euler.x = Math::atan2(elements[2][1], elements[2][2]);
+ euler.y = Math::asin(-sy);
+ euler.z = Math::atan2(elements[1][0], elements[0][0]);
+ } else {
+ // It's -1
+ euler.x = 0;
+ euler.y = Math_PI / 2.0;
+ euler.z = -Math::atan2(elements[0][1], elements[1][1]);
+ }
+ } else {
+ // It's 1
+ euler.x = 0;
+ euler.y = -Math_PI / 2.0;
+ euler.z = -Math::atan2(elements[0][1], elements[1][1]);
+ }
+ return euler;
+}
+
+void Basis::set_euler_zyx(const Vector3 &p_euler) {
+ real_t c, s;
+
+ c = Math::cos(p_euler.x);
+ s = Math::sin(p_euler.x);
+ Basis xmat(1.0, 0.0, 0.0, 0.0, c, -s, 0.0, s, c);
+
+ c = Math::cos(p_euler.y);
+ s = Math::sin(p_euler.y);
+ Basis ymat(c, 0.0, s, 0.0, 1.0, 0.0, -s, 0.0, c);
+
+ c = Math::cos(p_euler.z);
+ s = Math::sin(p_euler.z);
+ Basis zmat(c, -s, 0.0, s, c, 0.0, 0.0, 0.0, 1.0);
+
+ *this = zmat * ymat * xmat;
+}
+
bool Basis::is_equal_approx(const Basis &p_basis) const {
return elements[0].is_equal_approx(p_basis.elements[0]) && elements[1].is_equal_approx(p_basis.elements[1]) && elements[2].is_equal_approx(p_basis.elements[2]);
}
@@ -591,7 +773,7 @@ Basis::operator String() const {
mtx += ", ";
}
- mtx += rtos(elements[i][j]);
+ mtx += rtos(elements[j][i]); //matrix is stored transposed for performance, so print it transposed
}
}
diff --git a/core/math/basis.h b/core/math/basis.h
index d870a6b099..985fb0e44f 100644
--- a/core/math/basis.h
+++ b/core/math/basis.h
@@ -88,9 +88,22 @@ public:
Vector3 get_euler_xyz() const;
void set_euler_xyz(const Vector3 &p_euler);
+
+ Vector3 get_euler_xzy() const;
+ void set_euler_xzy(const Vector3 &p_euler);
+
+ Vector3 get_euler_yzx() const;
+ void set_euler_yzx(const Vector3 &p_euler);
+
Vector3 get_euler_yxz() const;
void set_euler_yxz(const Vector3 &p_euler);
+ Vector3 get_euler_zxy() const;
+ void set_euler_zxy(const Vector3 &p_euler);
+
+ Vector3 get_euler_zyx() const;
+ void set_euler_zyx(const Vector3 &p_euler);
+
Quat get_quat() const;
void set_quat(const Quat &p_quat);
diff --git a/core/math/camera_matrix.cpp b/core/math/camera_matrix.cpp
index 81c602d8fe..22ab83f358 100644
--- a/core/math/camera_matrix.cpp
+++ b/core/math/camera_matrix.cpp
@@ -116,18 +116,18 @@ void CameraMatrix::set_perspective(real_t p_fovy_degrees, real_t p_aspect, real_
left = -xmax + frustumshift;
right = xmax + frustumshift;
modeltranslation = p_intraocular_dist / 2.0;
- }; break;
+ } break;
case 2: { // right eye
left = -xmax - frustumshift;
right = xmax - frustumshift;
modeltranslation = -p_intraocular_dist / 2.0;
- }; break;
+ } break;
default: { // mono, should give the same result as set_perspective(p_fovy_degrees,p_aspect,p_z_near,p_z_far,p_flip_fov)
left = -xmax;
right = xmax;
modeltranslation = 0.0;
- }; break;
- };
+ } break;
+ }
set_frustum(left, right, -ymax, ymax, p_z_near, p_z_far);
@@ -157,14 +157,14 @@ void CameraMatrix::set_for_hmd(int p_eye, real_t p_aspect, real_t p_intraocular_
switch (p_eye) {
case 1: { // left eye
set_frustum(-f2 * p_z_near, f1 * p_z_near, -f3 * p_z_near, f3 * p_z_near, p_z_near, p_z_far);
- }; break;
+ } break;
case 2: { // right eye
set_frustum(-f1 * p_z_near, f2 * p_z_near, -f3 * p_z_near, f3 * p_z_near, p_z_near, p_z_far);
- }; break;
+ } break;
default: { // mono, does not apply here!
- }; break;
- };
-};
+ } break;
+ }
+}
void CameraMatrix::set_orthogonal(real_t p_left, real_t p_right, real_t p_bottom, real_t p_top, real_t p_znear, real_t p_zfar) {
set_identity();
diff --git a/core/math/expression.cpp b/core/math/expression.cpp
index 81c1e7f564..13a49feb6b 100644
--- a/core/math/expression.cpp
+++ b/core/math/expression.cpp
@@ -753,39 +753,39 @@ Error Expression::_get_token(Token &r_token) {
case 0: {
r_token.type = TK_EOF;
return OK;
- };
+ }
case '{': {
r_token.type = TK_CURLY_BRACKET_OPEN;
return OK;
- };
+ }
case '}': {
r_token.type = TK_CURLY_BRACKET_CLOSE;
return OK;
- };
+ }
case '[': {
r_token.type = TK_BRACKET_OPEN;
return OK;
- };
+ }
case ']': {
r_token.type = TK_BRACKET_CLOSE;
return OK;
- };
+ }
case '(': {
r_token.type = TK_PARENTHESIS_OPEN;
return OK;
- };
+ }
case ')': {
r_token.type = TK_PARENTHESIS_CLOSE;
return OK;
- };
+ }
case ',': {
r_token.type = TK_COMMA;
return OK;
- };
+ }
case ':': {
r_token.type = TK_COLON;
return OK;
- };
+ }
case '$': {
r_token.type = TK_INPUT;
int index = 0;
@@ -803,7 +803,7 @@ Error Expression::_get_token(Token &r_token) {
r_token.value = index;
return OK;
- };
+ }
case '=': {
cchar = GET_CHAR();
if (cchar == '=') {
@@ -814,7 +814,7 @@ Error Expression::_get_token(Token &r_token) {
return ERR_PARSE_ERROR;
}
return OK;
- };
+ }
case '!': {
if (expression[str_ofs] == '=') {
r_token.type = TK_OP_NOT_EQUAL;
@@ -823,7 +823,7 @@ Error Expression::_get_token(Token &r_token) {
r_token.type = TK_OP_NOT;
}
return OK;
- };
+ }
case '>': {
if (expression[str_ofs] == '=') {
r_token.type = TK_OP_GREATER_EQUAL;
@@ -835,7 +835,7 @@ Error Expression::_get_token(Token &r_token) {
r_token.type = TK_OP_GREATER;
}
return OK;
- };
+ }
case '<': {
if (expression[str_ofs] == '=') {
r_token.type = TK_OP_LESS_EQUAL;
@@ -847,27 +847,27 @@ Error Expression::_get_token(Token &r_token) {
r_token.type = TK_OP_LESS;
}
return OK;
- };
+ }
case '+': {
r_token.type = TK_OP_ADD;
return OK;
- };
+ }
case '-': {
r_token.type = TK_OP_SUB;
return OK;
- };
+ }
case '/': {
r_token.type = TK_OP_DIV;
return OK;
- };
+ }
case '*': {
r_token.type = TK_OP_MUL;
return OK;
- };
+ }
case '%': {
r_token.type = TK_OP_MOD;
return OK;
- };
+ }
case '&': {
if (expression[str_ofs] == '&') {
r_token.type = TK_OP_AND;
@@ -876,7 +876,7 @@ Error Expression::_get_token(Token &r_token) {
r_token.type = TK_OP_BIT_AND;
}
return OK;
- };
+ }
case '|': {
if (expression[str_ofs] == '|') {
r_token.type = TK_OP_OR;
@@ -885,17 +885,18 @@ Error Expression::_get_token(Token &r_token) {
r_token.type = TK_OP_BIT_OR;
}
return OK;
- };
+ }
case '^': {
r_token.type = TK_OP_BIT_XOR;
return OK;
- };
+ }
case '~': {
r_token.type = TK_OP_BIT_INVERT;
return OK;
- };
+ }
+ case '\'':
case '"': {
String str;
while (true) {
@@ -905,7 +906,8 @@ Error Expression::_get_token(Token &r_token) {
_set_error("Unterminated String");
r_token.type = TK_ERROR;
return ERR_PARSE_ERROR;
- } else if (ch == '"') {
+ } else if (ch == cchar) {
+ // cchar contain a corresponding quote symbol
break;
} else if (ch == '\\') {
//escaped characters...
@@ -1062,7 +1064,7 @@ Error Expression::_get_token(Token &r_token) {
if (is_float) {
r_token.value = num.to_double();
} else {
- r_token.value = num.to_int64();
+ r_token.value = num.to_int();
}
return OK;
@@ -1666,7 +1668,7 @@ Expression::ENode *Expression::_parse_expression() {
op = Variant::OP_BIT_NEGATE;
break;
default: {
- };
+ }
}
if (op == Variant::OP_MAX) { //stop appending stuff
diff --git a/core/math/face3.cpp b/core/math/face3.cpp
index 6d76e116be..db2bfaa58b 100644
--- a/core/math/face3.cpp
+++ b/core/math/face3.cpp
@@ -30,7 +30,7 @@
#include "face3.h"
-#include "core/math/geometry.h"
+#include "core/math/geometry_3d.h"
int Face3::split_by_plane(const Plane &p_plane, Face3 p_res[3], bool p_is_point_over[3]) const {
ERR_FAIL_COND_V(is_degenerate(), 0);
@@ -108,11 +108,11 @@ int Face3::split_by_plane(const Plane &p_plane, Face3 p_res[3], bool p_is_point_
}
bool Face3::intersects_ray(const Vector3 &p_from, const Vector3 &p_dir, Vector3 *p_intersection) const {
- return Geometry::ray_intersects_triangle(p_from, p_dir, vertex[0], vertex[1], vertex[2], p_intersection);
+ return Geometry3D::ray_intersects_triangle(p_from, p_dir, vertex[0], vertex[1], vertex[2], p_intersection);
}
bool Face3::intersects_segment(const Vector3 &p_from, const Vector3 &p_dir, Vector3 *p_intersection) const {
- return Geometry::segment_intersects_triangle(p_from, p_dir, vertex[0], vertex[1], vertex[2], p_intersection);
+ return Geometry3D::segment_intersects_triangle(p_from, p_dir, vertex[0], vertex[1], vertex[2], p_intersection);
}
bool Face3::is_degenerate() const {
diff --git a/core/math/geometry_2d.cpp b/core/math/geometry_2d.cpp
new file mode 100644
index 0000000000..4636e1c774
--- /dev/null
+++ b/core/math/geometry_2d.cpp
@@ -0,0 +1,384 @@
+/*************************************************************************/
+/* geometry_2d.cpp */
+/*************************************************************************/
+/* This file is part of: */
+/* GODOT ENGINE */
+/* https://godotengine.org */
+/*************************************************************************/
+/* Copyright (c) 2007-2020 Juan Linietsky, Ariel Manzur. */
+/* Copyright (c) 2014-2020 Godot Engine contributors (cf. AUTHORS.md). */
+/* */
+/* 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. */
+/*************************************************************************/
+
+#include "geometry_2d.h"
+
+#include "thirdparty/misc/clipper.hpp"
+#include "thirdparty/misc/triangulator.h"
+#define STB_RECT_PACK_IMPLEMENTATION
+#include "thirdparty/misc/stb_rect_pack.h"
+
+#define SCALE_FACTOR 100000.0 // Based on CMP_EPSILON.
+
+Vector<Vector<Vector2>> Geometry2D::decompose_polygon_in_convex(Vector<Point2> polygon) {
+ Vector<Vector<Vector2>> decomp;
+ List<TriangulatorPoly> in_poly, out_poly;
+
+ TriangulatorPoly inp;
+ inp.Init(polygon.size());
+ for (int i = 0; i < polygon.size(); i++) {
+ inp.GetPoint(i) = polygon[i];
+ }
+ inp.SetOrientation(TRIANGULATOR_CCW);
+ in_poly.push_back(inp);
+ TriangulatorPartition tpart;
+ if (tpart.ConvexPartition_HM(&in_poly, &out_poly) == 0) { // Failed.
+ ERR_PRINT("Convex decomposing failed!");
+ return decomp;
+ }
+
+ decomp.resize(out_poly.size());
+ int idx = 0;
+ for (List<TriangulatorPoly>::Element *I = out_poly.front(); I; I = I->next()) {
+ TriangulatorPoly &tp = I->get();
+
+ decomp.write[idx].resize(tp.GetNumPoints());
+
+ for (int64_t i = 0; i < tp.GetNumPoints(); i++) {
+ decomp.write[idx].write[i] = tp.GetPoint(i);
+ }
+
+ idx++;
+ }
+
+ return decomp;
+}
+
+struct _AtlasWorkRect {
+ Size2i s;
+ Point2i p;
+ int idx;
+ _FORCE_INLINE_ bool operator<(const _AtlasWorkRect &p_r) const { return s.width > p_r.s.width; };
+};
+
+struct _AtlasWorkRectResult {
+ Vector<_AtlasWorkRect> result;
+ int max_w;
+ int max_h;
+};
+
+void Geometry2D::make_atlas(const Vector<Size2i> &p_rects, Vector<Point2i> &r_result, Size2i &r_size) {
+ // Super simple, almost brute force scanline stacking fitter.
+ // It's pretty basic for now, but it tries to make sure that the aspect ratio of the
+ // resulting atlas is somehow square. This is necessary because video cards have limits.
+ // On texture size (usually 2048 or 4096), so the more square a texture, the more chances.
+ // It will work in every hardware.
+ // For example, it will prioritize a 1024x1024 atlas (works everywhere) instead of a
+ // 256x8192 atlas (won't work anywhere).
+
+ ERR_FAIL_COND(p_rects.size() == 0);
+
+ Vector<_AtlasWorkRect> wrects;
+ wrects.resize(p_rects.size());
+ for (int i = 0; i < p_rects.size(); i++) {
+ wrects.write[i].s = p_rects[i];
+ wrects.write[i].idx = i;
+ }
+ wrects.sort();
+ int widest = wrects[0].s.width;
+
+ Vector<_AtlasWorkRectResult> results;
+
+ for (int i = 0; i <= 12; i++) {
+ int w = 1 << i;
+ int max_h = 0;
+ int max_w = 0;
+ if (w < widest) {
+ continue;
+ }
+
+ Vector<int> hmax;
+ hmax.resize(w);
+ for (int j = 0; j < w; j++) {
+ hmax.write[j] = 0;
+ }
+
+ // Place them.
+ int ofs = 0;
+ int limit_h = 0;
+ for (int j = 0; j < wrects.size(); j++) {
+ if (ofs + wrects[j].s.width > w) {
+ ofs = 0;
+ }
+
+ int from_y = 0;
+ for (int k = 0; k < wrects[j].s.width; k++) {
+ if (hmax[ofs + k] > from_y) {
+ from_y = hmax[ofs + k];
+ }
+ }
+
+ wrects.write[j].p.x = ofs;
+ wrects.write[j].p.y = from_y;
+ int end_h = from_y + wrects[j].s.height;
+ int end_w = ofs + wrects[j].s.width;
+ if (ofs == 0) {
+ limit_h = end_h;
+ }
+
+ for (int k = 0; k < wrects[j].s.width; k++) {
+ hmax.write[ofs + k] = end_h;
+ }
+
+ if (end_h > max_h) {
+ max_h = end_h;
+ }
+
+ if (end_w > max_w) {
+ max_w = end_w;
+ }
+
+ if (ofs == 0 || end_h > limit_h) { // While h limit not reached, keep stacking.
+ ofs += wrects[j].s.width;
+ }
+ }
+
+ _AtlasWorkRectResult result;
+ result.result = wrects;
+ result.max_h = max_h;
+ result.max_w = max_w;
+ results.push_back(result);
+ }
+
+ // Find the result with the best aspect ratio.
+
+ int best = -1;
+ real_t best_aspect = 1e20;
+
+ for (int i = 0; i < results.size(); i++) {
+ real_t h = next_power_of_2(results[i].max_h);
+ real_t w = next_power_of_2(results[i].max_w);
+ real_t aspect = h > w ? h / w : w / h;
+ if (aspect < best_aspect) {
+ best = i;
+ best_aspect = aspect;
+ }
+ }
+
+ r_result.resize(p_rects.size());
+
+ for (int i = 0; i < p_rects.size(); i++) {
+ r_result.write[results[best].result[i].idx] = results[best].result[i].p;
+ }
+
+ r_size = Size2(results[best].max_w, results[best].max_h);
+}
+
+Vector<Vector<Point2>> Geometry2D::_polypaths_do_operation(PolyBooleanOperation p_op, const Vector<Point2> &p_polypath_a, const Vector<Point2> &p_polypath_b, bool is_a_open) {
+ using namespace ClipperLib;
+
+ ClipType op = ctUnion;
+
+ switch (p_op) {
+ case OPERATION_UNION:
+ op = ctUnion;
+ break;
+ case OPERATION_DIFFERENCE:
+ op = ctDifference;
+ break;
+ case OPERATION_INTERSECTION:
+ op = ctIntersection;
+ break;
+ case OPERATION_XOR:
+ op = ctXor;
+ break;
+ }
+ Path path_a, path_b;
+
+ // Need to scale points (Clipper's requirement for robust computation).
+ for (int i = 0; i != p_polypath_a.size(); ++i) {
+ path_a << IntPoint(p_polypath_a[i].x * SCALE_FACTOR, p_polypath_a[i].y * SCALE_FACTOR);
+ }
+ for (int i = 0; i != p_polypath_b.size(); ++i) {
+ path_b << IntPoint(p_polypath_b[i].x * SCALE_FACTOR, p_polypath_b[i].y * SCALE_FACTOR);
+ }
+ Clipper clp;
+ clp.AddPath(path_a, ptSubject, !is_a_open); // Forward compatible with Clipper 10.0.0.
+ clp.AddPath(path_b, ptClip, true); // Polylines cannot be set as clip.
+
+ Paths paths;
+
+ if (is_a_open) {
+ PolyTree tree; // Needed to populate polylines.
+ clp.Execute(op, tree);
+ OpenPathsFromPolyTree(tree, paths);
+ } else {
+ clp.Execute(op, paths); // Works on closed polygons only.
+ }
+ // Have to scale points down now.
+ Vector<Vector<Point2>> polypaths;
+
+ for (Paths::size_type i = 0; i < paths.size(); ++i) {
+ Vector<Vector2> polypath;
+
+ const Path &scaled_path = paths[i];
+
+ for (Paths::size_type j = 0; j < scaled_path.size(); ++j) {
+ polypath.push_back(Point2(
+ static_cast<real_t>(scaled_path[j].X) / SCALE_FACTOR,
+ static_cast<real_t>(scaled_path[j].Y) / SCALE_FACTOR));
+ }
+ polypaths.push_back(polypath);
+ }
+ return polypaths;
+}
+
+Vector<Vector<Point2>> Geometry2D::_polypath_offset(const Vector<Point2> &p_polypath, real_t p_delta, PolyJoinType p_join_type, PolyEndType p_end_type) {
+ using namespace ClipperLib;
+
+ JoinType jt = jtSquare;
+
+ switch (p_join_type) {
+ case JOIN_SQUARE:
+ jt = jtSquare;
+ break;
+ case JOIN_ROUND:
+ jt = jtRound;
+ break;
+ case JOIN_MITER:
+ jt = jtMiter;
+ break;
+ }
+
+ EndType et = etClosedPolygon;
+
+ switch (p_end_type) {
+ case END_POLYGON:
+ et = etClosedPolygon;
+ break;
+ case END_JOINED:
+ et = etClosedLine;
+ break;
+ case END_BUTT:
+ et = etOpenButt;
+ break;
+ case END_SQUARE:
+ et = etOpenSquare;
+ break;
+ case END_ROUND:
+ et = etOpenRound;
+ break;
+ }
+ ClipperOffset co(2.0, 0.25 * SCALE_FACTOR); // Defaults from ClipperOffset.
+ Path path;
+
+ // Need to scale points (Clipper's requirement for robust computation).
+ for (int i = 0; i != p_polypath.size(); ++i) {
+ path << IntPoint(p_polypath[i].x * SCALE_FACTOR, p_polypath[i].y * SCALE_FACTOR);
+ }
+ co.AddPath(path, jt, et);
+
+ Paths paths;
+ co.Execute(paths, p_delta * SCALE_FACTOR); // Inflate/deflate.
+
+ // Have to scale points down now.
+ Vector<Vector<Point2>> polypaths;
+
+ for (Paths::size_type i = 0; i < paths.size(); ++i) {
+ Vector<Vector2> polypath;
+
+ const Path &scaled_path = paths[i];
+
+ for (Paths::size_type j = 0; j < scaled_path.size(); ++j) {
+ polypath.push_back(Point2(
+ static_cast<real_t>(scaled_path[j].X) / SCALE_FACTOR,
+ static_cast<real_t>(scaled_path[j].Y) / SCALE_FACTOR));
+ }
+ polypaths.push_back(polypath);
+ }
+ return polypaths;
+}
+
+Vector<Point2i> Geometry2D::pack_rects(const Vector<Size2i> &p_sizes, const Size2i &p_atlas_size) {
+ Vector<stbrp_node> nodes;
+ nodes.resize(p_atlas_size.width);
+
+ stbrp_context context;
+ stbrp_init_target(&context, p_atlas_size.width, p_atlas_size.height, nodes.ptrw(), p_atlas_size.width);
+
+ Vector<stbrp_rect> rects;
+ rects.resize(p_sizes.size());
+
+ for (int i = 0; i < p_sizes.size(); i++) {
+ rects.write[i].id = 0;
+ rects.write[i].w = p_sizes[i].width;
+ rects.write[i].h = p_sizes[i].height;
+ rects.write[i].x = 0;
+ rects.write[i].y = 0;
+ rects.write[i].was_packed = 0;
+ }
+
+ int res = stbrp_pack_rects(&context, rects.ptrw(), rects.size());
+ if (res == 0) { //pack failed
+ return Vector<Point2i>();
+ }
+
+ Vector<Point2i> ret;
+ ret.resize(p_sizes.size());
+
+ for (int i = 0; i < p_sizes.size(); i++) {
+ Point2i r(rects[i].x, rects[i].y);
+ ret.write[i] = r;
+ }
+
+ return ret;
+}
+
+Vector<Vector3i> Geometry2D::partial_pack_rects(const Vector<Vector2i> &p_sizes, const Size2i &p_atlas_size) {
+ Vector<stbrp_node> nodes;
+ nodes.resize(p_atlas_size.width);
+ zeromem(nodes.ptrw(), sizeof(stbrp_node) * nodes.size());
+
+ stbrp_context context;
+ stbrp_init_target(&context, p_atlas_size.width, p_atlas_size.height, nodes.ptrw(), p_atlas_size.width);
+
+ Vector<stbrp_rect> rects;
+ rects.resize(p_sizes.size());
+
+ for (int i = 0; i < p_sizes.size(); i++) {
+ rects.write[i].id = i;
+ rects.write[i].w = p_sizes[i].width;
+ rects.write[i].h = p_sizes[i].height;
+ rects.write[i].x = 0;
+ rects.write[i].y = 0;
+ rects.write[i].was_packed = 0;
+ }
+
+ stbrp_pack_rects(&context, rects.ptrw(), rects.size());
+
+ Vector<Vector3i> ret;
+ ret.resize(p_sizes.size());
+
+ for (int i = 0; i < p_sizes.size(); i++) {
+ ret.write[rects[i].id] = Vector3i(rects[i].x, rects[i].y, rects[i].was_packed != 0 ? 1 : 0);
+ }
+
+ return ret;
+}
diff --git a/core/math/geometry_2d.h b/core/math/geometry_2d.h
new file mode 100644
index 0000000000..cfd7abfacb
--- /dev/null
+++ b/core/math/geometry_2d.h
@@ -0,0 +1,398 @@
+/*************************************************************************/
+/* geometry_2d.h */
+/*************************************************************************/
+/* This file is part of: */
+/* GODOT ENGINE */
+/* https://godotengine.org */
+/*************************************************************************/
+/* Copyright (c) 2007-2020 Juan Linietsky, Ariel Manzur. */
+/* Copyright (c) 2014-2020 Godot Engine contributors (cf. AUTHORS.md). */
+/* */
+/* 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 GEOMETRY_2D_H
+#define GEOMETRY_2D_H
+
+#include "core/math/delaunay_2d.h"
+#include "core/math/rect2.h"
+#include "core/math/triangulate.h"
+#include "core/object.h"
+#include "core/vector.h"
+
+class Geometry2D {
+ Geometry2D();
+
+public:
+ static real_t get_closest_points_between_segments(const Vector2 &p1, const Vector2 &q1, const Vector2 &p2, const Vector2 &q2, Vector2 &c1, Vector2 &c2) {
+ Vector2 d1 = q1 - p1; // Direction vector of segment S1.
+ Vector2 d2 = q2 - p2; // Direction vector of segment S2.
+ Vector2 r = p1 - p2;
+ real_t a = d1.dot(d1); // Squared length of segment S1, always nonnegative.
+ real_t e = d2.dot(d2); // Squared length of segment S2, always nonnegative.
+ real_t f = d2.dot(r);
+ real_t s, t;
+ // Check if either or both segments degenerate into points.
+ if (a <= CMP_EPSILON && e <= CMP_EPSILON) {
+ // Both segments degenerate into points.
+ c1 = p1;
+ c2 = p2;
+ return Math::sqrt((c1 - c2).dot(c1 - c2));
+ }
+ if (a <= CMP_EPSILON) {
+ // First segment degenerates into a point.
+ s = 0.0;
+ t = f / e; // s = 0 => t = (b*s + f) / e = f / e
+ t = CLAMP(t, 0.0, 1.0);
+ } else {
+ real_t c = d1.dot(r);
+ if (e <= CMP_EPSILON) {
+ // Second segment degenerates into a point.
+ t = 0.0;
+ s = CLAMP(-c / a, 0.0, 1.0); // t = 0 => s = (b*t - c) / a = -c / a
+ } else {
+ // The general nondegenerate case starts here.
+ real_t b = d1.dot(d2);
+ real_t denom = a * e - b * b; // Always nonnegative.
+ // If segments not parallel, compute closest point on L1 to L2 and
+ // clamp to segment S1. Else pick arbitrary s (here 0).
+ if (denom != 0.0) {
+ s = CLAMP((b * f - c * e) / denom, 0.0, 1.0);
+ } else {
+ s = 0.0;
+ }
+ // Compute point on L2 closest to S1(s) using
+ // t = Dot((P1 + D1*s) - P2,D2) / Dot(D2,D2) = (b*s + f) / e
+ t = (b * s + f) / e;
+
+ //If t in [0,1] done. Else clamp t, recompute s for the new value
+ // of t using s = Dot((P2 + D2*t) - P1,D1) / Dot(D1,D1)= (t*b - c) / a
+ // and clamp s to [0, 1].
+ if (t < 0.0) {
+ t = 0.0;
+ s = CLAMP(-c / a, 0.0, 1.0);
+ } else if (t > 1.0) {
+ t = 1.0;
+ s = CLAMP((b - c) / a, 0.0, 1.0);
+ }
+ }
+ }
+ c1 = p1 + d1 * s;
+ c2 = p2 + d2 * t;
+ return Math::sqrt((c1 - c2).dot(c1 - c2));
+ }
+
+ static Vector2 get_closest_point_to_segment(const Vector2 &p_point, const Vector2 *p_segment) {
+ Vector2 p = p_point - p_segment[0];
+ Vector2 n = p_segment[1] - p_segment[0];
+ real_t l2 = n.length_squared();
+ if (l2 < 1e-20) {
+ return p_segment[0]; // Both points are the same, just give any.
+ }
+
+ real_t d = n.dot(p) / l2;
+
+ if (d <= 0.0) {
+ return p_segment[0]; // Before first point.
+ } else if (d >= 1.0) {
+ return p_segment[1]; // After first point.
+ } else {
+ return p_segment[0] + n * d; // Inside.
+ }
+ }
+
+ static bool is_point_in_triangle(const Vector2 &s, const Vector2 &a, const Vector2 &b, const Vector2 &c) {
+ Vector2 an = a - s;
+ Vector2 bn = b - s;
+ Vector2 cn = c - s;
+
+ bool orientation = an.cross(bn) > 0;
+
+ if ((bn.cross(cn) > 0) != orientation) {
+ return false;
+ }
+
+ return (cn.cross(an) > 0) == orientation;
+ }
+
+ static Vector2 get_closest_point_to_segment_uncapped(const Vector2 &p_point, const Vector2 *p_segment) {
+ Vector2 p = p_point - p_segment[0];
+ Vector2 n = p_segment[1] - p_segment[0];
+ real_t l2 = n.length_squared();
+ if (l2 < 1e-20) {
+ return p_segment[0]; // Both points are the same, just give any.
+ }
+
+ real_t d = n.dot(p) / l2;
+
+ return p_segment[0] + n * d; // Inside.
+ }
+
+ static bool line_intersects_line(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::is_zero_approx(denom)) { // 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(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;
+ Vector2 C = p_from_b - p_from_a;
+ Vector2 D = p_to_b - p_from_a;
+
+ real_t ABlen = B.dot(B);
+ if (ABlen <= 0) {
+ return false;
+ }
+ Vector2 Bn = B / ABlen;
+ C = Vector2(C.x * Bn.x + C.y * Bn.y, C.y * Bn.x - C.x * Bn.y);
+ D = Vector2(D.x * Bn.x + D.y * Bn.y, D.y * Bn.x - D.x * Bn.y);
+
+ if ((C.y < 0 && D.y < 0) || (C.y >= 0 && D.y >= 0)) {
+ return false;
+ }
+
+ real_t ABpos = D.x + (C.x - D.x) * D.y / (D.y - C.y);
+
+ // Fail if segment C-D crosses line A-B outside of segment A-B.
+ if (ABpos < 0 || ABpos > 1.0) {
+ return false;
+ }
+
+ // (4) Apply the discovered position to line A-B in the original coordinate system.
+ if (r_result) {
+ *r_result = p_from_a + B * ABpos;
+ }
+
+ return true;
+ }
+
+ static inline bool is_point_in_circle(const Vector2 &p_point, const Vector2 &p_circle_pos, real_t p_circle_radius) {
+ return p_point.distance_squared_to(p_circle_pos) <= p_circle_radius * p_circle_radius;
+ }
+
+ static real_t segment_intersects_circle(const Vector2 &p_from, const Vector2 &p_to, const Vector2 &p_circle_pos, real_t p_circle_radius) {
+ Vector2 line_vec = p_to - p_from;
+ Vector2 vec_to_line = p_from - p_circle_pos;
+
+ // Create a quadratic formula of the form ax^2 + bx + c = 0
+ real_t a, b, c;
+
+ a = line_vec.dot(line_vec);
+ b = 2 * vec_to_line.dot(line_vec);
+ c = vec_to_line.dot(vec_to_line) - p_circle_radius * p_circle_radius;
+
+ // Solve for t.
+ real_t sqrtterm = b * b - 4 * a * c;
+
+ // If the term we intend to square root is less than 0 then the answer won't be real,
+ // so it definitely won't be t in the range 0 to 1.
+ if (sqrtterm < 0) {
+ return -1;
+ }
+
+ // If we can assume that the line segment starts outside the circle (e.g. for continuous time collision detection)
+ // then the following can be skipped and we can just return the equivalent of res1.
+ sqrtterm = Math::sqrt(sqrtterm);
+ real_t res1 = (-b - sqrtterm) / (2 * a);
+ real_t res2 = (-b + sqrtterm) / (2 * a);
+
+ if (res1 >= 0 && res1 <= 1) {
+ return res1;
+ }
+ if (res2 >= 0 && res2 <= 1) {
+ return res2;
+ }
+ return -1;
+ }
+
+ enum PolyBooleanOperation {
+ OPERATION_UNION,
+ OPERATION_DIFFERENCE,
+ OPERATION_INTERSECTION,
+ OPERATION_XOR
+ };
+ enum PolyJoinType {
+ JOIN_SQUARE,
+ JOIN_ROUND,
+ JOIN_MITER
+ };
+ enum PolyEndType {
+ END_POLYGON,
+ END_JOINED,
+ END_BUTT,
+ END_SQUARE,
+ END_ROUND
+ };
+
+ static Vector<Vector<Point2>> merge_polygons(const Vector<Point2> &p_polygon_a, const Vector<Point2> &p_polygon_b) {
+ return _polypaths_do_operation(OPERATION_UNION, p_polygon_a, p_polygon_b);
+ }
+
+ static Vector<Vector<Point2>> clip_polygons(const Vector<Point2> &p_polygon_a, const Vector<Point2> &p_polygon_b) {
+ return _polypaths_do_operation(OPERATION_DIFFERENCE, p_polygon_a, p_polygon_b);
+ }
+
+ static Vector<Vector<Point2>> intersect_polygons(const Vector<Point2> &p_polygon_a, const Vector<Point2> &p_polygon_b) {
+ return _polypaths_do_operation(OPERATION_INTERSECTION, p_polygon_a, p_polygon_b);
+ }
+
+ static Vector<Vector<Point2>> exclude_polygons(const Vector<Point2> &p_polygon_a, const Vector<Point2> &p_polygon_b) {
+ return _polypaths_do_operation(OPERATION_XOR, p_polygon_a, p_polygon_b);
+ }
+
+ static Vector<Vector<Point2>> clip_polyline_with_polygon(const Vector<Vector2> &p_polyline, const Vector<Vector2> &p_polygon) {
+ return _polypaths_do_operation(OPERATION_DIFFERENCE, p_polyline, p_polygon, true);
+ }
+
+ static Vector<Vector<Point2>> intersect_polyline_with_polygon(const Vector<Vector2> &p_polyline, const Vector<Vector2> &p_polygon) {
+ return _polypaths_do_operation(OPERATION_INTERSECTION, p_polyline, p_polygon, true);
+ }
+
+ static Vector<Vector<Point2>> offset_polygon(const Vector<Vector2> &p_polygon, real_t p_delta, PolyJoinType p_join_type) {
+ return _polypath_offset(p_polygon, p_delta, p_join_type, END_POLYGON);
+ }
+
+ static Vector<Vector<Point2>> offset_polyline(const Vector<Vector2> &p_polygon, real_t p_delta, PolyJoinType p_join_type, PolyEndType p_end_type) {
+ ERR_FAIL_COND_V_MSG(p_end_type == END_POLYGON, Vector<Vector<Point2>>(), "Attempt to offset a polyline like a polygon (use offset_polygon instead).");
+
+ return _polypath_offset(p_polygon, p_delta, p_join_type, p_end_type);
+ }
+
+ static Vector<int> triangulate_delaunay(const Vector<Vector2> &p_points) {
+ Vector<Delaunay2D::Triangle> tr = Delaunay2D::triangulate(p_points);
+ Vector<int> triangles;
+
+ for (int i = 0; i < tr.size(); i++) {
+ triangles.push_back(tr[i].points[0]);
+ triangles.push_back(tr[i].points[1]);
+ triangles.push_back(tr[i].points[2]);
+ }
+ return triangles;
+ }
+
+ static Vector<int> triangulate_polygon(const Vector<Vector2> &p_polygon) {
+ Vector<int> triangles;
+ if (!Triangulate::triangulate(p_polygon, triangles)) {
+ return Vector<int>(); //fail
+ }
+ return triangles;
+ }
+
+ static bool is_polygon_clockwise(const Vector<Vector2> &p_polygon) {
+ int c = p_polygon.size();
+ if (c < 3) {
+ return false;
+ }
+ const Vector2 *p = p_polygon.ptr();
+ real_t sum = 0;
+ for (int i = 0; i < c; i++) {
+ const Vector2 &v1 = p[i];
+ const Vector2 &v2 = p[(i + 1) % c];
+ sum += (v2.x - v1.x) * (v2.y + v1.y);
+ }
+
+ return sum > 0.0f;
+ }
+
+ // Alternate implementation that should be faster.
+ static bool is_point_in_polygon(const Vector2 &p_point, const Vector<Vector2> &p_polygon) {
+ int c = p_polygon.size();
+ if (c < 3) {
+ return false;
+ }
+ const Vector2 *p = p_polygon.ptr();
+ Vector2 further_away(-1e20, -1e20);
+ Vector2 further_away_opposite(1e20, 1e20);
+
+ for (int i = 0; i < c; i++) {
+ further_away.x = MAX(p[i].x, further_away.x);
+ further_away.y = MAX(p[i].y, further_away.y);
+ further_away_opposite.x = MIN(p[i].x, further_away_opposite.x);
+ further_away_opposite.y = MIN(p[i].y, further_away_opposite.y);
+ }
+
+ // Make point outside that won't intersect with points in segment from p_point.
+ further_away += (further_away - further_away_opposite) * Vector2(1.221313, 1.512312);
+
+ int intersections = 0;
+ for (int i = 0; i < c; i++) {
+ const Vector2 &v1 = p[i];
+ const Vector2 &v2 = p[(i + 1) % c];
+ if (segment_intersects_segment(v1, v2, p_point, further_away, nullptr)) {
+ intersections++;
+ }
+ }
+
+ return (intersections & 1);
+ }
+
+ static real_t vec2_cross(const Point2 &O, const Point2 &A, const Point2 &B) {
+ return (real_t)(A.x - O.x) * (B.y - O.y) - (real_t)(A.y - O.y) * (B.x - O.x);
+ }
+
+ // Returns a list of points on the convex hull in counter-clockwise order.
+ // Note: the last point in the returned list is the same as the first one.
+ static Vector<Point2> convex_hull(Vector<Point2> P) {
+ int n = P.size(), k = 0;
+ Vector<Point2> H;
+ H.resize(2 * n);
+
+ // Sort points lexicographically.
+ P.sort();
+
+ // Build lower hull.
+ for (int i = 0; i < n; ++i) {
+ while (k >= 2 && vec2_cross(H[k - 2], H[k - 1], P[i]) <= 0) {
+ k--;
+ }
+ H.write[k++] = P[i];
+ }
+
+ // Build upper hull.
+ for (int i = n - 2, t = k + 1; i >= 0; i--) {
+ while (k >= t && vec2_cross(H[k - 2], H[k - 1], P[i]) <= 0) {
+ k--;
+ }
+ H.write[k++] = P[i];
+ }
+
+ H.resize(k);
+ return H;
+ }
+ static Vector<Vector<Vector2>> decompose_polygon_in_convex(Vector<Point2> polygon);
+
+ static void make_atlas(const Vector<Size2i> &p_rects, Vector<Point2i> &r_result, Size2i &r_size);
+ static Vector<Point2i> pack_rects(const Vector<Size2i> &p_sizes, const Size2i &p_atlas_size);
+ static Vector<Vector3i> partial_pack_rects(const Vector<Vector2i> &p_sizes, const Size2i &p_atlas_size);
+
+private:
+ static Vector<Vector<Point2>> _polypaths_do_operation(PolyBooleanOperation p_op, const Vector<Point2> &p_polypath_a, const Vector<Point2> &p_polypath_b, bool is_a_open = false);
+ static Vector<Vector<Point2>> _polypath_offset(const Vector<Point2> &p_polypath, real_t p_delta, PolyJoinType p_join_type, PolyEndType p_end_type);
+};
+
+#endif // GEOMETRY_2D_H
diff --git a/core/math/geometry.cpp b/core/math/geometry_3d.cpp
index f6f22e1db2..2c19fe2085 100644
--- a/core/math/geometry.cpp
+++ b/core/math/geometry_3d.cpp
@@ -1,5 +1,5 @@
/*************************************************************************/
-/* geometry.cpp */
+/* geometry_3d.cpp */
/*************************************************************************/
/* This file is part of: */
/* GODOT ENGINE */
@@ -28,33 +28,14 @@
/* SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. */
/*************************************************************************/
-#include "geometry.h"
+#include "geometry_3d.h"
#include "core/print_string.h"
#include "thirdparty/misc/clipper.hpp"
#include "thirdparty/misc/triangulator.h"
-#define STB_RECT_PACK_IMPLEMENTATION
-#include "thirdparty/misc/stb_rect_pack.h"
-#define SCALE_FACTOR 100000.0 // Based on CMP_EPSILON.
-
-// This implementation is very inefficient, commenting unless bugs happen. See the other one.
-/*
-bool Geometry::is_point_in_polygon(const Vector2 &p_point, const Vector<Vector2> &p_polygon) {
-
- Vector<int> indices = Geometry::triangulate_polygon(p_polygon);
- for (int j = 0; j + 3 <= indices.size(); j += 3) {
- int i1 = indices[j], i2 = indices[j + 1], i3 = indices[j + 2];
- if (Geometry::is_point_in_triangle(p_point, p_polygon[i1], p_polygon[i2], p_polygon[i3]))
- return true;
- }
- return false;
-}
-
-*/
-
-void Geometry::MeshData::optimize_vertices() {
+void Geometry3D::MeshData::optimize_vertices() {
Map<int, int> vtx_remap;
for (int i = 0; i < faces.size(); i++) {
@@ -201,7 +182,7 @@ static bool _group_face(_FaceClassify *p_faces, int len, int p_index, int p_grou
return true;
}
-Vector<Vector<Face3>> Geometry::separate_objects(Vector<Face3> p_array) {
+Vector<Vector<Face3>> Geometry3D::separate_objects(Vector<Face3> p_array) {
Vector<Vector<Face3>> objects;
int len = p_array.size();
@@ -511,7 +492,7 @@ static inline void _build_faces(uint8_t ***p_cell_status, int x, int y, int z, i
}
}
-Vector<Face3> Geometry::wrap_geometry(Vector<Face3> p_array, real_t *p_error) {
+Vector<Face3> Geometry3D::wrap_geometry(Vector<Face3> p_array, real_t *p_error) {
#define _MIN_SIZE 1.0
#define _MAX_LENGTH 20
@@ -647,41 +628,7 @@ Vector<Face3> Geometry::wrap_geometry(Vector<Face3> p_array, real_t *p_error) {
return wrapped_faces;
}
-Vector<Vector<Vector2>> Geometry::decompose_polygon_in_convex(Vector<Point2> polygon) {
- Vector<Vector<Vector2>> decomp;
- List<TriangulatorPoly> in_poly, out_poly;
-
- TriangulatorPoly inp;
- inp.Init(polygon.size());
- for (int i = 0; i < polygon.size(); i++) {
- inp.GetPoint(i) = polygon[i];
- }
- inp.SetOrientation(TRIANGULATOR_CCW);
- in_poly.push_back(inp);
- TriangulatorPartition tpart;
- if (tpart.ConvexPartition_HM(&in_poly, &out_poly) == 0) { // Failed.
- ERR_PRINT("Convex decomposing failed!");
- return decomp;
- }
-
- decomp.resize(out_poly.size());
- int idx = 0;
- for (List<TriangulatorPoly>::Element *I = out_poly.front(); I; I = I->next()) {
- TriangulatorPoly &tp = I->get();
-
- decomp.write[idx].resize(tp.GetNumPoints());
-
- for (int64_t i = 0; i < tp.GetNumPoints(); i++) {
- decomp.write[idx].write[i] = tp.GetPoint(i);
- }
-
- idx++;
- }
-
- return decomp;
-}
-
-Geometry::MeshData Geometry::build_convex_mesh(const Vector<Plane> &p_planes) {
+Geometry3D::MeshData Geometry3D::build_convex_mesh(const Vector<Plane> &p_planes) {
MeshData mesh;
#define SUBPLANE_SIZE 1024.0
@@ -701,7 +648,7 @@ Geometry::MeshData Geometry::build_convex_mesh(const Vector<Plane> &p_planes) {
Vector<Vector3> vertices;
- Vector3 center = p.get_any_point();
+ Vector3 center = p.center();
// make a quad clockwise
vertices.push_back(center - up * subplane_size + right * subplane_size);
vertices.push_back(center - up * subplane_size - right * subplane_size);
@@ -816,7 +763,7 @@ Geometry::MeshData Geometry::build_convex_mesh(const Vector<Plane> &p_planes) {
return mesh;
}
-Vector<Plane> Geometry::build_box_planes(const Vector3 &p_extents) {
+Vector<Plane> Geometry3D::build_box_planes(const Vector3 &p_extents) {
Vector<Plane> planes;
planes.push_back(Plane(Vector3(1, 0, 0), p_extents.x));
@@ -829,7 +776,7 @@ Vector<Plane> Geometry::build_box_planes(const Vector3 &p_extents) {
return planes;
}
-Vector<Plane> Geometry::build_cylinder_planes(real_t p_radius, real_t p_height, int p_sides, Vector3::Axis p_axis) {
+Vector<Plane> Geometry3D::build_cylinder_planes(real_t p_radius, real_t p_height, int p_sides, Vector3::Axis p_axis) {
Vector<Plane> planes;
for (int i = 0; i < p_sides; i++) {
@@ -849,7 +796,7 @@ Vector<Plane> Geometry::build_cylinder_planes(real_t p_radius, real_t p_height,
return planes;
}
-Vector<Plane> Geometry::build_sphere_planes(real_t p_radius, int p_lats, int p_lons, Vector3::Axis p_axis) {
+Vector<Plane> Geometry3D::build_sphere_planes(real_t p_radius, int p_lats, int p_lons, Vector3::Axis p_axis) {
Vector<Plane> planes;
Vector3 axis;
@@ -879,7 +826,7 @@ Vector<Plane> Geometry::build_sphere_planes(real_t p_radius, int p_lats, int p_l
return planes;
}
-Vector<Plane> Geometry::build_capsule_planes(real_t p_radius, real_t p_height, int p_sides, int p_lats, Vector3::Axis p_axis) {
+Vector<Plane> Geometry3D::build_capsule_planes(real_t p_radius, real_t p_height, int p_sides, int p_lats, Vector3::Axis p_axis) {
Vector<Plane> planes;
Vector3 axis;
@@ -908,252 +855,7 @@ Vector<Plane> Geometry::build_capsule_planes(real_t p_radius, real_t p_height, i
return planes;
}
-struct _AtlasWorkRect {
- Size2i s;
- Point2i p;
- int idx;
- _FORCE_INLINE_ bool operator<(const _AtlasWorkRect &p_r) const { return s.width > p_r.s.width; };
-};
-
-struct _AtlasWorkRectResult {
- Vector<_AtlasWorkRect> result;
- int max_w;
- int max_h;
-};
-
-void Geometry::make_atlas(const Vector<Size2i> &p_rects, Vector<Point2i> &r_result, Size2i &r_size) {
- // Super simple, almost brute force scanline stacking fitter.
- // It's pretty basic for now, but it tries to make sure that the aspect ratio of the
- // resulting atlas is somehow square. This is necessary because video cards have limits.
- // On texture size (usually 2048 or 4096), so the more square a texture, the more chances.
- // It will work in every hardware.
- // For example, it will prioritize a 1024x1024 atlas (works everywhere) instead of a
- // 256x8192 atlas (won't work anywhere).
-
- ERR_FAIL_COND(p_rects.size() == 0);
-
- Vector<_AtlasWorkRect> wrects;
- wrects.resize(p_rects.size());
- for (int i = 0; i < p_rects.size(); i++) {
- wrects.write[i].s = p_rects[i];
- wrects.write[i].idx = i;
- }
- wrects.sort();
- int widest = wrects[0].s.width;
-
- Vector<_AtlasWorkRectResult> results;
-
- for (int i = 0; i <= 12; i++) {
- int w = 1 << i;
- int max_h = 0;
- int max_w = 0;
- if (w < widest) {
- continue;
- }
-
- Vector<int> hmax;
- hmax.resize(w);
- for (int j = 0; j < w; j++) {
- hmax.write[j] = 0;
- }
-
- // Place them.
- int ofs = 0;
- int limit_h = 0;
- for (int j = 0; j < wrects.size(); j++) {
- if (ofs + wrects[j].s.width > w) {
- ofs = 0;
- }
-
- int from_y = 0;
- for (int k = 0; k < wrects[j].s.width; k++) {
- if (hmax[ofs + k] > from_y) {
- from_y = hmax[ofs + k];
- }
- }
-
- wrects.write[j].p.x = ofs;
- wrects.write[j].p.y = from_y;
- int end_h = from_y + wrects[j].s.height;
- int end_w = ofs + wrects[j].s.width;
- if (ofs == 0) {
- limit_h = end_h;
- }
-
- for (int k = 0; k < wrects[j].s.width; k++) {
- hmax.write[ofs + k] = end_h;
- }
-
- if (end_h > max_h) {
- max_h = end_h;
- }
-
- if (end_w > max_w) {
- max_w = end_w;
- }
-
- if (ofs == 0 || end_h > limit_h) { // While h limit not reached, keep stacking.
- ofs += wrects[j].s.width;
- }
- }
-
- _AtlasWorkRectResult result;
- result.result = wrects;
- result.max_h = max_h;
- result.max_w = max_w;
- results.push_back(result);
- }
-
- // Find the result with the best aspect ratio.
-
- int best = -1;
- real_t best_aspect = 1e20;
-
- for (int i = 0; i < results.size(); i++) {
- real_t h = next_power_of_2(results[i].max_h);
- real_t w = next_power_of_2(results[i].max_w);
- real_t aspect = h > w ? h / w : w / h;
- if (aspect < best_aspect) {
- best = i;
- best_aspect = aspect;
- }
- }
-
- r_result.resize(p_rects.size());
-
- for (int i = 0; i < p_rects.size(); i++) {
- r_result.write[results[best].result[i].idx] = results[best].result[i].p;
- }
-
- r_size = Size2(results[best].max_w, results[best].max_h);
-}
-
-Vector<Vector<Point2>> Geometry::_polypaths_do_operation(PolyBooleanOperation p_op, const Vector<Point2> &p_polypath_a, const Vector<Point2> &p_polypath_b, bool is_a_open) {
- using namespace ClipperLib;
-
- ClipType op = ctUnion;
-
- switch (p_op) {
- case OPERATION_UNION:
- op = ctUnion;
- break;
- case OPERATION_DIFFERENCE:
- op = ctDifference;
- break;
- case OPERATION_INTERSECTION:
- op = ctIntersection;
- break;
- case OPERATION_XOR:
- op = ctXor;
- break;
- }
- Path path_a, path_b;
-
- // Need to scale points (Clipper's requirement for robust computation).
- for (int i = 0; i != p_polypath_a.size(); ++i) {
- path_a << IntPoint(p_polypath_a[i].x * SCALE_FACTOR, p_polypath_a[i].y * SCALE_FACTOR);
- }
- for (int i = 0; i != p_polypath_b.size(); ++i) {
- path_b << IntPoint(p_polypath_b[i].x * SCALE_FACTOR, p_polypath_b[i].y * SCALE_FACTOR);
- }
- Clipper clp;
- clp.AddPath(path_a, ptSubject, !is_a_open); // Forward compatible with Clipper 10.0.0.
- clp.AddPath(path_b, ptClip, true); // Polylines cannot be set as clip.
-
- Paths paths;
-
- if (is_a_open) {
- PolyTree tree; // Needed to populate polylines.
- clp.Execute(op, tree);
- OpenPathsFromPolyTree(tree, paths);
- } else {
- clp.Execute(op, paths); // Works on closed polygons only.
- }
- // Have to scale points down now.
- Vector<Vector<Point2>> polypaths;
-
- for (Paths::size_type i = 0; i < paths.size(); ++i) {
- Vector<Vector2> polypath;
-
- const Path &scaled_path = paths[i];
-
- for (Paths::size_type j = 0; j < scaled_path.size(); ++j) {
- polypath.push_back(Point2(
- static_cast<real_t>(scaled_path[j].X) / SCALE_FACTOR,
- static_cast<real_t>(scaled_path[j].Y) / SCALE_FACTOR));
- }
- polypaths.push_back(polypath);
- }
- return polypaths;
-}
-
-Vector<Vector<Point2>> Geometry::_polypath_offset(const Vector<Point2> &p_polypath, real_t p_delta, PolyJoinType p_join_type, PolyEndType p_end_type) {
- using namespace ClipperLib;
-
- JoinType jt = jtSquare;
-
- switch (p_join_type) {
- case JOIN_SQUARE:
- jt = jtSquare;
- break;
- case JOIN_ROUND:
- jt = jtRound;
- break;
- case JOIN_MITER:
- jt = jtMiter;
- break;
- }
-
- EndType et = etClosedPolygon;
-
- switch (p_end_type) {
- case END_POLYGON:
- et = etClosedPolygon;
- break;
- case END_JOINED:
- et = etClosedLine;
- break;
- case END_BUTT:
- et = etOpenButt;
- break;
- case END_SQUARE:
- et = etOpenSquare;
- break;
- case END_ROUND:
- et = etOpenRound;
- break;
- }
- ClipperOffset co(2.0, 0.25 * SCALE_FACTOR); // Defaults from ClipperOffset.
- Path path;
-
- // Need to scale points (Clipper's requirement for robust computation).
- for (int i = 0; i != p_polypath.size(); ++i) {
- path << IntPoint(p_polypath[i].x * SCALE_FACTOR, p_polypath[i].y * SCALE_FACTOR);
- }
- co.AddPath(path, jt, et);
-
- Paths paths;
- co.Execute(paths, p_delta * SCALE_FACTOR); // Inflate/deflate.
-
- // Have to scale points down now.
- Vector<Vector<Point2>> polypaths;
-
- for (Paths::size_type i = 0; i < paths.size(); ++i) {
- Vector<Vector2> polypath;
-
- const Path &scaled_path = paths[i];
-
- for (Paths::size_type j = 0; j < scaled_path.size(); ++j) {
- polypath.push_back(Point2(
- static_cast<real_t>(scaled_path[j].X) / SCALE_FACTOR,
- static_cast<real_t>(scaled_path[j].Y) / SCALE_FACTOR));
- }
- polypaths.push_back(polypath);
- }
- return polypaths;
-}
-
-Vector<Vector3> Geometry::compute_convex_mesh_points(const Plane *p_planes, int p_plane_count) {
+Vector<Vector3> Geometry3D::compute_convex_mesh_points(const Plane *p_planes, int p_plane_count) {
Vector<Vector3> points;
// Iterate through every unique combination of any three planes.
@@ -1189,73 +891,6 @@ Vector<Vector3> Geometry::compute_convex_mesh_points(const Plane *p_planes, int
return points;
}
-Vector<Point2i> Geometry::pack_rects(const Vector<Size2i> &p_sizes, const Size2i &p_atlas_size) {
- Vector<stbrp_node> nodes;
- nodes.resize(p_atlas_size.width);
-
- stbrp_context context;
- stbrp_init_target(&context, p_atlas_size.width, p_atlas_size.height, nodes.ptrw(), p_atlas_size.width);
-
- Vector<stbrp_rect> rects;
- rects.resize(p_sizes.size());
-
- for (int i = 0; i < p_sizes.size(); i++) {
- rects.write[i].id = 0;
- rects.write[i].w = p_sizes[i].width;
- rects.write[i].h = p_sizes[i].height;
- rects.write[i].x = 0;
- rects.write[i].y = 0;
- rects.write[i].was_packed = 0;
- }
-
- int res = stbrp_pack_rects(&context, rects.ptrw(), rects.size());
- if (res == 0) { //pack failed
- return Vector<Point2i>();
- }
-
- Vector<Point2i> ret;
- ret.resize(p_sizes.size());
-
- for (int i = 0; i < p_sizes.size(); i++) {
- Point2i r(rects[i].x, rects[i].y);
- ret.write[i] = r;
- }
-
- return ret;
-}
-
-Vector<Vector3i> Geometry::partial_pack_rects(const Vector<Vector2i> &p_sizes, const Size2i &p_atlas_size) {
- Vector<stbrp_node> nodes;
- nodes.resize(p_atlas_size.width);
- zeromem(nodes.ptrw(), sizeof(stbrp_node) * nodes.size());
-
- stbrp_context context;
- stbrp_init_target(&context, p_atlas_size.width, p_atlas_size.height, nodes.ptrw(), p_atlas_size.width);
-
- Vector<stbrp_rect> rects;
- rects.resize(p_sizes.size());
-
- for (int i = 0; i < p_sizes.size(); i++) {
- rects.write[i].id = i;
- rects.write[i].w = p_sizes[i].width;
- rects.write[i].h = p_sizes[i].height;
- rects.write[i].x = 0;
- rects.write[i].y = 0;
- rects.write[i].was_packed = 0;
- }
-
- stbrp_pack_rects(&context, rects.ptrw(), rects.size());
-
- Vector<Vector3i> ret;
- ret.resize(p_sizes.size());
-
- for (int i = 0; i < p_sizes.size(); i++) {
- ret.write[rects[i].id] = Vector3i(rects[i].x, rects[i].y, rects[i].was_packed != 0 ? 1 : 0);
- }
-
- return ret;
-}
-
#define square(m_s) ((m_s) * (m_s))
#define INF 1e20
@@ -1297,7 +932,7 @@ static void edt(float *f, int stride, int n) {
#undef square
-Vector<uint32_t> Geometry::generate_edf(const Vector<bool> &p_voxels, const Vector3i &p_size, bool p_negative) {
+Vector<uint32_t> Geometry3D::generate_edf(const Vector<bool> &p_voxels, const Vector3i &p_size, bool p_negative) {
uint32_t float_count = p_size.x * p_size.y * p_size.z;
ERR_FAIL_COND_V((uint32_t)p_voxels.size() != float_count, Vector<uint32_t>());
@@ -1358,10 +993,12 @@ Vector<uint32_t> Geometry::generate_edf(const Vector<bool> &p_voxels, const Vect
}
}
+ memdelete_arr(work_memory);
+
return ret;
}
-Vector<int8_t> Geometry::generate_sdf8(const Vector<uint32_t> &p_positive, const Vector<uint32_t> &p_negative) {
+Vector<int8_t> Geometry3D::generate_sdf8(const Vector<uint32_t> &p_positive, const Vector<uint32_t> &p_negative) {
ERR_FAIL_COND_V(p_positive.size() != p_negative.size(), Vector<int8_t>());
Vector<int8_t> sdf8;
int s = p_positive.size();
diff --git a/core/math/geometry.h b/core/math/geometry_3d.h
index a61bf20c4c..6bbf518141 100644
--- a/core/math/geometry.h
+++ b/core/math/geometry_3d.h
@@ -1,5 +1,5 @@
/*************************************************************************/
-/* geometry.h */
+/* geometry_3d.h */
/*************************************************************************/
/* This file is part of: */
/* GODOT ENGINE */
@@ -28,80 +28,17 @@
/* SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. */
/*************************************************************************/
-#ifndef GEOMETRY_H
-#define GEOMETRY_H
+#ifndef GEOMETRY_3D_H
+#define GEOMETRY_3D_H
-#include "core/math/delaunay_2d.h"
#include "core/math/face3.h"
-#include "core/math/rect2.h"
-#include "core/math/triangulate.h"
-#include "core/math/vector3.h"
#include "core/object.h"
-#include "core/print_string.h"
#include "core/vector.h"
-class Geometry {
- Geometry();
+class Geometry3D {
+ Geometry3D();
public:
- static real_t get_closest_points_between_segments(const Vector2 &p1, const Vector2 &q1, const Vector2 &p2, const Vector2 &q2, Vector2 &c1, Vector2 &c2) {
- Vector2 d1 = q1 - p1; // Direction vector of segment S1.
- Vector2 d2 = q2 - p2; // Direction vector of segment S2.
- Vector2 r = p1 - p2;
- real_t a = d1.dot(d1); // Squared length of segment S1, always nonnegative.
- real_t e = d2.dot(d2); // Squared length of segment S2, always nonnegative.
- real_t f = d2.dot(r);
- real_t s, t;
- // Check if either or both segments degenerate into points.
- if (a <= CMP_EPSILON && e <= CMP_EPSILON) {
- // Both segments degenerate into points.
- c1 = p1;
- c2 = p2;
- return Math::sqrt((c1 - c2).dot(c1 - c2));
- }
- if (a <= CMP_EPSILON) {
- // First segment degenerates into a point.
- s = 0.0;
- t = f / e; // s = 0 => t = (b*s + f) / e = f / e
- t = CLAMP(t, 0.0, 1.0);
- } else {
- real_t c = d1.dot(r);
- if (e <= CMP_EPSILON) {
- // Second segment degenerates into a point.
- t = 0.0;
- s = CLAMP(-c / a, 0.0, 1.0); // t = 0 => s = (b*t - c) / a = -c / a
- } else {
- // The general nondegenerate case starts here.
- real_t b = d1.dot(d2);
- real_t denom = a * e - b * b; // Always nonnegative.
- // If segments not parallel, compute closest point on L1 to L2 and
- // clamp to segment S1. Else pick arbitrary s (here 0).
- if (denom != 0.0) {
- s = CLAMP((b * f - c * e) / denom, 0.0, 1.0);
- } else {
- s = 0.0;
- }
- // Compute point on L2 closest to S1(s) using
- // t = Dot((P1 + D1*s) - P2,D2) / Dot(D2,D2) = (b*s + f) / e
- t = (b * s + f) / e;
-
- //If t in [0,1] done. Else clamp t, recompute s for the new value
- // of t using s = Dot((P2 + D2*t) - P1,D1) / Dot(D1,D1)= (t*b - c) / a
- // and clamp s to [0, 1].
- if (t < 0.0) {
- t = 0.0;
- s = CLAMP(-c / a, 0.0, 1.0);
- } else if (t > 1.0) {
- t = 1.0;
- s = CLAMP((b - c) / a, 0.0, 1.0);
- }
- }
- }
- c1 = p1 + d1 * s;
- c2 = p2 + d2 * t;
- return Math::sqrt((c1 - c2).dot(c1 - c2));
- }
-
static void get_closest_points_between_segments(const Vector3 &p1, const Vector3 &p2, const Vector3 &q1, const Vector3 &q2, Vector3 &c1, Vector3 &c2) {
// Do the function 'd' as defined by pb. I think is is dot product of some sort.
#define d_of(m, n, o, p) ((m.x - n.x) * (o.x - p.x) + (m.y - n.y) * (o.y - p.y) + (m.z - n.z) * (o.z - p.z))
@@ -501,98 +438,6 @@ public:
return p_segment[0] + n * d; // Inside.
}
- static Vector2 get_closest_point_to_segment_2d(const Vector2 &p_point, const Vector2 *p_segment) {
- Vector2 p = p_point - p_segment[0];
- Vector2 n = p_segment[1] - p_segment[0];
- real_t l2 = n.length_squared();
- if (l2 < 1e-20) {
- return p_segment[0]; // Both points are the same, just give any.
- }
-
- real_t d = n.dot(p) / l2;
-
- if (d <= 0.0) {
- return p_segment[0]; // Before first point.
- } else if (d >= 1.0) {
- return p_segment[1]; // After first point.
- } else {
- return p_segment[0] + n * d; // Inside.
- }
- }
-
- static bool is_point_in_triangle(const Vector2 &s, const Vector2 &a, const Vector2 &b, const Vector2 &c) {
- Vector2 an = a - s;
- Vector2 bn = b - s;
- Vector2 cn = c - s;
-
- bool orientation = an.cross(bn) > 0;
-
- if ((bn.cross(cn) > 0) != orientation) {
- return false;
- }
-
- return (cn.cross(an) > 0) == orientation;
- }
-
- static Vector2 get_closest_point_to_segment_uncapped_2d(const Vector2 &p_point, const Vector2 *p_segment) {
- Vector2 p = p_point - p_segment[0];
- Vector2 n = p_segment[1] - p_segment[0];
- real_t l2 = n.length_squared();
- if (l2 < 1e-20) {
- return p_segment[0]; // Both points are the same, just give any.
- }
-
- real_t d = n.dot(p) / l2;
-
- 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::is_zero_approx(denom)) { // 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;
- Vector2 C = p_from_b - p_from_a;
- Vector2 D = p_to_b - p_from_a;
-
- real_t ABlen = B.dot(B);
- if (ABlen <= 0) {
- return false;
- }
- Vector2 Bn = B / ABlen;
- C = Vector2(C.x * Bn.x + C.y * Bn.y, C.y * Bn.x - C.x * Bn.y);
- D = Vector2(D.x * Bn.x + D.y * Bn.y, D.y * Bn.x - D.x * Bn.y);
-
- if ((C.y < 0 && D.y < 0) || (C.y >= 0 && D.y >= 0)) {
- return false;
- }
-
- real_t ABpos = D.x + (C.x - D.x) * D.y / (D.y - C.y);
-
- // Fail if segment C-D crosses line A-B outside of segment A-B.
- if (ABpos < 0 || ABpos > 1.0) {
- return false;
- }
-
- // (4) Apply the discovered position to line A-B in the original coordinate system.
- if (r_result) {
- *r_result = p_from_a + B * ABpos;
- }
-
- return true;
- }
-
static inline bool point_in_projected_triangle(const Vector3 &p_point, const Vector3 &p_v1, const Vector3 &p_v2, const Vector3 &p_v3) {
Vector3 face_n = (p_v1 - p_v3).cross(p_v1 - p_v2);
@@ -629,7 +474,7 @@ public:
/** 2nd) TEST INSIDE TRIANGLE **/
- if (Geometry::point_in_projected_triangle(contact, p_triangle[0], p_triangle[1], p_triangle[2])) {
+ if (Geometry3D::point_in_projected_triangle(contact, p_triangle[0], p_triangle[1], p_triangle[2])) {
r_triangle_contact = contact;
r_sphere_contact = p_sphere_pos - p_normal * p_sphere_radius;
//printf("solved inside triangle\n");
@@ -695,45 +540,6 @@ public:
return false;
}
- static inline bool is_point_in_circle(const Vector2 &p_point, const Vector2 &p_circle_pos, real_t p_circle_radius) {
- return p_point.distance_squared_to(p_circle_pos) <= p_circle_radius * p_circle_radius;
- }
-
- static real_t segment_intersects_circle(const Vector2 &p_from, const Vector2 &p_to, const Vector2 &p_circle_pos, real_t p_circle_radius) {
- Vector2 line_vec = p_to - p_from;
- Vector2 vec_to_line = p_from - p_circle_pos;
-
- // Create a quadratic formula of the form ax^2 + bx + c = 0
- real_t a, b, c;
-
- a = line_vec.dot(line_vec);
- b = 2 * vec_to_line.dot(line_vec);
- c = vec_to_line.dot(vec_to_line) - p_circle_radius * p_circle_radius;
-
- // Solve for t.
- real_t sqrtterm = b * b - 4 * a * c;
-
- // If the term we intend to square root is less than 0 then the answer won't be real,
- // so it definitely won't be t in the range 0 to 1.
- if (sqrtterm < 0) {
- return -1;
- }
-
- // If we can assume that the line segment starts outside the circle (e.g. for continuous time collision detection)
- // then the following can be skipped and we can just return the equivalent of res1.
- sqrtterm = Math::sqrt(sqrtterm);
- real_t res1 = (-b - sqrtterm) / (2 * a);
- real_t res2 = (-b + sqrtterm) / (2 * a);
-
- if (res1 >= 0 && res1 <= 1) {
- return res1;
- }
- if (res2 >= 0 && res2 <= 1) {
- return res2;
- }
- return -1;
- }
-
static inline Vector<Vector3> clip_polygon(const Vector<Vector3> &polygon, const Plane &p_plane) {
enum LocationCache {
LOC_INSIDE = 1,
@@ -806,127 +612,6 @@ public:
return clipped;
}
- enum PolyBooleanOperation {
- OPERATION_UNION,
- OPERATION_DIFFERENCE,
- OPERATION_INTERSECTION,
- OPERATION_XOR
- };
- enum PolyJoinType {
- JOIN_SQUARE,
- JOIN_ROUND,
- JOIN_MITER
- };
- enum PolyEndType {
- END_POLYGON,
- END_JOINED,
- END_BUTT,
- END_SQUARE,
- END_ROUND
- };
-
- static Vector<Vector<Point2>> merge_polygons_2d(const Vector<Point2> &p_polygon_a, const Vector<Point2> &p_polygon_b) {
- return _polypaths_do_operation(OPERATION_UNION, p_polygon_a, p_polygon_b);
- }
-
- static Vector<Vector<Point2>> clip_polygons_2d(const Vector<Point2> &p_polygon_a, const Vector<Point2> &p_polygon_b) {
- return _polypaths_do_operation(OPERATION_DIFFERENCE, p_polygon_a, p_polygon_b);
- }
-
- static Vector<Vector<Point2>> intersect_polygons_2d(const Vector<Point2> &p_polygon_a, const Vector<Point2> &p_polygon_b) {
- return _polypaths_do_operation(OPERATION_INTERSECTION, p_polygon_a, p_polygon_b);
- }
-
- static Vector<Vector<Point2>> exclude_polygons_2d(const Vector<Point2> &p_polygon_a, const Vector<Point2> &p_polygon_b) {
- return _polypaths_do_operation(OPERATION_XOR, p_polygon_a, p_polygon_b);
- }
-
- static Vector<Vector<Point2>> clip_polyline_with_polygon_2d(const Vector<Vector2> &p_polyline, const Vector<Vector2> &p_polygon) {
- return _polypaths_do_operation(OPERATION_DIFFERENCE, p_polyline, p_polygon, true);
- }
-
- static Vector<Vector<Point2>> intersect_polyline_with_polygon_2d(const Vector<Vector2> &p_polyline, const Vector<Vector2> &p_polygon) {
- return _polypaths_do_operation(OPERATION_INTERSECTION, p_polyline, p_polygon, true);
- }
-
- static Vector<Vector<Point2>> offset_polygon_2d(const Vector<Vector2> &p_polygon, real_t p_delta, PolyJoinType p_join_type) {
- return _polypath_offset(p_polygon, p_delta, p_join_type, END_POLYGON);
- }
-
- static Vector<Vector<Point2>> offset_polyline_2d(const Vector<Vector2> &p_polygon, real_t p_delta, PolyJoinType p_join_type, PolyEndType p_end_type) {
- ERR_FAIL_COND_V_MSG(p_end_type == END_POLYGON, Vector<Vector<Point2>>(), "Attempt to offset a polyline like a polygon (use offset_polygon_2d instead).");
-
- return _polypath_offset(p_polygon, p_delta, p_join_type, p_end_type);
- }
-
- static Vector<int> triangulate_delaunay_2d(const Vector<Vector2> &p_points) {
- Vector<Delaunay2D::Triangle> tr = Delaunay2D::triangulate(p_points);
- Vector<int> triangles;
-
- for (int i = 0; i < tr.size(); i++) {
- triangles.push_back(tr[i].points[0]);
- triangles.push_back(tr[i].points[1]);
- triangles.push_back(tr[i].points[2]);
- }
- return triangles;
- }
-
- static Vector<int> triangulate_polygon(const Vector<Vector2> &p_polygon) {
- Vector<int> triangles;
- if (!Triangulate::triangulate(p_polygon, triangles)) {
- return Vector<int>(); //fail
- }
- return triangles;
- }
-
- static bool is_polygon_clockwise(const Vector<Vector2> &p_polygon) {
- int c = p_polygon.size();
- if (c < 3) {
- return false;
- }
- const Vector2 *p = p_polygon.ptr();
- real_t sum = 0;
- for (int i = 0; i < c; i++) {
- const Vector2 &v1 = p[i];
- const Vector2 &v2 = p[(i + 1) % c];
- sum += (v2.x - v1.x) * (v2.y + v1.y);
- }
-
- return sum > 0.0f;
- }
-
- // Alternate implementation that should be faster.
- static bool is_point_in_polygon(const Vector2 &p_point, const Vector<Vector2> &p_polygon) {
- int c = p_polygon.size();
- if (c < 3) {
- return false;
- }
- const Vector2 *p = p_polygon.ptr();
- Vector2 further_away(-1e20, -1e20);
- Vector2 further_away_opposite(1e20, 1e20);
-
- for (int i = 0; i < c; i++) {
- further_away.x = MAX(p[i].x, further_away.x);
- further_away.y = MAX(p[i].y, further_away.y);
- further_away_opposite.x = MIN(p[i].x, further_away_opposite.x);
- further_away_opposite.y = MIN(p[i].y, further_away_opposite.y);
- }
-
- // Make point outside that won't intersect with points in segment from p_point.
- further_away += (further_away - further_away_opposite) * Vector2(1.221313, 1.512312);
-
- int intersections = 0;
- for (int i = 0; i < c; i++) {
- const Vector2 &v1 = p[i];
- const Vector2 &v2 = p[(i + 1) % c];
- if (segment_intersects_segment_2d(v1, v2, p_point, further_away, nullptr)) {
- intersections++;
- }
- }
-
- return (intersections & 1);
- }
-
static Vector<Vector<Face3>> separate_objects(Vector<Face3> p_array);
// Create a "wrap" that encloses the given geometry.
@@ -999,50 +684,12 @@ public:
return ret;
}
}
-
- static real_t vec2_cross(const Point2 &O, const Point2 &A, const Point2 &B) {
- return (real_t)(A.x - O.x) * (B.y - O.y) - (real_t)(A.y - O.y) * (B.x - O.x);
- }
-
- // Returns a list of points on the convex hull in counter-clockwise order.
- // Note: the last point in the returned list is the same as the first one.
- static Vector<Point2> convex_hull_2d(Vector<Point2> P) {
- int n = P.size(), k = 0;
- Vector<Point2> H;
- H.resize(2 * n);
-
- // Sort points lexicographically.
- P.sort();
-
- // Build lower hull.
- for (int i = 0; i < n; ++i) {
- while (k >= 2 && vec2_cross(H[k - 2], H[k - 1], P[i]) <= 0) {
- k--;
- }
- H.write[k++] = P[i];
- }
-
- // Build upper hull.
- for (int i = n - 2, t = k + 1; i >= 0; i--) {
- while (k >= t && vec2_cross(H[k - 2], H[k - 1], P[i]) <= 0) {
- k--;
- }
- H.write[k++] = P[i];
- }
-
- H.resize(k);
- return H;
- }
- static Vector<Vector<Vector2>> decompose_polygon_in_convex(Vector<Point2> polygon);
-
static MeshData build_convex_mesh(const Vector<Plane> &p_planes);
static Vector<Plane> build_sphere_planes(real_t p_radius, int p_lats, int p_lons, Vector3::Axis p_axis = Vector3::AXIS_Z);
static Vector<Plane> build_box_planes(const Vector3 &p_extents);
static Vector<Plane> build_cylinder_planes(real_t p_radius, real_t p_height, int p_sides, Vector3::Axis p_axis = Vector3::AXIS_Z);
static Vector<Plane> build_capsule_planes(real_t p_radius, real_t p_height, int p_sides, int p_lats, Vector3::Axis p_axis = Vector3::AXIS_Z);
- static void make_atlas(const Vector<Size2i> &p_rects, Vector<Point2i> &r_result, Size2i &r_size);
-
static Vector<Vector3> compute_convex_mesh_points(const Plane *p_planes, int p_plane_count);
#define FINDMINMAX(x0, x1, x2, min, max) \
@@ -1255,9 +902,6 @@ public:
return planeBoxOverlap(normal, d, boxhalfsize); /* if true, box and triangle overlaps */
}
- static Vector<Point2i> pack_rects(const Vector<Size2i> &p_sizes, const Size2i &p_atlas_size);
- static Vector<Vector3i> partial_pack_rects(const Vector<Vector2i> &p_sizes, const Size2i &p_atlas_size);
-
static Vector<uint32_t> generate_edf(const Vector<bool> &p_voxels, const Vector3i &p_size, bool p_negative);
static Vector<int8_t> generate_sdf8(const Vector<uint32_t> &p_positive, const Vector<uint32_t> &p_negative);
@@ -1302,9 +946,15 @@ public:
#undef STP
}
-private:
- static Vector<Vector<Point2>> _polypaths_do_operation(PolyBooleanOperation p_op, const Vector<Point2> &p_polypath_a, const Vector<Point2> &p_polypath_b, bool is_a_open = false);
- static Vector<Vector<Point2>> _polypath_offset(const Vector<Point2> &p_polypath, real_t p_delta, PolyJoinType p_join_type, PolyEndType p_end_type);
+ _FORCE_INLINE_ static Vector3 octahedron_map_decode(const Vector2 &p_uv) {
+ // https://twitter.com/Stubbesaurus/status/937994790553227264
+ Vector2 f = p_uv * 2.0 - Vector2(1.0, 1.0);
+ Vector3 n = Vector3(f.x, f.y, 1.0f - Math::abs(f.x) - Math::abs(f.y));
+ float t = CLAMP(-n.z, 0.0, 1.0);
+ n.x += n.x >= 0 ? -t : t;
+ n.y += n.y >= 0 ? -t : t;
+ return n.normalized();
+ }
};
-#endif // GEOMETRY_H
+#endif // GEOMETRY_3D_H
diff --git a/core/math/octree.h b/core/math/octree.h
index c05fc4e9ed..5d9688d442 100644
--- a/core/math/octree.h
+++ b/core/math/octree.h
@@ -34,7 +34,7 @@
#include "core/list.h"
#include "core/map.h"
#include "core/math/aabb.h"
-#include "core/math/geometry.h"
+#include "core/math/geometry_3d.h"
#include "core/math/vector3.h"
#include "core/print_string.h"
#include "core/variant.h"
@@ -1201,7 +1201,7 @@ int Octree<T, use_pairs, AL>::cull_convex(const Vector<Plane> &p_convex, T **p_r
return 0;
}
- Vector<Vector3> convex_points = Geometry::compute_convex_mesh_points(&p_convex[0], p_convex.size());
+ Vector<Vector3> convex_points = Geometry3D::compute_convex_mesh_points(&p_convex[0], p_convex.size());
if (convex_points.size() == 0) {
return 0;
}
diff --git a/core/math/plane.cpp b/core/math/plane.cpp
index df37ceb0e5..4200484c59 100644
--- a/core/math/plane.cpp
+++ b/core/math/plane.cpp
@@ -52,10 +52,6 @@ Plane Plane::normalized() const {
return p;
}
-Vector3 Plane::get_any_point() const {
- return get_normal() * d;
-}
-
Vector3 Plane::get_any_perpendicular_normal() const {
static const Vector3 p1 = Vector3(1, 0, 0);
static const Vector3 p2 = Vector3(0, 1, 0);
diff --git a/core/math/plane.h b/core/math/plane.h
index 9a3e5a485f..70a6111edd 100644
--- a/core/math/plane.h
+++ b/core/math/plane.h
@@ -47,7 +47,6 @@ public:
/* Plane-Point operations */
_FORCE_INLINE_ Vector3 center() const { return normal * d; }
- Vector3 get_any_point() const;
Vector3 get_any_perpendicular_normal() const;
_FORCE_INLINE_ bool is_point_over(const Vector3 &p_point) const; ///< Point is over plane
diff --git a/core/math/quick_hull.cpp b/core/math/quick_hull.cpp
index fe16904448..8ba1ba9286 100644
--- a/core/math/quick_hull.cpp
+++ b/core/math/quick_hull.cpp
@@ -34,7 +34,7 @@
uint32_t QuickHull::debug_stop_after = 0xFFFFFFFF;
-Error QuickHull::build(const Vector<Vector3> &p_points, Geometry::MeshData &r_mesh) {
+Error QuickHull::build(const Vector<Vector3> &p_points, Geometry3D::MeshData &r_mesh) {
/* CREATE AABB VOLUME */
AABB aabb;
@@ -334,17 +334,17 @@ Error QuickHull::build(const Vector<Vector3> &p_points, Geometry::MeshData &r_me
//make a map of edges again
Map<Edge, RetFaceConnect> ret_edges;
- List<Geometry::MeshData::Face> ret_faces;
+ List<Geometry3D::MeshData::Face> ret_faces;
for (List<Face>::Element *E = faces.front(); E; E = E->next()) {
- Geometry::MeshData::Face f;
+ Geometry3D::MeshData::Face f;
f.plane = E->get().plane;
for (int i = 0; i < 3; i++) {
f.indices.push_back(E->get().vertices[i]);
}
- List<Geometry::MeshData::Face>::Element *F = ret_faces.push_back(f);
+ List<Geometry3D::MeshData::Face>::Element *F = ret_faces.push_back(f);
for (int i = 0; i < 3; i++) {
uint32_t a = E->get().vertices[i];
@@ -366,8 +366,8 @@ Error QuickHull::build(const Vector<Vector3> &p_points, Geometry::MeshData &r_me
//fill faces
- for (List<Geometry::MeshData::Face>::Element *E = ret_faces.front(); E; E = E->next()) {
- Geometry::MeshData::Face &f = E->get();
+ for (List<Geometry3D::MeshData::Face>::Element *E = ret_faces.front(); E; E = E->next()) {
+ Geometry3D::MeshData::Face &f = E->get();
for (int i = 0; i < f.indices.size(); i++) {
int a = E->get().indices[i];
@@ -377,7 +377,7 @@ Error QuickHull::build(const Vector<Vector3> &p_points, Geometry::MeshData &r_me
Map<Edge, RetFaceConnect>::Element *F = ret_edges.find(e);
ERR_CONTINUE(!F);
- List<Geometry::MeshData::Face>::Element *O = F->get().left == E ? F->get().right : F->get().left;
+ List<Geometry3D::MeshData::Face>::Element *O = F->get().left == E ? F->get().right : F->get().left;
ERR_CONTINUE(O == E);
ERR_CONTINUE(O == nullptr);
@@ -439,13 +439,13 @@ Error QuickHull::build(const Vector<Vector3> &p_points, Geometry::MeshData &r_me
r_mesh.faces.resize(ret_faces.size());
int idx = 0;
- for (List<Geometry::MeshData::Face>::Element *E = ret_faces.front(); E; E = E->next()) {
+ for (List<Geometry3D::MeshData::Face>::Element *E = ret_faces.front(); E; E = E->next()) {
r_mesh.faces.write[idx++] = E->get();
}
r_mesh.edges.resize(ret_edges.size());
idx = 0;
for (Map<Edge, RetFaceConnect>::Element *E = ret_edges.front(); E; E = E->next()) {
- Geometry::MeshData::Edge e;
+ Geometry3D::MeshData::Edge e;
e.a = E->key().vertices[0];
e.b = E->key().vertices[1];
r_mesh.edges.write[idx++] = e;
diff --git a/core/math/quick_hull.h b/core/math/quick_hull.h
index 29f709febe..cac8e58d23 100644
--- a/core/math/quick_hull.h
+++ b/core/math/quick_hull.h
@@ -33,7 +33,7 @@
#include "core/list.h"
#include "core/math/aabb.h"
-#include "core/math/geometry.h"
+#include "core/math/geometry_3d.h"
#include "core/set.h"
class QuickHull {
@@ -74,13 +74,13 @@ private:
FaceConnect() {}
};
struct RetFaceConnect {
- List<Geometry::MeshData::Face>::Element *left, *right = nullptr;
+ List<Geometry3D::MeshData::Face>::Element *left, *right = nullptr;
RetFaceConnect() {}
};
public:
static uint32_t debug_stop_after;
- static Error build(const Vector<Vector3> &p_points, Geometry::MeshData &r_mesh);
+ static Error build(const Vector<Vector3> &p_points, Geometry3D::MeshData &r_mesh);
};
#endif // QUICK_HULL_H
diff --git a/core/math/rect2.h b/core/math/rect2.h
index 1b86dbd49a..14393325ec 100644
--- a/core/math/rect2.h
+++ b/core/math/rect2.h
@@ -156,7 +156,7 @@ struct Rect2 {
new_rect.size = new_rect.size - new_rect.position; //make relative again
return new_rect;
- };
+ }
inline bool has_point(const Point2 &p_point) const {
if (p_point.x < position.x) {
return false;
@@ -323,7 +323,7 @@ struct Rect2i {
new_rect.size = new_rect.size - new_rect.position; //make relative again
return new_rect;
- };
+ }
bool has_point(const Point2 &p_point) const {
if (p_point.x < position.x) {
return false;
diff --git a/core/math/transform_2d.cpp b/core/math/transform_2d.cpp
index dee1b3b23e..180aeaa0af 100644
--- a/core/math/transform_2d.cpp
+++ b/core/math/transform_2d.cpp
@@ -78,12 +78,7 @@ void Transform2D::set_skew(float p_angle) {
}
real_t Transform2D::get_rotation() const {
- real_t det = basis_determinant();
- Transform2D m = orthonormalized();
- if (det < 0) {
- m.scale_basis(Size2(1, -1)); // convention to separate rotation and reflection for 2D is to absorb a flip along y into scaling.
- }
- return Math::atan2(m[0].y, m[0].x);
+ return Math::atan2(elements[0].y, elements[0].x);
}
void Transform2D::set_rotation(real_t p_rot) {
diff --git a/core/math/triangulate.cpp b/core/math/triangulate.cpp
index 7fab36ff50..12bd384c6a 100644
--- a/core/math/triangulate.cpp
+++ b/core/math/triangulate.cpp
@@ -79,7 +79,7 @@ bool Triangulate::is_inside_triangle(real_t Ax, real_t Ay,
} 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 relaxed) {
int p;
diff --git a/core/math/vector2.cpp b/core/math/vector2.cpp
index 7f264ce119..233421e070 100644
--- a/core/math/vector2.cpp
+++ b/core/math/vector2.cpp
@@ -209,28 +209,29 @@ void Vector2i::operator-=(const Vector2i &p_v) {
Vector2i Vector2i::operator*(const Vector2i &p_v1) const {
return Vector2i(x * p_v1.x, y * p_v1.y);
-};
+}
Vector2i Vector2i::operator*(const int &rvalue) const {
return Vector2i(x * rvalue, y * rvalue);
-};
+}
+
void Vector2i::operator*=(const int &rvalue) {
x *= rvalue;
y *= rvalue;
-};
+}
Vector2i Vector2i::operator/(const Vector2i &p_v1) const {
return Vector2i(x / p_v1.x, y / p_v1.y);
-};
+}
Vector2i Vector2i::operator/(const int &rvalue) const {
return Vector2i(x / rvalue, y / rvalue);
-};
+}
void Vector2i::operator/=(const int &rvalue) {
x /= rvalue;
y /= rvalue;
-};
+}
Vector2i Vector2i::operator-() const {
return Vector2i(-x, -y);
diff --git a/core/math/vector2.h b/core/math/vector2.h
index e5774f1d55..8a08d3bf64 100644
--- a/core/math/vector2.h
+++ b/core/math/vector2.h
@@ -174,28 +174,29 @@ _FORCE_INLINE_ void Vector2::operator-=(const Vector2 &p_v) {
_FORCE_INLINE_ Vector2 Vector2::operator*(const Vector2 &p_v1) const {
return Vector2(x * p_v1.x, y * p_v1.y);
-};
+}
_FORCE_INLINE_ Vector2 Vector2::operator*(const real_t &rvalue) const {
return Vector2(x * rvalue, y * rvalue);
-};
+}
+
_FORCE_INLINE_ void Vector2::operator*=(const real_t &rvalue) {
x *= rvalue;
y *= rvalue;
-};
+}
_FORCE_INLINE_ Vector2 Vector2::operator/(const Vector2 &p_v1) const {
return Vector2(x / p_v1.x, y / p_v1.y);
-};
+}
_FORCE_INLINE_ Vector2 Vector2::operator/(const real_t &rvalue) const {
return Vector2(x / rvalue, y / rvalue);
-};
+}
_FORCE_INLINE_ void Vector2::operator/=(const real_t &rvalue) {
x /= rvalue;
y /= rvalue;
-};
+}
_FORCE_INLINE_ Vector2 Vector2::operator-() const {
return Vector2(-x, -y);
generated by cgit v1.2.3 (git 2.25.1) at 2025-02-13 14:04:43 +0000