summaryrefslogtreecommitdiff
path: root/core/math/geometry.h
diff options
context:
space:
mode:
Diffstat (limited to 'core/math/geometry.h')
-rw-r--r--core/math/geometry.h243
1 files changed, 243 insertions, 0 deletions
diff --git a/core/math/geometry.h b/core/math/geometry.h
index 3bbd1911ee..5a8e21d02b 100644
--- a/core/math/geometry.h
+++ b/core/math/geometry.h
@@ -1024,6 +1024,249 @@ public:
static Vector<Vector3> compute_convex_mesh_points(const Plane *p_planes, int p_plane_count);
+#define FINDMINMAX(x0, x1, x2, min, max) \
+ min = max = x0; \
+ if (x1 < min) \
+ min = x1; \
+ if (x1 > max) \
+ max = x1; \
+ if (x2 < min) \
+ min = x2; \
+ if (x2 > max) \
+ max = x2;
+
+ _FORCE_INLINE_ static bool planeBoxOverlap(Vector3 normal, float d, Vector3 maxbox) {
+ int q;
+ Vector3 vmin, vmax;
+ for (q = 0; q <= 2; q++) {
+ if (normal[q] > 0.0f) {
+ vmin[q] = -maxbox[q];
+ vmax[q] = maxbox[q];
+ } else {
+ vmin[q] = maxbox[q];
+ vmax[q] = -maxbox[q];
+ }
+ }
+ if (normal.dot(vmin) + d > 0.0f)
+ return false;
+ if (normal.dot(vmax) + d >= 0.0f)
+ return true;
+
+ return false;
+ }
+
+/*======================== X-tests ========================*/
+#define AXISTEST_X01(a, b, fa, fb) \
+ p0 = a * v0.y - b * v0.z; \
+ p2 = a * v2.y - b * v2.z; \
+ if (p0 < p2) { \
+ min = p0; \
+ max = p2; \
+ } else { \
+ min = p2; \
+ max = p0; \
+ } \
+ rad = fa * boxhalfsize.y + fb * boxhalfsize.z; \
+ if (min > rad || max < -rad) \
+ return false;
+
+#define AXISTEST_X2(a, b, fa, fb) \
+ p0 = a * v0.y - b * v0.z; \
+ p1 = a * v1.y - b * v1.z; \
+ if (p0 < p1) { \
+ min = p0; \
+ max = p1; \
+ } else { \
+ min = p1; \
+ max = p0; \
+ } \
+ rad = fa * boxhalfsize.y + fb * boxhalfsize.z; \
+ if (min > rad || max < -rad) \
+ return false;
+
+/*======================== Y-tests ========================*/
+#define AXISTEST_Y02(a, b, fa, fb) \
+ p0 = -a * v0.x + b * v0.z; \
+ p2 = -a * v2.x + b * v2.z; \
+ if (p0 < p2) { \
+ min = p0; \
+ max = p2; \
+ } else { \
+ min = p2; \
+ max = p0; \
+ } \
+ rad = fa * boxhalfsize.x + fb * boxhalfsize.z; \
+ if (min > rad || max < -rad) \
+ return false;
+
+#define AXISTEST_Y1(a, b, fa, fb) \
+ p0 = -a * v0.x + b * v0.z; \
+ p1 = -a * v1.x + b * v1.z; \
+ if (p0 < p1) { \
+ min = p0; \
+ max = p1; \
+ } else { \
+ min = p1; \
+ max = p0; \
+ } \
+ rad = fa * boxhalfsize.x + fb * boxhalfsize.z; \
+ if (min > rad || max < -rad) \
+ return false;
+
+ /*======================== Z-tests ========================*/
+
+#define AXISTEST_Z12(a, b, fa, fb) \
+ p1 = a * v1.x - b * v1.y; \
+ p2 = a * v2.x - b * v2.y; \
+ if (p2 < p1) { \
+ min = p2; \
+ max = p1; \
+ } else { \
+ min = p1; \
+ max = p2; \
+ } \
+ rad = fa * boxhalfsize.x + fb * boxhalfsize.y; \
+ if (min > rad || max < -rad) \
+ return false;
+
+#define AXISTEST_Z0(a, b, fa, fb) \
+ p0 = a * v0.x - b * v0.y; \
+ p1 = a * v1.x - b * v1.y; \
+ if (p0 < p1) { \
+ min = p0; \
+ max = p1; \
+ } else { \
+ min = p1; \
+ max = p0; \
+ } \
+ rad = fa * boxhalfsize.x + fb * boxhalfsize.y; \
+ if (min > rad || max < -rad) \
+ return false;
+
+ _FORCE_INLINE_ static bool triangle_box_overlap(const Vector3 &boxcenter, const Vector3 boxhalfsize, const Vector3 *triverts) {
+
+ /* use separating axis theorem to test overlap between triangle and box */
+ /* need to test for overlap in these directions: */
+ /* 1) the {x,y,z}-directions (actually, since we use the AABB of the triangle */
+ /* we do not even need to test these) */
+ /* 2) normal of the triangle */
+ /* 3) crossproduct(edge from tri, {x,y,z}-directin) */
+ /* this gives 3x3=9 more tests */
+ Vector3 v0, v1, v2;
+ float min, max, d, p0, p1, p2, rad, fex, fey, fez;
+ Vector3 normal, e0, e1, e2;
+
+ /* This is the fastest branch on Sun */
+ /* move everything so that the boxcenter is in (0,0,0) */
+
+ v0 = triverts[0] - boxcenter;
+ v1 = triverts[1] - boxcenter;
+ v2 = triverts[2] - boxcenter;
+
+ /* compute triangle edges */
+ e0 = v1 - v0; /* tri edge 0 */
+ e1 = v2 - v1; /* tri edge 1 */
+ e2 = v0 - v2; /* tri edge 2 */
+
+ /* Bullet 3: */
+ /* test the 9 tests first (this was faster) */
+ fex = Math::abs(e0.x);
+ fey = Math::abs(e0.y);
+ fez = Math::abs(e0.z);
+ AXISTEST_X01(e0.z, e0.y, fez, fey);
+ AXISTEST_Y02(e0.z, e0.x, fez, fex);
+ AXISTEST_Z12(e0.y, e0.x, fey, fex);
+
+ fex = Math::abs(e1.x);
+ fey = Math::abs(e1.y);
+ fez = Math::abs(e1.z);
+ AXISTEST_X01(e1.z, e1.y, fez, fey);
+ AXISTEST_Y02(e1.z, e1.x, fez, fex);
+ AXISTEST_Z0(e1.y, e1.x, fey, fex);
+
+ fex = Math::abs(e2.x);
+ fey = Math::abs(e2.y);
+ fez = Math::abs(e2.z);
+ AXISTEST_X2(e2.z, e2.y, fez, fey);
+ AXISTEST_Y1(e2.z, e2.x, fez, fex);
+ AXISTEST_Z12(e2.y, e2.x, fey, fex);
+
+ /* Bullet 1: */
+ /* first test overlap in the {x,y,z}-directions */
+ /* find min, max of the triangle each direction, and test for overlap in */
+ /* that direction -- this is equivalent to testing a minimal AABB around */
+ /* the triangle against the AABB */
+
+ /* test in X-direction */
+ FINDMINMAX(v0.x, v1.x, v2.x, min, max);
+ if (min > boxhalfsize.x || max < -boxhalfsize.x)
+ return false;
+
+ /* test in Y-direction */
+ FINDMINMAX(v0.y, v1.y, v2.y, min, max);
+ if (min > boxhalfsize.y || max < -boxhalfsize.y)
+ return false;
+
+ /* test in Z-direction */
+ FINDMINMAX(v0.z, v1.z, v2.z, min, max);
+ if (min > boxhalfsize.z || max < -boxhalfsize.z)
+ return false;
+
+ /* Bullet 2: */
+ /* test if the box intersects the plane of the triangle */
+ /* compute plane equation of triangle: normal*x+d=0 */
+ normal = e0.cross(e1);
+ d = -normal.dot(v0); /* plane eq: normal.x+d=0 */
+ return planeBoxOverlap(normal, d, boxhalfsize); /* if true, box and triangle overlaps */
+ }
+
+ static Vector<Point2i> pack_rects(const Vector<Size2i> &p_sizes, const Size2i &p_atlas_size);
+ static Vector<Vector3i> partial_pack_rects(const Vector<Vector2i> &p_sizes, const Size2i &p_atlas_size);
+
+ static Vector<uint32_t> generate_edf(const Vector<bool> &p_voxels, const Vector3i &p_size, bool p_negative);
+ static Vector<int8_t> generate_sdf8(const Vector<uint32_t> &p_positive, const Vector<uint32_t> &p_negative);
+
+ static Vector3 triangle_get_barycentric_coords(const Vector3 &p_a, const Vector3 &p_b, const Vector3 &p_c, const Vector3 &p_pos) {
+ Vector3 v0 = p_b - p_a;
+ Vector3 v1 = p_c - p_a;
+ Vector3 v2 = p_pos - p_a;
+
+ float d00 = v0.dot(v0);
+ float d01 = v0.dot(v1);
+ float d11 = v1.dot(v1);
+ float d20 = v2.dot(v0);
+ float d21 = v2.dot(v1);
+ float denom = (d00 * d11 - d01 * d01);
+ if (denom == 0) {
+ return Vector3(); //invalid triangle, return empty
+ }
+ float v = (d11 * d20 - d01 * d21) / denom;
+ float w = (d00 * d21 - d01 * d20) / denom;
+ float u = 1.0f - v - w;
+ return Vector3(u, v, w);
+ }
+
+ static Color tetrahedron_get_barycentric_coords(const Vector3 &p_a, const Vector3 &p_b, const Vector3 &p_c, const Vector3 &p_d, const Vector3 &p_pos) {
+ Vector3 vap = p_pos - p_a;
+ Vector3 vbp = p_pos - p_b;
+
+ Vector3 vab = p_b - p_a;
+ Vector3 vac = p_c - p_a;
+ Vector3 vad = p_d - p_a;
+
+ Vector3 vbc = p_c - p_b;
+ Vector3 vbd = p_d - p_b;
+ // ScTP computes the scalar triple product
+#define STP(m_a, m_b, m_c) ((m_a).dot((m_b).cross((m_c))))
+ float va6 = STP(vbp, vbd, vbc);
+ float vb6 = STP(vap, vac, vad);
+ float vc6 = STP(vap, vad, vab);
+ float vd6 = STP(vap, vab, vac);
+ float v6 = 1 / STP(vab, vac, vad);
+ return Color(va6 * v6, vb6 * v6, vc6 * v6, vd6 * v6);
+#undef STP
+ }
+
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);
generated by cgit v1.2.3 (git 2.25.1) at 2024-11-22 03:59:45 +0000