diff options
Diffstat (limited to 'core/math')
30 files changed, 1127 insertions, 185 deletions
diff --git a/core/math/a_star_grid_2d.cpp b/core/math/a_star_grid_2d.cpp new file mode 100644 index 0000000000..ad67cfa852 --- /dev/null +++ b/core/math/a_star_grid_2d.cpp @@ -0,0 +1,589 @@ +/*************************************************************************/ +/* a_star_grid_2d.cpp */ +/*************************************************************************/ +/* This file is part of: */ +/* GODOT ENGINE */ +/* https://godotengine.org */ +/*************************************************************************/ +/* Copyright (c) 2007-2022 Juan Linietsky, Ariel Manzur. */ +/* Copyright (c) 2014-2022 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 "a_star_grid_2d.h" + +static real_t heuristic_euclidian(const Vector2i &p_from, const Vector2i &p_to) { + real_t dx = (real_t)ABS(p_to.x - p_from.x); + real_t dy = (real_t)ABS(p_to.y - p_from.y); + return (real_t)Math::sqrt(dx * dx + dy * dy); +} + +static real_t heuristic_manhattan(const Vector2i &p_from, const Vector2i &p_to) { + real_t dx = (real_t)ABS(p_to.x - p_from.x); + real_t dy = (real_t)ABS(p_to.y - p_from.y); + return dx + dy; +} + +static real_t heuristic_octile(const Vector2i &p_from, const Vector2i &p_to) { + real_t dx = (real_t)ABS(p_to.x - p_from.x); + real_t dy = (real_t)ABS(p_to.y - p_from.y); + real_t F = Math_SQRT2 - 1; + return (dx < dy) ? F * dx + dy : F * dy + dx; +} + +static real_t heuristic_chebyshev(const Vector2i &p_from, const Vector2i &p_to) { + real_t dx = (real_t)ABS(p_to.x - p_from.x); + real_t dy = (real_t)ABS(p_to.y - p_from.y); + return MAX(dx, dy); +} + +static real_t (*heuristics[AStarGrid2D::HEURISTIC_MAX])(const Vector2i &, const Vector2i &) = { heuristic_euclidian, heuristic_manhattan, heuristic_octile, heuristic_chebyshev }; + +void AStarGrid2D::set_size(const Size2i &p_size) { + ERR_FAIL_COND(p_size.x < 0 || p_size.y < 0); + if (p_size != size) { + size = p_size; + dirty = true; + } +} + +Size2i AStarGrid2D::get_size() const { + return size; +} + +void AStarGrid2D::set_offset(const Vector2 &p_offset) { + if (!offset.is_equal_approx(p_offset)) { + offset = p_offset; + dirty = true; + } +} + +Vector2 AStarGrid2D::get_offset() const { + return offset; +} + +void AStarGrid2D::set_cell_size(const Size2 &p_cell_size) { + if (!cell_size.is_equal_approx(p_cell_size)) { + cell_size = p_cell_size; + dirty = true; + } +} + +Size2 AStarGrid2D::get_cell_size() const { + return cell_size; +} + +void AStarGrid2D::update() { + points.clear(); + for (int64_t y = 0; y < size.y; y++) { + LocalVector<Point> line; + for (int64_t x = 0; x < size.x; x++) { + line.push_back(Point(Vector2i(x, y), offset + Vector2(x, y) * cell_size)); + } + points.push_back(line); + } + dirty = false; +} + +bool AStarGrid2D::is_in_bounds(int p_x, int p_y) const { + return p_x >= 0 && p_x < size.width && p_y >= 0 && p_y < size.height; +} + +bool AStarGrid2D::is_in_boundsv(const Vector2i &p_id) const { + return p_id.x >= 0 && p_id.x < size.width && p_id.y >= 0 && p_id.y < size.height; +} + +bool AStarGrid2D::is_dirty() const { + return dirty; +} + +void AStarGrid2D::set_jumping_enabled(bool p_enabled) { + jumping_enabled = p_enabled; +} + +bool AStarGrid2D::is_jumping_enabled() const { + return jumping_enabled; +} + +void AStarGrid2D::set_diagonal_mode(DiagonalMode p_diagonal_mode) { + ERR_FAIL_INDEX((int)p_diagonal_mode, (int)DIAGONAL_MODE_MAX); + diagonal_mode = p_diagonal_mode; +} + +AStarGrid2D::DiagonalMode AStarGrid2D::get_diagonal_mode() const { + return diagonal_mode; +} + +void AStarGrid2D::set_default_heuristic(Heuristic p_heuristic) { + ERR_FAIL_INDEX((int)p_heuristic, (int)HEURISTIC_MAX); + default_heuristic = p_heuristic; +} + +AStarGrid2D::Heuristic AStarGrid2D::get_default_heuristic() const { + return default_heuristic; +} + +void AStarGrid2D::set_point_solid(const Vector2i &p_id, bool p_solid) { + ERR_FAIL_COND_MSG(dirty, "Grid is not initialized. Call the update method."); + ERR_FAIL_COND_MSG(!is_in_boundsv(p_id), vformat("Can't set if point is disabled. Point out of bounds (%s/%s, %s/%s).", p_id.x, size.width, p_id.y, size.height)); + points[p_id.y][p_id.x].solid = p_solid; +} + +bool AStarGrid2D::is_point_solid(const Vector2i &p_id) const { + ERR_FAIL_COND_V_MSG(dirty, false, "Grid is not initialized. Call the update method."); + ERR_FAIL_COND_V_MSG(!is_in_boundsv(p_id), false, vformat("Can't get if point is disabled. Point out of bounds (%s/%s, %s/%s).", p_id.x, size.width, p_id.y, size.height)); + return points[p_id.y][p_id.x].solid; +} + +AStarGrid2D::Point *AStarGrid2D::_jump(Point *p_from, Point *p_to) { + if (!p_to || p_to->solid) { + return nullptr; + } + if (p_to == end) { + return p_to; + } + + int64_t from_x = p_from->id.x; + int64_t from_y = p_from->id.y; + + int64_t to_x = p_to->id.x; + int64_t to_y = p_to->id.y; + + int64_t dx = to_x - from_x; + int64_t dy = to_y - from_y; + + if (diagonal_mode == DIAGONAL_MODE_ALWAYS || diagonal_mode == DIAGONAL_MODE_AT_LEAST_ONE_WALKABLE) { + if (dx != 0 && dy != 0) { + if ((_is_walkable(to_x - dx, to_y + dy) && !_is_walkable(to_x - dx, to_y)) || (_is_walkable(to_x + dx, to_y - dy) && !_is_walkable(to_x, to_y - dy))) { + return p_to; + } + if (_jump(p_to, _get_point(to_x + dx, to_y)) != nullptr) { + return p_to; + } + if (_jump(p_to, _get_point(to_x, to_y + dy)) != nullptr) { + return p_to; + } + } else { + if (dx != 0) { + if ((_is_walkable(to_x + dx, to_y + 1) && !_is_walkable(to_x, to_y + 1)) || (_is_walkable(to_x + dx, to_y - 1) && !_is_walkable(to_x, to_y - 1))) { + return p_to; + } + } else { + if ((_is_walkable(to_x + 1, to_y + dy) && !_is_walkable(to_x + 1, to_y)) || (_is_walkable(to_x - 1, to_y + dy) && !_is_walkable(to_x - 1, to_y))) { + return p_to; + } + } + } + if (_is_walkable(to_x + dx, to_y + dy) && (diagonal_mode == DIAGONAL_MODE_ALWAYS || (_is_walkable(to_x + dx, to_y) || _is_walkable(to_x, to_y + dy)))) { + return _jump(p_to, _get_point(to_x + dx, to_y + dy)); + } + } else if (diagonal_mode == DIAGONAL_MODE_ONLY_IF_NO_OBSTACLES) { + if (dx != 0 && dy != 0) { + if ((_is_walkable(to_x + dx, to_y + dy) && !_is_walkable(to_x, to_y + dy)) || !_is_walkable(to_x + dx, to_y)) { + return p_to; + } + if (_jump(p_to, _get_point(to_x + dx, to_y)) != nullptr) { + return p_to; + } + if (_jump(p_to, _get_point(to_x, to_y + dy)) != nullptr) { + return p_to; + } + } else { + if (dx != 0) { + if ((_is_walkable(to_x, to_y + 1) && !_is_walkable(to_x - dx, to_y + 1)) || (_is_walkable(to_x, to_y - 1) && !_is_walkable(to_x - dx, to_y - 1))) { + return p_to; + } + } else { + if ((_is_walkable(to_x + 1, to_y) && !_is_walkable(to_x + 1, to_y - dy)) || (_is_walkable(to_x - 1, to_y) && !_is_walkable(to_x - 1, to_y - dy))) { + return p_to; + } + } + } + if (_is_walkable(to_x + dx, to_y + dy) && _is_walkable(to_x + dx, to_y) && _is_walkable(to_x, to_y + dy)) { + return _jump(p_to, _get_point(to_x + dx, to_y + dy)); + } + } else { // DIAGONAL_MODE_NEVER + if (dx != 0) { + if (!_is_walkable(to_x + dx, to_y)) { + return p_to; + } + if (_jump(p_to, _get_point(to_x, to_y + 1)) != nullptr) { + return p_to; + } + if (_jump(p_to, _get_point(to_x, to_y - 1)) != nullptr) { + return p_to; + } + } else { + if (!_is_walkable(to_x, to_y + dy)) { + return p_to; + } + if (_jump(p_to, _get_point(to_x + 1, to_y)) != nullptr) { + return p_to; + } + if (_jump(p_to, _get_point(to_x - 1, to_y)) != nullptr) { + return p_to; + } + } + if (_is_walkable(to_x + dx, to_y + dy) && _is_walkable(to_x + dx, to_y) && _is_walkable(to_x, to_y + dy)) { + return _jump(p_to, _get_point(to_x + dx, to_y + dy)); + } + } + return nullptr; +} + +void AStarGrid2D::_get_nbors(Point *p_point, List<Point *> &r_nbors) { + bool ts0 = false, td0 = false, + ts1 = false, td1 = false, + ts2 = false, td2 = false, + ts3 = false, td3 = false; + + Point *left = nullptr; + Point *right = nullptr; + Point *top = nullptr; + Point *bottom = nullptr; + + Point *top_left = nullptr; + Point *top_right = nullptr; + Point *bottom_left = nullptr; + Point *bottom_right = nullptr; + + { + bool has_left = false; + bool has_right = false; + + if (p_point->id.x - 1 >= 0) { + left = _get_point_unchecked(p_point->id.x - 1, p_point->id.y); + has_left = true; + } + if (p_point->id.x + 1 < size.width) { + right = _get_point_unchecked(p_point->id.x + 1, p_point->id.y); + has_right = true; + } + if (p_point->id.y - 1 >= 0) { + top = _get_point_unchecked(p_point->id.x, p_point->id.y - 1); + if (has_left) { + top_left = _get_point_unchecked(p_point->id.x - 1, p_point->id.y - 1); + } + if (has_right) { + top_right = _get_point_unchecked(p_point->id.x + 1, p_point->id.y - 1); + } + } + if (p_point->id.y + 1 < size.height) { + bottom = _get_point_unchecked(p_point->id.x, p_point->id.y + 1); + if (has_left) { + bottom_left = _get_point_unchecked(p_point->id.x - 1, p_point->id.y + 1); + } + if (has_right) { + bottom_right = _get_point_unchecked(p_point->id.x + 1, p_point->id.y + 1); + } + } + } + + if (top && !top->solid) { + r_nbors.push_back(top); + ts0 = true; + } + if (right && !right->solid) { + r_nbors.push_back(right); + ts1 = true; + } + if (bottom && !bottom->solid) { + r_nbors.push_back(bottom); + ts2 = true; + } + if (left && !left->solid) { + r_nbors.push_back(left); + ts3 = true; + } + + switch (diagonal_mode) { + case DIAGONAL_MODE_ALWAYS: { + td0 = true; + td1 = true; + td2 = true; + td3 = true; + } break; + case DIAGONAL_MODE_NEVER: { + } break; + case DIAGONAL_MODE_AT_LEAST_ONE_WALKABLE: { + td0 = ts3 || ts0; + td1 = ts0 || ts1; + td2 = ts1 || ts2; + td3 = ts2 || ts3; + } break; + case DIAGONAL_MODE_ONLY_IF_NO_OBSTACLES: { + td0 = ts3 && ts0; + td1 = ts0 && ts1; + td2 = ts1 && ts2; + td3 = ts2 && ts3; + } break; + default: + break; + } + + if (td0 && (top_left && !top_left->solid)) { + r_nbors.push_back(top_left); + } + if (td1 && (top_right && !top_right->solid)) { + r_nbors.push_back(top_right); + } + if (td2 && (bottom_right && !bottom_right->solid)) { + r_nbors.push_back(bottom_right); + } + if (td3 && (bottom_left && !bottom_left->solid)) { + r_nbors.push_back(bottom_left); + } +} + +bool AStarGrid2D::_solve(Point *p_begin_point, Point *p_end_point) { + pass++; + + if (p_end_point->solid) { + return false; + } + + bool found_route = false; + + Vector<Point *> open_list; + SortArray<Point *, SortPoints> sorter; + + p_begin_point->g_score = 0; + p_begin_point->f_score = _estimate_cost(p_begin_point->id, p_end_point->id); + open_list.push_back(p_begin_point); + end = p_end_point; + + while (!open_list.is_empty()) { + Point *p = open_list[0]; // The currently processed point. + + if (p == p_end_point) { + found_route = true; + break; + } + + sorter.pop_heap(0, open_list.size(), open_list.ptrw()); // Remove the current point from the open list. + open_list.remove_at(open_list.size() - 1); + p->closed_pass = pass; // Mark the point as closed. + + List<Point *> nbors; + _get_nbors(p, nbors); + for (List<Point *>::Element *E = nbors.front(); E; E = E->next()) { + Point *e = E->get(); // The neighbour point. + if (jumping_enabled) { + e = _jump(p, e); + if (!e || e->closed_pass == pass) { + continue; + } + } else { + if (e->solid || e->closed_pass == pass) { + continue; + } + } + + real_t tentative_g_score = p->g_score + _compute_cost(p->id, e->id); + bool new_point = false; + + if (e->open_pass != pass) { // The point wasn't inside the open list. + e->open_pass = pass; + open_list.push_back(e); + new_point = true; + } else if (tentative_g_score >= e->g_score) { // The new path is worse than the previous. + continue; + } + + e->prev_point = p; + e->g_score = tentative_g_score; + e->f_score = e->g_score + _estimate_cost(e->id, p_end_point->id); + + if (new_point) { // The position of the new points is already known. + sorter.push_heap(0, open_list.size() - 1, 0, e, open_list.ptrw()); + } else { + sorter.push_heap(0, open_list.find(e), 0, e, open_list.ptrw()); + } + } + } + + return found_route; +} + +real_t AStarGrid2D::_estimate_cost(const Vector2i &p_from_id, const Vector2i &p_to_id) { + real_t scost; + if (GDVIRTUAL_CALL(_estimate_cost, p_from_id, p_to_id, scost)) { + return scost; + } + return heuristics[default_heuristic](p_from_id, p_to_id); +} + +real_t AStarGrid2D::_compute_cost(const Vector2i &p_from_id, const Vector2i &p_to_id) { + real_t scost; + if (GDVIRTUAL_CALL(_compute_cost, p_from_id, p_to_id, scost)) { + return scost; + } + return heuristics[default_heuristic](p_from_id, p_to_id); +} + +void AStarGrid2D::clear() { + points.clear(); + size = Vector2i(); +} + +Vector<Vector2> AStarGrid2D::get_point_path(const Vector2i &p_from_id, const Vector2i &p_to_id) { + ERR_FAIL_COND_V_MSG(dirty, Vector<Vector2>(), "Grid is not initialized. Call the update method."); + ERR_FAIL_COND_V_MSG(!is_in_boundsv(p_from_id), Vector<Vector2>(), vformat("Can't get id path. Point out of bounds (%s/%s, %s/%s)", p_from_id.x, size.width, p_from_id.y, size.height)); + ERR_FAIL_COND_V_MSG(!is_in_boundsv(p_to_id), Vector<Vector2>(), vformat("Can't get id path. Point out of bounds (%s/%s, %s/%s)", p_to_id.x, size.width, p_to_id.y, size.height)); + + Point *a = _get_point(p_from_id.x, p_from_id.y); + Point *b = _get_point(p_to_id.x, p_to_id.y); + + if (a == b) { + Vector<Vector2> ret; + ret.push_back(a->pos); + return ret; + } + + Point *begin_point = a; + Point *end_point = b; + + bool found_route = _solve(begin_point, end_point); + if (!found_route) { + return Vector<Vector2>(); + } + + Point *p = end_point; + int64_t pc = 1; + while (p != begin_point) { + pc++; + p = p->prev_point; + } + + Vector<Vector2> path; + path.resize(pc); + + { + Vector2 *w = path.ptrw(); + + p = end_point; + int64_t idx = pc - 1; + while (p != begin_point) { + w[idx--] = p->pos; + p = p->prev_point; + } + + w[0] = p->pos; + } + + return path; +} + +Vector<Vector2> AStarGrid2D::get_id_path(const Vector2i &p_from_id, const Vector2i &p_to_id) { + ERR_FAIL_COND_V_MSG(dirty, Vector<Vector2>(), "Grid is not initialized. Call the update method."); + ERR_FAIL_COND_V_MSG(!is_in_boundsv(p_from_id), Vector<Vector2>(), vformat("Can't get id path. Point out of bounds (%s/%s, %s/%s)", p_from_id.x, size.width, p_from_id.y, size.height)); + ERR_FAIL_COND_V_MSG(!is_in_boundsv(p_to_id), Vector<Vector2>(), vformat("Can't get id path. Point out of bounds (%s/%s, %s/%s)", p_to_id.x, size.width, p_to_id.y, size.height)); + + Point *a = _get_point(p_from_id.x, p_from_id.y); + Point *b = _get_point(p_to_id.x, p_to_id.y); + + if (a == b) { + Vector<Vector2> ret; + ret.push_back(Vector2((float)a->id.x, (float)a->id.y)); + return ret; + } + + Point *begin_point = a; + Point *end_point = b; + + bool found_route = _solve(begin_point, end_point); + if (!found_route) { + return Vector<Vector2>(); + } + + Point *p = end_point; + int64_t pc = 1; + while (p != begin_point) { + pc++; + p = p->prev_point; + } + + Vector<Vector2> path; + path.resize(pc); + + { + Vector2 *w = path.ptrw(); + + p = end_point; + int64_t idx = pc - 1; + while (p != begin_point) { + w[idx--] = Vector2((float)p->id.x, (float)p->id.y); + p = p->prev_point; + } + + w[0] = p->id; + } + + return path; +} + +void AStarGrid2D::_bind_methods() { + ClassDB::bind_method(D_METHOD("set_size", "size"), &AStarGrid2D::set_size); + ClassDB::bind_method(D_METHOD("get_size"), &AStarGrid2D::get_size); + ClassDB::bind_method(D_METHOD("set_offset", "offset"), &AStarGrid2D::set_offset); + ClassDB::bind_method(D_METHOD("get_offset"), &AStarGrid2D::get_offset); + ClassDB::bind_method(D_METHOD("set_cell_size", "cell_size"), &AStarGrid2D::set_cell_size); + ClassDB::bind_method(D_METHOD("get_cell_size"), &AStarGrid2D::get_cell_size); + ClassDB::bind_method(D_METHOD("is_in_bounds", "x", "y"), &AStarGrid2D::is_in_bounds); + ClassDB::bind_method(D_METHOD("is_in_boundsv", "id"), &AStarGrid2D::is_in_boundsv); + ClassDB::bind_method(D_METHOD("is_dirty"), &AStarGrid2D::is_dirty); + ClassDB::bind_method(D_METHOD("update"), &AStarGrid2D::update); + ClassDB::bind_method(D_METHOD("set_jumping_enabled", "enabled"), &AStarGrid2D::set_jumping_enabled); + ClassDB::bind_method(D_METHOD("is_jumping_enabled"), &AStarGrid2D::is_jumping_enabled); + ClassDB::bind_method(D_METHOD("set_diagonal_mode", "mode"), &AStarGrid2D::set_diagonal_mode); + ClassDB::bind_method(D_METHOD("get_diagonal_mode"), &AStarGrid2D::get_diagonal_mode); + ClassDB::bind_method(D_METHOD("set_default_heuristic", "heuristic"), &AStarGrid2D::set_default_heuristic); + ClassDB::bind_method(D_METHOD("get_default_heuristic"), &AStarGrid2D::get_default_heuristic); + ClassDB::bind_method(D_METHOD("set_point_solid", "id", "solid"), &AStarGrid2D::set_point_solid, DEFVAL(true)); + ClassDB::bind_method(D_METHOD("is_point_solid", "id"), &AStarGrid2D::is_point_solid); + ClassDB::bind_method(D_METHOD("clear"), &AStarGrid2D::clear); + + ClassDB::bind_method(D_METHOD("get_point_path", "from_id", "to_id"), &AStarGrid2D::get_point_path); + ClassDB::bind_method(D_METHOD("get_id_path", "from_id", "to_id"), &AStarGrid2D::get_id_path); + + GDVIRTUAL_BIND(_estimate_cost, "from_id", "to_id") + GDVIRTUAL_BIND(_compute_cost, "from_id", "to_id") + + ADD_PROPERTY(PropertyInfo(Variant::VECTOR2I, "size"), "set_size", "get_size"); + ADD_PROPERTY(PropertyInfo(Variant::VECTOR2, "offset"), "set_offset", "get_offset"); + ADD_PROPERTY(PropertyInfo(Variant::VECTOR2, "cell_size"), "set_cell_size", "get_cell_size"); + + ADD_PROPERTY(PropertyInfo(Variant::BOOL, "jumping_enabled"), "set_jumping_enabled", "is_jumping_enabled"); + ADD_PROPERTY(PropertyInfo(Variant::INT, "default_heuristic", PROPERTY_HINT_ENUM, "Euclidean,Manhattan,Octile,Chebyshev,Max"), "set_default_heuristic", "get_default_heuristic"); + ADD_PROPERTY(PropertyInfo(Variant::INT, "diagonal_mode", PROPERTY_HINT_ENUM, "Never,Always,At Least One Walkable,Only If No Obstacles,Max"), "set_diagonal_mode", "get_diagonal_mode"); + + BIND_ENUM_CONSTANT(HEURISTIC_EUCLIDEAN); + BIND_ENUM_CONSTANT(HEURISTIC_MANHATTAN); + BIND_ENUM_CONSTANT(HEURISTIC_OCTILE); + BIND_ENUM_CONSTANT(HEURISTIC_CHEBYSHEV); + BIND_ENUM_CONSTANT(HEURISTIC_MAX); + + BIND_ENUM_CONSTANT(DIAGONAL_MODE_ALWAYS); + BIND_ENUM_CONSTANT(DIAGONAL_MODE_NEVER); + BIND_ENUM_CONSTANT(DIAGONAL_MODE_AT_LEAST_ONE_WALKABLE); + BIND_ENUM_CONSTANT(DIAGONAL_MODE_ONLY_IF_NO_OBSTACLES); + BIND_ENUM_CONSTANT(DIAGONAL_MODE_MAX); +} diff --git a/core/math/a_star_grid_2d.h b/core/math/a_star_grid_2d.h new file mode 100644 index 0000000000..bf6363aa01 --- /dev/null +++ b/core/math/a_star_grid_2d.h @@ -0,0 +1,178 @@ +/*************************************************************************/ +/* a_star_grid_2d.h */ +/*************************************************************************/ +/* This file is part of: */ +/* GODOT ENGINE */ +/* https://godotengine.org */ +/*************************************************************************/ +/* Copyright (c) 2007-2022 Juan Linietsky, Ariel Manzur. */ +/* Copyright (c) 2014-2022 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 A_STAR_GRID_2D_H +#define A_STAR_GRID_2D_H + +#include "core/object/gdvirtual.gen.inc" +#include "core/object/ref_counted.h" +#include "core/object/script_language.h" +#include "core/templates/list.h" +#include "core/templates/local_vector.h" + +class AStarGrid2D : public RefCounted { + GDCLASS(AStarGrid2D, RefCounted); + +public: + enum DiagonalMode { + DIAGONAL_MODE_ALWAYS, + DIAGONAL_MODE_NEVER, + DIAGONAL_MODE_AT_LEAST_ONE_WALKABLE, + DIAGONAL_MODE_ONLY_IF_NO_OBSTACLES, + DIAGONAL_MODE_MAX, + }; + + enum Heuristic { + HEURISTIC_EUCLIDEAN, + HEURISTIC_MANHATTAN, + HEURISTIC_OCTILE, + HEURISTIC_CHEBYSHEV, + HEURISTIC_MAX, + }; + +private: + Size2i size; + Vector2 offset; + Size2 cell_size = Size2(1, 1); + bool dirty = false; + + bool jumping_enabled = false; + DiagonalMode diagonal_mode = DIAGONAL_MODE_ALWAYS; + Heuristic default_heuristic = HEURISTIC_EUCLIDEAN; + + struct Point { + Vector2i id; + + bool solid = false; + Vector2 pos; + + // Used for pathfinding. + Point *prev_point = nullptr; + real_t g_score = 0; + real_t f_score = 0; + uint64_t open_pass = 0; + uint64_t closed_pass = 0; + + Point() {} + + Point(const Vector2i &p_id, const Vector2 &p_pos) : + id(p_id), pos(p_pos) {} + }; + + struct SortPoints { + _FORCE_INLINE_ bool operator()(const Point *A, const Point *B) const { // Returns true when the Point A is worse than Point B. + if (A->f_score > B->f_score) { + return true; + } else if (A->f_score < B->f_score) { + return false; + } else { + return A->g_score < B->g_score; // If the f_costs are the same then prioritize the points that are further away from the start. + } + } + }; + + LocalVector<LocalVector<Point>> points; + Point *end = nullptr; + + uint64_t pass = 1; + +private: // Internal routines. + _FORCE_INLINE_ bool _is_walkable(int64_t p_x, int64_t p_y) const { + if (p_x >= 0 && p_y >= 0 && p_x < size.width && p_y < size.height) { + return !points[p_y][p_x].solid; + } + return false; + } + + _FORCE_INLINE_ Point *_get_point(int64_t p_x, int64_t p_y) { + if (p_x >= 0 && p_y >= 0 && p_x < size.width && p_y < size.height) { + return &points[p_y][p_x]; + } + return nullptr; + } + + _FORCE_INLINE_ Point *_get_point_unchecked(int64_t p_x, int64_t p_y) { + return &points[p_y][p_x]; + } + + void _get_nbors(Point *p_point, List<Point *> &r_nbors); + Point *_jump(Point *p_from, Point *p_to); + bool _solve(Point *p_begin_point, Point *p_end_point); + +protected: + static void _bind_methods(); + + virtual real_t _estimate_cost(const Vector2i &p_from_id, const Vector2i &p_to_id); + virtual real_t _compute_cost(const Vector2i &p_from_id, const Vector2i &p_to_id); + + GDVIRTUAL2RC(real_t, _estimate_cost, Vector2i, Vector2i) + GDVIRTUAL2RC(real_t, _compute_cost, Vector2i, Vector2i) + +public: + void set_size(const Size2i &p_size); + Size2i get_size() const; + + void set_offset(const Vector2 &p_offset); + Vector2 get_offset() const; + + void set_cell_size(const Size2 &p_cell_size); + Size2 get_cell_size() const; + + void update(); + + int get_width() const; + int get_height() const; + + bool is_in_bounds(int p_x, int p_y) const; + bool is_in_boundsv(const Vector2i &p_id) const; + bool is_dirty() const; + + void set_jumping_enabled(bool p_enabled); + bool is_jumping_enabled() const; + + void set_diagonal_mode(DiagonalMode p_diagonal_mode); + DiagonalMode get_diagonal_mode() const; + + void set_default_heuristic(Heuristic p_heuristic); + Heuristic get_default_heuristic() const; + + void set_point_solid(const Vector2i &p_id, bool p_solid = true); + bool is_point_solid(const Vector2i &p_id) const; + + void clear(); + + Vector<Vector2> get_point_path(const Vector2i &p_from, const Vector2i &p_to); + Vector<Vector2> get_id_path(const Vector2i &p_from, const Vector2i &p_to); +}; + +VARIANT_ENUM_CAST(AStarGrid2D::DiagonalMode); +VARIANT_ENUM_CAST(AStarGrid2D::Heuristic); + +#endif // A_STAR_GRID_2D_H diff --git a/core/math/aabb.h b/core/math/aabb.h index e88ba33531..acf903eeba 100644 --- a/core/math/aabb.h +++ b/core/math/aabb.h @@ -47,12 +47,12 @@ struct _NO_DISCARD_ AABB { Vector3 size; real_t get_volume() const; - _FORCE_INLINE_ bool has_no_volume() const { - return (size.x <= 0 || size.y <= 0 || size.z <= 0); + _FORCE_INLINE_ bool has_volume() const { + return size.x > 0.0f && size.y > 0.0f && size.z > 0.0f; } - _FORCE_INLINE_ bool has_no_surface() const { - return (size.x <= 0 && size.y <= 0 && size.z <= 0); + _FORCE_INLINE_ bool has_surface() const { + return size.x > 0.0f || size.y > 0.0f || size.z > 0.0f; } const Vector3 &get_position() const { return position; } diff --git a/core/math/audio_frame.h b/core/math/audio_frame.h index b3d63c0094..1a80faaa12 100644 --- a/core/math/audio_frame.h +++ b/core/math/audio_frame.h @@ -48,7 +48,7 @@ static inline float undenormalise(volatile float f) { } static const float AUDIO_PEAK_OFFSET = 0.0000000001f; -static const float AUDIO_MIN_PEAK_DB = -200.0f; // linear2db(AUDIO_PEAK_OFFSET) +static const float AUDIO_MIN_PEAK_DB = -200.0f; // linear_to_db(AUDIO_PEAK_OFFSET) struct AudioFrame { //left and right samples diff --git a/core/math/basis.cpp b/core/math/basis.cpp index bc50d0e64c..4b163409ce 100644 --- a/core/math/basis.cpp +++ b/core/math/basis.cpp @@ -754,29 +754,28 @@ void Basis::get_axis_angle(Vector3 &r_axis, real_t &r_angle) const { #ifdef MATH_CHECKS ERR_FAIL_COND(!is_rotation()); #endif -*/ - real_t angle, x, y, z; // variables for result - real_t angle_epsilon = 0.1; // margin to distinguish between 0 and 180 degrees - - if ((Math::abs(rows[1][0] - rows[0][1]) < CMP_EPSILON) && (Math::abs(rows[2][0] - rows[0][2]) < CMP_EPSILON) && (Math::abs(rows[2][1] - rows[1][2]) < CMP_EPSILON)) { - // singularity found - // first check for identity matrix which must have +1 for all terms - // in leading diagonal and zero in other terms - if ((Math::abs(rows[1][0] + rows[0][1]) < angle_epsilon) && (Math::abs(rows[2][0] + rows[0][2]) < angle_epsilon) && (Math::abs(rows[2][1] + rows[1][2]) < angle_epsilon) && (Math::abs(rows[0][0] + rows[1][1] + rows[2][2] - 3) < angle_epsilon)) { - // this singularity is identity matrix so angle = 0 + */ + + // https://www.euclideanspace.com/maths/geometry/rotations/conversions/matrixToAngle/index.htm + real_t x, y, z; // Variables for result. + if (Math::is_zero_approx(rows[0][1] - rows[1][0]) && Math::is_zero_approx(rows[0][2] - rows[2][0]) && Math::is_zero_approx(rows[1][2] - rows[2][1])) { + // Singularity found. + // First check for identity matrix which must have +1 for all terms in leading diagonal and zero in other terms. + if (is_diagonal() && (Math::abs(rows[0][0] + rows[1][1] + rows[2][2] - 3) < 3 * CMP_EPSILON)) { + // This singularity is identity matrix so angle = 0. r_axis = Vector3(0, 1, 0); r_angle = 0; return; } - // otherwise this singularity is angle = 180 - angle = Math_PI; + // Otherwise this singularity is angle = 180. real_t xx = (rows[0][0] + 1) / 2; real_t yy = (rows[1][1] + 1) / 2; real_t zz = (rows[2][2] + 1) / 2; - real_t xy = (rows[1][0] + rows[0][1]) / 4; - real_t xz = (rows[2][0] + rows[0][2]) / 4; - real_t yz = (rows[2][1] + rows[1][2]) / 4; - if ((xx > yy) && (xx > zz)) { // rows[0][0] is the largest diagonal term + real_t xy = (rows[0][1] + rows[1][0]) / 4; + real_t xz = (rows[0][2] + rows[2][0]) / 4; + real_t yz = (rows[1][2] + rows[2][1]) / 4; + + if ((xx > yy) && (xx > zz)) { // rows[0][0] is the largest diagonal term. if (xx < CMP_EPSILON) { x = 0; y = Math_SQRT12; @@ -786,7 +785,7 @@ void Basis::get_axis_angle(Vector3 &r_axis, real_t &r_angle) const { y = xy / x; z = xz / x; } - } else if (yy > zz) { // rows[1][1] is the largest diagonal term + } else if (yy > zz) { // rows[1][1] is the largest diagonal term. if (yy < CMP_EPSILON) { x = Math_SQRT12; y = 0; @@ -796,7 +795,7 @@ void Basis::get_axis_angle(Vector3 &r_axis, real_t &r_angle) const { x = xy / y; z = yz / y; } - } else { // rows[2][2] is the largest diagonal term so base result on this + } else { // rows[2][2] is the largest diagonal term so base result on this. if (zz < CMP_EPSILON) { x = Math_SQRT12; y = Math_SQRT12; @@ -808,22 +807,24 @@ void Basis::get_axis_angle(Vector3 &r_axis, real_t &r_angle) const { } } r_axis = Vector3(x, y, z); - r_angle = angle; + r_angle = Math_PI; return; } - // as we have reached here there are no singularities so we can handle normally - real_t s = Math::sqrt((rows[1][2] - rows[2][1]) * (rows[1][2] - rows[2][1]) + (rows[2][0] - rows[0][2]) * (rows[2][0] - rows[0][2]) + (rows[0][1] - rows[1][0]) * (rows[0][1] - rows[1][0])); // s=|axis||sin(angle)|, used to normalise + // As we have reached here there are no singularities so we can handle normally. + double s = Math::sqrt((rows[2][1] - rows[1][2]) * (rows[2][1] - rows[1][2]) + (rows[0][2] - rows[2][0]) * (rows[0][2] - rows[2][0]) + (rows[1][0] - rows[0][1]) * (rows[1][0] - rows[0][1])); // Used to normalise. - angle = Math::acos((rows[0][0] + rows[1][1] + rows[2][2] - 1) / 2); - if (angle < 0) { - s = -s; + if (Math::abs(s) < CMP_EPSILON) { + // Prevent divide by zero, should not happen if matrix is orthogonal and should be caught by singularity test above. + s = 1; } + x = (rows[2][1] - rows[1][2]) / s; y = (rows[0][2] - rows[2][0]) / s; z = (rows[1][0] - rows[0][1]) / s; r_axis = Vector3(x, y, z); - r_angle = angle; + // CLAMP to avoid NaN if the value passed to acos is not in [0,1]. + r_angle = Math::acos(CLAMP((rows[0][0] + rows[1][1] + rows[2][2] - 1) / 2, (real_t)0.0, (real_t)1.0)); } void Basis::set_quaternion(const Quaternion &p_quaternion) { @@ -1033,13 +1034,13 @@ void Basis::rotate_sh(real_t *p_values) { Basis Basis::looking_at(const Vector3 &p_target, const Vector3 &p_up) { #ifdef MATH_CHECKS - ERR_FAIL_COND_V_MSG(p_target.is_equal_approx(Vector3()), Basis(), "The target vector can't be zero."); - ERR_FAIL_COND_V_MSG(p_up.is_equal_approx(Vector3()), Basis(), "The up vector can't be zero."); + ERR_FAIL_COND_V_MSG(p_target.is_zero_approx(), Basis(), "The target vector can't be zero."); + ERR_FAIL_COND_V_MSG(p_up.is_zero_approx(), Basis(), "The up vector can't be zero."); #endif Vector3 v_z = -p_target.normalized(); Vector3 v_x = p_up.cross(v_z); #ifdef MATH_CHECKS - ERR_FAIL_COND_V_MSG(v_x.is_equal_approx(Vector3()), Basis(), "The target vector and up vector can't be parallel to each other."); + ERR_FAIL_COND_V_MSG(v_x.is_zero_approx(), Basis(), "The target vector and up vector can't be parallel to each other."); #endif v_x.normalize(); Vector3 v_y = v_z.cross(v_x); diff --git a/core/math/basis.h b/core/math/basis.h index 2853947ba7..cc2924f5ff 100644 --- a/core/math/basis.h +++ b/core/math/basis.h @@ -238,10 +238,8 @@ struct _NO_DISCARD_ Basis { Basis(const Vector3 &p_axis, real_t p_angle, const Vector3 &p_scale) { set_axis_angle_scale(p_axis, p_angle, p_scale); } static Basis from_scale(const Vector3 &p_scale); - _FORCE_INLINE_ Basis(const Vector3 &row0, const Vector3 &row1, const Vector3 &row2) { - rows[0] = row0; - rows[1] = row1; - rows[2] = row2; + _FORCE_INLINE_ Basis(const Vector3 &p_x_axis, const Vector3 &p_y_axis, const Vector3 &p_z_axis) { + set_columns(p_x_axis, p_y_axis, p_z_axis); } _FORCE_INLINE_ Basis() {} diff --git a/core/math/bvh_split.inc b/core/math/bvh_split.inc index ff07166d4a..180bbfb511 100644 --- a/core/math/bvh_split.inc +++ b/core/math/bvh_split.inc @@ -13,7 +13,7 @@ void _split_inform_references(uint32_t p_node_id) { void _split_leaf_sort_groups_simple(int &num_a, int &num_b, uint16_t *group_a, uint16_t *group_b, const BVHABB_CLASS *temp_bounds, const BVHABB_CLASS full_bound) { // special case for low leaf sizes .. should static compile out - if (MAX_ITEMS < 4) { + if constexpr (MAX_ITEMS < 4) { uint32_t ind = group_a[0]; // add to b @@ -34,7 +34,7 @@ void _split_leaf_sort_groups_simple(int &num_a, int &num_b, uint16_t *group_a, u order[POINT::AXIS_COUNT - 1] = size.max_axis_index(); static_assert(POINT::AXIS_COUNT <= 3, "BVH POINT::AXIS_COUNT has unexpected size"); - if (POINT::AXIS_COUNT == 3) { + if constexpr (POINT::AXIS_COUNT == 3) { order[1] = 3 - (order[0] + order[2]); } diff --git a/core/math/bvh_structs.inc b/core/math/bvh_structs.inc index 58c8f0479a..06f6e5d05d 100644 --- a/core/math/bvh_structs.inc +++ b/core/math/bvh_structs.inc @@ -100,7 +100,11 @@ public: num_items++; return id; } +#ifdef DEV_ENABLED return -1; +#else + ERR_FAIL_V_MSG(0, "BVH request_item error."); +#endif } }; diff --git a/core/math/bvh_tree.h b/core/math/bvh_tree.h index cdb2bb4413..8291394b31 100644 --- a/core/math/bvh_tree.h +++ b/core/math/bvh_tree.h @@ -235,7 +235,7 @@ private: // no need to keep back references for children at the moment - uint32_t sibling_id; // always a node id, as tnode is never a leaf + uint32_t sibling_id = 0; // always a node id, as tnode is never a leaf bool sibling_present = false; // if there are more children, or this is the root node, don't try and delete diff --git a/core/math/convex_hull.h b/core/math/convex_hull.h index bd86fe0eba..cc41a794bd 100644 --- a/core/math/convex_hull.h +++ b/core/math/convex_hull.h @@ -28,6 +28,9 @@ /* SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. */ /*************************************************************************/ +#ifndef CONVEX_HULL_H +#define CONVEX_HULL_H + /* Copyright (c) 2011 Ole Kniemeyer, MAXON, www.maxon.net This software is provided 'as-is', without any express or implied warranty. @@ -40,9 +43,6 @@ subject to the following restrictions: 3. This notice may not be removed or altered from any source distribution. */ -#ifndef CONVEX_HULL_H -#define CONVEX_HULL_H - #include "core/math/geometry_3d.h" #include "core/math/vector3.h" #include "core/templates/local_vector.h" diff --git a/core/math/geometry_3d.cpp b/core/math/geometry_3d.cpp index ec96753c79..9238293b48 100644 --- a/core/math/geometry_3d.cpp +++ b/core/math/geometry_3d.cpp @@ -35,6 +35,111 @@ #include "thirdparty/misc/clipper.hpp" #include "thirdparty/misc/polypartition.h" +void Geometry3D::get_closest_points_between_segments(const Vector3 &p_p0, const Vector3 &p_p1, const Vector3 &p_q0, const Vector3 &p_q1, Vector3 &r_ps, Vector3 &r_qt) { + // Based on David Eberly's Computation of Distance Between Line Segments algorithm. + + Vector3 p = p_p1 - p_p0; + Vector3 q = p_q1 - p_q0; + Vector3 r = p_p0 - p_q0; + + real_t a = p.dot(p); + real_t b = p.dot(q); + real_t c = q.dot(q); + real_t d = p.dot(r); + real_t e = q.dot(r); + + real_t s = 0.0f; + real_t t = 0.0f; + + real_t det = a * c - b * b; + if (det > CMP_EPSILON) { + // Non-parallel segments + real_t bte = b * e; + real_t ctd = c * d; + + if (bte <= ctd) { + // s <= 0.0f + if (e <= 0.0f) { + // t <= 0.0f + s = (-d >= a ? 1 : (-d > 0.0f ? -d / a : 0.0f)); + t = 0.0f; + } else if (e < c) { + // 0.0f < t < 1 + s = 0.0f; + t = e / c; + } else { + // t >= 1 + s = (b - d >= a ? 1 : (b - d > 0.0f ? (b - d) / a : 0.0f)); + t = 1; + } + } else { + // s > 0.0f + s = bte - ctd; + if (s >= det) { + // s >= 1 + if (b + e <= 0.0f) { + // t <= 0.0f + s = (-d <= 0.0f ? 0.0f : (-d < a ? -d / a : 1)); + t = 0.0f; + } else if (b + e < c) { + // 0.0f < t < 1 + s = 1; + t = (b + e) / c; + } else { + // t >= 1 + s = (b - d <= 0.0f ? 0.0f : (b - d < a ? (b - d) / a : 1)); + t = 1; + } + } else { + // 0.0f < s < 1 + real_t ate = a * e; + real_t btd = b * d; + + if (ate <= btd) { + // t <= 0.0f + s = (-d <= 0.0f ? 0.0f : (-d >= a ? 1 : -d / a)); + t = 0.0f; + } else { + // t > 0.0f + t = ate - btd; + if (t >= det) { + // t >= 1 + s = (b - d <= 0.0f ? 0.0f : (b - d >= a ? 1 : (b - d) / a)); + t = 1; + } else { + // 0.0f < t < 1 + s /= det; + t /= det; + } + } + } + } + } else { + // Parallel segments + if (e <= 0.0f) { + s = (-d <= 0.0f ? 0.0f : (-d >= a ? 1 : -d / a)); + t = 0.0f; + } else if (e >= c) { + s = (b - d <= 0.0f ? 0.0f : (b - d >= a ? 1 : (b - d) / a)); + t = 1; + } else { + s = 0.0f; + t = e / c; + } + } + + r_ps = (1 - s) * p_p0 + s * p_p1; + r_qt = (1 - t) * p_q0 + t * p_q1; +} + +real_t Geometry3D::get_closest_distance_between_segments(const Vector3 &p_p0, const Vector3 &p_p1, const Vector3 &p_q0, const Vector3 &p_q1) { + Vector3 ps; + Vector3 qt; + get_closest_points_between_segments(p_p0, p_p1, p_q0, p_q1, ps, qt); + Vector3 st = qt - ps; + return st.length(); +} + void Geometry3D::MeshData::optimize_vertices() { HashMap<int, int> vtx_remap; diff --git a/core/math/geometry_3d.h b/core/math/geometry_3d.h index 59c56906f4..e5ace9db72 100644 --- a/core/math/geometry_3d.h +++ b/core/math/geometry_3d.h @@ -37,96 +37,8 @@ class Geometry3D { public: - 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 it's a 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)) - - // Calculate the parametric position on the 2 curves, mua and mub. - real_t mua = (d_of(p1, q1, q2, q1) * d_of(q2, q1, p2, p1) - d_of(p1, q1, p2, p1) * d_of(q2, q1, q2, q1)) / (d_of(p2, p1, p2, p1) * d_of(q2, q1, q2, q1) - d_of(q2, q1, p2, p1) * d_of(q2, q1, p2, p1)); - real_t mub = (d_of(p1, q1, q2, q1) + mua * d_of(q2, q1, p2, p1)) / d_of(q2, q1, q2, q1); - - // Clip the value between [0..1] constraining the solution to lie on the original curves. - if (mua < 0) { - mua = 0; - } - if (mub < 0) { - mub = 0; - } - if (mua > 1) { - mua = 1; - } - if (mub > 1) { - mub = 1; - } - c1 = p1.lerp(p2, mua); - c2 = q1.lerp(q2, mub); - } - - static real_t get_closest_distance_between_segments(const Vector3 &p_from_a, const Vector3 &p_to_a, const Vector3 &p_from_b, const Vector3 &p_to_b) { - Vector3 u = p_to_a - p_from_a; - Vector3 v = p_to_b - p_from_b; - Vector3 w = p_from_a - p_to_a; - real_t a = u.dot(u); // Always >= 0 - real_t b = u.dot(v); - real_t c = v.dot(v); // Always >= 0 - real_t d = u.dot(w); - real_t e = v.dot(w); - real_t D = a * c - b * b; // Always >= 0 - real_t sc, sN, sD = D; // sc = sN / sD, default sD = D >= 0 - real_t tc, tN, tD = D; // tc = tN / tD, default tD = D >= 0 - - // Compute the line parameters of the two closest points. - if (D < (real_t)CMP_EPSILON) { // The lines are almost parallel. - sN = 0.0f; // Force using point P0 on segment S1 - sD = 1.0f; // to prevent possible division by 0.0 later. - tN = e; - tD = c; - } else { // Get the closest points on the infinite lines - sN = (b * e - c * d); - tN = (a * e - b * d); - if (sN < 0.0f) { // sc < 0 => the s=0 edge is visible. - sN = 0.0f; - tN = e; - tD = c; - } else if (sN > sD) { // sc > 1 => the s=1 edge is visible. - sN = sD; - tN = e + b; - tD = c; - } - } - - if (tN < 0.0f) { // tc < 0 => the t=0 edge is visible. - tN = 0.0f; - // Recompute sc for this edge. - if (-d < 0.0f) { - sN = 0.0f; - } else if (-d > a) { - sN = sD; - } else { - sN = -d; - sD = a; - } - } else if (tN > tD) { // tc > 1 => the t=1 edge is visible. - tN = tD; - // Recompute sc for this edge. - if ((-d + b) < 0.0f) { - sN = 0; - } else if ((-d + b) > a) { - sN = sD; - } else { - sN = (-d + b); - sD = a; - } - } - // Finally do the division to get sc and tc. - sc = (Math::is_zero_approx(sN) ? 0.0f : sN / sD); - tc = (Math::is_zero_approx(tN) ? 0.0f : tN / tD); - - // Get the difference of the two closest points. - Vector3 dP = w + (sc * u) - (tc * v); // = S1(sc) - S2(tc) - - return dP.length(); // Return the closest distance. - } + static void get_closest_points_between_segments(const Vector3 &p_p0, const Vector3 &p_p1, const Vector3 &p_q0, const Vector3 &p_q1, Vector3 &r_ps, Vector3 &r_qt); + static real_t get_closest_distance_between_segments(const Vector3 &p_p0, const Vector3 &p_p1, const Vector3 &p_q0, const Vector3 &p_q1); static inline bool ray_intersects_triangle(const Vector3 &p_from, const Vector3 &p_dir, const Vector3 &p_v0, const Vector3 &p_v1, const Vector3 &p_v2, Vector3 *r_res = nullptr) { Vector3 e1 = p_v1 - p_v0; diff --git a/core/math/math_fieldwise.cpp b/core/math/math_fieldwise.cpp index 208f89f449..726a2aeb97 100644 --- a/core/math/math_fieldwise.cpp +++ b/core/math/math_fieldwise.cpp @@ -56,6 +56,15 @@ Variant fieldwise_assign(const Variant &p_target, const Variant &p_source, const return target; } + case Variant::VECTOR2I: { + SETUP_TYPE(Vector2i) + + /**/ TRY_TRANSFER_FIELD("x", x) + else TRY_TRANSFER_FIELD("y", y) + + return target; + } + case Variant::RECT2: { SETUP_TYPE(Rect2) @@ -67,6 +76,17 @@ Variant fieldwise_assign(const Variant &p_target, const Variant &p_source, const return target; } + case Variant::RECT2I: { + SETUP_TYPE(Rect2i) + + /**/ TRY_TRANSFER_FIELD("x", position.x) + else TRY_TRANSFER_FIELD("y", position.y) + else TRY_TRANSFER_FIELD("w", size.x) + else TRY_TRANSFER_FIELD("h", size.y) + + return target; + } + case Variant::VECTOR3: { SETUP_TYPE(Vector3) @@ -76,6 +96,7 @@ Variant fieldwise_assign(const Variant &p_target, const Variant &p_source, const return target; } + case Variant::VECTOR3I: { SETUP_TYPE(Vector3i) @@ -85,6 +106,7 @@ Variant fieldwise_assign(const Variant &p_target, const Variant &p_source, const return target; } + case Variant::VECTOR4: { SETUP_TYPE(Vector4) @@ -95,6 +117,7 @@ Variant fieldwise_assign(const Variant &p_target, const Variant &p_source, const return target; } + case Variant::VECTOR4I: { SETUP_TYPE(Vector4i) @@ -106,7 +129,6 @@ Variant fieldwise_assign(const Variant &p_target, const Variant &p_source, const return target; } - case Variant::PLANE: { SETUP_TYPE(Plane) @@ -190,6 +212,29 @@ Variant fieldwise_assign(const Variant &p_target, const Variant &p_source, const return target; } + case Variant::PROJECTION: { + SETUP_TYPE(Projection) + + /**/ TRY_TRANSFER_FIELD("xx", matrix[0].x) + else TRY_TRANSFER_FIELD("xy", matrix[0].y) + else TRY_TRANSFER_FIELD("xz", matrix[0].z) + else TRY_TRANSFER_FIELD("xw", matrix[0].w) + else TRY_TRANSFER_FIELD("yx", matrix[1].x) + else TRY_TRANSFER_FIELD("yy", matrix[1].y) + else TRY_TRANSFER_FIELD("yz", matrix[1].z) + else TRY_TRANSFER_FIELD("yw", matrix[1].w) + else TRY_TRANSFER_FIELD("zx", matrix[2].x) + else TRY_TRANSFER_FIELD("zy", matrix[2].y) + else TRY_TRANSFER_FIELD("zz", matrix[2].z) + else TRY_TRANSFER_FIELD("zw", matrix[2].w) + else TRY_TRANSFER_FIELD("xo", matrix[3].x) + else TRY_TRANSFER_FIELD("yo", matrix[3].y) + else TRY_TRANSFER_FIELD("zo", matrix[3].z) + else TRY_TRANSFER_FIELD("wo", matrix[3].w) + + return target; + } + default: { ERR_FAIL_V(p_target); } diff --git a/core/math/math_funcs.h b/core/math/math_funcs.h index 463e119add..7fa674a23d 100644 --- a/core/math/math_funcs.h +++ b/core/math/math_funcs.h @@ -229,11 +229,11 @@ public: return value; } - static _ALWAYS_INLINE_ double deg2rad(double p_y) { return p_y * (Math_PI / 180.0); } - static _ALWAYS_INLINE_ float deg2rad(float p_y) { return p_y * (float)(Math_PI / 180.0); } + static _ALWAYS_INLINE_ double deg_to_rad(double p_y) { return p_y * (Math_PI / 180.0); } + static _ALWAYS_INLINE_ float deg_to_rad(float p_y) { return p_y * (float)(Math_PI / 180.0); } - static _ALWAYS_INLINE_ double rad2deg(double p_y) { return p_y * (180.0 / Math_PI); } - static _ALWAYS_INLINE_ float rad2deg(float p_y) { return p_y * (float)(180.0 / Math_PI); } + static _ALWAYS_INLINE_ double rad_to_deg(double p_y) { return p_y * (180.0 / Math_PI); } + static _ALWAYS_INLINE_ float rad_to_deg(float p_y) { return p_y * (float)(180.0 / Math_PI); } static _ALWAYS_INLINE_ double lerp(double p_from, double p_to, double p_weight) { return p_from + (p_to - p_from) * p_weight; } static _ALWAYS_INLINE_ float lerp(float p_from, float p_to, float p_weight) { return p_from + (p_to - p_from) * p_weight; } @@ -253,6 +253,36 @@ public: (-p_pre + 3.0f * p_from - 3.0f * p_to + p_post) * (p_weight * p_weight * p_weight)); } + static _ALWAYS_INLINE_ double cubic_interpolate_angle(double p_from, double p_to, double p_pre, double p_post, double p_weight) { + double from_rot = fmod(p_from, Math_TAU); + + double pre_diff = fmod(p_pre - from_rot, Math_TAU); + double pre_rot = from_rot + fmod(2.0 * pre_diff, Math_TAU) - pre_diff; + + double to_diff = fmod(p_to - from_rot, Math_TAU); + double to_rot = from_rot + fmod(2.0 * to_diff, Math_TAU) - to_diff; + + double post_diff = fmod(p_post - to_rot, Math_TAU); + double post_rot = to_rot + fmod(2.0 * post_diff, Math_TAU) - post_diff; + + return cubic_interpolate(from_rot, to_rot, pre_rot, post_rot, p_weight); + } + + static _ALWAYS_INLINE_ float cubic_interpolate_angle(float p_from, float p_to, float p_pre, float p_post, float p_weight) { + float from_rot = fmod(p_from, (float)Math_TAU); + + float pre_diff = fmod(p_pre - from_rot, (float)Math_TAU); + float pre_rot = from_rot + fmod(2.0f * pre_diff, (float)Math_TAU) - pre_diff; + + float to_diff = fmod(p_to - from_rot, (float)Math_TAU); + float to_rot = from_rot + fmod(2.0f * to_diff, (float)Math_TAU) - to_diff; + + float post_diff = fmod(p_post - to_rot, (float)Math_TAU); + float post_rot = to_rot + fmod(2.0f * post_diff, (float)Math_TAU) - post_diff; + + return cubic_interpolate(from_rot, to_rot, pre_rot, post_rot, p_weight); + } + static _ALWAYS_INLINE_ double cubic_interpolate_in_time(double p_from, double p_to, double p_pre, double p_post, double p_weight, double p_to_t, double p_pre_t, double p_post_t) { /* Barry-Goldman method */ @@ -264,6 +294,7 @@ public: double b2 = Math::lerp(a2, a3, p_post_t == 0 ? 1.0 : t / p_post_t); return Math::lerp(b1, b2, p_to_t == 0 ? 0.5 : t / p_to_t); } + static _ALWAYS_INLINE_ float cubic_interpolate_in_time(float p_from, float p_to, float p_pre, float p_post, float p_weight, float p_to_t, float p_pre_t, float p_post_t) { /* Barry-Goldman method */ @@ -276,6 +307,38 @@ public: return Math::lerp(b1, b2, p_to_t == 0 ? 0.5f : t / p_to_t); } + static _ALWAYS_INLINE_ double cubic_interpolate_angle_in_time(double p_from, double p_to, double p_pre, double p_post, double p_weight, + double p_to_t, double p_pre_t, double p_post_t) { + double from_rot = fmod(p_from, Math_TAU); + + double pre_diff = fmod(p_pre - from_rot, Math_TAU); + double pre_rot = from_rot + fmod(2.0 * pre_diff, Math_TAU) - pre_diff; + + double to_diff = fmod(p_to - from_rot, Math_TAU); + double to_rot = from_rot + fmod(2.0 * to_diff, Math_TAU) - to_diff; + + double post_diff = fmod(p_post - to_rot, Math_TAU); + double post_rot = to_rot + fmod(2.0 * post_diff, Math_TAU) - post_diff; + + return cubic_interpolate_in_time(from_rot, to_rot, pre_rot, post_rot, p_weight, p_to_t, p_pre_t, p_post_t); + } + + static _ALWAYS_INLINE_ float cubic_interpolate_angle_in_time(float p_from, float p_to, float p_pre, float p_post, float p_weight, + float p_to_t, float p_pre_t, float p_post_t) { + float from_rot = fmod(p_from, (float)Math_TAU); + + float pre_diff = fmod(p_pre - from_rot, (float)Math_TAU); + float pre_rot = from_rot + fmod(2.0f * pre_diff, (float)Math_TAU) - pre_diff; + + float to_diff = fmod(p_to - from_rot, (float)Math_TAU); + float to_rot = from_rot + fmod(2.0f * to_diff, (float)Math_TAU) - to_diff; + + float post_diff = fmod(p_post - to_rot, (float)Math_TAU); + float post_rot = to_rot + fmod(2.0f * post_diff, (float)Math_TAU) - post_diff; + + return cubic_interpolate_in_time(from_rot, to_rot, pre_rot, post_rot, p_weight, p_to_t, p_pre_t, p_post_t); + } + static _ALWAYS_INLINE_ double bezier_interpolate(double p_start, double p_control_1, double p_control_2, double p_end, double p_t) { /* Formula from Wikipedia article on Bezier curves. */ double omt = (1.0 - p_t); @@ -286,6 +349,7 @@ public: return p_start * omt3 + p_control_1 * omt2 * p_t * 3.0 + p_control_2 * omt * t2 * 3.0 + p_end * t3; } + static _ALWAYS_INLINE_ float bezier_interpolate(float p_start, float p_control_1, float p_control_2, float p_end, float p_t) { /* Formula from Wikipedia article on Bezier curves. */ float omt = (1.0f - p_t); @@ -308,11 +372,19 @@ public: return p_from + distance * p_weight; } - static _ALWAYS_INLINE_ double inverse_lerp(double p_from, double p_to, double p_value) { return (p_value - p_from) / (p_to - p_from); } - static _ALWAYS_INLINE_ float inverse_lerp(float p_from, float p_to, float p_value) { return (p_value - p_from) / (p_to - p_from); } + static _ALWAYS_INLINE_ double inverse_lerp(double p_from, double p_to, double p_value) { + return (p_value - p_from) / (p_to - p_from); + } + static _ALWAYS_INLINE_ float inverse_lerp(float p_from, float p_to, float p_value) { + return (p_value - p_from) / (p_to - p_from); + } - static _ALWAYS_INLINE_ double range_lerp(double p_value, double p_istart, double p_istop, double p_ostart, double p_ostop) { return Math::lerp(p_ostart, p_ostop, Math::inverse_lerp(p_istart, p_istop, p_value)); } - static _ALWAYS_INLINE_ float range_lerp(float p_value, float p_istart, float p_istop, float p_ostart, float p_ostop) { return Math::lerp(p_ostart, p_ostop, Math::inverse_lerp(p_istart, p_istop, p_value)); } + static _ALWAYS_INLINE_ double remap(double p_value, double p_istart, double p_istop, double p_ostart, double p_ostop) { + return Math::lerp(p_ostart, p_ostop, Math::inverse_lerp(p_istart, p_istop, p_value)); + } + static _ALWAYS_INLINE_ float remap(float p_value, float p_istart, float p_istop, float p_ostart, float p_ostop) { + return Math::lerp(p_ostart, p_ostop, Math::inverse_lerp(p_istart, p_istop, p_value)); + } static _ALWAYS_INLINE_ double smoothstep(double p_from, double p_to, double p_s) { if (is_equal_approx(p_from, p_to)) { @@ -328,14 +400,26 @@ public: float s = CLAMP((p_s - p_from) / (p_to - p_from), 0.0f, 1.0f); return s * s * (3.0f - 2.0f * s); } - static _ALWAYS_INLINE_ double move_toward(double p_from, double p_to, double p_delta) { return abs(p_to - p_from) <= p_delta ? p_to : p_from + SIGN(p_to - p_from) * p_delta; } - static _ALWAYS_INLINE_ float move_toward(float p_from, float p_to, float p_delta) { return abs(p_to - p_from) <= p_delta ? p_to : p_from + SIGN(p_to - p_from) * p_delta; } + static _ALWAYS_INLINE_ double move_toward(double p_from, double p_to, double p_delta) { + return abs(p_to - p_from) <= p_delta ? p_to : p_from + SIGN(p_to - p_from) * p_delta; + } + static _ALWAYS_INLINE_ float move_toward(float p_from, float p_to, float p_delta) { + return abs(p_to - p_from) <= p_delta ? p_to : p_from + SIGN(p_to - p_from) * p_delta; + } - static _ALWAYS_INLINE_ double linear2db(double p_linear) { return Math::log(p_linear) * 8.6858896380650365530225783783321; } - static _ALWAYS_INLINE_ float linear2db(float p_linear) { return Math::log(p_linear) * (float)8.6858896380650365530225783783321; } + static _ALWAYS_INLINE_ double linear_to_db(double p_linear) { + return Math::log(p_linear) * 8.6858896380650365530225783783321; + } + static _ALWAYS_INLINE_ float linear_to_db(float p_linear) { + return Math::log(p_linear) * (float)8.6858896380650365530225783783321; + } - static _ALWAYS_INLINE_ double db2linear(double p_db) { return Math::exp(p_db * 0.11512925464970228420089957273422); } - static _ALWAYS_INLINE_ float db2linear(float p_db) { return Math::exp(p_db * (float)0.11512925464970228420089957273422); } + static _ALWAYS_INLINE_ double db_to_linear(double p_db) { + return Math::exp(p_db * 0.11512925464970228420089957273422); + } + static _ALWAYS_INLINE_ float db_to_linear(float p_db) { + return Math::exp(p_db * (float)0.11512925464970228420089957273422); + } static _ALWAYS_INLINE_ double round(double p_val) { return ::round(p_val); } static _ALWAYS_INLINE_ float round(float p_val) { return ::roundf(p_val); } diff --git a/core/math/projection.cpp b/core/math/projection.cpp index edf8bf36cd..863fe6ee79 100644 --- a/core/math/projection.cpp +++ b/core/math/projection.cpp @@ -255,7 +255,7 @@ void Projection::set_perspective(real_t p_fovy_degrees, real_t p_aspect, real_t } real_t sine, cotangent, deltaZ; - real_t radians = Math::deg2rad(p_fovy_degrees / 2.0); + real_t radians = Math::deg_to_rad(p_fovy_degrees / 2.0); deltaZ = p_z_far - p_z_near; sine = Math::sin(radians); @@ -282,7 +282,7 @@ void Projection::set_perspective(real_t p_fovy_degrees, real_t p_aspect, real_t real_t left, right, modeltranslation, ymax, xmax, frustumshift; - ymax = p_z_near * tan(Math::deg2rad(p_fovy_degrees / 2.0)); + ymax = p_z_near * tan(Math::deg_to_rad(p_fovy_degrees / 2.0)); xmax = ymax * p_aspect; frustumshift = (p_intraocular_dist / 2.0) * p_z_near / p_convergence_dist; @@ -816,7 +816,7 @@ real_t Projection::get_fov() const { right_plane.normalize(); if ((matrix[8] == 0) && (matrix[9] == 0)) { - return Math::rad2deg(Math::acos(Math::abs(right_plane.normal.x))) * 2.0; + return Math::rad_to_deg(Math::acos(Math::abs(right_plane.normal.x))) * 2.0; } else { // our frustum is asymmetrical need to calculate the left planes angle separately.. Plane left_plane = Plane(matrix[3] + matrix[0], @@ -825,7 +825,7 @@ real_t Projection::get_fov() const { matrix[15] + matrix[12]); left_plane.normalize(); - return Math::rad2deg(Math::acos(Math::abs(left_plane.normal.x))) + Math::rad2deg(Math::acos(Math::abs(right_plane.normal.x))); + return Math::rad_to_deg(Math::acos(Math::abs(left_plane.normal.x))) + Math::rad_to_deg(Math::acos(Math::abs(right_plane.normal.x))); } } diff --git a/core/math/projection.h b/core/math/projection.h index a3d2d7720b..f149d307b3 100644 --- a/core/math/projection.h +++ b/core/math/projection.h @@ -96,7 +96,7 @@ struct Projection { Projection jitter_offseted(const Vector2 &p_offset) const; static real_t get_fovy(real_t p_fovx, real_t p_aspect) { - return Math::rad2deg(Math::atan(p_aspect * Math::tan(Math::deg2rad(p_fovx) * 0.5)) * 2.0); + return Math::rad_to_deg(Math::atan(p_aspect * Math::tan(Math::deg_to_rad(p_fovx) * 0.5)) * 2.0); } real_t get_z_far() const; diff --git a/core/math/rect2.h b/core/math/rect2.h index 679af933c2..2d1be3d4f3 100644 --- a/core/math/rect2.h +++ b/core/math/rect2.h @@ -140,8 +140,8 @@ struct _NO_DISCARD_ Rect2 { ((p_rect.position.y + p_rect.size.y) <= (position.y + size.y)); } - _FORCE_INLINE_ bool has_no_area() const { - return (size.x <= 0 || size.y <= 0); + _FORCE_INLINE_ bool has_area() const { + return size.x > 0.0f && size.y > 0.0f; } // Returns the instersection between two Rect2s or an empty Rect2 if there is no intersection diff --git a/core/math/rect2i.h b/core/math/rect2i.h index db1459a3e6..2b58dcdd98 100644 --- a/core/math/rect2i.h +++ b/core/math/rect2i.h @@ -83,8 +83,8 @@ struct _NO_DISCARD_ Rect2i { ((p_rect.position.y + p_rect.size.y) <= (position.y + size.y)); } - _FORCE_INLINE_ bool has_no_area() const { - return (size.x <= 0 || size.y <= 0); + _FORCE_INLINE_ bool has_area() const { + return size.x > 0 && size.y > 0; } // Returns the instersection between two Rect2is or an empty Rect2i if there is no intersection diff --git a/core/math/transform_3d.cpp b/core/math/transform_3d.cpp index a634faca9a..2de9e81b38 100644 --- a/core/math/transform_3d.cpp +++ b/core/math/transform_3d.cpp @@ -94,9 +94,7 @@ void Transform3D::set_look_at(const Vector3 &p_eye, const Vector3 &p_target, con origin = p_eye; } -Transform3D Transform3D::spherical_interpolate_with(const Transform3D &p_transform, real_t p_c) const { - /* not sure if very "efficient" but good enough? */ - +Transform3D Transform3D::interpolate_with(const Transform3D &p_transform, real_t p_c) const { Transform3D interp; Vector3 src_scale = basis.get_scale(); @@ -113,15 +111,6 @@ Transform3D Transform3D::spherical_interpolate_with(const Transform3D &p_transfo return interp; } -Transform3D Transform3D::interpolate_with(const Transform3D &p_transform, real_t p_c) const { - Transform3D interp; - - interp.basis = basis.lerp(p_transform.basis, p_c); - interp.origin = origin.lerp(p_transform.origin, p_c); - - return interp; -} - void Transform3D::scale(const Vector3 &p_scale) { basis.scale(p_scale); origin *= p_scale; diff --git a/core/math/transform_3d.h b/core/math/transform_3d.h index b572e90859..c62e4a7b0e 100644 --- a/core/math/transform_3d.h +++ b/core/math/transform_3d.h @@ -103,7 +103,6 @@ struct _NO_DISCARD_ Transform3D { void operator*=(const real_t p_val); Transform3D operator*(const real_t p_val) const; - Transform3D spherical_interpolate_with(const Transform3D &p_transform, real_t p_c) const; Transform3D interpolate_with(const Transform3D &p_transform, real_t p_c) const; _FORCE_INLINE_ Transform3D inverse_xform(const Transform3D &t) const { diff --git a/core/math/vector2.cpp b/core/math/vector2.cpp index d9b5d55454..56dbba393a 100644 --- a/core/math/vector2.cpp +++ b/core/math/vector2.cpp @@ -182,6 +182,10 @@ bool Vector2::is_equal_approx(const Vector2 &p_v) const { return Math::is_equal_approx(x, p_v.x) && Math::is_equal_approx(y, p_v.y); } +bool Vector2::is_zero_approx() const { + return Math::is_zero_approx(x) && Math::is_zero_approx(y); +} + Vector2::operator String() const { return "(" + String::num_real(x, false) + ", " + String::num_real(y, false) + ")"; } diff --git a/core/math/vector2.h b/core/math/vector2.h index caa6b226e7..9441f84087 100644 --- a/core/math/vector2.h +++ b/core/math/vector2.h @@ -124,6 +124,7 @@ struct _NO_DISCARD_ Vector2 { Vector2 reflect(const Vector2 &p_normal) const; bool is_equal_approx(const Vector2 &p_v) const; + bool is_zero_approx() const; Vector2 operator+(const Vector2 &p_v) const; void operator+=(const Vector2 &p_v); diff --git a/core/math/vector2i.h b/core/math/vector2i.h index 13b70031bd..e131bdea94 100644 --- a/core/math/vector2i.h +++ b/core/math/vector2i.h @@ -38,6 +38,8 @@ class String; struct Vector2; struct _NO_DISCARD_ Vector2i { + static const int AXIS_COUNT = 2; + enum Axis { AXIS_X, AXIS_Y, @@ -115,7 +117,7 @@ struct _NO_DISCARD_ Vector2i { real_t aspect() const { return width / (real_t)height; } Vector2i sign() const { return Vector2i(SIGN(x), SIGN(y)); } - Vector2i abs() const { return Vector2i(ABS(x), ABS(y)); } + Vector2i abs() const { return Vector2i(Math::abs(x), Math::abs(y)); } Vector2i clamp(const Vector2i &p_min, const Vector2i &p_max) const; operator String() const; diff --git a/core/math/vector3.cpp b/core/math/vector3.cpp index fdbbb8cb5c..4db45fe798 100644 --- a/core/math/vector3.cpp +++ b/core/math/vector3.cpp @@ -134,17 +134,21 @@ Vector3 Vector3::octahedron_tangent_decode(const Vector2 &p_oct, float *sign) { } Basis Vector3::outer(const Vector3 &p_with) const { - Vector3 row0(x * p_with.x, x * p_with.y, x * p_with.z); - Vector3 row1(y * p_with.x, y * p_with.y, y * p_with.z); - Vector3 row2(z * p_with.x, z * p_with.y, z * p_with.z); - - return Basis(row0, row1, row2); + Basis basis; + basis.rows[0] = Vector3(x * p_with.x, x * p_with.y, x * p_with.z); + basis.rows[1] = Vector3(y * p_with.x, y * p_with.y, y * p_with.z); + basis.rows[2] = Vector3(z * p_with.x, z * p_with.y, z * p_with.z); + return basis; } bool Vector3::is_equal_approx(const Vector3 &p_v) const { return Math::is_equal_approx(x, p_v.x) && Math::is_equal_approx(y, p_v.y) && Math::is_equal_approx(z, p_v.z); } +bool Vector3::is_zero_approx() const { + return Math::is_zero_approx(x) && Math::is_zero_approx(y) && Math::is_zero_approx(z); +} + Vector3::operator String() const { return "(" + String::num_real(x, false) + ", " + String::num_real(y, false) + ", " + String::num_real(z, false) + ")"; } diff --git a/core/math/vector3.h b/core/math/vector3.h index 7cae6e2481..3944afa92e 100644 --- a/core/math/vector3.h +++ b/core/math/vector3.h @@ -142,6 +142,7 @@ struct _NO_DISCARD_ Vector3 { _FORCE_INLINE_ Vector3 reflect(const Vector3 &p_normal) const; bool is_equal_approx(const Vector3 &p_v) const; + bool is_zero_approx() const; /* Operators */ diff --git a/core/math/vector3i.h b/core/math/vector3i.h index b49c1142ed..c6d03cd031 100644 --- a/core/math/vector3i.h +++ b/core/math/vector3i.h @@ -38,6 +38,8 @@ class String; struct Vector3; struct _NO_DISCARD_ Vector3i { + static const int AXIS_COUNT = 3; + enum Axis { AXIS_X, AXIS_Y, @@ -128,7 +130,7 @@ double Vector3i::length() const { } Vector3i Vector3i::abs() const { - return Vector3i(ABS(x), ABS(y), ABS(z)); + return Vector3i(Math::abs(x), Math::abs(y), Math::abs(z)); } Vector3i Vector3i::sign() const { diff --git a/core/math/vector4.cpp b/core/math/vector4.cpp index 273a111891..3c25f454a3 100644 --- a/core/math/vector4.cpp +++ b/core/math/vector4.cpp @@ -71,20 +71,35 @@ bool Vector4::is_equal_approx(const Vector4 &p_vec4) const { return Math::is_equal_approx(x, p_vec4.x) && Math::is_equal_approx(y, p_vec4.y) && Math::is_equal_approx(z, p_vec4.z) && Math::is_equal_approx(w, p_vec4.w); } +bool Vector4::is_zero_approx() const { + return Math::is_zero_approx(x) && Math::is_zero_approx(y) && Math::is_zero_approx(z) && Math::is_zero_approx(w); +} + real_t Vector4::length() const { return Math::sqrt(length_squared()); } void Vector4::normalize() { - *this /= length(); + real_t lengthsq = length_squared(); + if (lengthsq == 0) { + x = y = z = w = 0; + } else { + real_t length = Math::sqrt(lengthsq); + x /= length; + y /= length; + z /= length; + w /= length; + } } Vector4 Vector4::normalized() const { - return *this / length(); + Vector4 v = *this; + v.normalize(); + return v; } bool Vector4::is_normalized() const { - return Math::is_equal_approx(length_squared(), 1, (real_t)UNIT_EPSILON); // Use less epsilon. + return Math::is_equal_approx(length_squared(), (real_t)1, (real_t)UNIT_EPSILON); } real_t Vector4::distance_to(const Vector4 &p_to) const { @@ -183,3 +198,5 @@ Vector4 Vector4::clamp(const Vector4 &p_min, const Vector4 &p_max) const { Vector4::operator String() const { return "(" + String::num_real(x, false) + ", " + String::num_real(y, false) + ", " + String::num_real(z, false) + ", " + String::num_real(w, false) + ")"; } + +static_assert(sizeof(Vector4) == 4 * sizeof(real_t)); diff --git a/core/math/vector4.h b/core/math/vector4.h index 17d0de18e1..d89f3ddb05 100644 --- a/core/math/vector4.h +++ b/core/math/vector4.h @@ -37,6 +37,8 @@ #include "core/string/ustring.h" struct _NO_DISCARD_ Vector4 { + static const int AXIS_COUNT = 4; + enum Axis { AXIS_X, AXIS_Y, @@ -73,6 +75,7 @@ struct _NO_DISCARD_ Vector4 { _FORCE_INLINE_ real_t length_squared() const; bool is_equal_approx(const Vector4 &p_vec4) const; + bool is_zero_approx() const; real_t length() const; void normalize(); Vector4 normalized() const; diff --git a/core/math/vector4i.cpp b/core/math/vector4i.cpp index 2dc5b74202..a89b802675 100644 --- a/core/math/vector4i.cpp +++ b/core/math/vector4i.cpp @@ -84,8 +84,10 @@ Vector4i::operator Vector4() const { } Vector4i::Vector4i(const Vector4 &p_vec4) { - x = p_vec4.x; - y = p_vec4.y; - z = p_vec4.z; - w = p_vec4.w; + x = (int32_t)p_vec4.x; + y = (int32_t)p_vec4.y; + z = (int32_t)p_vec4.z; + w = (int32_t)p_vec4.w; } + +static_assert(sizeof(Vector4i) == 4 * sizeof(int32_t)); diff --git a/core/math/vector4i.h b/core/math/vector4i.h index 37d905878f..fdf33b9569 100644 --- a/core/math/vector4i.h +++ b/core/math/vector4i.h @@ -38,6 +38,8 @@ class String; struct Vector4; struct _NO_DISCARD_ Vector4i { + static const int AXIS_COUNT = 4; + enum Axis { AXIS_X, AXIS_Y, @@ -132,7 +134,7 @@ double Vector4i::length() const { } Vector4i Vector4i::abs() const { - return Vector4i(ABS(x), ABS(y), ABS(z), ABS(w)); + return Vector4i(Math::abs(x), Math::abs(y), Math::abs(z), Math::abs(w)); } Vector4i Vector4i::sign() const { |