Merge pull request #28987 from Xrayez/geometry-clipper-bind

Expose 2D polygon boolean operations in Geometry singleton

4 files changed, 356 insertions, 1 deletions

diff --git a/core/bind/core_bind.cpp b/core/bind/core_bind.cpp
index ba595b9627..7562c82e8a 100644
--- a/core/bind/core_bind.cpp
+++ b/core/bind/core_bind.cpp
@@ -1491,6 +1491,11 @@ PoolVector<Vector3> _Geometry::segment_intersects_convex(const Vector3 &p_from,
 	return r;
 }
 
+bool _Geometry::is_polygon_clockwise(const Vector<Vector2> &p_polygon) {
+
+	return Geometry::is_polygon_clockwise(p_polygon);
+}
+
 Vector<int> _Geometry::triangulate_polygon(const Vector<Vector2> &p_polygon) {
 
 	return Geometry::triangulate_polygon(p_polygon);
@@ -1506,6 +1511,107 @@ Vector<Vector3> _Geometry::clip_polygon(const Vector<Vector3> &p_points, const P
 	return Geometry::clip_polygon(p_points, p_plane);
 }
 
+Array _Geometry::merge_polygons_2d(const Vector<Vector2> &p_polygon_a, const Vector<Vector2> &p_polygon_b) {
+
+	Vector<Vector<Point2> > polys = Geometry::merge_polygons_2d(p_polygon_a, p_polygon_b);
+
+	Array ret;
+
+	for (int i = 0; i < polys.size(); ++i) {
+		ret.push_back(polys[i]);
+	}
+	return ret;
+}
+
+Array _Geometry::clip_polygons_2d(const Vector<Vector2> &p_polygon_a, const Vector<Vector2> &p_polygon_b) {
+
+	Vector<Vector<Point2> > polys = Geometry::clip_polygons_2d(p_polygon_a, p_polygon_b);
+
+	Array ret;
+
+	for (int i = 0; i < polys.size(); ++i) {
+		ret.push_back(polys[i]);
+	}
+	return ret;
+}
+
+Array _Geometry::intersect_polygons_2d(const Vector<Vector2> &p_polygon_a, const Vector<Vector2> &p_polygon_b) {
+
+	Vector<Vector<Point2> > polys = Geometry::intersect_polygons_2d(p_polygon_a, p_polygon_b);
+
+	Array ret;
+
+	for (int i = 0; i < polys.size(); ++i) {
+		ret.push_back(polys[i]);
+	}
+	return ret;
+}
+
+Array _Geometry::exclude_polygons_2d(const Vector<Vector2> &p_polygon_a, const Vector<Vector2> &p_polygon_b) {
+
+	Vector<Vector<Point2> > polys = Geometry::exclude_polygons_2d(p_polygon_a, p_polygon_b);
+
+	Array ret;
+
+	for (int i = 0; i < polys.size(); ++i) {
+		ret.push_back(polys[i]);
+	}
+	return ret;
+}
+
+Array _Geometry::clip_polyline_with_polygon_2d(const Vector<Vector2> &p_polyline, const Vector<Vector2> &p_polygon) {
+
+	Vector<Vector<Point2> > polys = Geometry::clip_polyline_with_polygon_2d(p_polyline, p_polygon);
+
+	Array ret;
+
+	for (int i = 0; i < polys.size(); ++i) {
+		ret.push_back(polys[i]);
+	}
+	return ret;
+}
+
+Array _Geometry::intersect_polyline_with_polygon_2d(const Vector<Vector2> &p_polyline, const Vector<Vector2> &p_polygon) {
+
+	Vector<Vector<Point2> > polys = Geometry::intersect_polyline_with_polygon_2d(p_polyline, p_polygon);
+
+	Array ret;
+
+	for (int i = 0; i < polys.size(); ++i) {
+		ret.push_back(polys[i]);
+	}
+	return ret;
+}
+
+Array _Geometry::offset_polygon_2d(const Vector<Vector2> &p_polygon, real_t p_delta, PolyJoinType p_join_type) {
+
+	Vector<Vector<Point2> > polys = Geometry::offset_polygon_2d(p_polygon, p_delta, Geometry::PolyJoinType(p_join_type));
+
+	Array ret;
+
+	for (int i = 0; i < polys.size(); ++i) {
+		ret.push_back(polys[i]);
+	}
+	return ret;
+}
+
+Array _Geometry::offset_polyline_2d(const Vector<Vector2> &p_polygon, real_t p_delta, PolyJoinType p_join_type, PolyEndType p_end_type) {
+
+	Vector<Vector<Point2> > polys = Geometry::offset_polyline_2d(p_polygon, p_delta, Geometry::PolyJoinType(p_join_type), Geometry::PolyEndType(p_end_type));
+
+	Array ret;
+
+	for (int i = 0; i < polys.size(); ++i) {
+		ret.push_back(polys[i]);
+	}
+	return ret;
+}
+
+Vector<Point2> _Geometry::transform_points_2d(const Vector<Point2> &p_points, const Transform2D &p_mat) {
+
+	return Geometry::transform_points_2d(p_points, p_mat);
+}
+
 Dictionary _Geometry::make_atlas(const Vector<Size2> &p_rects) {
 
 	Dictionary ret;
@@ -1566,11 +1672,40 @@ void _Geometry::_bind_methods() {
 	ClassDB::bind_method(D_METHOD("segment_intersects_convex", "from", "to", "planes"), &_Geometry::segment_intersects_convex);
 	ClassDB::bind_method(D_METHOD("point_is_inside_triangle", "point", "a", "b", "c"), &_Geometry::point_is_inside_triangle);
 
+	ClassDB::bind_method(D_METHOD("is_polygon_clockwise", "polygon"), &_Geometry::is_polygon_clockwise);
 	ClassDB::bind_method(D_METHOD("triangulate_polygon", "polygon"), &_Geometry::triangulate_polygon);
 	ClassDB::bind_method(D_METHOD("convex_hull_2d", "points"), &_Geometry::convex_hull_2d);
 	ClassDB::bind_method(D_METHOD("clip_polygon", "points", "plane"), &_Geometry::clip_polygon);
 
+	ClassDB::bind_method(D_METHOD("merge_polygons_2d", "polygon_a", "polygon_b"), &_Geometry::merge_polygons_2d);
+	ClassDB::bind_method(D_METHOD("clip_polygons_2d", "polygon_a", "polygon_b"), &_Geometry::clip_polygons_2d);
+	ClassDB::bind_method(D_METHOD("intersect_polygons_2d", "polygon_a", "polygon_b"), &_Geometry::intersect_polygons_2d);
+	ClassDB::bind_method(D_METHOD("exclude_polygons_2d", "polygon_a", "polygon_b"), &_Geometry::exclude_polygons_2d);
+
+	ClassDB::bind_method(D_METHOD("clip_polyline_with_polygon_2d", "polyline", "polygon"), &_Geometry::clip_polyline_with_polygon_2d);
+	ClassDB::bind_method(D_METHOD("intersect_polyline_with_polygon_2d", "polyline", "polygon"), &_Geometry::intersect_polyline_with_polygon_2d);
+
+	ClassDB::bind_method(D_METHOD("offset_polygon_2d", "polygon", "delta", "join_type"), &_Geometry::offset_polygon_2d, DEFVAL(JOIN_SQUARE));
+	ClassDB::bind_method(D_METHOD("offset_polyline_2d", "polyline", "delta", "join_type", "end_type"), &_Geometry::offset_polyline_2d, DEFVAL(JOIN_SQUARE), DEFVAL(END_SQUARE));
+
+	ClassDB::bind_method(D_METHOD("transform_points_2d", "points", "transform"), &_Geometry::transform_points_2d);
+
 	ClassDB::bind_method(D_METHOD("make_atlas", "sizes"), &_Geometry::make_atlas);
+
+	BIND_ENUM_CONSTANT(OPERATION_UNION);
+	BIND_ENUM_CONSTANT(OPERATION_DIFFERENCE);
+	BIND_ENUM_CONSTANT(OPERATION_INTERSECTION);
+	BIND_ENUM_CONSTANT(OPERATION_XOR);
+
+	BIND_ENUM_CONSTANT(JOIN_SQUARE);
+	BIND_ENUM_CONSTANT(JOIN_ROUND);
+	BIND_ENUM_CONSTANT(JOIN_MITER);
+
+	BIND_ENUM_CONSTANT(END_POLYGON);
+	BIND_ENUM_CONSTANT(END_JOINED);
+	BIND_ENUM_CONSTANT(END_BUTT);
+	BIND_ENUM_CONSTANT(END_SQUARE);
+	BIND_ENUM_CONSTANT(END_ROUND);
 }
 
 _Geometry::_Geometry() {
diff --git a/core/bind/core_bind.h b/core/bind/core_bind.h
index 2906de4a4a..561449f29e 100644
--- a/core/bind/core_bind.h
+++ b/core/bind/core_bind.h
@@ -402,15 +402,54 @@ public:
 	real_t segment_intersects_circle(const Vector2 &p_from, const Vector2 &p_to, const Vector2 &p_circle_pos, real_t p_circle_radius);
 	int get_uv84_normal_bit(const Vector3 &p_vector);
 
+	bool is_polygon_clockwise(const Vector<Vector2> &p_polygon);
 	Vector<int> triangulate_polygon(const Vector<Vector2> &p_polygon);
 	Vector<Point2> convex_hull_2d(const Vector<Point2> &p_points);
 	Vector<Vector3> clip_polygon(const Vector<Vector3> &p_points, const Plane &p_plane);
 
+	enum PolyBooleanOperation {
+		OPERATION_UNION,
+		OPERATION_DIFFERENCE,
+		OPERATION_INTERSECTION,
+		OPERATION_XOR
+	};
+	// 2D polygon boolean operations
+	Array merge_polygons_2d(const Vector<Vector2> &p_polygon_a, const Vector<Vector2> &p_polygon_b); // union (add)
+	Array clip_polygons_2d(const Vector<Vector2> &p_polygon_a, const Vector<Vector2> &p_polygon_b); // difference (subtract)
+	Array intersect_polygons_2d(const Vector<Vector2> &p_polygon_a, const Vector<Vector2> &p_polygon_b); // common area (multiply)
+	Array exclude_polygons_2d(const Vector<Vector2> &p_polygon_a, const Vector<Vector2> &p_polygon_b); // all but common area (xor)
+
+	// 2D polyline vs polygon operations
+	Array clip_polyline_with_polygon_2d(const Vector<Vector2> &p_polyline, const Vector<Vector2> &p_polygon); // cut
+	Array intersect_polyline_with_polygon_2d(const Vector<Vector2> &p_polyline, const Vector<Vector2> &p_polygon); // chop
+
+	// 2D offset polygons/polylines
+	enum PolyJoinType {
+		JOIN_SQUARE,
+		JOIN_ROUND,
+		JOIN_MITER
+	};
+	enum PolyEndType {
+		END_POLYGON,
+		END_JOINED,
+		END_BUTT,
+		END_SQUARE,
+		END_ROUND
+	};
+	Array offset_polygon_2d(const Vector<Vector2> &p_polygon, real_t p_delta, PolyJoinType p_join_type = JOIN_SQUARE);
+	Array offset_polyline_2d(const Vector<Vector2> &p_polygon, real_t p_delta, PolyJoinType p_join_type = JOIN_SQUARE, PolyEndType p_end_type = END_SQUARE);
+
+	Vector<Point2> transform_points_2d(const Vector<Point2> &p_points, const Transform2D &p_mat);
+
 	Dictionary make_atlas(const Vector<Size2> &p_rects);
 
 	_Geometry();
 };
 
+VARIANT_ENUM_CAST(_Geometry::PolyBooleanOperation);
+VARIANT_ENUM_CAST(_Geometry::PolyJoinType);
+VARIANT_ENUM_CAST(_Geometry::PolyEndType);
+
 class _File : public Reference {
 
 	GDCLASS(_File, Reference);
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 0b2adf9513..c62573dd13 100644
--- a/core/math/geometry.h
+++ b/core/math/geometry.h
@@ -785,6 +785,78 @@ 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_polygon(const Vector<Vector2> &p_polygon) {
 
 		Vector<int> triangles;
@@ -951,7 +1023,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 +1032,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