summaryrefslogtreecommitdiff
path: root/core/math/geometry.cpp
diff options
context:
space:
mode:
Diffstat (limited to 'core/math/geometry.cpp')
-rw-r--r--core/math/geometry.cpp276
1 files changed, 183 insertions, 93 deletions
diff --git a/core/math/geometry.cpp b/core/math/geometry.cpp
index be5e40e4e6..e0ead8446f 100644
--- a/core/math/geometry.cpp
+++ b/core/math/geometry.cpp
@@ -5,8 +5,8 @@
/* GODOT ENGINE */
/* https://godotengine.org */
/*************************************************************************/
-/* Copyright (c) 2007-2018 Juan Linietsky, Ariel Manzur. */
-/* Copyright (c) 2014-2018 Godot Engine contributors (cf. AUTHORS.md) */
+/* Copyright (c) 2007-2019 Juan Linietsky, Ariel Manzur. */
+/* Copyright (c) 2014-2019 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 */
@@ -31,7 +31,13 @@
#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) {
Vector<int> indices = Geometry::triangulate_polygon(p_polygon);
@@ -42,6 +48,7 @@ bool Geometry::is_point_in_polygon(const Vector2 &p_point, const Vector<Vector2>
}
return false;
}
+*/
void Geometry::MeshData::optimize_vertices() {
@@ -118,8 +125,8 @@ struct _FaceClassify {
};
static bool _connect_faces(_FaceClassify *p_faces, int len, int p_group) {
- /* connect faces, error will occur if an edge is shared between more than 2 faces */
- /* clear connections */
+ // Connect faces, error will occur if an edge is shared between more than 2 faces.
+ // Clear connections.
bool error = false;
@@ -189,13 +196,6 @@ static bool _connect_faces(_FaceClassify *p_faces, int len, int p_group) {
if (p_faces[i].links[j].face == -1)
p_faces[i].valid = false;
}
- /*printf("face %i is valid: %i, group %i. connected to %i:%i,%i:%i,%i:%i\n",i,p_faces[i].valid,p_faces[i].group,
- p_faces[i].links[0].face,
- p_faces[i].links[0].edge,
- p_faces[i].links[1].face,
- p_faces[i].links[1].edge,
- p_faces[i].links[2].face,
- p_faces[i].links[2].edge);*/
}
return error;
}
@@ -241,12 +241,9 @@ PoolVector<PoolVector<Face3> > Geometry::separate_objects(PoolVector<Face3> p_ar
bool error = _connect_faces(_fcptr, len, -1);
- if (error) {
-
- ERR_FAIL_COND_V(error, PoolVector<PoolVector<Face3> >()); // invalid geometry
- }
+ ERR_FAIL_COND_V_MSG(error, PoolVector<PoolVector<Face3> >(), "Invalid geometry.");
- /* group connected faces in separate objects */
+ // Group connected faces in separate objects.
int group = 0;
for (int i = 0; i < len; i++) {
@@ -258,7 +255,7 @@ PoolVector<PoolVector<Face3> > Geometry::separate_objects(PoolVector<Face3> p_ar
}
}
- /* group connected faces in separate objects */
+ // Group connected faces in separate objects.
for (int i = 0; i < len; i++) {
@@ -370,7 +367,7 @@ static inline void _plot_face(uint8_t ***p_cell_status, int x, int y, int z, int
static inline void _mark_outside(uint8_t ***p_cell_status, int x, int y, int z, int len_x, int len_y, int len_z) {
if (p_cell_status[x][y][z] & 3)
- return; // nothing to do, already used and/or visited
+ return; // Nothing to do, already used and/or visited.
p_cell_status[x][y][z] = _CELL_PREV_FIRST;
@@ -378,29 +375,20 @@ static inline void _mark_outside(uint8_t ***p_cell_status, int x, int y, int z,
uint8_t &c = p_cell_status[x][y][z];
- //printf("at %i,%i,%i\n",x,y,z);
-
if ((c & _CELL_STEP_MASK) == _CELL_STEP_NONE) {
- /* Haven't been in here, mark as outside */
+ // Haven't been in here, mark as outside.
p_cell_status[x][y][z] |= _CELL_EXTERIOR;
- //printf("not marked as anything, marking exterior\n");
}
- //printf("cell step is %i\n",(c&_CELL_STEP_MASK));
-
if ((c & _CELL_STEP_MASK) != _CELL_STEP_DONE) {
- /* if not done, increase step */
+ // If not done, increase step.
c += 1 << 2;
- //printf("incrementing cell step\n");
}
if ((c & _CELL_STEP_MASK) == _CELL_STEP_DONE) {
- /* Go back */
- //printf("done, going back a cell\n");
-
+ // Go back.
switch (c & _CELL_PREV_MASK) {
case _CELL_PREV_FIRST: {
- //printf("at end, finished marking\n");
return;
} break;
case _CELL_PREV_Y_POS: {
@@ -434,8 +422,6 @@ static inline void _mark_outside(uint8_t ***p_cell_status, int x, int y, int z,
continue;
}
- //printf("attempting new cell!\n");
-
int next_x = x, next_y = y, next_z = z;
uint8_t prev = 0;
@@ -469,8 +455,6 @@ static inline void _mark_outside(uint8_t ***p_cell_status, int x, int y, int z,
default: ERR_FAIL();
}
- //printf("testing if new cell will be ok...!\n");
-
if (next_x < 0 || next_x >= len_x)
continue;
if (next_y < 0 || next_y >= len_y)
@@ -478,13 +462,9 @@ static inline void _mark_outside(uint8_t ***p_cell_status, int x, int y, int z,
if (next_z < 0 || next_z >= len_z)
continue;
- //printf("testing if new cell is traversable\n");
-
if (p_cell_status[next_x][next_y][next_z] & 3)
continue;
- //printf("move to it\n");
-
x = next_x;
y = next_y;
z = next_z;
@@ -501,18 +481,7 @@ static inline void _build_faces(uint8_t ***p_cell_status, int x, int y, int z, i
if (p_cell_status[x][y][z] & _CELL_EXTERIOR)
return;
-/* static const Vector3 vertices[8]={
- Vector3(0,0,0),
- Vector3(0,0,1),
- Vector3(0,1,0),
- Vector3(0,1,1),
- Vector3(1,0,0),
- Vector3(1,0,1),
- Vector3(1,1,0),
- Vector3(1,1,1),
- };
-*/
-#define vert(m_idx) Vector3((m_idx & 4) >> 2, (m_idx & 2) >> 1, m_idx & 1)
+#define vert(m_idx) Vector3(((m_idx)&4) >> 2, ((m_idx)&2) >> 1, (m_idx)&1)
static const uint8_t indices[6][4] = {
{ 7, 6, 4, 5 },
@@ -523,22 +492,6 @@ static inline void _build_faces(uint8_t ***p_cell_status, int x, int y, int z, i
{ 0, 4, 6, 2 },
};
- /*
-
- {0,1,2,3},
- {0,1,4,5},
- {0,2,4,6},
- {4,5,6,7},
- {2,3,7,6},
- {1,3,5,7},
-
- {0,2,3,1},
- {0,1,5,4},
- {0,4,6,2},
- {7,6,4,5},
- {7,3,2,6},
- {7,5,1,3},
-*/
for (int i = 0; i < 6; i++) {
@@ -601,9 +554,9 @@ PoolVector<Face3> Geometry::wrap_geometry(PoolVector<Face3> p_array, real_t *p_e
}
}
- global_aabb.grow_by(0.01); // avoid numerical error
+ global_aabb.grow_by(0.01); // Avoid numerical error.
- // determine amount of cells in grid axis
+ // Determine amount of cells in grid axis.
int div_x, div_y, div_z;
if (global_aabb.size.x / _MIN_SIZE < _MAX_LENGTH)
@@ -626,7 +579,7 @@ PoolVector<Face3> Geometry::wrap_geometry(PoolVector<Face3> p_array, real_t *p_e
voxelsize.y /= div_y;
voxelsize.z /= div_z;
- // create and initialize cells to zero
+ // Create and initialize cells to zero.
uint8_t ***cell_status = memnew_arr(uint8_t **, div_x);
for (int i = 0; i < div_x; i++) {
@@ -644,7 +597,7 @@ PoolVector<Face3> Geometry::wrap_geometry(PoolVector<Face3> p_array, real_t *p_e
}
}
- // plot faces into cells
+ // Plot faces into cells.
for (int i = 0; i < face_count; i++) {
@@ -656,7 +609,7 @@ PoolVector<Face3> Geometry::wrap_geometry(PoolVector<Face3> p_array, real_t *p_e
_plot_face(cell_status, 0, 0, 0, div_x, div_y, div_z, voxelsize, f);
}
- // determine which cells connect to the outside by traversing the outside and recursively flood-fill marking
+ // Determine which cells connect to the outside by traversing the outside and recursively flood-fill marking.
for (int i = 0; i < div_x; i++) {
@@ -685,7 +638,7 @@ PoolVector<Face3> Geometry::wrap_geometry(PoolVector<Face3> p_array, real_t *p_e
}
}
- // build faces for the inside-outside cell divisors
+ // Build faces for the inside-outside cell divisors.
PoolVector<Face3> wrapped_faces;
@@ -700,7 +653,7 @@ PoolVector<Face3> Geometry::wrap_geometry(PoolVector<Face3> p_array, real_t *p_e
}
}
- // transform face vertices to global coords
+ // Transform face vertices to global coords.
int wrapped_faces_count = wrapped_faces.size();
PoolVector<Face3>::Write wrapped_facesw = wrapped_faces.write();
@@ -735,13 +688,47 @@ PoolVector<Face3> Geometry::wrap_geometry(PoolVector<Face3> p_array, real_t *p_e
return wrapped_faces;
}
+Vector<Vector<Vector2> > Geometry::decompose_polygon_in_convex(Vector<Point2> polygon) {
+ Vector<Vector<Vector2> > decomp;
+ List<TriangulatorPoly> in_poly, out_poly;
+
+ TriangulatorPoly inp;
+ inp.Init(polygon.size());
+ for (int i = 0; i < polygon.size(); i++) {
+ inp.GetPoint(i) = polygon[i];
+ }
+ inp.SetOrientation(TRIANGULATOR_CCW);
+ in_poly.push_back(inp);
+ TriangulatorPartition tpart;
+ if (tpart.ConvexPartition_HM(&in_poly, &out_poly) == 0) { // Failed.
+ ERR_PRINT("Convex decomposing failed!");
+ return decomp;
+ }
+
+ decomp.resize(out_poly.size());
+ int idx = 0;
+ for (List<TriangulatorPoly>::Element *I = out_poly.front(); I; I = I->next()) {
+ TriangulatorPoly &tp = I->get();
+
+ decomp.write[idx].resize(tp.GetNumPoints());
+
+ for (int64_t i = 0; i < tp.GetNumPoints(); i++) {
+ decomp.write[idx].write[i] = tp.GetPoint(i);
+ }
+
+ idx++;
+ }
+
+ return decomp;
+}
+
Geometry::MeshData Geometry::build_convex_mesh(const PoolVector<Plane> &p_planes) {
MeshData mesh;
#define SUBPLANE_SIZE 1024.0
- real_t subplane_size = 1024.0; // should compute this from the actual plane
+ real_t subplane_size = 1024.0; // Should compute this from the actual plane.
for (int i = 0; i < p_planes.size(); i++) {
Plane p = p_planes[i];
@@ -749,7 +736,7 @@ Geometry::MeshData Geometry::build_convex_mesh(const PoolVector<Plane> &p_planes
Vector3 ref = Vector3(0.0, 1.0, 0.0);
if (ABS(p.normal.dot(ref)) > 0.95)
- ref = Vector3(0.0, 0.0, 1.0); // change axis
+ ref = Vector3(0.0, 0.0, 1.0); // Change axis.
Vector3 right = p.normal.cross(ref).normalized();
Vector3 up = p.normal.cross(right).normalized();
@@ -787,20 +774,20 @@ Geometry::MeshData Geometry::build_convex_mesh(const PoolVector<Plane> &p_planes
real_t dist0 = clip.distance_to(edge0_A);
real_t dist1 = clip.distance_to(edge1_A);
- if (dist0 <= 0) { // behind plane
+ if (dist0 <= 0) { // Behind plane.
new_vertices.push_back(vertices[k]);
}
- // check for different sides and non coplanar
+ // Check for different sides and non coplanar.
if ((dist0 * dist1) < 0) {
- // calculate intersection
+ // Calculate intersection.
Vector3 rel = edge1_A - edge0_A;
real_t den = clip.normal.dot(rel);
- if (Math::abs(den) < CMP_EPSILON)
- continue; // point too short
+ if (Math::is_zero_approx(den))
+ continue; // Point too short.
real_t dist = -(clip.normal.dot(edge0_A) - clip.d) / den;
Vector3 inters = edge0_A + rel * dist;
@@ -814,11 +801,11 @@ Geometry::MeshData Geometry::build_convex_mesh(const PoolVector<Plane> &p_planes
if (vertices.size() < 3)
continue;
- //result is a clockwise face
+ // Result is a clockwise face.
MeshData::Face face;
- // add face indices
+ // Add face indices.
for (int j = 0; j < vertices.size(); j++) {
int idx = -1;
@@ -842,7 +829,7 @@ Geometry::MeshData Geometry::build_convex_mesh(const PoolVector<Plane> &p_planes
face.plane = p;
mesh.faces.push_back(face);
- //add edge
+ // Add edge.
for (int j = 0; j < face.indices.size(); j++) {
@@ -932,7 +919,7 @@ PoolVector<Plane> Geometry::build_sphere_planes(real_t p_radius, int p_lats, int
for (int j = 1; j <= p_lats; j++) {
- //todo this is stupid, fix
+ // FIXME: This is stupid.
Vector3 angle = normal.linear_interpolate(axis, j / (real_t)p_lats).normalized();
Vector3 pos = angle * p_radius;
planes.push_back(Plane(pos, angle));
@@ -992,12 +979,12 @@ struct _AtlasWorkRectResult {
void Geometry::make_atlas(const Vector<Size2i> &p_rects, Vector<Point2i> &r_result, Size2i &r_size) {
- //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 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
+ // 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 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
// 256x8192 atlas (won't work anywhere).
ERR_FAIL_COND(p_rects.size() == 0);
@@ -1026,7 +1013,7 @@ void Geometry::make_atlas(const Vector<Size2i> &p_rects, Vector<Point2i> &r_resu
for (int j = 0; j < w; j++)
hmax.write[j] = 0;
- //place them
+ // Place them.
int ofs = 0;
int limit_h = 0;
for (int j = 0; j < wrects.size(); j++) {
@@ -1061,7 +1048,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 reached, keep stacking
+ if (ofs == 0 || end_h > limit_h) // While h limit not reached, keep stacking.
ofs += wrects[j].s.width;
}
@@ -1072,7 +1059,7 @@ void Geometry::make_atlas(const Vector<Size2i> &p_rects, Vector<Point2i> &r_resu
results.push_back(result);
}
- //find the result with the best aspect ratio
+ // Find the result with the best aspect ratio.
int best = -1;
real_t best_aspect = 1e20;
@@ -1097,3 +1084,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;
+}
generated by cgit v1.2.3 (git 2.25.1) at 2025-08-06 10:01:43 +0000