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 ops = build_scene_in(items, size, kurbo::Vec2::ZERO, size);
319    VectorScene::new(ops, size.width, size.height)
320}
321
322/// The operations `items` draw on a picture of `space` whose top-left
323/// corner lies at `origin` on a canvas of `canvas`, as an SVG viewBox
324/// places its picture: positions are normalized to `space`, lengths are
325/// fractions of its shorter side, and paints are in it. What they cover is
326/// clipped to `canvas`. [`build_scene`] is the case `space == canvas` at the
327/// origin.
328#[must_use]
329pub fn build_scene_in(
330    items: &[EvaluatedItem],
331    space: CanvasSize,
332    origin: kurbo::Vec2,
333    canvas: CanvasSize,
334) -> Vec<VectorOp> {
335    let mut builder = Builder::new(space, false, false);
336    builder.canvas = canvas_rect(canvas);
337    let (_, chunks) = builder.group(items, Affine::translate(origin), "");
338    back_to_front(chunks)
339        .into_iter()
340        .map(|(op, _)| op)
341        .collect()
342}
343
344fn canvas_rect(size: CanvasSize) -> IRect {
345    IRect::new(
346        0,
347        0,
348        i32::try_from(size.width).unwrap_or(i32::MAX),
349        i32::try_from(size.height).unwrap_or(i32::MAX),
350    )
351}
352
353/// The scene `items` draw, with the item each of its operations was drawn
354/// for (empty for a layer's push and pop).
355#[must_use]
356pub fn build_scene_with_items(
357    items: &[EvaluatedItem],
358    size: CanvasSize,
359) -> (VectorScene, Vec<String>) {
360    let mut builder = Builder::new(size, true, false);
361    let (_, chunks) = builder.group(items, Affine::IDENTITY, "items");
362    let (ops, owners): (Vec<_>, Vec<_>) = back_to_front(chunks).into_iter().unzip();
363    (VectorScene::new(ops, size.width, size.height), owners)
364}
365
366/// Every item's outline or painted area, in document order, for the
367/// editor's queries.
368#[must_use]
369pub fn item_paths(items: &[EvaluatedItem], size: CanvasSize) -> Vec<ItemPath> {
370    let mut builder = Builder::new(size, true, true);
371    builder.group(items, Affine::IDENTITY, "items");
372    builder.records.unwrap_or_default()
373}
374
375fn back_to_front(chunks: Chunks) -> Vec<(VectorOp, String)> {
376    chunks.into_iter().rev().flatten().collect()
377}
378
379impl Builder {
380    fn new(size: CanvasSize, named: bool, records: bool) -> Self {
381        Self {
382            size,
383            canvas: canvas_rect(size),
384            named,
385            records: records.then(Vec::new),
386        }
387    }
388
389    /// The pixel size of the space positions are normalized in.
390    #[allow(clippy::cast_precision_loss)]
391    fn space(&self) -> [f32; 2] {
392        [self.size.width as f32, self.size.height as f32]
393    }
394
395    fn record(&mut self, at: &str, path: BezPath, rule: FillRule, paint: bool) {
396        if let Some(records) = &mut self.records {
397            let bounds = if path.elements().is_empty() {
398                kurbo::Rect::ZERO
399            } else {
400                kurbo::Shape::bounding_box(&path)
401            };
402            records.push(ItemPath {
403                at: at.to_owned(),
404                path,
405                rule,
406                paint,
407                bounds,
408            });
409        }
410    }
411
412    /// Reads a group's items: the geometry it leaves for the enclosing group
413    /// (in this group's space) and its drawing.
414    #[allow(clippy::too_many_lines)]
415    fn group(
416        &mut self,
417        items: &[EvaluatedItem],
418        to_device: Affine,
419        at: &str,
420    ) -> (Vec<Entry>, Chunks) {
421        let mut entries: Vec<Entry> = Vec::new();
422        let mut chunks: Chunks = Vec::new();
423        for (index, item) in items.iter().enumerate() {
424            let at = if self.named {
425                format!("{at}[{index}]")
426            } else {
427                String::new()
428            };
429            match item {
430                EvaluatedItem::Group { items, transform } => {
431                    let local = transform.affine(self.size);
432                    let record_index = self.records.as_ref().map(Vec::len);
433                    let inner_at = if self.named {
434                        format!("{at}.items")
435                    } else {
436                        String::new()
437                    };
438                    let (inner, drawing) = self.group(items, to_device * local, &inner_at);
439                    if let (Some(records), Some(first)) = (&mut self.records, record_index) {
440                        let bounds = records[first..]
441                            .iter()
442                            .map(|record| record.bounds)
443                            .filter(|bounds| {
444                                bounds.area() > 0.0 || bounds.width() > 0.0 || bounds.height() > 0.0
445                            })
446                            .reduce(|a, b| a.union(b))
447                            .unwrap_or(kurbo::Rect::ZERO);
448                        records.insert(
449                            first,
450                            ItemPath {
451                                at: at.clone(),
452                                path: BezPath::new(),
453                                rule: FillRule::Nonzero,
454                                paint: false,
455                                bounds,
456                            },
457                        );
458                    }
459                    entries.extend(inner.into_iter().map(|entry| Entry {
460                        path: entry.path,
461                        relative: local * entry.relative,
462                    }));
463                    let ops = back_to_front(drawing);
464                    #[allow(clippy::cast_possible_truncation)]
465                    let opacity = transform.opacity.clamp(0.0, 1.0) as f32;
466                    if ops.is_empty() || opacity <= 0.0 {
467                        continue;
468                    }
469                    if opacity < 1.0 {
470                        let bounds = ops
471                            .iter()
472                            .filter_map(|(op, _)| match op {
473                                VectorOp::Fill { bounds, .. } => Some(*bounds),
474                                _ => None,
475                            })
476                            .fold(IRect::default(), IRect::union);
477                        let mut layer = Vec::with_capacity(ops.len() + 2);
478                        layer.push((VectorOp::PushLayer { opacity, bounds }, String::new()));
479                        layer.extend(ops);
480                        layer.push((VectorOp::PopLayer, String::new()));
481                        chunks.push(layer);
482                    } else {
483                        chunks.push(ops);
484                    }
485                }
486                EvaluatedItem::Geometry(geometry) => {
487                    let path = geometry.to_path(self.size);
488                    if self.records.is_some() {
489                        let device = to_device * path.clone();
490                        self.record(&at, device, FillRule::Nonzero, false);
491                    }
492                    entries.push(Entry {
493                        path,
494                        relative: Affine::IDENTITY,
495                    });
496                }
497                EvaluatedItem::Fill {
498                    paint,
499                    opacity,
500                    rule,
501                } => {
502                    let mut device = BezPath::new();
503                    for entry in &entries {
504                        device.extend(
505                            (to_device * entry.relative * entry.path.clone())
506                                .elements()
507                                .iter()
508                                .copied(),
509                        );
510                    }
511                    let device = project_far(&device, self.size.width, self.size.height);
512                    self.record(&at, device.clone(), *rule, true);
513                    if let Some(op) = self.fill_op(device, *rule, paint, *opacity, to_device) {
514                        chunks.push(vec![(op, at)]);
515                    }
516                }
517                EvaluatedItem::Stroke {
518                    paint,
519                    width,
520                    opacity,
521                    join,
522                    miter_limit,
523                    cap,
524                    dash,
525                    dash_offset,
526                } => {
527                    let unit = self.size.unit();
528                    let style = StrokeStyle {
529                        width: width * unit,
530                        join: *join,
531                        miter_limit: *miter_limit,
532                        cap: *cap,
533                        dash: dash.iter().map(|length| length.max(0.0) * unit).collect(),
534                        dash_offset: dash_offset * unit,
535                    };
536                    let mut local = BezPath::new();
537                    for entry in &entries {
538                        local.extend(
539                            (entry.relative * entry.path.clone())
540                                .elements()
541                                .iter()
542                                .copied(),
543                        );
544                    }
545                    let outline = stroke_outline(&local, &style, to_device);
546                    let outline = project_far(&outline, self.size.width, self.size.height);
547                    self.record(&at, outline.clone(), FillRule::Nonzero, true);
548                    if let Some(op) =
549                        self.fill_op(outline, FillRule::Nonzero, paint, *opacity, to_device)
550                    {
551                        chunks.push(vec![(op, at)]);
552                    }
553                }
554                EvaluatedItem::Trim {
555                    start,
556                    end,
557                    offset,
558                    mode,
559                } => {
560                    entries = trim_entries(&entries, to_device, *start, *end, *offset, *mode);
561                }
562            }
563        }
564        (entries, chunks)
565    }
566
567    fn fill_op(
568        &self,
569        path: BezPath,
570        rule: FillRule,
571        paint: &Paint,
572        opacity: f64,
573        to_device: Affine,
574    ) -> Option<VectorOp> {
575        #[allow(clippy::cast_possible_truncation)]
576        let opacity = opacity.clamp(0.0, 1.0) as f32;
577        if opacity <= 0.0 || path.elements().is_empty() || !affine::is_invertible(to_device) {
578            return None;
579        }
580        let bounds = IRect::covering(&path, self.canvas);
581        if bounds.is_empty() {
582            return None;
583        }
584        Some(VectorOp::Fill {
585            path: Arc::new(path),
586            rule,
587            paint: scene_paint(paint, to_device.inverse(), self.space()),
588            opacity,
589            bounds,
590        })
591    }
592}
593
594/// Trims `entries`, measured in device pixels, keeping each entry's
595/// transform for what remains of it.
596fn trim_entries(
597    entries: &[Entry],
598    to_device: Affine,
599    start: f64,
600    end: f64,
601    offset: f64,
602    mode: TrimMode,
603) -> Vec<Entry> {
604    let span = TrimSpan { start, end, offset };
605    // Every subpath, with the entry it came from.
606    let mut owners = Vec::new();
607    let mut parts = Vec::new();
608    for (index, entry) in entries.iter().enumerate() {
609        for subpath in trim::subpaths(&entry.path) {
610            owners.push(index);
611            parts.push(Measured {
612                subpath,
613                measure: to_device * entry.relative,
614            });
615        }
616    }
617    let kept = match mode {
618        TrimMode::Together => trim::trim_together(&parts, span),
619        TrimMode::Individually => trim::trim_individually(&parts, span),
620    };
621    let mut result: Vec<Entry> = Vec::new();
622    for (part, subpath) in kept {
623        let relative = entries[owners[part]].relative;
624        match result.last_mut() {
625            Some(last) if last.relative == relative => trim::append(&mut last.path, &subpath),
626            _ => {
627                let mut path = BezPath::new();
628                trim::append(&mut path, &subpath);
629                result.push(Entry { path, relative });
630            }
631        }
632    }
633    result
634}
635
636/// `paint` as the scene paints it, through `inverse` from device pixels into
637/// a paint space of `space` pixels.
638#[must_use]
639pub fn scene_paint(paint: &Paint, inverse: Affine, space: [f32; 2]) -> ScenePaint {
640    let color = |value: alpha2_model::Rgba| [value.red, value.green, value.blue, value.alpha];
641    let stops = |list: &[alpha2_model::GradientStop]| {
642        list.iter()
643            .map(|stop| SceneStop {
644                offset: stop.offset,
645                color: color(stop.color),
646            })
647            .collect::<Vec<_>>()
648    };
649    let spread = |value: alpha2_model::Spread| match value {
650        alpha2_model::Spread::Pad => 0,
651        alpha2_model::Spread::Repeat => 1,
652        alpha2_model::Spread::Reflect => 2,
653    };
654    match paint {
655        Paint::Solid { color: value } => ScenePaint {
656            kind: PaintKind::Solid,
657            a: [0.0; 2],
658            b: [0.0; 2],
659            spread: 0,
660            stops: vec![SceneStop {
661                offset: 0.0,
662                color: color(*value),
663            }],
664            inverse,
665            space,
666        },
667        Paint::LinearGradient {
668            start,
669            end,
670            stops: list,
671            spread: mode,
672        } => ScenePaint {
673            kind: PaintKind::Linear,
674            a: [start.x, start.y],
675            b: [end.x, end.y],
676            spread: spread(*mode),
677            stops: stops(list),
678            inverse,
679            space,
680        },
681        Paint::RadialGradient {
682            center,
683            radius,
684            stops: list,
685            spread: mode,
686        } => ScenePaint {
687            kind: PaintKind::Radial,
688            a: [center.x, center.y],
689            b: [*radius, 0.0],
690            spread: spread(*mode),
691            stops: stops(list),
692            inverse,
693            space,
694        },
695        Paint::ConicGradient {
696            center,
697            angle_degrees,
698            stops: list,
699        } => ScenePaint {
700            kind: PaintKind::Conic,
701            a: [center.x, center.y],
702            b: [angle_degrees.to_radians(), 0.0],
703            spread: 0,
704            stops: stops(list),
705            inverse,
706            space,
707        },
708    }
709}
alpha2_geometry/tree.rs

alpha2_geometry/
tree.rs
