atmos/os_lib/web_engine/
blur_box.rs

1//! ボックスブラーの高速実装（累積和による厳密な等価変換）。
2//!
3//! 仕様は `spec/backdrop_blur.md`。
4//!
5//! ## なぜ必要か
6//! `backdrop-filter: blur()` を持つ要素（sugi-lab.net のナビゲーションバー、
7//! 924×44）が **1 要素で 179〜478 tick** かかっていた。
8//! 面積が 12 分の 1 の要素が 924×529 の要素より数倍重く、
9//! これが `paint` の未特定分（約 53%）の正体だった。
10//!
11//! 素朴な 2 次元ボックスブラーは **O(W×H×(2r+1)²)**。
12//! r は 1〜8 にクランプされるので最大 17×17 = 289 サンプル／ピクセル。
13//! 924×44 なら 1170 万回の加算を**毎フレーム**行っていた。
14//!
15//! ## 方針
16//! ボックスブラーは「クリップした窓の総和 ÷ 窓内の画素数」。
17//! 窓は矩形なので画素数は `nx(x) × ny(y)` に分解でき、
18//! 総和も行方向の窓和 `H` の縦方向の和に分解できる。
19//! **総和のまま持ち回れば除算は最後の 1 回だけ**になり、
20//! 素朴実装と**ビット単位で同一の出力**になる（近似ではない）。
21//!
22//! 行ごとの累積和を使えば `H` は O(1) で引けるので全体は **O(W×H)**
23//! （半径に依存しない）。
24//!
25//! ## 不変条件（B-1〜B-4）
26//! - **B-1**: 出力は素朴実装とビット単位で一致
27//! - **B-2**: 端は矩形内へクリップし、実際に含まれた画素数で割る
28//! - **B-3**: 除算は最後の 1 回だけ（途中で平均を取ると誤差が積もる）
29//! - **B-4**: 半径 0 以下・幅高さ 0 は何もしない
30
31extern crate alloc;
32
33use alloc::vec::Vec;
34
35/// 窓の範囲（両端含む）を `0..n` へクリップして返す。
36///
37/// 計算量: **O(1)**。
38///
39/// `n == 0` のときは `(0, 0)` を返す（呼び出し側が空を扱う）。
40pub fn window_bounds(i: usize, r: usize, n: usize) -> (usize, usize) {
41    if n == 0 {
42        return (0, 0);
43    }
44    let lo = i.saturating_sub(r);
45    let hi = core::cmp::min(i + r, n - 1);
46    (lo, hi)
47}
48
49/// パック済み RGB（上位 8bit は無視し、出力では 0xFF を立てる）への
50/// ボックスブラー。
51///
52/// 計算量: **O(W×H)** — 半径に依存しない。
53/// 素朴実装は O(W×H×(2r+1)²) だった。
54///
55/// 出力は素朴な 2 次元実装と**ビット単位で一致**する（B-1）。
56/// 途中は総和のまま持ち回り、除算は最後の 1 回だけ（B-3）。
57pub fn box_blur_rgb(src: &[u32], w: usize, h: usize, radius: usize) -> Vec<u32> {
58    if radius == 0 || w == 0 || h == 0 || src.len() < w * h {
59        return src.to_vec();
60    }
61
62    // 1. 行ごとの累積和。`row_pre[y][x]` は「その行の先頭から x-1 まで」の総和。
63    //    幅は w+1（先頭に 0 を置くことで区間和を引き算 1 回で出せる）。
64    let mut pre_r: Vec<u32> = alloc::vec![0u32; (w + 1) * h];
65    let mut pre_g: Vec<u32> = alloc::vec![0u32; (w + 1) * h];
66    let mut pre_b: Vec<u32> = alloc::vec![0u32; (w + 1) * h];
67    for y in 0..h {
68        let base = y * (w + 1);
69        for x in 0..w {
70            let c = src[y * w + x];
71            pre_r[base + x + 1] = pre_r[base + x] + ((c >> 16) & 0xFF);
72            pre_g[base + x + 1] = pre_g[base + x] + ((c >> 8) & 0xFF);
73            pre_b[base + x + 1] = pre_b[base + x] + (c & 0xFF);
74        }
75    }
76
77    // 2. 行方向の窓和 H[y][x]（この時点ではまだ割らない）。
78    //    x の窓範囲は y に依らないので、x ごとに一度求めれば足りる。
79    let mut hr: Vec<u32> = alloc::vec![0u32; w * h];
80    let mut hg: Vec<u32> = alloc::vec![0u32; w * h];
81    let mut hb: Vec<u32> = alloc::vec![0u32; w * h];
82    for y in 0..h {
83        let rbase = y * (w + 1);
84        for x in 0..w {
85            let (x_lo, x_hi) = window_bounds(x, radius, w);
86            let i = y * w + x;
87            hr[i] = pre_r[rbase + x_hi + 1] - pre_r[rbase + x_lo];
88            hg[i] = pre_g[rbase + x_hi + 1] - pre_g[rbase + x_lo];
89            hb[i] = pre_b[rbase + x_hi + 1] - pre_b[rbase + x_lo];
90        }
91    }
92
93    // 3. 列方向にも累積和を取る。これで縦の窓和も引き算 1 回で出せるため、
94    //    全体が **O(W×H)**（半径に依存しない）になる。
95    let mut cr: Vec<u32> = alloc::vec![0u32; w * (h + 1)];
96    let mut cg: Vec<u32> = alloc::vec![0u32; w * (h + 1)];
97    let mut cb: Vec<u32> = alloc::vec![0u32; w * (h + 1)];
98    for y in 0..h {
99        for x in 0..w {
100            let i = y * w + x;
101            cr[(y + 1) * w + x] = cr[y * w + x] + hr[i];
102            cg[(y + 1) * w + x] = cg[y * w + x] + hg[i];
103            cb[(y + 1) * w + x] = cb[y * w + x] + hb[i];
104        }
105    }
106
107    // 4. 総和を画素数で割る。**除算はここ 1 回だけ**（B-3）。
108    let mut out: Vec<u32> = alloc::vec![0u32; w * h];
109    for y in 0..h {
110        let (y_lo, y_hi) = window_bounds(y, radius, h);
111        let ny = (y_hi - y_lo + 1) as u32;
112        for x in 0..w {
113            let (x_lo, x_hi) = window_bounds(x, radius, w);
114            let nx = (x_hi - x_lo + 1) as u32;
115            let n = nx * ny;
116
117            let sr = cr[(y_hi + 1) * w + x] - cr[y_lo * w + x];
118            let sg = cg[(y_hi + 1) * w + x] - cg[y_lo * w + x];
119            let sb = cb[(y_hi + 1) * w + x] - cb[y_lo * w + x];
120
121            out[y * w + x] = 0xFF00_0000 | ((sr / n) << 16) | ((sg / n) << 8) | (sb / n);
122        }
123    }
124    out
125}
atmos/os_lib/web_engine/blur_box.rs

atmos/os_lib/web_engine/
blur_box.rs
