1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
//! Parallel versions of [BSP](https://en.wikipedia.org/wiki/Binary_space_partitioning) operations
use crate::mesh::bsp::Node;
use std::fmt::Debug;
#[cfg(feature = "parallel")]
use crate::mesh::plane::{BACK, COPLANAR, FRONT, Plane, SPANNING};
#[cfg(feature = "parallel")]
use rayon::prelude::*;
#[cfg(feature = "parallel")]
use crate::mesh::Polygon;
#[cfg(feature = "parallel")]
use crate::mesh::Vertex;
#[cfg(feature = "parallel")]
use crate::float_types::EPSILON;
impl<S: Clone + Send + Sync + Debug> Node<S> {
/// Invert all polygons in the BSP tree using iterative approach to avoid stack overflow
#[cfg(feature = "parallel")]
pub fn invert(&mut self) {
// Use iterative approach with a stack to avoid recursive stack overflow
let mut stack = vec![self];
while let Some(node) = stack.pop() {
// Flip all polygons and plane in this node
node.polygons.par_iter_mut().for_each(|p| p.flip());
if let Some(ref mut plane) = node.plane {
plane.flip();
}
// Swap front and back children
std::mem::swap(&mut node.front, &mut node.back);
// Add children to stack for processing
if let Some(ref mut front) = node.front {
stack.push(front.as_mut());
}
if let Some(ref mut back) = node.back {
stack.push(back.as_mut());
}
}
}
/// Parallel version of clip Polygons
#[cfg(feature = "parallel")]
pub fn clip_polygons(&self, polygons: &[Polygon<S>]) -> Vec<Polygon<S>> {
// If this node has no plane, just return the original set
if self.plane.is_none() {
return polygons.to_vec();
}
let plane = self.plane.as_ref().unwrap();
// Split each polygon in parallel; gather results
let (coplanar_front, coplanar_back, mut front, mut back) = polygons
.par_iter()
.map(|poly| plane.split_polygon(poly)) // <-- just pass poly
.reduce(
|| (Vec::new(), Vec::new(), Vec::new(), Vec::new()),
|mut acc, x| {
acc.0.extend(x.0);
acc.1.extend(x.1);
acc.2.extend(x.2);
acc.3.extend(x.3);
acc
},
);
// Decide where to send the coplanar polygons
for cp in coplanar_front {
if plane.orient_plane(&cp.plane) == FRONT {
front.push(cp);
} else {
back.push(cp);
}
}
for cp in coplanar_back {
if plane.orient_plane(&cp.plane) == FRONT {
front.push(cp);
} else {
back.push(cp);
}
}
// Process front and back using parallel iterators to avoid recursive join
let mut result = if let Some(ref f) = self.front {
f.clip_polygons(&front)
} else {
front
};
if let Some(ref b) = self.back {
result.extend(b.clip_polygons(&back));
}
// If there's no back node, we simply don't extend (effectively discarding back polygons)
result
}
/// Parallel version of `clip_to` using iterative approach to avoid stack overflow
#[cfg(feature = "parallel")]
pub fn clip_to(&mut self, bsp: &Node<S>) {
// Use iterative approach with a stack to avoid recursive stack overflow
let mut stack = vec![self];
while let Some(node) = stack.pop() {
// Clip polygons at this node
node.polygons = bsp.clip_polygons(&node.polygons);
// Add children to stack for processing
if let Some(ref mut front) = node.front {
stack.push(front.as_mut());
}
if let Some(ref mut back) = node.back {
stack.push(back.as_mut());
}
}
}
/// Parallel version of `build`.
#[cfg(feature = "parallel")]
pub fn build(&mut self, polygons: &[Polygon<S>]) {
if polygons.is_empty() {
return;
}
// Choose splitting plane if not already set
if self.plane.is_none() {
self.plane = Some(self.pick_best_splitting_plane(polygons));
}
let plane = self.plane.as_ref().unwrap();
// Split polygons in parallel
let (mut coplanar_front, mut coplanar_back, front, back) =
polygons.par_iter().map(|p| plane.split_polygon(p)).reduce(
|| (Vec::new(), Vec::new(), Vec::new(), Vec::new()),
|mut acc, x| {
acc.0.extend(x.0);
acc.1.extend(x.1);
acc.2.extend(x.2);
acc.3.extend(x.3);
acc
},
);
// Append coplanar fronts/backs to self.polygons
self.polygons.append(&mut coplanar_front);
self.polygons.append(&mut coplanar_back);
// Build children sequentially to avoid stack overflow from recursive join
// The polygon splitting above already uses parallel iterators for the heavy work
if !front.is_empty() {
let mut front_node = self.front.take().unwrap_or_else(|| Box::new(Node::new()));
front_node.build(&front);
self.front = Some(front_node);
}
if !back.is_empty() {
let mut back_node = self.back.take().unwrap_or_else(|| Box::new(Node::new()));
back_node.build(&back);
self.back = Some(back_node);
}
}
// Parallel slice
#[cfg(feature = "parallel")]
pub fn slice(&self, slicing_plane: &Plane) -> (Vec<Polygon<S>>, Vec<[Vertex; 2]>) {
// Collect all polygons (this can be expensive, but let's do it).
let all_polys = self.all_polygons();
// Process polygons in parallel
let (coplanar_polygons, intersection_edges) = all_polys
.par_iter()
.map(|poly| {
let vcount = poly.vertices.len();
if vcount < 2 {
// Degenerate => skip
return (Vec::new(), Vec::new());
}
let mut polygon_type = 0;
let mut types = Vec::with_capacity(vcount);
for vertex in &poly.vertices {
let vertex_type = slicing_plane.orient_point(&vertex.pos);
polygon_type |= vertex_type;
types.push(vertex_type);
}
match polygon_type {
COPLANAR => {
// Entire polygon in plane
(vec![poly.clone()], Vec::new())
},
FRONT | BACK => {
// Entirely on one side => no intersection
(Vec::new(), Vec::new())
},
SPANNING => {
// The polygon crosses the plane => gather intersection edges
let mut crossing_points = Vec::new();
for i in 0..vcount {
let j = (i + 1) % vcount;
let ti = types[i];
let tj = types[j];
let vi = &poly.vertices[i];
let vj = &poly.vertices[j];
if (ti | tj) == SPANNING {
// The param intersection at which plane intersects the edge [vi -> vj].
// Avoid dividing by zero:
let denom = slicing_plane.normal().dot(&(vj.pos - vi.pos));
if denom.abs() > EPSILON {
let intersection = (slicing_plane.offset()
- slicing_plane.normal().dot(&vi.pos.coords))
/ denom;
// Interpolate:
let intersect_vert = vi.interpolate(vj, intersection);
crossing_points.push(intersect_vert);
}
}
}
// Pair up intersection points => edges
let mut edges = Vec::new();
for chunk in crossing_points.chunks_exact(2) {
edges.push([chunk[0].clone(), chunk[1].clone()]);
}
(Vec::new(), edges)
},
_ => (Vec::new(), Vec::new()),
}
})
.reduce(
|| (Vec::new(), Vec::new()),
|mut acc, x| {
acc.0.extend(x.0);
acc.1.extend(x.1);
acc
},
);
(coplanar_polygons, intersection_edges)
}
}