Skip to main content

meshoptimizer_rs/
lod_chain.rs

1use crate::{
2    simplify_generic, simplify_scale, simplify_with_attributes_generic, Attributes, Error, Limits,
3    Positions, SimplifyOptions, SimplifySettings, Usage, VertexFlags, Workspace,
4};
5use alloc::vec::Vec;
6use core::fmt;
7
8/// Level targets, expressed as index counts or fractions of the source index count.
9#[derive(Clone, Copy, Debug)]
10#[non_exhaustive]
11pub enum LodTargets<'a> {
12    /// Strictly decreasing counts, smaller than the source index count.
13    Counts(&'a [usize]),
14    /// Strictly decreasing finite fractions in [0, 1) of the source triangle count.
15    ///
16    /// Each ratio becomes `floor(ratio * source_triangles) * 3` indices, computed in
17    /// `f64`. The ratios must decrease strictly, but the rounded counts only need to
18    /// be non-increasing: on a small mesh two neighbouring ratios may round to the
19    /// same count, which yields a level equal in size to the previous one.
20    Ratios(&'a [f32]),
21}
22/// A single error cap or one cap per level, in the units selected by the simplifier options.
23#[derive(Clone, Copy, Debug)]
24#[non_exhaustive]
25pub enum LodErrors<'a> {
26    /// One cap for every level.
27    Uniform(f32),
28    /// One cap per target.
29    PerLevel(&'a [f32]),
30}
31/// Attribute inputs passed unchanged to the simplifier.
32///
33/// Per-vertex flags (locks) are set on [`LodChainOptions`] and apply with or
34/// without attributes.
35#[derive(Clone, Copy, Debug)]
36#[non_exhaustive]
37pub struct LodChainAttributes<'a> {
38    /// Attribute view.
39    pub attributes: Attributes<'a>,
40    /// One weight per attribute component.
41    pub weights: &'a [f32],
42}
43impl<'a> LodChainAttributes<'a> {
44    /// Attribute view and one weight per component.
45    pub fn new(attributes: Attributes<'a>, weights: &'a [f32]) -> Self {
46        Self {
47            attributes,
48            weights,
49        }
50    }
51}
52/// Parameters for the LOD chain builder. Build one with [`Self::new`] and the
53/// `with_*` setters; the struct is `#[non_exhaustive]` so options can be added.
54#[derive(Clone, Copy, Debug)]
55#[non_exhaustive]
56pub struct LodChainOptions<'a> {
57    /// Target index counts or source-relative ratios.
58    pub targets: LodTargets<'a>,
59    /// Error limits.
60    pub errors: LodErrors<'a>,
61    /// Simplification flags.
62    pub simplify_options: SimplifyOptions,
63    /// Optional attribute inputs.
64    pub attributes: Option<LodChainAttributes<'a>>,
65    /// Optional per-vertex flags (for example locks), one per vertex. They apply
66    /// to every level, with or without attributes.
67    pub vertex_flags: Option<&'a [VertexFlags]>,
68    /// Use the original source for every level instead of the preceding level (default false).
69    pub independent: bool,
70}
71impl<'a> LodChainOptions<'a> {
72    /// Create a successive chain with default simplification flags, no attributes
73    /// and no vertex flags.
74    pub fn new(targets: LodTargets<'a>, errors: LodErrors<'a>) -> Self {
75        Self {
76            targets,
77            errors,
78            simplify_options: SimplifyOptions::EMPTY,
79            attributes: None,
80            vertex_flags: None,
81            independent: false,
82        }
83    }
84    /// Set the simplification flags.
85    #[must_use]
86    pub fn with_simplify_options(mut self, options: SimplifyOptions) -> Self {
87        self.simplify_options = options;
88        self
89    }
90    /// Simplify with attributes.
91    #[must_use]
92    pub fn with_attributes(mut self, attributes: LodChainAttributes<'a>) -> Self {
93        self.attributes = Some(attributes);
94        self
95    }
96    /// Apply per-vertex flags to every level, with or without attributes.
97    #[must_use]
98    pub fn with_vertex_flags(mut self, flags: &'a [VertexFlags]) -> Self {
99        self.vertex_flags = Some(flags);
100        self
101    }
102    /// Simplify every level from the original source (`true`) or from the
103    /// preceding level (`false`, the default).
104    #[must_use]
105    pub fn with_independent(mut self, independent: bool) -> Self {
106        self.independent = independent;
107        self
108    }
109}
110/// One simplification result. Errors describe this call, not cumulative chain error.
111///
112/// The index buffer is an owned `Vec<u32>` per level; other outputs (meshlets,
113/// clusters) would be separate APIs rather than fields here.
114#[derive(Debug)]
115#[non_exhaustive]
116pub struct LodLevelGeneric<I: crate::Index = u32> {
117    /// Indices referencing the original vertices.
118    pub indices: Vec<I>,
119    /// The error the simplifier returned for this level, unmodified. It is per
120    /// level: in successive mode it is relative to this level's input (the
121    /// previous level), not to the source and not cumulative. With attributes it
122    /// includes the attribute terms. Units follow `ERROR_ABSOLUTE`: relative to
123    /// `scale` unless that flag is set, absolute position units otherwise.
124    pub error: f32,
125    /// Position extent (largest axis range) used to normalize this level's error:
126    /// all positions, or only the vertices this level's input references with
127    /// `SPARSE`.
128    pub scale: f32,
129    /// Number of triangles.
130    pub triangle_count: usize,
131    /// Whether the requested target was reached. A missed target can also result from topology constraints.
132    pub target_reached: bool,
133    /// The simplifier stopped because its next collapse candidate exceeded this
134    /// level's error limit before the target was reached. This does not prove
135    /// that a looser limit would reach the target; topology can still block it.
136    pub stopped_at_error_limit: bool,
137}
138/// The generated levels in target order.
139#[derive(Debug)]
140#[non_exhaustive]
141pub struct LodChainGeneric<I: crate::Index = u32> {
142    /// Generated levels.
143    pub levels: Vec<LodLevelGeneric<I>>,
144}
145/// A failed [`build_lod_chain`] call: the underlying [`Error`] and the level it
146/// occurred in.
147///
148/// The crate's other fallible calls return a bare [`Error`]; a chain has several
149/// independent steps, so this wrapper adds only the failing level. The result is
150/// atomic: no partial chain accompanies the error.
151#[derive(Clone, Copy, Debug, PartialEq, Eq)]
152#[non_exhaustive]
153pub struct LodChainError {
154    /// Zero-based index into the targets (and into `LodChain::levels`) of the
155    /// level that failed, or `None` for a failure of the call as a whole (an empty
156    /// or mismatched target list, or the chain metadata allocation).
157    pub level: Option<usize>,
158    /// The underlying failure.
159    pub error: Error,
160}
161impl fmt::Display for LodChainError {
162    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
163        match self.level {
164            Some(level) => write!(f, "LOD level {level}: {}", self.error),
165            None => write!(f, "LOD chain: {}", self.error),
166        }
167    }
168}
169#[cfg(feature = "std")]
170impl std::error::Error for LodChainError {
171    fn source(&self) -> Option<&(dyn std::error::Error + 'static)> {
172        Some(&self.error)
173    }
174}
175
176/// Whole-call meter: counted work shared by the builder's scans and every level,
177/// and peak bytes across the chain's own storage plus workspace scratch.
178struct Meter {
179    limit: u64,
180    spent: u64,
181    peak: usize,
182}
183impl Meter {
184    fn charge(&mut self, visits: usize) -> Result<(), Error> {
185        let visits = u64::try_from(visits).map_err(|_| Error::SizeOverflow)?;
186        self.spent = self.spent.saturating_add(visits);
187        if self.spent > self.limit {
188            return Err(Error::LimitExceeded);
189        }
190        Ok(())
191    }
192}
193
194/// Build a LOD chain. This extension is not in C++ meshoptimizer.
195///
196/// Each level is one [`simplify`](crate::simplify) (or [`simplify_with_attributes`](crate::simplify_with_attributes)) call, so its
197/// indices, error and limits behave exactly as the direct call on that level's
198/// input. Ratios are relative to the source, and rounded down to whole triangles
199/// (see [`LodTargets::Ratios`]). In chain mode a target is clamped to the previous
200/// result's size when necessary.
201///
202/// **Limits and usage.** The workspace limits apply to the whole call: counted
203/// work covers the target and cap validation (one visit per level), every level's
204/// simplification, and the scale scans (one visit per vertex of the mesh, once, or
205/// per referenced index of each level's input with `SPARSE`). Bytes cover the chain
206/// metadata and every retained level output together with the workspace scratch.
207/// [`Workspace::usage`] afterwards reports the whole call's work total and peak
208/// bytes, on success and on failure.
209///
210/// **Atomicity.** On failure no partial chain is returned; [`LodChainError::level`]
211/// names the failing level.
212///
213/// ```
214/// use meshoptimizer_rs::{build_lod_chain, LodChainOptions, LodTargets, LodErrors, Positions, Workspace};
215/// let p = [[0.,0.,0.], [1.,0.,0.], [0.,1.,0.], [1.,1.,0.]];
216/// let options = LodChainOptions::new(LodTargets::Counts(&[3]), LodErrors::Uniform(1.0));
217/// let chain = build_lod_chain(&[0,1,2,2,1,3], Positions::from_packed(&p), &options, &mut Workspace::default())?;
218/// assert_eq!(chain.levels.len(), 1);
219/// # Ok::<(), meshoptimizer_rs::LodChainError>(())
220/// ```
221/// # Errors
222/// [`LodChainError`] with `InvalidParameter` for invalid targets or caps, and the
223/// simplification, allocation and limit errors of the failing level.
224pub fn build_lod_chain_generic<I: crate::Index>(
225    indices: &[I],
226    positions: Positions<'_>,
227    options: &LodChainOptions<'_>,
228    workspace: &mut Workspace,
229) -> Result<LodChainGeneric<I>, LodChainError> {
230    build_lod_chain_internal(indices, positions, options, workspace, false)
231}
232
233// Character selection clamps a single level to its kept input size. Public
234// count lists still require strictly decreasing targets below the source.
235pub(crate) fn build_lod_chain_internal<I: crate::Index>(
236    indices: &[I],
237    positions: Positions<'_>,
238    options: &LodChainOptions<'_>,
239    workspace: &mut Workspace,
240    allow_equal: bool,
241) -> Result<LodChainGeneric<I>, LodChainError> {
242    let limits = workspace.limits();
243    let mut meter = Meter {
244        limit: limits.max_work,
245        spent: 0,
246        peak: 0,
247    };
248    let result = build(
249        indices,
250        positions,
251        options,
252        workspace,
253        limits,
254        &mut meter,
255        allow_equal,
256    );
257    workspace.set_lod_limits(limits);
258    workspace.set_lod_usage(Usage {
259        bytes: meter.peak,
260        work: meter.spent,
261    });
262    result
263}
264
265#[allow(clippy::too_many_arguments)]
266fn build<I: crate::Index>(
267    indices: &[I],
268    positions: Positions<'_>,
269    options: &LodChainOptions<'_>,
270    workspace: &mut Workspace,
271    limits: Limits,
272    meter: &mut Meter,
273    allow_equal: bool,
274) -> Result<LodChainGeneric<I>, LodChainError> {
275    let whole = |error: Error| LodChainError { level: None, error };
276    let at = |level: usize| {
277        move |error: Error| LodChainError {
278            level: Some(level),
279            error,
280        }
281    };
282    let len = match options.targets {
283        LodTargets::Counts(v) => v.len(),
284        LodTargets::Ratios(v) => v.len(),
285    };
286    if len == 0 {
287        return Err(whole(Error::InvalidParameter));
288    }
289    if let LodErrors::PerLevel(v) = options.errors {
290        if v.len() != len {
291            return Err(whole(Error::InvalidParameter));
292        }
293    }
294    // One visit per level for the target and cap validation below.
295    meter.charge(len).map_err(whole)?;
296    let target = |i: usize| match options.targets {
297        LodTargets::Counts(v) => v[i],
298        // The float-to-integer cast saturates, so a huge ratio only needs the
299        // multiplication to saturate too; the order check below then rejects it.
300        LodTargets::Ratios(v) => {
301            ((v[i] as f64 * (indices.len() / 3) as f64) as usize).saturating_mul(3)
302        }
303    };
304    let cap = |i: usize| match options.errors {
305        LodErrors::Uniform(v) => v,
306        LodErrors::PerLevel(v) => v[i],
307    };
308    let mut prev = indices.len();
309    let mut prev_ratio = 1.0f32;
310    for i in 0..len {
311        let t = target(i);
312        let e = cap(i);
313        let order_ok = match options.targets {
314            // Strictly decreasing counts below the source count.
315            LodTargets::Counts(_) => t < prev || (allow_equal && len == 1 && t == prev),
316            // Ratios must decrease strictly; their rounded counts may coincide.
317            LodTargets::Ratios(v) => {
318                let r = v[i];
319                let ok = r.is_finite() && r >= 0.0 && r < prev_ratio && t <= prev;
320                prev_ratio = r;
321                ok
322            }
323        };
324        if !order_ok || !e.is_finite() || e < 0.0 {
325            return Err(at(i)(Error::InvalidParameter));
326        }
327        prev = t;
328    }
329    let mut levels: Vec<LodLevelGeneric<I>> = Vec::new();
330    let metadata = len
331        .checked_mul(core::mem::size_of::<LodLevelGeneric<I>>())
332        .ok_or(Error::SizeOverflow)
333        .map_err(whole)?;
334    if metadata > limits.max_bytes {
335        meter.peak = metadata;
336        return Err(whole(Error::LimitExceeded));
337    }
338    levels
339        .try_reserve_exact(len)
340        .map_err(|_| whole(Error::AllocationFailed))?;
341    // Chain metadata plus every retained level output; workspace scratch is added
342    // by each level's own accounting under the reduced limit below.
343    let mut used = levels
344        .capacity()
345        .checked_mul(core::mem::size_of::<LodLevelGeneric<I>>())
346        .ok_or(Error::SizeOverflow)
347        .map_err(whole)?;
348    meter.peak = used;
349    let sparse = options.simplify_options.contains(SimplifyOptions::SPARSE);
350    let mut dense_scale: Option<f32> = None;
351    for i in 0..len {
352        let input = if options.independent || i == 0 {
353            indices
354        } else {
355            &levels[i - 1].indices
356        };
357        let settings = SimplifySettings {
358            target_index_count: target(i).min(input.len()),
359            target_error: cap(i),
360            options: options.simplify_options,
361        };
362        workspace.set_lod_limits(Limits {
363            max_bytes: limits
364                .max_bytes
365                .checked_sub(used)
366                .ok_or(Error::LimitExceeded)
367                .map_err(at(i))?,
368            max_work: limits
369                .max_work
370                .checked_sub(meter.spent)
371                .ok_or(Error::LimitExceeded)
372                .map_err(at(i))?,
373        });
374        let result = match (options.attributes, options.vertex_flags) {
375            (Some(a), flags) => simplify_with_attributes_generic(
376                input,
377                positions,
378                a.attributes,
379                a.weights,
380                flags,
381                settings,
382                workspace,
383            ),
384            (None, Some(flags)) => I::with_input(input, workspace, |input, workspace| {
385                crate::simplify::simplify_flagged(input, positions, flags, settings, workspace)
386                    .and_then(|value| crate::index::Convert::<I>::convert(value, workspace))
387            }),
388            (None, None) => simplify_generic(input, positions, settings, workspace),
389        };
390        let error_limited = workspace.lod_error_limited;
391        let usage = workspace.usage();
392        meter.spent = meter.spent.saturating_add(usage.work);
393        meter.peak = meter.peak.max(used.saturating_add(usage.bytes));
394        let result = result.map_err(at(i))?;
395        // The scale is computed only after the simplifier accepted the input, so
396        // it cannot add a failure the direct call does not have: a sparse call
397        // never looks at unreferenced vertices, and a dense call has already
398        // validated the same finite extent.
399        let scale = if sparse {
400            meter.charge(input.len()).map_err(at(i))?;
401            sparse_scale(input, positions).map_err(at(i))?
402        } else if let Some(scale) = dense_scale {
403            scale
404        } else {
405            meter.charge(positions.len()).map_err(at(i))?;
406            let scale = simplify_scale(positions).map_err(at(i))?;
407            dense_scale = Some(scale);
408            scale
409        };
410        used = used
411            .checked_add(
412                result
413                    .indices
414                    .capacity()
415                    .checked_mul(core::mem::size_of::<I>())
416                    .ok_or(Error::SizeOverflow)
417                    .map_err(at(i))?,
418            )
419            .ok_or(Error::SizeOverflow)
420            .map_err(at(i))?;
421        levels.push(LodLevelGeneric {
422            triangle_count: result.indices.len() / 3,
423            target_reached: result.indices.len() <= target(i),
424            stopped_at_error_limit: result.indices.len() > target(i) && error_limited,
425            indices: result.indices,
426            error: result.error,
427            scale,
428        });
429    }
430    Ok(LodChainGeneric { levels })
431}
432
433/// The largest axis range of the vertices `input` references, as sparse
434/// simplification computes it. An index outside `positions` cannot occur after a
435/// successful simplify call.
436fn sparse_scale<I: crate::Index>(input: &[I], positions: Positions<'_>) -> Result<f32, Error> {
437    if input.is_empty() {
438        return Ok(0.0);
439    }
440    let mut lo = [f32::INFINITY; 3];
441    let mut hi = [f32::NEG_INFINITY; 3];
442    for &index in input {
443        let p = positions
444            .get(index.to_u32() as usize)
445            .ok_or(Error::IndexOutOfBounds)?;
446        for k in 0..3 {
447            lo[k] = lo[k].min(p[k]);
448            hi[k] = hi[k].max(p[k]);
449        }
450    }
451    Ok((hi[0] - lo[0]).max(hi[1] - lo[1]).max(hi[2] - lo[2]))
452}
453
454/// The source-compatible u32 entry point; see [`build_lod_chain_generic`] for selectable index widths.
455#[inline]
456pub fn build_lod_chain(
457    indices: &[u32],
458    positions: Positions<'_>,
459    options: &LodChainOptions<'_>,
460    workspace: &mut Workspace,
461) -> Result<LodChain, LodChainError> {
462    build_lod_chain_generic::<u32>(indices, positions, options, workspace).map(Into::into)
463}
464
465/// The source-compatible u32 form of [`LodLevelGeneric`].
466/// One simplification result. Errors describe this call, not cumulative chain error.
467///
468/// The index buffer is an owned `Vec<u32>` per level; other outputs (meshlets,
469/// clusters) would be separate APIs rather than fields here.
470#[derive(Debug)]
471#[non_exhaustive]
472pub struct LodLevel {
473    /// Indices referencing the original vertices.
474    pub indices: Vec<u32>,
475    /// The error the simplifier returned for this level, unmodified. It is per
476    /// level: in successive mode it is relative to this level's input (the
477    /// previous level), not to the source and not cumulative. With attributes it
478    /// includes the attribute terms. Units follow `ERROR_ABSOLUTE`: relative to
479    /// `scale` unless that flag is set, absolute position units otherwise.
480    pub error: f32,
481    /// Position extent (largest axis range) used to normalize this level's error:
482    /// all positions, or only the vertices this level's input references with
483    /// `SPARSE`.
484    pub scale: f32,
485    /// Number of triangles.
486    pub triangle_count: usize,
487    /// Whether the requested target was reached. A missed target can also result from topology constraints.
488    pub target_reached: bool,
489    /// The simplifier stopped because its next collapse candidate exceeded this
490    /// level's error limit before the target was reached. This does not prove
491    /// that a looser limit would reach the target; topology can still block it.
492    pub stopped_at_error_limit: bool,
493}
494impl From<LodLevelGeneric<u32>> for LodLevel {
495    #[inline]
496    fn from(value: LodLevelGeneric<u32>) -> Self {
497        Self {
498            indices: value.indices,
499            error: value.error,
500            scale: value.scale,
501            triangle_count: value.triangle_count,
502            target_reached: value.target_reached,
503            stopped_at_error_limit: value.stopped_at_error_limit,
504        }
505    }
506}
507
508impl From<LodLevel> for LodLevelGeneric<u32> {
509    #[inline]
510    fn from(value: LodLevel) -> Self {
511        Self {
512            indices: value.indices,
513            error: value.error,
514            scale: value.scale,
515            triangle_count: value.triangle_count,
516            target_reached: value.target_reached,
517            stopped_at_error_limit: value.stopped_at_error_limit,
518        }
519    }
520}
521
522/// The source-compatible u32 form of [`LodChainGeneric`].
523/// The generated levels in target order.
524#[derive(Debug)]
525#[non_exhaustive]
526pub struct LodChain {
527    /// Generated levels.
528    pub levels: Vec<LodLevel>,
529}
530impl From<LodChainGeneric<u32>> for LodChain {
531    #[inline]
532    fn from(value: LodChainGeneric<u32>) -> Self {
533        Self {
534            levels: value.levels.into_iter().map(Into::into).collect(),
535        }
536    }
537}
538
539impl From<LodChain> for LodChainGeneric<u32> {
540    #[inline]
541    fn from(value: LodChain) -> Self {
542        Self {
543            levels: value.levels.into_iter().map(Into::into).collect(),
544        }
545    }
546}