collective
Browse / github.com/storytold/photocraft / patch
Select Inverse: invert shared tiles without full-canvas buffers
Select Inverse: invert shared tiles without full-canvas buffers `Select > Inverse` (`Cmd+Shift+I`) read the whole canvas into a float buffer, inverted every sample, then rebuilt and pruned the GRAY8 selection. On 24 MP this took 85–97 ms even for a rectangular selection or Select All, and each surviving tile had its own pixel allocation. ## Change - New `selection::inverse_surface` works directly on tiles. Missing zero-default tiles become references to one solid selected tile; fully selected tiles disappear; mixed GRAY8 tiles invert their bytes with `255 - b`. - Interior tiles are cached by their source payload. A solid fill or a repeated mixed tile is
- Status
- open
- Score
- 0.00
- Adopters
- 0 other operators
- Author
- wanikhawar (imported from pull request #9793, open)
- Base
d42f9da94a421980d7130c63ca2953e47802cfbe- Size
- +336 −6 in 6 files
- Review
- pending
- Shared
- 2026-10-28
- Id
4eff9effe0c64a6a6a0da1ff
How it went
No other operator has reported using it yet.
Diff
raw · crates/algo/src/selection.rs crates/algo/src/selection/inverse.rs crates/algo/src/selection/inverse/tests.rs crates/engine/examples/bench_selection_inverse.rs crates/engine/src/cmd.rs crates/engine/src/tests.rs
@@ -761,10 +761,12 @@ pub fn tone_range(px: &[[f32; 4]], lo: f32, hi: f32, falloff: f32) -> Vec<f32> { } mod distance;+mod inverse; mod lasso; mod marquee; pub use distance::edt;+pub use inverse::inverse_surface; pub(crate) use lasso::clip_segment; pub use lasso::{MAX_PAINTED_TILES, polygon_edge_tiles, polygon_surface}; pub use marquee::{combine_sparse, combine_surfaces, ellipse_surface};new file mode 100644@@ -0,0 +1,104 @@+//! Tile-wise selection inversion, with shared solid tiles and no canvas-sized buffers.++use std::collections::HashMap;+use std::sync::{Arc, OnceLock};++use photocraft_color::{PixelFormat, read_sample};+use photocraft_geom::{Rect, TILE_SIZE, TileCoord};+use photocraft_raster::{Surface, Tile};++use crate::photo_util::par_map;++use super::coverage8;++/// Invert coverage within `area`, returning a zero-default GRAY8 selection with nothing+/// outside it. Missing tiles become shared solid tiles; selected solid tiles disappear.+/// Each distinct interior source tile is inverted only once, preserving sharing and snapshots.+/// Selections are GRAY8; other formats use their first channel, quantized to selection coverage.+pub fn inverse_surface(source: &Surface, area: Rect) -> Surface {+ let mut out = Surface::new(PixelFormat::GRAY8);+ if area.is_empty() {+ return out;+ }+ let (blank, full) = (out.solid_tile(&[0.0]), out.solid_tile(&[1.0]));+ let default = coverage8(1.0 - source.default_pixel().first().copied().unwrap_or(0.0));+ let missing = match default {+ 0 => None,+ 255 => Some(Arc::clone(&full)),+ v => Some(out.solid_tile(&[f32::from(v) / 255.0])),+ };+ // Solid fills share one payload across many coordinates. Cache by payload, rather than+ // scanning/copying the same 64 KiB for every tile. OnceLock allows parallel tile workers.+ let cache: HashMap<_, OnceLock<Option<Arc<Tile>>>> =+ source.tiles().filter(|(c, _)| area.contains_rect(&c.rect())).map(|(_, t)| (Arc::as_ptr(t) as usize, OnceLock::new())).collect();+ let format = source.format();+ let value = |t: &Tile, i: usize| {+ if format == PixelFormat::GRAY8 {+ t.bytes().get(i).map_or(default, |b| 255 - b)+ } else {+ let bpp = format.bytes_per_pixel();+ t.bytes().get(i * bpp..(i + 1) * bpp).map_or(default, |pixel| coverage8(1.0 - read_sample(pixel, format.sample, 0)))+ }+ };+ let coords: Vec<TileCoord> = area.tiles().collect();+ let built = par_map(coords.len(), |k| {+ let tc = *coords.get(k)?;+ let rect = tc.rect();+ let cut = rect.intersect(&area);+ let input = source.tile(tc);+ // At i32::MAX the coordinate rectangle is saturated and omits the tile's last+ // column/row, so it must still take the clipped path.+ if cut == rect && cut.width() == TILE_SIZE as u32 && cut.height() == TILE_SIZE as u32 {+ let Some(input) = input else { return missing.clone().map(|t| (tc, t)) };+ let cell = cache.get(&(Arc::as_ptr(input) as usize))?;+ let tile = cell.get_or_init(|| {+ if format == PixelFormat::GRAY8 {+ if input.bytes() == full.bytes() {+ return None;+ }+ if input.bytes() == blank.bytes() {+ return Some(Arc::clone(&full));+ }+ let mut tile = Tile::clone(input);+ for b in tile.bytes_mut() {+ *b = 255 - *b;+ }+ return Some(Arc::new(tile));+ }+ let mut tile = Tile::clone(&blank);+ for (i, b) in tile.bytes_mut().iter_mut().enumerate() {+ *b = value(input, i);+ }+ canonical(tile, &blank, &full)+ });+ return tile.clone().map(|t| (tc, t));+ }+ // Boundary tiles start at zero so no inverted coverage leaks past the canvas.+ let mut tile = Tile::clone(&blank);+ let (x0, x1) = ((cut.x0 - rect.x0) as usize, (cut.x1 - rect.x0) as usize);+ for y in (cut.y0 - rect.y0) as usize..(cut.y1 - rect.y0) as usize {+ let start = y * TILE_SIZE as usize + x0;+ if let Some(row) = tile.bytes_mut().get_mut(start..start + x1 - x0) {+ for (i, b) in (start..).zip(row) {+ *b = input.map_or(default, |t| value(t, i));+ }+ }+ }+ canonical(tile, &blank, &full).map(|t| (tc, t))+ });+ out.put_tiles(built.into_iter().flatten());+ out+}++fn canonical(tile: Tile, blank: &Arc<Tile>, full: &Arc<Tile>) -> Option<Arc<Tile>> {+ if tile.bytes() == blank.bytes() {+ None+ } else if tile.bytes() == full.bytes() {+ Some(Arc::clone(full))+ } else {+ Some(Arc::new(tile))+ }+}++#[cfg(test)]+mod tests;new file mode 100644@@ -0,0 +1,85 @@+use super::*;+use photocraft_color::{ColorMode, SampleType};++fn reference(source: &Surface, area: Rect) -> Surface {+ let data: Vec<f32> = source.read_region(area).chunks_exact(source.channels()).map(|p| 1.0 - p[0]).collect();+ let mut out = Surface::new(PixelFormat::GRAY8);+ out.write_region(area, &data);+ out.prune();+ out+}++#[test]+fn inverse_matches_float_reference_and_clips_boundary_tiles() {+ // Negative, misaligned and empty bounds, including stored pixels beyond the canvas.+ for area in [Rect::new(-17, -11, 530, 270), Rect::new(0, 0, 512, 256), Rect::new(3, 5, 4, 6), Rect::EMPTY] {+ for sample in SampleType::ALL {+ for default in [0.0, 0.25, 1.0] {+ let fmt = PixelFormat::new(ColorMode::Grayscale, sample, false);+ let mut source = Surface::with_default(fmt, &[default]);+ source.fill_rect(Rect::new(-100, -100, 260, 120), &[1.0]);+ // Every encoded GRAY8 value, including feathered coverage at tile seams.+ let values: Vec<f32> = (0..256).map(|v| v as f32 / 255.0).collect();+ source.write_region(Rect::new(240, 125, 496, 126), &values);+ source.write_pixel(750, 280, &[0.7]);+ let got = inverse_surface(&source, area);+ let want = reference(&source, area);+ let window = Rect::new(-30, -20, 800, 290);+ assert_eq!(got.to_interleaved(window), want.to_interleaved(window), "{sample:?} {default} {area:?}");+ assert_eq!(got.default_bytes(), &[0]);+ assert_eq!(got.tile_count(), want.tile_count(), "zero tiles must be pruned");+ }+ }+ }+}++#[test]+fn inverse_preserves_sparse_storage_and_shared_payloads() {+ let area = Rect::new(0, 0, 2048, 1024);+ let empty = Surface::new(PixelFormat::GRAY8);+ let selected = inverse_surface(&empty, area);+ assert_eq!(selected.tile_count(), 32);+ let full = selected.tile(TileCoord::new(0, 0)).unwrap();+ assert!(selected.tiles().all(|(_, t)| Arc::ptr_eq(t, full)), "missing tiles share one solid payload");+ let cleared = inverse_surface(&selected, area);+ assert_eq!(cleared.tile_count(), 0, "fully selected tiles disappear");++ let mut mixed = Surface::new(PixelFormat::GRAY8);+ mixed.write_pixel(10, 11, &[0.25]);+ let payload = mixed.tile(TileCoord::new(0, 0)).unwrap().clone();+ mixed.put_tiles(area.tiles().map(|c| (c, payload.clone())));+ let snapshot = mixed.clone();+ let inverted = inverse_surface(&mixed, area);+ let result = inverted.tile(TileCoord::new(0, 0)).unwrap();+ assert!(inverted.tiles().all(|(_, t)| Arc::ptr_eq(t, result)), "shared mixed tiles are inverted once");+ assert!(!Arc::ptr_eq(result, &payload));+ assert_eq!(mixed.to_interleaved(area), snapshot.to_interleaved(area));+ assert_eq!(inverse_surface(&inverted, area).to_interleaved(area), mixed.to_interleaved(area));+}++#[test]+fn inverse_of_unpruned_zero_tiles_is_shared_full() {+ let mut source = Surface::new(PixelFormat::GRAY8);+ let area = Rect::new(0, 0, 768, 256);+ source.fill_rect(Rect::new(0, 0, 256, 256), &[0.0]);+ source.fill_rect(Rect::new(256, 0, 512, 256), &[1.0]);+ let out = inverse_surface(&source, area);+ assert_eq!(out.tile_count(), 2);+ assert!(out.tile(TileCoord::new(1, 0)).is_none());+ assert!(Arc::ptr_eq(out.tile(TileCoord::new(0, 0)).unwrap(), out.tile(TileCoord::new(2, 0)).unwrap()));+}++#[test]+fn inverse_clips_at_coordinate_limits_and_uses_first_channel() {+ for area in [Rect::new(i32::MAX - 255, 0, i32::MAX, 256), Rect::new(0, i32::MAX - 255, 256, i32::MAX), Rect::new(i32::MIN, -1, i32::MIN + 3, 2)] {+ let source = Surface::new(PixelFormat::GRAY8);+ let out = inverse_surface(&source, area);+ assert_eq!(out.to_interleaved(area), reference(&source, area).to_interleaved(area));+ assert_eq!(out.sample_channel(area.x1, area.y0, 0), 0.0);+ assert_eq!(out.sample_channel(area.x0, area.y1, 0), 0.0);+ }+ let area = Rect::new(0, 0, 513, 260);+ let mut source = Surface::with_default(PixelFormat::RGBA32F, &[0.25, 0.5, 0.75, 1.0]);+ source.fill_rect(Rect::new(10, 10, 400, 200), &[0.75, 1.0, 0.0, 0.5]);+ assert_eq!(inverse_surface(&source, area).to_interleaved(area), reference(&source, area).to_interleaved(area));+}new file mode 100644@@ -0,0 +1,109 @@+//! End-to-end timing of `select.inverse` on a 6000×4000 document.+//!+//! ```sh+//! cargo run --release -p photocraft-engine --example bench_selection_inverse -- [--quick] [--reps 11]+//! ```+//!+//! Three rows: inverting a rectangular marquee, an elliptical marquee (central 2/3 of the+//! canvas) and `select.all`. Setup is never timed — only the `execute("select.inverse")`+//! call between `Instant`s. After the timed op (before deselect) the resulting selection+//! surface is inspected for storage diagnostics: unique tile payloads (distinct `Arc`+//! allocations behind the coverage surface) and allocated tile count.++use std::collections::HashSet;+use std::time::Instant;++use photocraft_engine::Session;+use serde_json::{Value, json};++type Res = Result<(), Box<dyn std::error::Error>>;++fn arg<'a>(args: &'a [String], name: &str) -> Option<&'a String> {+ args.iter().position(|a| a == name).and_then(|i| args.get(i + 1))+}++/// Nearest-rank percentile of a pre-sorted slice.+fn pct(sorted: &[f64], p: f64) -> f64 {+ let n = sorted.len();+ let idx = ((p / 100.0) * n as f64).ceil() as usize;+ sorted.get(idx.saturating_sub(1).min(n.saturating_sub(1))).copied().unwrap_or(0.0)+}++/// Selection setup for one row; each previous sample already deselected.+fn setup(s: &mut Session, w: i32, h: i32, ellipse: Option<bool>) -> Result<Value, Box<dyn std::error::Error>> {+ let params = match ellipse {+ Some(ellipse) => {+ // Central 2/3 of the canvas.+ let x = w / 6;+ let y = h / 6;+ json!({+ "x": x,+ "y": y,+ "width": w.saturating_mul(2) / 3,+ "height": h.saturating_mul(2) / 3,+ "ellipse": ellipse,+ })+ }+ None => json!({}), // select.all+ };+ let id = if ellipse.is_some() { "select.rect" } else { "select.all" };+ let v = s.execute(id, params)?;+ Ok(v)+}++/// Storage diagnostics of the current selection surface: distinct tile payloads and tiles held.+fn diagnostics(s: &Session) -> Result<(usize, usize), Box<dyn std::error::Error>> {+ let Some(state) = s.active() else {+ return Err("no active document after select.inverse".into());+ };+ let Some(sel) = state.doc.selection.as_ref() else {+ return Err("no selection after select.inverse".into());+ };+ let mut payloads: HashSet<usize> = HashSet::new();+ let mut count = 0usize;+ for (_, tile) in sel.tiles() {+ payloads.insert(std::sync::Arc::as_ptr(tile) as usize);+ count += 1;+ }+ Ok((payloads.len(), count))+}++/// One measured sample: setup, time ONLY `select.inverse`, print diagnostics, deselect.+fn sample(s: &mut Session, w: i32, h: i32, ellipse: Option<bool>) -> Result<(f64, usize, usize), Box<dyn std::error::Error>> {+ setup(s, w, h, ellipse)?;+ let t = Instant::now();+ s.execute("select.inverse", json!({}))?;+ let ms = t.elapsed().as_secs_f64() * 1000.0;+ let (payloads, tiles) = diagnostics(s)?;+ s.execute("select.deselect", json!({}))?;+ Ok((ms, payloads, tiles))+}++fn main() -> Res {+ let args: Vec<String> = std::env::args().collect();+ let (w, h) = if args.iter().any(|a| a == "--quick") { (1200, 800) } else { (6000, 4000) };+ let reps = arg(&args, "--reps").and_then(|v| v.parse::<usize>().ok()).unwrap_or(11).clamp(1, 100);++ let mut s = Session::new();+ s.execute("file.new", json!({"width": w, "height": h, "background": "transparent"}))?;++ let rows: [(&str, Option<bool>); 3] = [("Inverse rectangular", Some(false)), ("Inverse ellipse", Some(true)), ("Inverse all", None)];+ for (label, ellipse) in rows {+ // Warm-up: one untimed sample to page in allocations and caches.+ sample(&mut s, w, h, ellipse)?;+ let mut times: Vec<f64> = Vec::with_capacity(reps);+ for _ in 0..reps {+ let (ms, payloads, tiles) = sample(&mut s, w, h, ellipse)?;+ times.push(ms);+ println!("sample: {ms:8.2} ms (selection tiles: {payloads} unique payloads, {tiles} allocated)");+ }+ times.sort_by(|a, b| a.total_cmp(b));+ println!(+ "{label:<22} ({w}×{h}, {reps} reps) p50 {p50:8.2} ms p95 {p95:8.2} ms max {max:8.2} ms",+ p50 = pct(×, 50.0),+ p95 = pct(×, 95.0),+ max = pct(×, 100.0),+ );+ }+ Ok(())+}@@ -363,12 +363,7 @@ fn build() -> Vec<CommandSpec> { cmd!("select.inverse", "Inverse", ["Select"], Some("Cmd+Shift+I"), "{}", has_selection, |s, _| { s.edit("Inverse", |doc, _| { let old = doc.selection.take().unwrap_or_else(|| Surface::new(photocraft_color::PixelFormat::GRAY8));- let b = doc.bounds();- let data: Vec<f32> = old.read_region(b).into_iter().map(|v| 1.0 - v).collect();- let mut m = Surface::new(photocraft_color::PixelFormat::GRAY8);- m.write_region(b, &data);- m.prune();- doc.selection = Some(m);+ doc.selection = Some(photocraft_algo::selection::inverse_surface(&old, doc.bounds())); Ok(()) })?; Ok(Value::Null)@@ -506,6 +506,41 @@ fn undo_and_redo_restore_the_targeted_layers() { assert_eq!(target(&s), copies); } +#[test]+fn selection_inverse_preserves_coverage_history_and_empty_selection() {+ for depth in [8, 16, 32] {+ let mut s = Session::new();+ s.execute("file.new", json!({"width": 530, "height": 270, "depth": depth})).unwrap();+ s.execute("select.rect", json!({"x": 250, "y": 10, "width": 30, "height": 30, "ellipse": true})).unwrap();+ let before = s.active().unwrap().doc.clone();+ let area = before.bounds();+ let original = before.selection.as_ref().unwrap().to_interleaved(area);+ s.execute("select.inverse", json!({})).unwrap();+ let after = s.active().unwrap();+ let inverted = after.doc.selection.as_ref().unwrap();+ assert_eq!(inverted.to_interleaved(area), original.iter().map(|b| 255 - b).collect::<Vec<_>>());+ assert_eq!(inverted.sample_channel(530, 269, 0), 0.0);+ assert_eq!(inverted.sample_channel(529, 270, 0), 0.0);+ assert_eq!(after.last_damage, Some(photocraft_geom::Rect::EMPTY));+ assert_eq!(before.selection.as_ref().unwrap().to_interleaved(area), original);+ assert!(s.undo());+ assert_eq!(s.active().unwrap().doc.selection.as_ref().unwrap().to_interleaved(area), original);+ assert!(s.redo());+ s.execute("select.inverse", json!({})).unwrap();+ assert_eq!(s.active().unwrap().doc.selection.as_ref().unwrap().to_interleaved(area), original);++ s.execute("select.all", json!({})).unwrap();+ s.execute("select.inverse", json!({})).unwrap();+ let empty = s.active().unwrap().doc.selection.as_ref().unwrap();+ assert_eq!(empty.tile_count(), 0);+ // Keep Some(empty), as before: the next Inverse selects the whole canvas again.+ s.execute("select.inverse", json!({})).unwrap();+ assert_eq!(s.active().unwrap().doc.selection.as_ref().unwrap().content_bounds(), area);+ }+ let mut s = Session::new();+ assert!(s.execute("select.inverse", json!({})).is_err());+}+ #[test] fn selection_modes() { let mut s = session_with_doc();