diff options
Diffstat (limited to 'src/sim/lib')
| -rw-r--r-- | src/sim/lib/marching_squares.rs | 201 | ||||
| -rw-r--r-- | src/sim/lib/mod.rs | 1 |
2 files changed, 202 insertions, 0 deletions
diff --git a/src/sim/lib/marching_squares.rs b/src/sim/lib/marching_squares.rs new file mode 100644 index 0000000..41d50ee --- /dev/null +++ b/src/sim/lib/marching_squares.rs @@ -0,0 +1,201 @@ +use glam::Vec2; + +/** +0b(tl)(tr)(br)(bl), 0..=15 + +0 0000 - - + +1 0001 BL S → W + +2 0010 BR E → S + +3 0011 BL BR E → W + +4 0100 TR N → E + +5 0101 TR BL saddle: N → W, S → E + +6 0110 TR BR N → S + +7 0111 TR BR BL N → W + +8 1000 TL W → N + +9 1001 TL BL S → N + +10 1010 TL BR saddle: E → N, W → S + +11 1011 TL BR BL E → N + +12 1100 TL TR W → E + +13 1101 TL TR BL S → E + +14 1110 TL TR BR W → S + +15 1111 - - +*/ + +#[inline] +fn derive_type(tl: bool, tr: bool, br: bool, bl: bool) -> usize { + bl as usize | (br as usize) << 1 | (tr as usize) << 2 | (tl as usize) << 3 +} + +pub trait Marchable { + fn occupied(&self, x: i32, y: i32) -> bool; +} + +pub fn compute_types(marchable: &impl Marchable, w: i32, h: i32) -> Vec<u8> { + // TODO could pre-allocate size + let mut types = Vec::new(); + for y in -1..h { + // TODO precompute per column + for x in -1..w { + let tl = marchable.occupied(x, y); + let tr = marchable.occupied(x + 1, y); + let br = marchable.occupied(x + 1, y + 1); + let bl = marchable.occupied(x, y + 1); + types.push(derive_type(tl, tr, br, bl) as u8); + } + } + types +} + +#[derive(PartialEq, Eq, Clone, Copy)] +enum Side { + None, + N, + E, + S, + W, +} + +const EDGE_COUNT_BY_TYPE: [usize; 16] = [0, 1, 1, 1, 1, 2, 1, 1, 1, 1, 2, 1, 1, 1, 1, 0]; +const EDGE_START_BY_TYPE_BY_IDX: [[Side; 2]; 16] = [ + [Side::None, Side::None], + [Side::S, Side::None], + [Side::E, Side::None], + [Side::E, Side::None], + [Side::N, Side::None], + [Side::N, Side::S], + [Side::N, Side::None], + [Side::N, Side::None], + [Side::W, Side::None], + [Side::S, Side::None], + [Side::E, Side::W], + [Side::E, Side::None], + [Side::W, Side::None], + [Side::S, Side::None], + [Side::W, Side::None], + [Side::None, Side::None], +]; + +const EDGE_END_BY_TYPE: [[Side; 2]; 16] = [ + [Side::None, Side::None], + [Side::W, Side::None], + [Side::S, Side::None], + [Side::W, Side::None], + [Side::E, Side::None], + [Side::W, Side::E], + [Side::S, Side::None], + [Side::W, Side::None], + [Side::N, Side::None], + [Side::N, Side::None], + [Side::N, Side::S], + [Side::N, Side::None], + [Side::E, Side::None], + [Side::E, Side::None], + [Side::S, Side::None], + [Side::None, Side::None], +]; + +fn side_centre(x: i32, y: i32, s: Side) -> Vec2 { + let (x, y) = (x as f32, y as f32); + match s { + Side::N => Vec2::new(x + 0.5, y), + Side::E => Vec2::new(x + 1.0, y + 0.5), + Side::S => Vec2::new(x + 0.5, y + 1.0), + Side::W => Vec2::new(x, y + 0.5), + Side::None => panic!("Tried to access None side"), + } +} + +fn toward_side(x: i32, y: i32, exit: Side) -> (i32, i32, Side) { + match exit { + Side::N => (x, y - 1, Side::S), + Side::E => (x + 1, y, Side::W), + Side::S => (x, y + 1, Side::N), + Side::W => (x - 1, y, Side::E), + Side::None => panic!("Tried to access None side"), + } +} + +// outer is cw, inner ccw +pub fn marching_squares_vertex_trace(marchable: &impl Marchable, w: i32, h: i32) -> Vec<Vec<Vec2>> { + let mut visited = vec![0u8; ((w + 1) * (h + 1)) as usize]; + let idx = |cx: i32, cy: i32| (((cy + 1) * (w + 1)) + (cx + 1)) as usize; + + let types = compute_types(marchable, w, h); + let mut polys = Vec::new(); + + for y in -1..h { + for x in -1..w { + let mut t = types[(x + 1 + (y + 1) * (w + 1)) as usize] as usize; + // if there are multiple edges for this type (saddle), try to build a poly for each + for e in 0..EDGE_COUNT_BY_TYPE[t] { + // if we have already visited this cell FOR this edge, skip + if visited[idx(x, y)] & (1 << e) != 0 { + continue; + } + + let mut poly = Vec::new(); + let (mut xi, mut yi, mut ei) = (x, y, e); + // keep collecting until we don't connect to an edge + loop { + // if we have already visited this cell FOR this edge, skip + if visited[idx(xi, yi)] & (1 << ei) != 0 { + break; + } + // set this on the inner loop since every cell we take on the loop is claimed + visited[idx(xi, yi)] |= 1 << ei; + + // this edge starts and ends against some side of our cell + let (start, end) = (EDGE_START_BY_TYPE_BY_IDX[t][ei], EDGE_END_BY_TYPE[t][ei]); + poly.push(side_centre(xi, yi, start)); + + // move ourselves into the cell that our edge ends in, unless it's out of the grid + let (nx, ny, entry) = toward_side(xi, yi, end); + // TODO is equality cheaper? + if nx < -1 || nx >= w || ny < -1 || ny >= h { + // exited the board + panic!( + "Expecting closed loop but it's not (off the board)! Came from ({xi}, {yi}, {ei}) to ({nx}, {ny})" + ) + } + + let nt = types[(nx + 1 + (ny + 1) * (w + 1)) as usize] as usize; + + if EDGE_START_BY_TYPE_BY_IDX[nt][0] == entry { + // there's an edge starting where we entered + xi = nx; + yi = ny; + ei = 0; + t = nt; + } else if EDGE_START_BY_TYPE_BY_IDX[nt][1] == entry { + // entering the other side of the saddle + xi = nx; + yi = ny; + ei = 1; + t = nt; + } else { + panic!( + "Expecting closed loop but it's not! Came from ({xi}, {yi}, {ei}) to ({nx}, {ny})" + ) + } + } + polys.push(poly); + } + } + } + polys +} diff --git a/src/sim/lib/mod.rs b/src/sim/lib/mod.rs new file mode 100644 index 0000000..1d802dc --- /dev/null +++ b/src/sim/lib/mod.rs @@ -0,0 +1 @@ +pub mod marching_squares; |