vello_common/
util.rs

1// Copyright 2025 the Vello Authors
2// SPDX-License-Identifier: Apache-2.0 OR MIT
3
4//! Utility functions.
5
6use crate::geometry::RectU16;
7use crate::math::{FloatExt, snap_up};
8use crate::strip::{Strip, visit_strip_fill_segments};
9use crate::tile::Tile;
10use alloc::vec::Vec;
11use core::ops::{Index, IndexMut};
12use fearless_simd::{
13    Bytes, Simd, SimdBase, SimdFloat, f32x16, u8x16, u8x32, u16x16, u16x32, u32x16,
14};
15#[cfg(not(feature = "std"))]
16use peniko::kurbo::common::FloatFuncs as _;
17use peniko::kurbo::{Affine, Rect};
18
19/// Convert f32x16 to u8x16.
20///
21/// **Important note: The values need to be between 0.0 and 1.0, otherwise you might
22/// get inconsistent results across different platforms.**
23// We can't guarantee correctness for values < 0.0 due to a restriction in fearless_simd:
24// https://github.com/linebender/fearless_simd/blob/3f4489389940b7c3c6ee1847a2d007a22494eeff/fearless_simd/src/generated/simd_types.rs#L1623
25#[inline(always)]
26pub fn f32_to_u8<S: Simd>(val: f32x16<S>) -> u8x16<S> {
27    let simd = val.simd;
28    let converted = val.to_int::<u32x16<S>>().to_bytes();
29
30    let (x8_1, x8_2) = simd.split_u8x64(converted);
31    let (p1, p2) = simd.split_u8x32(x8_1);
32    let (p3, p4) = simd.split_u8x32(x8_2);
33
34    let uzp1 = simd.unzip_low_u8x16(p1, p2);
35    let uzp2 = simd.unzip_low_u8x16(p3, p4);
36    simd.unzip_low_u8x16(uzp1, uzp2)
37}
38
39/// A trait for implementing a fast approximal division by 255 for integers.
40pub trait Div255Ext {
41    /// Divide by 255.
42    fn div_255(self) -> Self;
43}
44
45impl<S: Simd> Div255Ext for u16x32<S> {
46    #[inline(always)]
47    fn div_255(self) -> Self {
48        let p1 = Self::splat(self.simd, 255);
49        let p2 = self + p1;
50        p2 >> 8
51    }
52}
53
54impl<S: Simd> Div255Ext for u16x16<S> {
55    #[inline(always)]
56    fn div_255(self) -> Self {
57        let p1 = Self::splat(self.simd, 255);
58        let p2 = self + p1;
59        p2 >> 8
60    }
61}
62
63/// Perform a normalized multiplication for u8x32.
64#[inline(always)]
65pub fn normalized_mul_u8x32<S: Simd>(a: u8x32<S>, b: u8x32<S>) -> u16x32<S> {
66    (S::widen_u8x32(a.simd, a) * S::widen_u8x32(b.simd, b)).div_255()
67}
68
69/// Perform a normalized multiplication for u8x16.
70#[inline(always)]
71pub fn normalized_mul_u8x16<S: Simd>(a: u8x16<S>, b: u8x16<S>) -> u16x16<S> {
72    (S::widen_u8x16(a.simd, a) * S::widen_u8x16(b.simd, b)).div_255()
73}
74
75/// Check if an affine transform is a pure integer translation.
76///
77/// Returns true if the transform only contains integer translation (no rotation,
78/// skew, or scaling), meaning rectangles will remain pixel-aligned after transformation.
79#[inline]
80pub fn is_integer_translation(transform: &Affine) -> bool {
81    let [a, b, c, d, e, f] = transform.as_coeffs();
82    (a - 1.0).is_nearly_zero()
83        && b.is_nearly_zero()
84        && c.is_nearly_zero()
85        && (d - 1.0).is_nearly_zero()
86        && (e - e.round()).is_nearly_zero()
87        && (f - f.round()).is_nearly_zero()
88}
89/// Check if an affine transform has no skewing (i.e. preserves axis alignment).
90#[inline]
91pub fn is_axis_aligned(transform: &Affine) -> bool {
92    let [_, b, c, ..] = transform.as_coeffs();
93    b.is_nearly_zero() && c.is_nearly_zero()
94}
95
96/// Extract scale factors from an affine transform using singular value decomposition.
97///
98/// Returns a tuple of (`scale_x`, `scale_y`) representing the scale along each axis.
99/// This uses the same algorithm as kurbo's internal `svd()` method.
100///
101/// # Arguments
102/// * `transform` - The affine transformation to extract scales from.
103///
104/// # Returns
105/// A tuple `(scale_x, scale_y)` with minimum values clamped to 1e-6 to avoid division by zero.
106///
107/// # Note
108/// TODO: Consider making `Affine::svd()` public in kurbo to avoid duplicating this code.
109/// This implementation mirrors kurbo's internal SVD calculation for extracting scale factors
110/// from arbitrary affine transformations.
111#[inline]
112pub fn extract_scales(transform: &Affine) -> (f32, f32) {
113    let [a, b, c, d, _, _] = transform.as_coeffs();
114    let a = a as f32;
115    let b = b as f32;
116    let c = c as f32;
117    let d = d as f32;
118
119    // Compute singular values using the same formula as kurbo's svd()
120    let a2 = a * a;
121    let b2 = b * b;
122    let c2 = c * c;
123    let d2 = d * d;
124    let s1 = a2 + b2 + c2 + d2;
125    let s2 = ((a2 - b2 + c2 - d2).powi(2) + 4.0 * (a * b + c * d).powi(2)).sqrt();
126
127    let scale_x = (0.5 * (s1 + s2)).sqrt();
128    let scale_y = (0.5 * (s1 - s2)).sqrt();
129
130    (scale_x.max(1e-6), scale_y.max(1e-6))
131}
132
133/// Extension methods for rectangles.
134pub trait RectExt {
135    /// Snap the rect to whole tile coordinates.
136    fn snap_to_tile_coordinates(self) -> Self;
137}
138
139impl RectExt for Rect {
140    #[inline]
141    fn snap_to_tile_coordinates(self) -> Self {
142        let x0 = snap_down(self.x0, Tile::WIDTH);
143        let y0 = snap_down(self.y0, Tile::HEIGHT);
144
145        if self.is_zero_area() {
146            return Self::new(x0, y0, x0, y0);
147        }
148
149        Self::new(
150            x0,
151            y0,
152            snap_up(self.x1, Tile::WIDTH),
153            snap_up(self.y1, Tile::HEIGHT),
154        )
155    }
156}
157
158impl RectExt for RectU16 {
159    #[inline]
160    fn snap_to_tile_coordinates(self) -> Self {
161        // This method will panic if we have a viewport of size u16::MAX and draw
162        // at the very edge, but better than returning a wrong result.
163
164        let x0 = (self.x0 / Tile::WIDTH).checked_mul(Tile::WIDTH).unwrap();
165        let y0 = (self.y0 / Tile::HEIGHT).checked_mul(Tile::HEIGHT).unwrap();
166
167        if self.is_empty() {
168            return Self::new(x0, y0, x0, y0);
169        }
170
171        Self::new(
172            x0,
173            y0,
174            self.x1.checked_next_multiple_of(Tile::WIDTH).unwrap(),
175            self.y1.checked_next_multiple_of(Tile::HEIGHT).unwrap(),
176        )
177    }
178}
179
180#[inline]
181fn snap_down(value: f64, step: u16) -> f64 {
182    let step = f64::from(step);
183    (value / step).floor() * step
184}
185
186/// A type that can be cleared.
187pub trait Clear {
188    /// Clear the object to its default state.
189    fn clear(&mut self);
190}
191
192impl<T> Clear for Vec<T> {
193    fn clear(&mut self) {
194        Self::clear(self);
195    }
196}
197
198/// Pool for reusing allocations.
199#[derive(Debug)]
200pub struct Pool<T> {
201    entries: Vec<T>,
202    clear_on_submit: bool,
203}
204
205impl<T> Default for Pool<T> {
206    fn default() -> Self {
207        Self::new(true)
208    }
209}
210
211impl<T> Pool<T> {
212    /// Create a new pool.
213    ///
214    /// `clear_on_submit` decides whether submitted values should
215    /// be cleared when they are submitted or whether they should retain
216    /// their original contents.
217    pub fn new(clear_on_submit: bool) -> Self {
218        Self {
219            entries: Vec::new(),
220            clear_on_submit,
221        }
222    }
223
224    /// Take an object from the pool or create a new one.
225    pub fn take(&mut self) -> T
226    where
227        T: Default,
228    {
229        self.entries.pop().unwrap_or_default()
230    }
231
232    /// Return an object to the pool.
233    pub fn submit(&mut self, mut entry: T)
234    where
235        T: Clear,
236    {
237        if self.clear_on_submit {
238            entry.clear();
239        }
240
241        self.entries.push(entry);
242    }
243}
244
245/// Pool for reusing vector allocations.
246pub type VecPool<T> = Pool<Vec<T>>;
247
248/// A resizable vector that retains inner elements upon resizing.
249#[derive(Debug)]
250pub struct RetainVec<T> {
251    inner: Vec<T>,
252    len: usize,
253}
254
255impl<T: Clear> RetainVec<T> {
256    /// Create an empty `RetainVec`.
257    pub fn new() -> Self {
258        Self {
259            inner: Vec::new(),
260            len: 0,
261        }
262    }
263
264    /// Create a `RetainVec` with `len` initialized entries.
265    pub fn with_len(len: usize, mut init: impl FnMut() -> T) -> Self {
266        let mut inner = Vec::with_capacity(len);
267        inner.resize_with(len, &mut init);
268        Self { inner, len }
269    }
270
271    /// Return the length.
272    pub fn len(&self) -> usize {
273        self.len
274    }
275
276    /// Return `true` if the vector is empty.
277    pub fn is_empty(&self) -> bool {
278        self.len == 0
279    }
280
281    /// Return the entries as a slice.
282    pub fn as_slice(&self) -> &[T] {
283        &self.inner[..self.len]
284    }
285
286    /// Return the entries as a mutable slice.
287    pub fn as_mut_slice(&mut self) -> &mut [T] {
288        &mut self.inner[..self.len]
289    }
290
291    /// Iterate mutably over active entries.
292    pub fn iter_mut(&mut self) -> core::slice::IterMut<'_, T> {
293        self.as_mut_slice().iter_mut()
294    }
295
296    /// Clear the elements in this vector.
297    pub fn clear(&mut self) {
298        self.len = 0;
299    }
300
301    /// Resize the vector.
302    pub fn resize_with(&mut self, new_len: usize, mut init: impl FnMut() -> T) {
303        let old_len = self.len;
304        if new_len > self.inner.len() {
305            self.inner.resize_with(new_len, &mut init);
306        }
307        self.len = new_len;
308
309        // Make sure to actually reset the newly added values since they are not reset when shrinking
310        // the vector.
311        if new_len > old_len {
312            for item in &mut self.inner[old_len..new_len] {
313                item.clear();
314            }
315        }
316    }
317}
318
319impl<T: Clear> Default for RetainVec<T> {
320    fn default() -> Self {
321        Self::new()
322    }
323}
324
325impl<T> Index<usize> for RetainVec<T> {
326    type Output = T;
327
328    fn index(&self, index: usize) -> &Self::Output {
329        &self.inner[..self.len][index]
330    }
331}
332
333impl<T> IndexMut<usize> for RetainVec<T> {
334    fn index_mut(&mut self, index: usize) -> &mut Self::Output {
335        &mut self.inner[..self.len][index]
336    }
337}
338
339/// Calculate the bounding box of the strips.
340pub fn strip_bbox(strips: &[Strip]) -> Option<RectU16> {
341    // Fill and alpha fill segments internally store their coordinates in tile units,
342    // in order to avoid multiplications in every invocation of the closure we calculate
343    // the bbox in tile units first and then convert back to pixel units.
344    let mut tile_bbox = RectU16::INVERTED;
345
346    visit_strip_fill_segments(
347        strips,
348        RectU16::new(
349            0,
350            0,
351            u16::MAX.div_ceil(Tile::WIDTH),
352            u16::MAX.div_ceil(Tile::HEIGHT),
353        ),
354        &mut tile_bbox,
355        |bbox, segment| bbox.union(segment.fill.tile_rect()),
356        |bbox, segment| bbox.union(segment.tile_rect()),
357    );
358
359    // Convert to pixel units.
360    if tile_bbox.is_empty() {
361        None
362    } else {
363        Some(RectU16::new(
364            tile_bbox.x0.checked_mul(Tile::WIDTH).unwrap(),
365            tile_bbox.y0.checked_mul(Tile::HEIGHT).unwrap(),
366            tile_bbox.x1.checked_mul(Tile::WIDTH).unwrap(),
367            tile_bbox.y1.checked_mul(Tile::HEIGHT).unwrap(),
368        ))
369    }
370}
371
372#[cfg(test)]
373mod tests {
374    use super::RectU16;
375    use super::{RectExt, strip_bbox};
376    use crate::strip::Strip;
377    use crate::tile::Tile;
378    use peniko::kurbo::Rect;
379
380    fn sentinel(y: u16, alpha_idx: u32) -> Strip {
381        Strip::new(u16::MAX, y, alpha_idx, false)
382    }
383
384    #[test]
385    fn snap_to_tile_coordinates_rounds_outward() {
386        let rect = Rect::new(-4.1, -0.1, 4.1, 8.0).snap_to_tile_coordinates();
387        assert_eq!(rect, Rect::new(-8.0, -4.0, 8.0, 8.0));
388    }
389
390    #[test]
391    fn snap_u16_to_tile_coordinates_rounds_outward() {
392        let rect = RectU16::new(5, 3, 9, 7).snap_to_tile_coordinates();
393        assert_eq!(rect, RectU16::new(4, 0, 12, 8));
394    }
395
396    #[test]
397    fn snap_to_tile_coordinates_preserves_empty_rects() {
398        assert_eq!(
399            Rect::new(5.0, 3.0, 5.0, 7.0).snap_to_tile_coordinates(),
400            Rect::new(4.0, 0.0, 4.0, 0.0)
401        );
402        assert_eq!(
403            RectU16::new(5, 3, 9, 3).snap_to_tile_coordinates(),
404            RectU16::new(4, 0, 4, 0)
405        );
406    }
407
408    #[test]
409    fn empty_strip_bbox() {
410        let strips = [Strip::sentinel(0, 0)];
411
412        assert_eq!(strip_bbox(&strips), None);
413    }
414
415    #[test]
416    fn single_strip_bbox() {
417        let strips = [
418            Strip::new(8, 4, 0, false),
419            sentinel(4, u32::from(Tile::HEIGHT) * 4),
420        ];
421
422        assert_eq!(strip_bbox(&strips), Some(RectU16::new(8, 4, 12, 8)));
423    }
424
425    #[test]
426    fn strip_with_fill_bbox() {
427        let strips = [
428            Strip::new(4, 0, 0, false),
429            Strip::new(20, 0, u32::from(Tile::HEIGHT) * 4, true),
430            sentinel(0, u32::from(Tile::HEIGHT) * 8),
431        ];
432
433        assert_eq!(strip_bbox(&strips), Some(RectU16::new(4, 0, 24, 4)));
434    }
435
436    #[test]
437    fn strip_with_row_end_fill_gap_bbox_is_clamped_to_viewport() {
438        let strips = [
439            Strip::new(4, 0, 0, false),
440            Strip::new(32, 0, u32::from(Tile::HEIGHT) * 4, true),
441            sentinel(0, u32::from(Tile::HEIGHT) * 4),
442        ];
443
444        assert_eq!(strip_bbox(&strips), Some(RectU16::new(4, 0, 32, 4)));
445    }
446
447    #[test]
448    fn strips_with_multiple_rows_bbox() {
449        let strips = [
450            Strip::new(12, 0, 0, false),
451            Strip::new(4, 8, u32::from(Tile::HEIGHT) * 4, false),
452            sentinel(8, u32::from(Tile::HEIGHT) * 8),
453        ];
454
455        assert_eq!(strip_bbox(&strips), Some(RectU16::new(4, 0, 16, 12)));
456    }
457}
vello_common/util.rs

vello_common/
util.rs
