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)]
348pub fn opacity_map_measure(
349    indices: &[u32],
350    uvs: &[f32],
351    vertex_count: usize,
352    uv_stride: usize,
353    texture_width: u32,
354    texture_height: u32,
355    max_level: u8,
356    target_edge: f32,
357    workspace: &mut Workspace,
358) -> Result<OpacityMapMeasure, Error> {
359    let mut work = workspace.begin();
360    let result = (|| {
361        if !indices.len().is_multiple_of(3) {
362            return Err(Error::InvalidTopology);
363        }
364        if !(2..=64).contains(&uv_stride)
365            || texture_width == 0
366            || texture_width > 16384
367            || texture_height == 0
368            || texture_height > 16384
369            || max_level > 12
370            || !target_edge.is_finite()
371            || target_edge < 0.0
372        {
373            return Err(Error::InvalidParameter);
374        }
375        if vertex_count > u32::MAX as usize || indices.len() / 3 > i32::MAX as usize {
376            return Err(Error::SizeOverflow);
377        }
378        let needed = vertex_count
379            .checked_sub(1)
380            .and_then(|v| v.checked_mul(uv_stride))
381            .and_then(|v| v.checked_add(2))
382            .unwrap_or(0);
383        if uvs.len() < needed {
384            return Err(Error::InvalidLayout);
385        }
386        work.indices(indices, vertex_count)?;
387        let count = indices.len() / 3;
388        let buckets = table_size(count)?;
389        let bytes = count
390            .checked_mul(3 * 4 + 6 * 4 + 4 + 4)
391            .and_then(|n| n.checked_add(buckets * 4))
392            .ok_or(Error::SizeOverflow)?;
393        workspace.account_codec(bytes)?;
394        let mut table = reserve::<u32>(buckets)?;
395        table.resize(buckets, u32::MAX);
396        let mut keys = reserve::<([i32; 6], u8)>(count)?;
397        let mut levels = reserve::<u8>(count)?;
398        let mut sources = reserve::<u32>(count)?;
399        let mut omm_indices = reserve::<i32>(count)?;
400        if uv_stride == 2 {
401            measure_ranges(
402                indices,
403                uvs.as_chunks::<2>().0,
404                texture_width,
405                texture_height,
406                max_level,
407                target_edge,
408                &mut table,
409                &mut keys,
410                &mut levels,
411                &mut sources,
412                &mut omm_indices,
413                &mut work,
414            )?;
415        } else {
416            measure_ranges(
417                indices,
418                InterleavedUvs {
419                    data: uvs,
420                    stride: uv_stride,
421                },
422                texture_width,
423                texture_height,
424                max_level,
425                target_edge,
426                &mut table,
427                &mut keys,
428                &mut levels,
429                &mut sources,
430                &mut omm_indices,
431                &mut work,
432            )?;
433        }
434        Ok(OpacityMapMeasure {
435            levels,
436            sources,
437            omm_indices,
438        })
439    })();
440    workspace.finish(&work);
441    result
442}
443
444/// Caller-buffer form of `meshopt_opacityMapMeasure`; returns unique entry count.
445/// The three destinations are unchanged when validation fails.
446///
447/// # Errors
448/// Same errors as [`opacity_map_measure`]. `BufferTooSmall` if an output buffer is too short.
449#[allow(clippy::too_many_arguments)]
450pub fn opacity_map_measure_into(
451    levels: &mut [u8],
452    sources: &mut [u32],
453    omm_indices: &mut [i32],
454    indices: &[u32],
455    uvs: &[f32],
456    vertex_count: usize,
457    uv_stride: usize,
458    texture_width: u32,
459    texture_height: u32,
460    max_level: u8,
461    target_edge: f32,
462    workspace: &mut Workspace,
463) -> Result<usize, Error> {
464    let triangles = indices.len() / 3;
465    if levels.len() < triangles || sources.len() < triangles || omm_indices.len() < triangles {
466        return Err(Error::BufferTooSmall);
467    }
468    let result = opacity_map_measure(
469        indices,
470        uvs,
471        vertex_count,
472        uv_stride,
473        texture_width,
474        texture_height,
475        max_level,
476        target_edge,
477        workspace,
478    )?;
479    let count = result.levels.len();
480    levels[..count].copy_from_slice(&result.levels);
481    sources[..count].copy_from_slice(&result.sources);
482    omm_indices[..triangles].copy_from_slice(&result.omm_indices);
483    Ok(count)
484}
485
486fn special_index(data: &[u8], level: u8, states: u8) -> i32 {
487    let first = i32::from(data[0] & if states == 2 { 1 } else { 3 });
488    let special = -(1 + first);
489    if level == 0 {
490        return special;
491    }
492    if level == 1 && states == 2 {
493        return if i32::from(data[0] & 15) == ((-first) & 15) {
494            special
495        } else {
496            0
497        };
498    }
499    let expected = first * if states == 2 { 0xff } else { 0x55 };
500    if data.iter().all(|&v| i32::from(v) == expected) {
501        special
502    } else {
503        0
504    }
505}
506
507/// Compact OMM data in place, as upstream `meshopt_opacityMapCompact` does.
508///
509/// Returns the remaining entry count and used byte count. Callers may trim the
510/// arrays to those lengths. Existing negative triangle references are retained.
511///
512/// # Errors
513/// `InvalidParameter` for unsupported states/levels; `InvalidLayout` for mismatched or out-of-range entries;
514/// `IndexOutOfBounds` for invalid opacity references; `BufferTooSmall` if compacted data exceeds capacity; `SizeOverflow` for size overflow, `LimitExceeded` for exhausted limits, or `AllocationFailed` for failed reservation.
515pub fn opacity_map_compact(
516    data: &mut [u8],
517    levels: &mut [u8],
518    offsets: &mut [u32],
519    omm_indices: &mut [i32],
520    states: u8,
521    workspace: &mut Workspace,
522) -> Result<(usize, usize), Error> {
523    let mut work = workspace.begin();
524    let result = (|| {
525        if states != 2 && states != 4 {
526            return Err(Error::InvalidParameter);
527        }
528        if levels.len() != offsets.len() || levels.len() > i32::MAX as usize {
529            return Err(Error::InvalidLayout);
530        }
531        let count = levels.len();
532        let buckets = table_size(count)?;
533        for (&level, &offset) in levels.iter().zip(offsets.iter()) {
534            work.add(1)?;
535            let size = opacity_map_entry_size(level, states)?;
536            let end = (offset as usize)
537                .checked_add(size)
538                .ok_or(Error::SizeOverflow)?;
539            if end > data.len() {
540                return Err(Error::InvalidLayout);
541            }
542        }
543        for &index in omm_indices.iter() {
544            work.add(1)?;
545            if index >= count as i32 {
546                return Err(Error::IndexOutOfBounds);
547            }
548        }
549        let bytes = data
550            .len()
551            .checked_add(buckets * 4)
552            .and_then(|n| n.checked_add(count * 4))
553            .ok_or(Error::SizeOverflow)?;
554        workspace.account_codec(bytes)?;
555        // Small calls need no heap scratch. Keep the same logical byte budget
556        // and retain independent heap fallbacks for larger inputs.
557        let mut old_inline = [0u8; 64];
558        let mut old_heap;
559        let old = if data.len() <= old_inline.len() {
560            old_inline[..data.len()].copy_from_slice(data);
561            &old_inline[..data.len()]
562        } else {
563            old_heap = reserve::<u8>(data.len())?;
564            old_heap.extend_from_slice(data);
565            &old_heap[..]
566        };
567        let mut table_inline = [u32::MAX; 16];
568        let mut table_heap;
569        let table = if buckets <= table_inline.len() {
570            &mut table_inline[..buckets]
571        } else {
572            table_heap = reserve::<u32>(buckets)?;
573            table_heap.resize(buckets, u32::MAX);
574            &mut table_heap[..]
575        };
576        let mut remap_inline = [0i32; 8];
577        let mut remap_heap;
578        let remap = if count <= remap_inline.len() {
579            &mut remap_inline[..count]
580        } else {
581            remap_heap = reserve::<i32>(count)?;
582            remap_heap.resize(count, 0);
583            &mut remap_heap[..]
584        };
585        let (mut next, mut output_offset) = (0usize, 0usize);
586        for i in 0..count {
587            work.add(1)?;
588            let level = levels[i];
589            let size = opacity_map_entry_size(level, states)?;
590            let source = &old[offsets[i] as usize..offsets[i] as usize + size];
591            let special = special_index(source, level, states);
592            if special < 0 {
593                remap[i] = special;
594                continue;
595            }
596            if output_offset.checked_add(size).ok_or(Error::SizeOverflow)? > data.len() {
597                return Err(Error::BufferTooSmall);
598            }
599            data[output_offset..output_offset + size].copy_from_slice(source);
600            offsets[next] = output_offset as u32;
601            levels[next] = level;
602            let candidate = next as u32;
603            let mut bucket =
604                hash_bytes(u32::from(level), &data[output_offset..output_offset + size]) as usize
605                    & (buckets - 1);
606            let mut found = None;
607            for probe in 0..buckets {
608                work.add(1)?;
609                let entry = table[bucket];
610                if entry == u32::MAX {
611                    table[bucket] = candidate;
612                    break;
613                }
614                let other = offsets[entry as usize] as usize;
615                if levels[entry as usize] == level
616                    && data[other..other + size] == data[output_offset..output_offset + size]
617                {
618                    found = Some(entry);
619                    break;
620                }
621                bucket = (bucket + probe + 1) & (buckets - 1);
622            }
623            if let Some(existing) = found {
624                remap[i] = existing as i32;
625            } else {
626                remap[i] = candidate as i32;
627                next += 1;
628                output_offset += size;
629            }
630        }
631        for index in omm_indices.iter_mut() {
632            if *index >= 0 {
633                *index = remap[*index as usize];
634            }
635        }
636        Ok((next, output_offset))
637    })();
638    workspace.finish(&work);
639    result
640}
641
642#[inline(always)]
643fn sample(
644    data: &[u8],
645    stride: usize,
646    pitch: usize,
647    width: u32,
648    height: u32,
649    u: f32,
650    v: f32,
651) -> f32 {
652    let u = if (u - 0.5).abs() > 0.5 {
653        u - floor(u)
654    } else {
655        u
656    };
657    let v = if (v - 0.5).abs() > 0.5 {
658        v - floor(v)
659    } else {
660        v
661    };
662    let uf = ((u * (width as f32 * 256.0) - 127.5) as i32).max(0);
663    let vf = ((v * (height as f32 * 256.0) - 127.5) as i32).max(0);
664    let (x, y, rx, ry) = (uf >> 8, vf >> 8, uf & 255, vf & 255);
665    if x as u32 >= width || y as u32 >= height {
666        return 0.0;
667    }
668    let offset = y as usize * pitch + x as usize * stride;
669    let ox = if x as u32 + 1 < width { stride } else { 0 };
670    let oy = if y as u32 + 1 < height { pitch } else { 0 };
671    let (a00, a10, a01, a11) = (
672        data[offset] as i32,
673        data[offset + ox] as i32,
674        data[offset + oy] as i32,
675        data[offset + ox + oy] as i32,
676    );
677    let ax0 = a00 * 256 + (a10 - a00) * rx;
678    let ax1 = a01 * 256 + (a11 - a01) * rx;
679    let axy = ax0 * 256 + (ax1 - ax0) * ry;
680    axy as f32 * (1.0 / (255.0 * 65536.0))
681}
682
683#[inline(always)]
684fn edge(texture: &Texture<'_>, a: [f32; 3], b: [f32; 3], resolution: i32) -> i32 {
685    let step = 1.0 / (resolution + 1) as f32;
686    let (du, dv) = ((b[0] - a[0]) * step, (b[1] - a[1]) * step);
687    let (mut u, mut v) = (a[0], a[1]);
688    let (mut mask, mut count) = (0, 0);
689    for i in 0..resolution {
690        u += du;
691        v += dv;
692        let alpha = texture.sample(u, v);
693        mask |= i32::from(alpha >= 0.5) << i;
694        count += i32::from(alpha >= 0.5);
695    }
696    mask | (count << 16)
697}
698
699struct Texture<'a> {
700    data: &'a [u8],
701    stride: usize,
702    pitch: usize,
703    width: u32,
704    height: u32,
705}
706impl Texture<'_> {
707    #[inline(always)]
708    fn sample(&self, u: f32, v: f32) -> f32 {
709        sample(
710            self.data,
711            self.stride,
712            self.pitch,
713            self.width,
714            self.height,
715            u,
716            v,
717        )
718    }
719}
720
721fn emit<const STATES: u8>(
722    result: &mut [u8],
723    index: usize,
724    points: [[f32; 3]; 3],
725    center: f32,
726    edges: [i32; 3],
727    edgeres: i32,
728) {
729    let (a0, a1, a2) = (points[0][2], points[1][2], points[2][2]);
730    let mut coverage = (a0 + a1 + a2) * 0.12 + center * 0.64;
731    if edgeres != 0 {
732        coverage = center * 0.22
733            + ((edges[0] >> 16) + (edges[1] >> 16) + (edges[2] >> 16)) as f32
734                * (1.0 / edgeres as f32)
735                * 0.23
736            + (a0 + a1 + a2) * 0.03;
737    }
738    if STATES == 2 {
739        result[index / 8] |= u8::from(coverage >= 0.5) << (index % 8);
740        return;
741    }
742    let transparent = a0 < 0.5 && a1 < 0.5 && a2 < 0.5 && center < 0.5;
743    let opaque = a0 > 0.5 && a1 > 0.5 && a2 > 0.5 && center > 0.5;
744    let unknown = 2 + i32::from(coverage >= 0.5);
745    let mut state = if transparent || opaque {
746        i32::from(opaque)
747    } else {
748        unknown
749    };
750    if edgeres != 0 && (transparent || opaque) {
751        let expected = if opaque { (1 << edgeres) - 1 } else { 0 };
752        if edges.iter().any(|e| (e & 0xffff) != expected) {
753            state = unknown;
754        }
755    }
756    result[index / 4] |= (state as u8) << ((index % 4) * 2);
757}
758
759#[inline(always)]
760#[allow(clippy::too_many_arguments)]
761fn raster_setup<'a>(
762    level: u8,
763    uvs: [[f32; 2]; 3],
764    texture_data: &'a [u8],
765    texture_stride: usize,
766    texture_pitch: usize,
767    texture_width: u32,
768    texture_height: u32,
769) -> Result<(Texture<'a>, i32, [[f32; 3]; 3]), Error> {
770    if texture_width == 0
771        || texture_width > 16384
772        || texture_height == 0
773        || texture_height > 16384
774        || !(1..=4).contains(&texture_stride)
775        || texture_pitch < texture_stride * texture_width as usize
776        || uvs.iter().flatten().any(|v| !v.is_finite())
777    {
778        return Err(Error::InvalidParameter);
779    }
780    let required = (texture_height as usize - 1)
781        .checked_mul(texture_pitch)
782        .and_then(|n| n.checked_add((texture_width as usize - 1) * texture_stride))
783        .and_then(|n| n.checked_add(1))
784        .ok_or(Error::SizeOverflow)?;
785    if texture_data.len() < required {
786        return Err(Error::InvalidLayout);
787    }
788    let texture = Texture {
789        data: texture_data,
790        stride: texture_stride,
791        pitch: texture_pitch,
792        width: texture_width,
793        height: texture_height,
794    };
795    let area = texture_width as f32 * texture_height as f32;
796    let uvarea = ((uvs[1][0] - uvs[0][0]) * (uvs[2][1] - uvs[0][1])
797        - (uvs[2][0] - uvs[0][0]) * (uvs[1][1] - uvs[0][1]))
798        .abs()
799        * 0.5
800        * area;
801    let uvedge = square_root(uvarea) / (1u32 << level) as f32;
802    let edgeres = ((uvedge * 0.75) as i32).clamp(0, 7);
803    let corners = [
804        [uvs[0][0], uvs[0][1], texture.sample(uvs[0][0], uvs[0][1])],
805        [uvs[1][0], uvs[1][1], texture.sample(uvs[1][0], uvs[1][1])],
806        [uvs[2][0], uvs[2][1], texture.sample(uvs[2][0], uvs[2][1])],
807    ];
808    Ok((texture, edgeres, corners))
809}
810
811fn raster_visits(level: u8) -> usize {
812    // Each level has four children. The level-one edge-specialized path
813    // charges the same four children without recursing.
814    ((1usize << ((usize::from(level) + 1) * 2)) - 1) / 3
815}
816
817/// Rasterize one upstream opacity entry using an alpha-channel byte view.
818///
819/// # Errors
820/// `InvalidParameter` for unsupported settings; `InvalidLayout` for an invalid texture view;
821/// `SizeOverflow` for size overflow, `LimitExceeded` for exhausted limits, or `AllocationFailed` for failed reservation.
822#[allow(clippy::too_many_arguments)]
823#[inline(always)]
824pub fn opacity_map_rasterize(
825    level: u8,
826    states: u8,
827    uvs: [[f32; 2]; 3],
828    texture_data: &[u8],
829    texture_stride: usize,
830    texture_pitch: usize,
831    texture_width: u32,
832    texture_height: u32,
833    workspace: &mut Workspace,
834) -> Result<Vec<u8>, Error> {
835    let mut work = workspace.begin();
836    let result = rasterize_impl(
837        level,
838        states,
839        uvs,
840        texture_data,
841        texture_stride,
842        texture_pitch,
843        texture_width,
844        texture_height,
845        workspace,
846        &mut work,
847    );
848    workspace.finish(&work);
849    result
850}
851
852#[inline(always)]
853#[allow(clippy::too_many_arguments)]
854fn rasterize_impl(
855    level: u8,
856    states: u8,
857    uvs: [[f32; 2]; 3],
858    texture_data: &[u8],
859    texture_stride: usize,
860    texture_pitch: usize,
861    texture_width: u32,
862    texture_height: u32,
863    workspace: &mut Workspace,
864    work: &mut crate::workspace::Work,
865) -> Result<Vec<u8>, Error> {
866    let size = opacity_map_entry_size(level, states)?;
867    let (texture, edgeres, corners) = raster_setup(
868        level,
869        uvs,
870        texture_data,
871        texture_stride,
872        texture_pitch,
873        texture_width,
874        texture_height,
875    )?;
876    workspace.account_codec(size)?;
877    let mut result = reserve::<u8>(size)?;
878    result.resize(size, 0);
879    // The state format is passed explicitly through the recursive path.
880    raster_state(
881        &mut result,
882        0,
883        level,
884        states,
885        edgeres,
886        corners,
887        &texture,
888        work,
889    )?;
890    Ok(result)
891}
892
893/// Caller-buffer form of `meshopt_opacityMapRasterize`.
894/// Returns the number of bytes written and preserves the destination on error.
895///
896/// # Errors
897/// Same errors as [`opacity_map_rasterize`]. `BufferTooSmall` if an output buffer is too short.
898#[allow(clippy::too_many_arguments)]
899#[inline(always)]
900pub fn opacity_map_rasterize_into(
901    destination: &mut [u8],
902    level: u8,
903    states: u8,
904    uvs: [[f32; 2]; 3],
905    texture_data: &[u8],
906    texture_stride: usize,
907    texture_pitch: usize,
908    texture_width: u32,
909    texture_height: u32,
910    workspace: &mut Workspace,
911) -> Result<usize, Error> {
912    let size = opacity_map_entry_size(level, states)?;
913    if destination.len() < size {
914        return Err(Error::BufferTooSmall);
915    }
916    // Preserve the complete destination on a tight work budget by using the
917    // staged path; the default budget covers every recursive visit upfront.
918    if workspace.limits().max_work < raster_visits(level) as u64 {
919        let result = opacity_map_rasterize(
920            level,
921            states,
922            uvs,
923            texture_data,
924            texture_stride,
925            texture_pitch,
926            texture_width,
927            texture_height,
928            workspace,
929        )?;
930        destination[..size].copy_from_slice(&result);
931        return Ok(size);
932    }
933    let mut work = workspace.begin();
934    let result = rasterize_into_impl(
935        destination,
936        level,
937        states,
938        uvs,
939        texture_data,
940        texture_stride,
941        texture_pitch,
942        texture_width,
943        texture_height,
944        workspace,
945        size,
946        &mut work,
947    );
948    workspace.finish(&work);
949    result
950}
951
952#[inline(always)]
953#[allow(clippy::too_many_arguments)]
954fn rasterize_into_impl(
955    destination: &mut [u8],
956    level: u8,
957    states: u8,
958    uvs: [[f32; 2]; 3],
959    texture_data: &[u8],
960    texture_stride: usize,
961    texture_pitch: usize,
962    texture_width: u32,
963    texture_height: u32,
964    workspace: &mut Workspace,
965    size: usize,
966    work: &mut crate::workspace::Work,
967) -> Result<usize, Error> {
968    let (texture, edgeres, corners) = raster_setup(
969        level,
970        uvs,
971        texture_data,
972        texture_stride,
973        texture_pitch,
974        texture_width,
975        texture_height,
976    )?;
977    workspace.account_codec(0)?;
978    let result = &mut destination[..size];
979    result.fill(0);
980    raster_state(result, 0, level, states, edgeres, corners, &texture, work)?;
981    Ok(size)
982}
983
984#[inline(always)]
985fn midpoint(a: [f32; 3], b: [f32; 3], texture: &Texture<'_>) -> [f32; 3] {
986    let u = (a[0] + b[0]) / 2.0;
987    let v = (a[1] + b[1]) / 2.0;
988    [u, v, texture.sample(u, v)]
989}
990
991#[allow(clippy::too_many_arguments)]
992fn raster_state(
993    result: &mut [u8],
994    index: usize,
995    level: u8,
996    states: u8,
997    edgeres: i32,
998    corners: [[f32; 3]; 3],
999    texture: &Texture<'_>,
1000    work: &mut crate::workspace::Work,
1001) -> Result<(), Error> {
1002    let visits = raster_visits(level);
1003    let bulk = work.covers(visits)?;
1004    if bulk {
1005        work.add(visits)?;
1006    }
1007    match (states == 2, bulk) {
1008        (true, true) => {
1009            raster_state_core::<false, 2>(result, index, level, edgeres, corners, texture, work)
1010        }
1011        (false, true) => {
1012            raster_state_core::<false, 4>(result, index, level, edgeres, corners, texture, work)
1013        }
1014        (true, false) => {
1015            raster_state_core::<true, 2>(result, index, level, edgeres, corners, texture, work)
1016        }
1017        (false, false) => {
1018            raster_state_core::<true, 4>(result, index, level, edgeres, corners, texture, work)
1019        }
1020    }
1021}
1022
1023#[allow(clippy::too_many_arguments)]
1024fn raster_state_core<const CHARGE_WORK: bool, const STATES: u8>(
1025    result: &mut [u8],
1026    index: usize,
1027    level: u8,
1028    edgeres: i32,
1029    corners: [[f32; 3]; 3],
1030    texture: &Texture<'_>,
1031    work: &mut crate::workspace::Work,
1032) -> Result<(), Error> {
1033    if CHARGE_WORK {
1034        work.add(1)?;
1035    }
1036    if level == 0 {
1037        let center = texture.sample(
1038            (corners[0][0] + corners[1][0] + corners[2][0]) * (1.0 / 3.0),
1039            (corners[0][1] + corners[1][1] + corners[2][1]) * (1.0 / 3.0),
1040        );
1041        let edges = if edgeres > 0 {
1042            [
1043                edge(texture, corners[0], corners[1], edgeres),
1044                edge(texture, corners[1], corners[2], edgeres),
1045                edge(texture, corners[2], corners[0], edgeres),
1046            ]
1047        } else {
1048            [0; 3]
1049        };
1050        emit::<STATES>(result, index, corners, center, edges, edgeres);
1051        return Ok(());
1052    }
1053    let mid = [
1054        midpoint(corners[0], corners[1], texture),
1055        midpoint(corners[1], corners[2], texture),
1056        midpoint(corners[2], corners[0], texture),
1057    ];
1058    if level == 1 && edgeres > 0 {
1059        let points = [corners[0], mid[0], corners[1], mid[1], corners[2], mid[2]];
1060        let edge_samples = [
1061            edge(texture, points[0], points[1], edgeres),
1062            edge(texture, points[1], points[2], edgeres),
1063            edge(texture, points[2], points[3], edgeres),
1064            edge(texture, points[3], points[4], edgeres),
1065            edge(texture, points[4], points[5], edgeres),
1066            edge(texture, points[5], points[0], edgeres),
1067            edge(texture, points[5], points[1], edgeres),
1068            edge(texture, points[1], points[3], edgeres),
1069            edge(texture, points[3], points[5], edgeres),
1070        ];
1071        let triangles = [
1072            [0, 1, 5, 0, 6, 5],
1073            [5, 3, 1, 8, 7, 6],
1074            [1, 2, 3, 1, 2, 7],
1075            [3, 5, 4, 8, 4, 3],
1076        ];
1077        for (child, [a, b, c, e0, e1, e2]) in triangles.into_iter().enumerate() {
1078            if CHARGE_WORK {
1079                work.add(1)?;
1080            }
1081            let tri = [points[a], points[b], points[c]];
1082            let center = texture.sample(
1083                (tri[0][0] + tri[1][0] + tri[2][0]) * (1.0 / 3.0),
1084                (tri[0][1] + tri[1][1] + tri[2][1]) * (1.0 / 3.0),
1085            );
1086            emit::<STATES>(
1087                result,
1088                index * 4 + child,
1089                tri,
1090                center,
1091                [edge_samples[e0], edge_samples[e1], edge_samples[e2]],
1092                edgeres,
1093            );
1094        }
1095        return Ok(());
1096    }
1097    for (child, tri) in [
1098        [corners[0], mid[0], mid[2]],
1099        [mid[2], mid[1], mid[0]],
1100        [mid[0], corners[1], mid[1]],
1101        [mid[1], mid[2], corners[2]],
1102    ]
1103    .into_iter()
1104    .enumerate()
1105    {
1106        raster_state_core::<CHARGE_WORK, STATES>(
1107            result,
1108            index * 4 + child,
1109            level - 1,
1110            edgeres,
1111            tri,
1112            texture,
1113            work,
1114        )?;
1115    }
1116    Ok(())
1117}