Add `non-zero` and `even-odd` fill rules to `path` and `polygon` (#4580)

Co-authored-by: Laurenz <laurmaedje@gmail.com>

9 files changed, 98 insertions, 27 deletions

diff --git a/crates/typst-pdf/src/content.rs b/crates/typst-pdf/src/content.rs
index d9830e43..e8876944 100644
--- a/crates/typst-pdf/src/content.rs
+++ b/crates/typst-pdf/src/content.rs
@@ -16,7 +16,8 @@ use typst::model::Destination;
 use typst::text::{color::is_color_glyph, Font, TextItem, TextItemView};
 use typst::utils::{Deferred, Numeric, SliceExt};
 use typst::visualize::{
-    FixedStroke, Geometry, Image, LineCap, LineJoin, Paint, Path, PathItem, Shape,
+    FillRule, FixedStroke, Geometry, Image, LineCap, LineJoin, Paint, Path, PathItem,
+    Shape,
 };
 
 use crate::color_font::ColorFontMap;
@@ -636,11 +637,13 @@ fn write_shape(ctx: &mut Builder, pos: Point, shape: &Shape) {
         }
     }
 
-    match (&shape.fill, stroke) {
-        (None, None) => unreachable!(),
-        (Some(_), None) => ctx.content.fill_nonzero(),
-        (None, Some(_)) => ctx.content.stroke(),
-        (Some(_), Some(_)) => ctx.content.fill_nonzero_and_stroke(),
+    match (&shape.fill, &shape.fill_rule, stroke) {
+        (None, _, None) => unreachable!(),
+        (Some(_), FillRule::NonZero, None) => ctx.content.fill_nonzero(),
+        (Some(_), FillRule::EvenOdd, None) => ctx.content.fill_even_odd(),
+        (None, _, Some(_)) => ctx.content.stroke(),
+        (Some(_), FillRule::NonZero, Some(_)) => ctx.content.fill_nonzero_and_stroke(),
+        (Some(_), FillRule::EvenOdd, Some(_)) => ctx.content.fill_even_odd_and_stroke(),
     };
 }
 
diff --git a/crates/typst-render/src/shape.rs b/crates/typst-render/src/shape.rs
index 360c2a4f..f31262ef 100644
--- a/crates/typst-render/src/shape.rs
+++ b/crates/typst-render/src/shape.rs
@@ -1,7 +1,8 @@
 use tiny_skia as sk;
 use typst::layout::{Abs, Axes, Point, Ratio, Size};
 use typst::visualize::{
-    DashPattern, FixedStroke, Geometry, LineCap, LineJoin, Path, PathItem, Shape,
+    DashPattern, FillRule, FixedStroke, Geometry, LineCap, LineJoin, Path, PathItem,
+    Shape,
 };
 
 use crate::{paint, AbsExt, State};
@@ -51,7 +52,10 @@ pub fn render_shape(canvas: &mut sk::Pixmap, state: State, shape: &Shape) -> Opt
             paint.anti_alias = false;
         }
 
-        let rule = sk::FillRule::default();
+        let rule = match shape.fill_rule {
+            FillRule::NonZero => sk::FillRule::Winding,
+            FillRule::EvenOdd => sk::FillRule::EvenOdd,
+        };
         canvas.fill_path(&path, &paint, rule, ts, state.mask);
     }
 
diff --git a/crates/typst-svg/src/paint.rs b/crates/typst-svg/src/paint.rs
index a382bd9d..364cdd23 100644
--- a/crates/typst-svg/src/paint.rs
+++ b/crates/typst-svg/src/paint.rs
@@ -5,7 +5,7 @@ use ttf_parser::OutlineBuilder;
 use typst::foundations::Repr;
 use typst::layout::{Angle, Axes, Frame, Quadrant, Ratio, Size, Transform};
 use typst::utils::hash128;
-use typst::visualize::{Color, Gradient, Paint, Pattern, RatioOrAngle};
+use typst::visualize::{Color, FillRule, Gradient, Paint, Pattern, RatioOrAngle};
 use xmlwriter::XmlWriter;
 
 use crate::{Id, SVGRenderer, State, SvgMatrix, SvgPathBuilder};
@@ -31,7 +31,13 @@ impl SVGRenderer {
     }
 
     /// Write a fill attribute.
-    pub(super) fn write_fill(&mut self, fill: &Paint, size: Size, ts: Transform) {
+    pub(super) fn write_fill(
+        &mut self,
+        fill: &Paint,
+        fill_rule: FillRule,
+        size: Size,
+        ts: Transform,
+    ) {
         match fill {
             Paint::Solid(color) => self.xml.write_attribute("fill", &color.encode()),
             Paint::Gradient(gradient) => {
@@ -43,6 +49,10 @@ impl SVGRenderer {
                 self.xml.write_attribute_fmt("fill", format_args!("url(#{id})"));
             }
         }
+        match fill_rule {
+            FillRule::NonZero => self.xml.write_attribute("fill-rule", "nonzero"),
+            FillRule::EvenOdd => self.xml.write_attribute("fill-rule", "evenodd"),
+        }
     }
 
     /// Pushes a gradient to the list of gradients to write SVG file.
diff --git a/crates/typst-svg/src/shape.rs b/crates/typst-svg/src/shape.rs
index 4caae2fd..12be2e22 100644
--- a/crates/typst-svg/src/shape.rs
+++ b/crates/typst-svg/src/shape.rs
@@ -17,6 +17,7 @@ impl SVGRenderer {
         if let Some(paint) = &shape.fill {
             self.write_fill(
                 paint,
+                shape.fill_rule,
                 self.shape_fill_size(state, paint, shape),
                 self.shape_paint_transform(state, paint, shape),
             );
diff --git a/crates/typst-svg/src/text.rs b/crates/typst-svg/src/text.rs
index 04b75123..6af93398 100644
--- a/crates/typst-svg/src/text.rs
+++ b/crates/typst-svg/src/text.rs
@@ -6,7 +6,7 @@ use ttf_parser::GlyphId;
 use typst::layout::{Abs, Point, Ratio, Size, Transform};
 use typst::text::{Font, TextItem};
 use typst::utils::hash128;
-use typst::visualize::{Image, Paint, RasterFormat, RelativeTo};
+use typst::visualize::{FillRule, Image, Paint, RasterFormat, RelativeTo};
 
 use crate::{SVGRenderer, State, SvgMatrix, SvgPathBuilder};
 
@@ -138,6 +138,7 @@ impl SVGRenderer {
         self.xml.write_attribute_fmt("x", format_args!("{x_offset}"));
         self.write_fill(
             &text.fill,
+            FillRule::default(),
             Size::new(Abs::pt(width), Abs::pt(height)),
             self.text_paint_transform(state, &text.fill),
         );
diff --git a/crates/typst/src/math/matrix.rs b/crates/typst/src/math/matrix.rs
index 95164e82..51449047 100644
--- a/crates/typst/src/math/matrix.rs
+++ b/crates/typst/src/math/matrix.rs
@@ -18,7 +18,7 @@ use crate::symbols::Symbol;
 use crate::syntax::{Span, Spanned};
 use crate::text::TextElem;
 use crate::utils::Numeric;
-use crate::visualize::{FixedStroke, Geometry, LineCap, Shape, Stroke};
+use crate::visualize::{FillRule, FixedStroke, Geometry, LineCap, Shape, Stroke};
 
 use super::delimiter_alignment;
 
@@ -597,6 +597,7 @@ fn line_item(length: Abs, vertical: bool, stroke: FixedStroke, span: Span) -> Fr
         Shape {
             geometry: line_geom,
             fill: None,
+            fill_rule: FillRule::default(),
             stroke: Some(stroke),
         },
         span,
diff --git a/crates/typst/src/visualize/path.rs b/crates/typst/src/visualize/path.rs
index df911426..0ba412cd 100644
--- a/crates/typst/src/visualize/path.rs
+++ b/crates/typst/src/visualize/path.rs
@@ -10,7 +10,7 @@ use crate::introspection::Locator;
 use crate::layout::{
     Abs, Axes, BlockElem, Frame, FrameItem, Length, Point, Region, Rel, Size,
 };
-use crate::visualize::{FixedStroke, Geometry, Paint, Shape, Stroke};
+use crate::visualize::{FillRule, FixedStroke, Geometry, Paint, Shape, Stroke};
 
 use PathVertex::{AllControlPoints, MirroredControlPoint, Vertex};
 
@@ -33,11 +33,12 @@ pub struct PathElem {
     ///
     /// When setting a fill, the default stroke disappears. To create a
     /// rectangle with both fill and stroke, you have to configure both.
-    ///
-    /// Currently all paths are filled according to the [non-zero winding
-    /// rule](https://en.wikipedia.org/wiki/Nonzero-rule).
     pub fill: Option<Paint>,
 
+    /// The rule used to fill the path.
+    #[default]
+    pub fill_rule: FillRule,
+
     /// How to [stroke] the path. This can be:
     ///
     /// Can be set to  `{none}` to disable the stroke or to `{auto}` for a
@@ -147,6 +148,7 @@ fn layout_path(
 
     // Prepare fill and stroke.
     let fill = elem.fill(styles);
+    let fill_rule = elem.fill_rule(styles);
     let stroke = match elem.stroke(styles) {
         Smart::Auto if fill.is_none() => Some(FixedStroke::default()),
         Smart::Auto => None,
@@ -154,7 +156,12 @@ fn layout_path(
     };
 
     let mut frame = Frame::soft(size);
-    let shape = Shape { geometry: Geometry::Path(path), stroke, fill };
+    let shape = Shape {
+        geometry: Geometry::Path(path),
+        stroke,
+        fill,
+        fill_rule,
+    };
     frame.push(Point::zero(), FrameItem::Shape(shape, elem.span()));
     Ok(frame)
 }
diff --git a/crates/typst/src/visualize/polygon.rs b/crates/typst/src/visualize/polygon.rs
index 120f41fc..deb5e100 100644
--- a/crates/typst/src/visualize/polygon.rs
+++ b/crates/typst/src/visualize/polygon.rs
@@ -9,7 +9,7 @@ use crate::introspection::Locator;
 use crate::layout::{Axes, BlockElem, Em, Frame, FrameItem, Length, Point, Region, Rel};
 use crate::syntax::Span;
 use crate::utils::Numeric;
-use crate::visualize::{FixedStroke, Geometry, Paint, Path, Shape, Stroke};
+use crate::visualize::{FillRule, FixedStroke, Geometry, Paint, Path, Shape, Stroke};
 
 /// A closed polygon.
 ///
@@ -32,11 +32,12 @@ pub struct PolygonElem {
     ///
     /// When setting a fill, the default stroke disappears. To create a
     /// rectangle with both fill and stroke, you have to configure both.
-    ///
-    /// Currently all polygons are filled according to the
-    /// [non-zero winding rule](https://en.wikipedia.org/wiki/Nonzero-rule).
     pub fill: Option<Paint>,
 
+    /// The rule used to fill the polygon.
+    #[default]
+    pub fill_rule: FillRule,
+
     /// How to [stroke] the polygon. This can be:
     ///
     /// Can be set to  `{none}` to disable the stroke or to `{auto}` for a
@@ -161,6 +162,7 @@ fn layout_polygon(
 
     // Prepare fill and stroke.
     let fill = elem.fill(styles);
+    let fill_rule = elem.fill_rule(styles);
     let stroke = match elem.stroke(styles) {
         Smart::Auto if fill.is_none() => Some(FixedStroke::default()),
         Smart::Auto => None,
@@ -175,7 +177,12 @@ fn layout_polygon(
     }
     path.close_path();
 
-    let shape = Shape { geometry: Geometry::Path(path), stroke, fill };
+    let shape = Shape {
+        geometry: Geometry::Path(path),
+        stroke,
+        fill,
+        fill_rule,
+    };
     frame.push(Point::zero(), FrameItem::Shape(shape, elem.span()));
     Ok(frame)
 }
diff --git a/crates/typst/src/visualize/shape.rs b/crates/typst/src/visualize/shape.rs
index 8564e1dd..e8a68fe3 100644
--- a/crates/typst/src/visualize/shape.rs
+++ b/crates/typst/src/visualize/shape.rs
@@ -2,7 +2,9 @@ use std::f64::consts::SQRT_2;
 
 use crate::diag::SourceResult;
 use crate::engine::Engine;
-use crate::foundations::{elem, Content, NativeElement, Packed, Show, Smart, StyleChain};
+use crate::foundations::{
+    elem, Cast, Content, NativeElement, Packed, Show, Smart, StyleChain,
+};
 use crate::introspection::Locator;
 use crate::layout::{
     Abs, Axes, BlockElem, Corner, Corners, Frame, FrameItem, Length, Point, Ratio,
@@ -583,10 +585,22 @@ pub struct Shape {
     pub geometry: Geometry,
     /// The shape's background fill.
     pub fill: Option<Paint>,
+    /// The shape's fill rule.
+    pub fill_rule: FillRule,
     /// The shape's border stroke.
     pub stroke: Option<FixedStroke>,
 }
 
+/// A path filling rule.
+#[derive(Debug, Default, Copy, Clone, Eq, PartialEq, Hash, Cast)]
+pub enum FillRule {
+    /// Specifies that "inside" is computed by a non-zero sum of signed edge crossings.
+    #[default]
+    NonZero,
+    /// Specifies that "inside" is computed by an odd number of edge crossings.
+    EvenOdd,
+}
+
 /// A shape's geometry.
 #[derive(Debug, Clone, Eq, PartialEq, Hash)]
 pub enum Geometry {
@@ -601,12 +615,22 @@ pub enum Geometry {
 impl Geometry {
     /// Fill the geometry without a stroke.
     pub fn filled(self, fill: Paint) -> Shape {
-        Shape { geometry: self, fill: Some(fill), stroke: None }
+        Shape {
+            geometry: self,
+            fill: Some(fill),
+            fill_rule: FillRule::default(),
+            stroke: None,
+        }
     }
 
     /// Stroke the geometry without a fill.
     pub fn stroked(self, stroke: FixedStroke) -> Shape {
-        Shape { geometry: self, fill: None, stroke: Some(stroke) }
+        Shape {
+            geometry: self,
+            fill: None,
+            fill_rule: FillRule::default(),
+            stroke: Some(stroke),
+        }
     }
 
     /// The bounding box of the geometry.
@@ -641,7 +665,12 @@ pub(crate) fn ellipse(
     path.cubic_to(point(rx, my), point(mx, ry), point(z, ry));
     path.cubic_to(point(-mx, ry), point(-rx, my), point(-rx, z));
 
-    Shape { geometry: Geometry::Path(path), stroke, fill }
+    Shape {
+        geometry: Geometry::Path(path),
+        stroke,
+        fill,
+        fill_rule: FillRule::default(),
+    }
 }
 
 /// Creates a new rectangle as a path.
@@ -704,7 +733,12 @@ fn simple_rect(
     fill: Option<Paint>,
     stroke: Option<FixedStroke>,
 ) -> Vec<Shape> {
-    vec![Shape { geometry: Geometry::Rect(size), fill, stroke }]
+    vec![Shape {
+        geometry: Geometry::Rect(size),
+        fill,
+        stroke,
+        fill_rule: FillRule::default(),
+    }]
 }
 
 fn corners_control_points(
@@ -779,6 +813,7 @@ fn segmented_rect(
         res.push(Shape {
             geometry: Geometry::Path(path),
             fill: Some(fill),
+            fill_rule: FillRule::default(),
             stroke: None,
         });
         stroke_insert += 1;
@@ -916,6 +951,7 @@ fn stroke_segment(
         geometry: Geometry::Path(path),
         stroke: Some(stroke),
         fill: None,
+        fill_rule: FillRule::default(),
     }
 }
 
@@ -1014,6 +1050,7 @@ fn fill_segment(
         geometry: Geometry::Path(path),
         stroke: None,
         fill: Some(stroke.paint.clone()),
+        fill_rule: FillRule::default(),
     }
 }