alpha2_geometry/
tree.rs

1//! A content tree evaluated at one time, and the scene it draws.
2//!
3//! The rules are After Effects' and Lottie's. A group is read front to back.
4//! Geometry accumulates in its group; a fill or stroke paints the geometry
5//! listed before it there, nested groups' included, and a trim cuts that
6//! geometry and replaces it. Paints listed earlier are drawn on top, so a
7//! group's drawing is emitted from its last item back to its first.
8//!
9//! Positions are normalized and lengths fractions of the shorter side, as
10//! the model has them; [`build_scene`] takes them to device pixels. A
11//! group's transform acts in pixel space, and the paths, strokes, and paint
12//! coordinates under it go through it: a stroke is expanded in the space of
13//! the group its stroke item is in, then transformed, so a non-uniform scale
14//! makes its pen an ellipse.
15
16use crate::scene::{IRect, PaintKind, ScenePaint, SceneStop, VectorOp, VectorScene};
17use crate::trim::{Measured, TrimSpan};
18use crate::{CanvasSize, StrokeStyle, affine, project_far, shapes, stroke_outline, trim};
19use alpha2_model::{FillRule, LineCap, LineJoin, Paint, PolystarKind, TrimMode};
20use kurbo::{Affine, BezPath, Point, Vec2};
21use std::sync::Arc;
22
23/// A path vertex evaluated at one time, normalized.
24#[derive(Copy, Clone, Debug, Default, PartialEq)]
25pub struct EvaluatedVertex {
26    /// Where it lies.
27    pub point: Point,
28    /// The control point of the segment ending here, relative to `point`.
29    pub in_tangent: Vec2,
30    /// The control point of the segment starting here, relative to `point`.
31    pub out_tangent: Vec2,
32}
33
34/// A subpath evaluated at one time.
35#[derive(Clone, Debug, Default, PartialEq)]
36pub struct EvaluatedSubpath {
37    /// Whether a segment joins the last vertex back to the first.
38    pub closed: bool,
39    /// The vertices.
40    pub vertices: Vec<EvaluatedVertex>,
41}
42
43/// A path evaluated at one time.
44#[derive(Clone, Debug, Default, PartialEq)]
45pub struct EvaluatedPath {
46    /// The subpaths.
47    pub subpaths: Vec<EvaluatedSubpath>,
48}
49
50impl From<&alpha2_model::Path> for EvaluatedPath {
51    fn from(path: &alpha2_model::Path) -> Self {
52        let point = |value: alpha2_model::Vec2| Point::new(f64::from(value.x), f64::from(value.y));
53        let vector = |value: alpha2_model::Vec2| Vec2::new(f64::from(value.x), f64::from(value.y));
54        Self {
55            subpaths: path
56                .subpaths
57                .iter()
58                .map(|subpath| EvaluatedSubpath {
59                    closed: subpath.closed,
60                    vertices: subpath
61                        .vertices
62                        .iter()
63                        .map(|vertex| EvaluatedVertex {
64                            point: point(vertex.point),
65                            in_tangent: vector(vertex.in_tangent),
66                            out_tangent: vector(vertex.out_tangent),
67                        })
68                        .collect(),
69                })
70                .collect(),
71        }
72    }
73}
74
75/// A geometry item evaluated at one time.
76#[derive(Clone, Debug, PartialEq)]
77pub enum EvaluatedGeometry {
78    /// A rectangle.
79    Rectangle {
80        /// Centre.
81        center: Point,
82        /// Full size.
83        size: Vec2,
84        /// Corner radius, a fraction of the shorter side.
85        corner_radius: f64,
86        /// Clockwise rotation in degrees.
87        rotation_degrees: f64,
88    },
89    /// An ellipse.
90    Ellipse {
91        /// Centre.
92        center: Point,
93        /// Full size.
94        size: Vec2,
95        /// Clockwise rotation in degrees.
96        rotation_degrees: f64,
97    },
98    /// A star or polygon.
99    Polystar {
100        /// Star or polygon.
101        kind: PolystarKind,
102        /// Centre.
103        center: Point,
104        /// Number of points; a fraction is dropped.
105        points: f64,
106        /// Points' radius, a fraction of the shorter side.
107        outer_radius: f64,
108        /// A star's inner radius, a fraction of the shorter side.
109        inner_radius: f64,
110        /// Roundness of the points.
111        outer_roundness: f64,
112        /// Roundness of a star's inner corners.
113        inner_roundness: f64,
114        /// Clockwise rotation in degrees.
115        rotation_degrees: f64,
116    },
117    /// A Bezier path.
118    Path(Arc<EvaluatedPath>),
119}
120
121impl EvaluatedGeometry {
122    /// The geometry in the pixels of a picture of `size`.
123    #[must_use]
124    pub fn to_path(&self, size: CanvasSize) -> BezPath {
125        let scale = size.scale();
126        let pixel = |point: Point| Point::new(point.x * scale.x, point.y * scale.y);
127        let extent = |vector: Vec2| Vec2::new(vector.x * scale.x, vector.y * scale.y);
128        let unit = size.unit();
129        match self {
130            Self::Rectangle {
131                center,
132                size: extent_value,
133                corner_radius,
134                rotation_degrees,
135            } => shapes::rectangle(
136                pixel(*center),
137                extent(*extent_value),
138                corner_radius * unit,
139                *rotation_degrees,
140            ),
141            Self::Ellipse {
142                center,
143                size: extent_value,
144                rotation_degrees,
145            } => shapes::ellipse(pixel(*center), extent(*extent_value), *rotation_degrees),
146            Self::Polystar {
147                kind,
148                center,
149                points,
150                outer_radius,
151                inner_radius,
152                outer_roundness,
153                inner_roundness,
154                rotation_degrees,
155            } => shapes::polystar(&shapes::Polystar {
156                star: *kind == PolystarKind::Star,
157                center: pixel(*center),
158                points: *points,
159                outer_radius: outer_radius * unit,
160                inner_radius: inner_radius * unit,
161                outer_roundness: *outer_roundness,
162                inner_roundness: *inner_roundness,
163                degrees: *rotation_degrees,
164            }),
165            Self::Path(path) => {
166                let mut bez = BezPath::new();
167                let mut vertices = Vec::new();
168                for subpath in &path.subpaths {
169                    vertices.clear();
170                    vertices.extend(subpath.vertices.iter().map(|vertex| shapes::Vertex {
171                        point: pixel(vertex.point),
172                        in_tangent: extent(vertex.in_tangent),
173                        out_tangent: extent(vertex.out_tangent),
174                    }));
175                    shapes::append_subpath(&mut bez, &vertices, subpath.closed);
176                }
177                bez
178            }
179        }
180    }
181}
182
183/// A group's transform evaluated at one time, normalized.
184#[derive(Copy, Clone, Debug, PartialEq)]
185pub struct EvaluatedTransform {
186    /// The point of the items placed at `position`.
187    pub anchor: Point,
188    /// Where `anchor` is placed.
189    pub position: Point,
190    /// Per-axis scale.
191    pub scale: Vec2,
192    /// Clockwise rotation in degrees.
193    pub rotation_degrees: f64,
194    /// Group opacity, in `0..=1`.
195    pub opacity: f64,
196}
197
198impl Default for EvaluatedTransform {
199    fn default() -> Self {
200        Self {
201            anchor: Point::ZERO,
202            position: Point::ZERO,
203            scale: Vec2::new(1.0, 1.0),
204            rotation_degrees: 0.0,
205            opacity: 1.0,
206        }
207    }
208}
209
210impl EvaluatedTransform {
211    /// The transform in the pixels of a picture of `size`.
212    #[must_use]
213    pub fn affine(&self, size: CanvasSize) -> Affine {
214        affine::placement(
215            size.point(self.position.x, self.position.y),
216            size.point(self.anchor.x, self.anchor.y),
217            self.scale,
218            self.rotation_degrees,
219        )
220    }
221}
222
223/// One content-tree item evaluated at one time.
224#[derive(Clone, Debug, PartialEq)]
225pub enum EvaluatedItem {
226    /// Items drawn through one transform and opacity.
227    Group {
228        /// The items, front first. Shared, so a subtree that does not change
229        /// over time is evaluated once.
230        items: Arc<[EvaluatedItem]>,
231        /// The group's transform.
232        transform: EvaluatedTransform,
233    },
234    /// Geometry.
235    Geometry(EvaluatedGeometry),
236    /// A fill of the geometry before it.
237    Fill {
238        /// What covers it.
239        paint: Paint,
240        /// Opacity in `0..=1`.
241        opacity: f64,
242        /// Which regions are inside.
243        rule: FillRule,
244    },
245    /// A stroke of the geometry before it.
246    Stroke {
247        /// What covers it.
248        paint: Paint,
249        /// Full width, a fraction of the shorter side.
250        width: f64,
251        /// Opacity in `0..=1`.
252        opacity: f64,
253        /// How segments meet.
254        join: LineJoin,
255        /// Miter limit.
256        miter_limit: f64,
257        /// How ends look.
258        cap: LineCap,
259        /// Dash and gap lengths, fractions of the shorter side; solid when
260        /// empty.
261        dash: Vec<f64>,
262        /// Dash offset, a fraction of the shorter side.
263        dash_offset: f64,
264    },
265    /// A trim of the geometry before it.
266    Trim {
267        /// Start fraction.
268        start: f64,
269        /// End fraction.
270        end: f64,
271        /// Offset in turns.
272        offset: f64,
273        /// Together or individually.
274        mode: TrimMode,
275    },
276}
277
278/// Geometry accumulated in a group: a path in the space of the item that
279/// made it, and the transform from there to the group's space.
280#[derive(Clone)]
281struct Entry {
282    path: BezPath,
283    relative: Affine,
284}
285
286/// What [`item_paths`] reports of one item.
287#[derive(Clone, Debug, PartialEq)]
288pub struct ItemPath {
289    /// The item's place in the tree, like `items[0].items[2]`.
290    pub at: String,
291    /// What it covers in device pixels: geometry's outline, a fill's area,
292    /// a stroke's outline; empty for a group. Trims are not recorded.
293    pub path: BezPath,
294    /// How `path` is filled.
295    pub rule: FillRule,
296    /// Whether it is paint (a fill or a stroke) rather than geometry.
297    pub paint: bool,
298    /// The device pixels it reaches; a group's is its items'.
299    pub bounds: kurbo::Rect,
300}
301
302struct Builder {
303    size: CanvasSize,
304    canvas: IRect,
305    /// Whether items are named by their place in the tree: only queries
306    /// read the names, so a scene drawn for a frame formats none.
307    named: bool,
308    /// Every item's outline or area, when queries need them.
309    records: Option<Vec<ItemPath>>,
310}
311
312/// A group's drawing, in item order: the scene emits it back to front.
313type Chunks = Vec<Vec<(VectorOp, String)>>;
314
315/// The scene `items` draw on a picture of `size`.
316#[must_use]
317pub fn build_scene(items: &[EvaluatedItem], size: CanvasSize) -> VectorScene {
318    let mut builder = Builder::new(size, false, false);
319    let (_, chunks) = builder.group(items, Affine::IDENTITY, "");
320    let ops = back_to_front(chunks)
321        .into_iter()
322        .map(|(op, _)| op)
323        .collect();
324    VectorScene::new(ops, size.width, size.height)
325}
326
327/// The scene `items` draw, with the item each of its operations was drawn
328/// for (empty for a layer's push and pop).
329#[must_use]
330pub fn build_scene_with_items(
331    items: &[EvaluatedItem],
332    size: CanvasSize,
333) -> (VectorScene, Vec<String>) {
334    let mut builder = Builder::new(size, true, false);
335    let (_, chunks) = builder.group(items, Affine::IDENTITY, "items");
336    let (ops, owners): (Vec<_>, Vec<_>) = back_to_front(chunks).into_iter().unzip();
337    (VectorScene::new(ops, size.width, size.height), owners)
338}
339
340/// Every item's outline or painted area, in document order, for the
341/// editor's queries.
342#[must_use]
343pub fn item_paths(items: &[EvaluatedItem], size: CanvasSize) -> Vec<ItemPath> {
344    let mut builder = Builder::new(size, true, true);
345    builder.group(items, Affine::IDENTITY, "items");
346    builder.records.unwrap_or_default()
347}
348
349fn back_to_front(chunks: Chunks) -> Vec<(VectorOp, String)> {
350    chunks.into_iter().rev().flatten().collect()
351}
352
353impl Builder {
354    fn new(size: CanvasSize, named: bool, records: bool) -> Self {
355        let canvas = IRect::new(
356            0,
357            0,
358            i32::try_from(size.width).unwrap_or(i32::MAX),
359            i32::try_from(size.height).unwrap_or(i32::MAX),
360        );
361        Self {
362            size,
363            canvas,
364            named,
365            records: records.then(Vec::new),
366        }
367    }
368
369    fn record(&mut self, at: &str, path: BezPath, rule: FillRule, paint: bool) {
370        if let Some(records) = &mut self.records {
371            let bounds = if path.elements().is_empty() {
372                kurbo::Rect::ZERO
373            } else {
374                kurbo::Shape::bounding_box(&path)
375            };
376            records.push(ItemPath {
377                at: at.to_owned(),
378                path,
379                rule,
380                paint,
381                bounds,
382            });
383        }
384    }
385
386    /// Reads a group's items: the geometry it leaves for the enclosing group
387    /// (in this group's space) and its drawing.
388    #[allow(clippy::too_many_lines)]
389    fn group(
390        &mut self,
391        items: &[EvaluatedItem],
392        to_device: Affine,
393        at: &str,
394    ) -> (Vec<Entry>, Chunks) {
395        let mut entries: Vec<Entry> = Vec::new();
396        let mut chunks: Chunks = Vec::new();
397        for (index, item) in items.iter().enumerate() {
398            let at = if self.named {
399                format!("{at}[{index}]")
400            } else {
401                String::new()
402            };
403            match item {
404                EvaluatedItem::Group { items, transform } => {
405                    let local = transform.affine(self.size);
406                    let record_index = self.records.as_ref().map(Vec::len);
407                    let inner_at = if self.named {
408                        format!("{at}.items")
409                    } else {
410                        String::new()
411                    };
412                    let (inner, drawing) = self.group(items, to_device * local, &inner_at);
413                    if let (Some(records), Some(first)) = (&mut self.records, record_index) {
414                        let bounds = records[first..]
415                            .iter()
416                            .map(|record| record.bounds)
417                            .filter(|bounds| {
418                                bounds.area() > 0.0 || bounds.width() > 0.0 || bounds.height() > 0.0
419                            })
420                            .reduce(|a, b| a.union(b))
421                            .unwrap_or(kurbo::Rect::ZERO);
422                        records.insert(
423                            first,
424                            ItemPath {
425                                at: at.clone(),
426                                path: BezPath::new(),
427                                rule: FillRule::Nonzero,
428                                paint: false,
429                                bounds,
430                            },
431                        );
432                    }
433                    entries.extend(inner.into_iter().map(|entry| Entry {
434                        path: entry.path,
435                        relative: local * entry.relative,
436                    }));
437                    let ops = back_to_front(drawing);
438                    #[allow(clippy::cast_possible_truncation)]
439                    let opacity = transform.opacity.clamp(0.0, 1.0) as f32;
440                    if ops.is_empty() || opacity <= 0.0 {
441                        continue;
442                    }
443                    if opacity < 1.0 {
444                        let bounds = ops
445                            .iter()
446                            .filter_map(|(op, _)| match op {
447                                VectorOp::Fill { bounds, .. } => Some(*bounds),
448                                _ => None,
449                            })
450                            .fold(IRect::default(), IRect::union);
451                        let mut layer = Vec::with_capacity(ops.len() + 2);
452                        layer.push((VectorOp::PushLayer { opacity, bounds }, String::new()));
453                        layer.extend(ops);
454                        layer.push((VectorOp::PopLayer, String::new()));
455                        chunks.push(layer);
456                    } else {
457                        chunks.push(ops);
458                    }
459                }
460                EvaluatedItem::Geometry(geometry) => {
461                    let path = geometry.to_path(self.size);
462                    if self.records.is_some() {
463                        let device = to_device * path.clone();
464                        self.record(&at, device, FillRule::Nonzero, false);
465                    }
466                    entries.push(Entry {
467                        path,
468                        relative: Affine::IDENTITY,
469                    });
470                }
471                EvaluatedItem::Fill {
472                    paint,
473                    opacity,
474                    rule,
475                } => {
476                    let mut device = BezPath::new();
477                    for entry in &entries {
478                        device.extend(
479                            (to_device * entry.relative * entry.path.clone())
480                                .elements()
481                                .iter()
482                                .copied(),
483                        );
484                    }
485                    let device = project_far(&device, self.size.width, self.size.height);
486                    self.record(&at, device.clone(), *rule, true);
487                    if let Some(op) = self.fill_op(device, *rule, paint, *opacity, to_device) {
488                        chunks.push(vec![(op, at)]);
489                    }
490                }
491                EvaluatedItem::Stroke {
492                    paint,
493                    width,
494                    opacity,
495                    join,
496                    miter_limit,
497                    cap,
498                    dash,
499                    dash_offset,
500                } => {
501                    let unit = self.size.unit();
502                    let style = StrokeStyle {
503                        width: width * unit,
504                        join: *join,
505                        miter_limit: *miter_limit,
506                        cap: *cap,
507                        dash: dash.iter().map(|length| length.max(0.0) * unit).collect(),
508                        dash_offset: dash_offset * unit,
509                    };
510                    let mut local = BezPath::new();
511                    for entry in &entries {
512                        local.extend(
513                            (entry.relative * entry.path.clone())
514                                .elements()
515                                .iter()
516                                .copied(),
517                        );
518                    }
519                    let outline = stroke_outline(&local, &style, to_device);
520                    let outline = project_far(&outline, self.size.width, self.size.height);
521                    self.record(&at, outline.clone(), FillRule::Nonzero, true);
522                    if let Some(op) =
523                        self.fill_op(outline, FillRule::Nonzero, paint, *opacity, to_device)
524                    {
525                        chunks.push(vec![(op, at)]);
526                    }
527                }
528                EvaluatedItem::Trim {
529                    start,
530                    end,
531                    offset,
532                    mode,
533                } => {
534                    entries = trim_entries(&entries, to_device, *start, *end, *offset, *mode);
535                }
536            }
537        }
538        (entries, chunks)
539    }
540
541    fn fill_op(
542        &self,
543        path: BezPath,
544        rule: FillRule,
545        paint: &Paint,
546        opacity: f64,
547        to_device: Affine,
548    ) -> Option<VectorOp> {
549        #[allow(clippy::cast_possible_truncation)]
550        let opacity = opacity.clamp(0.0, 1.0) as f32;
551        if opacity <= 0.0 || path.elements().is_empty() || !affine::is_invertible(to_device) {
552            return None;
553        }
554        let bounds = IRect::covering(&path, self.canvas);
555        if bounds.is_empty() {
556            return None;
557        }
558        Some(VectorOp::Fill {
559            path: Arc::new(path),
560            rule,
561            paint: scene_paint(paint, to_device.inverse()),
562            opacity,
563            bounds,
564        })
565    }
566}
567
568/// Trims `entries`, measured in device pixels, keeping each entry's
569/// transform for what remains of it.
570fn trim_entries(
571    entries: &[Entry],
572    to_device: Affine,
573    start: f64,
574    end: f64,
575    offset: f64,
576    mode: TrimMode,
577) -> Vec<Entry> {
578    let span = TrimSpan { start, end, offset };
579    // Every subpath, with the entry it came from.
580    let mut owners = Vec::new();
581    let mut parts = Vec::new();
582    for (index, entry) in entries.iter().enumerate() {
583        for subpath in trim::subpaths(&entry.path) {
584            owners.push(index);
585            parts.push(Measured {
586                subpath,
587                measure: to_device * entry.relative,
588            });
589        }
590    }
591    let kept = match mode {
592        TrimMode::Together => trim::trim_together(&parts, span),
593        TrimMode::Individually => trim::trim_individually(&parts, span),
594    };
595    let mut result: Vec<Entry> = Vec::new();
596    for (part, subpath) in kept {
597        let relative = entries[owners[part]].relative;
598        match result.last_mut() {
599            Some(last) if last.relative == relative => trim::append(&mut last.path, &subpath),
600            _ => {
601                let mut path = BezPath::new();
602                trim::append(&mut path, &subpath);
603                result.push(Entry { path, relative });
604            }
605        }
606    }
607    result
608}
609
610/// `paint` as the scene paints it, through `inverse` from device pixels.
611#[must_use]
612pub fn scene_paint(paint: &Paint, inverse: Affine) -> ScenePaint {
613    let color = |value: alpha2_model::Rgba| [value.red, value.green, value.blue, value.alpha];
614    let stops = |list: &[alpha2_model::GradientStop]| {
615        list.iter()
616            .map(|stop| SceneStop {
617                offset: stop.offset,
618                color: color(stop.color),
619            })
620            .collect::<Vec<_>>()
621    };
622    let spread = |value: alpha2_model::Spread| match value {
623        alpha2_model::Spread::Pad => 0,
624        alpha2_model::Spread::Repeat => 1,
625        alpha2_model::Spread::Reflect => 2,
626    };
627    match paint {
628        Paint::Solid { color: value } => ScenePaint {
629            kind: PaintKind::Solid,
630            a: [0.0; 2],
631            b: [0.0; 2],
632            spread: 0,
633            stops: vec![SceneStop {
634                offset: 0.0,
635                color: color(*value),
636            }],
637            inverse,
638        },
639        Paint::LinearGradient {
640            start,
641            end,
642            stops: list,
643            spread: mode,
644        } => ScenePaint {
645            kind: PaintKind::Linear,
646            a: [start.x, start.y],
647            b: [end.x, end.y],
648            spread: spread(*mode),
649            stops: stops(list),
650            inverse,
651        },
652        Paint::RadialGradient {
653            center,
654            radius,
655            stops: list,
656            spread: mode,
657        } => ScenePaint {
658            kind: PaintKind::Radial,
659            a: [center.x, center.y],
660            b: [*radius, 0.0],
661            spread: spread(*mode),
662            stops: stops(list),
663            inverse,
664        },
665        Paint::ConicGradient {
666            center,
667            angle_degrees,
668            stops: list,
669        } => ScenePaint {
670            kind: PaintKind::Conic,
671            a: [center.x, center.y],
672            b: [angle_degrees.to_radians(), 0.0],
673            spread: 0,
674            stops: stops(list),
675            inverse,
676        },
677    }
678}
alpha2_geometry/tree.rs

alpha2_geometry/
tree.rs
