fast_mesh_store/
compact.rs

1use crate::column::{Column, try_reserve, try_reserve_exact, try_vec};
2use crate::mesh::full_bits;
3use crate::{Mesh, Result, TriangleId, VertexId};
4
5/// Old slot id → new id mapping produced by [`Mesh::compact`].
6#[derive(Debug, Clone, PartialEq, Eq)]
7pub struct Remap {
8    /// Indexed by old vertex slot; [`Remap::REMOVED`] for dead slots.
9    pub vertices: Vec<VertexId>,
10    /// Indexed by old triangle slot; [`Remap::REMOVED`] for dead slots.
11    pub triangles: Vec<TriangleId>,
12}
13
14impl Remap {
15    pub const REMOVED: u32 = u32::MAX;
16
17    pub fn vertex(&self, old: VertexId) -> Option<VertexId> {
18        self.vertices
19            .get(old as usize)
20            .copied()
21            .filter(|&v| v != Self::REMOVED)
22    }
23
24    pub fn triangle(&self, old: TriangleId) -> Option<TriangleId> {
25        self.triangles
26            .get(old as usize)
27            .copied()
28            .filter(|&t| t != Self::REMOVED)
29    }
30}
31
32/// Appends with a fallible reservation, so allocation failure is an error, not an
33/// abort. Callers reserve the final size up front; this then never reallocates.
34fn try_push<T>(v: &mut Vec<T>, x: T) -> Result<()> {
35    try_reserve(v, 1)?;
36    v.push(x);
37    Ok(())
38}
39
40impl Mesh {
41    /// Removes dead slots and renumbers alive vertices and triangles in their current
42    /// order. All existing patches become stale (`StalePatch`); use
43    /// [`crate::History::compact`] to clear a history at the same time. Channels
44    /// dropped by [`crate::Transaction::drop_channel`] are then gone for good.
45    ///
46    /// Failure-atomic: if memory runs out, the mesh is left unchanged.
47    pub fn compact(&mut self) -> Result<Remap> {
48        // Phase 1 (fallible): build every new column as a local. `self` is not written.
49        let mut vmap = try_vec(self.vertex_slots(), Remap::REMOVED)?;
50        let mut alive_v: Vec<usize> = Vec::new();
51        try_reserve_exact(&mut alive_v, self.live_vertices)?;
52        for v in 0..self.vertex_slots() as u32 {
53            if self.is_vertex_alive(v) {
54                vmap[v as usize] = alive_v.len() as u32;
55                try_push(&mut alive_v, v as usize)?;
56            }
57        }
58        let mut tmap = try_vec(self.triangle_slots(), Remap::REMOVED)?;
59        let mut tris: Vec<[u32; 3]> = Vec::new();
60        try_reserve_exact(&mut tris, self.live_triangles)?;
61        for t in 0..self.triangle_slots() as u32 {
62            if let Some(tri) = self.triangle(t) {
63                tmap[t as usize] = tris.len() as u32;
64                try_push(&mut tris, tri.map(|v| vmap[v as usize]))?;
65            }
66        }
67
68        let mut positions: Vec<[f32; 3]> = Vec::new();
69        let mut refs: Vec<u32> = Vec::new();
70        try_reserve_exact(&mut positions, alive_v.len())?;
71        try_reserve_exact(&mut refs, alive_v.len())?;
72        for &v in &alive_v {
73            try_push(&mut positions, self.positions.get(v))?;
74            try_push(&mut refs, self.vertex_refs.get(v))?;
75        }
76        let mut channel_data: Vec<Vec<f32>> = Vec::new();
77        try_reserve_exact(&mut channel_data, self.channels.len())?;
78        // Hidden channels only served patches, which compacting makes stale.
79        for c in self.channels.iter().filter(|c| !c.hidden) {
80            let w = c.desc.width;
81            let data = c.data.as_slice();
82            let mut compacted: Vec<f32> = Vec::new();
83            try_reserve_exact(&mut compacted, alive_v.len() * w)?;
84            for &v in &alive_v {
85                for &x in &data[v * w..(v + 1) * w] {
86                    try_push(&mut compacted, x)?;
87                }
88            }
89            channel_data.push(compacted);
90        }
91        let vertex_live = full_bits(alive_v.len())?;
92        let triangle_live = full_bits(tris.len())?;
93
94        // Phase 2 (infallible): install the new columns and bump the revision.
95        self.channels.retain(|c| !c.hidden);
96        for (c, data) in self.channels.iter_mut().zip(channel_data) {
97            c.data = Column::from_vec(data);
98        }
99        self.vertex_live = Column::from_vec(vertex_live);
100        self.triangle_live = Column::from_vec(triangle_live);
101        self.positions = Column::from_vec(positions);
102        self.vertex_refs = Column::from_vec(refs);
103        self.triangles = Column::from_vec(tris);
104        self.live_vertices = alive_v.len();
105        self.live_triangles = self.triangles.len();
106        self.vertex_free.clear();
107        self.triangle_free.clear();
108        self.epoch += 1;
109        self.next_revision += 1;
110        self.revision = self.next_revision;
111        self.on_slots_renumbered();
112        Ok(Remap {
113            vertices: vmap,
114            triangles: tmap,
115        })
116    }
117}
118
119#[cfg(test)]
120mod tests {
121    use crate::{ChannelDesc, History, Mesh, StoreError};
122
123    #[test]
124    fn compact_renumbers_alive_elements_in_order() {
125        let mut m = Mesh::from_buffers(
126            &[0., 0., 0., 1., 0., 0., 1., 1., 0., 0., 1., 0.],
127            &[0, 1, 2, 0, 2, 3],
128        )
129        .unwrap();
130        m.add_channel(ChannelDesc::source("mask", 1)).unwrap();
131        let mut tx = m.begin_edit();
132        tx.write_channel("mask", &[0, 1, 2, 3], &[0., 1., 2., 3.])
133            .unwrap();
134        tx.remove_triangles(&[0]).unwrap();
135        tx.remove_vertices(&[1]).unwrap();
136        let patch = tx.commit().unwrap();
137
138        let epoch = m.epoch();
139        let remap = m.compact().unwrap();
140        assert_ne!(m.epoch(), epoch, "compact must change the epoch");
141        assert_eq!(remap.vertices, vec![0, u32::MAX, 1, 2]);
142        assert_eq!(remap.triangle(1), Some(0));
143        assert_eq!(remap.triangle(0), None);
144        assert_eq!((m.vertex_slots(), m.triangle_slots()), (3, 1));
145        assert_eq!(m.triangle(0), Some([0, 1, 2]));
146        assert_eq!(m.position(1), Some([1., 1., 0.]));
147        assert_eq!(m.channel("mask").unwrap(), &[0., 2., 3.]);
148        assert_eq!(m.corner_count(0), 1);
149        assert_eq!(patch.revert(&mut m).err(), Some(StoreError::StalePatch));
150    }
151
152    #[test]
153    fn compacted_columns_have_no_slack() {
154        let positions = vec![0.0f32; 3 * 100];
155        let indices: Vec<u32> = (0..98).flat_map(|i| [i, i + 1, i + 2]).collect();
156        let mut m = Mesh::from_buffers(&positions, &indices).unwrap();
157        let mut tx = m.begin_edit();
158        tx.remove_triangles(&[97]).unwrap();
159        tx.remove_vertices(&[99]).unwrap();
160        tx.commit().unwrap();
161        m.compact().unwrap();
162        assert_eq!((m.vertex_slots(), m.triangle_slots()), (99, 97));
163        assert_eq!(m.positions.capacity(), 99);
164        assert_eq!(m.vertex_refs.capacity(), 99);
165        assert_eq!(m.triangles.capacity(), 97);
166    }
167
168    #[test]
169    fn history_compact_clears_the_stacks() {
170        let mut m = Mesh::from_buffers(&[0., 0., 0.], &[]).unwrap();
171        let mut h = History::new(1 << 20);
172        let mut tx = m.begin_edit();
173        tx.remove_vertices(&[0]).unwrap();
174        let p = tx.commit().unwrap();
175        h.push(&mut m, p).unwrap();
176        h.compact(&mut m).unwrap();
177        assert!(!h.can_undo());
178        assert_eq!(m.vertex_slots(), 0);
179        assert!(m.free_vertex_slots().is_empty());
180    }
181}
fast_mesh_store/compact.rs

fast_mesh_store/
compact.rs
