summaryrefslogtreecommitdiff
path: root/core/math
diff options
context:
space:
mode:
Diffstat (limited to 'core/math')
-rw-r--r--core/math/aabb.h28
-rw-r--r--core/math/geometry.cpp39
-rw-r--r--core/math/geometry.h2
-rw-r--r--core/math/octree.h18
-rw-r--r--core/math/transform_2d.cpp12
-rw-r--r--core/math/transform_2d.h11
-rw-r--r--core/math/triangle_mesh.cpp8
-rw-r--r--core/math/triangle_mesh.h4
8 files changed, 109 insertions, 13 deletions
diff --git a/core/math/aabb.h b/core/math/aabb.h
index eca74e6755..7fdad07c89 100644
--- a/core/math/aabb.h
+++ b/core/math/aabb.h
@@ -76,7 +76,7 @@ public:
bool intersects_ray(const Vector3 &p_from, const Vector3 &p_dir, Vector3 *r_clip = nullptr, Vector3 *r_normal = nullptr) const;
_FORCE_INLINE_ bool smits_intersect_ray(const Vector3 &p_from, const Vector3 &p_dir, real_t t0, real_t t1) const;
- _FORCE_INLINE_ bool intersects_convex_shape(const Plane *p_planes, int p_plane_count) const;
+ _FORCE_INLINE_ bool intersects_convex_shape(const Plane *p_planes, int p_plane_count, const Vector3 *p_points, int p_point_count) const;
_FORCE_INLINE_ bool inside_convex_shape(const Plane *p_planes, int p_plane_count) const;
bool intersects_plane(const Plane &p_plane) const;
@@ -190,7 +190,7 @@ Vector3 AABB::get_endpoint(int p_point) const {
ERR_FAIL_V(Vector3());
}
-bool AABB::intersects_convex_shape(const Plane *p_planes, int p_plane_count) const {
+bool AABB::intersects_convex_shape(const Plane *p_planes, int p_plane_count, const Vector3 *p_points, int p_point_count) const {
Vector3 half_extents = size * 0.5;
Vector3 ofs = position + half_extents;
@@ -206,6 +206,30 @@ bool AABB::intersects_convex_shape(const Plane *p_planes, int p_plane_count) con
return false;
}
+ // Make sure all points in the shape aren't fully separated from the AABB on
+ // each axis.
+ int bad_point_counts_positive[3] = { 0 };
+ int bad_point_counts_negative[3] = { 0 };
+
+ for (int k = 0; k < 3; k++) {
+
+ for (int i = 0; i < p_point_count; i++) {
+ if (p_points[i].coord[k] > ofs.coord[k] + half_extents.coord[k]) {
+ bad_point_counts_positive[k]++;
+ }
+ if (p_points[i].coord[k] < ofs.coord[k] - half_extents.coord[k]) {
+ bad_point_counts_negative[k]++;
+ }
+ }
+
+ if (bad_point_counts_negative[k] == p_point_count) {
+ return false;
+ }
+ if (bad_point_counts_positive[k] == p_point_count) {
+ return false;
+ }
+ }
+
return true;
}
diff --git a/core/math/geometry.cpp b/core/math/geometry.cpp
index 4733c27cbc..fa96fc4535 100644
--- a/core/math/geometry.cpp
+++ b/core/math/geometry.cpp
@@ -1178,3 +1178,42 @@ Vector<Vector<Point2>> Geometry::_polypath_offset(const Vector<Point2> &p_polypa
}
return polypaths;
}
+
+Vector<Vector3> Geometry::compute_convex_mesh_points(const Plane *p_planes, int p_plane_count) {
+
+ Vector<Vector3> points;
+
+ // Iterate through every unique combination of any three planes.
+ for (int i = p_plane_count - 1; i >= 0; i--) {
+ for (int j = i - 1; j >= 0; j--) {
+ for (int k = j - 1; k >= 0; k--) {
+
+ // Find the point where these planes all cross over (if they
+ // do at all).
+ Vector3 convex_shape_point;
+ if (p_planes[i].intersect_3(p_planes[j], p_planes[k], &convex_shape_point)) {
+
+ // See if any *other* plane excludes this point because it's
+ // on the wrong side.
+ bool excluded = false;
+ for (int n = 0; n < p_plane_count; n++) {
+ if (n != i && n != j && n != k) {
+ real_t dp = p_planes[n].normal.dot(convex_shape_point);
+ if (dp - p_planes[n].d > CMP_EPSILON) {
+ excluded = true;
+ break;
+ }
+ }
+ }
+
+ // Only add the point if it passed all tests.
+ if (!excluded) {
+ points.push_back(convex_shape_point);
+ }
+ }
+ }
+ }
+ }
+
+ return points;
+}
diff --git a/core/math/geometry.h b/core/math/geometry.h
index a86db6e395..ea063a8a59 100644
--- a/core/math/geometry.h
+++ b/core/math/geometry.h
@@ -1014,6 +1014,8 @@ public:
static void make_atlas(const Vector<Size2i> &p_rects, Vector<Point2i> &r_result, Size2i &r_size);
+ static Vector<Vector3> compute_convex_mesh_points(const Plane *p_planes, int p_plane_count);
+
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);
diff --git a/core/math/octree.h b/core/math/octree.h
index 5225fbecb4..ffb405bd0f 100644
--- a/core/math/octree.h
+++ b/core/math/octree.h
@@ -34,6 +34,7 @@
#include "core/list.h"
#include "core/map.h"
#include "core/math/aabb.h"
+#include "core/math/geometry.h"
#include "core/math/vector3.h"
#include "core/print_string.h"
#include "core/variant.h"
@@ -341,6 +342,8 @@ private:
const Plane *planes;
int plane_count;
+ const Vector3 *points;
+ int point_count;
T **result_array;
int *result_idx;
int result_max;
@@ -1017,8 +1020,7 @@ void Octree<T, use_pairs, AL>::_cull_convex(Octant *p_octant, _CullConvexData *p
continue;
e->last_pass = pass;
- if (e->aabb.intersects_convex_shape(p_cull->planes, p_cull->plane_count)) {
-
+ if (e->aabb.intersects_convex_shape(p_cull->planes, p_cull->plane_count, p_cull->points, p_cull->point_count)) {
if (*p_cull->result_idx < p_cull->result_max) {
p_cull->result_array[*p_cull->result_idx] = e->userdata;
(*p_cull->result_idx)++;
@@ -1043,7 +1045,7 @@ void Octree<T, use_pairs, AL>::_cull_convex(Octant *p_octant, _CullConvexData *p
continue;
e->last_pass = pass;
- if (e->aabb.intersects_convex_shape(p_cull->planes, p_cull->plane_count)) {
+ if (e->aabb.intersects_convex_shape(p_cull->planes, p_cull->plane_count, p_cull->points, p_cull->point_count)) {
if (*p_cull->result_idx < p_cull->result_max) {
@@ -1059,7 +1061,7 @@ void Octree<T, use_pairs, AL>::_cull_convex(Octant *p_octant, _CullConvexData *p
for (int i = 0; i < 8; i++) {
- if (p_octant->children[i] && p_octant->children[i]->aabb.intersects_convex_shape(p_cull->planes, p_cull->plane_count)) {
+ if (p_octant->children[i] && p_octant->children[i]->aabb.intersects_convex_shape(p_cull->planes, p_cull->plane_count, p_cull->points, p_cull->point_count)) {
_cull_convex(p_octant->children[i], p_cull);
}
}
@@ -1288,7 +1290,11 @@ void Octree<T, use_pairs, AL>::_cull_point(Octant *p_octant, const Vector3 &p_po
template <class T, bool use_pairs, class AL>
int Octree<T, use_pairs, AL>::cull_convex(const Vector<Plane> &p_convex, T **p_result_array, int p_result_max, uint32_t p_mask) {
- if (!root)
+ if (!root || p_convex.size() == 0)
+ return 0;
+
+ Vector<Vector3> convex_points = Geometry::compute_convex_mesh_points(&p_convex[0], p_convex.size());
+ if (convex_points.size() == 0)
return 0;
int result_count = 0;
@@ -1296,6 +1302,8 @@ int Octree<T, use_pairs, AL>::cull_convex(const Vector<Plane> &p_convex, T **p_r
_CullConvexData cdata;
cdata.planes = &p_convex[0];
cdata.plane_count = p_convex.size();
+ cdata.points = &convex_points[0];
+ cdata.point_count = convex_points.size();
cdata.result_array = p_result_array;
cdata.result_max = p_result_max;
cdata.result_idx = &result_count;
diff --git a/core/math/transform_2d.cpp b/core/math/transform_2d.cpp
index 97a9216a5a..ed95baa233 100644
--- a/core/math/transform_2d.cpp
+++ b/core/math/transform_2d.cpp
@@ -70,6 +70,18 @@ void Transform2D::rotate(real_t p_phi) {
*this = Transform2D(p_phi, Vector2()) * (*this);
}
+real_t Transform2D::get_skew() const {
+
+ real_t det = basis_determinant();
+ return Math::acos(elements[0].normalized().dot(SGN(det) * elements[1].normalized())) - Math_PI * 0.5;
+}
+
+void Transform2D::set_skew(float p_angle) {
+
+ real_t det = basis_determinant();
+ elements[1] = SGN(det) * elements[0].rotated((Math_PI * 0.5 + p_angle)).normalized() * elements[1].length();
+}
+
real_t Transform2D::get_rotation() const {
real_t det = basis_determinant();
Transform2D m = orthonormalized();
diff --git a/core/math/transform_2d.h b/core/math/transform_2d.h
index fa43762aa4..459ceed7a9 100644
--- a/core/math/transform_2d.h
+++ b/core/math/transform_2d.h
@@ -70,7 +70,10 @@ struct Transform2D {
void set_rotation(real_t p_rot);
real_t get_rotation() const;
+ real_t get_skew() const;
+ void set_skew(float p_angle);
_FORCE_INLINE_ void set_rotation_and_scale(real_t p_rot, const Size2 &p_scale);
+ _FORCE_INLINE_ void set_rotation_scale_and_skew(real_t p_rot, const Size2 &p_scale, float p_skew);
void rotate(real_t p_phi);
void scale(const Size2 &p_scale);
@@ -184,6 +187,14 @@ void Transform2D::set_rotation_and_scale(real_t p_rot, const Size2 &p_scale) {
elements[0][1] = Math::sin(p_rot) * p_scale.x;
}
+void Transform2D::set_rotation_scale_and_skew(real_t p_rot, const Size2 &p_scale, float p_skew) {
+
+ elements[0][0] = Math::cos(p_rot) * p_scale.x;
+ elements[1][1] = Math::cos(p_rot + p_skew) * p_scale.y;
+ elements[1][0] = -Math::sin(p_rot + p_skew) * p_scale.y;
+ elements[0][1] = Math::sin(p_rot) * p_scale.x;
+}
+
Rect2 Transform2D::xform_inv(const Rect2 &p_rect) const {
Vector2 ends[4] = {
diff --git a/core/math/triangle_mesh.cpp b/core/math/triangle_mesh.cpp
index 01d38cf24e..5c66721b9d 100644
--- a/core/math/triangle_mesh.cpp
+++ b/core/math/triangle_mesh.cpp
@@ -502,7 +502,7 @@ bool TriangleMesh::intersect_ray(const Vector3 &p_begin, const Vector3 &p_dir, V
return inters;
}
-bool TriangleMesh::intersect_convex_shape(const Plane *p_planes, int p_plane_count) const {
+bool TriangleMesh::intersect_convex_shape(const Plane *p_planes, int p_plane_count, const Vector3 *p_points, int p_point_count) const {
uint32_t *stack = (uint32_t *)alloca(sizeof(int) * max_depth);
//p_fully_inside = true;
@@ -536,7 +536,7 @@ bool TriangleMesh::intersect_convex_shape(const Plane *p_planes, int p_plane_cou
switch (stack[level] >> VISITED_BIT_SHIFT) {
case TEST_AABB_BIT: {
- bool valid = b.aabb.intersects_convex_shape(p_planes, p_plane_count);
+ bool valid = b.aabb.intersects_convex_shape(p_planes, p_plane_count, p_points, p_point_count);
if (!valid) {
stack[level] = (VISIT_DONE_BIT << VISITED_BIT_SHIFT) | node;
@@ -617,7 +617,7 @@ bool TriangleMesh::intersect_convex_shape(const Plane *p_planes, int p_plane_cou
return false;
}
-bool TriangleMesh::inside_convex_shape(const Plane *p_planes, int p_plane_count, Vector3 p_scale) const {
+bool TriangleMesh::inside_convex_shape(const Plane *p_planes, int p_plane_count, const Vector3 *p_points, int p_point_count, Vector3 p_scale) const {
uint32_t *stack = (uint32_t *)alloca(sizeof(int) * max_depth);
enum {
@@ -651,7 +651,7 @@ bool TriangleMesh::inside_convex_shape(const Plane *p_planes, int p_plane_count,
switch (stack[level] >> VISITED_BIT_SHIFT) {
case TEST_AABB_BIT: {
- bool intersects = scale.xform(b.aabb).intersects_convex_shape(p_planes, p_plane_count);
+ bool intersects = scale.xform(b.aabb).intersects_convex_shape(p_planes, p_plane_count, p_points, p_point_count);
if (!intersects) return false;
bool inside = scale.xform(b.aabb).inside_convex_shape(p_planes, p_plane_count);
diff --git a/core/math/triangle_mesh.h b/core/math/triangle_mesh.h
index fdbfb90465..64704477cc 100644
--- a/core/math/triangle_mesh.h
+++ b/core/math/triangle_mesh.h
@@ -90,8 +90,8 @@ public:
bool is_valid() const;
bool intersect_segment(const Vector3 &p_begin, const Vector3 &p_end, Vector3 &r_point, Vector3 &r_normal) const;
bool intersect_ray(const Vector3 &p_begin, const Vector3 &p_dir, Vector3 &r_point, Vector3 &r_normal) const;
- bool intersect_convex_shape(const Plane *p_planes, int p_plane_count) const;
- bool inside_convex_shape(const Plane *p_planes, int p_plane_count, Vector3 p_scale = Vector3(1, 1, 1)) const;
+ bool intersect_convex_shape(const Plane *p_planes, int p_plane_count, const Vector3 *p_points, int p_point_count) const;
+ bool inside_convex_shape(const Plane *p_planes, int p_plane_count, const Vector3 *p_points, int p_point_count, Vector3 p_scale = Vector3(1, 1, 1)) const;
Vector3 get_area_normal(const AABB &p_aabb) const;
Vector<Face3> get_faces() const;
generated by cgit v1.2.3 (git 2.25.1) at 2025-04-12 22:44:08 +0000