git.seregonwar.com

crates/strato-ui-renderer/src/rendering/atlas/allocator.rs

StratoSDK / crates / strato-ui-renderer / src / rendering / atlas / allocator.rs

1	use crate::rendering::atlas::{AllocatedRegion, AllocationError};
2	use pathfinder_geometry::rect::{RectF, RectI};
3	use pathfinder_geometry::vector::{vec2f, vec2i, Vector2I};
4
5	/// The number of pixels of padding that should be applied between elements
6	/// in an atlas row.
7	const HORIZONTAL_PADDING: i32 = 1;
8	/// The number of pixels of padding that should be applied between rows of
9	/// elements in the atlas.
10	const VERTICAL_PADDING: i32 = 1;
11
12	/// A naive allocator to determine where items should be inserted into an atlas. Items are packed in
13	/// by using the Shelf-Next Fit algorithm (as described in
14	/// <https://blog.roomanna.com/09-25-2015/binpacking-shelf>). Items are fit horizontally in the
15	/// current open row (aka shelf) until a new element does not fit in that row, at which point a new
16	/// row for elements are created.
17	/// Visually, this looks like the following:
18	///
19	/// ```text
20	/// (width, height)
21	/// ┌─────┬─────┬─────┬─────┬─────┐
22	/// │ 10 │ │ │ │ │ <- Empty spaces; can be filled while
23	/// │ │ │ │ │ │ element_height < height - row_baseline
24	/// ├─────┼─────┼─────┼─────┼─────┤
25	/// │ 5 │ 6 │ 7 │ 8 │ 9 │
26	/// │ │ │ │ │ │
27	/// ├─────┼─────┼─────┼─────┴─────┤ <- Row height is tallest element in row; this is
28	/// │ 1 │ 2 │ 3 │ 4 │ used as the baseline for the following row.
29	/// │ │ │ │ │ <- Row considered full when next element doesn't
30	/// └─────┴─────┴─────┴───────────┘ fit in the row.
31	/// (0, 0) x->
32	/// ```
33	#[derive(Debug)]
34	pub(crate) struct Allocator {
35	/// Width of atlas.
36	width: i32,
37
38	/// Height of atlas.
39	height: i32,
40
41	/// Left-most free pixel in a row.
42	///
43	/// This is called the extent because it is the upper bound of used pixels
44	/// in a row.
45	row_extent: i32,
46
47	/// Baseline for elements in the current row.
48	row_baseline: i32,
49
50	/// Tallest element in current row.
51	///
52	/// This is used as the advance when end of row is reached.
53	row_tallest: i32,
54	}
55
56	impl Allocator {
57	pub fn new(size: usize) -> Self {
58	Self {
59	width: size as i32,
60	height: size as i32,
61	row_extent: 0,
62	row_baseline: 0,
63	row_tallest: 0,
64	}
65	}
66
67	/// Attempts to allocate space for an item of size `element_size` into the atlas. If allocated,
68	/// returns an [`AllocatedRegion`] that describes the region of the texture that was allocated.
69	/// Returns an [`AllocationError`] if the item was unable to be inserted into the atlas.
70	pub fn insert(&mut self, element_size: Vector2I) -> Result<AllocatedRegion, AllocationError> {
71	if element_size.x() > self.width \|\| element_size.y() > self.height {
72	return Err(AllocationError::ItemTooLarge);
73	}
74
75	// If there's not enough room in current row, go onto next one.
76	if !self.room_in_row(element_size) {
77	self.advance_row()?;
78	}
79
80	// If there's still not room, there's nothing that can be done here.
81	if !self.room_in_row(element_size) {
82	return Err(AllocationError::Full);
83	}
84
85	// There appears to be room; allocate space for the iten.
86	Ok(self.insert_inner(element_size))
87	}
88
89	/// Allocate space for the item without checking for room.
90	///
91	/// Internal function for use once atlas has been checked for space.
92	fn insert_inner(&mut self, element_size: Vector2I) -> AllocatedRegion {
93	let offset_y = self.row_baseline;
94	let offset_x = self.row_extent;
95	let height = element_size.y();
96	let width = element_size.x();
97
98	// Update Atlas state.
99	self.row_extent = offset_x + width + HORIZONTAL_PADDING;
100	if height > self.row_tallest {
101	self.row_tallest = height;
102	}
103
104	// Generate UV coordinates.
105	let uv_top = offset_y as f32 / self.height as f32;
106	let uv_left = offset_x as f32 / self.width as f32;
107	let uv_height = height as f32 / self.height as f32;
108	let uv_width = width as f32 / self.width as f32;
109
110	AllocatedRegion {
111	uv_region: RectF::new(vec2f(uv_left, uv_top), vec2f(uv_width, uv_height)),
112	pixel_region: RectI::new(vec2i(offset_x, offset_y), vec2i(width, height)),
113	}
114	}
115
116	/// Check if there's room in the current row for given element..
117	fn room_in_row(&self, element_size: Vector2I) -> bool {
118	let next_extent = self.row_extent + element_size.x();
119	let enough_width = next_extent <= self.width;
120	let enough_height = element_size.y() < (self.height - self.row_baseline);
121
122	enough_width && enough_height
123	}
124
125	/// Mark current row as finished and prepare to insert into the next row.
126	fn advance_row(&mut self) -> Result<(), AllocationError> {
127	let advance_to = self.row_baseline + self.row_tallest + VERTICAL_PADDING;
128	if self.height - advance_to <= 0 {
129	return Err(AllocationError::Full);
130	}
131
132	self.row_baseline = advance_to;
133	self.row_extent = 0;
134	self.row_tallest = 0;
135
136	Ok(())
137	}
138	}
139

Seregon/StratoSDK