color/
gradient.rs

1// Copyright 2024 the Color Authors
2// SPDX-License-Identifier: Apache-2.0 OR MIT
3
4use crate::{
5    ColorSpace, ColorSpaceTag, DynamicColor, HueDirection, Interpolator, Oklab, PremulColor,
6};
7
8/// The iterator for gradient approximation.
9///
10/// This will yield a value for each gradient stop, including `t` values
11/// of 0 and 1 at the endpoints.
12///
13/// Use the [`gradient`] function to generate this iterator.
14#[expect(missing_debug_implementations, reason = "it's an iterator")]
15pub struct GradientIter<CS: ColorSpace> {
16    interpolator: Interpolator,
17    // This is in deltaEOK units
18    tolerance: f32,
19    // The adaptive subdivision logic is lifted from the stroke expansion paper.
20    t0: u32,
21    dt: f32,
22    target0: PremulColor<CS>,
23    target1: PremulColor<CS>,
24    end_color: PremulColor<CS>,
25}
26
27/// Generate a piecewise linear approximation to a gradient ramp.
28///
29/// The target gradient ramp is the linear interpolation from `color0` to `color1` in the target
30/// color space specified by `interp_cs`. For efficiency, this function returns an
31/// [iterator over color stops](GradientIter) in the `CS` color space, such that the gradient ramp
32/// created by linearly interpolating between those stops in the `CS` color space is equal within
33/// the specified `tolerance` to the target gradient ramp.
34///
35/// When the target interpolation color space is cylindrical, the hue can be interpolated in
36/// multiple ways. The [`direction`](`HueDirection`) parameter controls the way in which the hue is
37/// interpolated.
38///
39/// The given `tolerance` value specifies the maximum perceptual error in the approximation
40/// measured as the [Euclidean distance][euclidean-distance] in the [Oklab] color space (see also
41/// [`PremulColor::difference`][crate::PremulColor::difference]). This metric is known as
42/// [deltaEOK][delta-eok]. A reasonable value is 0.01, which in testing is nearly indistinguishable
43/// from the exact ramp. The number of stops scales roughly as the inverse square root of the
44/// tolerance.
45///
46/// The error is measured at the midpoint of each segment, which in some cases may underestimate
47/// the error.
48///
49/// For regular interpolation between two colors, see [`DynamicColor::interpolate`].
50///
51/// [euclidean-distance]: https://en.wikipedia.org/wiki/Euclidean_distance
52/// [delta-eok]: https://www.w3.org/TR/css-color-4/#color-difference-OK
53///
54/// # Motivation
55///
56/// A major feature of CSS Color 4 is the ability to specify color interpolation in any
57/// interpolation color space [CSS Color Module Level 4 § 12.1][css-sec], which may be quite a bit
58/// better than simple linear interpolation in sRGB (for example).
59///
60/// One strategy for implementing these gradients is to interpolate in the appropriate
61/// (premultiplied) space, then map each resulting color to the space used for compositing. That
62/// can be expensive. An alternative strategy is to precompute a piecewise linear ramp that closely
63/// approximates the desired ramp, then render that using high performance techniques. This method
64/// computes such an approximation.
65///
66/// [css-sec]: https://www.w3.org/TR/css-color-4/#interpolation-space
67///
68/// # Example
69///
70/// The following compares interpolating in the target color space Oklab with interpolating
71/// piecewise in the color space sRGB.
72///
73/// ```rust
74/// use color::{AlphaColor, ColorSpaceTag, DynamicColor, HueDirection, Oklab, Srgb};
75///
76/// let start = DynamicColor::from_alpha_color(AlphaColor::<Srgb>::new([1., 0., 0., 1.]));
77/// let end = DynamicColor::from_alpha_color(AlphaColor::<Srgb>::new([0., 1., 0., 1.]));
78///
79/// // Interpolation in a target interpolation color space.
80/// let interp = start.interpolate(end, ColorSpaceTag::Oklab, HueDirection::default());
81/// // Piecewise-approximated interpolation in a compositing color space.
82/// let mut gradient = color::gradient::<Srgb>(
83///     start,
84///     end,
85///     ColorSpaceTag::Oklab,
86///     HueDirection::default(),
87///     0.01,
88/// );
89///
90/// let (mut t0, mut stop0) = gradient.next().unwrap();
91/// for (t1, stop1) in gradient {
92///     // Compare a few points between the piecewise stops.
93///     for point in [0.0, 0.1, 0.2, 0.3, 0.4, 0.5, 0.6, 0.7, 0.8, 0.9] {
94///         let interpolated_point = interp
95///             .eval(t0 + (t1 - t0) * point)
96///             .to_alpha_color::<Srgb>()
97///             .discard_alpha();
98///         let approximated_point = stop0.lerp_rect(stop1, point).discard_alpha();
99///
100///         // The perceptual deltaEOK between the two is lower than the tolerance.
101///         assert!(
102///             approximated_point
103///                 .convert::<Oklab>()
104///                 .difference(interpolated_point.convert::<Oklab>())
105///                 < 0.01
106///         );
107///     }
108///
109///     t0 = t1;
110///     stop0 = stop1;
111/// }
112/// ```
113pub fn gradient<CS: ColorSpace>(
114    mut color0: DynamicColor,
115    mut color1: DynamicColor,
116    interp_cs: ColorSpaceTag,
117    direction: HueDirection,
118    tolerance: f32,
119) -> GradientIter<CS> {
120    let interpolator = color0.interpolate(color1, interp_cs, direction);
121    if !color0.flags.missing().is_empty() {
122        color0 = interpolator.eval(0.0);
123    }
124    let target0 = color0.to_alpha_color().premultiply();
125    if !color1.flags.missing().is_empty() {
126        color1 = interpolator.eval(1.0);
127    }
128    let target1 = color1.to_alpha_color().premultiply();
129    let end_color = target1;
130    GradientIter {
131        interpolator,
132        tolerance,
133        t0: 0,
134        dt: 0.0,
135        target0,
136        target1,
137        end_color,
138    }
139}
140
141impl<CS: ColorSpace> Iterator for GradientIter<CS> {
142    type Item = (f32, PremulColor<CS>);
143
144    fn next(&mut self) -> Option<Self::Item> {
145        if self.dt == 0.0 {
146            self.dt = 1.0;
147            return Some((0.0, self.target0));
148        }
149        let t0 = self.t0 as f32 * self.dt;
150        if t0 == 1.0 {
151            return None;
152        }
153        loop {
154            // compute midpoint color
155            let midpoint = self.interpolator.eval(t0 + 0.5 * self.dt);
156            let midpoint_oklab: PremulColor<Oklab> = midpoint.to_alpha_color().premultiply();
157            let approx = self.target0.lerp_rect(self.target1, 0.5);
158            let error = midpoint_oklab.difference(approx.convert());
159            if error <= self.tolerance {
160                let t1 = t0 + self.dt;
161                self.t0 += 1;
162                let shift = self.t0.trailing_zeros();
163                self.t0 >>= shift;
164                self.dt *= (1 << shift) as f32;
165                self.target0 = self.target1;
166                let new_t1 = t1 + self.dt;
167                if new_t1 < 1.0 {
168                    self.target1 = self
169                        .interpolator
170                        .eval(new_t1)
171                        .to_alpha_color()
172                        .premultiply();
173                } else {
174                    self.target1 = self.end_color;
175                }
176                return Some((t1, self.target0));
177            }
178            self.t0 *= 2;
179            self.dt *= 0.5;
180            self.target1 = midpoint.to_alpha_color().premultiply();
181        }
182    }
183}
color/gradient.rs

color/
gradient.rs
