diff options
Diffstat (limited to 'core/math')
49 files changed, 1502 insertions, 1070 deletions
diff --git a/core/math/a_star.cpp b/core/math/a_star.cpp index 5258099558..c43fcf279e 100644 --- a/core/math/a_star.cpp +++ b/core/math/a_star.cpp @@ -33,7 +33,7 @@ #include "core/math/geometry_3d.h" #include "core/object/script_language.h" -int AStar::get_available_point_id() const { +int AStar3D::get_available_point_id() const { if (points.has(last_free_id)) { int cur_new_id = last_free_id + 1; while (points.has(cur_new_id)) { @@ -45,9 +45,9 @@ int AStar::get_available_point_id() const { return last_free_id; } -void AStar::add_point(int p_id, const Vector3 &p_pos, real_t p_weight_scale) { +void AStar3D::add_point(int p_id, const Vector3 &p_pos, real_t p_weight_scale) { ERR_FAIL_COND_MSG(p_id < 0, vformat("Can't add a point with negative id: %d.", p_id)); - ERR_FAIL_COND_MSG(p_weight_scale < 1, vformat("Can't add a point with weight scale less than one: %f.", p_weight_scale)); + ERR_FAIL_COND_MSG(p_weight_scale < 0.0, vformat("Can't add a point with weight scale less than 0.0: %f.", p_weight_scale)); Point *found_pt; bool p_exists = points.lookup(p_id, found_pt); @@ -68,7 +68,7 @@ void AStar::add_point(int p_id, const Vector3 &p_pos, real_t p_weight_scale) { } } -Vector3 AStar::get_point_position(int p_id) const { +Vector3 AStar3D::get_point_position(int p_id) const { Point *p; bool p_exists = points.lookup(p_id, p); ERR_FAIL_COND_V_MSG(!p_exists, Vector3(), vformat("Can't get point's position. Point with id: %d doesn't exist.", p_id)); @@ -76,7 +76,7 @@ Vector3 AStar::get_point_position(int p_id) const { return p->pos; } -void AStar::set_point_position(int p_id, const Vector3 &p_pos) { +void AStar3D::set_point_position(int p_id, const Vector3 &p_pos) { Point *p; bool p_exists = points.lookup(p_id, p); ERR_FAIL_COND_MSG(!p_exists, vformat("Can't set point's position. Point with id: %d doesn't exist.", p_id)); @@ -84,7 +84,7 @@ void AStar::set_point_position(int p_id, const Vector3 &p_pos) { p->pos = p_pos; } -real_t AStar::get_point_weight_scale(int p_id) const { +real_t AStar3D::get_point_weight_scale(int p_id) const { Point *p; bool p_exists = points.lookup(p_id, p); ERR_FAIL_COND_V_MSG(!p_exists, 0, vformat("Can't get point's weight scale. Point with id: %d doesn't exist.", p_id)); @@ -92,16 +92,16 @@ real_t AStar::get_point_weight_scale(int p_id) const { return p->weight_scale; } -void AStar::set_point_weight_scale(int p_id, real_t p_weight_scale) { +void AStar3D::set_point_weight_scale(int p_id, real_t p_weight_scale) { Point *p; bool p_exists = points.lookup(p_id, p); ERR_FAIL_COND_MSG(!p_exists, vformat("Can't set point's weight scale. Point with id: %d doesn't exist.", p_id)); - ERR_FAIL_COND_MSG(p_weight_scale < 1, vformat("Can't set point's weight scale less than one: %f.", p_weight_scale)); + ERR_FAIL_COND_MSG(p_weight_scale < 0.0, vformat("Can't set point's weight scale less than 0.0: %f.", p_weight_scale)); p->weight_scale = p_weight_scale; } -void AStar::remove_point(int p_id) { +void AStar3D::remove_point(int p_id) { Point *p; bool p_exists = points.lookup(p_id, p); ERR_FAIL_COND_MSG(!p_exists, vformat("Can't remove point. Point with id: %d doesn't exist.", p_id)); @@ -127,7 +127,7 @@ void AStar::remove_point(int p_id) { last_free_id = p_id; } -void AStar::connect_points(int p_id, int p_with_id, bool bidirectional) { +void AStar3D::connect_points(int p_id, int p_with_id, bool bidirectional) { ERR_FAIL_COND_MSG(p_id == p_with_id, vformat("Can't connect point with id: %d to itself.", p_id)); Point *a; @@ -151,21 +151,21 @@ void AStar::connect_points(int p_id, int p_with_id, bool bidirectional) { s.direction = Segment::BIDIRECTIONAL; } - Set<Segment>::Element *element = segments.find(s); - if (element != nullptr) { - s.direction |= element->get().direction; + HashSet<Segment, Segment>::Iterator element = segments.find(s); + if (element) { + s.direction |= element->direction; if (s.direction == Segment::BIDIRECTIONAL) { // Both are neighbours of each other now a->unlinked_neighbours.remove(b->id); b->unlinked_neighbours.remove(a->id); } - segments.erase(element); + segments.remove(element); } segments.insert(s); } -void AStar::disconnect_points(int p_id, int p_with_id, bool bidirectional) { +void AStar3D::disconnect_points(int p_id, int p_with_id, bool bidirectional) { Point *a; bool a_exists = points.lookup(p_id, a); ERR_FAIL_COND_MSG(!a_exists, vformat("Can't disconnect points. Point with id: %d doesn't exist.", p_id)); @@ -177,16 +177,16 @@ void AStar::disconnect_points(int p_id, int p_with_id, bool bidirectional) { Segment s(p_id, p_with_id); int remove_direction = bidirectional ? (int)Segment::BIDIRECTIONAL : s.direction; - Set<Segment>::Element *element = segments.find(s); - if (element != nullptr) { + HashSet<Segment, Segment>::Iterator element = segments.find(s); + if (element) { // s is the new segment // Erase the directions to be removed - s.direction = (element->get().direction & ~remove_direction); + s.direction = (element->direction & ~remove_direction); a->neighbours.remove(b->id); if (bidirectional) { b->neighbours.remove(a->id); - if (element->get().direction != Segment::BIDIRECTIONAL) { + if (element->direction != Segment::BIDIRECTIONAL) { a->unlinked_neighbours.remove(b->id); b->unlinked_neighbours.remove(a->id); } @@ -198,18 +198,18 @@ void AStar::disconnect_points(int p_id, int p_with_id, bool bidirectional) { } } - segments.erase(element); + segments.remove(element); if (s.direction != Segment::NONE) { segments.insert(s); } } } -bool AStar::has_point(int p_id) const { +bool AStar3D::has_point(int p_id) const { return points.has(p_id); } -Array AStar::get_point_ids() { +Array AStar3D::get_point_ids() { Array point_list; for (OAHashMap<int, Point *>::Iterator it = points.iter(); it.valid; it = points.next_iter(it)) { @@ -219,7 +219,7 @@ Array AStar::get_point_ids() { return point_list; } -Vector<int> AStar::get_point_connections(int p_id) { +Vector<int> AStar3D::get_point_connections(int p_id) { Point *p; bool p_exists = points.lookup(p_id, p); ERR_FAIL_COND_V_MSG(!p_exists, Vector<int>(), vformat("Can't get point's connections. Point with id: %d doesn't exist.", p_id)); @@ -233,15 +233,15 @@ Vector<int> AStar::get_point_connections(int p_id) { return point_list; } -bool AStar::are_points_connected(int p_id, int p_with_id, bool bidirectional) const { +bool AStar3D::are_points_connected(int p_id, int p_with_id, bool bidirectional) const { Segment s(p_id, p_with_id); - const Set<Segment>::Element *element = segments.find(s); + const HashSet<Segment, Segment>::Iterator element = segments.find(s); - return element != nullptr && - (bidirectional || (element->get().direction & s.direction) == s.direction); + return element && + (bidirectional || (element->direction & s.direction) == s.direction); } -void AStar::clear() { +void AStar3D::clear() { last_free_id = 0; for (OAHashMap<int, Point *>::Iterator it = points.iter(); it.valid; it = points.next_iter(it)) { memdelete(*(it.value)); @@ -250,21 +250,21 @@ void AStar::clear() { points.clear(); } -int AStar::get_point_count() const { +int AStar3D::get_point_count() const { return points.get_num_elements(); } -int AStar::get_point_capacity() const { +int AStar3D::get_point_capacity() const { return points.get_capacity(); } -void AStar::reserve_space(int p_num_nodes) { +void AStar3D::reserve_space(int p_num_nodes) { ERR_FAIL_COND_MSG(p_num_nodes <= 0, vformat("New capacity must be greater than 0, new was: %d.", p_num_nodes)); ERR_FAIL_COND_MSG((uint32_t)p_num_nodes < points.get_capacity(), vformat("New capacity must be greater than current capacity: %d, new was: %d.", points.get_capacity(), p_num_nodes)); points.reserve(p_num_nodes); } -int AStar::get_closest_point(const Vector3 &p_point, bool p_include_disabled) const { +int AStar3D::get_closest_point(const Vector3 &p_point, bool p_include_disabled) const { int closest_id = -1; real_t closest_dist = 1e20; @@ -289,14 +289,14 @@ int AStar::get_closest_point(const Vector3 &p_point, bool p_include_disabled) co return closest_id; } -Vector3 AStar::get_closest_position_in_segment(const Vector3 &p_point) const { +Vector3 AStar3D::get_closest_position_in_segment(const Vector3 &p_point) const { real_t closest_dist = 1e20; Vector3 closest_point; - for (const Set<Segment>::Element *E = segments.front(); E; E = E->next()) { + for (const Segment &E : segments) { Point *from_point = nullptr, *to_point = nullptr; - points.lookup(E->get().u, from_point); - points.lookup(E->get().v, to_point); + points.lookup(E.u, from_point); + points.lookup(E.v, to_point); if (!(from_point->enabled && to_point->enabled)) { continue; @@ -318,7 +318,7 @@ Vector3 AStar::get_closest_position_in_segment(const Vector3 &p_point) const { return closest_point; } -bool AStar::_solve(Point *begin_point, Point *end_point) { +bool AStar3D::_solve(Point *begin_point, Point *end_point) { pass++; if (!end_point->enabled) { @@ -380,7 +380,7 @@ bool AStar::_solve(Point *begin_point, Point *end_point) { return found_route; } -real_t AStar::_estimate_cost(int p_from_id, int p_to_id) { +real_t AStar3D::_estimate_cost(int p_from_id, int p_to_id) { real_t scost; if (GDVIRTUAL_CALL(_estimate_cost, p_from_id, p_to_id, scost)) { return scost; @@ -397,7 +397,7 @@ real_t AStar::_estimate_cost(int p_from_id, int p_to_id) { return from_point->pos.distance_to(to_point->pos); } -real_t AStar::_compute_cost(int p_from_id, int p_to_id) { +real_t AStar3D::_compute_cost(int p_from_id, int p_to_id) { real_t scost; if (GDVIRTUAL_CALL(_compute_cost, p_from_id, p_to_id, scost)) { return scost; @@ -414,7 +414,7 @@ real_t AStar::_compute_cost(int p_from_id, int p_to_id) { return from_point->pos.distance_to(to_point->pos); } -Vector<Vector3> AStar::get_point_path(int p_from_id, int p_to_id) { +Vector<Vector3> AStar3D::get_point_path(int p_from_id, int p_to_id) { Point *a; bool from_exists = points.lookup(p_from_id, a); ERR_FAIL_COND_V_MSG(!from_exists, Vector<Vector3>(), vformat("Can't get point path. Point with id: %d doesn't exist.", p_from_id)); @@ -463,7 +463,7 @@ Vector<Vector3> AStar::get_point_path(int p_from_id, int p_to_id) { return path; } -Vector<int> AStar::get_id_path(int p_from_id, int p_to_id) { +Vector<int> AStar3D::get_id_path(int p_from_id, int p_to_id) { Point *a; bool from_exists = points.lookup(p_from_id, a); ERR_FAIL_COND_V_MSG(!from_exists, Vector<int>(), vformat("Can't get id path. Point with id: %d doesn't exist.", p_from_id)); @@ -512,7 +512,7 @@ Vector<int> AStar::get_id_path(int p_from_id, int p_to_id) { return path; } -void AStar::set_point_disabled(int p_id, bool p_disabled) { +void AStar3D::set_point_disabled(int p_id, bool p_disabled) { Point *p; bool p_exists = points.lookup(p_id, p); ERR_FAIL_COND_MSG(!p_exists, vformat("Can't set if point is disabled. Point with id: %d doesn't exist.", p_id)); @@ -520,7 +520,7 @@ void AStar::set_point_disabled(int p_id, bool p_disabled) { p->enabled = !p_disabled; } -bool AStar::is_point_disabled(int p_id) const { +bool AStar3D::is_point_disabled(int p_id) const { Point *p; bool p_exists = points.lookup(p_id, p); ERR_FAIL_COND_V_MSG(!p_exists, false, vformat("Can't get if point is disabled. Point with id: %d doesn't exist.", p_id)); @@ -528,41 +528,41 @@ bool AStar::is_point_disabled(int p_id) const { return !p->enabled; } -void AStar::_bind_methods() { - ClassDB::bind_method(D_METHOD("get_available_point_id"), &AStar::get_available_point_id); - ClassDB::bind_method(D_METHOD("add_point", "id", "position", "weight_scale"), &AStar::add_point, DEFVAL(1.0)); - ClassDB::bind_method(D_METHOD("get_point_position", "id"), &AStar::get_point_position); - ClassDB::bind_method(D_METHOD("set_point_position", "id", "position"), &AStar::set_point_position); - ClassDB::bind_method(D_METHOD("get_point_weight_scale", "id"), &AStar::get_point_weight_scale); - ClassDB::bind_method(D_METHOD("set_point_weight_scale", "id", "weight_scale"), &AStar::set_point_weight_scale); - ClassDB::bind_method(D_METHOD("remove_point", "id"), &AStar::remove_point); - ClassDB::bind_method(D_METHOD("has_point", "id"), &AStar::has_point); - ClassDB::bind_method(D_METHOD("get_point_connections", "id"), &AStar::get_point_connections); - ClassDB::bind_method(D_METHOD("get_point_ids"), &AStar::get_point_ids); +void AStar3D::_bind_methods() { + ClassDB::bind_method(D_METHOD("get_available_point_id"), &AStar3D::get_available_point_id); + ClassDB::bind_method(D_METHOD("add_point", "id", "position", "weight_scale"), &AStar3D::add_point, DEFVAL(1.0)); + ClassDB::bind_method(D_METHOD("get_point_position", "id"), &AStar3D::get_point_position); + ClassDB::bind_method(D_METHOD("set_point_position", "id", "position"), &AStar3D::set_point_position); + ClassDB::bind_method(D_METHOD("get_point_weight_scale", "id"), &AStar3D::get_point_weight_scale); + ClassDB::bind_method(D_METHOD("set_point_weight_scale", "id", "weight_scale"), &AStar3D::set_point_weight_scale); + ClassDB::bind_method(D_METHOD("remove_point", "id"), &AStar3D::remove_point); + ClassDB::bind_method(D_METHOD("has_point", "id"), &AStar3D::has_point); + ClassDB::bind_method(D_METHOD("get_point_connections", "id"), &AStar3D::get_point_connections); + ClassDB::bind_method(D_METHOD("get_point_ids"), &AStar3D::get_point_ids); - ClassDB::bind_method(D_METHOD("set_point_disabled", "id", "disabled"), &AStar::set_point_disabled, DEFVAL(true)); - ClassDB::bind_method(D_METHOD("is_point_disabled", "id"), &AStar::is_point_disabled); + ClassDB::bind_method(D_METHOD("set_point_disabled", "id", "disabled"), &AStar3D::set_point_disabled, DEFVAL(true)); + ClassDB::bind_method(D_METHOD("is_point_disabled", "id"), &AStar3D::is_point_disabled); - ClassDB::bind_method(D_METHOD("connect_points", "id", "to_id", "bidirectional"), &AStar::connect_points, DEFVAL(true)); - ClassDB::bind_method(D_METHOD("disconnect_points", "id", "to_id", "bidirectional"), &AStar::disconnect_points, DEFVAL(true)); - ClassDB::bind_method(D_METHOD("are_points_connected", "id", "to_id", "bidirectional"), &AStar::are_points_connected, DEFVAL(true)); + ClassDB::bind_method(D_METHOD("connect_points", "id", "to_id", "bidirectional"), &AStar3D::connect_points, DEFVAL(true)); + ClassDB::bind_method(D_METHOD("disconnect_points", "id", "to_id", "bidirectional"), &AStar3D::disconnect_points, DEFVAL(true)); + ClassDB::bind_method(D_METHOD("are_points_connected", "id", "to_id", "bidirectional"), &AStar3D::are_points_connected, DEFVAL(true)); - ClassDB::bind_method(D_METHOD("get_point_count"), &AStar::get_point_count); - ClassDB::bind_method(D_METHOD("get_point_capacity"), &AStar::get_point_capacity); - ClassDB::bind_method(D_METHOD("reserve_space", "num_nodes"), &AStar::reserve_space); - ClassDB::bind_method(D_METHOD("clear"), &AStar::clear); + ClassDB::bind_method(D_METHOD("get_point_count"), &AStar3D::get_point_count); + ClassDB::bind_method(D_METHOD("get_point_capacity"), &AStar3D::get_point_capacity); + ClassDB::bind_method(D_METHOD("reserve_space", "num_nodes"), &AStar3D::reserve_space); + ClassDB::bind_method(D_METHOD("clear"), &AStar3D::clear); - ClassDB::bind_method(D_METHOD("get_closest_point", "to_position", "include_disabled"), &AStar::get_closest_point, DEFVAL(false)); - ClassDB::bind_method(D_METHOD("get_closest_position_in_segment", "to_position"), &AStar::get_closest_position_in_segment); + ClassDB::bind_method(D_METHOD("get_closest_point", "to_position", "include_disabled"), &AStar3D::get_closest_point, DEFVAL(false)); + ClassDB::bind_method(D_METHOD("get_closest_position_in_segment", "to_position"), &AStar3D::get_closest_position_in_segment); - ClassDB::bind_method(D_METHOD("get_point_path", "from_id", "to_id"), &AStar::get_point_path); - ClassDB::bind_method(D_METHOD("get_id_path", "from_id", "to_id"), &AStar::get_id_path); + ClassDB::bind_method(D_METHOD("get_point_path", "from_id", "to_id"), &AStar3D::get_point_path); + ClassDB::bind_method(D_METHOD("get_id_path", "from_id", "to_id"), &AStar3D::get_id_path); GDVIRTUAL_BIND(_estimate_cost, "from_id", "to_id") GDVIRTUAL_BIND(_compute_cost, "from_id", "to_id") } -AStar::~AStar() { +AStar3D::~AStar3D() { clear(); } @@ -660,11 +660,11 @@ real_t AStar2D::_estimate_cost(int p_from_id, int p_to_id) { return scost; } - AStar::Point *from_point; + AStar3D::Point *from_point; bool from_exists = astar.points.lookup(p_from_id, from_point); ERR_FAIL_COND_V_MSG(!from_exists, 0, vformat("Can't estimate cost. Point with id: %d doesn't exist.", p_from_id)); - AStar::Point *to_point; + AStar3D::Point *to_point; bool to_exists = astar.points.lookup(p_to_id, to_point); ERR_FAIL_COND_V_MSG(!to_exists, 0, vformat("Can't estimate cost. Point with id: %d doesn't exist.", p_to_id)); @@ -677,11 +677,11 @@ real_t AStar2D::_compute_cost(int p_from_id, int p_to_id) { return scost; } - AStar::Point *from_point; + AStar3D::Point *from_point; bool from_exists = astar.points.lookup(p_from_id, from_point); ERR_FAIL_COND_V_MSG(!from_exists, 0, vformat("Can't compute cost. Point with id: %d doesn't exist.", p_from_id)); - AStar::Point *to_point; + AStar3D::Point *to_point; bool to_exists = astar.points.lookup(p_to_id, to_point); ERR_FAIL_COND_V_MSG(!to_exists, 0, vformat("Can't compute cost. Point with id: %d doesn't exist.", p_to_id)); @@ -689,11 +689,11 @@ real_t AStar2D::_compute_cost(int p_from_id, int p_to_id) { } Vector<Vector2> AStar2D::get_point_path(int p_from_id, int p_to_id) { - AStar::Point *a; + AStar3D::Point *a; bool from_exists = astar.points.lookup(p_from_id, a); ERR_FAIL_COND_V_MSG(!from_exists, Vector<Vector2>(), vformat("Can't get point path. Point with id: %d doesn't exist.", p_from_id)); - AStar::Point *b; + AStar3D::Point *b; bool to_exists = astar.points.lookup(p_to_id, b); ERR_FAIL_COND_V_MSG(!to_exists, Vector<Vector2>(), vformat("Can't get point path. Point with id: %d doesn't exist.", p_to_id)); @@ -702,15 +702,15 @@ Vector<Vector2> AStar2D::get_point_path(int p_from_id, int p_to_id) { return ret; } - AStar::Point *begin_point = a; - AStar::Point *end_point = b; + AStar3D::Point *begin_point = a; + AStar3D::Point *end_point = b; bool found_route = _solve(begin_point, end_point); if (!found_route) { return Vector<Vector2>(); } - AStar::Point *p = end_point; + AStar3D::Point *p = end_point; int pc = 1; // Begin point while (p != begin_point) { pc++; @@ -723,7 +723,7 @@ Vector<Vector2> AStar2D::get_point_path(int p_from_id, int p_to_id) { { Vector2 *w = path.ptrw(); - AStar::Point *p2 = end_point; + AStar3D::Point *p2 = end_point; int idx = pc - 1; while (p2 != begin_point) { w[idx--] = Vector2(p2->pos.x, p2->pos.y); @@ -737,11 +737,11 @@ Vector<Vector2> AStar2D::get_point_path(int p_from_id, int p_to_id) { } Vector<int> AStar2D::get_id_path(int p_from_id, int p_to_id) { - AStar::Point *a; + AStar3D::Point *a; bool from_exists = astar.points.lookup(p_from_id, a); ERR_FAIL_COND_V_MSG(!from_exists, Vector<int>(), vformat("Can't get id path. Point with id: %d doesn't exist.", p_from_id)); - AStar::Point *b; + AStar3D::Point *b; bool to_exists = astar.points.lookup(p_to_id, b); ERR_FAIL_COND_V_MSG(!to_exists, Vector<int>(), vformat("Can't get id path. Point with id: %d doesn't exist.", p_to_id)); @@ -751,15 +751,15 @@ Vector<int> AStar2D::get_id_path(int p_from_id, int p_to_id) { return ret; } - AStar::Point *begin_point = a; - AStar::Point *end_point = b; + AStar3D::Point *begin_point = a; + AStar3D::Point *end_point = b; bool found_route = _solve(begin_point, end_point); if (!found_route) { return Vector<int>(); } - AStar::Point *p = end_point; + AStar3D::Point *p = end_point; int pc = 1; // Begin point while (p != begin_point) { pc++; @@ -785,7 +785,7 @@ Vector<int> AStar2D::get_id_path(int p_from_id, int p_to_id) { return path; } -bool AStar2D::_solve(AStar::Point *begin_point, AStar::Point *end_point) { +bool AStar2D::_solve(AStar3D::Point *begin_point, AStar3D::Point *end_point) { astar.pass++; if (!end_point->enabled) { @@ -794,15 +794,15 @@ bool AStar2D::_solve(AStar::Point *begin_point, AStar::Point *end_point) { bool found_route = false; - Vector<AStar::Point *> open_list; - SortArray<AStar::Point *, AStar::SortPoints> sorter; + Vector<AStar3D::Point *> open_list; + SortArray<AStar3D::Point *, AStar3D::SortPoints> sorter; begin_point->g_score = 0; begin_point->f_score = _estimate_cost(begin_point->id, end_point->id); open_list.push_back(begin_point); while (!open_list.is_empty()) { - AStar::Point *p = open_list[0]; // The currently processed point + AStar3D::Point *p = open_list[0]; // The currently processed point if (p == end_point) { found_route = true; @@ -813,8 +813,8 @@ bool AStar2D::_solve(AStar::Point *begin_point, AStar::Point *end_point) { open_list.remove_at(open_list.size() - 1); p->closed_pass = astar.pass; // Mark the point as closed - for (OAHashMap<int, AStar::Point *>::Iterator it = p->neighbours.iter(); it.valid; it = p->neighbours.next_iter(it)) { - AStar::Point *e = *(it.value); // The neighbour point + for (OAHashMap<int, AStar3D::Point *>::Iterator it = p->neighbours.iter(); it.valid; it = p->neighbours.next_iter(it)) { + AStar3D::Point *e = *(it.value); // The neighbour point if (!e->enabled || e->closed_pass == astar.pass) { continue; diff --git a/core/math/a_star.h b/core/math/a_star.h index 93e6c381f6..4d69822254 100644 --- a/core/math/a_star.h +++ b/core/math/a_star.h @@ -40,8 +40,8 @@ A* pathfinding algorithm. */ -class AStar : public RefCounted { - GDCLASS(AStar, RefCounted); +class AStar3D : public RefCounted { + GDCLASS(AStar3D, RefCounted); friend class AStar2D; struct Point { @@ -92,7 +92,10 @@ class AStar : public RefCounted { }; unsigned char direction = NONE; - bool operator<(const Segment &p_s) const { return key < p_s.key; } + static uint32_t hash(const Segment &p_seg) { + return hash_one_uint64(p_seg.key); + } + bool operator==(const Segment &p_s) const { return key == p_s.key; } Segment() {} Segment(int p_from, int p_to) { @@ -112,7 +115,7 @@ class AStar : public RefCounted { uint64_t pass = 1; OAHashMap<int, Point *> points; - Set<Segment> segments; + HashSet<Segment, Segment> segments; bool _solve(Point *begin_point, Point *end_point); @@ -156,15 +159,15 @@ public: Vector<Vector3> get_point_path(int p_from_id, int p_to_id); Vector<int> get_id_path(int p_from_id, int p_to_id); - AStar() {} - ~AStar(); + AStar3D() {} + ~AStar3D(); }; class AStar2D : public RefCounted { GDCLASS(AStar2D, RefCounted); - AStar astar; + AStar3D astar; - bool _solve(AStar::Point *begin_point, AStar::Point *end_point); + bool _solve(AStar3D::Point *begin_point, AStar3D::Point *end_point); protected: static void _bind_methods(); diff --git a/core/math/basis.cpp b/core/math/basis.cpp index 84f9d12bb1..65353d8118 100644 --- a/core/math/basis.cpp +++ b/core/math/basis.cpp @@ -34,32 +34,32 @@ #include "core/string/print_string.h" #define cofac(row1, col1, row2, col2) \ - (elements[row1][col1] * elements[row2][col2] - elements[row1][col2] * elements[row2][col1]) + (rows[row1][col1] * rows[row2][col2] - rows[row1][col2] * rows[row2][col1]) void Basis::from_z(const Vector3 &p_z) { if (Math::abs(p_z.z) > (real_t)Math_SQRT12) { // choose p in y-z plane real_t a = p_z[1] * p_z[1] + p_z[2] * p_z[2]; real_t k = 1.0f / Math::sqrt(a); - elements[0] = Vector3(0, -p_z[2] * k, p_z[1] * k); - elements[1] = Vector3(a * k, -p_z[0] * elements[0][2], p_z[0] * elements[0][1]); + rows[0] = Vector3(0, -p_z[2] * k, p_z[1] * k); + rows[1] = Vector3(a * k, -p_z[0] * rows[0][2], p_z[0] * rows[0][1]); } else { // choose p in x-y plane real_t a = p_z.x * p_z.x + p_z.y * p_z.y; real_t k = 1.0f / Math::sqrt(a); - elements[0] = Vector3(-p_z.y * k, p_z.x * k, 0); - elements[1] = Vector3(-p_z.z * elements[0].y, p_z.z * elements[0].x, a * k); + rows[0] = Vector3(-p_z.y * k, p_z.x * k, 0); + rows[1] = Vector3(-p_z.z * rows[0].y, p_z.z * rows[0].x, a * k); } - elements[2] = p_z; + rows[2] = p_z; } void Basis::invert() { real_t co[3] = { cofac(1, 1, 2, 2), cofac(1, 2, 2, 0), cofac(1, 0, 2, 1) }; - real_t det = elements[0][0] * co[0] + - elements[0][1] * co[1] + - elements[0][2] * co[2]; + real_t det = rows[0][0] * co[0] + + rows[0][1] * co[1] + + rows[0][2] * co[2]; #ifdef MATH_CHECKS ERR_FAIL_COND(det == 0); #endif @@ -73,9 +73,9 @@ void Basis::invert() { void Basis::orthonormalize() { // Gram-Schmidt Process - Vector3 x = get_axis(0); - Vector3 y = get_axis(1); - Vector3 z = get_axis(2); + Vector3 x = get_column(0); + Vector3 y = get_column(1); + Vector3 z = get_column(2); x.normalize(); y = (y - x * (x.dot(y))); @@ -83,9 +83,9 @@ void Basis::orthonormalize() { z = (z - x * (x.dot(z)) - y * (y.dot(z))); z.normalize(); - set_axis(0, x); - set_axis(1, y); - set_axis(2, z); + set_column(0, x); + set_column(1, y); + set_column(2, z); } Basis Basis::orthonormalized() const { @@ -115,9 +115,9 @@ bool Basis::is_orthogonal() const { bool Basis::is_diagonal() const { return ( - Math::is_zero_approx(elements[0][1]) && Math::is_zero_approx(elements[0][2]) && - Math::is_zero_approx(elements[1][0]) && Math::is_zero_approx(elements[1][2]) && - Math::is_zero_approx(elements[2][0]) && Math::is_zero_approx(elements[2][1])); + Math::is_zero_approx(rows[0][1]) && Math::is_zero_approx(rows[0][2]) && + Math::is_zero_approx(rows[1][0]) && Math::is_zero_approx(rows[1][2]) && + Math::is_zero_approx(rows[2][0]) && Math::is_zero_approx(rows[2][1])); } bool Basis::is_rotation() const { @@ -127,13 +127,13 @@ bool Basis::is_rotation() const { #ifdef MATH_CHECKS // This method is only used once, in diagonalize. If it's desired elsewhere, feel free to remove the #ifdef. bool Basis::is_symmetric() const { - if (!Math::is_equal_approx(elements[0][1], elements[1][0])) { + if (!Math::is_equal_approx(rows[0][1], rows[1][0])) { return false; } - if (!Math::is_equal_approx(elements[0][2], elements[2][0])) { + if (!Math::is_equal_approx(rows[0][2], rows[2][0])) { return false; } - if (!Math::is_equal_approx(elements[1][2], elements[2][1])) { + if (!Math::is_equal_approx(rows[1][2], rows[2][1])) { return false; } @@ -149,14 +149,14 @@ Basis Basis::diagonalize() { #endif const int ite_max = 1024; - real_t off_matrix_norm_2 = elements[0][1] * elements[0][1] + elements[0][2] * elements[0][2] + elements[1][2] * elements[1][2]; + real_t off_matrix_norm_2 = rows[0][1] * rows[0][1] + rows[0][2] * rows[0][2] + rows[1][2] * rows[1][2]; int ite = 0; Basis acc_rot; while (off_matrix_norm_2 > (real_t)CMP_EPSILON2 && ite++ < ite_max) { - real_t el01_2 = elements[0][1] * elements[0][1]; - real_t el02_2 = elements[0][2] * elements[0][2]; - real_t el12_2 = elements[1][2] * elements[1][2]; + real_t el01_2 = rows[0][1] * rows[0][1]; + real_t el02_2 = rows[0][2] * rows[0][2]; + real_t el12_2 = rows[1][2] * rows[1][2]; // Find the pivot element int i, j; if (el01_2 > el02_2) { @@ -179,19 +179,19 @@ Basis Basis::diagonalize() { // Compute the rotation angle real_t angle; - if (Math::is_equal_approx(elements[j][j], elements[i][i])) { + if (Math::is_equal_approx(rows[j][j], rows[i][i])) { angle = Math_PI / 4; } else { - angle = 0.5f * Math::atan(2 * elements[i][j] / (elements[j][j] - elements[i][i])); + angle = 0.5f * Math::atan(2 * rows[i][j] / (rows[j][j] - rows[i][i])); } // Compute the rotation matrix Basis rot; - rot.elements[i][i] = rot.elements[j][j] = Math::cos(angle); - rot.elements[i][j] = -(rot.elements[j][i] = Math::sin(angle)); + rot.rows[i][i] = rot.rows[j][j] = Math::cos(angle); + rot.rows[i][j] = -(rot.rows[j][i] = Math::sin(angle)); // Update the off matrix norm - off_matrix_norm_2 -= elements[i][j] * elements[i][j]; + off_matrix_norm_2 -= rows[i][j] * rows[i][j]; // Apply the rotation *this = rot * *this * rot.transposed(); @@ -208,9 +208,9 @@ Basis Basis::inverse() const { } void Basis::transpose() { - SWAP(elements[0][1], elements[1][0]); - SWAP(elements[0][2], elements[2][0]); - SWAP(elements[1][2], elements[2][1]); + SWAP(rows[0][1], rows[1][0]); + SWAP(rows[0][2], rows[2][0]); + SWAP(rows[1][2], rows[2][1]); } Basis Basis::transposed() const { @@ -226,15 +226,15 @@ Basis Basis::from_scale(const Vector3 &p_scale) { // Multiplies the matrix from left by the scaling matrix: M -> S.M // See the comment for Basis::rotated for further explanation. void Basis::scale(const Vector3 &p_scale) { - elements[0][0] *= p_scale.x; - elements[0][1] *= p_scale.x; - elements[0][2] *= p_scale.x; - elements[1][0] *= p_scale.y; - elements[1][1] *= p_scale.y; - elements[1][2] *= p_scale.y; - elements[2][0] *= p_scale.z; - elements[2][1] *= p_scale.z; - elements[2][2] *= p_scale.z; + rows[0][0] *= p_scale.x; + rows[0][1] *= p_scale.x; + rows[0][2] *= p_scale.x; + rows[1][0] *= p_scale.y; + rows[1][1] *= p_scale.y; + rows[1][2] *= p_scale.y; + rows[2][0] *= p_scale.z; + rows[2][1] *= p_scale.z; + rows[2][2] *= p_scale.z; } Basis Basis::scaled(const Vector3 &p_scale) const { @@ -260,7 +260,7 @@ Basis Basis::scaled_orthogonal(const Vector3 &p_scale) const { Basis b; for (int i = 0; i < 3; i++) { for (int j = 0; j < 3; j++) { - dots[j] += s[i] * abs(m.get_axis(i).normalized().dot(b.get_axis(j))); + dots[j] += s[i] * abs(m.get_column(i).normalized().dot(b.get_column(j))); } } m.scale_local(Vector3(1, 1, 1) + dots); @@ -268,14 +268,14 @@ Basis Basis::scaled_orthogonal(const Vector3 &p_scale) const { } float Basis::get_uniform_scale() const { - return (elements[0].length() + elements[1].length() + elements[2].length()) / 3.0f; + return (rows[0].length() + rows[1].length() + rows[2].length()) / 3.0f; } void Basis::make_scale_uniform() { - float l = (elements[0].length() + elements[1].length() + elements[2].length()) / 3.0f; + float l = (rows[0].length() + rows[1].length() + rows[2].length()) / 3.0f; for (int i = 0; i < 3; i++) { - elements[i].normalize(); - elements[i] *= l; + rows[i].normalize(); + rows[i] *= l; } } @@ -285,14 +285,14 @@ Basis Basis::scaled_local(const Vector3 &p_scale) const { Vector3 Basis::get_scale_abs() const { return Vector3( - Vector3(elements[0][0], elements[1][0], elements[2][0]).length(), - Vector3(elements[0][1], elements[1][1], elements[2][1]).length(), - Vector3(elements[0][2], elements[1][2], elements[2][2]).length()); + Vector3(rows[0][0], rows[1][0], rows[2][0]).length(), + Vector3(rows[0][1], rows[1][1], rows[2][1]).length(), + Vector3(rows[0][2], rows[1][2], rows[2][2]).length()); } Vector3 Basis::get_scale_local() const { real_t det_sign = SIGN(determinant()); - return det_sign * Vector3(elements[0].length(), elements[1].length(), elements[2].length()); + return det_sign * Vector3(rows[0].length(), rows[1].length(), rows[2].length()); } // get_scale works with get_rotation, use get_scale_abs if you need to enforce positive signature. @@ -347,22 +347,22 @@ Vector3 Basis::rotref_posscale_decomposition(Basis &rotref) const { // The main use of Basis is as Transform.basis, which is used by the transformation matrix // of 3D object. Rotate here refers to rotation of the object (which is R * (*this)), // not the matrix itself (which is R * (*this) * R.transposed()). -Basis Basis::rotated(const Vector3 &p_axis, real_t p_phi) const { - return Basis(p_axis, p_phi) * (*this); +Basis Basis::rotated(const Vector3 &p_axis, real_t p_angle) const { + return Basis(p_axis, p_angle) * (*this); } -void Basis::rotate(const Vector3 &p_axis, real_t p_phi) { - *this = rotated(p_axis, p_phi); +void Basis::rotate(const Vector3 &p_axis, real_t p_angle) { + *this = rotated(p_axis, p_angle); } -void Basis::rotate_local(const Vector3 &p_axis, real_t p_phi) { +void Basis::rotate_local(const Vector3 &p_axis, real_t p_angle) { // performs a rotation in object-local coordinate system: // M -> (M.R.Minv).M = M.R. - *this = rotated_local(p_axis, p_phi); + *this = rotated_local(p_axis, p_angle); } -Basis Basis::rotated_local(const Vector3 &p_axis, real_t p_phi) const { - return (*this) * Basis(p_axis, p_phi); +Basis Basis::rotated_local(const Vector3 &p_axis, real_t p_angle) const { + return (*this) * Basis(p_axis, p_angle); } Basis Basis::rotated(const Vector3 &p_euler) const { @@ -462,27 +462,27 @@ Vector3 Basis::get_euler(EulerOrder p_order) const { // -cx*cz*sy+sx*sz cz*sx+cx*sy*sz cx*cy Vector3 euler; - real_t sy = elements[0][2]; + real_t sy = rows[0][2]; if (sy < (1.0f - (real_t)CMP_EPSILON)) { if (sy > -(1.0f - (real_t)CMP_EPSILON)) { // is this a pure Y rotation? - if (elements[1][0] == 0 && elements[0][1] == 0 && elements[1][2] == 0 && elements[2][1] == 0 && elements[1][1] == 1) { + if (rows[1][0] == 0 && rows[0][1] == 0 && rows[1][2] == 0 && rows[2][1] == 0 && rows[1][1] == 1) { // return the simplest form (human friendlier in editor and scripts) euler.x = 0; - euler.y = atan2(elements[0][2], elements[0][0]); + euler.y = atan2(rows[0][2], rows[0][0]); euler.z = 0; } else { - euler.x = Math::atan2(-elements[1][2], elements[2][2]); + euler.x = Math::atan2(-rows[1][2], rows[2][2]); euler.y = Math::asin(sy); - euler.z = Math::atan2(-elements[0][1], elements[0][0]); + euler.z = Math::atan2(-rows[0][1], rows[0][0]); } } else { - euler.x = Math::atan2(elements[2][1], elements[1][1]); + euler.x = Math::atan2(rows[2][1], rows[1][1]); euler.y = -Math_PI / 2.0f; euler.z = 0.0f; } } else { - euler.x = Math::atan2(elements[2][1], elements[1][1]); + euler.x = Math::atan2(rows[2][1], rows[1][1]); euler.y = Math_PI / 2.0f; euler.z = 0.0f; } @@ -497,21 +497,21 @@ Vector3 Basis::get_euler(EulerOrder p_order) const { // cy*sx*sz cz*sx cx*cy+sx*sz*sy Vector3 euler; - real_t sz = elements[0][1]; + real_t sz = rows[0][1]; if (sz < (1.0f - (real_t)CMP_EPSILON)) { if (sz > -(1.0f - (real_t)CMP_EPSILON)) { - euler.x = Math::atan2(elements[2][1], elements[1][1]); - euler.y = Math::atan2(elements[0][2], elements[0][0]); + euler.x = Math::atan2(rows[2][1], rows[1][1]); + euler.y = Math::atan2(rows[0][2], rows[0][0]); euler.z = Math::asin(-sz); } else { // It's -1 - euler.x = -Math::atan2(elements[1][2], elements[2][2]); + euler.x = -Math::atan2(rows[1][2], rows[2][2]); euler.y = 0.0f; euler.z = Math_PI / 2.0f; } } else { // It's 1 - euler.x = -Math::atan2(elements[1][2], elements[2][2]); + euler.x = -Math::atan2(rows[1][2], rows[2][2]); euler.y = 0.0f; euler.z = -Math_PI / 2.0f; } @@ -527,29 +527,29 @@ Vector3 Basis::get_euler(EulerOrder p_order) const { Vector3 euler; - real_t m12 = elements[1][2]; + real_t m12 = rows[1][2]; if (m12 < (1 - (real_t)CMP_EPSILON)) { if (m12 > -(1 - (real_t)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) { + if (rows[1][0] == 0 && rows[0][1] == 0 && rows[0][2] == 0 && rows[2][0] == 0 && rows[0][0] == 1) { // return the simplest form (human friendlier in editor and scripts) - euler.x = atan2(-m12, elements[1][1]); + euler.x = atan2(-m12, rows[1][1]); euler.y = 0; euler.z = 0; } else { euler.x = asin(-m12); - euler.y = atan2(elements[0][2], elements[2][2]); - euler.z = atan2(elements[1][0], elements[1][1]); + euler.y = atan2(rows[0][2], rows[2][2]); + euler.z = atan2(rows[1][0], rows[1][1]); } } else { // m12 == -1 euler.x = Math_PI * 0.5f; - euler.y = atan2(elements[0][1], elements[0][0]); + euler.y = atan2(rows[0][1], rows[0][0]); euler.z = 0; } } else { // m12 == 1 euler.x = -Math_PI * 0.5f; - euler.y = -atan2(elements[0][1], elements[0][0]); + euler.y = -atan2(rows[0][1], rows[0][0]); euler.z = 0; } @@ -564,21 +564,21 @@ Vector3 Basis::get_euler(EulerOrder p_order) const { // -cz*sy cy*sx+cx*sy*sz cy*cx-sy*sz*sx Vector3 euler; - real_t sz = elements[1][0]; + real_t sz = rows[1][0]; if (sz < (1.0f - (real_t)CMP_EPSILON)) { if (sz > -(1.0f - (real_t)CMP_EPSILON)) { - euler.x = Math::atan2(-elements[1][2], elements[1][1]); - euler.y = Math::atan2(-elements[2][0], elements[0][0]); + euler.x = Math::atan2(-rows[1][2], rows[1][1]); + euler.y = Math::atan2(-rows[2][0], rows[0][0]); euler.z = Math::asin(sz); } else { // It's -1 - euler.x = Math::atan2(elements[2][1], elements[2][2]); + euler.x = Math::atan2(rows[2][1], rows[2][2]); euler.y = 0.0f; euler.z = -Math_PI / 2.0f; } } else { // It's 1 - euler.x = Math::atan2(elements[2][1], elements[2][2]); + euler.x = Math::atan2(rows[2][1], rows[2][2]); euler.y = 0.0f; euler.z = Math_PI / 2.0f; } @@ -592,22 +592,22 @@ Vector3 Basis::get_euler(EulerOrder p_order) const { // 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]; + real_t sx = rows[2][1]; if (sx < (1.0f - (real_t)CMP_EPSILON)) { if (sx > -(1.0f - (real_t)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]); + euler.y = Math::atan2(-rows[2][0], rows[2][2]); + euler.z = Math::atan2(-rows[0][1], rows[1][1]); } else { // It's -1 euler.x = -Math_PI / 2.0f; - euler.y = Math::atan2(elements[0][2], elements[0][0]); + euler.y = Math::atan2(rows[0][2], rows[0][0]); euler.z = 0; } } else { // It's 1 euler.x = Math_PI / 2.0f; - euler.y = Math::atan2(elements[0][2], elements[0][0]); + euler.y = Math::atan2(rows[0][2], rows[0][0]); euler.z = 0; } return euler; @@ -620,23 +620,23 @@ Vector3 Basis::get_euler(EulerOrder p_order) const { // 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]; + real_t sy = rows[2][0]; if (sy < (1.0f - (real_t)CMP_EPSILON)) { if (sy > -(1.0f - (real_t)CMP_EPSILON)) { - euler.x = Math::atan2(elements[2][1], elements[2][2]); + euler.x = Math::atan2(rows[2][1], rows[2][2]); euler.y = Math::asin(-sy); - euler.z = Math::atan2(elements[1][0], elements[0][0]); + euler.z = Math::atan2(rows[1][0], rows[0][0]); } else { // It's -1 euler.x = 0; euler.y = Math_PI / 2.0f; - euler.z = -Math::atan2(elements[0][1], elements[1][1]); + euler.z = -Math::atan2(rows[0][1], rows[1][1]); } } else { // It's 1 euler.x = 0; euler.y = -Math_PI / 2.0f; - euler.z = -Math::atan2(elements[0][1], elements[1][1]); + euler.z = -Math::atan2(rows[0][1], rows[1][1]); } return euler; } break; @@ -688,13 +688,13 @@ void Basis::set_euler(const Vector3 &p_euler, EulerOrder p_order) { } 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]); + return rows[0].is_equal_approx(p_basis.rows[0]) && rows[1].is_equal_approx(p_basis.rows[1]) && rows[2].is_equal_approx(p_basis.rows[2]); } bool Basis::operator==(const Basis &p_matrix) const { for (int i = 0; i < 3; i++) { for (int j = 0; j < 3; j++) { - if (elements[i][j] != p_matrix.elements[i][j]) { + if (rows[i][j] != p_matrix.rows[i][j]) { return false; } } @@ -708,9 +708,9 @@ bool Basis::operator!=(const Basis &p_matrix) const { } Basis::operator String() const { - return "[X: " + get_axis(0).operator String() + - ", Y: " + get_axis(1).operator String() + - ", Z: " + get_axis(2).operator String() + "]"; + return "[X: " + get_column(0).operator String() + + ", Y: " + get_column(1).operator String() + + ", Z: " + get_column(2).operator String() + "]"; } Quaternion Basis::get_quaternion() const { @@ -719,7 +719,7 @@ Quaternion Basis::get_quaternion() const { #endif /* Allow getting a quaternion from an unnormalized transform */ Basis m = *this; - real_t trace = m.elements[0][0] + m.elements[1][1] + m.elements[2][2]; + real_t trace = m.rows[0][0] + m.rows[1][1] + m.rows[2][2]; real_t temp[4]; if (trace > 0.0f) { @@ -727,23 +727,23 @@ Quaternion Basis::get_quaternion() const { temp[3] = (s * 0.5f); s = 0.5f / s; - temp[0] = ((m.elements[2][1] - m.elements[1][2]) * s); - temp[1] = ((m.elements[0][2] - m.elements[2][0]) * s); - temp[2] = ((m.elements[1][0] - m.elements[0][1]) * s); + temp[0] = ((m.rows[2][1] - m.rows[1][2]) * s); + temp[1] = ((m.rows[0][2] - m.rows[2][0]) * s); + temp[2] = ((m.rows[1][0] - m.rows[0][1]) * s); } else { - int i = m.elements[0][0] < m.elements[1][1] - ? (m.elements[1][1] < m.elements[2][2] ? 2 : 1) - : (m.elements[0][0] < m.elements[2][2] ? 2 : 0); + int i = m.rows[0][0] < m.rows[1][1] + ? (m.rows[1][1] < m.rows[2][2] ? 2 : 1) + : (m.rows[0][0] < m.rows[2][2] ? 2 : 0); int j = (i + 1) % 3; int k = (i + 2) % 3; - real_t s = Math::sqrt(m.elements[i][i] - m.elements[j][j] - m.elements[k][k] + 1.0f); + real_t s = Math::sqrt(m.rows[i][i] - m.rows[j][j] - m.rows[k][k] + 1.0f); temp[i] = s * 0.5f; s = 0.5f / s; - temp[3] = (m.elements[k][j] - m.elements[j][k]) * s; - temp[j] = (m.elements[j][i] + m.elements[i][j]) * s; - temp[k] = (m.elements[k][i] + m.elements[i][k]) * s; + temp[3] = (m.rows[k][j] - m.rows[j][k]) * s; + temp[j] = (m.rows[j][i] + m.rows[i][j]) * s; + temp[k] = (m.rows[k][i] + m.rows[i][k]) * s; } return Quaternion(temp[0], temp[1], temp[2], temp[3]); @@ -820,11 +820,11 @@ void Basis::get_axis_angle(Vector3 &r_axis, real_t &r_angle) const { real_t epsilon = 0.01; // margin to allow for rounding errors real_t epsilon2 = 0.1; // margin to distinguish between 0 and 180 degrees - if ((Math::abs(elements[1][0] - elements[0][1]) < epsilon) && (Math::abs(elements[2][0] - elements[0][2]) < epsilon) && (Math::abs(elements[2][1] - elements[1][2]) < epsilon)) { + if ((Math::abs(rows[1][0] - rows[0][1]) < epsilon) && (Math::abs(rows[2][0] - rows[0][2]) < epsilon) && (Math::abs(rows[2][1] - rows[1][2]) < 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(elements[1][0] + elements[0][1]) < epsilon2) && (Math::abs(elements[2][0] + elements[0][2]) < epsilon2) && (Math::abs(elements[2][1] + elements[1][2]) < epsilon2) && (Math::abs(elements[0][0] + elements[1][1] + elements[2][2] - 3) < epsilon2)) { + if ((Math::abs(rows[1][0] + rows[0][1]) < epsilon2) && (Math::abs(rows[2][0] + rows[0][2]) < epsilon2) && (Math::abs(rows[2][1] + rows[1][2]) < epsilon2) && (Math::abs(rows[0][0] + rows[1][1] + rows[2][2] - 3) < epsilon2)) { // this singularity is identity matrix so angle = 0 r_axis = Vector3(0, 1, 0); r_angle = 0; @@ -832,13 +832,13 @@ void Basis::get_axis_angle(Vector3 &r_axis, real_t &r_angle) const { } // otherwise this singularity is angle = 180 angle = Math_PI; - real_t xx = (elements[0][0] + 1) / 2; - real_t yy = (elements[1][1] + 1) / 2; - real_t zz = (elements[2][2] + 1) / 2; - real_t xy = (elements[1][0] + elements[0][1]) / 4; - real_t xz = (elements[2][0] + elements[0][2]) / 4; - real_t yz = (elements[2][1] + elements[1][2]) / 4; - if ((xx > yy) && (xx > zz)) { // elements[0][0] is the largest diagonal term + 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 if (xx < epsilon) { x = 0; y = Math_SQRT12; @@ -848,7 +848,7 @@ void Basis::get_axis_angle(Vector3 &r_axis, real_t &r_angle) const { y = xy / x; z = xz / x; } - } else if (yy > zz) { // elements[1][1] is the largest diagonal term + } else if (yy > zz) { // rows[1][1] is the largest diagonal term if (yy < epsilon) { x = Math_SQRT12; y = 0; @@ -858,7 +858,7 @@ void Basis::get_axis_angle(Vector3 &r_axis, real_t &r_angle) const { x = xy / y; z = yz / y; } - } else { // elements[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 < epsilon) { x = Math_SQRT12; y = Math_SQRT12; @@ -874,15 +874,15 @@ void Basis::get_axis_angle(Vector3 &r_axis, real_t &r_angle) const { return; } // as we have reached here there are no singularities so we can handle normally - real_t s = Math::sqrt((elements[1][2] - elements[2][1]) * (elements[1][2] - elements[2][1]) + (elements[2][0] - elements[0][2]) * (elements[2][0] - elements[0][2]) + (elements[0][1] - elements[1][0]) * (elements[0][1] - elements[1][0])); // s=|axis||sin(angle)|, used to normalise + 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 - angle = Math::acos((elements[0][0] + elements[1][1] + elements[2][2] - 1) / 2); + angle = Math::acos((rows[0][0] + rows[1][1] + rows[2][2] - 1) / 2); if (angle < 0) { s = -s; } - x = (elements[2][1] - elements[1][2]) / s; - y = (elements[0][2] - elements[2][0]) / s; - z = (elements[1][0] - elements[0][1]) / s; + 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; @@ -900,39 +900,39 @@ void Basis::set_quaternion(const Quaternion &p_quaternion) { xz - wy, yz + wx, 1.0f - (xx + yy)); } -void Basis::set_axis_angle(const Vector3 &p_axis, real_t p_phi) { +void Basis::set_axis_angle(const Vector3 &p_axis, real_t p_angle) { // Rotation matrix from axis and angle, see https://en.wikipedia.org/wiki/Rotation_matrix#Rotation_matrix_from_axis_angle #ifdef MATH_CHECKS ERR_FAIL_COND_MSG(!p_axis.is_normalized(), "The axis Vector3 must be normalized."); #endif Vector3 axis_sq(p_axis.x * p_axis.x, p_axis.y * p_axis.y, p_axis.z * p_axis.z); - real_t cosine = Math::cos(p_phi); - elements[0][0] = axis_sq.x + cosine * (1.0f - axis_sq.x); - elements[1][1] = axis_sq.y + cosine * (1.0f - axis_sq.y); - elements[2][2] = axis_sq.z + cosine * (1.0f - axis_sq.z); + real_t cosine = Math::cos(p_angle); + rows[0][0] = axis_sq.x + cosine * (1.0f - axis_sq.x); + rows[1][1] = axis_sq.y + cosine * (1.0f - axis_sq.y); + rows[2][2] = axis_sq.z + cosine * (1.0f - axis_sq.z); - real_t sine = Math::sin(p_phi); + real_t sine = Math::sin(p_angle); real_t t = 1 - cosine; real_t xyzt = p_axis.x * p_axis.y * t; real_t zyxs = p_axis.z * sine; - elements[0][1] = xyzt - zyxs; - elements[1][0] = xyzt + zyxs; + rows[0][1] = xyzt - zyxs; + rows[1][0] = xyzt + zyxs; xyzt = p_axis.x * p_axis.z * t; zyxs = p_axis.y * sine; - elements[0][2] = xyzt + zyxs; - elements[2][0] = xyzt - zyxs; + rows[0][2] = xyzt + zyxs; + rows[2][0] = xyzt - zyxs; xyzt = p_axis.y * p_axis.z * t; zyxs = p_axis.x * sine; - elements[1][2] = xyzt - zyxs; - elements[2][1] = xyzt + zyxs; + rows[1][2] = xyzt - zyxs; + rows[2][1] = xyzt + zyxs; } -void Basis::set_axis_angle_scale(const Vector3 &p_axis, real_t p_phi, const Vector3 &p_scale) { +void Basis::set_axis_angle_scale(const Vector3 &p_axis, real_t p_angle, const Vector3 &p_scale) { _set_diagonal(p_scale); - rotate(p_axis, p_phi); + rotate(p_axis, p_angle); } void Basis::set_euler_scale(const Vector3 &p_euler, const Vector3 &p_scale) { @@ -948,24 +948,24 @@ void Basis::set_quaternion_scale(const Quaternion &p_quaternion, const Vector3 & // This also sets the non-diagonal elements to 0, which is misleading from the // name, so we want this method to be private. Use `from_scale` externally. void Basis::_set_diagonal(const Vector3 &p_diag) { - elements[0][0] = p_diag.x; - elements[0][1] = 0; - elements[0][2] = 0; + rows[0][0] = p_diag.x; + rows[0][1] = 0; + rows[0][2] = 0; - elements[1][0] = 0; - elements[1][1] = p_diag.y; - elements[1][2] = 0; + rows[1][0] = 0; + rows[1][1] = p_diag.y; + rows[1][2] = 0; - elements[2][0] = 0; - elements[2][1] = 0; - elements[2][2] = p_diag.z; + rows[2][0] = 0; + rows[2][1] = 0; + rows[2][2] = p_diag.z; } Basis Basis::lerp(const Basis &p_to, const real_t &p_weight) const { Basis b; - b.elements[0] = elements[0].lerp(p_to.elements[0], p_weight); - b.elements[1] = elements[1].lerp(p_to.elements[1], p_weight); - b.elements[2] = elements[2].lerp(p_to.elements[2], p_weight); + b.rows[0] = rows[0].lerp(p_to.rows[0], p_weight); + b.rows[1] = rows[1].lerp(p_to.rows[1], p_weight); + b.rows[2] = rows[2].lerp(p_to.rows[2], p_weight); return b; } @@ -976,9 +976,9 @@ Basis Basis::slerp(const Basis &p_to, const real_t &p_weight) const { Quaternion to(p_to); Basis b(from.slerp(to, p_weight)); - b.elements[0] *= Math::lerp(elements[0].length(), p_to.elements[0].length(), p_weight); - b.elements[1] *= Math::lerp(elements[1].length(), p_to.elements[1].length(), p_weight); - b.elements[2] *= Math::lerp(elements[2].length(), p_to.elements[2].length(), p_weight); + b.rows[0] *= Math::lerp(rows[0].length(), p_to.rows[0].length(), p_weight); + b.rows[1] *= Math::lerp(rows[1].length(), p_to.rows[1].length(), p_weight); + b.rows[2] *= Math::lerp(rows[2].length(), p_to.rows[2].length(), p_weight); return b; } @@ -1002,17 +1002,17 @@ void Basis::rotate_sh(real_t *p_values) { const static real_t s_scale_dst2 = s_c3 * s_c_scale_inv; const static real_t s_scale_dst4 = s_c5 * s_c_scale_inv; - real_t src[9] = { p_values[0], p_values[1], p_values[2], p_values[3], p_values[4], p_values[5], p_values[6], p_values[7], p_values[8] }; + const real_t src[9] = { p_values[0], p_values[1], p_values[2], p_values[3], p_values[4], p_values[5], p_values[6], p_values[7], p_values[8] }; - real_t m00 = elements[0][0]; - real_t m01 = elements[0][1]; - real_t m02 = elements[0][2]; - real_t m10 = elements[1][0]; - real_t m11 = elements[1][1]; - real_t m12 = elements[1][2]; - real_t m20 = elements[2][0]; - real_t m21 = elements[2][1]; - real_t m22 = elements[2][2]; + real_t m00 = rows[0][0]; + real_t m01 = rows[0][1]; + real_t m02 = rows[0][2]; + real_t m10 = rows[1][0]; + real_t m11 = rows[1][1]; + real_t m12 = rows[1][2]; + real_t m20 = rows[2][0]; + real_t m21 = rows[2][1]; + real_t m22 = rows[2][2]; p_values[0] = src[0]; p_values[1] = m11 * src[1] - m12 * src[2] + m10 * src[3]; @@ -1107,6 +1107,6 @@ Basis Basis::looking_at(const Vector3 &p_target, const Vector3 &p_up) { Vector3 v_y = v_z.cross(v_x); Basis basis; - basis.set(v_x, v_y, v_z); + basis.set_columns(v_x, v_y, v_z); return basis; } diff --git a/core/math/basis.h b/core/math/basis.h index 683f05150c..9cce22510b 100644 --- a/core/math/basis.h +++ b/core/math/basis.h @@ -35,17 +35,17 @@ #include "core/math/vector3.h" struct _NO_DISCARD_ Basis { - Vector3 elements[3] = { + Vector3 rows[3] = { Vector3(1, 0, 0), Vector3(0, 1, 0), Vector3(0, 0, 1) }; _FORCE_INLINE_ const Vector3 &operator[](int axis) const { - return elements[axis]; + return rows[axis]; } _FORCE_INLINE_ Vector3 &operator[](int axis) { - return elements[axis]; + return rows[axis]; } void invert(); @@ -58,22 +58,11 @@ struct _NO_DISCARD_ Basis { void from_z(const Vector3 &p_z); - _FORCE_INLINE_ Vector3 get_axis(int p_axis) const { - // get actual basis axis (elements is transposed for performance) - return Vector3(elements[0][p_axis], elements[1][p_axis], elements[2][p_axis]); - } - _FORCE_INLINE_ void set_axis(int p_axis, const Vector3 &p_value) { - // get actual basis axis (elements is transposed for performance) - elements[0][p_axis] = p_value.x; - elements[1][p_axis] = p_value.y; - elements[2][p_axis] = p_value.z; - } + void rotate(const Vector3 &p_axis, real_t p_angle); + Basis rotated(const Vector3 &p_axis, real_t p_angle) const; - void rotate(const Vector3 &p_axis, real_t p_phi); - Basis rotated(const Vector3 &p_axis, real_t p_phi) const; - - void rotate_local(const Vector3 &p_axis, real_t p_phi); - Basis rotated_local(const Vector3 &p_axis, real_t p_phi) const; + void rotate_local(const Vector3 &p_axis, real_t p_angle); + Basis rotated_local(const Vector3 &p_axis, real_t p_angle) const; void rotate(const Vector3 &p_euler); Basis rotated(const Vector3 &p_euler) const; @@ -111,7 +100,7 @@ struct _NO_DISCARD_ Basis { void set_quaternion(const Quaternion &p_quaternion); void get_axis_angle(Vector3 &r_axis, real_t &r_angle) const; - void set_axis_angle(const Vector3 &p_axis, real_t p_phi); + void set_axis_angle(const Vector3 &p_axis, real_t p_angle); void scale(const Vector3 &p_scale); Basis scaled(const Vector3 &p_scale) const; @@ -129,19 +118,19 @@ struct _NO_DISCARD_ Basis { Vector3 get_scale_abs() const; Vector3 get_scale_local() const; - void set_axis_angle_scale(const Vector3 &p_axis, real_t p_phi, const Vector3 &p_scale); + void set_axis_angle_scale(const Vector3 &p_axis, real_t p_angle, const Vector3 &p_scale); void set_euler_scale(const Vector3 &p_euler, const Vector3 &p_scale); void set_quaternion_scale(const Quaternion &p_quaternion, const Vector3 &p_scale); // transposed dot products _FORCE_INLINE_ real_t tdotx(const Vector3 &v) const { - return elements[0][0] * v[0] + elements[1][0] * v[1] + elements[2][0] * v[2]; + return rows[0][0] * v[0] + rows[1][0] * v[1] + rows[2][0] * v[2]; } _FORCE_INLINE_ real_t tdoty(const Vector3 &v) const { - return elements[0][1] * v[0] + elements[1][1] * v[1] + elements[2][1] * v[2]; + return rows[0][1] * v[0] + rows[1][1] * v[1] + rows[2][1] * v[2]; } _FORCE_INLINE_ real_t tdotz(const Vector3 &v) const { - return elements[0][2] * v[0] + elements[1][2] * v[1] + elements[2][2] * v[2]; + return rows[0][2] * v[0] + rows[1][2] * v[1] + rows[2][2] * v[2]; } bool is_equal_approx(const Basis &p_basis) const; @@ -176,55 +165,55 @@ struct _NO_DISCARD_ Basis { /* create / set */ _FORCE_INLINE_ void set(real_t xx, real_t xy, real_t xz, real_t yx, real_t yy, real_t yz, real_t zx, real_t zy, real_t zz) { - elements[0][0] = xx; - elements[0][1] = xy; - elements[0][2] = xz; - elements[1][0] = yx; - elements[1][1] = yy; - elements[1][2] = yz; - elements[2][0] = zx; - elements[2][1] = zy; - elements[2][2] = zz; - } - _FORCE_INLINE_ void set(const Vector3 &p_x, const Vector3 &p_y, const Vector3 &p_z) { - set_axis(0, p_x); - set_axis(1, p_y); - set_axis(2, p_z); + rows[0][0] = xx; + rows[0][1] = xy; + rows[0][2] = xz; + rows[1][0] = yx; + rows[1][1] = yy; + rows[1][2] = yz; + rows[2][0] = zx; + rows[2][1] = zy; + rows[2][2] = zz; } - _FORCE_INLINE_ Vector3 get_column(int i) const { - return Vector3(elements[0][i], elements[1][i], elements[2][i]); + _FORCE_INLINE_ void set_columns(const Vector3 &p_x, const Vector3 &p_y, const Vector3 &p_z) { + set_column(0, p_x); + set_column(1, p_y); + set_column(2, p_z); } - _FORCE_INLINE_ Vector3 get_row(int i) const { - return Vector3(elements[i][0], elements[i][1], elements[i][2]); + _FORCE_INLINE_ Vector3 get_column(int p_index) const { + // Get actual basis axis column (we store transposed as rows for performance). + return Vector3(rows[0][p_index], rows[1][p_index], rows[2][p_index]); } - _FORCE_INLINE_ Vector3 get_main_diagonal() const { - return Vector3(elements[0][0], elements[1][1], elements[2][2]); + + _FORCE_INLINE_ void set_column(int p_index, const Vector3 &p_value) { + // Set actual basis axis column (we store transposed as rows for performance). + rows[0][p_index] = p_value.x; + rows[1][p_index] = p_value.y; + rows[2][p_index] = p_value.z; } - _FORCE_INLINE_ void set_row(int i, const Vector3 &p_row) { - elements[i][0] = p_row.x; - elements[i][1] = p_row.y; - elements[i][2] = p_row.z; + _FORCE_INLINE_ Vector3 get_main_diagonal() const { + return Vector3(rows[0][0], rows[1][1], rows[2][2]); } _FORCE_INLINE_ void set_zero() { - elements[0].zero(); - elements[1].zero(); - elements[2].zero(); + rows[0].zero(); + rows[1].zero(); + rows[2].zero(); } _FORCE_INLINE_ Basis transpose_xform(const Basis &m) const { return Basis( - elements[0].x * m[0].x + elements[1].x * m[1].x + elements[2].x * m[2].x, - elements[0].x * m[0].y + elements[1].x * m[1].y + elements[2].x * m[2].y, - elements[0].x * m[0].z + elements[1].x * m[1].z + elements[2].x * m[2].z, - elements[0].y * m[0].x + elements[1].y * m[1].x + elements[2].y * m[2].x, - elements[0].y * m[0].y + elements[1].y * m[1].y + elements[2].y * m[2].y, - elements[0].y * m[0].z + elements[1].y * m[1].z + elements[2].y * m[2].z, - elements[0].z * m[0].x + elements[1].z * m[1].x + elements[2].z * m[2].x, - elements[0].z * m[0].y + elements[1].z * m[1].y + elements[2].z * m[2].y, - elements[0].z * m[0].z + elements[1].z * m[1].z + elements[2].z * m[2].z); + rows[0].x * m[0].x + rows[1].x * m[1].x + rows[2].x * m[2].x, + rows[0].x * m[0].y + rows[1].x * m[1].y + rows[2].x * m[2].y, + rows[0].x * m[0].z + rows[1].x * m[1].z + rows[2].x * m[2].z, + rows[0].y * m[0].x + rows[1].y * m[1].x + rows[2].y * m[2].x, + rows[0].y * m[0].y + rows[1].y * m[1].y + rows[2].y * m[2].y, + rows[0].y * m[0].z + rows[1].y * m[1].z + rows[2].y * m[2].z, + rows[0].z * m[0].x + rows[1].z * m[1].x + rows[2].z * m[2].x, + rows[0].z * m[0].y + rows[1].z * m[1].y + rows[2].z * m[2].y, + rows[0].z * m[0].z + rows[1].z * m[1].z + rows[2].z * m[2].z); } Basis(real_t xx, real_t xy, real_t xz, real_t yx, real_t yy, real_t yz, real_t zx, real_t zy, real_t zz) { set(xx, xy, xz, yx, yy, yz, zx, zy, zz); @@ -248,14 +237,14 @@ struct _NO_DISCARD_ Basis { Basis(const Quaternion &p_quaternion) { set_quaternion(p_quaternion); }; Basis(const Quaternion &p_quaternion, const Vector3 &p_scale) { set_quaternion_scale(p_quaternion, p_scale); } - Basis(const Vector3 &p_axis, real_t p_phi) { set_axis_angle(p_axis, p_phi); } - Basis(const Vector3 &p_axis, real_t p_phi, const Vector3 &p_scale) { set_axis_angle_scale(p_axis, p_phi, p_scale); } + Basis(const Vector3 &p_axis, real_t p_angle) { set_axis_angle(p_axis, p_angle); } + 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) { - elements[0] = row0; - elements[1] = row1; - elements[2] = row2; + rows[0] = row0; + rows[1] = row1; + rows[2] = row2; } _FORCE_INLINE_ Basis() {} @@ -267,22 +256,22 @@ private: _FORCE_INLINE_ void Basis::operator*=(const Basis &p_matrix) { set( - p_matrix.tdotx(elements[0]), p_matrix.tdoty(elements[0]), p_matrix.tdotz(elements[0]), - p_matrix.tdotx(elements[1]), p_matrix.tdoty(elements[1]), p_matrix.tdotz(elements[1]), - p_matrix.tdotx(elements[2]), p_matrix.tdoty(elements[2]), p_matrix.tdotz(elements[2])); + p_matrix.tdotx(rows[0]), p_matrix.tdoty(rows[0]), p_matrix.tdotz(rows[0]), + p_matrix.tdotx(rows[1]), p_matrix.tdoty(rows[1]), p_matrix.tdotz(rows[1]), + p_matrix.tdotx(rows[2]), p_matrix.tdoty(rows[2]), p_matrix.tdotz(rows[2])); } _FORCE_INLINE_ Basis Basis::operator*(const Basis &p_matrix) const { return Basis( - p_matrix.tdotx(elements[0]), p_matrix.tdoty(elements[0]), p_matrix.tdotz(elements[0]), - p_matrix.tdotx(elements[1]), p_matrix.tdoty(elements[1]), p_matrix.tdotz(elements[1]), - p_matrix.tdotx(elements[2]), p_matrix.tdoty(elements[2]), p_matrix.tdotz(elements[2])); + p_matrix.tdotx(rows[0]), p_matrix.tdoty(rows[0]), p_matrix.tdotz(rows[0]), + p_matrix.tdotx(rows[1]), p_matrix.tdoty(rows[1]), p_matrix.tdotz(rows[1]), + p_matrix.tdotx(rows[2]), p_matrix.tdoty(rows[2]), p_matrix.tdotz(rows[2])); } _FORCE_INLINE_ void Basis::operator+=(const Basis &p_matrix) { - elements[0] += p_matrix.elements[0]; - elements[1] += p_matrix.elements[1]; - elements[2] += p_matrix.elements[2]; + rows[0] += p_matrix.rows[0]; + rows[1] += p_matrix.rows[1]; + rows[2] += p_matrix.rows[2]; } _FORCE_INLINE_ Basis Basis::operator+(const Basis &p_matrix) const { @@ -292,9 +281,9 @@ _FORCE_INLINE_ Basis Basis::operator+(const Basis &p_matrix) const { } _FORCE_INLINE_ void Basis::operator-=(const Basis &p_matrix) { - elements[0] -= p_matrix.elements[0]; - elements[1] -= p_matrix.elements[1]; - elements[2] -= p_matrix.elements[2]; + rows[0] -= p_matrix.rows[0]; + rows[1] -= p_matrix.rows[1]; + rows[2] -= p_matrix.rows[2]; } _FORCE_INLINE_ Basis Basis::operator-(const Basis &p_matrix) const { @@ -304,9 +293,9 @@ _FORCE_INLINE_ Basis Basis::operator-(const Basis &p_matrix) const { } _FORCE_INLINE_ void Basis::operator*=(const real_t p_val) { - elements[0] *= p_val; - elements[1] *= p_val; - elements[2] *= p_val; + rows[0] *= p_val; + rows[1] *= p_val; + rows[2] *= p_val; } _FORCE_INLINE_ Basis Basis::operator*(const real_t p_val) const { @@ -317,22 +306,22 @@ _FORCE_INLINE_ Basis Basis::operator*(const real_t p_val) const { Vector3 Basis::xform(const Vector3 &p_vector) const { return Vector3( - elements[0].dot(p_vector), - elements[1].dot(p_vector), - elements[2].dot(p_vector)); + rows[0].dot(p_vector), + rows[1].dot(p_vector), + rows[2].dot(p_vector)); } Vector3 Basis::xform_inv(const Vector3 &p_vector) const { return Vector3( - (elements[0][0] * p_vector.x) + (elements[1][0] * p_vector.y) + (elements[2][0] * p_vector.z), - (elements[0][1] * p_vector.x) + (elements[1][1] * p_vector.y) + (elements[2][1] * p_vector.z), - (elements[0][2] * p_vector.x) + (elements[1][2] * p_vector.y) + (elements[2][2] * p_vector.z)); + (rows[0][0] * p_vector.x) + (rows[1][0] * p_vector.y) + (rows[2][0] * p_vector.z), + (rows[0][1] * p_vector.x) + (rows[1][1] * p_vector.y) + (rows[2][1] * p_vector.z), + (rows[0][2] * p_vector.x) + (rows[1][2] * p_vector.y) + (rows[2][2] * p_vector.z)); } real_t Basis::determinant() const { - return elements[0][0] * (elements[1][1] * elements[2][2] - elements[2][1] * elements[1][2]) - - elements[1][0] * (elements[0][1] * elements[2][2] - elements[2][1] * elements[0][2]) + - elements[2][0] * (elements[0][1] * elements[1][2] - elements[1][1] * elements[0][2]); + return rows[0][0] * (rows[1][1] * rows[2][2] - rows[2][1] * rows[1][2]) - + rows[1][0] * (rows[0][1] * rows[2][2] - rows[2][1] * rows[0][2]) + + rows[2][0] * (rows[0][1] * rows[1][2] - rows[1][1] * rows[0][2]); } #endif // BASIS_H diff --git a/core/math/bvh.h b/core/math/bvh.h index a8e3cc7bbe..9f6ab9f736 100644 --- a/core/math/bvh.h +++ b/core/math/bvh.h @@ -46,21 +46,35 @@ // Layer masks are implemented in the renderers as a later step, and light_cull_mask appears to be // implemented in GLES3 but not GLES2. Layer masks are not yet implemented for directional lights. +// In the physics, the pairable_type is based on 1 << p_object->get_type() where: +// TYPE_AREA, +// TYPE_BODY +// and pairable_mask is either 0 if static, or set to all if non static + #include "bvh_tree.h" +#include "core/os/mutex.h" -#define BVHTREE_CLASS BVH_Tree<T, 2, MAX_ITEMS, USE_PAIRS, Bounds, Point> +#define BVHTREE_CLASS BVH_Tree<T, NUM_TREES, 2, MAX_ITEMS, USER_PAIR_TEST_FUNCTION, USER_CULL_TEST_FUNCTION, USE_PAIRS, BOUNDS, POINT> +#define BVH_LOCKED_FUNCTION BVHLockedFunction(&_mutex, BVH_THREAD_SAFE &&_thread_safe); -template <class T, bool USE_PAIRS = false, int MAX_ITEMS = 32, class Bounds = AABB, class Point = Vector3> +template <class T, int NUM_TREES = 1, bool USE_PAIRS = false, int MAX_ITEMS = 32, class USER_PAIR_TEST_FUNCTION = BVH_DummyPairTestFunction<T>, class USER_CULL_TEST_FUNCTION = BVH_DummyCullTestFunction<T>, class BOUNDS = AABB, class POINT = Vector3, bool BVH_THREAD_SAFE = true> class BVH_Manager { public: // note we are using uint32_t instead of BVHHandle, losing type safety, but this // is for compatibility with octree typedef void *(*PairCallback)(void *, uint32_t, T *, int, uint32_t, T *, int); typedef void (*UnpairCallback)(void *, uint32_t, T *, int, uint32_t, T *, int, void *); + typedef void *(*CheckPairCallback)(void *, uint32_t, T *, int, uint32_t, T *, int, void *); + + // allow locally toggling thread safety if the template has been compiled with BVH_THREAD_SAFE + void params_set_thread_safe(bool p_enable) { + _thread_safe = p_enable; + } // these 2 are crucial for fine tuning, and can be applied manually // see the variable declarations for more info. void params_set_node_expansion(real_t p_value) { + BVH_LOCKED_FUNCTION if (p_value >= 0.0) { tree._node_expansion = p_value; tree._auto_node_expansion = false; @@ -70,43 +84,40 @@ public: } void params_set_pairing_expansion(real_t p_value) { - if (p_value >= 0.0) { - tree._pairing_expansion = p_value; - tree._auto_pairing_expansion = false; - } else { - tree._auto_pairing_expansion = true; - } + BVH_LOCKED_FUNCTION + tree.params_set_pairing_expansion(p_value); } void set_pair_callback(PairCallback p_callback, void *p_userdata) { + BVH_LOCKED_FUNCTION pair_callback = p_callback; pair_callback_userdata = p_userdata; } void set_unpair_callback(UnpairCallback p_callback, void *p_userdata) { + BVH_LOCKED_FUNCTION unpair_callback = p_callback; unpair_callback_userdata = p_userdata; } + void set_check_pair_callback(CheckPairCallback p_callback, void *p_userdata) { + BVH_LOCKED_FUNCTION + check_pair_callback = p_callback; + check_pair_callback_userdata = p_userdata; + } + + BVHHandle create(T *p_userdata, bool p_active = true, uint32_t p_tree_id = 0, uint32_t p_tree_collision_mask = 1, const BOUNDS &p_aabb = BOUNDS(), int p_subindex = 0) { + BVH_LOCKED_FUNCTION - BVHHandle create(T *p_userdata, bool p_active, const Bounds &p_aabb = Bounds(), int p_subindex = 0, bool p_pairable = false, uint32_t p_pairable_type = 0, uint32_t p_pairable_mask = 1) { // not sure if absolutely necessary to flush collisions here. It will cost performance to, instead // of waiting for update, so only uncomment this if there are bugs. if (USE_PAIRS) { //_check_for_collisions(); } -#ifdef TOOLS_ENABLED - if (!USE_PAIRS) { - if (p_pairable) { - WARN_PRINT_ONCE("creating pairable item in BVH with USE_PAIRS set to false"); - } - } -#endif - - BVHHandle h = tree.item_add(p_userdata, p_active, p_aabb, p_subindex, p_pairable, p_pairable_type, p_pairable_mask); + BVHHandle h = tree.item_add(p_userdata, p_active, p_aabb, p_subindex, p_tree_id, p_tree_collision_mask); if (USE_PAIRS) { // for safety initialize the expanded AABB - Bounds &expanded_aabb = tree._pairs[h.id()].expanded_aabb; + BOUNDS &expanded_aabb = tree._pairs[h.id()].expanded_aabb; expanded_aabb = p_aabb; expanded_aabb.grow_by(tree._pairing_expansion); @@ -123,12 +134,18 @@ public: //////////////////////////////////////////////////// // wrapper versions that use uint32_t instead of handle // for backward compatibility. Less type safe - void move(uint32_t p_handle, const Bounds &p_aabb) { + void move(uint32_t p_handle, const BOUNDS &p_aabb) { BVHHandle h; h.set(p_handle); move(h, p_aabb); } + void recheck_pairs(uint32_t p_handle) { + BVHHandle h; + h.set(p_handle); + recheck_pairs(h); + } + void erase(uint32_t p_handle) { BVHHandle h; h.set(p_handle); @@ -141,7 +158,7 @@ public: force_collision_check(h); } - bool activate(uint32_t p_handle, const Bounds &p_aabb, bool p_delay_collision_check = false) { + bool activate(uint32_t p_handle, const BOUNDS &p_aabb, bool p_delay_collision_check = false) { BVHHandle h; h.set(p_handle); return activate(h, p_aabb, p_delay_collision_check); @@ -153,16 +170,16 @@ public: return deactivate(h); } - void set_pairable(uint32_t p_handle, bool p_pairable, uint32_t p_pairable_type, uint32_t p_pairable_mask, bool p_force_collision_check = true) { + void set_tree(uint32_t p_handle, uint32_t p_tree_id, uint32_t p_tree_collision_mask, bool p_force_collision_check = true) { BVHHandle h; h.set(p_handle); - set_pairable(h, p_pairable, p_pairable_type, p_pairable_mask, p_force_collision_check); + set_tree(h, p_tree_id, p_tree_collision_mask, p_force_collision_check); } - bool is_pairable(uint32_t p_handle) const { + uint32_t get_tree_id(uint32_t p_handle) const { BVHHandle h; h.set(p_handle); - return item_is_pairable(h); + return item_get_tree_id(h); } int get_subindex(uint32_t p_handle) const { BVHHandle h; @@ -178,7 +195,9 @@ public: //////////////////////////////////////////////////// - void move(BVHHandle p_handle, const Bounds &p_aabb) { + void move(BVHHandle p_handle, const BOUNDS &p_aabb) { + DEV_ASSERT(!p_handle.is_invalid()); + BVH_LOCKED_FUNCTION if (tree.item_move(p_handle, p_aabb)) { if (USE_PAIRS) { _add_changed_item(p_handle, p_aabb); @@ -186,7 +205,14 @@ public: } } + void recheck_pairs(BVHHandle p_handle) { + DEV_ASSERT(!p_handle.is_invalid()); + force_collision_check(p_handle); + } + void erase(BVHHandle p_handle) { + DEV_ASSERT(!p_handle.is_invalid()); + BVH_LOCKED_FUNCTION // call unpair and remove all references to the item // before deleting from the tree if (USE_PAIRS) { @@ -200,11 +226,13 @@ public: // use in conjunction with activate if you have deferred the collision check, and // set pairable has never been called. - // (deferred collision checks are a workaround for rendering server for historical reasons) + // (deferred collision checks are a workaround for visual server for historical reasons) void force_collision_check(BVHHandle p_handle) { + DEV_ASSERT(!p_handle.is_invalid()); + BVH_LOCKED_FUNCTION if (USE_PAIRS) { // the aabb should already be up to date in the BVH - Bounds aabb; + BOUNDS aabb; item_get_AABB(p_handle, aabb); // add it as changed even if aabb not different @@ -218,7 +246,9 @@ public: // these should be read as set_visible for render trees, // but generically this makes items add or remove from the // tree internally, to speed things up by ignoring inactive items - bool activate(BVHHandle p_handle, const Bounds &p_aabb, bool p_delay_collision_check = false) { + bool activate(BVHHandle p_handle, const BOUNDS &p_aabb, bool p_delay_collision_check = false) { + DEV_ASSERT(!p_handle.is_invalid()); + BVH_LOCKED_FUNCTION // sending the aabb here prevents the need for the BVH to maintain // a redundant copy of the aabb. // returns success @@ -242,6 +272,8 @@ public: } bool deactivate(BVHHandle p_handle) { + DEV_ASSERT(!p_handle.is_invalid()); + BVH_LOCKED_FUNCTION // returns success if (tree.item_deactivate(p_handle)) { // call unpair and remove all references to the item @@ -258,12 +290,15 @@ public: return false; } - bool get_active(BVHHandle p_handle) const { + bool get_active(BVHHandle p_handle) { + DEV_ASSERT(!p_handle.is_invalid()); + BVH_LOCKED_FUNCTION return tree.item_get_active(p_handle); } // call e.g. once per frame (this does a trickle optimize) void update() { + BVH_LOCKED_FUNCTION tree.update(); _check_for_collisions(); #ifdef BVH_INTEGRITY_CHECKS @@ -273,24 +308,27 @@ public: // this can be called more frequently than per frame if necessary void update_collisions() { + BVH_LOCKED_FUNCTION _check_for_collisions(); } // prefer calling this directly as type safe - void set_pairable(const BVHHandle &p_handle, bool p_pairable, uint32_t p_pairable_type, uint32_t p_pairable_mask, bool p_force_collision_check = true) { + void set_tree(const BVHHandle &p_handle, uint32_t p_tree_id, uint32_t p_tree_collision_mask, bool p_force_collision_check = true) { + DEV_ASSERT(!p_handle.is_invalid()); + BVH_LOCKED_FUNCTION // Returns true if the pairing state has changed. - bool state_changed = tree.item_set_pairable(p_handle, p_pairable, p_pairable_type, p_pairable_mask); + bool state_changed = tree.item_set_tree(p_handle, p_tree_id, p_tree_collision_mask); if (USE_PAIRS) { // not sure if absolutely necessary to flush collisions here. It will cost performance to, instead // of waiting for update, so only uncomment this if there are bugs. //_check_for_collisions(); - if ((p_force_collision_check || state_changed) && get_active(p_handle)) { + if ((p_force_collision_check || state_changed) && tree.item_get_active(p_handle)) { // when the pairable state changes, we need to force a collision check because newly pairable // items may be in collision, and unpairable items might move out of collision. // We cannot depend on waiting for the next update, because that may come much later. - Bounds aabb; + BOUNDS aabb; item_get_AABB(p_handle, aabb); // passing false disables the optimization which prevents collision checks if @@ -307,32 +345,33 @@ public: } // cull tests - int cull_aabb(const Bounds &p_aabb, T **p_result_array, int p_result_max, int *p_subindex_array = nullptr, uint32_t p_mask = 0xFFFFFFFF) { + int cull_aabb(const BOUNDS &p_aabb, T **p_result_array, int p_result_max, const T *p_tester, uint32_t p_tree_collision_mask = 0xFFFFFFFF, int *p_subindex_array = nullptr) { + BVH_LOCKED_FUNCTION typename BVHTREE_CLASS::CullParams params; params.result_count_overall = 0; params.result_max = p_result_max; params.result_array = p_result_array; params.subindex_array = p_subindex_array; - params.mask = p_mask; - params.pairable_type = 0; - params.test_pairable_only = false; + params.tree_collision_mask = p_tree_collision_mask; params.abb.from(p_aabb); + params.tester = p_tester; tree.cull_aabb(params); return params.result_count_overall; } - int cull_segment(const Point &p_from, const Point &p_to, T **p_result_array, int p_result_max, int *p_subindex_array = nullptr, uint32_t p_mask = 0xFFFFFFFF) { + int cull_segment(const POINT &p_from, const POINT &p_to, T **p_result_array, int p_result_max, const T *p_tester, uint32_t p_tree_collision_mask = 0xFFFFFFFF, int *p_subindex_array = nullptr) { + BVH_LOCKED_FUNCTION typename BVHTREE_CLASS::CullParams params; params.result_count_overall = 0; params.result_max = p_result_max; params.result_array = p_result_array; params.subindex_array = p_subindex_array; - params.mask = p_mask; - params.pairable_type = 0; + params.tester = p_tester; + params.tree_collision_mask = p_tree_collision_mask; params.segment.from = p_from; params.segment.to = p_to; @@ -342,15 +381,16 @@ public: return params.result_count_overall; } - int cull_point(const Point &p_point, T **p_result_array, int p_result_max, int *p_subindex_array = nullptr, uint32_t p_mask = 0xFFFFFFFF) { + int cull_point(const POINT &p_point, T **p_result_array, int p_result_max, const T *p_tester, uint32_t p_tree_collision_mask = 0xFFFFFFFF, int *p_subindex_array = nullptr) { + BVH_LOCKED_FUNCTION typename BVHTREE_CLASS::CullParams params; params.result_count_overall = 0; params.result_max = p_result_max; params.result_array = p_result_array; params.subindex_array = p_subindex_array; - params.mask = p_mask; - params.pairable_type = 0; + params.tester = p_tester; + params.tree_collision_mask = p_tree_collision_mask; params.point = p_point; @@ -358,7 +398,8 @@ public: return params.result_count_overall; } - int cull_convex(const Vector<Plane> &p_convex, T **p_result_array, int p_result_max, uint32_t p_mask = 0xFFFFFFFF) { + int cull_convex(const Vector<Plane> &p_convex, T **p_result_array, int p_result_max, const T *p_tester, uint32_t p_tree_collision_mask = 0xFFFFFFFF) { + BVH_LOCKED_FUNCTION if (!p_convex.size()) { return 0; } @@ -373,8 +414,8 @@ public: params.result_max = p_result_max; params.result_array = p_result_array; params.subindex_array = nullptr; - params.mask = p_mask; - params.pairable_type = 0; + params.tester = p_tester; + params.tree_collision_mask = p_tree_collision_mask; params.hull.planes = &p_convex[0]; params.hull.num_planes = p_convex.size(); @@ -394,7 +435,7 @@ private: return; } - Bounds bb; + BOUNDS bb; typename BVHTREE_CLASS::CullParams params; @@ -402,28 +443,23 @@ private: params.result_max = INT_MAX; params.result_array = nullptr; params.subindex_array = nullptr; - params.mask = 0xFFFFFFFF; - params.pairable_type = 0; for (unsigned int n = 0; n < changed_items.size(); n++) { const BVHHandle &h = changed_items[n]; // use the expanded aabb for pairing - const Bounds &expanded_aabb = tree._pairs[h.id()].expanded_aabb; + const BOUNDS &expanded_aabb = tree._pairs[h.id()].expanded_aabb; BVHABB_CLASS abb; abb.from(expanded_aabb); + tree.item_fill_cullparams(h, params); + // find all the existing paired aabbs that are no longer // paired, and send callbacks _find_leavers(h, abb, p_full_check); uint32_t changed_item_ref_id = h.id(); - // set up the test from this item. - // this includes whether to test the non pairable tree, - // and the item mask. - tree.item_fill_cullparams(h, params); - params.abb = abb; params.result_count_overall = 0; // might not be needed @@ -437,13 +473,6 @@ private: continue; } -#ifdef BVH_CHECKS - // if neither are pairable, they should ignore each other - // THIS SHOULD NEVER HAPPEN .. now we only test the pairable tree - // if the changed item is not pairable - CRASH_COND(params.test_pairable_only && !tree._extra[ref_id].pairable); -#endif - // checkmasks is already done in the cull routine. BVHHandle h_collidee; h_collidee.set_id(ref_id); @@ -456,7 +485,8 @@ private: } public: - void item_get_AABB(BVHHandle p_handle, Bounds &r_aabb) { + void item_get_AABB(BVHHandle p_handle, BOUNDS &r_aabb) { + DEV_ASSERT(!p_handle.is_invalid()); BVHABB_CLASS abb; tree.item_get_ABB(p_handle, abb); abb.to(r_aabb); @@ -464,7 +494,7 @@ public: private: // supplemental funcs - bool item_is_pairable(BVHHandle p_handle) const { return _get_extra(p_handle).pairable; } + uint32_t item_get_tree_id(BVHHandle p_handle) const { return _get_extra(p_handle).tree_id; } T *item_get_userdata(BVHHandle p_handle) const { return _get_extra(p_handle).userdata; } int item_get_subindex(BVHHandle p_handle) const { return _get_extra(p_handle).subindex; } @@ -485,12 +515,35 @@ private: void *ud_from = pairs_from.remove_pair_to(p_to); pairs_to.remove_pair_to(p_from); +#ifdef BVH_VERBOSE_PAIRING + print_line("_unpair " + itos(p_from.id()) + " from " + itos(p_to.id())); +#endif + // callback if (unpair_callback) { unpair_callback(pair_callback_userdata, p_from, exa.userdata, exa.subindex, p_to, exb.userdata, exb.subindex, ud_from); } } + void *_recheck_pair(BVHHandle p_from, BVHHandle p_to, void *p_pair_data) { + tree._handle_sort(p_from, p_to); + + typename BVHTREE_CLASS::ItemExtra &exa = tree._extra[p_from.id()]; + typename BVHTREE_CLASS::ItemExtra &exb = tree._extra[p_to.id()]; + + // if the userdata is the same, no collisions should occur + if ((exa.userdata == exb.userdata) && exa.userdata) { + return p_pair_data; + } + + // callback + if (check_pair_callback) { + return check_pair_callback(check_pair_callback_userdata, p_from, exa.userdata, exa.subindex, p_to, exb.userdata, exb.subindex, p_pair_data); + } + + return p_pair_data; + } + // returns true if unpair bool _find_leavers_process_pair(typename BVHTREE_CLASS::ItemPairs &p_pairs_from, const BVHABB_CLASS &p_abb_from, BVHHandle p_from, BVHHandle p_to, bool p_full_check) { BVHABB_CLASS abb_to; @@ -498,8 +551,8 @@ private: // do they overlap? if (p_abb_from.intersects(abb_to)) { - // the full check for pairable / non pairable and mask changes is extra expense - // this need not be done in most cases (for speed) except in the case where set_pairable is called + // the full check for pairable / non pairable (i.e. tree_id and tree_masks) and mask changes is extra expense + // this need not be done in most cases (for speed) except in the case where set_tree is called // where the masks etc of the objects in question may have changed if (!p_full_check) { return false; @@ -507,12 +560,13 @@ private: const typename BVHTREE_CLASS::ItemExtra &exa = _get_extra(p_from); const typename BVHTREE_CLASS::ItemExtra &exb = _get_extra(p_to); - // one of the two must be pairable to still pair - // if neither are pairable, we always unpair - if (exa.pairable || exb.pairable) { + // Checking tree_ids and tree_collision_masks + if (exa.are_item_trees_compatible(exb)) { + bool pair_allowed = USER_PAIR_TEST_FUNCTION::user_pair_check(exa.userdata, exb.userdata); + // the masks must still be compatible to pair - // i.e. if there is a hit between the two, then they should stay paired - if (tree._cull_pairing_mask_test_hit(exa.pairable_mask, exa.pairable_type, exb.pairable_mask, exb.pairable_type)) { + // i.e. if there is a hit between the two and they intersect, then they should stay paired + if (pair_allowed) { return false; } } @@ -550,6 +604,11 @@ private: const typename BVHTREE_CLASS::ItemExtra &exa = _get_extra(p_ha); const typename BVHTREE_CLASS::ItemExtra &exb = _get_extra(p_hb); + // user collision callback + if (!USER_PAIR_TEST_FUNCTION::user_pair_check(exa.userdata, exb.userdata)) { + return; + } + // if the userdata is the same, no collisions should occur if ((exa.userdata == exb.userdata) && exa.userdata) { return; @@ -573,6 +632,10 @@ private: // callback void *callback_userdata = nullptr; +#ifdef BVH_VERBOSE_PAIRING + print_line("_pair " + itos(p_ha.id()) + " to " + itos(p_hb.id())); +#endif + if (pair_callback) { callback_userdata = pair_callback(pair_callback_userdata, p_ha, exa.userdata, exa.subindex, p_hb, exb.userdata, exb.subindex); } @@ -594,6 +657,32 @@ private: } } + // Send pair callbacks again for all existing pairs for the given handle. + void _recheck_pairs(BVHHandle p_handle) { + typename BVHTREE_CLASS::ItemPairs &from = tree._pairs[p_handle.id()]; + + // checking pair for every partner. + for (unsigned int n = 0; n < from.extended_pairs.size(); n++) { + typename BVHTREE_CLASS::ItemPairs::Link &pair = from.extended_pairs[n]; + BVHHandle h_to = pair.handle; + void *new_pair_data = _recheck_pair(p_handle, h_to, pair.userdata); + + if (new_pair_data != pair.userdata) { + pair.userdata = new_pair_data; + + // Update pair data for the second item. + typename BVHTREE_CLASS::ItemPairs &to = tree._pairs[h_to.id()]; + for (unsigned int to_index = 0; to_index < to.extended_pairs.size(); to_index++) { + typename BVHTREE_CLASS::ItemPairs::Link &to_pair = to.extended_pairs[to_index]; + if (to_pair.handle == p_handle) { + to_pair.userdata = new_pair_data; + break; + } + } + } + } + } + private: const typename BVHTREE_CLASS::ItemExtra &_get_extra(BVHHandle p_handle) const { return tree._extra[p_handle.id()]; @@ -607,19 +696,24 @@ private: _tick++; } - void _add_changed_item(BVHHandle p_handle, const Bounds &aabb, bool p_check_aabb = true) { + void _add_changed_item(BVHHandle p_handle, const BOUNDS &aabb, bool p_check_aabb = true) { // Note that non pairable items can pair with pairable, // so all types must be added to the list +#ifdef BVH_EXPAND_LEAF_AABBS + // if using expanded AABB in the leaf, the redundancy check will already have been made + BOUNDS &expanded_aabb = tree._pairs[p_handle.id()].expanded_aabb; + item_get_AABB(p_handle, expanded_aabb); +#else // aabb check with expanded aabb. This greatly decreases processing // at the cost of slightly less accurate pairing checks // Note this pairing AABB is separate from the AABB in the actual tree - Bounds &expanded_aabb = tree._pairs[p_handle.id()].expanded_aabb; + BOUNDS &expanded_aabb = tree._pairs[p_handle.id()].expanded_aabb; // passing p_check_aabb false disables the optimization which prevents collision checks if // the aabb hasn't changed. This is needed where set_pairable has been called, but the position // has not changed. - if (p_check_aabb && expanded_aabb.encloses(aabb)) { + if (p_check_aabb && tree.expanded_aabb_encloses_not_shrink(expanded_aabb, aabb)) { return; } @@ -627,6 +721,7 @@ private: // this tick, because it is vital that the AABB is kept up to date expanded_aabb = aabb; expanded_aabb.grow_by(tree._pairing_expansion); +#endif // this code is to ensure that changed items only appear once on the updated list // collision checking them multiple times is not needed, and repeats the same thing @@ -668,26 +763,54 @@ private: tree._extra[p_handle.id()].last_updated_tick = 0; } - PairCallback pair_callback; - UnpairCallback unpair_callback; - void *pair_callback_userdata; - void *unpair_callback_userdata; + PairCallback pair_callback = nullptr; + UnpairCallback unpair_callback = nullptr; + CheckPairCallback check_pair_callback = nullptr; + void *pair_callback_userdata = nullptr; + void *unpair_callback_userdata = nullptr; + void *check_pair_callback_userdata = nullptr; BVHTREE_CLASS tree; // for collision pairing, // maintain a list of all items moved etc on each frame / tick LocalVector<BVHHandle, uint32_t, true> changed_items; - uint32_t _tick; + uint32_t _tick = 1; // Start from 1 so items with 0 indicate never updated. + + class BVHLockedFunction { + public: + BVHLockedFunction(Mutex *p_mutex, bool p_thread_safe) { + // will be compiled out if not set in template + if (p_thread_safe) { + _mutex = p_mutex; + + if (_mutex->try_lock() != OK) { + WARN_PRINT("Info : multithread BVH access detected (benign)"); + _mutex->lock(); + } + + } else { + _mutex = nullptr; + } + } + ~BVHLockedFunction() { + // will be compiled out if not set in template + if (_mutex) { + _mutex->unlock(); + } + } + + private: + Mutex *_mutex = nullptr; + }; + + Mutex _mutex; + + // local toggle for turning on and off thread safety in project settings + bool _thread_safe = BVH_THREAD_SAFE; public: - BVH_Manager() { - _tick = 1; // start from 1 so items with 0 indicate never updated - pair_callback = nullptr; - unpair_callback = nullptr; - pair_callback_userdata = nullptr; - unpair_callback_userdata = nullptr; - } + BVH_Manager() {} }; #undef BVHTREE_CLASS diff --git a/core/math/bvh_abb.h b/core/math/bvh_abb.h index 009032d34d..8a44f1c4da 100644 --- a/core/math/bvh_abb.h +++ b/core/math/bvh_abb.h @@ -32,7 +32,7 @@ #define BVH_ABB_H // special optimized version of axis aligned bounding box -template <class Bounds = AABB, class Point = Vector3> +template <class BOUNDS = AABB, class POINT = Vector3> struct BVH_ABB { struct ConvexHull { // convex hulls (optional) @@ -43,8 +43,8 @@ struct BVH_ABB { }; struct Segment { - Point from; - Point to; + POINT from; + POINT to; }; enum IntersectResult { @@ -54,47 +54,47 @@ struct BVH_ABB { }; // we store mins with a negative value in order to test them with SIMD - Point min; - Point neg_max; + POINT min; + POINT neg_max; bool operator==(const BVH_ABB &o) const { return (min == o.min) && (neg_max == o.neg_max); } bool operator!=(const BVH_ABB &o) const { return (*this == o) == false; } - void set(const Point &_min, const Point &_max) { + void set(const POINT &_min, const POINT &_max) { min = _min; neg_max = -_max; } // to and from standard AABB - void from(const Bounds &p_aabb) { + void from(const BOUNDS &p_aabb) { min = p_aabb.position; neg_max = -(p_aabb.position + p_aabb.size); } - void to(Bounds &r_aabb) const { + void to(BOUNDS &r_aabb) const { r_aabb.position = min; r_aabb.size = calculate_size(); } void merge(const BVH_ABB &p_o) { - for (int axis = 0; axis < Point::AXIS_COUNT; ++axis) { + for (int axis = 0; axis < POINT::AXIS_COUNT; ++axis) { neg_max[axis] = MIN(neg_max[axis], p_o.neg_max[axis]); min[axis] = MIN(min[axis], p_o.min[axis]); } } - Point calculate_size() const { + POINT calculate_size() const { return -neg_max - min; } - Point calculate_centre() const { - return Point((calculate_size() * 0.5) + min); + POINT calculate_centre() const { + return POINT((calculate_size() * 0.5) + min); } real_t get_proximity_to(const BVH_ABB &p_b) const { - const Point d = (min - neg_max) - (p_b.min - p_b.neg_max); + const POINT d = (min - neg_max) - (p_b.min - p_b.neg_max); real_t proximity = 0.0; - for (int axis = 0; axis < Point::AXIS_COUNT; ++axis) { + for (int axis = 0; axis < POINT::AXIS_COUNT; ++axis) { proximity += Math::abs(d[axis]); } return proximity; @@ -104,7 +104,7 @@ struct BVH_ABB { return (get_proximity_to(p_a) < get_proximity_to(p_b) ? 0 : 1); } - uint32_t find_cutting_planes(const BVH_ABB::ConvexHull &p_hull, uint32_t *p_plane_ids) const { + uint32_t find_cutting_planes(const typename BVH_ABB::ConvexHull &p_hull, uint32_t *p_plane_ids) const { uint32_t count = 0; for (int n = 0; n < p_hull.num_planes; n++) { @@ -162,7 +162,7 @@ struct BVH_ABB { } bool intersects_convex_partial(const ConvexHull &p_hull) const { - Bounds bb; + BOUNDS bb; to(bb); return bb.intersects_convex_shape(p_hull.planes, p_hull.num_planes, p_hull.points, p_hull.num_points); } @@ -182,7 +182,7 @@ struct BVH_ABB { bool is_within_convex(const ConvexHull &p_hull) const { // use half extents routine - Bounds bb; + BOUNDS bb; to(bb); return bb.inside_convex_shape(p_hull.planes, p_hull.num_planes); } @@ -197,12 +197,12 @@ struct BVH_ABB { } bool intersects_segment(const Segment &p_s) const { - Bounds bb; + BOUNDS bb; to(bb); return bb.intersects_segment(p_s.from, p_s.to); } - bool intersects_point(const Point &p_pt) const { + bool intersects_point(const POINT &p_pt) const { if (_any_lessthan(-p_pt, neg_max)) { return false; } @@ -212,6 +212,7 @@ struct BVH_ABB { return true; } + // Very hot in profiling, make sure optimized bool intersects(const BVH_ABB &p_o) const { if (_any_morethan(p_o.min, -neg_max)) { return false; @@ -222,6 +223,17 @@ struct BVH_ABB { return true; } + // for pre-swizzled tester (this object) + bool intersects_swizzled(const BVH_ABB &p_o) const { + if (_any_lessthan(min, p_o.min)) { + return false; + } + if (_any_lessthan(neg_max, p_o.neg_max)) { + return false; + } + return true; + } + bool is_other_within(const BVH_ABB &p_o) const { if (_any_lessthan(p_o.neg_max, neg_max)) { return false; @@ -232,20 +244,20 @@ struct BVH_ABB { return true; } - void grow(const Point &p_change) { + void grow(const POINT &p_change) { neg_max -= p_change; min -= p_change; } void expand(real_t p_change) { - Point change; + POINT change; change.set_all(p_change); grow(change); } // Actually surface area metric. float get_area() const { - Point d = calculate_size(); + POINT d = calculate_size(); return 2.0f * (d.x * d.y + d.y * d.z + d.z * d.x); } @@ -254,8 +266,8 @@ struct BVH_ABB { min = neg_max; } - bool _any_morethan(const Point &p_a, const Point &p_b) const { - for (int axis = 0; axis < Point::AXIS_COUNT; ++axis) { + bool _any_morethan(const POINT &p_a, const POINT &p_b) const { + for (int axis = 0; axis < POINT::AXIS_COUNT; ++axis) { if (p_a[axis] > p_b[axis]) { return true; } @@ -263,8 +275,8 @@ struct BVH_ABB { return false; } - bool _any_lessthan(const Point &p_a, const Point &p_b) const { - for (int axis = 0; axis < Point::AXIS_COUNT; ++axis) { + bool _any_lessthan(const POINT &p_a, const POINT &p_b) const { + for (int axis = 0; axis < POINT::AXIS_COUNT; ++axis) { if (p_a[axis] < p_b[axis]) { return true; } diff --git a/core/math/bvh_cull.inc b/core/math/bvh_cull.inc index ab468bfd29..11f50e41e6 100644 --- a/core/math/bvh_cull.inc +++ b/core/math/bvh_cull.inc @@ -9,20 +9,22 @@ struct CullParams { T **result_array; int *subindex_array; - // nobody truly understands how masks are intended to work. - uint32_t mask; - uint32_t pairable_type; + // We now process masks etc in a user template function, + // and these for simplicity assume even for cull tests there is a + // testing object (which has masks etc) for the user cull checks. + // This means for cull tests on their own, the client will usually + // want to create a dummy object, just in order to specify masks etc. + const T *tester; // optional components for different tests - Point point; + POINT point; BVHABB_CLASS abb; typename BVHABB_CLASS::ConvexHull hull; typename BVHABB_CLASS::Segment segment; - // when collision testing, non pairable moving items - // only need to be tested against the pairable tree. - // collisions with other non pairable items are irrelevant. - bool test_pairable_only; + // When collision testing, we can specify which tree ids + // to collide test against with the tree_collision_mask. + uint32_t tree_collision_mask; }; private: @@ -58,11 +60,22 @@ int cull_convex(CullParams &r_params, bool p_translate_hits = true) { _cull_hits.clear(); r_params.result_count = 0; + uint32_t tree_test_mask = 0; + for (int n = 0; n < NUM_TREES; n++) { + tree_test_mask <<= 1; + if (!tree_test_mask) { + tree_test_mask = 1; + } + if (_root_node_id[n] == BVHCommon::INVALID) { continue; } + if (!(r_params.tree_collision_mask & tree_test_mask)) { + continue; + } + _cull_convex_iterative(_root_node_id[n], r_params); } @@ -77,11 +90,22 @@ int cull_segment(CullParams &r_params, bool p_translate_hits = true) { _cull_hits.clear(); r_params.result_count = 0; + uint32_t tree_test_mask = 0; + for (int n = 0; n < NUM_TREES; n++) { + tree_test_mask <<= 1; + if (!tree_test_mask) { + tree_test_mask = 1; + } + if (_root_node_id[n] == BVHCommon::INVALID) { continue; } + if (!(r_params.tree_collision_mask & tree_test_mask)) { + continue; + } + _cull_segment_iterative(_root_node_id[n], r_params); } @@ -96,11 +120,22 @@ int cull_point(CullParams &r_params, bool p_translate_hits = true) { _cull_hits.clear(); r_params.result_count = 0; + uint32_t tree_test_mask = 0; + for (int n = 0; n < NUM_TREES; n++) { + tree_test_mask <<= 1; + if (!tree_test_mask) { + tree_test_mask = 1; + } + if (_root_node_id[n] == BVHCommon::INVALID) { continue; } + if (!(r_params.tree_collision_mask & tree_test_mask)) { + continue; + } + _cull_point_iterative(_root_node_id[n], r_params); } @@ -115,12 +150,20 @@ int cull_aabb(CullParams &r_params, bool p_translate_hits = true) { _cull_hits.clear(); r_params.result_count = 0; + uint32_t tree_test_mask = 0; + for (int n = 0; n < NUM_TREES; n++) { + tree_test_mask <<= 1; + if (!tree_test_mask) { + tree_test_mask = 1; + } + if (_root_node_id[n] == BVHCommon::INVALID) { continue; } - if ((n == 0) && r_params.test_pairable_only) { + // the tree collision mask determines which trees to collide test against + if (!(r_params.tree_collision_mask & tree_test_mask)) { continue; } @@ -142,22 +185,6 @@ bool _cull_hits_full(const CullParams &p) { return (int)_cull_hits.size() >= p.result_max; } -// write this logic once for use in all routines -// double check this as a possible source of bugs in future. -bool _cull_pairing_mask_test_hit(uint32_t p_maskA, uint32_t p_typeA, uint32_t p_maskB, uint32_t p_typeB) const { - // double check this as a possible source of bugs in future. - bool A_match_B = p_maskA & p_typeB; - - if (!A_match_B) { - bool B_match_A = p_maskB & p_typeA; - if (!B_match_A) { - return false; - } - } - - return true; -} - void _cull_hit(uint32_t p_ref_id, CullParams &p) { // take into account masks etc // this would be more efficient to do before plane checks, @@ -165,7 +192,8 @@ void _cull_hit(uint32_t p_ref_id, CullParams &p) { if (USE_PAIRS) { const ItemExtra &ex = _extra[p_ref_id]; - if (!_cull_pairing_mask_test_hit(p.mask, p.pairable_type, ex.pairable_mask, ex.pairable_type)) { + // user supplied function (for e.g. pairable types and pairable masks in the render tree) + if (!USER_CULL_TEST_FUNCTION::user_cull_check(p.tester, ex.userdata)) { return; } } @@ -294,6 +322,7 @@ bool _cull_point_iterative(uint32_t p_node_id, CullParams &r_params) { return true; } +// Note: This is a very hot loop profiling wise. Take care when changing this and profile. bool _cull_aabb_iterative(uint32_t p_node_id, CullParams &r_params, bool p_fully_within = false) { // our function parameters to keep on a stack struct CullAABBParams { @@ -336,16 +365,26 @@ bool _cull_aabb_iterative(uint32_t p_node_id, CullParams &r_params, bool p_fully _cull_hit(child_id, r_params); } } else { - for (int n = 0; n < leaf.num_items; n++) { + // This section is the hottest area in profiling, so + // is optimized highly + // get this into a local register and preconverted to correct type + int leaf_num_items = leaf.num_items; + + BVHABB_CLASS swizzled_tester; + swizzled_tester.min = -r_params.abb.neg_max; + swizzled_tester.neg_max = -r_params.abb.min; + + for (int n = 0; n < leaf_num_items; n++) { const BVHABB_CLASS &aabb = leaf.get_aabb(n); - if (aabb.intersects(r_params.abb)) { + if (swizzled_tester.intersects_swizzled(aabb)) { uint32_t child_id = leaf.get_item_ref_id(n); // register hit _cull_hit(child_id, r_params); } } + } // not fully within } else { if (!cap.fully_within) { diff --git a/core/math/bvh_debug.inc b/core/math/bvh_debug.inc index 896c36ecf1..2e519ceb3d 100644 --- a/core/math/bvh_debug.inc +++ b/core/math/bvh_debug.inc @@ -7,12 +7,12 @@ void _debug_recursive_print_tree(int p_tree_id) const { } String _debug_aabb_to_string(const BVHABB_CLASS &aabb) const { - Point size = aabb.calculate_size(); + POINT size = aabb.calculate_size(); String sz; float vol = 0.0; - for (int i = 0; i < Point::AXES_COUNT; ++i) { + for (int i = 0; i < POINT::AXIS_COUNT; ++i) { sz += "("; sz += itos(aabb.min[i]); sz += " ~ "; diff --git a/core/math/bvh_logic.inc b/core/math/bvh_logic.inc index c65002a9fd..dd3b135bb5 100644 --- a/core/math/bvh_logic.inc +++ b/core/math/bvh_logic.inc @@ -42,9 +42,9 @@ BVHABB_CLASS _logic_abb_merge(const BVHABB_CLASS &a, const BVHABB_CLASS &b) { //-------------------------------------------------------------------------------------------------- /** - * @file q3DynamicAABBTree.h - * @author Randy Gaul - * @date 10/10/2014 + * @file q3DynamicAABBTree.h + * @author Randy Gaul + * @date 10/10/2014 * Copyright (c) 2014 Randy Gaul http://www.randygaul.net * This software is provided 'as-is', without any express or implied * warranty. In no event will the authors be held liable for any damages @@ -75,11 +75,11 @@ int32_t _logic_balance(int32_t iA, uint32_t p_tree_id) { return iA; } - /* A - * / \ - * B C - * / \ / \ - * D E F G + /* A + * / \ + * B C + * / \ / \ + * D E F G */ CRASH_COND(A->num_children != 2); diff --git a/core/math/bvh_misc.inc b/core/math/bvh_misc.inc index 71aa0e4fe0..9b35a1d36d 100644 --- a/core/math/bvh_misc.inc +++ b/core/math/bvh_misc.inc @@ -1,11 +1,7 @@ int _handle_get_tree_id(BVHHandle p_handle) const { if (USE_PAIRS) { - int tree = 0; - if (_extra[p_handle.id()].pairable) { - tree = 1; - } - return tree; + return _extra[p_handle.id()].tree_id; } return 0; } diff --git a/core/math/bvh_pair.inc b/core/math/bvh_pair.inc index a12acec2b6..7b9c7ce6ae 100644 --- a/core/math/bvh_pair.inc +++ b/core/math/bvh_pair.inc @@ -14,10 +14,10 @@ struct ItemPairs { void clear() { num_pairs = 0; extended_pairs.reset(); - expanded_aabb = Bounds(); + expanded_aabb = BOUNDS(); } - Bounds expanded_aabb; + BOUNDS expanded_aabb; // maybe we can just use the number in the vector TODO int32_t num_pairs; @@ -59,4 +59,14 @@ struct ItemPairs { return userdata; } + + // experiment : scale the pairing expansion by the number of pairs. + // when the number of pairs is high, the density is high and a lower collision margin is better. + // when there are few local pairs, a larger margin is more optimal. + real_t scale_expansion_margin(real_t p_margin) const { + real_t x = real_t(num_pairs) * (1.0 / 9.0); + x = MIN(x, 1.0); + x = 1.0 - x; + return p_margin * x; + } }; diff --git a/core/math/bvh_public.inc b/core/math/bvh_public.inc index 2c1e406712..36b0bfeb13 100644 --- a/core/math/bvh_public.inc +++ b/core/math/bvh_public.inc @@ -1,5 +1,5 @@ public: -BVHHandle item_add(T *p_userdata, bool p_active, const Bounds &p_aabb, int32_t p_subindex, bool p_pairable, uint32_t p_pairable_type, uint32_t p_pairable_mask, bool p_invisible = false) { +BVHHandle item_add(T *p_userdata, bool p_active, const BOUNDS &p_aabb, int32_t p_subindex, uint32_t p_tree_id, uint32_t p_tree_collision_mask, bool p_invisible = false) { #ifdef BVH_VERBOSE_TREE VERBOSE_PRINT("\nitem_add BEFORE"); _debug_recursive_print_tree(0); @@ -9,6 +9,13 @@ BVHHandle item_add(T *p_userdata, bool p_active, const Bounds &p_aabb, int32_t p BVHABB_CLASS abb; abb.from(p_aabb); + // NOTE that we do not expand the AABB for the first create even if + // leaf expansion is switched on. This is for two reasons: + // (1) We don't know if this object will move in future, in which case a non-expanded + // bound would be better... + // (2) We don't yet know how many objects will be paired, which is used to modify + // the expansion margin. + // handle to be filled with the new item ref BVHHandle handle; @@ -40,29 +47,17 @@ BVHHandle item_add(T *p_userdata, bool p_active, const Bounds &p_aabb, int32_t p extra->active_ref_id = _active_refs.size(); _active_refs.push_back(ref_id); - if (USE_PAIRS) { - extra->pairable_mask = p_pairable_mask; - extra->pairable_type = p_pairable_type; - extra->pairable = p_pairable; - } else { - // just for safety, in case this gets queried etc - extra->pairable = 0; - p_pairable = false; - } + extra->tree_id = p_tree_id; + extra->tree_collision_mask = p_tree_collision_mask; // assign to handle to return handle.set_id(ref_id); - uint32_t tree_id = 0; - if (p_pairable) { - tree_id = 1; - } - - create_root_node(tree_id); + create_root_node(p_tree_id); // we must choose where to add to tree if (p_active) { - ref->tnode_id = _logic_choose_item_add_node(_root_node_id[tree_id], abb); + ref->tnode_id = _logic_choose_item_add_node(_root_node_id[p_tree_id], abb); bool refit = _node_add_item(ref->tnode_id, ref_id, abb); @@ -70,7 +65,7 @@ BVHHandle item_add(T *p_userdata, bool p_active, const Bounds &p_aabb, int32_t p // only need to refit from the parent const TNode &add_node = _nodes[ref->tnode_id]; if (add_node.parent_id != BVHCommon::INVALID) { - refit_upward_and_balance(add_node.parent_id, tree_id); + refit_upward_and_balance(add_node.parent_id, p_tree_id); } } } else { @@ -103,7 +98,7 @@ void _debug_print_refs() { } // returns false if noop -bool item_move(BVHHandle p_handle, const Bounds &p_aabb) { +bool item_move(BVHHandle p_handle, const BOUNDS &p_aabb) { uint32_t ref_id = p_handle.id(); // get the reference @@ -115,10 +110,19 @@ bool item_move(BVHHandle p_handle, const Bounds &p_aabb) { BVHABB_CLASS abb; abb.from(p_aabb); +#ifdef BVH_EXPAND_LEAF_AABBS + if (USE_PAIRS) { + // scale the pairing expansion by the number of pairs. + abb.expand(_pairs[ref_id].scale_expansion_margin(_pairing_expansion)); + } else { + abb.expand(_pairing_expansion); + } +#endif + BVH_ASSERT(ref.tnode_id != BVHCommon::INVALID); TNode &tnode = _nodes[ref.tnode_id]; - // does it fit within the current aabb? + // does it fit within the current leaf aabb? if (tnode.aabb.is_other_within(abb)) { // do nothing .. fast path .. not moved enough to need refit @@ -129,9 +133,24 @@ bool item_move(BVHHandle p_handle, const Bounds &p_aabb) { BVHABB_CLASS &leaf_abb = leaf.get_aabb(ref.item_id); // no change? +#ifdef BVH_EXPAND_LEAF_AABBS + BOUNDS leaf_aabb; + leaf_abb.to(leaf_aabb); + + // This test should pass in a lot of cases, and by returning false we can avoid + // collision pairing checks later, which greatly reduces processing. + if (expanded_aabb_encloses_not_shrink(leaf_aabb, p_aabb)) { + return false; + } +#else if (leaf_abb == abb) { return false; } +#endif + +#ifdef BVH_VERBOSE_MOVES + print_line("item_move " + itos(p_handle.id()) + "(within tnode aabb) : " + _debug_aabb_to_string(abb)); +#endif leaf_abb = abb; _integrity_check_all(); @@ -139,6 +158,10 @@ bool item_move(BVHHandle p_handle, const Bounds &p_aabb) { return true; } +#ifdef BVH_VERBOSE_MOVES + print_line("item_move " + itos(p_handle.id()) + "(outside tnode aabb) : " + _debug_aabb_to_string(abb)); +#endif + uint32_t tree_id = _handle_get_tree_id(p_handle); // remove and reinsert @@ -206,7 +229,7 @@ void item_remove(BVHHandle p_handle) { } // returns success -bool item_activate(BVHHandle p_handle, const Bounds &p_aabb) { +bool item_activate(BVHHandle p_handle, const BOUNDS &p_aabb) { uint32_t ref_id = p_handle.id(); ItemRef &ref = _refs[ref_id]; if (ref.is_active()) { @@ -260,12 +283,14 @@ void item_fill_cullparams(BVHHandle p_handle, CullParams &r_params) const { uint32_t ref_id = p_handle.id(); const ItemExtra &extra = _extra[ref_id]; - // testing from a non pairable item, we only want to test pairable items - r_params.test_pairable_only = extra.pairable == 0; + // which trees does this item want to collide detect against? + r_params.tree_collision_mask = extra.tree_collision_mask; - // we take into account the mask of the item testing from - r_params.mask = extra.pairable_mask; - r_params.pairable_type = extra.pairable_type; + // The testing user defined object is passed to the user defined cull check function + // for masks etc. This is usually a dummy object of type T with masks set. + // However, if not using the cull_check callback (i.e. returning true), you can pass + // a nullptr instead of dummy object, as it will not be used. + r_params.tester = extra.userdata; } bool item_is_pairable(const BVHHandle &p_handle) { @@ -285,7 +310,7 @@ void item_get_ABB(const BVHHandle &p_handle, BVHABB_CLASS &r_abb) { r_abb = leaf.get_aabb(ref.item_id); } -bool item_set_pairable(const BVHHandle &p_handle, bool p_pairable, uint32_t p_pairable_type, uint32_t p_pairable_mask) { +bool item_set_tree(const BVHHandle &p_handle, uint32_t p_tree_id, uint32_t p_tree_collision_mask) { // change tree? uint32_t ref_id = p_handle.id(); @@ -293,13 +318,15 @@ bool item_set_pairable(const BVHHandle &p_handle, bool p_pairable, uint32_t p_pa ItemRef &ref = _refs[ref_id]; bool active = ref.is_active(); - bool pairable_changed = (ex.pairable != 0) != p_pairable; - bool state_changed = pairable_changed || (ex.pairable_type != p_pairable_type) || (ex.pairable_mask != p_pairable_mask); + bool tree_changed = ex.tree_id != p_tree_id; + bool mask_changed = ex.tree_collision_mask != p_tree_collision_mask; + bool state_changed = tree_changed | mask_changed; - ex.pairable_type = p_pairable_type; - ex.pairable_mask = p_pairable_mask; + // Keep an eye on this for bugs of not noticing changes to objects, + // especially when changing client user masks that will not be detected as a change + // in the BVH. You may need to force a collision check in this case with recheck_pairs(). - if (active && pairable_changed) { + if (active && (tree_changed | mask_changed)) { // record abb TNode &tnode = _nodes[ref.tnode_id]; TLeaf &leaf = _node_get_leaf(tnode); @@ -313,7 +340,8 @@ bool item_set_pairable(const BVHHandle &p_handle, bool p_pairable, uint32_t p_pa // we must set the pairable AFTER getting the current tree // because the pairable status determines which tree - ex.pairable = p_pairable; + ex.tree_id = p_tree_id; + ex.tree_collision_mask = p_tree_collision_mask; // add to new tree tree_id = _handle_get_tree_id(p_handle); @@ -333,7 +361,8 @@ bool item_set_pairable(const BVHHandle &p_handle, bool p_pairable, uint32_t p_pa } } else { // always keep this up to date - ex.pairable = p_pairable; + ex.tree_id = p_tree_id; + ex.tree_collision_mask = p_tree_collision_mask; } return state_changed; @@ -403,7 +432,7 @@ void update() { // if there are no nodes, do nothing, but if there are... if (bound_valid) { - Bounds bb; + BOUNDS bb; world_bound.to(bb); real_t size = bb.get_longest_axis_size(); @@ -421,3 +450,50 @@ void update() { } #endif } + +void params_set_pairing_expansion(real_t p_value) { + if (p_value < 0.0) { +#ifdef BVH_ALLOW_AUTO_EXPANSION + _auto_pairing_expansion = true; +#endif + return; + } +#ifdef BVH_ALLOW_AUTO_EXPANSION + _auto_pairing_expansion = false; +#endif + + _pairing_expansion = p_value; + + // calculate shrinking threshold + const real_t fudge_factor = 1.1; + _aabb_shrinkage_threshold = _pairing_expansion * POINT::AXIS_COUNT * 2.0 * fudge_factor; +} + +// This routine is not just an enclose check, it also checks for special case of shrinkage +bool expanded_aabb_encloses_not_shrink(const BOUNDS &p_expanded_aabb, const BOUNDS &p_aabb) const { + if (!p_expanded_aabb.encloses(p_aabb)) { + return false; + } + + // Check for special case of shrinkage. If the aabb has shrunk + // significantly we want to create a new expanded bound, because + // the previous expanded bound will have diverged significantly. + const POINT &exp_size = p_expanded_aabb.size; + const POINT &new_size = p_aabb.size; + + real_t exp_l = 0.0; + real_t new_l = 0.0; + + for (int i = 0; i < POINT::AXIS_COUNT; ++i) { + exp_l += exp_size[i]; + new_l += new_size[i]; + } + + // is difference above some metric + real_t diff = exp_l - new_l; + if (diff < _aabb_shrinkage_threshold) { + return true; + } + + return false; +} diff --git a/core/math/bvh_split.inc b/core/math/bvh_split.inc index f19ee8a7da..ff07166d4a 100644 --- a/core/math/bvh_split.inc +++ b/core/math/bvh_split.inc @@ -25,16 +25,16 @@ void _split_leaf_sort_groups_simple(int &num_a, int &num_b, uint16_t *group_a, u return; } - Point centre = full_bound.calculate_centre(); - Point size = full_bound.calculate_size(); + POINT centre = full_bound.calculate_centre(); + POINT size = full_bound.calculate_size(); - int order[Point::AXIS_COUNT]; + int order[POINT::AXIS_COUNT]; order[0] = size.min_axis_index(); - order[Point::AXIS_COUNT - 1] = size.max_axis_index(); + order[POINT::AXIS_COUNT - 1] = size.max_axis_index(); - static_assert(Point::AXIS_COUNT <= 3); - if (Point::AXIS_COUNT == 3) { + static_assert(POINT::AXIS_COUNT <= 3, "BVH POINT::AXIS_COUNT has unexpected size"); + if (POINT::AXIS_COUNT == 3) { order[1] = 3 - (order[0] + order[2]); } @@ -58,7 +58,7 @@ void _split_leaf_sort_groups_simple(int &num_a, int &num_b, uint16_t *group_a, u // detect when split on longest axis failed int min_threshold = MAX_ITEMS / 4; - int min_group_size[Point::AXIS_COUNT]; + int min_group_size[POINT::AXIS_COUNT]; min_group_size[0] = MIN(num_a, num_b); if (min_group_size[0] < min_threshold) { // slow but sure .. first move everything back into a @@ -68,7 +68,7 @@ void _split_leaf_sort_groups_simple(int &num_a, int &num_b, uint16_t *group_a, u num_b = 0; // now calculate the best split - for (int axis = 1; axis < Point::AXIS_COUNT; axis++) { + for (int axis = 1; axis < POINT::AXIS_COUNT; axis++) { split_axis = order[axis]; int count = 0; @@ -86,7 +86,7 @@ void _split_leaf_sort_groups_simple(int &num_a, int &num_b, uint16_t *group_a, u // best axis int best_axis = 0; int best_min = min_group_size[0]; - for (int axis = 1; axis < Point::AXIS_COUNT; axis++) { + for (int axis = 1; axis < POINT::AXIS_COUNT; axis++) { if (min_group_size[axis] > best_min) { best_min = min_group_size[axis]; best_axis = axis; diff --git a/core/math/bvh_structs.inc b/core/math/bvh_structs.inc index 1d1e0e6468..58c8f0479a 100644 --- a/core/math/bvh_structs.inc +++ b/core/math/bvh_structs.inc @@ -14,25 +14,38 @@ struct ItemRef { // extra info kept in separate parallel list to the references, // as this is less used as keeps cache better struct ItemExtra { - uint32_t last_updated_tick; - uint32_t pairable; - uint32_t pairable_mask; - uint32_t pairable_type; + // Before doing user defined pairing checks (especially in the find_leavers function), + // we may want to check that two items have compatible tree ids and tree masks, + // as if they are incompatible they should not pair / collide. + bool are_item_trees_compatible(const ItemExtra &p_other) const { + uint32_t other_type = 1 << p_other.tree_id; + if (tree_collision_mask & other_type) { + return true; + } + uint32_t our_type = 1 << tree_id; + if (p_other.tree_collision_mask & our_type) { + return true; + } + return false; + } + + // There can be multiple user defined trees + uint32_t tree_id; + + // Defines which trees this item should collision check against. + // 1 << tree_id, and normally items would collide against there own + // tree (but not always). + uint32_t tree_collision_mask; + uint32_t last_updated_tick; int32_t subindex; + T *userdata; + // the active reference is a separate list of which references // are active so that we can slowly iterate through it over many frames for // slow optimize. uint32_t active_ref_id; - - T *userdata; -}; - -// this is an item OR a child node depending on whether a leaf node -struct Item { - BVHABB_CLASS aabb; - uint32_t item_ref_id; }; // tree leaf @@ -47,11 +60,23 @@ private: public: // accessors - BVHABB_CLASS &get_aabb(uint32_t p_id) { return aabbs[p_id]; } - const BVHABB_CLASS &get_aabb(uint32_t p_id) const { return aabbs[p_id]; } + BVHABB_CLASS &get_aabb(uint32_t p_id) { + BVH_ASSERT(p_id < MAX_ITEMS); + return aabbs[p_id]; + } + const BVHABB_CLASS &get_aabb(uint32_t p_id) const { + BVH_ASSERT(p_id < MAX_ITEMS); + return aabbs[p_id]; + } - uint32_t &get_item_ref_id(uint32_t p_id) { return item_ref_ids[p_id]; } - const uint32_t &get_item_ref_id(uint32_t p_id) const { return item_ref_ids[p_id]; } + uint32_t &get_item_ref_id(uint32_t p_id) { + BVH_ASSERT(p_id < MAX_ITEMS); + return item_ref_ids[p_id]; + } + const uint32_t &get_item_ref_id(uint32_t p_id) const { + BVH_ASSERT(p_id < MAX_ITEMS); + return item_ref_ids[p_id]; + } bool is_dirty() const { return dirty; } void set_dirty(bool p) { dirty = p; } @@ -133,13 +158,13 @@ struct TNode { // instead of using linked list we maintain // item references (for quick lookup) -PooledList<ItemRef, true> _refs; -PooledList<ItemExtra, true> _extra; +PooledList<ItemRef, uint32_t, true> _refs; +PooledList<ItemExtra, uint32_t, true> _extra; PooledList<ItemPairs> _pairs; // these 2 are not in sync .. nodes != leaves! -PooledList<TNode, true> _nodes; -PooledList<TLeaf, true> _leaves; +PooledList<TNode, uint32_t, true> _nodes; +PooledList<TLeaf, uint32_t, true> _leaves; // we can maintain an un-ordered list of which references are active, // in order to do a slow incremental optimize of the tree over each frame. @@ -152,15 +177,11 @@ uint32_t _current_active_ref = 0; // for pairing collision detection LocalVector<uint32_t, uint32_t, true> _cull_hits; -// we now have multiple root nodes, allowing us to store -// more than 1 tree. This can be more efficient, while sharing the same -// common lists -enum { NUM_TREES = 2, -}; - -// Tree 0 - Non pairable -// Tree 1 - Pairable -// This is more efficient because in physics we only need check non pairable against the pairable tree. +// We can now have a user definable number of trees. +// This allows using e.g. a non-pairable and pairable tree, +// which can be more efficient for example, if we only need check non pairable against the pairable tree. +// It also may be more efficient in terms of separating static from dynamic objects, by reducing housekeeping. +// However this is a trade off, as there is a cost of traversing two trees. uint32_t _root_node_id[NUM_TREES]; // these values may need tweaking according to the project @@ -177,4 +198,14 @@ bool _auto_node_expansion = true; // larger values gives more 'sticky' pairing, and is less likely to exhibit tunneling // we can either use auto mode, where the expansion is based on the root node size, or specify manually real_t _pairing_expansion = 0.1; + +#ifdef BVH_ALLOW_AUTO_EXPANSION bool _auto_pairing_expansion = true; +#endif + +// when using an expanded bound, we must detect the condition where a new AABB +// is significantly smaller than the expanded bound, as this is a special case where we +// should override the optimization and create a new expanded bound. +// This threshold is derived from the _pairing_expansion, and should be recalculated +// if _pairing_expansion is changed. +real_t _aabb_shrinkage_threshold = 0.0; diff --git a/core/math/bvh_tree.h b/core/math/bvh_tree.h index c948d83456..cdb2bb4413 100644 --- a/core/math/bvh_tree.h +++ b/core/math/bvh_tree.h @@ -48,12 +48,17 @@ #include "core/templates/pooled_list.h" #include <limits.h> -#define BVHABB_CLASS BVH_ABB<Bounds, Point> +#define BVHABB_CLASS BVH_ABB<BOUNDS, POINT> + +// not sure if this is better yet so making optional +#define BVH_EXPAND_LEAF_AABBS // never do these checks in release -#if defined(TOOLS_ENABLED) && defined(DEBUG_ENABLED) +#ifdef DEV_ENABLED //#define BVH_VERBOSE //#define BVH_VERBOSE_TREE +//#define BVH_VERBOSE_PAIRING +//#define BVH_VERBOSE_MOVES //#define BVH_VERBOSE_FRAME //#define BVH_CHECKS @@ -148,7 +153,25 @@ public: } }; -template <class T, int MAX_CHILDREN, int MAX_ITEMS, bool USE_PAIRS = false, class Bounds = AABB, class Point = Vector3> +template <class T> +class BVH_DummyPairTestFunction { +public: + static bool user_collision_check(T *p_a, T *p_b) { + // return false if no collision, decided by masks etc + return true; + } +}; + +template <class T> +class BVH_DummyCullTestFunction { +public: + static bool user_cull_check(T *p_a, T *p_b) { + // return false if no collision + return true; + } +}; + +template <class T, int NUM_TREES, int MAX_CHILDREN, int MAX_ITEMS, class USER_PAIR_TEST_FUNCTION = BVH_DummyPairTestFunction<T>, class USER_CULL_TEST_FUNCTION = BVH_DummyCullTestFunction<T>, bool USE_PAIRS = false, class BOUNDS = AABB, class POINT = Vector3> class BVH_Tree { friend class BVH; @@ -165,6 +188,11 @@ public: // (as these ids are stored as negative numbers in the node) uint32_t dummy_leaf_id; _leaves.request(dummy_leaf_id); + + // In many cases you may want to change this default in the client code, + // or expose this value to the user. + // This default may make sense for a typically scaled 3d game, but maybe not for 2d on a pixel scale. + params_set_pairing_expansion(0.1); } private: @@ -189,7 +217,7 @@ private: BVH_ASSERT(!parent.is_leaf()); int child_num = parent.find_child(p_old_child_id); - BVH_ASSERT(child_num != BVHCommon::INVALID); + BVH_ASSERT(child_num != -1); parent.children[child_num] = p_new_child_id; TNode &new_child = _nodes[p_new_child_id]; @@ -201,7 +229,7 @@ private: BVH_ASSERT(!parent.is_leaf()); int child_num = parent.find_child(p_child_id); - BVH_ASSERT(child_num != BVHCommon::INVALID); + BVH_ASSERT(child_num != -1); parent.remove_child_internal(child_num); @@ -234,7 +262,7 @@ private: change_root_node(sibling_id, p_tree_id); // delete the old root node as no longer needed - _nodes.free(p_parent_id); + node_free_node_and_leaf(p_parent_id); } return; @@ -247,7 +275,19 @@ private: } // put the node on the free list to recycle - _nodes.free(p_parent_id); + node_free_node_and_leaf(p_parent_id); + } + + // A node can either be a node, or a node AND a leaf combo. + // Both must be deleted to prevent a leak. + void node_free_node_and_leaf(uint32_t p_node_id) { + TNode &node = _nodes[p_node_id]; + if (node.is_leaf()) { + int leaf_id = node.get_leaf_id(); + _leaves.free(leaf_id); + } + + _nodes.free(p_node_id); } void change_root_node(uint32_t p_new_root_id, uint32_t p_tree_id) { @@ -339,7 +379,7 @@ private: refit_upward(parent_id); // put the node on the free list to recycle - _nodes.free(owner_node_id); + node_free_node_and_leaf(owner_node_id); } // else if no parent, it is the root node. Do not delete diff --git a/core/math/camera_matrix.cpp b/core/math/camera_matrix.cpp index f4392c74b7..57c53b0adb 100644 --- a/core/math/camera_matrix.cpp +++ b/core/math/camera_matrix.cpp @@ -710,21 +710,26 @@ void CameraMatrix::scale_translate_to_fit(const AABB &p_aabb) { matrix[3][3] = 1; } +void CameraMatrix::add_jitter_offset(const Vector2 &p_offset) { + matrix[3][0] += p_offset.x; + matrix[3][1] += p_offset.y; +} + CameraMatrix::operator Transform3D() const { Transform3D tr; const real_t *m = &matrix[0][0]; - tr.basis.elements[0][0] = m[0]; - tr.basis.elements[1][0] = m[1]; - tr.basis.elements[2][0] = m[2]; + tr.basis.rows[0][0] = m[0]; + tr.basis.rows[1][0] = m[1]; + tr.basis.rows[2][0] = m[2]; - tr.basis.elements[0][1] = m[4]; - tr.basis.elements[1][1] = m[5]; - tr.basis.elements[2][1] = m[6]; + tr.basis.rows[0][1] = m[4]; + tr.basis.rows[1][1] = m[5]; + tr.basis.rows[2][1] = m[6]; - tr.basis.elements[0][2] = m[8]; - tr.basis.elements[1][2] = m[9]; - tr.basis.elements[2][2] = m[10]; + tr.basis.rows[0][2] = m[8]; + tr.basis.rows[1][2] = m[9]; + tr.basis.rows[2][2] = m[10]; tr.origin.x = m[12]; tr.origin.y = m[13]; @@ -737,17 +742,17 @@ CameraMatrix::CameraMatrix(const Transform3D &p_transform) { const Transform3D &tr = p_transform; real_t *m = &matrix[0][0]; - m[0] = tr.basis.elements[0][0]; - m[1] = tr.basis.elements[1][0]; - m[2] = tr.basis.elements[2][0]; + m[0] = tr.basis.rows[0][0]; + m[1] = tr.basis.rows[1][0]; + m[2] = tr.basis.rows[2][0]; m[3] = 0.0; - m[4] = tr.basis.elements[0][1]; - m[5] = tr.basis.elements[1][1]; - m[6] = tr.basis.elements[2][1]; + m[4] = tr.basis.rows[0][1]; + m[5] = tr.basis.rows[1][1]; + m[6] = tr.basis.rows[2][1]; m[7] = 0.0; - m[8] = tr.basis.elements[0][2]; - m[9] = tr.basis.elements[1][2]; - m[10] = tr.basis.elements[2][2]; + m[8] = tr.basis.rows[0][2]; + m[9] = tr.basis.rows[1][2]; + m[10] = tr.basis.rows[2][2]; m[11] = 0.0; m[12] = tr.origin.x; m[13] = tr.origin.y; diff --git a/core/math/camera_matrix.h b/core/math/camera_matrix.h index f1aea5e4e8..a4051cee3b 100644 --- a/core/math/camera_matrix.h +++ b/core/math/camera_matrix.h @@ -95,6 +95,7 @@ struct CameraMatrix { operator String() const; void scale_translate_to_fit(const AABB &p_aabb); + void add_jitter_offset(const Vector2 &p_offset); void make_scale(const Vector3 &p_scale); int get_pixels_per_meter(int p_for_pixel_width) const; operator Transform3D() const; diff --git a/core/math/color.cpp b/core/math/color.cpp index e32f9147d9..4bdeafd2f2 100644 --- a/core/math/color.cpp +++ b/core/math/color.cpp @@ -33,7 +33,9 @@ #include "color_names.inc" #include "core/math/math_funcs.h" #include "core/string/print_string.h" -#include "core/templates/map.h" +#include "core/templates/rb_map.h" + +#include "thirdparty/misc/ok_color.h" uint32_t Color::to_argb32() const { uint32_t c = (uint8_t)Math::round(a * 255); @@ -240,6 +242,20 @@ void Color::set_hsv(float p_h, float p_s, float p_v, float p_alpha) { } } +void Color::set_ok_hsl(float p_h, float p_s, float p_l, float p_alpha) { + ok_color::HSL hsl; + hsl.h = p_h; + hsl.s = p_s; + hsl.l = p_l; + ok_color new_ok_color; + ok_color::RGB rgb = new_ok_color.okhsl_to_srgb(hsl); + Color c = Color(rgb.r, rgb.g, rgb.b, p_alpha).clamp(); + r = c.r; + g = c.g; + b = c.b; + a = c.a; +} + bool Color::is_equal_approx(const Color &p_color) const { return Math::is_equal_approx(r, p_color.r) && Math::is_equal_approx(g, p_color.g) && Math::is_equal_approx(b, p_color.b) && Math::is_equal_approx(a, p_color.a); } @@ -568,3 +584,48 @@ Color Color::operator-() const { 1.0f - b, 1.0f - a); } + +Color Color::from_ok_hsl(float p_h, float p_s, float p_l, float p_alpha) { + Color c; + c.set_ok_hsl(p_h, p_s, p_l, p_alpha); + return c; +} + +float Color::get_ok_hsl_h() const { + ok_color::RGB rgb; + rgb.r = r; + rgb.g = g; + rgb.b = b; + ok_color new_ok_color; + ok_color::HSL ok_hsl = new_ok_color.srgb_to_okhsl(rgb); + if (Math::is_nan(ok_hsl.h)) { + return 0.0f; + } + return CLAMP(ok_hsl.h, 0.0f, 1.0f); +} + +float Color::get_ok_hsl_s() const { + ok_color::RGB rgb; + rgb.r = r; + rgb.g = g; + rgb.b = b; + ok_color new_ok_color; + ok_color::HSL ok_hsl = new_ok_color.srgb_to_okhsl(rgb); + if (Math::is_nan(ok_hsl.s)) { + return 0.0f; + } + return CLAMP(ok_hsl.s, 0.0f, 1.0f); +} + +float Color::get_ok_hsl_l() const { + ok_color::RGB rgb; + rgb.r = r; + rgb.g = g; + rgb.b = b; + ok_color new_ok_color; + ok_color::HSL ok_hsl = new_ok_color.srgb_to_okhsl(rgb); + if (Math::is_nan(ok_hsl.l)) { + return 0.0f; + } + return CLAMP(ok_hsl.l, 0.0f, 1.0f); +} diff --git a/core/math/color.h b/core/math/color.h index b90a0f33a2..0afa6006a8 100644 --- a/core/math/color.h +++ b/core/math/color.h @@ -56,6 +56,10 @@ struct _NO_DISCARD_ Color { float get_s() const; float get_v() const; void set_hsv(float p_h, float p_s, float p_v, float p_alpha = 1.0); + float get_ok_hsl_h() const; + float get_ok_hsl_s() const; + float get_ok_hsl_l() const; + void set_ok_hsl(float p_h, float p_s, float p_l, float p_alpha = 1.0); _FORCE_INLINE_ float &operator[](int p_idx) { return components[p_idx]; @@ -169,14 +173,14 @@ struct _NO_DISCARD_ Color { return res; } - _FORCE_INLINE_ Color to_linear() const { + _FORCE_INLINE_ Color srgb_to_linear() const { return Color( r < 0.04045f ? r * (1.0 / 12.92) : Math::pow((r + 0.055f) * (float)(1.0 / (1 + 0.055)), 2.4f), g < 0.04045f ? g * (1.0 / 12.92) : Math::pow((g + 0.055f) * (float)(1.0 / (1 + 0.055)), 2.4f), b < 0.04045f ? b * (1.0 / 12.92) : Math::pow((b + 0.055f) * (float)(1.0 / (1 + 0.055)), 2.4f), a); } - _FORCE_INLINE_ Color to_srgb() const { + _FORCE_INLINE_ Color linear_to_srgb() const { return Color( r < 0.0031308f ? 12.92f * r : (1.0f + 0.055f) * Math::pow(r, 1.0f / 2.4f) - 0.055f, g < 0.0031308f ? 12.92f * g : (1.0f + 0.055f) * Math::pow(g, 1.0f / 2.4f) - 0.055f, @@ -195,6 +199,7 @@ struct _NO_DISCARD_ Color { static Color get_named_color(int p_idx); static Color from_string(const String &p_string, const Color &p_default); static Color from_hsv(float p_h, float p_s, float p_v, float p_alpha = 1.0); + static Color from_ok_hsl(float p_h, float p_s, float p_l, float p_alpha = 1.0); static Color from_rgbe9995(uint32_t p_rgbe); _FORCE_INLINE_ bool operator<(const Color &p_color) const; //used in set keys @@ -213,6 +218,9 @@ struct _NO_DISCARD_ Color { _FORCE_INLINE_ void set_h(float p_h) { set_hsv(p_h, get_s(), get_v()); } _FORCE_INLINE_ void set_s(float p_s) { set_hsv(get_h(), p_s, get_v()); } _FORCE_INLINE_ void set_v(float p_v) { set_hsv(get_h(), get_s(), p_v); } + _FORCE_INLINE_ void set_ok_hsl_h(float p_h) { set_ok_hsl(p_h, get_ok_hsl_s(), get_ok_hsl_l()); } + _FORCE_INLINE_ void set_ok_hsl_s(float p_s) { set_ok_hsl(get_ok_hsl_h(), p_s, get_ok_hsl_l()); } + _FORCE_INLINE_ void set_ok_hsl_l(float p_l) { set_ok_hsl(get_ok_hsl_h(), get_ok_hsl_s(), p_l); } _FORCE_INLINE_ Color() {} diff --git a/core/math/color_names.inc b/core/math/color_names.inc index 2020bdbfca..654fa83877 100644 --- a/core/math/color_names.inc +++ b/core/math/color_names.inc @@ -13,151 +13,151 @@ struct NamedColor { // modules/mono/glue/GodotSharp/GodotSharp/Core/Colors.cs static NamedColor named_colors[] = { - { "ALICE_BLUE", Color(0.94, 0.97, 1.00) }, - { "ANTIQUE_WHITE", Color(0.98, 0.92, 0.84) }, - { "AQUA", Color(0.00, 1.00, 1.00) }, - { "AQUAMARINE", Color(0.50, 1.00, 0.83) }, - { "AZURE", Color(0.94, 1.00, 1.00) }, - { "BEIGE", Color(0.96, 0.96, 0.86) }, - { "BISQUE", Color(1.00, 0.89, 0.77) }, - { "BLACK", Color(0.00, 0.00, 0.00) }, - { "BLANCHED_ALMOND", Color(1.00, 0.92, 0.80) }, - { "BLUE", Color(0.00, 0.00, 1.00) }, - { "BLUE_VIOLET", Color(0.54, 0.17, 0.89) }, - { "BROWN", Color(0.65, 0.16, 0.16) }, - { "BURLYWOOD", Color(0.87, 0.72, 0.53) }, - { "CADET_BLUE", Color(0.37, 0.62, 0.63) }, - { "CHARTREUSE", Color(0.50, 1.00, 0.00) }, - { "CHOCOLATE", Color(0.82, 0.41, 0.12) }, - { "CORAL", Color(1.00, 0.50, 0.31) }, - { "CORNFLOWER_BLUE", Color(0.39, 0.58, 0.93) }, - { "CORNSILK", Color(1.00, 0.97, 0.86) }, - { "CRIMSON", Color(0.86, 0.08, 0.24) }, - { "CYAN", Color(0.00, 1.00, 1.00) }, - { "DARK_BLUE", Color(0.00, 0.00, 0.55) }, - { "DARK_CYAN", Color(0.00, 0.55, 0.55) }, - { "DARK_GOLDENROD", Color(0.72, 0.53, 0.04) }, - { "DARK_GRAY", Color(0.66, 0.66, 0.66) }, - { "DARK_GREEN", Color(0.00, 0.39, 0.00) }, - { "DARK_KHAKI", Color(0.74, 0.72, 0.42) }, - { "DARK_MAGENTA", Color(0.55, 0.00, 0.55) }, - { "DARK_OLIVE_GREEN", Color(0.33, 0.42, 0.18) }, - { "DARK_ORANGE", Color(1.00, 0.55, 0.00) }, - { "DARK_ORCHID", Color(0.60, 0.20, 0.80) }, - { "DARK_RED", Color(0.55, 0.00, 0.00) }, - { "DARK_SALMON", Color(0.91, 0.59, 0.48) }, - { "DARK_SEA_GREEN", Color(0.56, 0.74, 0.56) }, - { "DARK_SLATE_BLUE", Color(0.28, 0.24, 0.55) }, - { "DARK_SLATE_GRAY", Color(0.18, 0.31, 0.31) }, - { "DARK_TURQUOISE", Color(0.00, 0.81, 0.82) }, - { "DARK_VIOLET", Color(0.58, 0.00, 0.83) }, - { "DEEP_PINK", Color(1.00, 0.08, 0.58) }, - { "DEEP_SKY_BLUE", Color(0.00, 0.75, 1.00) }, - { "DIM_GRAY", Color(0.41, 0.41, 0.41) }, - { "DODGER_BLUE", Color(0.12, 0.56, 1.00) }, - { "FIREBRICK", Color(0.70, 0.13, 0.13) }, - { "FLORAL_WHITE", Color(1.00, 0.98, 0.94) }, - { "FOREST_GREEN", Color(0.13, 0.55, 0.13) }, - { "FUCHSIA", Color(1.00, 0.00, 1.00) }, - { "GAINSBORO", Color(0.86, 0.86, 0.86) }, - { "GHOST_WHITE", Color(0.97, 0.97, 1.00) }, - { "GOLD", Color(1.00, 0.84, 0.00) }, - { "GOLDENROD", Color(0.85, 0.65, 0.13) }, - { "GRAY", Color(0.75, 0.75, 0.75) }, - { "GREEN", Color(0.00, 1.00, 0.00) }, - { "GREEN_YELLOW", Color(0.68, 1.00, 0.18) }, - { "HONEYDEW", Color(0.94, 1.00, 0.94) }, - { "HOT_PINK", Color(1.00, 0.41, 0.71) }, - { "INDIAN_RED", Color(0.80, 0.36, 0.36) }, - { "INDIGO", Color(0.29, 0.00, 0.51) }, - { "IVORY", Color(1.00, 1.00, 0.94) }, - { "KHAKI", Color(0.94, 0.90, 0.55) }, - { "LAVENDER", Color(0.90, 0.90, 0.98) }, - { "LAVENDER_BLUSH", Color(1.00, 0.94, 0.96) }, - { "LAWN_GREEN", Color(0.49, 0.99, 0.00) }, - { "LEMON_CHIFFON", Color(1.00, 0.98, 0.80) }, - { "LIGHT_BLUE", Color(0.68, 0.85, 0.90) }, - { "LIGHT_CORAL", Color(0.94, 0.50, 0.50) }, - { "LIGHT_CYAN", Color(0.88, 1.00, 1.00) }, - { "LIGHT_GOLDENROD", Color(0.98, 0.98, 0.82) }, - { "LIGHT_GRAY", Color(0.83, 0.83, 0.83) }, - { "LIGHT_GREEN", Color(0.56, 0.93, 0.56) }, - { "LIGHT_PINK", Color(1.00, 0.71, 0.76) }, - { "LIGHT_SALMON", Color(1.00, 0.63, 0.48) }, - { "LIGHT_SEA_GREEN", Color(0.13, 0.70, 0.67) }, - { "LIGHT_SKY_BLUE", Color(0.53, 0.81, 0.98) }, - { "LIGHT_SLATE_GRAY", Color(0.47, 0.53, 0.60) }, - { "LIGHT_STEEL_BLUE", Color(0.69, 0.77, 0.87) }, - { "LIGHT_YELLOW", Color(1.00, 1.00, 0.88) }, - { "LIME", Color(0.00, 1.00, 0.00) }, - { "LIME_GREEN", Color(0.20, 0.80, 0.20) }, - { "LINEN", Color(0.98, 0.94, 0.90) }, - { "MAGENTA", Color(1.00, 0.00, 1.00) }, - { "MAROON", Color(0.69, 0.19, 0.38) }, - { "MEDIUM_AQUAMARINE", Color(0.40, 0.80, 0.67) }, - { "MEDIUM_BLUE", Color(0.00, 0.00, 0.80) }, - { "MEDIUM_ORCHID", Color(0.73, 0.33, 0.83) }, - { "MEDIUM_PURPLE", Color(0.58, 0.44, 0.86) }, - { "MEDIUM_SEA_GREEN", Color(0.24, 0.70, 0.44) }, - { "MEDIUM_SLATE_BLUE", Color(0.48, 0.41, 0.93) }, - { "MEDIUM_SPRING_GREEN", Color(0.00, 0.98, 0.60) }, - { "MEDIUM_TURQUOISE", Color(0.28, 0.82, 0.80) }, - { "MEDIUM_VIOLET_RED", Color(0.78, 0.08, 0.52) }, - { "MIDNIGHT_BLUE", Color(0.10, 0.10, 0.44) }, - { "MINT_CREAM", Color(0.96, 1.00, 0.98) }, - { "MISTY_ROSE", Color(1.00, 0.89, 0.88) }, - { "MOCCASIN", Color(1.00, 0.89, 0.71) }, - { "NAVAJO_WHITE", Color(1.00, 0.87, 0.68) }, - { "NAVY_BLUE", Color(0.00, 0.00, 0.50) }, - { "OLD_LACE", Color(0.99, 0.96, 0.90) }, - { "OLIVE", Color(0.50, 0.50, 0.00) }, - { "OLIVE_DRAB", Color(0.42, 0.56, 0.14) }, - { "ORANGE", Color(1.00, 0.65, 0.00) }, - { "ORANGE_RED", Color(1.00, 0.27, 0.00) }, - { "ORCHID", Color(0.85, 0.44, 0.84) }, - { "PALE_GOLDENROD", Color(0.93, 0.91, 0.67) }, - { "PALE_GREEN", Color(0.60, 0.98, 0.60) }, - { "PALE_TURQUOISE", Color(0.69, 0.93, 0.93) }, - { "PALE_VIOLET_RED", Color(0.86, 0.44, 0.58) }, - { "PAPAYA_WHIP", Color(1.00, 0.94, 0.84) }, - { "PEACH_PUFF", Color(1.00, 0.85, 0.73) }, - { "PERU", Color(0.80, 0.52, 0.25) }, - { "PINK", Color(1.00, 0.75, 0.80) }, - { "PLUM", Color(0.87, 0.63, 0.87) }, - { "POWDER_BLUE", Color(0.69, 0.88, 0.90) }, - { "PURPLE", Color(0.63, 0.13, 0.94) }, - { "REBECCA_PURPLE", Color(0.40, 0.20, 0.60) }, - { "RED", Color(1.00, 0.00, 0.00) }, - { "ROSY_BROWN", Color(0.74, 0.56, 0.56) }, - { "ROYAL_BLUE", Color(0.25, 0.41, 0.88) }, - { "SADDLE_BROWN", Color(0.55, 0.27, 0.07) }, - { "SALMON", Color(0.98, 0.50, 0.45) }, - { "SANDY_BROWN", Color(0.96, 0.64, 0.38) }, - { "SEA_GREEN", Color(0.18, 0.55, 0.34) }, - { "SEASHELL", Color(1.00, 0.96, 0.93) }, - { "SIENNA", Color(0.63, 0.32, 0.18) }, - { "SILVER", Color(0.75, 0.75, 0.75) }, - { "SKY_BLUE", Color(0.53, 0.81, 0.92) }, - { "SLATE_BLUE", Color(0.42, 0.35, 0.80) }, - { "SLATE_GRAY", Color(0.44, 0.50, 0.56) }, - { "SNOW", Color(1.00, 0.98, 0.98) }, - { "SPRING_GREEN", Color(0.00, 1.00, 0.50) }, - { "STEEL_BLUE", Color(0.27, 0.51, 0.71) }, - { "TAN", Color(0.82, 0.71, 0.55) }, - { "TEAL", Color(0.00, 0.50, 0.50) }, - { "THISTLE", Color(0.85, 0.75, 0.85) }, - { "TOMATO", Color(1.00, 0.39, 0.28) }, - { "TRANSPARENT", Color(1.00, 1.00, 1.00, 0.00) }, - { "TURQUOISE", Color(0.25, 0.88, 0.82) }, - { "VIOLET", Color(0.93, 0.51, 0.93) }, - { "WEB_GRAY", Color(0.50, 0.50, 0.50) }, - { "WEB_GREEN", Color(0.00, 0.50, 0.00) }, - { "WEB_MAROON", Color(0.50, 0.00, 0.00) }, - { "WEB_PURPLE", Color(0.50, 0.00, 0.50) }, - { "WHEAT", Color(0.96, 0.87, 0.70) }, - { "WHITE", Color(1.00, 1.00, 1.00) }, - { "WHITE_SMOKE", Color(0.96, 0.96, 0.96) }, - { "YELLOW", Color(1.00, 1.00, 0.00) }, - { "YELLOW_GREEN", Color(0.60, 0.80, 0.20) }, + { "ALICE_BLUE", Color::hex(0xF0F8FFFF) }, + { "ANTIQUE_WHITE", Color::hex(0xFAEBD7FF) }, + { "AQUA", Color::hex(0x00FFFFFF) }, + { "AQUAMARINE", Color::hex(0x7FFFD4FF) }, + { "AZURE", Color::hex(0xF0FFFFFF) }, + { "BEIGE", Color::hex(0xF5F5DCFF) }, + { "BISQUE", Color::hex(0xFFE4C4FF) }, + { "BLACK", Color::hex(0x000000FF) }, + { "BLANCHED_ALMOND", Color::hex(0xFFEBCDFF) }, + { "BLUE", Color::hex(0x0000FFFF) }, + { "BLUE_VIOLET", Color::hex(0x8A2BE2FF) }, + { "BROWN", Color::hex(0xA52A2AFF) }, + { "BURLYWOOD", Color::hex(0xDEB887FF) }, + { "CADET_BLUE", Color::hex(0x5F9EA0FF) }, + { "CHARTREUSE", Color::hex(0x7FFF00FF) }, + { "CHOCOLATE", Color::hex(0xD2691EFF) }, + { "CORAL", Color::hex(0xFF7F50FF) }, + { "CORNFLOWER_BLUE", Color::hex(0x6495EDFF) }, + { "CORNSILK", Color::hex(0xFFF8DCFF) }, + { "CRIMSON", Color::hex(0xDC143CFF) }, + { "CYAN", Color::hex(0x00FFFFFF) }, + { "DARK_BLUE", Color::hex(0x00008BFF) }, + { "DARK_CYAN", Color::hex(0x008B8BFF) }, + { "DARK_GOLDENROD", Color::hex(0xB8860BFF) }, + { "DARK_GRAY", Color::hex(0xA9A9A9FF) }, + { "DARK_GREEN", Color::hex(0x006400FF) }, + { "DARK_KHAKI", Color::hex(0xBDB76BFF) }, + { "DARK_MAGENTA", Color::hex(0x8B008BFF) }, + { "DARK_OLIVE_GREEN", Color::hex(0x556B2FFF) }, + { "DARK_ORANGE", Color::hex(0xFF8C00FF) }, + { "DARK_ORCHID", Color::hex(0x9932CCFF) }, + { "DARK_RED", Color::hex(0x8B0000FF) }, + { "DARK_SALMON", Color::hex(0xE9967AFF) }, + { "DARK_SEA_GREEN", Color::hex(0x8FBC8FFF) }, + { "DARK_SLATE_BLUE", Color::hex(0x483D8BFF) }, + { "DARK_SLATE_GRAY", Color::hex(0x2F4F4FFF) }, + { "DARK_TURQUOISE", Color::hex(0x00CED1FF) }, + { "DARK_VIOLET", Color::hex(0x9400D3FF) }, + { "DEEP_PINK", Color::hex(0xFF1493FF) }, + { "DEEP_SKY_BLUE", Color::hex(0x00BFFFFF) }, + { "DIM_GRAY", Color::hex(0x696969FF) }, + { "DODGER_BLUE", Color::hex(0x1E90FFFF) }, + { "FIREBRICK", Color::hex(0xB22222FF) }, + { "FLORAL_WHITE", Color::hex(0xFFFAF0FF) }, + { "FOREST_GREEN", Color::hex(0x228B22FF) }, + { "FUCHSIA", Color::hex(0xFF00FFFF) }, + { "GAINSBORO", Color::hex(0xDCDCDCFF) }, + { "GHOST_WHITE", Color::hex(0xF8F8FFFF) }, + { "GOLD", Color::hex(0xFFD700FF) }, + { "GOLDENROD", Color::hex(0xDAA520FF) }, + { "GRAY", Color::hex(0xBEBEBEFF) }, + { "GREEN", Color::hex(0x00FF00FF) }, + { "GREEN_YELLOW", Color::hex(0xADFF2FFF) }, + { "HONEYDEW", Color::hex(0xF0FFF0FF) }, + { "HOT_PINK", Color::hex(0xFF69B4FF) }, + { "INDIAN_RED", Color::hex(0xCD5C5CFF) }, + { "INDIGO", Color::hex(0x4B0082FF) }, + { "IVORY", Color::hex(0xFFFFF0FF) }, + { "KHAKI", Color::hex(0xF0E68CFF) }, + { "LAVENDER", Color::hex(0xE6E6FAFF) }, + { "LAVENDER_BLUSH", Color::hex(0xFFF0F5FF) }, + { "LAWN_GREEN", Color::hex(0x7CFC00FF) }, + { "LEMON_CHIFFON", Color::hex(0xFFFACDFF) }, + { "LIGHT_BLUE", Color::hex(0xADD8E6FF) }, + { "LIGHT_CORAL", Color::hex(0xF08080FF) }, + { "LIGHT_CYAN", Color::hex(0xE0FFFFFF) }, + { "LIGHT_GOLDENROD", Color::hex(0xFAFAD2FF) }, + { "LIGHT_GRAY", Color::hex(0xD3D3D3FF) }, + { "LIGHT_GREEN", Color::hex(0x90EE90FF) }, + { "LIGHT_PINK", Color::hex(0xFFB6C1FF) }, + { "LIGHT_SALMON", Color::hex(0xFFA07AFF) }, + { "LIGHT_SEA_GREEN", Color::hex(0x20B2AAFF) }, + { "LIGHT_SKY_BLUE", Color::hex(0x87CEFAFF) }, + { "LIGHT_SLATE_GRAY", Color::hex(0x778899FF) }, + { "LIGHT_STEEL_BLUE", Color::hex(0xB0C4DEFF) }, + { "LIGHT_YELLOW", Color::hex(0xFFFFE0FF) }, + { "LIME", Color::hex(0x00FF00FF) }, + { "LIME_GREEN", Color::hex(0x32CD32FF) }, + { "LINEN", Color::hex(0xFAF0E6FF) }, + { "MAGENTA", Color::hex(0xFF00FFFF) }, + { "MAROON", Color::hex(0xB03060FF) }, + { "MEDIUM_AQUAMARINE", Color::hex(0x66CDAAFF) }, + { "MEDIUM_BLUE", Color::hex(0x0000CDFF) }, + { "MEDIUM_ORCHID", Color::hex(0xBA55D3FF) }, + { "MEDIUM_PURPLE", Color::hex(0x9370DBFF) }, + { "MEDIUM_SEA_GREEN", Color::hex(0x3CB371FF) }, + { "MEDIUM_SLATE_BLUE", Color::hex(0x7B68EEFF) }, + { "MEDIUM_SPRING_GREEN", Color::hex(0x00FA9AFF) }, + { "MEDIUM_TURQUOISE", Color::hex(0x48D1CCFF) }, + { "MEDIUM_VIOLET_RED", Color::hex(0xC71585FF) }, + { "MIDNIGHT_BLUE", Color::hex(0x191970FF) }, + { "MINT_CREAM", Color::hex(0xF5FFFAFF) }, + { "MISTY_ROSE", Color::hex(0xFFE4E1FF) }, + { "MOCCASIN", Color::hex(0xFFE4B5FF) }, + { "NAVAJO_WHITE", Color::hex(0xFFDEADFF) }, + { "NAVY_BLUE", Color::hex(0x000080FF) }, + { "OLD_LACE", Color::hex(0xFDF5E6FF) }, + { "OLIVE", Color::hex(0x808000FF) }, + { "OLIVE_DRAB", Color::hex(0x6B8E23FF) }, + { "ORANGE", Color::hex(0xFFA500FF) }, + { "ORANGE_RED", Color::hex(0xFF4500FF) }, + { "ORCHID", Color::hex(0xDA70D6FF) }, + { "PALE_GOLDENROD", Color::hex(0xEEE8AAFF) }, + { "PALE_GREEN", Color::hex(0x98FB98FF) }, + { "PALE_TURQUOISE", Color::hex(0xAFEEEEFF) }, + { "PALE_VIOLET_RED", Color::hex(0xDB7093FF) }, + { "PAPAYA_WHIP", Color::hex(0xFFEFD5FF) }, + { "PEACH_PUFF", Color::hex(0xFFDAB9FF) }, + { "PERU", Color::hex(0xCD853FFF) }, + { "PINK", Color::hex(0xFFC0CBFF) }, + { "PLUM", Color::hex(0xDDA0DDFF) }, + { "POWDER_BLUE", Color::hex(0xB0E0E6FF) }, + { "PURPLE", Color::hex(0xA020F0FF) }, + { "REBECCA_PURPLE", Color::hex(0x663399FF) }, + { "RED", Color::hex(0xFF0000FF) }, + { "ROSY_BROWN", Color::hex(0xBC8F8FFF) }, + { "ROYAL_BLUE", Color::hex(0x4169E1FF) }, + { "SADDLE_BROWN", Color::hex(0x8B4513FF) }, + { "SALMON", Color::hex(0xFA8072FF) }, + { "SANDY_BROWN", Color::hex(0xF4A460FF) }, + { "SEA_GREEN", Color::hex(0x2E8B57FF) }, + { "SEASHELL", Color::hex(0xFFF5EEFF) }, + { "SIENNA", Color::hex(0xA0522DFF) }, + { "SILVER", Color::hex(0xC0C0C0FF) }, + { "SKY_BLUE", Color::hex(0x87CEEBFF) }, + { "SLATE_BLUE", Color::hex(0x6A5ACDFF) }, + { "SLATE_GRAY", Color::hex(0x708090FF) }, + { "SNOW", Color::hex(0xFFFAFAFF) }, + { "SPRING_GREEN", Color::hex(0x00FF7FFF) }, + { "STEEL_BLUE", Color::hex(0x4682B4FF) }, + { "TAN", Color::hex(0xD2B48CFF) }, + { "TEAL", Color::hex(0x008080FF) }, + { "THISTLE", Color::hex(0xD8BFD8FF) }, + { "TOMATO", Color::hex(0xFF6347FF) }, + { "TRANSPARENT", Color::hex(0xFFFFFF00) }, + { "TURQUOISE", Color::hex(0x40E0D0FF) }, + { "VIOLET", Color::hex(0xEE82EEFF) }, + { "WEB_GRAY", Color::hex(0x808080FF) }, + { "WEB_GREEN", Color::hex(0x008000FF) }, + { "WEB_MAROON", Color::hex(0x800000FF) }, + { "WEB_PURPLE", Color::hex(0x800080FF) }, + { "WHEAT", Color::hex(0xF5DEB3FF) }, + { "WHITE", Color::hex(0xFFFFFFFF) }, + { "WHITE_SMOKE", Color::hex(0xF5F5F5FF) }, + { "YELLOW", Color::hex(0xFFFF00FF) }, + { "YELLOW_GREEN", Color::hex(0x9ACD32FF) }, { nullptr, Color() }, }; diff --git a/core/math/convex_hull.cpp b/core/math/convex_hull.cpp index bd292f4c2a..996f4f4d67 100644 --- a/core/math/convex_hull.cpp +++ b/core/math/convex_hull.cpp @@ -509,7 +509,7 @@ public: Face() { } - void init(Vertex *p_a, Vertex *p_b, Vertex *p_c) { + void init(Vertex *p_a, const Vertex *p_b, const Vertex *p_c) { nearby_vertex = p_a; origin = p_a->point; dir0 = *p_b - *p_a; @@ -614,7 +614,7 @@ private: static Orientation get_orientation(const Edge *p_prev, const Edge *p_next, const Point32 &p_s, const Point32 &p_t); Edge *find_max_angle(bool p_ccw, const Vertex *p_start, const Point32 &p_s, const Point64 &p_rxs, const Point64 &p_ssxrxs, Rational64 &p_min_cot); - void find_edge_for_coplanar_faces(Vertex *p_c0, Vertex *p_c1, Edge *&p_e0, Edge *&p_e1, Vertex *p_stop0, Vertex *p_stop1); + void find_edge_for_coplanar_faces(Vertex *p_c0, Vertex *p_c1, Edge *&p_e0, Edge *&p_e1, const Vertex *p_stop0, const Vertex *p_stop1); Edge *new_edge_pair(Vertex *p_from, Vertex *p_to); @@ -666,7 +666,7 @@ public: face_pool.reset(true); } - Vertex *vertex_list; + Vertex *vertex_list = nullptr; void compute(const Vector3 *p_coords, int32_t p_count); @@ -1189,7 +1189,7 @@ ConvexHullInternal::Edge *ConvexHullInternal::find_max_angle(bool p_ccw, const V return min_edge; } -void ConvexHullInternal::find_edge_for_coplanar_faces(Vertex *p_c0, Vertex *p_c1, Edge *&p_e0, Edge *&p_e1, Vertex *p_stop0, Vertex *p_stop1) { +void ConvexHullInternal::find_edge_for_coplanar_faces(Vertex *p_c0, Vertex *p_c1, Edge *&p_e0, Edge *&p_e1, const Vertex *p_stop0, const Vertex *p_stop1) { Edge *start0 = p_e0; Edge *start1 = p_e1; Point32 et0 = start0 ? start0->target->point : p_c0->point; diff --git a/core/math/delaunay_3d.h b/core/math/delaunay_3d.h index 7ad5f76645..f8a10ec87e 100644 --- a/core/math/delaunay_3d.h +++ b/core/math/delaunay_3d.h @@ -323,7 +323,6 @@ public: E = N; } - uint32_t good_triangles = 0; for (uint32_t j = 0; j < triangles.size(); j++) { if (triangles[j].bad) { continue; @@ -360,11 +359,8 @@ public: } } } - - good_triangles++; } - //print_line("at point " + itos(i) + "/" + itos(point_count) + " simplices added " + itos(good_triangles) + "/" + itos(simplex_list.size()) + " - triangles: " + itos(triangles.size())); triangles.clear(); triangles_inserted.clear(); } diff --git a/core/math/disjoint_set.h b/core/math/disjoint_set.h index 8657dc068e..d07c08e45e 100644 --- a/core/math/disjoint_set.h +++ b/core/math/disjoint_set.h @@ -31,11 +31,11 @@ #ifndef DISJOINT_SET_H #define DISJOINT_SET_H -#include "core/templates/map.h" +#include "core/templates/rb_map.h" #include "core/templates/vector.h" /* This DisjointSet class uses Find with path compression and Union by rank */ -template <typename T, class C = Comparator<T>, class AL = DefaultAllocator> +template <typename T, class H = HashMapHasherDefault, class C = HashMapComparatorDefault<T>, class AL = DefaultAllocator> class DisjointSet { struct Element { T object; @@ -43,7 +43,7 @@ class DisjointSet { int rank = 0; }; - typedef Map<T, Element *, C, AL> MapT; + typedef HashMap<T, Element *, H, C> MapT; MapT elements; @@ -65,15 +65,15 @@ public: /* FUNCTIONS */ -template <typename T, class C, class AL> -DisjointSet<T, C, AL>::~DisjointSet() { - for (typename MapT::Element *itr = elements.front(); itr != nullptr; itr = itr->next()) { - memdelete_allocator<Element, AL>(itr->value()); +template <typename T, class H, class C, class AL> +DisjointSet<T, H, C, AL>::~DisjointSet() { + for (KeyValue<T, Element *> &E : elements) { + memdelete_allocator<Element, AL>(E.value); } } -template <typename T, class C, class AL> -typename DisjointSet<T, C, AL>::Element *DisjointSet<T, C, AL>::get_parent(Element *element) { +template <typename T, class H, class C, class AL> +typename DisjointSet<T, H, C, AL>::Element *DisjointSet<T, H, C, AL>::get_parent(Element *element) { if (element->parent != element) { element->parent = get_parent(element->parent); } @@ -81,11 +81,11 @@ typename DisjointSet<T, C, AL>::Element *DisjointSet<T, C, AL>::get_parent(Eleme return element->parent; } -template <typename T, class C, class AL> -typename DisjointSet<T, C, AL>::Element *DisjointSet<T, C, AL>::insert_or_get(T object) { - typename MapT::Element *itr = elements.find(object); +template <typename T, class H, class C, class AL> +typename DisjointSet<T, H, C, AL>::Element *DisjointSet<T, H, C, AL>::insert_or_get(T object) { + typename MapT::Iterator itr = elements.find(object); if (itr != nullptr) { - return itr->value(); + return itr->value; } Element *new_element = memnew_allocator(Element, AL); @@ -96,8 +96,8 @@ typename DisjointSet<T, C, AL>::Element *DisjointSet<T, C, AL>::insert_or_get(T return new_element; } -template <typename T, class C, class AL> -void DisjointSet<T, C, AL>::create_union(T a, T b) { +template <typename T, class H, class C, class AL> +void DisjointSet<T, H, C, AL>::create_union(T a, T b) { Element *x = insert_or_get(a); Element *y = insert_or_get(b); @@ -121,28 +121,28 @@ void DisjointSet<T, C, AL>::create_union(T a, T b) { } } -template <typename T, class C, class AL> -void DisjointSet<T, C, AL>::get_representatives(Vector<T> &out_representatives) { - for (typename MapT::Element *itr = elements.front(); itr != nullptr; itr = itr->next()) { - Element *element = itr->value(); +template <typename T, class H, class C, class AL> +void DisjointSet<T, H, C, AL>::get_representatives(Vector<T> &out_representatives) { + for (KeyValue<T, Element *> &E : elements) { + Element *element = E.value; if (element->parent == element) { out_representatives.push_back(element->object); } } } -template <typename T, class C, class AL> -void DisjointSet<T, C, AL>::get_members(Vector<T> &out_members, T representative) { - typename MapT::Element *rep_itr = elements.find(representative); +template <typename T, class H, class C, class AL> +void DisjointSet<T, H, C, AL>::get_members(Vector<T> &out_members, T representative) { + typename MapT::Iterator rep_itr = elements.find(representative); ERR_FAIL_COND(rep_itr == nullptr); - Element *rep_element = rep_itr->value(); + Element *rep_element = rep_itr->value; ERR_FAIL_COND(rep_element->parent != rep_element); - for (typename MapT::Element *itr = elements.front(); itr != nullptr; itr = itr->next()) { - Element *parent = get_parent(itr->value()); + for (KeyValue<T, Element *> &E : elements) { + Element *parent = get_parent(E.value); if (parent == rep_element) { - out_members.push_back(itr->key()); + out_members.push_back(E.key); } } } diff --git a/core/math/expression.cpp b/core/math/expression.cpp index 0ddac9744e..5a90f68b66 100644 --- a/core/math/expression.cpp +++ b/core/math/expression.cpp @@ -155,7 +155,12 @@ Error Expression::_get_token(Token &r_token) { return OK; } case '*': { - r_token.type = TK_OP_MUL; + if (expression[str_ofs] == '*') { + r_token.type = TK_OP_POW; + str_ofs++; + } else { + r_token.type = TK_OP_MUL; + } return OK; } case '%': { @@ -542,6 +547,7 @@ const char *Expression::token_name[TK_MAX] = { "OP MUL", "OP DIV", "OP MOD", + "OP POW", "OP SHIFT LEFT", "OP SHIFT RIGHT", "OP BIT AND", @@ -1013,6 +1019,9 @@ Expression::ENode *Expression::_parse_expression() { case TK_OP_MOD: op = Variant::OP_MODULE; break; + case TK_OP_POW: + op = Variant::OP_POWER; + break; case TK_OP_SHIFT_LEFT: op = Variant::OP_SHIFT_LEFT; break; @@ -1066,35 +1075,38 @@ Expression::ENode *Expression::_parse_expression() { bool unary = false; switch (expression[i].op) { - case Variant::OP_BIT_NEGATE: + case Variant::OP_POWER: priority = 0; + break; + case Variant::OP_BIT_NEGATE: + priority = 1; unary = true; break; case Variant::OP_NEGATE: - priority = 1; + priority = 2; unary = true; break; case Variant::OP_MULTIPLY: case Variant::OP_DIVIDE: case Variant::OP_MODULE: - priority = 2; + priority = 3; break; case Variant::OP_ADD: case Variant::OP_SUBTRACT: - priority = 3; + priority = 4; break; case Variant::OP_SHIFT_LEFT: case Variant::OP_SHIFT_RIGHT: - priority = 4; + priority = 5; break; case Variant::OP_BIT_AND: - priority = 5; + priority = 6; break; case Variant::OP_BIT_XOR: - priority = 6; + priority = 7; break; case Variant::OP_BIT_OR: - priority = 7; + priority = 8; break; case Variant::OP_LESS: case Variant::OP_LESS_EQUAL: @@ -1102,20 +1114,20 @@ Expression::ENode *Expression::_parse_expression() { case Variant::OP_GREATER_EQUAL: case Variant::OP_EQUAL: case Variant::OP_NOT_EQUAL: - priority = 8; + priority = 9; break; case Variant::OP_IN: - priority = 10; + priority = 11; break; case Variant::OP_NOT: - priority = 11; + priority = 12; unary = true; break; case Variant::OP_AND: - priority = 12; + priority = 13; break; case Variant::OP_OR: - priority = 13; + priority = 14; break; default: { _set_error("Parser bug, invalid operator in expression: " + itos(expression[i].op)); @@ -1233,7 +1245,7 @@ bool Expression::_execute(const Array &p_inputs, Object *p_instance, Expression: case Expression::ENode::TYPE_INPUT: { const Expression::InputNode *in = static_cast<const Expression::InputNode *>(p_node); if (in->index < 0 || in->index >= p_inputs.size()) { - r_error_str = vformat(RTR("Invalid input %i (not passed) in expression"), in->index); + r_error_str = vformat(RTR("Invalid input %d (not passed) in expression"), in->index); return true; } r_ret = p_inputs[in->index]; @@ -1440,7 +1452,7 @@ bool Expression::_execute(const Array &p_inputs, Object *p_instance, Expression: } Callable::CallError ce; - base.call(call->method, (const Variant **)argp.ptr(), argp.size(), r_ret, ce); + base.callp(call->method, (const Variant **)argp.ptr(), argp.size(), r_ret, ce); if (ce.error != Callable::CallError::CALL_OK) { r_error_str = vformat(RTR("On call to '%s':"), String(call->method)); diff --git a/core/math/expression.h b/core/math/expression.h index 9b87bdd6ec..6ea3c1611f 100644 --- a/core/math/expression.h +++ b/core/math/expression.h @@ -85,6 +85,7 @@ private: TK_OP_MUL, TK_OP_DIV, TK_OP_MOD, + TK_OP_POW, TK_OP_SHIFT_LEFT, TK_OP_SHIFT_RIGHT, TK_OP_BIT_AND, @@ -147,7 +148,7 @@ private: bool is_op = false; union { Variant::Operator op; - ENode *node; + ENode *node = nullptr; }; }; diff --git a/core/math/face3.cpp b/core/math/face3.cpp index 5bc1bc25e6..fb92f6b0df 100644 --- a/core/math/face3.cpp +++ b/core/math/face3.cpp @@ -208,7 +208,7 @@ bool Face3::intersects_aabb(const AABB &p_aabb) const { /** TEST ALL EDGES **/ - Vector3 edge_norms[3] = { + const Vector3 edge_norms[3] = { vertex[0] - vertex[1], vertex[1] - vertex[2], vertex[2] - vertex[0], diff --git a/core/math/face3.h b/core/math/face3.h index c61d6ad66e..23260336fa 100644 --- a/core/math/face3.h +++ b/core/math/face3.h @@ -133,7 +133,7 @@ bool Face3::intersects_aabb2(const AABB &p_aabb) const { #undef TEST_AXIS - Vector3 edge_norms[3] = { + const Vector3 edge_norms[3] = { vertex[0] - vertex[1], vertex[1] - vertex[2], vertex[2] - vertex[0], diff --git a/core/math/geometry_2d.cpp b/core/math/geometry_2d.cpp index 46b7d99b43..31fade5a99 100644 --- a/core/math/geometry_2d.cpp +++ b/core/math/geometry_2d.cpp @@ -74,14 +74,14 @@ Vector<Vector<Vector2>> Geometry2D::decompose_polygon_in_convex(Vector<Point2> p struct _AtlasWorkRect { Size2i s; Point2i p; - int idx; + int idx = 0; _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; + int max_w = 0; + int max_h = 0; }; void Geometry2D::make_atlas(const Vector<Size2i> &p_rects, Vector<Point2i> &r_result, Size2i &r_size) { diff --git a/core/math/geometry_3d.cpp b/core/math/geometry_3d.cpp index bd22bffb1f..ec96753c79 100644 --- a/core/math/geometry_3d.cpp +++ b/core/math/geometry_3d.cpp @@ -36,7 +36,7 @@ #include "thirdparty/misc/polypartition.h" void Geometry3D::MeshData::optimize_vertices() { - Map<int, int> vtx_remap; + HashMap<int, int> vtx_remap; for (int i = 0; i < faces.size(); i++) { for (int j = 0; j < faces[i].indices.size(); j++) { @@ -904,8 +904,8 @@ Vector<Vector3> Geometry3D::compute_convex_mesh_points(const Plane *p_planes, in /* dt of 1d function using squared distance */ static void edt(float *f, int stride, int n) { float *d = (float *)alloca(sizeof(float) * n + sizeof(int) * n + sizeof(float) * (n + 1)); - int *v = (int *)&(d[n]); - float *z = (float *)&v[n]; + int *v = reinterpret_cast<int *>(&(d[n])); + float *z = reinterpret_cast<float *>(&v[n]); int k = 0; v[0] = 0; diff --git a/core/math/math_fieldwise.cpp b/core/math/math_fieldwise.cpp index 1717ecd74b..4be4809e3f 100644 --- a/core/math/math_fieldwise.cpp +++ b/core/math/math_fieldwise.cpp @@ -115,12 +115,12 @@ Variant fieldwise_assign(const Variant &p_target, const Variant &p_source, const case Variant::TRANSFORM2D: { SETUP_TYPE(Transform2D) - /**/ TRY_TRANSFER_FIELD("xx", elements[0][0]) - else TRY_TRANSFER_FIELD("xy", elements[0][1]) - else TRY_TRANSFER_FIELD("yx", elements[1][0]) - else TRY_TRANSFER_FIELD("yy", elements[1][1]) - else TRY_TRANSFER_FIELD("ox", elements[2][0]) - else TRY_TRANSFER_FIELD("oy", elements[2][1]) + /**/ TRY_TRANSFER_FIELD("xx", columns[0][0]) + else TRY_TRANSFER_FIELD("xy", columns[0][1]) + else TRY_TRANSFER_FIELD("yx", columns[1][0]) + else TRY_TRANSFER_FIELD("yy", columns[1][1]) + else TRY_TRANSFER_FIELD("ox", columns[2][0]) + else TRY_TRANSFER_FIELD("oy", columns[2][1]) return target; } @@ -128,15 +128,15 @@ Variant fieldwise_assign(const Variant &p_target, const Variant &p_source, const case Variant::BASIS: { SETUP_TYPE(Basis) - /**/ TRY_TRANSFER_FIELD("xx", elements[0][0]) - else TRY_TRANSFER_FIELD("xy", elements[0][1]) - else TRY_TRANSFER_FIELD("xz", elements[0][2]) - else TRY_TRANSFER_FIELD("yx", elements[1][0]) - else TRY_TRANSFER_FIELD("yy", elements[1][1]) - else TRY_TRANSFER_FIELD("yz", elements[1][2]) - else TRY_TRANSFER_FIELD("zx", elements[2][0]) - else TRY_TRANSFER_FIELD("zy", elements[2][1]) - else TRY_TRANSFER_FIELD("zz", elements[2][2]) + /**/ TRY_TRANSFER_FIELD("xx", rows[0][0]) + else TRY_TRANSFER_FIELD("xy", rows[0][1]) + else TRY_TRANSFER_FIELD("xz", rows[0][2]) + else TRY_TRANSFER_FIELD("yx", rows[1][0]) + else TRY_TRANSFER_FIELD("yy", rows[1][1]) + else TRY_TRANSFER_FIELD("yz", rows[1][2]) + else TRY_TRANSFER_FIELD("zx", rows[2][0]) + else TRY_TRANSFER_FIELD("zy", rows[2][1]) + else TRY_TRANSFER_FIELD("zz", rows[2][2]) return target; } @@ -144,15 +144,15 @@ Variant fieldwise_assign(const Variant &p_target, const Variant &p_source, const case Variant::TRANSFORM3D: { SETUP_TYPE(Transform3D) - /**/ TRY_TRANSFER_FIELD("xx", basis.elements[0][0]) - else TRY_TRANSFER_FIELD("xy", basis.elements[0][1]) - else TRY_TRANSFER_FIELD("xz", basis.elements[0][2]) - else TRY_TRANSFER_FIELD("yx", basis.elements[1][0]) - else TRY_TRANSFER_FIELD("yy", basis.elements[1][1]) - else TRY_TRANSFER_FIELD("yz", basis.elements[1][2]) - else TRY_TRANSFER_FIELD("zx", basis.elements[2][0]) - else TRY_TRANSFER_FIELD("zy", basis.elements[2][1]) - else TRY_TRANSFER_FIELD("zz", basis.elements[2][2]) + /**/ TRY_TRANSFER_FIELD("xx", basis.rows[0][0]) + else TRY_TRANSFER_FIELD("xy", basis.rows[0][1]) + else TRY_TRANSFER_FIELD("xz", basis.rows[0][2]) + else TRY_TRANSFER_FIELD("yx", basis.rows[1][0]) + else TRY_TRANSFER_FIELD("yy", basis.rows[1][1]) + else TRY_TRANSFER_FIELD("yz", basis.rows[1][2]) + else TRY_TRANSFER_FIELD("zx", basis.rows[2][0]) + else TRY_TRANSFER_FIELD("zy", basis.rows[2][1]) + else TRY_TRANSFER_FIELD("zz", basis.rows[2][2]) else TRY_TRANSFER_FIELD("xo", origin.x) else TRY_TRANSFER_FIELD("yo", origin.y) else TRY_TRANSFER_FIELD("zo", origin.z) diff --git a/core/math/math_funcs.h b/core/math/math_funcs.h index 8c0b87cf4a..c8a55341aa 100644 --- a/core/math/math_funcs.h +++ b/core/math/math_funcs.h @@ -103,6 +103,9 @@ public: static _ALWAYS_INLINE_ double log(double p_x) { return ::log(p_x); } static _ALWAYS_INLINE_ float log(float p_x) { return ::logf(p_x); } + static _ALWAYS_INLINE_ double log1p(double p_x) { return ::log1p(p_x); } + static _ALWAYS_INLINE_ float log1p(float p_x) { return ::log1pf(p_x); } + static _ALWAYS_INLINE_ double log2(double p_x) { return ::log2(p_x); } static _ALWAYS_INLINE_ float log2(float p_x) { return ::log2f(p_x); } @@ -299,11 +302,19 @@ public: } static _ALWAYS_INLINE_ double wrapf(double value, double min, double max) { double range = max - min; - return is_zero_approx(range) ? min : value - (range * Math::floor((value - min) / range)); + double result = is_zero_approx(range) ? min : value - (range * Math::floor((value - min) / range)); + if (is_equal_approx(result, max)) { + return min; + } + return result; } static _ALWAYS_INLINE_ float wrapf(float value, float min, float max) { float range = max - min; - return is_zero_approx(range) ? min : value - (range * Math::floor((value - min) / range)); + float result = is_zero_approx(range) ? min : value - (range * Math::floor((value - min) / range)); + if (is_equal_approx(result, max)) { + return min; + } + return result; } static _ALWAYS_INLINE_ float fract(float value) { @@ -322,7 +333,7 @@ public: // double only, as these functions are mainly used by the editor and not performance-critical, static double ease(double p_x, double p_c); static int step_decimals(double p_step); - static int range_step_decimals(double p_step); + static int range_step_decimals(double p_step); // For editor use only. static double snapped(double p_value, double p_step); static uint32_t larger_prime(uint32_t p_val); @@ -473,16 +484,16 @@ public: uint32_t x = ci.ui; uint32_t sign = (unsigned short)(x >> 31); uint32_t mantissa; - uint32_t exp; + uint32_t exponent; uint16_t hf; // get mantissa mantissa = x & ((1 << 23) - 1); // get exponent bits - exp = x & (0xFF << 23); - if (exp >= 0x47800000) { + exponent = x & (0xFF << 23); + if (exponent >= 0x47800000) { // check if the original single precision float number is a NaN - if (mantissa && (exp == (0xFF << 23))) { + if (mantissa && (exponent == (0xFF << 23))) { // we have a single precision NaN mantissa = (1 << 23) - 1; } else { @@ -493,17 +504,18 @@ public: (uint16_t)(mantissa >> 13); } // check if exponent is <= -15 - else if (exp <= 0x38000000) { - /*// store a denorm half-float value or zero - exp = (0x38000000 - exp) >> 23; - mantissa >>= (14 + exp); - - hf = (((uint16_t)sign) << 15) | (uint16_t)(mantissa); - */ + else if (exponent <= 0x38000000) { + /* + // store a denorm half-float value or zero + exponent = (0x38000000 - exponent) >> 23; + mantissa >>= (14 + exponent); + + hf = (((uint16_t)sign) << 15) | (uint16_t)(mantissa); + */ hf = 0; //denormals do not work for 3D, convert to zero } else { hf = (((uint16_t)sign) << 15) | - (uint16_t)((exp - 0x38000000) >> 13) | + (uint16_t)((exponent - 0x38000000) >> 13) | (uint16_t)(mantissa >> 13); } diff --git a/core/math/octree.h b/core/math/octree.h index e73f8213b3..8dd103f109 100644 --- a/core/math/octree.h +++ b/core/math/octree.h @@ -36,7 +36,7 @@ #include "core/math/vector3.h" #include "core/string/print_string.h" #include "core/templates/list.h" -#include "core/templates/map.h" +#include "core/templates/rb_map.h" #include "core/variant/variant.h" typedef uint32_t OctreeElementID; @@ -134,7 +134,7 @@ private: List<PairData *, AL> pair_list; struct OctantOwner { - Octant *octant; + Octant *octant = nullptr; typename List<Element *, AL>::Element *E; }; // an element can be in max 8 octants @@ -147,27 +147,27 @@ private: int refcount; bool intersect; Element *A, *B; - void *ud; + void *ud = nullptr; typename List<PairData *, AL>::Element *eA, *eB; }; - typedef Map<OctreeElementID, Element, Comparator<OctreeElementID>, AL> ElementMap; - typedef Map<PairKey, PairData, Comparator<PairKey>, AL> PairMap; + typedef HashMap<OctreeElementID, Element, Comparator<OctreeElementID>, AL> ElementMap; + typedef HashMap<PairKey, PairData, Comparator<PairKey>, AL> PairMap; ElementMap element_map; PairMap pair_map; - PairCallback pair_callback; - UnpairCallback unpair_callback; - void *pair_callback_userdata; - void *unpair_callback_userdata; + PairCallback pair_callback = nullptr; + UnpairCallback unpair_callback = nullptr; + void *pair_callback_userdata = nullptr; + void *unpair_callback_userdata = nullptr; - OctreeElementID last_element_id; - uint64_t pass; + OctreeElementID last_element_id = 1; + uint64_t pass = 1; - real_t unit_size; - Octant *root; - int octant_count; - int pair_count; + real_t unit_size = 1.0; + Octant *root = nullptr; + int octant_count = 0; + int pair_count = 0; _FORCE_INLINE_ void _pair_check(PairData *p_pair) { bool intersect = p_pair->A->aabb.intersects_inclusive(p_pair->B->aabb); @@ -294,7 +294,7 @@ private: const Vector3 *points; int point_count; T **result_array; - int *result_idx; + int *result_idx = nullptr; int result_max; uint32_t mask; }; @@ -1265,18 +1265,7 @@ void Octree<T, use_pairs, AL>::set_unpair_callback(UnpairCallback p_callback, vo template <class T, bool use_pairs, class AL> Octree<T, use_pairs, AL>::Octree(real_t p_unit_size) { - last_element_id = 1; - pass = 1; unit_size = p_unit_size; - root = nullptr; - - octant_count = 0; - pair_count = 0; - - pair_callback = nullptr; - unpair_callback = nullptr; - pair_callback_userdata = nullptr; - unpair_callback_userdata = nullptr; } #endif // OCTREE_H diff --git a/core/math/quaternion.cpp b/core/math/quaternion.cpp index 0a650a8578..11bfcc1a6f 100644 --- a/core/math/quaternion.cpp +++ b/core/math/quaternion.cpp @@ -102,6 +102,22 @@ Quaternion Quaternion::inverse() const { return Quaternion(-x, -y, -z, w); } +Quaternion Quaternion::log() const { + Quaternion src = *this; + Vector3 src_v = src.get_axis() * src.get_angle(); + return Quaternion(src_v.x, src_v.y, src_v.z, 0); +} + +Quaternion Quaternion::exp() const { + Quaternion src = *this; + Vector3 src_v = Vector3(src.x, src.y, src.z); + float theta = src_v.length(); + if (theta < CMP_EPSILON) { + return Quaternion(0, 0, 0, 1); + } + return Quaternion(src_v.normalized(), theta); +} + Quaternion Quaternion::slerp(const Quaternion &p_to, const real_t &p_weight) const { #ifdef MATH_CHECKS ERR_FAIL_COND_V_MSG(!is_normalized(), Quaternion(), "The start quaternion must be normalized."); @@ -190,6 +206,9 @@ Quaternion::operator String() const { } Vector3 Quaternion::get_axis() const { + if (Math::abs(w) > 1 - CMP_EPSILON) { + return Vector3(x, y, z); + } real_t r = ((real_t)1) / Math::sqrt(1 - w * w); return Vector3(x * r, y * r, z * r); } diff --git a/core/math/quaternion.h b/core/math/quaternion.h index 38729ac3df..9801746659 100644 --- a/core/math/quaternion.h +++ b/core/math/quaternion.h @@ -60,6 +60,8 @@ struct _NO_DISCARD_ Quaternion { Quaternion normalized() const; bool is_normalized() const; Quaternion inverse() const; + Quaternion log() const; + Quaternion exp() const; _FORCE_INLINE_ real_t dot(const Quaternion &p_q) const; real_t angle_to(const Quaternion &p_to) const; diff --git a/core/math/quick_hull.cpp b/core/math/quick_hull.cpp index 8e87d44b7f..c7727a44a1 100644 --- a/core/math/quick_hull.cpp +++ b/core/math/quick_hull.cpp @@ -30,7 +30,7 @@ #include "quick_hull.h" -#include "core/templates/map.h" +#include "core/templates/rb_map.h" uint32_t QuickHull::debug_stop_after = 0xFFFFFFFF; @@ -52,7 +52,7 @@ Error QuickHull::build(const Vector<Vector3> &p_points, Geometry3D::MeshData &r_ Vector<bool> valid_points; valid_points.resize(p_points.size()); - Set<Vector3> valid_cache; + HashSet<Vector3> valid_cache; for (int i = 0; i < p_points.size(); i++) { Vector3 sp = p_points[i].snapped(Vector3(0.0001, 0.0001, 0.0001)); @@ -237,7 +237,7 @@ Error QuickHull::build(const Vector<Vector3> &p_points, Geometry3D::MeshData &r_ //find lit faces and lit edges List<List<Face>::Element *> lit_faces; //lit face is a death sentence - Map<Edge, FaceConnect> lit_edges; //create this on the flight, should not be that bad for performance and simplifies code a lot + HashMap<Edge, FaceConnect, Edge> lit_edges; //create this on the flight, should not be that bad for performance and simplifies code a lot for (List<Face>::Element *E = faces.front(); E; E = E->next()) { if (E->get().plane.distance_to(v) > 0) { @@ -248,15 +248,15 @@ Error QuickHull::build(const Vector<Vector3> &p_points, Geometry3D::MeshData &r_ uint32_t b = E->get().vertices[(i + 1) % 3]; Edge e(a, b); - Map<Edge, FaceConnect>::Element *F = lit_edges.find(e); + HashMap<Edge, FaceConnect, Edge>::Iterator F = lit_edges.find(e); if (!F) { F = lit_edges.insert(e, FaceConnect()); } if (e.vertices[0] == a) { //left - F->get().left = E; + F->value.left = E; } else { - F->get().right = E; + F->value.right = E; } } } @@ -333,7 +333,7 @@ Error QuickHull::build(const Vector<Vector3> &p_points, Geometry3D::MeshData &r_ /* CREATE MESHDATA */ //make a map of edges again - Map<Edge, RetFaceConnect> ret_edges; + HashMap<Edge, RetFaceConnect, Edge> ret_edges; List<Geometry3D::MeshData::Face> ret_faces; for (const Face &E : faces) { @@ -351,15 +351,15 @@ Error QuickHull::build(const Vector<Vector3> &p_points, Geometry3D::MeshData &r_ uint32_t b = E.vertices[(i + 1) % 3]; Edge e(a, b); - Map<Edge, RetFaceConnect>::Element *G = ret_edges.find(e); + HashMap<Edge, RetFaceConnect, Edge>::Iterator G = ret_edges.find(e); if (!G) { G = ret_edges.insert(e, RetFaceConnect()); } if (e.vertices[0] == a) { //left - G->get().left = F; + G->value.left = F; } else { - G->get().right = F; + G->value.right = F; } } } @@ -374,17 +374,16 @@ Error QuickHull::build(const Vector<Vector3> &p_points, Geometry3D::MeshData &r_ int b = E->get().indices[(i + 1) % f.indices.size()]; Edge e(a, b); - Map<Edge, RetFaceConnect>::Element *F = ret_edges.find(e); + HashMap<Edge, RetFaceConnect, Edge>::Iterator F = ret_edges.find(e); ERR_CONTINUE(!F); - List<Geometry3D::MeshData::Face>::Element *O = F->get().left == E ? F->get().right : F->get().left; + List<Geometry3D::MeshData::Face>::Element *O = F->value.left == E ? F->value.right : F->value.left; ERR_CONTINUE(O == E); ERR_CONTINUE(O == nullptr); if (O->get().plane.is_equal_approx(f.plane)) { //merge and delete edge and contiguous face, while repointing edges (uuugh!) int ois = O->get().indices.size(); - int merged = 0; for (int j = 0; j < ois; j++) { //search a @@ -399,17 +398,16 @@ Error QuickHull::build(const Vector<Vector3> &p_points, Geometry3D::MeshData &r_ if (idx != a) { f.indices.insert(i + 1, idx); i++; - merged++; } Edge e2(idx, idxn); - Map<Edge, RetFaceConnect>::Element *F2 = ret_edges.find(e2); + HashMap<Edge, RetFaceConnect, Edge>::Iterator F2 = ret_edges.find(e2); ERR_CONTINUE(!F2); //change faceconnect, point to this face instead - if (F2->get().left == O) { - F2->get().left = E; - } else if (F2->get().right == O) { - F2->get().right = E; + if (F2->value.left == O) { + F2->value.left = E; + } else if (F2->value.right == O) { + F2->value.right = E; } } @@ -428,7 +426,7 @@ Error QuickHull::build(const Vector<Vector3> &p_points, Geometry3D::MeshData &r_ } } - ret_edges.erase(F); //remove the edge + ret_edges.remove(F); //remove the edge ret_faces.erase(O); //remove the face } } diff --git a/core/math/quick_hull.h b/core/math/quick_hull.h index b8d813c979..6783743fc2 100644 --- a/core/math/quick_hull.h +++ b/core/math/quick_hull.h @@ -33,8 +33,8 @@ #include "core/math/aabb.h" #include "core/math/geometry_3d.h" +#include "core/templates/hash_set.h" #include "core/templates/list.h" -#include "core/templates/set.h" class QuickHull { public: @@ -44,9 +44,16 @@ public: uint64_t id = 0; }; + static uint32_t hash(const Edge &p_edge) { + return hash_one_uint64(p_edge.id); + } + bool operator<(const Edge &p_edge) const { return id < p_edge.id; } + bool operator==(const Edge &p_edge) const { + return id == p_edge.id; + } Edge(int p_vtx_a = 0, int p_vtx_b = 0) { if (p_vtx_a > p_vtx_b) { diff --git a/core/math/random_pcg.h b/core/math/random_pcg.h index 65fcf67664..a088b30d17 100644 --- a/core/math/random_pcg.h +++ b/core/math/random_pcg.h @@ -61,8 +61,8 @@ static int __bsr_clz32(uint32_t x) { class RandomPCG { pcg32_random_t pcg; - uint64_t current_seed; // The seed the current generator state started from. - uint64_t current_inc; + uint64_t current_seed = 0; // The seed the current generator state started from. + uint64_t current_inc = 0; public: static const uint64_t DEFAULT_SEED = 12047754176567800795U; diff --git a/core/math/rect2.cpp b/core/math/rect2.cpp index d6e20bdc3c..9e78ead816 100644 --- a/core/math/rect2.cpp +++ b/core/math/rect2.cpp @@ -201,33 +201,33 @@ next4: Vector2(position.x + size.x, position.y + size.y), }; - real_t maxa = p_xform.elements[0].dot(xf_points2[0]); + real_t maxa = p_xform.columns[0].dot(xf_points2[0]); real_t mina = maxa; - real_t dp = p_xform.elements[0].dot(xf_points2[1]); + real_t dp = p_xform.columns[0].dot(xf_points2[1]); maxa = MAX(dp, maxa); mina = MIN(dp, mina); - dp = p_xform.elements[0].dot(xf_points2[2]); + dp = p_xform.columns[0].dot(xf_points2[2]); maxa = MAX(dp, maxa); mina = MIN(dp, mina); - dp = p_xform.elements[0].dot(xf_points2[3]); + dp = p_xform.columns[0].dot(xf_points2[3]); maxa = MAX(dp, maxa); mina = MIN(dp, mina); - real_t maxb = p_xform.elements[0].dot(xf_points[0]); + real_t maxb = p_xform.columns[0].dot(xf_points[0]); real_t minb = maxb; - dp = p_xform.elements[0].dot(xf_points[1]); + dp = p_xform.columns[0].dot(xf_points[1]); maxb = MAX(dp, maxb); minb = MIN(dp, minb); - dp = p_xform.elements[0].dot(xf_points[2]); + dp = p_xform.columns[0].dot(xf_points[2]); maxb = MAX(dp, maxb); minb = MIN(dp, minb); - dp = p_xform.elements[0].dot(xf_points[3]); + dp = p_xform.columns[0].dot(xf_points[3]); maxb = MAX(dp, maxb); minb = MIN(dp, minb); @@ -238,33 +238,33 @@ next4: return false; } - maxa = p_xform.elements[1].dot(xf_points2[0]); + maxa = p_xform.columns[1].dot(xf_points2[0]); mina = maxa; - dp = p_xform.elements[1].dot(xf_points2[1]); + dp = p_xform.columns[1].dot(xf_points2[1]); maxa = MAX(dp, maxa); mina = MIN(dp, mina); - dp = p_xform.elements[1].dot(xf_points2[2]); + dp = p_xform.columns[1].dot(xf_points2[2]); maxa = MAX(dp, maxa); mina = MIN(dp, mina); - dp = p_xform.elements[1].dot(xf_points2[3]); + dp = p_xform.columns[1].dot(xf_points2[3]); maxa = MAX(dp, maxa); mina = MIN(dp, mina); - maxb = p_xform.elements[1].dot(xf_points[0]); + maxb = p_xform.columns[1].dot(xf_points[0]); minb = maxb; - dp = p_xform.elements[1].dot(xf_points[1]); + dp = p_xform.columns[1].dot(xf_points[1]); maxb = MAX(dp, maxb); minb = MIN(dp, minb); - dp = p_xform.elements[1].dot(xf_points[2]); + dp = p_xform.columns[1].dot(xf_points[2]); maxb = MAX(dp, maxb); minb = MIN(dp, minb); - dp = p_xform.elements[1].dot(xf_points[3]); + dp = p_xform.columns[1].dot(xf_points[3]); maxb = MAX(dp, maxb); minb = MIN(dp, minb); diff --git a/core/math/static_raycaster.h b/core/math/static_raycaster.h index 33254399c7..bc6511c073 100644 --- a/core/math/static_raycaster.h +++ b/core/math/static_raycaster.h @@ -102,7 +102,7 @@ public: virtual void add_mesh(const PackedVector3Array &p_vertices, const PackedInt32Array &p_indices, unsigned int p_id) = 0; virtual void commit() = 0; - virtual void set_mesh_filter(const Set<int> &p_mesh_ids) = 0; + virtual void set_mesh_filter(const HashSet<int> &p_mesh_ids) = 0; virtual void clear_mesh_filter() = 0; static Ref<StaticRaycaster> create(); diff --git a/core/math/transform_2d.cpp b/core/math/transform_2d.cpp index 71953e4130..cbd2fd3fa1 100644 --- a/core/math/transform_2d.cpp +++ b/core/math/transform_2d.cpp @@ -35,8 +35,8 @@ void Transform2D::invert() { // FIXME: this function assumes the basis is a rotation matrix, with no scaling. // Transform2D::affine_inverse can handle matrices with scaling, so GDScript should eventually use that. - SWAP(elements[0][1], elements[1][0]); - elements[2] = basis_xform(-elements[2]); + SWAP(columns[0][1], columns[1][0]); + columns[2] = basis_xform(-columns[2]); } Transform2D Transform2D::inverse() const { @@ -52,11 +52,11 @@ void Transform2D::affine_invert() { #endif real_t idet = 1.0f / det; - SWAP(elements[0][0], elements[1][1]); - elements[0] *= Vector2(idet, -idet); - elements[1] *= Vector2(-idet, idet); + SWAP(columns[0][0], columns[1][1]); + columns[0] *= Vector2(idet, -idet); + columns[1] *= Vector2(-idet, idet); - elements[2] = basis_xform(-elements[2]); + columns[2] = basis_xform(-columns[2]); } Transform2D Transform2D::affine_inverse() const { @@ -65,75 +65,75 @@ Transform2D Transform2D::affine_inverse() const { return inv; } -void Transform2D::rotate(const real_t p_phi) { - *this = Transform2D(p_phi, Vector2()) * (*this); +void Transform2D::rotate(const real_t p_angle) { + *this = Transform2D(p_angle, Vector2()) * (*this); } real_t Transform2D::get_skew() const { real_t det = basis_determinant(); - return Math::acos(elements[0].normalized().dot(SIGN(det) * elements[1].normalized())) - (real_t)Math_PI * 0.5f; + return Math::acos(columns[0].normalized().dot(SIGN(det) * columns[1].normalized())) - (real_t)Math_PI * 0.5f; } void Transform2D::set_skew(const real_t p_angle) { real_t det = basis_determinant(); - elements[1] = SIGN(det) * elements[0].rotated(((real_t)Math_PI * 0.5f + p_angle)).normalized() * elements[1].length(); + columns[1] = SIGN(det) * columns[0].rotated(((real_t)Math_PI * 0.5f + p_angle)).normalized() * columns[1].length(); } real_t Transform2D::get_rotation() const { - return Math::atan2(elements[0].y, elements[0].x); + return Math::atan2(columns[0].y, columns[0].x); } void Transform2D::set_rotation(const real_t p_rot) { Size2 scale = get_scale(); real_t cr = Math::cos(p_rot); real_t sr = Math::sin(p_rot); - elements[0][0] = cr; - elements[0][1] = sr; - elements[1][0] = -sr; - elements[1][1] = cr; + columns[0][0] = cr; + columns[0][1] = sr; + columns[1][0] = -sr; + columns[1][1] = cr; set_scale(scale); } Transform2D::Transform2D(const real_t p_rot, const Vector2 &p_pos) { real_t cr = Math::cos(p_rot); real_t sr = Math::sin(p_rot); - elements[0][0] = cr; - elements[0][1] = sr; - elements[1][0] = -sr; - elements[1][1] = cr; - elements[2] = p_pos; + columns[0][0] = cr; + columns[0][1] = sr; + columns[1][0] = -sr; + columns[1][1] = cr; + columns[2] = p_pos; } Transform2D::Transform2D(const real_t p_rot, const Size2 &p_scale, const real_t p_skew, const Vector2 &p_pos) { - elements[0][0] = Math::cos(p_rot) * p_scale.x; - elements[1][1] = Math::cos(p_rot + p_skew) * p_scale.y; - elements[1][0] = -Math::sin(p_rot + p_skew) * p_scale.y; - elements[0][1] = Math::sin(p_rot) * p_scale.x; - elements[2] = p_pos; + columns[0][0] = Math::cos(p_rot) * p_scale.x; + columns[1][1] = Math::cos(p_rot + p_skew) * p_scale.y; + columns[1][0] = -Math::sin(p_rot + p_skew) * p_scale.y; + columns[0][1] = Math::sin(p_rot) * p_scale.x; + columns[2] = p_pos; } Size2 Transform2D::get_scale() const { real_t det_sign = SIGN(basis_determinant()); - return Size2(elements[0].length(), det_sign * elements[1].length()); + return Size2(columns[0].length(), det_sign * columns[1].length()); } void Transform2D::set_scale(const Size2 &p_scale) { - elements[0].normalize(); - elements[1].normalize(); - elements[0] *= p_scale.x; - elements[1] *= p_scale.y; + columns[0].normalize(); + columns[1].normalize(); + columns[0] *= p_scale.x; + columns[1] *= p_scale.y; } void Transform2D::scale(const Size2 &p_scale) { scale_basis(p_scale); - elements[2] *= p_scale; + columns[2] *= p_scale; } void Transform2D::scale_basis(const Size2 &p_scale) { - elements[0][0] *= p_scale.x; - elements[0][1] *= p_scale.y; - elements[1][0] *= p_scale.x; - elements[1][1] *= p_scale.y; + columns[0][0] *= p_scale.x; + columns[0][1] *= p_scale.y; + columns[1][0] *= p_scale.x; + columns[1][1] *= p_scale.y; } void Transform2D::translate(const real_t p_tx, const real_t p_ty) { @@ -141,21 +141,21 @@ void Transform2D::translate(const real_t p_tx, const real_t p_ty) { } void Transform2D::translate(const Vector2 &p_translation) { - elements[2] += basis_xform(p_translation); + columns[2] += basis_xform(p_translation); } void Transform2D::orthonormalize() { // Gram-Schmidt Process - Vector2 x = elements[0]; - Vector2 y = elements[1]; + Vector2 x = columns[0]; + Vector2 y = columns[1]; x.normalize(); y = (y - x * (x.dot(y))); y.normalize(); - elements[0] = x; - elements[1] = y; + columns[0] = x; + columns[1] = y; } Transform2D Transform2D::orthonormalized() const { @@ -165,7 +165,7 @@ Transform2D Transform2D::orthonormalized() const { } bool Transform2D::is_equal_approx(const Transform2D &p_transform) const { - return elements[0].is_equal_approx(p_transform.elements[0]) && elements[1].is_equal_approx(p_transform.elements[1]) && elements[2].is_equal_approx(p_transform.elements[2]); + return columns[0].is_equal_approx(p_transform.columns[0]) && columns[1].is_equal_approx(p_transform.columns[1]) && columns[2].is_equal_approx(p_transform.columns[2]); } Transform2D Transform2D::looking_at(const Vector2 &p_target) const { @@ -177,7 +177,7 @@ Transform2D Transform2D::looking_at(const Vector2 &p_target) const { bool Transform2D::operator==(const Transform2D &p_transform) const { for (int i = 0; i < 3; i++) { - if (elements[i] != p_transform.elements[i]) { + if (columns[i] != p_transform.columns[i]) { return false; } } @@ -187,7 +187,7 @@ bool Transform2D::operator==(const Transform2D &p_transform) const { bool Transform2D::operator!=(const Transform2D &p_transform) const { for (int i = 0; i < 3; i++) { - if (elements[i] != p_transform.elements[i]) { + if (columns[i] != p_transform.columns[i]) { return true; } } @@ -196,19 +196,19 @@ bool Transform2D::operator!=(const Transform2D &p_transform) const { } void Transform2D::operator*=(const Transform2D &p_transform) { - elements[2] = xform(p_transform.elements[2]); + columns[2] = xform(p_transform.columns[2]); real_t x0, x1, y0, y1; - x0 = tdotx(p_transform.elements[0]); - x1 = tdoty(p_transform.elements[0]); - y0 = tdotx(p_transform.elements[1]); - y1 = tdoty(p_transform.elements[1]); + x0 = tdotx(p_transform.columns[0]); + x1 = tdoty(p_transform.columns[0]); + y0 = tdotx(p_transform.columns[1]); + y1 = tdoty(p_transform.columns[1]); - elements[0][0] = x0; - elements[0][1] = x1; - elements[1][0] = y0; - elements[1][1] = y1; + columns[0][0] = x0; + columns[0][1] = x1; + columns[1][0] = y0; + columns[1][1] = y1; } Transform2D Transform2D::operator*(const Transform2D &p_transform) const { @@ -231,7 +231,7 @@ Transform2D Transform2D::basis_scaled(const Size2 &p_scale) const { Transform2D Transform2D::untranslated() const { Transform2D copy = *this; - copy.elements[2] = Vector2(); + copy.columns[2] = Vector2(); return copy; } @@ -241,14 +241,14 @@ Transform2D Transform2D::translated(const Vector2 &p_offset) const { return copy; } -Transform2D Transform2D::rotated(const real_t p_phi) const { +Transform2D Transform2D::rotated(const real_t p_angle) const { Transform2D copy = *this; - copy.rotate(p_phi); + copy.rotate(p_angle); return copy; } real_t Transform2D::basis_determinant() const { - return elements[0].x * elements[1].y - elements[0].y * elements[1].x; + return columns[0].x * columns[1].y - columns[0].y * columns[1].x; } Transform2D Transform2D::interpolate_with(const Transform2D &p_transform, const real_t p_c) const { @@ -287,9 +287,9 @@ Transform2D Transform2D::interpolate_with(const Transform2D &p_transform, const } void Transform2D::operator*=(const real_t p_val) { - elements[0] *= p_val; - elements[1] *= p_val; - elements[2] *= p_val; + columns[0] *= p_val; + columns[1] *= p_val; + columns[2] *= p_val; } Transform2D Transform2D::operator*(const real_t p_val) const { @@ -299,7 +299,7 @@ Transform2D Transform2D::operator*(const real_t p_val) const { } Transform2D::operator String() const { - return "[X: " + elements[0].operator String() + - ", Y: " + elements[1].operator String() + - ", O: " + elements[2].operator String() + "]"; + return "[X: " + columns[0].operator String() + + ", Y: " + columns[1].operator String() + + ", O: " + columns[2].operator String() + "]"; } diff --git a/core/math/transform_2d.h b/core/math/transform_2d.h index f4546c13c8..72d34a5d4c 100644 --- a/core/math/transform_2d.h +++ b/core/math/transform_2d.h @@ -39,33 +39,24 @@ class String; struct _NO_DISCARD_ Transform2D { - // Warning #1: basis of Transform2D is stored differently from Basis. In terms of elements array, the basis matrix looks like "on paper": - // M = (elements[0][0] elements[1][0]) - // (elements[0][1] elements[1][1]) - // This is such that the columns, which can be interpreted as basis vectors of the coordinate system "painted" on the object, can be accessed as elements[i]. - // Note that this is the opposite of the indices in mathematical texts, meaning: $M_{12}$ in a math book corresponds to elements[1][0] here. + // Warning #1: basis of Transform2D is stored differently from Basis. In terms of columns array, the basis matrix looks like "on paper": + // M = (columns[0][0] columns[1][0]) + // (columns[0][1] columns[1][1]) + // This is such that the columns, which can be interpreted as basis vectors of the coordinate system "painted" on the object, can be accessed as columns[i]. + // Note that this is the opposite of the indices in mathematical texts, meaning: $M_{12}$ in a math book corresponds to columns[1][0] here. // This requires additional care when working with explicit indices. // See https://en.wikipedia.org/wiki/Row-_and_column-major_order for further reading. // Warning #2: 2D be aware that unlike 3D code, 2D code uses a left-handed coordinate system: Y-axis points down, // and angle is measure from +X to +Y in a clockwise-fashion. - Vector2 elements[3]; + Vector2 columns[3]; - _FORCE_INLINE_ real_t tdotx(const Vector2 &v) const { return elements[0][0] * v.x + elements[1][0] * v.y; } - _FORCE_INLINE_ real_t tdoty(const Vector2 &v) const { return elements[0][1] * v.x + elements[1][1] * v.y; } + _FORCE_INLINE_ real_t tdotx(const Vector2 &v) const { return columns[0][0] * v.x + columns[1][0] * v.y; } + _FORCE_INLINE_ real_t tdoty(const Vector2 &v) const { return columns[0][1] * v.x + columns[1][1] * v.y; } - const Vector2 &operator[](int p_idx) const { return elements[p_idx]; } - Vector2 &operator[](int p_idx) { return elements[p_idx]; } - - _FORCE_INLINE_ Vector2 get_axis(int p_axis) const { - ERR_FAIL_INDEX_V(p_axis, 3, Vector2()); - return elements[p_axis]; - } - _FORCE_INLINE_ void set_axis(int p_axis, const Vector2 &p_vec) { - ERR_FAIL_INDEX(p_axis, 3); - elements[p_axis] = p_vec; - } + const Vector2 &operator[](int p_idx) const { return columns[p_idx]; } + Vector2 &operator[](int p_idx) { return columns[p_idx]; } void invert(); Transform2D inverse() const; @@ -79,7 +70,7 @@ struct _NO_DISCARD_ Transform2D { void set_skew(const real_t p_angle); _FORCE_INLINE_ void set_rotation_and_scale(const real_t p_rot, const Size2 &p_scale); _FORCE_INLINE_ void set_rotation_scale_and_skew(const real_t p_rot, const Size2 &p_scale, const real_t p_skew); - void rotate(const real_t p_phi); + void rotate(const real_t p_angle); void scale(const Size2 &p_scale); void scale_basis(const Size2 &p_scale); @@ -91,13 +82,13 @@ struct _NO_DISCARD_ Transform2D { Size2 get_scale() const; void set_scale(const Size2 &p_scale); - _FORCE_INLINE_ const Vector2 &get_origin() const { return elements[2]; } - _FORCE_INLINE_ void set_origin(const Vector2 &p_origin) { elements[2] = p_origin; } + _FORCE_INLINE_ const Vector2 &get_origin() const { return columns[2]; } + _FORCE_INLINE_ void set_origin(const Vector2 &p_origin) { columns[2] = p_origin; } Transform2D scaled(const Size2 &p_scale) const; Transform2D basis_scaled(const Size2 &p_scale) const; Transform2D translated(const Vector2 &p_offset) const; - Transform2D rotated(const real_t p_phi) const; + Transform2D rotated(const real_t p_angle) const; Transform2D untranslated() const; @@ -129,18 +120,18 @@ struct _NO_DISCARD_ Transform2D { operator String() const; Transform2D(const real_t xx, const real_t xy, const real_t yx, const real_t yy, const real_t ox, const real_t oy) { - elements[0][0] = xx; - elements[0][1] = xy; - elements[1][0] = yx; - elements[1][1] = yy; - elements[2][0] = ox; - elements[2][1] = oy; + columns[0][0] = xx; + columns[0][1] = xy; + columns[1][0] = yx; + columns[1][1] = yy; + columns[2][0] = ox; + columns[2][1] = oy; } Transform2D(const Vector2 &p_x, const Vector2 &p_y, const Vector2 &p_origin) { - elements[0] = p_x; - elements[1] = p_y; - elements[2] = p_origin; + columns[0] = p_x; + columns[1] = p_y; + columns[2] = p_origin; } Transform2D(const real_t p_rot, const Vector2 &p_pos); @@ -148,8 +139,8 @@ struct _NO_DISCARD_ Transform2D { Transform2D(const real_t p_rot, const Size2 &p_scale, const real_t p_skew, const Vector2 &p_pos); Transform2D() { - elements[0][0] = 1.0; - elements[1][1] = 1.0; + columns[0][0] = 1.0; + columns[1][1] = 1.0; } }; @@ -161,28 +152,28 @@ Vector2 Transform2D::basis_xform(const Vector2 &p_vec) const { Vector2 Transform2D::basis_xform_inv(const Vector2 &p_vec) const { return Vector2( - elements[0].dot(p_vec), - elements[1].dot(p_vec)); + columns[0].dot(p_vec), + columns[1].dot(p_vec)); } Vector2 Transform2D::xform(const Vector2 &p_vec) const { return Vector2( tdotx(p_vec), tdoty(p_vec)) + - elements[2]; + columns[2]; } Vector2 Transform2D::xform_inv(const Vector2 &p_vec) const { - Vector2 v = p_vec - elements[2]; + Vector2 v = p_vec - columns[2]; return Vector2( - elements[0].dot(v), - elements[1].dot(v)); + columns[0].dot(v), + columns[1].dot(v)); } Rect2 Transform2D::xform(const Rect2 &p_rect) const { - Vector2 x = elements[0] * p_rect.size.x; - Vector2 y = elements[1] * p_rect.size.y; + Vector2 x = columns[0] * p_rect.size.x; + Vector2 y = columns[1] * p_rect.size.y; Vector2 pos = xform(p_rect.position); Rect2 new_rect; @@ -194,17 +185,17 @@ Rect2 Transform2D::xform(const Rect2 &p_rect) const { } void Transform2D::set_rotation_and_scale(const real_t p_rot, const Size2 &p_scale) { - elements[0][0] = Math::cos(p_rot) * p_scale.x; - elements[1][1] = Math::cos(p_rot) * p_scale.y; - elements[1][0] = -Math::sin(p_rot) * p_scale.y; - elements[0][1] = Math::sin(p_rot) * p_scale.x; + columns[0][0] = Math::cos(p_rot) * p_scale.x; + columns[1][1] = Math::cos(p_rot) * p_scale.y; + columns[1][0] = -Math::sin(p_rot) * p_scale.y; + columns[0][1] = Math::sin(p_rot) * p_scale.x; } void Transform2D::set_rotation_scale_and_skew(const real_t p_rot, const Size2 &p_scale, const real_t p_skew) { - elements[0][0] = Math::cos(p_rot) * p_scale.x; - elements[1][1] = Math::cos(p_rot + p_skew) * p_scale.y; - elements[1][0] = -Math::sin(p_rot + p_skew) * p_scale.y; - elements[0][1] = Math::sin(p_rot) * p_scale.x; + columns[0][0] = Math::cos(p_rot) * p_scale.x; + columns[1][1] = Math::cos(p_rot + p_skew) * p_scale.y; + columns[1][0] = -Math::sin(p_rot + p_skew) * p_scale.y; + columns[0][1] = Math::sin(p_rot) * p_scale.x; } Rect2 Transform2D::xform_inv(const Rect2 &p_rect) const { diff --git a/core/math/transform_3d.cpp b/core/math/transform_3d.cpp index e5374315e2..76b31daa76 100644 --- a/core/math/transform_3d.cpp +++ b/core/math/transform_3d.cpp @@ -57,16 +57,16 @@ Transform3D Transform3D::inverse() const { return ret; } -void Transform3D::rotate(const Vector3 &p_axis, real_t p_phi) { - *this = rotated(p_axis, p_phi); +void Transform3D::rotate(const Vector3 &p_axis, real_t p_angle) { + *this = rotated(p_axis, p_angle); } -Transform3D Transform3D::rotated(const Vector3 &p_axis, real_t p_phi) const { - return Transform3D(Basis(p_axis, p_phi), Vector3()) * (*this); +Transform3D Transform3D::rotated(const Vector3 &p_axis, real_t p_angle) const { + return Transform3D(Basis(p_axis, p_angle), Vector3()) * (*this); } -void Transform3D::rotate_basis(const Vector3 &p_axis, real_t p_phi) { - basis.rotate(p_axis, p_phi); +void Transform3D::rotate_basis(const Vector3 &p_axis, real_t p_angle) { + basis.rotate(p_axis, p_angle); } Transform3D Transform3D::looking_at(const Vector3 &p_target, const Vector3 &p_up) const { @@ -194,9 +194,9 @@ Transform3D Transform3D::operator*(const real_t p_val) const { } Transform3D::operator String() const { - return "[X: " + basis.get_axis(0).operator String() + - ", Y: " + basis.get_axis(1).operator String() + - ", Z: " + basis.get_axis(2).operator String() + + return "[X: " + basis.get_column(0).operator String() + + ", Y: " + basis.get_column(1).operator String() + + ", Z: " + basis.get_column(2).operator String() + ", O: " + origin.operator String() + "]"; } @@ -207,9 +207,9 @@ Transform3D::Transform3D(const Basis &p_basis, const Vector3 &p_origin) : Transform3D::Transform3D(const Vector3 &p_x, const Vector3 &p_y, const Vector3 &p_z, const Vector3 &p_origin) : origin(p_origin) { - basis.set_axis(0, p_x); - basis.set_axis(1, p_y); - basis.set_axis(2, p_z); + basis.set_column(0, p_x); + basis.set_column(1, p_y); + basis.set_column(2, p_z); } Transform3D::Transform3D(real_t xx, real_t xy, real_t xz, real_t yx, real_t yy, real_t yz, real_t zx, real_t zy, real_t zz, real_t ox, real_t oy, real_t oz) { diff --git a/core/math/transform_3d.h b/core/math/transform_3d.h index 3b4762e221..25832434cd 100644 --- a/core/math/transform_3d.h +++ b/core/math/transform_3d.h @@ -45,10 +45,10 @@ struct _NO_DISCARD_ Transform3D { void affine_invert(); Transform3D affine_inverse() const; - Transform3D rotated(const Vector3 &p_axis, real_t p_phi) const; + Transform3D rotated(const Vector3 &p_axis, real_t p_angle) const; - void rotate(const Vector3 &p_axis, real_t p_phi); - void rotate_basis(const Vector3 &p_axis, real_t p_phi); + void rotate(const Vector3 &p_axis, real_t p_angle); + void rotate_basis(const Vector3 &p_axis, real_t p_angle); void set_look_at(const Vector3 &p_eye, const Vector3 &p_target, const Vector3 &p_up = Vector3(0, 1, 0)); Transform3D looking_at(const Vector3 &p_target, const Vector3 &p_up = Vector3(0, 1, 0)) const; @@ -135,9 +135,9 @@ _FORCE_INLINE_ Vector3 Transform3D::xform_inv(const Vector3 &p_vector) const { Vector3 v = p_vector - origin; return Vector3( - (basis.elements[0][0] * v.x) + (basis.elements[1][0] * v.y) + (basis.elements[2][0] * v.z), - (basis.elements[0][1] * v.x) + (basis.elements[1][1] * v.y) + (basis.elements[2][1] * v.z), - (basis.elements[0][2] * v.x) + (basis.elements[1][2] * v.y) + (basis.elements[2][2] * v.z)); + (basis.rows[0][0] * v.x) + (basis.rows[1][0] * v.y) + (basis.rows[2][0] * v.z), + (basis.rows[0][1] * v.x) + (basis.rows[1][1] * v.y) + (basis.rows[2][1] * v.z), + (basis.rows[0][2] * v.x) + (basis.rows[1][2] * v.y) + (basis.rows[2][2] * v.z)); } // Neither the plane regular xform or xform_inv are particularly efficient, diff --git a/core/math/triangle_mesh.cpp b/core/math/triangle_mesh.cpp index debc5cd00d..54461bf70f 100644 --- a/core/math/triangle_mesh.cpp +++ b/core/math/triangle_mesh.cpp @@ -122,7 +122,7 @@ void TriangleMesh::create(const Vector<Vector3> &p_faces) { const Vector3 *r = p_faces.ptr(); Triangle *w = triangles.ptrw(); - Map<Vector3, int> db; + HashMap<Vector3, int> db; for (int i = 0; i < fc; i++) { Triangle &f = w[i]; @@ -131,9 +131,9 @@ void TriangleMesh::create(const Vector<Vector3> &p_faces) { for (int j = 0; j < 3; j++) { int vidx = -1; Vector3 vs = v[j].snapped(Vector3(0.0001, 0.0001, 0.0001)); - Map<Vector3, int>::Element *E = db.find(vs); + HashMap<Vector3, int>::Iterator E = db.find(vs); if (E) { - vidx = E->get(); + vidx = E->value; } else { vidx = db.size(); db[vs] = vidx; @@ -231,14 +231,14 @@ Vector3 TriangleMesh::get_area_normal(const AABB &p_aabb) const { } case VISIT_LEFT_BIT: { stack[level] = (VISIT_RIGHT_BIT << VISITED_BIT_SHIFT) | node; - stack[level + 1] = b.left | TEST_AABB_BIT; level++; + stack[level] = b.left | TEST_AABB_BIT; continue; } case VISIT_RIGHT_BIT: { stack[level] = (VISIT_DONE_BIT << VISITED_BIT_SHIFT) | node; - stack[level + 1] = b.right | TEST_AABB_BIT; level++; + stack[level] = b.right | TEST_AABB_BIT; continue; } case VISIT_DONE_BIT: { @@ -331,14 +331,14 @@ bool TriangleMesh::intersect_segment(const Vector3 &p_begin, const Vector3 &p_en } case VISIT_LEFT_BIT: { stack[level] = (VISIT_RIGHT_BIT << VISITED_BIT_SHIFT) | node; - stack[level + 1] = b.left | TEST_AABB_BIT; level++; + stack[level] = b.left | TEST_AABB_BIT; continue; } case VISIT_RIGHT_BIT: { stack[level] = (VISIT_DONE_BIT << VISITED_BIT_SHIFT) | node; - stack[level + 1] = b.right | TEST_AABB_BIT; level++; + stack[level] = b.right | TEST_AABB_BIT; continue; } case VISIT_DONE_BIT: { @@ -431,14 +431,14 @@ bool TriangleMesh::intersect_ray(const Vector3 &p_begin, const Vector3 &p_dir, V } case VISIT_LEFT_BIT: { stack[level] = (VISIT_RIGHT_BIT << VISITED_BIT_SHIFT) | node; - stack[level + 1] = b.left | TEST_AABB_BIT; level++; + stack[level] = b.left | TEST_AABB_BIT; continue; } case VISIT_RIGHT_BIT: { stack[level] = (VISIT_DONE_BIT << VISITED_BIT_SHIFT) | node; - stack[level + 1] = b.right | TEST_AABB_BIT; level++; + stack[level] = b.right | TEST_AABB_BIT; continue; } case VISIT_DONE_BIT: { @@ -551,14 +551,14 @@ bool TriangleMesh::intersect_convex_shape(const Plane *p_planes, int p_plane_cou } case VISIT_LEFT_BIT: { stack[level] = (VISIT_RIGHT_BIT << VISITED_BIT_SHIFT) | node; - stack[level + 1] = b.left | TEST_AABB_BIT; level++; + stack[level] = b.left | TEST_AABB_BIT; continue; } case VISIT_RIGHT_BIT: { stack[level] = (VISIT_DONE_BIT << VISITED_BIT_SHIFT) | node; - stack[level + 1] = b.right | TEST_AABB_BIT; level++; + stack[level] = b.right | TEST_AABB_BIT; continue; } case VISIT_DONE_BIT: { @@ -644,14 +644,14 @@ bool TriangleMesh::inside_convex_shape(const Plane *p_planes, int p_plane_count, } case VISIT_LEFT_BIT: { stack[level] = (VISIT_RIGHT_BIT << VISITED_BIT_SHIFT) | node; - stack[level + 1] = b.left | TEST_AABB_BIT; level++; + stack[level] = b.left | TEST_AABB_BIT; continue; } case VISIT_RIGHT_BIT: { stack[level] = (VISIT_DONE_BIT << VISITED_BIT_SHIFT) | node; - stack[level + 1] = b.right | TEST_AABB_BIT; level++; + stack[level] = b.right | TEST_AABB_BIT; continue; } case VISIT_DONE_BIT: { diff --git a/core/math/vector2.h b/core/math/vector2.h index a2680b84fc..bd67299f33 100644 --- a/core/math/vector2.h +++ b/core/math/vector2.h @@ -31,6 +31,7 @@ #ifndef VECTOR2_H #define VECTOR2_H +#include "core/error/error_macros.h" #include "core/math/math_funcs.h" class String; @@ -60,9 +61,11 @@ struct _NO_DISCARD_ Vector2 { }; _FORCE_INLINE_ real_t &operator[](int p_idx) { + DEV_ASSERT((unsigned int)p_idx < 2); return coord[p_idx]; } _FORCE_INLINE_ const real_t &operator[](int p_idx) const { + DEV_ASSERT((unsigned int)p_idx < 2); return coord[p_idx]; } diff --git a/core/math/vector2i.h b/core/math/vector2i.h index 3f5f12d4dd..13b70031bd 100644 --- a/core/math/vector2i.h +++ b/core/math/vector2i.h @@ -31,6 +31,7 @@ #ifndef VECTOR2I_H #define VECTOR2I_H +#include "core/error/error_macros.h" #include "core/math/math_funcs.h" class String; @@ -58,9 +59,11 @@ struct _NO_DISCARD_ Vector2i { }; _FORCE_INLINE_ int32_t &operator[](int p_idx) { + DEV_ASSERT((unsigned int)p_idx < 2); return coord[p_idx]; } _FORCE_INLINE_ const int32_t &operator[](int p_idx) const { + DEV_ASSERT((unsigned int)p_idx < 2); return coord[p_idx]; } diff --git a/core/math/vector3.cpp b/core/math/vector3.cpp index 87b2ac7104..f94f39b7f2 100644 --- a/core/math/vector3.cpp +++ b/core/math/vector3.cpp @@ -35,13 +35,13 @@ #include "core/math/vector3i.h" #include "core/string/ustring.h" -void Vector3::rotate(const Vector3 &p_axis, const real_t p_phi) { - *this = Basis(p_axis, p_phi).xform(*this); +void Vector3::rotate(const Vector3 &p_axis, const real_t p_angle) { + *this = Basis(p_axis, p_angle).xform(*this); } -Vector3 Vector3::rotated(const Vector3 &p_axis, const real_t p_phi) const { +Vector3 Vector3::rotated(const Vector3 &p_axis, const real_t p_angle) const { Vector3 r = *this; - r.rotate(p_axis, p_phi); + r.rotate(p_axis, p_angle); return r; } diff --git a/core/math/vector3.h b/core/math/vector3.h index 89b0095741..8891532f42 100644 --- a/core/math/vector3.h +++ b/core/math/vector3.h @@ -59,10 +59,12 @@ struct _NO_DISCARD_ Vector3 { }; _FORCE_INLINE_ const real_t &operator[](const int p_axis) const { + DEV_ASSERT((unsigned int)p_axis < 3); return coord[p_axis]; } _FORCE_INLINE_ real_t &operator[](const int p_axis) { + DEV_ASSERT((unsigned int)p_axis < 3); return coord[p_axis]; } @@ -95,8 +97,8 @@ struct _NO_DISCARD_ Vector3 { void snap(const Vector3 p_val); Vector3 snapped(const Vector3 p_val) const; - void rotate(const Vector3 &p_axis, const real_t p_phi); - Vector3 rotated(const Vector3 &p_axis, const real_t p_phi) const; + void rotate(const Vector3 &p_axis, const real_t p_angle); + Vector3 rotated(const Vector3 &p_axis, const real_t p_angle) const; /* Static Methods between 2 vector3s */ diff --git a/core/math/vector3i.h b/core/math/vector3i.h index 2a4c7e2e97..b49c1142ed 100644 --- a/core/math/vector3i.h +++ b/core/math/vector3i.h @@ -31,6 +31,7 @@ #ifndef VECTOR3I_H #define VECTOR3I_H +#include "core/error/error_macros.h" #include "core/math/math_funcs.h" class String; @@ -54,10 +55,12 @@ struct _NO_DISCARD_ Vector3i { }; _FORCE_INLINE_ const int32_t &operator[](const int p_axis) const { + DEV_ASSERT((unsigned int)p_axis < 3); return coord[p_axis]; } _FORCE_INLINE_ int32_t &operator[](const int p_axis) { + DEV_ASSERT((unsigned int)p_axis < 3); return coord[p_axis]; } |