rust/lib-hedgewars-engine/src/render/atlas.rs
author alfadur
Thu, 28 Mar 2019 00:33:36 +0300
changeset 14728 069291842d52
parent 14727 2cc36cb1c258
child 14743 731c8406bff0
permissions -rw-r--r--
fix atlas.insert_set
Ignore whitespace changes - Everywhere: Within whitespace: At end of lines:
14717
16024046d458 rescue the atlas
alfadur
parents:
diff changeset
     1
use integral_geometry::{Rect, Size};
16024046d458 rescue the atlas
alfadur
parents:
diff changeset
     2
use std::cmp::{max, min, Ordering};
16024046d458 rescue the atlas
alfadur
parents:
diff changeset
     3
14720
b110cbe52e51 save more of the atlas
alfadur
parents: 14717
diff changeset
     4
#[derive(PartialEq, Eq, PartialOrd, Ord, Clone)]
14717
16024046d458 rescue the atlas
alfadur
parents:
diff changeset
     5
struct Fit {
14725
19d30d96d7d6 fix atlas.insert
alfadur
parents: 14723
diff changeset
     6
    short_side: u32,
19d30d96d7d6 fix atlas.insert
alfadur
parents: 14723
diff changeset
     7
    long_side: u32,
14717
16024046d458 rescue the atlas
alfadur
parents:
diff changeset
     8
}
16024046d458 rescue the atlas
alfadur
parents:
diff changeset
     9
16024046d458 rescue the atlas
alfadur
parents:
diff changeset
    10
impl Fit {
16024046d458 rescue the atlas
alfadur
parents:
diff changeset
    11
    fn new() -> Self {
16024046d458 rescue the atlas
alfadur
parents:
diff changeset
    12
        Self {
14725
19d30d96d7d6 fix atlas.insert
alfadur
parents: 14723
diff changeset
    13
            short_side: u32::max_value(),
19d30d96d7d6 fix atlas.insert
alfadur
parents: 14723
diff changeset
    14
            long_side: u32::max_value(),
14717
16024046d458 rescue the atlas
alfadur
parents:
diff changeset
    15
        }
16024046d458 rescue the atlas
alfadur
parents:
diff changeset
    16
    }
16024046d458 rescue the atlas
alfadur
parents:
diff changeset
    17
16024046d458 rescue the atlas
alfadur
parents:
diff changeset
    18
    fn measure(container: Size, size: Size) -> Option<Self> {
16024046d458 rescue the atlas
alfadur
parents:
diff changeset
    19
        if container.contains(size) {
16024046d458 rescue the atlas
alfadur
parents:
diff changeset
    20
            let x_leftover = container.width - size.width;
16024046d458 rescue the atlas
alfadur
parents:
diff changeset
    21
            let y_leftover = container.height - size.height;
16024046d458 rescue the atlas
alfadur
parents:
diff changeset
    22
            Some(Self {
14725
19d30d96d7d6 fix atlas.insert
alfadur
parents: 14723
diff changeset
    23
                short_side: min(x_leftover, y_leftover) as u32,
19d30d96d7d6 fix atlas.insert
alfadur
parents: 14723
diff changeset
    24
                long_side: max(x_leftover, y_leftover) as u32,
14717
16024046d458 rescue the atlas
alfadur
parents:
diff changeset
    25
            })
16024046d458 rescue the atlas
alfadur
parents:
diff changeset
    26
        } else {
16024046d458 rescue the atlas
alfadur
parents:
diff changeset
    27
            None
16024046d458 rescue the atlas
alfadur
parents:
diff changeset
    28
        }
16024046d458 rescue the atlas
alfadur
parents:
diff changeset
    29
    }
16024046d458 rescue the atlas
alfadur
parents:
diff changeset
    30
}
16024046d458 rescue the atlas
alfadur
parents:
diff changeset
    31
14726
75ff5c643004 actually atlas tests were also broken
alfadur
parents: 14725
diff changeset
    32
#[derive(PartialEq, Eq)]
75ff5c643004 actually atlas tests were also broken
alfadur
parents: 14725
diff changeset
    33
pub struct UsedSpace {
75ff5c643004 actually atlas tests were also broken
alfadur
parents: 14725
diff changeset
    34
    used_area: usize,
75ff5c643004 actually atlas tests were also broken
alfadur
parents: 14725
diff changeset
    35
    total_area: usize,
75ff5c643004 actually atlas tests were also broken
alfadur
parents: 14725
diff changeset
    36
}
75ff5c643004 actually atlas tests were also broken
alfadur
parents: 14725
diff changeset
    37
75ff5c643004 actually atlas tests were also broken
alfadur
parents: 14725
diff changeset
    38
impl UsedSpace {
75ff5c643004 actually atlas tests were also broken
alfadur
parents: 14725
diff changeset
    39
    const fn new(used_area: usize, total_area: usize) -> Self {
75ff5c643004 actually atlas tests were also broken
alfadur
parents: 14725
diff changeset
    40
        Self {
75ff5c643004 actually atlas tests were also broken
alfadur
parents: 14725
diff changeset
    41
            used_area,
75ff5c643004 actually atlas tests were also broken
alfadur
parents: 14725
diff changeset
    42
            total_area,
75ff5c643004 actually atlas tests were also broken
alfadur
parents: 14725
diff changeset
    43
        }
75ff5c643004 actually atlas tests were also broken
alfadur
parents: 14725
diff changeset
    44
    }
75ff5c643004 actually atlas tests were also broken
alfadur
parents: 14725
diff changeset
    45
75ff5c643004 actually atlas tests were also broken
alfadur
parents: 14725
diff changeset
    46
    const fn used(&self) -> usize {
75ff5c643004 actually atlas tests were also broken
alfadur
parents: 14725
diff changeset
    47
        self.used_area
75ff5c643004 actually atlas tests were also broken
alfadur
parents: 14725
diff changeset
    48
    }
75ff5c643004 actually atlas tests were also broken
alfadur
parents: 14725
diff changeset
    49
75ff5c643004 actually atlas tests were also broken
alfadur
parents: 14725
diff changeset
    50
    const fn total(&self) -> usize {
75ff5c643004 actually atlas tests were also broken
alfadur
parents: 14725
diff changeset
    51
        self.total_area
75ff5c643004 actually atlas tests were also broken
alfadur
parents: 14725
diff changeset
    52
    }
75ff5c643004 actually atlas tests were also broken
alfadur
parents: 14725
diff changeset
    53
}
75ff5c643004 actually atlas tests were also broken
alfadur
parents: 14725
diff changeset
    54
75ff5c643004 actually atlas tests were also broken
alfadur
parents: 14725
diff changeset
    55
impl std::fmt::Debug for UsedSpace {
75ff5c643004 actually atlas tests were also broken
alfadur
parents: 14725
diff changeset
    56
    fn fmt(&self, f: &mut std::fmt::Formatter) -> Result<(), std::fmt::Error> {
75ff5c643004 actually atlas tests were also broken
alfadur
parents: 14725
diff changeset
    57
        write!(
75ff5c643004 actually atlas tests were also broken
alfadur
parents: 14725
diff changeset
    58
            f,
75ff5c643004 actually atlas tests were also broken
alfadur
parents: 14725
diff changeset
    59
            "{:.2}%",
75ff5c643004 actually atlas tests were also broken
alfadur
parents: 14725
diff changeset
    60
            self.used() as f32 / self.total() as f32 / 100.0
75ff5c643004 actually atlas tests were also broken
alfadur
parents: 14725
diff changeset
    61
        )?;
75ff5c643004 actually atlas tests were also broken
alfadur
parents: 14725
diff changeset
    62
        Ok(())
75ff5c643004 actually atlas tests were also broken
alfadur
parents: 14725
diff changeset
    63
    }
75ff5c643004 actually atlas tests were also broken
alfadur
parents: 14725
diff changeset
    64
}
75ff5c643004 actually atlas tests were also broken
alfadur
parents: 14725
diff changeset
    65
14720
b110cbe52e51 save more of the atlas
alfadur
parents: 14717
diff changeset
    66
pub struct Atlas {
b110cbe52e51 save more of the atlas
alfadur
parents: 14717
diff changeset
    67
    size: Size,
b110cbe52e51 save more of the atlas
alfadur
parents: 14717
diff changeset
    68
    free_rects: Vec<Rect>,
b110cbe52e51 save more of the atlas
alfadur
parents: 14717
diff changeset
    69
    used_rects: Vec<Rect>,
14717
16024046d458 rescue the atlas
alfadur
parents:
diff changeset
    70
}
16024046d458 rescue the atlas
alfadur
parents:
diff changeset
    71
16024046d458 rescue the atlas
alfadur
parents:
diff changeset
    72
impl Atlas {
16024046d458 rescue the atlas
alfadur
parents:
diff changeset
    73
    pub fn new(size: Size) -> Self {
16024046d458 rescue the atlas
alfadur
parents:
diff changeset
    74
        Self {
16024046d458 rescue the atlas
alfadur
parents:
diff changeset
    75
            size,
16024046d458 rescue the atlas
alfadur
parents:
diff changeset
    76
            free_rects: vec![Rect::at_origin(size)],
16024046d458 rescue the atlas
alfadur
parents:
diff changeset
    77
            used_rects: vec![],
16024046d458 rescue the atlas
alfadur
parents:
diff changeset
    78
        }
16024046d458 rescue the atlas
alfadur
parents:
diff changeset
    79
    }
16024046d458 rescue the atlas
alfadur
parents:
diff changeset
    80
14720
b110cbe52e51 save more of the atlas
alfadur
parents: 14717
diff changeset
    81
    pub fn size(&self) -> Size {
b110cbe52e51 save more of the atlas
alfadur
parents: 14717
diff changeset
    82
        self.size
b110cbe52e51 save more of the atlas
alfadur
parents: 14717
diff changeset
    83
    }
b110cbe52e51 save more of the atlas
alfadur
parents: 14717
diff changeset
    84
14726
75ff5c643004 actually atlas tests were also broken
alfadur
parents: 14725
diff changeset
    85
    pub fn used_space(&self) -> UsedSpace {
75ff5c643004 actually atlas tests were also broken
alfadur
parents: 14725
diff changeset
    86
        let used = self.used_rects.iter().map(|r| r.size().area()).sum();
75ff5c643004 actually atlas tests were also broken
alfadur
parents: 14725
diff changeset
    87
        UsedSpace::new(used, self.size.area())
75ff5c643004 actually atlas tests were also broken
alfadur
parents: 14725
diff changeset
    88
    }
75ff5c643004 actually atlas tests were also broken
alfadur
parents: 14725
diff changeset
    89
14717
16024046d458 rescue the atlas
alfadur
parents:
diff changeset
    90
    fn find_position(&self, size: Size) -> Option<(Rect, Fit)> {
16024046d458 rescue the atlas
alfadur
parents:
diff changeset
    91
        let mut best_rect = Rect::EMPTY;
16024046d458 rescue the atlas
alfadur
parents:
diff changeset
    92
        let mut best_fit = Fit::new();
16024046d458 rescue the atlas
alfadur
parents:
diff changeset
    93
16024046d458 rescue the atlas
alfadur
parents:
diff changeset
    94
        for rect in &self.free_rects {
16024046d458 rescue the atlas
alfadur
parents:
diff changeset
    95
            if let Some(fit) = Fit::measure(rect.size(), size) {
16024046d458 rescue the atlas
alfadur
parents:
diff changeset
    96
                if fit < best_fit {
16024046d458 rescue the atlas
alfadur
parents:
diff changeset
    97
                    best_fit = fit;
16024046d458 rescue the atlas
alfadur
parents:
diff changeset
    98
                    best_rect = Rect::from_size(rect.top_left(), size);
16024046d458 rescue the atlas
alfadur
parents:
diff changeset
    99
                }
16024046d458 rescue the atlas
alfadur
parents:
diff changeset
   100
            }
16024046d458 rescue the atlas
alfadur
parents:
diff changeset
   101
16024046d458 rescue the atlas
alfadur
parents:
diff changeset
   102
            if let Some(fit) = Fit::measure(rect.size(), size.transpose()) {
16024046d458 rescue the atlas
alfadur
parents:
diff changeset
   103
                if fit < best_fit {
16024046d458 rescue the atlas
alfadur
parents:
diff changeset
   104
                    best_fit = fit;
16024046d458 rescue the atlas
alfadur
parents:
diff changeset
   105
                    best_rect = Rect::from_size(rect.top_left(), size.transpose());
16024046d458 rescue the atlas
alfadur
parents:
diff changeset
   106
                }
16024046d458 rescue the atlas
alfadur
parents:
diff changeset
   107
            }
16024046d458 rescue the atlas
alfadur
parents:
diff changeset
   108
        }
16024046d458 rescue the atlas
alfadur
parents:
diff changeset
   109
16024046d458 rescue the atlas
alfadur
parents:
diff changeset
   110
        if best_rect == Rect::EMPTY {
16024046d458 rescue the atlas
alfadur
parents:
diff changeset
   111
            None
16024046d458 rescue the atlas
alfadur
parents:
diff changeset
   112
        } else {
16024046d458 rescue the atlas
alfadur
parents:
diff changeset
   113
            Some((best_rect, best_fit))
16024046d458 rescue the atlas
alfadur
parents:
diff changeset
   114
        }
16024046d458 rescue the atlas
alfadur
parents:
diff changeset
   115
    }
16024046d458 rescue the atlas
alfadur
parents:
diff changeset
   116
16024046d458 rescue the atlas
alfadur
parents:
diff changeset
   117
    fn prune(&mut self) {
16024046d458 rescue the atlas
alfadur
parents:
diff changeset
   118
        self.free_rects = self
16024046d458 rescue the atlas
alfadur
parents:
diff changeset
   119
            .free_rects
16024046d458 rescue the atlas
alfadur
parents:
diff changeset
   120
            .iter()
16024046d458 rescue the atlas
alfadur
parents:
diff changeset
   121
            .filter(|inner| {
16024046d458 rescue the atlas
alfadur
parents:
diff changeset
   122
                self.free_rects
16024046d458 rescue the atlas
alfadur
parents:
diff changeset
   123
                    .iter()
16024046d458 rescue the atlas
alfadur
parents:
diff changeset
   124
                    .all(|outer| outer == *inner || !outer.contains_rect(inner))
16024046d458 rescue the atlas
alfadur
parents:
diff changeset
   125
            })
16024046d458 rescue the atlas
alfadur
parents:
diff changeset
   126
            .cloned()
16024046d458 rescue the atlas
alfadur
parents:
diff changeset
   127
            .collect();
16024046d458 rescue the atlas
alfadur
parents:
diff changeset
   128
    }
16024046d458 rescue the atlas
alfadur
parents:
diff changeset
   129
14728
069291842d52 fix atlas.insert_set
alfadur
parents: 14727
diff changeset
   130
    fn split_insert(&mut self, rect: Rect) {
14727
2cc36cb1c258 fix atlas.insert for real this time
alfadur
parents: 14726
diff changeset
   131
        let mut splits = vec![];
14717
16024046d458 rescue the atlas
alfadur
parents:
diff changeset
   132
14727
2cc36cb1c258 fix atlas.insert for real this time
alfadur
parents: 14726
diff changeset
   133
        for i in (0..self.free_rects.len()).rev() {
2cc36cb1c258 fix atlas.insert for real this time
alfadur
parents: 14726
diff changeset
   134
            if split_rect(self.free_rects[i], rect, &mut splits) {
2cc36cb1c258 fix atlas.insert for real this time
alfadur
parents: 14726
diff changeset
   135
                self.free_rects.swap_remove(i as usize);
14717
16024046d458 rescue the atlas
alfadur
parents:
diff changeset
   136
            }
16024046d458 rescue the atlas
alfadur
parents:
diff changeset
   137
        }
14728
069291842d52 fix atlas.insert_set
alfadur
parents: 14727
diff changeset
   138
14727
2cc36cb1c258 fix atlas.insert for real this time
alfadur
parents: 14726
diff changeset
   139
        self.free_rects.extend(splits);
2cc36cb1c258 fix atlas.insert for real this time
alfadur
parents: 14726
diff changeset
   140
        self.prune();
14728
069291842d52 fix atlas.insert_set
alfadur
parents: 14727
diff changeset
   141
        self.used_rects.push(rect);
069291842d52 fix atlas.insert_set
alfadur
parents: 14727
diff changeset
   142
    }
14717
16024046d458 rescue the atlas
alfadur
parents:
diff changeset
   143
14728
069291842d52 fix atlas.insert_set
alfadur
parents: 14727
diff changeset
   144
    pub fn insert(&mut self, size: Size) -> Option<Rect> {
069291842d52 fix atlas.insert_set
alfadur
parents: 14727
diff changeset
   145
        let (rect, _) = self.find_position(size)?;
069291842d52 fix atlas.insert_set
alfadur
parents: 14727
diff changeset
   146
        self.split_insert(rect);
14717
16024046d458 rescue the atlas
alfadur
parents:
diff changeset
   147
        Some(rect)
16024046d458 rescue the atlas
alfadur
parents:
diff changeset
   148
    }
16024046d458 rescue the atlas
alfadur
parents:
diff changeset
   149
16024046d458 rescue the atlas
alfadur
parents:
diff changeset
   150
    pub fn insert_set<Iter>(&mut self, sizes: Iter) -> Vec<Rect>
16024046d458 rescue the atlas
alfadur
parents:
diff changeset
   151
    where
16024046d458 rescue the atlas
alfadur
parents:
diff changeset
   152
        Iter: Iterator<Item = Size>,
16024046d458 rescue the atlas
alfadur
parents:
diff changeset
   153
    {
14720
b110cbe52e51 save more of the atlas
alfadur
parents: 14717
diff changeset
   154
        let mut sizes: Vec<_> = sizes.collect();
b110cbe52e51 save more of the atlas
alfadur
parents: 14717
diff changeset
   155
        let mut result = vec![];
b110cbe52e51 save more of the atlas
alfadur
parents: 14717
diff changeset
   156
b110cbe52e51 save more of the atlas
alfadur
parents: 14717
diff changeset
   157
        while let Some((index, (rect, _))) = sizes
b110cbe52e51 save more of the atlas
alfadur
parents: 14717
diff changeset
   158
            .iter()
b110cbe52e51 save more of the atlas
alfadur
parents: 14717
diff changeset
   159
            .enumerate()
b110cbe52e51 save more of the atlas
alfadur
parents: 14717
diff changeset
   160
            .filter_map(|(i, s)| self.find_position(*s).map(|res| (i, res)))
b110cbe52e51 save more of the atlas
alfadur
parents: 14717
diff changeset
   161
            .min_by_key(|(_, (_, fit))| fit.clone())
b110cbe52e51 save more of the atlas
alfadur
parents: 14717
diff changeset
   162
        {
14728
069291842d52 fix atlas.insert_set
alfadur
parents: 14727
diff changeset
   163
            self.split_insert(rect);
069291842d52 fix atlas.insert_set
alfadur
parents: 14727
diff changeset
   164
14720
b110cbe52e51 save more of the atlas
alfadur
parents: 14717
diff changeset
   165
            result.push(rect);
b110cbe52e51 save more of the atlas
alfadur
parents: 14717
diff changeset
   166
            sizes.swap_remove(index);
b110cbe52e51 save more of the atlas
alfadur
parents: 14717
diff changeset
   167
        }
14728
069291842d52 fix atlas.insert_set
alfadur
parents: 14727
diff changeset
   168
        result
14717
16024046d458 rescue the atlas
alfadur
parents:
diff changeset
   169
    }
16024046d458 rescue the atlas
alfadur
parents:
diff changeset
   170
16024046d458 rescue the atlas
alfadur
parents:
diff changeset
   171
    pub fn reset(&mut self) {
16024046d458 rescue the atlas
alfadur
parents:
diff changeset
   172
        self.free_rects.clear();
16024046d458 rescue the atlas
alfadur
parents:
diff changeset
   173
        self.used_rects.clear();
16024046d458 rescue the atlas
alfadur
parents:
diff changeset
   174
        self.free_rects.push(Rect::at_origin(self.size));
16024046d458 rescue the atlas
alfadur
parents:
diff changeset
   175
    }
16024046d458 rescue the atlas
alfadur
parents:
diff changeset
   176
}
16024046d458 rescue the atlas
alfadur
parents:
diff changeset
   177
14720
b110cbe52e51 save more of the atlas
alfadur
parents: 14717
diff changeset
   178
pub struct AtlasCollection {
b110cbe52e51 save more of the atlas
alfadur
parents: 14717
diff changeset
   179
    texture_size: Size,
b110cbe52e51 save more of the atlas
alfadur
parents: 14717
diff changeset
   180
    atlases: Vec<Atlas>,
b110cbe52e51 save more of the atlas
alfadur
parents: 14717
diff changeset
   181
}
b110cbe52e51 save more of the atlas
alfadur
parents: 14717
diff changeset
   182
b110cbe52e51 save more of the atlas
alfadur
parents: 14717
diff changeset
   183
impl AtlasCollection {
b110cbe52e51 save more of the atlas
alfadur
parents: 14717
diff changeset
   184
    pub fn new(texture_size: Size) -> Self {
b110cbe52e51 save more of the atlas
alfadur
parents: 14717
diff changeset
   185
        Self {
b110cbe52e51 save more of the atlas
alfadur
parents: 14717
diff changeset
   186
            texture_size,
b110cbe52e51 save more of the atlas
alfadur
parents: 14717
diff changeset
   187
            atlases: vec![],
b110cbe52e51 save more of the atlas
alfadur
parents: 14717
diff changeset
   188
        }
b110cbe52e51 save more of the atlas
alfadur
parents: 14717
diff changeset
   189
    }
b110cbe52e51 save more of the atlas
alfadur
parents: 14717
diff changeset
   190
b110cbe52e51 save more of the atlas
alfadur
parents: 14717
diff changeset
   191
    fn repack(&mut self, size: Size) -> bool {
b110cbe52e51 save more of the atlas
alfadur
parents: 14717
diff changeset
   192
        for atlas in &mut self.atlases {
b110cbe52e51 save more of the atlas
alfadur
parents: 14717
diff changeset
   193
            let mut temp_atlas = Atlas::new(atlas.size());
b110cbe52e51 save more of the atlas
alfadur
parents: 14717
diff changeset
   194
            let sizes = atlas
b110cbe52e51 save more of the atlas
alfadur
parents: 14717
diff changeset
   195
                .used_rects
b110cbe52e51 save more of the atlas
alfadur
parents: 14717
diff changeset
   196
                .iter()
b110cbe52e51 save more of the atlas
alfadur
parents: 14717
diff changeset
   197
                .map(|r| r.size())
b110cbe52e51 save more of the atlas
alfadur
parents: 14717
diff changeset
   198
                .chain(std::iter::once(size));
b110cbe52e51 save more of the atlas
alfadur
parents: 14717
diff changeset
   199
            if !temp_atlas.insert_set(sizes).is_empty() {
b110cbe52e51 save more of the atlas
alfadur
parents: 14717
diff changeset
   200
                std::mem::swap(atlas, &mut temp_atlas);
b110cbe52e51 save more of the atlas
alfadur
parents: 14717
diff changeset
   201
                return true;
b110cbe52e51 save more of the atlas
alfadur
parents: 14717
diff changeset
   202
            }
b110cbe52e51 save more of the atlas
alfadur
parents: 14717
diff changeset
   203
        }
b110cbe52e51 save more of the atlas
alfadur
parents: 14717
diff changeset
   204
        false
b110cbe52e51 save more of the atlas
alfadur
parents: 14717
diff changeset
   205
    }
b110cbe52e51 save more of the atlas
alfadur
parents: 14717
diff changeset
   206
b110cbe52e51 save more of the atlas
alfadur
parents: 14717
diff changeset
   207
    pub fn insert_sprite(&mut self, size: Size) -> bool {
b110cbe52e51 save more of the atlas
alfadur
parents: 14717
diff changeset
   208
        if !self.texture_size.contains(size) {
b110cbe52e51 save more of the atlas
alfadur
parents: 14717
diff changeset
   209
            false
b110cbe52e51 save more of the atlas
alfadur
parents: 14717
diff changeset
   210
        } else {
14722
c97faf0aef78 proptest atlas, find 🐛🐜🦋
alfadur
parents: 14720
diff changeset
   211
            if let Some(rect) = self.atlases.iter_mut().find_map(|a| a.insert(size)) {
14720
b110cbe52e51 save more of the atlas
alfadur
parents: 14717
diff changeset
   212
b110cbe52e51 save more of the atlas
alfadur
parents: 14717
diff changeset
   213
            } else if !self.repack(size) {
b110cbe52e51 save more of the atlas
alfadur
parents: 14717
diff changeset
   214
                let mut atlas = Atlas::new(self.texture_size);
b110cbe52e51 save more of the atlas
alfadur
parents: 14717
diff changeset
   215
                atlas.insert(size);
b110cbe52e51 save more of the atlas
alfadur
parents: 14717
diff changeset
   216
                self.atlases.push(atlas);
b110cbe52e51 save more of the atlas
alfadur
parents: 14717
diff changeset
   217
            }
b110cbe52e51 save more of the atlas
alfadur
parents: 14717
diff changeset
   218
            true
b110cbe52e51 save more of the atlas
alfadur
parents: 14717
diff changeset
   219
        }
b110cbe52e51 save more of the atlas
alfadur
parents: 14717
diff changeset
   220
    }
b110cbe52e51 save more of the atlas
alfadur
parents: 14717
diff changeset
   221
}
b110cbe52e51 save more of the atlas
alfadur
parents: 14717
diff changeset
   222
14727
2cc36cb1c258 fix atlas.insert for real this time
alfadur
parents: 14726
diff changeset
   223
fn split_rect(free_rect: Rect, rect: Rect, output: &mut Vec<Rect>) -> bool {
2cc36cb1c258 fix atlas.insert for real this time
alfadur
parents: 14726
diff changeset
   224
    let split = free_rect.intersects(&rect);
2cc36cb1c258 fix atlas.insert for real this time
alfadur
parents: 14726
diff changeset
   225
    if split {
14720
b110cbe52e51 save more of the atlas
alfadur
parents: 14717
diff changeset
   226
        if rect.left() > free_rect.left() {
b110cbe52e51 save more of the atlas
alfadur
parents: 14717
diff changeset
   227
            let trim = free_rect.right() - rect.left() + 1;
14727
2cc36cb1c258 fix atlas.insert for real this time
alfadur
parents: 14726
diff changeset
   228
            output.push(free_rect.with_margins(0, -trim, 0, 0))
14720
b110cbe52e51 save more of the atlas
alfadur
parents: 14717
diff changeset
   229
        }
b110cbe52e51 save more of the atlas
alfadur
parents: 14717
diff changeset
   230
        if rect.right() < free_rect.right() {
b110cbe52e51 save more of the atlas
alfadur
parents: 14717
diff changeset
   231
            let trim = rect.right() - free_rect.left() + 1;
14727
2cc36cb1c258 fix atlas.insert for real this time
alfadur
parents: 14726
diff changeset
   232
            output.push(free_rect.with_margins(-trim, 0, 0, 0))
14720
b110cbe52e51 save more of the atlas
alfadur
parents: 14717
diff changeset
   233
        }
b110cbe52e51 save more of the atlas
alfadur
parents: 14717
diff changeset
   234
        if rect.top() > free_rect.top() {
b110cbe52e51 save more of the atlas
alfadur
parents: 14717
diff changeset
   235
            let trim = free_rect.bottom() - rect.top() + 1;
14727
2cc36cb1c258 fix atlas.insert for real this time
alfadur
parents: 14726
diff changeset
   236
            output.push(free_rect.with_margins(0, 0, 0, -trim));
14720
b110cbe52e51 save more of the atlas
alfadur
parents: 14717
diff changeset
   237
        }
b110cbe52e51 save more of the atlas
alfadur
parents: 14717
diff changeset
   238
        if rect.bottom() < free_rect.bottom() {
b110cbe52e51 save more of the atlas
alfadur
parents: 14717
diff changeset
   239
            let trim = rect.bottom() - free_rect.top() + 1;
14727
2cc36cb1c258 fix atlas.insert for real this time
alfadur
parents: 14726
diff changeset
   240
            output.push(free_rect.with_margins(0, 0, -trim, 0));
14720
b110cbe52e51 save more of the atlas
alfadur
parents: 14717
diff changeset
   241
        }
b110cbe52e51 save more of the atlas
alfadur
parents: 14717
diff changeset
   242
    }
14727
2cc36cb1c258 fix atlas.insert for real this time
alfadur
parents: 14726
diff changeset
   243
    split
14720
b110cbe52e51 save more of the atlas
alfadur
parents: 14717
diff changeset
   244
}
b110cbe52e51 save more of the atlas
alfadur
parents: 14717
diff changeset
   245
14717
16024046d458 rescue the atlas
alfadur
parents:
diff changeset
   246
#[cfg(test)]
16024046d458 rescue the atlas
alfadur
parents:
diff changeset
   247
mod tests {
16024046d458 rescue the atlas
alfadur
parents:
diff changeset
   248
    use super::Atlas;
16024046d458 rescue the atlas
alfadur
parents:
diff changeset
   249
    use integral_geometry::{Rect, Size};
14726
75ff5c643004 actually atlas tests were also broken
alfadur
parents: 14725
diff changeset
   250
    use itertools::Itertools as _;
14722
c97faf0aef78 proptest atlas, find 🐛🐜🦋
alfadur
parents: 14720
diff changeset
   251
    use proptest::prelude::*;
14717
16024046d458 rescue the atlas
alfadur
parents:
diff changeset
   252
16024046d458 rescue the atlas
alfadur
parents:
diff changeset
   253
    #[test]
16024046d458 rescue the atlas
alfadur
parents:
diff changeset
   254
    fn insert() {
16024046d458 rescue the atlas
alfadur
parents:
diff changeset
   255
        let atlas_size = Size::square(16);
16024046d458 rescue the atlas
alfadur
parents:
diff changeset
   256
        let mut atlas = Atlas::new(atlas_size);
16024046d458 rescue the atlas
alfadur
parents:
diff changeset
   257
14720
b110cbe52e51 save more of the atlas
alfadur
parents: 14717
diff changeset
   258
        assert_eq!(None, atlas.insert(Size::square(20)));
14717
16024046d458 rescue the atlas
alfadur
parents:
diff changeset
   259
16024046d458 rescue the atlas
alfadur
parents:
diff changeset
   260
        let rect_size = Size::new(11, 3);
14720
b110cbe52e51 save more of the atlas
alfadur
parents: 14717
diff changeset
   261
        let rect = atlas.insert(rect_size).unwrap();
14723
766ce87dfdfc finetune atlas proptest
alfadur
parents: 14722
diff changeset
   262
14717
16024046d458 rescue the atlas
alfadur
parents:
diff changeset
   263
        assert_eq!(rect, Rect::at_origin(rect_size));
16024046d458 rescue the atlas
alfadur
parents:
diff changeset
   264
        assert_eq!(2, atlas.free_rects.len());
16024046d458 rescue the atlas
alfadur
parents:
diff changeset
   265
    }
14722
c97faf0aef78 proptest atlas, find 🐛🐜🦋
alfadur
parents: 14720
diff changeset
   266
c97faf0aef78 proptest atlas, find 🐛🐜🦋
alfadur
parents: 14720
diff changeset
   267
    #[derive(Debug, Clone)]
c97faf0aef78 proptest atlas, find 🐛🐜🦋
alfadur
parents: 14720
diff changeset
   268
    struct TestRect(Size);
c97faf0aef78 proptest atlas, find 🐛🐜🦋
alfadur
parents: 14720
diff changeset
   269
    struct TestRectParameters(Size);
c97faf0aef78 proptest atlas, find 🐛🐜🦋
alfadur
parents: 14720
diff changeset
   270
c97faf0aef78 proptest atlas, find 🐛🐜🦋
alfadur
parents: 14720
diff changeset
   271
    impl Default for TestRectParameters {
c97faf0aef78 proptest atlas, find 🐛🐜🦋
alfadur
parents: 14720
diff changeset
   272
        fn default() -> Self {
c97faf0aef78 proptest atlas, find 🐛🐜🦋
alfadur
parents: 14720
diff changeset
   273
            Self(Size::square(64))
c97faf0aef78 proptest atlas, find 🐛🐜🦋
alfadur
parents: 14720
diff changeset
   274
        }
c97faf0aef78 proptest atlas, find 🐛🐜🦋
alfadur
parents: 14720
diff changeset
   275
    }
c97faf0aef78 proptest atlas, find 🐛🐜🦋
alfadur
parents: 14720
diff changeset
   276
c97faf0aef78 proptest atlas, find 🐛🐜🦋
alfadur
parents: 14720
diff changeset
   277
    impl Arbitrary for TestRect {
c97faf0aef78 proptest atlas, find 🐛🐜🦋
alfadur
parents: 14720
diff changeset
   278
        type Parameters = TestRectParameters;
c97faf0aef78 proptest atlas, find 🐛🐜🦋
alfadur
parents: 14720
diff changeset
   279
c97faf0aef78 proptest atlas, find 🐛🐜🦋
alfadur
parents: 14720
diff changeset
   280
        fn arbitrary_with(args: Self::Parameters) -> Self::Strategy {
c97faf0aef78 proptest atlas, find 🐛🐜🦋
alfadur
parents: 14720
diff changeset
   281
            (1..=args.0.width, 1..=args.0.height)
c97faf0aef78 proptest atlas, find 🐛🐜🦋
alfadur
parents: 14720
diff changeset
   282
                .prop_map(|(w, h)| TestRect(Size::new(w, h)))
c97faf0aef78 proptest atlas, find 🐛🐜🦋
alfadur
parents: 14720
diff changeset
   283
                .boxed()
c97faf0aef78 proptest atlas, find 🐛🐜🦋
alfadur
parents: 14720
diff changeset
   284
        }
c97faf0aef78 proptest atlas, find 🐛🐜🦋
alfadur
parents: 14720
diff changeset
   285
c97faf0aef78 proptest atlas, find 🐛🐜🦋
alfadur
parents: 14720
diff changeset
   286
        type Strategy = BoxedStrategy<TestRect>;
c97faf0aef78 proptest atlas, find 🐛🐜🦋
alfadur
parents: 14720
diff changeset
   287
    }
c97faf0aef78 proptest atlas, find 🐛🐜🦋
alfadur
parents: 14720
diff changeset
   288
c97faf0aef78 proptest atlas, find 🐛🐜🦋
alfadur
parents: 14720
diff changeset
   289
    trait HasSize {
c97faf0aef78 proptest atlas, find 🐛🐜🦋
alfadur
parents: 14720
diff changeset
   290
        fn size(&self) -> Size;
c97faf0aef78 proptest atlas, find 🐛🐜🦋
alfadur
parents: 14720
diff changeset
   291
    }
c97faf0aef78 proptest atlas, find 🐛🐜🦋
alfadur
parents: 14720
diff changeset
   292
c97faf0aef78 proptest atlas, find 🐛🐜🦋
alfadur
parents: 14720
diff changeset
   293
    impl HasSize for TestRect {
c97faf0aef78 proptest atlas, find 🐛🐜🦋
alfadur
parents: 14720
diff changeset
   294
        fn size(&self) -> Size {
c97faf0aef78 proptest atlas, find 🐛🐜🦋
alfadur
parents: 14720
diff changeset
   295
            self.0
c97faf0aef78 proptest atlas, find 🐛🐜🦋
alfadur
parents: 14720
diff changeset
   296
        }
c97faf0aef78 proptest atlas, find 🐛🐜🦋
alfadur
parents: 14720
diff changeset
   297
    }
c97faf0aef78 proptest atlas, find 🐛🐜🦋
alfadur
parents: 14720
diff changeset
   298
c97faf0aef78 proptest atlas, find 🐛🐜🦋
alfadur
parents: 14720
diff changeset
   299
    impl HasSize for Rect {
c97faf0aef78 proptest atlas, find 🐛🐜🦋
alfadur
parents: 14720
diff changeset
   300
        fn size(&self) -> Size {
c97faf0aef78 proptest atlas, find 🐛🐜🦋
alfadur
parents: 14720
diff changeset
   301
            self.size()
c97faf0aef78 proptest atlas, find 🐛🐜🦋
alfadur
parents: 14720
diff changeset
   302
        }
c97faf0aef78 proptest atlas, find 🐛🐜🦋
alfadur
parents: 14720
diff changeset
   303
    }
c97faf0aef78 proptest atlas, find 🐛🐜🦋
alfadur
parents: 14720
diff changeset
   304
c97faf0aef78 proptest atlas, find 🐛🐜🦋
alfadur
parents: 14720
diff changeset
   305
    fn sum_area<S: HasSize>(items: &[S]) -> usize {
c97faf0aef78 proptest atlas, find 🐛🐜🦋
alfadur
parents: 14720
diff changeset
   306
        items.iter().map(|s| s.size().area()).sum()
c97faf0aef78 proptest atlas, find 🐛🐜🦋
alfadur
parents: 14720
diff changeset
   307
    }
c97faf0aef78 proptest atlas, find 🐛🐜🦋
alfadur
parents: 14720
diff changeset
   308
c97faf0aef78 proptest atlas, find 🐛🐜🦋
alfadur
parents: 14720
diff changeset
   309
    proptest! {
c97faf0aef78 proptest atlas, find 🐛🐜🦋
alfadur
parents: 14720
diff changeset
   310
        #[test]
c97faf0aef78 proptest atlas, find 🐛🐜🦋
alfadur
parents: 14720
diff changeset
   311
        fn prop_insert(rects in Vec::<TestRect>::arbitrary()) {
14723
766ce87dfdfc finetune atlas proptest
alfadur
parents: 14722
diff changeset
   312
            let container = Rect::at_origin(Size::square(2048));
766ce87dfdfc finetune atlas proptest
alfadur
parents: 14722
diff changeset
   313
            let mut atlas = Atlas::new(container.size());
766ce87dfdfc finetune atlas proptest
alfadur
parents: 14722
diff changeset
   314
            let inserted: Vec<_> = rects.iter().filter_map(|TestRect(size)| atlas.insert(*size)).collect();
14722
c97faf0aef78 proptest atlas, find 🐛🐜🦋
alfadur
parents: 14720
diff changeset
   315
14726
75ff5c643004 actually atlas tests were also broken
alfadur
parents: 14725
diff changeset
   316
            let mut inserted_pairs = inserted.iter().cartesian_product(inserted.iter());
14723
766ce87dfdfc finetune atlas proptest
alfadur
parents: 14722
diff changeset
   317
14725
19d30d96d7d6 fix atlas.insert
alfadur
parents: 14723
diff changeset
   318
            assert!(inserted.iter().all(|r| container.contains_rect(r)));
14726
75ff5c643004 actually atlas tests were also broken
alfadur
parents: 14725
diff changeset
   319
            assert!(inserted_pairs.all(|(r1, r2)| r1 == r2 || r1 != r2 && !r1.intersects(r2)));
14725
19d30d96d7d6 fix atlas.insert
alfadur
parents: 14723
diff changeset
   320
14726
75ff5c643004 actually atlas tests were also broken
alfadur
parents: 14725
diff changeset
   321
            assert_eq!(inserted.len(), rects.len());
14723
766ce87dfdfc finetune atlas proptest
alfadur
parents: 14722
diff changeset
   322
            assert_eq!(sum_area(&inserted), sum_area(&rects));
14722
c97faf0aef78 proptest atlas, find 🐛🐜🦋
alfadur
parents: 14720
diff changeset
   323
        }
c97faf0aef78 proptest atlas, find 🐛🐜🦋
alfadur
parents: 14720
diff changeset
   324
    }
14726
75ff5c643004 actually atlas tests were also broken
alfadur
parents: 14725
diff changeset
   325
75ff5c643004 actually atlas tests were also broken
alfadur
parents: 14725
diff changeset
   326
    proptest! {
75ff5c643004 actually atlas tests were also broken
alfadur
parents: 14725
diff changeset
   327
        #[test]
75ff5c643004 actually atlas tests were also broken
alfadur
parents: 14725
diff changeset
   328
        fn prop_insert_set(rects in Vec::<TestRect>::arbitrary()) {
75ff5c643004 actually atlas tests were also broken
alfadur
parents: 14725
diff changeset
   329
            let container = Rect::at_origin(Size::square(2048));
75ff5c643004 actually atlas tests were also broken
alfadur
parents: 14725
diff changeset
   330
            let mut atlas = Atlas::new(container.size());
75ff5c643004 actually atlas tests were also broken
alfadur
parents: 14725
diff changeset
   331
            let mut set_atlas = Atlas::new(container.size());
75ff5c643004 actually atlas tests were also broken
alfadur
parents: 14725
diff changeset
   332
75ff5c643004 actually atlas tests were also broken
alfadur
parents: 14725
diff changeset
   333
            let inserted: Vec<_> = rects.iter().filter_map(|TestRect(size)| atlas.insert(*size)).collect();
75ff5c643004 actually atlas tests were also broken
alfadur
parents: 14725
diff changeset
   334
            let set_inserted: Vec<_> = set_atlas.insert_set(rects.iter().map(|TestRect(size)| *size));
75ff5c643004 actually atlas tests were also broken
alfadur
parents: 14725
diff changeset
   335
75ff5c643004 actually atlas tests were also broken
alfadur
parents: 14725
diff changeset
   336
            let mut set_inserted_pairs = set_inserted.iter().cartesian_product(set_inserted.iter());
75ff5c643004 actually atlas tests were also broken
alfadur
parents: 14725
diff changeset
   337
75ff5c643004 actually atlas tests were also broken
alfadur
parents: 14725
diff changeset
   338
            assert!(set_inserted_pairs.all(|(r1, r2)| r1 == r2 || r1 != r2 && !r1.intersects(r2)));
75ff5c643004 actually atlas tests were also broken
alfadur
parents: 14725
diff changeset
   339
            assert!(set_atlas.used_space().used() <= atlas.used_space().used());
75ff5c643004 actually atlas tests were also broken
alfadur
parents: 14725
diff changeset
   340
75ff5c643004 actually atlas tests were also broken
alfadur
parents: 14725
diff changeset
   341
            assert_eq!(sum_area(&set_inserted), sum_area(&inserted));
75ff5c643004 actually atlas tests were also broken
alfadur
parents: 14725
diff changeset
   342
        }
75ff5c643004 actually atlas tests were also broken
alfadur
parents: 14725
diff changeset
   343
    }
14717
16024046d458 rescue the atlas
alfadur
parents:
diff changeset
   344
}