diff options
Diffstat (limited to 'core/math')
| -rw-r--r-- | core/math/geometry.cpp | 106 | ||||
| -rw-r--r-- | core/math/geometry.h | 93 |
2 files changed, 197 insertions, 2 deletions
diff --git a/core/math/geometry.cpp b/core/math/geometry.cpp index 0ab8707d3a..8314cb827c 100644 --- a/core/math/geometry.cpp +++ b/core/math/geometry.cpp @@ -31,8 +31,11 @@ #include "geometry.h" #include "core/print_string.h" +#include "thirdparty/misc/clipper.hpp" #include "thirdparty/misc/triangulator.h" +#define SCALE_FACTOR 100000.0 // based on CMP_EPSILON + /* this implementation is very inefficient, commenting unless bugs happen. See the other one. bool Geometry::is_point_in_polygon(const Vector2 &p_point, const Vector<Vector2> &p_polygon) { @@ -1134,3 +1137,106 @@ void Geometry::make_atlas(const Vector<Size2i> &p_rects, Vector<Point2i> &r_resu r_size = Size2(results[best].max_w, results[best].max_h); } + +Vector<Vector<Point2> > Geometry::_polypaths_do_operation(PolyBooleanOperation p_op, const Vector<Point2> &p_polypath_a, const Vector<Point2> &p_polypath_b, bool is_a_open) { + + using namespace ClipperLib; + + ClipType op = ctUnion; + + switch (p_op) { + case OPERATION_UNION: op = ctUnion; break; + case OPERATION_DIFFERENCE: op = ctDifference; break; + case OPERATION_INTERSECTION: op = ctIntersection; break; + case OPERATION_XOR: op = ctXor; break; + } + Path path_a, path_b; + + // Need to scale points (Clipper's requirement for robust computation) + for (int i = 0; i != p_polypath_a.size(); ++i) { + path_a << IntPoint(p_polypath_a[i].x * SCALE_FACTOR, p_polypath_a[i].y * SCALE_FACTOR); + } + for (int i = 0; i != p_polypath_b.size(); ++i) { + path_b << IntPoint(p_polypath_b[i].x * SCALE_FACTOR, p_polypath_b[i].y * SCALE_FACTOR); + } + Clipper clp; + clp.AddPath(path_a, ptSubject, !is_a_open); // forward compatible with Clipper 10.0.0 + clp.AddPath(path_b, ptClip, true); // polylines cannot be set as clip + + Paths paths; + + if (is_a_open) { + PolyTree tree; // needed to populate polylines + clp.Execute(op, tree); + OpenPathsFromPolyTree(tree, paths); + } else { + clp.Execute(op, paths); // works on closed polygons only + } + // Have to scale points down now + Vector<Vector<Point2> > polypaths; + + for (Paths::size_type i = 0; i < paths.size(); ++i) { + Vector<Vector2> polypath; + + const Path &scaled_path = paths[i]; + + for (Paths::size_type j = 0; j < scaled_path.size(); ++j) { + polypath.push_back(Point2( + static_cast<real_t>(scaled_path[j].X) / SCALE_FACTOR, + static_cast<real_t>(scaled_path[j].Y) / SCALE_FACTOR)); + } + polypaths.push_back(polypath); + } + return polypaths; +} + +Vector<Vector<Point2> > Geometry::_polypath_offset(const Vector<Point2> &p_polypath, real_t p_delta, PolyJoinType p_join_type, PolyEndType p_end_type) { + + using namespace ClipperLib; + + JoinType jt = jtSquare; + + switch (p_join_type) { + case JOIN_SQUARE: jt = jtSquare; break; + case JOIN_ROUND: jt = jtRound; break; + case JOIN_MITER: jt = jtMiter; break; + } + + EndType et = etClosedPolygon; + + switch (p_end_type) { + case END_POLYGON: et = etClosedPolygon; break; + case END_JOINED: et = etClosedLine; break; + case END_BUTT: et = etOpenButt; break; + case END_SQUARE: et = etOpenSquare; break; + case END_ROUND: et = etOpenRound; break; + } + ClipperOffset co; + Path path; + + // Need to scale points (Clipper's requirement for robust computation) + for (int i = 0; i != p_polypath.size(); ++i) { + path << IntPoint(p_polypath[i].x * SCALE_FACTOR, p_polypath[i].y * SCALE_FACTOR); + } + co.AddPath(path, jt, et); + + Paths paths; + co.Execute(paths, p_delta * SCALE_FACTOR); // inflate/deflate + + // Have to scale points down now + Vector<Vector<Point2> > polypaths; + + for (Paths::size_type i = 0; i < paths.size(); ++i) { + Vector<Vector2> polypath; + + const Path &scaled_path = paths[i]; + + for (Paths::size_type j = 0; j < scaled_path.size(); ++j) { + polypath.push_back(Point2( + static_cast<real_t>(scaled_path[j].X) / SCALE_FACTOR, + static_cast<real_t>(scaled_path[j].Y) / SCALE_FACTOR)); + } + polypaths.push_back(polypath); + } + return polypaths; +} diff --git a/core/math/geometry.h b/core/math/geometry.h index f3a671aa9a..0e144e491f 100644 --- a/core/math/geometry.h +++ b/core/math/geometry.h @@ -31,6 +31,7 @@ #ifndef GEOMETRY_H #define GEOMETRY_H +#include "core/math/delaunay.h" #include "core/math/face3.h" #include "core/math/rect2.h" #include "core/math/triangulate.h" @@ -785,6 +786,91 @@ public: return clipped; } + enum PolyBooleanOperation { + OPERATION_UNION, + OPERATION_DIFFERENCE, + OPERATION_INTERSECTION, + OPERATION_XOR + }; + enum PolyJoinType { + JOIN_SQUARE, + JOIN_ROUND, + JOIN_MITER + }; + enum PolyEndType { + END_POLYGON, + END_JOINED, + END_BUTT, + END_SQUARE, + END_ROUND + }; + + static Vector<Vector<Point2> > merge_polygons_2d(const Vector<Point2> &p_polygon_a, const Vector<Point2> &p_polygon_b) { + + return _polypaths_do_operation(OPERATION_UNION, p_polygon_a, p_polygon_b); + } + + static Vector<Vector<Point2> > clip_polygons_2d(const Vector<Point2> &p_polygon_a, const Vector<Point2> &p_polygon_b) { + + return _polypaths_do_operation(OPERATION_DIFFERENCE, p_polygon_a, p_polygon_b); + } + + static Vector<Vector<Point2> > intersect_polygons_2d(const Vector<Point2> &p_polygon_a, const Vector<Point2> &p_polygon_b) { + + return _polypaths_do_operation(OPERATION_INTERSECTION, p_polygon_a, p_polygon_b); + } + + static Vector<Vector<Point2> > exclude_polygons_2d(const Vector<Point2> &p_polygon_a, const Vector<Point2> &p_polygon_b) { + + return _polypaths_do_operation(OPERATION_XOR, p_polygon_a, p_polygon_b); + } + + static Vector<Vector<Point2> > clip_polyline_with_polygon_2d(const Vector<Vector2> &p_polyline, const Vector<Vector2> &p_polygon) { + + return _polypaths_do_operation(OPERATION_DIFFERENCE, p_polyline, p_polygon, true); + } + + static Vector<Vector<Point2> > intersect_polyline_with_polygon_2d(const Vector<Vector2> &p_polyline, const Vector<Vector2> &p_polygon) { + + return _polypaths_do_operation(OPERATION_INTERSECTION, p_polyline, p_polygon, true); + } + + static Vector<Vector<Point2> > offset_polygon_2d(const Vector<Vector2> &p_polygon, real_t p_delta, PolyJoinType p_join_type) { + + return _polypath_offset(p_polygon, p_delta, p_join_type, END_POLYGON); + } + + static Vector<Vector<Point2> > offset_polyline_2d(const Vector<Vector2> &p_polygon, real_t p_delta, PolyJoinType p_join_type, PolyEndType p_end_type) { + + ERR_EXPLAIN("Attempt to offset a polyline like a polygon (use offset_polygon_2d instead)."); + ERR_FAIL_COND_V(p_end_type == END_POLYGON, Vector<Vector<Point2> >()); + + return _polypath_offset(p_polygon, p_delta, p_join_type, p_end_type); + } + + static Vector<Point2> transform_points_2d(const Vector<Point2> &p_points, const Transform2D &p_mat) { + + Vector<Point2> points; + + for (int i = 0; i < p_points.size(); ++i) { + points.push_back(p_mat.xform(p_points[i])); + } + return points; + } + + static Vector<int> triangulate_delaunay_2d(const Vector<Vector2> &p_points) { + + Vector<Delaunay2D::Triangle> tr = Delaunay2D::triangulate(p_points); + Vector<int> triangles; + + for (int i = 0; i < tr.size(); i++) { + triangles.push_back(tr[i].points[0]); + triangles.push_back(tr[i].points[1]); + triangles.push_back(tr[i].points[2]); + } + return triangles; + } + static Vector<int> triangulate_polygon(const Vector<Vector2> &p_polygon) { Vector<int> triangles; @@ -833,7 +919,7 @@ public: further_away_opposite.y = MIN(p[i].y, further_away_opposite.y); } - further_away += (further_away - further_away_opposite) * Vector2(1.221313, 1.512312); // make point outside that wont intersect with points in segment from p_point + further_away += (further_away - further_away_opposite) * Vector2(1.221313, 1.512312); // make point outside that won't intersect with points in segment from p_point int intersections = 0; for (int i = 0; i < c; i++) { @@ -951,7 +1037,6 @@ public: H.resize(k); return H; } - static Vector<Vector<Vector2> > decompose_polygon_in_convex(Vector<Point2> polygon); static MeshData build_convex_mesh(const PoolVector<Plane> &p_planes); @@ -961,6 +1046,10 @@ public: static PoolVector<Plane> build_capsule_planes(real_t p_radius, real_t p_height, int p_sides, int p_lats, Vector3::Axis p_axis = Vector3::AXIS_Z); static void make_atlas(const Vector<Size2i> &p_rects, Vector<Point2i> &r_result, Size2i &r_size); + +private: + static Vector<Vector<Point2> > _polypaths_do_operation(PolyBooleanOperation p_op, const Vector<Point2> &p_polypath_a, const Vector<Point2> &p_polypath_b, bool is_a_open = false); + static Vector<Vector<Point2> > _polypath_offset(const Vector<Point2> &p_polypath, real_t p_delta, PolyJoinType p_join_type, PolyEndType p_end_type); }; #endif |