fast_mesh_scene/
cut.rs

1//! Cutting a mesh by a world plane into two capped meshes.
2//!
3//! [`Scene::cut_by_plane`] maps the world plane into the mesh's local frame
4//! (like a section, but without needing a BVH), splits the mesh with
5//! [`ops::cut_by_plane`](fast_mesh_ops::cut_by_plane) and adds the removed
6//! side as a new mesh with the same placement and update mode. The original
7//! handle keeps the `+` side; the report's `added` is the `-` side.
8//!
9//! Only positions and triangles cross over (see the ops docs); the new mesh
10//! has no normals, colouring, fields or section entries. Undo restores the
11//! cut mesh in one step; the added mesh stays, like the removed source of
12//! [`Scene::join`].
13
14use crate::ops::{CutOptions as OpsCutOptions, cut_by_plane as ops_cut_by_plane};
15use crate::placement::world_to_local;
16use crate::{MeshId, MeshOptions, Plane, Result, Scene};
17
18/// What to cut: a world plane and whether to cap.
19#[derive(Debug, Clone, Copy, PartialEq)]
20pub struct CutOptions {
21    /// The cutting plane, in world coordinates. The `+` side
22    /// (`signed_distance >= 0`) stays on the original mesh.
23    pub plane: Plane,
24    /// Close both openings with flat, unfaired patches, across UV seams on a
25    /// mesh with UVs. Without it both
26    /// parts keep the open rim the cut leaves.
27    pub cap: bool,
28}
29
30/// What [`Scene::cut_by_plane`] did.
31#[derive(Debug, Clone, Copy, PartialEq, Eq)]
32pub struct CutReport {
33    /// The new mesh holding the `-` side.
34    pub added: MeshId,
35    /// Alive triangles of the kept (`+`) mesh, cap included.
36    pub kept_triangles: usize,
37    /// Alive triangles of the added (`-`) mesh, cap included.
38    pub removed_triangles: usize,
39    /// Cap triangles added on both sides together.
40    pub cap_triangles: usize,
41}
42
43fn dot(a: [f64; 3], b: [f64; 3]) -> f64 {
44    a[0] * b[0] + a[1] * b[1] + a[2] * b[2]
45}
46
47fn unit(a: [f64; 3]) -> [f64; 3] {
48    let n = dot(a, a).sqrt();
49    a.map(|c| c / n)
50}
51
52/// The world plane in the mesh's stored local frame (origin excluded), as
53/// for a section: the axes are the world `(u, v)` mapped through the
54/// placement's linear inverse, then re-orthonormalised, so that the local
55/// plane's zero set is the preimage of the world's, with matching sides.
56/// `s >= 0` then means the same side in both frames.
57fn local_plane(
58    placement: &crate::Placement,
59    mesh_origin: [f64; 3],
60    plane: &Plane,
61) -> Result<Plane> {
62    let origin = world_to_local(placement, mesh_origin, plane.origin());
63    let u = unit(placement.inverse_direction(plane.u()));
64    let v = placement.inverse_direction(plane.v());
65    let d = dot(v, u);
66    let v = unit(std::array::from_fn(|k| v[k] - d * u[k]));
67    Ok(Plane::with_axes(origin, u, v)?)
68}
69
70impl Scene {
71    /// Cuts the mesh with a world plane: the `+` side
72    /// (`signed_distance >= 0`) stays on the mesh and the `-` side is added
73    /// as a new mesh, both with the mesh's placement, so the world shape is
74    /// kept. With `options.cap` (the usual case) both openings are closed
75    /// with flat, unfaired patches; without it both parts keep the open rim.
76    /// Cutting a closed mesh with `cap` yields two closed meshes. On a mesh
77    /// with UVs, closed means closed by exact position, so seams count as
78    /// closed. A rim that runs into a real boundary stays open; on a mesh
79    /// without UVs, split vertices are such a boundary, so weld them first.
80    ///
81    /// The cut runs as one edit of the mesh, so it undoes in one step; the
82    /// added mesh is permanent, like the removed source of [`Scene::join`].
83    /// Only positions and triangles cross over: the added mesh has no
84    /// normals, colouring, fields or section entries, and new vertices take
85    /// channel defaults (crossing vertices on the kept side interpolate
86    /// their parents). UVs carry over to both sides, interpolated at the
87    /// crossing vertices and across the caps.
88    ///
89    /// # Errors
90    /// [`SceneError::UnknownMesh`] for a stale id;
91    /// [`SceneError::InvalidInput`] when the plane does not cut the mesh, or
92    /// a rim cannot be capped; [`SceneError::Ops`] or [`SceneError::Store`]
93    /// from the cut or the add. A failed cut changes nothing. If adding the
94    /// removed side fails (out of memory), the cut of the original stays
95    /// recorded and the added mesh is missing.
96    pub fn cut_by_plane(&mut self, id: MeshId, options: &CutOptions) -> Result<CutReport> {
97        self.drop_field_unit();
98        let local = {
99            let entry = self.entry(id)?;
100            local_plane(&entry.placement, entry.mesh.origin(), &options.plane)?
101        };
102        let output = self.edit(id, |tx| {
103            ops_cut_by_plane(tx, &local, &OpsCutOptions { cap: options.cap })
104        })?;
105        let (placement, mode) = {
106            let entry = self.entry(id)?;
107            (entry.placement, entry.mode)
108        };
109        let removed_triangles = output.report.removed_triangles;
110        let cap_triangles = output.report.cap_triangles;
111        let added = self.add_mesh(
112            output.removed,
113            MeshOptions {
114                placement,
115                mode,
116                ..MeshOptions::default()
117            },
118        )?;
119        Ok(CutReport {
120            added,
121            kept_triangles: output.report.kept_triangles,
122            removed_triangles,
123            cap_triangles,
124        })
125    }
126}
127
128#[cfg(test)]
129mod tests {
130    use fast_mesh_store::Mesh;
131
132    use crate::ops::OpsError;
133    use crate::{CutOptions, MeshOptions, Placement, Plane, Scene, SceneError, SceneOptions};
134
135    /// A closed unit cube, outward wound.
136    fn cube() -> Mesh {
137        Mesh::from_buffers(
138            &[
139                0.0, 0.0, 0.0, //
140                1.0, 0.0, 0.0, //
141                1.0, 1.0, 0.0, //
142                0.0, 1.0, 0.0, //
143                0.0, 0.0, 1.0, //
144                1.0, 0.0, 1.0, //
145                1.0, 1.0, 1.0, //
146                0.0, 1.0, 1.0,
147            ],
148            &[
149                0, 2, 1, 0, 3, 2, //
150                4, 5, 6, 4, 6, 7, //
151                0, 1, 5, 0, 5, 4, //
152                2, 3, 7, 2, 7, 6, //
153                1, 2, 6, 1, 6, 5, //
154                3, 0, 4, 3, 4, 7, //
155            ],
156        )
157        .unwrap()
158    }
159
160    fn plane(origin: [f64; 3], normal: [f64; 3]) -> Plane {
161        Plane::new(origin, normal).unwrap()
162    }
163
164    #[test]
165    fn cut_keeps_placement_and_undoes_in_one_step() {
166        let mut scene = Scene::new(SceneOptions::default());
167        // A unit cube moved to [10, 0, 0]: the world plane x = 10.5 cuts its
168        // middle, whatever the local coordinates say.
169        let placement = Placement {
170            translation: [10.0, 0.0, 0.0],
171            ..Placement::IDENTITY
172        };
173        let id = scene
174            .add_mesh(
175                cube(),
176                MeshOptions {
177                    placement,
178                    ..MeshOptions::default()
179                },
180            )
181            .unwrap();
182        scene.take_changes();
183        let before = scene.mesh(id).unwrap().triangle_count();
184
185        let report = scene
186            .cut_by_plane(
187                id,
188                &CutOptions {
189                    plane: plane([10.5, 0.0, 0.0], [1.0, 0.0, 0.0]),
190                    cap: true,
191                },
192            )
193            .unwrap();
194        // Both parts closed, both placed where the cube was.
195        assert!(
196            crate::ops::boundary_loops(scene.mesh(id).unwrap())
197                .unwrap()
198                .is_empty()
199        );
200        assert!(
201            crate::ops::boundary_loops(scene.mesh(report.added).unwrap())
202                .unwrap()
203                .is_empty()
204        );
205        assert_eq!(scene.placement(report.added), Ok(placement));
206        assert_eq!(scene.mode(report.added), Ok(scene.mode(id).unwrap()));
207        assert_ne!(report.added, id);
208        // The kept side is the + one: its world box starts at the plane.
209        let kept_world: Vec<[f64; 3]> = (0..scene.mesh(id).unwrap().vertex_slots() as u32)
210            .filter(|&v| scene.mesh(id).unwrap().is_vertex_alive(v))
211            .map(|v| {
212                placement.apply([
213                    scene.mesh(id).unwrap().origin()[0]
214                        + f64::from(scene.mesh(id).unwrap().position(v).unwrap()[0]),
215                    scene.mesh(id).unwrap().origin()[1]
216                        + f64::from(scene.mesh(id).unwrap().position(v).unwrap()[1]),
217                    scene.mesh(id).unwrap().origin()[2]
218                        + f64::from(scene.mesh(id).unwrap().position(v).unwrap()[2]),
219                ])
220            })
221            .collect();
222        assert!(kept_world.iter().all(|p| p[0] >= 10.5 - 1e-6));
223        assert_eq!(
224            report.kept_triangles,
225            scene.mesh(id).unwrap().triangle_count()
226        );
227        assert_eq!(
228            report.removed_triangles,
229            scene.mesh(report.added).unwrap().triangle_count()
230        );
231
232        // One undo step restores the cut mesh; the added part stays.
233        assert!(scene.can_undo());
234        assert!(scene.undo().unwrap());
235        assert_eq!(scene.mesh(id).unwrap().triangle_count(), before);
236        assert!(scene.mesh(report.added).is_ok());
237        assert!(!scene.can_undo());
238        assert!(scene.redo().unwrap());
239        assert_ne!(scene.mesh(id).unwrap().triangle_count(), before);
240    }
241
242    #[test]
243    fn scaled_cut_follows_the_scale() {
244        // The unit cube scaled by [2, 1, 1] and moved to [0, 3, 0]: the
245        // world shape is x in [0, 2]. The world plane x = 1 cuts its middle.
246        let mut scene = Scene::new(SceneOptions::default());
247        let placement = Placement {
248            translation: [0.0, 3.0, 0.0],
249            scale: [2.0, 1.0, 1.0],
250            ..Placement::IDENTITY
251        };
252        let id = scene
253            .add_mesh(
254                cube(),
255                MeshOptions {
256                    placement,
257                    ..MeshOptions::default()
258                },
259            )
260            .unwrap();
261        scene.take_changes();
262        let report = scene
263            .cut_by_plane(
264                id,
265                &CutOptions {
266                    plane: plane([1.0, 3.0, 0.0], [1.0, 0.0, 0.0]),
267                    cap: true,
268                },
269            )
270            .unwrap();
271        assert!(
272            crate::ops::boundary_loops(scene.mesh(id).unwrap())
273                .unwrap()
274                .is_empty()
275        );
276        assert!(
277            crate::ops::boundary_loops(scene.mesh(report.added).unwrap())
278                .unwrap()
279                .is_empty()
280        );
281        assert_eq!(scene.placement(report.added), Ok(placement));
282        // The kept world box is the + half: x in [1, 2], y in [3, 4].
283        let mut lo = [f64::INFINITY; 3];
284        let mut hi = [f64::NEG_INFINITY; 3];
285        let mesh = scene.mesh(id).unwrap();
286        for v in 0..mesh.vertex_slots() as u32 {
287            let Some(p) = mesh.position(v) else {
288                continue;
289            };
290            let w = placement.apply([
291                mesh.origin()[0] + f64::from(p[0]),
292                mesh.origin()[1] + f64::from(p[1]),
293                mesh.origin()[2] + f64::from(p[2]),
294            ]);
295            for k in 0..3 {
296                lo[k] = lo[k].min(w[k]);
297                hi[k] = hi[k].max(w[k]);
298            }
299        }
300        assert!((lo[0] - 1.0).abs() < 1e-4, "{lo:?}");
301        assert!((hi[0] - 2.0).abs() < 1e-4, "{hi:?}");
302        assert!((lo[1] - 3.0).abs() < 1e-4, "{lo:?}");
303        assert!((hi[1] - 4.0).abs() < 1e-4, "{hi:?}");
304    }
305
306    #[test]
307    fn missing_and_uncapped_cuts() {
308        let mut scene = Scene::new(SceneOptions::default());
309        let id = scene.add_mesh(cube(), MeshOptions::default()).unwrap();
310        scene.take_changes();
311        // A plane past the cube misses it: nothing changes.
312        assert_eq!(
313            scene.cut_by_plane(
314                id,
315                &CutOptions {
316                    plane: plane([5.0, 0.0, 0.0], [1.0, 0.0, 0.0]),
317                    cap: true,
318                },
319            ),
320            Err(SceneError::Ops(OpsError::InvalidInput(
321                "plane does not cut the mesh",
322            )))
323        );
324        assert_eq!(scene.mesh(id).unwrap().triangle_count(), 12);
325        assert!(!scene.can_undo());
326        // Without cap both parts stay open.
327        let report = scene
328            .cut_by_plane(
329                id,
330                &CutOptions {
331                    plane: plane([0.5, 0.0, 0.0], [1.0, 0.0, 0.0]),
332                    cap: false,
333                },
334            )
335            .unwrap();
336        assert_eq!(report.cap_triangles, 0);
337        assert!(
338            !crate::ops::boundary_loops(scene.mesh(id).unwrap())
339                .unwrap()
340                .is_empty()
341        );
342        assert!(
343            !crate::ops::boundary_loops(scene.mesh(report.added).unwrap())
344                .unwrap()
345                .is_empty()
346        );
347    }
348}
fast_mesh_scene/cut.rs

fast_mesh_scene/
cut.rs
