# HG changeset patch
# User alfadur
# Date 1553301851 -10800
# Node ID 16024046d4583504ed080b1ab06dfad35d0a98b6
# Parent  8e74d4eb89f584220a40ef85474e561e5baa156d
rescue the atlas

diff -r 8e74d4eb89f5 -r 16024046d458 rust/integral-geometry/src/lib.rs
--- a/rust/integral-geometry/src/lib.rs	Sat Mar 23 01:07:23 2019 +0300
+++ b/rust/integral-geometry/src/lib.rs	Sat Mar 23 03:44:11 2019 +0300
@@ -109,6 +109,8 @@
 }
 
 impl Size {
+    pub const EMPTY: Self = Self::square(0);
+
     #[inline]
     pub const fn new(width: usize, height: usize) -> Self {
         Self { width, height }
@@ -163,6 +165,11 @@
     pub fn to_grid_index(&self) -> GridIndex {
         GridIndex::new(*self)
     }
+
+    #[inline]
+    pub fn contains(&self, other: Self) -> bool {
+        self.width >= other.width && self.height >= other.height
+    }
 }
 
 #[derive(PartialEq, Eq, Clone, Copy, Debug)]
@@ -302,6 +309,11 @@
 }
 
 impl Rect {
+    pub const EMPTY: Self = Self {
+        top_left: Point::ZERO,
+        bottom_right: Point::ZERO,
+    };
+
     #[inline]
     pub fn new(top_left: Point, bottom_right: Point) -> Self {
         debug_assert!(top_left.x <= bottom_right.x + 1);
@@ -416,6 +428,11 @@
     }
 
     #[inline]
+    pub fn contains_rect(&self, other: &Self) -> bool {
+        self.contains(other.top_left()) && self.contains(other.bottom_right())
+    }
+
+    #[inline]
     pub fn intersects(&self, other: &Rect) -> bool {
         self.left() <= self.right()
             && self.right() >= other.left()
@@ -435,6 +452,16 @@
     }
 
     #[inline]
+    pub fn with_margins(&self, left: i32, right: i32, top: i32, bottom: i32) -> Self {
+        Self::from_box(
+            self.left() + left,
+            self.right() + right,
+            self.top() + top,
+            self.bottom() + bottom,
+        )
+    }
+
+    #[inline]
     pub fn quotient(self, x: usize, y: usize) -> Point {
         self.top_left() + Point::new((x % self.width()) as i32, (y % self.height()) as i32)
     }
diff -r 8e74d4eb89f5 -r 16024046d458 rust/lib-hedgewars-engine/src/render.rs
--- a/rust/lib-hedgewars-engine/src/render.rs	Sat Mar 23 01:07:23 2019 +0300
+++ b/rust/lib-hedgewars-engine/src/render.rs	Sat Mar 23 03:44:11 2019 +0300
@@ -1,3 +1,4 @@
+pub mod atlas;
 pub mod camera;
 mod gl;
 mod map;
diff -r 8e74d4eb89f5 -r 16024046d458 rust/lib-hedgewars-engine/src/render/atlas.rs
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/rust/lib-hedgewars-engine/src/render/atlas.rs	Sat Mar 23 03:44:11 2019 +0300
@@ -0,0 +1,163 @@
+use integral_geometry::{Rect, Size};
+use std::cmp::{max, min, Ordering};
+
+pub struct Atlas {
+    size: Size,
+    free_rects: Vec<Rect>,
+    used_rects: Vec<Rect>,
+}
+
+#[derive(PartialEq, Eq, PartialOrd, Ord)]
+struct Fit {
+    short_size: u32,
+    long_size: u32,
+}
+
+impl Fit {
+    fn new() -> Self {
+        Self {
+            short_size: u32::max_value(),
+            long_size: u32::max_value(),
+        }
+    }
+
+    fn measure(container: Size, size: Size) -> Option<Self> {
+        if container.contains(size) {
+            let x_leftover = container.width - size.width;
+            let y_leftover = container.height - size.height;
+            Some(Self {
+                short_size: min(x_leftover, y_leftover) as u32,
+                long_size: max(x_leftover, y_leftover) as u32,
+            })
+        } else {
+            None
+        }
+    }
+}
+
+fn split_rect(free_rect: Rect, rect: Rect) -> Vec<Rect> {
+    let mut result = vec![];
+    if free_rect.intersects(&rect) {
+        if rect.left() > free_rect.left() {
+            let trim = free_rect.right() - rect.left() + 1;
+            result.push(free_rect.with_margins(0, -trim, 0, 0))
+        }
+        if rect.right() < free_rect.right() {
+            let trim = rect.right() - free_rect.left() + 1;
+            result.push(free_rect.with_margins(-trim, 0, 0, 0))
+        }
+        if rect.top() > free_rect.top() {
+            let trim = free_rect.bottom() - rect.top() + 1;
+            result.push(free_rect.with_margins(0, 0, 0, -trim));
+        }
+        if rect.bottom() < free_rect.bottom() {
+            let trim = rect.bottom() - free_rect.top() + 1;
+            result.push(free_rect.with_margins(0, 0, -trim, 0));
+        }
+    }
+    result
+}
+
+impl Atlas {
+    pub fn new(size: Size) -> Self {
+        Self {
+            size,
+            free_rects: vec![Rect::at_origin(size)],
+            used_rects: vec![],
+        }
+    }
+
+    fn find_position(&self, size: Size) -> Option<(Rect, Fit)> {
+        let mut best_rect = Rect::EMPTY;
+        let mut best_fit = Fit::new();
+
+        for rect in &self.free_rects {
+            if let Some(fit) = Fit::measure(rect.size(), size) {
+                if fit < best_fit {
+                    best_fit = fit;
+                    best_rect = Rect::from_size(rect.top_left(), size);
+                }
+            }
+
+            if let Some(fit) = Fit::measure(rect.size(), size.transpose()) {
+                if fit < best_fit {
+                    best_fit = fit;
+                    best_rect = Rect::from_size(rect.top_left(), size.transpose());
+                }
+            }
+        }
+
+        if best_rect == Rect::EMPTY {
+            None
+        } else {
+            Some((best_rect, best_fit))
+        }
+    }
+
+    fn prune(&mut self) {
+        self.free_rects = self
+            .free_rects
+            .iter()
+            .filter(|inner| {
+                self.free_rects
+                    .iter()
+                    .all(|outer| outer == *inner || !outer.contains_rect(inner))
+            })
+            .cloned()
+            .collect();
+    }
+
+    pub fn insert_adaptive(&mut self, size: Size) -> Option<Rect> {
+        let (rect, fit) = self.find_position(size)?;
+
+        let mut rects_to_process = self.free_rects.len();
+        let mut i = 0;
+
+        while i < rects_to_process {
+            let rects = split_rect(self.free_rects[i], rect);
+            if !rects.is_empty() {
+                self.free_rects.remove(i);
+                self.free_rects.extend(rects);
+                rects_to_process -= 1
+            } else {
+                i += 1;
+            }
+        }
+
+        self.used_rects.push(rect);
+        self.prune();
+        Some(rect)
+    }
+
+    pub fn insert_set<Iter>(&mut self, sizes: Iter) -> Vec<Rect>
+    where
+        Iter: Iterator<Item = Size>,
+    {
+        unimplemented!()
+    }
+
+    pub fn reset(&mut self) {
+        self.free_rects.clear();
+        self.used_rects.clear();
+        self.free_rects.push(Rect::at_origin(self.size));
+    }
+}
+
+#[cfg(test)]
+mod tests {
+    use super::Atlas;
+    use integral_geometry::{Rect, Size};
+
+    #[test]
+    fn insert() {
+        let atlas_size = Size::square(16);
+        let mut atlas = Atlas::new(atlas_size);
+
+        assert_eq!(None, atlas.insert_adaptive(Size::square(20)));
+
+        let rect_size = Size::new(11, 3);
+        let rect = atlas.insert_adaptive(rect_size).unwrap();
+        assert_eq!(rect, Rect::at_origin(rect_size));
+        assert_eq!(2, atlas.free_rects.len());
+    }
+}