| 1 | use crate::geom::{Change, Rect}; |
| 2 | use crate::plan::{Config, GroupPlan, Strategy, Style}; |
| 3 | use crate::relation::{ABOVE, LEFT, X_BITS, Y_BITS, adjacency, separation}; |
| 4 | use crate::sat::{Lit, TwoSat}; |
| 5 | |
| 6 | /// Upper bound on lane-assignment search steps before giving up on a lane count. |
| 7 | const LANE_SEARCH_BUDGET: usize = 20_000; |
| 8 | |
| 9 | #[derive(Clone, Copy, PartialEq, Eq)] |
| 10 | enum Axis { |
| 11 | X, |
| 12 | Y, |
| 13 | } |
| 14 | |
| 15 | pub(crate) fn plan_group(from: &[Rect], to: &[Rect], cfg: &Config) -> GroupPlan { |
| 16 | let done = |keys: Vec<Vec<Rect>>, strategy| GroupPlan { |
| 17 | keys, |
| 18 | strategy, |
| 19 | opens_hole: false, |
| 20 | }; |
| 21 | let movers: Vec<usize> = (0..from.len()) |
| 22 | .filter(|&i| Change::between(&from[i], &to[i]).moves()) |
| 23 | .collect(); |
| 24 | if movers.is_empty() { |
| 25 | return done(vec![from.to_vec()], Strategy::Unchanged); |
| 26 | } |
| 27 | let pure = movers |
| 28 | .iter() |
| 29 | .all(|&i| !Change::between(&from[i], &to[i]).both()); |
| 30 | if phase_ok(from, to, cfg) && (cfg.style == Style::Direct || pure) { |
| 31 | return done(vec![from.to_vec(), to.to_vec()], Strategy::Direct); |
| 32 | } |
| 33 | if let Some((k1, opens_hole)) = axis_order(from, to, &movers, cfg) { |
| 34 | return GroupPlan { |
| 35 | keys: vec![from.to_vec(), k1, to.to_vec()], |
| 36 | strategy: Strategy::AxisOrder, |
| 37 | opens_hole, |
| 38 | }; |
| 39 | } |
| 40 | for axis in [Axis::Y, Axis::X] { |
| 41 | if let Some((k1, k2, lanes)) = lanes(from, to, &movers, axis, cfg) { |
| 42 | return done( |
| 43 | vec![from.to_vec(), k1, k2, to.to_vec()], |
| 44 | Strategy::Lanes { lanes }, |
| 45 | ); |
| 46 | } |
| 47 | } |
| 48 | if let Some((keys, cells)) = grid(from, to, &movers, cfg) { |
| 49 | return done(keys, Strategy::Grid { cells }); |
| 50 | } |
| 51 | done(pinch(from, to, &movers), Strategy::Pinch) |
| 52 | } |
| 53 | |
| 54 | /// Every pair shares a separating relation at both ends of the phase. |
| 55 | pub(crate) fn phase_ok(a: &[Rect], b: &[Rect], cfg: &Config) -> bool { |
| 56 | (0..a.len()).all(|i| { |
| 57 | (i + 1..a.len()) |
| 58 | .all(|j| separation(&a[i], &a[j], cfg.eps) & separation(&b[i], &b[j], cfg.eps) != 0) |
| 59 | }) |
| 60 | } |
| 61 | |
| 62 | fn pure_ok(keys: &[&[Rect]], cfg: &Config) -> bool { |
| 63 | cfg.style == Style::Direct |
| 64 | || keys.windows(2).all(|w| { |
| 65 | w[0].iter() |
| 66 | .zip(w[1]) |
| 67 | .all(|(a, b)| !Change::between(a, b).both()) |
| 68 | }) |
| 69 | } |
| 70 | |
| 71 | fn valid(keys: &[&[Rect]], cfg: &Config) -> bool { |
| 72 | keys.windows(2).all(|w| phase_ok(w[0], w[1], cfg)) && pure_ok(keys, cfg) |
| 73 | } |
| 74 | |
| 75 | fn conflict_set(from: &[Rect], to: &[Rect], cfg: &Config) -> Vec<usize> { |
| 76 | let n = from.len(); |
| 77 | let mut hit = vec![false; n]; |
| 78 | for i in 0..n { |
| 79 | for j in i + 1..n { |
| 80 | if separation(&from[i], &from[j], cfg.eps) & separation(&to[i], &to[j], cfg.eps) == 0 { |
| 81 | hit[i] = true; |
| 82 | hit[j] = true; |
| 83 | } |
| 84 | } |
| 85 | } |
| 86 | (0..n).filter(|&i| hit[i]).collect() |
| 87 | } |
| 88 | |
| 89 | /// Two phases. Each moving window takes one axis of its target in phase 1 and |
| 90 | /// the other in phase 2. The choice per window is a boolean, every pair forbids |
| 91 | /// some combinations, and the result is a 2-SAT instance. Neighbours that touch |
| 92 | /// at both ends must also touch in the middle keyframe when that is possible. |
| 93 | fn axis_order( |
| 94 | from: &[Rect], |
| 95 | to: &[Rect], |
| 96 | movers: &[usize], |
| 97 | cfg: &Config, |
| 98 | ) -> Option<(Vec<Rect>, bool)> { |
| 99 | let n = from.len(); |
| 100 | let mut var = vec![None; n]; |
| 101 | for (v, &i) in movers.iter().enumerate() { |
| 102 | var[i] = Some(v); |
| 103 | } |
| 104 | let options = |i: usize| -> Vec<(Option<bool>, Rect)> { |
| 105 | if var[i].is_some() { |
| 106 | vec![ |
| 107 | (Some(false), Rect::mixed(&from[i], &to[i])), |
| 108 | (Some(true), Rect::mixed(&to[i], &from[i])), |
| 109 | ] |
| 110 | } else { |
| 111 | vec![(None, from[i])] |
| 112 | } |
| 113 | }; |
| 114 | let preferred: Vec<bool> = movers |
| 115 | .iter() |
| 116 | .map(|&i| { |
| 117 | let c = Change::between(&from[i], &to[i]); |
| 118 | c.x && !c.y |
| 119 | }) |
| 120 | .collect(); |
| 121 | for keep_edges in [true, false] { |
| 122 | let mut sat = TwoSat::new(movers.len()); |
| 123 | let mut impossible = false; |
| 124 | for i in 0..n { |
| 125 | for j in i + 1..n { |
| 126 | if var[i].is_none() && var[j].is_none() { |
| 127 | continue; |
| 128 | } |
| 129 | let sf = separation(&from[i], &from[j], cfg.eps); |
| 130 | let st = separation(&to[i], &to[j], cfg.eps); |
| 131 | let coupled = adjacency(&from[i], &from[j], cfg.gap, cfg.eps) |
| 132 | & adjacency(&to[i], &to[j], cfg.gap, cfg.eps); |
| 133 | for (ci, ri) in options(i) { |
| 134 | for (cj, rj) in options(j) { |
| 135 | let s = separation(&ri, &rj, cfg.eps); |
| 136 | let held = !keep_edges |
| 137 | || adjacency(&ri, &rj, cfg.gap, cfg.eps) & coupled == coupled; |
| 138 | if sf & s != 0 && s & st != 0 && held { |
| 139 | continue; |
| 140 | } |
| 141 | match (ci, cj) { |
| 142 | (Some(a), Some(b)) => { |
| 143 | sat.either(Lit::new(var[i]?, !a), Lit::new(var[j]?, !b)) |
| 144 | } |
| 145 | (Some(a), None) => sat.require(Lit::new(var[i]?, !a)), |
| 146 | (None, Some(b)) => sat.require(Lit::new(var[j]?, !b)), |
| 147 | (None, None) => impossible = true, |
| 148 | } |
| 149 | } |
| 150 | } |
| 151 | } |
| 152 | } |
| 153 | if impossible { |
| 154 | continue; |
| 155 | } |
| 156 | if let Some(choice) = sat.solve_preferring(&preferred) { |
| 157 | let mut k1 = from.to_vec(); |
| 158 | for (v, &i) in movers.iter().enumerate() { |
| 159 | k1[i] = if choice[v] { |
| 160 | Rect::mixed(&to[i], &from[i]) |
| 161 | } else { |
| 162 | Rect::mixed(&from[i], &to[i]) |
| 163 | }; |
| 164 | } |
| 165 | let hole = opens_hole(from, to, &k1, cfg); |
| 166 | return Some((k1, hole)); |
| 167 | } |
| 168 | } |
| 169 | None |
| 170 | } |
| 171 | |
| 172 | fn opens_hole(from: &[Rect], to: &[Rect], mid: &[Rect], cfg: &Config) -> bool { |
| 173 | let n = from.len(); |
| 174 | (0..n).any(|i| { |
| 175 | (i + 1..n).any(|j| { |
| 176 | let coupled = adjacency(&from[i], &from[j], cfg.gap, cfg.eps) |
| 177 | & adjacency(&to[i], &to[j], cfg.gap, cfg.eps); |
| 178 | adjacency(&mid[i], &mid[j], cfg.gap, cfg.eps) & coupled != coupled |
| 179 | }) |
| 180 | }) |
| 181 | } |
| 182 | |
| 183 | /// Three phases. Windows that pass each other shrink across the axis of travel |
| 184 | /// into separate lanes, slide, then expand. Lanes span only the band the |
| 185 | /// involved windows occupy. |
| 186 | fn lanes( |
| 187 | from: &[Rect], |
| 188 | to: &[Rect], |
| 189 | movers: &[usize], |
| 190 | axis: Axis, |
| 191 | cfg: &Config, |
| 192 | ) -> Option<(Vec<Rect>, Vec<Rect>, usize)> { |
| 193 | let n = from.len(); |
| 194 | let (travel, before) = match axis { |
| 195 | Axis::Y => (X_BITS, ABOVE), |
| 196 | Axis::X => (Y_BITS, LEFT), |
| 197 | }; |
| 198 | let span = |r: &Rect| match axis { |
| 199 | Axis::Y => (r.y, r.bottom()), |
| 200 | Axis::X => (r.x, r.right()), |
| 201 | }; |
| 202 | for set in [ |
| 203 | conflict_set(from, to, cfg), |
| 204 | movers.to_vec(), |
| 205 | (0..n).collect(), |
| 206 | ] { |
| 207 | let m = set.len(); |
| 208 | if m < 2 { |
| 209 | continue; |
| 210 | } |
| 211 | let (mut lo, mut hi) = (f64::INFINITY, f64::NEG_INFINITY); |
| 212 | for &i in &set { |
| 213 | for r in [&from[i], &to[i]] { |
| 214 | let (a, b) = span(r); |
| 215 | lo = lo.min(a); |
| 216 | hi = hi.max(b); |
| 217 | } |
| 218 | } |
| 219 | let mut diff = vec![vec![false; m]; m]; |
| 220 | let mut lt = vec![vec![false; m]; m]; |
| 221 | for a in 0..m { |
| 222 | for b in 0..m { |
| 223 | if a == b { |
| 224 | continue; |
| 225 | } |
| 226 | let f = separation(&from[set[a]], &from[set[b]], cfg.eps); |
| 227 | let t = separation(&to[set[a]], &to[set[b]], cfg.eps); |
| 228 | diff[a][b] = f & t & travel == 0; |
| 229 | lt[a][b] = [f, t].iter().any(|r| r & travel == 0 && r & before != 0); |
| 230 | } |
| 231 | } |
| 232 | let in_set: Vec<Option<usize>> = (0..n).map(|i| set.iter().position(|&s| s == i)).collect(); |
| 233 | for k in 2..=m { |
| 234 | let size = (hi - lo - (k - 1) as f64 * cfg.gap) / k as f64; |
| 235 | if size < cfg.min_lane { |
| 236 | break; |
| 237 | } |
| 238 | let mut lane = vec![usize::MAX; m]; |
| 239 | let mut budget = LANE_SEARCH_BUDGET; |
| 240 | if !assign_lanes(0, k, &mut lane, &diff, <, &mut budget) { |
| 241 | continue; |
| 242 | } |
| 243 | let strip = |l: usize| lo + l as f64 * (size + cfg.gap); |
| 244 | let in_lane = |r: &Rect, l: usize| match axis { |
| 245 | Axis::Y => Rect::new(r.x, strip(l), r.w, size), |
| 246 | Axis::X => Rect::new(strip(l), r.y, size, r.h), |
| 247 | }; |
| 248 | for phase in [2, 1, 3] { |
| 249 | let mut k1 = Vec::with_capacity(n); |
| 250 | let mut k2 = Vec::with_capacity(n); |
| 251 | for i in 0..n { |
| 252 | let (f, t) = (from[i], to[i]); |
| 253 | let (a, b) = match (in_set[i], phase) { |
| 254 | (Some(s), _) => (in_lane(&f, lane[s]), in_lane(&t, lane[s])), |
| 255 | (None, 1) => (t, t), |
| 256 | (None, 2) => (f, t), |
| 257 | (None, _) => (f, f), |
| 258 | }; |
| 259 | k1.push(a); |
| 260 | k2.push(b); |
| 261 | } |
| 262 | if valid(&[from, &k1, &k2, to], cfg) { |
| 263 | return Some((k1, k2, k)); |
| 264 | } |
| 265 | } |
| 266 | } |
| 267 | } |
| 268 | None |
| 269 | } |
| 270 | |
| 271 | fn assign_lanes( |
| 272 | i: usize, |
| 273 | k: usize, |
| 274 | lane: &mut [usize], |
| 275 | diff: &[Vec<bool>], |
| 276 | lt: &[Vec<bool>], |
| 277 | budget: &mut usize, |
| 278 | ) -> bool { |
| 279 | if i == lane.len() { |
| 280 | return true; |
| 281 | } |
| 282 | for l in 0..k { |
| 283 | if *budget == 0 { |
| 284 | return false; |
| 285 | } |
| 286 | *budget -= 1; |
| 287 | let fits = (0..i).all(|j| { |
| 288 | !(diff[i][j] && lane[j] == l) |
| 289 | && !(lt[i][j] && l >= lane[j]) |
| 290 | && !(lt[j][i] && lane[j] >= l) |
| 291 | }); |
| 292 | if fits { |
| 293 | lane[i] = l; |
| 294 | if assign_lanes(i + 1, k, lane, diff, lt, budget) { |
| 295 | return true; |
| 296 | } |
| 297 | lane[i] = usize::MAX; |
| 298 | } |
| 299 | } |
| 300 | false |
| 301 | } |
| 302 | |
| 303 | /// Four phases that work for any input. Involved windows shrink into rows |
| 304 | /// ordered by where they start, then into columns ordered by where they end, |
| 305 | /// then move vertically to their target, then horizontally. |
| 306 | fn grid( |
| 307 | from: &[Rect], |
| 308 | to: &[Rect], |
| 309 | movers: &[usize], |
| 310 | cfg: &Config, |
| 311 | ) -> Option<(Vec<Vec<Rect>>, usize)> { |
| 312 | let n = from.len(); |
| 313 | for set in [ |
| 314 | conflict_set(from, to, cfg), |
| 315 | movers.to_vec(), |
| 316 | (0..n).collect(), |
| 317 | ] { |
| 318 | let m = set.len(); |
| 319 | if m < 2 { |
| 320 | continue; |
| 321 | } |
| 322 | let area = Rect::bounding(set.iter().flat_map(|&i| [&from[i], &to[i]])); |
| 323 | let gap = |len: f64| { |
| 324 | if len - (m - 1) as f64 * cfg.gap > m as f64 { |
| 325 | cfg.gap |
| 326 | } else { |
| 327 | 0.0 |
| 328 | } |
| 329 | }; |
| 330 | let (gh, gw) = (gap(area.h), gap(area.w)); |
| 331 | let sh = (area.h - (m - 1) as f64 * gh) / m as f64; |
| 332 | let sw = (area.w - (m - 1) as f64 * gw) / m as f64; |
| 333 | let mut by_row = set.clone(); |
| 334 | by_row.sort_by(|&a, &b| { |
| 335 | from[a] |
| 336 | .center_y() |
| 337 | .total_cmp(&from[b].center_y()) |
| 338 | .then(from[a].center_x().total_cmp(&from[b].center_x())) |
| 339 | }); |
| 340 | let mut by_col = set.clone(); |
| 341 | by_col.sort_by(|&a, &b| { |
| 342 | to[a] |
| 343 | .center_x() |
| 344 | .total_cmp(&to[b].center_x()) |
| 345 | .then(to[a].center_y().total_cmp(&to[b].center_y())) |
| 346 | }); |
| 347 | let mut row = vec![0.0; n]; |
| 348 | let mut col = vec![0.0; n]; |
| 349 | for (r, &i) in by_row.iter().enumerate() { |
| 350 | row[i] = area.y + r as f64 * (sh + gh); |
| 351 | } |
| 352 | for (c, &i) in by_col.iter().enumerate() { |
| 353 | col[i] = area.x + c as f64 * (sw + gw); |
| 354 | } |
| 355 | let in_set: Vec<bool> = (0..n).map(|i| set.contains(&i)).collect(); |
| 356 | for phase in [3, 2, 4, 1] { |
| 357 | let mut keys = vec![ |
| 358 | from.to_vec(), |
| 359 | Vec::new(), |
| 360 | Vec::new(), |
| 361 | Vec::new(), |
| 362 | to.to_vec(), |
| 363 | ]; |
| 364 | for i in 0..n { |
| 365 | let (f, t) = (from[i], to[i]); |
| 366 | let mid = if in_set[i] { |
| 367 | [ |
| 368 | Rect::new(f.x, row[i], f.w, sh), |
| 369 | Rect::new(col[i], row[i], sw, sh), |
| 370 | Rect::new(col[i], t.y, sw, t.h), |
| 371 | ] |
| 372 | } else { |
| 373 | [1, 2, 3].map(|k| if k >= phase { t } else { f }) |
| 374 | }; |
| 375 | for (k, r) in mid.into_iter().enumerate() { |
| 376 | keys[k + 1].push(r); |
| 377 | } |
| 378 | } |
| 379 | let refs: Vec<&[Rect]> = keys.iter().map(|k| k.as_slice()).collect(); |
| 380 | if valid(&refs, cfg) { |
| 381 | return Some((keys, m)); |
| 382 | } |
| 383 | } |
| 384 | } |
| 385 | None |
| 386 | } |
| 387 | |
| 388 | /// Safety net. Movers shrink to a point, travel invisibly, and regrow. |
| 389 | fn pinch(from: &[Rect], to: &[Rect], movers: &[usize]) -> Vec<Vec<Rect>> { |
| 390 | let mut k1 = from.to_vec(); |
| 391 | let mut k2 = to.to_vec(); |
| 392 | for &i in movers { |
| 393 | k1[i] = Rect::new(from[i].center_x(), from[i].center_y(), 0.0, 0.0); |
| 394 | k2[i] = Rect::new(to[i].center_x(), to[i].center_y(), 0.0, 0.0); |
| 395 | } |
| 396 | vec![from.to_vec(), k1, k2, to.to_vec()] |
| 397 | } |