Skip to main content

meshoptimizer_rs/
opacity.rs

1//! Opacity micromap generation translated from the pinned scalar reference.
2use crate::workspace::{checked_bytes, Work};
3use crate::{Error, Workspace};
4use alloc::vec::Vec;
5
6/// Output of upstream `meshopt_opacityMapMeasure`.
7#[derive(Clone, Debug, PartialEq)]
8pub struct OpacityMapMeasure {
9    /// Subdivision level for each unique entry.
10    pub levels: Vec<u8>,
11    /// Source triangle for each unique entry.
12    pub sources: Vec<u32>,
13    /// Entry index for each input triangle.
14    pub omm_indices: Vec<i32>,
15}
16
17/// Packed byte count for one micromap, corresponding to `meshopt_opacityMapEntrySize`.
18///
19/// # Errors
20/// `InvalidParameter` if the subdivision level or number of states is unsupported.
21#[inline(always)]
22pub fn opacity_map_entry_size(level: u8, states: u8) -> Result<usize, Error> {
23    if level > 12 || (states != 2 && states != 4) {
24        return Err(Error::InvalidParameter);
25    }
26    Ok(((1usize << (usize::from(level) * 2)) * usize::from(states / 2) + 7) >> 3)
27}
28
29fn table_size(count: usize) -> Result<usize, Error> {
30    let target = count.checked_add(count / 4).ok_or(Error::SizeOverflow)?;
31    target
32        .checked_next_power_of_two()
33        .ok_or(Error::SizeOverflow)
34}
35
36fn reserve<T>(count: usize) -> Result<Vec<T>, Error> {
37    checked_bytes(count, core::mem::size_of::<T>())?;
38    let mut value = Vec::new();
39    value
40        .try_reserve_exact(count)
41        .map_err(|_| Error::AllocationFailed)?;
42    Ok(value)
43}
44
45#[inline(always)]
46fn hash_update(mut h: u32, values: &[i32]) -> u32 {
47    for &value in values {
48        let mut k = value as u32;
49        k = k.wrapping_mul(0x5bd1e995);
50        k ^= k >> 24;
51        k = k.wrapping_mul(0x5bd1e995);
52        h = h.wrapping_mul(0x5bd1e995) ^ k;
53    }
54    h
55}
56
57#[inline(always)]
58fn hash_bytes(mut h: u32, key: &[u8]) -> u32 {
59    if key.len() < 4 {
60        h ^= u32::from(key[0]) | (u32::from(key[key.len() - 1]) << 8);
61    } else {
62        for bytes in key.as_chunks::<4>().0 {
63            let mut k = u32::from_le_bytes(*bytes);
64            k = k.wrapping_mul(0x5bd1e995);
65            k ^= k >> 24;
66            k = k.wrapping_mul(0x5bd1e995);
67            h = h.wrapping_mul(0x5bd1e995) ^ k;
68        }
69    }
70    h ^= h >> 13;
71    h = h.wrapping_mul(0x5bd1e995);
72    h ^ (h >> 15)
73}
74
75fn quantize(v: f32, size: u32) -> i32 {
76    (v * ((size * 4) as f32) + if v >= 0.0 { 0.5 } else { -0.5 }) as i32
77}
78
79#[inline]
80fn square_root(value: f32) -> f32 {
81    #[cfg(feature = "std")]
82    {
83        value.sqrt()
84    }
85    #[cfg(not(feature = "std"))]
86    {
87        libm::sqrtf(value)
88    }
89}
90
91// Scalar bit rounding follows libm's MIT-licensed generic floor (musl).
92// Preserve the existing feature-specific handling of non-finite values.
93#[inline(always)]
94fn floor(value: f32) -> f32 {
95    let bits = value.to_bits();
96    let exponent = ((bits >> 23) & 255) as i32 - 127;
97    if exponent >= 23 {
98        if exponent == 128 {
99            #[cfg(feature = "std")]
100            {
101                return value.floor();
102            }
103            #[cfg(not(feature = "std"))]
104            {
105                return libm::floorf(value);
106            }
107        }
108        return value;
109    }
110    if exponent < 0 {
111        return if bits >> 31 == 0 {
112            0.0
113        } else if bits << 1 != 0 {
114            -1.0
115        } else {
116            value
117        };
118    }
119    let mask = 0x007f_ffff >> exponent;
120    if bits & mask == 0 {
121        return value;
122    }
123    let rounded = if bits >> 31 != 0 { bits + mask } else { bits };
124    f32::from_bits(rounded & !mask)
125}
126
127#[inline]
128fn log2(value: f32) -> f32 {
129    #[cfg(feature = "std")]
130    {
131        value.log2()
132    }
133    #[cfg(not(feature = "std"))]
134    {
135        libm::log2f(value)
136    }
137}
138
139trait UvReader: Copy {
140    fn read(self, index: usize) -> [f32; 2];
141}
142impl UvReader for &[[f32; 2]] {
143    #[inline(always)]
144    fn read(self, index: usize) -> [f32; 2] {
145        self[index]
146    }
147}
148#[derive(Clone, Copy)]
149struct InterleavedUvs<'a> {
150    data: &'a [f32],
151    stride: usize,
152}
153impl UvReader for InterleavedUvs<'_> {
154    #[inline(always)]
155    fn read(self, index: usize) -> [f32; 2] {
156        let pair = &self.data[index * self.stride..][..2];
157        [pair[0], pair[1]]
158    }
159}
160
161#[allow(clippy::too_many_arguments)]
162fn measure_ranges(
163    indices: &[u32],
164    uvs: impl UvReader,
165    texture_width: u32,
166    texture_height: u32,
167    max_level: u8,
168    target_edge: f32,
169    table: &mut [u32],
170    keys: &mut Vec<([i32; 6], u8)>,
171    levels: &mut Vec<u8>,
172    sources: &mut Vec<u32>,
173    omm_indices: &mut Vec<i32>,
174    work: &mut Work,
175) -> Result<(), Error> {
176    let buckets = table.len();
177    let covers = |count: usize, work: &Work| -> Result<bool, Error> {
178        match count.checked_mul(buckets.saturating_add(1)) {
179            Some(bound) => work.covers(bound),
180            None => Ok(false),
181        }
182    };
183    if covers(indices.len() / 3, work)? {
184        return measure_triangles::<false>(
185            indices,
186            uvs,
187            0,
188            texture_width,
189            texture_height,
190            max_level,
191            target_edge,
192            table,
193            keys,
194            levels,
195            sources,
196            omm_indices,
197            work,
198        );
199    }
200    // Prove each small range independently; preserve exact per-probe fallback
201    // when remaining fuel cannot cover its worst-case bound.
202    for (range, slice) in indices.chunks(128 * 3).enumerate() {
203        if covers(slice.len() / 3, work)? {
204            measure_triangles::<false>(
205                slice,
206                uvs,
207                range * 128,
208                texture_width,
209                texture_height,
210                max_level,
211                target_edge,
212                table,
213                keys,
214                levels,
215                sources,
216                omm_indices,
217                work,
218            )?;
219        } else {
220            measure_triangles::<true>(
221                slice,
222                uvs,
223                range * 128,
224                texture_width,
225                texture_height,
226                max_level,
227                target_edge,
228                table,
229                keys,
230                levels,
231                sources,
232                omm_indices,
233                work,
234            )?;
235        }
236    }
237    Ok(())
238}
239
240#[allow(clippy::too_many_arguments)]
241fn measure_triangles<const CHARGE: bool>(
242    indices: &[u32],
243    uvs: impl UvReader,
244    source_base: usize,
245    texture_width: u32,
246    texture_height: u32,
247    max_level: u8,
248    target_edge: f32,
249    table: &mut [u32],
250    keys: &mut Vec<([i32; 6], u8)>,
251    levels: &mut Vec<u8>,
252    sources: &mut Vec<u32>,
253    omm_indices: &mut Vec<i32>,
254    work: &mut Work,
255) -> Result<(), Error> {
256    let buckets = table.len();
257    let mut visits = 0usize;
258    let area = texture_width as f32 * texture_height as f32;
259    for (i, triangle) in indices.as_chunks::<3>().0.iter().enumerate() {
260        if CHARGE {
261            work.add(1)?;
262        } else {
263            visits += 1;
264        }
265        let a = uvs.read(triangle[0] as usize);
266        let b = uvs.read(triangle[1] as usize);
267        let c = uvs.read(triangle[2] as usize);
268        let uv = [[a[0], a[1]], [b[0], b[1]], [c[0], c[1]]];
269        if !a[0].is_finite()
270            || !a[1].is_finite()
271            || !b[0].is_finite()
272            || !b[1].is_finite()
273            || !c[0].is_finite()
274            || !c[1].is_finite()
275        {
276            if !CHARGE {
277                work.add(visits)?;
278            }
279            return Err(Error::NumericalFailure);
280        }
281        let mut level = max_level;
282        if target_edge > 0.0 {
283            let uvarea = ((uv[1][0] - uv[0][0]) * (uv[2][1] - uv[0][1])
284                - (uv[2][0] - uv[0][0]) * (uv[1][1] - uv[0][1]))
285                .abs()
286                * 0.5
287                * area;
288            let ratio = square_root(uvarea) / target_edge;
289            let levelf = log2(ratio.max(1.0));
290            level = ((levelf + 0.5) as u8).min(max_level);
291        }
292        let key = (
293            [
294                quantize(uv[0][0], texture_width),
295                quantize(uv[0][1], texture_height),
296                quantize(uv[1][0], texture_width),
297                quantize(uv[1][1], texture_height),
298                quantize(uv[2][0], texture_width),
299                quantize(uv[2][1], texture_height),
300            ],
301            level,
302        );
303        let candidate = keys.len() as u32;
304        let mut bucket = hash_update(level as u32, &key.0) as usize & (buckets - 1);
305        let mut found = None;
306        for probe in 0..buckets {
307            if CHARGE {
308                work.add(1)?;
309            } else {
310                visits += 1;
311            }
312            let entry = table[bucket];
313            if entry == u32::MAX {
314                table[bucket] = candidate;
315                break;
316            }
317            if keys[entry as usize].1 == key.1 && keys[entry as usize].0 == key.0 {
318                found = Some(entry);
319                break;
320            }
321            bucket = (bucket + probe + 1) & (buckets - 1);
322        }
323        if let Some(existing) = found {
324            omm_indices.push(existing as i32);
325        } else {
326            keys.push(key);
327            levels.push(level);
328            sources.push((source_base + i) as u32);
329            omm_indices.push(candidate as i32);
330        }
331    }
332    if !CHARGE {
333        work.add(visits)?;
334    }
335    Ok(())
336}
337
338/// Deduplicate triangles by quantized UV and choose adaptive OMM levels.
339///
340/// `uvs` is an interleaved float view with `uv_stride` floats per vertex.
341/// It reproduces upstream `meshopt_opacityMapMeasure` for finite inputs.
342///
343/// # Errors
344/// `InvalidTopology` for incomplete triangles or `IndexOutOfBounds` for invalid vertex references.
345/// `InvalidParameter` for invalid texture/UV settings; `InvalidLayout` for a short UV view; `NumericalFailure` for non-finite geometry or calculations.
346/// `SizeOverflow` for size overflow, `LimitExceeded` for exhausted limits, or `AllocationFailed` for failed reservation.
347#[allow(clippy::too_many_arguments)]
348#[inline]
349pub fn opacity_map_measure_generic<I: crate::Index>(
350    indices: &[I],
351    uvs: &[f32],
352    vertex_count: usize,
353    uv_stride: usize,
354    texture_width: u32,
355    texture_height: u32,
356    max_level: u8,
357    target_edge: f32,
358    workspace: &mut Workspace,
359) -> Result<OpacityMapMeasure, Error> {
360    I::with_input(indices, workspace, |indices, workspace| {
361        opacity_map_measure_u32(
362            indices,
363            uvs,
364            vertex_count,
365            uv_stride,
366            texture_width,
367            texture_height,
368            max_level,
369            target_edge,
370            workspace,
371        )
372    })
373}
374
375#[allow(clippy::too_many_arguments)]
376fn opacity_map_measure_u32(
377    indices: &[u32],
378    uvs: &[f32],
379    vertex_count: usize,
380    uv_stride: usize,
381    texture_width: u32,
382    texture_height: u32,
383    max_level: u8,
384    target_edge: f32,
385    workspace: &mut Workspace,
386) -> Result<OpacityMapMeasure, Error> {
387    let mut work = workspace.begin();
388    let result = (|| {
389        if !indices.len().is_multiple_of(3) {
390            return Err(Error::InvalidTopology);
391        }
392        if !(2..=64).contains(&uv_stride)
393            || texture_width == 0
394            || texture_width > 16384
395            || texture_height == 0
396            || texture_height > 16384
397            || max_level > 12
398            || !target_edge.is_finite()
399            || target_edge < 0.0
400        {
401            return Err(Error::InvalidParameter);
402        }
403        if vertex_count > u32::MAX as usize || indices.len() / 3 > i32::MAX as usize {
404            return Err(Error::SizeOverflow);
405        }
406        let needed = vertex_count
407            .checked_sub(1)
408            .and_then(|v| v.checked_mul(uv_stride))
409            .and_then(|v| v.checked_add(2))
410            .unwrap_or(0);
411        if uvs.len() < needed {
412            return Err(Error::InvalidLayout);
413        }
414        work.indices(indices, vertex_count)?;
415        let count = indices.len() / 3;
416        let buckets = table_size(count)?;
417        let bytes = count
418            .checked_mul(3 * 4 + 6 * 4 + 4 + 4)
419            .and_then(|n| n.checked_add(buckets * 4))
420            .ok_or(Error::SizeOverflow)?;
421        workspace.account_codec(bytes)?;
422        let mut table = reserve::<u32>(buckets)?;
423        table.resize(buckets, u32::MAX);
424        let mut keys = reserve::<([i32; 6], u8)>(count)?;
425        let mut levels = reserve::<u8>(count)?;
426        let mut sources = reserve::<u32>(count)?;
427        let mut omm_indices = reserve::<i32>(count)?;
428        if uv_stride == 2 {
429            measure_ranges(
430                indices,
431                uvs.as_chunks::<2>().0,
432                texture_width,
433                texture_height,
434                max_level,
435                target_edge,
436                &mut table,
437                &mut keys,
438                &mut levels,
439                &mut sources,
440                &mut omm_indices,
441                &mut work,
442            )?;
443        } else {
444            measure_ranges(
445                indices,
446                InterleavedUvs {
447                    data: uvs,
448                    stride: uv_stride,
449                },
450                texture_width,
451                texture_height,
452                max_level,
453                target_edge,
454                &mut table,
455                &mut keys,
456                &mut levels,
457                &mut sources,
458                &mut omm_indices,
459                &mut work,
460            )?;
461        }
462        Ok(OpacityMapMeasure {
463            levels,
464            sources,
465            omm_indices,
466        })
467    })();
468    workspace.finish(&work);
469    result
470}
471
472/// Caller-buffer form of `meshopt_opacityMapMeasure`; returns unique entry count.
473/// The three destinations are unchanged when validation fails.
474///
475/// # Errors
476/// Same errors as [`opacity_map_measure`]. `BufferTooSmall` if an output buffer is too short.
477#[allow(clippy::too_many_arguments)]
478#[inline]
479pub fn opacity_map_measure_into_generic<I: crate::Index>(
480    levels: &mut [u8],
481    sources: &mut [u32],
482    omm_indices: &mut [i32],
483    indices: &[I],
484    uvs: &[f32],
485    vertex_count: usize,
486    uv_stride: usize,
487    texture_width: u32,
488    texture_height: u32,
489    max_level: u8,
490    target_edge: f32,
491    workspace: &mut Workspace,
492) -> Result<usize, Error> {
493    I::with_input(indices, workspace, |indices, workspace| {
494        opacity_map_measure_into_u32(
495            levels,
496            sources,
497            omm_indices,
498            indices,
499            uvs,
500            vertex_count,
501            uv_stride,
502            texture_width,
503            texture_height,
504            max_level,
505            target_edge,
506            workspace,
507        )
508    })
509}
510
511#[allow(clippy::too_many_arguments)]
512fn opacity_map_measure_into_u32(
513    levels: &mut [u8],
514    sources: &mut [u32],
515    omm_indices: &mut [i32],
516    indices: &[u32],
517    uvs: &[f32],
518    vertex_count: usize,
519    uv_stride: usize,
520    texture_width: u32,
521    texture_height: u32,
522    max_level: u8,
523    target_edge: f32,
524    workspace: &mut Workspace,
525) -> Result<usize, Error> {
526    let triangles = indices.len() / 3;
527    if levels.len() < triangles || sources.len() < triangles || omm_indices.len() < triangles {
528        return Err(Error::BufferTooSmall);
529    }
530    let result = opacity_map_measure_generic(
531        indices,
532        uvs,
533        vertex_count,
534        uv_stride,
535        texture_width,
536        texture_height,
537        max_level,
538        target_edge,
539        workspace,
540    )?;
541    let count = result.levels.len();
542    levels[..count].copy_from_slice(&result.levels);
543    sources[..count].copy_from_slice(&result.sources);
544    omm_indices[..triangles].copy_from_slice(&result.omm_indices);
545    Ok(count)
546}
547
548fn special_index(data: &[u8], level: u8, states: u8) -> i32 {
549    let first = i32::from(data[0] & if states == 2 { 1 } else { 3 });
550    let special = -(1 + first);
551    if level == 0 {
552        return special;
553    }
554    if level == 1 && states == 2 {
555        return if i32::from(data[0] & 15) == ((-first) & 15) {
556            special
557        } else {
558            0
559        };
560    }
561    let expected = first * if states == 2 { 0xff } else { 0x55 };
562    if data.iter().all(|&v| i32::from(v) == expected) {
563        special
564    } else {
565        0
566    }
567}
568
569/// Compact OMM data in place, as upstream `meshopt_opacityMapCompact` does.
570///
571/// Returns the remaining entry count and used byte count. Callers may trim the
572/// arrays to those lengths. Existing negative triangle references are retained.
573///
574/// # Errors
575/// `InvalidParameter` for unsupported states/levels; `InvalidLayout` for mismatched or out-of-range entries;
576/// `IndexOutOfBounds` for invalid opacity references; `BufferTooSmall` if compacted data exceeds capacity; `SizeOverflow` for size overflow, `LimitExceeded` for exhausted limits, or `AllocationFailed` for failed reservation.
577#[inline]
578pub fn opacity_map_compact(
579    data: &mut [u8],
580    levels: &mut [u8],
581    offsets: &mut [u32],
582    omm_indices: &mut [i32],
583    states: u8,
584    workspace: &mut Workspace,
585) -> Result<(usize, usize), Error> {
586    let mut work = workspace.begin();
587    let result = (|| {
588        if states != 2 && states != 4 {
589            return Err(Error::InvalidParameter);
590        }
591        if levels.len() != offsets.len() || levels.len() > i32::MAX as usize {
592            return Err(Error::InvalidLayout);
593        }
594        let count = levels.len();
595        let buckets = table_size(count)?;
596        for (&level, &offset) in levels.iter().zip(offsets.iter()) {
597            work.add(1)?;
598            let size = opacity_map_entry_size(level, states)?;
599            let end = (offset as usize)
600                .checked_add(size)
601                .ok_or(Error::SizeOverflow)?;
602            if end > data.len() {
603                return Err(Error::InvalidLayout);
604            }
605        }
606        for &index in omm_indices.iter() {
607            work.add(1)?;
608            if index >= count as i32 {
609                return Err(Error::IndexOutOfBounds);
610            }
611        }
612        let bytes = data
613            .len()
614            .checked_add(buckets * 4)
615            .and_then(|n| n.checked_add(count * 4))
616            .ok_or(Error::SizeOverflow)?;
617        workspace.account_codec(bytes)?;
618        // Small calls need no heap scratch. Keep the same logical byte budget
619        // and retain independent heap fallbacks for larger inputs.
620        let mut old_inline = [0u8; 64];
621        let mut old_heap;
622        let old = if data.len() <= old_inline.len() {
623            old_inline[..data.len()].copy_from_slice(data);
624            &old_inline[..data.len()]
625        } else {
626            old_heap = reserve::<u8>(data.len())?;
627            old_heap.extend_from_slice(data);
628            &old_heap[..]
629        };
630        let mut table_inline = [u32::MAX; 16];
631        let mut table_heap;
632        let table = if buckets <= table_inline.len() {
633            &mut table_inline[..buckets]
634        } else {
635            table_heap = reserve::<u32>(buckets)?;
636            table_heap.resize(buckets, u32::MAX);
637            &mut table_heap[..]
638        };
639        let mut remap_inline = [0i32; 8];
640        let mut remap_heap;
641        let remap = if count <= remap_inline.len() {
642            &mut remap_inline[..count]
643        } else {
644            remap_heap = reserve::<i32>(count)?;
645            remap_heap.resize(count, 0);
646            &mut remap_heap[..]
647        };
648        let (mut next, mut output_offset) = (0usize, 0usize);
649        for i in 0..count {
650            work.add(1)?;
651            let level = levels[i];
652            let size = opacity_map_entry_size(level, states)?;
653            let source = &old[offsets[i] as usize..offsets[i] as usize + size];
654            let special = special_index(source, level, states);
655            if special < 0 {
656                remap[i] = special;
657                continue;
658            }
659            if output_offset.checked_add(size).ok_or(Error::SizeOverflow)? > data.len() {
660                return Err(Error::BufferTooSmall);
661            }
662            data[output_offset..output_offset + size].copy_from_slice(source);
663            offsets[next] = output_offset as u32;
664            levels[next] = level;
665            let candidate = next as u32;
666            let mut bucket =
667                hash_bytes(u32::from(level), &data[output_offset..output_offset + size]) as usize
668                    & (buckets - 1);
669            let mut found = None;
670            for probe in 0..buckets {
671                work.add(1)?;
672                let entry = table[bucket];
673                if entry == u32::MAX {
674                    table[bucket] = candidate;
675                    break;
676                }
677                let other = offsets[entry as usize] as usize;
678                if levels[entry as usize] == level
679                    && data[other..other + size] == data[output_offset..output_offset + size]
680                {
681                    found = Some(entry);
682                    break;
683                }
684                bucket = (bucket + probe + 1) & (buckets - 1);
685            }
686            if let Some(existing) = found {
687                remap[i] = existing as i32;
688            } else {
689                remap[i] = candidate as i32;
690                next += 1;
691                output_offset += size;
692            }
693        }
694        for index in omm_indices.iter_mut() {
695            if *index >= 0 {
696                *index = remap[*index as usize];
697            }
698        }
699        Ok((next, output_offset))
700    })();
701    workspace.finish(&work);
702    result
703}
704
705#[inline(always)]
706fn sample(
707    data: &[u8],
708    stride: usize,
709    pitch: usize,
710    width: u32,
711    height: u32,
712    u: f32,
713    v: f32,
714) -> f32 {
715    let u = if (u - 0.5).abs() > 0.5 {
716        u - floor(u)
717    } else {
718        u
719    };
720    let v = if (v - 0.5).abs() > 0.5 {
721        v - floor(v)
722    } else {
723        v
724    };
725    let uf = ((u * (width as f32 * 256.0) - 127.5) as i32).max(0);
726    let vf = ((v * (height as f32 * 256.0) - 127.5) as i32).max(0);
727    let (x, y, rx, ry) = (uf >> 8, vf >> 8, uf & 255, vf & 255);
728    if x as u32 >= width || y as u32 >= height {
729        return 0.0;
730    }
731    let offset = y as usize * pitch + x as usize * stride;
732    let ox = if x as u32 + 1 < width { stride } else { 0 };
733    let oy = if y as u32 + 1 < height { pitch } else { 0 };
734    let (a00, a10, a01, a11) = (
735        data[offset] as i32,
736        data[offset + ox] as i32,
737        data[offset + oy] as i32,
738        data[offset + ox + oy] as i32,
739    );
740    let ax0 = a00 * 256 + (a10 - a00) * rx;
741    let ax1 = a01 * 256 + (a11 - a01) * rx;
742    let axy = ax0 * 256 + (ax1 - ax0) * ry;
743    axy as f32 * (1.0 / (255.0 * 65536.0))
744}
745
746#[inline(always)]
747fn edge(texture: &Texture<'_>, a: [f32; 3], b: [f32; 3], resolution: i32) -> i32 {
748    let step = 1.0 / (resolution + 1) as f32;
749    let (du, dv) = ((b[0] - a[0]) * step, (b[1] - a[1]) * step);
750    let (mut u, mut v) = (a[0], a[1]);
751    let (mut mask, mut count) = (0, 0);
752    for i in 0..resolution {
753        u += du;
754        v += dv;
755        let alpha = texture.sample(u, v);
756        mask |= i32::from(alpha >= 0.5) << i;
757        count += i32::from(alpha >= 0.5);
758    }
759    mask | (count << 16)
760}
761
762struct Texture<'a> {
763    data: &'a [u8],
764    stride: usize,
765    pitch: usize,
766    width: u32,
767    height: u32,
768}
769impl Texture<'_> {
770    #[inline(always)]
771    fn sample(&self, u: f32, v: f32) -> f32 {
772        sample(
773            self.data,
774            self.stride,
775            self.pitch,
776            self.width,
777            self.height,
778            u,
779            v,
780        )
781    }
782}
783
784fn emit<const STATES: u8>(
785    result: &mut [u8],
786    index: usize,
787    points: [[f32; 3]; 3],
788    center: f32,
789    edges: [i32; 3],
790    edgeres: i32,
791) {
792    let (a0, a1, a2) = (points[0][2], points[1][2], points[2][2]);
793    let mut coverage = (a0 + a1 + a2) * 0.12 + center * 0.64;
794    if edgeres != 0 {
795        coverage = center * 0.22
796            + ((edges[0] >> 16) + (edges[1] >> 16) + (edges[2] >> 16)) as f32
797                * (1.0 / edgeres as f32)
798                * 0.23
799            + (a0 + a1 + a2) * 0.03;
800    }
801    if STATES == 2 {
802        result[index / 8] |= u8::from(coverage >= 0.5) << (index % 8);
803        return;
804    }
805    let transparent = a0 < 0.5 && a1 < 0.5 && a2 < 0.5 && center < 0.5;
806    let opaque = a0 > 0.5 && a1 > 0.5 && a2 > 0.5 && center > 0.5;
807    let unknown = 2 + i32::from(coverage >= 0.5);
808    let mut state = if transparent || opaque {
809        i32::from(opaque)
810    } else {
811        unknown
812    };
813    if edgeres != 0 && (transparent || opaque) {
814        let expected = if opaque { (1 << edgeres) - 1 } else { 0 };
815        if edges.iter().any(|e| (e & 0xffff) != expected) {
816            state = unknown;
817        }
818    }
819    result[index / 4] |= (state as u8) << ((index % 4) * 2);
820}
821
822#[inline(always)]
823#[allow(clippy::too_many_arguments)]
824fn raster_setup<'a>(
825    level: u8,
826    uvs: [[f32; 2]; 3],
827    texture_data: &'a [u8],
828    texture_stride: usize,
829    texture_pitch: usize,
830    texture_width: u32,
831    texture_height: u32,
832) -> Result<(Texture<'a>, i32, [[f32; 3]; 3]), Error> {
833    if texture_width == 0
834        || texture_width > 16384
835        || texture_height == 0
836        || texture_height > 16384
837        || !(1..=4).contains(&texture_stride)
838        || texture_pitch < texture_stride * texture_width as usize
839        || uvs.iter().flatten().any(|v| !v.is_finite())
840    {
841        return Err(Error::InvalidParameter);
842    }
843    let required = (texture_height as usize - 1)
844        .checked_mul(texture_pitch)
845        .and_then(|n| n.checked_add((texture_width as usize - 1) * texture_stride))
846        .and_then(|n| n.checked_add(1))
847        .ok_or(Error::SizeOverflow)?;
848    if texture_data.len() < required {
849        return Err(Error::InvalidLayout);
850    }
851    let texture = Texture {
852        data: texture_data,
853        stride: texture_stride,
854        pitch: texture_pitch,
855        width: texture_width,
856        height: texture_height,
857    };
858    let area = texture_width as f32 * texture_height as f32;
859    let uvarea = ((uvs[1][0] - uvs[0][0]) * (uvs[2][1] - uvs[0][1])
860        - (uvs[2][0] - uvs[0][0]) * (uvs[1][1] - uvs[0][1]))
861        .abs()
862        * 0.5
863        * area;
864    let uvedge = square_root(uvarea) / (1u32 << level) as f32;
865    let edgeres = ((uvedge * 0.75) as i32).clamp(0, 7);
866    let corners = [
867        [uvs[0][0], uvs[0][1], texture.sample(uvs[0][0], uvs[0][1])],
868        [uvs[1][0], uvs[1][1], texture.sample(uvs[1][0], uvs[1][1])],
869        [uvs[2][0], uvs[2][1], texture.sample(uvs[2][0], uvs[2][1])],
870    ];
871    Ok((texture, edgeres, corners))
872}
873
874fn raster_visits(level: u8) -> usize {
875    // Each level has four children. The level-one edge-specialized path
876    // charges the same four children without recursing.
877    ((1usize << ((usize::from(level) + 1) * 2)) - 1) / 3
878}
879
880/// Rasterize one upstream opacity entry using an alpha-channel byte view.
881///
882/// # Errors
883/// `InvalidParameter` for unsupported settings; `InvalidLayout` for an invalid texture view;
884/// `SizeOverflow` for size overflow, `LimitExceeded` for exhausted limits, or `AllocationFailed` for failed reservation.
885#[allow(clippy::too_many_arguments)]
886#[inline(always)]
887pub fn opacity_map_rasterize(
888    level: u8,
889    states: u8,
890    uvs: [[f32; 2]; 3],
891    texture_data: &[u8],
892    texture_stride: usize,
893    texture_pitch: usize,
894    texture_width: u32,
895    texture_height: u32,
896    workspace: &mut Workspace,
897) -> Result<Vec<u8>, Error> {
898    let mut work = workspace.begin();
899    let result = rasterize_impl(
900        level,
901        states,
902        uvs,
903        texture_data,
904        texture_stride,
905        texture_pitch,
906        texture_width,
907        texture_height,
908        workspace,
909        &mut work,
910    );
911    workspace.finish(&work);
912    result
913}
914
915#[inline(always)]
916#[allow(clippy::too_many_arguments)]
917fn rasterize_impl(
918    level: u8,
919    states: u8,
920    uvs: [[f32; 2]; 3],
921    texture_data: &[u8],
922    texture_stride: usize,
923    texture_pitch: usize,
924    texture_width: u32,
925    texture_height: u32,
926    workspace: &mut Workspace,
927    work: &mut crate::workspace::Work,
928) -> Result<Vec<u8>, Error> {
929    let size = opacity_map_entry_size(level, states)?;
930    let (texture, edgeres, corners) = raster_setup(
931        level,
932        uvs,
933        texture_data,
934        texture_stride,
935        texture_pitch,
936        texture_width,
937        texture_height,
938    )?;
939    workspace.account_codec(size)?;
940    let mut result = reserve::<u8>(size)?;
941    result.resize(size, 0);
942    // The state format is passed explicitly through the recursive path.
943    raster_state(
944        &mut result,
945        0,
946        level,
947        states,
948        edgeres,
949        corners,
950        &texture,
951        work,
952    )?;
953    Ok(result)
954}
955
956/// Caller-buffer form of `meshopt_opacityMapRasterize`.
957/// Returns the number of bytes written and preserves the destination on error.
958///
959/// # Errors
960/// Same errors as [`opacity_map_rasterize`]. `BufferTooSmall` if an output buffer is too short.
961#[allow(clippy::too_many_arguments)]
962#[inline(always)]
963pub fn opacity_map_rasterize_into(
964    destination: &mut [u8],
965    level: u8,
966    states: u8,
967    uvs: [[f32; 2]; 3],
968    texture_data: &[u8],
969    texture_stride: usize,
970    texture_pitch: usize,
971    texture_width: u32,
972    texture_height: u32,
973    workspace: &mut Workspace,
974) -> Result<usize, Error> {
975    let size = opacity_map_entry_size(level, states)?;
976    if destination.len() < size {
977        return Err(Error::BufferTooSmall);
978    }
979    // Preserve the complete destination on a tight work budget by using the
980    // staged path; the default budget covers every recursive visit upfront.
981    if workspace.limits().max_work < raster_visits(level) as u64 {
982        let result = opacity_map_rasterize(
983            level,
984            states,
985            uvs,
986            texture_data,
987            texture_stride,
988            texture_pitch,
989            texture_width,
990            texture_height,
991            workspace,
992        )?;
993        destination[..size].copy_from_slice(&result);
994        return Ok(size);
995    }
996    let mut work = workspace.begin();
997    let result = rasterize_into_impl(
998        destination,
999        level,
1000        states,
1001        uvs,
1002        texture_data,
1003        texture_stride,
1004        texture_pitch,
1005        texture_width,
1006        texture_height,
1007        workspace,
1008        size,
1009        &mut work,
1010    );
1011    workspace.finish(&work);
1012    result
1013}
1014
1015#[inline(always)]
1016#[allow(clippy::too_many_arguments)]
1017fn rasterize_into_impl(
1018    destination: &mut [u8],
1019    level: u8,
1020    states: u8,
1021    uvs: [[f32; 2]; 3],
1022    texture_data: &[u8],
1023    texture_stride: usize,
1024    texture_pitch: usize,
1025    texture_width: u32,
1026    texture_height: u32,
1027    workspace: &mut Workspace,
1028    size: usize,
1029    work: &mut crate::workspace::Work,
1030) -> Result<usize, Error> {
1031    let (texture, edgeres, corners) = raster_setup(
1032        level,
1033        uvs,
1034        texture_data,
1035        texture_stride,
1036        texture_pitch,
1037        texture_width,
1038        texture_height,
1039    )?;
1040    workspace.account_codec(0)?;
1041    let result = &mut destination[..size];
1042    result.fill(0);
1043    raster_state(result, 0, level, states, edgeres, corners, &texture, work)?;
1044    Ok(size)
1045}
1046
1047#[inline(always)]
1048fn midpoint(a: [f32; 3], b: [f32; 3], texture: &Texture<'_>) -> [f32; 3] {
1049    let u = (a[0] + b[0]) / 2.0;
1050    let v = (a[1] + b[1]) / 2.0;
1051    [u, v, texture.sample(u, v)]
1052}
1053
1054#[allow(clippy::too_many_arguments)]
1055fn raster_state(
1056    result: &mut [u8],
1057    index: usize,
1058    level: u8,
1059    states: u8,
1060    edgeres: i32,
1061    corners: [[f32; 3]; 3],
1062    texture: &Texture<'_>,
1063    work: &mut crate::workspace::Work,
1064) -> Result<(), Error> {
1065    let visits = raster_visits(level);
1066    let bulk = work.covers(visits)?;
1067    if bulk {
1068        work.add(visits)?;
1069    }
1070    match (states == 2, bulk) {
1071        (true, true) => {
1072            raster_state_core::<false, 2>(result, index, level, edgeres, corners, texture, work)
1073        }
1074        (false, true) => {
1075            raster_state_core::<false, 4>(result, index, level, edgeres, corners, texture, work)
1076        }
1077        (true, false) => {
1078            raster_state_core::<true, 2>(result, index, level, edgeres, corners, texture, work)
1079        }
1080        (false, false) => {
1081            raster_state_core::<true, 4>(result, index, level, edgeres, corners, texture, work)
1082        }
1083    }
1084}
1085
1086#[allow(clippy::too_many_arguments)]
1087fn raster_state_core<const CHARGE_WORK: bool, const STATES: u8>(
1088    result: &mut [u8],
1089    index: usize,
1090    level: u8,
1091    edgeres: i32,
1092    corners: [[f32; 3]; 3],
1093    texture: &Texture<'_>,
1094    work: &mut crate::workspace::Work,
1095) -> Result<(), Error> {
1096    if CHARGE_WORK {
1097        work.add(1)?;
1098    }
1099    if level == 0 {
1100        let center = texture.sample(
1101            (corners[0][0] + corners[1][0] + corners[2][0]) * (1.0 / 3.0),
1102            (corners[0][1] + corners[1][1] + corners[2][1]) * (1.0 / 3.0),
1103        );
1104        let edges = if edgeres > 0 {
1105            [
1106                edge(texture, corners[0], corners[1], edgeres),
1107                edge(texture, corners[1], corners[2], edgeres),
1108                edge(texture, corners[2], corners[0], edgeres),
1109            ]
1110        } else {
1111            [0; 3]
1112        };
1113        emit::<STATES>(result, index, corners, center, edges, edgeres);
1114        return Ok(());
1115    }
1116    let mid = [
1117        midpoint(corners[0], corners[1], texture),
1118        midpoint(corners[1], corners[2], texture),
1119        midpoint(corners[2], corners[0], texture),
1120    ];
1121    if level == 1 && edgeres > 0 {
1122        let points = [corners[0], mid[0], corners[1], mid[1], corners[2], mid[2]];
1123        let edge_samples = [
1124            edge(texture, points[0], points[1], edgeres),
1125            edge(texture, points[1], points[2], edgeres),
1126            edge(texture, points[2], points[3], edgeres),
1127            edge(texture, points[3], points[4], edgeres),
1128            edge(texture, points[4], points[5], edgeres),
1129            edge(texture, points[5], points[0], edgeres),
1130            edge(texture, points[5], points[1], edgeres),
1131            edge(texture, points[1], points[3], edgeres),
1132            edge(texture, points[3], points[5], edgeres),
1133        ];
1134        let triangles = [
1135            [0, 1, 5, 0, 6, 5],
1136            [5, 3, 1, 8, 7, 6],
1137            [1, 2, 3, 1, 2, 7],
1138            [3, 5, 4, 8, 4, 3],
1139        ];
1140        for (child, [a, b, c, e0, e1, e2]) in triangles.into_iter().enumerate() {
1141            if CHARGE_WORK {
1142                work.add(1)?;
1143            }
1144            let tri = [points[a], points[b], points[c]];
1145            let center = texture.sample(
1146                (tri[0][0] + tri[1][0] + tri[2][0]) * (1.0 / 3.0),
1147                (tri[0][1] + tri[1][1] + tri[2][1]) * (1.0 / 3.0),
1148            );
1149            emit::<STATES>(
1150                result,
1151                index * 4 + child,
1152                tri,
1153                center,
1154                [edge_samples[e0], edge_samples[e1], edge_samples[e2]],
1155                edgeres,
1156            );
1157        }
1158        return Ok(());
1159    }
1160    for (child, tri) in [
1161        [corners[0], mid[0], mid[2]],
1162        [mid[2], mid[1], mid[0]],
1163        [mid[0], corners[1], mid[1]],
1164        [mid[1], mid[2], corners[2]],
1165    ]
1166    .into_iter()
1167    .enumerate()
1168    {
1169        raster_state_core::<CHARGE_WORK, STATES>(
1170            result,
1171            index * 4 + child,
1172            level - 1,
1173            edgeres,
1174            tri,
1175            texture,
1176            work,
1177        )?;
1178    }
1179    Ok(())
1180}
1181
1182/// The source-compatible u32 entry point; see [`opacity_map_measure_generic`] for selectable index widths.
1183#[inline]
1184#[allow(clippy::too_many_arguments)]
1185pub fn opacity_map_measure(
1186    indices: &[u32],
1187    uvs: &[f32],
1188    vertex_count: usize,
1189    uv_stride: usize,
1190    texture_width: u32,
1191    texture_height: u32,
1192    max_level: u8,
1193    target_edge: f32,
1194    workspace: &mut Workspace,
1195) -> Result<OpacityMapMeasure, Error> {
1196    opacity_map_measure_generic::<u32>(
1197        indices,
1198        uvs,
1199        vertex_count,
1200        uv_stride,
1201        texture_width,
1202        texture_height,
1203        max_level,
1204        target_edge,
1205        workspace,
1206    )
1207}
1208
1209/// The source-compatible u32 entry point; see [`opacity_map_measure_into_generic`] for selectable index widths.
1210#[inline]
1211#[allow(clippy::too_many_arguments)]
1212pub fn opacity_map_measure_into(
1213    levels: &mut [u8],
1214    sources: &mut [u32],
1215    omm_indices: &mut [i32],
1216    indices: &[u32],
1217    uvs: &[f32],
1218    vertex_count: usize,
1219    uv_stride: usize,
1220    texture_width: u32,
1221    texture_height: u32,
1222    max_level: u8,
1223    target_edge: f32,
1224    workspace: &mut Workspace,
1225) -> Result<usize, Error> {
1226    opacity_map_measure_into_generic::<u32>(
1227        levels,
1228        sources,
1229        omm_indices,
1230        indices,
1231        uvs,
1232        vertex_count,
1233        uv_stride,
1234        texture_width,
1235        texture_height,
1236        max_level,
1237        target_edge,
1238        workspace,
1239    )
1240}