diff options
Diffstat (limited to 'core/math')
49 files changed, 1145 insertions, 383 deletions
diff --git a/core/math/a_star.cpp b/core/math/a_star.cpp index 451c45cade..7ce3824505 100644 --- a/core/math/a_star.cpp +++ b/core/math/a_star.cpp @@ -5,8 +5,8 @@ /* GODOT ENGINE */ /* https://godotengine.org */ /*************************************************************************/ -/* Copyright (c) 2007-2018 Juan Linietsky, Ariel Manzur. */ -/* Copyright (c) 2014-2018 Godot Engine contributors (cf. AUTHORS.md) */ +/* Copyright (c) 2007-2019 Juan Linietsky, Ariel Manzur. */ +/* Copyright (c) 2014-2019 Godot Engine contributors (cf. AUTHORS.md) */ /* */ /* Permission is hereby granted, free of charge, to any person obtaining */ /* a copy of this software and associated documentation files (the */ @@ -54,7 +54,9 @@ void AStar::add_point(int p_id, const Vector3 &p_pos, real_t p_weight_scale) { pt->pos = p_pos; pt->weight_scale = p_weight_scale; pt->prev_point = NULL; - pt->last_pass = 0; + pt->open_pass = 0; + pt->closed_pass = 0; + pt->enabled = true; points[p_id] = pt; } else { points[p_id]->pos = p_pos; @@ -101,7 +103,18 @@ void AStar::remove_point(int p_id) { Segment s(p_id, E->get()->id); segments.erase(s); + E->get()->neighbours.erase(p); + E->get()->unlinked_neighbours.erase(p); + } + + for (Set<Point *>::Element *E = p->unlinked_neighbours.front(); E; E = E->next()) { + + Segment s(p_id, E->get()->id); + segments.erase(s); + + E->get()->neighbours.erase(p); + E->get()->unlinked_neighbours.erase(p); } memdelete(p); @@ -120,6 +133,8 @@ void AStar::connect_points(int p_id, int p_with_id, bool bidirectional) { if (bidirectional) b->neighbours.insert(a); + else + b->unlinked_neighbours.insert(a); Segment s(p_id, p_with_id); if (s.from == p_id) { @@ -142,7 +157,9 @@ void AStar::disconnect_points(int p_id, int p_with_id) { Point *a = points[p_id]; Point *b = points[p_with_id]; a->neighbours.erase(b); + a->unlinked_neighbours.erase(b); b->neighbours.erase(a); + b->unlinked_neighbours.erase(a); } bool AStar::has_point(int p_id) const { @@ -239,79 +256,65 @@ bool AStar::_solve(Point *begin_point, Point *end_point) { pass++; - SelfList<Point>::List open_list; + if (!end_point->enabled) + return false; bool found_route = false; - for (Set<Point *>::Element *E = begin_point->neighbours.front(); E; E = E->next()) { + Vector<Point *> open_list; + SortArray<Point *, SortPoints> sorter; - Point *n = E->get(); - n->prev_point = begin_point; - n->distance = _compute_cost(begin_point->id, n->id) * n->weight_scale; - n->last_pass = pass; - open_list.add(&n->list); - } + begin_point->g_score = 0; + begin_point->f_score = _estimate_cost(begin_point->id, end_point->id); + + open_list.push_back(begin_point); while (true) { - if (open_list.first() == NULL) { - // No path found + if (open_list.size() == 0) // No path found break; - } - // Check open list - - SelfList<Point> *least_cost_point = NULL; - real_t least_cost = 1e30; - - // TODO: Cache previous results - for (SelfList<Point> *E = open_list.first(); E; E = E->next()) { - Point *p = E->self(); + Point *p = open_list[0]; // The currently processed point - real_t cost = p->distance; - cost += _estimate_cost(p->id, end_point->id); - - if (cost < least_cost) { - least_cost_point = E; - least_cost = cost; - } - } - - Point *p = least_cost_point->self(); if (p == end_point) { found_route = true; break; } + sorter.pop_heap(0, open_list.size(), open_list.ptrw()); // Remove the current point from the open list + open_list.remove(open_list.size() - 1); + p->closed_pass = pass; // Mark the point as closed + for (Set<Point *>::Element *E = p->neighbours.front(); E; E = E->next()) { - Point *e = E->get(); + Point *e = E->get(); // The neighbour point + + if (!e->enabled || e->closed_pass == pass) + continue; - real_t distance = _compute_cost(p->id, e->id) * e->weight_scale + p->distance; + real_t tentative_g_score = p->g_score + _compute_cost(p->id, e->id) * e->weight_scale; - if (e->last_pass == pass) { - // Already visited, is this cheaper? + bool new_point = false; - if (e->distance > distance) { - e->prev_point = p; - e->distance = distance; - } - } else { - // Add to open neighbours + if (e->open_pass != pass) { // The point wasn't inside the open list - e->prev_point = p; - e->distance = distance; - e->last_pass = pass; // Mark as used - open_list.add(&e->list); + e->open_pass = pass; + open_list.push_back(e); + new_point = true; + } else if (tentative_g_score >= e->g_score) { // The new path is worse than the previous + + continue; } - } - open_list.remove(least_cost_point); - } + e->prev_point = p; + e->g_score = tentative_g_score; + e->f_score = e->g_score + _estimate_cost(e->id, end_point->id); - // Clear the openf list - while (open_list.first()) { - open_list.remove(open_list.first()); + if (new_point) // The position of the new points is already known + sorter.push_heap(0, open_list.size() - 1, 0, e, open_list.ptrw()); + else + sorter.push_heap(0, open_list.find(e), 0, e, open_list.ptrw()); + } } return found_route; @@ -338,8 +341,6 @@ PoolVector<Vector3> AStar::get_point_path(int p_from_id, int p_to_id) { ERR_FAIL_COND_V(!points.has(p_from_id), PoolVector<Vector3>()); ERR_FAIL_COND_V(!points.has(p_to_id), PoolVector<Vector3>()); - pass++; - Point *a = points[p_from_id]; Point *b = points[p_to_id]; @@ -371,14 +372,14 @@ PoolVector<Vector3> AStar::get_point_path(int p_from_id, int p_to_id) { { PoolVector<Vector3>::Write w = path.write(); - Point *p = end_point; + Point *p2 = end_point; int idx = pc - 1; - while (p != begin_point) { - w[idx--] = p->pos; - p = p->prev_point; + while (p2 != begin_point) { + w[idx--] = p2->pos; + p2 = p2->prev_point; } - w[0] = p->pos; // Assign first + w[0] = p2->pos; // Assign first } return path; @@ -389,8 +390,6 @@ PoolVector<int> AStar::get_id_path(int p_from_id, int p_to_id) { ERR_FAIL_COND_V(!points.has(p_from_id), PoolVector<int>()); ERR_FAIL_COND_V(!points.has(p_to_id), PoolVector<int>()); - pass++; - Point *a = points[p_from_id]; Point *b = points[p_to_id]; @@ -435,6 +434,20 @@ PoolVector<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) { + + ERR_FAIL_COND(!points.has(p_id)); + + points[p_id]->enabled = !p_disabled; +} + +bool AStar::is_point_disabled(int p_id) const { + + ERR_FAIL_COND_V(!points.has(p_id), false); + + return !points[p_id]->enabled; +} + void AStar::_bind_methods() { ClassDB::bind_method(D_METHOD("get_available_point_id"), &AStar::get_available_point_id); @@ -445,9 +458,11 @@ void AStar::_bind_methods() { 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_points"), &AStar::get_points); - ClassDB::bind_method(D_METHOD("get_point_connections", "id"), &AStar::get_point_connections); + 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("connect_points", "id", "to_id", "bidirectional"), &AStar::connect_points, DEFVAL(true)); ClassDB::bind_method(D_METHOD("disconnect_points", "id", "to_id"), &AStar::disconnect_points); @@ -475,3 +490,135 @@ AStar::~AStar() { pass = 1; clear(); } + +///////////////////////////////////////////////////////////// + +int AStar2D::get_available_point_id() const { + return astar.get_available_point_id(); +} + +void AStar2D::add_point(int p_id, const Vector2 &p_pos, real_t p_weight_scale) { + astar.add_point(p_id, Vector3(p_pos.x, p_pos.y, 0), p_weight_scale); +} + +Vector2 AStar2D::get_point_position(int p_id) const { + Vector3 p = astar.get_point_position(p_id); + return Vector2(p.x, p.y); +} + +void AStar2D::set_point_position(int p_id, const Vector2 &p_pos) { + astar.set_point_position(p_id, Vector3(p_pos.x, p_pos.y, 0)); +} + +real_t AStar2D::get_point_weight_scale(int p_id) const { + return astar.get_point_weight_scale(p_id); +} + +void AStar2D::set_point_weight_scale(int p_id, real_t p_weight_scale) { + astar.set_point_weight_scale(p_id, p_weight_scale); +} + +void AStar2D::remove_point(int p_id) { + astar.remove_point(p_id); +} + +bool AStar2D::has_point(int p_id) const { + return astar.has_point(p_id); +} + +PoolVector<int> AStar2D::get_point_connections(int p_id) { + return astar.get_point_connections(p_id); +} + +Array AStar2D::get_points() { + return astar.get_points(); +} + +void AStar2D::set_point_disabled(int p_id, bool p_disabled) { + astar.set_point_disabled(p_id, p_disabled); +} + +bool AStar2D::is_point_disabled(int p_id) const { + return astar.is_point_disabled(p_id); +} + +void AStar2D::connect_points(int p_id, int p_with_id, bool p_bidirectional) { + astar.connect_points(p_id, p_with_id, p_bidirectional); +} + +void AStar2D::disconnect_points(int p_id, int p_with_id) { + astar.disconnect_points(p_id, p_with_id); +} + +bool AStar2D::are_points_connected(int p_id, int p_with_id) const { + return astar.are_points_connected(p_id, p_with_id); +} + +void AStar2D::clear() { + astar.clear(); +} + +int AStar2D::get_closest_point(const Vector2 &p_point) const { + return astar.get_closest_point(Vector3(p_point.x, p_point.y, 0)); +} + +Vector2 AStar2D::get_closest_position_in_segment(const Vector2 &p_point) const { + Vector3 p = astar.get_closest_position_in_segment(Vector3(p_point.x, p_point.y, 0)); + return Vector2(p.x, p.y); +} + +PoolVector<Vector2> AStar2D::get_point_path(int p_from_id, int p_to_id) { + + PoolVector3Array pv = astar.get_point_path(p_from_id, p_to_id); + int size = pv.size(); + PoolVector2Array path; + path.resize(size); + { + PoolVector<Vector3>::Read r = pv.read(); + PoolVector<Vector2>::Write w = path.write(); + for (int i = 0; i < size; i++) { + Vector3 p = r[i]; + w[i] = Vector2(p.x, p.y); + } + } + return path; +} + +PoolVector<int> AStar2D::get_id_path(int p_from_id, int p_to_id) { + return astar.get_id_path(p_from_id, p_to_id); +} + +void AStar2D::_bind_methods() { + + ClassDB::bind_method(D_METHOD("get_available_point_id"), &AStar2D::get_available_point_id); + ClassDB::bind_method(D_METHOD("add_point", "id", "position", "weight_scale"), &AStar2D::add_point, DEFVAL(1.0)); + ClassDB::bind_method(D_METHOD("get_point_position", "id"), &AStar2D::get_point_position); + ClassDB::bind_method(D_METHOD("set_point_position", "id", "position"), &AStar2D::set_point_position); + ClassDB::bind_method(D_METHOD("get_point_weight_scale", "id"), &AStar2D::get_point_weight_scale); + ClassDB::bind_method(D_METHOD("set_point_weight_scale", "id", "weight_scale"), &AStar2D::set_point_weight_scale); + ClassDB::bind_method(D_METHOD("remove_point", "id"), &AStar2D::remove_point); + ClassDB::bind_method(D_METHOD("has_point", "id"), &AStar2D::has_point); + ClassDB::bind_method(D_METHOD("get_point_connections", "id"), &AStar2D::get_point_connections); + ClassDB::bind_method(D_METHOD("get_points"), &AStar2D::get_points); + + ClassDB::bind_method(D_METHOD("set_point_disabled", "id", "disabled"), &AStar2D::set_point_disabled, DEFVAL(true)); + ClassDB::bind_method(D_METHOD("is_point_disabled", "id"), &AStar2D::is_point_disabled); + + ClassDB::bind_method(D_METHOD("connect_points", "id", "to_id", "bidirectional"), &AStar2D::connect_points, DEFVAL(true)); + ClassDB::bind_method(D_METHOD("disconnect_points", "id", "to_id"), &AStar2D::disconnect_points); + ClassDB::bind_method(D_METHOD("are_points_connected", "id", "to_id"), &AStar2D::are_points_connected); + + ClassDB::bind_method(D_METHOD("clear"), &AStar2D::clear); + + ClassDB::bind_method(D_METHOD("get_closest_point", "to_position"), &AStar2D::get_closest_point); + ClassDB::bind_method(D_METHOD("get_closest_position_in_segment", "to_position"), &AStar2D::get_closest_position_in_segment); + + ClassDB::bind_method(D_METHOD("get_point_path", "from_id", "to_id"), &AStar2D::get_point_path); + ClassDB::bind_method(D_METHOD("get_id_path", "from_id", "to_id"), &AStar2D::get_id_path); +} + +AStar2D::AStar2D() { +} + +AStar2D::~AStar2D() { +} diff --git a/core/math/a_star.h b/core/math/a_star.h index d2ef765006..ec333efc1d 100644 --- a/core/math/a_star.h +++ b/core/math/a_star.h @@ -5,8 +5,8 @@ /* GODOT ENGINE */ /* https://godotengine.org */ /*************************************************************************/ -/* Copyright (c) 2007-2018 Juan Linietsky, Ariel Manzur. */ -/* Copyright (c) 2014-2018 Godot Engine contributors (cf. AUTHORS.md) */ +/* Copyright (c) 2007-2019 Juan Linietsky, Ariel Manzur. */ +/* Copyright (c) 2014-2019 Godot Engine contributors (cf. AUTHORS.md) */ /* */ /* Permission is hereby granted, free of charge, to any person obtaining */ /* a copy of this software and associated documentation files (the */ @@ -42,31 +42,41 @@ class AStar : public Reference { - GDCLASS(AStar, Reference) + GDCLASS(AStar, Reference); uint64_t pass; struct Point { - SelfList<Point> list; - int id; Vector3 pos; real_t weight_scale; - uint64_t last_pass; + bool enabled; Set<Point *> neighbours; + Set<Point *> unlinked_neighbours; // Used for pathfinding Point *prev_point; - real_t distance; - - Point() : - list(this) {} + real_t g_score; + real_t f_score; + uint64_t open_pass; + uint64_t closed_pass; }; Map<int, Point *> points; + struct SortPoints { + _FORCE_INLINE_ bool operator()(const Point *A, const Point *B) const { // Returns true when the Point A is worse than Point B + if (A->f_score > B->f_score) + return true; + else if (A->f_score < B->f_score) + return false; + else + return A->g_score < B->g_score; // If the f_costs are the same then prioritize the points that are further away from the start + } + }; + struct Segment { union { struct { @@ -114,6 +124,9 @@ public: PoolVector<int> get_point_connections(int p_id); Array get_points(); + void set_point_disabled(int p_id, bool p_disabled = true); + bool is_point_disabled(int p_id) const; + void connect_points(int p_id, int p_with_id, bool bidirectional = true); void disconnect_points(int p_id, int p_with_id); bool are_points_connected(int p_id, int p_with_id) const; @@ -130,4 +143,43 @@ public: ~AStar(); }; +class AStar2D : public Reference { + GDCLASS(AStar2D, Reference); + AStar astar; + +protected: + static void _bind_methods(); + +public: + int get_available_point_id() const; + + void add_point(int p_id, const Vector2 &p_pos, real_t p_weight_scale = 1); + Vector2 get_point_position(int p_id) const; + void set_point_position(int p_id, const Vector2 &p_pos); + real_t get_point_weight_scale(int p_id) const; + void set_point_weight_scale(int p_id, real_t p_weight_scale); + void remove_point(int p_id); + bool has_point(int p_id) const; + PoolVector<int> get_point_connections(int p_id); + Array get_points(); + + void set_point_disabled(int p_id, bool p_disabled = true); + bool is_point_disabled(int p_id) const; + + void connect_points(int p_id, int p_with_id, bool p_bidirectional = true); + void disconnect_points(int p_id, int p_with_id); + bool are_points_connected(int p_id, int p_with_id) const; + + void clear(); + + int get_closest_point(const Vector2 &p_point) const; + Vector2 get_closest_position_in_segment(const Vector2 &p_point) const; + + PoolVector<Vector2> get_point_path(int p_from_id, int p_to_id); + PoolVector<int> get_id_path(int p_from_id, int p_to_id); + + AStar2D(); + ~AStar2D(); +}; + #endif // ASTAR_H diff --git a/core/math/aabb.cpp b/core/math/aabb.cpp index d0cb2b5195..a4eb1fe2a5 100644 --- a/core/math/aabb.cpp +++ b/core/math/aabb.cpp @@ -5,8 +5,8 @@ /* GODOT ENGINE */ /* https://godotengine.org */ /*************************************************************************/ -/* Copyright (c) 2007-2018 Juan Linietsky, Ariel Manzur. */ -/* Copyright (c) 2014-2018 Godot Engine contributors (cf. AUTHORS.md) */ +/* Copyright (c) 2007-2019 Juan Linietsky, Ariel Manzur. */ +/* Copyright (c) 2014-2019 Godot Engine contributors (cf. AUTHORS.md) */ /* */ /* Permission is hereby granted, free of charge, to any person obtaining */ /* a copy of this software and associated documentation files (the */ diff --git a/core/math/aabb.h b/core/math/aabb.h index 0b03b7d314..52e5ed3626 100644 --- a/core/math/aabb.h +++ b/core/math/aabb.h @@ -5,8 +5,8 @@ /* GODOT ENGINE */ /* https://godotengine.org */ /*************************************************************************/ -/* Copyright (c) 2007-2018 Juan Linietsky, Ariel Manzur. */ -/* Copyright (c) 2014-2018 Godot Engine contributors (cf. AUTHORS.md) */ +/* Copyright (c) 2007-2019 Juan Linietsky, Ariel Manzur. */ +/* Copyright (c) 2014-2019 Godot Engine contributors (cf. AUTHORS.md) */ /* */ /* Permission is hereby granted, free of charge, to any person obtaining */ /* a copy of this software and associated documentation files (the */ diff --git a/core/math/audio_frame.cpp b/core/math/audio_frame.cpp index eff817bbaa..2496a70890 100644 --- a/core/math/audio_frame.cpp +++ b/core/math/audio_frame.cpp @@ -5,8 +5,8 @@ /* GODOT ENGINE */ /* https://godotengine.org */ /*************************************************************************/ -/* Copyright (c) 2007-2018 Juan Linietsky, Ariel Manzur. */ -/* Copyright (c) 2014-2018 Godot Engine contributors (cf. AUTHORS.md) */ +/* Copyright (c) 2007-2019 Juan Linietsky, Ariel Manzur. */ +/* Copyright (c) 2014-2019 Godot Engine contributors (cf. AUTHORS.md) */ /* */ /* Permission is hereby granted, free of charge, to any person obtaining */ /* a copy of this software and associated documentation files (the */ diff --git a/core/math/audio_frame.h b/core/math/audio_frame.h index fde26e8056..98e4e33021 100644 --- a/core/math/audio_frame.h +++ b/core/math/audio_frame.h @@ -5,8 +5,8 @@ /* GODOT ENGINE */ /* https://godotengine.org */ /*************************************************************************/ -/* Copyright (c) 2007-2018 Juan Linietsky, Ariel Manzur. */ -/* Copyright (c) 2014-2018 Godot Engine contributors (cf. AUTHORS.md) */ +/* Copyright (c) 2007-2019 Juan Linietsky, Ariel Manzur. */ +/* Copyright (c) 2014-2019 Godot Engine contributors (cf. AUTHORS.md) */ /* */ /* Permission is hereby granted, free of charge, to any person obtaining */ /* a copy of this software and associated documentation files (the */ @@ -31,6 +31,7 @@ #ifndef AUDIOFRAME_H #define AUDIOFRAME_H +#include "core/math/vector2.h" #include "core/typedefs.h" static inline float undenormalise(volatile float f) { @@ -122,6 +123,20 @@ struct AudioFrame { r = p_frame.r; } + _ALWAYS_INLINE_ AudioFrame operator=(const AudioFrame &p_frame) { + l = p_frame.l; + r = p_frame.r; + return *this; + } + + _ALWAYS_INLINE_ operator Vector2() const { + return Vector2(l, r); + } + + _ALWAYS_INLINE_ AudioFrame(const Vector2 &p_v2) { + l = p_v2.x; + r = p_v2.y; + } _ALWAYS_INLINE_ AudioFrame() {} }; diff --git a/core/math/matrix3.cpp b/core/math/basis.cpp index 925a7b3f1e..1540bc8fe1 100644 --- a/core/math/matrix3.cpp +++ b/core/math/basis.cpp @@ -1,12 +1,12 @@ /*************************************************************************/ -/* matrix3.cpp */ +/* basis.cpp */ /*************************************************************************/ /* This file is part of: */ /* GODOT ENGINE */ /* https://godotengine.org */ /*************************************************************************/ -/* Copyright (c) 2007-2018 Juan Linietsky, Ariel Manzur. */ -/* Copyright (c) 2014-2018 Godot Engine contributors (cf. AUTHORS.md) */ +/* Copyright (c) 2007-2019 Juan Linietsky, Ariel Manzur. */ +/* Copyright (c) 2014-2019 Godot Engine contributors (cf. AUTHORS.md) */ /* */ /* Permission is hereby granted, free of charge, to any person obtaining */ /* a copy of this software and associated documentation files (the */ @@ -28,7 +28,7 @@ /* SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. */ /*************************************************************************/ -#include "matrix3.h" +#include "basis.h" #include "core/math/math_funcs.h" #include "core/os/copymem.h" @@ -76,9 +76,11 @@ void Basis::invert() { } void Basis::orthonormalize() { + #ifdef MATH_CHECKS ERR_FAIL_COND(determinant() == 0); #endif + // Gram-Schmidt Process Vector3 x = get_axis(0); @@ -118,16 +120,16 @@ bool Basis::is_diagonal() const { } bool Basis::is_rotation() const { - return Math::is_equal_approx(determinant(), 1) && is_orthogonal(); + return Math::is_equal_approx(determinant(), 1, UNIT_EPSILON) && is_orthogonal(); } bool Basis::is_symmetric() const { - if (!Math::is_equal_approx(elements[0][1], elements[1][0])) + if (!Math::is_equal_approx_ratio(elements[0][1], elements[1][0], UNIT_EPSILON)) return false; - if (!Math::is_equal_approx(elements[0][2], elements[2][0])) + if (!Math::is_equal_approx_ratio(elements[0][2], elements[2][0], UNIT_EPSILON)) return false; - if (!Math::is_equal_approx(elements[1][2], elements[2][1])) + if (!Math::is_equal_approx_ratio(elements[1][2], elements[2][1], UNIT_EPSILON)) return false; return true; @@ -258,7 +260,7 @@ Vector3 Basis::get_scale_abs() const { } Vector3 Basis::get_scale_local() const { - real_t det_sign = determinant() > 0 ? 1 : -1; + real_t det_sign = SGN(determinant()); return det_sign * Vector3(elements[0].length(), elements[1].length(), elements[2].length()); } @@ -284,7 +286,7 @@ Vector3 Basis::get_scale() const { // matrix elements. // // The rotation part of this decomposition is returned by get_rotation* functions. - real_t det_sign = determinant() > 0 ? 1 : -1; + real_t det_sign = SGN(determinant()); return det_sign * Vector3( Vector3(elements[0][0], elements[1][0], elements[2][0]).length(), Vector3(elements[0][1], elements[1][1], elements[2][1]).length(), @@ -488,6 +490,11 @@ void Basis::set_euler_xyz(const Vector3 &p_euler) { // as the x, y, and z components of a Vector3 respectively. Vector3 Basis::get_euler_yxz() const { + /* checking this is a bad idea, because obtaining from scaled transform is a valid use case +#ifdef MATH_CHECKS + ERR_FAIL_COND(!is_rotation()); +#endif +*/ // Euler angles in YXZ convention. // See https://en.wikipedia.org/wiki/Euler_angles#Rotation_matrix // @@ -496,9 +503,7 @@ Vector3 Basis::get_euler_yxz() const { // cy*sx*sz-cz*sy cy*cz*sx+sy*sz cy*cx Vector3 euler; -#ifdef MATH_CHECKS - ERR_FAIL_COND_V(!is_rotation(), euler); -#endif + real_t m12 = elements[1][2]; if (m12 < 1) { @@ -552,11 +557,23 @@ void Basis::set_euler_yxz(const Vector3 &p_euler) { *this = ymat * xmat * zmat; } -bool Basis::is_equal_approx(const Basis &a, const Basis &b) const { +bool Basis::is_equal_approx(const Basis &a, const Basis &b, real_t p_epsilon) const { for (int i = 0; i < 3; i++) { for (int j = 0; j < 3; j++) { - if (!Math::is_equal_approx(a.elements[i][j], b.elements[i][j])) + if (!Math::is_equal_approx(a.elements[i][j], b.elements[i][j], p_epsilon)) + return false; + } + } + + return true; +} + +bool Basis::is_equal_approx_ratio(const Basis &a, const Basis &b, real_t p_epsilon) const { + + for (int i = 0; i < 3; i++) { + for (int j = 0; j < 3; j++) { + if (!Math::is_equal_approx_ratio(a.elements[i][j], b.elements[i][j], p_epsilon)) return false; } } @@ -599,10 +616,16 @@ Basis::operator String() const { } Quat Basis::get_quat() const { + #ifdef MATH_CHECKS - ERR_FAIL_COND_V(!is_rotation(), Quat()); + if (!is_rotation()) { + ERR_EXPLAIN("Basis must be normalized in order to be casted to a Quaternion. Use get_rotation_quat() or call orthonormalized() instead."); + ERR_FAIL_V(Quat()); + } #endif - real_t trace = elements[0][0] + elements[1][1] + elements[2][2]; + /* 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 temp[4]; if (trace > 0.0) { @@ -610,23 +633,23 @@ Quat Basis::get_quat() const { temp[3] = (s * 0.5); s = 0.5 / s; - temp[0] = ((elements[2][1] - elements[1][2]) * s); - temp[1] = ((elements[0][2] - elements[2][0]) * s); - temp[2] = ((elements[1][0] - elements[0][1]) * 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); } else { - int i = elements[0][0] < elements[1][1] ? - (elements[1][1] < elements[2][2] ? 2 : 1) : - (elements[0][0] < elements[2][2] ? 2 : 0); + 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 j = (i + 1) % 3; int k = (i + 2) % 3; - real_t s = Math::sqrt(elements[i][i] - elements[j][j] - elements[k][k] + 1.0); + real_t s = Math::sqrt(m.elements[i][i] - m.elements[j][j] - m.elements[k][k] + 1.0); temp[i] = s * 0.5; s = 0.5 / s; - temp[3] = (elements[k][j] - elements[j][k]) * s; - temp[j] = (elements[j][i] + elements[i][j]) * s; - temp[k] = (elements[k][i] + elements[i][k]) * 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; } return Quat(temp[0], temp[1], temp[2], temp[3]); @@ -696,9 +719,11 @@ void Basis::set_orthogonal_index(int p_index) { } void Basis::get_axis_angle(Vector3 &r_axis, real_t &r_angle) const { + /* checking this is a bad idea, because obtaining from scaled transform is a valid use case #ifdef MATH_CHECKS ERR_FAIL_COND(!is_rotation()); #endif +*/ real_t angle, x, y, z; // variables for result real_t epsilon = 0.01; // margin to allow for rounding errors real_t epsilon2 = 0.1; // margin to distinguish between 0 and 180 degrees @@ -788,21 +813,28 @@ void Basis::set_axis_angle(const Vector3 &p_axis, real_t p_phi) { ERR_FAIL_COND(!p_axis.is_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.0 - axis_sq.x); + elements[1][1] = axis_sq.y + cosine * (1.0 - axis_sq.y); + elements[2][2] = axis_sq.z + cosine * (1.0 - axis_sq.z); + real_t sine = Math::sin(p_phi); + real_t t = 1 - cosine; - elements[0][0] = axis_sq.x + cosine * (1.0 - axis_sq.x); - elements[0][1] = p_axis.x * p_axis.y * (1.0 - cosine) - p_axis.z * sine; - elements[0][2] = p_axis.z * p_axis.x * (1.0 - cosine) + p_axis.y * sine; + 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; - elements[1][0] = p_axis.x * p_axis.y * (1.0 - cosine) + p_axis.z * sine; - elements[1][1] = axis_sq.y + cosine * (1.0 - axis_sq.y); - elements[1][2] = p_axis.y * p_axis.z * (1.0 - cosine) - p_axis.x * sine; + xyzt = p_axis.x * p_axis.z * t; + zyxs = p_axis.y * sine; + elements[0][2] = xyzt + zyxs; + elements[2][0] = xyzt - zyxs; - elements[2][0] = p_axis.z * p_axis.x * (1.0 - cosine) - p_axis.y * sine; - elements[2][1] = p_axis.y * p_axis.z * (1.0 - cosine) + p_axis.x * sine; - elements[2][2] = axis_sq.z + cosine * (1.0 - axis_sq.z); + xyzt = p_axis.y * p_axis.z * t; + zyxs = p_axis.x * sine; + elements[1][2] = xyzt - zyxs; + elements[2][1] = xyzt + zyxs; } void Basis::set_axis_angle_scale(const Vector3 &p_axis, real_t p_phi, const Vector3 &p_scale) { @@ -835,14 +867,15 @@ void Basis::set_diagonal(const Vector3 p_diag) { } Basis Basis::slerp(const Basis &target, const real_t &t) const { -// TODO: implement this directly without using quaternions to make it more efficient -#ifdef MATH_CHECKS - ERR_FAIL_COND_V(!is_rotation(), Basis()); - ERR_FAIL_COND_V(!target.is_rotation(), Basis()); -#endif + //consider scale Quat from(*this); Quat to(target); - return Basis(from.slerp(to, t)); + Basis b(from.slerp(to, t)); + b.elements[0] *= Math::lerp(elements[0].length(), target.elements[0].length(), t); + b.elements[1] *= Math::lerp(elements[1].length(), target.elements[1].length(), t); + b.elements[2] *= Math::lerp(elements[2].length(), target.elements[2].length(), t); + + return b; } diff --git a/core/math/matrix3.h b/core/math/basis.h index 35bf75bbe4..75037c2c52 100644 --- a/core/math/matrix3.h +++ b/core/math/basis.h @@ -1,12 +1,12 @@ /*************************************************************************/ -/* matrix3.h */ +/* basis.h */ /*************************************************************************/ /* This file is part of: */ /* GODOT ENGINE */ /* https://godotengine.org */ /*************************************************************************/ -/* Copyright (c) 2007-2018 Juan Linietsky, Ariel Manzur. */ -/* Copyright (c) 2014-2018 Godot Engine contributors (cf. AUTHORS.md) */ +/* Copyright (c) 2007-2019 Juan Linietsky, Ariel Manzur. */ +/* Copyright (c) 2014-2019 Godot Engine contributors (cf. AUTHORS.md) */ /* */ /* Permission is hereby granted, free of charge, to any person obtaining */ /* a copy of this software and associated documentation files (the */ @@ -31,8 +31,8 @@ // Circular dependency between Vector3 and Basis :/ #include "core/math/vector3.h" -#ifndef MATRIX3_H -#define MATRIX3_H +#ifndef BASIS_H +#define BASIS_H #include "core/math/quat.h" @@ -133,7 +133,8 @@ public: return elements[0][2] * v[0] + elements[1][2] * v[1] + elements[2][2] * v[2]; } - bool is_equal_approx(const Basis &a, const Basis &b) const; + bool is_equal_approx(const Basis &a, const Basis &b, real_t p_epsilon = CMP_EPSILON) const; + bool is_equal_approx_ratio(const Basis &a, const Basis &b, real_t p_epsilon = UNIT_EPSILON) const; bool operator==(const Basis &p_matrix) const; bool operator!=(const Basis &p_matrix) const; @@ -341,4 +342,4 @@ real_t Basis::determinant() const { 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]); } -#endif +#endif // BASIS_H diff --git a/core/math/bsp_tree.cpp b/core/math/bsp_tree.cpp index 6ffc963783..d7e6e82cd9 100644 --- a/core/math/bsp_tree.cpp +++ b/core/math/bsp_tree.cpp @@ -5,8 +5,8 @@ /* GODOT ENGINE */ /* https://godotengine.org */ /*************************************************************************/ -/* Copyright (c) 2007-2018 Juan Linietsky, Ariel Manzur. */ -/* Copyright (c) 2014-2018 Godot Engine contributors (cf. AUTHORS.md) */ +/* Copyright (c) 2007-2019 Juan Linietsky, Ariel Manzur. */ +/* Copyright (c) 2014-2019 Godot Engine contributors (cf. AUTHORS.md) */ /* */ /* Permission is hereby granted, free of charge, to any person obtaining */ /* a copy of this software and associated documentation files (the */ diff --git a/core/math/bsp_tree.h b/core/math/bsp_tree.h index b06e6b8539..a7a3697990 100644 --- a/core/math/bsp_tree.h +++ b/core/math/bsp_tree.h @@ -5,8 +5,8 @@ /* GODOT ENGINE */ /* https://godotengine.org */ /*************************************************************************/ -/* Copyright (c) 2007-2018 Juan Linietsky, Ariel Manzur. */ -/* Copyright (c) 2014-2018 Godot Engine contributors (cf. AUTHORS.md) */ +/* Copyright (c) 2007-2019 Juan Linietsky, Ariel Manzur. */ +/* Copyright (c) 2014-2019 Godot Engine contributors (cf. AUTHORS.md) */ /* */ /* Permission is hereby granted, free of charge, to any person obtaining */ /* a copy of this software and associated documentation files (the */ @@ -31,11 +31,11 @@ #ifndef BSP_TREE_H #define BSP_TREE_H -#include "core/dvector.h" #include "core/math/aabb.h" #include "core/math/face3.h" #include "core/math/plane.h" #include "core/method_ptrcall.h" +#include "core/pool_vector.h" #include "core/variant.h" #include "core/vector.h" /** diff --git a/core/math/camera_matrix.cpp b/core/math/camera_matrix.cpp index 3a082d5720..f615cc8c65 100644 --- a/core/math/camera_matrix.cpp +++ b/core/math/camera_matrix.cpp @@ -5,8 +5,8 @@ /* GODOT ENGINE */ /* https://godotengine.org */ /*************************************************************************/ -/* Copyright (c) 2007-2018 Juan Linietsky, Ariel Manzur. */ -/* Copyright (c) 2014-2018 Godot Engine contributors (cf. AUTHORS.md) */ +/* Copyright (c) 2007-2019 Juan Linietsky, Ariel Manzur. */ +/* Copyright (c) 2014-2019 Godot Engine contributors (cf. AUTHORS.md) */ /* */ /* Permission is hereby granted, free of charge, to any person obtaining */ /* a copy of this software and associated documentation files (the */ @@ -210,6 +210,14 @@ void CameraMatrix::set_frustum(real_t p_left, real_t p_right, real_t p_bottom, r te[15] = 0; } +void CameraMatrix::set_frustum(real_t p_size, real_t p_aspect, Vector2 p_offset, real_t p_near, real_t p_far, bool p_flip_fov) { + if (!p_flip_fov) { + p_size *= p_aspect; + } + + set_frustum(-p_size / 2 + p_offset.x, +p_size / 2 + p_offset.x, -p_size / p_aspect / 2 + p_offset.y, +p_size / p_aspect / 2 + p_offset.y, p_near, p_far); +} + real_t CameraMatrix::get_z_far() const { const real_t *matrix = (const real_t *)this->matrix; diff --git a/core/math/camera_matrix.h b/core/math/camera_matrix.h index bd20908ad9..3bcf48f5da 100644 --- a/core/math/camera_matrix.h +++ b/core/math/camera_matrix.h @@ -5,8 +5,8 @@ /* GODOT ENGINE */ /* https://godotengine.org */ /*************************************************************************/ -/* Copyright (c) 2007-2018 Juan Linietsky, Ariel Manzur. */ -/* Copyright (c) 2014-2018 Godot Engine contributors (cf. AUTHORS.md) */ +/* Copyright (c) 2007-2019 Juan Linietsky, Ariel Manzur. */ +/* Copyright (c) 2014-2019 Godot Engine contributors (cf. AUTHORS.md) */ /* */ /* Permission is hereby granted, free of charge, to any person obtaining */ /* a copy of this software and associated documentation files (the */ @@ -61,6 +61,7 @@ struct CameraMatrix { void set_orthogonal(real_t p_left, real_t p_right, real_t p_bottom, real_t p_top, real_t p_znear, real_t p_zfar); void set_orthogonal(real_t p_size, real_t p_aspect, real_t p_znear, real_t p_zfar, bool p_flip_fov = false); void set_frustum(real_t p_left, real_t p_right, real_t p_bottom, real_t p_top, real_t p_near, real_t p_far); + void set_frustum(real_t p_size, real_t p_aspect, Vector2 p_offset, real_t p_near, real_t p_far, bool p_flip_fov = false); static real_t get_fovy(real_t p_fovx, real_t p_aspect) { diff --git a/core/math/delaunay.h b/core/math/delaunay.h index 9c5eef9069..ed52c506db 100644 --- a/core/math/delaunay.h +++ b/core/math/delaunay.h @@ -5,8 +5,8 @@ /* GODOT ENGINE */ /* https://godotengine.org */ /*************************************************************************/ -/* Copyright (c) 2007-2018 Juan Linietsky, Ariel Manzur. */ -/* Copyright (c) 2014-2018 Godot Engine contributors (cf. AUTHORS.md) */ +/* Copyright (c) 2007-2019 Juan Linietsky, Ariel Manzur. */ +/* Copyright (c) 2014-2019 Godot Engine contributors (cf. AUTHORS.md) */ /* */ /* Permission is hereby granted, free of charge, to any person obtaining */ /* a copy of this software and associated documentation files (the */ @@ -80,11 +80,11 @@ public: } static bool edge_compare(const Vector<Vector2> &p_vertices, const Edge &p_a, const Edge &p_b) { - if (p_vertices[p_a.edge[0]].distance_to(p_vertices[p_b.edge[0]]) < CMP_EPSILON && p_vertices[p_a.edge[1]].distance_to(p_vertices[p_b.edge[1]]) < CMP_EPSILON) { + if (Math::is_zero_approx(p_vertices[p_a.edge[0]].distance_to(p_vertices[p_b.edge[0]])) && Math::is_zero_approx(p_vertices[p_a.edge[1]].distance_to(p_vertices[p_b.edge[1]]))) { return true; } - if (p_vertices[p_a.edge[0]].distance_to(p_vertices[p_b.edge[1]]) < CMP_EPSILON && p_vertices[p_a.edge[1]].distance_to(p_vertices[p_b.edge[0]]) < CMP_EPSILON) { + if (Math::is_zero_approx(p_vertices[p_a.edge[0]].distance_to(p_vertices[p_b.edge[1]])) && Math::is_zero_approx(p_vertices[p_a.edge[1]].distance_to(p_vertices[p_b.edge[0]]))) { return true; } diff --git a/core/math/expression.cpp b/core/math/expression.cpp index 0cfb54234c..e484e9194d 100644 --- a/core/math/expression.cpp +++ b/core/math/expression.cpp @@ -5,8 +5,8 @@ /* GODOT ENGINE */ /* https://godotengine.org */ /*************************************************************************/ -/* Copyright (c) 2007-2018 Juan Linietsky, Ariel Manzur. */ -/* Copyright (c) 2014-2018 Godot Engine contributors (cf. AUTHORS.md) */ +/* Copyright (c) 2007-2019 Juan Linietsky, Ariel Manzur. */ +/* Copyright (c) 2014-2019 Godot Engine contributors (cf. AUTHORS.md) */ /* */ /* Permission is hereby granted, free of charge, to any person obtaining */ /* a copy of this software and associated documentation files (the */ @@ -64,10 +64,13 @@ const char *Expression::func_name[Expression::FUNC_MAX] = { "is_inf", "ease", "decimals", + "step_decimals", "stepify", "lerp", "inverse_lerp", "range_lerp", + "smoothstep", + "move_toward", "dectime", "randomize", "randi", @@ -148,6 +151,7 @@ int Expression::get_func_argument_count(BuiltinFunc p_func) { case MATH_ISNAN: case MATH_ISINF: case MATH_DECIMALS: + case MATH_STEP_DECIMALS: case MATH_SEED: case MATH_RANDSEED: case MATH_DEG2RAD: @@ -164,10 +168,10 @@ int Expression::get_func_argument_count(BuiltinFunc p_func) { case TEXT_PRINTRAW: case VAR_TO_STR: case STR_TO_VAR: - case VAR_TO_BYTES: - case BYTES_TO_VAR: case TYPE_EXISTS: return 1; + case VAR_TO_BYTES: + case BYTES_TO_VAR: case MATH_ATAN2: case MATH_FMOD: case MATH_FPOSMOD: @@ -185,6 +189,8 @@ int Expression::get_func_argument_count(BuiltinFunc p_func) { return 2; case MATH_LERP: case MATH_INVERSE_LERP: + case MATH_SMOOTHSTEP: + case MATH_MOVE_TOWARD: case MATH_DECTIME: case MATH_WRAP: case MATH_WRAPF: @@ -363,6 +369,11 @@ void Expression::exec_func(BuiltinFunc p_func, const Variant **p_inputs, Variant VALIDATE_ARG_NUM(0); *r_return = Math::step_decimals((double)*p_inputs[0]); } break; + case MATH_STEP_DECIMALS: { + + VALIDATE_ARG_NUM(0); + *r_return = Math::step_decimals((double)*p_inputs[0]); + } break; case MATH_STEPIFY: { VALIDATE_ARG_NUM(0); @@ -392,6 +403,19 @@ void Expression::exec_func(BuiltinFunc p_func, const Variant **p_inputs, Variant VALIDATE_ARG_NUM(4); *r_return = Math::range_lerp((double)*p_inputs[0], (double)*p_inputs[1], (double)*p_inputs[2], (double)*p_inputs[3], (double)*p_inputs[4]); } break; + case MATH_SMOOTHSTEP: { + VALIDATE_ARG_NUM(0); + VALIDATE_ARG_NUM(1); + VALIDATE_ARG_NUM(2); + *r_return = Math::smoothstep((double)*p_inputs[0], (double)*p_inputs[1], (double)*p_inputs[2]); + } break; + case MATH_MOVE_TOWARD: { + + VALIDATE_ARG_NUM(0); + VALIDATE_ARG_NUM(1); + VALIDATE_ARG_NUM(2); + *r_return = Math::move_toward((double)*p_inputs[0], (double)*p_inputs[1], (double)*p_inputs[2]); + } break; case MATH_DECTIME: { VALIDATE_ARG_NUM(0); @@ -696,8 +720,9 @@ void Expression::exec_func(BuiltinFunc p_func, const Variant **p_inputs, Variant case VAR_TO_BYTES: { PoolByteArray barr; + bool full_objects = *p_inputs[1]; int len; - Error err = encode_variant(*p_inputs[0], NULL, len); + Error err = encode_variant(*p_inputs[0], NULL, len, full_objects); if (err) { r_error.error = Variant::CallError::CALL_ERROR_INVALID_ARGUMENT; r_error.argument = 0; @@ -709,7 +734,7 @@ void Expression::exec_func(BuiltinFunc p_func, const Variant **p_inputs, Variant barr.resize(len); { PoolByteArray::Write w = barr.write(); - encode_variant(*p_inputs[0], w.ptr(), len); + encode_variant(*p_inputs[0], w.ptr(), len, full_objects); } *r_return = barr; } break; @@ -724,10 +749,11 @@ void Expression::exec_func(BuiltinFunc p_func, const Variant **p_inputs, Variant } PoolByteArray varr = *p_inputs[0]; + bool allow_objects = *p_inputs[1]; Variant ret; { PoolByteArray::Read r = varr.read(); - Error err = decode_variant(ret, r.ptr(), varr.size(), NULL); + Error err = decode_variant(ret, r.ptr(), varr.size(), NULL, allow_objects); if (err != OK) { r_error_str = RTR("Not enough bytes for decoding bytes, or invalid format."); r_error.error = Variant::CallError::CALL_ERROR_INVALID_ARGUMENT; @@ -750,7 +776,8 @@ void Expression::exec_func(BuiltinFunc p_func, const Variant **p_inputs, Variant *r_return = String(color); } break; - default: {} + default: { + } } } @@ -1264,10 +1291,10 @@ Expression::ENode *Expression::_parse_expression() { } str_ofs = cofs; //revert //parse an expression - ENode *expr = _parse_expression(); - if (!expr) + ENode *subexpr = _parse_expression(); + if (!subexpr) return NULL; - dn->dict.push_back(expr); + dn->dict.push_back(subexpr); _get_token(tk); if (tk.type != TK_COLON) { @@ -1275,11 +1302,11 @@ Expression::ENode *Expression::_parse_expression() { return NULL; } - expr = _parse_expression(); - if (!expr) + subexpr = _parse_expression(); + if (!subexpr) return NULL; - dn->dict.push_back(expr); + dn->dict.push_back(subexpr); cofs = str_ofs; _get_token(tk); @@ -1308,10 +1335,10 @@ Expression::ENode *Expression::_parse_expression() { } str_ofs = cofs; //revert //parse an expression - ENode *expr = _parse_expression(); - if (!expr) + ENode *subexpr = _parse_expression(); + if (!subexpr) return NULL; - an->array.push_back(expr); + an->array.push_back(subexpr); cofs = str_ofs; _get_token(tk); @@ -1355,25 +1382,25 @@ Expression::ENode *Expression::_parse_expression() { while (true) { - int cofs = str_ofs; + int cofs2 = str_ofs; _get_token(tk); if (tk.type == TK_PARENTHESIS_CLOSE) { break; } - str_ofs = cofs; //revert + str_ofs = cofs2; //revert //parse an expression - ENode *expr = _parse_expression(); - if (!expr) + ENode *subexpr = _parse_expression(); + if (!subexpr) return NULL; - func_call->arguments.push_back(expr); + func_call->arguments.push_back(subexpr); - cofs = str_ofs; + cofs2 = str_ofs; _get_token(tk); if (tk.type == TK_COMMA) { //all good } else if (tk.type == TK_PARENTHESIS_CLOSE) { - str_ofs = cofs; + str_ofs = cofs2; } else { _set_error("Expected ',' or ')'"); } @@ -1444,11 +1471,11 @@ Expression::ENode *Expression::_parse_expression() { } str_ofs = cofs; //revert //parse an expression - ENode *expr = _parse_expression(); - if (!expr) + ENode *subexpr = _parse_expression(); + if (!subexpr) return NULL; - constructor->arguments.push_back(expr); + constructor->arguments.push_back(subexpr); cofs = str_ofs; _get_token(tk); @@ -1485,11 +1512,11 @@ Expression::ENode *Expression::_parse_expression() { } str_ofs = cofs; //revert //parse an expression - ENode *expr = _parse_expression(); - if (!expr) + ENode *subexpr = _parse_expression(); + if (!subexpr) return NULL; - bifunc->arguments.push_back(expr); + bifunc->arguments.push_back(subexpr); cofs = str_ofs; _get_token(tk); @@ -1584,25 +1611,25 @@ Expression::ENode *Expression::_parse_expression() { while (true) { - int cofs = str_ofs; + int cofs3 = str_ofs; _get_token(tk); if (tk.type == TK_PARENTHESIS_CLOSE) { break; } - str_ofs = cofs; //revert + str_ofs = cofs3; //revert //parse an expression - ENode *expr = _parse_expression(); - if (!expr) + ENode *subexpr = _parse_expression(); + if (!subexpr) return NULL; - func_call->arguments.push_back(expr); + func_call->arguments.push_back(subexpr); - cofs = str_ofs; + cofs3 = str_ofs; _get_token(tk); if (tk.type == TK_COMMA) { //all good } else if (tk.type == TK_PARENTHESIS_CLOSE) { - str_ofs = cofs; + str_ofs = cofs3; } else { _set_error("Expected ',' or ')'"); } @@ -1669,7 +1696,8 @@ Expression::ENode *Expression::_parse_expression() { case TK_OP_BIT_OR: op = Variant::OP_BIT_OR; break; case TK_OP_BIT_XOR: op = Variant::OP_BIT_XOR; break; case TK_OP_BIT_INVERT: op = Variant::OP_BIT_NEGATE; break; - default: {}; + default: { + }; } if (op == Variant::OP_MAX) { //stop appending stuff @@ -1902,7 +1930,7 @@ bool Expression::_execute(const Array &p_inputs, Object *p_instance, Expression: Variant b; if (op->nodes[1]) { - bool ret = _execute(p_inputs, p_instance, op->nodes[1], b, r_error_str); + ret = _execute(p_inputs, p_instance, op->nodes[1], b, r_error_str); if (ret) return true; } @@ -2070,7 +2098,7 @@ bool Expression::_execute(const Array &p_inputs, Object *p_instance, Expression: for (int i = 0; i < call->arguments.size(); i++) { Variant value; - bool ret = _execute(p_inputs, p_instance, call->arguments[i], value, r_error_str); + ret = _execute(p_inputs, p_instance, call->arguments[i], value, r_error_str); if (ret) return true; @@ -2157,13 +2185,13 @@ void Expression::_bind_methods() { ClassDB::bind_method(D_METHOD("get_error_text"), &Expression::get_error_text); } -Expression::Expression() { - output_type = Variant::NIL; - error_set = true; - root = NULL; - nodes = NULL; - sequenced = false; - execution_error = false; +Expression::Expression() : + output_type(Variant::NIL), + sequenced(false), + error_set(true), + root(NULL), + nodes(NULL), + execution_error(false) { } Expression::~Expression() { diff --git a/core/math/expression.h b/core/math/expression.h index ac2416d0dd..1113bb6587 100644 --- a/core/math/expression.h +++ b/core/math/expression.h @@ -5,8 +5,8 @@ /* GODOT ENGINE */ /* https://godotengine.org */ /*************************************************************************/ -/* Copyright (c) 2007-2018 Juan Linietsky, Ariel Manzur. */ -/* Copyright (c) 2014-2018 Godot Engine contributors (cf. AUTHORS.md) */ +/* Copyright (c) 2007-2019 Juan Linietsky, Ariel Manzur. */ +/* Copyright (c) 2014-2019 Godot Engine contributors (cf. AUTHORS.md) */ /* */ /* Permission is hereby granted, free of charge, to any person obtaining */ /* a copy of this software and associated documentation files (the */ @@ -34,7 +34,8 @@ #include "core/reference.h" class Expression : public Reference { - GDCLASS(Expression, Reference) + GDCLASS(Expression, Reference); + public: enum BuiltinFunc { MATH_SIN, @@ -62,10 +63,13 @@ public: MATH_ISINF, MATH_EASE, MATH_DECIMALS, + MATH_STEP_DECIMALS, MATH_STEPIFY, MATH_LERP, MATH_INVERSE_LERP, MATH_RANGE_LERP, + MATH_SMOOTHSTEP, + MATH_MOVE_TOWARD, MATH_DECTIME, MATH_RANDOMIZE, MATH_RAND, @@ -116,7 +120,9 @@ private: Variant::Type type; String name; - Input() { type = Variant::NIL; } + Input() : + type(Variant::NIL) { + } }; Vector<Input> inputs; diff --git a/core/math/face3.cpp b/core/math/face3.cpp index 8366137131..ab09142b2d 100644 --- a/core/math/face3.cpp +++ b/core/math/face3.cpp @@ -5,8 +5,8 @@ /* GODOT ENGINE */ /* https://godotengine.org */ /*************************************************************************/ -/* Copyright (c) 2007-2018 Juan Linietsky, Ariel Manzur. */ -/* Copyright (c) 2014-2018 Godot Engine contributors (cf. AUTHORS.md) */ +/* Copyright (c) 2007-2019 Juan Linietsky, Ariel Manzur. */ +/* Copyright (c) 2014-2019 Godot Engine contributors (cf. AUTHORS.md) */ /* */ /* Permission is hereby granted, free of charge, to any person obtaining */ /* a copy of this software and associated documentation files (the */ diff --git a/core/math/face3.h b/core/math/face3.h index b41daf04d4..184e80ff77 100644 --- a/core/math/face3.h +++ b/core/math/face3.h @@ -5,8 +5,8 @@ /* GODOT ENGINE */ /* https://godotengine.org */ /*************************************************************************/ -/* Copyright (c) 2007-2018 Juan Linietsky, Ariel Manzur. */ -/* Copyright (c) 2014-2018 Godot Engine contributors (cf. AUTHORS.md) */ +/* Copyright (c) 2007-2019 Juan Linietsky, Ariel Manzur. */ +/* Copyright (c) 2014-2019 Godot Engine contributors (cf. AUTHORS.md) */ /* */ /* Permission is hereby granted, free of charge, to any person obtaining */ /* a copy of this software and associated documentation files (the */ @@ -241,13 +241,13 @@ bool Face3::intersects_aabb2(const AABB &p_aabb) const { real_t minT = 1e20, maxT = -1e20; for (int k = 0; k < 3; k++) { - real_t d = axis.dot(vertex[k]); + real_t vert_d = axis.dot(vertex[k]); - if (d > maxT) - maxT = d; + if (vert_d > maxT) + maxT = vert_d; - if (d < minT) - minT = d; + if (vert_d < minT) + minT = vert_d; } if (maxB < minT || maxT < minB) diff --git a/core/math/geometry.cpp b/core/math/geometry.cpp index be5e40e4e6..8314cb827c 100644 --- a/core/math/geometry.cpp +++ b/core/math/geometry.cpp @@ -5,8 +5,8 @@ /* GODOT ENGINE */ /* https://godotengine.org */ /*************************************************************************/ -/* Copyright (c) 2007-2018 Juan Linietsky, Ariel Manzur. */ -/* Copyright (c) 2014-2018 Godot Engine contributors (cf. AUTHORS.md) */ +/* Copyright (c) 2007-2019 Juan Linietsky, Ariel Manzur. */ +/* Copyright (c) 2014-2019 Godot Engine contributors (cf. AUTHORS.md) */ /* */ /* Permission is hereby granted, free of charge, to any person obtaining */ /* a copy of this software and associated documentation files (the */ @@ -31,7 +31,12 @@ #include "geometry.h" #include "core/print_string.h" +#include "thirdparty/misc/clipper.hpp" +#include "thirdparty/misc/triangulator.h" +#define SCALE_FACTOR 100000.0 // based on CMP_EPSILON + +/* this implementation is very inefficient, commenting unless bugs happen. See the other one. bool Geometry::is_point_in_polygon(const Vector2 &p_point, const Vector<Vector2> &p_polygon) { Vector<int> indices = Geometry::triangulate_polygon(p_polygon); @@ -42,6 +47,7 @@ bool Geometry::is_point_in_polygon(const Vector2 &p_point, const Vector<Vector2> } return false; } +*/ void Geometry::MeshData::optimize_vertices() { @@ -512,7 +518,7 @@ static inline void _build_faces(uint8_t ***p_cell_status, int x, int y, int z, i Vector3(1,1,1), }; */ -#define vert(m_idx) Vector3((m_idx & 4) >> 2, (m_idx & 2) >> 1, m_idx & 1) +#define vert(m_idx) Vector3(((m_idx)&4) >> 2, ((m_idx)&2) >> 1, (m_idx)&1) static const uint8_t indices[6][4] = { { 7, 6, 4, 5 }, @@ -735,6 +741,40 @@ PoolVector<Face3> Geometry::wrap_geometry(PoolVector<Face3> p_array, real_t *p_e return wrapped_faces; } +Vector<Vector<Vector2> > Geometry::decompose_polygon_in_convex(Vector<Point2> polygon) { + Vector<Vector<Vector2> > decomp; + List<TriangulatorPoly> in_poly, out_poly; + + TriangulatorPoly inp; + inp.Init(polygon.size()); + for (int i = 0; i < polygon.size(); i++) { + inp.GetPoint(i) = polygon[i]; + } + inp.SetOrientation(TRIANGULATOR_CCW); + in_poly.push_back(inp); + TriangulatorPartition tpart; + if (tpart.ConvexPartition_HM(&in_poly, &out_poly) == 0) { //failed! + ERR_PRINT("Convex decomposing failed!"); + return decomp; + } + + decomp.resize(out_poly.size()); + int idx = 0; + for (List<TriangulatorPoly>::Element *I = out_poly.front(); I; I = I->next()) { + TriangulatorPoly &tp = I->get(); + + decomp.write[idx].resize(tp.GetNumPoints()); + + for (int i = 0; i < tp.GetNumPoints(); i++) { + decomp.write[idx].write[i] = tp.GetPoint(i); + } + + idx++; + } + + return decomp; +} + Geometry::MeshData Geometry::build_convex_mesh(const PoolVector<Plane> &p_planes) { MeshData mesh; @@ -799,7 +839,7 @@ Geometry::MeshData Geometry::build_convex_mesh(const PoolVector<Plane> &p_planes Vector3 rel = edge1_A - edge0_A; real_t den = clip.normal.dot(rel); - if (Math::abs(den) < CMP_EPSILON) + if (Math::is_zero_approx(den)) continue; // point too short real_t dist = -(clip.normal.dot(edge0_A) - clip.d) / den; @@ -1097,3 +1137,106 @@ void Geometry::make_atlas(const Vector<Size2i> &p_rects, Vector<Point2i> &r_resu r_size = Size2(results[best].max_w, results[best].max_h); } + +Vector<Vector<Point2> > Geometry::_polypaths_do_operation(PolyBooleanOperation p_op, const Vector<Point2> &p_polypath_a, const Vector<Point2> &p_polypath_b, bool is_a_open) { + + using namespace ClipperLib; + + ClipType op = ctUnion; + + switch (p_op) { + case OPERATION_UNION: op = ctUnion; break; + case OPERATION_DIFFERENCE: op = ctDifference; break; + case OPERATION_INTERSECTION: op = ctIntersection; break; + case OPERATION_XOR: op = ctXor; break; + } + Path path_a, path_b; + + // Need to scale points (Clipper's requirement for robust computation) + for (int i = 0; i != p_polypath_a.size(); ++i) { + path_a << IntPoint(p_polypath_a[i].x * SCALE_FACTOR, p_polypath_a[i].y * SCALE_FACTOR); + } + for (int i = 0; i != p_polypath_b.size(); ++i) { + path_b << IntPoint(p_polypath_b[i].x * SCALE_FACTOR, p_polypath_b[i].y * SCALE_FACTOR); + } + Clipper clp; + clp.AddPath(path_a, ptSubject, !is_a_open); // forward compatible with Clipper 10.0.0 + clp.AddPath(path_b, ptClip, true); // polylines cannot be set as clip + + Paths paths; + + if (is_a_open) { + PolyTree tree; // needed to populate polylines + clp.Execute(op, tree); + OpenPathsFromPolyTree(tree, paths); + } else { + clp.Execute(op, paths); // works on closed polygons only + } + // Have to scale points down now + Vector<Vector<Point2> > polypaths; + + for (Paths::size_type i = 0; i < paths.size(); ++i) { + Vector<Vector2> polypath; + + const Path &scaled_path = paths[i]; + + for (Paths::size_type j = 0; j < scaled_path.size(); ++j) { + polypath.push_back(Point2( + static_cast<real_t>(scaled_path[j].X) / SCALE_FACTOR, + static_cast<real_t>(scaled_path[j].Y) / SCALE_FACTOR)); + } + polypaths.push_back(polypath); + } + return polypaths; +} + +Vector<Vector<Point2> > Geometry::_polypath_offset(const Vector<Point2> &p_polypath, real_t p_delta, PolyJoinType p_join_type, PolyEndType p_end_type) { + + using namespace ClipperLib; + + JoinType jt = jtSquare; + + switch (p_join_type) { + case JOIN_SQUARE: jt = jtSquare; break; + case JOIN_ROUND: jt = jtRound; break; + case JOIN_MITER: jt = jtMiter; break; + } + + EndType et = etClosedPolygon; + + switch (p_end_type) { + case END_POLYGON: et = etClosedPolygon; break; + case END_JOINED: et = etClosedLine; break; + case END_BUTT: et = etOpenButt; break; + case END_SQUARE: et = etOpenSquare; break; + case END_ROUND: et = etOpenRound; break; + } + ClipperOffset co; + Path path; + + // Need to scale points (Clipper's requirement for robust computation) + for (int i = 0; i != p_polypath.size(); ++i) { + path << IntPoint(p_polypath[i].x * SCALE_FACTOR, p_polypath[i].y * SCALE_FACTOR); + } + co.AddPath(path, jt, et); + + Paths paths; + co.Execute(paths, p_delta * SCALE_FACTOR); // inflate/deflate + + // Have to scale points down now + Vector<Vector<Point2> > polypaths; + + for (Paths::size_type i = 0; i < paths.size(); ++i) { + Vector<Vector2> polypath; + + const Path &scaled_path = paths[i]; + + for (Paths::size_type j = 0; j < scaled_path.size(); ++j) { + polypath.push_back(Point2( + static_cast<real_t>(scaled_path[j].X) / SCALE_FACTOR, + static_cast<real_t>(scaled_path[j].Y) / SCALE_FACTOR)); + } + polypaths.push_back(polypath); + } + return polypaths; +} diff --git a/core/math/geometry.h b/core/math/geometry.h index df63f0dabe..0e144e491f 100644 --- a/core/math/geometry.h +++ b/core/math/geometry.h @@ -5,8 +5,8 @@ /* GODOT ENGINE */ /* https://godotengine.org */ /*************************************************************************/ -/* Copyright (c) 2007-2018 Juan Linietsky, Ariel Manzur. */ -/* Copyright (c) 2014-2018 Godot Engine contributors (cf. AUTHORS.md) */ +/* Copyright (c) 2007-2019 Juan Linietsky, Ariel Manzur. */ +/* Copyright (c) 2014-2019 Godot Engine contributors (cf. AUTHORS.md) */ /* */ /* Permission is hereby granted, free of charge, to any person obtaining */ /* a copy of this software and associated documentation files (the */ @@ -31,12 +31,13 @@ #ifndef GEOMETRY_H #define GEOMETRY_H -#include "core/dvector.h" +#include "core/math/delaunay.h" #include "core/math/face3.h" #include "core/math/rect2.h" #include "core/math/triangulate.h" #include "core/math/vector3.h" #include "core/object.h" +#include "core/pool_vector.h" #include "core/print_string.h" #include "core/vector.h" @@ -181,8 +182,8 @@ public: } } // finally do the division to get sc and tc - sc = (Math::abs(sN) < CMP_EPSILON ? 0.0 : sN / sD); - tc = (Math::abs(tN) < CMP_EPSILON ? 0.0 : tN / tD); + sc = (Math::is_zero_approx(sN) ? 0.0 : sN / sD); + tc = (Math::is_zero_approx(tN) ? 0.0 : tN / tD); // get the difference of the two closest points Vector3 dP = w + (sc * u) - (tc * v); // = S1(sc) - S2(tc) @@ -195,7 +196,7 @@ public: Vector3 e2 = p_v2 - p_v0; Vector3 h = p_dir.cross(e2); real_t a = e1.dot(h); - if (a > -CMP_EPSILON && a < CMP_EPSILON) // parallel test + if (Math::is_zero_approx(a)) // parallel test return false; real_t f = 1.0 / a; @@ -233,7 +234,7 @@ public: Vector3 e2 = p_v2 - p_v0; Vector3 h = rel.cross(e2); real_t a = e1.dot(h); - if (a > -CMP_EPSILON && a < CMP_EPSILON) // parallel test + if (Math::is_zero_approx(a)) // parallel test return false; real_t f = 1.0 / a; @@ -514,7 +515,7 @@ public: return (cn.cross(an) > 0) == orientation; } - static bool is_point_in_polygon(const Vector2 &p_point, const Vector<Vector2> &p_polygon); + //static bool is_point_in_polygon(const Vector2 &p_point, const Vector<Vector2> &p_polygon); static Vector2 get_closest_point_to_segment_uncapped_2d(const Vector2 &p_point, const Vector2 *p_segment) { @@ -535,7 +536,7 @@ public: // see http://paulbourke.net/geometry/pointlineplane/ const real_t denom = p_dir_b.y * p_dir_a.x - p_dir_b.x * p_dir_a.y; - if (Math::abs(denom) < CMP_EPSILON) { // parallel? + if (Math::is_zero_approx(denom)) { // parallel? return false; } @@ -702,9 +703,11 @@ public: /* if we can assume that the line segment starts outside the circle (e.g. for continuous time collision detection) then the following can be skipped and we can just return the equivalent of res1 */ sqrtterm = Math::sqrt(sqrtterm); real_t res1 = (-b - sqrtterm) / (2 * a); - //real_t res2 = ( -b + sqrtterm ) / (2 * a); + real_t res2 = (-b + sqrtterm) / (2 * a); - return (res1 >= 0 && res1 <= 1) ? res1 : -1; + if (res1 >= 0 && res1 <= 1) return res1; + if (res2 >= 0 && res2 <= 1) return res2; + return -1; } static inline Vector<Vector3> clip_polygon(const Vector<Vector3> &polygon, const Plane &p_plane) { @@ -783,6 +786,91 @@ public: return clipped; } + enum PolyBooleanOperation { + OPERATION_UNION, + OPERATION_DIFFERENCE, + OPERATION_INTERSECTION, + OPERATION_XOR + }; + enum PolyJoinType { + JOIN_SQUARE, + JOIN_ROUND, + JOIN_MITER + }; + enum PolyEndType { + END_POLYGON, + END_JOINED, + END_BUTT, + END_SQUARE, + END_ROUND + }; + + static Vector<Vector<Point2> > merge_polygons_2d(const Vector<Point2> &p_polygon_a, const Vector<Point2> &p_polygon_b) { + + return _polypaths_do_operation(OPERATION_UNION, p_polygon_a, p_polygon_b); + } + + static Vector<Vector<Point2> > clip_polygons_2d(const Vector<Point2> &p_polygon_a, const Vector<Point2> &p_polygon_b) { + + return _polypaths_do_operation(OPERATION_DIFFERENCE, p_polygon_a, p_polygon_b); + } + + static Vector<Vector<Point2> > intersect_polygons_2d(const Vector<Point2> &p_polygon_a, const Vector<Point2> &p_polygon_b) { + + return _polypaths_do_operation(OPERATION_INTERSECTION, p_polygon_a, p_polygon_b); + } + + static Vector<Vector<Point2> > exclude_polygons_2d(const Vector<Point2> &p_polygon_a, const Vector<Point2> &p_polygon_b) { + + return _polypaths_do_operation(OPERATION_XOR, p_polygon_a, p_polygon_b); + } + + static Vector<Vector<Point2> > clip_polyline_with_polygon_2d(const Vector<Vector2> &p_polyline, const Vector<Vector2> &p_polygon) { + + return _polypaths_do_operation(OPERATION_DIFFERENCE, p_polyline, p_polygon, true); + } + + static Vector<Vector<Point2> > intersect_polyline_with_polygon_2d(const Vector<Vector2> &p_polyline, const Vector<Vector2> &p_polygon) { + + return _polypaths_do_operation(OPERATION_INTERSECTION, p_polyline, p_polygon, true); + } + + static Vector<Vector<Point2> > offset_polygon_2d(const Vector<Vector2> &p_polygon, real_t p_delta, PolyJoinType p_join_type) { + + return _polypath_offset(p_polygon, p_delta, p_join_type, END_POLYGON); + } + + static Vector<Vector<Point2> > offset_polyline_2d(const Vector<Vector2> &p_polygon, real_t p_delta, PolyJoinType p_join_type, PolyEndType p_end_type) { + + ERR_EXPLAIN("Attempt to offset a polyline like a polygon (use offset_polygon_2d instead)."); + ERR_FAIL_COND_V(p_end_type == END_POLYGON, Vector<Vector<Point2> >()); + + return _polypath_offset(p_polygon, p_delta, p_join_type, p_end_type); + } + + static Vector<Point2> transform_points_2d(const Vector<Point2> &p_points, const Transform2D &p_mat) { + + Vector<Point2> points; + + for (int i = 0; i < p_points.size(); ++i) { + points.push_back(p_mat.xform(p_points[i])); + } + return points; + } + + static Vector<int> triangulate_delaunay_2d(const Vector<Vector2> &p_points) { + + Vector<Delaunay2D::Triangle> tr = Delaunay2D::triangulate(p_points); + Vector<int> triangles; + + for (int i = 0; i < tr.size(); i++) { + triangles.push_back(tr[i].points[0]); + triangles.push_back(tr[i].points[1]); + triangles.push_back(tr[i].points[2]); + } + return triangles; + } + static Vector<int> triangulate_polygon(const Vector<Vector2> &p_polygon) { Vector<int> triangles; @@ -815,6 +903,36 @@ public: return sum > 0.0f; } + /* alternate implementation that should be faster */ + static bool is_point_in_polygon(const Vector2 &p_point, const Vector<Vector2> &p_polygon) { + int c = p_polygon.size(); + if (c < 3) + return false; + const Vector2 *p = p_polygon.ptr(); + Vector2 further_away(-1e20, -1e20); + Vector2 further_away_opposite(1e20, 1e20); + + for (int i = 0; i < c; i++) { + further_away.x = MAX(p[i].x, further_away.x); + further_away.y = MAX(p[i].y, further_away.y); + further_away_opposite.x = MIN(p[i].x, further_away_opposite.x); + further_away_opposite.y = MIN(p[i].y, further_away_opposite.y); + } + + further_away += (further_away - further_away_opposite) * Vector2(1.221313, 1.512312); // make point outside that won't intersect with points in segment from p_point + + int intersections = 0; + for (int i = 0; i < c; i++) { + const Vector2 &v1 = p[i]; + const Vector2 &v2 = p[(i + 1) % c]; + if (segment_intersects_segment_2d(v1, v2, p_point, further_away, NULL)) { + intersections++; + } + } + + return (intersections & 1); + } + static PoolVector<PoolVector<Face3> > separate_objects(PoolVector<Face3> p_array); static PoolVector<Face3> wrap_geometry(PoolVector<Face3> p_array, real_t *p_error = NULL); ///< create a "wrap" that encloses the given geometry @@ -919,6 +1037,7 @@ public: H.resize(k); return H; } + static Vector<Vector<Vector2> > decompose_polygon_in_convex(Vector<Point2> polygon); static MeshData build_convex_mesh(const PoolVector<Plane> &p_planes); static PoolVector<Plane> build_sphere_planes(real_t p_radius, int p_lats, int p_lons, Vector3::Axis p_axis = Vector3::AXIS_Z); @@ -927,6 +1046,10 @@ public: static PoolVector<Plane> build_capsule_planes(real_t p_radius, real_t p_height, int p_sides, int p_lats, Vector3::Axis p_axis = Vector3::AXIS_Z); static void make_atlas(const Vector<Size2i> &p_rects, Vector<Point2i> &r_result, Size2i &r_size); + +private: + static Vector<Vector<Point2> > _polypaths_do_operation(PolyBooleanOperation p_op, const Vector<Point2> &p_polypath_a, const Vector<Point2> &p_polypath_b, bool is_a_open = false); + static Vector<Vector<Point2> > _polypath_offset(const Vector<Point2> &p_polypath, real_t p_delta, PolyJoinType p_join_type, PolyEndType p_end_type); }; #endif diff --git a/core/math/math_defs.h b/core/math/math_defs.h index db9055cee2..c54d3cc96f 100644 --- a/core/math/math_defs.h +++ b/core/math/math_defs.h @@ -5,8 +5,8 @@ /* GODOT ENGINE */ /* https://godotengine.org */ /*************************************************************************/ -/* Copyright (c) 2007-2018 Juan Linietsky, Ariel Manzur. */ -/* Copyright (c) 2014-2018 Godot Engine contributors (cf. AUTHORS.md) */ +/* Copyright (c) 2007-2019 Juan Linietsky, Ariel Manzur. */ +/* Copyright (c) 2014-2019 Godot Engine contributors (cf. AUTHORS.md) */ /* */ /* Permission is hereby granted, free of charge, to any person obtaining */ /* a copy of this software and associated documentation files (the */ @@ -33,6 +33,7 @@ #define CMP_EPSILON 0.00001 #define CMP_EPSILON2 (CMP_EPSILON * CMP_EPSILON) + #define CMP_NORMALIZE_TOLERANCE 0.000001 #define CMP_POINT_IN_PLANE_EPSILON 0.00001 @@ -49,6 +50,14 @@ #define MATH_CHECKS #endif +//this epsilon is for values related to a unit size (scalar or vector len) +#ifdef PRECISE_MATH_CHECKS +#define UNIT_EPSILON 0.00001 +#else +//tolerate some more floating point error normally +#define UNIT_EPSILON 0.001 +#endif + #define USEC_TO_SEC(m_usec) ((m_usec) / 1000000.0) enum ClockDirection { diff --git a/core/math/math_fieldwise.cpp b/core/math/math_fieldwise.cpp index 20b2341ab0..f65f504f4c 100644 --- a/core/math/math_fieldwise.cpp +++ b/core/math/math_fieldwise.cpp @@ -5,8 +5,8 @@ /* GODOT ENGINE */ /* https://godotengine.org */ /*************************************************************************/ -/* Copyright (c) 2007-2018 Juan Linietsky, Ariel Manzur. */ -/* Copyright (c) 2014-2018 Godot Engine contributors (cf. AUTHORS.md) */ +/* Copyright (c) 2007-2019 Juan Linietsky, Ariel Manzur. */ +/* Copyright (c) 2014-2019 Godot Engine contributors (cf. AUTHORS.md) */ /* */ /* Permission is hereby granted, free of charge, to any person obtaining */ /* a copy of this software and associated documentation files (the */ diff --git a/core/math/math_fieldwise.h b/core/math/math_fieldwise.h index 0e7cc3ea4a..c245928f56 100644 --- a/core/math/math_fieldwise.h +++ b/core/math/math_fieldwise.h @@ -5,8 +5,8 @@ /* GODOT ENGINE */ /* https://godotengine.org */ /*************************************************************************/ -/* Copyright (c) 2007-2018 Juan Linietsky, Ariel Manzur. */ -/* Copyright (c) 2014-2018 Godot Engine contributors (cf. AUTHORS.md) */ +/* Copyright (c) 2007-2019 Juan Linietsky, Ariel Manzur. */ +/* Copyright (c) 2014-2019 Godot Engine contributors (cf. AUTHORS.md) */ /* */ /* Permission is hereby granted, free of charge, to any person obtaining */ /* a copy of this software and associated documentation files (the */ diff --git a/core/math/math_funcs.cpp b/core/math/math_funcs.cpp index 06355d15ed..5b5fd8e283 100644 --- a/core/math/math_funcs.cpp +++ b/core/math/math_funcs.cpp @@ -5,8 +5,8 @@ /* GODOT ENGINE */ /* https://godotengine.org */ /*************************************************************************/ -/* Copyright (c) 2007-2018 Juan Linietsky, Ariel Manzur. */ -/* Copyright (c) 2014-2018 Godot Engine contributors (cf. AUTHORS.md) */ +/* Copyright (c) 2007-2019 Juan Linietsky, Ariel Manzur. */ +/* Copyright (c) 2014-2019 Godot Engine contributors (cf. AUTHORS.md) */ /* */ /* Permission is hereby granted, free of charge, to any person obtaining */ /* a copy of this software and associated documentation files (the */ diff --git a/core/math/math_funcs.h b/core/math/math_funcs.h index f9d89d5d5a..0e3bd8a318 100644 --- a/core/math/math_funcs.h +++ b/core/math/math_funcs.h @@ -5,8 +5,8 @@ /* GODOT ENGINE */ /* https://godotengine.org */ /*************************************************************************/ -/* Copyright (c) 2007-2018 Juan Linietsky, Ariel Manzur. */ -/* Copyright (c) 2014-2018 Godot Engine contributors (cf. AUTHORS.md) */ +/* Copyright (c) 2007-2019 Juan Linietsky, Ariel Manzur. */ +/* Copyright (c) 2014-2019 Godot Engine contributors (cf. AUTHORS.md) */ /* */ /* Permission is hereby granted, free of charge, to any person obtaining */ /* a copy of this software and associated documentation files (the */ @@ -61,6 +61,12 @@ public: static _ALWAYS_INLINE_ double sinh(double p_x) { return ::sinh(p_x); } static _ALWAYS_INLINE_ float sinh(float p_x) { return ::sinhf(p_x); } + static _ALWAYS_INLINE_ float sinc(float p_x) { return p_x == 0 ? 1 : ::sin(p_x) / p_x; } + static _ALWAYS_INLINE_ double sinc(double p_x) { return p_x == 0 ? 1 : ::sin(p_x) / p_x; } + + static _ALWAYS_INLINE_ float sincn(float p_x) { return sinc(Math_PI * p_x); } + static _ALWAYS_INLINE_ double sincn(double p_x) { return sinc(Math_PI * p_x); } + static _ALWAYS_INLINE_ double cosh(double p_x) { return ::cosh(p_x); } static _ALWAYS_INLINE_ float cosh(float p_x) { return ::coshf(p_x); } @@ -208,6 +214,19 @@ public: static _ALWAYS_INLINE_ double range_lerp(double p_value, double p_istart, double p_istop, double p_ostart, double p_ostop) { return Math::lerp(p_ostart, p_ostop, Math::inverse_lerp(p_istart, p_istop, p_value)); } static _ALWAYS_INLINE_ float range_lerp(float p_value, float p_istart, float p_istop, float p_ostart, float p_ostop) { return Math::lerp(p_ostart, p_ostop, Math::inverse_lerp(p_istart, p_istop, p_value)); } + static _ALWAYS_INLINE_ double smoothstep(double p_from, double p_to, double p_weight) { + if (is_equal_approx(p_from, p_to)) return p_from; + double x = CLAMP((p_weight - p_from) / (p_to - p_from), 0.0, 1.0); + return x * x * (3.0 - 2.0 * x); + } + static _ALWAYS_INLINE_ float smoothstep(float p_from, float p_to, float p_weight) { + if (is_equal_approx(p_from, p_to)) return p_from; + float x = CLAMP((p_weight - p_from) / (p_to - p_from), 0.0f, 1.0f); + return x * x * (3.0f - 2.0f * x); + } + static _ALWAYS_INLINE_ double move_toward(double p_from, double p_to, double p_delta) { return abs(p_to - p_from) <= p_delta ? p_to : p_from + SGN(p_to - p_from) * p_delta; } + static _ALWAYS_INLINE_ float move_toward(float p_from, float p_to, float p_delta) { return abs(p_to - p_from) <= p_delta ? p_to : p_from + SGN(p_to - p_from) * p_delta; } + static _ALWAYS_INLINE_ double linear2db(double p_linear) { return Math::log(p_linear) * 8.6858896380650365530225783783321; } static _ALWAYS_INLINE_ float linear2db(float p_linear) { return Math::log(p_linear) * 8.6858896380650365530225783783321; } @@ -217,17 +236,17 @@ public: static _ALWAYS_INLINE_ double round(double p_val) { return (p_val >= 0) ? Math::floor(p_val + 0.5) : -Math::floor(-p_val + 0.5); } static _ALWAYS_INLINE_ float round(float p_val) { return (p_val >= 0) ? Math::floor(p_val + 0.5) : -Math::floor(-p_val + 0.5); } - static _ALWAYS_INLINE_ int wrapi(int value, int min, int max) { - int rng = max - min; - return min + ((((value - min) % rng) + rng) % rng); + static _ALWAYS_INLINE_ int64_t wrapi(int64_t value, int64_t min, int64_t max) { + int64_t rng = max - min; + return (rng != 0) ? min + ((((value - min) % rng) + rng) % rng) : min; } static _ALWAYS_INLINE_ double wrapf(double value, double min, double max) { double rng = max - min; - return value - (rng * Math::floor((value - min) / rng)); + return (!is_equal_approx(rng, 0.0)) ? value - (rng * Math::floor((value - min) / rng)) : min; } static _ALWAYS_INLINE_ float wrapf(float value, float min, float max) { float rng = max - min; - return value - (rng * Math::floor((value - min) / rng)); + return (!is_equal_approx(rng, 0.0f)) ? value - (rng * Math::floor((value - min) / rng)) : min; } // double only, as these functions are mainly used by the editor and not performance-critical, @@ -242,20 +261,39 @@ public: static void randomize(); static uint32_t rand_from_seed(uint64_t *seed); static uint32_t rand(); - static _ALWAYS_INLINE_ double randf() { return (double)rand() / (double)Math::RANDOM_MAX; } - static _ALWAYS_INLINE_ float randd() { return (float)rand() / (float)Math::RANDOM_MAX; } + static _ALWAYS_INLINE_ double randd() { return (double)rand() / (double)Math::RANDOM_MAX; } + static _ALWAYS_INLINE_ float randf() { return (float)rand() / (float)Math::RANDOM_MAX; } static double random(double from, double to); static float random(float from, float to); static real_t random(int from, int to) { return (real_t)random((real_t)from, (real_t)to); } + static _ALWAYS_INLINE_ bool is_equal_approx_ratio(real_t a, real_t b, real_t epsilon = CMP_EPSILON, real_t min_epsilon = CMP_EPSILON) { + // this is an approximate way to check that numbers are close, as a ratio of their average size + // helps compare approximate numbers that may be very big or very small + real_t diff = abs(a - b); + if (diff == 0.0 || diff < min_epsilon) { + return true; + } + real_t avg_size = (abs(a) + abs(b)) / 2.0; + diff /= avg_size; + return diff < epsilon; + } + static _ALWAYS_INLINE_ bool is_equal_approx(real_t a, real_t b) { - // TODO: Comparing floats for approximate-equality is non-trivial. - // Using epsilon should cover the typical cases in Godot (where a == b is used to compare two reals), such as matrix and vector comparison operators. - // A proper implementation in terms of ULPs should eventually replace the contents of this function. - // See https://randomascii.wordpress.com/2012/02/25/comparing-floating-point-numbers-2012-edition/ for details. + real_t tolerance = CMP_EPSILON * abs(a); + if (tolerance < CMP_EPSILON) { + tolerance = CMP_EPSILON; + } + return abs(a - b) < tolerance; + } + + static _ALWAYS_INLINE_ bool is_equal_approx(real_t a, real_t b, real_t tolerance) { + return abs(a - b) < tolerance; + } - return abs(a - b) < CMP_EPSILON; + static _ALWAYS_INLINE_ bool is_zero_approx(real_t s) { + return abs(s) < CMP_EPSILON; } static _ALWAYS_INLINE_ float absf(float g) { diff --git a/core/math/octree.h b/core/math/octree.h index cd89743a5a..d6fc9776bc 100644 --- a/core/math/octree.h +++ b/core/math/octree.h @@ -5,8 +5,8 @@ /* GODOT ENGINE */ /* https://godotengine.org */ /*************************************************************************/ -/* Copyright (c) 2007-2018 Juan Linietsky, Ariel Manzur. */ -/* Copyright (c) 2014-2018 Godot Engine contributors (cf. AUTHORS.md) */ +/* Copyright (c) 2007-2019 Juan Linietsky, Ariel Manzur. */ +/* Copyright (c) 2014-2019 Godot Engine contributors (cf. AUTHORS.md) */ /* */ /* Permission is hereby granted, free of charge, to any person obtaining */ /* a copy of this software and associated documentation files (the */ @@ -916,34 +916,34 @@ void Octree<T, use_pairs, AL>::move(OctreeElementID p_id, const AABB &p_aabb) { pass++; - for (typename List<typename Element::OctantOwner, AL>::Element *E = owners.front(); E;) { + for (typename List<typename Element::OctantOwner, AL>::Element *F = owners.front(); F;) { - Octant *o = E->get().octant; - typename List<typename Element::OctantOwner, AL>::Element *N = E->next(); + Octant *o = F->get().octant; + typename List<typename Element::OctantOwner, AL>::Element *N = F->next(); /* if (!use_pairs) - o->elements.erase( E->get().E ); + o->elements.erase( F->get().E ); */ if (use_pairs && e.pairable) - o->pairable_elements.erase(E->get().E); + o->pairable_elements.erase(F->get().E); else - o->elements.erase(E->get().E); + o->elements.erase(F->get().E); if (_remove_element_from_octant(&e, o, common_parent->parent)) { - owners.erase(E); + owners.erase(F); } - E = N; + F = N; } if (use_pairs) { //unpair child elements in anything that survived - for (typename List<typename Element::OctantOwner, AL>::Element *E = owners.front(); E; E = E->next()) { + for (typename List<typename Element::OctantOwner, AL>::Element *F = owners.front(); F; F = F->next()) { - Octant *o = E->get().octant; + Octant *o = F->get().octant; // erase children pairs, unref ONCE pass++; diff --git a/core/math/plane.cpp b/core/math/plane.cpp index 3c597d57f8..b01853c4ac 100644 --- a/core/math/plane.cpp +++ b/core/math/plane.cpp @@ -5,8 +5,8 @@ /* GODOT ENGINE */ /* https://godotengine.org */ /*************************************************************************/ -/* Copyright (c) 2007-2018 Juan Linietsky, Ariel Manzur. */ -/* Copyright (c) 2014-2018 Godot Engine contributors (cf. AUTHORS.md) */ +/* Copyright (c) 2007-2019 Juan Linietsky, Ariel Manzur. */ +/* Copyright (c) 2014-2019 Godot Engine contributors (cf. AUTHORS.md) */ /* */ /* Permission is hereby granted, free of charge, to any person obtaining */ /* a copy of this software and associated documentation files (the */ @@ -110,7 +110,7 @@ bool Plane::intersects_ray(const Vector3 &p_from, const Vector3 &p_dir, Vector3 real_t den = normal.dot(segment); //printf("den is %i\n",den); - if (Math::abs(den) <= CMP_EPSILON) { + if (Math::is_zero_approx(den)) { return false; } @@ -135,7 +135,7 @@ bool Plane::intersects_segment(const Vector3 &p_begin, const Vector3 &p_end, Vec real_t den = normal.dot(segment); //printf("den is %i\n",den); - if (Math::abs(den) <= CMP_EPSILON) { + if (Math::is_zero_approx(den)) { return false; } diff --git a/core/math/plane.h b/core/math/plane.h index 4eedebb79e..ec817edd2c 100644 --- a/core/math/plane.h +++ b/core/math/plane.h @@ -5,8 +5,8 @@ /* GODOT ENGINE */ /* https://godotengine.org */ /*************************************************************************/ -/* Copyright (c) 2007-2018 Juan Linietsky, Ariel Manzur. */ -/* Copyright (c) 2014-2018 Godot Engine contributors (cf. AUTHORS.md) */ +/* Copyright (c) 2007-2019 Juan Linietsky, Ariel Manzur. */ +/* Copyright (c) 2014-2019 Godot Engine contributors (cf. AUTHORS.md) */ /* */ /* Permission is hereby granted, free of charge, to any person obtaining */ /* a copy of this software and associated documentation files (the */ @@ -74,10 +74,11 @@ public: _FORCE_INLINE_ bool operator!=(const Plane &p_plane) const; operator String() const; - _FORCE_INLINE_ Plane() { d = 0; } + _FORCE_INLINE_ Plane() : + d(0) {} _FORCE_INLINE_ Plane(real_t p_a, real_t p_b, real_t p_c, real_t p_d) : normal(p_a, p_b, p_c), - d(p_d){}; + d(p_d) {} _FORCE_INLINE_ Plane(const Vector3 &p_normal, real_t p_d); _FORCE_INLINE_ Plane(const Vector3 &p_point, const Vector3 &p_normal); @@ -124,12 +125,12 @@ Plane::Plane(const Vector3 &p_point1, const Vector3 &p_point2, const Vector3 &p_ bool Plane::operator==(const Plane &p_plane) const { - return normal == p_plane.normal && d == p_plane.d; + return normal == p_plane.normal && Math::is_equal_approx(d, p_plane.d); } bool Plane::operator!=(const Plane &p_plane) const { - return normal != p_plane.normal || d != p_plane.d; + return normal != p_plane.normal || !Math::is_equal_approx(d, p_plane.d); } #endif // PLANE_H diff --git a/core/math/quat.cpp b/core/math/quat.cpp index 791e84f089..1a67be7384 100644 --- a/core/math/quat.cpp +++ b/core/math/quat.cpp @@ -5,8 +5,8 @@ /* GODOT ENGINE */ /* https://godotengine.org */ /*************************************************************************/ -/* Copyright (c) 2007-2018 Juan Linietsky, Ariel Manzur. */ -/* Copyright (c) 2014-2018 Godot Engine contributors (cf. AUTHORS.md) */ +/* Copyright (c) 2007-2019 Juan Linietsky, Ariel Manzur. */ +/* Copyright (c) 2014-2019 Godot Engine contributors (cf. AUTHORS.md) */ /* */ /* Permission is hereby granted, free of charge, to any person obtaining */ /* a copy of this software and associated documentation files (the */ @@ -30,7 +30,7 @@ #include "quat.h" -#include "core/math/matrix3.h" +#include "core/math/basis.h" #include "core/print_string.h" // set_euler_xyz expects a vector containing the Euler angles in the format @@ -135,7 +135,7 @@ Quat Quat::normalized() const { } bool Quat::is_normalized() const { - return Math::is_equal_approx(length_squared(), 1.0); + return Math::is_equal_approx(length_squared(), 1.0, UNIT_EPSILON); //use less epsilon } Quat Quat::inverse() const { diff --git a/core/math/quat.h b/core/math/quat.h index c4f9b3a732..8ed2fa7cc2 100644 --- a/core/math/quat.h +++ b/core/math/quat.h @@ -5,8 +5,8 @@ /* GODOT ENGINE */ /* https://godotengine.org */ /*************************************************************************/ -/* Copyright (c) 2007-2018 Juan Linietsky, Ariel Manzur. */ -/* Copyright (c) 2014-2018 Godot Engine contributors (cf. AUTHORS.md) */ +/* Copyright (c) 2007-2019 Juan Linietsky, Ariel Manzur. */ +/* Copyright (c) 2014-2019 Godot Engine contributors (cf. AUTHORS.md) */ /* */ /* Permission is hereby granted, free of charge, to any person obtaining */ /* a copy of this software and associated documentation files (the */ @@ -115,20 +115,28 @@ public: z = p_z; w = p_w; } - inline Quat(real_t p_x, real_t p_y, real_t p_z, real_t p_w) { - x = p_x; - y = p_y; - z = p_z; - w = p_w; + inline Quat(real_t p_x, real_t p_y, real_t p_z, real_t p_w) : + x(p_x), + y(p_y), + z(p_z), + w(p_w) { } Quat(const Vector3 &axis, const real_t &angle) { set_axis_angle(axis, angle); } Quat(const Vector3 &euler) { set_euler(euler); } - Quat(const Quat &q) { + Quat(const Quat &q) : + x(q.x), + y(q.y), + z(q.z), + w(q.w) { + } + + Quat operator=(const Quat &q) { x = q.x; y = q.y; z = q.z; w = q.w; + return *this; } Quat(const Vector3 &v0, const Vector3 &v1) // shortest arc @@ -153,9 +161,11 @@ public: } } - inline Quat() { - x = y = z = 0; - w = 1; + inline Quat() : + x(0), + y(0), + z(0), + w(1) { } }; diff --git a/core/math/quick_hull.cpp b/core/math/quick_hull.cpp index 23823b339a..fc2eb1454d 100644 --- a/core/math/quick_hull.cpp +++ b/core/math/quick_hull.cpp @@ -5,8 +5,8 @@ /* GODOT ENGINE */ /* https://godotengine.org */ /*************************************************************************/ -/* Copyright (c) 2007-2018 Juan Linietsky, Ariel Manzur. */ -/* Copyright (c) 2014-2018 Godot Engine contributors (cf. AUTHORS.md) */ +/* Copyright (c) 2007-2019 Juan Linietsky, Ariel Manzur. */ +/* Copyright (c) 2014-2019 Godot Engine contributors (cf. AUTHORS.md) */ /* */ /* Permission is hereby granted, free of charge, to any person obtaining */ /* a copy of this software and associated documentation files (the */ @@ -36,8 +36,6 @@ uint32_t QuickHull::debug_stop_after = 0xFFFFFFFF; Error QuickHull::build(const Vector<Vector3> &p_points, Geometry::MeshData &r_mesh) { - static const real_t over_tolerance = 0.0001; - /* CREATE AABB VOLUME */ AABB aabb; @@ -180,6 +178,8 @@ Error QuickHull::build(const Vector<Vector3> &p_points, Geometry::MeshData &r_me faces.push_back(f); } + real_t over_tolerance = 3 * UNIT_EPSILON * (aabb.size.x + aabb.size.y + aabb.size.z); + /* COMPUTE AVAILABLE VERTICES */ for (int i = 0; i < p_points.size(); i++) { @@ -438,12 +438,12 @@ Error QuickHull::build(const Vector<Vector3> &p_points, Geometry::MeshData &r_me } // remove all edge connections to this face - for (Map<Edge, RetFaceConnect>::Element *E = ret_edges.front(); E; E = E->next()) { - if (E->get().left == O) - E->get().left = NULL; + for (Map<Edge, RetFaceConnect>::Element *G = ret_edges.front(); G; G = G->next()) { + if (G->get().left == O) + G->get().left = NULL; - if (E->get().right == O) - E->get().right = NULL; + if (G->get().right == O) + G->get().right = NULL; } ret_edges.erase(F); //remove the edge diff --git a/core/math/quick_hull.h b/core/math/quick_hull.h index 0ac2758323..a445a47cbe 100644 --- a/core/math/quick_hull.h +++ b/core/math/quick_hull.h @@ -5,8 +5,8 @@ /* GODOT ENGINE */ /* https://godotengine.org */ /*************************************************************************/ -/* Copyright (c) 2007-2018 Juan Linietsky, Ariel Manzur. */ -/* Copyright (c) 2014-2018 Godot Engine contributors (cf. AUTHORS.md) */ +/* Copyright (c) 2007-2019 Juan Linietsky, Ariel Manzur. */ +/* Copyright (c) 2014-2019 Godot Engine contributors (cf. AUTHORS.md) */ /* */ /* Permission is hereby granted, free of charge, to any person obtaining */ /* a copy of this software and associated documentation files (the */ @@ -64,7 +64,7 @@ public: struct Face { Plane plane; - int vertices[3]; + uint32_t vertices[3]; Vector<int> points_over; bool operator<(const Face &p_face) const { diff --git a/core/math/random_number_generator.cpp b/core/math/random_number_generator.cpp index e4ec0dac99..6add00c1d8 100644 --- a/core/math/random_number_generator.cpp +++ b/core/math/random_number_generator.cpp @@ -5,8 +5,8 @@ /* GODOT ENGINE */ /* https://godotengine.org */ /*************************************************************************/ -/* Copyright (c) 2007-2018 Juan Linietsky, Ariel Manzur. */ -/* Copyright (c) 2014-2018 Godot Engine contributors (cf. AUTHORS.md) */ +/* Copyright (c) 2007-2019 Juan Linietsky, Ariel Manzur. */ +/* Copyright (c) 2014-2019 Godot Engine contributors (cf. AUTHORS.md) */ /* */ /* Permission is hereby granted, free of charge, to any person obtaining */ /* a copy of this software and associated documentation files (the */ @@ -40,6 +40,8 @@ void RandomNumberGenerator::_bind_methods() { ClassDB::bind_method(D_METHOD("randi"), &RandomNumberGenerator::randi); ClassDB::bind_method(D_METHOD("randf"), &RandomNumberGenerator::randf); - ClassDB::bind_method(D_METHOD("rand_range", "from", "to"), &RandomNumberGenerator::rand_range); + ClassDB::bind_method(D_METHOD("randfn", "mean", "deviation"), &RandomNumberGenerator::randfn, DEFVAL(0.0), DEFVAL(1.0)); + ClassDB::bind_method(D_METHOD("randf_range", "from", "to"), &RandomNumberGenerator::randf_range); + ClassDB::bind_method(D_METHOD("randi_range", "from", "to"), &RandomNumberGenerator::randi_range); ClassDB::bind_method(D_METHOD("randomize"), &RandomNumberGenerator::randomize); } diff --git a/core/math/random_number_generator.h b/core/math/random_number_generator.h index 557863fdbd..a6182a4b33 100644 --- a/core/math/random_number_generator.h +++ b/core/math/random_number_generator.h @@ -5,8 +5,8 @@ /* GODOT ENGINE */ /* https://godotengine.org */ /*************************************************************************/ -/* Copyright (c) 2007-2018 Juan Linietsky, Ariel Manzur. */ -/* Copyright (c) 2014-2018 Godot Engine contributors (cf. AUTHORS.md) */ +/* Copyright (c) 2007-2019 Juan Linietsky, Ariel Manzur. */ +/* Copyright (c) 2014-2019 Godot Engine contributors (cf. AUTHORS.md) */ /* */ /* Permission is hereby granted, free of charge, to any person obtaining */ /* a copy of this software and associated documentation files (the */ @@ -53,7 +53,17 @@ public: _FORCE_INLINE_ real_t randf() { return randbase.randf(); } - _FORCE_INLINE_ real_t rand_range(real_t from, real_t to) { return randbase.random(from, to); } + _FORCE_INLINE_ real_t randf_range(real_t from, real_t to) { return randbase.random(from, to); } + + _FORCE_INLINE_ real_t randfn(real_t mean = 0.0, real_t deviation = 1.0) { return randbase.randfn(mean, deviation); } + + _FORCE_INLINE_ int randi_range(int from, int to) { + unsigned int ret = randbase.rand(); + if (to < from) + return ret % (from - to + 1) + to; + else + return ret % (to - from + 1) + from; + } RandomNumberGenerator(); }; diff --git a/core/math/random_pcg.cpp b/core/math/random_pcg.cpp index 16899f79da..00c0af515d 100644 --- a/core/math/random_pcg.cpp +++ b/core/math/random_pcg.cpp @@ -5,8 +5,8 @@ /* GODOT ENGINE */ /* https://godotengine.org */ /*************************************************************************/ -/* Copyright (c) 2007-2018 Juan Linietsky, Ariel Manzur. */ -/* Copyright (c) 2014-2018 Godot Engine contributors (cf. AUTHORS.md) */ +/* Copyright (c) 2007-2019 Juan Linietsky, Ariel Manzur. */ +/* Copyright (c) 2014-2019 Godot Engine contributors (cf. AUTHORS.md) */ /* */ /* Permission is hereby granted, free of charge, to any person obtaining */ /* a copy of this software and associated documentation files (the */ @@ -32,24 +32,20 @@ #include "core/os/os.h" -RandomPCG::RandomPCG(uint64_t seed, uint64_t inc) : - pcg() { - pcg.state = seed; - pcg.inc = inc; +RandomPCG::RandomPCG(uint64_t p_seed, uint64_t p_inc) : + pcg(), + current_inc(p_inc) { + seed(p_seed); } void RandomPCG::randomize() { seed(OS::get_singleton()->get_ticks_usec() * pcg.state + PCG_DEFAULT_INC_64); } -double RandomPCG::random(double from, double to) { - unsigned int r = rand(); - double ret = (double)r / (double)RANDOM_MAX; - return (ret) * (to - from) + from; +double RandomPCG::random(double p_from, double p_to) { + return randd() * (p_to - p_from) + p_from; } -float RandomPCG::random(float from, float to) { - unsigned int r = rand(); - float ret = (float)r / (float)RANDOM_MAX; - return (ret) * (to - from) + from; +float RandomPCG::random(float p_from, float p_to) { + return randf() * (p_to - p_from) + p_from; } diff --git a/core/math/random_pcg.h b/core/math/random_pcg.h index 4a43c36ede..aa25914638 100644 --- a/core/math/random_pcg.h +++ b/core/math/random_pcg.h @@ -5,8 +5,8 @@ /* GODOT ENGINE */ /* https://godotengine.org */ /*************************************************************************/ -/* Copyright (c) 2007-2018 Juan Linietsky, Ariel Manzur. */ -/* Copyright (c) 2014-2018 Godot Engine contributors (cf. AUTHORS.md) */ +/* Copyright (c) 2007-2019 Juan Linietsky, Ariel Manzur. */ +/* Copyright (c) 2014-2019 Godot Engine contributors (cf. AUTHORS.md) */ /* */ /* Permission is hereby granted, free of charge, to any person obtaining */ /* a copy of this software and associated documentation files (the */ @@ -31,31 +31,106 @@ #ifndef RANDOM_PCG_H #define RANDOM_PCG_H +#include <math.h> + #include "core/math/math_defs.h" #include "thirdparty/misc/pcg.h" +#if defined(__GNUC__) || (_llvm_has_builtin(__builtin_clz)) +#define CLZ32(x) __builtin_clz(x) +#elif defined(_MSC_VER) +#include "intrin.h" +static int __bsr_clz32(uint32_t x) { + unsigned long index; + _BitScanReverse(&index, x); + return 31 - index; +} +#define CLZ32(x) __bsr_clz32(x) +#else +#endif + +#if defined(__GNUC__) || (_llvm_has_builtin(__builtin_ldexp) && _llvm_has_builtin(__builtin_ldexpf)) +#define LDEXP(s, e) __builtin_ldexp(s, e) +#define LDEXPF(s, e) __builtin_ldexpf(s, e) +#else +#include "math.h" +#define LDEXP(s, e) ldexp(s, e) +#define LDEXPF(s, e) ldexp(s, e) +#endif + class RandomPCG { pcg32_random_t pcg; + uint64_t current_seed; // seed with this to get the same state + uint64_t current_inc; public: - static const uint64_t DEFAULT_SEED = 12047754176567800795ULL; + static const uint64_t DEFAULT_SEED = 12047754176567800795U; static const uint64_t DEFAULT_INC = PCG_DEFAULT_INC_64; - static const uint64_t RANDOM_MAX = 4294967295; + static const uint64_t RANDOM_MAX = 0xFFFFFFFF; - RandomPCG(uint64_t seed = DEFAULT_SEED, uint64_t inc = PCG_DEFAULT_INC_64); + RandomPCG(uint64_t p_seed = DEFAULT_SEED, uint64_t p_inc = DEFAULT_INC); - _FORCE_INLINE_ void seed(uint64_t seed) { pcg.state = seed; } - _FORCE_INLINE_ uint64_t get_seed() { return pcg.state; } + _FORCE_INLINE_ void seed(uint64_t p_seed) { + current_seed = p_seed; + pcg32_srandom_r(&pcg, current_seed, current_inc); + } + _FORCE_INLINE_ uint64_t get_seed() { return current_seed; } void randomize(); - _FORCE_INLINE_ uint32_t rand() { return pcg32_random_r(&pcg); } - _FORCE_INLINE_ double randf() { return (double)rand() / (double)RANDOM_MAX; } - _FORCE_INLINE_ float randd() { return (float)rand() / (float)RANDOM_MAX; } + _FORCE_INLINE_ uint32_t rand() { + current_seed = pcg.state; + return pcg32_random_r(&pcg); + } + + // Obtaining floating point numbers in [0, 1] range with "good enough" uniformity. + // These functions sample the output of rand() as the fraction part of an infinite binary number, + // with some tricks applied to reduce ops and branching: + // 1. Instead of shifting to the first 1 and connecting random bits, we simply set the MSB and LSB to 1. + // Provided that the RNG is actually uniform bit by bit, this should have the exact same effect. + // 2. In order to compensate for exponent info loss, we count zeros from another random number, + // and just add that to the initial offset. + // This has the same probability as counting and shifting an actual bit stream: 2^-n for n zeroes. + // For all numbers above 2^-96 (2^-64 for floats), the functions should be uniform. + // However, all numbers below that threshold are floored to 0. + // The thresholds are chosen to minimize rand() calls while keeping the numbers within a totally subjective quality standard. + // If clz or ldexp isn't available, fall back to bit truncation for performance, sacrificing uniformity. + _FORCE_INLINE_ double randd() { +#if defined(CLZ32) + uint32_t proto_exp_offset = rand(); + if (unlikely(proto_exp_offset == 0)) { + return 0; + } + uint64_t significand = (((uint64_t)rand()) << 32) | rand() | 0x8000000000000001U; + return LDEXP((double)significand, -64 - CLZ32(proto_exp_offset)); +#else +#pragma message("RandomPCG::randd - intrinsic clz is not available, falling back to bit truncation") + return (double)(((((uint64_t)rand()) << 32) | rand()) & 0x1FFFFFFFFFFFFFU) / (double)0x1FFFFFFFFFFFFFU; +#endif + } + _FORCE_INLINE_ float randf() { +#if defined(CLZ32) + uint32_t proto_exp_offset = rand(); + if (unlikely(proto_exp_offset == 0)) { + return 0; + } + return LDEXPF((float)(rand() | 0x80000001), -32 - CLZ32(proto_exp_offset)); +#else +#pragma message("RandomPCG::randf - intrinsic clz is not available, falling back to bit truncation") + return (float)(rand() & 0xFFFFFF) / (float)0xFFFFFF; +#endif + } + + _FORCE_INLINE_ double randfn(double p_mean, double p_deviation) { + return p_mean + p_deviation * (cos(Math_TAU * randd()) * sqrt(-2.0 * log(randd()))); // Box-Muller transform + } + _FORCE_INLINE_ float randfn(float p_mean, float p_deviation) { + return p_mean + p_deviation * (cos(Math_TAU * randf()) * sqrt(-2.0 * log(randf()))); // Box-Muller transform + } - double random(double from, double to); - float random(float from, float to); - real_t random(int from, int to) { return (real_t)random((real_t)from, (real_t)to); } + double random(double p_from, double p_to); + float random(float p_from, float p_to); + real_t random(int p_from, int p_to) { return (real_t)random((real_t)p_from, (real_t)p_to); } }; #endif // RANDOM_PCG_H diff --git a/core/math/rect2.cpp b/core/math/rect2.cpp index 24c1c8c984..fea128afbd 100644 --- a/core/math/rect2.cpp +++ b/core/math/rect2.cpp @@ -5,8 +5,8 @@ /* GODOT ENGINE */ /* https://godotengine.org */ /*************************************************************************/ -/* Copyright (c) 2007-2018 Juan Linietsky, Ariel Manzur. */ -/* Copyright (c) 2014-2018 Godot Engine contributors (cf. AUTHORS.md) */ +/* Copyright (c) 2007-2019 Juan Linietsky, Ariel Manzur. */ +/* Copyright (c) 2014-2019 Godot Engine contributors (cf. AUTHORS.md) */ /* */ /* Permission is hereby granted, free of charge, to any person obtaining */ /* a copy of this software and associated documentation files (the */ diff --git a/core/math/rect2.h b/core/math/rect2.h index 96c0e177d3..d636aa223f 100644 --- a/core/math/rect2.h +++ b/core/math/rect2.h @@ -5,8 +5,8 @@ /* GODOT ENGINE */ /* https://godotengine.org */ /*************************************************************************/ -/* Copyright (c) 2007-2018 Juan Linietsky, Ariel Manzur. */ -/* Copyright (c) 2014-2018 Godot Engine contributors (cf. AUTHORS.md) */ +/* Copyright (c) 2007-2019 Juan Linietsky, Ariel Manzur. */ +/* Copyright (c) 2014-2019 Godot Engine contributors (cf. AUTHORS.md) */ /* */ /* Permission is hereby granted, free of charge, to any person obtaining */ /* a copy of this software and associated documentation files (the */ @@ -67,7 +67,7 @@ struct Rect2 { if (p_point.x < position.x) { real_t d = position.x - p_point.x; - dist = inside ? d : MIN(dist, d); + dist = d; inside = false; } if (p_point.y < position.y) { @@ -103,7 +103,7 @@ struct Rect2 { ((p_rect.position.y + p_rect.size.y) < (position.y + size.y)); } - inline bool has_no_area() const { + _FORCE_INLINE_ bool has_no_area() const { return (size.x <= 0 || size.y <= 0); } @@ -154,8 +154,6 @@ struct Rect2 { return true; } - inline bool no_area() const { return (size.width <= 0 || size.height <= 0); } - bool operator==(const Rect2 &p_rect) const { return position == p_rect.position && size == p_rect.size; } bool operator!=(const Rect2 &p_rect) const { return position != p_rect.position || size != p_rect.size; } @@ -189,7 +187,7 @@ struct Rect2 { return g; } - inline Rect2 expand(const Vector2 &p_vector) const { + _FORCE_INLINE_ Rect2 expand(const Vector2 &p_vector) const { Rect2 r = *this; r.expand_to(p_vector); @@ -215,7 +213,7 @@ struct Rect2 { size = end - begin; } - inline Rect2 abs() const { + _FORCE_INLINE_ Rect2 abs() const { return Rect2(Point2(position.x + MIN(size.x, 0), position.y + MIN(size.y, 0)), size.abs()); } @@ -265,7 +263,7 @@ struct Rect2i { ((p_rect.position.y + p_rect.size.y) < (position.y + size.y)); } - inline bool has_no_area() const { + _FORCE_INLINE_ bool has_no_area() const { return (size.x <= 0 || size.y <= 0); } @@ -316,8 +314,6 @@ struct Rect2i { return true; } - bool no_area() { return (size.width <= 0 || size.height <= 0); } - bool operator==(const Rect2i &p_rect) const { return position == p_rect.position && size == p_rect.size; } bool operator!=(const Rect2i &p_rect) const { return position != p_rect.position || size != p_rect.size; } @@ -331,6 +327,33 @@ struct Rect2i { return g; } + inline Rect2i grow_margin(Margin p_margin, int p_amount) const { + Rect2i g = *this; + g = g.grow_individual((MARGIN_LEFT == p_margin) ? p_amount : 0, + (MARGIN_TOP == p_margin) ? p_amount : 0, + (MARGIN_RIGHT == p_margin) ? p_amount : 0, + (MARGIN_BOTTOM == p_margin) ? p_amount : 0); + return g; + } + + inline Rect2i grow_individual(int p_left, int p_top, int p_right, int p_bottom) const { + + Rect2i g = *this; + g.position.x -= p_left; + g.position.y -= p_top; + g.size.width += p_left + p_right; + g.size.height += p_top + p_bottom; + + return g; + } + + _FORCE_INLINE_ Rect2i expand(const Vector2i &p_vector) const { + + Rect2i r = *this; + r.expand_to(p_vector); + return r; + } + inline void expand_to(const Point2i &p_vector) { Point2i begin = position; diff --git a/core/math/transform.cpp b/core/math/transform.cpp index 75257a6e60..7ff7cac914 100644 --- a/core/math/transform.cpp +++ b/core/math/transform.cpp @@ -5,8 +5,8 @@ /* GODOT ENGINE */ /* https://godotengine.org */ /*************************************************************************/ -/* Copyright (c) 2007-2018 Juan Linietsky, Ariel Manzur. */ -/* Copyright (c) 2014-2018 Godot Engine contributors (cf. AUTHORS.md) */ +/* Copyright (c) 2007-2019 Juan Linietsky, Ariel Manzur. */ +/* Copyright (c) 2014-2019 Godot Engine contributors (cf. AUTHORS.md) */ /* */ /* Permission is hereby granted, free of charge, to any person obtaining */ /* a copy of this software and associated documentation files (the */ diff --git a/core/math/transform.h b/core/math/transform.h index 97c8bf9ab0..2f43f6b035 100644 --- a/core/math/transform.h +++ b/core/math/transform.h @@ -5,8 +5,8 @@ /* GODOT ENGINE */ /* https://godotengine.org */ /*************************************************************************/ -/* Copyright (c) 2007-2018 Juan Linietsky, Ariel Manzur. */ -/* Copyright (c) 2014-2018 Godot Engine contributors (cf. AUTHORS.md) */ +/* Copyright (c) 2007-2019 Juan Linietsky, Ariel Manzur. */ +/* Copyright (c) 2014-2019 Godot Engine contributors (cf. AUTHORS.md) */ /* */ /* Permission is hereby granted, free of charge, to any person obtaining */ /* a copy of this software and associated documentation files (the */ @@ -32,7 +32,7 @@ #define TRANSFORM_H #include "core/math/aabb.h" -#include "core/math/matrix3.h" +#include "core/math/basis.h" #include "core/math/plane.h" /** diff --git a/core/math/transform_2d.cpp b/core/math/transform_2d.cpp index 4bb763c879..1d0387bd45 100644 --- a/core/math/transform_2d.cpp +++ b/core/math/transform_2d.cpp @@ -5,8 +5,8 @@ /* GODOT ENGINE */ /* https://godotengine.org */ /*************************************************************************/ -/* Copyright (c) 2007-2018 Juan Linietsky, Ariel Manzur. */ -/* Copyright (c) 2014-2018 Godot Engine contributors (cf. AUTHORS.md) */ +/* Copyright (c) 2007-2019 Juan Linietsky, Ariel Manzur. */ +/* Copyright (c) 2014-2019 Godot Engine contributors (cf. AUTHORS.md) */ /* */ /* Permission is hereby granted, free of charge, to any person obtaining */ /* a copy of this software and associated documentation files (the */ @@ -80,13 +80,14 @@ real_t Transform2D::get_rotation() const { } void Transform2D::set_rotation(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; + set_scale(scale); } Transform2D::Transform2D(real_t p_rot, const Vector2 &p_pos) { @@ -101,10 +102,17 @@ Transform2D::Transform2D(real_t p_rot, const Vector2 &p_pos) { } Size2 Transform2D::get_scale() const { - real_t det_sign = basis_determinant() > 0 ? 1 : -1; + real_t det_sign = SGN(basis_determinant()); return Size2(elements[0].length(), det_sign * elements[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; +} + void Transform2D::scale(const Size2 &p_scale) { scale_basis(p_scale); elements[2] *= p_scale; diff --git a/core/math/transform_2d.h b/core/math/transform_2d.h index c8fc3c39e3..c44678674a 100644 --- a/core/math/transform_2d.h +++ b/core/math/transform_2d.h @@ -5,8 +5,8 @@ /* GODOT ENGINE */ /* https://godotengine.org */ /*************************************************************************/ -/* Copyright (c) 2007-2018 Juan Linietsky, Ariel Manzur. */ -/* Copyright (c) 2014-2018 Godot Engine contributors (cf. AUTHORS.md) */ +/* Copyright (c) 2007-2019 Juan Linietsky, Ariel Manzur. */ +/* Copyright (c) 2014-2019 Godot Engine contributors (cf. AUTHORS.md) */ /* */ /* Permission is hereby granted, free of charge, to any person obtaining */ /* a copy of this software and associated documentation files (the */ @@ -81,6 +81,7 @@ struct Transform2D { real_t basis_determinant() const; 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; } diff --git a/core/math/triangle_mesh.cpp b/core/math/triangle_mesh.cpp index 6b8dc5eeb3..83784a1fa7 100644 --- a/core/math/triangle_mesh.cpp +++ b/core/math/triangle_mesh.cpp @@ -5,8 +5,8 @@ /* GODOT ENGINE */ /* https://godotengine.org */ /*************************************************************************/ -/* Copyright (c) 2007-2018 Juan Linietsky, Ariel Manzur. */ -/* Copyright (c) 2014-2018 Godot Engine contributors (cf. AUTHORS.md) */ +/* Copyright (c) 2007-2019 Juan Linietsky, Ariel Manzur. */ +/* Copyright (c) 2014-2019 Godot Engine contributors (cf. AUTHORS.md) */ /* */ /* Permission is hereby granted, free of charge, to any person obtaining */ /* a copy of this software and associated documentation files (the */ @@ -30,7 +30,7 @@ #include "triangle_mesh.h" -#include "core/sort.h" +#include "core/sort_array.h" int TriangleMesh::_create_bvh(BVH *p_bvh, BVH **p_bb, int p_from, int p_size, int p_depth, int &max_depth, int &max_alloc) { diff --git a/core/math/triangle_mesh.h b/core/math/triangle_mesh.h index e5f181fba7..ee7bf0f6b5 100644 --- a/core/math/triangle_mesh.h +++ b/core/math/triangle_mesh.h @@ -5,8 +5,8 @@ /* GODOT ENGINE */ /* https://godotengine.org */ /*************************************************************************/ -/* Copyright (c) 2007-2018 Juan Linietsky, Ariel Manzur. */ -/* Copyright (c) 2014-2018 Godot Engine contributors (cf. AUTHORS.md) */ +/* Copyright (c) 2007-2019 Juan Linietsky, Ariel Manzur. */ +/* Copyright (c) 2014-2019 Godot Engine contributors (cf. AUTHORS.md) */ /* */ /* Permission is hereby granted, free of charge, to any person obtaining */ /* a copy of this software and associated documentation files (the */ diff --git a/core/math/triangulate.cpp b/core/math/triangulate.cpp index 69ffc95946..be409e62a7 100644 --- a/core/math/triangulate.cpp +++ b/core/math/triangulate.cpp @@ -5,8 +5,8 @@ /* GODOT ENGINE */ /* https://godotengine.org */ /*************************************************************************/ -/* Copyright (c) 2007-2018 Juan Linietsky, Ariel Manzur. */ -/* Copyright (c) 2014-2018 Godot Engine contributors (cf. AUTHORS.md) */ +/* Copyright (c) 2007-2019 Juan Linietsky, Ariel Manzur. */ +/* Copyright (c) 2014-2019 Godot Engine contributors (cf. AUTHORS.md) */ /* */ /* Permission is hereby granted, free of charge, to any person obtaining */ /* a copy of this software and associated documentation files (the */ diff --git a/core/math/triangulate.h b/core/math/triangulate.h index 2b0557ee55..2437e2b0f0 100644 --- a/core/math/triangulate.h +++ b/core/math/triangulate.h @@ -5,8 +5,8 @@ /* GODOT ENGINE */ /* https://godotengine.org */ /*************************************************************************/ -/* Copyright (c) 2007-2018 Juan Linietsky, Ariel Manzur. */ -/* Copyright (c) 2014-2018 Godot Engine contributors (cf. AUTHORS.md) */ +/* Copyright (c) 2007-2019 Juan Linietsky, Ariel Manzur. */ +/* Copyright (c) 2014-2019 Godot Engine contributors (cf. AUTHORS.md) */ /* */ /* Permission is hereby granted, free of charge, to any person obtaining */ /* a copy of this software and associated documentation files (the */ diff --git a/core/math/vector2.cpp b/core/math/vector2.cpp index 7c6f056f09..779a28be66 100644 --- a/core/math/vector2.cpp +++ b/core/math/vector2.cpp @@ -5,8 +5,8 @@ /* GODOT ENGINE */ /* https://godotengine.org */ /*************************************************************************/ -/* Copyright (c) 2007-2018 Juan Linietsky, Ariel Manzur. */ -/* Copyright (c) 2014-2018 Godot Engine contributors (cf. AUTHORS.md) */ +/* Copyright (c) 2007-2019 Juan Linietsky, Ariel Manzur. */ +/* Copyright (c) 2014-2019 Godot Engine contributors (cf. AUTHORS.md) */ /* */ /* Permission is hereby granted, free of charge, to any person obtaining */ /* a copy of this software and associated documentation files (the */ @@ -65,7 +65,7 @@ Vector2 Vector2::normalized() const { bool Vector2::is_normalized() const { // use length_squared() instead of length() to avoid sqrt(), makes it more stringent. - return Math::is_equal_approx(length_squared(), 1.0); + return Math::is_equal_approx(length_squared(), 1.0, UNIT_EPSILON); } real_t Vector2::distance_to(const Vector2 &p_vector2) const { @@ -164,6 +164,13 @@ Vector2 Vector2::cubic_interpolate(const Vector2 &p_b, const Vector2 &p_pre_a, c return out; } +Vector2 Vector2::move_toward(const Vector2 &p_to, const real_t p_delta) const { + Vector2 v = *this; + Vector2 vd = p_to - v; + real_t len = vd.length(); + return len <= p_delta || len < CMP_EPSILON ? p_to : v + vd / len * p_delta; +} + // slide returns the component of the vector along the given plane, specified by its normal vector. Vector2 Vector2::slide(const Vector2 &p_normal) const { #ifdef MATH_CHECKS diff --git a/core/math/vector2.h b/core/math/vector2.h index e5e555597d..78a1641c1e 100644 --- a/core/math/vector2.h +++ b/core/math/vector2.h @@ -5,8 +5,8 @@ /* GODOT ENGINE */ /* https://godotengine.org */ /*************************************************************************/ -/* Copyright (c) 2007-2018 Juan Linietsky, Ariel Manzur. */ -/* Copyright (c) 2014-2018 Godot Engine contributors (cf. AUTHORS.md) */ +/* Copyright (c) 2007-2019 Juan Linietsky, Ariel Manzur. */ +/* Copyright (c) 2014-2019 Godot Engine contributors (cf. AUTHORS.md) */ /* */ /* Permission is hereby granted, free of charge, to any person obtaining */ /* a copy of this software and associated documentation files (the */ @@ -65,6 +65,7 @@ struct Vector2 { real_t distance_squared_to(const Vector2 &p_vector2) const; real_t angle_to(const Vector2 &p_vector2) const; real_t angle_to_point(const Vector2 &p_vector2) const; + _FORCE_INLINE_ Vector2 direction_to(const Vector2 &p_b) const; real_t dot(const Vector2 &p_other) const; real_t cross(const Vector2 &p_other) const; @@ -78,6 +79,7 @@ struct Vector2 { _FORCE_INLINE_ Vector2 linear_interpolate(const Vector2 &p_b, real_t p_t) const; _FORCE_INLINE_ Vector2 slerp(const Vector2 &p_b, real_t p_t) const; Vector2 cubic_interpolate(const Vector2 &p_b, const Vector2 &p_pre_a, const Vector2 &p_post_b, real_t p_t) const; + Vector2 move_toward(const Vector2 &p_to, const real_t p_delta) const; Vector2 slide(const Vector2 &p_normal) const; Vector2 bounce(const Vector2 &p_normal) const; @@ -98,14 +100,15 @@ struct Vector2 { Vector2 operator/(const real_t &rvalue) const; void operator/=(const real_t &rvalue); + void operator/=(const Vector2 &rvalue) { *this = *this / rvalue; } Vector2 operator-() const; bool operator==(const Vector2 &p_vec2) const; bool operator!=(const Vector2 &p_vec2) const; - bool operator<(const Vector2 &p_vec2) const { return (x == p_vec2.x) ? (y < p_vec2.y) : (x < p_vec2.x); } - bool operator<=(const Vector2 &p_vec2) const { return (x == p_vec2.x) ? (y <= p_vec2.y) : (x <= p_vec2.x); } + bool operator<(const Vector2 &p_vec2) const { return (Math::is_equal_approx(x, p_vec2.x)) ? (y < p_vec2.y) : (x < p_vec2.x); } + bool operator<=(const Vector2 &p_vec2) const { return (Math::is_equal_approx(x, p_vec2.x)) ? (y <= p_vec2.y) : (x < p_vec2.x); } real_t angle() const; @@ -211,11 +214,11 @@ _FORCE_INLINE_ Vector2 Vector2::operator-() const { _FORCE_INLINE_ bool Vector2::operator==(const Vector2 &p_vec2) const { - return x == p_vec2.x && y == p_vec2.y; + return Math::is_equal_approx(x, p_vec2.x) && Math::is_equal_approx(y, p_vec2.y); } _FORCE_INLINE_ bool Vector2::operator!=(const Vector2 &p_vec2) const { - return x != p_vec2.x || y != p_vec2.y; + return !Math::is_equal_approx(x, p_vec2.x) || !Math::is_equal_approx(y, p_vec2.y); } Vector2 Vector2::linear_interpolate(const Vector2 &p_b, real_t p_t) const { @@ -236,6 +239,12 @@ Vector2 Vector2::slerp(const Vector2 &p_b, real_t p_t) const { return rotated(theta * p_t); } +Vector2 Vector2::direction_to(const Vector2 &p_b) const { + Vector2 ret(p_b.x - x, p_b.y - y); + ret.normalize(); + return ret; +} + Vector2 Vector2::linear_interpolate(const Vector2 &p_a, const Vector2 &p_b, real_t p_t) { Vector2 res = p_a; diff --git a/core/math/vector3.cpp b/core/math/vector3.cpp index 5dbb01493d..73927821cf 100644 --- a/core/math/vector3.cpp +++ b/core/math/vector3.cpp @@ -5,8 +5,8 @@ /* GODOT ENGINE */ /* https://godotengine.org */ /*************************************************************************/ -/* Copyright (c) 2007-2018 Juan Linietsky, Ariel Manzur. */ -/* Copyright (c) 2014-2018 Godot Engine contributors (cf. AUTHORS.md) */ +/* Copyright (c) 2007-2019 Juan Linietsky, Ariel Manzur. */ +/* Copyright (c) 2014-2019 Godot Engine contributors (cf. AUTHORS.md) */ /* */ /* Permission is hereby granted, free of charge, to any person obtaining */ /* a copy of this software and associated documentation files (the */ @@ -30,7 +30,7 @@ #include "vector3.h" -#include "core/math/matrix3.h" +#include "core/math/basis.h" void Vector3::rotate(const Vector3 &p_axis, real_t p_phi) { @@ -127,6 +127,13 @@ Vector3 Vector3::cubic_interpolate(const Vector3 &p_b, const Vector3 &p_pre_a, c return out; } +Vector3 Vector3::move_toward(const Vector3 &p_to, const real_t p_delta) const { + Vector3 v = *this; + Vector3 vd = p_to - v; + real_t len = vd.length(); + return len <= p_delta || len < CMP_EPSILON ? p_to : v + vd / len * p_delta; +} + Vector3::operator String() const { return (rtos(x) + ", " + rtos(y) + ", " + rtos(z)); diff --git a/core/math/vector3.h b/core/math/vector3.h index 16feba6a0c..811a207138 100644 --- a/core/math/vector3.h +++ b/core/math/vector3.h @@ -5,8 +5,8 @@ /* GODOT ENGINE */ /* https://godotengine.org */ /*************************************************************************/ -/* Copyright (c) 2007-2018 Juan Linietsky, Ariel Manzur. */ -/* Copyright (c) 2014-2018 Godot Engine contributors (cf. AUTHORS.md) */ +/* Copyright (c) 2007-2019 Juan Linietsky, Ariel Manzur. */ +/* Copyright (c) 2014-2019 Godot Engine contributors (cf. AUTHORS.md) */ /* */ /* Permission is hereby granted, free of charge, to any person obtaining */ /* a copy of this software and associated documentation files (the */ @@ -94,6 +94,7 @@ struct Vector3 { _FORCE_INLINE_ Vector3 slerp(const Vector3 &p_b, real_t p_t) const; Vector3 cubic_interpolate(const Vector3 &p_b, const Vector3 &p_pre_a, const Vector3 &p_post_b, real_t p_t) const; Vector3 cubic_interpolaten(const Vector3 &p_b, const Vector3 &p_pre_a, const Vector3 &p_post_b, real_t p_t) const; + Vector3 move_toward(const Vector3 &p_to, const real_t p_delta) const; _FORCE_INLINE_ Vector3 cross(const Vector3 &p_b) const; _FORCE_INLINE_ real_t dot(const Vector3 &p_b) const; @@ -112,6 +113,7 @@ struct Vector3 { _FORCE_INLINE_ Vector3 project(const Vector3 &p_b) const; _FORCE_INLINE_ real_t angle_to(const Vector3 &p_b) const; + _FORCE_INLINE_ Vector3 direction_to(const Vector3 &p_b) const; _FORCE_INLINE_ Vector3 slide(const Vector3 &p_normal) const; _FORCE_INLINE_ Vector3 bounce(const Vector3 &p_normal) const; @@ -151,7 +153,7 @@ struct Vector3 { }; // Should be included after class definition, otherwise we get circular refs -#include "core/math/matrix3.h" +#include "core/math/basis.h" Vector3 Vector3::cross(const Vector3 &p_b) const { @@ -222,7 +224,7 @@ Vector3 Vector3::slerp(const Vector3 &p_b, real_t p_t) const { #endif real_t theta = angle_to(p_b); - return rotated(cross(p_b), theta * p_t); + return rotated(cross(p_b).normalized(), theta * p_t); } real_t Vector3::distance_to(const Vector3 &p_b) const { @@ -244,6 +246,12 @@ real_t Vector3::angle_to(const Vector3 &p_b) const { return Math::atan2(cross(p_b).length(), dot(p_b)); } +Vector3 Vector3::direction_to(const Vector3 &p_b) const { + Vector3 ret(p_b.x - x, p_b.y - y, p_b.z - z); + ret.normalize(); + return ret; +} + /* Operators */ Vector3 &Vector3::operator+=(const Vector3 &p_v) { @@ -334,17 +342,17 @@ Vector3 Vector3::operator-() const { bool Vector3::operator==(const Vector3 &p_v) const { - return (x == p_v.x && y == p_v.y && z == p_v.z); + return (Math::is_equal_approx(x, p_v.x) && Math::is_equal_approx(y, p_v.y) && Math::is_equal_approx(z, p_v.z)); } bool Vector3::operator!=(const Vector3 &p_v) const { - return (x != p_v.x || y != p_v.y || z != p_v.z); + return (!Math::is_equal_approx(x, p_v.x) || !Math::is_equal_approx(y, p_v.y) || !Math::is_equal_approx(z, p_v.z)); } bool Vector3::operator<(const Vector3 &p_v) const { - if (x == p_v.x) { - if (y == p_v.y) + if (Math::is_equal_approx(x, p_v.x)) { + if (Math::is_equal_approx(y, p_v.y)) return z < p_v.z; else return y < p_v.y; @@ -355,8 +363,8 @@ bool Vector3::operator<(const Vector3 &p_v) const { bool Vector3::operator<=(const Vector3 &p_v) const { - if (x == p_v.x) { - if (y == p_v.y) + if (Math::is_equal_approx(x, p_v.x)) { + if (Math::is_equal_approx(y, p_v.y)) return z <= p_v.z; else return y < p_v.y; @@ -395,13 +403,14 @@ real_t Vector3::length_squared() const { void Vector3::normalize() { - real_t l = length(); - if (l == 0) { + real_t lengthsq = length_squared(); + if (lengthsq == 0) { x = y = z = 0; } else { - x /= l; - y /= l; - z /= l; + real_t length = Math::sqrt(lengthsq); + x /= length; + y /= length; + z /= length; } } @@ -414,7 +423,7 @@ Vector3 Vector3::normalized() const { bool Vector3::is_normalized() const { // use length_squared() instead of length() to avoid sqrt(), makes it more stringent. - return Math::is_equal_approx(length_squared(), 1.0); + return Math::is_equal_approx(length_squared(), 1.0, UNIT_EPSILON); } Vector3 Vector3::inverse() const { |