d84914ef1e5a
tile.rs
//! Sparse, copy-on-write tiled images of `u16` components.
use std::sync::Arc;
/// Tile edge in texels.
pub const TILE: u32 = 64;
/// Texels per tile.
pub const TILE_AREA: usize = (TILE * TILE) as usize;
/// A tile's texel data: `TILE_AREA ร comps` interleaved components.
pub type TileData = Arc<Vec<u16>>;
/// An image split into 64ร64 tiles; unallocated tiles read as zero. Cloning shares the tile table
/// and every tile, so a snapshot costs one reference-count bump; the first write after a clone
/// copies the table (one pointer per tile slot) once.
#[derive(Clone, Debug, PartialEq)]
pub struct TileImage {
width: u32,
height: u32,
comps: usize,
tiles_x: u32,
tiles_y: u32,
tiles: Arc<Vec<Option<TileData>>>,
}
impl TileImage {
/// `comps` is clamped to 1..=4; sizes to at least 1.
pub fn new(width: u32, height: u32, comps: usize) -> TileImage {
let (width, height) = (width.max(1), height.max(1));
let tiles_x = width.div_ceil(TILE);
let tiles_y = height.div_ceil(TILE);
TileImage { width, height, comps: comps.clamp(1, 4), tiles_x, tiles_y, tiles: Arc::new(vec![None; (tiles_x * tiles_y) as usize]) }
}
pub fn width(&self) -> u32 {
self.width
}
pub fn height(&self) -> u32 {
self.height
}
pub fn comps(&self) -> usize {
self.comps
}
pub fn tiles_x(&self) -> u32 {
self.tiles_x
}
pub fn tiles_y(&self) -> u32 {
self.tiles_y
}
fn tile_index(&self, tx: u32, ty: u32) -> Option<usize> {
(tx < self.tiles_x && ty < self.tiles_y).then(|| (ty * self.tiles_x + tx) as usize)
}
pub fn tile(&self, tx: u32, ty: u32) -> Option<&[u16]> {
self.tile_index(tx, ty).and_then(|i| self.tiles.get(i)).and_then(|t| t.as_deref().map(Vec::as_slice))
}
/// The shared tile handle (for undo snapshots and change fingerprints).
pub fn tile_handle(&self, tx: u32, ty: u32) -> Option<&TileData> {
self.tile_index(tx, ty).and_then(|i| self.tiles.get(i)).and_then(Option::as_ref)
}
/// Replace a tile wholesale (None frees it).
pub fn set_tile(&mut self, tx: u32, ty: u32, data: Option<TileData>) {
let len = TILE_AREA * self.comps;
let data = data.filter(|d| d.len() == len);
let Some(i) = self.tile_index(tx, ty) else { return };
// Keep the shared table when freeing an already empty tile
if data.is_none() && self.tiles.get(i).is_some_and(Option::is_none) {
return;
}
if let Some(slot) = Arc::make_mut(&mut self.tiles).get_mut(i) {
*slot = data;
}
}
/// Mutable texels of a tile, allocating it filled with `fill` (one value per component)
/// when absent and un-sharing it when shared.
pub fn tile_mut(&mut self, tx: u32, ty: u32, fill: &[u16]) -> Option<&mut [u16]> {
let comps = self.comps;
let i = self.tile_index(tx, ty)?;
let slot = Arc::make_mut(&mut self.tiles).get_mut(i)?;
let tile = slot.get_or_insert_with(|| {
let mut data = vec![0u16; TILE_AREA * comps];
if fill.iter().any(|value| *value != 0) {
for texel in data.chunks_exact_mut(comps) {
for (component, value) in texel.iter_mut().zip(fill) {
*component = *value;
}
}
}
Arc::new(data)
});
Some(Arc::make_mut(tile).as_mut_slice())
}
pub fn is_allocated(&self, tx: u32, ty: u32) -> bool {
self.tile_handle(tx, ty).is_some()
}
/// Allocated tile coordinates.
pub fn allocated(&self) -> impl Iterator<Item = (u32, u32)> + '_ {
self.tiles.iter().enumerate().filter(|(_, t)| t.is_some()).map(|(i, _)| (i as u32 % self.tiles_x, i as u32 / self.tiles_x))
}
pub fn allocated_count(&self) -> usize {
self.tiles.iter().filter(|t| t.is_some()).count()
}
/// Components of the texel at (x, y); zeros when out of range or unallocated.
pub fn get(&self, x: u32, y: u32) -> [u16; 4] {
let mut out = [0u16; 4];
if x >= self.width || y >= self.height {
return out;
}
if let Some(t) = self.tile(x / TILE, y / TILE) {
let o = (((y % TILE) * TILE + x % TILE) as usize) * self.comps;
for (c, v) in out.iter_mut().take(self.comps).enumerate() {
*v = t.get(o + c).copied().unwrap_or(0);
}
}
out
}
/// Set one texel (allocating its tile with zeros).
pub fn set(&mut self, x: u32, y: u32, v: &[u16]) {
if x >= self.width || y >= self.height {
return;
}
let comps = self.comps;
if let Some(t) = self.tile_mut(x / TILE, y / TILE, &[]) {
let o = (((y % TILE) * TILE + x % TILE) as usize) * comps;
for (c, s) in v.iter().take(comps).enumerate() {
if let Some(d) = t.get_mut(o + c) {
*d = *s;
}
}
}
}
/// Bytes held by allocated tiles (memory estimate for the status bar).
pub fn bytes(&self) -> usize {
self.allocated_count() * TILE_AREA * self.comps * 2
}
/// Whether both images currently share the same tile table. Mutable access can unshare it
/// even if the caller leaves the texels unchanged.
pub fn same_tiles(&self, other: &TileImage) -> bool {
Arc::ptr_eq(&self.tiles, &other.tiles)
}
/// Drop tiles whose every texel is zero.
pub fn prune_empty(&mut self) {
let is_zero_tile = |tile: &Option<TileData>| tile.as_ref().is_some_and(|data| data.iter().all(|value| *value == 0));
if !self.tiles.iter().any(is_zero_tile) {
return;
}
for tile in Arc::make_mut(&mut self.tiles) {
if is_zero_tile(tile) {
*tile = None;
}
}
}
}
/// 0..1 โ u16.
#[inline]
pub fn to_u16(v: f32) -> u16 {
(v.clamp(0.0, 1.0) * 65535.0 + 0.5) as u16
}
/// u16 โ 0..1.
#[inline]
pub fn from_u16(v: u16) -> f32 {
v as f32 * (1.0 / 65535.0)
}
/// -1..1 โ u16.
#[inline]
pub fn to_u16_signed(v: f32) -> u16 {
to_u16(v * 0.5 + 0.5)
}
/// u16 โ -1..1.
#[inline]
pub fn from_u16_signed(v: u16) -> f32 {
from_u16(v) * 2.0 - 1.0
}
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn unallocated_tiles_read_zero_and_writes_allocate() {
let mut img = TileImage::new(200, 130, 2);
assert_eq!(img.tiles_x(), 4);
assert_eq!(img.tiles_y(), 3);
assert_eq!(img.get(10, 10), [0; 4]);
img.set(199, 129, &[7, 9]);
assert_eq!(img.get(199, 129), [7, 9, 0, 0]);
assert_eq!(img.allocated_count(), 1);
assert_eq!(img.allocated().collect::<Vec<_>>(), vec![(3, 2)]);
// An out-of-range write must leave the image intact
img.set(500, 500, &[1, 1]);
assert_eq!(img.get(500, 500), [0; 4]);
}
#[test]
fn clones_share_tiles_until_written() {
let mut original = TileImage::new(64, 64, 1);
original.set(0, 0, &[5]);
let snapshot = original.clone();
assert!(Arc::ptr_eq(original.tile_handle(0, 0).unwrap(), snapshot.tile_handle(0, 0).unwrap()));
original.set(1, 0, &[6]);
assert!(!Arc::ptr_eq(original.tile_handle(0, 0).unwrap(), snapshot.tile_handle(0, 0).unwrap()));
assert_eq!(snapshot.get(1, 0)[0], 0);
assert_eq!(original.get(1, 0)[0], 6);
}
#[test]
fn clone_shares_the_table_until_written() {
let mut original = TileImage::new(512, 512, 2);
original.set(0, 0, &[1, 2]);
let mut copy = original.clone();
assert!(original.same_tiles(©));
copy.set(70, 0, &[3, 4]);
assert!(!original.same_tiles(©));
assert_eq!(original.get(70, 0)[..2], [0, 0]);
assert_eq!(copy.get(70, 0)[..2], [3, 4]);
assert_eq!(original.get(0, 0)[..2], [1, 2]);
assert_eq!(copy.get(0, 0)[..2], [1, 2]);
}
#[test]
fn cloning_an_image_does_not_clone_its_tile_handles() {
let mut original = TileImage::new(512, 512, 2);
original.set(0, 0, &[1, 2]);
let copy = original.clone();
assert_eq!(Arc::strong_count(original.tile_handle(0, 0).unwrap()), 1);
assert_eq!(copy.get(0, 0)[..2], [1, 2]);
}
// Writes must detach the shared tile as well as its table
#[test]
fn writing_a_shared_tile_leaves_the_clone_alone() {
let mut original = TileImage::new(512, 512, 2);
original.set(0, 0, &[1, 2]);
let mut copy = original.clone();
copy.set(0, 0, &[3, 4]);
copy.tile_mut(0, 0, &[]).unwrap()[2..4].copy_from_slice(&[5, 6]);
assert_eq!(original.get(0, 0)[..2], [1, 2]);
assert_eq!(original.get(1, 0)[..2], [0, 0]);
assert_eq!(copy.get(0, 0)[..2], [3, 4]);
assert_eq!(copy.get(1, 0)[..2], [5, 6]);
}
#[test]
fn out_of_range_writes_do_not_unshare() {
let mut original = TileImage::new(512, 512, 2);
original.set(0, 0, &[1, 2]);
let mut copy = original.clone();
copy.set_tile(999, 999, None);
assert!(copy.tile_mut(999, 999, &[0, 0]).is_none());
assert!(original.same_tiles(©));
}
// An already empty tile must leave the shared table intact for undo restores
#[test]
fn freeing_a_free_tile_does_not_unshare() {
let mut original = TileImage::new(512, 512, 2);
original.set(0, 0, &[1, 2]);
let mut copy = original.clone();
copy.set_tile(1, 0, None);
assert!(original.same_tiles(©));
copy.set_tile(0, 0, None);
assert!(!original.same_tiles(©), "freeing a used tile still un-shares");
assert_eq!(copy.get(0, 0)[..2], [0, 0]);
}
#[test]
fn noop_prune_does_not_unshare() {
let mut original = TileImage::new(512, 512, 2);
original.set(0, 0, &[1, 2]);
let mut copy = original.clone();
copy.prune_empty();
assert!(original.same_tiles(©));
}
#[test]
fn tile_mut_fills_new_tiles() {
let mut img = TileImage::new(64, 64, 2);
let texels = img.tile_mut(0, 0, &[100, 200]).unwrap();
assert_eq!(&texels[..4], &[100, 200, 100, 200]);
img.prune_empty();
assert_eq!(img.allocated_count(), 1);
img.set_tile(0, 0, Some(Arc::new(vec![0; TILE_AREA * 2])));
img.prune_empty();
assert_eq!(img.allocated_count(), 0);
}
#[test]
fn unorm_round_trips() {
for v in [0.0, 0.25, 0.5, 1.0] {
assert!((from_u16(to_u16(v)) - v).abs() < 1e-4);
assert!((from_u16_signed(to_u16_signed(v * 2.0 - 1.0)) - (v * 2.0 - 1.0)).abs() < 1e-4);
}
assert_eq!(to_u16(f32::NAN), 0);
}
}
impl TileImage {
/// A bilinear resample to `width ร height` (same component count). Unallocated source
/// texels read as `empty` (one value per component); destination tiles whose source
/// footprint is entirely unallocated stay unallocated.
pub fn resampled(&self, width: u32, height: u32, empty: &[u16]) -> TileImage {
let mut out = TileImage::new(width, height, self.comps);
if self.allocated_count() == 0 {
return out;
}
for ty in 0..out.tiles_y {
for tx in 0..out.tiles_x {
if let Some(data) = self.resampled_tile(width, height, tx, ty, empty) {
out.set_tile(tx, ty, Some(Arc::new(data)));
}
}
}
out
}
/// Tile (tx, ty) of [`TileImage::resampled`] alone (None when its source footprint is
/// entirely unallocated).
pub fn resampled_tile(&self, width: u32, height: u32, tx: u32, ty: u32, empty: &[u16]) -> Option<Vec<u16>> {
let (sw, sh) = (self.width as f32, self.height as f32);
let (dw, dh) = (width.max(1), height.max(1));
let comps = self.comps;
// Skip destination tiles whose source footprint has no allocated tile.
let (x0, y0) = ((tx * TILE) as f32 * sw / dw as f32, (ty * TILE) as f32 * sh / dh as f32);
let (x1, y1) = (((tx + 1) * TILE) as f32 * sw / dw as f32, ((ty + 1) * TILE) as f32 * sh / dh as f32);
let any = ((y0 as u32).saturating_sub(1) / TILE..=((y1 as u32 + 1) / TILE).min(self.tiles_y.saturating_sub(1))).any(|sy| {
((x0 as u32).saturating_sub(1) / TILE..=((x1 as u32 + 1) / TILE).min(self.tiles_x.saturating_sub(1))).any(|sx| self.is_allocated(sx, sy))
});
if !any || self.width == 0 || self.height == 0 {
return None;
}
let mut data = vec![0u16; TILE_AREA * comps];
for ly in 0..TILE {
let y = ty * TILE + ly;
if y >= dh {
break;
}
let fy = (y as f32 + 0.5) * sh / dh as f32;
for lx in 0..TILE {
let x = tx * TILE + lx;
if x >= dw {
break;
}
let fx = (x as f32 + 0.5) * sw / dw as f32;
let o = ((ly * TILE + lx) as usize) * comps;
if let Some(out) = data.get_mut(o..o + comps) {
self.bilinear(fx, fy, empty, out);
}
}
}
Some(data)
}
/// Bilinear sample at `(fx, fy)` in texels (texel centers at +0.5, clamped to the image)
/// into `out` (one value per component); unallocated texels read as `empty`. Returns
/// whether any of the four texels is allocated.
fn bilinear(&self, fx: f32, fy: f32, empty: &[u16], out: &mut [u16]) -> bool {
let (fx, fy) = ((fx - 0.5).max(0.0), (fy - 0.5).max(0.0));
let (ix, wx, iy, wy) = (fx.floor() as u32, fx.fract(), fy.floor() as u32, fy.fract());
let mut any = false;
let mut get = |x: u32, y: u32| {
let (x, y) = (x.min(self.width.saturating_sub(1)), y.min(self.height.saturating_sub(1)));
if self.is_allocated(x / TILE, y / TILE) {
any = true;
self.get(x, y)
} else {
let mut e = [0u16; 4];
for (d, s) in e.iter_mut().zip(empty) {
*d = *s;
}
e
}
};
let (a, b, c, d) = (get(ix, iy), get(ix + 1, iy), get(ix, iy + 1), get(ix + 1, iy + 1));
for (k, slot) in out.iter_mut().enumerate().take(4) {
let top = a[k] as f32 * (1.0 - wx) + b[k] as f32 * wx;
let bot = c[k] as f32 * (1.0 - wx) + d[k] as f32 * wx;
*slot = (top * (1.0 - wy) + bot * wy + 0.5) as u16;
}
any
}
/// Whether a bilinear read anywhere in the texel box `(x0, y0)..(x1, y1)` can touch an
/// allocated tile (callers skip work for regions that would read only `empty`).
pub fn any_allocated_in(&self, x0: f32, y0: f32, x1: f32, y1: f32) -> bool {
let span = |lo: f32, hi: f32, n: u32| ((lo - 1.0).max(0.0) as u32 / TILE, ((hi + 1.0).max(0.0) as u32 / TILE).min(n.saturating_sub(1)));
let ((ax, bx), (ay, by)) = (span(x0.min(x1), x0.max(x1), self.tiles_x), span(y0.min(y1), y0.max(y1), self.tiles_y));
(ay..=by).any(|sy| (ax..=bx).any(|sx| self.is_allocated(sx, sy)))
}
/// Tile (tx, ty) of a `width ร height` image resampled through `map`: the center of
/// destination texel (x, y) reads this image bilinearly at `map(x + 0.5, y + 0.5)` (texels;
/// None leaves `empty`). None when no texel of the tile reads an allocated source texel.
pub fn remapped_tile(&self, width: u32, height: u32, tx: u32, ty: u32, empty: &[u16], map: &dyn Fn(f32, f32) -> Option<(f32, f32)>) -> Option<Vec<u16>> {
if self.allocated_count() == 0 || self.width == 0 || self.height == 0 {
return None;
}
let comps = self.comps;
let mut data = vec![0u16; TILE_AREA * comps];
let mut any = false;
for ly in 0..TILE.min(height.saturating_sub(ty * TILE)) {
for lx in 0..TILE.min(width.saturating_sub(tx * TILE)) {
let o = ((ly * TILE + lx) as usize) * comps;
let Some(out) = data.get_mut(o..o + comps) else { continue };
match map((tx * TILE + lx) as f32 + 0.5, (ty * TILE + ly) as f32 + 0.5) {
Some((sx, sy)) if sx.is_finite() && sy.is_finite() => any |= self.bilinear(sx, sy, empty, out),
_ => {
for (d, s) in out.iter_mut().zip(empty) {
*d = *s;
}
}
}
}
}
any.then_some(data)
}
}
#[cfg(test)]
mod resample_tests {
use super::*;
#[test]
fn resample_up_and_down_keeps_values_and_sparsity() {
let mut img = TileImage::new(128, 128, 2);
for y in 0..64 {
for x in 0..64 {
img.set(x, y, &[30000, 65535]);
}
}
let up = img.resampled(256, 256, &[]);
assert_eq!(up.get(40, 40)[..2], [30000, 65535]);
assert!(!up.is_allocated(3, 3), "empty regions stay sparse");
let down = img.resampled(64, 64, &[]);
assert_eq!(down.get(10, 10)[..2], [30000, 65535]);
}
#[test]
fn remap_moves_texels_and_keeps_sparsity() {
let mut img = TileImage::new(128, 128, 2);
img.set(10, 20, &[1000, 65535]);
// Mirror horizontally into a 256-wide image (destination x reads source 127.x - x / 2).
let map = |x: f32, y: f32| (x < 256.0).then(|| (128.0 - x / 2.0, y / 2.0));
let tile = |tx, ty| img.remapped_tile(256, 256, tx, ty, &[0, 0], &map);
assert!(tile(0, 0).is_none(), "nothing allocated is read there");
let t = tile(3, 0).unwrap();
// Destination (234, 41) center (234.5, 41.5) reads (10.75, 20.75): mostly texel (10, 20).
let v = t[((41 * TILE + (234 - 192)) * 2) as usize];
assert!(v > 500, "{v}");
}
}
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.