diff options
Diffstat (limited to 'core/math')
40 files changed, 616 insertions, 2301 deletions
diff --git a/core/math/a_star.cpp b/core/math/a_star.cpp index 110185c2d2..838fec22f0 100644 --- a/core/math/a_star.cpp +++ b/core/math/a_star.cpp @@ -6,6 +6,7 @@ /* http://www.godotengine.org */ /*************************************************************************/ /* Copyright (c) 2007-2017 Juan Linietsky, Ariel Manzur. */ +/* Copyright (c) 2014-2017 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,6 +29,8 @@ /*************************************************************************/ #include "a_star.h" #include "geometry.h" +#include "scene/scene_string_names.h" +#include "script_language.h" int AStar::get_available_point_id() const { @@ -40,6 +43,7 @@ int AStar::get_available_point_id() const { void AStar::add_point(int p_id, const Vector3 &p_pos, real_t p_weight_scale) { ERR_FAIL_COND(p_id < 0); + ERR_FAIL_COND(p_weight_scale < 1); if (!points.has(p_id)) { Point *pt = memnew(Point); pt->id = p_id; @@ -83,7 +87,7 @@ void AStar::remove_point(int p_id) { points.erase(p_id); } -void AStar::connect_points(int p_id, int p_with_id) { +void AStar::connect_points(int p_id, int p_with_id, bool bidirectional) { ERR_FAIL_COND(!points.has(p_id)); ERR_FAIL_COND(!points.has(p_with_id)); @@ -92,7 +96,9 @@ void AStar::connect_points(int p_id, int p_with_id) { Point *a = points[p_id]; Point *b = points[p_with_id]; a->neighbours.push_back(b); - b->neighbours.push_back(a); + + if (bidirectional) + b->neighbours.push_back(a); Segment s(p_id, p_with_id); if (s.from == p_id) { @@ -187,8 +193,7 @@ bool AStar::_solve(Point *begin_point, Point *end_point) { Point *n = begin_point->neighbours[i]; n->prev_point = begin_point; - n->distance = n->pos.distance_to(begin_point->pos); - n->distance *= n->weight_scale; + n->distance = _compute_cost(begin_point->id, n->id) * n->weight_scale; n->last_pass = pass; open_list.add(&n->list); @@ -215,8 +220,7 @@ bool AStar::_solve(Point *begin_point, Point *end_point) { Point *p = E->self(); real_t cost = p->distance; - cost += p->pos.distance_to(end_point->pos); - cost *= p->weight_scale; + cost += _estimate_cost(p->id, end_point->id); if (cost < least_cost) { @@ -233,8 +237,7 @@ bool AStar::_solve(Point *begin_point, Point *end_point) { Point *e = p->neighbours[i]; - real_t distance = p->pos.distance_to(e->pos) + p->distance; - distance *= e->weight_scale; + real_t distance = _compute_cost(p->id, e->id) * e->weight_scale + p->distance; if (e->last_pass == pass) { //oh this was visited already, can we win the cost? @@ -274,6 +277,20 @@ bool AStar::_solve(Point *begin_point, Point *end_point) { return found_route; } +float AStar::_estimate_cost(int p_from_id, int p_to_id) { + if (get_script_instance() && get_script_instance()->has_method(SceneStringNames::get_singleton()->_estimate_cost)) + return get_script_instance()->call(SceneStringNames::get_singleton()->_estimate_cost, p_from_id, p_to_id); + + return points[p_from_id]->pos.distance_to(points[p_to_id]->pos); +} + +float AStar::_compute_cost(int p_from_id, int p_to_id) { + if (get_script_instance() && get_script_instance()->has_method(SceneStringNames::get_singleton()->_compute_cost)) + return get_script_instance()->call(SceneStringNames::get_singleton()->_compute_cost, p_from_id, p_to_id); + + return points[p_from_id]->pos.distance_to(points[p_to_id]->pos); +} + 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>()); @@ -384,7 +401,7 @@ void AStar::_bind_methods() { ClassDB::bind_method(D_METHOD("get_point_weight_scale", "id"), &AStar::get_point_weight_scale); ClassDB::bind_method(D_METHOD("remove_point", "id"), &AStar::remove_point); - ClassDB::bind_method(D_METHOD("connect_points", "id", "to_id"), &AStar::connect_points); + 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); ClassDB::bind_method(D_METHOD("are_points_connected", "id", "to_id"), &AStar::are_points_connected); @@ -395,6 +412,9 @@ void AStar::_bind_methods() { ClassDB::bind_method(D_METHOD("get_point_path", "from_id", "to_id"), &AStar::get_point_path); ClassDB::bind_method(D_METHOD("get_id_path", "from_id", "to_id"), &AStar::get_id_path); + + BIND_VMETHOD(MethodInfo("_estimate_cost", PropertyInfo(Variant::INT, "from_id"), PropertyInfo(Variant::INT, "to_id"))); + BIND_VMETHOD(MethodInfo("_compute_cost", PropertyInfo(Variant::INT, "from_id"), PropertyInfo(Variant::INT, "to_id"))); } AStar::AStar() { diff --git a/core/math/a_star.h b/core/math/a_star.h index 2ac855737c..34a5358344 100644 --- a/core/math/a_star.h +++ b/core/math/a_star.h @@ -6,6 +6,7 @@ /* http://www.godotengine.org */ /*************************************************************************/ /* Copyright (c) 2007-2017 Juan Linietsky, Ariel Manzur. */ +/* Copyright (c) 2014-2017 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 */ @@ -93,6 +94,9 @@ class AStar : public Reference { protected: static void _bind_methods(); + virtual float _estimate_cost(int p_from_id, int p_to_id); + virtual float _compute_cost(int p_from_id, int p_to_id); + public: int get_available_point_id() const; @@ -101,7 +105,7 @@ public: real_t get_point_weight_scale(int p_id) const; void remove_point(int p_id); - void connect_points(int p_id, int p_with_id); + 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; diff --git a/core/math/audio_frame.cpp b/core/math/audio_frame.cpp index e56157ffef..30a50c8add 100644 --- a/core/math/audio_frame.cpp +++ b/core/math/audio_frame.cpp @@ -6,6 +6,7 @@ /* http://www.godotengine.org */ /*************************************************************************/ /* Copyright (c) 2007-2017 Juan Linietsky, Ariel Manzur. */ +/* Copyright (c) 2014-2017 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 dd43f48df4..5ccc9d9e5e 100644 --- a/core/math/audio_frame.h +++ b/core/math/audio_frame.h @@ -6,6 +6,7 @@ /* http://www.godotengine.org */ /*************************************************************************/ /* Copyright (c) 2007-2017 Juan Linietsky, Ariel Manzur. */ +/* Copyright (c) 2014-2017 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.cpp b/core/math/bsp_tree.cpp index ef229a0553..327a6017c3 100644 --- a/core/math/bsp_tree.cpp +++ b/core/math/bsp_tree.cpp @@ -6,6 +6,7 @@ /* http://www.godotengine.org */ /*************************************************************************/ /* Copyright (c) 2007-2017 Juan Linietsky, Ariel Manzur. */ +/* Copyright (c) 2014-2017 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 */ @@ -38,8 +39,8 @@ void BSP_Tree::from_aabb(const Rect3 &p_aabb) { Vector3 n; n[i] = 1; - planes.push_back(Plane(n, p_aabb.pos[i] + p_aabb.size[i])); - planes.push_back(Plane(-n, -p_aabb.pos[i])); + planes.push_back(Plane(n, p_aabb.position[i] + p_aabb.size[i])); + planes.push_back(Plane(-n, -p_aabb.position[i])); } nodes.clear(); @@ -551,7 +552,7 @@ BSP_Tree::BSP_Tree(const PoolVector<Face3> &p_faces, real_t p_error_radius) { if (first) { - aabb.pos = f.vertex[0]; + aabb.position = f.vertex[0]; first = false; } else { diff --git a/core/math/bsp_tree.h b/core/math/bsp_tree.h index 4cfac35a2c..8296e57943 100644 --- a/core/math/bsp_tree.h +++ b/core/math/bsp_tree.h @@ -6,6 +6,7 @@ /* http://www.godotengine.org */ /*************************************************************************/ /* Copyright (c) 2007-2017 Juan Linietsky, Ariel Manzur. */ +/* Copyright (c) 2014-2017 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/camera_matrix.cpp b/core/math/camera_matrix.cpp index 227f586c43..33ad522315 100644 --- a/core/math/camera_matrix.cpp +++ b/core/math/camera_matrix.cpp @@ -6,6 +6,7 @@ /* http://www.godotengine.org */ /*************************************************************************/ /* Copyright (c) 2007-2017 Juan Linietsky, Ariel Manzur. */ +/* Copyright (c) 2014-2017 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 */ @@ -506,8 +507,8 @@ void CameraMatrix::set_light_atlas_rect(const Rect2 &p_rect) { m[9] = 0.0, m[10] = 1.0, m[11] = 0.0, - m[12] = p_rect.pos.x, - m[13] = p_rect.pos.y, + m[12] = p_rect.position.x, + m[13] = p_rect.position.y, m[14] = 0.0, m[15] = 1.0; } @@ -558,8 +559,8 @@ void CameraMatrix::make_scale(const Vector3 &p_scale) { void CameraMatrix::scale_translate_to_fit(const Rect3 &p_aabb) { - Vector3 min = p_aabb.pos; - Vector3 max = p_aabb.pos + p_aabb.size; + Vector3 min = p_aabb.position; + Vector3 max = p_aabb.position + p_aabb.size; matrix[0][0] = 2 / (max.x - min.x); matrix[1][0] = 0; diff --git a/core/math/camera_matrix.h b/core/math/camera_matrix.h index 857628c703..af61e35993 100644 --- a/core/math/camera_matrix.h +++ b/core/math/camera_matrix.h @@ -6,6 +6,7 @@ /* http://www.godotengine.org */ /*************************************************************************/ /* Copyright (c) 2007-2017 Juan Linietsky, Ariel Manzur. */ +/* Copyright (c) 2014-2017 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.cpp b/core/math/face3.cpp index d9d99b0384..5b66e1999a 100644 --- a/core/math/face3.cpp +++ b/core/math/face3.cpp @@ -6,6 +6,7 @@ /* http://www.godotengine.org */ /*************************************************************************/ /* Copyright (c) 2007-2017 Juan Linietsky, Ariel Manzur. */ +/* Copyright (c) 2014-2017 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 */ @@ -136,7 +137,7 @@ Face3::Side Face3::get_side_of(const Face3 &p_face, ClockDirection p_clock_dir) const Vector3 &v = p_face.vertex[i]; - if (plane.has_point(v)) //coplanar, dont bother + if (plane.has_point(v)) //coplanar, don't bother continue; if (plane.is_point_over(v)) @@ -196,20 +197,20 @@ bool Face3::intersects_aabb(const Rect3 &p_aabb) const { /** TEST FACE AXIS */ -#define TEST_AXIS(m_ax) \ - { \ - real_t aabb_min = p_aabb.pos.m_ax; \ - real_t aabb_max = p_aabb.pos.m_ax + p_aabb.size.m_ax; \ - real_t tri_min, tri_max; \ - for (int i = 0; i < 3; i++) { \ - if (i == 0 || vertex[i].m_ax > tri_max) \ - tri_max = vertex[i].m_ax; \ - if (i == 0 || vertex[i].m_ax < tri_min) \ - tri_min = vertex[i].m_ax; \ - } \ - \ - if (tri_max < aabb_min || aabb_max < tri_min) \ - return false; \ +#define TEST_AXIS(m_ax) \ + { \ + real_t aabb_min = p_aabb.position.m_ax; \ + real_t aabb_max = p_aabb.position.m_ax + p_aabb.size.m_ax; \ + real_t tri_min, tri_max; \ + for (int i = 0; i < 3; i++) { \ + if (i == 0 || vertex[i].m_ax > tri_max) \ + tri_max = vertex[i].m_ax; \ + if (i == 0 || vertex[i].m_ax < tri_min) \ + tri_min = vertex[i].m_ax; \ + } \ + \ + if (tri_max < aabb_min || aabb_max < tri_min) \ + return false; \ } TEST_AXIS(x); diff --git a/core/math/face3.h b/core/math/face3.h index 6d15c60e3b..1cc94321c3 100644 --- a/core/math/face3.h +++ b/core/math/face3.h @@ -6,6 +6,7 @@ /* http://www.godotengine.org */ /*************************************************************************/ /* Copyright (c) 2007-2017 Juan Linietsky, Ariel Manzur. */ +/* Copyright (c) 2014-2017 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 */ @@ -100,7 +101,7 @@ bool Face3::intersects_aabb2(const Rect3 &p_aabb) const { Vector3 perp = (vertex[0] - vertex[2]).cross(vertex[0] - vertex[1]); Vector3 half_extents = p_aabb.size * 0.5; - Vector3 ofs = p_aabb.pos + half_extents; + Vector3 ofs = p_aabb.position + half_extents; Vector3 sup = Vector3( (perp.x > 0) ? -half_extents.x : half_extents.x, @@ -116,8 +117,8 @@ bool Face3::intersects_aabb2(const Rect3 &p_aabb) const { #define TEST_AXIS(m_ax) \ { \ - real_t aabb_min = p_aabb.pos.m_ax; \ - real_t aabb_max = p_aabb.pos.m_ax + p_aabb.size.m_ax; \ + real_t aabb_min = p_aabb.position.m_ax; \ + real_t aabb_max = p_aabb.position.m_ax + p_aabb.size.m_ax; \ real_t tri_min, tri_max; \ for (int i = 0; i < 3; i++) { \ if (i == 0 || vertex[i].m_ax > tri_max) \ @@ -149,68 +150,68 @@ bool Face3::intersects_aabb2(const Rect3 &p_aabb) const { case 0: { - from = Vector3(p_aabb.pos.x + p_aabb.size.x, p_aabb.pos.y, p_aabb.pos.z); - to = Vector3(p_aabb.pos.x, p_aabb.pos.y, p_aabb.pos.z); + from = Vector3(p_aabb.position.x + p_aabb.size.x, p_aabb.position.y, p_aabb.position.z); + to = Vector3(p_aabb.position.x, p_aabb.position.y, p_aabb.position.z); } break; case 1: { - from = Vector3(p_aabb.pos.x + p_aabb.size.x, p_aabb.pos.y, p_aabb.pos.z + p_aabb.size.z); - to = Vector3(p_aabb.pos.x + p_aabb.size.x, p_aabb.pos.y, p_aabb.pos.z); + from = Vector3(p_aabb.position.x + p_aabb.size.x, p_aabb.position.y, p_aabb.position.z + p_aabb.size.z); + to = Vector3(p_aabb.position.x + p_aabb.size.x, p_aabb.position.y, p_aabb.position.z); } break; case 2: { - from = Vector3(p_aabb.pos.x, p_aabb.pos.y, p_aabb.pos.z + p_aabb.size.z); - to = Vector3(p_aabb.pos.x + p_aabb.size.x, p_aabb.pos.y, p_aabb.pos.z + p_aabb.size.z); + from = Vector3(p_aabb.position.x, p_aabb.position.y, p_aabb.position.z + p_aabb.size.z); + to = Vector3(p_aabb.position.x + p_aabb.size.x, p_aabb.position.y, p_aabb.position.z + p_aabb.size.z); } break; case 3: { - from = Vector3(p_aabb.pos.x, p_aabb.pos.y, p_aabb.pos.z); - to = Vector3(p_aabb.pos.x, p_aabb.pos.y, p_aabb.pos.z + p_aabb.size.z); + from = Vector3(p_aabb.position.x, p_aabb.position.y, p_aabb.position.z); + to = Vector3(p_aabb.position.x, p_aabb.position.y, p_aabb.position.z + p_aabb.size.z); } break; case 4: { - from = Vector3(p_aabb.pos.x, p_aabb.pos.y + p_aabb.size.y, p_aabb.pos.z); - to = Vector3(p_aabb.pos.x + p_aabb.size.x, p_aabb.pos.y + p_aabb.size.y, p_aabb.pos.z); + from = Vector3(p_aabb.position.x, p_aabb.position.y + p_aabb.size.y, p_aabb.position.z); + to = Vector3(p_aabb.position.x + p_aabb.size.x, p_aabb.position.y + p_aabb.size.y, p_aabb.position.z); } break; case 5: { - from = Vector3(p_aabb.pos.x + p_aabb.size.x, p_aabb.pos.y + p_aabb.size.y, p_aabb.pos.z); - to = Vector3(p_aabb.pos.x + p_aabb.size.x, p_aabb.pos.y + p_aabb.size.y, p_aabb.pos.z + p_aabb.size.z); + from = Vector3(p_aabb.position.x + p_aabb.size.x, p_aabb.position.y + p_aabb.size.y, p_aabb.position.z); + to = Vector3(p_aabb.position.x + p_aabb.size.x, p_aabb.position.y + p_aabb.size.y, p_aabb.position.z + p_aabb.size.z); } break; case 6: { - from = Vector3(p_aabb.pos.x + p_aabb.size.x, p_aabb.pos.y + p_aabb.size.y, p_aabb.pos.z + p_aabb.size.z); - to = Vector3(p_aabb.pos.x, p_aabb.pos.y + p_aabb.size.y, p_aabb.pos.z + p_aabb.size.z); + from = Vector3(p_aabb.position.x + p_aabb.size.x, p_aabb.position.y + p_aabb.size.y, p_aabb.position.z + p_aabb.size.z); + to = Vector3(p_aabb.position.x, p_aabb.position.y + p_aabb.size.y, p_aabb.position.z + p_aabb.size.z); } break; case 7: { - from = Vector3(p_aabb.pos.x, p_aabb.pos.y + p_aabb.size.y, p_aabb.pos.z + p_aabb.size.z); - to = Vector3(p_aabb.pos.x, p_aabb.pos.y + p_aabb.size.y, p_aabb.pos.z); + from = Vector3(p_aabb.position.x, p_aabb.position.y + p_aabb.size.y, p_aabb.position.z + p_aabb.size.z); + to = Vector3(p_aabb.position.x, p_aabb.position.y + p_aabb.size.y, p_aabb.position.z); } break; case 8: { - from = Vector3(p_aabb.pos.x, p_aabb.pos.y, p_aabb.pos.z + p_aabb.size.z); - to = Vector3(p_aabb.pos.x, p_aabb.pos.y + p_aabb.size.y, p_aabb.pos.z + p_aabb.size.z); + from = Vector3(p_aabb.position.x, p_aabb.position.y, p_aabb.position.z + p_aabb.size.z); + to = Vector3(p_aabb.position.x, p_aabb.position.y + p_aabb.size.y, p_aabb.position.z + p_aabb.size.z); } break; case 9: { - from = Vector3(p_aabb.pos.x, p_aabb.pos.y, p_aabb.pos.z); - to = Vector3(p_aabb.pos.x, p_aabb.pos.y + p_aabb.size.y, p_aabb.pos.z); + from = Vector3(p_aabb.position.x, p_aabb.position.y, p_aabb.position.z); + to = Vector3(p_aabb.position.x, p_aabb.position.y + p_aabb.size.y, p_aabb.position.z); } break; case 10: { - from = Vector3(p_aabb.pos.x + p_aabb.size.x, p_aabb.pos.y, p_aabb.pos.z); - to = Vector3(p_aabb.pos.x + p_aabb.size.x, p_aabb.pos.y + p_aabb.size.y, p_aabb.pos.z); + from = Vector3(p_aabb.position.x + p_aabb.size.x, p_aabb.position.y, p_aabb.position.z); + to = Vector3(p_aabb.position.x + p_aabb.size.x, p_aabb.position.y + p_aabb.size.y, p_aabb.position.z); } break; case 11: { - from = Vector3(p_aabb.pos.x + p_aabb.size.x, p_aabb.pos.y, p_aabb.pos.z + p_aabb.size.z); - to = Vector3(p_aabb.pos.x + p_aabb.size.x, p_aabb.pos.y + p_aabb.size.y, p_aabb.pos.z + p_aabb.size.z); + from = Vector3(p_aabb.position.x + p_aabb.size.x, p_aabb.position.y, p_aabb.position.z + p_aabb.size.z); + to = Vector3(p_aabb.position.x + p_aabb.size.x, p_aabb.position.y + p_aabb.size.y, p_aabb.position.z + p_aabb.size.z); } break; } diff --git a/core/math/geometry.cpp b/core/math/geometry.cpp index ec4d352a8f..2bea514d37 100644 --- a/core/math/geometry.cpp +++ b/core/math/geometry.cpp @@ -6,6 +6,7 @@ /* http://www.godotengine.org */ /*************************************************************************/ /* Copyright (c) 2007-2017 Juan Linietsky, Ariel Manzur. */ +/* Copyright (c) 2014-2017 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 */ @@ -300,7 +301,7 @@ enum _CellFlags { static inline void _plot_face(uint8_t ***p_cell_status, int x, int y, int z, int len_x, int len_y, int len_z, const Vector3 &voxelsize, const Face3 &p_face) { Rect3 aabb(Vector3(x, y, z), Vector3(len_x, len_y, len_z)); - aabb.pos = aabb.pos * voxelsize; + aabb.position = aabb.position * voxelsize; aabb.size = aabb.size * voxelsize; if (!p_face.intersects_aabb(aabb)) @@ -639,7 +640,7 @@ PoolVector<Face3> Geometry::wrap_geometry(PoolVector<Face3> p_array, real_t *p_e Face3 f = faces[i]; for (int j = 0; j < 3; j++) { - f.vertex[j] -= global_aabb.pos; + f.vertex[j] -= global_aabb.position; } _plot_face(cell_status, 0, 0, 0, div_x, div_y, div_z, voxelsize, f); } @@ -706,7 +707,7 @@ PoolVector<Face3> Geometry::wrap_geometry(PoolVector<Face3> p_array, real_t *p_e Vector3 &v = wrapped_faces_ptr[i].vertex[j]; v = v * voxelsize; - v += global_aabb.pos; + v += global_aabb.position; } } @@ -990,7 +991,7 @@ void Geometry::make_atlas(const Vector<Size2i> &p_rects, Vector<Point2i> &r_resu //super simple, almost brute force scanline stacking fitter //it's pretty basic for now, but it tries to make sure that the aspect ratio of the - //resulting atlas is somehow square. This is necesary because video cards have limits + //resulting atlas is somehow square. This is necessary because video cards have limits //on texture size (usually 2048 or 4096), so the more square a texture, the more chances //it will work in every hardware. // for example, it will prioritize a 1024x1024 atlas (works everywhere) instead of a @@ -1057,7 +1058,7 @@ void Geometry::make_atlas(const Vector<Size2i> &p_rects, Vector<Point2i> &r_resu if (end_w > max_w) max_w = end_w; - if (ofs == 0 || end_h > limit_h) //while h limit not reched, keep stacking + if (ofs == 0 || end_h > limit_h) //while h limit not reached, keep stacking ofs += wrects[j].s.width; } diff --git a/core/math/geometry.h b/core/math/geometry.h index 93ab0be2e0..909d8164c3 100644 --- a/core/math/geometry.h +++ b/core/math/geometry.h @@ -6,6 +6,7 @@ /* http://www.godotengine.org */ /*************************************************************************/ /* Copyright (c) 2007-2017 Juan Linietsky, Ariel Manzur. */ +/* Copyright (c) 2014-2017 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 */ @@ -104,23 +105,23 @@ public: } static void get_closest_points_between_segments(const Vector3 &p1, const Vector3 &p2, const Vector3 &q1, const Vector3 &q2, Vector3 &c1, Vector3 &c2) { -#if 0 - //do the function 'd' as defined by pb. I think is is dot product of some sort +#if 1 +//do the function 'd' as defined by pb. I think is is dot product of some sort #define d_of(m, n, o, p) ((m.x - n.x) * (o.x - p.x) + (m.y - n.y) * (o.y - p.y) + (m.z - n.z) * (o.z - p.z)) - //caluclate the parpametric position on the 2 curves, mua and mub - real_t mua = ( d_of(p1,q1,q2,q1) * d_of(q2,q1,p2,p1) - d_of(p1,q1,p2,p1) * d_of(q2,q1,q2,q1) ) / ( d_of(p2,p1,p2,p1) * d_of(q2,q1,q2,q1) - d_of(q2,q1,p2,p1) * d_of(q2,q1,p2,p1) ); - real_t mub = ( d_of(p1,q1,q2,q1) + mua * d_of(q2,q1,p2,p1) ) / d_of(q2,q1,q2,q1); + //calculate the parametric position on the 2 curves, mua and mub + real_t mua = (d_of(p1, q1, q2, q1) * d_of(q2, q1, p2, p1) - d_of(p1, q1, p2, p1) * d_of(q2, q1, q2, q1)) / (d_of(p2, p1, p2, p1) * d_of(q2, q1, q2, q1) - d_of(q2, q1, p2, p1) * d_of(q2, q1, p2, p1)); + real_t mub = (d_of(p1, q1, q2, q1) + mua * d_of(q2, q1, p2, p1)) / d_of(q2, q1, q2, q1); //clip the value between [0..1] constraining the solution to lie on the original curves if (mua < 0) mua = 0; if (mub < 0) mub = 0; if (mua > 1) mua = 1; if (mub > 1) mub = 1; - c1 = p1.linear_interpolate(p2,mua); - c2 = q1.linear_interpolate(q2,mub); -#endif - + c1 = p1.linear_interpolate(p2, mua); + c2 = q1.linear_interpolate(q2, mub); +#else + //this is broken do not use Vector3 u = p2 - p1; Vector3 v = q2 - q1; Vector3 w = p1 - q1; @@ -143,8 +144,9 @@ public: c1 = w + sc * u; c2 = w + tc * v; - // get the difference of the two closest points - //Vector dP = w + (sc * u) - (tc * v); // = L1(sc) - L2(tc) +// get the difference of the two closest points +//Vector dP = w + (sc * u) - (tc * v); // = L1(sc) - L2(tc) +#endif } static real_t get_closest_distance_between_segments(const Vector3 &p_from_a, const Vector3 &p_to_a, const Vector3 &p_from_b, const Vector3 &p_to_b) { diff --git a/core/math/math_2d.cpp b/core/math/math_2d.cpp index 021b1fbf55..52e240ed47 100644 --- a/core/math/math_2d.cpp +++ b/core/math/math_2d.cpp @@ -6,6 +6,7 @@ /* http://www.godotengine.org */ /*************************************************************************/ /* Copyright (c) 2007-2017 Juan Linietsky, Ariel Manzur. */ +/* Copyright (c) 2014-2017 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 +62,11 @@ Vector2 Vector2::normalized() const { return v; } +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); +} + real_t Vector2::distance_to(const Vector2 &p_vector2) const { return Math::sqrt((x - p_vector2.x) * (x - p_vector2.x) + (y - p_vector2.y) * (y - p_vector2.y)); @@ -274,13 +280,23 @@ Vector2 Vector2::cubic_interpolate(const Vector2 &p_b, const Vector2 &p_pre_a, c */ } -Vector2 Vector2::slide(const Vector2 &p_vec) const { +// slide returns the component of the vector along the given plane, specified by its normal vector. +Vector2 Vector2::slide(const Vector2 &p_n) const { +#ifdef MATH_CHECKS + ERR_FAIL_COND_V(p_n.is_normalized() == false, Vector2()); +#endif + return *this - p_n * this->dot(p_n); +} - return p_vec - *this * this->dot(p_vec); +Vector2 Vector2::bounce(const Vector2 &p_n) const { + return -reflect(p_n); } -Vector2 Vector2::reflect(const Vector2 &p_vec) const { - return p_vec - *this * this->dot(p_vec) * 2.0; +Vector2 Vector2::reflect(const Vector2 &p_n) const { +#ifdef MATH_CHECKS + ERR_FAIL_COND_V(p_n.is_normalized() == false, Vector2()); +#endif + return 2.0 * p_n * this->dot(p_n) - *this; } bool Rect2::intersects_segment(const Point2 &p_from, const Point2 &p_to, Point2 *r_pos, Point2 *r_normal) const { @@ -292,7 +308,7 @@ bool Rect2::intersects_segment(const Point2 &p_from, const Point2 &p_to, Point2 for (int i = 0; i < 2; i++) { real_t seg_from = p_from[i]; real_t seg_to = p_to[i]; - real_t box_begin = pos[i]; + real_t box_begin = position[i]; real_t box_end = box_begin + size[i]; real_t cmin, cmax; real_t csign; @@ -424,7 +440,9 @@ Transform2D Transform2D::inverse() const { void Transform2D::affine_invert() { real_t det = basis_determinant(); +#ifdef MATH_CHECKS ERR_FAIL_COND(det == 0); +#endif real_t idet = 1.0 / det; SWAP(elements[0][0], elements[1][1]); @@ -449,7 +467,7 @@ real_t Transform2D::get_rotation() const { real_t det = basis_determinant(); Transform2D m = orthonormalized(); if (det < 0) { - m.scale_basis(Size2(-1, -1)); + m.scale_basis(Size2(1, -1)); // convention to separate rotation and reflection for 2D is to absorb a flip along y into scaling. } return Math::atan2(m[0].y, m[0].x); } @@ -477,7 +495,7 @@ Transform2D::Transform2D(real_t p_rot, const Vector2 &p_pos) { Size2 Transform2D::get_scale() const { real_t det_sign = basis_determinant() > 0 ? 1 : -1; - return det_sign * Size2(elements[0].length(), elements[1].length()); + return Size2(elements[0].length(), det_sign * elements[1].length()); } void Transform2D::scale(const Size2 &p_scale) { diff --git a/core/math/math_2d.h b/core/math/math_2d.h index af6437d7f1..780bb532d7 100644 --- a/core/math/math_2d.h +++ b/core/math/math_2d.h @@ -6,6 +6,7 @@ /* http://www.godotengine.org */ /*************************************************************************/ /* Copyright (c) 2007-2017 Juan Linietsky, Ariel Manzur. */ +/* Copyright (c) 2014-2017 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 */ @@ -82,6 +83,7 @@ struct Vector2 { void normalize(); Vector2 normalized() const; + bool is_normalized() const; real_t length() const; real_t length_squared() const; @@ -106,6 +108,7 @@ struct Vector2 { Vector2 cubic_interpolate_soft(const Vector2 &p_b, const Vector2 &p_pre_a, const Vector2 &p_post_b, real_t p_t) const; Vector2 slide(const Vector2 &p_vec) const; + Vector2 bounce(const Vector2 &p_vec) const; Vector2 reflect(const Vector2 &p_vec) const; Vector2 operator+(const Vector2 &p_v) const; @@ -204,24 +207,24 @@ struct Transform2D; struct Rect2 { - Point2 pos; + Point2 position; Size2 size; - const Vector2 &get_pos() const { return pos; } - void set_pos(const Vector2 &p_pos) { pos = p_pos; } + const Vector2 &get_position() const { return position; } + void set_position(const Vector2 &p_pos) { position = p_pos; } const Vector2 &get_size() const { return size; } void set_size(const Vector2 &p_size) { size = p_size; } real_t get_area() const { return size.width * size.height; } inline bool intersects(const Rect2 &p_rect) const { - if (pos.x >= (p_rect.pos.x + p_rect.size.width)) + if (position.x >= (p_rect.position.x + p_rect.size.width)) return false; - if ((pos.x + size.width) <= p_rect.pos.x) + if ((position.x + size.width) <= p_rect.position.x) return false; - if (pos.y >= (p_rect.pos.y + p_rect.size.height)) + if (position.y >= (p_rect.position.y + p_rect.size.height)) return false; - if ((pos.y + size.height) <= p_rect.pos.y) + if ((position.y + size.height) <= p_rect.position.y) return false; return true; @@ -231,17 +234,17 @@ struct Rect2 { real_t dist = 1e20; - if (p_point.x < pos.x) { - dist = MIN(dist, pos.x - p_point.x); + if (p_point.x < position.x) { + dist = MIN(dist, position.x - p_point.x); } - if (p_point.y < pos.y) { - dist = MIN(dist, pos.y - p_point.y); + if (p_point.y < position.y) { + dist = MIN(dist, position.y - p_point.y); } - if (p_point.x >= (pos.x + size.x)) { - dist = MIN(p_point.x - (pos.x + size.x), dist); + if (p_point.x >= (position.x + size.x)) { + dist = MIN(p_point.x - (position.x + size.x), dist); } - if (p_point.y >= (pos.y + size.y)) { - dist = MIN(p_point.y - (pos.y + size.y), dist); + if (p_point.y >= (position.y + size.y)) { + dist = MIN(p_point.y - (position.y + size.y), dist); } if (dist == 1e20) @@ -256,9 +259,9 @@ struct Rect2 { inline bool encloses(const Rect2 &p_rect) const { - return (p_rect.pos.x >= pos.x) && (p_rect.pos.y >= pos.y) && - ((p_rect.pos.x + p_rect.size.x) < (pos.x + size.x)) && - ((p_rect.pos.y + p_rect.size.y) < (pos.y + size.y)); + return (p_rect.position.x >= position.x) && (p_rect.position.y >= position.y) && + ((p_rect.position.x + p_rect.size.x) < (position.x + size.x)) && + ((p_rect.position.y + p_rect.size.y) < (position.y + size.y)); } inline bool has_no_area() const { @@ -272,14 +275,14 @@ struct Rect2 { if (!intersects(new_rect)) return Rect2(); - new_rect.pos.x = MAX(p_rect.pos.x, pos.x); - new_rect.pos.y = MAX(p_rect.pos.y, pos.y); + new_rect.position.x = MAX(p_rect.position.x, position.x); + new_rect.position.y = MAX(p_rect.position.y, position.y); - Point2 p_rect_end = p_rect.pos + p_rect.size; - Point2 end = pos + size; + Point2 p_rect_end = p_rect.position + p_rect.size; + Point2 end = position + size; - new_rect.size.x = MIN(p_rect_end.x, end.x) - new_rect.pos.x; - new_rect.size.y = MIN(p_rect_end.y, end.y) - new_rect.pos.y; + new_rect.size.x = MIN(p_rect_end.x, end.x) - new_rect.position.x; + new_rect.size.y = MIN(p_rect_end.y, end.y) - new_rect.position.y; return new_rect; } @@ -288,25 +291,25 @@ struct Rect2 { Rect2 new_rect; - new_rect.pos.x = MIN(p_rect.pos.x, pos.x); - new_rect.pos.y = MIN(p_rect.pos.y, pos.y); + new_rect.position.x = MIN(p_rect.position.x, position.x); + new_rect.position.y = MIN(p_rect.position.y, position.y); - new_rect.size.x = MAX(p_rect.pos.x + p_rect.size.x, pos.x + size.x); - new_rect.size.y = MAX(p_rect.pos.y + p_rect.size.y, pos.y + size.y); + new_rect.size.x = MAX(p_rect.position.x + p_rect.size.x, position.x + size.x); + new_rect.size.y = MAX(p_rect.position.y + p_rect.size.y, position.y + size.y); - new_rect.size = new_rect.size - new_rect.pos; //make relative again + new_rect.size = new_rect.size - new_rect.position; //make relative again return new_rect; }; inline bool has_point(const Point2 &p_point) const { - if (p_point.x < pos.x) + if (p_point.x < position.x) return false; - if (p_point.y < pos.y) + if (p_point.y < position.y) return false; - if (p_point.x >= (pos.x + size.x)) + if (p_point.x >= (position.x + size.x)) return false; - if (p_point.y >= (pos.y + size.y)) + if (p_point.y >= (position.y + size.y)) return false; return true; @@ -314,18 +317,37 @@ struct Rect2 { inline bool no_area() const { return (size.width <= 0 || size.height <= 0); } - bool operator==(const Rect2 &p_rect) const { return pos == p_rect.pos && size == p_rect.size; } - bool operator!=(const Rect2 &p_rect) const { return pos != p_rect.pos || size != p_rect.size; } + 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; } inline Rect2 grow(real_t p_by) const { Rect2 g = *this; - g.pos.x -= p_by; - g.pos.y -= p_by; + g.position.x -= p_by; + g.position.y -= p_by; g.size.width += p_by * 2; g.size.height += p_by * 2; return g; } + inline Rect2 grow_margin(Margin p_margin, real_t p_amount) const { + Rect2 g = *this; + 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 Rect2 grow_individual(real_t p_left, real_t p_top, real_t p_right, real_t p_bottom) const { + + Rect2 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; + } inline Rect2 expand(const Vector2 &p_vector) const { @@ -336,8 +358,8 @@ struct Rect2 { inline void expand_to(const Vector2 &p_vector) { //in place function for speed - Vector2 begin = pos; - Vector2 end = pos + size; + Vector2 begin = position; + Vector2 end = position + size; if (p_vector.x < begin.x) begin.x = p_vector.x; @@ -349,19 +371,19 @@ struct Rect2 { if (p_vector.y > end.y) end.y = p_vector.y; - pos = begin; + position = begin; size = end - begin; } - operator String() const { return String(pos) + ", " + String(size); } + operator String() const { return String(position) + ", " + String(size); } Rect2() {} Rect2(real_t p_x, real_t p_y, real_t p_width, real_t p_height) { - pos = Point2(p_x, p_y); + position = Point2(p_x, p_y); size = Size2(p_width, p_height); } Rect2(const Point2 &p_pos, const Size2 &p_size) { - pos = p_pos; + position = p_pos; size = p_size; } }; @@ -431,24 +453,24 @@ typedef Point2i Size2i; struct Rect2i { - Point2i pos; + Point2i position; Size2i size; - const Point2i &get_pos() const { return pos; } - void set_pos(const Point2i &p_pos) { pos = p_pos; } + const Point2i &get_position() const { return position; } + void set_position(const Point2i &p_pos) { position = p_pos; } const Point2i &get_size() const { return size; } void set_size(const Point2i &p_size) { size = p_size; } int get_area() const { return size.width * size.height; } inline bool intersects(const Rect2i &p_rect) const { - if (pos.x > (p_rect.pos.x + p_rect.size.width)) + if (position.x > (p_rect.position.x + p_rect.size.width)) return false; - if ((pos.x + size.width) < p_rect.pos.x) + if ((position.x + size.width) < p_rect.position.x) return false; - if (pos.y > (p_rect.pos.y + p_rect.size.height)) + if (position.y > (p_rect.position.y + p_rect.size.height)) return false; - if ((pos.y + size.height) < p_rect.pos.y) + if ((position.y + size.height) < p_rect.position.y) return false; return true; @@ -456,9 +478,9 @@ struct Rect2i { inline bool encloses(const Rect2i &p_rect) const { - return (p_rect.pos.x >= pos.x) && (p_rect.pos.y >= pos.y) && - ((p_rect.pos.x + p_rect.size.x) < (pos.x + size.x)) && - ((p_rect.pos.y + p_rect.size.y) < (pos.y + size.y)); + return (p_rect.position.x >= position.x) && (p_rect.position.y >= position.y) && + ((p_rect.position.x + p_rect.size.x) < (position.x + size.x)) && + ((p_rect.position.y + p_rect.size.y) < (position.y + size.y)); } inline bool has_no_area() const { @@ -472,14 +494,14 @@ struct Rect2i { if (!intersects(new_rect)) return Rect2i(); - new_rect.pos.x = MAX(p_rect.pos.x, pos.x); - new_rect.pos.y = MAX(p_rect.pos.y, pos.y); + new_rect.position.x = MAX(p_rect.position.x, position.x); + new_rect.position.y = MAX(p_rect.position.y, position.y); - Point2 p_rect_end = p_rect.pos + p_rect.size; - Point2 end = pos + size; + Point2 p_rect_end = p_rect.position + p_rect.size; + Point2 end = position + size; - new_rect.size.x = (int)(MIN(p_rect_end.x, end.x) - new_rect.pos.x); - new_rect.size.y = (int)(MIN(p_rect_end.y, end.y) - new_rect.pos.y); + new_rect.size.x = (int)(MIN(p_rect_end.x, end.x) - new_rect.position.x); + new_rect.size.y = (int)(MIN(p_rect_end.y, end.y) - new_rect.position.y); return new_rect; } @@ -488,25 +510,25 @@ struct Rect2i { Rect2i new_rect; - new_rect.pos.x = MIN(p_rect.pos.x, pos.x); - new_rect.pos.y = MIN(p_rect.pos.y, pos.y); + new_rect.position.x = MIN(p_rect.position.x, position.x); + new_rect.position.y = MIN(p_rect.position.y, position.y); - new_rect.size.x = MAX(p_rect.pos.x + p_rect.size.x, pos.x + size.x); - new_rect.size.y = MAX(p_rect.pos.y + p_rect.size.y, pos.y + size.y); + new_rect.size.x = MAX(p_rect.position.x + p_rect.size.x, position.x + size.x); + new_rect.size.y = MAX(p_rect.position.y + p_rect.size.y, position.y + size.y); - new_rect.size = new_rect.size - new_rect.pos; //make relative again + new_rect.size = new_rect.size - new_rect.position; //make relative again return new_rect; }; bool has_point(const Point2 &p_point) const { - if (p_point.x < pos.x) + if (p_point.x < position.x) return false; - if (p_point.y < pos.y) + if (p_point.y < position.y) return false; - if (p_point.x >= (pos.x + size.x)) + if (p_point.x >= (position.x + size.x)) return false; - if (p_point.y >= (pos.y + size.y)) + if (p_point.y >= (position.y + size.y)) return false; return true; @@ -514,14 +536,14 @@ struct Rect2i { bool no_area() { return (size.width <= 0 || size.height <= 0); } - bool operator==(const Rect2i &p_rect) const { return pos == p_rect.pos && size == p_rect.size; } - bool operator!=(const Rect2i &p_rect) const { return pos != p_rect.pos || size != p_rect.size; } + 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; } Rect2i grow(int p_by) const { Rect2i g = *this; - g.pos.x -= p_by; - g.pos.y -= p_by; + g.position.x -= p_by; + g.position.y -= p_by; g.size.width += p_by * 2; g.size.height += p_by * 2; return g; @@ -529,8 +551,8 @@ struct Rect2i { inline void expand_to(const Point2i &p_vector) { - Point2i begin = pos; - Point2i end = pos + size; + Point2i begin = position; + Point2i end = position + size; if (p_vector.x < begin.x) begin.x = p_vector.x; @@ -542,24 +564,24 @@ struct Rect2i { if (p_vector.y > end.y) end.y = p_vector.y; - pos = begin; + position = begin; size = end - begin; } - operator String() const { return String(pos) + ", " + String(size); } + operator String() const { return String(position) + ", " + String(size); } - operator Rect2() const { return Rect2(pos, size); } + operator Rect2() const { return Rect2(position, size); } Rect2i(const Rect2 &p_r2) { - pos = p_r2.pos; + position = p_r2.position; size = p_r2.size; } Rect2i() {} Rect2i(int p_x, int p_y, int p_width, int p_height) { - pos = Point2(p_x, p_y); + position = Point2(p_x, p_y); size = Size2(p_width, p_height); } Rect2i(const Point2 &p_pos, const Size2 &p_size) { - pos = p_pos; + position = p_pos; size = p_size; } }; @@ -665,30 +687,30 @@ bool Rect2::intersects_transformed(const Transform2D &p_xform, const Rect2 &p_re //SAT intersection between local and transformed rect2 Vector2 xf_points[4] = { - p_xform.xform(p_rect.pos), - p_xform.xform(Vector2(p_rect.pos.x + p_rect.size.x, p_rect.pos.y)), - p_xform.xform(Vector2(p_rect.pos.x, p_rect.pos.y + p_rect.size.y)), - p_xform.xform(Vector2(p_rect.pos.x + p_rect.size.x, p_rect.pos.y + p_rect.size.y)), + p_xform.xform(p_rect.position), + p_xform.xform(Vector2(p_rect.position.x + p_rect.size.x, p_rect.position.y)), + p_xform.xform(Vector2(p_rect.position.x, p_rect.position.y + p_rect.size.y)), + p_xform.xform(Vector2(p_rect.position.x + p_rect.size.x, p_rect.position.y + p_rect.size.y)), }; real_t low_limit; //base rect2 first (faster) - if (xf_points[0].y > pos.y) + if (xf_points[0].y > position.y) goto next1; - if (xf_points[1].y > pos.y) + if (xf_points[1].y > position.y) goto next1; - if (xf_points[2].y > pos.y) + if (xf_points[2].y > position.y) goto next1; - if (xf_points[3].y > pos.y) + if (xf_points[3].y > position.y) goto next1; return false; next1: - low_limit = pos.y + size.y; + low_limit = position.y + size.y; if (xf_points[0].y < low_limit) goto next2; @@ -703,20 +725,20 @@ next1: next2: - if (xf_points[0].x > pos.x) + if (xf_points[0].x > position.x) goto next3; - if (xf_points[1].x > pos.x) + if (xf_points[1].x > position.x) goto next3; - if (xf_points[2].x > pos.x) + if (xf_points[2].x > position.x) goto next3; - if (xf_points[3].x > pos.x) + if (xf_points[3].x > position.x) goto next3; return false; next3: - low_limit = pos.x + size.x; + low_limit = position.x + size.x; if (xf_points[0].x < low_limit) goto next4; @@ -732,10 +754,10 @@ next3: next4: Vector2 xf_points2[4] = { - pos, - Vector2(pos.x + size.x, pos.y), - Vector2(pos.x, pos.y + size.y), - Vector2(pos.x + size.x, pos.y + size.y), + position, + Vector2(position.x + size.x, position.y), + Vector2(position.x, position.y + size.y), + Vector2(position.x + size.x, position.y + size.y), }; real_t maxa = p_xform.elements[0].dot(xf_points2[0]); @@ -844,10 +866,10 @@ Rect2 Transform2D::xform(const Rect2 &p_rect) const { Vector2 x = elements[0] * p_rect.size.x; Vector2 y = elements[1] * p_rect.size.y; - Vector2 pos = xform(p_rect.pos); + Vector2 pos = xform(p_rect.position); Rect2 new_rect; - new_rect.pos = pos; + new_rect.position = pos; new_rect.expand_to(pos + x); new_rect.expand_to(pos + y); new_rect.expand_to(pos + x + y); @@ -865,14 +887,14 @@ void Transform2D::set_rotation_and_scale(real_t p_rot, const Size2 &p_scale) { Rect2 Transform2D::xform_inv(const Rect2 &p_rect) const { Vector2 ends[4] = { - xform_inv(p_rect.pos), - xform_inv(Vector2(p_rect.pos.x, p_rect.pos.y + p_rect.size.y)), - xform_inv(Vector2(p_rect.pos.x + p_rect.size.x, p_rect.pos.y + p_rect.size.y)), - xform_inv(Vector2(p_rect.pos.x + p_rect.size.x, p_rect.pos.y)) + xform_inv(p_rect.position), + xform_inv(Vector2(p_rect.position.x, p_rect.position.y + p_rect.size.y)), + xform_inv(Vector2(p_rect.position.x + p_rect.size.x, p_rect.position.y + p_rect.size.y)), + xform_inv(Vector2(p_rect.position.x + p_rect.size.x, p_rect.position.y)) }; Rect2 new_rect; - new_rect.pos = ends[0]; + new_rect.position = ends[0]; new_rect.expand_to(ends[1]); new_rect.expand_to(ends[2]); new_rect.expand_to(ends[3]); diff --git a/core/math/math_defs.h b/core/math/math_defs.h index 08f4e27e64..3d9eb63e11 100644 --- a/core/math/math_defs.h +++ b/core/math/math_defs.h @@ -6,6 +6,7 @@ /* http://www.godotengine.org */ /*************************************************************************/ /* Copyright (c) 2007-2017 Juan Linietsky, Ariel Manzur. */ +/* Copyright (c) 2014-2017 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,6 +35,10 @@ #define CMP_NORMALIZE_TOLERANCE 0.000001 #define CMP_POINT_IN_PLANE_EPSILON 0.00001 +#ifdef DEBUG_ENABLED +#define MATH_CHECKS +#endif + #define USEC_TO_SEC(m_usec) ((m_usec) / 1000000.0) /** * "Real" is a type that will be translated to either floats or fixed depending diff --git a/core/math/math_funcs.cpp b/core/math/math_funcs.cpp index ccc463c114..9f5a9c193a 100644 --- a/core/math/math_funcs.cpp +++ b/core/math/math_funcs.cpp @@ -6,6 +6,7 @@ /* http://www.godotengine.org */ /*************************************************************************/ /* Copyright (c) 2007-2017 Juan Linietsky, Ariel Manzur. */ +/* Copyright (c) 2014-2017 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 */ @@ -29,7 +30,7 @@ #include "math_funcs.h" #include "core/os/os.h" -pcg32_random_t Math::default_pcg = { 1, PCG_DEFAULT_INC_64 }; +pcg32_random_t Math::default_pcg = { 12047754176567800795ULL, PCG_DEFAULT_INC_64 }; #define PHI 0x9e3779b9 @@ -50,9 +51,7 @@ void Math::seed(uint64_t x) { } void Math::randomize() { - - OS::Time time = OS::get_singleton()->get_time(); - seed(OS::get_singleton()->get_ticks_usec() * (time.hour + 1) * (time.min + 1) * (time.sec + 1) * rand()); // TODO: can be simplified. + seed(OS::get_singleton()->get_ticks_usec() * default_pcg.state + PCG_DEFAULT_INC_64); } uint32_t Math::rand() { diff --git a/core/math/math_funcs.h b/core/math/math_funcs.h index 3e02ac0bb8..45509a0808 100644 --- a/core/math/math_funcs.h +++ b/core/math/math_funcs.h @@ -6,6 +6,7 @@ /* http://www.godotengine.org */ /*************************************************************************/ /* Copyright (c) 2007-2017 Juan Linietsky, Ariel Manzur. */ +/* Copyright (c) 2014-2017 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,9 +31,10 @@ #define MATH_FUNCS_H #include "math_defs.h" -#include "pcg.h" #include "typedefs.h" +#include "thirdparty/misc/pcg.h" + #include <float.h> #include <math.h> @@ -49,9 +51,7 @@ class Math { public: Math() {} // useless to instance - enum { - RANDOM_MAX = 4294967295L - }; + static const uint64_t RANDOM_MAX = 4294967295; static _ALWAYS_INLINE_ double sin(double p_x) { return ::sin(p_x); } static _ALWAYS_INLINE_ float sin(float p_x) { return ::sinf(p_x); } @@ -110,6 +110,15 @@ public: static _ALWAYS_INLINE_ bool is_inf(double p_val) { #ifdef _MSC_VER return !_finite(p_val); +// use an inline implementation of isinf as a workaround for problematic libstdc++ versions from gcc 5.x era +#elif defined(__GNUC__) && __GNUC__ < 6 + union { + uint64_t u; + double f; + } ieee754; + ieee754.f = p_val; + return ((unsigned)(ieee754.u >> 32) & 0x7fffffff) == 0x7ff00000 && + ((unsigned)ieee754.u == 0); #else return isinf(p_val); #endif @@ -118,6 +127,14 @@ public: static _ALWAYS_INLINE_ bool is_inf(float p_val) { #ifdef _MSC_VER return !_finite(p_val); +// use an inline implementation of isinf as a workaround for problematic libstdc++ versions from gcc 5.x era +#elif defined(__GNUC__) && __GNUC__ < 6 + union { + uint32_t u; + float f; + } ieee754; + ieee754.f = p_val; + return (ieee754.u & 0x7fffffff) == 0x7f800000; #else return isinf(p_val); #endif @@ -156,7 +173,7 @@ public: static uint32_t larger_prime(uint32_t p_val); - static void seed(uint64_t x = 0); + static void seed(uint64_t x); static void randomize(); static uint32_t rand_from_seed(uint64_t *seed); static uint32_t rand(); @@ -167,7 +184,7 @@ public: 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 isequal_approx(real_t a, real_t b) { + 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. @@ -276,6 +293,10 @@ public: return u.f32; } + static _ALWAYS_INLINE_ float half_to_float(const uint16_t h) { + return halfptr_to_float(&h); + } + static _ALWAYS_INLINE_ uint16_t make_half_float(float f) { union { diff --git a/core/math/matrix3.cpp b/core/math/matrix3.cpp index 5f73d91ef3..c733251c3c 100644 --- a/core/math/matrix3.cpp +++ b/core/math/matrix3.cpp @@ -6,6 +6,7 @@ /* http://www.godotengine.org */ /*************************************************************************/ /* Copyright (c) 2007-2017 Juan Linietsky, Ariel Manzur. */ +/* Copyright (c) 2014-2017 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,8 +62,9 @@ void Basis::invert() { real_t det = elements[0][0] * co[0] + elements[0][1] * co[1] + elements[0][2] * co[2]; - +#ifdef MATH_CHECKS ERR_FAIL_COND(det == 0); +#endif real_t s = 1.0 / det; set(co[0] * s, cofac(0, 2, 2, 1) * s, cofac(0, 1, 1, 2) * s, @@ -71,8 +73,9 @@ void Basis::invert() { } void Basis::orthonormalize() { +#ifdef MATH_CHECKS ERR_FAIL_COND(determinant() == 0); - +#endif // Gram-Schmidt Process Vector3 x = get_axis(0); @@ -101,20 +104,20 @@ bool Basis::is_orthogonal() const { Basis id; Basis m = (*this) * transposed(); - return isequal_approx(id, m); + return is_equal_approx(id, m); } bool Basis::is_rotation() const { - return Math::isequal_approx(determinant(), 1) && is_orthogonal(); + return Math::is_equal_approx(determinant(), 1) && is_orthogonal(); } bool Basis::is_symmetric() const { - if (Math::abs(elements[0][1] - elements[1][0]) > CMP_EPSILON) + if (!Math::is_equal_approx(elements[0][1], elements[1][0])) return false; - if (Math::abs(elements[0][2] - elements[2][0]) > CMP_EPSILON) + if (!Math::is_equal_approx(elements[0][2], elements[2][0])) return false; - if (Math::abs(elements[1][2] - elements[2][1]) > CMP_EPSILON) + if (!Math::is_equal_approx(elements[1][2], elements[2][1])) return false; return true; @@ -122,11 +125,11 @@ bool Basis::is_symmetric() const { Basis Basis::diagonalize() { - //NOTE: only implemented for symmetric matrices - //with the Jacobi iterative method method - +//NOTE: only implemented for symmetric matrices +//with the Jacobi iterative method method +#ifdef MATH_CHECKS ERR_FAIL_COND_V(!is_symmetric(), Basis()); - +#endif const int ite_max = 1024; real_t off_matrix_norm_2 = elements[0][1] * elements[0][1] + elements[0][2] * elements[0][2] + elements[1][2] * elements[1][2]; @@ -159,7 +162,7 @@ Basis Basis::diagonalize() { // Compute the rotation angle real_t angle; - if (Math::abs(elements[j][j] - elements[i][i]) < CMP_EPSILON) { + if (Math::is_equal_approx(elements[j][j], elements[i][i])) { angle = Math_PI / 4; } else { angle = 0.5 * Math::atan(2 * elements[i][j] / (elements[j][j] - elements[i][i])); @@ -225,11 +228,25 @@ Basis Basis::scaled(const Vector3 &p_scale) const { } Vector3 Basis::get_scale() const { - // We are assuming M = R.S, and performing a polar decomposition to extract R and S. - // FIXME: We eventually need a proper polar decomposition. - // As a cheap workaround until then, to ensure that R is a proper rotation matrix with determinant +1 - // (such that it can be represented by a Quat or Euler angles), we absorb the sign flip into the scaling matrix. - // As such, it works in conjuction with get_rotation(). + // FIXME: We are assuming M = R.S (R is rotation and S is scaling), and use polar decomposition to extract R and S. + // A polar decomposition is M = O.P, where O is an orthogonal matrix (meaning rotation and reflection) and + // P is a positive semi-definite matrix (meaning it contains absolute values of scaling along its diagonal). + // + // Despite being different from what we want to achieve, we can nevertheless make use of polar decomposition + // here as follows. We can split O into a rotation and a reflection as O = R.Q, and obtain M = R.S where + // we defined S = Q.P. Now, R is a proper rotation matrix and S is a (signed) scaling matrix, + // which can involve negative scalings. However, there is a catch: unlike the polar decomposition of M = O.P, + // the decomposition of O into a rotation and reflection matrix as O = R.Q is not unique. + // Therefore, we are going to do this decomposition by sticking to a particular convention. + // This may lead to confusion for some users though. + // + // The convention we use here is to absorb the sign flip into the scaling matrix. + // The same convention is also used in other similar functions such as set_scale, + // get_rotation_axis_angle, get_rotation, set_rotation_axis_angle, set_rotation_euler, ... + // + // A proper way to get rid of this issue would be to store the scaling values (or at least their signs) + // as a part of Basis. However, if we go that path, we need to disable direct (write) access to the + // matrix elements. real_t det_sign = determinant() > 0 ? 1 : -1; return det_sign * Vector3( Vector3(elements[0][0], elements[1][0], elements[2][0]).length(), @@ -237,6 +254,17 @@ Vector3 Basis::get_scale() const { Vector3(elements[0][2], elements[1][2], elements[2][2]).length()); } +// Sets scaling while preserving rotation. +// This requires some care when working with matrices with negative determinant, +// since we're using a particular convention for "polar" decomposition in get_scale and get_rotation. +// For details, see the explanation in get_scale. +void Basis::set_scale(const Vector3 &p_scale) { + Vector3 e = get_euler(); + Basis(); // reset to identity + scale(p_scale); + rotate(e); +} + // Multiplies the matrix from left by the rotation matrix: M -> R.M // Note that this does *not* rotate the matrix itself. // @@ -259,6 +287,7 @@ void Basis::rotate(const Vector3 &p_euler) { *this = rotated(p_euler); } +// TODO: rename this to get_rotation_euler Vector3 Basis::get_rotation() const { // Assumes that the matrix can be decomposed into a proper rotation and scaling matrix as M = R.S, // and returns the Euler angles corresponding to the rotation part, complementing get_scale(). @@ -273,6 +302,42 @@ Vector3 Basis::get_rotation() const { return m.get_euler(); } +void Basis::get_rotation_axis_angle(Vector3 &p_axis, real_t &p_angle) const { + // Assumes that the matrix can be decomposed into a proper rotation and scaling matrix as M = R.S, + // and returns the Euler angles corresponding to the rotation part, complementing get_scale(). + // See the comment in get_scale() for further information. + Basis m = orthonormalized(); + real_t det = m.determinant(); + if (det < 0) { + // Ensure that the determinant is 1, such that result is a proper rotation matrix which can be represented by Euler angles. + m.scale(Vector3(-1, -1, -1)); + } + + m.get_axis_angle(p_axis, p_angle); +} + +// Sets rotation while preserving scaling. +// This requires some care when working with matrices with negative determinant, +// since we're using a particular convention for "polar" decomposition in get_scale and get_rotation. +// For details, see the explanation in get_scale. +void Basis::set_rotation_euler(const Vector3 &p_euler) { + Vector3 s = get_scale(); + Basis(); // reset to identity + scale(s); + rotate(p_euler); +} + +// Sets rotation while preserving scaling. +// This requires some care when working with matrices with negative determinant, +// since we're using a particular convention for "polar" decomposition in get_scale and get_rotation. +// For details, see the explanation in get_scale. +void Basis::set_rotation_axis_angle(const Vector3 &p_axis, real_t p_angle) { + Vector3 s = get_scale(); + Basis(); // reset to identity + scale(s); + rotate(p_axis, p_angle); +} + // get_euler returns a vector containing the Euler angles in the format // (a1,a2,a3), where a3 is the angle of the first rotation, and a1 is the last // (following the convention they are commonly defined in the literature). @@ -293,9 +358,9 @@ Vector3 Basis::get_euler() const { // -cx*cz*sy+sx*sz cz*sx+cx*sy*sz cx*cy Vector3 euler; - +#ifdef MATH_CHECKS ERR_FAIL_COND_V(is_rotation() == false, euler); - +#endif euler.y = Math::asin(elements[0][2]); if (euler.y < Math_PI * 0.5) { if (euler.y > -Math_PI * 0.5) { @@ -339,11 +404,11 @@ void Basis::set_euler(const Vector3 &p_euler) { *this = xmat * (ymat * zmat); } -bool Basis::isequal_approx(const Basis &a, const Basis &b) const { +bool Basis::is_equal_approx(const Basis &a, const Basis &b) const { for (int i = 0; i < 3; i++) { for (int j = 0; j < 3; j++) { - if (Math::isequal_approx(a.elements[i][j], b.elements[i][j]) == false) + if (Math::is_equal_approx(a.elements[i][j], b.elements[i][j]) == false) return false; } } @@ -386,8 +451,9 @@ Basis::operator String() const { } Basis::operator Quat() const { +#ifdef MATH_CHECKS ERR_FAIL_COND_V(is_rotation() == false, Quat()); - +#endif real_t trace = elements[0][0] + elements[1][1] + elements[2][2]; real_t temp[4]; @@ -481,9 +547,10 @@ void Basis::set_orthogonal_index(int p_index) { *this = _ortho_bases[p_index]; } -void Basis::get_axis_and_angle(Vector3 &r_axis, real_t &r_angle) const { +void Basis::get_axis_angle(Vector3 &r_axis, real_t &r_angle) const { +#ifdef MATH_CHECKS ERR_FAIL_COND(is_rotation() == false); - +#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 @@ -572,9 +639,11 @@ Basis::Basis(const Quat &p_quat) { xz - wy, yz + wx, 1.0 - (xx + yy)); } -Basis::Basis(const Vector3 &p_axis, real_t p_phi) { - // Rotation matrix from axis and angle, see https://en.wikipedia.org/wiki/Rotation_matrix#Rotation_matrix_from_axis_and_angle - +void Basis::set_axis_angle(const Vector3 &p_axis, real_t p_phi) { +// Rotation matrix from axis and angle, see https://en.wikipedia.org/wiki/Rotation_matrix#Rotation_matrix_from_axis_angle +#ifdef MATH_CHECKS + ERR_FAIL_COND(p_axis.is_normalized() == false); +#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); @@ -592,3 +661,7 @@ Basis::Basis(const Vector3 &p_axis, real_t p_phi) { elements[2][1] = p_axis.y * p_axis.z * (1.0 - cosine) + p_axis.x * sine; elements[2][2] = axis_sq.z + cosine * (1.0 - axis_sq.z); } + +Basis::Basis(const Vector3 &p_axis, real_t p_phi) { + set_axis_angle(p_axis, p_phi); +} diff --git a/core/math/matrix3.h b/core/math/matrix3.h index 0240bc8610..8897c692f7 100644 --- a/core/math/matrix3.h +++ b/core/math/matrix3.h @@ -6,6 +6,7 @@ /* http://www.godotengine.org */ /*************************************************************************/ /* Copyright (c) 2007-2017 Juan Linietsky, Ariel Manzur. */ +/* Copyright (c) 2014-2017 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 */ @@ -76,15 +77,25 @@ public: void rotate(const Vector3 &p_euler); Basis rotated(const Vector3 &p_euler) const; + Vector3 get_rotation() const; + void get_rotation_axis_angle(Vector3 &p_axis, real_t &p_angle) const; - void scale(const Vector3 &p_scale); - Basis scaled(const Vector3 &p_scale) const; - Vector3 get_scale() const; + void set_rotation_euler(const Vector3 &p_euler); + void set_rotation_axis_angle(const Vector3 &p_axis, real_t p_angle); Vector3 get_euler() const; void set_euler(const Vector3 &p_euler); + void get_axis_angle(Vector3 &r_axis, real_t &r_angle) const; + void set_axis_angle(const Vector3 &p_axis, real_t p_phi); + + void scale(const Vector3 &p_scale); + Basis scaled(const Vector3 &p_scale) const; + + Vector3 get_scale() const; + void set_scale(const Vector3 &p_scale); + // transposed dot products _FORCE_INLINE_ real_t tdotx(const Vector3 &v) const { return elements[0][0] * v[0] + elements[1][0] * v[1] + elements[2][0] * v[2]; @@ -96,7 +107,7 @@ public: return elements[0][2] * v[0] + elements[1][2] * v[1] + elements[2][2] * v[2]; } - bool isequal_approx(const Basis &a, const Basis &b) const; + bool is_equal_approx(const Basis &a, const Basis &b) const; bool operator==(const Basis &p_matrix) const; bool operator!=(const Basis &p_matrix) const; @@ -120,8 +131,6 @@ public: operator String() const; - void get_axis_and_angle(Vector3 &r_axis, real_t &r_angle) const; - /* create / set */ _FORCE_INLINE_ void set(real_t xx, real_t xy, real_t xz, real_t yx, real_t yy, real_t yz, real_t zx, real_t zy, real_t zz) { @@ -136,6 +145,12 @@ public: elements[2][1] = zy; elements[2][2] = zz; } + _FORCE_INLINE_ void set(const Vector3 &p_x, const Vector3 &p_y, const Vector3 &p_z) { + + set_axis(0, p_x); + set_axis(1, p_y); + set_axis(2, p_z); + } _FORCE_INLINE_ Vector3 get_column(int i) const { return Vector3(elements[0][i], elements[1][i], elements[2][i]); diff --git a/core/math/octree.h b/core/math/octree.h index 06c5791b11..010c1b18f7 100644 --- a/core/math/octree.h +++ b/core/math/octree.h @@ -6,6 +6,7 @@ /* http://www.godotengine.org */ /*************************************************************************/ /* Copyright (c) 2007-2017 Juan Linietsky, Ariel Manzur. */ +/* Copyright (c) 2014-2017 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 */ @@ -482,11 +483,11 @@ void Octree<T, use_pairs, AL>::_insert_element(Element *p_element, Octant *p_oct aabb.size *= 0.5; if (i & 1) - aabb.pos.x += aabb.size.x; + aabb.position.x += aabb.size.x; if (i & 2) - aabb.pos.y += aabb.size.y; + aabb.position.y += aabb.size.y; if (i & 4) - aabb.pos.z += aabb.size.z; + aabb.position.z += aabb.size.z; if (aabb.intersects_inclusive(p_element->aabb)) { /* if actually intersects, create the child */ @@ -543,11 +544,11 @@ void Octree<T, use_pairs, AL>::_ensure_valid_root(const Rect3 &p_aabb) { while (!base.encloses(p_aabb)) { - if (ABS(base.pos.x + base.size.x) <= ABS(base.pos.x)) { + if (ABS(base.position.x + base.size.x) <= ABS(base.position.x)) { /* grow towards positive */ base.size *= 2.0; } else { - base.pos -= base.size; + base.position -= base.size; base.size *= 2.0; } } @@ -575,14 +576,14 @@ void Octree<T, use_pairs, AL>::_ensure_valid_root(const Rect3 &p_aabb) { octant_count++; root->parent = gp; - if (ABS(base.pos.x + base.size.x) <= ABS(base.pos.x)) { + if (ABS(base.position.x + base.size.x) <= ABS(base.position.x)) { /* grow towards positive */ base.size *= 2.0; gp->aabb = base; gp->children[0] = root; root->parent_index = 0; } else { - base.pos -= base.size; + base.position -= base.size; base.size *= 2.0; gp->aabb = base; gp->children[(1 << 0) | (1 << 1) | (1 << 2)] = root; // add at all-positive @@ -796,9 +797,9 @@ OctreeElementID Octree<T, use_pairs, AL>::create(T *p_userdata, const Rect3 &p_a // check for AABB validity #ifdef DEBUG_ENABLED - ERR_FAIL_COND_V(p_aabb.pos.x > 1e15 || p_aabb.pos.x < -1e15, 0); - ERR_FAIL_COND_V(p_aabb.pos.y > 1e15 || p_aabb.pos.y < -1e15, 0); - ERR_FAIL_COND_V(p_aabb.pos.z > 1e15 || p_aabb.pos.z < -1e15, 0); + ERR_FAIL_COND_V(p_aabb.position.x > 1e15 || p_aabb.position.x < -1e15, 0); + ERR_FAIL_COND_V(p_aabb.position.y > 1e15 || p_aabb.position.y < -1e15, 0); + ERR_FAIL_COND_V(p_aabb.position.z > 1e15 || p_aabb.position.z < -1e15, 0); ERR_FAIL_COND_V(p_aabb.size.x > 1e15 || p_aabb.size.x < 0.0, 0); ERR_FAIL_COND_V(p_aabb.size.y > 1e15 || p_aabb.size.y < 0.0, 0); ERR_FAIL_COND_V(p_aabb.size.z > 1e15 || p_aabb.size.z < 0.0, 0); @@ -836,9 +837,9 @@ void Octree<T, use_pairs, AL>::move(OctreeElementID p_id, const Rect3 &p_aabb) { #ifdef DEBUG_ENABLED // check for AABB validity - ERR_FAIL_COND(p_aabb.pos.x > 1e15 || p_aabb.pos.x < -1e15); - ERR_FAIL_COND(p_aabb.pos.y > 1e15 || p_aabb.pos.y < -1e15); - ERR_FAIL_COND(p_aabb.pos.z > 1e15 || p_aabb.pos.z < -1e15); + ERR_FAIL_COND(p_aabb.position.x > 1e15 || p_aabb.position.x < -1e15); + ERR_FAIL_COND(p_aabb.position.y > 1e15 || p_aabb.position.y < -1e15); + ERR_FAIL_COND(p_aabb.position.z > 1e15 || p_aabb.position.z < -1e15); ERR_FAIL_COND(p_aabb.size.x > 1e15 || p_aabb.size.x < 0.0); ERR_FAIL_COND(p_aabb.size.y > 1e15 || p_aabb.size.y < 0.0); ERR_FAIL_COND(p_aabb.size.z > 1e15 || p_aabb.size.z < 0.0); diff --git a/core/math/pcg.cpp b/core/math/pcg.cpp deleted file mode 100644 index eac3b36d36..0000000000 --- a/core/math/pcg.cpp +++ /dev/null @@ -1,15 +0,0 @@ -// *Really* minimal PCG32 code / (c) 2014 M.E. O'Neill / pcg-random.org -// Licensed under Apache License 2.0 (NO WARRANTY, etc. see website) - -#include "pcg.h" - -uint32_t pcg32_random_r(pcg32_random_t* rng) -{ - uint64_t oldstate = rng->state; - // Advance internal state - rng->state = oldstate * 6364136223846793005ULL + (rng->inc|1); - // Calculate output function (XSH RR), uses old state for max ILP - uint32_t xorshifted = ((oldstate >> 18u) ^ oldstate) >> 27u; - uint32_t rot = oldstate >> 59u; - return (xorshifted >> rot) | (xorshifted << ((-rot) & 31)); -} diff --git a/core/math/pcg.h b/core/math/pcg.h deleted file mode 100644 index 81f4c9770e..0000000000 --- a/core/math/pcg.h +++ /dev/null @@ -1,14 +0,0 @@ -// *Really* minimal PCG32 code / (c) 2014 M.E. O'Neill / pcg-random.org -// Licensed under Apache License 2.0 (NO WARRANTY, etc. see website) - -#ifndef RANDOM_H -#define RANDOM_H - -#include "typedefs.h" - -#define PCG_DEFAULT_INC_64 1442695040888963407ULL - -typedef struct { uint64_t state; uint64_t inc; } pcg32_random_t; -uint32_t pcg32_random_r(pcg32_random_t* rng); - -#endif // RANDOM_H diff --git a/core/math/plane.cpp b/core/math/plane.cpp index 29e7f2e75c..f5e92866c4 100644 --- a/core/math/plane.cpp +++ b/core/math/plane.cpp @@ -6,6 +6,7 @@ /* http://www.godotengine.org */ /*************************************************************************/ /* Copyright (c) 2007-2017 Juan Linietsky, Ariel Manzur. */ +/* Copyright (c) 2014-2017 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 */ @@ -116,7 +117,7 @@ bool Plane::intersects_ray(Vector3 p_from, Vector3 p_dir, Vector3 *p_intersectio real_t dist = (normal.dot(p_from) - d) / den; //printf("dist is %i\n",dist); - if (dist > CMP_EPSILON) { //this is a ray, before the emiting pos (p_from) doesnt exist + if (dist > CMP_EPSILON) { //this is a ray, before the emitting pos (p_from) doesn't exist return false; } diff --git a/core/math/plane.h b/core/math/plane.h index 380452f6d2..5a048674e4 100644 --- a/core/math/plane.h +++ b/core/math/plane.h @@ -6,6 +6,7 @@ /* http://www.godotengine.org */ /*************************************************************************/ /* Copyright (c) 2007-2017 Juan Linietsky, Ariel Manzur. */ +/* Copyright (c) 2014-2017 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/quat.cpp b/core/math/quat.cpp index b990e9184f..0bea97c2e8 100644 --- a/core/math/quat.cpp +++ b/core/math/quat.cpp @@ -6,6 +6,7 @@ /* http://www.godotengine.org */ /*************************************************************************/ /* Copyright (c) 2007-2017 Juan Linietsky, Ariel Manzur. */ +/* Copyright (c) 2014-2017 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 */ @@ -91,6 +92,10 @@ Quat Quat::normalized() const { return *this / length(); } +bool Quat::is_normalized() const { + return Math::is_equal_approx(length(), 1.0); +} + Quat Quat::inverse() const { return Quat(-x, -y, -z, w); } diff --git a/core/math/quat.h b/core/math/quat.h index 3fc843b83a..f22275b457 100644 --- a/core/math/quat.h +++ b/core/math/quat.h @@ -6,6 +6,7 @@ /* http://www.godotengine.org */ /*************************************************************************/ /* Copyright (c) 2007-2017 Juan Linietsky, Ariel Manzur. */ +/* Copyright (c) 2014-2017 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 */ @@ -47,6 +48,7 @@ public: real_t length() const; void normalize(); Quat normalized() const; + bool is_normalized() const; Quat inverse() const; _FORCE_INLINE_ real_t dot(const Quat &q) const; void set_euler(const Vector3 &p_euler); @@ -55,7 +57,7 @@ public: Quat slerpni(const Quat &q, const real_t &t) const; Quat cubic_slerp(const Quat &q, const Quat &prep, const Quat &postq, const real_t &t) const; - _FORCE_INLINE_ void get_axis_and_angle(Vector3 &r_axis, real_t &r_angle) const { + _FORCE_INLINE_ void get_axis_angle(Vector3 &r_axis, real_t &r_angle) const { r_angle = 2 * Math::acos(w); r_axis.x = x / Math::sqrt(1 - w * w); r_axis.y = y / Math::sqrt(1 - w * w); diff --git a/core/math/quick_hull.cpp b/core/math/quick_hull.cpp index a235d1cf32..9f594ba4fa 100644 --- a/core/math/quick_hull.cpp +++ b/core/math/quick_hull.cpp @@ -6,6 +6,7 @@ /* http://www.godotengine.org */ /*************************************************************************/ /* Copyright (c) 2007-2017 Juan Linietsky, Ariel Manzur. */ +/* Copyright (c) 2014-2017 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 */ @@ -41,7 +42,7 @@ Error QuickHull::build(const Vector<Vector3> &p_points, Geometry::MeshData &r_me for (int i = 0; i < p_points.size(); i++) { if (i == 0) { - aabb.pos = p_points[i]; + aabb.position = p_points[i]; } else { aabb.expand_to(p_points[i]); } diff --git a/core/math/quick_hull.h b/core/math/quick_hull.h index 43a802e6bd..49600649e3 100644 --- a/core/math/quick_hull.h +++ b/core/math/quick_hull.h @@ -6,6 +6,7 @@ /* http://www.godotengine.org */ /*************************************************************************/ /* Copyright (c) 2007-2017 Juan Linietsky, Ariel Manzur. */ +/* Copyright (c) 2014-2017 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/rect3.cpp b/core/math/rect3.cpp index c0cd66d9bb..973607f565 100644 --- a/core/math/rect3.cpp +++ b/core/math/rect3.cpp @@ -6,6 +6,7 @@ /* http://www.godotengine.org */ /*************************************************************************/ /* Copyright (c) 2007-2017 Juan Linietsky, Ariel Manzur. */ +/* Copyright (c) 2014-2017 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 */ @@ -37,11 +38,11 @@ real_t Rect3::get_area() const { bool Rect3::operator==(const Rect3 &p_rval) const { - return ((pos == p_rval.pos) && (size == p_rval.size)); + return ((position == p_rval.position) && (size == p_rval.size)); } bool Rect3::operator!=(const Rect3 &p_rval) const { - return ((pos != p_rval.pos) || (size != p_rval.size)); + return ((position != p_rval.position) || (size != p_rval.size)); } void Rect3::merge_with(const Rect3 &p_aabb) { @@ -50,8 +51,8 @@ void Rect3::merge_with(const Rect3 &p_aabb) { Vector3 end_1, end_2; Vector3 min, max; - beg_1 = pos; - beg_2 = p_aabb.pos; + beg_1 = position; + beg_2 = p_aabb.position; end_1 = Vector3(size.x, size.y, size.z) + beg_1; end_2 = Vector3(p_aabb.size.x, p_aabb.size.y, p_aabb.size.z) + beg_2; @@ -63,16 +64,16 @@ void Rect3::merge_with(const Rect3 &p_aabb) { max.y = (end_1.y > end_2.y) ? end_1.y : end_2.y; max.z = (end_1.z > end_2.z) ? end_1.z : end_2.z; - pos = min; + position = min; size = max - min; } Rect3 Rect3::intersection(const Rect3 &p_aabb) const { - Vector3 src_min = pos; - Vector3 src_max = pos + size; - Vector3 dst_min = p_aabb.pos; - Vector3 dst_max = p_aabb.pos + p_aabb.size; + Vector3 src_min = position; + Vector3 src_max = position + size; + Vector3 dst_min = p_aabb.position; + Vector3 dst_max = p_aabb.position + p_aabb.size; Vector3 min, max; @@ -106,18 +107,18 @@ Rect3 Rect3::intersection(const Rect3 &p_aabb) const { bool Rect3::intersects_ray(const Vector3 &p_from, const Vector3 &p_dir, Vector3 *r_clip, Vector3 *r_normal) const { Vector3 c1, c2; - Vector3 end = pos + size; + Vector3 end = position + size; real_t near = -1e20; real_t far = 1e20; int axis = 0; for (int i = 0; i < 3; i++) { if (p_dir[i] == 0) { - if ((p_from[i] < pos[i]) || (p_from[i] > end[i])) { + if ((p_from[i] < position[i]) || (p_from[i] > end[i])) { return false; } } else { // ray not parallel to planes in this direction - c1[i] = (pos[i] - p_from[i]) / p_dir[i]; + c1[i] = (position[i] - p_from[i]) / p_dir[i]; c2[i] = (end[i] - p_from[i]) / p_dir[i]; if (c1[i] > c2[i]) { @@ -155,7 +156,7 @@ bool Rect3::intersects_segment(const Vector3 &p_from, const Vector3 &p_to, Vecto for (int i = 0; i < 3; i++) { real_t seg_from = p_from[i]; real_t seg_to = p_to[i]; - real_t box_begin = pos[i]; + real_t box_begin = position[i]; real_t box_end = box_begin + size[i]; real_t cmin, cmax; real_t csign; @@ -207,14 +208,14 @@ bool Rect3::intersects_segment(const Vector3 &p_from, const Vector3 &p_to, Vecto bool Rect3::intersects_plane(const Plane &p_plane) const { Vector3 points[8] = { - Vector3(pos.x, pos.y, pos.z), - Vector3(pos.x, pos.y, pos.z + size.z), - Vector3(pos.x, pos.y + size.y, pos.z), - Vector3(pos.x, pos.y + size.y, pos.z + size.z), - Vector3(pos.x + size.x, pos.y, pos.z), - Vector3(pos.x + size.x, pos.y, pos.z + size.z), - Vector3(pos.x + size.x, pos.y + size.y, pos.z), - Vector3(pos.x + size.x, pos.y + size.y, pos.z + size.z), + Vector3(position.x, position.y, position.z), + Vector3(position.x, position.y, position.z + size.z), + Vector3(position.x, position.y + size.y, position.z), + Vector3(position.x, position.y + size.y, position.z + size.z), + Vector3(position.x + size.x, position.y, position.z), + Vector3(position.x + size.x, position.y, position.z + size.z), + Vector3(position.x + size.x, position.y + size.y, position.z), + Vector3(position.x + size.x, position.y + size.y, position.z + size.z), }; bool over = false; @@ -326,68 +327,68 @@ void Rect3::get_edge(int p_edge, Vector3 &r_from, Vector3 &r_to) const { case 0: { - r_from = Vector3(pos.x + size.x, pos.y, pos.z); - r_to = Vector3(pos.x, pos.y, pos.z); + r_from = Vector3(position.x + size.x, position.y, position.z); + r_to = Vector3(position.x, position.y, position.z); } break; case 1: { - r_from = Vector3(pos.x + size.x, pos.y, pos.z + size.z); - r_to = Vector3(pos.x + size.x, pos.y, pos.z); + r_from = Vector3(position.x + size.x, position.y, position.z + size.z); + r_to = Vector3(position.x + size.x, position.y, position.z); } break; case 2: { - r_from = Vector3(pos.x, pos.y, pos.z + size.z); - r_to = Vector3(pos.x + size.x, pos.y, pos.z + size.z); + r_from = Vector3(position.x, position.y, position.z + size.z); + r_to = Vector3(position.x + size.x, position.y, position.z + size.z); } break; case 3: { - r_from = Vector3(pos.x, pos.y, pos.z); - r_to = Vector3(pos.x, pos.y, pos.z + size.z); + r_from = Vector3(position.x, position.y, position.z); + r_to = Vector3(position.x, position.y, position.z + size.z); } break; case 4: { - r_from = Vector3(pos.x, pos.y + size.y, pos.z); - r_to = Vector3(pos.x + size.x, pos.y + size.y, pos.z); + r_from = Vector3(position.x, position.y + size.y, position.z); + r_to = Vector3(position.x + size.x, position.y + size.y, position.z); } break; case 5: { - r_from = Vector3(pos.x + size.x, pos.y + size.y, pos.z); - r_to = Vector3(pos.x + size.x, pos.y + size.y, pos.z + size.z); + r_from = Vector3(position.x + size.x, position.y + size.y, position.z); + r_to = Vector3(position.x + size.x, position.y + size.y, position.z + size.z); } break; case 6: { - r_from = Vector3(pos.x + size.x, pos.y + size.y, pos.z + size.z); - r_to = Vector3(pos.x, pos.y + size.y, pos.z + size.z); + r_from = Vector3(position.x + size.x, position.y + size.y, position.z + size.z); + r_to = Vector3(position.x, position.y + size.y, position.z + size.z); } break; case 7: { - r_from = Vector3(pos.x, pos.y + size.y, pos.z + size.z); - r_to = Vector3(pos.x, pos.y + size.y, pos.z); + r_from = Vector3(position.x, position.y + size.y, position.z + size.z); + r_to = Vector3(position.x, position.y + size.y, position.z); } break; case 8: { - r_from = Vector3(pos.x, pos.y, pos.z + size.z); - r_to = Vector3(pos.x, pos.y + size.y, pos.z + size.z); + r_from = Vector3(position.x, position.y, position.z + size.z); + r_to = Vector3(position.x, position.y + size.y, position.z + size.z); } break; case 9: { - r_from = Vector3(pos.x, pos.y, pos.z); - r_to = Vector3(pos.x, pos.y + size.y, pos.z); + r_from = Vector3(position.x, position.y, position.z); + r_to = Vector3(position.x, position.y + size.y, position.z); } break; case 10: { - r_from = Vector3(pos.x + size.x, pos.y, pos.z); - r_to = Vector3(pos.x + size.x, pos.y + size.y, pos.z); + r_from = Vector3(position.x + size.x, position.y, position.z); + r_to = Vector3(position.x + size.x, position.y + size.y, position.z); } break; case 11: { - r_from = Vector3(pos.x + size.x, pos.y, pos.z + size.z); - r_to = Vector3(pos.x + size.x, pos.y + size.y, pos.z + size.z); + r_from = Vector3(position.x + size.x, position.y, position.z + size.z); + r_to = Vector3(position.x + size.x, position.y + size.y, position.z + size.z); } break; } @@ -395,5 +396,5 @@ void Rect3::get_edge(int p_edge, Vector3 &r_from, Vector3 &r_to) const { Rect3::operator String() const { - return String() + pos + " - " + size; + return String() + position + " - " + size; } diff --git a/core/math/rect3.h b/core/math/rect3.h index 26198537c2..b7c94ad9f7 100644 --- a/core/math/rect3.h +++ b/core/math/rect3.h @@ -6,6 +6,7 @@ /* http://www.godotengine.org */ /*************************************************************************/ /* Copyright (c) 2007-2017 Juan Linietsky, Ariel Manzur. */ +/* Copyright (c) 2014-2017 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 */ @@ -35,12 +36,12 @@ /** * AABB / AABB (Axis Aligned Bounding Box) - * This is implemented by a point (pos) and the box size + * This is implemented by a point (position) and the box size */ class Rect3 { public: - Vector3 pos; + Vector3 position; Vector3 size; real_t get_area() const; /// get area @@ -54,8 +55,8 @@ public: return (size.x <= CMP_EPSILON && size.y <= CMP_EPSILON && size.z <= CMP_EPSILON); } - const Vector3 &get_pos() const { return pos; } - void set_pos(const Vector3 &p_pos) { pos = p_pos; } + const Vector3 &get_position() const { return position; } + void set_position(const Vector3 &p_pos) { position = p_pos; } const Vector3 &get_size() const { return size; } void set_size(const Vector3 &p_size) { size = p_size; } @@ -95,30 +96,30 @@ public: Rect3 expand(const Vector3 &p_vector) const; _FORCE_INLINE_ void project_range_in_plane(const Plane &p_plane, real_t &r_min, real_t &r_max) const; - _FORCE_INLINE_ void expand_to(const Vector3 &p_vector); /** expand to contain a point if necesary */ + _FORCE_INLINE_ void expand_to(const Vector3 &p_vector); /** expand to contain a point if necessary */ operator String() const; _FORCE_INLINE_ Rect3() {} inline Rect3(const Vector3 &p_pos, const Vector3 &p_size) { - pos = p_pos; + position = p_pos; size = p_size; } }; inline bool Rect3::intersects(const Rect3 &p_aabb) const { - if (pos.x >= (p_aabb.pos.x + p_aabb.size.x)) + if (position.x >= (p_aabb.position.x + p_aabb.size.x)) return false; - if ((pos.x + size.x) <= p_aabb.pos.x) + if ((position.x + size.x) <= p_aabb.position.x) return false; - if (pos.y >= (p_aabb.pos.y + p_aabb.size.y)) + if (position.y >= (p_aabb.position.y + p_aabb.size.y)) return false; - if ((pos.y + size.y) <= p_aabb.pos.y) + if ((position.y + size.y) <= p_aabb.position.y) return false; - if (pos.z >= (p_aabb.pos.z + p_aabb.size.z)) + if (position.z >= (p_aabb.position.z + p_aabb.size.z)) return false; - if ((pos.z + size.z) <= p_aabb.pos.z) + if ((position.z + size.z) <= p_aabb.position.z) return false; return true; @@ -126,17 +127,17 @@ inline bool Rect3::intersects(const Rect3 &p_aabb) const { inline bool Rect3::intersects_inclusive(const Rect3 &p_aabb) const { - if (pos.x > (p_aabb.pos.x + p_aabb.size.x)) + if (position.x > (p_aabb.position.x + p_aabb.size.x)) return false; - if ((pos.x + size.x) < p_aabb.pos.x) + if ((position.x + size.x) < p_aabb.position.x) return false; - if (pos.y > (p_aabb.pos.y + p_aabb.size.y)) + if (position.y > (p_aabb.position.y + p_aabb.size.y)) return false; - if ((pos.y + size.y) < p_aabb.pos.y) + if ((position.y + size.y) < p_aabb.position.y) return false; - if (pos.z > (p_aabb.pos.z + p_aabb.size.z)) + if (position.z > (p_aabb.position.z + p_aabb.size.z)) return false; - if ((pos.z + size.z) < p_aabb.pos.z) + if ((position.z + size.z) < p_aabb.position.z) return false; return true; @@ -144,10 +145,10 @@ inline bool Rect3::intersects_inclusive(const Rect3 &p_aabb) const { inline bool Rect3::encloses(const Rect3 &p_aabb) const { - Vector3 src_min = pos; - Vector3 src_max = pos + size; - Vector3 dst_min = p_aabb.pos; - Vector3 dst_max = p_aabb.pos + p_aabb.size; + Vector3 src_min = position; + Vector3 src_max = position + size; + Vector3 dst_min = p_aabb.position; + Vector3 dst_max = p_aabb.position + p_aabb.size; return ( (src_min.x <= dst_min.x) && @@ -161,7 +162,7 @@ inline bool Rect3::encloses(const Rect3 &p_aabb) const { Vector3 Rect3::get_support(const Vector3 &p_normal) const { Vector3 half_extents = size * 0.5; - Vector3 ofs = pos + half_extents; + Vector3 ofs = position + half_extents; return Vector3( (p_normal.x > 0) ? -half_extents.x : half_extents.x, @@ -173,14 +174,14 @@ Vector3 Rect3::get_support(const Vector3 &p_normal) const { Vector3 Rect3::get_endpoint(int p_point) const { switch (p_point) { - case 0: return Vector3(pos.x, pos.y, pos.z); - case 1: return Vector3(pos.x, pos.y, pos.z + size.z); - case 2: return Vector3(pos.x, pos.y + size.y, pos.z); - case 3: return Vector3(pos.x, pos.y + size.y, pos.z + size.z); - case 4: return Vector3(pos.x + size.x, pos.y, pos.z); - case 5: return Vector3(pos.x + size.x, pos.y, pos.z + size.z); - case 6: return Vector3(pos.x + size.x, pos.y + size.y, pos.z); - case 7: return Vector3(pos.x + size.x, pos.y + size.y, pos.z + size.z); + case 0: return Vector3(position.x, position.y, position.z); + case 1: return Vector3(position.x, position.y, position.z + size.z); + case 2: return Vector3(position.x, position.y + size.y, position.z); + case 3: return Vector3(position.x, position.y + size.y, position.z + size.z); + case 4: return Vector3(position.x + size.x, position.y, position.z); + case 5: return Vector3(position.x + size.x, position.y, position.z + size.z); + case 6: return Vector3(position.x + size.x, position.y + size.y, position.z); + case 7: return Vector3(position.x + size.x, position.y + size.y, position.z + size.z); }; ERR_FAIL_V(Vector3()); @@ -191,7 +192,7 @@ bool Rect3::intersects_convex_shape(const Plane *p_planes, int p_plane_count) co #if 1 Vector3 half_extents = size * 0.5; - Vector3 ofs = pos + half_extents; + Vector3 ofs = position + half_extents; for (int i = 0; i < p_plane_count; i++) { const Plane &p = p_planes[i]; @@ -209,14 +210,14 @@ bool Rect3::intersects_convex_shape(const Plane *p_planes, int p_plane_count) co //cache all points to check against! // #warning should be easy to optimize, just use the same as when taking the support and use only that point Vector3 points[8] = { - Vector3(pos.x, pos.y, pos.z), - Vector3(pos.x, pos.y, pos.z + size.z), - Vector3(pos.x, pos.y + size.y, pos.z), - Vector3(pos.x, pos.y + size.y, pos.z + size.z), - Vector3(pos.x + size.x, pos.y, pos.z), - Vector3(pos.x + size.x, pos.y, pos.z + size.z), - Vector3(pos.x + size.x, pos.y + size.y, pos.z), - Vector3(pos.x + size.x, pos.y + size.y, pos.z + size.z), + Vector3(position.x, position.y, position.z), + Vector3(position.x, position.y, position.z + size.z), + Vector3(position.x, position.y + size.y, position.z), + Vector3(position.x, position.y + size.y, position.z + size.z), + Vector3(position.x + size.x, position.y, position.z), + Vector3(position.x + size.x, position.y, position.z + size.z), + Vector3(position.x + size.x, position.y + size.y, position.z), + Vector3(position.x + size.x, position.y + size.y, position.z + size.z), }; for (int i = 0; i < p_plane_count; i++) { //for each plane @@ -245,17 +246,17 @@ bool Rect3::intersects_convex_shape(const Plane *p_planes, int p_plane_count) co bool Rect3::has_point(const Vector3 &p_point) const { - if (p_point.x < pos.x) + if (p_point.x < position.x) return false; - if (p_point.y < pos.y) + if (p_point.y < position.y) return false; - if (p_point.z < pos.z) + if (p_point.z < position.z) return false; - if (p_point.x > pos.x + size.x) + if (p_point.x > position.x + size.x) return false; - if (p_point.y > pos.y + size.y) + if (p_point.y > position.y + size.y) return false; - if (p_point.z > pos.z + size.z) + if (p_point.z > position.z + size.z) return false; return true; @@ -263,8 +264,8 @@ bool Rect3::has_point(const Vector3 &p_point) const { inline void Rect3::expand_to(const Vector3 &p_vector) { - Vector3 begin = pos; - Vector3 end = pos + size; + Vector3 begin = position; + Vector3 end = position + size; if (p_vector.x < begin.x) begin.x = p_vector.x; @@ -280,14 +281,14 @@ inline void Rect3::expand_to(const Vector3 &p_vector) { if (p_vector.z > end.z) end.z = p_vector.z; - pos = begin; + position = begin; size = end - begin; } void Rect3::project_range_in_plane(const Plane &p_plane, real_t &r_min, real_t &r_max) const { Vector3 half_extents(size.x * 0.5, size.y * 0.5, size.z * 0.5); - Vector3 center(pos.x + half_extents.x, pos.y + half_extents.y, pos.z + half_extents.z); + Vector3 center(position.x + half_extents.x, position.y + half_extents.y, position.z + half_extents.z); real_t length = p_plane.normal.abs().dot(half_extents); real_t distance = p_plane.distance_to(center); @@ -331,21 +332,21 @@ bool Rect3::smits_intersect_ray(const Vector3 &from, const Vector3 &dir, real_t real_t divy = 1.0 / dir.y; real_t divz = 1.0 / dir.z; - Vector3 upbound = pos + size; + Vector3 upbound = position + size; real_t tmin, tmax, tymin, tymax, tzmin, tzmax; if (dir.x >= 0) { - tmin = (pos.x - from.x) * divx; + tmin = (position.x - from.x) * divx; tmax = (upbound.x - from.x) * divx; } else { tmin = (upbound.x - from.x) * divx; - tmax = (pos.x - from.x) * divx; + tmax = (position.x - from.x) * divx; } if (dir.y >= 0) { - tymin = (pos.y - from.y) * divy; + tymin = (position.y - from.y) * divy; tymax = (upbound.y - from.y) * divy; } else { tymin = (upbound.y - from.y) * divy; - tymax = (pos.y - from.y) * divy; + tymax = (position.y - from.y) * divy; } if ((tmin > tymax) || (tymin > tmax)) return false; @@ -354,11 +355,11 @@ bool Rect3::smits_intersect_ray(const Vector3 &from, const Vector3 &dir, real_t if (tymax < tmax) tmax = tymax; if (dir.z >= 0) { - tzmin = (pos.z - from.z) * divz; + tzmin = (position.z - from.z) * divz; tzmax = (upbound.z - from.z) * divz; } else { tzmin = (upbound.z - from.z) * divz; - tzmax = (pos.z - from.z) * divz; + tzmax = (position.z - from.z) * divz; } if ((tmin > tzmax) || (tzmin > tmax)) return false; @@ -371,9 +372,9 @@ bool Rect3::smits_intersect_ray(const Vector3 &from, const Vector3 &dir, real_t void Rect3::grow_by(real_t p_amount) { - pos.x -= p_amount; - pos.y -= p_amount; - pos.z -= p_amount; + position.x -= p_amount; + position.y -= p_amount; + position.z -= p_amount; size.x += 2.0 * p_amount; size.y += 2.0 * p_amount; size.z += 2.0 * p_amount; diff --git a/core/math/transform.cpp b/core/math/transform.cpp index d35938e559..7a50214596 100644 --- a/core/math/transform.cpp +++ b/core/math/transform.cpp @@ -6,6 +6,7 @@ /* http://www.godotengine.org */ /*************************************************************************/ /* Copyright (c) 2007-2017 Juan Linietsky, Ariel Manzur. */ +/* Copyright (c) 2014-2017 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,7 +82,10 @@ Transform Transform::looking_at(const Vector3 &p_target, const Vector3 &p_up) co } void Transform::set_look_at(const Vector3 &p_eye, const Vector3 &p_target, const Vector3 &p_up) { - +#ifdef MATH_CHECKS + ERR_FAIL_COND(p_eye == p_target); + ERR_FAIL_COND(p_up.length() == 0); +#endif // Reference: MESA source code Vector3 v_x, v_y, v_z; @@ -95,6 +99,9 @@ void Transform::set_look_at(const Vector3 &p_eye, const Vector3 &p_target, const v_y = p_up; v_x = v_y.cross(v_z); +#ifdef MATH_CHECKS + ERR_FAIL_COND(v_x.length() == 0); +#endif /* Recompute Y = Z cross X */ v_y = v_z.cross(v_x); @@ -102,9 +109,8 @@ void Transform::set_look_at(const Vector3 &p_eye, const Vector3 &p_target, const v_x.normalize(); v_y.normalize(); - basis.set_axis(0, v_x); - basis.set_axis(1, v_y); - basis.set_axis(2, v_z); + basis.set(v_x, v_y, v_z); + origin = p_eye; } diff --git a/core/math/transform.h b/core/math/transform.h index e307aba129..48467f2ed7 100644 --- a/core/math/transform.h +++ b/core/math/transform.h @@ -6,6 +6,7 @@ /* http://www.godotengine.org */ /*************************************************************************/ /* Copyright (c) 2007-2017 Juan Linietsky, Ariel Manzur. */ +/* Copyright (c) 2014-2017 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 */ @@ -96,15 +97,7 @@ public: void set(real_t xx, real_t xy, real_t xz, real_t yx, real_t yy, real_t yz, real_t zx, real_t zy, real_t zz, real_t tx, real_t ty, real_t tz) { - basis.elements[0][0] = xx; - basis.elements[0][1] = xy; - basis.elements[0][2] = xz; - basis.elements[1][0] = yx; - basis.elements[1][1] = yy; - basis.elements[1][2] = yz; - basis.elements[2][0] = zx; - basis.elements[2][1] = zy; - basis.elements[2][2] = zz; + basis.set(xx, xy, xz, yx, yy, yz, zx, zy, zz); origin.x = tx; origin.y = ty; origin.z = tz; @@ -166,10 +159,10 @@ _FORCE_INLINE_ Rect3 Transform::xform(const Rect3 &p_aabb) const { Vector3 x = basis.get_axis(0) * p_aabb.size.x; Vector3 y = basis.get_axis(1) * p_aabb.size.y; Vector3 z = basis.get_axis(2) * p_aabb.size.z; - Vector3 pos = xform(p_aabb.pos); + Vector3 pos = xform(p_aabb.position); //could be even further optimized Rect3 new_aabb; - new_aabb.pos = pos; + new_aabb.position = pos; new_aabb.expand_to(pos + x); new_aabb.expand_to(pos + y); new_aabb.expand_to(pos + z); @@ -181,14 +174,14 @@ _FORCE_INLINE_ Rect3 Transform::xform(const Rect3 &p_aabb) const { #else Vector3 vertices[8] = { - Vector3(p_aabb.pos.x + p_aabb.size.x, p_aabb.pos.y + p_aabb.size.y, p_aabb.pos.z + p_aabb.size.z), - Vector3(p_aabb.pos.x + p_aabb.size.x, p_aabb.pos.y + p_aabb.size.y, p_aabb.pos.z), - Vector3(p_aabb.pos.x + p_aabb.size.x, p_aabb.pos.y, p_aabb.pos.z + p_aabb.size.z), - Vector3(p_aabb.pos.x + p_aabb.size.x, p_aabb.pos.y, p_aabb.pos.z), - Vector3(p_aabb.pos.x, p_aabb.pos.y + p_aabb.size.y, p_aabb.pos.z + p_aabb.size.z), - Vector3(p_aabb.pos.x, p_aabb.pos.y + p_aabb.size.y, p_aabb.pos.z), - Vector3(p_aabb.pos.x, p_aabb.pos.y, p_aabb.pos.z + p_aabb.size.z), - Vector3(p_aabb.pos.x, p_aabb.pos.y, p_aabb.pos.z) + Vector3(p_aabb.position.x + p_aabb.size.x, p_aabb.position.y + p_aabb.size.y, p_aabb.position.z + p_aabb.size.z), + Vector3(p_aabb.position.x + p_aabb.size.x, p_aabb.position.y + p_aabb.size.y, p_aabb.position.z), + Vector3(p_aabb.position.x + p_aabb.size.x, p_aabb.position.y, p_aabb.position.z + p_aabb.size.z), + Vector3(p_aabb.position.x + p_aabb.size.x, p_aabb.position.y, p_aabb.position.z), + Vector3(p_aabb.position.x, p_aabb.position.y + p_aabb.size.y, p_aabb.position.z + p_aabb.size.z), + Vector3(p_aabb.position.x, p_aabb.position.y + p_aabb.size.y, p_aabb.position.z), + Vector3(p_aabb.position.x, p_aabb.position.y, p_aabb.position.z + p_aabb.size.z), + Vector3(p_aabb.position.x, p_aabb.position.y, p_aabb.position.z) }; AABB ret; @@ -207,19 +200,19 @@ _FORCE_INLINE_ Rect3 Transform::xform_inv(const Rect3 &p_aabb) const { /* define vertices */ Vector3 vertices[8] = { - Vector3(p_aabb.pos.x + p_aabb.size.x, p_aabb.pos.y + p_aabb.size.y, p_aabb.pos.z + p_aabb.size.z), - Vector3(p_aabb.pos.x + p_aabb.size.x, p_aabb.pos.y + p_aabb.size.y, p_aabb.pos.z), - Vector3(p_aabb.pos.x + p_aabb.size.x, p_aabb.pos.y, p_aabb.pos.z + p_aabb.size.z), - Vector3(p_aabb.pos.x + p_aabb.size.x, p_aabb.pos.y, p_aabb.pos.z), - Vector3(p_aabb.pos.x, p_aabb.pos.y + p_aabb.size.y, p_aabb.pos.z + p_aabb.size.z), - Vector3(p_aabb.pos.x, p_aabb.pos.y + p_aabb.size.y, p_aabb.pos.z), - Vector3(p_aabb.pos.x, p_aabb.pos.y, p_aabb.pos.z + p_aabb.size.z), - Vector3(p_aabb.pos.x, p_aabb.pos.y, p_aabb.pos.z) + Vector3(p_aabb.position.x + p_aabb.size.x, p_aabb.position.y + p_aabb.size.y, p_aabb.position.z + p_aabb.size.z), + Vector3(p_aabb.position.x + p_aabb.size.x, p_aabb.position.y + p_aabb.size.y, p_aabb.position.z), + Vector3(p_aabb.position.x + p_aabb.size.x, p_aabb.position.y, p_aabb.position.z + p_aabb.size.z), + Vector3(p_aabb.position.x + p_aabb.size.x, p_aabb.position.y, p_aabb.position.z), + Vector3(p_aabb.position.x, p_aabb.position.y + p_aabb.size.y, p_aabb.position.z + p_aabb.size.z), + Vector3(p_aabb.position.x, p_aabb.position.y + p_aabb.size.y, p_aabb.position.z), + Vector3(p_aabb.position.x, p_aabb.position.y, p_aabb.position.z + p_aabb.size.z), + Vector3(p_aabb.position.x, p_aabb.position.y, p_aabb.position.z) }; Rect3 ret; - ret.pos = xform_inv(vertices[0]); + ret.position = xform_inv(vertices[0]); for (int i = 1; i < 8; i++) { @@ -229,27 +222,4 @@ _FORCE_INLINE_ Rect3 Transform::xform_inv(const Rect3 &p_aabb) const { return ret; } -#ifdef OPTIMIZED_TRANSFORM_IMPL_OVERRIDE - -#else - -struct OptimizedTransform { - - Transform transform; - - _FORCE_INLINE_ void invert() { transform.invert(); } - _FORCE_INLINE_ void affine_invert() { transform.affine_invert(); } - _FORCE_INLINE_ Vector3 xform(const Vector3 &p_vec) const { return transform.xform(p_vec); }; - _FORCE_INLINE_ Vector3 xform_inv(const Vector3 &p_vec) const { return transform.xform_inv(p_vec); }; - _FORCE_INLINE_ OptimizedTransform operator*(const OptimizedTransform &p_ot) const { return OptimizedTransform(transform * p_ot.transform); } - _FORCE_INLINE_ Transform get_transform() const { return transform; } - _FORCE_INLINE_ void set_transform(const Transform &p_transform) { transform = p_transform; } - - OptimizedTransform(const Transform &p_transform) { - transform = p_transform; - } -}; - -#endif - #endif diff --git a/core/math/triangle_mesh.cpp b/core/math/triangle_mesh.cpp index 93c6b2786e..08ac08d776 100644 --- a/core/math/triangle_mesh.cpp +++ b/core/math/triangle_mesh.cpp @@ -6,6 +6,7 @@ /* http://www.godotengine.org */ /*************************************************************************/ /* Copyright (c) 2007-2017 Juan Linietsky, Ariel Manzur. */ +/* Copyright (c) 2014-2017 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 */ @@ -78,7 +79,7 @@ int TriangleMesh::_create_bvh(BVH *p_bvh, BVH **p_bb, int p_from, int p_size, in int index = max_alloc++; BVH *_new = &p_bvh[index]; _new->aabb = aabb; - _new->center = aabb.pos + aabb.size * 0.5; + _new->center = aabb.position + aabb.size * 0.5; _new->face_index = -1; _new->left = left; _new->right = right; @@ -127,7 +128,7 @@ void TriangleMesh::create(const PoolVector<Vector3> &p_faces) { f.indices[j] = vidx; if (j == 0) - bw[i].aabb.pos = vs; + bw[i].aabb.position = vs; else bw[i].aabb.expand_to(vs); } @@ -137,7 +138,7 @@ void TriangleMesh::create(const PoolVector<Vector3> &p_faces) { bw[i].left = -1; bw[i].right = -1; bw[i].face_index = i; - bw[i].center = bw[i].aabb.pos + bw[i].aabb.size * 0.5; + bw[i].center = bw[i].aabb.position + bw[i].aabb.size * 0.5; } vertices.resize(db.size()); diff --git a/core/math/triangle_mesh.h b/core/math/triangle_mesh.h index 7f81e54613..166f10c577 100644 --- a/core/math/triangle_mesh.h +++ b/core/math/triangle_mesh.h @@ -6,6 +6,7 @@ /* http://www.godotengine.org */ /*************************************************************************/ /* Copyright (c) 2007-2017 Juan Linietsky, Ariel Manzur. */ +/* Copyright (c) 2014-2017 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 8568a963ab..4a5d0a078e 100644 --- a/core/math/triangulate.cpp +++ b/core/math/triangulate.cpp @@ -6,6 +6,7 @@ /* http://www.godotengine.org */ /*************************************************************************/ /* Copyright (c) 2007-2017 Juan Linietsky, Ariel Manzur. */ +/* Copyright (c) 2014-2017 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 c23d3ba27d..3f0ad00033 100644 --- a/core/math/triangulate.h +++ b/core/math/triangulate.h @@ -6,6 +6,7 @@ /* http://www.godotengine.org */ /*************************************************************************/ /* Copyright (c) 2007-2017 Juan Linietsky, Ariel Manzur. */ +/* Copyright (c) 2014-2017 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/triangulator.cpp b/core/math/triangulator.cpp deleted file mode 100644 index 75b2b064c4..0000000000 --- a/core/math/triangulator.cpp +++ /dev/null @@ -1,1550 +0,0 @@ -//Copyright (C) 2011 by Ivan Fratric -// -//Permission is hereby granted, free of charge, to any person obtaining a copy -//of this software and associated documentation files (the "Software"), to deal -//in the Software without restriction, including without limitation the rights -//to use, copy, modify, merge, publish, distribute, sublicense, and/or sell -//copies of the Software, and to permit persons to whom the Software is -//furnished to do so, subject to the following conditions: -// -//The above copyright notice and this permission notice shall be included in -//all copies or substantial portions of the Software. -// -//THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR -//IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, -//FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE -//AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER -//LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, -//OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN -//THE SOFTWARE. - - -#include <stdio.h> -#include <string.h> -#include <math.h> - -#include "triangulator.h" - - -#define TRIANGULATOR_VERTEXTYPE_REGULAR 0 -#define TRIANGULATOR_VERTEXTYPE_START 1 -#define TRIANGULATOR_VERTEXTYPE_END 2 -#define TRIANGULATOR_VERTEXTYPE_SPLIT 3 -#define TRIANGULATOR_VERTEXTYPE_MERGE 4 - -TriangulatorPoly::TriangulatorPoly() { - hole = false; - numpoints = 0; - points = NULL; -} - -TriangulatorPoly::~TriangulatorPoly() { - if(points) delete [] points; -} - -void TriangulatorPoly::Clear() { - if(points) delete [] points; - hole = false; - numpoints = 0; - points = NULL; -} - -void TriangulatorPoly::Init(long numpoints) { - Clear(); - this->numpoints = numpoints; - points = new Vector2[numpoints]; -} - -void TriangulatorPoly::Triangle(Vector2 &p1, Vector2 &p2, Vector2 &p3) { - Init(3); - points[0] = p1; - points[1] = p2; - points[2] = p3; -} - -TriangulatorPoly::TriangulatorPoly(const TriangulatorPoly &src) { - hole = src.hole; - numpoints = src.numpoints; - points = new Vector2[numpoints]; - memcpy(points, src.points, numpoints*sizeof(Vector2)); -} - -TriangulatorPoly& TriangulatorPoly::operator=(const TriangulatorPoly &src) { - Clear(); - hole = src.hole; - numpoints = src.numpoints; - points = new Vector2[numpoints]; - memcpy(points, src.points, numpoints*sizeof(Vector2)); - return *this; -} - -int TriangulatorPoly::GetOrientation() { - long i1,i2; - real_t area = 0; - for(i1=0; i1<numpoints; i1++) { - i2 = i1+1; - if(i2 == numpoints) i2 = 0; - area += points[i1].x * points[i2].y - points[i1].y * points[i2].x; - } - if(area>0) return TRIANGULATOR_CCW; - if(area<0) return TRIANGULATOR_CW; - return 0; -} - -void TriangulatorPoly::SetOrientation(int orientation) { - int polyorientation = GetOrientation(); - if(polyorientation&&(polyorientation!=orientation)) { - Invert(); - } -} - -void TriangulatorPoly::Invert() { - long i; - Vector2 *invpoints; - - invpoints = new Vector2[numpoints]; - for(i=0;i<numpoints;i++) { - invpoints[i] = points[numpoints-i-1]; - } - - delete [] points; - points = invpoints; -} - -Vector2 TriangulatorPartition::Normalize(const Vector2 &p) { - Vector2 r; - real_t n = sqrt(p.x*p.x + p.y*p.y); - if(n!=0) { - r = p/n; - } else { - r.x = 0; - r.y = 0; - } - return r; -} - -real_t TriangulatorPartition::Distance(const Vector2 &p1, const Vector2 &p2) { - real_t dx,dy; - dx = p2.x - p1.x; - dy = p2.y - p1.y; - return(sqrt(dx*dx + dy*dy)); -} - -//checks if two lines intersect -int TriangulatorPartition::Intersects(Vector2 &p11, Vector2 &p12, Vector2 &p21, Vector2 &p22) { - if((p11.x == p21.x)&&(p11.y == p21.y)) return 0; - if((p11.x == p22.x)&&(p11.y == p22.y)) return 0; - if((p12.x == p21.x)&&(p12.y == p21.y)) return 0; - if((p12.x == p22.x)&&(p12.y == p22.y)) return 0; - - Vector2 v1ort,v2ort,v; - real_t dot11,dot12,dot21,dot22; - - v1ort.x = p12.y-p11.y; - v1ort.y = p11.x-p12.x; - - v2ort.x = p22.y-p21.y; - v2ort.y = p21.x-p22.x; - - v = p21-p11; - dot21 = v.x*v1ort.x + v.y*v1ort.y; - v = p22-p11; - dot22 = v.x*v1ort.x + v.y*v1ort.y; - - v = p11-p21; - dot11 = v.x*v2ort.x + v.y*v2ort.y; - v = p12-p21; - dot12 = v.x*v2ort.x + v.y*v2ort.y; - - if(dot11*dot12>0) return 0; - if(dot21*dot22>0) return 0; - - return 1; -} - -//removes holes from inpolys by merging them with non-holes -int TriangulatorPartition::RemoveHoles(List<TriangulatorPoly> *inpolys, List<TriangulatorPoly> *outpolys) { - List<TriangulatorPoly> polys; - List<TriangulatorPoly>::Element *holeiter,*polyiter,*iter,*iter2; - long i,i2,holepointindex,polypointindex; - Vector2 holepoint,polypoint,bestpolypoint; - Vector2 linep1,linep2; - Vector2 v1,v2; - TriangulatorPoly newpoly; - bool hasholes; - bool pointvisible; - bool pointfound; - - //check for trivial case (no holes) - hasholes = false; - for(iter = inpolys->front(); iter; iter=iter->next()) { - if(iter->get().IsHole()) { - hasholes = true; - break; - } - } - if(!hasholes) { - for(iter = inpolys->front(); iter; iter=iter->next()) { - outpolys->push_back(iter->get()); - } - return 1; - } - - polys = *inpolys; - - while(1) { - //find the hole point with the largest x - hasholes = false; - for(iter = polys.front(); iter; iter=iter->next()) { - if(!iter->get().IsHole()) continue; - - if(!hasholes) { - hasholes = true; - holeiter = iter; - holepointindex = 0; - } - - for(i=0; i < iter->get().GetNumPoints(); i++) { - if(iter->get().GetPoint(i).x > holeiter->get().GetPoint(holepointindex).x) { - holeiter = iter; - holepointindex = i; - } - } - } - if(!hasholes) break; - holepoint = holeiter->get().GetPoint(holepointindex); - - pointfound = false; - for(iter = polys.front(); iter; iter=iter->next()) { - if(iter->get().IsHole()) continue; - for(i=0; i < iter->get().GetNumPoints(); i++) { - if(iter->get().GetPoint(i).x <= holepoint.x) continue; - if(!InCone(iter->get().GetPoint((i+iter->get().GetNumPoints()-1)%(iter->get().GetNumPoints())), - iter->get().GetPoint(i), - iter->get().GetPoint((i+1)%(iter->get().GetNumPoints())), - holepoint)) - continue; - polypoint = iter->get().GetPoint(i); - if(pointfound) { - v1 = Normalize(polypoint-holepoint); - v2 = Normalize(bestpolypoint-holepoint); - if(v2.x > v1.x) continue; - } - pointvisible = true; - for(iter2 = polys.front(); iter2; iter2=iter2->next()) { - if(iter2->get().IsHole()) continue; - for(i2=0; i2 < iter2->get().GetNumPoints(); i2++) { - linep1 = iter2->get().GetPoint(i2); - linep2 = iter2->get().GetPoint((i2+1)%(iter2->get().GetNumPoints())); - if(Intersects(holepoint,polypoint,linep1,linep2)) { - pointvisible = false; - break; - } - } - if(!pointvisible) break; - } - if(pointvisible) { - pointfound = true; - bestpolypoint = polypoint; - polyiter = iter; - polypointindex = i; - } - } - } - - if(!pointfound) return 0; - - newpoly.Init(holeiter->get().GetNumPoints() + polyiter->get().GetNumPoints() + 2); - i2 = 0; - for(i=0;i<=polypointindex;i++) { - newpoly[i2] = polyiter->get().GetPoint(i); - i2++; - } - for(i=0;i<=holeiter->get().GetNumPoints();i++) { - newpoly[i2] = holeiter->get().GetPoint((i+holepointindex)%holeiter->get().GetNumPoints()); - i2++; - } - for(i=polypointindex;i<polyiter->get().GetNumPoints();i++) { - newpoly[i2] = polyiter->get().GetPoint(i); - i2++; - } - - polys.erase(holeiter); - polys.erase(polyiter); - polys.push_back(newpoly); - } - - for(iter = polys.front(); iter; iter=iter->next()) { - outpolys->push_back(iter->get()); - } - - return 1; -} - -bool TriangulatorPartition::IsConvex(Vector2& p1, Vector2& p2, Vector2& p3) { - real_t tmp; - tmp = (p3.y-p1.y)*(p2.x-p1.x)-(p3.x-p1.x)*(p2.y-p1.y); - if(tmp>0) return 1; - else return 0; -} - -bool TriangulatorPartition::IsReflex(Vector2& p1, Vector2& p2, Vector2& p3) { - real_t tmp; - tmp = (p3.y-p1.y)*(p2.x-p1.x)-(p3.x-p1.x)*(p2.y-p1.y); - if(tmp<0) return 1; - else return 0; -} - -bool TriangulatorPartition::IsInside(Vector2& p1, Vector2& p2, Vector2& p3, Vector2 &p) { - if(IsConvex(p1,p,p2)) return false; - if(IsConvex(p2,p,p3)) return false; - if(IsConvex(p3,p,p1)) return false; - return true; -} - -bool TriangulatorPartition::InCone(Vector2 &p1, Vector2 &p2, Vector2 &p3, Vector2 &p) { - bool convex; - - convex = IsConvex(p1,p2,p3); - - if(convex) { - if(!IsConvex(p1,p2,p)) return false; - if(!IsConvex(p2,p3,p)) return false; - return true; - } else { - if(IsConvex(p1,p2,p)) return true; - if(IsConvex(p2,p3,p)) return true; - return false; - } -} - -bool TriangulatorPartition::InCone(PartitionVertex *v, Vector2 &p) { - Vector2 p1,p2,p3; - - p1 = v->previous->p; - p2 = v->p; - p3 = v->next->p; - - return InCone(p1,p2,p3,p); -} - -void TriangulatorPartition::UpdateVertexReflexity(PartitionVertex *v) { - PartitionVertex *v1,*v3; - v1 = v->previous; - v3 = v->next; - v->isConvex = !IsReflex(v1->p,v->p,v3->p); -} - -void TriangulatorPartition::UpdateVertex(PartitionVertex *v, PartitionVertex *vertices, long numvertices) { - long i; - PartitionVertex *v1,*v3; - Vector2 vec1,vec3; - - v1 = v->previous; - v3 = v->next; - - v->isConvex = IsConvex(v1->p,v->p,v3->p); - - vec1 = Normalize(v1->p - v->p); - vec3 = Normalize(v3->p - v->p); - v->angle = vec1.x*vec3.x + vec1.y*vec3.y; - - if(v->isConvex) { - v->isEar = true; - for(i=0;i<numvertices;i++) { - if((vertices[i].p.x==v->p.x)&&(vertices[i].p.y==v->p.y)) continue; - if((vertices[i].p.x==v1->p.x)&&(vertices[i].p.y==v1->p.y)) continue; - if((vertices[i].p.x==v3->p.x)&&(vertices[i].p.y==v3->p.y)) continue; - if(IsInside(v1->p,v->p,v3->p,vertices[i].p)) { - v->isEar = false; - break; - } - } - } else { - v->isEar = false; - } -} - -//triangulation by ear removal -int TriangulatorPartition::Triangulate_EC(TriangulatorPoly *poly, List<TriangulatorPoly> *triangles) { - long numvertices; - PartitionVertex *vertices; - PartitionVertex *ear; - TriangulatorPoly triangle; - long i,j; - bool earfound; - - if(poly->GetNumPoints() < 3) return 0; - if(poly->GetNumPoints() == 3) { - triangles->push_back(*poly); - return 1; - } - - numvertices = poly->GetNumPoints(); - - vertices = new PartitionVertex[numvertices]; - for(i=0;i<numvertices;i++) { - vertices[i].isActive = true; - vertices[i].p = poly->GetPoint(i); - if(i==(numvertices-1)) vertices[i].next=&(vertices[0]); - else vertices[i].next=&(vertices[i+1]); - if(i==0) vertices[i].previous = &(vertices[numvertices-1]); - else vertices[i].previous = &(vertices[i-1]); - } - for(i=0;i<numvertices;i++) { - UpdateVertex(&vertices[i],vertices,numvertices); - } - - for(i=0;i<numvertices-3;i++) { - earfound = false; - //find the most extruded ear - for(j=0;j<numvertices;j++) { - if(!vertices[j].isActive) continue; - if(!vertices[j].isEar) continue; - if(!earfound) { - earfound = true; - ear = &(vertices[j]); - } else { - if(vertices[j].angle > ear->angle) { - ear = &(vertices[j]); - } - } - } - if(!earfound) { - delete [] vertices; - return 0; - } - - triangle.Triangle(ear->previous->p,ear->p,ear->next->p); - triangles->push_back(triangle); - - ear->isActive = false; - ear->previous->next = ear->next; - ear->next->previous = ear->previous; - - if(i==numvertices-4) break; - - UpdateVertex(ear->previous,vertices,numvertices); - UpdateVertex(ear->next,vertices,numvertices); - } - for(i=0;i<numvertices;i++) { - if(vertices[i].isActive) { - triangle.Triangle(vertices[i].previous->p,vertices[i].p,vertices[i].next->p); - triangles->push_back(triangle); - break; - } - } - - delete [] vertices; - - return 1; -} - -int TriangulatorPartition::Triangulate_EC(List<TriangulatorPoly> *inpolys, List<TriangulatorPoly> *triangles) { - List<TriangulatorPoly> outpolys; - List<TriangulatorPoly>::Element*iter; - - if(!RemoveHoles(inpolys,&outpolys)) return 0; - for(iter=outpolys.front();iter;iter=iter->next()) { - if(!Triangulate_EC(&(iter->get()),triangles)) return 0; - } - return 1; -} - -int TriangulatorPartition::ConvexPartition_HM(TriangulatorPoly *poly, List<TriangulatorPoly> *parts) { - List<TriangulatorPoly> triangles; - List<TriangulatorPoly>::Element *iter1,*iter2; - TriangulatorPoly *poly1,*poly2; - TriangulatorPoly newpoly; - Vector2 d1,d2,p1,p2,p3; - long i11,i12,i21,i22,i13,i23,j,k; - bool isdiagonal; - long numreflex; - - //check if the poly is already convex - numreflex = 0; - for(i11=0;i11<poly->GetNumPoints();i11++) { - if(i11==0) i12 = poly->GetNumPoints()-1; - else i12=i11-1; - if(i11==(poly->GetNumPoints()-1)) i13=0; - else i13=i11+1; - if(IsReflex(poly->GetPoint(i12),poly->GetPoint(i11),poly->GetPoint(i13))) { - numreflex = 1; - break; - } - } - if(numreflex == 0) { - parts->push_back(*poly); - return 1; - } - - if(!Triangulate_EC(poly,&triangles)) return 0; - - for(iter1 = triangles.front(); iter1 ; iter1=iter1->next()) { - poly1 = &(iter1->get()); - for(i11=0;i11<poly1->GetNumPoints();i11++) { - d1 = poly1->GetPoint(i11); - i12 = (i11+1)%(poly1->GetNumPoints()); - d2 = poly1->GetPoint(i12); - - isdiagonal = false; - for(iter2 = iter1; iter2 ; iter2=iter2->next()) { - if(iter1 == iter2) continue; - poly2 = &(iter2->get()); - - for(i21=0;i21<poly2->GetNumPoints();i21++) { - if((d2.x != poly2->GetPoint(i21).x)||(d2.y != poly2->GetPoint(i21).y)) continue; - i22 = (i21+1)%(poly2->GetNumPoints()); - if((d1.x != poly2->GetPoint(i22).x)||(d1.y != poly2->GetPoint(i22).y)) continue; - isdiagonal = true; - break; - } - if(isdiagonal) break; - } - - if(!isdiagonal) continue; - - p2 = poly1->GetPoint(i11); - if(i11 == 0) i13 = poly1->GetNumPoints()-1; - else i13 = i11-1; - p1 = poly1->GetPoint(i13); - if(i22 == (poly2->GetNumPoints()-1)) i23 = 0; - else i23 = i22+1; - p3 = poly2->GetPoint(i23); - - if(!IsConvex(p1,p2,p3)) continue; - - p2 = poly1->GetPoint(i12); - if(i12 == (poly1->GetNumPoints()-1)) i13 = 0; - else i13 = i12+1; - p3 = poly1->GetPoint(i13); - if(i21 == 0) i23 = poly2->GetNumPoints()-1; - else i23 = i21-1; - p1 = poly2->GetPoint(i23); - - if(!IsConvex(p1,p2,p3)) continue; - - newpoly.Init(poly1->GetNumPoints()+poly2->GetNumPoints()-2); - k = 0; - for(j=i12;j!=i11;j=(j+1)%(poly1->GetNumPoints())) { - newpoly[k] = poly1->GetPoint(j); - k++; - } - for(j=i22;j!=i21;j=(j+1)%(poly2->GetNumPoints())) { - newpoly[k] = poly2->GetPoint(j); - k++; - } - - triangles.erase(iter2); - iter1->get() = newpoly; - poly1 = &(iter1->get()); - i11 = -1; - - continue; - } - } - - for(iter1 = triangles.front(); iter1 ; iter1=iter1->next()) { - parts->push_back(iter1->get()); - } - - return 1; -} - -int TriangulatorPartition::ConvexPartition_HM(List<TriangulatorPoly> *inpolys, List<TriangulatorPoly> *parts) { - List<TriangulatorPoly> outpolys; - List<TriangulatorPoly>::Element* iter; - - if(!RemoveHoles(inpolys,&outpolys)) return 0; - for(iter=outpolys.front();iter;iter=iter->next()) { - if(!ConvexPartition_HM(&(iter->get()),parts)) return 0; - } - return 1; -} - -//minimum-weight polygon triangulation by dynamic programming -//O(n^3) time complexity -//O(n^2) space complexity -int TriangulatorPartition::Triangulate_OPT(TriangulatorPoly *poly, List<TriangulatorPoly> *triangles) { - long i,j,k,gap,n; - DPState **dpstates; - Vector2 p1,p2,p3,p4; - long bestvertex; - real_t weight,minweight,d1,d2; - Diagonal diagonal,newdiagonal; - List<Diagonal> diagonals; - TriangulatorPoly triangle; - int ret = 1; - - n = poly->GetNumPoints(); - dpstates = new DPState *[n]; - for(i=1;i<n;i++) { - dpstates[i] = new DPState[i]; - } - - //init states and visibility - for(i=0;i<(n-1);i++) { - p1 = poly->GetPoint(i); - for(j=i+1;j<n;j++) { - dpstates[j][i].visible = true; - dpstates[j][i].weight = 0; - dpstates[j][i].bestvertex = -1; - if(j!=(i+1)) { - p2 = poly->GetPoint(j); - - //visibility check - if(i==0) p3 = poly->GetPoint(n-1); - else p3 = poly->GetPoint(i-1); - if(i==(n-1)) p4 = poly->GetPoint(0); - else p4 = poly->GetPoint(i+1); - if(!InCone(p3,p1,p4,p2)) { - dpstates[j][i].visible = false; - continue; - } - - if(j==0) p3 = poly->GetPoint(n-1); - else p3 = poly->GetPoint(j-1); - if(j==(n-1)) p4 = poly->GetPoint(0); - else p4 = poly->GetPoint(j+1); - if(!InCone(p3,p2,p4,p1)) { - dpstates[j][i].visible = false; - continue; - } - - for(k=0;k<n;k++) { - p3 = poly->GetPoint(k); - if(k==(n-1)) p4 = poly->GetPoint(0); - else p4 = poly->GetPoint(k+1); - if(Intersects(p1,p2,p3,p4)) { - dpstates[j][i].visible = false; - break; - } - } - } - } - } - dpstates[n-1][0].visible = true; - dpstates[n-1][0].weight = 0; - dpstates[n-1][0].bestvertex = -1; - - for(gap = 2; gap<n; gap++) { - for(i=0; i<(n-gap); i++) { - j = i+gap; - if(!dpstates[j][i].visible) continue; - bestvertex = -1; - for(k=(i+1);k<j;k++) { - if(!dpstates[k][i].visible) continue; - if(!dpstates[j][k].visible) continue; - - if(k<=(i+1)) d1=0; - else d1 = Distance(poly->GetPoint(i),poly->GetPoint(k)); - if(j<=(k+1)) d2=0; - else d2 = Distance(poly->GetPoint(k),poly->GetPoint(j)); - - weight = dpstates[k][i].weight + dpstates[j][k].weight + d1 + d2; - - if((bestvertex == -1)||(weight<minweight)) { - bestvertex = k; - minweight = weight; - } - } - if(bestvertex == -1) { - for(i=1;i<n;i++) { - delete [] dpstates[i]; - } - delete [] dpstates; - - return 0; - } - - dpstates[j][i].bestvertex = bestvertex; - dpstates[j][i].weight = minweight; - } - } - - newdiagonal.index1 = 0; - newdiagonal.index2 = n-1; - diagonals.push_back(newdiagonal); - while(!diagonals.empty()) { - diagonal = (diagonals.front()->get()); - diagonals.pop_front(); - bestvertex = dpstates[diagonal.index2][diagonal.index1].bestvertex; - if(bestvertex == -1) { - ret = 0; - break; - } - triangle.Triangle(poly->GetPoint(diagonal.index1),poly->GetPoint(bestvertex),poly->GetPoint(diagonal.index2)); - triangles->push_back(triangle); - if(bestvertex > (diagonal.index1+1)) { - newdiagonal.index1 = diagonal.index1; - newdiagonal.index2 = bestvertex; - diagonals.push_back(newdiagonal); - } - if(diagonal.index2 > (bestvertex+1)) { - newdiagonal.index1 = bestvertex; - newdiagonal.index2 = diagonal.index2; - diagonals.push_back(newdiagonal); - } - } - - for(i=1;i<n;i++) { - delete [] dpstates[i]; - } - delete [] dpstates; - - return ret; -} - -void TriangulatorPartition::UpdateState(long a, long b, long w, long i, long j, DPState2 **dpstates) { - Diagonal newdiagonal; - List<Diagonal> *pairs; - long w2; - - w2 = dpstates[a][b].weight; - if(w>w2) return; - - pairs = &(dpstates[a][b].pairs); - newdiagonal.index1 = i; - newdiagonal.index2 = j; - - if(w<w2) { - pairs->clear(); - pairs->push_front(newdiagonal); - dpstates[a][b].weight = w; - } else { - if((!pairs->empty())&&(i <= pairs->front()->get().index1)) return; - while((!pairs->empty())&&(pairs->front()->get().index2 >= j)) pairs->pop_front(); - pairs->push_front(newdiagonal); - } -} - -void TriangulatorPartition::TypeA(long i, long j, long k, PartitionVertex *vertices, DPState2 **dpstates) { - List<Diagonal> *pairs; - List<Diagonal>::Element *iter,*lastiter; - long top; - long w; - - if(!dpstates[i][j].visible) return; - top = j; - w = dpstates[i][j].weight; - if(k-j > 1) { - if (!dpstates[j][k].visible) return; - w += dpstates[j][k].weight + 1; - } - if(j-i > 1) { - pairs = &(dpstates[i][j].pairs); - iter = NULL; - lastiter = NULL; - while(iter!=pairs->front()) { - if (!iter) - iter=pairs->back(); - else - iter=iter->prev(); - - if(!IsReflex(vertices[iter->get().index2].p,vertices[j].p,vertices[k].p)) lastiter = iter; - else break; - } - if(lastiter == NULL) w++; - else { - if(IsReflex(vertices[k].p,vertices[i].p,vertices[lastiter->get().index1].p)) w++; - else top = lastiter->get().index1; - } - } - UpdateState(i,k,w,top,j,dpstates); -} - -void TriangulatorPartition::TypeB(long i, long j, long k, PartitionVertex *vertices, DPState2 **dpstates) { - List<Diagonal> *pairs; - List<Diagonal>::Element* iter,*lastiter; - long top; - long w; - - if(!dpstates[j][k].visible) return; - top = j; - w = dpstates[j][k].weight; - - if (j-i > 1) { - if (!dpstates[i][j].visible) return; - w += dpstates[i][j].weight + 1; - } - if (k-j > 1) { - pairs = &(dpstates[j][k].pairs); - - iter = pairs->front(); - if((!pairs->empty())&&(!IsReflex(vertices[i].p,vertices[j].p,vertices[iter->get().index1].p))) { - lastiter = iter; - while(iter!=NULL) { - if(!IsReflex(vertices[i].p,vertices[j].p,vertices[iter->get().index1].p)) { - lastiter = iter; - iter=iter->next(); - } - else break; - } - if(IsReflex(vertices[lastiter->get().index2].p,vertices[k].p,vertices[i].p)) w++; - else top = lastiter->get().index2; - } else w++; - } - UpdateState(i,k,w,j,top,dpstates); -} - -int TriangulatorPartition::ConvexPartition_OPT(TriangulatorPoly *poly, List<TriangulatorPoly> *parts) { - Vector2 p1,p2,p3,p4; - PartitionVertex *vertices; - DPState2 **dpstates; - long i,j,k,n,gap; - List<Diagonal> diagonals,diagonals2; - Diagonal diagonal,newdiagonal; - List<Diagonal> *pairs,*pairs2; - List<Diagonal>::Element* iter,*iter2; - int ret; - TriangulatorPoly newpoly; - List<long> indices; - List<long>::Element* iiter; - bool ijreal,jkreal; - - n = poly->GetNumPoints(); - vertices = new PartitionVertex[n]; - - dpstates = new DPState2 *[n]; - for(i=0;i<n;i++) { - dpstates[i] = new DPState2[n]; - } - - //init vertex information - for(i=0;i<n;i++) { - vertices[i].p = poly->GetPoint(i); - vertices[i].isActive = true; - if(i==0) vertices[i].previous = &(vertices[n-1]); - else vertices[i].previous = &(vertices[i-1]); - if(i==(poly->GetNumPoints()-1)) vertices[i].next = &(vertices[0]); - else vertices[i].next = &(vertices[i+1]); - } - for(i=1;i<n;i++) { - UpdateVertexReflexity(&(vertices[i])); - } - - //init states and visibility - for(i=0;i<(n-1);i++) { - p1 = poly->GetPoint(i); - for(j=i+1;j<n;j++) { - dpstates[i][j].visible = true; - if(j==i+1) { - dpstates[i][j].weight = 0; - } else { - dpstates[i][j].weight = 2147483647; - } - if(j!=(i+1)) { - p2 = poly->GetPoint(j); - - //visibility check - if(!InCone(&vertices[i],p2)) { - dpstates[i][j].visible = false; - continue; - } - if(!InCone(&vertices[j],p1)) { - dpstates[i][j].visible = false; - continue; - } - - for(k=0;k<n;k++) { - p3 = poly->GetPoint(k); - if(k==(n-1)) p4 = poly->GetPoint(0); - else p4 = poly->GetPoint(k+1); - if(Intersects(p1,p2,p3,p4)) { - dpstates[i][j].visible = false; - break; - } - } - } - } - } - for(i=0;i<(n-2);i++) { - j = i+2; - if(dpstates[i][j].visible) { - dpstates[i][j].weight = 0; - newdiagonal.index1 = i+1; - newdiagonal.index2 = i+1; - dpstates[i][j].pairs.push_back(newdiagonal); - } - } - - dpstates[0][n-1].visible = true; - vertices[0].isConvex = false; //by convention - - for(gap=3; gap<n; gap++) { - for(i=0;i<n-gap;i++) { - if(vertices[i].isConvex) continue; - k = i+gap; - if(dpstates[i][k].visible) { - if(!vertices[k].isConvex) { - for(j=i+1;j<k;j++) TypeA(i,j,k,vertices,dpstates); - } else { - for(j=i+1;j<(k-1);j++) { - if(vertices[j].isConvex) continue; - TypeA(i,j,k,vertices,dpstates); - } - TypeA(i,k-1,k,vertices,dpstates); - } - } - } - for(k=gap;k<n;k++) { - if(vertices[k].isConvex) continue; - i = k-gap; - if((vertices[i].isConvex)&&(dpstates[i][k].visible)) { - TypeB(i,i+1,k,vertices,dpstates); - for(j=i+2;j<k;j++) { - if(vertices[j].isConvex) continue; - TypeB(i,j,k,vertices,dpstates); - } - } - } - } - - - //recover solution - ret = 1; - newdiagonal.index1 = 0; - newdiagonal.index2 = n-1; - diagonals.push_front(newdiagonal); - while(!diagonals.empty()) { - diagonal = (diagonals.front()->get()); - diagonals.pop_front(); - if((diagonal.index2 - diagonal.index1) <=1) continue; - pairs = &(dpstates[diagonal.index1][diagonal.index2].pairs); - if(pairs->empty()) { - ret = 0; - break; - } - if(!vertices[diagonal.index1].isConvex) { - iter = pairs->back(); - - j = iter->get().index2; - newdiagonal.index1 = j; - newdiagonal.index2 = diagonal.index2; - diagonals.push_front(newdiagonal); - if((j - diagonal.index1)>1) { - if(iter->get().index1 != iter->get().index2) { - pairs2 = &(dpstates[diagonal.index1][j].pairs); - while(1) { - if(pairs2->empty()) { - ret = 0; - break; - } - iter2 = pairs2->back(); - - if(iter->get().index1 != iter2->get().index1) pairs2->pop_back(); - else break; - } - if(ret == 0) break; - } - newdiagonal.index1 = diagonal.index1; - newdiagonal.index2 = j; - diagonals.push_front(newdiagonal); - } - } else { - iter = pairs->front(); - j = iter->get().index1; - newdiagonal.index1 = diagonal.index1; - newdiagonal.index2 = j; - diagonals.push_front(newdiagonal); - if((diagonal.index2 - j) > 1) { - if(iter->get().index1 != iter->get().index2) { - pairs2 = &(dpstates[j][diagonal.index2].pairs); - while(1) { - if(pairs2->empty()) { - ret = 0; - break; - } - iter2 = pairs2->front(); - if(iter->get().index2 != iter2->get().index2) pairs2->pop_front(); - else break; - } - if(ret == 0) break; - } - newdiagonal.index1 = j; - newdiagonal.index2 = diagonal.index2; - diagonals.push_front(newdiagonal); - } - } - } - - if(ret == 0) { - for(i=0;i<n;i++) { - delete [] dpstates[i]; - } - delete [] dpstates; - delete [] vertices; - - return ret; - } - - newdiagonal.index1 = 0; - newdiagonal.index2 = n-1; - diagonals.push_front(newdiagonal); - while(!diagonals.empty()) { - diagonal = (diagonals.front())->get(); - diagonals.pop_front(); - if((diagonal.index2 - diagonal.index1) <= 1) continue; - - indices.clear(); - diagonals2.clear(); - indices.push_back(diagonal.index1); - indices.push_back(diagonal.index2); - diagonals2.push_front(diagonal); - - while(!diagonals2.empty()) { - diagonal = (diagonals2.front()->get()); - diagonals2.pop_front(); - if((diagonal.index2 - diagonal.index1) <= 1) continue; - ijreal = true; - jkreal = true; - pairs = &(dpstates[diagonal.index1][diagonal.index2].pairs); - if(!vertices[diagonal.index1].isConvex) { - iter = pairs->back(); - j = iter->get().index2; - if(iter->get().index1 != iter->get().index2) ijreal = false; - } else { - iter = pairs->front(); - j = iter->get().index1; - if(iter->get().index1 != iter->get().index2) jkreal = false; - } - - newdiagonal.index1 = diagonal.index1; - newdiagonal.index2 = j; - if(ijreal) { - diagonals.push_back(newdiagonal); - } else { - diagonals2.push_back(newdiagonal); - } - - newdiagonal.index1 = j; - newdiagonal.index2 = diagonal.index2; - if(jkreal) { - diagonals.push_back(newdiagonal); - } else { - diagonals2.push_back(newdiagonal); - } - - indices.push_back(j); - } - - indices.sort(); - newpoly.Init((long)indices.size()); - k=0; - for(iiter = indices.front();iiter;iiter=iiter->next()) { - newpoly[k] = vertices[iiter->get()].p; - k++; - } - parts->push_back(newpoly); - } - - for(i=0;i<n;i++) { - delete [] dpstates[i]; - } - delete [] dpstates; - delete [] vertices; - - return ret; -} - -//triangulates a set of polygons by first partitioning them into monotone polygons -//O(n*log(n)) time complexity, O(n) space complexity -//the algorithm used here is outlined in the book -//"Computational Geometry: Algorithms and Applications" -//by Mark de Berg, Otfried Cheong, Marc van Kreveld and Mark Overmars -int TriangulatorPartition::MonotonePartition(List<TriangulatorPoly> *inpolys, List<TriangulatorPoly> *monotonePolys) { - List<TriangulatorPoly>::Element *iter; - MonotoneVertex *vertices; - long i,numvertices,vindex,vindex2,newnumvertices,maxnumvertices; - long polystartindex, polyendindex; - TriangulatorPoly *poly; - MonotoneVertex *v,*v2,*vprev,*vnext; - ScanLineEdge newedge; - bool error = false; - - numvertices = 0; - for(iter = inpolys->front(); iter ; iter=iter->next()) { - numvertices += iter->get().GetNumPoints(); - } - - maxnumvertices = numvertices*3; - vertices = new MonotoneVertex[maxnumvertices]; - newnumvertices = numvertices; - - polystartindex = 0; - for(iter = inpolys->front(); iter ; iter=iter->next()) { - poly = &(iter->get()); - polyendindex = polystartindex + poly->GetNumPoints()-1; - for(i=0;i<poly->GetNumPoints();i++) { - vertices[i+polystartindex].p = poly->GetPoint(i); - if(i==0) vertices[i+polystartindex].previous = polyendindex; - else vertices[i+polystartindex].previous = i+polystartindex-1; - if(i==(poly->GetNumPoints()-1)) vertices[i+polystartindex].next = polystartindex; - else vertices[i+polystartindex].next = i+polystartindex+1; - } - polystartindex = polyendindex+1; - } - - //construct the priority queue - long *priority = new long [numvertices]; - for(i=0;i<numvertices;i++) priority[i] = i; - SortArray<long,VertexSorter> sorter; - sorter.compare.vertices=vertices; - sorter.sort(priority,numvertices); - - //determine vertex types - char *vertextypes = new char[maxnumvertices]; - for(i=0;i<numvertices;i++) { - v = &(vertices[i]); - vprev = &(vertices[v->previous]); - vnext = &(vertices[v->next]); - - if(Below(vprev->p,v->p)&&Below(vnext->p,v->p)) { - if(IsConvex(vnext->p,vprev->p,v->p)) { - vertextypes[i] = TRIANGULATOR_VERTEXTYPE_START; - } else { - vertextypes[i] = TRIANGULATOR_VERTEXTYPE_SPLIT; - } - } else if(Below(v->p,vprev->p)&&Below(v->p,vnext->p)) { - if(IsConvex(vnext->p,vprev->p,v->p)) - { - vertextypes[i] = TRIANGULATOR_VERTEXTYPE_END; - } else { - vertextypes[i] = TRIANGULATOR_VERTEXTYPE_MERGE; - } - } else { - vertextypes[i] = TRIANGULATOR_VERTEXTYPE_REGULAR; - } - } - - //helpers - long *helpers = new long[maxnumvertices]; - - //binary search tree that holds edges intersecting the scanline - //note that while set doesn't actually have to be implemented as a tree - //complexity requirements for operations are the same as for the balanced binary search tree - Set<ScanLineEdge> edgeTree; - //store iterators to the edge tree elements - //this makes deleting existing edges much faster - Set<ScanLineEdge>::Element **edgeTreeIterators,*edgeIter; - edgeTreeIterators = new Set<ScanLineEdge>::Element*[maxnumvertices]; - //Pair<Set<ScanLineEdge>::Element*,bool> edgeTreeRet; - for(i = 0; i<numvertices; i++) edgeTreeIterators[i] = NULL; - - //for each vertex - for(i=0;i<numvertices;i++) { - vindex = priority[i]; - v = &(vertices[vindex]); - vindex2 = vindex; - v2 = v; - - //depending on the vertex type, do the appropriate action - //comments in the following sections are copied from "Computational Geometry: Algorithms and Applications" - switch(vertextypes[vindex]) { - case TRIANGULATOR_VERTEXTYPE_START: - //Insert ei in T and set helper(ei) to vi. - newedge.p1 = v->p; - newedge.p2 = vertices[v->next].p; - newedge.index = vindex; - edgeTreeIterators[vindex] = edgeTree.insert(newedge); - helpers[vindex] = vindex; - break; - - case TRIANGULATOR_VERTEXTYPE_END: - //if helper(ei-1) is a merge vertex - if(vertextypes[helpers[v->previous]]==TRIANGULATOR_VERTEXTYPE_MERGE) { - //Insert the diagonal connecting vi to helper(ei-1) in D. - AddDiagonal(vertices,&newnumvertices,vindex,helpers[v->previous], - vertextypes, edgeTreeIterators, &edgeTree, helpers); - } - //Delete ei-1 from T - edgeTree.erase(edgeTreeIterators[v->previous]); - break; - - case TRIANGULATOR_VERTEXTYPE_SPLIT: - //Search in T to find the edge e j directly left of vi. - newedge.p1 = v->p; - newedge.p2 = v->p; - edgeIter = edgeTree.lower_bound(newedge); - if(edgeIter == edgeTree.front()) { - error = true; - break; - } - edgeIter=edgeIter->prev(); - //Insert the diagonal connecting vi to helper(ej) in D. - AddDiagonal(vertices,&newnumvertices,vindex,helpers[edgeIter->get().index], - vertextypes, edgeTreeIterators, &edgeTree, helpers); - vindex2 = newnumvertices-2; - v2 = &(vertices[vindex2]); - //helper(e j)�vi - helpers[edgeIter->get().index] = vindex; - //Insert ei in T and set helper(ei) to vi. - newedge.p1 = v2->p; - newedge.p2 = vertices[v2->next].p; - newedge.index = vindex2; - - edgeTreeIterators[vindex2] = edgeTree.insert(newedge); - helpers[vindex2] = vindex2; - break; - - case TRIANGULATOR_VERTEXTYPE_MERGE: - //if helper(ei-1) is a merge vertex - if(vertextypes[helpers[v->previous]]==TRIANGULATOR_VERTEXTYPE_MERGE) { - //Insert the diagonal connecting vi to helper(ei-1) in D. - AddDiagonal(vertices,&newnumvertices,vindex,helpers[v->previous], - vertextypes, edgeTreeIterators, &edgeTree, helpers); - vindex2 = newnumvertices-2; - v2 = &(vertices[vindex2]); - } - //Delete ei-1 from T. - edgeTree.erase(edgeTreeIterators[v->previous]); - //Search in T to find the edge e j directly left of vi. - newedge.p1 = v->p; - newedge.p2 = v->p; - edgeIter = edgeTree.lower_bound(newedge); - if(edgeIter == edgeTree.front()) { - error = true; - break; - } - edgeIter=edgeIter->prev(); - //if helper(ej) is a merge vertex - if(vertextypes[helpers[edgeIter->get().index]]==TRIANGULATOR_VERTEXTYPE_MERGE) { - //Insert the diagonal connecting vi to helper(e j) in D. - AddDiagonal(vertices,&newnumvertices,vindex2,helpers[edgeIter->get().index], - vertextypes, edgeTreeIterators, &edgeTree, helpers); - } - //helper(e j)�vi - helpers[edgeIter->get().index] = vindex2; - break; - - case TRIANGULATOR_VERTEXTYPE_REGULAR: - //if the interior of P lies to the right of vi - if(Below(v->p,vertices[v->previous].p)) { - //if helper(ei-1) is a merge vertex - if(vertextypes[helpers[v->previous]]==TRIANGULATOR_VERTEXTYPE_MERGE) { - //Insert the diagonal connecting vi to helper(ei-1) in D. - AddDiagonal(vertices,&newnumvertices,vindex,helpers[v->previous], - vertextypes, edgeTreeIterators, &edgeTree, helpers); - vindex2 = newnumvertices-2; - v2 = &(vertices[vindex2]); - } - //Delete ei-1 from T. - edgeTree.erase(edgeTreeIterators[v->previous]); - //Insert ei in T and set helper(ei) to vi. - newedge.p1 = v2->p; - newedge.p2 = vertices[v2->next].p; - newedge.index = vindex2; - edgeTreeIterators[vindex2] = edgeTree.insert(newedge); - helpers[vindex2] = vindex; - } else { - //Search in T to find the edge ej directly left of vi. - newedge.p1 = v->p; - newedge.p2 = v->p; - edgeIter = edgeTree.lower_bound(newedge); - if(edgeIter == edgeTree.front()) { - error = true; - break; - } - edgeIter=edgeIter->prev(); - //if helper(ej) is a merge vertex - if(vertextypes[helpers[edgeIter->get().index]]==TRIANGULATOR_VERTEXTYPE_MERGE) { - //Insert the diagonal connecting vi to helper(e j) in D. - AddDiagonal(vertices,&newnumvertices,vindex,helpers[edgeIter->get().index], - vertextypes, edgeTreeIterators, &edgeTree, helpers); - } - //helper(e j)�vi - helpers[edgeIter->get().index] = vindex; - } - break; - } - - if(error) break; - } - - char *used = new char[newnumvertices]; - memset(used,0,newnumvertices*sizeof(char)); - - if(!error) { - //return result - long size; - TriangulatorPoly mpoly; - for(i=0;i<newnumvertices;i++) { - if(used[i]) continue; - v = &(vertices[i]); - vnext = &(vertices[v->next]); - size = 1; - while(vnext!=v) { - vnext = &(vertices[vnext->next]); - size++; - } - mpoly.Init(size); - v = &(vertices[i]); - mpoly[0] = v->p; - vnext = &(vertices[v->next]); - size = 1; - used[i] = 1; - used[v->next] = 1; - while(vnext!=v) { - mpoly[size] = vnext->p; - used[vnext->next] = 1; - vnext = &(vertices[vnext->next]); - size++; - } - monotonePolys->push_back(mpoly); - } - } - - //cleanup - delete [] vertices; - delete [] priority; - delete [] vertextypes; - delete [] edgeTreeIterators; - delete [] helpers; - delete [] used; - - if(error) { - return 0; - } else { - return 1; - } -} - -//adds a diagonal to the doubly-connected list of vertices -void TriangulatorPartition::AddDiagonal(MonotoneVertex *vertices, long *numvertices, long index1, long index2, - char *vertextypes, Set<ScanLineEdge>::Element **edgeTreeIterators, - Set<ScanLineEdge> *edgeTree, long *helpers) -{ - long newindex1,newindex2; - - newindex1 = *numvertices; - (*numvertices)++; - newindex2 = *numvertices; - (*numvertices)++; - - vertices[newindex1].p = vertices[index1].p; - vertices[newindex2].p = vertices[index2].p; - - vertices[newindex2].next = vertices[index2].next; - vertices[newindex1].next = vertices[index1].next; - - vertices[vertices[index2].next].previous = newindex2; - vertices[vertices[index1].next].previous = newindex1; - - vertices[index1].next = newindex2; - vertices[newindex2].previous = index1; - - vertices[index2].next = newindex1; - vertices[newindex1].previous = index2; - - //update all relevant structures - vertextypes[newindex1] = vertextypes[index1]; - edgeTreeIterators[newindex1] = edgeTreeIterators[index1]; - helpers[newindex1] = helpers[index1]; - if(edgeTreeIterators[newindex1] != NULL) - edgeTreeIterators[newindex1]->get().index = newindex1; - vertextypes[newindex2] = vertextypes[index2]; - edgeTreeIterators[newindex2] = edgeTreeIterators[index2]; - helpers[newindex2] = helpers[index2]; - if(edgeTreeIterators[newindex2] != NULL) - edgeTreeIterators[newindex2]->get().index = newindex2; -} - -bool TriangulatorPartition::Below(Vector2 &p1, Vector2 &p2) { - if(p1.y < p2.y) return true; - else if(p1.y == p2.y) { - if(p1.x < p2.x) return true; - } - return false; -} - - - - - -//sorts in the falling order of y values, if y is equal, x is used instead -bool TriangulatorPartition::VertexSorter::operator() (long index1, long index2) const { - if(vertices[index1].p.y > vertices[index2].p.y) return true; - else if(vertices[index1].p.y == vertices[index2].p.y) { - if(vertices[index1].p.x > vertices[index2].p.x) return true; - } - return false; -} - -bool TriangulatorPartition::ScanLineEdge::IsConvex(const Vector2& p1, const Vector2& p2, const Vector2& p3) const { - real_t tmp; - tmp = (p3.y-p1.y)*(p2.x-p1.x)-(p3.x-p1.x)*(p2.y-p1.y); - if(tmp>0) return 1; - else return 0; -} - -bool TriangulatorPartition::ScanLineEdge::operator < (const ScanLineEdge & other) const { - if(other.p1.y == other.p2.y) { - if(p1.y == p2.y) { - if(p1.y < other.p1.y) return true; - else return false; - } - if(IsConvex(p1,p2,other.p1)) return true; - else return false; - } else if(p1.y == p2.y) { - if(IsConvex(other.p1,other.p2,p1)) return false; - else return true; - } else if(p1.y < other.p1.y) { - if(IsConvex(other.p1,other.p2,p1)) return false; - else return true; - } else { - if(IsConvex(p1,p2,other.p1)) return true; - else return false; - } -} - -//triangulates monotone polygon -//O(n) time, O(n) space complexity -int TriangulatorPartition::TriangulateMonotone(TriangulatorPoly *inPoly, List<TriangulatorPoly> *triangles) { - long i,i2,j,topindex,bottomindex,leftindex,rightindex,vindex; - Vector2 *points; - long numpoints; - TriangulatorPoly triangle; - - numpoints = inPoly->GetNumPoints(); - points = inPoly->GetPoints(); - - //trivial calses - if(numpoints < 3) return 0; - if(numpoints == 3) { - triangles->push_back(*inPoly); - } - - topindex = 0; bottomindex=0; - for(i=1;i<numpoints;i++) { - if(Below(points[i],points[bottomindex])) bottomindex = i; - if(Below(points[topindex],points[i])) topindex = i; - } - - //check if the poly is really monotone - i = topindex; - while(i!=bottomindex) { - i2 = i+1; if(i2>=numpoints) i2 = 0; - if(!Below(points[i2],points[i])) return 0; - i = i2; - } - i = bottomindex; - while(i!=topindex) { - i2 = i+1; if(i2>=numpoints) i2 = 0; - if(!Below(points[i],points[i2])) return 0; - i = i2; - } - - char *vertextypes = new char[numpoints]; - long *priority = new long[numpoints]; - - //merge left and right vertex chains - priority[0] = topindex; - vertextypes[topindex] = 0; - leftindex = topindex+1; if(leftindex>=numpoints) leftindex = 0; - rightindex = topindex-1; if(rightindex<0) rightindex = numpoints-1; - for(i=1;i<(numpoints-1);i++) { - if(leftindex==bottomindex) { - priority[i] = rightindex; - rightindex--; if(rightindex<0) rightindex = numpoints-1; - vertextypes[priority[i]] = -1; - } else if(rightindex==bottomindex) { - priority[i] = leftindex; - leftindex++; if(leftindex>=numpoints) leftindex = 0; - vertextypes[priority[i]] = 1; - } else { - if(Below(points[leftindex],points[rightindex])) { - priority[i] = rightindex; - rightindex--; if(rightindex<0) rightindex = numpoints-1; - vertextypes[priority[i]] = -1; - } else { - priority[i] = leftindex; - leftindex++; if(leftindex>=numpoints) leftindex = 0; - vertextypes[priority[i]] = 1; - } - } - } - priority[i] = bottomindex; - vertextypes[bottomindex] = 0; - - long *stack = new long[numpoints]; - long stackptr = 0; - - stack[0] = priority[0]; - stack[1] = priority[1]; - stackptr = 2; - - //for each vertex from top to bottom trim as many triangles as possible - for(i=2;i<(numpoints-1);i++) { - vindex = priority[i]; - if(vertextypes[vindex]!=vertextypes[stack[stackptr-1]]) { - for(j=0;j<(stackptr-1);j++) { - if(vertextypes[vindex]==1) { - triangle.Triangle(points[stack[j+1]],points[stack[j]],points[vindex]); - } else { - triangle.Triangle(points[stack[j]],points[stack[j+1]],points[vindex]); - } - triangles->push_back(triangle); - } - stack[0] = priority[i-1]; - stack[1] = priority[i]; - stackptr = 2; - } else { - stackptr--; - while(stackptr>0) { - if(vertextypes[vindex]==1) { - if(IsConvex(points[vindex],points[stack[stackptr-1]],points[stack[stackptr]])) { - triangle.Triangle(points[vindex],points[stack[stackptr-1]],points[stack[stackptr]]); - triangles->push_back(triangle); - stackptr--; - } else { - break; - } - } else { - if(IsConvex(points[vindex],points[stack[stackptr]],points[stack[stackptr-1]])) { - triangle.Triangle(points[vindex],points[stack[stackptr]],points[stack[stackptr-1]]); - triangles->push_back(triangle); - stackptr--; - } else { - break; - } - } - } - stackptr++; - stack[stackptr] = vindex; - stackptr++; - } - } - vindex = priority[i]; - for(j=0;j<(stackptr-1);j++) { - if(vertextypes[stack[j+1]]==1) { - triangle.Triangle(points[stack[j]],points[stack[j+1]],points[vindex]); - } else { - triangle.Triangle(points[stack[j+1]],points[stack[j]],points[vindex]); - } - triangles->push_back(triangle); - } - - delete [] priority; - delete [] vertextypes; - delete [] stack; - - return 1; -} - -int TriangulatorPartition::Triangulate_MONO(List<TriangulatorPoly> *inpolys, List<TriangulatorPoly> *triangles) { - List<TriangulatorPoly> monotone; - List<TriangulatorPoly>::Element* iter; - - if(!MonotonePartition(inpolys,&monotone)) return 0; - for(iter = monotone.front(); iter;iter=iter->next()) { - if(!TriangulateMonotone(&(iter->get()),triangles)) return 0; - } - return 1; -} - -int TriangulatorPartition::Triangulate_MONO(TriangulatorPoly *poly, List<TriangulatorPoly> *triangles) { - List<TriangulatorPoly> polys; - polys.push_back(*poly); - - return Triangulate_MONO(&polys, triangles); -} diff --git a/core/math/triangulator.h b/core/math/triangulator.h deleted file mode 100644 index b6dd7e8236..0000000000 --- a/core/math/triangulator.h +++ /dev/null @@ -1,306 +0,0 @@ -//Copyright (C) 2011 by Ivan Fratric -// -//Permission is hereby granted, free of charge, to any person obtaining a copy -//of this software and associated documentation files (the "Software"), to deal -//in the Software without restriction, including without limitation the rights -//to use, copy, modify, merge, publish, distribute, sublicense, and/or sell -//copies of the Software, and to permit persons to whom the Software is -//furnished to do so, subject to the following conditions: -// -//The above copyright notice and this permission notice shall be included in -//all copies or substantial portions of the Software. -// -//THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR -//IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, -//FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE -//AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER -//LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, -//OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN -//THE SOFTWARE. - -#ifndef TRIANGULATOR_H -#define TRIANGULATOR_H - -#include "math_2d.h" -#include "list.h" -#include "set.h" -//2D point structure - - -#define TRIANGULATOR_CCW 1 -#define TRIANGULATOR_CW -1 -//Polygon implemented as an array of points with a 'hole' flag -class TriangulatorPoly { -protected: - - - - Vector2 *points; - long numpoints; - bool hole; - -public: - - //constructors/destructors - TriangulatorPoly(); - ~TriangulatorPoly(); - - TriangulatorPoly(const TriangulatorPoly &src); - TriangulatorPoly& operator=(const TriangulatorPoly &src); - - //getters and setters - long GetNumPoints() { - return numpoints; - } - - bool IsHole() { - return hole; - } - - void SetHole(bool hole) { - this->hole = hole; - } - - Vector2 &GetPoint(long i) { - return points[i]; - } - - Vector2 *GetPoints() { - return points; - } - - Vector2& operator[] (int i) { - return points[i]; - } - - //clears the polygon points - void Clear(); - - //inits the polygon with numpoints vertices - void Init(long numpoints); - - //creates a triangle with points p1,p2,p3 - void Triangle(Vector2 &p1, Vector2 &p2, Vector2 &p3); - - //inverts the orfer of vertices - void Invert(); - - //returns the orientation of the polygon - //possible values: - // Triangulator_CCW : polygon vertices are in counter-clockwise order - // Triangulator_CW : polygon vertices are in clockwise order - // 0 : the polygon has no (measurable) area - int GetOrientation(); - - //sets the polygon orientation - //orientation can be - // Triangulator_CCW : sets vertices in counter-clockwise order - // Triangulator_CW : sets vertices in clockwise order - void SetOrientation(int orientation); -}; - -class TriangulatorPartition { -protected: - struct PartitionVertex { - bool isActive; - bool isConvex; - bool isEar; - - Vector2 p; - real_t angle; - PartitionVertex *previous; - PartitionVertex *next; - }; - - struct MonotoneVertex { - Vector2 p; - long previous; - long next; - }; - - struct VertexSorter{ - mutable MonotoneVertex *vertices; - bool operator() (long index1, long index2) const; - }; - - struct Diagonal { - long index1; - long index2; - }; - - //dynamic programming state for minimum-weight triangulation - struct DPState { - bool visible; - real_t weight; - long bestvertex; - }; - - //dynamic programming state for convex partitioning - struct DPState2 { - bool visible; - long weight; - List<Diagonal> pairs; - }; - - //edge that intersects the scanline - struct ScanLineEdge { - mutable long index; - Vector2 p1; - Vector2 p2; - - //determines if the edge is to the left of another edge - bool operator< (const ScanLineEdge & other) const; - - bool IsConvex(const Vector2& p1, const Vector2& p2, const Vector2& p3) const; - }; - - //standard helper functions - bool IsConvex(Vector2& p1, Vector2& p2, Vector2& p3); - bool IsReflex(Vector2& p1, Vector2& p2, Vector2& p3); - bool IsInside(Vector2& p1, Vector2& p2, Vector2& p3, Vector2 &p); - - bool InCone(Vector2 &p1, Vector2 &p2, Vector2 &p3, Vector2 &p); - bool InCone(PartitionVertex *v, Vector2 &p); - - int Intersects(Vector2 &p11, Vector2 &p12, Vector2 &p21, Vector2 &p22); - - Vector2 Normalize(const Vector2 &p); - real_t Distance(const Vector2 &p1, const Vector2 &p2); - - //helper functions for Triangulate_EC - void UpdateVertexReflexity(PartitionVertex *v); - void UpdateVertex(PartitionVertex *v,PartitionVertex *vertices, long numvertices); - - //helper functions for ConvexPartition_OPT - void UpdateState(long a, long b, long w, long i, long j, DPState2 **dpstates); - void TypeA(long i, long j, long k, PartitionVertex *vertices, DPState2 **dpstates); - void TypeB(long i, long j, long k, PartitionVertex *vertices, DPState2 **dpstates); - - //helper functions for MonotonePartition - bool Below(Vector2 &p1, Vector2 &p2); - void AddDiagonal(MonotoneVertex *vertices, long *numvertices, long index1, long index2, - char *vertextypes, Set<ScanLineEdge>::Element **edgeTreeIterators, - Set<ScanLineEdge> *edgeTree, long *helpers); - - //triangulates a monotone polygon, used in Triangulate_MONO - int TriangulateMonotone(TriangulatorPoly *inPoly, List<TriangulatorPoly> *triangles); - -public: - - //simple heuristic procedure for removing holes from a list of polygons - //works by creating a diagonal from the rightmost hole vertex to some visible vertex - //time complexity: O(h*(n^2)), h is the number of holes, n is the number of vertices - //space complexity: O(n) - //params: - // inpolys : a list of polygons that can contain holes - // vertices of all non-hole polys have to be in counter-clockwise order - // vertices of all hole polys have to be in clockwise order - // outpolys : a list of polygons without holes - //returns 1 on success, 0 on failure - int RemoveHoles(List<TriangulatorPoly> *inpolys, List<TriangulatorPoly> *outpolys); - - //triangulates a polygon by ear clipping - //time complexity O(n^2), n is the number of vertices - //space complexity: O(n) - //params: - // poly : an input polygon to be triangulated - // vertices have to be in counter-clockwise order - // triangles : a list of triangles (result) - //returns 1 on success, 0 on failure - int Triangulate_EC(TriangulatorPoly *poly, List<TriangulatorPoly> *triangles); - - //triangulates a list of polygons that may contain holes by ear clipping algorithm - //first calls RemoveHoles to get rid of the holes, and then Triangulate_EC for each resulting polygon - //time complexity: O(h*(n^2)), h is the number of holes, n is the number of vertices - //space complexity: O(n) - //params: - // inpolys : a list of polygons to be triangulated (can contain holes) - // vertices of all non-hole polys have to be in counter-clockwise order - // vertices of all hole polys have to be in clockwise order - // triangles : a list of triangles (result) - //returns 1 on success, 0 on failure - int Triangulate_EC(List<TriangulatorPoly> *inpolys, List<TriangulatorPoly> *triangles); - - //creates an optimal polygon triangulation in terms of minimal edge length - //time complexity: O(n^3), n is the number of vertices - //space complexity: O(n^2) - //params: - // poly : an input polygon to be triangulated - // vertices have to be in counter-clockwise order - // triangles : a list of triangles (result) - //returns 1 on success, 0 on failure - int Triangulate_OPT(TriangulatorPoly *poly, List<TriangulatorPoly> *triangles); - - //triangulates a polygons by firstly partitioning it into monotone polygons - //time complexity: O(n*log(n)), n is the number of vertices - //space complexity: O(n) - //params: - // poly : an input polygon to be triangulated - // vertices have to be in counter-clockwise order - // triangles : a list of triangles (result) - //returns 1 on success, 0 on failure - int Triangulate_MONO(TriangulatorPoly *poly, List<TriangulatorPoly> *triangles); - - //triangulates a list of polygons by firstly partitioning them into monotone polygons - //time complexity: O(n*log(n)), n is the number of vertices - //space complexity: O(n) - //params: - // inpolys : a list of polygons to be triangulated (can contain holes) - // vertices of all non-hole polys have to be in counter-clockwise order - // vertices of all hole polys have to be in clockwise order - // triangles : a list of triangles (result) - //returns 1 on success, 0 on failure - int Triangulate_MONO(List<TriangulatorPoly> *inpolys, List<TriangulatorPoly> *triangles); - - //creates a monotone partition of a list of polygons that can contain holes - //time complexity: O(n*log(n)), n is the number of vertices - //space complexity: O(n) - //params: - // inpolys : a list of polygons to be triangulated (can contain holes) - // vertices of all non-hole polys have to be in counter-clockwise order - // vertices of all hole polys have to be in clockwise order - // monotonePolys : a list of monotone polygons (result) - //returns 1 on success, 0 on failure - int MonotonePartition(List<TriangulatorPoly> *inpolys, List<TriangulatorPoly> *monotonePolys); - - //partitions a polygon into convex polygons by using Hertel-Mehlhorn algorithm - //the algorithm gives at most four times the number of parts as the optimal algorithm - //however, in practice it works much better than that and often gives optimal partition - //uses triangulation obtained by ear clipping as intermediate result - //time complexity O(n^2), n is the number of vertices - //space complexity: O(n) - //params: - // poly : an input polygon to be partitioned - // vertices have to be in counter-clockwise order - // parts : resulting list of convex polygons - //returns 1 on success, 0 on failure - int ConvexPartition_HM(TriangulatorPoly *poly, List<TriangulatorPoly> *parts); - - //partitions a list of polygons into convex parts by using Hertel-Mehlhorn algorithm - //the algorithm gives at most four times the number of parts as the optimal algorithm - //however, in practice it works much better than that and often gives optimal partition - //uses triangulation obtained by ear clipping as intermediate result - //time complexity O(n^2), n is the number of vertices - //space complexity: O(n) - //params: - // inpolys : an input list of polygons to be partitioned - // vertices of all non-hole polys have to be in counter-clockwise order - // vertices of all hole polys have to be in clockwise order - // parts : resulting list of convex polygons - //returns 1 on success, 0 on failure - int ConvexPartition_HM(List<TriangulatorPoly> *inpolys, List<TriangulatorPoly> *parts); - - //optimal convex partitioning (in terms of number of resulting convex polygons) - //using the Keil-Snoeyink algorithm - //M. Keil, J. Snoeyink, "On the time bound for convex decomposition of simple polygons", 1998 - //time complexity O(n^3), n is the number of vertices - //space complexity: O(n^3) - // poly : an input polygon to be partitioned - // vertices have to be in counter-clockwise order - // parts : resulting list of convex polygons - //returns 1 on success, 0 on failure - int ConvexPartition_OPT(TriangulatorPoly *poly, List<TriangulatorPoly> *parts); -}; - - -#endif diff --git a/core/math/vector3.cpp b/core/math/vector3.cpp index 235840e06a..e413cc147d 100644 --- a/core/math/vector3.cpp +++ b/core/math/vector3.cpp @@ -6,6 +6,7 @@ /* http://www.godotengine.org */ /*************************************************************************/ /* Copyright (c) 2007-2017 Juan Linietsky, Ariel Manzur. */ +/* Copyright (c) 2014-2017 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/vector3.h b/core/math/vector3.h index fc02e66c33..5f4390fbd1 100644 --- a/core/math/vector3.h +++ b/core/math/vector3.h @@ -6,6 +6,7 @@ /* http://www.godotengine.org */ /*************************************************************************/ /* Copyright (c) 2007-2017 Juan Linietsky, Ariel Manzur. */ +/* Copyright (c) 2014-2017 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 */ @@ -75,6 +76,7 @@ struct Vector3 { _FORCE_INLINE_ void normalize(); _FORCE_INLINE_ Vector3 normalized() const; + _FORCE_INLINE_ bool is_normalized() const; _FORCE_INLINE_ Vector3 inverse() const; _FORCE_INLINE_ void zero(); @@ -106,6 +108,7 @@ struct Vector3 { _FORCE_INLINE_ real_t angle_to(const Vector3 &p_b) const; _FORCE_INLINE_ Vector3 slide(const Vector3 &p_vec) const; + _FORCE_INLINE_ Vector3 bounce(const Vector3 &p_vec) const; _FORCE_INLINE_ Vector3 reflect(const Vector3 &p_vec) const; /* Operators */ @@ -214,7 +217,7 @@ real_t Vector3::distance_squared_to(const Vector3 &p_b) const { real_t Vector3::angle_to(const Vector3 &p_b) const { - return Math::acos(this->dot(p_b) / Math::sqrt(this->length_squared() * p_b.length_squared())); + return Math::atan2(cross(p_b).length(), dot(p_b)); } /* Operators */ @@ -385,6 +388,11 @@ Vector3 Vector3::normalized() const { return v; } +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); +} + Vector3 Vector3::inverse() const { return Vector3(1.0 / x, 1.0 / y, 1.0 / z); @@ -395,14 +403,23 @@ void Vector3::zero() { x = y = z = 0; } -Vector3 Vector3::slide(const Vector3 &p_vec) const { - - return p_vec - *this * this->dot(p_vec); +// slide returns the component of the vector along the given plane, specified by its normal vector. +Vector3 Vector3::slide(const Vector3 &p_n) const { +#ifdef MATH_CHECKS + ERR_FAIL_COND_V(p_n.is_normalized() == false, Vector3()); +#endif + return *this - p_n * this->dot(p_n); } -Vector3 Vector3::reflect(const Vector3 &p_vec) const { +Vector3 Vector3::bounce(const Vector3 &p_n) const { + return -reflect(p_n); +} - return p_vec - *this * this->dot(p_vec) * 2.0; +Vector3 Vector3::reflect(const Vector3 &p_n) const { +#ifdef MATH_CHECKS + ERR_FAIL_COND_V(p_n.is_normalized() == false, Vector3()); +#endif + return 2.0 * p_n * this->dot(p_n) - *this; } #endif |