1// Copyright © SixtyFPS GmbH <info@slint.dev>
2// SPDX-License-Identifier: GPL-3.0-only OR LicenseRef-Slint-Royalty-free-2.0 OR LicenseRef-Slint-Software-3.0
3
4//! This is the module contain data structures for a scene of items that can be rendered
5
6use super::{
7 Fixed, PhysicalBorderRadius, PhysicalLength, PhysicalPoint, PhysicalRect, PhysicalRegion,
8 PhysicalSize, PremultipliedRgbaColor, RenderingRotation,
9};
10use crate::graphics::{SharedImageBuffer, TexturePixelFormat};
11use crate::lengths::{PointLengths as _, SizeLengths as _};
12use crate::Color;
13use alloc::rc::Rc;
14use alloc::vec::Vec;
15use euclid::Length;
16
17#[derive(Default)]
18pub struct SceneVectors {
19 pub textures: Vec<SceneTexture<'static>>,
20 pub rounded_rectangles: Vec<RoundedRectangle>,
21 pub shared_buffers: Vec<SharedBufferCommand>,
22 pub gradients: Vec<GradientCommand>,
23}
24
25pub struct Scene {
26 /// the next line to be processed
27 pub(super) current_line: PhysicalLength,
28
29 /// The items are sorted like so:
30 /// - `items[future_items_index..]` are the items that have `y > current_line`.
31 /// They must be sorted by `y` (top to bottom), then by `z` (front to back)
32 /// - `items[..current_items_index]` are the items that overlap with the current_line,
33 /// sorted by z (front to back)
34 pub(super) items: Vec<SceneItem>,
35
36 pub(super) vectors: SceneVectors,
37
38 pub(super) future_items_index: usize,
39 pub(super) current_items_index: usize,
40
41 pub(super) dirty_region: PhysicalRegion,
42
43 pub(super) current_line_ranges: Vec<core::ops::Range<i16>>,
44 pub(super) range_valid_until_line: PhysicalLength,
45}
46
47impl Scene {
48 pub fn new(
49 mut items: Vec<SceneItem>,
50 vectors: SceneVectors,
51 dirty_region: PhysicalRegion,
52 ) -> Self {
53 let current_line =
54 dirty_region.iter_box().map(|x| x.min.y_length()).min().unwrap_or_default();
55 items.retain(|i| i.pos.y_length() + i.size.height_length() > current_line);
56 items.sort_unstable_by(compare_scene_item);
57 let current_items_index = items.partition_point(|i| i.pos.y_length() <= current_line);
58 items[..current_items_index].sort_unstable_by(|a, b| b.z.cmp(&a.z));
59 let mut r = Self {
60 items,
61 current_line,
62 current_items_index,
63 future_items_index: current_items_index,
64 vectors,
65 dirty_region,
66 current_line_ranges: Default::default(),
67 range_valid_until_line: Default::default(),
68 };
69 r.recompute_ranges();
70 debug_assert_eq!(r.current_line, r.dirty_region.bounding_rect().origin.y_length());
71 r
72 }
73
74 /// Updates `current_items_index` and `future_items_index` to match the invariant
75 pub fn next_line(&mut self) {
76 self.current_line += PhysicalLength::new(1);
77
78 let skipped = self.current_line >= self.range_valid_until_line && self.recompute_ranges();
79
80 // The items array is split in part:
81 // 1. [0..i] are the items that have already been processed, that are on this line
82 // 2. [j..current_items_index] are the items from the previous line that might still be
83 // valid on this line
84 // 3. [tmp1, tmp2] is a buffer where we swap items so we can make room for the items in [0..i]
85 // 4. [future_items_index..] are the items which might get processed now
86 // 5. [current_items_index..tmp1], [tmp2..future_items_index] and [i..j] is garbage
87 //
88 // At each step, we selecting the item with the higher z from the list 2 or 3 or 4 and take it from
89 // that list. Then we add it to the list [0..i] if it needs more processing. If needed,
90 // we move the first item from list 2. to list 3. to make some room
91
92 let (mut i, mut j, mut tmp1, mut tmp2) =
93 (0, 0, self.current_items_index, self.current_items_index);
94
95 if skipped {
96 // Merge sort doesn't work in that case.
97 while j < self.current_items_index {
98 let item = self.items[j];
99 if item.pos.y_length() + item.size.height_length() > self.current_line {
100 self.items[i] = item;
101 i += 1;
102 }
103 j += 1;
104 }
105 while self.future_items_index < self.items.len() {
106 let item = self.items[self.future_items_index];
107 if item.pos.y_length() > self.current_line {
108 break;
109 }
110 self.future_items_index += 1;
111 if item.pos.y_length() + item.size.height_length() < self.current_line {
112 continue;
113 }
114 self.items[i] = item;
115 i += 1;
116 }
117 self.items[0..i].sort_unstable_by(|a, b| b.z.cmp(&a.z));
118 self.current_items_index = i;
119 return;
120 }
121
122 'outer: loop {
123 let future_next_z = self
124 .items
125 .get(self.future_items_index)
126 .filter(|i| i.pos.y_length() <= self.current_line)
127 .map(|i| i.z);
128 let item = loop {
129 if tmp1 != tmp2 {
130 if future_next_z.map_or(true, |z| self.items[tmp1].z > z) {
131 let idx = tmp1;
132 tmp1 += 1;
133 if tmp1 == tmp2 {
134 tmp1 = self.current_items_index;
135 tmp2 = self.current_items_index;
136 }
137 break self.items[idx];
138 }
139 } else if j < self.current_items_index {
140 let item = &self.items[j];
141 if item.pos.y_length() + item.size.height_length() <= self.current_line {
142 j += 1;
143 continue;
144 }
145 if future_next_z.map_or(true, |z| item.z > z) {
146 j += 1;
147 break *item;
148 }
149 }
150 if future_next_z.is_some() {
151 self.future_items_index += 1;
152 break self.items[self.future_items_index - 1];
153 }
154 break 'outer;
155 };
156 if i != j {
157 // there is room
158 } else if j >= self.current_items_index && tmp1 == tmp2 {
159 // the current_items list is empty
160 j += 1
161 } else if self.items[j].pos.y_length() + self.items[j].size.height_length()
162 <= self.current_line
163 {
164 // next item in the current_items array is no longer in this line
165 j += 1;
166 } else if tmp2 < self.future_items_index && j < self.current_items_index {
167 // move the next item in current_items
168 let to_move = self.items[j];
169 self.items[tmp2] = to_move;
170 j += 1;
171 tmp2 += 1;
172 } else {
173 debug_assert!(tmp1 >= self.current_items_index);
174 let sort_begin = i;
175 // merge sort doesn't work because we don't have enough tmp space, just bring all items and use a normal sort.
176 while j < self.current_items_index {
177 let item = self.items[j];
178 if item.pos.y_length() + item.size.height_length() > self.current_line {
179 self.items[i] = item;
180 i += 1;
181 }
182 j += 1;
183 }
184 self.items.copy_within(tmp1..tmp2, i);
185 i += tmp2 - tmp1;
186 debug_assert!(i < self.future_items_index);
187 self.items[i] = item;
188 i += 1;
189 while self.future_items_index < self.items.len() {
190 let item = self.items[self.future_items_index];
191 if item.pos.y_length() > self.current_line {
192 break;
193 }
194 self.future_items_index += 1;
195 self.items[i] = item;
196 i += 1;
197 }
198 self.items[sort_begin..i].sort_unstable_by(|a, b| b.z.cmp(&a.z));
199 break;
200 }
201 self.items[i] = item;
202 i += 1;
203 }
204 self.current_items_index = i;
205 // check that current items are properly sorted
206 debug_assert!(self.items[0..self.current_items_index].windows(2).all(|x| x[0].z >= x[1].z));
207 }
208
209 // return true if lines were skipped
210 fn recompute_ranges(&mut self) -> bool {
211 let validity = super::region_line_ranges(
212 &self.dirty_region,
213 self.current_line.get(),
214 &mut self.current_line_ranges,
215 );
216 if self.current_line_ranges.is_empty() {
217 if let Some(next) = validity {
218 self.current_line = Length::new(next);
219 self.range_valid_until_line = Length::new(
220 super::region_line_ranges(
221 &self.dirty_region,
222 self.current_line.get(),
223 &mut self.current_line_ranges,
224 )
225 .unwrap_or_default(),
226 );
227 return true;
228 }
229 }
230 self.range_valid_until_line = Length::new(validity.unwrap_or_default());
231 false
232 }
233}
234
235#[derive(Clone, Copy, Debug)]
236pub struct SceneItem {
237 pub pos: PhysicalPoint,
238 pub size: PhysicalSize,
239 // this is the order of the item from which it is in the item tree
240 pub z: u16,
241 pub command: SceneCommand,
242}
243
244fn compare_scene_item(a: &SceneItem, b: &SceneItem) -> core::cmp::Ordering {
245 // First, order by line (top to bottom)
246 match a.pos.y.partial_cmp(&b.pos.y) {
247 None | Some(core::cmp::Ordering::Equal) => {}
248 Some(ord: Ordering) => return ord,
249 }
250 // Then by the reverse z (front to back)
251 match a.z.partial_cmp(&b.z) {
252 None | Some(core::cmp::Ordering::Equal) => {}
253 Some(ord: Ordering) => return ord.reverse(),
254 }
255
256 // anything else, we don't care
257 core::cmp::Ordering::Equal
258}
259
260#[derive(Clone, Copy, Debug)]
261#[repr(u8)]
262pub enum SceneCommand {
263 Rectangle {
264 color: PremultipliedRgbaColor,
265 },
266 /// texture_index is an index in the [`SceneVectors::textures`] array
267 Texture {
268 texture_index: u16,
269 },
270 /// shared_buffer_index is an index in [`SceneVectors::shared_buffers`]
271 SharedBuffer {
272 shared_buffer_index: u16,
273 },
274 /// rectangle_index is an index in the [`SceneVectors::rounded_rectangle`] array
275 RoundedRectangle {
276 rectangle_index: u16,
277 },
278 /// rectangle_index is an index in the [`SceneVectors::rounded_gradients`] array
279 Gradient {
280 gradient_index: u16,
281 },
282}
283
284pub struct SceneTexture<'a> {
285 /// This should have a size so that the entire slice is ((height - 1) * pixel_stride + width) * bpp
286 pub data: &'a [u8],
287 pub format: TexturePixelFormat,
288 /// number of pixels between two lines in the source
289 pub pixel_stride: u16,
290
291 pub extra: SceneTextureExtra,
292}
293
294impl SceneTexture<'_> {
295 pub fn source_size(&self) -> PhysicalSize {
296 let mut len: usize = self.data.len();
297 if self.format == TexturePixelFormat::SignedDistanceField {
298 len -= 1;
299 } else {
300 len /= self.format.bpp();
301 }
302 let stride: usize = self.pixel_stride as usize;
303 let h: usize = len / stride;
304 let w: usize = len % stride;
305 if w == 0 {
306 PhysicalSize::new(width:stride as _, height:h as _)
307 } else {
308 PhysicalSize::new(width:w as _, (h + 1) as _)
309 }
310 }
311}
312
313#[derive(Clone, Copy, Debug)]
314pub struct SceneTextureExtra {
315 /// Delta x: the amount of "image pixel" that we need to skip for each physical pixel in the target buffer
316 pub dx: Fixed<u16, 8>,
317 pub dy: Fixed<u16, 8>,
318 /// Offset which is the coordinate of the "image pixel" which going to be drawn at location SceneItem::pos
319 pub off_x: Fixed<u16, 4>,
320 pub off_y: Fixed<u16, 4>,
321 /// Color to colorize. When not transparent, consider that the image is an alpha map and always use that color.
322 /// The alpha of this color is ignored. (it is supposed to be mixed in `Self::alpha`)
323 pub colorize: Color,
324 pub alpha: u8,
325 pub rotation: RenderingRotation,
326}
327
328pub enum SharedBufferData {
329 SharedImage(SharedImageBuffer),
330 AlphaMap { data: Rc<[u8]>, width: u16 },
331}
332
333impl SharedBufferData {
334 fn width(&self) -> usize {
335 match self {
336 SharedBufferData::SharedImage(image: &SharedImageBuffer) => image.width() as usize,
337 SharedBufferData::AlphaMap { width: &u16, .. } => *width as usize,
338 }
339 }
340}
341
342pub struct SharedBufferCommand {
343 pub buffer: SharedBufferData,
344 /// The source rectangle that is mapped into this command span
345 pub source_rect: PhysicalRect,
346 pub extra: SceneTextureExtra,
347}
348
349impl SharedBufferCommand {
350 pub fn as_texture(&self) -> SceneTexture<'_> {
351 let stride = self.buffer.width();
352 let core::ops::Range { start, end } = compute_range_in_buffer(&self.source_rect, stride);
353
354 match &self.buffer {
355 SharedBufferData::SharedImage(SharedImageBuffer::RGB8(b)) => SceneTexture {
356 data: &b.as_bytes()[start * 3..end * 3],
357 pixel_stride: stride as u16,
358 format: TexturePixelFormat::Rgb,
359 extra: self.extra,
360 },
361 SharedBufferData::SharedImage(SharedImageBuffer::RGBA8(b)) => SceneTexture {
362 data: &b.as_bytes()[start * 4..end * 4],
363 pixel_stride: stride as u16,
364 format: TexturePixelFormat::Rgba,
365 extra: self.extra,
366 },
367 SharedBufferData::SharedImage(SharedImageBuffer::RGBA8Premultiplied(b)) => {
368 SceneTexture {
369 data: &b.as_bytes()[start * 4..end * 4],
370 pixel_stride: stride as u16,
371 format: TexturePixelFormat::RgbaPremultiplied,
372 extra: self.extra,
373 }
374 }
375 SharedBufferData::AlphaMap { data, width } => SceneTexture {
376 data: &data[start..end],
377 pixel_stride: *width,
378 format: TexturePixelFormat::AlphaMap,
379 extra: self.extra,
380 },
381 }
382 }
383}
384
385/// Given a rectangle of coordinate in a buffer and a stride, compute the range, in pixel
386pub fn compute_range_in_buffer(
387 source_rect: &PhysicalRect,
388 pixel_stride: usize,
389) -> core::ops::Range<usize> {
390 let start: usize = pixel_stride * source_rect.min_y() as usize + source_rect.min_x() as usize;
391 let end: usize = pixel_stride * (source_rect.max_y() - 1) as usize + source_rect.max_x() as usize;
392 start..end
393}
394
395#[derive(Debug)]
396pub struct RoundedRectangle {
397 pub radius: PhysicalBorderRadius,
398 /// the border's width
399 pub width: PhysicalLength,
400 pub border_color: PremultipliedRgbaColor,
401 pub inner_color: PremultipliedRgbaColor,
402 /// The clips is the amount of pixels of the rounded rectangle that is clipped away.
403 /// For example, if left_clip > width, then the left border will not be visible, and
404 /// if left_clip > radius, then no radius will be seen in the left side
405 pub left_clip: PhysicalLength,
406 pub right_clip: PhysicalLength,
407 pub top_clip: PhysicalLength,
408 pub bottom_clip: PhysicalLength,
409}
410
411/// Goes from color 1 to color2
412///
413/// depending of `flags & 0b1`
414/// - if false: on the left side, goes from `start` to 1, on the right side, goes from 0 to `1-start`
415/// - if true: on the left side, goes from 0 to `1-start`, on the right side, goes from `start` to `1`
416#[derive(Debug)]
417pub struct GradientCommand {
418 pub color1: PremultipliedRgbaColor,
419 pub color2: PremultipliedRgbaColor,
420 pub start: u8,
421 /// bit 0: if the slope is positive or negative
422 /// bit 1: if we should fill with color1 on the left side when left_clip is negative (or transparent)
423 /// bit 2: if we should fill with color2 on the left side when right_clip is negative (or transparent)
424 pub flags: u8,
425 /// If positive, the clip has the same meaning as in RoundedRectangle.
426 /// If negative, that means the "stop" is only starting or stopping at that point
427 pub left_clip: PhysicalLength,
428 pub right_clip: PhysicalLength,
429 pub top_clip: PhysicalLength,
430 pub bottom_clip: PhysicalLength,
431}
432