Merge pull request #69 from typst/shapeees

Advanced shapes

5 files changed, 322 insertions, 1 deletions

diff --git a/src/geom/mod.rs b/src/geom/mod.rs
index a6f53c87..bdd08fe5 100644
--- a/src/geom/mod.rs
+++ b/src/geom/mod.rs
@@ -13,6 +13,7 @@ mod paint;
 mod path;
 mod point;
 mod ratio;
+mod rect;
 mod relative;
 mod scalar;
 mod sides;
@@ -30,6 +31,7 @@ pub use paint::*;
 pub use path::*;
 pub use point::*;
 pub use ratio::*;
+pub use rect::*;
 pub use relative::*;
 pub use scalar::*;
 pub use sides::*;
@@ -60,6 +62,50 @@ pub trait Get<Index> {
     }
 }
 
+/// A geometric shape with optional fill and stroke.
+#[derive(Debug, Clone, Eq, PartialEq)]
+pub struct Shape {
+    /// The shape's geometry.
+    pub geometry: Geometry,
+    /// The shape's background fill.
+    pub fill: Option<Paint>,
+    /// The shape's border stroke.
+    pub stroke: Option<Stroke>,
+}
+
+/// A shape's geometry.
+#[derive(Debug, Clone, Eq, PartialEq)]
+pub enum Geometry {
+    /// A line to a point (relative to its position).
+    Line(Point),
+    /// A rectangle with its origin in the topleft corner.
+    Rect(Size),
+    /// A ellipse with its origin in the topleft corner.
+    Ellipse(Size),
+    /// A bezier path.
+    Path(Path),
+}
+
+impl Geometry {
+    /// Fill the geometry without a stroke.
+    pub fn filled(self, fill: Paint) -> Shape {
+        Shape {
+            geometry: self,
+            fill: Some(fill),
+            stroke: None,
+        }
+    }
+
+    /// Stroke the geometry without a fill.
+    pub fn stroked(self, stroke: Stroke) -> Shape {
+        Shape {
+            geometry: self,
+            fill: None,
+            stroke: Some(stroke),
+        }
+    }
+}
+
 /// A numeric type.
 pub trait Numeric:
     Sized
diff --git a/src/geom/path.rs b/src/geom/path.rs
index 836be1b4..d0c3c75d 100644
--- a/src/geom/path.rs
+++ b/src/geom/path.rs
@@ -71,3 +71,22 @@ impl Path {
         self.0.push(PathElement::ClosePath);
     }
 }
+
+/// Get the control points for a bezier curve that describes a circular arc for
+/// a start point, an end point and a center of the circle whose arc connects
+/// the two.
+pub fn bezier_arc(start: Point, center: Point, end: Point) -> [Point; 4] {
+    // https://stackoverflow.com/a/44829356/1567835
+    let a = start - center;
+    let b = end - center;
+
+    let q1 = a.x.to_raw() * a.x.to_raw() + a.y.to_raw() * a.y.to_raw();
+    let q2 = q1 + a.x.to_raw() * b.x.to_raw() + a.y.to_raw() * b.y.to_raw();
+    let k2 = (4.0 / 3.0) * ((2.0 * q1 * q2).sqrt() - q2)
+        / (a.x.to_raw() * b.y.to_raw() - a.y.to_raw() * b.x.to_raw());
+
+    let control_1 = Point::new(center.x + a.x - k2 * a.y, center.y + a.y + k2 * a.x);
+    let control_2 = Point::new(center.x + b.x + k2 * b.y, center.y + b.y - k2 * b.x);
+
+    [start, control_1, control_2, end]
+}
diff --git a/src/geom/rect.rs b/src/geom/rect.rs
new file mode 100644
index 00000000..34160b04
--- /dev/null
+++ b/src/geom/rect.rs
@@ -0,0 +1,184 @@
+use super::*;
+
+use std::mem;
+
+/// A rectangle with rounded corners.
+#[derive(Debug, Copy, Clone, PartialEq)]
+pub struct Rect {
+    size: Size,
+    radius: Sides<Length>,
+}
+
+impl Rect {
+    /// Create a new rectangle.
+    pub fn new(size: Size, radius: Sides<Length>) -> Self {
+        Self { size, radius }
+    }
+
+    /// Output all constituent shapes of the rectangle in order. The last one is
+    /// in the foreground. The function will output multiple items if the stroke
+    /// properties differ by side.
+    pub fn shapes(
+        self,
+        fill: Option<Paint>,
+        stroke: Sides<Option<Stroke>>,
+    ) -> Vec<Shape> {
+        let mut res = vec![];
+        if fill.is_some() || (stroke.iter().any(Option::is_some) && stroke.is_uniform()) {
+            res.push(Shape {
+                geometry: self.fill_geometry(),
+                fill,
+                stroke: if stroke.is_uniform() { stroke.top } else { None },
+            });
+        }
+
+        if !stroke.is_uniform() {
+            for (path, stroke) in self.stroke_segments(stroke) {
+                if stroke.is_some() {
+                    res.push(Shape {
+                        geometry: Geometry::Path(path),
+                        fill: None,
+                        stroke,
+                    });
+                }
+            }
+        }
+
+        res
+    }
+
+    /// Output the shape of the rectangle as a path or primitive rectangle,
+    /// depending on whether it is rounded.
+    fn fill_geometry(self) -> Geometry {
+        if self.radius.iter().copied().all(Length::is_zero) {
+            Geometry::Rect(self.size)
+        } else {
+            let mut paths = self.stroke_segments(Sides::splat(None));
+            assert_eq!(paths.len(), 1);
+
+            Geometry::Path(paths.pop().unwrap().0)
+        }
+    }
+
+    /// Output the minimum number of paths along the rectangles border.
+    fn stroke_segments(
+        self,
+        strokes: Sides<Option<Stroke>>,
+    ) -> Vec<(Path, Option<Stroke>)> {
+        let mut res = vec![];
+
+        let mut connection = Connection::default();
+        let mut path = Path::new();
+        let mut always_continuous = true;
+
+        for side in [Side::Top, Side::Right, Side::Bottom, Side::Left] {
+            let is_continuous = strokes.get(side) == strokes.get(side.next_cw());
+            connection = connection.advance(is_continuous && side != Side::Left);
+            always_continuous &= is_continuous;
+
+            draw_side(
+                &mut path,
+                side,
+                self.size,
+                self.radius.get(side.next_ccw()),
+                self.radius.get(side),
+                connection,
+            );
+
+            if !is_continuous {
+                res.push((mem::take(&mut path), strokes.get(side)));
+            }
+        }
+
+        if always_continuous {
+            path.close_path();
+        }
+
+        if !path.0.is_empty() {
+            res.push((path, strokes.left));
+        }
+
+        res
+    }
+}
+
+/// Draws one side of the rounded rectangle. Will always draw the left arc. The
+/// right arc will be drawn halfway iff there is no connection.
+fn draw_side(
+    path: &mut Path,
+    side: Side,
+    size: Size,
+    radius_left: Length,
+    radius_right: Length,
+    connection: Connection,
+) {
+    let angle_left = Angle::deg(if connection.prev { 90.0 } else { 45.0 });
+    let angle_right = Angle::deg(if connection.next { 90.0 } else { 45.0 });
+
+    let length = size.get(side.axis());
+
+    // The arcs for a border of the rectangle along the x-axis, starting at (0,0).
+    let p1 = Point::with_x(radius_left);
+    let mut arc1 = bezier_arc(
+        p1 + Point::new(
+            -angle_left.sin() * radius_left,
+            (1.0 - angle_left.cos()) * radius_left,
+        ),
+        Point::new(radius_left, radius_left),
+        p1,
+    );
+
+    let p2 = Point::with_x(length - radius_right);
+    let mut arc2 = bezier_arc(
+        p2,
+        Point::new(length - radius_right, radius_right),
+        p2 + Point::new(
+            angle_right.sin() * radius_right,
+            (1.0 - angle_right.cos()) * radius_right,
+        ),
+    );
+
+    let transform = match side {
+        Side::Left => Transform::rotate(Angle::deg(-90.0))
+            .post_concat(Transform::translate(Length::zero(), size.y)),
+        Side::Bottom => Transform::rotate(Angle::deg(180.0))
+            .post_concat(Transform::translate(size.x, size.y)),
+        Side::Right => Transform::rotate(Angle::deg(90.0))
+            .post_concat(Transform::translate(size.x, Length::zero())),
+        _ => Transform::identity(),
+    };
+
+    arc1 = arc1.map(|x| x.transform(transform));
+    arc2 = arc2.map(|x| x.transform(transform));
+
+    if !connection.prev {
+        path.move_to(if radius_left.is_zero() { arc1[3] } else { arc1[0] });
+    }
+
+    if !radius_left.is_zero() {
+        path.cubic_to(arc1[1], arc1[2], arc1[3]);
+    }
+
+    path.line_to(arc2[0]);
+
+    if !connection.next && !radius_right.is_zero() {
+        path.cubic_to(arc2[1], arc2[2], arc2[3]);
+    }
+}
+
+/// A state machine that indicates which sides of the border strokes in a 2D
+/// polygon are connected to their neighboring sides.
+#[derive(Debug, Default, Copy, Clone, PartialEq, Eq)]
+struct Connection {
+    prev: bool,
+    next: bool,
+}
+
+impl Connection {
+    /// Advance to the next clockwise side of the polygon. The argument
+    /// indicates whether the border is connected on the right side of the next
+    /// edge.
+    pub fn advance(self, next: bool) -> Self {
+        Self { prev: self.next, next }
+    }
+}
diff --git a/src/geom/sides.rs b/src/geom/sides.rs
index 3584a1ce..43e470d2 100644
--- a/src/geom/sides.rs
+++ b/src/geom/sides.rs
@@ -31,6 +31,45 @@ impl<T> Sides<T> {
             bottom: value,
         }
     }
+
+    /// Maps the individual fields with `f`.
+    pub fn map<F, U>(self, mut f: F) -> Sides<U>
+    where
+        F: FnMut(T) -> U,
+    {
+        Sides {
+            left: f(self.left),
+            top: f(self.top),
+            right: f(self.right),
+            bottom: f(self.bottom),
+        }
+    }
+
+    /// Zip two instances into an instance.
+    pub fn zip<F, V, W>(self, other: Sides<V>, mut f: F) -> Sides<W>
+    where
+        F: FnMut(T, V, Side) -> W,
+    {
+        Sides {
+            left: f(self.left, other.left, Side::Left),
+            top: f(self.top, other.top, Side::Top),
+            right: f(self.right, other.right, Side::Right),
+            bottom: f(self.bottom, other.bottom, Side::Bottom),
+        }
+    }
+
+    /// Returns an iterator over the sides.
+    pub fn iter(&self) -> impl Iterator<Item = &T> {
+        [&self.left, &self.top, &self.right, &self.bottom].into_iter()
+    }
+
+    /// Returns whether all sides are equal.
+    pub fn is_uniform(&self) -> bool
+    where
+        T: PartialEq,
+    {
+        self.left == self.top && self.top == self.right && self.right == self.bottom
+    }
 }
 
 impl<T> Sides<T>
@@ -100,4 +139,32 @@ impl Side {
             Self::Bottom => Self::Top,
         }
     }
+
+    /// The next side, clockwise.
+    pub fn next_cw(self) -> Self {
+        match self {
+            Self::Left => Self::Top,
+            Self::Top => Self::Right,
+            Self::Right => Self::Bottom,
+            Self::Bottom => Self::Left,
+        }
+    }
+
+    /// The next side, counter-clockwise.
+    pub fn next_ccw(self) -> Self {
+        match self {
+            Self::Left => Self::Bottom,
+            Self::Top => Self::Left,
+            Self::Right => Self::Top,
+            Self::Bottom => Self::Right,
+        }
+    }
+
+    /// Return the corresponding axis.
+    pub fn axis(self) -> SpecAxis {
+        match self {
+            Self::Left | Self::Right => SpecAxis::Vertical,
+            Self::Top | Self::Bottom => SpecAxis::Horizontal,
+        }
+    }
 }
diff --git a/src/geom/transform.rs b/src/geom/transform.rs
index 28a1af80..40c8e9e4 100644
--- a/src/geom/transform.rs
+++ b/src/geom/transform.rs
@@ -53,7 +53,7 @@ impl Transform {
     }
 
     /// Pre-concatenate another transformation.
-    pub fn pre_concat(&self, prev: Self) -> Self {
+    pub fn pre_concat(self, prev: Self) -> Self {
         Transform {
             sx: self.sx * prev.sx + self.kx * prev.ky,
             ky: self.ky * prev.sx + self.sy * prev.ky,
@@ -63,6 +63,11 @@ impl Transform {
             ty: self.ky.of(prev.tx) + self.sy.of(prev.ty) + self.ty,
         }
     }
+
+    /// Post-concatenate another transformation.
+    pub fn post_concat(self, next: Self) -> Self {
+        next.pre_concat(self)
+    }
 }
 
 impl Default for Transform {