cull.rs
raw
//! Deciding which display items a walk can skip.
//!
//! A fragment's display list is as large as its widget's *content*, not as
//! large as the window: a scroll area holding a hundred-page document paints
//! every page of it into one list and clips the result to the viewport. That
//! is the right shape for painting — the list is rebuilt only when the content
//! changes, and scrolling is then a transform — but a backend that hands every
//! item to the GPU pays for the whole document on every frame, and a scene
//! large enough stops being drawable at all: vello encodes each glyph's
//! outline into one buffer, and wgpu's default limits cap a binding at 128 MiB.
//!
//! Nothing outside the clip in force can affect a pixel inside it, so a walk
//! may drop those items and produce the same picture. This module is the one
//! definition of that judgement: [`ClipBounds`] carries the intersected clip
//! down a walk, and [`DisplayItem::draw_bounds`] says where an item can draw.
//!
//! Every bound here is an *over*-estimate where it is not exact, which is the
//! direction that keeps the answer sound: culling something visible would lose
//! pixels, while keeping something invisible only costs the work this module
//! exists to save.
use crate::display_list::{DisplayItem, GlyphRun};
use crate::geom::{Affine, Rect};
/// How far past a glyph's origin its ink is assumed to reach, in ems.
///
/// The display list records where each glyph in a run is *placed*, not how far
/// its outline extends from there — that is in the font, and reading it would
/// mean rasterizing the run to decide whether to rasterize the run. Three ems
/// in every direction is far past where a text face draws: it covers the last
/// glyph's own advance (one em for a full-width CJK glyph), the tallest
/// stacked diacritics, and the deepest descenders and swashes together, with
/// room to spare — including for a synthesized italic, whose lean moves the
/// top of a glyph about a quarter of an em, and a synthesized bold, which
/// grows it by a fiftieth.
const INK_REACH_EM: f64 = 3.0;
impl GlyphRun {
/// A bound, in run-local coordinates, on the pixels this run can touch.
///
/// Conservative by [`INK_REACH_EM`]: exact glyph extents live in the font.
/// `None` for a run with no glyphs, which draws nothing at all.
pub fn ink_bounds(&self) -> Option<Rect> {
let mut glyphs = self.glyphs.iter();
let first = glyphs.next()?;
let (mut x0, mut y0, mut x1, mut y1) = (first.x, first.y, first.x, first.y);
for glyph in glyphs {
x0 = x0.min(glyph.x);
y0 = y0.min(glyph.y);
x1 = x1.max(glyph.x);
y1 = y1.max(glyph.y);
}
let reach = f64::from(self.size) * INK_REACH_EM;
Some(
Rect::new(f64::from(x0), f64::from(y0), f64::from(x1), f64::from(y1))
.inflate(reach, reach),
)
}
}
impl DisplayItem {
/// Where this item can draw, under `transform`, or `None` if it draws
/// nothing itself — a scope marker, or a [`Child`](DisplayItem::Child),
/// whose extent is the child fragment's business.
///
/// The rectangle is an axis-aligned bound in the transform's target space,
/// so a rotated shape reports the box around it.
pub fn draw_bounds(&self, transform: Affine) -> Option<Rect> {
let local = match self {
DisplayItem::Fill { shape, .. } => shape.bounding_box(),
DisplayItem::Stroke { shape, style, .. } => {
// A stroke straddles its path, and a miter join runs out
// further still: the join's tip reaches half the width times
// the miter limit from the corner. Taking the whole width for
// the straddle rather than half of it leaves margin for a
// transform that scales the two axes differently, since the
// reach is measured in the shape's space and the bound is
// taken in the target's.
let reach = style.width * style.miter_limit.max(1.0);
shape.bounding_box().inflate(reach, reach)
}
DisplayItem::GlyphRun(run) => run.ink_bounds()?,
DisplayItem::Image { dest, .. } => *dest,
DisplayItem::PushClip(_)
| DisplayItem::PopClip
| DisplayItem::PushLayer { .. }
| DisplayItem::PopLayer
| DisplayItem::PushTransform(_)
| DisplayItem::PopTransform
| DisplayItem::Child { .. } => return None,
};
Some(transform.transform_rect_bbox(local))
}
}
/// The clip in force at a point in a display-list walk, in the walk's target
/// space.
///
/// A clip of `None` is unclipped, which is where a walk with no bound on its
/// target starts; a walk that knows its surface starts from
/// [`ClipBounds::new`] with that surface's rectangle, and everything off the
/// edge of it is then culled along with everything else.
#[derive(Clone, Debug)]
pub struct ClipBounds {
current: Option<Rect>,
stack: Vec<Option<Rect>>,
}
impl ClipBounds {
/// A stack whose outermost clip is `bounds` (`None` for unclipped).
pub fn new(bounds: Option<Rect>) -> Self {
Self {
current: bounds,
stack: Vec::new(),
}
}
/// The clip in force, `None` if unclipped.
pub fn current(&self) -> Option<Rect> {
self.current
}
/// Open a scope clipped to `bounds`, intersected with the clip already in
/// force. Pairs with [`pop`](Self::pop).
///
/// A clip that has closed to nothing stays closed as further scopes
/// intersect into it, which is what lets [`any_visible`](Self::any_visible)
/// answer for a whole subtree at once.
pub fn push(&mut self, bounds: Rect) {
self.stack.push(self.current);
self.current = Some(match self.current {
Some(clip) => clip.intersect(bounds),
None => bounds,
});
}
/// Close the innermost scope. A pop with nothing open leaves the clip
/// alone; backends reject the unbalanced list that could cause one.
pub fn pop(&mut self) {
if let Some(previous) = self.stack.pop() {
self.current = previous;
}
}
/// Whether anything at all can still be drawn: false once the clip has
/// closed to nothing, in which case a whole subtree can be skipped.
pub fn any_visible(&self) -> bool {
!self.current.is_some_and(is_empty)
}
/// Whether something bounded by `bounds` can affect a pixel inside the
/// clip.
pub fn visible(&self, bounds: Rect) -> bool {
match self.current {
Some(clip) => !is_empty(clip.intersect(bounds)),
None => true,
}
}
/// Whether `item` can affect a pixel inside the clip, under `transform`.
/// An item that draws nothing itself is never culled: its scope still has
/// to be tracked, and a child fragment is entered on its own terms.
pub fn item_visible(&self, item: &DisplayItem, transform: Affine) -> bool {
match item.draw_bounds(transform) {
Some(bounds) => self.visible(bounds),
None => true,
}
}
}
/// Whether a rectangle encloses no pixels — including one whose corners are
/// the wrong way round, which is why this is a test on the edges rather than
/// on the area.
fn is_empty(rect: Rect) -> bool {
rect.x1 <= rect.x0 || rect.y1 <= rect.y0
}
#[cfg(test)]
mod tests;