ogeom_mesh/editable/
simplify.rs

1//! Decimating an editable mesh in place, its source vertices carried.
2//!
3//! [`Editable::simplify`] writes the mesh out as
4//! [`Editable::to_triangulation`] does, decimates that with
5//! [`simplify`](crate::simplify()), and builds the mesh again from the
6//! result. The result is the free function's on the written mesh, triangle
7//! for triangle, and so is what it reports. Each vertex of the result
8//! takes the source vertices of every vertex merged into it, through
9//! [`Simplified::result_vertex`](crate::Simplified::result_vertex), so a
10//! marking of the first source still selects what it did, as the
11//! [module documentation](super) defines selection.
12//!
13//! # What stays
14//!
15//! Nothing of the numbering: decimation is a compaction, as
16//! [`Editable::to_triangulation`] is. Vertex `v` afterwards is the result's
17//! vertex `v`, and face `f` its triangle `f`; a point the result's faces
18//! meet in several fans is split as [`Editable::from`] splits it, each copy
19//! with the point's source vertices. A vertex no face used is dropped with
20//! its source vertices.
21
22use ogeom_core::{OgeomResult, Tolerances};
23
24use super::{Editable, index};
25use crate::simplify::{Deviation, Target, simplify};
26
27/// What decimating an editable mesh did: [`Simplified`](crate::Simplified)
28/// without the mesh, which is now the editable one.
29#[derive(Debug, Clone, Copy, PartialEq)]
30pub struct SimplifyReport {
31    /// The worst error accepted, as a distance; as
32    /// [`Simplified::error`](crate::Simplified::error).
33    pub error: f64,
34    /// How many edge collapses were made.
35    pub collapsed: usize,
36    /// Whether the target was reached; as
37    /// [`Simplified::target_met`](crate::Simplified::target_met).
38    pub target_met: bool,
39    /// With [`Target::Verified`], what was measured against the mesh as it
40    /// stood before; `None` otherwise.
41    pub deviation: Option<Deviation>,
42}
43
44impl Editable {
45    /// Decimate the mesh to `target`, as [`simplify`](crate::simplify())
46    /// decimates [`Editable::to_triangulation`]'s mesh, keeping every
47    /// vertex's source vertices: a vertex of the result has those of every
48    /// vertex merged into it. See the [module
49    /// documentation](crate::editable::simplify) for the numbering after.
50    ///
51    /// # Errors
52    ///
53    /// As [`simplify`](crate::simplify()); nothing changes when it
54    /// refuses.
55    pub fn simplify(&mut self, target: Target, tol: Tolerances) -> OgeomResult<SimplifyReport> {
56        let written = self.to_triangulation();
57        let done = simplify(&written, target, tol)?;
58        let mut sources: Vec<Vec<u32>> = vec![Vec::new(); done.mesh.positions.len()];
59        let kept = (0..self.positions.len()).filter(|&v| !self.gone[v]);
60        for (v, r) in kept.zip(&done.result_vertex) {
61            if let Some(r) = r {
62                sources[*r as usize].extend_from_slice(self.source_vertices(index(v)));
63            }
64        }
65        let mut next = Self::from(&done.mesh, 0.0)?;
66        for set in &mut sources {
67            set.sort_unstable();
68            set.dedup();
69        }
70        // Built without a weld, each vertex's source is the result vertex
71        // it is or was split from.
72        for v in 0..next.positions.len() {
73            let r = next.source[v] as usize;
74            next.set_sources(index(v), sources[r].clone());
75        }
76        next.source_count = self.source_count;
77        *self = next;
78        Ok(SimplifyReport {
79            error: done.error,
80            collapsed: done.collapsed,
81            target_met: done.target_met,
82            deviation: done.deviation,
83        })
84    }
85}
86
87#[cfg(test)]
88#[allow(clippy::unwrap_used)]
89mod tests {
90    use super::super::tests::{check, torus};
91    use super::*;
92    use crate::editable::{Cap, Side, Smooth};
93    use crate::{Deflection, triangulate};
94    use ogeom_algo::make_sphere;
95    use ogeom_math::{Direction, Frame, Plane, Point, Vector};
96    use ogeom_topo::{Model, Triangulation};
97
98    const T: Tolerances = Tolerances::millimetres();
99
100    fn sphere(chord: f64) -> Triangulation {
101        let mut model = Model::new();
102        let built = make_sphere(&mut model, Frame::WORLD, 10.0, T).unwrap();
103        let deflection = Deflection {
104            chord,
105            ..Deflection::default()
106        };
107        triangulate(&model, &built.shape, deflection, T).unwrap()
108    }
109
110    const TO_200: Target = Target::Verified {
111        tolerance: 0.2,
112        share: 0.999,
113        max_triangles: Some(200),
114    };
115
116    /// The vertex numbers there, with a face or not.
117    fn present(e: &Editable) -> Vec<u32> {
118        (0..e.vertex_count())
119            .map(index)
120            .filter(|&v| e.position(v).is_some())
121            .collect()
122    }
123
124    #[test]
125    fn marking_every_source_vertex_offsets_the_reduced_mesh_whole() {
126        let source = sphere(0.005);
127        assert!(source.is_closed() && source.triangle_count() > 10_000);
128        let mut e = Editable::from(&source, 0.0).unwrap();
129        let report = e.simplify(TO_200, T).unwrap();
130        check(&e);
131
132        // The free function's mesh and report, unchanged.
133        let free = simplify(&source, TO_200, T).unwrap();
134        let written = e.to_triangulation();
135        assert_eq!(written.positions, free.mesh.positions);
136        assert_eq!(written.triangles, free.mesh.triangles);
137        assert!(free.mesh.triangle_count() <= 200);
138        assert_eq!(report.deviation, free.deviation);
139        assert_eq!(report.error.to_bits(), free.error.to_bits());
140        assert_eq!(report.collapsed, free.collapsed);
141        assert_eq!(report.target_met, free.target_met);
142        assert_eq!(e.source_count(), source.positions.len());
143
144        let region = e
145            .region_from_sources(&vec![true; e.source_count()])
146            .unwrap();
147        assert!(present(&e).iter().all(|&v| region[v as usize]));
148        let (mut marked, mut whole) = (e.clone(), e.clone());
149        let by_marking = marked.offset(0.1, Some(&region)).unwrap();
150        let by_whole = whole.offset(0.1, None).unwrap();
151        assert_eq!(by_marking, by_whole);
152        assert_eq!(marked.to_triangulation(), whole.to_triangulation());
153        // Every vertex moved outward, the collapsed ones as well.
154        let moved = marked.to_triangulation();
155        for (p, q) in moved.positions.iter().zip(&written.positions) {
156            assert!(p.to_vector().magnitude() > q.to_vector().magnitude());
157        }
158    }
159
160    #[test]
161    fn one_collapse_merges_the_two_source_sets() {
162        // One collapse on a closed mesh removes two triangles, and puts
163        // the vertex it keeps at the midpoint of the two it merged.
164        let source = torus(12, 8);
165        let mut e = Editable::from(&source, 0.0).unwrap();
166        let report = e
167            .simplify(Target::Triangles(source.triangle_count() - 2), T)
168            .unwrap();
169        check(&e);
170        assert_eq!(report.collapsed, 1);
171        assert_eq!(e.vertex_count(), source.positions.len() - 1);
172
173        let mut pair = None;
174        for v in present(&e) {
175            let at = e.position(v).unwrap();
176            match *e.source_vertices(v) {
177                [s] => {
178                    assert_eq!(e.source_vertex(v), Some(s));
179                    assert_eq!(at, source.positions[s as usize]);
180                }
181                [a, b] => {
182                    assert!(pair.is_none(), "a second merged vertex {v}");
183                    assert_eq!(e.source_vertex(v), None);
184                    let (pa, pb) = (source.positions[a as usize], source.positions[b as usize]);
185                    assert_eq!(
186                        at,
187                        Point::from_vector((pa.to_vector() + pb.to_vector()) * 0.5)
188                    );
189                    pair = Some((v, a, b));
190                }
191                ref other => panic!("vertex {v} from {other:?}"),
192            }
193        }
194        let (v, a, b) = pair.unwrap();
195        // Every source vertex is behind exactly one vertex.
196        let mut all: Vec<u32> = present(&e)
197            .iter()
198            .flat_map(|&w| e.source_vertices(w).to_vec())
199            .collect();
200        all.sort_unstable();
201        assert_eq!(all, (0..index(source.positions.len())).collect::<Vec<_>>());
202
203        // The merged vertex is selected only with both its sources marked;
204        // the others with theirs, whatever their numbers now.
205        for marks in [vec![a], vec![b], vec![a, b]] {
206            let mut marked = vec![false; source.positions.len()];
207            for &s in &marks {
208                marked[s as usize] = true;
209            }
210            marked[0] = true;
211            let region = e.region_from_sources(&marked).unwrap();
212            assert_eq!(region[v as usize], marks.len() == 2);
213            for w in present(&e).into_iter().filter(|&w| w != v) {
214                let s = e.source_vertex(w).unwrap();
215                assert_eq!(region[w as usize], marked[s as usize], "vertex {w}");
216            }
217        }
218        assert!(e.region_from_sources(&[true; 3]).is_err());
219    }
220
221    #[test]
222    fn a_partial_marking_follows_the_recorded_sets() {
223        let source = sphere(0.005);
224        let mut e = Editable::from(&source, 0.0).unwrap();
225        e.simplify(TO_200, T).unwrap();
226        let marked: Vec<bool> = source.positions.iter().map(|p| p.z > 0.0).collect();
227        let region = e.region_from_sources(&marked).unwrap();
228
229        let mut seen = vec![false; source.positions.len()];
230        let mut mixed = 0;
231        for v in present(&e) {
232            let sources = e.source_vertices(v);
233            assert!(!sources.is_empty() && sources.windows(2).all(|w| w[0] < w[1]));
234            for &s in sources {
235                assert!(!seen[s as usize], "source vertex {s} behind two vertices");
236                seen[s as usize] = true;
237            }
238            if let [s] = *sources {
239                // A vertex nothing merged into has not moved.
240                assert_eq!(e.position(v), Some(source.positions[s as usize]));
241            }
242            let all = sources.iter().all(|&s| marked[s as usize]);
243            let any = sources.iter().any(|&s| marked[s as usize]);
244            mixed += usize::from(any && !all);
245            assert_eq!(region[v as usize], all, "vertex {v} from {sources:?}");
246        }
247        assert!(seen.iter().all(|&s| s), "a source vertex behind none");
248        // Not a marking every set falls on one side of.
249        assert!(mixed > 0);
250        assert!(region.iter().any(|&r| r) && present(&e).iter().any(|&v| !region[v as usize]));
251    }
252
253    /// Each source vertex, and how many vertices name it.
254    fn uses(e: &Editable) -> Vec<usize> {
255        let mut count = vec![0; e.source_count()];
256        for v in present(e) {
257            for &s in e.source_vertices(v) {
258                count[s as usize] += 1;
259            }
260        }
261        count
262    }
263
264    #[test]
265    fn edits_then_two_reductions_carry_sources_and_make_none_up() {
266        let source = sphere(0.1);
267        let mut e = Editable::from(&source, 0.0).unwrap();
268        // A cut makes vertices with no source, an offset of a region
269        // copies the vertices on its edge with their sources, and a smooth
270        // moves them all.
271        let plane = Plane::through(
272            Point::new(0.0, 0.0, 6.0),
273            Direction::new(Vector::Z, T).unwrap(),
274        );
275        e.cut(&plane, Side::Below, Some(Cap::default())).unwrap();
276        let marked: Vec<bool> = source.positions.iter().map(|p| p.x > 0.0).collect();
277        let region = e.region_from_sources(&marked).unwrap();
278        e.offset(0.5, Some(&region)).unwrap();
279        e.smooth(&Smooth {
280            size: 1.0,
281            max_move: 0.05,
282            keep_edges: Some(0.5),
283            region: None,
284        })
285        .unwrap();
286        check(&e);
287        let unsourced = |e: &Editable| {
288            present(e)
289                .into_iter()
290                .filter(|&v| e.source_vertices(v).is_empty())
291                .count()
292        };
293        assert!(unsourced(&e) > 0);
294        assert!(uses(&e).iter().any(|&n| n > 1), "the wall copied nothing");
295
296        for target in [
297            Target::Verified {
298                tolerance: 0.05,
299                share: 0.999,
300                max_triangles: None,
301            },
302            Target::Triangles(400),
303        ] {
304            let before = uses(&e);
305            let none_before = unsourced(&e);
306            let report = e.simplify(target, T).unwrap();
307            check(&e);
308            assert!(report.collapsed > 0);
309            // A collapse only merges: no source vertex behind more vertices
310            // than before, none appearing, and no vertex without a source
311            // that did not come only of such vertices.
312            for (s, (&after, &was)) in uses(&e).iter().zip(&before).enumerate() {
313                assert!(after <= was, "source vertex {s} behind {after}, was {was}");
314            }
315            assert!(unsourced(&e) <= none_before);
316            for v in present(&e) {
317                assert!(
318                    e.source_vertices(v)
319                        .iter()
320                        .all(|&s| (s as usize) < source.positions.len())
321                );
322            }
323        }
324        assert!(e.to_triangulation().triangle_count() <= 400);
325    }
326}
ogeom_mesh/editable/simplify.rs

ogeom_mesh/editable/
simplify.rs
