cvkg_render_gpu/
heim.rs

1//! Heim packing utilities.
2//!
3//! SundrPacker implements a skyline bin-packing algorithm for the
4//! Mega-Heim texture array. It tracks horizontal segments and finds
5//! the best position for each new rectangle.
6
7#[derive(Clone, Copy)]
8pub struct SkylineSegment {
9    pub x: u32,
10    pub y: u32,
11    pub w: u32,
12}
13
14pub struct SundrPacker {
15    width: u32,
16    height: u32,
17    skyline: Vec<SkylineSegment>,
18}
19
20impl SundrPacker {
21    pub fn new(width: u32, height: u32) -> Self {
22        Self {
23            width,
24            height,
25            skyline: vec![SkylineSegment {
26                x: 0,
27                y: 0,
28                w: width,
29            }],
30        }
31    }
32
33    pub fn pack(&mut self, w: u32, h: u32) -> Option<(u32, u32)> {
34        if w > self.width || h > self.height {
35            return None;
36        }
37
38        let mut best_idx = None;
39        let mut best_y = u32::MAX;
40        let mut best_w = u32::MAX;
41
42        for i in 0..self.skyline.len() {
43            let seg = &self.skyline[i];
44            if seg.x + w > self.width {
45                continue;
46            }
47
48            let mut y = seg.y;
49            let mut remaining = w;
50            let mut j = i;
51            let mut fits = true;
52
53            while remaining > 0 {
54                if j >= self.skyline.len() {
55                    fits = false;
56                    break;
57                }
58                let s = &self.skyline[j];
59                y = y.max(s.y);
60                if y + h > self.height {
61                    fits = false;
62                    break;
63                }
64                if s.w >= remaining {
65                    break;
66                }
67                remaining -= s.w;
68                j += 1;
69            }
70
71            if fits && (y < best_y || (y == best_y && seg.w < best_w)) {
72                best_y = y;
73                best_idx = Some(i);
74                best_w = seg.w;
75            }
76        }
77
78        if let Some(idx) = best_idx {
79            let x = self.skyline[idx].x;
80            let y = best_y;
81
82            let new_seg = SkylineSegment { x, y: y + h, w };
83            let mut remaining = w;
84            let insert_idx = idx;
85
86            while remaining > 0 {
87                if self.skyline[insert_idx].w <= remaining {
88                    remaining -= self.skyline[insert_idx].w;
89                    self.skyline.remove(insert_idx);
90                } else {
91                    self.skyline[insert_idx].x += remaining;
92                    self.skyline[insert_idx].w -= remaining;
93                    remaining = 0;
94                }
95            }
96            self.skyline.insert(insert_idx, new_seg);
97
98            let mut i = 0;
99            while i < self.skyline.len() - 1 {
100                if self.skyline[i].y == self.skyline[i + 1].y {
101                    let w = self.skyline[i + 1].w;
102                    self.skyline[i].w += w;
103                    self.skyline.remove(i + 1);
104                } else {
105                    i += 1;
106                }
107            }
108
109            return Some((x, y));
110        }
111        None
112    }
113}
114
115#[cfg(test)]
116mod tests {
117    use super::*;
118
119    #[test]
120    fn test_shelf_packer_basic() {
121        let mut packer = SundrPacker::new(100, 100);
122        assert_eq!(packer.pack(10, 10), Some((0, 0)));
123        assert_eq!(packer.pack(20, 15), Some((10, 0)));
124    }
125
126    #[test]
127    fn test_shelf_packer_wrap() {
128        let mut packer = SundrPacker::new(100, 100);
129        packer.pack(60, 10);
130        assert_eq!(packer.pack(50, 20), Some((0, 10)));
131    }
132
133    #[test]
134    fn test_shelf_packer_oversized() {
135        let mut packer = SundrPacker::new(10, 10);
136        assert_eq!(packer.pack(11, 5), None);
137        assert_eq!(packer.pack(5, 11), None);
138    }
139}
cvkg_render_gpu/heim.rs

cvkg_render_gpu/
heim.rs
