summaryrefslogtreecommitdiff
path: root/core/math
diff options
context:
space:
mode:
Diffstat (limited to 'core/math')
-rw-r--r--core/math/geometry.cpp106
-rw-r--r--core/math/geometry.h91
2 files changed, 196 insertions, 1 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 0b2adf9513..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;
@@ -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
generated by cgit v1.2.3 (git 2.25.1) at 2024-12-20 03:50:54 +0000