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.cpp151
1 files changed, 49 insertions, 102 deletions
diff --git a/core/math/geometry.cpp b/core/math/geometry.cpp
index 8314cb827c..e0ead8446f 100644
--- a/core/math/geometry.cpp
+++ b/core/math/geometry.cpp
@@ -34,9 +34,10 @@
#include "thirdparty/misc/clipper.hpp"
#include "thirdparty/misc/triangulator.h"
-#define SCALE_FACTOR 100000.0 // based on CMP_EPSILON
+#define SCALE_FACTOR 100000.0 // Based on CMP_EPSILON.
-/* this implementation is very inefficient, commenting unless bugs happen. See the other one.
+// 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);
@@ -124,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;
@@ -195,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;
}
@@ -247,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_MSG(error, PoolVector<PoolVector<Face3> >(), "Invalid geometry.");
- ERR_FAIL_COND_V(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++) {
@@ -264,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++) {
@@ -376,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;
@@ -384,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: {
@@ -440,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;
@@ -475,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)
@@ -484,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;
@@ -507,17 +481,6 @@ 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)
static const uint8_t indices[6][4] = {
@@ -529,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++) {
@@ -607,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)
@@ -632,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++) {
@@ -650,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++) {
@@ -662,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++) {
@@ -691,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;
@@ -706,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();
@@ -753,7 +700,7 @@ Vector<Vector<Vector2> > Geometry::decompose_polygon_in_convex(Vector<Point2> po
inp.SetOrientation(TRIANGULATOR_CCW);
in_poly.push_back(inp);
TriangulatorPartition tpart;
- if (tpart.ConvexPartition_HM(&in_poly, &out_poly) == 0) { //failed!
+ if (tpart.ConvexPartition_HM(&in_poly, &out_poly) == 0) { // Failed.
ERR_PRINT("Convex decomposing failed!");
return decomp;
}
@@ -765,7 +712,7 @@ Vector<Vector<Vector2> > Geometry::decompose_polygon_in_convex(Vector<Point2> po
decomp.write[idx].resize(tp.GetNumPoints());
- for (int i = 0; i < tp.GetNumPoints(); i++) {
+ for (int64_t i = 0; i < tp.GetNumPoints(); i++) {
decomp.write[idx].write[i] = tp.GetPoint(i);
}
@@ -781,7 +728,7 @@ Geometry::MeshData Geometry::build_convex_mesh(const PoolVector<Plane> &p_planes
#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];
@@ -789,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();
@@ -827,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::is_zero_approx(den))
- continue; // point too short
+ continue; // Point too short.
real_t dist = -(clip.normal.dot(edge0_A) - clip.d) / den;
Vector3 inters = edge0_A + rel * dist;
@@ -854,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;
@@ -882,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++) {
@@ -972,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));
@@ -1032,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);
@@ -1066,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++) {
@@ -1101,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;
}
@@ -1112,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;
@@ -1152,7 +1099,7 @@ Vector<Vector<Point2> > Geometry::_polypaths_do_operation(PolyBooleanOperation p
}
Path path_a, path_b;
- // Need to scale points (Clipper's requirement for robust computation)
+ // 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);
}
@@ -1160,19 +1107,19 @@ Vector<Vector<Point2> > Geometry::_polypaths_do_operation(PolyBooleanOperation p
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
+ 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
+ PolyTree tree; // Needed to populate polylines.
clp.Execute(op, tree);
OpenPathsFromPolyTree(tree, paths);
} else {
- clp.Execute(op, paths); // works on closed polygons only
+ clp.Execute(op, paths); // Works on closed polygons only.
}
- // Have to scale points down now
+ // Have to scale points down now.
Vector<Vector<Point2> > polypaths;
for (Paths::size_type i = 0; i < paths.size(); ++i) {
@@ -1214,16 +1161,16 @@ Vector<Vector<Point2> > Geometry::_polypath_offset(const Vector<Point2> &p_polyp
ClipperOffset co;
Path path;
- // Need to scale points (Clipper's requirement for robust computation)
+ // 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
+ co.Execute(paths, p_delta * SCALE_FACTOR); // Inflate/deflate.
- // Have to scale points down now
+ // Have to scale points down now.
Vector<Vector<Point2> > polypaths;
for (Paths::size_type i = 0; i < paths.size(); ++i) {
generated by cgit v1.2.3 (git 2.25.1) at 2024-12-30 20:34:11 +0000