vello_common/strip.rs
1// Copyright 2025 the Vello Authors
2// SPDX-License-Identifier: Apache-2.0 OR MIT
3
4//! Rendering strips.
5
6use crate::flatten::Line;
7use crate::geometry::RectU16;
8use crate::peniko::Fill;
9use crate::tile::{Tile, Tiles};
10use crate::util::f32_to_u8;
11use alloc::vec::Vec;
12use core::ops::{Deref, DerefMut};
13use fearless_simd::*;
14
15/// A strip.
16#[derive(Debug, Clone, Copy, PartialEq, Eq)]
17pub struct Strip {
18 /// The x coordinate of the strip, in user coordinates.
19 pub x: u16,
20 /// The y coordinate of the strip, in user coordinates.
21 pub y: u16,
22 /// Packed alpha index and fill gap flag.
23 ///
24 /// Bit layout (u32):
25 /// - bit 31: `fill_gap` (See `Strip::fill_gap()`).
26 /// - bits 0..=30: `alpha_idx` (See `Strip::alpha_idx()`).
27 packed_alpha_idx_fill_gap: u32,
28}
29
30/// A fill region with alpha coverage.
31#[derive(Debug, Clone, Copy, PartialEq, Eq)]
32pub struct StripAlphaFillSegment {
33 /// The fill region covered by this alpha segment.
34 pub fill: StripFillSegment,
35 /// The index into the alpha buffer of the segment.
36 pub alpha_idx: u32,
37}
38
39impl Deref for StripAlphaFillSegment {
40 type Target = StripFillSegment;
41
42 #[inline(always)]
43 fn deref(&self) -> &Self::Target {
44 &self.fill
45 }
46}
47
48impl DerefMut for StripAlphaFillSegment {
49 #[inline(always)]
50 fn deref_mut(&mut self) -> &mut Self::Target {
51 &mut self.fill
52 }
53}
54
55/// A fill region without alpha coverage.
56#[derive(Debug, Clone, Copy, PartialEq, Eq)]
57pub struct StripFillSegment {
58 /// The inclusive start x coordinate in tile units.
59 pub tile_x0: u16,
60 /// The exclusive end x coordinate in tile units.
61 pub tile_x1: u16,
62 /// The y coordinate in tile units.
63 pub tile_y: u16,
64}
65
66impl StripFillSegment {
67 /// The inclusive start x coordinate in pixels.
68 #[inline(always)]
69 pub const fn x0(self) -> u16 {
70 self.tile_x0 * Tile::WIDTH
71 }
72
73 /// The exclusive end x coordinate in pixels.
74 #[inline(always)]
75 pub const fn x1(self) -> u16 {
76 self.tile_x1 * Tile::WIDTH
77 }
78
79 /// The y coordinate in pixels.
80 #[inline(always)]
81 pub const fn y(self) -> u16 {
82 self.tile_y * Tile::HEIGHT
83 }
84
85 /// Return this segment's rectangle in tile coordinates.
86 #[inline(always)]
87 pub const fn tile_rect(self) -> RectU16 {
88 RectU16::new(
89 self.tile_x0,
90 self.tile_y,
91 self.tile_x1,
92 self.tile_y.saturating_add(1),
93 )
94 }
95
96 /// Return this segment's rectangle in pixel coordinates.
97 #[inline(always)]
98 pub const fn pixel_rect(self) -> RectU16 {
99 RectU16::new(
100 self.tile_x0.saturating_mul(Tile::WIDTH),
101 self.tile_y.saturating_mul(Tile::HEIGHT),
102 self.tile_x1.saturating_mul(Tile::WIDTH),
103 self.tile_y.saturating_add(1).saturating_mul(Tile::HEIGHT),
104 )
105 }
106
107 /// Return this segment's pixel-space rectangle shifted by `shift`.
108 #[inline(always)]
109 pub fn shift(self, shift: (i32, i32)) -> RectU16 {
110 self.pixel_rect().shift(shift)
111 }
112}
113
114/// Iterate over all fill and alpha-fill regions formed by the sequence of strips,
115/// within the tile-unit bounds indicated by `tile_bounds`.
116pub fn visit_strip_fill_segments<C>(
117 strips: &[Strip],
118 tile_bounds: RectU16,
119 context: &mut C,
120 mut alpha_fill: impl FnMut(&mut C, StripAlphaFillSegment),
121 mut fill: impl FnMut(&mut C, StripFillSegment),
122) {
123 // Need at least two strips: 1 (or more) for the generated path, and the sentinel strip.
124 if strips.len() < 2 || tile_bounds.is_empty() {
125 return;
126 }
127
128 for pair in strips.windows(2) {
129 let strip = pair[0];
130 let tile_y = strip.strip_y();
131
132 // Skip strips that are outside the viewport vertically.
133 if tile_y < tile_bounds.y0 {
134 continue;
135 }
136 if tile_y >= tile_bounds.y1 {
137 break;
138 }
139
140 let next_strip = pair[1];
141 let strip_width = strip.width_to(&next_strip);
142
143 debug_assert_eq!(
144 strip.x % Tile::WIDTH,
145 0,
146 "strip x must be tile-width aligned",
147 );
148 debug_assert_eq!(
149 strip_width % Tile::WIDTH,
150 0,
151 "strip width must be tile-width aligned",
152 );
153
154 let strip_tile_x0 = strip.x / Tile::WIDTH;
155 let strip_tile_x1 = strip_tile_x0.saturating_add(strip_width / Tile::WIDTH);
156 // Clip strips that are outside the viewport horizontally.
157 let tile_x0 = strip_tile_x0.max(tile_bounds.x0);
158 let tile_x1 = strip_tile_x1.min(tile_bounds.x1);
159
160 if tile_x0 < tile_x1 {
161 alpha_fill(
162 context,
163 StripAlphaFillSegment {
164 fill: StripFillSegment {
165 tile_x0,
166 tile_x1,
167 tile_y,
168 },
169 // Make sure to recalculate the index in case we had to clip.
170 alpha_idx: strip.alpha_idx()
171 + u32::from(tile_x0 - strip_tile_x0)
172 * u32::from(Tile::WIDTH)
173 * u32::from(Tile::HEIGHT),
174 },
175 );
176 }
177
178 if next_strip.fill_gap() && next_strip.y == strip.y {
179 // Similar procedure to above.
180
181 let tile_x0 = strip_tile_x1.max(tile_bounds.x0);
182 let tile_x1 = (next_strip.x / Tile::WIDTH).min(tile_bounds.x1);
183
184 if tile_x0 < tile_x1 {
185 fill(
186 context,
187 StripFillSegment {
188 tile_x0,
189 tile_x1,
190 tile_y,
191 },
192 );
193 }
194 }
195 }
196}
197
198impl Strip {
199 /// The bit mask for `fill_gap` packed into `packed_alpha_idx_fill_gap`.
200 const FILL_GAP_MASK: u32 = 1 << 31;
201
202 /// Creates a new strip.
203 pub fn new(x: u16, y: u16, alpha_idx: u32, fill_gap: bool) -> Self {
204 // Ensure `alpha_idx` does not collide with the fill flag bit.
205 assert!(
206 alpha_idx & Self::FILL_GAP_MASK == 0,
207 "`alpha_idx` too large"
208 );
209 let fill_gap = u32::from(fill_gap) << 31;
210 Self {
211 x,
212 y,
213 packed_alpha_idx_fill_gap: alpha_idx | fill_gap,
214 }
215 }
216
217 /// Creates a sentinel strip.
218 pub fn sentinel(y: u16, alpha_idx: u32) -> Self {
219 Self::new(u16::MAX, y, alpha_idx, false)
220 }
221
222 /// Return whether the strip is a sentinel strip.
223 pub fn is_sentinel(&self) -> bool {
224 self.x == u16::MAX
225 }
226
227 /// Return the y coordinate of the strip, in strip units.
228 pub fn strip_y(&self) -> u16 {
229 self.y / Tile::HEIGHT
230 }
231
232 /// Returns the horizontal pixel width of this strip.
233 ///
234 /// **IMPORTANT**: This assumes that the `next` is actually the next adjacent strip
235 /// to `self`, otherwise this method will return a garbage value!
236 pub fn width_to(&self, next: &Self) -> u16 {
237 let col = self.alpha_idx() / u32::from(Tile::HEIGHT);
238 let next_col = next.alpha_idx() / u32::from(Tile::HEIGHT);
239 next_col.saturating_sub(col) as u16
240 }
241
242 /// Returns the alpha index.
243 #[inline(always)]
244 pub fn alpha_idx(&self) -> u32 {
245 self.packed_alpha_idx_fill_gap & !Self::FILL_GAP_MASK
246 }
247
248 /// Sets the alpha index.
249 ///
250 /// Note that the largest value that can be stored in the alpha index is `u32::MAX << 1`, as the
251 /// highest bit is reserved for `fill_gap`.
252 #[inline(always)]
253 pub fn set_alpha_idx(&mut self, alpha_idx: u32) {
254 // Ensure `alpha_idx` does not collide with the fill flag bit.
255 assert!(
256 alpha_idx & Self::FILL_GAP_MASK == 0,
257 "`alpha_idx` too large"
258 );
259 let fill_gap = self.packed_alpha_idx_fill_gap & Self::FILL_GAP_MASK;
260 self.packed_alpha_idx_fill_gap = alpha_idx | fill_gap;
261 }
262
263 /// Returns whether the gap that lies between this strip and the previous in the same row should be filled.
264 #[inline(always)]
265 pub fn fill_gap(&self) -> bool {
266 (self.packed_alpha_idx_fill_gap & Self::FILL_GAP_MASK) != 0
267 }
268
269 /// Sets whether the gap that lies between this strip and the previous in the same row should be filled.
270 #[inline(always)]
271 pub fn set_fill_gap(&mut self, fill: bool) {
272 let fill = u32::from(fill) << 31;
273 self.packed_alpha_idx_fill_gap =
274 (self.packed_alpha_idx_fill_gap & !Self::FILL_GAP_MASK) | fill;
275 }
276
277 /// When early culling is active, geometry fully to the left of the viewport creates no tiles.
278 /// However, if that geometry has a non-zero winding (e.g. a large shape surrounding the
279 /// viewport), then we must output strips for those fills.
280 ///
281 /// We reconstruct this "background" fill using `row_windings` (the winding at x=0) to emit solid
282 /// strips for:
283 /// 1. All rows vertically above the first visible tile.
284 /// 2. 'Captive' rows between two tile-containing rows.
285 /// 3. All rows vertically below the last visible tile.
286 #[inline(always)]
287 fn emit_culled_background<F>(
288 start: u16,
289 end: u16,
290 viewport_width: u16,
291 strips: &mut Vec<Self>,
292 alphas: &mut Vec<u8>,
293 windings: &crate::tile::CulledWindings,
294 mut should_fill: F,
295 ) where
296 F: FnMut(i32) -> bool,
297 {
298 windings.for_active_rows_in_range(start as usize, end as usize, |row| {
299 if should_fill(windings.coarse[row] as i32) {
300 let y_pos = row as u16 * Tile::HEIGHT;
301 strips.push(Self::new(0, y_pos, alphas.len() as u32, false));
302 // TODO: Would be nice to get rid of this, but the current clipping code only
303 // allows zero-width strips as a row terminator, not in-between.
304 alphas.extend([255_u8; Tile::HEIGHT as usize * Tile::WIDTH as usize]);
305 strips.push(Self::new(viewport_width, y_pos, alphas.len() as u32, true));
306 }
307 });
308 }
309}
310
311/// Render the tiles stored in `tiles` into the strip and alpha buffer.
312pub fn render(
313 level: Level,
314 tiles: &Tiles,
315 strip_buf: &mut Vec<Strip>,
316 alpha_buf: &mut Vec<u8>,
317 fill_rule: Fill,
318 aliasing_threshold: Option<u8>,
319 lines: &[Line],
320) {
321 dispatch!(level, simd => render_impl(simd,
322 tiles,
323 strip_buf,
324 alpha_buf,
325 fill_rule,
326 aliasing_threshold,
327 lines));
328}
329
330#[inline(always)]
331fn render_impl<S: Simd>(
332 s: S,
333 tiles: &Tiles,
334 strip_buf: &mut Vec<Strip>,
335 alpha_buf: &mut Vec<u8>,
336 fill_rule: Fill,
337 aliasing_threshold: Option<u8>,
338 lines: &[Line],
339) {
340 let row_windings = &tiles.windings.coarse;
341 let has_culled_tiles = tiles.has_culled_tiles();
342 let viewport_width = tiles
343 .width()
344 // We need to make sure strips are tile-aligned.
345 .checked_next_multiple_of(Tile::WIDTH)
346 .unwrap_or(u16::MAX);
347 let strip_start = strip_buf.len();
348 let maybe_emit_sentinel_strip = |strip_buf: &mut Vec<Strip>, alpha_buf: &Vec<u8>| {
349 // Emit the final sentinel strip, if we produced at least one strip.
350 if let Some(last_y) = strip_buf[strip_start..].last().map(|s| s.y) {
351 strip_buf.push(Strip::sentinel(last_y, alpha_buf.len() as u32));
352 }
353 };
354
355 // If no tiles were culled and the tile buffer is empty, we can simply exit. If tiles were
356 // culled, the tile buffer may be empty but there may be winding produced by culled geometry
357 // left of the viewport that must be checked for filling.
358 if !has_culled_tiles && tiles.is_empty() {
359 return;
360 }
361
362 let should_fill = |winding: i32| match fill_rule {
363 Fill::NonZero => winding != 0,
364 Fill::EvenOdd => winding % 2 != 0,
365 };
366
367 // Helper to handle "captive strips". When a row has tiles, but the first tile
368 // is not at the left edge of the viewport (x != 0), we must emit a solid strip
369 // from x=0 to that tile if the coarse winding dictates a fill.
370 let emit_captive_strip =
371 |y: u16, is_left_viewport: bool, strips: &mut Vec<Strip>, alphas: &mut Vec<u8>| {
372 let coarse_wd = tiles.windings.coarse[y as usize] as i32;
373
374 if should_fill(coarse_wd) && !is_left_viewport {
375 strips.push(Strip::new(0, y * Tile::HEIGHT, alphas.len() as u32, false));
376 alphas.extend([255_u8; Tile::HEIGHT as usize * Tile::WIDTH as usize]);
377 }
378
379 let mut acc = f32x4::splat(s, coarse_wd as f32);
380 if is_left_viewport {
381 let fine_winding: f32x4<_> = tiles.windings.partial[y as usize].simd_into(s);
382 acc += fine_winding;
383 }
384
385 (coarse_wd, acc)
386 };
387
388 // The accumulated tile winding delta. A line that crosses the top edge of a tile
389 // increments the delta if the line is directed upwards, and decrements it if goes
390 // downwards. Horizontal lines leave it unchanged.
391 let mut winding_delta: i32 = 0;
392
393 // The previous tile visited.
394 let mut prev_tile = if has_culled_tiles && tiles.is_empty() {
395 Tile::SENTINEL
396 } else {
397 *tiles.get(0)
398 };
399
400 // The accumulated (fractional) winding of the tile-sized location we're currently at.
401 // Note multiple tiles can be at the same location.
402 // Note that we are also implicitly assuming here that the tile height exactly fits into a
403 // SIMD vector (i.e. 128 bits).
404 let mut location_winding = [f32x4::splat(s, 0.0); Tile::WIDTH as usize];
405 // The accumulated (fractional) windings at this location's right edge. When we move to the
406 // next location, this is splatted to that location's starting winding.
407 let mut accumulated_winding = f32x4::splat(s, 0.0);
408
409 let left_viewport = prev_tile.x == 0;
410 if has_culled_tiles {
411 let row_max = prev_tile.y.min(row_windings.len() as u16);
412 Strip::emit_culled_background(
413 0,
414 row_max,
415 viewport_width,
416 strip_buf,
417 alpha_buf,
418 &tiles.windings,
419 should_fill,
420 );
421 if tiles.is_empty() {
422 maybe_emit_sentinel_strip(strip_buf, alpha_buf);
423
424 return;
425 }
426 let (wd, acc) = emit_captive_strip(prev_tile.y, left_viewport, strip_buf, alpha_buf);
427 winding_delta = wd;
428 accumulated_winding = acc;
429 location_winding = [accumulated_winding; Tile::WIDTH as usize];
430 }
431
432 // The strip we're building.
433 let mut strip = Strip::new(
434 prev_tile.x * Tile::WIDTH,
435 prev_tile.y * Tile::HEIGHT,
436 alpha_buf.len() as u32,
437 should_fill(winding_delta) && !left_viewport,
438 );
439
440 for (tile_idx, tile) in tiles.iter().copied().chain([Tile::SENTINEL]).enumerate() {
441 let line = lines[tile.line_idx() as usize];
442 let tile_left_x = f32::from(tile.x) * f32::from(Tile::WIDTH);
443 let tile_top_y = f32::from(tile.y) * f32::from(Tile::HEIGHT);
444 let p0_x = line.p0.x - tile_left_x;
445 let p0_y = line.p0.y - tile_top_y;
446 let p1_x = line.p1.x - tile_left_x;
447 let p1_y = line.p1.y - tile_top_y;
448
449 // Push out the winding as an alpha mask when we move to the next location (i.e., a tile
450 // without the same location).
451 if !prev_tile.same_loc(&tile) {
452 match fill_rule {
453 Fill::NonZero => {
454 let p1 = f32x4::splat(s, 0.5);
455 let p2 = f32x4::splat(s, 255.0);
456
457 #[expect(clippy::needless_range_loop, reason = "dimension clarity")]
458 for x in 0..Tile::WIDTH as usize {
459 let area = location_winding[x];
460 let coverage = area.abs();
461 let mulled = coverage.mul_add(p2, p1);
462 // Note that we are not storing the location winding here but the actual
463 // alpha value as f32, so we reuse the variable as a temporary storage.
464 // Also note that we need the `min` here because the winding can be > 1
465 // and thus the calculated alpha value need to be clamped to 255.
466 location_winding[x] = mulled.min(p2);
467 }
468 }
469 Fill::EvenOdd => {
470 let p1 = f32x4::splat(s, 0.5);
471 let p2 = f32x4::splat(s, -2.0);
472 let p3 = f32x4::splat(s, 255.0);
473
474 #[expect(clippy::needless_range_loop, reason = "dimension clarity")]
475 for x in 0..Tile::WIDTH as usize {
476 let area = location_winding[x];
477 let im1 = area.mul_add(p1, p1).floor();
478 let coverage = p2.mul_add(im1, area).abs();
479 let mulled = p3.mul_add(coverage, p1);
480 // TODO: It is possible that, unlike for `NonZero`, we don't need the `min`
481 // here.
482 location_winding[x] = mulled.min(p3);
483 }
484 }
485 };
486
487 let p1 = s.combine_f32x4(location_winding[0], location_winding[1]);
488 let p2 = s.combine_f32x4(location_winding[2], location_winding[3]);
489
490 let mut u8_vals = f32_to_u8(s.combine_f32x8(p1, p2));
491
492 if let Some(aliasing_threshold) = aliasing_threshold {
493 u8_vals = s.select_u8x16(
494 u8_vals.simd_ge(u8x16::splat(s, aliasing_threshold)),
495 u8x16::splat(s, 255),
496 u8x16::splat(s, 0),
497 );
498 }
499
500 alpha_buf.extend_from_slice(u8_vals.as_slice());
501
502 #[expect(clippy::needless_range_loop, reason = "dimension clarity")]
503 for x in 0..Tile::WIDTH as usize {
504 location_winding[x] = accumulated_winding;
505 }
506 }
507
508 // Push out the strip if we're moving to a next strip.
509 if !prev_tile.same_loc(&tile) && !prev_tile.prev_loc(&tile) {
510 debug_assert_eq!(
511 (prev_tile.x as u32 + 1) * Tile::WIDTH as u32 - strip.x as u32,
512 ((alpha_buf.len() - strip.alpha_idx() as usize) / usize::from(Tile::HEIGHT)) as u32,
513 "The number of columns written to the alpha buffer should equal the number of columns spanned by this strip."
514 );
515 strip_buf.push(strip);
516
517 let is_sentinel = tile_idx == tiles.len() as usize;
518 let left_viewport = tile.x == 0;
519 if !prev_tile.same_row(&tile) {
520 // Emit a final strip in the row if there is non-zero winding for the sparse fill
521 if winding_delta != 0 {
522 strip_buf.push(Strip::new(
523 viewport_width,
524 prev_tile.y * Tile::HEIGHT,
525 alpha_buf.len() as u32,
526 should_fill(winding_delta),
527 ));
528 }
529
530 // Logic identical to the start (see above): fill any vertical gaps (empty rows)
531 // between the previous and current tile using the row windings.
532 if has_culled_tiles && !is_sentinel {
533 Strip::emit_culled_background(
534 prev_tile.y + 1,
535 tile.y,
536 viewport_width,
537 strip_buf,
538 alpha_buf,
539 &tiles.windings,
540 should_fill,
541 );
542
543 let (wd, acc) = emit_captive_strip(tile.y, left_viewport, strip_buf, alpha_buf);
544 winding_delta = wd;
545 accumulated_winding = acc;
546 } else {
547 winding_delta = 0;
548 accumulated_winding = f32x4::splat(s, 0.0);
549 };
550
551 #[expect(clippy::needless_range_loop, reason = "dimension clarity")]
552 for x in 0..Tile::WIDTH as usize {
553 location_winding[x] = accumulated_winding;
554 }
555 } else {
556 // Note: this fill is mathematically not necessary. It provides a way to reduce
557 // accumulation of float rounding errors.
558 accumulated_winding = f32x4::splat(s, winding_delta as f32);
559 }
560
561 if is_sentinel {
562 break;
563 }
564
565 strip = Strip::new(
566 tile.x * Tile::WIDTH,
567 tile.y * Tile::HEIGHT,
568 alpha_buf.len() as u32,
569 should_fill(winding_delta) && !left_viewport,
570 );
571 }
572 prev_tile = tile;
573
574 // TODO: horizontal geometry has no impact on winding. This branch will be removed when
575 // horizontal geometry is culled at the tile-generation stage.
576 if p0_y == p1_y {
577 continue;
578 }
579
580 // Lines moving upwards (in a y-down coordinate system) add to winding; lines moving
581 // downwards subtract from winding.
582 let sign = (p0_y - p1_y).signum();
583
584 // Calculate winding / pixel area coverage.
585 //
586 // Conceptually, horizontal rays are shot from left to right. Every time the ray crosses a
587 // line that is directed upwards (decreasing `y`), the winding is incremented. Every time
588 // the ray crosses a line moving downwards (increasing `y`), the winding is decremented.
589 // The fractional area coverage of a pixel is the integral of the winding within it.
590 //
591 // Practically, to calculate this, each pixel is considered individually, and we determine
592 // whether the line moves through this pixel. The line's y-delta within this pixel is
593 // accumulated and added to the area coverage of pixels to the right. Within the pixel
594 // itself, the area to the right of the line segment forms a trapezoid (or a triangle in
595 // the degenerate case). The area of this trapezoid is added to the pixel's area coverage.
596 //
597 // For example, consider the following pixel square, with a line indicated by asterisks
598 // starting inside the pixel and crossing its bottom edge. The area covered is the
599 // trapezoid on the bottom-right enclosed by the line and the pixel square. The area is
600 // positive if the line moves down, and negative otherwise.
601 //
602 // __________________
603 // | |
604 // | *------|
605 // | * |
606 // | * |
607 // | * |
608 // | * |
609 // | * |
610 // |___*____________|
611 // *
612 // *
613
614 let (line_top_y, line_top_x, line_bottom_y, line_bottom_x) = if p0_y < p1_y {
615 (p0_y, p0_x, p1_y, p1_x)
616 } else {
617 (p1_y, p1_x, p0_y, p0_x)
618 };
619
620 let y_slope = (line_bottom_y - line_top_y) / (line_bottom_x - line_top_x);
621 let x_slope = 1. / y_slope;
622
623 winding_delta += sign as i32 * i32::from(tile.winding());
624
625 let line_top_y = f32x4::splat(s, line_top_y);
626 let line_bottom_y = f32x4::splat(s, line_bottom_y);
627
628 // See the explanation of this term on the `line_px_left_yx` and `line_px_right_yx`
629 // variables below.
630 let line_px_base_yx = line_top_y.mul_add(-x_slope, line_top_x);
631
632 let px_top_y = f32x4::simd_from(s, [0., 1., 2., 3.]);
633 let px_bottom_y = 1. + px_top_y;
634
635 let ymin = line_top_y.max(px_top_y);
636 let ymax = line_bottom_y.min(px_bottom_y);
637
638 let mut acc = f32x4::splat(s, 0.0);
639
640 for x_idx in 0..Tile::WIDTH {
641 let x_idx_s = f32x4::splat(s, x_idx as f32);
642 let px_left_x = x_idx_s;
643 let px_right_x = 1.0 + x_idx_s;
644
645 // The y-coordinate of the intersections between the line and the pixel's left and
646 // right edges respectively.
647 //
648 // There is some subtlety going on here: `y_slope` will usually be finite, but will
649 // be `inf` for purely vertical lines (`p0_x == p1_x`).
650 //
651 // In the case of `inf`, the resulting slope calculation will be `-inf` or `inf`
652 // depending on whether the pixel edge is left or right of the line, respectively
653 // (from the viewport's coordinate system perspective). The `min` and `max`
654 // y-clamping logic generalizes nicely, as a pixel edge to the left of the line is
655 // clamped to `ymin`, and a pixel edge to the right is clamped to `ymax`.
656 //
657 // In the special case where a vertical line and pixel edge are at the exact same
658 // x-position (collinear), the line belongs to the pixel on whose _left_ edge it is
659 // situated. The resulting slope calculation for the edge the line is situated on
660 // will be NaN, as `0 * inf` results in NaN. This is true for both the left and
661 // right edge.
662 //
663 // We know `ymin` and `ymax` are finite. We require the `max` operation to pick `ymin`
664 // if its first operand is NaN. On x86, that maps to the semantics of `_mm_max_ps`,
665 // which `f32x4::max` emits: that instruction takes element-wise
666 // `if first > second { first } else { second }`. For AArch64, we do require the
667 // `f32x4::max_precise` semantics (as `vmax_f32` returns NaN if either operand is NaN);
668 // however, for AArch64 the precise version should be comparatively less expensive than
669 // on x86. For `min`, we then know both operands are finite, so we can unambiguously
670 // use the relaxed version. If this ever breaks, tests should fail loudly, because NaNs
671 // happen a lot here!
672 trait F32x4MaxExt {
673 fn max_if_first_nan_take_second(self, rhs: Self) -> Self;
674 }
675 #[cfg(any(target_arch = "x86", target_arch = "x86_64"))]
676 impl<S: Simd> F32x4MaxExt for f32x4<S> {
677 #[inline(always)]
678 fn max_if_first_nan_take_second(self, rhs: Self) -> Self {
679 self.max(rhs)
680 }
681 }
682 #[cfg(not(any(target_arch = "x86", target_arch = "x86_64")))]
683 impl<S: Simd> F32x4MaxExt for f32x4<S> {
684 #[inline(always)]
685 fn max_if_first_nan_take_second(self, rhs: Self) -> Self {
686 self.max_precise(rhs)
687 }
688 }
689 let line_px_left_y = (px_left_x - line_top_x)
690 .mul_add(y_slope, line_top_y)
691 .max_if_first_nan_take_second(ymin)
692 .min(ymax);
693 let line_px_right_y = (px_right_x - line_top_x)
694 .mul_add(y_slope, line_top_y)
695 .max_if_first_nan_take_second(ymin)
696 .min(ymax);
697
698 // For each pixel we calculate the x-coordinates of the left- and rightmost points on
699 // the line segment within that pixel. We do this based on the y-offsets of those two
700 // points from the top of the line. This can be calculated as, e.g.,
701 // `(line_px_left_y - line_top_y) * x_slope + line_top_x`.
702 //
703 // Rather than calculating that y-offset twice for each pixel within the loop through
704 // subtracting from the points' y-coordinates, we get rid of that subtraction by baking
705 // it into the algebraic "base" x-coordinate `line_px_base_yx` calculated above the
706 // loop. When adding that term to `y * x_slope` it gives the x-coordinate of the point
707 // along the line.
708 //
709 // Note `x_slope` is always finite, as horizontal geometry is elided.
710 let line_px_left_yx = line_px_left_y.mul_add(x_slope, line_px_base_yx);
711 let line_px_right_yx = line_px_right_y.mul_add(x_slope, line_px_base_yx);
712 let h = (line_px_right_y - line_px_left_y).abs();
713
714 // The trapezoidal area enclosed between the line and the right edge of the pixel
715 // square. More straightforwardly written as follows, but the `madd` is faster.
716 // 0.5 * h * (2. * px_right_x - line_px_right_yx - line_px_left_yx).
717 let area = h * (line_px_right_yx + line_px_left_yx).mul_add(-0.5, px_right_x);
718 location_winding[x_idx as usize] += area.mul_add(sign, acc);
719 acc = h.mul_add(sign, acc);
720 }
721
722 accumulated_winding += acc;
723 }
724
725 if has_culled_tiles {
726 Strip::emit_culled_background(
727 (prev_tile.y + 1).min(row_windings.len() as u16),
728 row_windings.len() as u16,
729 viewport_width,
730 strip_buf,
731 alpha_buf,
732 &tiles.windings,
733 should_fill,
734 );
735 }
736
737 maybe_emit_sentinel_strip(strip_buf, alpha_buf);
738}