fast_mesh_scene/
boolean.rs

1//! Boolean operations (union, subtract, intersect) between two meshes.
2//!
3//! [`Scene::boolean`] combines mesh B into mesh A in the world: B is mapped
4//! into A's local frame (rigid pairs through the relative transform,
5//! scaled ones through a baked copy, like the pair queries), the
6//! [`ops::boolean_plan`](fast_mesh_ops::boolean_plan) runs, and the plan
7//! applies as one edit. The result keeps A's placement, so the world shape
8//! is the boolean of the world shapes. B is unchanged.
9//!
10//! Only positions and triangles cross over (see the ops docs); the new mesh
11//! has no normals, colouring, fields or section entries. Undo restores the
12//! combined mesh in one step. Combining a mesh with itself is a no-op for
13//! union and intersect, and clears it for subtract.
14
15use fast_mesh_bvh::{BuildOptions, Bvh};
16use fast_mesh_query::Rigid;
17use fast_mesh_store::{Mesh, StoreError, TriangleId, UV_CHANNEL, VertexId};
18
19use crate::baked::baked_mesh;
20use crate::placement::relative_affine;
21use crate::{MeshId, Result, Scene};
22
23/// Which boolean to compute.
24#[derive(Debug, Clone, Copy, PartialEq, Eq)]
25pub enum BooleanOp {
26    /// Whatever is in either mesh.
27    Union,
28    /// Whatever is in A but not in B.
29    Subtract,
30    /// Whatever is in both meshes.
31    Intersect,
32}
33
34/// What [`Scene::boolean`] did.
35#[derive(Debug, Clone, Copy, Default, PartialEq, Eq)]
36pub struct BooleanReport {
37    /// Alive triangles of the result.
38    pub kept_triangles: usize,
39    /// Triangles added (split pieces and the tool's kept pieces), minus the
40    /// ones the cleanup merged or removed again.
41    pub triangles_added: usize,
42    /// A's UVs were dropped; undo restores them. The result mixes split pieces
43    /// and B's surface, which have no UVs in A's space.
44    pub uvs_dropped: bool,
45}
46
47/// Whether a boolean must read `mesh` with its UV seams closed: it has UVs and
48/// an open boundary. Whether that boundary is only seams is for the boolean's
49/// own input checks to find, on the welded copy.
50fn has_open_uvs(mesh: &Mesh) -> Result<bool> {
51    Ok(mesh.uvs().is_some() && !crate::ops::boundary_loops(mesh)?.is_empty())
52}
53
54/// `baked` with exact duplicates merged and a new BVH. Slot ids stay, so the
55/// same weld of the original gives the very mesh a plan was made for.
56fn welded(mut baked: Mesh, options: &BuildOptions) -> Result<(Mesh, Bvh)> {
57    let mut tx = baked.begin_edit();
58    crate::ops::weld(&mut tx, 0.0)?;
59    tx.commit()?;
60    let bvh = Bvh::build(&baked, options)?;
61    Ok((baked, bvh))
62}
63
64impl Scene {
65    /// Combines mesh B into mesh A: union, subtract or intersect as placed
66    /// in the world. The result replaces A with A's placement, so the world
67    /// shape is the boolean of the world shapes; B is unchanged. Closed
68    /// manifold inputs give a closed result; touches leave pinch vertices.
69    ///
70    /// The combination runs as one edit of A, so it undoes in one step.
71    /// Combining a mesh with itself is a no-op for union and intersect
72    /// (nothing is recorded), and clears it for subtract. Only positions
73    /// and triangles cross over: new vertices take channel defaults, and A's
74    /// UV channel is dropped ([`BooleanReport::uvs_dropped`]). Since UVs do not
75    /// survive, a mesh with UVs is read with exactly coincident vertices
76    /// merged, so seams do not make a closed surface count as open; every
77    /// input check below applies to the merged geometry. B is unchanged, and
78    /// undo restores A's split vertices.
79    ///
80    /// # Errors
81    /// [`SceneError::UnknownMesh`] for a stale id;
82    /// [`SceneError::InvalidInput`] when an input is not closed, manifold,
83    /// consistently wound or free of degenerate, duplicate and
84    /// self-intersecting triangles, or when a mapped position leaves `f32`
85    /// range; [`SceneError::Ops`], [`SceneError::Query`],
86    /// [`SceneError::Store`] or [`SceneError::StaleBvh`] from the plan, the
87    /// bakes and the edit. A failed boolean changes nothing. A stale Manual
88    /// BVH fails the query with [`SceneError::StaleBvh`], like the pair
89    /// queries.
90    pub fn boolean(&mut self, a: MeshId, b: MeshId, op: BooleanOp) -> Result<BooleanReport> {
91        self.entry(a)?;
92        self.entry(b)?;
93        if a == b {
94            return self.boolean_self(a, op);
95        }
96        // Bring both BVHs up to date (§15.4): rigid pairs plan against the
97        // live meshes, scaled ones against baked copies.
98        self.prepare(Some(&[a, b]))?;
99        let ops_op = match op {
100            BooleanOp::Union => crate::ops::BooleanOp::Union,
101            BooleanOp::Subtract => crate::ops::BooleanOp::Subtract,
102            BooleanOp::Intersect => crate::ops::BooleanOp::Intersect,
103        };
104        // A with its seams closed, when it has them: the plan's vertex ids are
105        // then those of the same weld, run first in the edit below.
106        let (a_seams, b_seams) = (
107            has_open_uvs(&self.entry(a)?.mesh)?,
108            has_open_uvs(&self.entry(b)?.mesh)?,
109        );
110        let a_copy = if a_seams {
111            let ea = self.entry(a)?;
112            let options = ea.bvh.options();
113            let (baked, _) = baked_mesh(&ea.mesh, |l| l.map(f64::from), options)?;
114            Some(welded(baked, options)?)
115        } else {
116            None
117        };
118        let apply = |tx: &mut fast_mesh_store::Transaction, plan: &crate::ops::BooleanPlan| {
119            if a_seams {
120                tx.drop_channel(UV_CHANNEL)?;
121                crate::ops::weld(tx, 0.0)?;
122            }
123            let mut report = crate::ops::apply_boolean(tx, plan)?;
124            report.uvs_dropped |= a_seams;
125            Ok::<_, crate::ops::OpsError>(report)
126        };
127        if self.is_rigid_pair(a, b)? {
128            let plan = {
129                let (ea, eb) = (self.entry(a)?, self.entry(b)?);
130                let xf = crate::placement::relative_rigid(
131                    &ea.placement,
132                    ea.mesh.origin(),
133                    &eb.placement,
134                    eb.mesh.origin(),
135                );
136                let b_copy = if b_seams {
137                    let options = eb.bvh.options();
138                    let (baked, _) = baked_mesh(&eb.mesh, |l| l.map(f64::from), options)?;
139                    Some(welded(baked, options)?)
140                } else {
141                    None
142                };
143                let (ma, ba) = a_copy.as_ref().map_or((&ea.mesh, &ea.bvh), |(m, b)| (m, b));
144                let (mb, bb) = b_copy.as_ref().map_or((&eb.mesh, &eb.bvh), |(m, b)| (m, b));
145                crate::ops::boolean_plan(ma, ba, mb, bb, &xf, ops_op)?
146            };
147            let report = self.edit(a, |tx| apply(tx, &plan))?;
148            return Ok(BooleanReport {
149                kept_triangles: report.kept_triangles,
150                triangles_added: report.triangles_added,
151                uvs_dropped: report.uvs_dropped,
152            });
153        }
154        // A scaled placement on either side: the pair query would run on
155        // baked copies, and so does the boolean — baked into A's local
156        // space, where the result lands.
157        let plan = {
158            let (ea, eb) = (self.entry(a)?, self.entry(b)?);
159            let affine = relative_affine(
160                &ea.placement,
161                ea.mesh.origin(),
162                &eb.placement,
163                eb.mesh.origin(),
164            );
165            let (baked, baked_bvh) = baked_mesh(
166                &eb.mesh,
167                |l| affine.apply(l.map(f64::from)),
168                eb.bvh.options(),
169            )?;
170            let (baked, baked_bvh) = if b_seams {
171                welded(baked, eb.bvh.options())?
172            } else {
173                (baked, baked_bvh)
174            };
175            let (ma, ba) = a_copy.as_ref().map_or((&ea.mesh, &ea.bvh), |(m, b)| (m, b));
176            crate::ops::boolean_plan(ma, ba, &baked, &baked_bvh, &Rigid::IDENTITY, ops_op)?
177        };
178        let report = self.edit(a, |tx| apply(tx, &plan))?;
179        Ok(BooleanReport {
180            kept_triangles: report.kept_triangles,
181            triangles_added: report.triangles_added,
182            uvs_dropped: report.uvs_dropped,
183        })
184    }
185
186    /// Combines a mesh with itself: union and intersect change nothing (and
187    /// record nothing), subtract clears the mesh in one undo step.
188    fn boolean_self(&mut self, a: MeshId, op: BooleanOp) -> Result<BooleanReport> {
189        match op {
190            BooleanOp::Union | BooleanOp::Intersect => Ok(BooleanReport {
191                kept_triangles: self.mesh(a)?.triangle_count(),
192                triangles_added: 0,
193                uvs_dropped: false,
194            }),
195            BooleanOp::Subtract => {
196                self.edit(a, |tx| {
197                    let all: Vec<TriangleId> = (0..tx.mesh().triangle_slots() as TriangleId)
198                        .filter(|&t| tx.mesh().triangle(t).is_some())
199                        .collect();
200                    if all.is_empty() {
201                        return Ok::<(), StoreError>(());
202                    }
203                    tx.remove_triangles(&all)?;
204                    let mut orphans: Vec<VertexId> = Vec::new();
205                    for v in 0..tx.mesh().vertex_slots() as VertexId {
206                        if tx.mesh().is_vertex_alive(v) && tx.mesh().corner_count(v) == 0 {
207                            orphans.push(v);
208                        }
209                    }
210                    if !orphans.is_empty() {
211                        tx.remove_vertices(&orphans)?;
212                    }
213                    Ok::<(), StoreError>(())
214                })?;
215                Ok(BooleanReport {
216                    kept_triangles: 0,
217                    triangles_added: 0,
218                    uvs_dropped: false,
219                })
220            }
221        }
222    }
223}
224
225#[cfg(test)]
226mod tests {
227    use fast_mesh_store::Mesh;
228
229    use crate::{MeshOptions, Placement, Scene, SceneError, SceneOptions};
230
231    /// A closed unit cube, outward wound.
232    fn cube() -> Mesh {
233        Mesh::from_buffers(
234            &[
235                0.0, 0.0, 0.0, //
236                1.0, 0.0, 0.0, //
237                1.0, 1.0, 0.0, //
238                0.0, 1.0, 0.0, //
239                0.0, 0.0, 1.0, //
240                1.0, 0.0, 1.0, //
241                1.0, 1.0, 1.0, //
242                0.0, 1.0, 1.0,
243            ],
244            &[
245                0, 2, 1, 0, 3, 2, //
246                4, 5, 6, 4, 6, 7, //
247                0, 1, 5, 0, 5, 4, //
248                2, 3, 7, 2, 7, 6, //
249                1, 2, 6, 1, 6, 5, //
250                3, 0, 4, 3, 4, 7, //
251            ],
252        )
253        .unwrap()
254    }
255
256    /// Six times the signed world-space volume, via the placement.
257    fn world_volume6(scene: &Scene, id: crate::MeshId) -> f64 {
258        let mesh = scene.mesh(id).unwrap();
259        let placement = scene.placement(id).unwrap();
260        let origin = mesh.origin();
261        let mut v = 0.0;
262        for t in 0..mesh.triangle_slots() as u32 {
263            let Some(tri) = mesh.triangle(t) else {
264                continue;
265            };
266            let [a, b, c] = tri.map(|x| {
267                let p = mesh.position(x).unwrap().map(f64::from);
268                placement.apply([origin[0] + p[0], origin[1] + p[1], origin[2] + p[2]])
269            });
270            v += a[0] * (b[1] * c[2] - b[2] * c[1]) - a[1] * (b[0] * c[2] - b[2] * c[0])
271                + a[2] * (b[0] * c[1] - b[1] * c[0]);
272        }
273        v
274    }
275
276    fn placed_cube(scene: &mut Scene, placement: Placement) -> crate::MeshId {
277        scene
278            .add_mesh(
279                cube(),
280                MeshOptions {
281                    placement,
282                    ..MeshOptions::default()
283                },
284            )
285            .unwrap()
286    }
287
288    #[test]
289    fn boolean_respects_placement_and_undoes_in_one_step() {
290        let mut scene = Scene::new(SceneOptions::default());
291        // A unit cube at [10, 0, 0] and one at [10.5, 0, 0]: the world
292        // overlap is half a cube, whatever the local coordinates say.
293        let a = placed_cube(
294            &mut scene,
295            Placement {
296                translation: [10.0, 0.0, 0.0],
297                ..Placement::IDENTITY
298            },
299        );
300        let b = placed_cube(
301            &mut scene,
302            Placement {
303                translation: [10.5, 0.0, 0.0],
304                ..Placement::IDENTITY
305            },
306        );
307        scene.take_changes();
308        let before = scene.mesh(a).unwrap().triangle_count();
309
310        let report = scene.boolean(a, b, crate::BooleanOp::Subtract).unwrap();
311        assert!(
312            crate::ops::boundary_loops(scene.mesh(a).unwrap())
313                .unwrap()
314                .is_empty()
315        );
316        assert_eq!(scene.placement(a).unwrap().translation, [10.0, 0.0, 0.0]);
317        // The tool is unchanged.
318        assert_eq!(scene.mesh(b).unwrap().triangle_count(), 12);
319        // The world volume lost half a cube.
320        assert!(
321            (world_volume6(&scene, a) - 6.0 * 0.5).abs() < 1e-3,
322            "{}",
323            world_volume6(&scene, a)
324        );
325        assert_eq!(
326            report.kept_triangles,
327            scene.mesh(a).unwrap().triangle_count()
328        );
329
330        // One undo step restores the combined mesh; the tool was never in
331        // the history.
332        assert!(scene.can_undo());
333        assert!(scene.undo().unwrap());
334        assert_eq!(scene.mesh(a).unwrap().triangle_count(), before);
335        assert!(!scene.can_undo());
336        assert!(scene.redo().unwrap());
337        assert_ne!(scene.mesh(a).unwrap().triangle_count(), before);
338    }
339
340    #[test]
341    fn scaled_boolean_follows_the_scale() {
342        // The unit cube scaled by [2, 1, 1] and moved to [0, 3, 0]: the
343        // world shape is x in [0, 2]. Another unit cube at [1, 3, 0]
344        // overlaps its middle in the world.
345        let mut scene = Scene::new(SceneOptions::default());
346        let placement = Placement {
347            translation: [0.0, 3.0, 0.0],
348            scale: [2.0, 1.0, 1.0],
349            ..Placement::IDENTITY
350        };
351        let a = placed_cube(&mut scene, placement);
352        let b = placed_cube(
353            &mut scene,
354            Placement {
355                translation: [1.0, 3.0, 0.0],
356                ..Placement::IDENTITY
357            },
358        );
359        scene.take_changes();
360        let report = scene.boolean(a, b, crate::BooleanOp::Intersect).unwrap();
361        assert!(
362            crate::ops::boundary_loops(scene.mesh(a).unwrap())
363                .unwrap()
364                .is_empty()
365        );
366        assert_eq!(scene.placement(a), Ok(placement));
367        // The intersect is the world box x in [1, 2], y, z in [0, 1]
368        // shifted by [0, 3, 0]: volume 1.
369        assert!(
370            (world_volume6(&scene, a) - 6.0).abs() < 1e-2,
371            "{}",
372            world_volume6(&scene, a)
373        );
374        assert_eq!(
375            report.kept_triangles,
376            scene.mesh(a).unwrap().triangle_count()
377        );
378    }
379
380    #[test]
381    fn boolean_rejects_unknown_meshes_and_clears_self() {
382        let mut scene = Scene::new(SceneOptions::default());
383        let a = scene.add_mesh(cube(), MeshOptions::default()).unwrap();
384        let b = scene.add_mesh(cube(), MeshOptions::default()).unwrap();
385        scene.take_changes();
386        // Unknown ids first (before any stale-BVH or plan error).
387        let missing = scene.remove_mesh(b).unwrap();
388        let _ = missing;
389        assert_eq!(
390            scene.boolean(a, b, crate::BooleanOp::Union),
391            Err(SceneError::UnknownMesh)
392        );
393        assert!(!scene.can_undo());
394        // Union with itself changes nothing and records nothing.
395        let before = scene.mesh(a).unwrap().triangle_count();
396        let report = scene.boolean(a, a, crate::BooleanOp::Union).unwrap();
397        assert_eq!(report.kept_triangles, before);
398        assert!(!scene.can_undo());
399        // Subtract clears it in one undo step.
400        scene.boolean(a, a, crate::BooleanOp::Subtract).unwrap();
401        assert_eq!(scene.mesh(a).unwrap().triangle_count(), 0);
402        assert!(scene.undo().unwrap());
403        assert_eq!(scene.mesh(a).unwrap().triangle_count(), before);
404    }
405}
fast_mesh_scene/boolean.rs

fast_mesh_scene/
boolean.rs
