856f865cf98d
blend.rs
use super::{Normal, Placement, par_map, par_rows};
use photocraft_raster::AllocationError;
fn alloc_plane(len: usize) -> Result<Vec<f32>, AllocationError> {
let bytes = len.checked_mul(std::mem::size_of::<f32>()).ok_or(AllocationError::SizeOverflow)?;
let mut v = Vec::new();
v.try_reserve_exact(len).map_err(|_| AllocationError::NotEnoughMemory { bytes })?;
v.resize(len, 0.0);
Ok(v)
}
fn plane_len(w: usize, h: usize, ch: usize) -> Result<usize, AllocationError> {
w.checked_mul(h).and_then(|n| n.checked_mul(ch)).ok_or(AllocationError::SizeOverflow)
}
// ---------- photometric ----------
/// One image warped into the panorama: an axis-aligned region with colour channels and coverage.
#[derive(Clone, Debug)]
pub struct RoiImage {
pub x0: i32,
pub y0: i32,
pub w: usize,
pub h: usize,
/// Colour channels per pixel (no alpha).
pub ch: usize,
pub px: Vec<f32>,
/// Coverage `0..=1`.
pub alpha: Vec<f32>,
}
impl RoiImage {
fn at(&self, x: i32, y: i32) -> Option<usize> {
let (lx, ly) = (x - self.x0, y - self.y0);
(lx >= 0 && ly >= 0 && (lx as usize) < self.w && (ly as usize) < self.h).then(|| ly as usize * self.w + lx as usize)
}
}
/// Placements and source sizes (for the vignetting radius).
pub type Geometry<'a> = (&'a [Placement], &'a [(usize, usize)]);
/// Gains (per image, per channel) and the vignetting model found by [`photometric`].
#[derive(Clone, Debug, PartialEq)]
pub struct Photometric {
pub gains: Vec<Vec<f32>>,
/// `log V(r) = a·r² + b·r⁴`, `r` = distance from the image centre over the half diagonal.
pub vignette: [f64; 2],
}
impl Photometric {
/// Multiplier that corrects a pixel of image `i` at normalised squared radius `r2`.
pub fn factor(&self, i: usize, c: usize, r2: f64) -> f32 {
let v = (self.vignette[0] * r2 + self.vignette[1] * r2 * r2).exp();
(1.0 / (self.gains[i][c] as f64 * v)) as f32
}
}
/// Estimates exposure gains (`gain`) and a shared vignetting falloff (`vignette`) from the
/// overlaps of `imgs` (`placements`/`sizes` give each panorama pixel's source radius).
/// Without `geometry` (placements and source sizes) the vignetting model is not estimated.
pub fn photometric(imgs: &[RoiImage], geometry: Option<Geometry>, gain: bool, vignette: bool) -> Photometric {
let vignette = vignette && geometry.is_some();
let n = imgs.len();
let ch = imgs.first().map_or(1, |i| i.ch);
let identity = Photometric { gains: vec![vec![1.0; ch]; n], vignette: [0.0, 0.0] };
if n == 0 || (!gain && !vignette) {
return identity;
}
// Overlap samples on a grid: (a, b, colours, radii²).
let (mut x0, mut y0, mut x1, mut y1) = (i32::MAX, i32::MAX, i32::MIN, i32::MIN);
for im in imgs {
x0 = x0.min(im.x0);
y0 = y0.min(im.y0);
x1 = x1.max(im.x0 + im.w as i32);
y1 = y1.max(im.y0 + im.h as i32);
}
let step = (((x1 - x0) as i64 * (y1 - y0) as i64 / 40_000).max(1) as f64).sqrt().ceil() as i32;
let r2_of = |i: usize, u: i32, v: i32| -> Option<f64> {
let Some((placements, sizes)) = geometry else { return Some(0.0) };
let (sx, sy) = placements[i].inverse(u as f64 + 0.5, v as f64 + 0.5)?;
let (w, h) = (sizes[i].0 as f64, sizes[i].1 as f64);
let (dx, dy) = (sx - w / 2.0, sy - h / 2.0);
Some((dx * dx + dy * dy) / (w * w / 4.0 + h * h / 4.0))
};
type Sample = (usize, usize, Vec<f32>, Vec<f32>, f64, f64);
let mut samples: Vec<Sample> = Vec::new();
let mut y = y0;
while y < y1 {
let mut x = x0;
while x < x1 {
let cover: Vec<(usize, usize)> = (0..n).filter_map(|i| imgs[i].at(x, y).filter(|&k| imgs[i].alpha[k] > 0.999).map(|k| (i, k))).collect();
for p in 0..cover.len() {
for q in p + 1..cover.len() {
let ((a, ka), (b, kb)) = (cover[p], cover[q]);
let ca = imgs[a].px[ka * ch..(ka + 1) * ch].to_vec();
let cb = imgs[b].px[kb * ch..(kb + 1) * ch].to_vec();
if ca.iter().chain(&cb).any(|v| !(0.02..=0.98).contains(v)) {
continue;
}
// Disagreeing content (parallax, moving objects) says nothing about exposure.
if ca.iter().zip(&cb).any(|(x, y)| (x / y).ln().abs() > 1.0) {
continue;
}
let (Some(ra), Some(rb)) = (r2_of(a, x, y), r2_of(b, x, y)) else { continue };
samples.push((a, b, ca, cb, ra, rb));
}
}
x += step;
}
y += step;
}
if samples.len() < 20 {
return identity;
}
// Unknowns: log gain per image (per channel), then a, b (shared, from mean log intensity).
let sigma_n = 0.05;
let sigma_g = if gain { 0.15 } else { 1e-4 };
let mut out = identity.clone();
let nv = if vignette { 2 } else { 0 };
// Vignetting is solved on the channel mean, then gains per channel with it fixed.
let mut ne = Normal::new(n + nv);
for (a, b, ca, cb, ra, rb) in &samples {
let la = ca.iter().map(|v| (*v as f64).ln()).sum::<f64>() / ch as f64;
let lb = cb.iter().map(|v| (*v as f64).ln()).sum::<f64>() / ch as f64;
let mut row = vec![(*a, 1.0), (*b, -1.0)];
if vignette {
row.push((n, ra - rb));
row.push((n + 1, ra * ra - rb * rb));
}
ne.add(&row, la - lb, 1.0 / sigma_n);
}
for i in 0..n {
ne.add(&[(i, 1.0)], 0.0, 1.0 / sigma_g);
}
if vignette {
ne.add(&[(n, 1.0)], 0.0, 0.5);
ne.add(&[(n + 1, 1.0)], 0.0, 0.5);
}
let Some(sol) = ne.solve() else { return out };
if vignette {
// Vignetting only darkens; clamp a runaway brightening fit.
out.vignette = [sol[n].clamp(-2.0, 0.5), sol[n + 1].clamp(-2.0, 2.0)];
}
if gain {
for c in 0..ch {
let mut ne = Normal::new(n);
for (a, b, ca, cb, ra, rb) in &samples {
let va = out.vignette[0] * ra + out.vignette[1] * ra * ra;
let vb = out.vignette[0] * rb + out.vignette[1] * rb * rb;
ne.add(&[(*a, 1.0), (*b, -1.0)], ((ca[c] as f64).ln() - va) - ((cb[c] as f64).ln() - vb), 1.0 / sigma_n);
}
for i in 0..n {
ne.add(&[(i, 1.0)], 0.0, 1.0 / sigma_g);
}
if let Some(g) = ne.solve() {
for i in 0..n {
out.gains[i][c] = g[i].exp().clamp(0.2, 5.0) as f32;
}
}
}
}
out
}
// ---------- seams ----------
/// Seam labels on a `w × h` grid (`-1` = no image): images are added in `order`; each new image
/// takes the part of its overlap with the composite that lies on its side of the cheapest path
/// through the overlap (cost = colour difference).
pub fn seam_labels(w: usize, h: usize, luma: &[Vec<f32>], cover: &[Vec<bool>], order: &[usize]) -> Vec<i32> {
let mut label = vec![-1i32; w * h];
for &img in order {
let cov = &cover[img];
let mut overlap = vec![false; w * h];
let (mut sx, mut sy, mut no) = (0.0f64, 0.0f64, 0usize);
let (mut nx, mut ny, mut nn) = (0.0f64, 0.0f64, 0usize);
for i in 0..w * h {
if !cov[i] {
continue;
}
nx += (i % w) as f64;
ny += (i / w) as f64;
nn += 1;
if label[i] >= 0 {
overlap[i] = true;
sx += (i % w) as f64;
sy += (i / w) as f64;
no += 1;
} else {
label[i] = img as i32;
}
}
if no == 0 {
continue;
}
let (cx, cy) = (nx / nn as f64, ny / nn as f64);
let contained = nn == no;
let (ox, oy) = if contained {
// Wholly inside the composite (#5745: two photos in one document, the second moved
// by Auto-Align so the canvas crops it to the part over the first). Its side of the
// seam is the one it lies towards from the composite's centre; an image centred on
// the composite has no side, and the earlier images keep it.
let (mut px, mut py, mut pn) = (0.0f64, 0.0f64, 0usize);
for (i, l) in label.iter().enumerate() {
if *l >= 0 {
px += (i % w) as f64;
py += (i / w) as f64;
pn += 1;
}
}
let (px, py) = (px / pn.max(1) as f64, py / pn.max(1) as f64);
if (cx - px).abs() < 0.5 && (cy - py).abs() < 0.5 {
continue;
}
(px, py)
} else {
(sx / no as f64, sy / no as f64)
};
let vertical = (cx - ox).abs() >= (cy - oy).abs();
// Image on the increasing side along the seam's cross axis?
let positive = if vertical { cx > ox } else { cy > oy };
// A contained image has no pixels of its own, so a seam on its outer edge would leave it
// nothing: break cost ties away from its side (towards larger k when it lies on the
// decreasing side) so it keeps its side of the overlap.
let prefer_high = contained && !positive;
let cost = |i: usize| -> f32 { 0.002 + (luma[img][i] - luma[label[i] as usize][i]).abs() };
let (lines, len) = if vertical { (h, w) } else { (w, h) };
let idx = |line: usize, k: usize| if vertical { line * w + k } else { k * w + line };
// DP over lines (rows for a vertical seam), within the overlap.
let mut acc = vec![f32::INFINITY; w * h];
let mut from = vec![usize::MAX; w * h];
let mut prev_line: Option<usize> = None;
for line in 0..lines {
let any = (0..len).any(|k| overlap[idx(line, k)]);
if !any {
continue;
}
for k in 0..len {
let i = idx(line, k);
if !overlap[i] {
continue;
}
let mut best = (0.0f32, usize::MAX);
if let Some(pl) = prev_line.filter(|pl| *pl + 1 == line) {
best = (f32::INFINITY, usize::MAX);
let dks = if prefer_high { [1i64, 0, -1] } else { [-1i64, 0, 1] };
for dk in dks {
let kk = k as i64 + dk;
if kk < 0 || kk >= len as i64 {
continue;
}
let j = idx(pl, kk as usize);
if acc[j] < best.0 {
best = (acc[j], kk as usize);
}
}
if best.1 == usize::MAX {
best = (0.0, usize::MAX);
}
}
acc[i] = best.0 + cost(i);
from[i] = best.1;
}
prev_line = Some(line);
}
// Backtrack from the cheapest end; lines not reached keep their own best cell.
let mut seam = vec![usize::MAX; lines];
let mut line = lines;
while line > 0 {
line -= 1;
if seam[line] != usize::MAX {
continue;
}
let Some(k) = (0..len)
.filter(|&k| overlap[idx(line, k)])
.min_by(|&a, &b| acc[idx(line, a)].total_cmp(&acc[idx(line, b)]).then(if prefer_high { b.cmp(&a) } else { a.cmp(&b) }))
else {
continue;
};
let (mut l, mut k) = (line, k);
loop {
seam[l] = k;
let f = from[idx(l, k)];
if f == usize::MAX || l == 0 {
break;
}
l -= 1;
if seam[l] != usize::MAX {
break;
}
k = f;
}
}
for line in 0..lines {
let s = seam[line];
if s == usize::MAX {
continue;
}
let on_side = |k: usize| if positive { k > s } else { k < s };
// A contained image has no other cells, so where the overlap has nothing on its side
// of the seam (a line one cell wide) it takes the seam cell rather than nothing.
let take_seam = contained && !(0..len).any(|k| overlap[idx(line, k)] && on_side(k));
for k in 0..len {
let i = idx(line, k);
if overlap[i] && (on_side(k) || (take_seam && k == s)) {
label[i] = img as i32;
}
}
}
}
label
}
// ---------- multi-band blending ----------
/// Number of pyramid levels used by [`multiband`] for a seam mask of this size.
pub fn blend_levels(w: usize, h: usize) -> usize {
let mut s = w.min(h);
let mut n = 1;
while s > 16 && n < 7 {
s /= 2;
n += 1;
}
n
}
/// `a[i] = f(a[i], b[i])` for every `i` (the shorter length wins), in place and in parallel on
/// native targets. Purely elementwise, so the result is the serial result bit for bit.
fn par_zip_assign(a: &mut [f32], b: &[f32], f: impl Fn(f32, f32) -> f32 + Sync + Send) {
const CHUNK: usize = 1 << 14;
let fill = |a: &mut [f32], b: &[f32]| {
for (a, &b) in a.iter_mut().zip(b) {
*a = f(*a, b);
}
};
#[cfg(not(target_arch = "wasm32"))]
{
use rayon::prelude::*;
a.par_chunks_mut(CHUNK).zip(b.par_chunks(CHUNK)).for_each(|(a, b)| fill(a, b));
}
#[cfg(target_arch = "wasm32")]
a.chunks_mut(CHUNK).zip(b.chunks(CHUNK)).for_each(|(a, b)| fill(a, b));
}
// `reduce`, `expand` and `push_pull` run one pyramid level for one image at a time, and the
// images themselves only fill part of a many-core machine, so each of them also runs its rows
// in parallel. Every output element is computed by the same expression, in the same order, as
// the one-thread loops they replace (rows never read each other's output), so the result is
// bit for bit unchanged.
pub(super) fn reduce(w: usize, h: usize, ch: usize, src: &[f32]) -> Result<(usize, usize, Vec<f32>), AllocationError> {
let (nw, nh) = (w.div_ceil(2), h.div_ceil(2));
let k = [1.0f32, 4.0, 6.0, 4.0, 1.0];
// Separable 5-tap binomial, then decimate.
let mut tmp = alloc_plane(plane_len(nw, h, ch)?)?;
par_rows(&mut tmp, nw, ch, |y, row| {
let line = &src[y * w * ch..(y + 1) * w * ch];
for x in 0..nw {
// The clamped source column of each tap is the same for every channel.
let xs: [usize; 5] = std::array::from_fn(|t| (2 * x as i64 + t as i64 - 2).clamp(0, w as i64 - 1) as usize * ch);
for c in 0..ch {
let mut s = 0.0;
for (kv, xx) in k.iter().zip(xs) {
s += kv * line[xx + c];
}
row[x * ch + c] = s / 16.0;
}
}
});
let mut out = alloc_plane(plane_len(nw, nh, ch)?)?;
par_rows(&mut out, nw, ch, |y, row| {
// Each output row is five source rows added in tap order: the same sum per element as
// before (`0 + k0·a + k1·b + …`), but over whole rows so it vectorises.
for (t, kv) in k.iter().enumerate() {
let yy = (2 * y as i64 + t as i64 - 2).clamp(0, h as i64 - 1) as usize;
for (o, &v) in row.iter_mut().zip(&tmp[yy * nw * ch..(yy + 1) * nw * ch]) {
*o += kv * v;
}
}
for o in row.iter_mut() {
*o /= 16.0;
}
});
Ok((nw, nh, out))
}
pub(super) fn expand(sw: usize, sh: usize, ch: usize, src: &[f32], w: usize, h: usize) -> Result<Vec<f32>, AllocationError> {
// Bilinear upsampling at half-pixel-aligned positions.
let mut out = alloc_plane(plane_len(w, h, ch)?)?;
// Source columns and weights depend on x only: worked out once instead of for every row.
// The clamped position is never negative, so truncating is `floor` (and spares the libm call).
let mut cols = Vec::new();
cols.try_reserve_exact(w).map_err(|_| AllocationError::NotEnoughMemory { bytes: w.saturating_mul(std::mem::size_of::<(usize, usize, f32)>()) })?;
cols.extend((0..w).map(|x| {
let fx = ((x as f32 + 0.5) / 2.0 - 0.5).clamp(0.0, (sw - 1) as f32);
let x0 = fx as usize;
(x0 * ch, (x0 + 1).min(sw - 1) * ch, fx - x0 as f32)
}));
par_rows(&mut out, w, ch, |y, row| {
let fy = ((y as f32 + 0.5) / 2.0 - 0.5).clamp(0.0, (sh - 1) as f32);
let y0 = fy as usize;
let ty = fy - y0 as f32;
let y1 = (y0 + 1).min(sh - 1);
let (r0, r1) = (&src[y0 * sw * ch..(y0 + 1) * sw * ch], &src[y1 * sw * ch..(y1 + 1) * sw * ch]);
for (px, &(x0, x1, tx)) in row.chunks_exact_mut(ch.max(1)).zip(&cols) {
for (c, o) in px.iter_mut().enumerate() {
let top = r0[x0 + c] + (r0[x1 + c] - r0[x0 + c]) * tx;
let bot = r1[x0 + c] + (r1[x1 + c] - r1[x0 + c]) * tx;
*o = top + (bot - top) * ty;
}
}
});
Ok(out)
}
/// Fills pixels with zero `wt` from their surroundings (push-pull), so pyramid levels don't
/// pull in black from outside an image.
pub(super) fn push_pull(w: usize, h: usize, ch: usize, px: &mut [f32], wt: &[f32]) -> Result<(), AllocationError> {
if w <= 1 && h <= 1 {
return Ok(());
}
let (nw, nh) = (w.div_ceil(2), h.div_ceil(2));
// Coarse sums. A coarse row is fed by two fine rows; walking them in raster order adds each
// coarse cell's (up to) four fine pixels in the order the serial scatter-add did, from zero.
let mut cpx = alloc_plane(plane_len(nw, nh, ch)?)?;
let mut cw = alloc_plane(plane_len(nw, nh, 1)?)?;
par_rows(&mut cw, nw, 1, |cy, row| {
for y in 2 * cy..(2 * cy + 2).min(h) {
for (x, &a) in wt[y * w..(y + 1) * w].iter().enumerate() {
row[x / 2] += a;
}
}
});
let px_in: &[f32] = px;
par_rows(&mut cpx, nw, ch, |cy, row| {
for y in 2 * cy..(2 * cy + 2).min(h) {
for x in 0..w {
let (i, j) = (y * w + x, x / 2);
let a = wt[i];
for c in 0..ch {
row[j * ch + c] += a * px_in[i * ch + c];
}
}
}
});
// Normalise by the weight (this reads `cw` before it is reset to 0 / 1 below).
par_rows(&mut cpx, nw, ch, |cy, row| {
for cx in 0..nw {
let wj = cw[cy * nw + cx];
if wj > 0.0 {
for c in 0..ch {
row[cx * ch + c] /= wj;
}
}
}
});
for v in cw.iter_mut() {
if *v > 0.0 {
*v = 1.0;
}
}
if cw.contains(&0.0) && cw.iter().any(|v| *v > 0.0) {
push_pull(nw, nh, ch, &mut cpx, &cw)?;
}
par_rows(px, w, ch, |y, row| {
for x in 0..w {
let i = y * w + x;
if wt[i] < 1.0 {
let j = (y / 2) * nw + x / 2;
let a = wt[i];
for c in 0..ch {
row[x * ch + c] = a * row[x * ch + c] + (1.0 - a) * cpx[j * ch + c];
}
}
}
});
Ok(())
}
/// One image's pyramid in [`multiband`]: the grid origin `(gx0, gy0)` at level 0, the Laplacian
/// levels `(w, h, colours)` and the Gaussian weight levels.
type PyramidBand = (i32, i32, Vec<(usize, usize, Vec<f32>)>, Vec<Vec<f32>>);
/// The part of `band` on panorama row `py` of level `l`: the panorama column its first pixel
/// lands on, its width, its weight row and its colour row. `None` when it misses the row.
fn band_row(band: &PyramidBand, l: usize, ch: usize, py: usize) -> Option<(usize, usize, &[f32], &[f32])> {
let (ox, oy) = ((band.0 >> l) as usize, (band.1 >> l) as usize);
let (lw, lh, colours) = &band.2[l];
(py >= oy && py - oy < *lh).then(|| {
let y = py - oy;
(ox, *lw, &band.3[l][y * lw..(y + 1) * lw], &colours[y * lw * ch..(y + 1) * lw * ch])
})
}
/// Estimated bytes of band construction [`multiband`] keeps in flight at once. Images are built
/// and accumulated in batches under it, so its peak memory doesn't grow with the image count
/// (#7758). Four 24 MP RGB sources (~1.2 GB each) fit in one batch: building bands side by side
/// uses a many-core machine better than one band's row-parallel work, and one at a time made the
/// usual 2–4 image Photomerge 12–36% slower on a 32-thread desktop.
#[cfg(not(target_arch = "wasm32"))]
pub const BAND_BUDGET: usize = 5 << 30;
/// Without threads the bands of a batch are built one after another anyway, so each is added as
/// soon as it is built (the browser's address space is 4 GB).
#[cfg(target_arch = "wasm32")]
pub const BAND_BUDGET: usize = 0;
/// Multi-band blend of `imgs` into a `w × h` panorama (origin 0,0) with one weight map per image
/// over the same grid as its ROI (`weights[i]` has `w_i × h_i` entries). Returns the colour
/// channels (`ch` per pixel) and the total coverage, or an error when a buffer can't be allocated.
pub fn multiband(w: usize, h: usize, imgs: &[RoiImage], weights: &[Vec<f32>], levels: usize) -> Result<(Vec<f32>, Vec<f32>), AllocationError> {
try_multiband_batched(w, h, imgs, weights, levels, BAND_BUDGET, None)
}
/// The grid an image's band is built on: its ROI grown by a margin and aligned down to the
/// coarsest level's grid, clipped to the `w × h` canvas. Returns `(x0, y0, width, height)`.
fn band_grid(im: &RoiImage, w: usize, h: usize, levels: usize) -> (i32, i32, usize, usize) {
let align = 1i32 << (levels.max(1) - 1);
let margin = align * 4;
let gx0 = ((im.x0 - margin).max(0) / align) * align;
let gy0 = ((im.y0 - margin).max(0) / align) * align;
let gx1 = (im.x0 + im.w as i32 + margin).min(w as i32);
let gy1 = (im.y0 + im.h as i32 + margin).min(h as i32);
(gx0, gy0, (gx1 - gx0).max(1) as usize, (gy1 - gy0).max(1) as usize)
}
/// Estimated bytes of building one band: its grid's colour and weight planes about three times
/// over (the pyramids are 4/3 of a plane, and the grid copy and `expand`/`reduce` scratch come
/// on top). A safe upper bound: the build itself peaks lower.
pub(super) fn band_cost(im: &RoiImage, w: usize, h: usize, ch: usize, levels: usize) -> usize {
let (_, _, gw, gh) = band_grid(im, w, h, levels);
gw.saturating_mul(gh).saturating_mul(ch + 1).saturating_mul(4 * 3)
}
/// An upper bound on `band_cost` (the estimate batching uses) for any ROI of `w × h` pixels on a `canvas_w × canvas_h`
/// canvas: the grid grows the ROI by the margin on both sides and aligns its start down by up to
/// `align - 1`, and never exceeds the canvas.
pub fn band_bytes_bound(w: usize, h: usize, ch: usize, levels: usize, canvas_w: usize, canvas_h: usize) -> usize {
let align = 1usize << (levels.max(1) - 1).min(30);
let margin = align.saturating_mul(4);
let extent = |n: usize, canvas: usize| n.saturating_add(margin.saturating_mul(2)).saturating_add(align).min(canvas).max(1);
extent(w, canvas_w).saturating_mul(extent(h, canvas_h)).saturating_mul(ch.saturating_add(1)).saturating_mul(4 * 3)
}
/// [`multiband`], building at most `budget` estimated bytes of bands at a time (at least one
/// image). Each pixel still adds the bands in image order, so the result doesn't depend on it.
/// With `max_band_budget`, a single band estimated above it is an error instead.
pub fn try_multiband_batched(
w: usize,
h: usize,
imgs: &[RoiImage],
weights: &[Vec<f32>],
levels: usize,
budget: usize,
max_band_budget: Option<usize>,
) -> Result<(Vec<f32>, Vec<f32>), AllocationError> {
let ch = imgs.first().map_or(1, |i| i.ch);
// Levels past 1x1 add nothing; 16 (real use is at most 7) keeps the shifts below in range.
let levels = levels.clamp(1, 16);
let cost = |im: &RoiImage| band_cost(im, w, h, ch, levels);
if let Some(limit) = max_band_budget {
for im in imgs {
let bytes = cost(im);
if bytes > limit {
return Err(AllocationError::NotEnoughMemory { bytes });
}
}
}
// Level sizes of the panorama.
let mut sizes = vec![(w, h)];
for _ in 1..levels {
let Some(&(pw, ph)) = sizes.last() else { break };
sizes.push((pw.div_ceil(2), ph.div_ceil(2)));
}
let mut acc: Vec<Vec<f32>> = Vec::with_capacity(sizes.len());
let mut wsum: Vec<Vec<f32>> = Vec::with_capacity(sizes.len());
for &(lw, lh) in &sizes {
let acc_len = lw.checked_mul(lh).and_then(|n| n.checked_mul(ch)).ok_or(AllocationError::SizeOverflow)?;
acc.push(alloc_plane(acc_len)?);
let wsum_len = lw.checked_mul(lh).ok_or(AllocationError::SizeOverflow)?;
wsum.push(alloc_plane(wsum_len)?);
}
let grid = |im: &RoiImage| band_grid(im, w, h, levels);
let band = |k: usize| -> Result<PyramidBand, AllocationError> {
let im = &imgs[k];
let (gx0, gy0, gw, gh) = grid(im);
// Each grid pixel takes the image pixel that lands on it (every image pixel lands on at
// most one), so rows of the grid are independent and fill in parallel.
let src_of = |gx: usize, gy: usize| -> Option<usize> {
let (x, y) = (gx as i64 + gx0 as i64 - im.x0 as i64, gy as i64 + gy0 as i64 - im.y0 as i64);
(x >= 0 && y >= 0 && (x as usize) < im.w && (y as usize) < im.h).then(|| y as usize * im.w + x as usize)
};
let mut px = alloc_plane(plane_len(gw, gh, ch)?)?;
par_rows(&mut px, gw, ch, |gy, row| {
for gx in 0..gw {
if let Some(i) = src_of(gx, gy) {
row[gx * ch..(gx + 1) * ch].copy_from_slice(&im.px[i * ch..(i + 1) * ch]);
}
}
});
let mut wt = alloc_plane(plane_len(gw, gh, 1)?)?;
par_rows(&mut wt, gw, 1, |gy, row| {
for (gx, o) in row.iter_mut().enumerate() {
if let Some(i) = src_of(gx, gy) {
*o = weights[k][i] * im.alpha[i].min(1.0);
}
}
});
// Binary coverage straight from the alpha (0 outside the image), without a coverage plane.
let mut bin = alloc_plane(plane_len(gw, gh, 1)?)?;
par_rows(&mut bin, gw, 1, |gy, row| {
for (gx, o) in row.iter_mut().enumerate() {
if let Some(i) = src_of(gx, gy) {
*o = if im.alpha[i] > 0.5 { 1.0 } else { 0.0 };
}
}
});
push_pull(gw, gh, ch, &mut px, &bin)?;
drop(bin);
// Laplacian of the colours, Gaussian of the weights. Planes move into the pyramids rather
// than being copied: with one image built at a time, a copy is a serial pass over it.
let mut lap: Vec<(usize, usize, Vec<f32>)> = Vec::new();
let mut gau: Vec<Vec<f32>> = Vec::new();
let (mut cw, mut chh, mut cur, mut cwt) = (gw, gh, px, wt);
for l in 0..levels {
if l + 1 == levels {
lap.push((cw, chh, cur));
gau.push(cwt);
break;
}
let (nw, nh, down) = reduce(cw, chh, ch, &cur)?;
let up = expand(nw, nh, ch, &down, cw, chh)?;
// The Laplacian replaces the level's colours in place (`cur - up`, elementwise).
par_zip_assign(&mut cur, &up, |a, b| a - b);
drop(up);
lap.push((cw, chh, cur));
let (_, _, wdown) = reduce(cw, chh, 1, &cwt)?;
gau.push(cwt);
cw = nw;
chh = nh;
cur = down;
cwt = wdown;
}
Ok((gx0, gy0, lap, gau))
};
// Build the bands a batch at a time and add each batch before building the next. Each pixel
// adds the bands in the same order as the serial loop (per level, bands one after another;
// batches follow each other in image order), but rows of a level are independent, so they
// run in parallel: every row walks the batch's bands itself.
let mut start = 0;
while start < imgs.len() {
let mut end = start + 1;
let c = cost(&imgs[start]);
let mut bytes = c;
while let Some(im) = imgs.get(end)
&& bytes.saturating_add(cost(im)) <= budget
{
bytes = bytes.saturating_add(cost(im));
end += 1;
}
let bands = par_map(end - start, |j| band(start + j)).into_iter().collect::<Result<Vec<_>, _>>()?;
for l in 0..levels {
let pw = sizes[l].0;
par_rows(&mut wsum[l], pw, 1, |py, row| {
for b in &bands {
let Some((ox, lw, g, _)) = band_row(b, l, ch, py) else { continue };
for x in 0..lw {
let px = ox + x;
if px >= pw {
break;
}
let k = g[x];
if k <= 0.0 {
continue;
}
row[px] += k;
}
}
});
par_rows(&mut acc[l], pw, ch, |py, row| {
for b in &bands {
let Some((ox, lw, g, band)) = band_row(b, l, ch, py) else { continue };
for x in 0..lw {
let px = ox + x;
if px >= pw {
break;
}
let k = g[x];
if k <= 0.0 {
continue;
}
for c in 0..ch {
row[px * ch + c] += k * band[x * ch + c];
}
}
}
});
}
start = end;
}
for l in 0..levels {
let pw = sizes[l].0;
let ws = &wsum[l];
par_rows(&mut acc[l], pw, ch, |py, row| {
for x in 0..pw {
let k = ws[py * pw + x];
for c in 0..ch {
row[x * ch + c] = if k > 1e-8 { row[x * ch + c] / k } else { 0.0 };
}
}
});
}
drop(wsum);
// Collapse.
// `levels ≥ 1`, so there is always a coarsest level.
let Some(mut cur) = acc.pop() else {
let total = w.checked_mul(h).and_then(|n| n.checked_mul(ch)).ok_or(AllocationError::SizeOverflow)?;
let cov_total = w.checked_mul(h).ok_or(AllocationError::SizeOverflow)?;
return Ok((alloc_plane(total)?, alloc_plane(cov_total)?));
};
for l in (0..levels - 1).rev() {
let (pw, ph) = sizes[l];
let (sw, sh) = sizes[l + 1];
let up = expand(sw, sh, ch, &cur, pw, ph)?;
// Add the upsampled coarser levels into this level's accumulator (`acc + up`, in place).
let mut level = std::mem::take(&mut acc[l]);
par_zip_assign(&mut level, &up, |a, b| a + b);
drop(up);
cur = level;
}
// Coverage: union of the images. Rows are independent; each walks the images in order, so a
// pixel sees the same sequence of `max` calls as in the serial loop.
let cov_len = w.checked_mul(h).ok_or(AllocationError::SizeOverflow)?;
let mut cov = alloc_plane(cov_len)?;
par_rows(&mut cov, w, 1, |py, row| {
for im in imgs {
let y = py as i64 - im.y0 as i64;
if y < 0 || y as usize >= im.h {
continue;
}
for x in 0..im.w {
let px = im.x0 + x as i32;
if px < 0 || px as usize >= w {
continue;
}
let p = px as usize;
row[p] = row[p].max(im.alpha[y as usize * im.w + x]);
}
}
});
Ok((cur, cov))
}
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.