Source code
Revision control
Copy as Markdown
Other Tools
/* This Source Code Form is subject to the terms of the Mozilla Public
* License, v. 2.0. If a copy of the MPL was not distributed with this
//! A sparse tiling path rasterizer.
//!
//! Paths are flattened and their edges binned into 16x16 pixel tiles on the CPU.
//! Tiles that contain edges are rasterized on the GPU by evaluating the area
//! coverage of each of their edges in the fragment shader (see `cs_path_tile`),
//! while tiles that are fully covered are emitted as solid spans. Tiles that
//! are not covered at all are not emitted.
//!
//! # Overview
//!
//! Evaluating coverage for arbitrary paths is difficult because paths can
//! contain a lot of edges, and edges very far from the sample position
//! can contribute to its coverage. Brute force is not a viable approach, so
//! the name of the game is to break large paths into many small regions that
//! can be evaluated independently in parallel on the GPU.
//!
//! The theory behind this approach is that given a small region of the entire
//! path shape in device space (a tile), coverage for each pixel of the tile
//! can be determined by only looking at the edges that cross that tile if we
//! know the winding number at one reference point of the tile (in our case,
//! the top left corner). We call this reference point the backdrop of the tile.
//!
//! # Algorithm
//!
//! Each tile carries a backdrop: the winding number at its top-left corner.
//! It is computed on the CPU by accumulating the winding of the edges that
//! cross the horizontal tile boundaries, from left to right within each row
//! of tiles.
//!
//! The tiling algorithm contains three stages: binning, sorting and scanning:
//! - (Bin) For each (curve) segment in the input path:
//! - For each line segment in the flattened approximation of the curve
//! segment:
//! - Split the segment into segments that fit into tiles using an
//! adaptation of the DDA algorithm.
//! - Push the split segments into an event buffer.
//! - Whenever a segment crosses a horizontal tile boundary, push a backdrop
//! event into the event buffer.
//! - (Sort) Sort events from top to bottom and from left to right.
//! - (Scan) Scan the event buffer, emitting tile segments and
//! instances.
//!
//! Edges are implicitly grouped by tile via the sorting step. This makes it trivial
//! to generate the edge data. The scanning stage acts as a very coarse rasterizer:
//! it computes winding numbers for the top-left of each tile and can trivially
//! detect when a tile is fully inside or outside of the path. This enables the tiler
//! to not generate geometry where it isn't needed and to produce very cheap geometry
//! where there is coverage but no edges in the tile.
//! Consecutive fully covered tiles (with no edges) are merged into a single "stretched"
//! tile, which greatly reduces the amount of geometry produced.
//!
//! ## Auxiliary edges
//!
//! Although it is sufficient to know only the backdrop winding number and edges
//! overlapping the tile, we want the fragment shader to evaluate the edges by casting
//! horizontal rays (instead of rays between the backdrop and the shaded pixel).
//! To make this work we need a way to express the winding number along the left side
//! of the tile.
//!
//! Conceptually this is equivalent to tracing a vertical ray down from the backdrop
//! along the left side of the tile. If an edge leaves the tile, it has positive
//! contribution to the winding number of all positions below it, whereas if an edge
//! enters the tile, it has a negative contribution to all positions below it.
//! These contributions can be represented by positive/negative vertical edges going
//! from the point where an edge enters/leaves a tile, down to the bottom of the tile
//! along the left side.
//! These edges are called **auxiliary edges**. They are added during the binning phase
//! and treated as regular edges by the rest of the pipeline.
//!
//! # Tradeoffs
//!
//! With large tile sizes, the number of pixels that can require expensive edge evaluation
//! increases and the number of edges per tile increases, putting more pressure on the GPU.
//! Smaller tile sizes naturally run faster on the GPU, but require more work on the CPU
//! since path segments get broken up into more edges which need to be sorted and scanned.
//!
//! I experimentally found the sweet spot to be somewhere between 8x8 and 16x16 tiles,
//! depending on the hardware and the anti-aliasing strategy used by the shader.
use api::{FillRule, Path, PathEvent};
use api::units::*;
use euclid::default::Box2D;
use euclid::{point2, Transform2D, Transform3D};
use crate::bezier;
use crate::internal_types::FrameVec;
use crate::renderer::{GpuBufferBlockEdge, PathEdgeBufferBuilder};
pub const TILE_SIZE: i32 = 16;
const TILE_SIZE_F32: f32 = TILE_SIZE as f32;
const UNITS_PER_TILE: i32 = 256;
const UNITS_PER_TILE_F32: f32 = UNITS_PER_TILE as f32;
const LOCAL_COORD_BITS: i32 = 8;
const COORD_SCALE: f32 = UNITS_PER_TILE_F32 / TILE_SIZE_F32;
/// Edge coordinates are encoded into 4 u8 values per edge, in a coordinate
/// space local to the tile. It would be tempting to use all 255 values over
/// the x and y ranges of the tile, however 255 is not a multiple of the tile
/// size (16), so that would not let us express non-fractional edge coordinates
/// exactly. Instead we use 15 steps per pixel (therefore only use 15*16 = 240
/// values of the available u8 range).
/// This constant must match the scale in path_tile.glsl.
const EDGE_STEPS_PER_PIXEL: i32 = 15;
/// The largest encoded edge coordinate, which is the tile's right or bottom side.
const MAX_EDGE_COORD: u8 = (EDGE_STEPS_PER_PIXEL * TILE_SIZE) as u8;
/// Convert a coordinate to fixed point, with `UNITS_PER_TILE` units per tile.
///
/// Rounds rather than truncates, so that coordinates that are equal up to
/// floating point error, typically on integer positions, get the same value.
/// The tile index of a fixed point coordinate is its upper bits, so binning
/// must use this function wherever it computes one. Coordinates are clipped
/// to the vicinity of the target beforehand, so the cheap rounding (which
/// differs for negative values) is fine.
#[inline(always)]
fn to_fixed(coord: f32) -> i32 {
(coord * COORD_SCALE + 0.5) as i32
}
/// Encode a tile-local coordinate in fixed point units (nominally in
/// `0..=UNITS_PER_TILE`) into an edge coordinate, in `0..=MAX_EDGE_COORD`.
/// Values outside of the tile are clamped.
#[inline(always)]
fn encode_edge_coord_f32(units: f32) -> u8 {
(units * (MAX_EDGE_COORD as f32 / UNITS_PER_TILE_F32) + 0.5).min(MAX_EDGE_COORD as f32) as u8
}
/// Tile coordinates are encoded with 10 bits. The last row and column are
/// reserved for the sentinel event that flushes the last tile.
const MAX_TILES_PER_AXIS: i32 = 1023;
pub const MAX_TILED_SIZE: i32 = MAX_TILES_PER_AXIS * TILE_SIZE;
/// Curves with control points spanning more than this many pixels are
/// replaced with their chord instead of being flattened, to bound the number
/// of segments.
const MAX_CURVE_EXTENT: f32 = 1_000_000.0;
/// Points at a smaller `w` are behind the eye or too close to it.
const MIN_W: f32 = 1e-5;
const DEFAULT_TOLERANCE: f32 = 0.25;
/// Maps the path to task-local device pixels.
#[derive(Copy, Clone, Debug, PartialEq)]
#[cfg_attr(feature = "capture", derive(Serialize))]
#[cfg_attr(feature = "replay", derive(Deserialize))]
pub enum PathTransform {
Simple(Transform2D<f32, LayoutPixel, DevicePixel>),
Perspective(Transform3D<f32, LayoutPixel, DevicePixel>),
}
impl PathTransform {
pub fn new(transform: &Transform3D<f32, LayoutPixel, DevicePixel>) -> Self {
// Points on the z = 0 plane are mapped without a perspective divide
// when w does not depend on x and y.
if transform.m14 == 0.0 && transform.m24 == 0.0 && transform.m44 == 1.0 {
PathTransform::Simple(transform.to_2d())
} else {
PathTransform::Perspective(*transform)
}
}
}
#[derive(Copy, Clone, Debug, PartialEq, Eq, Hash)]
pub struct TilePosition(u32);
impl TilePosition {
const MASK: u32 = 0x3FF;
pub fn extended(x: u32, y: u32, extend: u32) -> Self {
debug_assert!(x <= Self::MASK);
debug_assert!(y <= Self::MASK);
debug_assert!(extend <= Self::MASK);
TilePosition(extend << 20 | x << 10 | y)
}
pub fn new(x: u32, y: u32) -> Self {
debug_assert!(x <= Self::MASK);
debug_assert!(y <= Self::MASK);
TilePosition(x << 10 | y)
}
pub fn extend(&mut self) {
self.0 += 1 << 20;
}
pub fn to_u32(&self) -> u32 {
self.0
}
pub fn x(&self) -> u32 {
(self.0 >> 10) & Self::MASK
}
pub fn y(&self) -> u32 {
(self.0) & Self::MASK
}
pub fn extension(&self) -> u32 {
(self.0 >> 20) & Self::MASK
}
}
#[derive(Copy, Clone, Debug, PartialEq, Eq)]
struct TilePoint {
x: u16,
y: u16,
}
impl TilePoint {
fn new(x: u16, y: u16) -> Self {
TilePoint { x, y }
}
}
/// The encoded path tile instance, as consumed by the `cs_path_tile` shader.
///
/// - `data[0]`: the `TilePosition`,
/// - `data[1]`: the index of the tile's first edge in the frame's edge buffer,
/// - `data[2]`: the edge count in the upper 16 bits, the backdrop plus 128 in
/// the lower 16 bits,
/// - `data[3]`: the address of the `PathInfo` in the i32 gpu buffer.
#[repr(C)]
#[derive(Copy, Clone, Debug, PartialEq)]
#[cfg_attr(feature = "capture", derive(Serialize))]
#[cfg_attr(feature = "replay", derive(Deserialize))]
pub struct PathTileInstance {
pub data: [u32; 4],
}
#[derive(Copy, Clone, Debug)]
struct TileInstance {
position: TilePosition,
first_edge: u32,
edge_count: u16,
backdrop: i16,
path_index: u32,
}
impl TileInstance {
fn encode(self) -> PathTileInstance {
PathTileInstance {
data: [
self.position.to_u32(),
self.first_edge,
(self.edge_count as u32) << 16 | (self.backdrop as i32 + 128) as u32,
self.path_index,
]
}
}
}
/// Per-path parameters, stored in one texel of the i32 gpu buffer.
pub struct PathInfo {
/// The render task the path is rasterized into.
pub render_task_address: u32,
pub fill_rule: FillRule,
/// Whether to fill the outside of the path instead of its inside.
pub inverted: bool,
pub opacity: f32,
}
impl PathInfo {
pub fn encode(&self) -> [i32; 4] {
let mut fill_rule = match self.fill_rule {
FillRule::Evenodd => 0,
FillRule::Nonzero => 1,
};
if self.inverted {
fill_rule |= 2;
}
[
self.render_task_address as i32,
fill_rule,
(self.opacity.max(0.0).min(1.0) * 65535.0) as i32,
0,
]
}
}
pub struct PathTilerOutput<'l> {
/// The frame's global edge buffer.
pub edges: &'l mut PathEdgeBufferBuilder,
pub tiles: &'l mut FrameVec<PathTileInstance>,
}
pub struct PathTiler {
events: Vec<Event>,
tolerance: f32,
viewport: DeviceRect,
scissor: DeviceRect,
// The scissor rect, rounded up to include the top and left part of
// partially covered tiles. Backdrop calculation for partially covered
// tiles requires the top-left corver to be included in the clip rect.
culling_rect: DeviceRect,
scissor_tiles: Box2D<i32>,
edge_buffer: Vec<GpuBufferBlockEdge>,
// Whether segments of the current path can lie outside the culling
// rect. False when the path's bounding rect is fully inside, which
// lets the binning skip its per-segment culling tests.
cull_segments: bool,
}
impl PathTiler {
pub fn new() -> Self {
PathTiler {
events: Vec::new(),
tolerance: DEFAULT_TOLERANCE,
viewport: DeviceRect::zero(),
scissor: DeviceRect::zero(),
culling_rect: DeviceRect::zero(),
scissor_tiles: Box2D::zero(),
edge_buffer: Vec::with_capacity(32),
cull_segments: true,
}
}
/// Begin rasterizing into a target. Coordinates are relative to the
/// target's origin and are clamped to `MAX_TILED_SIZE`.
pub fn begin_target(&mut self, mut viewport: DeviceIntRect) {
viewport.min.x = viewport.min.x.max(0).min(MAX_TILED_SIZE);
viewport.min.y = viewport.min.y.max(0).min(MAX_TILED_SIZE);
viewport.max.x = viewport.max.x.max(0).min(MAX_TILED_SIZE);
viewport.max.y = viewport.max.y.max(0).min(MAX_TILED_SIZE);
self.viewport = viewport.to_f32();
self.set_scissor_rect(viewport);
}
pub fn set_scissor_rect(&mut self, i32_scissor: DeviceIntRect) {
let scissor = i32_scissor.to_f32().intersection_unchecked(&self.viewport);
self.scissor = scissor;
self.scissor_tiles = Box2D {
min: point2(
i32_scissor.min.x / TILE_SIZE,
i32_scissor.min.y / TILE_SIZE,
),
max: point2(
(scissor.max.x as i32) / TILE_SIZE + (i32_scissor.max.x % TILE_SIZE != 0) as i32,
(scissor.max.y as i32) / TILE_SIZE + (i32_scissor.max.y % TILE_SIZE != 0) as i32,
),
};
self.culling_rect.min.x = self.scissor_tiles.min.x as f32 * TILE_SIZE_F32;
self.culling_rect.min.y = self.scissor_tiles.min.y as f32 * TILE_SIZE_F32;
self.culling_rect.max = self.scissor.max;
}
/// Fill a path.
///
/// `path_address` is the address of the path's `PathInfo` in the i32 gpu
/// buffer.
pub fn fill_path(
&mut self,
path: &Path,
transform: &PathTransform,
fill_rule: FillRule,
inverted: bool,
path_address: u32,
output: &mut PathTilerOutput,
) {
self.events.clear();
self.edge_buffer.clear();
if self.scissor_tiles.is_empty() {
return;
}
profile_marker!("Tile path");
match transform {
PathTransform::Simple(transform) => {
let aabb = transform.outer_transformed_box(&path.aabb());
if !aabb.min.x.is_finite() || !aabb.min.y.is_finite()
|| !aabb.max.x.is_finite() || !aabb.max.y.is_finite() {
// Degenerate path: nothing inside of it is drawn.
if inverted {
self.generate_tiles(fill_rule, inverted, path_address, output);
}
return;
}
self.cull_segments = !(aabb.min.y >= self.culling_rect.min.y - 1.0
&& aabb.max.y <= self.culling_rect.max.y + 1.0
&& aabb.min.x >= self.culling_rect.min.x - 1.0
&& aabb.max.x <= self.culling_rect.max.x + 1.0);
self.tile_path_2d(path, transform);
}
PathTransform::Perspective(transform) => {
self.cull_segments = true;
self.tile_path_3d(path, transform);
}
}
self.generate_tiles(fill_rule, inverted, path_address, output);
}
fn tile_path_2d(
&mut self,
path: &Path,
transform: &Transform2D<f32, LayoutPixel, DevicePixel>,
) {
// The last binned endpoint, in task space. Each point is transformed
// once even though it is the endpoint of two consecutive segments.
let mut from = DevicePoint::zero();
let mut first = DevicePoint::zero();
for evt in path.iter() {
match evt {
PathEvent::Begin { at } => {
from = transform.transform_point(at);
first = from;
}
PathEvent::End { .. } => {
// Open sub-paths are implicitly closed.
if from != first {
self.bin_line(from, first);
}
}
PathEvent::Line { to, .. } => {
self.add_line(&mut from, transform.transform_point(to));
}
PathEvent::Quadratic { ctrl, to, .. } => {
self.add_quadratic(
&mut from,
transform.transform_point(ctrl),
transform.transform_point(to),
);
}
PathEvent::Cubic { ctrl1, ctrl2, to, .. } => {
self.add_cubic(
&mut from,
transform.transform_point(ctrl1),
transform.transform_point(ctrl2),
transform.transform_point(to),
);
}
}
}
}
/// Whether a segment with these bounds can be skipped because it does
/// not affect any tile in the scissor rect.
#[inline]
fn is_culled(&self, min_x: f32, min_y: f32, max_y: f32) -> bool {
min_y > self.culling_rect.max.y + 1.0
|| max_y < self.culling_rect.min.y - 1.0
|| min_x > self.culling_rect.max.x + 1.0
}
/// Whether a segment with this right edge is fully on the left side of
/// the culling rect, where only its contribution to the backdrops matters.
#[inline]
fn is_on_the_left(&self, max_x: f32) -> bool {
max_x < self.culling_rect.min.x - 1.0
}
fn add_line(&mut self, from: &mut DevicePoint, to: DevicePoint) {
if self.cull_segments {
let min_y = from.y.min(to.y);
let max_y = from.y.max(to.y);
let min_x = from.x.min(to.x);
if self.is_culled(min_x, min_y, max_y) {
*from = to;
return;
}
}
// Skip tiny edges without introducing gaps: `from` does not advance.
if (to - *from).square_length() < self.tolerance * self.tolerance {
return;
}
self.bin_line(*from, to);
*from = to;
}
fn add_quadratic(&mut self, from: &mut DevicePoint, ctrl: DevicePoint, to: DevicePoint) {
let min_x = from.x.min(ctrl.x).min(to.x);
let max_x = from.x.max(ctrl.x).max(to.x);
let min_y = from.y.min(ctrl.y).min(to.y);
let max_y = from.y.max(ctrl.y).max(to.y);
let sq_tolerance = self.tolerance * self.tolerance;
if self.cull_segments {
if self.is_culled(min_x, min_y, max_y) {
*from = to;
return;
}
// A curve and its chord form a closed loop that does not cover
// anything on its right, so they contribute the same backdrop.
if self.is_on_the_left(max_x) {
self.bin_line(*from, to);
*from = to;
return;
}
}
if (to - *from).square_length() < sq_tolerance {
let center = from.lerp(to, 0.5);
if (ctrl - center).square_length() < sq_tolerance {
return;
}
}
if max_x - min_x > MAX_CURVE_EXTENT || max_y - min_y > MAX_CURVE_EXTENT {
self.bin_line(*from, to);
*from = to;
return;
}
let tolerance = self.tolerance;
let mut prev = *from;
bezier::flatten_quadratic(*from, ctrl, to, tolerance, &mut |p| {
self.bin_line(prev, p);
prev = p;
});
*from = to;
}
fn add_cubic(&mut self, from: &mut DevicePoint, ctrl1: DevicePoint, ctrl2: DevicePoint, to: DevicePoint) {
let min_x = from.x.min(ctrl1.x).min(ctrl2.x).min(to.x);
let max_x = from.x.max(ctrl1.x).max(ctrl2.x).max(to.x);
let min_y = from.y.min(ctrl1.y).min(ctrl2.y).min(to.y);
let max_y = from.y.max(ctrl1.y).max(ctrl2.y).max(to.y);
let sq_tolerance = self.tolerance * self.tolerance;
if self.cull_segments {
if self.is_culled(min_x, min_y, max_y) {
*from = to;
return;
}
// See add_quadratic.
if self.is_on_the_left(max_x) {
self.bin_line(*from, to);
*from = to;
return;
}
}
if (to - *from).square_length() < sq_tolerance {
let center = from.lerp(to, 0.5);
if (ctrl1 - center).square_length() < sq_tolerance
&& (ctrl2 - center).square_length() < sq_tolerance
{
return;
}
}
if max_x - min_x > MAX_CURVE_EXTENT || max_y - min_y > MAX_CURVE_EXTENT {
self.bin_line(*from, to);
*from = to;
return;
}
let tolerance = self.tolerance;
let mut prev = *from;
bezier::flatten_cubic(*from, ctrl1, ctrl2, to, tolerance, &mut |p| {
self.bin_line(prev, p);
prev = p;
});
*from = to;
}
fn tile_path_3d(
&mut self,
path: &Path,
transform: &Transform3D<f32, LayoutPixel, DevicePixel>,
) {
// Curves are flattened in the path's space and the resulting points
// are projected, so the tolerance is scaled by an estimate of the
// scale of the transform.
let local_aabb = path.aabb();
let mut tolerance = self.tolerance;
if let Some(device_aabb) = transform.outer_transformed_box2d(&local_aabb) {
let sx = device_aabb.width() / local_aabb.width();
let sy = device_aabb.height() / local_aabb.height();
let scale = sx.max(sy);
if scale.is_finite() && scale > 0.0 {
tolerance /= scale;
}
}
let local_extent = local_aabb.width().max(local_aabb.height());
let flatten_curves = local_extent / tolerance < MAX_CURVE_EXTENT;
let mut state = ProjectedSubPath::new(transform);
let mut first = LayoutPoint::zero();
let mut from = LayoutPoint::zero();
for evt in path.iter() {
match evt {
PathEvent::Begin { at } => {
state.begin(at);
first = at;
from = at;
}
PathEvent::End { .. } => {
state.line_to(first, self);
state.end(self);
}
PathEvent::Line { to, .. } => {
state.line_to(to, self);
from = to;
}
PathEvent::Quadratic { ctrl, to, .. } => {
if flatten_curves {
bezier::flatten_quadratic(from, ctrl, to, tolerance, &mut |p| {
state.line_to(p, self);
});
} else {
state.line_to(to, self);
}
from = to;
}
PathEvent::Cubic { ctrl1, ctrl2, to, .. } => {
if flatten_curves {
bezier::flatten_cubic(from, ctrl1, ctrl2, to, tolerance, &mut |p| {
state.line_to(p, self);
});
} else {
state.line_to(to, self);
}
from = to;
}
}
}
}
/// Bin a line segment, after clipping it to the area that affects the
/// tiles in the scissor rect.
///
/// The contribution of each segment to the tiles is independent from the
/// other segments, so the parts that are above, below or on the right side
/// of the culling rect can be dropped. The parts on the left side only
/// contribute to the backdrops and are replaced with a vertical segment
/// that crosses the same tile rows.
fn bin_line(&mut self, from: DevicePoint, to: DevicePoint) {
if !self.cull_segments {
self.tile_segment_f32(from, to);
return;
}
let x_min = self.culling_rect.min.x - 1.0;
let x_max = self.culling_rect.max.x + 1.0;
let y_min = self.culling_rect.min.y - 1.0;
let y_max = self.culling_rect.max.y + 1.0;
let inside = from.x >= x_min && from.x <= x_max && to.x >= x_min && to.x <= x_max
&& from.y >= y_min && from.y <= y_max && to.y >= y_min && to.y <= y_max;
if inside {
self.tile_segment_f32(from, to);
return;
}
if !(from.x.is_finite() && from.y.is_finite() && to.x.is_finite() && to.y.is_finite()) {
return;
}
let (mut a, mut b) = (from, to);
// Clip vertically.
if a.y.max(b.y) < y_min || a.y.min(b.y) > y_max {
return;
}
if a.y < y_min || b.y < y_min || a.y > y_max || b.y > y_max {
let dy = b.y - a.y;
let clip_y = |y: f32| -> DevicePoint {
let t = (y - from.y) / dy;
point2(from.x + (to.x - from.x) * t, y)
};
if a.y < y_min { a = clip_y(y_min); }
if a.y > y_max { a = clip_y(y_max); }
if b.y < y_min { b = clip_y(y_min); }
if b.y > y_max { b = clip_y(y_max); }
}
// Drop the part on the right side.
if a.x.min(b.x) > x_max {
return;
}
if a.x > x_max || b.x > x_max {
let t = (x_max - a.x) / (b.x - a.x);
let p = point2(x_max, a.y + (b.y - a.y) * t);
if a.x > x_max { a = p; } else { b = p; }
}
// Replace the part on the left side with a vertical segment.
if a.x.max(b.x) < x_min {
self.tile_segment_f32(point2(x_min, a.y), point2(x_min, b.y));
return;
}
if a.x < x_min || b.x < x_min {
let t = (x_min - a.x) / (b.x - a.x);
let p = point2(x_min, a.y + (b.y - a.y) * t);
if a.x < x_min {
self.tile_segment_f32(point2(x_min, a.y), p);
a = p;
} else {
self.tile_segment_f32(p, point2(x_min, b.y));
b = p;
}
}
self.tile_segment_f32(a, b);
}
#[inline]
fn tile_segment_f32(&mut self, from: DevicePoint, to: DevicePoint) {
self.tile_segment(
from, to,
to_fixed(from.x), to_fixed(from.y),
to_fixed(to.x), to_fixed(to.y),
);
}
fn tile_segment(
&mut self,
from: DevicePoint,
to: DevicePoint,
from_i32_x: i32, from_i32_y: i32,
to_i32_x: i32, to_i32_y: i32,
) {
let mut src_tx = from_i32_x >> LOCAL_COORD_BITS;
let mut src_ty = from_i32_y >> LOCAL_COORD_BITS;
let dst_tx = to_i32_x >> LOCAL_COORD_BITS;
let dst_ty = to_i32_y >> LOCAL_COORD_BITS;
// Fast path for segments contained in a single tile (the vast
// majority of flattened curve segments). No tile boundary is
// crossed so there is no backdrop or auxiliary edge to add,
// and the edge fits in a single event. The scissor tile test
// below subsumes the culling rect check for the top, bottom and
// left sides, but not the right side: the last tile column can
// extend past the scissor rect, so segments there still need the
// horizontal culling test.
if src_tx == dst_tx && src_ty == dst_ty {
if src_ty >= self.scissor_tiles.min.y && src_ty < self.scissor_tiles.max.y
&& src_tx >= self.scissor_tiles.min.x && src_tx < self.scissor_tiles.max.x
&& !(self.cull_segments
&& from.x.min(to.x) > self.culling_rect.max.x + 1.0)
{
// Encoded from the floating point coordinates like in the
// general case below, so that the endpoints shared with the
// segments that cross tile boundaries line up exactly.
let offset_x = (src_tx * UNITS_PER_TILE) as f32;
let offset_y = (src_ty * UNITS_PER_TILE) as f32;
let local_x0 = encode_edge_coord_f32(from.x * COORD_SCALE - offset_x);
let local_y0 = encode_edge_coord_f32(from.y * COORD_SCALE - offset_y);
let local_x1 = encode_edge_coord_f32(to.x * COORD_SCALE - offset_x);
let local_y1 = encode_edge_coord_f32(to.y * COORD_SCALE - offset_y);
self.events.push(Event::edge(
src_tx as u16, src_ty as u16,
[local_x0, local_y0, local_x1, local_y1],
));
}
return;
}
// Leave some margin around this early scissor test so that
// we keep track of the previous tile near the boundary of the
// scissor rect.
let min_x = to.x.min(from.x);
let max_x = to.x.max(from.x);
if self.cull_segments {
let min_y = to.y.min(from.y);
let max_y = to.y.max(from.y);
if self.is_culled(min_x, min_y, max_y) {
return;
}
}
let scissor_min_tx = self.scissor_tiles.min.x;
let dx = to.x - from.x;
let dy = to.y - from.y;
let dx_dy = dx / dy;
let dy_dx = 1.0 / dx_dy;
let x_step = (dst_tx - src_tx).signum();
let y_step = (dst_ty - src_ty).signum();
let h_tile_side = x_step.max(0);
let v_tile_side = y_step.max(0);
let mut v_x0 = from.x;
let mut v_y0 = from.y;
// x and y index of the current tile.
let mut tx = src_tx;
let mut ty = src_ty;
loop {
let v_y1;
let v_x1;
let h_dst_tx;
if ty == dst_ty {
v_y1 = to.y;
v_x1 = to.x;
h_dst_tx = dst_tx;
} else {
v_y1 = (ty + v_tile_side) as f32 * TILE_SIZE_F32;
// The min and max operations prevent limited arithmetic precision from
// allowing the computed vertex to fall on a tile outside of the expected
// range.
v_x1 = (from.x + dx_dy * (v_y1 - from.y)).max(min_x).min(max_x);
h_dst_tx = if x_step == 0 {
dst_tx
} else {
to_fixed(v_x1) >> LOCAL_COORD_BITS
};
}
let row_occluded = ty < self.scissor_tiles.min.y || ty >= self.scissor_tiles.max.y;
// When moving to a different row of tiles, add backdrop events.
if ty != src_ty {
let positive = ty > src_ty;
let row = ty + (!positive) as i32;
if row >= self.scissor_tiles.min.y && row < self.scissor_tiles.max.y && tx + 1 < self.scissor_tiles.max.x {
self.events.push(Event::backdrop((tx + 1).max(scissor_min_tx) as u16, row as u16, positive));
}
src_ty = ty;
}
let mut h_x0 = v_x0;
let mut h_y0 = v_y0;
debug_assert!(x_step > 0 || h_dst_tx <= tx);
debug_assert!(x_step < 0 || h_dst_tx >= tx);
loop {
let h_x1;
let h_y1;
if tx == h_dst_tx {
h_x1 = v_x1;
h_y1 = v_y1;
} else {
debug_assert!(x_step != 0, "tx {}, h_dst_tx {}, src_tx {} dst_tx {}", tx, h_dst_tx, src_tx, dst_tx);
h_x1 = (tx + h_tile_side) as f32 * TILE_SIZE_F32;
h_y1 = v_y0 + dy_dx * (h_x1 - v_x0);
}
let occluded = row_occluded || tx < self.scissor_tiles.min.x || tx >= self.scissor_tiles.max.x;
if !row_occluded {
let offset_y = (ty * UNITS_PER_TILE) as f32;
let local_y0 = encode_edge_coord_f32((h_y0 * COORD_SCALE) - offset_y);
if !occluded {
let offset_x = (tx * UNITS_PER_TILE) as f32;
let local_x0 = encode_edge_coord_f32((h_x0 * COORD_SCALE) - offset_x);
let local_x1 = encode_edge_coord_f32((h_x1 * COORD_SCALE) - offset_x);
let local_y1 = encode_edge_coord_f32((h_y1 * COORD_SCALE) - offset_y);
debug_assert!(tx < self.scissor_tiles.max.x);
self.events.push(Event::edge(
tx as u16, ty as u16,
[local_x0, local_y0, local_x1, local_y1]
));
}
// Add an auxiliary edge when crossing a vertical boundary (tile x
// coordinate changes).
if tx != src_tx {
// Note, if the edge is going in the negative x orientation, then
// we are actually adding an auxiliary edge to the previous tile
// rather than the current one.
let aux_tx = tx.max(src_tx);
let aux_occluded = aux_tx < self.scissor_tiles.min.x || aux_tx >= self.scissor_tiles.max.x;
if !aux_occluded {
let (y0, y1) = if tx < src_tx {
(local_y0, MAX_EDGE_COORD)
} else {
(MAX_EDGE_COORD, local_y0)
};
self.events.push(Event::edge(
aux_tx as u16, ty as u16,
[0, y0, 0, y1]
));
}
}
}
src_tx = tx;
debug_assert!(x_step > 0 || tx >= h_dst_tx);
debug_assert!(x_step < 0 || tx <= h_dst_tx);
if tx == h_dst_tx {
break;
}
h_x0 = h_x1;
h_y0 = h_y1;
tx += x_step;
}
v_x0 = v_x1;
v_y0 = v_y1;
if ty == dst_ty {
break;
}
ty += y_step;
}
}
fn push_mask_tile(
&mut self,
tile: TilePoint,
backdrop: i16,
path_index: u32,
output: &mut PathTilerOutput,
) {
let edge_count = self.edge_buffer.len();
// This limit isn't necessary but it is useful to catch bugs. In practice there should
// never be this many edges in a single tile.
const MAX_EDGES_PER_TILE: usize = 4096;
debug_assert!(edge_count < MAX_EDGES_PER_TILE, "bad tile at {:?}, {} edges", tile, edge_count);
let first_edge = output.edges.push_slice(&self.edge_buffer);
let edge_count = usize::min(edge_count, MAX_EDGES_PER_TILE) as u16;
self.edge_buffer.clear();
output.tiles.push(TileInstance {
position: TilePosition::new(tile.x as u32, tile.y as u32),
backdrop,
first_edge,
edge_count,
path_index,
}.encode());
}
fn generate_tiles(&mut self, fill_rule: FillRule, inverted: bool, path_index: u32, output: &mut PathTilerOutput) {
if inverted {
self.generate_tiles_inverted(fill_rule, path_index, output);
return;
}
if self.events.is_empty() {
return;
}
let mut events = std::mem::take(&mut self.events);
events.sort_unstable();
// Push a dummy backdrop out of view that will cause the current tile to be flushed
// at the last iteration without having to replicate the logic out of the loop.
events.push(Event::backdrop(0, u16::MAX, false));
let mut current = TilePoint::new(0, 0);
let mut backdrop: i16 = 0;
for evt in events.iter() {
let tile = evt.tile();
if current != tile {
if !self.edge_buffer.is_empty() {
self.push_mask_tile(current, backdrop, path_index, output);
current.x += 1;
}
let x_end = if current.y == tile.y {
tile.x.min(self.scissor_tiles.max.x as u16)
} else {
self.scissor_tiles.max.x as u16
};
let inside = match fill_rule {
FillRule::Evenodd => backdrop % 2 != 0,
FillRule::Nonzero => backdrop != 0,
};
if current.x < x_end && inside {
Self::fill_span(current.x, x_end, current.y, backdrop, path_index, output);
}
if current.y != tile.y {
// We moved to a new row of tiles.
if current.y >= self.scissor_tiles.max.y as u16 {
break;
}
backdrop = 0;
}
current = tile;
}
if evt.is_edge() {
self.edge_buffer.push(GpuBufferBlockEdge(evt.payload().to_ne_bytes()));
} else {
let winding = if evt.payload() == 0 { -1 } else { 1 };
backdrop += winding;
}
}
self.events = events;
}
fn generate_tiles_inverted(&mut self, fill_rule: FillRule, path_index: u32, output: &mut PathTilerOutput) {
let min_x = self.scissor_tiles.min.x as u16;
let max_x = self.scissor_tiles.max.x as u16;
let mut events = std::mem::take(&mut self.events);
events.sort_unstable();
// Push a dummy backdrop out of view that will cause the current tile to be flushed
// at the last iteration without having to replicate the logic out of the loop.
events.push(Event::backdrop(0, u16::MAX, false));
let mut current = TilePoint::new(min_x, self.scissor_tiles.min.y as u16);
let mut backdrop: i16 = 0;
for evt in events.iter() {
let tile = evt.tile();
if current != tile && !self.edge_buffer.is_empty() {
self.push_mask_tile(current, backdrop, path_index, output);
current.x += 1;
}
while current != tile {
let next_x = if current.y == tile.y {
tile.x.min(max_x)
} else {
max_x
};
let inside = !match fill_rule {
FillRule::Evenodd => backdrop % 2 != 0,
FillRule::Nonzero => backdrop != 0,
};
// Fill solid tiles if any, up to the new tile or the end of the current row.
if inside && current.x < next_x {
Self::fill_span(current.x, next_x, current.y, backdrop, path_index, output);
}
if next_x == max_x {
// Reached the end of a row, move to the next.
backdrop = 0;
current.x = min_x;
current.y += 1;
// The dummy tile is the only one expected to be outside the visible
// area. No need to fill solid tiles
if current.y >= self.scissor_tiles.max.y as u16 {
break;
}
} else {
current.x = next_x;
}
}
if evt.is_edge() {
self.edge_buffer.push(GpuBufferBlockEdge(evt.payload().to_ne_bytes()));
} else {
let winding = if evt.payload() == 0 { -1 } else { 1 };
backdrop += winding;
}
}
self.events = events;
}
/// Emit a solid tile stretched over `x..x_end`.
fn fill_span(
x: u16,
x_end: u16,
y: u16,
backdrop: i16,
path_index: u32,
output: &mut PathTilerOutput,
) {
if x >= x_end {
return;
}
output.tiles.push(TileInstance {
position: TilePosition::extended(x as u32, y as u32, (x_end - x - 1) as u32),
backdrop,
first_edge: 0,
edge_count: 0,
path_index,
}.encode());
}
}
/// Clips the projected edges of a sub-path against the `w = MIN_W` plane.
///
/// The part of the sub-path that is behind the plane is replaced with
/// segments along the plane's projection, connecting each point where the
/// sub-path exits the visible half-space to the point where it re-enters it.
struct ProjectedSubPath<'l> {
transform: &'l Transform3D<f32, LayoutPixel, DevicePixel>,
prev: euclid::HomogeneousVector<f32, DevicePixel>,
exit: Option<DevicePoint>,
first_entry: Option<DevicePoint>,
}
impl<'l> ProjectedSubPath<'l> {
fn new(transform: &'l Transform3D<f32, LayoutPixel, DevicePixel>) -> Self {
ProjectedSubPath {
transform,
prev: euclid::HomogeneousVector::new(0.0, 0.0, 0.0, 1.0),
exit: None,
first_entry: None,
}
}
fn project(&self, p: LayoutPoint) -> euclid::HomogeneousVector<f32, DevicePixel> {
self.transform.transform_point2d_homogeneous(p)
}
fn begin(&mut self, at: LayoutPoint) {
self.prev = self.project(at);
self.exit = None;
self.first_entry = None;
}
fn line_to(&mut self, to: LayoutPoint, tiler: &mut PathTiler) {
let a = self.prev;
let b = self.project(to);
self.prev = b;
let to_2d = |h: euclid::HomogeneousVector<f32, DevicePixel>| point2(h.x / h.w, h.y / h.w);
let on_plane = |a: euclid::HomogeneousVector<f32, DevicePixel>, b: euclid::HomogeneousVector<f32, DevicePixel>| {
let t = (MIN_W - a.w) / (b.w - a.w);
point2(
(a.x + (b.x - a.x) * t) / MIN_W,
(a.y + (b.y - a.y) * t) / MIN_W,
)
};
match (a.w >= MIN_W, b.w >= MIN_W) {
(true, true) => {
tiler.bin_line(to_2d(a), to_2d(b));
}
(true, false) => {
let p = on_plane(a, b);
tiler.bin_line(to_2d(a), p);
self.exit = Some(p);
}
(false, true) => {
let p = on_plane(a, b);
match self.exit.take() {
Some(exit) => tiler.bin_line(exit, p),
None => self.first_entry = Some(p),
}
tiler.bin_line(p, to_2d(b));
}
(false, false) => {}
}
}
fn end(&mut self, tiler: &mut PathTiler) {
if let (Some(exit), Some(entry)) = (self.exit.take(), self.first_entry.take()) {
tiler.bin_line(exit, entry);
}
}
}
/// A sortable compressed event that encodes either a binned edge or a backdrop update.
///
/// The sort key (tile coordinates and the edge/backdrop flag) lives in the
/// high 32 bits and the payload in the low 32 bits, so sorting events as
/// plain integers groups them by tile with backdrops before edges. The
/// payload takes part in the comparison, which is fine: the relative order
/// of edges within a tile and of backdrops on the same tile does not matter.
#[derive(Copy, Clone, PartialEq, Eq, PartialOrd, Ord)]
struct Event(u64);
impl Event {
fn edge(tx: u16, ty: u16, edge: [u8; 4]) -> Self {
let key = 1 | ((tx as u64) << 1) | ((ty as u64) << 11);
Event((key << 32) | u32::from_ne_bytes(edge) as u64)
}
fn backdrop(tx: u16, ty: u16, positive: bool) -> Self {
let key = ((tx as u64) << 1) | ((ty as u64) << 11);
Event((key << 32) | positive as u64)
}
fn is_edge(&self) -> bool {
self.0 & (1 << 32) != 0
}
fn payload(&self) -> u32 {
self.0 as u32
}
fn tile(&self) -> TilePoint {
TilePoint::new(
((self.0 >> 33) & 0x3FF) as u16,
((self.0 >> 43) & 0x3FF) as u16,
)
}
}
impl std::fmt::Debug for Event {
fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> Result<(), std::fmt::Error> {
let tile = self.tile();
if self.is_edge() {
write!(f, "Edge at {:?}", tile)
} else {
write!(f, "Backdrop at {:?}", tile)
}
}
}
#[test]
fn tile_position() {
let mut p0 = TilePosition::new(1, 2);
assert_eq!(p0.x(), 1);
assert_eq!(p0.y(), 2);
assert_eq!(p0.extension(), 0);
p0.extend();
assert_eq!(p0.x(), 1);
assert_eq!(p0.y(), 2);
assert_eq!(p0.extension(), 1);
p0.extend();
assert_eq!(p0.x(), 1);
assert_eq!(p0.y(), 2);
assert_eq!(p0.extension(), 2);
}
#[test]
fn event() {
let e1 = Event::edge(1, 3, [0, 0, 255, 50]);
let e2 = Event::edge(2, 3, [0, 0, 255, 50]);
let e3 = Event::edge(0b1111111111, 0b1101010101, [0, 1, 2, 3]);
let b1 = Event::backdrop(1, 3, true);
let b2 = Event::backdrop(2, 3, true);
assert_eq!(e1.tile(), TilePoint::new(1, 3));
assert_eq!(e2.tile(), TilePoint::new(2, 3));
assert_eq!(e3.tile(), TilePoint::new(0b1111111111, 0b1101010101));
assert_eq!(b1.tile(), TilePoint::new(1, 3));
assert_eq!(b2.tile(), TilePoint::new(2, 3));
let mut v = vec![e3, e2, e1, b2, b1];
v.sort_unstable();
assert_eq!(v, vec![b1, e1, b2, e2, e3]);
}