1use crate::{
2 AtlasTextureId, AtlasTile, Bounds, Corners, Edges, Hsla, Point, ScaledContentMask, ScaledPixels,
3};
4use collections::BTreeMap;
5use etagere::euclid::{Point3D, Vector3D};
6use plane_split::{BspSplitter, Polygon as BspPolygon};
7use smallvec::SmallVec;
8use std::{iter::Peekable, mem, slice};
9
10// Exported to metal
11pub type PointF = Point<f32>;
12pub type StackingOrder = SmallVec<[u32; 16]>;
13pub type LayerId = u32;
14pub type DrawOrder = u32;
15
16#[derive(Debug)]
17pub struct Scene {
18 pub(crate) scale_factor: f32,
19 pub(crate) layers: BTreeMap<StackingOrder, LayerId>,
20 pub quads: Vec<Quad>,
21 pub shadows: Vec<Shadow>,
22 pub monochrome_sprites: Vec<MonochromeSprite>,
23 pub polychrome_sprites: Vec<PolychromeSprite>,
24}
25
26impl Scene {
27 pub fn new(scale_factor: f32) -> Scene {
28 Scene {
29 scale_factor,
30 layers: BTreeMap::new(),
31 quads: Vec::new(),
32 shadows: Vec::new(),
33 monochrome_sprites: Vec::new(),
34 polychrome_sprites: Vec::new(),
35 }
36 }
37
38 pub fn take(&mut self) -> Scene {
39 Scene {
40 scale_factor: self.scale_factor,
41 layers: mem::take(&mut self.layers),
42 quads: mem::take(&mut self.quads),
43 shadows: mem::take(&mut self.shadows),
44 monochrome_sprites: mem::take(&mut self.monochrome_sprites),
45 polychrome_sprites: mem::take(&mut self.polychrome_sprites),
46 }
47 }
48
49 pub fn insert(&mut self, layer_id: StackingOrder, primitive: impl Into<Primitive>) {
50 let next_id = self.layers.len() as LayerId;
51 let layer_id = *self.layers.entry(layer_id).or_insert(next_id);
52 let primitive = primitive.into();
53 match primitive {
54 Primitive::Quad(mut quad) => {
55 quad.order = layer_id;
56 self.quads.push(quad);
57 }
58 Primitive::Shadow(mut shadow) => {
59 shadow.order = layer_id;
60 self.shadows.push(shadow);
61 }
62 Primitive::MonochromeSprite(mut sprite) => {
63 sprite.order = layer_id;
64 self.monochrome_sprites.push(sprite);
65 }
66 Primitive::PolychromeSprite(mut sprite) => {
67 sprite.order = layer_id;
68 self.polychrome_sprites.push(sprite);
69 }
70 }
71 }
72
73 pub(crate) fn batches(&mut self) -> impl Iterator<Item = PrimitiveBatch> {
74 // Map each layer id to a float between 0. and 1., with 1. closer to the viewer.
75 let mut layer_z_values = vec![0.; self.layers.len()];
76 for (ix, layer_id) in self.layers.values().enumerate() {
77 layer_z_values[*layer_id as usize] = ix as f32 / self.layers.len() as f32;
78 }
79
80 // Add all primitives to the BSP splitter to determine draw order
81 let mut splitter = BspSplitter::new();
82 for (ix, quad) in self.quads.iter().enumerate() {
83 let z = layer_z_values[quad.order as LayerId as usize];
84 splitter.add(quad.bounds.to_bsp_polygon(z, (PrimitiveKind::Quad, ix)));
85 }
86
87 for (ix, shadow) in self.shadows.iter().enumerate() {
88 let z = layer_z_values[shadow.order as LayerId as usize];
89 splitter.add(shadow.bounds.to_bsp_polygon(z, (PrimitiveKind::Shadow, ix)));
90 }
91
92 for (ix, monochrome_sprite) in self.monochrome_sprites.iter().enumerate() {
93 let z = layer_z_values[monochrome_sprite.order as LayerId as usize];
94 splitter.add(
95 monochrome_sprite
96 .bounds
97 .to_bsp_polygon(z, (PrimitiveKind::MonochromeSprite, ix)),
98 );
99 }
100
101 for (ix, polychrome_sprite) in self.polychrome_sprites.iter().enumerate() {
102 let z = layer_z_values[polychrome_sprite.order as LayerId as usize];
103 splitter.add(
104 polychrome_sprite
105 .bounds
106 .to_bsp_polygon(z, (PrimitiveKind::PolychromeSprite, ix)),
107 );
108 }
109
110 // Sort all polygons, then reassign the order field of each primitive to `draw_order`
111 // We need primitives to be repr(C), hence the weird reuse of the order field for two different types.
112 for (draw_order, polygon) in splitter.sort(Vector3D::new(0., 0., 1.)).iter().enumerate() {
113 match polygon.anchor {
114 (PrimitiveKind::Quad, ix) => self.quads[ix].order = draw_order as DrawOrder,
115 (PrimitiveKind::Shadow, ix) => self.shadows[ix].order = draw_order as DrawOrder,
116 (PrimitiveKind::MonochromeSprite, ix) => {
117 self.monochrome_sprites[ix].order = draw_order as DrawOrder
118 }
119 (PrimitiveKind::PolychromeSprite, ix) => {
120 self.polychrome_sprites[ix].order = draw_order as DrawOrder
121 }
122 }
123 }
124
125 // Sort the primitives
126 self.quads.sort_unstable();
127 self.shadows.sort_unstable();
128 self.monochrome_sprites.sort_unstable();
129 self.polychrome_sprites.sort_unstable();
130
131 BatchIterator {
132 quads: &self.quads,
133 quads_start: 0,
134 quads_iter: self.quads.iter().peekable(),
135 shadows: &self.shadows,
136 shadows_start: 0,
137 shadows_iter: self.shadows.iter().peekable(),
138 monochrome_sprites: &self.monochrome_sprites,
139 monochrome_sprites_start: 0,
140 monochrome_sprites_iter: self.monochrome_sprites.iter().peekable(),
141 polychrome_sprites: &self.polychrome_sprites,
142 polychrome_sprites_start: 0,
143 polychrome_sprites_iter: self.polychrome_sprites.iter().peekable(),
144 }
145 }
146}
147
148struct BatchIterator<'a> {
149 quads: &'a [Quad],
150 quads_start: usize,
151 quads_iter: Peekable<slice::Iter<'a, Quad>>,
152 shadows: &'a [Shadow],
153 shadows_start: usize,
154 shadows_iter: Peekable<slice::Iter<'a, Shadow>>,
155 monochrome_sprites: &'a [MonochromeSprite],
156 monochrome_sprites_start: usize,
157 monochrome_sprites_iter: Peekable<slice::Iter<'a, MonochromeSprite>>,
158 polychrome_sprites: &'a [PolychromeSprite],
159 polychrome_sprites_start: usize,
160 polychrome_sprites_iter: Peekable<slice::Iter<'a, PolychromeSprite>>,
161}
162
163impl<'a> Iterator for BatchIterator<'a> {
164 type Item = PrimitiveBatch<'a>;
165
166 fn next(&mut self) -> Option<Self::Item> {
167 let mut orders_and_kinds = [
168 (self.quads_iter.peek().map(|q| q.order), PrimitiveKind::Quad),
169 (
170 self.shadows_iter.peek().map(|s| s.order),
171 PrimitiveKind::Shadow,
172 ),
173 (
174 self.monochrome_sprites_iter.peek().map(|s| s.order),
175 PrimitiveKind::MonochromeSprite,
176 ),
177 (
178 self.polychrome_sprites_iter.peek().map(|s| s.order),
179 PrimitiveKind::PolychromeSprite,
180 ),
181 ];
182 orders_and_kinds.sort_by_key(|(order, kind)| (order.unwrap_or(u32::MAX), *kind));
183
184 let first = orders_and_kinds[0];
185 let second = orders_and_kinds[1];
186 let (batch_kind, max_order) = if first.0.is_some() {
187 (first.1, second.0.unwrap_or(u32::MAX))
188 } else {
189 return None;
190 };
191
192 match batch_kind {
193 PrimitiveKind::Quad => {
194 let quads_start = self.quads_start;
195 let mut quads_end = quads_start;
196 while self
197 .quads_iter
198 .next_if(|quad| quad.order <= max_order)
199 .is_some()
200 {
201 quads_end += 1;
202 }
203 self.quads_start = quads_end;
204 Some(PrimitiveBatch::Quads(&self.quads[quads_start..quads_end]))
205 }
206 PrimitiveKind::Shadow => {
207 let shadows_start = self.shadows_start;
208 let mut shadows_end = shadows_start;
209 while self
210 .shadows_iter
211 .next_if(|shadow| shadow.order <= max_order)
212 .is_some()
213 {
214 shadows_end += 1;
215 }
216 self.shadows_start = shadows_end;
217 Some(PrimitiveBatch::Shadows(
218 &self.shadows[shadows_start..shadows_end],
219 ))
220 }
221 PrimitiveKind::MonochromeSprite => {
222 let texture_id = self.monochrome_sprites_iter.peek().unwrap().tile.texture_id;
223 let sprites_start = self.monochrome_sprites_start;
224 let mut sprites_end = sprites_start;
225 while self
226 .monochrome_sprites_iter
227 .next_if(|sprite| {
228 sprite.order <= max_order && sprite.tile.texture_id == texture_id
229 })
230 .is_some()
231 {
232 sprites_end += 1;
233 }
234 self.monochrome_sprites_start = sprites_end;
235 Some(PrimitiveBatch::MonochromeSprites {
236 texture_id,
237 sprites: &self.monochrome_sprites[sprites_start..sprites_end],
238 })
239 }
240 PrimitiveKind::PolychromeSprite => {
241 let texture_id = self.polychrome_sprites_iter.peek().unwrap().tile.texture_id;
242 let sprites_start = self.polychrome_sprites_start;
243 let mut sprites_end = self.polychrome_sprites_start;
244 while self
245 .polychrome_sprites_iter
246 .next_if(|sprite| {
247 sprite.order <= max_order && sprite.tile.texture_id == texture_id
248 })
249 .is_some()
250 {
251 sprites_end += 1;
252 }
253 self.polychrome_sprites_start = sprites_end;
254 Some(PrimitiveBatch::PolychromeSprites {
255 texture_id,
256 sprites: &self.polychrome_sprites[sprites_start..sprites_end],
257 })
258 }
259 }
260 }
261}
262
263#[derive(Clone, Copy, Debug, Eq, PartialEq, Ord, PartialOrd, Default)]
264pub enum PrimitiveKind {
265 Shadow,
266 #[default]
267 Quad,
268 MonochromeSprite,
269 PolychromeSprite,
270}
271
272#[derive(Clone, Debug)]
273pub enum Primitive {
274 Quad(Quad),
275 Shadow(Shadow),
276 MonochromeSprite(MonochromeSprite),
277 PolychromeSprite(PolychromeSprite),
278}
279
280#[derive(Debug)]
281pub(crate) enum PrimitiveBatch<'a> {
282 Quads(&'a [Quad]),
283 Shadows(&'a [Shadow]),
284 MonochromeSprites {
285 texture_id: AtlasTextureId,
286 sprites: &'a [MonochromeSprite],
287 },
288 PolychromeSprites {
289 texture_id: AtlasTextureId,
290 sprites: &'a [PolychromeSprite],
291 },
292}
293
294#[derive(Default, Debug, Clone, Eq, PartialEq)]
295#[repr(C)]
296pub struct Quad {
297 pub order: u32, // Initially a LayerId, then a DrawOrder.
298 pub bounds: Bounds<ScaledPixels>,
299 pub content_mask: ScaledContentMask,
300 pub background: Hsla,
301 pub border_color: Hsla,
302 pub corner_radii: Corners<ScaledPixels>,
303 pub border_widths: Edges<ScaledPixels>,
304}
305
306impl Ord for Quad {
307 fn cmp(&self, other: &Self) -> std::cmp::Ordering {
308 self.order.cmp(&other.order)
309 }
310}
311
312impl PartialOrd for Quad {
313 fn partial_cmp(&self, other: &Self) -> Option<std::cmp::Ordering> {
314 Some(self.cmp(other))
315 }
316}
317
318impl From<Quad> for Primitive {
319 fn from(quad: Quad) -> Self {
320 Primitive::Quad(quad)
321 }
322}
323
324#[derive(Debug, Clone, Eq, PartialEq)]
325#[repr(C)]
326pub struct Shadow {
327 pub order: u32,
328 pub bounds: Bounds<ScaledPixels>,
329 pub corner_radii: Corners<ScaledPixels>,
330 pub content_mask: ScaledContentMask,
331 pub color: Hsla,
332 pub blur_radius: ScaledPixels,
333}
334
335impl Ord for Shadow {
336 fn cmp(&self, other: &Self) -> std::cmp::Ordering {
337 self.order.cmp(&other.order)
338 }
339}
340
341impl PartialOrd for Shadow {
342 fn partial_cmp(&self, other: &Self) -> Option<std::cmp::Ordering> {
343 Some(self.cmp(other))
344 }
345}
346
347impl From<Shadow> for Primitive {
348 fn from(shadow: Shadow) -> Self {
349 Primitive::Shadow(shadow)
350 }
351}
352
353#[derive(Clone, Debug, Eq, PartialEq)]
354#[repr(C)]
355pub struct MonochromeSprite {
356 pub order: u32,
357 pub bounds: Bounds<ScaledPixels>,
358 pub content_mask: ScaledContentMask,
359 pub color: Hsla,
360 pub tile: AtlasTile,
361}
362
363impl Ord for MonochromeSprite {
364 fn cmp(&self, other: &Self) -> std::cmp::Ordering {
365 match self.order.cmp(&other.order) {
366 std::cmp::Ordering::Equal => self.tile.tile_id.cmp(&other.tile.tile_id),
367 order => order,
368 }
369 }
370}
371
372impl PartialOrd for MonochromeSprite {
373 fn partial_cmp(&self, other: &Self) -> Option<std::cmp::Ordering> {
374 Some(self.cmp(other))
375 }
376}
377
378impl From<MonochromeSprite> for Primitive {
379 fn from(sprite: MonochromeSprite) -> Self {
380 Primitive::MonochromeSprite(sprite)
381 }
382}
383
384#[derive(Clone, Debug, Eq, PartialEq)]
385#[repr(C)]
386pub struct PolychromeSprite {
387 pub order: u32,
388 pub bounds: Bounds<ScaledPixels>,
389 pub content_mask: ScaledContentMask,
390 pub corner_radii: Corners<ScaledPixels>,
391 pub tile: AtlasTile,
392 pub grayscale: bool,
393}
394
395impl Ord for PolychromeSprite {
396 fn cmp(&self, other: &Self) -> std::cmp::Ordering {
397 match self.order.cmp(&other.order) {
398 std::cmp::Ordering::Equal => self.tile.tile_id.cmp(&other.tile.tile_id),
399 order => order,
400 }
401 }
402}
403
404impl PartialOrd for PolychromeSprite {
405 fn partial_cmp(&self, other: &Self) -> Option<std::cmp::Ordering> {
406 Some(self.cmp(other))
407 }
408}
409
410impl From<PolychromeSprite> for Primitive {
411 fn from(sprite: PolychromeSprite) -> Self {
412 Primitive::PolychromeSprite(sprite)
413 }
414}
415
416#[derive(Copy, Clone, Debug)]
417pub struct AtlasId(pub(crate) usize);
418
419impl Bounds<ScaledPixels> {
420 fn to_bsp_polygon<A: Copy>(&self, z: f32, anchor: A) -> BspPolygon<A> {
421 let upper_left = self.origin;
422 let upper_right = self.upper_right();
423 let lower_right = self.lower_right();
424 let lower_left = self.lower_left();
425
426 BspPolygon::from_points(
427 [
428 Point3D::new(upper_left.x.into(), upper_left.y.into(), z as f64),
429 Point3D::new(upper_right.x.into(), upper_right.y.into(), z as f64),
430 Point3D::new(lower_right.x.into(), lower_right.y.into(), z as f64),
431 Point3D::new(lower_left.x.into(), lower_left.y.into(), z as f64),
432 ],
433 anchor,
434 )
435 .expect("Polygon should not be empty")
436 }
437}
438
439#[cfg(test)]
440mod tests {
441 use crate::{point, size};
442
443 use super::*;
444 use smallvec::smallvec;
445
446 #[test]
447 fn test_scene() {
448 let mut scene = Scene::new(1.0);
449 assert_eq!(scene.layers.len(), 0);
450
451 scene.insert(smallvec![1], quad());
452 scene.insert(smallvec![2], shadow());
453 scene.insert(smallvec![3], quad());
454
455 let mut batches_count = 0;
456 for _ in scene.batches() {
457 batches_count += 1;
458 }
459 assert_eq!(batches_count, 3);
460 }
461
462 fn quad() -> Quad {
463 Quad {
464 order: 0,
465 bounds: Bounds {
466 origin: point(ScaledPixels(0.), ScaledPixels(0.)),
467 size: size(ScaledPixels(100.), ScaledPixels(100.)),
468 },
469 content_mask: Default::default(),
470 background: Default::default(),
471 border_color: Default::default(),
472 corner_radii: Default::default(),
473 border_widths: Default::default(),
474 }
475 }
476
477 fn shadow() -> Shadow {
478 Shadow {
479 order: Default::default(),
480 bounds: Bounds {
481 origin: point(ScaledPixels(0.), ScaledPixels(0.)),
482 size: size(ScaledPixels(100.), ScaledPixels(100.)),
483 },
484 corner_radii: Default::default(),
485 content_mask: Default::default(),
486 color: Default::default(),
487 blur_radius: Default::default(),
488 }
489 }
490}