Skip to main content

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