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#[derive(Clone, Copy, Debug)]
10#[non_exhaustive]
11pub enum LodTargets<'a> {
12 Counts(&'a [usize]),
14 Ratios(&'a [f32]),
21}
22#[derive(Clone, Copy, Debug)]
24#[non_exhaustive]
25pub enum LodErrors<'a> {
26 Uniform(f32),
28 PerLevel(&'a [f32]),
30}
31#[derive(Clone, Copy, Debug)]
36#[non_exhaustive]
37pub struct LodChainAttributes<'a> {
38 pub attributes: Attributes<'a>,
40 pub weights: &'a [f32],
42}
43impl<'a> LodChainAttributes<'a> {
44 pub fn new(attributes: Attributes<'a>, weights: &'a [f32]) -> Self {
46 Self {
47 attributes,
48 weights,
49 }
50 }
51}
52#[derive(Clone, Copy, Debug)]
55#[non_exhaustive]
56pub struct LodChainOptions<'a> {
57 pub targets: LodTargets<'a>,
59 pub errors: LodErrors<'a>,
61 pub simplify_options: SimplifyOptions,
63 pub attributes: Option<LodChainAttributes<'a>>,
65 pub vertex_flags: Option<&'a [VertexFlags]>,
68 pub independent: bool,
70}
71impl<'a> LodChainOptions<'a> {
72 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 #[must_use]
86 pub fn with_simplify_options(mut self, options: SimplifyOptions) -> Self {
87 self.simplify_options = options;
88 self
89 }
90 #[must_use]
92 pub fn with_attributes(mut self, attributes: LodChainAttributes<'a>) -> Self {
93 self.attributes = Some(attributes);
94 self
95 }
96 #[must_use]
98 pub fn with_vertex_flags(mut self, flags: &'a [VertexFlags]) -> Self {
99 self.vertex_flags = Some(flags);
100 self
101 }
102 #[must_use]
105 pub fn with_independent(mut self, independent: bool) -> Self {
106 self.independent = independent;
107 self
108 }
109}
110#[derive(Debug)]
115#[non_exhaustive]
116pub struct LodLevelGeneric<I: crate::Index = u32> {
117 pub indices: Vec<I>,
119 pub error: f32,
125 pub scale: f32,
129 pub triangle_count: usize,
131 pub target_reached: bool,
133 pub stopped_at_error_limit: bool,
137}
138#[derive(Debug)]
140#[non_exhaustive]
141pub struct LodChainGeneric<I: crate::Index = u32> {
142 pub levels: Vec<LodLevelGeneric<I>>,
144}
145#[derive(Clone, Copy, Debug, PartialEq, Eq)]
152#[non_exhaustive]
153pub struct LodChainError {
154 pub level: Option<usize>,
158 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
176struct 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
194pub 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
233pub(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 meter.charge(len).map_err(whole)?;
296 let target = |i: usize| match options.targets {
297 LodTargets::Counts(v) => v[i],
298 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 LodTargets::Counts(_) => t < prev || (allow_equal && len == 1 && t == prev),
316 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 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 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
433fn 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#[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#[derive(Debug)]
471#[non_exhaustive]
472pub struct LodLevel {
473 pub indices: Vec<u32>,
475 pub error: f32,
481 pub scale: f32,
485 pub triangle_count: usize,
487 pub target_reached: bool,
489 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#[derive(Debug)]
525#[non_exhaustive]
526pub struct LodChain {
527 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}