diff options
| -rw-r--r-- | core/math/geometry.h | 31 | ||||
| -rw-r--r-- | scene/resources/convex_polygon_shape_2d.cpp | 6 |
2 files changed, 36 insertions, 1 deletions
diff --git a/core/math/geometry.h b/core/math/geometry.h index b438b41d61..8214895676 100644 --- a/core/math/geometry.h +++ b/core/math/geometry.h @@ -886,7 +886,38 @@ public: } + static double vec2_cross(const Point2 &O, const Point2 &A, const Point2 &B) + { + return (double)(A.x - O.x) * (B.y - O.y) - (double)(A.y - O.y) * (B.x - O.x); + } + + // Returns a list of points on the convex hull in counter-clockwise order. + // Note: the last point in the returned list is the same as the first one. + static Vector<Point2> convex_hull_2d(Vector<Point2> P) + { + int n = P.size(), k = 0; + Vector<Point2> H; + H.resize(2*n); + + // Sort points lexicographically + P.sort(); + + // Build lower hull + for (int i = 0; i < n; ++i) { + while (k >= 2 && vec2_cross(H[k-2], H[k-1], P[i]) <= 0) k--; + H[k++] = P[i]; + } + + // Build upper hull + for (int i = n-2, t = k+1; i >= 0; i--) { + while (k >= t && vec2_cross(H[k-2], H[k-1], P[i]) <= 0) k--; + H[k++] = P[i]; + } + + H.resize(k); + return H; + } static MeshData build_convex_mesh(const DVector<Plane> &p_planes); static DVector<Plane> build_sphere_planes(float p_radius, int p_lats, int p_lons, Vector3::Axis p_axis=Vector3::AXIS_Z); diff --git a/scene/resources/convex_polygon_shape_2d.cpp b/scene/resources/convex_polygon_shape_2d.cpp index a1137ba614..86cf818ac3 100644 --- a/scene/resources/convex_polygon_shape_2d.cpp +++ b/scene/resources/convex_polygon_shape_2d.cpp @@ -30,6 +30,8 @@ #include "servers/physics_2d_server.h" #include "servers/visual_server.h" +#include "geometry.h" + void ConvexPolygonShape2D::_update_shape() { Physics2DServer::get_singleton()->shape_set_data(get_rid(),points); @@ -40,7 +42,9 @@ void ConvexPolygonShape2D::_update_shape() { void ConvexPolygonShape2D::set_point_cloud(const Vector<Vector2>& p_points) { - + Vector<Point2> hull=Geometry::convex_hull_2d(p_points); + ERR_FAIL_COND(hull.size()<3); + set_points(hull); } void ConvexPolygonShape2D::set_points(const Vector<Vector2>& p_points) { |