crates/encoding/src/estimate.rs - external/github.com/linebender/vello - Git at Google

 // Copyright 2024 the Vello Authors
 // SPDX-License-Identifier: Apache-2.0 OR MIT

 //! This utility provides conservative size estimation for buffer allocations backing
 //! GPU bump memory. This estimate relies on heuristics and naturally overestimates.

 use super::{BumpAllocatorMemory, BumpAllocators, Transform};
 use peniko::kurbo::{Cap, Join, PathEl, Point, Stroke, Vec2};

 const RSQRT_OF_TOL: f64 = 2.2360679775; // tol = 0.2

 #[derive(Clone, Default)]
 pub struct BumpEstimator {
     // TODO: support binning
     // TODO: support ptcl
     // TODO: support tile

     // NOTE: The segment count estimation could use further refinement, particularly to handle
     // viewport clipping and rotation applied to fragments during append. We can produce a more
     // optimal result under scale and rotation if we track more data for each shape during insertion
     // and defer the final tally to resolve-time (in which we could evaluate the estimates using
     // precisely transformed coordinates). For now we apply a fudge factor of sqrt(2) and inflate
     // the number of tile crossing (a near~diagonal line orientation would result in worst case for
     // the number of intersected tiles) to account for this.
     //
     // Accounting for viewport clipping (for the right and bottom edges of the viewport) is simply
     // impossible at insertion time as the render target dimensions are unknown. We could
     // potentially account for clipping (including clip shapes/layers) by tracking bounding boxes
     // during insertion and resolving all clips at tally time (e.g. one could come up with a
     // heuristic for scaling the counts based on the proportions of a clipped bbox area).
     //
     // Since we currently don't account for clipping, this will always overshoot when clips are
     // present and when the bounding box of a shape is partially or wholly outside the viewport.
     segments: u32,
     lines: LineSoup,
 }

 impl BumpEstimator {
     pub fn new() -> Self {
         Self::default()
     }

     pub fn reset(&mut self) {
         *self = Self::default();
     }

     /// Combine the counts of this estimator with `other` after applying an optional `transform`.
     pub fn append(&mut self, other: &Self, transform: Option<&Transform>) {
         let scale = transform_scale(transform);
         self.segments += (other.segments as f64 * scale).ceil() as u32;
         self.lines.add(&other.lines, scale);
     }

     pub fn count_path(
         &mut self,
         path: impl Iterator<Item = PathEl>,
         t: &Transform,
         stroke: Option<&Stroke>,
     ) {
         let mut caps = 1;
         let mut joins: u32 = 0;
         let mut lineto_lines = 0;
         let mut fill_close_lines = 1;
         let mut curve_lines = 0;
         let mut curve_count = 0;
         let mut segments = 0;

         // Track the path state to correctly count empty paths and close joins.
         let mut first_pt = None;
         let mut last_pt = None;
         let scale = transform_scale(Some(t));
         let scaled_width = stroke.map(|s| s.width * scale).unwrap_or(0.);
         let offset_fudge = scaled_width.sqrt().max(1.);
         for el in path {
             match el {
                 PathEl::MoveTo(p0) => {
                     first_pt = Some(p0);
                     if last_pt.is_none() {
                         continue;
                     }
                     caps += 1;
                     joins = joins.saturating_sub(1);
                     fill_close_lines += 1;
                     segments += count_segments_for_line(first_pt.unwrap(), last_pt.unwrap(), t);
                     last_pt = None;
                 }
                 PathEl::ClosePath => {
                     if last_pt.is_some() {
                         joins += 1;
                         lineto_lines += 1;
                         segments += count_segments_for_line(first_pt.unwrap(), last_pt.unwrap(), t);
                     }
                     last_pt = first_pt;
                 }
                 PathEl::LineTo(p0) => {
                     last_pt = Some(p0);
                     joins += 1;
                     lineto_lines += 1;
                     segments += count_segments_for_line(first_pt.unwrap(), last_pt.unwrap(), t);
                 }
                 PathEl::QuadTo(p1, p2) => {
                     let Some(p0) = last_pt.or(first_pt) else {
                         continue;
                     };
                     last_pt = Some(p2);

                     let p0 = p0.to_vec2();
                     let p1 = p1.to_vec2();
                     let p2 = p2.to_vec2();
                     let lines = offset_fudge * wang::quadratic(RSQRT_OF_TOL, p0, p1, p2, t);

                     curve_lines += lines.ceil() as u32;
                     curve_count += 1;
                     joins += 1;

                     let segs = offset_fudge * count_segments_for_quadratic(p0, p1, p2, t);
                     segments += segs.ceil().max(lines.ceil()) as u32;
                 }
                 PathEl::CurveTo(p1, p2, p3) => {
                     let Some(p0) = last_pt.or(first_pt) else {
                         continue;
                     };
                     last_pt = Some(p3);

                     let p0 = p0.to_vec2();
                     let p1 = p1.to_vec2();
                     let p2 = p2.to_vec2();
                     let p3 = p3.to_vec2();
                     let lines = offset_fudge * wang::cubic(RSQRT_OF_TOL, p0, p1, p2, p3, t);

                     curve_lines += lines.ceil() as u32;
                     curve_count += 1;
                     joins += 1;
                     let segs = count_segments_for_cubic(p0, p1, p2, p3, t);
                     segments += segs.ceil().max(lines.ceil()) as u32;
                 }
             }
         }

         let Some(style) = stroke else {
             self.lines.linetos += lineto_lines + fill_close_lines;
             self.lines.curves += curve_lines;
             self.lines.curve_count += curve_count;
             self.segments += segments;

             // Account for the implicit close
             if let (Some(first_pt), Some(last_pt)) = (first_pt, last_pt) {
                 self.segments += count_segments_for_line(first_pt, last_pt, t);
             }
             return;
         };

         // For strokes, double-count the lines to estimate offset curves.
         self.lines.linetos += 2 * lineto_lines;
         self.lines.curves += 2 * curve_lines;
         self.lines.curve_count += 2 * curve_count;
         self.segments += 2 * segments;

         self.count_stroke_caps(style.start_cap, scaled_width, caps);
         self.count_stroke_caps(style.end_cap, scaled_width, caps);
         self.count_stroke_joins(style.join, scaled_width, style.miter_limit, joins);
     }

     /// Produce the final total, applying an optional transform to all content.
     pub fn tally(&self, transform: Option<&Transform>) -> BumpAllocatorMemory {
         let scale = transform_scale(transform);

         // The post-flatten line estimate.
         let lines = self.lines.tally(scale);

         // The estimate for tile crossings for lines. Here we ensure that there are at least as many
         // segments as there are lines, in case `segments` was underestimated at small scales.
         let n_segments = ((self.segments as f64 * scale).ceil() as u32).max(lines);

         let bump = BumpAllocators {
             failed: 0,
             // TODO: we can provide a tighter bound here but for now we
             // assume that binning must be bounded by the segment count.
             binning: n_segments,
             ptcl: 0,
             tile: 0,
             blend: 0,
             seg_counts: n_segments,
             segments: n_segments,
             lines,
         };
         bump.memory()
     }

     fn count_stroke_caps(&mut self, style: Cap, scaled_width: f64, count: u32) {
         match style {
             Cap::Butt => {
                 self.lines.linetos += count;
                 self.segments += count_segments_for_line_length(scaled_width) * count;
             }
             Cap::Square => {
                 self.lines.linetos += 3 * count;
                 self.segments += count_segments_for_line_length(scaled_width) * count;
                 self.segments += 2 * count_segments_for_line_length(0.5 * scaled_width) * count;
             }
             Cap::Round => {
                 let (arc_lines, line_len) = estimate_arc_lines(scaled_width);
                 self.lines.curves += count * arc_lines;
                 self.lines.curve_count += 1;
                 self.segments += count * arc_lines * count_segments_for_line_length(line_len);
             }
         }
     }

     fn count_stroke_joins(&mut self, style: Join, scaled_width: f64, miter_limit: f64, count: u32) {
         match style {
             Join::Bevel => {
                 self.lines.linetos += count;
                 self.segments += count_segments_for_line_length(scaled_width) * count;
             }
             Join::Miter => {
                 let max_miter_len = scaled_width * miter_limit;
                 self.lines.linetos += 2 * count;
                 self.segments += 2 * count * count_segments_for_line_length(max_miter_len);
             }
             Join::Round => {
                 let (arc_lines, line_len) = estimate_arc_lines(scaled_width);
                 self.lines.curves += count * arc_lines;
                 self.lines.curve_count += 1;
                 self.segments += count * arc_lines * count_segments_for_line_length(line_len);
             }
         }

         // Count inner join lines
         self.lines.linetos += count;
         self.segments += count_segments_for_line_length(scaled_width) * count;
     }
 }

 fn estimate_arc_lines(scaled_stroke_width: f64) -> (u32, f64) {
     // These constants need to be kept consistent with the definitions in `flatten_arc` in
     // flatten.wgsl.
     // TODO: It would be better if these definitions were shared/configurable. For example an
     // option is for all tolerances to be parameters to the estimator as well as the GPU pipelines
     // (the latter could be in the form of a config uniform) which would help to keep them in
     // sync.
     const MIN_THETA: f64 = 1e-6;
     const TOL: f64 = 0.25;
     let radius = TOL.max(scaled_stroke_width * 0.5);
     let theta = (2. * (1. - TOL / radius).acos()).max(MIN_THETA);
     let arc_lines = ((std::f64::consts::FRAC_PI_2 / theta).ceil() as u32).max(2);
     (arc_lines, 2. * theta.sin() * radius)
 }

 #[derive(Clone, Default)]
 struct LineSoup {
     // Explicit lines (such as linetos and non-round stroke caps/joins) and Bezier curves
     // get tracked separately to ensure that explicit lines remain scale invariant.
     linetos: u32,
     curves: u32,

     // Curve count is simply used to ensure a minimum number of lines get counted for each curve
     // at very small scales to reduce the chances of an under-estimate.
     curve_count: u32,
 }

 impl LineSoup {
     fn tally(&self, scale: f64) -> u32 {
         let curves = self
             .scaled_curve_line_count(scale)
             .max(5 * self.curve_count);

         self.linetos + curves
     }

     fn scaled_curve_line_count(&self, scale: f64) -> u32 {
         (self.curves as f64 * scale.sqrt()).ceil() as u32
     }

     fn add(&mut self, other: &LineSoup, scale: f64) {
         self.linetos += other.linetos;
         self.curves += other.scaled_curve_line_count(scale);
         self.curve_count += other.curve_count;
     }
 }

 // TODO: The 32-bit Vec2 definition from cpu_shaders/util.rs could come in handy here.
 fn transform(t: &Transform, v: Vec2) -> Vec2 {
     Vec2::new(
         t.matrix[0] as f64 * v.x + t.matrix[2] as f64 * v.y,
         t.matrix[1] as f64 * v.x + t.matrix[3] as f64 * v.y,
     )
 }

 fn transform_scale(t: Option<&Transform>) -> f64 {
     match t {
         Some(t) => {
             let m = t.matrix;
             let v1x = m[0] as f64 + m[3] as f64;
             let v2x = m[0] as f64 - m[3] as f64;
             let v1y = m[1] as f64 - m[2] as f64;
             let v2y = m[1] as f64 + m[2] as f64;
             (v1x * v1x + v1y * v1y).sqrt() + (v2x * v2x + v2y * v2y).sqrt()
         }
         None => 1.,
     }
 }

 fn approx_arc_length_cubic(p0: Vec2, p1: Vec2, p2: Vec2, p3: Vec2) -> f64 {
     let chord_len = (p3 - p0).length();
     // Length of the control polygon
     let poly_len = (p1 - p0).length() + (p2 - p1).length() + (p3 - p2).length();
     0.5 * (chord_len + poly_len)
 }

 fn count_segments_for_cubic(p0: Vec2, p1: Vec2, p2: Vec2, p3: Vec2, t: &Transform) -> f64 {
     let p0 = transform(t, p0);
     let p1 = transform(t, p1);
     let p2 = transform(t, p2);
     let p3 = transform(t, p3);
     (approx_arc_length_cubic(p0, p1, p2, p3) * 0.0625 * std::f64::consts::SQRT_2).ceil()
 }

 fn count_segments_for_quadratic(p0: Vec2, p1: Vec2, p2: Vec2, t: &Transform) -> f64 {
     count_segments_for_cubic(p0, p1.lerp(p0, 0.333333), p1.lerp(p2, 0.333333), p2, t)
 }

 // Estimate tile crossings for a line with known endpoints.
 fn count_segments_for_line(p0: Point, p1: Point, t: &Transform) -> u32 {
     let dxdy = p0 - p1;
     let dxdy = transform(t, dxdy);
     let segments = (dxdy.x.abs().ceil() * 0.0625).ceil() + (dxdy.y.abs().ceil() * 0.0625).ceil();
     (segments as u32).max(1)
 }

 // Estimate tile crossings for a line with a known length.
 fn count_segments_for_line_length(scaled_width: f64) -> u32 {
     // scale the tile count by sqrt(2) to allow some slack for diagonal lines.
     // TODO: Would "2" be a better factor?
     ((scaled_width * 0.0625 * std::f64::consts::SQRT_2).ceil() as u32).max(1)
 }

 /// Wang's Formula (as described in Pyramid Algorithms by Ron Goldman, 2003, Chapter 5, Section
 /// 5.6.3 on Bezier Approximation) is a fast method for computing a lower bound on the number of
 /// recursive subdivisions required to approximate a Bezier curve within a certain tolerance. The
 /// formula for a Bezier curve of degree `n`, control points `p[0]...p[n]`, and number of levels of
 /// subdivision `l`, and flattening tolerance `tol` is defined as follows:
 ///
 /// ```ignore
 ///     m = max([length(p[k+2] - 2 * p[k+1] + p[k]) for (0 <= k <= n-2)])
 ///     l >= log_4((n * (n - 1) * m) / (8 * tol))
 /// ```
 ///
 /// For recursive subdivisions that split a curve into 2 segments at each level, the minimum number
 /// of segments is given by 2^l. From the formula above it follows that:
 ///
 /// ```ignore
 ///       segments >= 2^l >= 2^log_4(x)                      (1)
 ///     segments^2 >= 2^(2*log_4(x)) >= 4^log_4(x)           (2)
 ///     segments^2 >= x
 ///       segments >= sqrt((n * (n - 1) * m) / (8 * tol))    (3)
 /// ```
 ///
 /// Wang's formula computes an error bound on recursive subdivision based on the second derivative
 /// which tends to result in a suboptimal estimate when the curvature within the curve has a lot of
 /// variation. This is expected to frequently overshoot the flattening formula used in vello, which
 /// is closer to optimal (vello uses a method based on a numerical approximation of the integral
 /// over the continuous change in the number of flattened segments, with an error expressed in terms
 /// of curvature and infinitesimal arclength).
 mod wang {
     use super::*;

     // The curve degree term sqrt(n * (n - 1) / 8) specialized for cubics:
     //
     //    sqrt(3 * (3 - 1) / 8)
     //
     const SQRT_OF_DEGREE_TERM_CUBIC: f64 = 0.86602540378;

     // The curve degree term sqrt(n * (n - 1) / 8) specialized for quadratics:
     //
     //    sqrt(2 * (2 - 1) / 8)
     //
     const SQRT_OF_DEGREE_TERM_QUAD: f64 = 0.5;

     pub fn quadratic(rsqrt_of_tol: f64, p0: Vec2, p1: Vec2, p2: Vec2, t: &Transform) -> f64 {
         let v = -2. * p1 + p0 + p2;
         let v = transform(t, v); // transform is distributive
         let m = v.length();
         (SQRT_OF_DEGREE_TERM_QUAD * m.sqrt() * rsqrt_of_tol).ceil() as f64
     }

     pub fn cubic(rsqrt_of_tol: f64, p0: Vec2, p1: Vec2, p2: Vec2, p3: Vec2, t: &Transform) -> f64 {
         let v1 = -2. * p1 + p0 + p2;
         let v2 = -2. * p2 + p1 + p3;
         let v1 = transform(t, v1);
         let v2 = transform(t, v2);
         let m = v1.length().max(v2.length()) as f64;
         (SQRT_OF_DEGREE_TERM_CUBIC * m.sqrt() * rsqrt_of_tol).ceil() as f64
     }
 }
	// Copyright 2024 the Vello Authors
	// SPDX-License-Identifier: Apache-2.0 OR MIT

	//! This utility provides conservative size estimation for buffer allocations backing
	//! GPU bump memory. This estimate relies on heuristics and naturally overestimates.

	use super::{BumpAllocatorMemory, BumpAllocators, Transform};
	use peniko::kurbo::{Cap, Join, PathEl, Point, Stroke, Vec2};

	const RSQRT_OF_TOL: f64 = 2.2360679775; // tol = 0.2

	#[derive(Clone, Default)]
	pub struct BumpEstimator {
	// TODO: support binning
	// TODO: support ptcl
	// TODO: support tile

	// NOTE: The segment count estimation could use further refinement, particularly to handle
	// viewport clipping and rotation applied to fragments during append. We can produce a more
	// optimal result under scale and rotation if we track more data for each shape during insertion
	// and defer the final tally to resolve-time (in which we could evaluate the estimates using
	// precisely transformed coordinates). For now we apply a fudge factor of sqrt(2) and inflate
	// the number of tile crossing (a near~diagonal line orientation would result in worst case for
	// the number of intersected tiles) to account for this.
	//
	// Accounting for viewport clipping (for the right and bottom edges of the viewport) is simply
	// impossible at insertion time as the render target dimensions are unknown. We could
	// potentially account for clipping (including clip shapes/layers) by tracking bounding boxes
	// during insertion and resolving all clips at tally time (e.g. one could come up with a
	// heuristic for scaling the counts based on the proportions of a clipped bbox area).
	//
	// Since we currently don't account for clipping, this will always overshoot when clips are
	// present and when the bounding box of a shape is partially or wholly outside the viewport.
	segments: u32,
	lines: LineSoup,
	}

	impl BumpEstimator {
	pub fn new() -> Self {
	Self::default()
	}

	pub fn reset(&mut self) {
	*self = Self::default();
	}

	/// Combine the counts of this estimator with `other` after applying an optional `transform`.
	pub fn append(&mut self, other: &Self, transform: Option<&Transform>) {
	let scale = transform_scale(transform);
	self.segments += (other.segments as f64 * scale).ceil() as u32;
	self.lines.add(&other.lines, scale);
	}

	pub fn count_path(
	&mut self,
	path: impl Iterator<Item = PathEl>,
	t: &Transform,
	stroke: Option<&Stroke>,
	) {
	let mut caps = 1;
	let mut joins: u32 = 0;
	let mut lineto_lines = 0;
	let mut fill_close_lines = 1;
	let mut curve_lines = 0;
	let mut curve_count = 0;
	let mut segments = 0;

	// Track the path state to correctly count empty paths and close joins.
	let mut first_pt = None;
	let mut last_pt = None;
	let scale = transform_scale(Some(t));
	let scaled_width = stroke.map(\|s\| s.width * scale).unwrap_or(0.);
	let offset_fudge = scaled_width.sqrt().max(1.);
	for el in path {
	match el {
	PathEl::MoveTo(p0) => {
	first_pt = Some(p0);
	if last_pt.is_none() {
	continue;
	}
	caps += 1;
	joins = joins.saturating_sub(1);
	fill_close_lines += 1;
	segments += count_segments_for_line(first_pt.unwrap(), last_pt.unwrap(), t);
	last_pt = None;
	}
	PathEl::ClosePath => {
	if last_pt.is_some() {
	joins += 1;
	lineto_lines += 1;
	segments += count_segments_for_line(first_pt.unwrap(), last_pt.unwrap(), t);
	}
	last_pt = first_pt;
	}
	PathEl::LineTo(p0) => {
	last_pt = Some(p0);
	joins += 1;
	lineto_lines += 1;
	segments += count_segments_for_line(first_pt.unwrap(), last_pt.unwrap(), t);
	}
	PathEl::QuadTo(p1, p2) => {
	let Some(p0) = last_pt.or(first_pt) else {
	continue;
	};
	last_pt = Some(p2);

	let p0 = p0.to_vec2();
	let p1 = p1.to_vec2();
	let p2 = p2.to_vec2();
	let lines = offset_fudge * wang::quadratic(RSQRT_OF_TOL, p0, p1, p2, t);

	curve_lines += lines.ceil() as u32;
	curve_count += 1;
	joins += 1;

	let segs = offset_fudge * count_segments_for_quadratic(p0, p1, p2, t);
	segments += segs.ceil().max(lines.ceil()) as u32;
	}
	PathEl::CurveTo(p1, p2, p3) => {
	let Some(p0) = last_pt.or(first_pt) else {
	continue;
	};
	last_pt = Some(p3);

	let p0 = p0.to_vec2();
	let p1 = p1.to_vec2();
	let p2 = p2.to_vec2();
	let p3 = p3.to_vec2();
	let lines = offset_fudge * wang::cubic(RSQRT_OF_TOL, p0, p1, p2, p3, t);

	curve_lines += lines.ceil() as u32;
	curve_count += 1;
	joins += 1;
	let segs = count_segments_for_cubic(p0, p1, p2, p3, t);
	segments += segs.ceil().max(lines.ceil()) as u32;
	}
	}
	}

	let Some(style) = stroke else {
	self.lines.linetos += lineto_lines + fill_close_lines;
	self.lines.curves += curve_lines;
	self.lines.curve_count += curve_count;
	self.segments += segments;

	// Account for the implicit close
	if let (Some(first_pt), Some(last_pt)) = (first_pt, last_pt) {
	self.segments += count_segments_for_line(first_pt, last_pt, t);
	}
	return;
	};

	// For strokes, double-count the lines to estimate offset curves.
	self.lines.linetos += 2 * lineto_lines;
	self.lines.curves += 2 * curve_lines;
	self.lines.curve_count += 2 * curve_count;
	self.segments += 2 * segments;

	self.count_stroke_caps(style.start_cap, scaled_width, caps);
	self.count_stroke_caps(style.end_cap, scaled_width, caps);
	self.count_stroke_joins(style.join, scaled_width, style.miter_limit, joins);
	}

	/// Produce the final total, applying an optional transform to all content.
	pub fn tally(&self, transform: Option<&Transform>) -> BumpAllocatorMemory {
	let scale = transform_scale(transform);

	// The post-flatten line estimate.
	let lines = self.lines.tally(scale);

	// The estimate for tile crossings for lines. Here we ensure that there are at least as many
	// segments as there are lines, in case `segments` was underestimated at small scales.
	let n_segments = ((self.segments as f64 * scale).ceil() as u32).max(lines);

	let bump = BumpAllocators {
	failed: 0,
	// TODO: we can provide a tighter bound here but for now we
	// assume that binning must be bounded by the segment count.
	binning: n_segments,
	ptcl: 0,
	tile: 0,
	blend: 0,
	seg_counts: n_segments,
	segments: n_segments,
	lines,
	};
	bump.memory()
	}

	fn count_stroke_caps(&mut self, style: Cap, scaled_width: f64, count: u32) {
	match style {
	Cap::Butt => {
	self.lines.linetos += count;
	self.segments += count_segments_for_line_length(scaled_width) * count;
	}
	Cap::Square => {
	self.lines.linetos += 3 * count;
	self.segments += count_segments_for_line_length(scaled_width) * count;
	self.segments += 2 * count_segments_for_line_length(0.5 * scaled_width) * count;
	}
	Cap::Round => {
	let (arc_lines, line_len) = estimate_arc_lines(scaled_width);
	self.lines.curves += count * arc_lines;
	self.lines.curve_count += 1;
	self.segments += count * arc_lines * count_segments_for_line_length(line_len);
	}
	}
	}

	fn count_stroke_joins(&mut self, style: Join, scaled_width: f64, miter_limit: f64, count: u32) {
	match style {
	Join::Bevel => {
	self.lines.linetos += count;
	self.segments += count_segments_for_line_length(scaled_width) * count;
	}
	Join::Miter => {
	let max_miter_len = scaled_width * miter_limit;
	self.lines.linetos += 2 * count;
	self.segments += 2 * count * count_segments_for_line_length(max_miter_len);
	}
	Join::Round => {
	let (arc_lines, line_len) = estimate_arc_lines(scaled_width);
	self.lines.curves += count * arc_lines;
	self.lines.curve_count += 1;
	self.segments += count * arc_lines * count_segments_for_line_length(line_len);
	}
	}

	// Count inner join lines
	self.lines.linetos += count;
	self.segments += count_segments_for_line_length(scaled_width) * count;
	}
	}

	fn estimate_arc_lines(scaled_stroke_width: f64) -> (u32, f64) {
	// These constants need to be kept consistent with the definitions in `flatten_arc` in
	// flatten.wgsl.
	// TODO: It would be better if these definitions were shared/configurable. For example an
	// option is for all tolerances to be parameters to the estimator as well as the GPU pipelines
	// (the latter could be in the form of a config uniform) which would help to keep them in
	// sync.
	const MIN_THETA: f64 = 1e-6;
	const TOL: f64 = 0.25;
	let radius = TOL.max(scaled_stroke_width * 0.5);
	let theta = (2. * (1. - TOL / radius).acos()).max(MIN_THETA);
	let arc_lines = ((std::f64::consts::FRAC_PI_2 / theta).ceil() as u32).max(2);
	(arc_lines, 2. * theta.sin() * radius)
	}

	#[derive(Clone, Default)]
	struct LineSoup {
	// Explicit lines (such as linetos and non-round stroke caps/joins) and Bezier curves
	// get tracked separately to ensure that explicit lines remain scale invariant.
	linetos: u32,
	curves: u32,

	// Curve count is simply used to ensure a minimum number of lines get counted for each curve
	// at very small scales to reduce the chances of an under-estimate.
	curve_count: u32,
	}

	impl LineSoup {
	fn tally(&self, scale: f64) -> u32 {
	let curves = self
	.scaled_curve_line_count(scale)
	.max(5 * self.curve_count);

	self.linetos + curves
	}

	fn scaled_curve_line_count(&self, scale: f64) -> u32 {
	(self.curves as f64 * scale.sqrt()).ceil() as u32
	}

	fn add(&mut self, other: &LineSoup, scale: f64) {
	self.linetos += other.linetos;
	self.curves += other.scaled_curve_line_count(scale);
	self.curve_count += other.curve_count;
	}
	}

	// TODO: The 32-bit Vec2 definition from cpu_shaders/util.rs could come in handy here.
	fn transform(t: &Transform, v: Vec2) -> Vec2 {
	Vec2::new(
	t.matrix[0] as f64 * v.x + t.matrix[2] as f64 * v.y,
	t.matrix[1] as f64 * v.x + t.matrix[3] as f64 * v.y,
	)
	}

	fn transform_scale(t: Option<&Transform>) -> f64 {
	match t {
	Some(t) => {
	let m = t.matrix;
	let v1x = m[0] as f64 + m[3] as f64;
	let v2x = m[0] as f64 - m[3] as f64;
	let v1y = m[1] as f64 - m[2] as f64;
	let v2y = m[1] as f64 + m[2] as f64;
	(v1x * v1x + v1y * v1y).sqrt() + (v2x * v2x + v2y * v2y).sqrt()
	}
	None => 1.,
	}
	}

	fn approx_arc_length_cubic(p0: Vec2, p1: Vec2, p2: Vec2, p3: Vec2) -> f64 {
	let chord_len = (p3 - p0).length();
	// Length of the control polygon
	let poly_len = (p1 - p0).length() + (p2 - p1).length() + (p3 - p2).length();
	0.5 * (chord_len + poly_len)
	}

	fn count_segments_for_cubic(p0: Vec2, p1: Vec2, p2: Vec2, p3: Vec2, t: &Transform) -> f64 {
	let p0 = transform(t, p0);
	let p1 = transform(t, p1);
	let p2 = transform(t, p2);
	let p3 = transform(t, p3);
	(approx_arc_length_cubic(p0, p1, p2, p3) * 0.0625 * std::f64::consts::SQRT_2).ceil()
	}

	fn count_segments_for_quadratic(p0: Vec2, p1: Vec2, p2: Vec2, t: &Transform) -> f64 {
	count_segments_for_cubic(p0, p1.lerp(p0, 0.333333), p1.lerp(p2, 0.333333), p2, t)
	}

	// Estimate tile crossings for a line with known endpoints.
	fn count_segments_for_line(p0: Point, p1: Point, t: &Transform) -> u32 {
	let dxdy = p0 - p1;
	let dxdy = transform(t, dxdy);
	let segments = (dxdy.x.abs().ceil() * 0.0625).ceil() + (dxdy.y.abs().ceil() * 0.0625).ceil();
	(segments as u32).max(1)
	}

	// Estimate tile crossings for a line with a known length.
	fn count_segments_for_line_length(scaled_width: f64) -> u32 {
	// scale the tile count by sqrt(2) to allow some slack for diagonal lines.
	// TODO: Would "2" be a better factor?
	((scaled_width * 0.0625 * std::f64::consts::SQRT_2).ceil() as u32).max(1)
	}

	/// Wang's Formula (as described in Pyramid Algorithms by Ron Goldman, 2003, Chapter 5, Section
	/// 5.6.3 on Bezier Approximation) is a fast method for computing a lower bound on the number of
	/// recursive subdivisions required to approximate a Bezier curve within a certain tolerance. The
	/// formula for a Bezier curve of degree `n`, control points `p[0]...p[n]`, and number of levels of
	/// subdivision `l`, and flattening tolerance `tol` is defined as follows:
	///
	/// ```ignore
	/// m = max([length(p[k+2] - 2 * p[k+1] + p[k]) for (0 <= k <= n-2)])
	/// l >= log_4((n * (n - 1) * m) / (8 * tol))
	/// ```
	///
	/// For recursive subdivisions that split a curve into 2 segments at each level, the minimum number
	/// of segments is given by 2^l. From the formula above it follows that:
	///
	/// ```ignore
	/// segments >= 2^l >= 2^log_4(x) (1)
	/// segments^2 >= 2^(2*log_4(x)) >= 4^log_4(x) (2)
	/// segments^2 >= x
	/// segments >= sqrt((n * (n - 1) * m) / (8 * tol)) (3)
	/// ```
	///
	/// Wang's formula computes an error bound on recursive subdivision based on the second derivative
	/// which tends to result in a suboptimal estimate when the curvature within the curve has a lot of
	/// variation. This is expected to frequently overshoot the flattening formula used in vello, which
	/// is closer to optimal (vello uses a method based on a numerical approximation of the integral
	/// over the continuous change in the number of flattened segments, with an error expressed in terms
	/// of curvature and infinitesimal arclength).
	mod wang {
	use super::*;

	// The curve degree term sqrt(n * (n - 1) / 8) specialized for cubics:
	//
	// sqrt(3 * (3 - 1) / 8)
	//
	const SQRT_OF_DEGREE_TERM_CUBIC: f64 = 0.86602540378;

	// The curve degree term sqrt(n * (n - 1) / 8) specialized for quadratics:
	//
	// sqrt(2 * (2 - 1) / 8)
	//
	const SQRT_OF_DEGREE_TERM_QUAD: f64 = 0.5;

	pub fn quadratic(rsqrt_of_tol: f64, p0: Vec2, p1: Vec2, p2: Vec2, t: &Transform) -> f64 {
	let v = -2. * p1 + p0 + p2;
	let v = transform(t, v); // transform is distributive
	let m = v.length();
	(SQRT_OF_DEGREE_TERM_QUAD * m.sqrt() * rsqrt_of_tol).ceil() as f64
	}

	pub fn cubic(rsqrt_of_tol: f64, p0: Vec2, p1: Vec2, p2: Vec2, p3: Vec2, t: &Transform) -> f64 {
	let v1 = -2. * p1 + p0 + p2;
	let v2 = -2. * p2 + p1 + p3;
	let v1 = transform(t, v1);
	let v2 = transform(t, v2);
	let m = v1.length().max(v2.length()) as f64;
	(SQRT_OF_DEGREE_TERM_CUBIC * m.sqrt() * rsqrt_of_tol).ceil() as f64
	}
	}