alpha2_geometry/
tree.rs

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

alpha2_geometry/
tree.rs
