856f865cf98d
marquee.rs
//! Marquee shapes built straight into tiles, and the tile-wise combination of two selections
//! (#2888, part of #211).
//!
//! Both produce exactly the bytes the per-pixel versions did (an ellipse written with
//! `Surface::write_pixel`, a combination read and written through whole-canvas `f32` buffers),
//! but work a tile at a time in parallel, keep only the tiles that hold something (as
//! `Surface::prune` would leave them) and share one tile for every fully selected one.
use std::sync::Arc;
use photocraft_color::{PixelFormat, SampleType, read_sample, write_sample};
use photocraft_geom::{Rect, TILE_SIZE, TileCoord};
use photocraft_raster::{Surface, Tile};
use crate::photo_util::par_map;
const TS: usize = TILE_SIZE as usize;
/// The byte a GRAY8 surface stores for `v`.
fn encode8(v: f32) -> u8 {
let mut b = [0u8];
write_sample(&mut b, SampleType::U8, 0, v);
let [b] = b;
b
}
/// The value a GRAY8 surface reads for `b`.
fn decode8(b: u8) -> f32 {
read_sample(&[b], SampleType::U8, 0)
}
/// An ellipse inscribed in a rectangle, tested in `f32` exactly as the Elliptical Marquee
/// always has (so its hard edge keeps the same bytes).
struct Ellipse {
cx: f32,
cy: f32,
rx: f32,
ry: f32,
/// At most 3 px across: the anti-aliased edge keeps its 4×4 sub-samples (#11391 measured
/// only larger ellipses).
small: bool,
/// `1 / rx`, `1 / ry`, `1 / rx²` and `1 / ry²` for [`Ellipse::ramp`].
inv: [f64; 4],
}
/// The widest an ellipse is across and still [`Ellipse::small`].
const SMALL: u32 = 3;
impl Ellipse {
fn new(r: Rect) -> Self {
Self {
cx: (i64::from(r.x0) + i64::from(r.x1)) as f32 / 2.0,
cy: (i64::from(r.y0) + i64::from(r.y1)) as f32 / 2.0,
rx: r.width() as f32 / 2.0,
ry: r.height() as f32 / 2.0,
small: r.width().min(r.height()) <= SMALL,
inv: {
let (rx, ry) = (f64::from(r.width()) / 2.0, f64::from(r.height()) / 2.0);
[1.0 / rx, 1.0 / ry, 1.0 / (rx * rx), 1.0 / (ry * ry)]
},
}
}
/// The anti-aliased edge's coverage of pixel `(x, y)`, as Photoshop draws it (#11391): with
/// `F` the normalised radius at the pixel's centre, `(F - 1) / (|∂F/∂x| + |∂F/∂y|)` is the
/// centre's distance to the edge measured in the pixel's own width across the edge, and the
/// coverage ramps linearly over that width. An axis-aligned edge gets the pixel's exact
/// area; a 45° edge ramps over √2 px. 1 exactly at and around the centre.
#[inline]
fn ramp(&self, x: i32, y: i32) -> f64 {
let [irx, iry, irx2, iry2] = self.inv;
let (dx, dy) = (f64::from(x) + 0.5 - f64::from(self.cx), f64::from(y) + 0.5 - f64::from(self.cy));
let (u, v) = (dx * irx, dy * iry);
let f = (u * u + v * v).sqrt();
// `f · (|∂F/∂x| + |∂F/∂y|)`; 0 only at the centre itself.
let across = dx.abs() * irx2 + dy.abs() * iry2;
if across <= 0.0 {
return 1.0;
}
(0.5 - (f - 1.0) * f / across).clamp(0.0, 1.0)
}
#[inline]
fn inside(&self, x: f32, y: f32) -> bool {
let (dx, dy) = ((x - self.cx) / self.rx, (y - self.cy) / self.ry);
dx * dx + dy * dy <= 1.0
}
/// Whether pixel `(x, y)` is fully selected: its centre is inside (hard edge), its four
/// corners are (a small anti-aliased ellipse), or its [`Ellipse::ramp`] is 1. Along a row
/// the pixels where this holds form one run: each test grows with the distance from the
/// centre; [`row_span`] checks both ends of the run.
#[inline]
fn full(&self, x: i32, y: i32, aa: bool) -> bool {
let (fx, fy) = (x as f32, y as f32);
if !aa {
return self.inside(fx + 0.5, fy + 0.5);
}
if self.small {
return self.inside(fx, fy) && self.inside(fx + 1.0, fy) && self.inside(fx, fy + 1.0) && self.inside(fx + 1.0, fy + 1.0);
}
self.ramp(x, y) >= 1.0
}
/// The byte pixel `(x, y)` stores: `one` when [`Ellipse::full`], 0 outside a hard edge, and
/// otherwise the fraction of its 4×4 sub-samples inside (small) or its [`Ellipse::ramp`].
#[inline]
fn coverage(&self, x: i32, y: i32, aa: bool, enc: &[u8; 17]) -> u8 {
let one = enc[16];
if aa && !self.small {
// One ramp: a full pixel's is 1, which encodes as `one`.
// `encode8`'s rounding, inline: this runs for every edge pixel.
return (self.ramp(x, y) as f32 * 255.0 + 0.5) as u8;
}
if self.full(x, y, aa) {
return one;
}
if !aa {
return 0;
}
let (fx, fy) = (x as f32, y as f32);
let n = (0..16u8).filter(|i| self.inside(fx + ((i % 4) as f32 + 0.5) / 4.0, fy + ((i / 4) as f32 + 0.5) / 4.0)).count();
enc.get(n).copied().unwrap_or(one)
}
}
/// The bytes for 0/16 … 16/16 coverage.
fn sixteenths() -> [u8; 17] {
std::array::from_fn(|n| encode8(n as f32 / 16.0))
}
/// One row of the ellipse: nothing outside `lo..hi`, fully selected in `full_lo..full_hi`, and
/// the edge pixels in between (`lo..full_lo`, `full_hi..hi`) need the exact coverage test.
#[derive(Clone, Copy)]
struct RowSpan {
lo: i32,
full_lo: i32,
full_hi: i32,
hi: i32,
}
/// Bounds row `y` of `e` within `cut.x0..cut.x1` from the exact (f64) ellipse, widened by a
/// margin that covers the f32 tests' rounding. The bounds are then checked with the exact tests
/// (the fully selected run at both ends, nothing just outside); any doubt evaluates the whole row.
fn row_span(e: &Ellipse, y: i32, cut: Rect, aa: bool, enc: &[u8; 17]) -> RowSpan {
let exact = RowSpan { lo: cut.x0, full_lo: cut.x1, full_hi: cut.x1, hi: cut.x1 };
let (cx, cy, rx, ry) = (f64::from(e.cx), f64::from(e.cy), f64::from(e.rx), f64::from(e.ry));
// Every point the tests sample in this row lies in `y..y + 1`.
let (ya, yb) = (f64::from(y), f64::from(y) + 1.0);
let near = if cy < ya { ya - cy } else { (cy - yb).max(0.0) };
let far = (ya - cy).abs().max((yb - cy).abs());
let half = |d: f64| {
let t = 1.0 - (d / ry) * (d / ry);
if t >= 0.0 { rx * t.sqrt() } else { -1.0 }
};
let (outer, inner) = (half(near).max(0.0), half(far));
// Near the top and bottom a rounding error δ in the test moves the edge by up to rx·√δ.
let m = 2.0 + rx * 1e-3;
if !(outer.is_finite() && inner.is_finite() && m.is_finite()) {
return exact;
}
let px = |v: f64| v.clamp(f64::from(cut.x0), f64::from(cut.x1)) as i32;
let lo = px((cx - outer - m).floor());
let hi = px((cx + outer + m).floor() + 1.0);
let (mut full_lo, mut full_hi) = (px((cx - inner + m).ceil()), px((cx + inner - m).floor()));
if inner < 0.0 || full_lo >= full_hi {
(full_lo, full_hi) = (hi, hi);
}
let empty = |x: i32| e.coverage(x, y, aa, enc) == 0;
let ok = (lo <= cut.x0 || empty(lo - 1)) && (hi >= cut.x1 || empty(hi)) && (full_lo >= full_hi || (e.full(full_lo, y, aa) && e.full(full_hi - 1, y, aa)));
if ok { RowSpan { lo, full_lo, full_hi, hi } } else { exact }
}
/// The Elliptical Marquee's shape: the ellipse inscribed in `r`, cut to `clip`, as a GRAY8
/// selection. Anti-aliased edge pixels ramp across the edge as in Photoshop ([`Ellipse::ramp`];
/// an ellipse at most 3 px across keeps the fraction of 4×4 sub-samples inside); without
/// anti-aliasing a pixel is selected when its centre is inside.
pub fn ellipse_surface(r: Rect, clip: Rect, anti_alias: bool) -> Surface {
let mut s = Surface::new(PixelFormat::GRAY8);
let cut = r.intersect(&clip);
if cut.is_empty() {
return s;
}
let e = Ellipse::new(r);
let enc = sixteenths();
let one = encode8(1.0);
let rows = par_map(cut.height() as usize, |i| row_span(&e, cut.y0 + i as i32, cut, anti_alias, &enc));
let span = |y: i32| rows.get(usize::try_from(y - cut.y0).ok()?);
let full = s.solid_tile(&[1.0]);
let blank = s.solid_tile(&[0.0]);
let coords: Vec<TileCoord> = cut.tiles().collect();
let built = par_map(coords.len(), |k| {
let tc = *coords.get(k)?;
let rect = tc.rect();
let tr = rect.intersect(&cut);
if tr == rect && (tr.y0..tr.y1).all(|y| span(y).is_some_and(|s| s.full_lo <= tr.x0 && s.full_hi >= tr.x1)) {
return Some((tc, Arc::clone(&full)));
}
let mut tile: Option<Tile> = None;
for y in tr.y0..tr.y1 {
let Some(sp) = span(y) else { continue };
let row = (y - rect.y0) as usize * TS;
let at = |x: i32| row + (x - rect.x0) as usize;
let (a, b) = (sp.full_lo.max(tr.x0), sp.full_hi.min(tr.x1));
if a < b
&& let Some(d) = tile.get_or_insert_with(|| Tile::clone(&blank)).bytes_mut().get_mut(at(a)..at(b))
{
d.fill(one);
}
for x in (sp.lo.max(tr.x0)..sp.full_lo.min(tr.x1)).chain(sp.full_hi.max(tr.x0)..sp.hi.min(tr.x1)) {
let n = e.coverage(x, y, anti_alias, &enc);
if n > 0
&& let Some(d) = tile.get_or_insert_with(|| Tile::clone(&blank)).bytes_mut().get_mut(at(x))
{
*d = n;
}
}
}
tile.map(|t| (tc, Arc::new(t)))
});
s.put_tiles(built.into_iter().flatten());
s
}
/// `f(a, b)` per pixel over `area` for two selections, as a GRAY8 selection holding nothing
/// outside `area`: the same bytes as reading both over `area`, mapping and writing the result.
/// GRAY8 inputs (every selection) go tile by tile in parallel through a table of all 256×256
/// byte pairs; a tile `f` leaves unchanged stays shared with its input.
pub fn combine_surfaces(a: &Surface, b: &Surface, area: Rect, f: impl Fn(f32, f32) -> f32) -> Surface {
let mut out = Surface::new(PixelFormat::GRAY8);
if area.is_empty() {
return out;
}
if a.format() != PixelFormat::GRAY8 || b.format() != PixelFormat::GRAY8 {
let (ra, rb) = (a.read_region(area), b.read_region(area));
let data: Vec<f32> = ra.iter().zip(&rb).map(|(x, y)| f(*x, *y)).collect();
if data.len() == area.width() as usize * area.height() as usize {
out.write_region(area, &data);
out.prune();
}
return out;
}
let lut: Vec<u8> = (0..=u16::MAX).map(|i| encode8(f(decode8((i >> 8) as u8), decode8(i as u8)))).collect();
let pair = |x: u8, y: u8| lut.get(usize::from(x) << 8 | usize::from(y)).copied().unwrap_or(0);
let (da, db) = (a.default_bytes().first().copied().unwrap_or(0), b.default_bytes().first().copied().unwrap_or(0));
// Whether `f` passes one side through where the other side has no tile (e.g. Add, Subtract).
let keeps_a = (0..=255u8).all(|v| pair(v, db) == v);
let keeps_b = (0..=255u8).all(|v| pair(da, v) == v);
let (full, blank) = (out.solid_tile(&[1.0]), out.solid_tile(&[0.0]));
let (row_a, row_b) = ([da; TS], [db; TS]);
let coords: Vec<TileCoord> = area.tiles().collect();
let built = par_map(coords.len(), |k| {
let tc = *coords.get(k)?;
let rect = tc.rect();
let tr = rect.intersect(&area);
let (ta, tb) = (a.tile(tc), b.tile(tc));
if tr == rect {
let pass = match (ta, tb) {
(Some(t), None) if keeps_a => Some(t),
(None, Some(t)) if keeps_b => Some(t),
(None, None) if pair(da, db) == 0 => return None,
_ => None,
};
if let Some(t) = pass {
return t.bytes().iter().any(|v| *v != 0).then(|| (tc, Arc::clone(t)));
}
}
let mut tile = Tile::clone(&blank);
let mut data = tile.bytes_mut();
let same_tile = ta.zip(tb).is_some_and(|(left, right)| Arc::ptr_eq(left, right));
let read_a = ta.map(|tile| tile.bytes());
let read_b = tb.filter(|_| !same_tile).map(|tile| tile.bytes());
let bytes_a = read_a.as_deref();
let bytes_b = if same_tile { bytes_a } else { read_b.as_deref() };
let (mut lo, mut hi) = (if tr == rect { u8::MAX } else { 0 }, 0u8);
let (x0, x1) = ((tr.x0 - rect.x0) as usize, (tr.x1 - rect.x0) as usize);
for ly in (tr.y0 - rect.y0) as usize..(tr.y1 - rect.y0) as usize {
let (s, e) = (ly * TS + x0, ly * TS + x1);
let src_a = bytes_a.and_then(|bytes| bytes.get(s..e)).unwrap_or(&row_a[..x1 - x0]);
let src_b = bytes_b.and_then(|bytes| bytes.get(s..e)).unwrap_or(&row_b[..x1 - x0]);
let Some(dst) = data.get_mut(s..e) else { continue };
for (d, (x, y)) in dst.iter_mut().zip(src_a.iter().zip(src_b)) {
*d = pair(*x, *y);
(lo, hi) = (lo.min(*d), hi.max(*d));
}
}
drop(data);
(hi > 0).then(|| (tc, if lo == u8::MAX { Arc::clone(&full) } else { Arc::new(tile) }))
});
out.put_tiles(built.into_iter().flatten());
out
}
/// [`combine_surfaces`] for an `f` that keeps `a` wherever `b` reads 0 (Add, Subtract), visiting
/// only `b`'s tiles within `area`: the rest of `a` (its other tiles and its untouched value) is
/// kept as it is, so painting a thin stroke across a huge canvas costs the tiles it paints, not
/// the canvas (#8783). Falls back to [`combine_surfaces`] over `area` for other inputs.
pub fn combine_sparse(a: &Surface, b: &Surface, area: Rect, f: impl Fn(f32, f32) -> f32) -> Surface {
let gray = PixelFormat::GRAY8;
let lut: Vec<u8> = (0..=u16::MAX).map(|i| encode8(f(decode8((i >> 8) as u8), decode8(i as u8)))).collect();
let pair = |x: u8, y: u8| lut.get(usize::from(x) << 8 | usize::from(y)).copied().unwrap_or(0);
if a.format() != gray || b.format() != gray || b.default_bytes() != [0] || !(0..=255u8).all(|v| pair(v, 0) == v) {
return combine_surfaces(a, b, area, f);
}
let da = a.default_bytes().first().copied().unwrap_or(0);
let mut out = a.clone();
let (full, untouched) = (out.solid_tile(&[1.0]), out.solid_tile(&[decode8(da)]));
let coords: Vec<TileCoord> = b.tiles().map(|(c, _)| *c).filter(|c| !c.rect().intersect(&area).is_empty()).collect();
// Each tile: `Some(tile)` to store, `None` when it reads as `a`'s untouched value.
let built = par_map(coords.len(), |k| {
let tc = *coords.get(k)?;
let rect = tc.rect();
let tr = rect.intersect(&area);
let tb = b.tile(tc)?;
let mut tile = Tile::clone(a.tile(tc).unwrap_or(&untouched));
let mut data = tile.bytes_mut();
let source = tb.bytes();
let (x0, x1) = ((tr.x0 - rect.x0) as usize, (tr.x1 - rect.x0) as usize);
for ly in (tr.y0 - rect.y0) as usize..(tr.y1 - rect.y0) as usize {
let (s, e) = (ly * TS + x0, ly * TS + x1);
let (Some(dst), Some(src)) = (data.get_mut(s..e), source.get(s..e)) else { continue };
for (d, y) in dst.iter_mut().zip(src) {
*d = pair(*d, *y);
}
}
drop((data, source));
let (lo, hi) = tile.bytes().iter().fold((u8::MAX, 0u8), |(lo, hi), v| (lo.min(*v), hi.max(*v)));
Some((
tc,
if lo == da && hi == da {
None
} else if lo == u8::MAX {
Some(Arc::clone(&full))
} else {
Some(Arc::new(tile))
},
))
});
for (tc, tile) in built.into_iter().flatten() {
match tile {
Some(t) => out.put_tiles([(tc, t)]),
// `take_tiles` only allocates for a tile that is missing; this one is there.
None if out.tile(tc).is_some() => drop(out.take_tiles(tc.rect())),
None => {}
}
}
out
}
#[cfg(test)]
mod tests {
use super::*;
/// The Elliptical Marquee one pixel at a time: every pixel tested and written on its own (the
/// anti-aliased ramp through [`Ellipse::ramp`]).
fn old_ellipse(r: Rect, area: Rect, aa: bool) -> Surface {
let cut = r.intersect(&area);
let mut shape = Surface::new(PixelFormat::GRAY8);
let (cx, cy) = ((r.x0 + r.x1) as f32 / 2.0, (r.y0 + r.y1) as f32 / 2.0);
let (rx, ry) = (r.width() as f32 / 2.0, r.height() as f32 / 2.0);
let inside = |x: f32, y: f32| {
let (dx, dy) = ((x - cx) / rx, (y - cy) / ry);
dx * dx + dy * dy <= 1.0
};
for y in cut.y0..cut.y1 {
for x in cut.x0..cut.x1 {
let (fx, fy) = (x as f32, y as f32);
let corners = [(fx, fy), (fx + 1.0, fy), (fx, fy + 1.0), (fx + 1.0, fy + 1.0)].iter().filter(|(a, b)| inside(*a, *b)).count();
let cov = if !aa {
if inside(fx + 0.5, fy + 0.5) { 1.0 } else { 0.0 }
} else if r.width().min(r.height()) > SMALL {
Ellipse::new(r).ramp(x, y) as f32
} else if corners == 4 {
1.0
} else {
let n = (0..16).filter(|i| inside(fx + ((i % 4) as f32 + 0.5) / 4.0, fy + ((i / 4) as f32 + 0.5) / 4.0)).count();
n as f32 / 16.0
};
if cov > 0.0 {
shape.write_pixel(x, y, &[cov]);
}
}
}
shape
}
/// Combining two selections as it was: whole-area `f32` buffers.
fn old_combine(a: &Surface, b: &Surface, area: Rect, f: impl Fn(f32, f32) -> f32) -> Surface {
let (ra, rb) = (a.read_region(area), b.read_region(area));
let data: Vec<f32> = ra.iter().zip(&rb).map(|(x, y)| f(*x, *y)).collect();
let mut out = Surface::new(PixelFormat::GRAY8);
out.write_region(area, &data);
out.prune();
out
}
#[test]
fn marquee_matches_the_per_pixel_version() {
let area = Rect::new(0, 0, 1100, 700);
let shapes = [
Rect::from_xywh(40, 30, 1000, 620), // whole tiles inside
Rect::from_xywh(3, 5, 1, 1),
Rect::from_xywh(10, 10, 2, 7),
Rect::from_xywh(100, 200, 37, 301),
Rect::from_xywh(255, 255, 258, 2),
Rect::from_xywh(-300, -200, 900, 600), // dragged past the canvas
Rect::from_xywh(-500, -500, 2100, 1700), // larger than the canvas
Rect::from_xywh(1090, 690, 40, 40),
Rect::from_xywh(2000, 0, 50, 50), // entirely outside
];
for r in shapes {
for aa in [true, false] {
let new = ellipse_surface(r, area, aa);
assert!(new == old_ellipse(r, area, aa), "ellipse {r:?} aa={aa}");
}
}
// The other modes, against a rectangle and an anti-aliased ellipse with a partial edge.
let mut rect = Surface::new(PixelFormat::GRAY8);
rect.fill_rect(Rect::from_xywh(200, 100, 600, 520), &[1.0]);
let ell = old_ellipse(Rect::from_xywh(-60, 250, 700, 500), area, true);
let ops: [fn(f32, f32) -> f32; 3] = [|a, b| a.max(b), |a, b| a * (1.0 - b), |a, b| a.min(b)];
for (a, b) in [(&rect, &ell), (&ell, &rect), (&ell, &ell)] {
for f in ops {
assert!(combine_surfaces(a, b, area, f) == old_combine(a, b, area, f));
}
}
}
/// Add and Subtract through only the new shape's tiles give the bytes of the whole-area
/// combination, keep the old selection's other tiles shared, and keep an untouched value
/// (a layer mask's reveal-all) outside them.
#[test]
fn sparse_combination_matches_the_whole_area_one() {
let area = Rect::new(0, 0, 1100, 700);
let mut rect = Surface::new(PixelFormat::GRAY8);
rect.fill_rect(Rect::from_xywh(200, 100, 600, 520), &[1.0]);
let ell = old_ellipse(Rect::from_xywh(-60, 250, 700, 500), area, true);
let far = ellipse_surface(Rect::from_xywh(900, 20, 150, 150), area, true);
let ops: [fn(f32, f32) -> f32; 2] = [|a, b| a.max(b), |a, b| (a - b).max(0.0)];
for (a, b) in [(&rect, &ell), (&ell, &rect), (&ell, &ell), (&rect, &far)] {
for f in ops {
let sparse = combine_sparse(a, b, area, f);
assert!(sparse.read_region(area) == old_combine(a, b, area, f).read_region(area));
assert!(sparse.tiles().all(|(_, t)| t.bytes().iter().any(|v| *v != 0)), "no empty tiles kept");
}
}
let kept = combine_sparse(&rect, &far, area, |a, b| a.max(b));
let tc = TileCoord::new(1, 1);
assert!(Arc::ptr_eq(kept.tile(tc).expect("kept"), rect.tile(tc).expect("there")), "untouched tiles stay shared");
let reveal = Surface::with_default(PixelFormat::GRAY8, &[1.0]);
let cut = combine_sparse(&reveal, &far, area, |a, b| (a - b).max(0.0));
assert!(cut.pixel(5000, 5000)[0] == 1.0 && cut.pixel(975, 95)[0] == 0.0);
}
}
No file is open. Choose one in the tree, or press Ctrl+O (⌘O on a Mac) to find one by name.
Syntax highlighting could not load. The unmodified read-only text remains available above.