summaryrefslogtreecommitdiffstats
path: root/core/math/geometry.cpp
diff options
context:
space:
mode:
Diffstat (limited to 'core/math/geometry.cpp')
-rw-r--r--core/math/geometry.cpp246
1 files changed, 233 insertions, 13 deletions
diff --git a/core/math/geometry.cpp b/core/math/geometry.cpp
index fa96fc4535..b0a46036f9 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 STB_RECT_PACK_IMPLEMENTATION
+#include "thirdparty/misc/stb_rect_pack.h"
#define SCALE_FACTOR 100000.0 // Based on CMP_EPSILON.
@@ -445,7 +448,8 @@ static inline void _mark_outside(uint8_t ***p_cell_status, int x, int y, int z,
next_z--;
prev = _CELL_PREV_Z_POS;
} break;
- default: ERR_FAIL();
+ default:
+ ERR_FAIL();
}
if (next_x < 0 || next_x >= len_x)
@@ -1083,10 +1087,18 @@ Vector<Vector<Point2>> Geometry::_polypaths_do_operation(PolyBooleanOperation p_
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;
+ 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;
@@ -1135,19 +1147,35 @@ Vector<Vector<Point2>> Geometry::_polypath_offset(const Vector<Point2> &p_polypa
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;
+ 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;
+ 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(2.0, 0.25 * SCALE_FACTOR); // Defaults from ClipperOffset.
Path path;
@@ -1217,3 +1245,195 @@ Vector<Vector3> Geometry::compute_convex_mesh_points(const Plane *p_planes, int
return points;
}
+
+Vector<Point2i> Geometry::pack_rects(const Vector<Size2i> &p_sizes, const Size2i &p_atlas_size) {
+
+ Vector<stbrp_node> nodes;
+ nodes.resize(p_atlas_size.width);
+
+ stbrp_context context;
+ stbrp_init_target(&context, p_atlas_size.width, p_atlas_size.height, nodes.ptrw(), p_atlas_size.width);
+
+ Vector<stbrp_rect> rects;
+ rects.resize(p_sizes.size());
+
+ for (int i = 0; i < p_sizes.size(); i++) {
+ rects.write[i].id = 0;
+ rects.write[i].w = p_sizes[i].width;
+ rects.write[i].h = p_sizes[i].height;
+ rects.write[i].x = 0;
+ rects.write[i].y = 0;
+ rects.write[i].was_packed = 0;
+ }
+
+ int res = stbrp_pack_rects(&context, rects.ptrw(), rects.size());
+ if (res == 0) { //pack failed
+ return Vector<Point2i>();
+ }
+
+ Vector<Point2i> ret;
+ ret.resize(p_sizes.size());
+
+ for (int i = 0; i < p_sizes.size(); i++) {
+ Point2i r(rects[i].x, rects[i].y);
+ ret.write[i] = r;
+ }
+
+ return ret;
+}
+
+Vector<Vector3i> Geometry::partial_pack_rects(const Vector<Vector2i> &p_sizes, const Size2i &p_atlas_size) {
+
+ Vector<stbrp_node> nodes;
+ nodes.resize(p_atlas_size.width);
+ zeromem(nodes.ptrw(), sizeof(stbrp_node) * nodes.size());
+
+ stbrp_context context;
+ stbrp_init_target(&context, p_atlas_size.width, p_atlas_size.height, nodes.ptrw(), p_atlas_size.width);
+
+ Vector<stbrp_rect> rects;
+ rects.resize(p_sizes.size());
+
+ for (int i = 0; i < p_sizes.size(); i++) {
+ rects.write[i].id = i;
+ rects.write[i].w = p_sizes[i].width;
+ rects.write[i].h = p_sizes[i].height;
+ rects.write[i].x = 0;
+ rects.write[i].y = 0;
+ rects.write[i].was_packed = 0;
+ }
+
+ stbrp_pack_rects(&context, rects.ptrw(), rects.size());
+
+ Vector<Vector3i> ret;
+ ret.resize(p_sizes.size());
+
+ for (int i = 0; i < p_sizes.size(); i++) {
+ ret.write[rects[i].id] = Vector3i(rects[i].x, rects[i].y, rects[i].was_packed != 0 ? 1 : 0);
+ }
+
+ return ret;
+}
+
+#define square(m_s) ((m_s) * (m_s))
+#define INF 1e20
+
+/* dt of 1d function using squared distance */
+static void edt(float *f, int stride, int n) {
+
+ float *d = (float *)alloca(sizeof(float) * n + sizeof(int) * n + sizeof(float) * (n + 1));
+ int *v = (int *)&(d[n]);
+ float *z = (float *)&v[n];
+
+ int k = 0;
+ v[0] = 0;
+ z[0] = -INF;
+ z[1] = +INF;
+ for (int q = 1; q <= n - 1; q++) {
+ float s = ((f[q * stride] + square(q)) - (f[v[k] * stride] + square(v[k]))) / (2 * q - 2 * v[k]);
+ while (s <= z[k]) {
+ k--;
+ s = ((f[q * stride] + square(q)) - (f[v[k] * stride] + square(v[k]))) / (2 * q - 2 * v[k]);
+ }
+ k++;
+ v[k] = q;
+
+ z[k] = s;
+ z[k + 1] = +INF;
+ }
+
+ k = 0;
+ for (int q = 0; q <= n - 1; q++) {
+ while (z[k + 1] < q)
+ k++;
+ d[q] = square(q - v[k]) + f[v[k] * stride];
+ }
+
+ for (int i = 0; i < n; i++) {
+ f[i * stride] = d[i];
+ }
+}
+
+#undef square
+
+Vector<uint32_t> Geometry::generate_edf(const Vector<bool> &p_voxels, const Vector3i &p_size, bool p_negative) {
+
+ uint32_t float_count = p_size.x * p_size.y * p_size.z;
+
+ ERR_FAIL_COND_V((uint32_t)p_voxels.size() != float_count, Vector<uint32_t>());
+
+ float *work_memory = memnew_arr(float, float_count);
+ for (uint32_t i = 0; i < float_count; i++) {
+ work_memory[i] = INF;
+ }
+
+ uint32_t y_mult = p_size.x;
+ uint32_t z_mult = y_mult * p_size.y;
+
+ //plot solid cells
+ {
+ const bool *voxr = p_voxels.ptr();
+ for (uint32_t i = 0; i < float_count; i++) {
+
+ bool plot = voxr[i];
+ if (p_negative) {
+ plot = !plot;
+ }
+ if (plot) {
+ work_memory[i] = 0;
+ }
+ }
+ }
+
+ //process in each direction
+
+ //xy->z
+
+ for (int i = 0; i < p_size.x; i++) {
+ for (int j = 0; j < p_size.y; j++) {
+ edt(&work_memory[i + j * y_mult], z_mult, p_size.z);
+ }
+ }
+
+ //xz->y
+
+ for (int i = 0; i < p_size.x; i++) {
+ for (int j = 0; j < p_size.z; j++) {
+ edt(&work_memory[i + j * z_mult], y_mult, p_size.y);
+ }
+ }
+
+ //yz->x
+ for (int i = 0; i < p_size.y; i++) {
+ for (int j = 0; j < p_size.z; j++) {
+ edt(&work_memory[i * y_mult + j * z_mult], 1, p_size.x);
+ }
+ }
+
+ Vector<uint32_t> ret;
+ ret.resize(float_count);
+ {
+ uint32_t *w = ret.ptrw();
+ for (uint32_t i = 0; i < float_count; i++) {
+ w[i] = uint32_t(Math::sqrt(work_memory[i]));
+ }
+ }
+
+ return ret;
+}
+
+Vector<int8_t> Geometry::generate_sdf8(const Vector<uint32_t> &p_positive, const Vector<uint32_t> &p_negative) {
+ ERR_FAIL_COND_V(p_positive.size() != p_negative.size(), Vector<int8_t>());
+ Vector<int8_t> sdf8;
+ int s = p_positive.size();
+ sdf8.resize(s);
+
+ const uint32_t *rpos = p_positive.ptr();
+ const uint32_t *rneg = p_negative.ptr();
+ int8_t *wsdf = sdf8.ptrw();
+ for (int i = 0; i < s; i++) {
+ int32_t diff = int32_t(rpos[i]) - int32_t(rneg[i]);
+ wsdf[i] = CLAMP(diff, -128, 127);
+ }
+ return sdf8;
+}