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