manifold_rust/
boolean_result_assemble.rs

1// Boolean result assembly — extracted from boolean_result.rs
2// Contains update_reference, create_properties, and boolean_result entry point
3
4use std::collections::BTreeMap;
5
6use crate::boolean3::Boolean3;
7use crate::edge_op::simplify_topology;
8use crate::face_op::{face2tri, get_barycentric, reorder_halfedges};
9use crate::impl_mesh::{reserve_ids, ManifoldImpl};
10use crate::linalg::Vec3;
11use crate::types::{OpType, TriRef};
12
13use super::{EdgePos, abs_sum, exclusive_scan_abs,
14            size_output, add_new_edge_verts, append_partial_edges,
15            append_new_edges, append_whole_edges};
16
17// ---------------------------------------------------------------------------
18// UpdateReference -- map tri refs from input meshes to output
19// ---------------------------------------------------------------------------
20
21pub(super) fn update_reference(out_r: &mut ManifoldImpl, in_p: &ManifoldImpl, in_q: &ManifoldImpl, invert_q: bool) {
22    let offset_q = reserve_ids(in_q.mesh_relation.mesh_id_transform.len() as u32) as i32;
23
24    for tri_ref in out_r.mesh_relation.tri_ref.iter_mut() {
25        let tri = tri_ref.face_id;
26        let pq = tri_ref.mesh_id == 0;
27        if pq {
28            if (tri as usize) < in_p.mesh_relation.tri_ref.len() {
29                *tri_ref = in_p.mesh_relation.tri_ref[tri as usize];
30            }
31        } else {
32            if (tri as usize) < in_q.mesh_relation.tri_ref.len() {
33                *tri_ref = in_q.mesh_relation.tri_ref[tri as usize];
34                tri_ref.mesh_id += offset_q;
35            }
36        }
37    }
38
39    for (&k, v) in &in_p.mesh_relation.mesh_id_transform {
40        out_r.mesh_relation.mesh_id_transform.insert(k, v.clone());
41    }
42    for (&k, v) in &in_q.mesh_relation.mesh_id_transform {
43        let mut rel = v.clone();
44        rel.back_side ^= invert_q;
45        out_r.mesh_relation.mesh_id_transform.insert(k + offset_q, rel);
46    }
47}
48
49// ---------------------------------------------------------------------------
50// CreateProperties -- barycentric interpolation of properties
51// ---------------------------------------------------------------------------
52
53pub(super) fn create_properties(out_r: &mut ManifoldImpl, in_p: &ManifoldImpl, in_q: &ManifoldImpl, invert_q: bool) {
54    let num_prop_p = in_p.num_prop;
55    let num_prop_q = in_q.num_prop;
56    let num_prop = num_prop_p.max(num_prop_q);
57    out_r.num_prop = num_prop;
58    if num_prop == 0 {
59        return;
60    }
61
62    let num_tri = out_r.num_tri();
63
64    // Compute barycentric coordinates for each output halfedge
65    let mut bary = vec![Vec3::splat(0.0); out_r.halfedge.len()];
66    for tri in 0..num_tri {
67        let ref_pq = out_r.mesh_relation.tri_ref[tri];
68        if out_r.halfedge[3 * tri].start_vert < 0 {
69            continue;
70        }
71
72        let tri_pq = ref_pq.face_id as usize;
73        let pq = ref_pq.mesh_id == 0;
74        let vert_pos = if pq { &in_p.vert_pos } else { &in_q.vert_pos };
75        let halfedge = if pq { &in_p.halfedge } else { &in_q.halfedge };
76
77        if 3 * tri_pq + 2 >= halfedge.len() {
78            continue;
79        }
80
81        let tri_pos = [
82            vert_pos[halfedge[3 * tri_pq].start_vert as usize],
83            vert_pos[halfedge[3 * tri_pq + 1].start_vert as usize],
84            vert_pos[halfedge[3 * tri_pq + 2].start_vert as usize],
85        ];
86
87        for i in 0..3 {
88            let vert = out_r.halfedge[3 * tri + i].start_vert;
89            if vert >= 0 && (vert as usize) < out_r.vert_pos.len() {
90                bary[3 * tri + i] = get_barycentric(out_r.vert_pos[vert as usize], tri_pos, out_r.epsilon);
91            }
92        }
93    }
94
95    // Build properties with deduplication (matches C++ CreateProperties)
96    out_r.properties.clear();
97    out_r.properties.reserve(out_r.num_vert() * num_prop);
98    let mut idx = 0i32;
99
100    // Property vertex deduplication structures
101    let id_miss_prop = out_r.num_vert() as i32;
102    // propIdx: indexed by output vertex; bins hold ([pq, key_z, key_w], prop_idx)
103    let mut prop_idx: Vec<Vec<([i32; 3], i32)>> = vec![Vec::new(); out_r.num_vert() + 1];
104    // propMissIdx: [0] for mesh Q, [1] for mesh P -- indexed by source propVert
105    let mut prop_miss_idx: [Vec<i32>; 2] = [
106        vec![-1i32; in_q.num_prop_vert()],
107        vec![-1i32; in_p.num_prop_vert()],
108    ];
109
110    #[inline]
111    fn next3(i: usize) -> usize { (i + 1) % 3 }
112    #[inline]
113    fn prev3(i: usize) -> usize { (i + 2) % 3 }
114
115    for tri in 0..num_tri {
116        if out_r.halfedge[3 * tri].start_vert < 0 {
117            continue;
118        }
119        let ref_pq = out_r.mesh_relation.tri_ref[tri];
120        let pq = ref_pq.mesh_id == 0;
121        let pq_flag: i32 = if pq { 0 } else { 1 };
122        let old_num_prop = if pq { num_prop_p } else { num_prop_q };
123        let properties = if pq { &in_p.properties } else { &in_q.properties };
124        let halfedge = if pq { &in_p.halfedge } else { &in_q.halfedge };
125
126        // Per #1718: for Subtract, Q's triangles are flipped in the result, so
127        // Q's world-frame vertex normals (slot 0..2 when hasNormals) need a
128        // sign flip to point outward from the result's solid (into the cavity).
129        // Check is per-source-triangle — in_q may itself be a mixed Boolean
130        // result with only some meshIDs carrying normals.
131        let negate_normals = !pq
132            && invert_q
133            && old_num_prop >= 3
134            && in_q.tri_has_normals(ref_pq.face_id as usize);
135
136        for i in 0..3 {
137            let vert = out_r.halfedge[3 * tri + i].start_vert;
138            let uvw = bary[3 * tri + i];
139
140            // Build dedup key: [pq_flag, vert_key, key_z, key_w]
141            let mut key = [pq_flag, id_miss_prop, -1i32, -1i32];
142            if old_num_prop > 0 && 3 * ref_pq.face_id as usize + 2 < halfedge.len() {
143                let mut edge: i32 = -2;
144                for j in 0..3usize {
145                    if uvw[j] == 1.0 {
146                        // On a retained vertex
147                        key[2] = halfedge[3 * ref_pq.face_id as usize + j].prop_vert;
148                        edge = -1;
149                        break;
150                    }
151                    if uvw[j] == 0.0 {
152                        edge = j as i32;
153                    }
154                }
155                if edge >= 0 {
156                    // On an edge: both prop verts must match
157                    let p0 = halfedge[3 * ref_pq.face_id as usize + next3(edge as usize)].prop_vert;
158                    let p1 = halfedge[3 * ref_pq.face_id as usize + prev3(edge as usize)].prop_vert;
159                    key[1] = vert;
160                    key[2] = p0.min(p1);
161                    key[3] = p0.max(p1);
162                } else if edge == -2 {
163                    // Interior point
164                    key[1] = vert;
165                }
166            }
167
168            // Attempt dedup lookup
169            let mut found = false;
170            if key[1] == id_miss_prop && key[2] >= 0 {
171                // Vertex case: use propMissIdx
172                let pq_idx = key[0] as usize;
173                let prop_key = key[2] as usize;
174                if pq_idx < 2 && prop_key < prop_miss_idx[pq_idx].len() {
175                    let entry = prop_miss_idx[pq_idx][prop_key];
176                    if entry >= 0 {
177                        out_r.halfedge[3 * tri + i].prop_vert = entry;
178                        found = true;
179                    } else {
180                        prop_miss_idx[pq_idx][prop_key] = idx;
181                    }
182                }
183            } else {
184                // Edge/interior case: use propIdx
185                let bin_idx = key[1] as usize;
186                if bin_idx < prop_idx.len() {
187                    let search_key = [key[0], key[2], key[3]];
188                    if let Some(entry) = prop_idx[bin_idx].iter().find(|(k, _)| *k == search_key) {
189                        out_r.halfedge[3 * tri + i].prop_vert = entry.1;
190                        found = true;
191                    } else {
192                        prop_idx[bin_idx].push((search_key, idx));
193                    }
194                }
195            }
196
197            if found {
198                continue;
199            }
200
201            // No dedup match -- assign new property vertex and interpolate
202            out_r.halfedge[3 * tri + i].prop_vert = idx;
203            idx += 1;
204
205            for p in 0..num_prop {
206                if p < old_num_prop && 3 * ref_pq.face_id as usize + 2 < halfedge.len() {
207                    let mut old_props = [0.0f64; 3];
208                    for j in 0..3 {
209                        let prop_vert = halfedge[3 * ref_pq.face_id as usize + j].prop_vert;
210                        if prop_vert >= 0 {
211                            let prop_idx_val = old_num_prop * prop_vert as usize + p;
212                            if prop_idx_val < properties.len() {
213                                old_props[j] = properties[prop_idx_val];
214                            }
215                        }
216                    }
217                    let mut val = uvw.x * old_props[0] + uvw.y * old_props[1] + uvw.z * old_props[2];
218                    if negate_normals && p < 3 {
219                        val = -val;
220                    }
221                    out_r.properties.push(val);
222                } else {
223                    out_r.properties.push(0.0);
224                }
225            }
226        }
227    }
228}
229
230// ---------------------------------------------------------------------------
231// boolean_result -- the main entry point
232// ---------------------------------------------------------------------------
233
234/// Assemble the output mesh from Boolean3 intersection data.
235///
236/// This is the Rust port of `Boolean3::Result()` from `boolean_result.cpp`.
237pub fn boolean_result(
238    in_p: &ManifoldImpl,
239    in_q: &ManifoldImpl,
240    op: OpType,
241    bool3: &Boolean3,
242) -> ManifoldImpl {
243    debug_assert!(
244        bool3.expand_p == (op == OpType::Add),
245        "Result op type not compatible with constructor op type."
246    );
247
248    let c1 = if op == OpType::Intersect { 0 } else { 1 };
249    let c2 = if op == OpType::Add { 1 } else { 0 };
250    let c3 = if op == OpType::Intersect { 1 } else { -1 };
251
252    // Early returns for empty inputs (matches C++ boolean_result.cpp lines 680-690)
253    if in_p.is_empty() {
254        if !in_q.is_empty() && op == OpType::Add {
255            return in_q.clone();
256        }
257        return ManifoldImpl::new();
258    } else if in_q.is_empty() {
259        if op == OpType::Intersect {
260            return ManifoldImpl::new();
261        }
262        return in_p.clone();
263    }
264
265    // Check for valid (overflow) result
266    if !bool3.valid {
267        return ManifoldImpl::new();
268    }
269
270    let invert_q = op == OpType::Subtract;
271
272    // Convert winding numbers to inclusion values
273    let i12: Vec<i32> = bool3.xv12.x12.iter().map(|&v| c3 * v).collect();
274    let i21: Vec<i32> = bool3.xv21.x12.iter().map(|&v| c3 * v).collect();
275    let i03: Vec<i32> = bool3.w03.iter().map(|&v| c1 + c3 * v).collect();
276    let i30: Vec<i32> = bool3.w30.iter().map(|&v| c2 + c3 * v).collect();
277
278    // Vertex remapping via exclusive scan with abs_sum
279    let vp2r = exclusive_scan_abs(&i03, 0);
280    let num_vert_r = if let Some(&last) = i03.last() {
281        abs_sum(*vp2r.last().unwrap_or(&0), last)
282    } else {
283        0
284    };
285    let n_pv = num_vert_r;
286
287    let vq2r = exclusive_scan_abs(&i30, num_vert_r);
288    let num_vert_r = if let Some(&last) = i30.last() {
289        abs_sum(*vq2r.last().unwrap_or(&num_vert_r), last)
290    } else {
291        num_vert_r
292    };
293    let n_qv = num_vert_r - n_pv;
294
295    let v12r = if !bool3.xv12.v12.is_empty() {
296        exclusive_scan_abs(&i12, num_vert_r)
297    } else {
298        Vec::new()
299    };
300    let num_vert_r = if !i12.is_empty() {
301        abs_sum(*v12r.last().unwrap_or(&num_vert_r), *i12.last().unwrap())
302    } else {
303        num_vert_r
304    };
305    let n12 = num_vert_r - n_pv - n_qv;
306
307    let v21r = if !bool3.xv21.v12.is_empty() {
308        exclusive_scan_abs(&i21, num_vert_r)
309    } else {
310        Vec::new()
311    };
312    let num_vert_r = if !i21.is_empty() {
313        abs_sum(*v21r.last().unwrap_or(&num_vert_r), *i21.last().unwrap())
314    } else {
315        num_vert_r
316    };
317    let _n21 = num_vert_r - n_pv - n_qv - n12;
318
319    // Create the output Manifold
320    let mut out_r = ManifoldImpl::new();
321    if num_vert_r == 0 {
322        return out_r;
323    }
324
325    out_r.epsilon = in_p.epsilon.max(in_q.epsilon);
326    out_r.tolerance = in_p.tolerance.max(in_q.tolerance);
327
328    // Allocate and populate output vertices
329    out_r.vert_pos.resize(num_vert_r as usize, Vec3::splat(0.0));
330
331    // DuplicateVerts: retained vertices from P
332    for vert in 0..in_p.num_vert() {
333        let n = i03[vert].abs();
334        for i in 0..n {
335            out_r.vert_pos[(vp2r[vert] + i) as usize] = in_p.vert_pos[vert];
336        }
337    }
338    // Retained vertices from Q
339    for vert in 0..in_q.num_vert() {
340        let n = i30[vert].abs();
341        for i in 0..n {
342            out_r.vert_pos[(vq2r[vert] + i) as usize] = in_q.vert_pos[vert];
343        }
344    }
345    // New vertices from P edges -> Q faces
346    for vert in 0..i12.len() {
347        let n = i12[vert].abs();
348        for i in 0..n {
349            out_r.vert_pos[(v12r[vert] + i) as usize] = bool3.xv12.v12[vert];
350        }
351    }
352    // New vertices from Q edges -> P faces
353    for vert in 0..i21.len() {
354        let n = i21[vert].abs();
355        for i in 0..n {
356            out_r.vert_pos[(v21r[vert] + i) as usize] = bool3.xv21.v12[vert];
357        }
358    }
359
360    // Build edge maps
361    let mut edges_p: BTreeMap<i32, Vec<EdgePos>> = BTreeMap::new();
362    let mut edges_q: BTreeMap<i32, Vec<EdgePos>> = BTreeMap::new();
363    let mut edges_new: BTreeMap<(i32, i32), Vec<EdgePos>> = BTreeMap::new();
364
365    add_new_edge_verts(
366        &mut edges_p,
367        &mut edges_new,
368        &bool3.xv12.p1q2,
369        &i12,
370        &v12r,
371        &in_p.halfedge,
372        true,
373        0,
374    );
375    add_new_edge_verts(
376        &mut edges_q,
377        &mut edges_new,
378        &bool3.xv21.p1q2,
379        &i21,
380        &v21r,
381        &in_q.halfedge,
382        false,
383        bool3.xv12.p1q2.len(),
384    );
385
386    // Size output
387    let (face_edge, face_pq2r) = size_output(
388        &mut out_r,
389        in_p,
390        in_q,
391        &i03,
392        &i30,
393        &i12,
394        &i21,
395        &bool3.xv12.p1q2,
396        &bool3.xv21.p1q2,
397        invert_q,
398    );
399
400    // Assemble edges
401    let mut face_ptr_r = face_edge.clone();
402    let mut whole_halfedge_p = vec![true; in_p.halfedge.len()];
403    let mut whole_halfedge_q = vec![true; in_q.halfedge.len()];
404    let mut halfedge_ref = vec![
405        TriRef {
406            mesh_id: 0,
407            original_id: -1,
408            face_id: -1,
409            coplanar_id: -1,
410        };
411        2 * out_r.num_edge()
412    ];
413
414    append_partial_edges(
415        &mut out_r,
416        &mut whole_halfedge_p,
417        &mut face_ptr_r,
418        &mut edges_p,
419        &mut halfedge_ref,
420        in_p,
421        &i03,
422        &vp2r,
423        &face_pq2r[..in_p.num_tri()],
424        true,
425    );
426    append_partial_edges(
427        &mut out_r,
428        &mut whole_halfedge_q,
429        &mut face_ptr_r,
430        &mut edges_q,
431        &mut halfedge_ref,
432        in_q,
433        &i30,
434        &vq2r,
435        &face_pq2r[in_p.num_tri()..],
436        false,
437    );
438    append_new_edges(
439        &mut out_r,
440        &mut face_ptr_r,
441        &mut edges_new,
442        &mut halfedge_ref,
443        &face_pq2r,
444        in_p.num_tri(),
445    );
446    append_whole_edges(
447        &mut out_r,
448        &mut face_ptr_r,
449        &mut halfedge_ref,
450        in_p,
451        &whole_halfedge_p,
452        &i03,
453        &vp2r,
454        &face_pq2r[..in_p.num_tri()],
455        true,
456    );
457    append_whole_edges(
458        &mut out_r,
459        &mut face_ptr_r,
460        &mut halfedge_ref,
461        in_q,
462        &whole_halfedge_q,
463        &i30,
464        &vq2r,
465        &face_pq2r[in_p.num_tri()..],
466        false,
467    );
468
469    // Triangulate polygonal faces (allowConvex=false per C++ boolean_result.cpp)
470    face2tri(&mut out_r, &face_edge, &halfedge_ref, false);
471    reorder_halfedges(&mut out_r);
472
473    // Create properties via barycentric interpolation
474    create_properties(&mut out_r, in_p, in_q, invert_q);
475
476    // Update references
477    update_reference(&mut out_r, in_p, in_q, invert_q);
478
479    // Simplify topology
480    simplify_topology(&mut out_r, (n_pv + n_qv) as i32);
481    out_r.remove_unreferenced_verts();
482
483    // Finalize
484    out_r.calculate_bbox();
485    out_r.sort_geometry();
486    out_r.increment_mesh_ids();
487
488    out_r
489}
manifold_rust/boolean_result_assemble.rs

manifold_rust/
boolean_result_assemble.rs
