summaryrefslogtreecommitdiff
path: root/modules/csg/csg.cpp
diff options
context:
space:
mode:
Diffstat (limited to 'modules/csg/csg.cpp')
-rw-r--r--modules/csg/csg.cpp135
1 files changed, 102 insertions, 33 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);
generated by cgit v1.2.3 (git 2.25.1) at 2024-11-22 01:31:51 +0000