summaryrefslogtreecommitdiff
path: root/modules/csg
diff options
context:
space:
mode:
Diffstat (limited to 'modules/csg')
-rw-r--r--modules/csg/csg.cpp135
-rw-r--r--modules/csg/csg.h17
-rw-r--r--modules/csg/csg_shape.cpp2
-rw-r--r--modules/csg/doc_classes/CSGShape3D.xml2
4 files changed, 118 insertions, 38 deletions
diff --git a/modules/csg/csg.cpp b/modules/csg/csg.cpp
index dee95d1ac5..878664bb9c 100644
--- a/modules/csg/csg.cpp
+++ b/modules/csg/csg.cpp
@@ -467,7 +467,7 @@ void CSGBrushOperation::merge_brushes(Operation p_operation, const CSGBrush &p_b
// Use a limit to speed up bvh and limit the depth.
#define BVH_LIMIT 8
-int CSGBrushOperation::MeshMerge::_create_bvh(FaceBVH *facebvhptr, FaceBVH **facebvhptrptr, int p_from, int p_size, int p_depth, int &r_max_depth, int &r_max_alloc) {
+int CSGBrushOperation::MeshMerge::_create_bvh(FaceBVH *r_facebvhptr, FaceBVH **r_facebvhptrptr, int p_from, int p_size, int p_depth, int &r_max_depth, int &r_max_alloc) {
if (p_depth > r_max_depth) {
r_max_depth = p_depth;
}
@@ -478,15 +478,15 @@ int CSGBrushOperation::MeshMerge::_create_bvh(FaceBVH *facebvhptr, FaceBVH **fac
if (p_size <= BVH_LIMIT) {
for (int i = 0; i < p_size - 1; i++) {
- facebvhptrptr[p_from + i]->next = facebvhptrptr[p_from + i + 1] - facebvhptr;
+ r_facebvhptrptr[p_from + i]->next = r_facebvhptrptr[p_from + i + 1] - r_facebvhptr;
}
- return facebvhptrptr[p_from] - facebvhptr;
+ return r_facebvhptrptr[p_from] - r_facebvhptr;
}
AABB aabb;
- aabb = facebvhptrptr[p_from]->aabb;
+ aabb = r_facebvhptrptr[p_from]->aabb;
for (int i = 1; i < p_size; i++) {
- aabb.merge_with(facebvhptrptr[p_from + i]->aabb);
+ aabb.merge_with(r_facebvhptrptr[p_from + i]->aabb);
}
int li = aabb.get_longest_axis_index();
@@ -494,28 +494,28 @@ int CSGBrushOperation::MeshMerge::_create_bvh(FaceBVH *facebvhptr, FaceBVH **fac
switch (li) {
case Vector3::AXIS_X: {
SortArray<FaceBVH *, FaceBVHCmpX> sort_x;
- sort_x.nth_element(0, p_size, p_size / 2, &facebvhptrptr[p_from]);
+ sort_x.nth_element(0, p_size, p_size / 2, &r_facebvhptrptr[p_from]);
//sort_x.sort(&p_bb[p_from],p_size);
} break;
case Vector3::AXIS_Y: {
SortArray<FaceBVH *, FaceBVHCmpY> sort_y;
- sort_y.nth_element(0, p_size, p_size / 2, &facebvhptrptr[p_from]);
+ sort_y.nth_element(0, p_size, p_size / 2, &r_facebvhptrptr[p_from]);
//sort_y.sort(&p_bb[p_from],p_size);
} break;
case Vector3::AXIS_Z: {
SortArray<FaceBVH *, FaceBVHCmpZ> sort_z;
- sort_z.nth_element(0, p_size, p_size / 2, &facebvhptrptr[p_from]);
+ sort_z.nth_element(0, p_size, p_size / 2, &r_facebvhptrptr[p_from]);
//sort_z.sort(&p_bb[p_from],p_size);
} break;
}
- int left = _create_bvh(facebvhptr, facebvhptrptr, p_from, p_size / 2, p_depth + 1, r_max_depth, r_max_alloc);
- int right = _create_bvh(facebvhptr, facebvhptrptr, p_from + p_size / 2, p_size - p_size / 2, p_depth + 1, r_max_depth, r_max_alloc);
+ int left = _create_bvh(r_facebvhptr, r_facebvhptrptr, p_from, p_size / 2, p_depth + 1, r_max_depth, r_max_alloc);
+ int right = _create_bvh(r_facebvhptr, r_facebvhptrptr, p_from + p_size / 2, p_size - p_size / 2, p_depth + 1, r_max_depth, r_max_alloc);
int index = r_max_alloc++;
- FaceBVH *_new = &facebvhptr[index];
+ FaceBVH *_new = &r_facebvhptr[index];
_new->aabb = aabb;
_new->center = aabb.get_center();
_new->face = -1;
@@ -526,20 +526,22 @@ int CSGBrushOperation::MeshMerge::_create_bvh(FaceBVH *facebvhptr, FaceBVH **fac
return index;
}
-void CSGBrushOperation::MeshMerge::_add_distance(List<real_t> &r_intersectionsA, List<real_t> &r_intersectionsB, bool p_from_B, real_t p_distance) const {
- List<real_t> &intersections = p_from_B ? r_intersectionsB : r_intersectionsA;
+void CSGBrushOperation::MeshMerge::_add_distance(List<IntersectionDistance> &r_intersectionsA, List<IntersectionDistance> &r_intersectionsB, bool p_from_B, real_t p_distance_squared, bool p_is_conormal) const {
+ List<IntersectionDistance> &intersections = p_from_B ? r_intersectionsB : r_intersectionsA;
// Check if distance exists.
- for (const real_t E : intersections) {
- if (Math::is_equal_approx(E, p_distance)) {
+ for (const IntersectionDistance E : intersections) {
+ if (E.is_conormal == p_is_conormal && Math::is_equal_approx(E.distance_squared, p_distance_squared)) {
return;
}
}
-
- intersections.push_back(p_distance);
+ IntersectionDistance distance;
+ distance.is_conormal = p_is_conormal;
+ distance.distance_squared = p_distance_squared;
+ intersections.push_back(distance);
}
-bool CSGBrushOperation::MeshMerge::_bvh_inside(FaceBVH *facebvhptr, int p_max_depth, int p_bvh_first, int p_face_idx) const {
+bool CSGBrushOperation::MeshMerge::_bvh_inside(FaceBVH *r_facebvhptr, int p_max_depth, int p_bvh_first, int p_face_idx) const {
Face face = faces[p_face_idx];
Vector3 face_points[3] = {
points[face.points[0]],
@@ -561,8 +563,11 @@ bool CSGBrushOperation::MeshMerge::_bvh_inside(FaceBVH *facebvhptr, int p_max_de
VISITED_BIT_MASK = ~NODE_IDX_MASK
};
- List<real_t> intersectionsA;
- List<real_t> intersectionsB;
+ List<IntersectionDistance> intersectionsA;
+ List<IntersectionDistance> intersectionsB;
+
+ Intersection closest_intersection;
+ closest_intersection.found = false;
int level = 0;
int pos = p_bvh_first;
@@ -570,7 +575,7 @@ bool CSGBrushOperation::MeshMerge::_bvh_inside(FaceBVH *facebvhptr, int p_max_de
while (true) {
uint32_t node = stack[level] & NODE_IDX_MASK;
- const FaceBVH *current_facebvhptr = &(facebvhptr[node]);
+ const FaceBVH *current_facebvhptr = &(r_facebvhptr[node]);
bool done = false;
switch (stack[level] >> VISITED_BIT_SHIFT) {
@@ -587,22 +592,66 @@ bool CSGBrushOperation::MeshMerge::_bvh_inside(FaceBVH *facebvhptr, int p_max_de
};
Vector3 current_normal = Plane(current_points[0], current_points[1], current_points[2]).normal;
Vector3 intersection_point;
-
// Check if faces are co-planar.
if (current_normal.is_equal_approx(face_normal) &&
is_point_in_triangle(face_center, current_points)) {
// Only add an intersection if not a B face.
if (!face.from_b) {
- _add_distance(intersectionsA, intersectionsB, current_face.from_b, 0);
+ _add_distance(intersectionsA, intersectionsB, current_face.from_b, 0, true);
}
} else if (ray_intersects_triangle(face_center, face_normal, current_points, CMP_EPSILON, intersection_point)) {
- real_t distance = face_center.distance_to(intersection_point);
- _add_distance(intersectionsA, intersectionsB, current_face.from_b, distance);
+ real_t distance_squared = face_center.distance_squared_to(intersection_point);
+ real_t inner = current_normal.dot(face_normal);
+ // If the faces are perpendicular, ignore this face.
+ // The triangles on the side should be intersected and result in the correct behavior.
+ if (!Math::is_zero_approx(inner)) {
+ _add_distance(intersectionsA, intersectionsB, current_face.from_b, distance_squared, inner > 0.0f);
+ }
+ }
+
+ if (face.from_b != current_face.from_b) {
+ if (current_normal.is_equal_approx(face_normal) &&
+ is_point_in_triangle(face_center, current_points)) {
+ // Only add an intersection if not a B face.
+ if (!face.from_b) {
+ closest_intersection.found = true;
+ closest_intersection.conormal = 1.0f;
+ closest_intersection.distance_squared = 0.0f;
+ closest_intersection.origin_angle = -FLT_MAX;
+ }
+ } else if (ray_intersects_triangle(face_center, face_normal, current_points, CMP_EPSILON, intersection_point)) {
+ Intersection potential_intersection;
+ potential_intersection.found = true;
+ potential_intersection.conormal = face_normal.dot(current_normal);
+ potential_intersection.distance_squared = face_center.distance_squared_to(intersection_point);
+ potential_intersection.origin_angle = Math::abs(potential_intersection.conormal);
+ real_t intersection_dist_from_face = face_normal.dot(intersection_point - face_center);
+ for (int i = 0; i < 3; i++) {
+ real_t point_dist_from_face = face_normal.dot(current_points[i] - face_center);
+ if (!Math::is_equal_approx(point_dist_from_face, intersection_dist_from_face) &&
+ point_dist_from_face < intersection_dist_from_face) {
+ potential_intersection.origin_angle = -potential_intersection.origin_angle;
+ break;
+ }
+ }
+ if (potential_intersection.conormal != 0.0f) {
+ if (!closest_intersection.found) {
+ closest_intersection = potential_intersection;
+ } else if (!Math::is_equal_approx(potential_intersection.distance_squared, closest_intersection.distance_squared) &&
+ potential_intersection.distance_squared < closest_intersection.distance_squared) {
+ closest_intersection = potential_intersection;
+ } else if (Math::is_equal_approx(potential_intersection.distance_squared, closest_intersection.distance_squared)) {
+ if (potential_intersection.origin_angle < closest_intersection.origin_angle) {
+ closest_intersection = potential_intersection;
+ }
+ }
+ }
+ }
}
}
if (current_facebvhptr->next != -1) {
- current_facebvhptr = &facebvhptr[current_facebvhptr->next];
+ current_facebvhptr = &r_facebvhptr[current_facebvhptr->next];
} else {
current_facebvhptr = nullptr;
}
@@ -652,8 +701,11 @@ bool CSGBrushOperation::MeshMerge::_bvh_inside(FaceBVH *facebvhptr, int p_max_de
}
}
- // Inside if face normal intersects other faces an odd number of times.
- return (intersectionsA.size() + intersectionsB.size()) & 1;
+ if (!closest_intersection.found) {
+ return false;
+ } else {
+ return closest_intersection.conormal > 0.0f;
+ }
}
void CSGBrushOperation::MeshMerge::mark_inside_faces() {
@@ -1016,6 +1068,8 @@ void CSGBrushOperation::Build2DFaces::_merge_faces(const Vector<int> &p_segment_
}
void CSGBrushOperation::Build2DFaces::_find_edge_intersections(const Vector2 p_segment_points[2], Vector<int> &r_segment_indices) {
+ LocalVector<Vector<Vector2>> processed_edges;
+
// For each face.
for (int face_idx = 0; face_idx < faces.size(); ++face_idx) {
Face2D face = faces[face_idx];
@@ -1027,17 +1081,32 @@ void CSGBrushOperation::Build2DFaces::_find_edge_intersections(const Vector2 p_s
// Check each edge.
for (int face_edge_idx = 0; face_edge_idx < 3; ++face_edge_idx) {
- Vector2 edge_points[2] = {
+ Vector<Vector2> edge_points_and_uvs = {
face_vertices[face_edge_idx].point,
- face_vertices[(face_edge_idx + 1) % 3].point
- };
- Vector2 edge_uvs[2] = {
+ face_vertices[(face_edge_idx + 1) % 3].point,
face_vertices[face_edge_idx].uv,
face_vertices[(face_edge_idx + 1) % 3].uv
};
- Vector2 intersection_point;
+
+ Vector2 edge_points[2] = {
+ edge_points_and_uvs[0],
+ edge_points_and_uvs[1],
+ };
+ Vector2 edge_uvs[2] = {
+ edge_points_and_uvs[2],
+ edge_points_and_uvs[3],
+ };
+
+ // Check if edge has already been processed.
+ if (processed_edges.find(edge_points_and_uvs) != -1) {
+ continue;
+ }
+
+ processed_edges.push_back(edge_points_and_uvs);
// First check if the ends of the segment are on the edge.
+ Vector2 intersection_point;
+
bool on_edge = false;
for (int edge_point_idx = 0; edge_point_idx < 2; ++edge_point_idx) {
intersection_point = Geometry2D::get_closest_point_to_segment(p_segment_points[edge_point_idx], edge_points);
diff --git a/modules/csg/csg.h b/modules/csg/csg.h
index 1513a01f9e..2a0831e1ce 100644
--- a/modules/csg/csg.h
+++ b/modules/csg/csg.h
@@ -135,6 +135,17 @@ struct CSGBrushOperation {
return h;
}
};
+ struct Intersection {
+ bool found = false;
+ real_t conormal = FLT_MAX;
+ real_t distance_squared = FLT_MAX;
+ real_t origin_angle = FLT_MAX;
+ };
+
+ struct IntersectionDistance {
+ bool is_conormal;
+ real_t distance_squared;
+ };
Vector<Vector3> points;
Vector<Face> faces;
@@ -143,9 +154,9 @@ struct CSGBrushOperation {
OAHashMap<VertexKey, int, VertexKeyHash> snap_cache;
float vertex_snap = 0.0;
- inline void _add_distance(List<real_t> &r_intersectionsA, List<real_t> &r_intersectionsB, bool p_from_B, real_t p_distance) const;
- inline bool _bvh_inside(FaceBVH *facebvhptr, int p_max_depth, int p_bvh_first, int p_face_idx) const;
- inline int _create_bvh(FaceBVH *facebvhptr, FaceBVH **facebvhptrptr, int p_from, int p_size, int p_depth, int &r_max_depth, int &r_max_alloc);
+ inline void _add_distance(List<IntersectionDistance> &r_intersectionsA, List<IntersectionDistance> &r_intersectionsB, bool p_from_B, real_t p_distance, bool p_is_conormal) const;
+ inline bool _bvh_inside(FaceBVH *r_facebvhptr, int p_max_depth, int p_bvh_first, int p_face_idx) const;
+ inline int _create_bvh(FaceBVH *r_facebvhptr, FaceBVH **r_facebvhptrptr, int p_from, int p_size, int p_depth, int &r_max_depth, int &r_max_alloc);
void add_face(const Vector3 p_points[3], const Vector2 p_uvs[3], bool p_smooth, bool p_invert, const Ref<Material> &p_material, bool p_from_b);
void mark_inside_faces();
diff --git a/modules/csg/csg_shape.cpp b/modules/csg/csg_shape.cpp
index afb8e62eea..ba0d49c993 100644
--- a/modules/csg/csg_shape.cpp
+++ b/modules/csg/csg_shape.cpp
@@ -653,7 +653,7 @@ void CSGShape3D::_bind_methods() {
ClassDB::bind_method(D_METHOD("get_meshes"), &CSGShape3D::get_meshes);
ADD_PROPERTY(PropertyInfo(Variant::INT, "operation", PROPERTY_HINT_ENUM, "Union,Intersection,Subtraction"), "set_operation", "get_operation");
- ADD_PROPERTY(PropertyInfo(Variant::FLOAT, "snap", PROPERTY_HINT_RANGE, "0.0001,1,0.001,suffix:m"), "set_snap", "get_snap");
+ ADD_PROPERTY(PropertyInfo(Variant::FLOAT, "snap", PROPERTY_HINT_RANGE, "0.000001,1,0.000001,suffix:m"), "set_snap", "get_snap");
ADD_PROPERTY(PropertyInfo(Variant::BOOL, "calculate_tangents"), "set_calculate_tangents", "is_calculating_tangents");
ADD_GROUP("Collision", "collision_");
diff --git a/modules/csg/doc_classes/CSGShape3D.xml b/modules/csg/doc_classes/CSGShape3D.xml
index 06f8f5a403..c29c3c789e 100644
--- a/modules/csg/doc_classes/CSGShape3D.xml
+++ b/modules/csg/doc_classes/CSGShape3D.xml
@@ -73,7 +73,7 @@
The operation that is performed on this shape. This is ignored for the first CSG child node as the operation is between this node and the previous child of this nodes parent.
</member>
<member name="snap" type="float" setter="set_snap" getter="get_snap" default="0.001">
- Snap makes the mesh snap to a given distance so that the faces of two meshes can be perfectly aligned. A lower value results in greater precision but may be harder to adjust.
+ Snap makes the mesh vertices snap to a given distance so that the faces of two meshes can be perfectly aligned. A lower value results in greater precision but may be harder to adjust.
</member>
<member name="use_collision" type="bool" setter="set_use_collision" getter="is_using_collision" default="false">
Adds a collision shape to the physics engine for our CSG shape. This will always act like a static body. Note that the collision shape is still active even if the CSG shape itself is hidden. See also [member collision_mask] and [member collision_priority].
generated by cgit v1.2.3 (git 2.25.1) at 2024-11-22 07:04:43 +0000