surpass/rasterizer/

mod.rs

// Copyright 2020 The Fuchsia Authors. All rights reserved.
// Use of this source code is governed by a BSD-style license that can be
// found in the LICENSE file.

use rayon::prelude::*;

use crate::{Lines, PIXEL_SHIFT, PIXEL_WIDTH};

mod grouped_iter;
mod pixel_segment;

use grouped_iter::GroupedIter;
pub use pixel_segment::{bit_field_lens, search_last_by_key, PixelSegment, PixelSegmentUnpacked};

// This finds the ith term in the ordered union of two sequences:
//
// 1. a * x + c
// 2. b * x + d
//
// It works by estimating the amount of items that came from sequence 1 and
// sequence 2 such that the next item will be the ith. This results in two
// indices from each sequence. The final step is to simply pick the smaller one
// which naturally comes next.
fn find(i: i32, sum_recip: f32, cd: f32, a: f32, b: f32, c: f32, d: f32) -> f32 {
    const BIAS: f32 = -0.000_000_5;

    let i = i as f32;

    let ja = if b.is_finite() { (b.mul_add(i, -cd).mul_add(sum_recip, BIAS)).ceil() } else { i };
    let jb = if a.is_finite() { (a.mul_add(i, cd).mul_add(sum_recip, BIAS)).ceil() } else { i };

    let guess_a = a.mul_add(ja, c);
    let guess_b = b.mul_add(jb, d);

    guess_a.min(guess_b)
}

fn round(v: f32) -> i32 {
    unsafe { (v + 0.5).floor().to_int_unchecked() }
}

#[derive(Debug, Default)]
pub struct Rasterizer<const TW: usize, const TH: usize> {
    segments: Vec<PixelSegment<TW, TH>>,
}

impl<const TW: usize, const TH: usize> Rasterizer<TW, TH> {
    pub fn new() -> Self {
        Self::default()
    }

    pub fn segments(&self) -> &[PixelSegment<TW, TH>] {
        self.segments.as_slice()
    }

    #[inline(never)]
    pub fn rasterize(&mut self, lines: &Lines) {
        // Shard the workload into set of similar output size in PixelSegment.
        let iter = GroupedIter::new(&lines.lengths);

        iter.into_par_iter()
            .with_min_len(256)
            .map(|(li, pi)| {
                let a = lines.a[li as usize];
                let b = lines.b[li as usize];
                let c = lines.c[li as usize];
                let d = lines.d[li as usize];

                let i = pi as i32 - i32::from(c != 0.0) - i32::from(d != 0.0);

                let i0 = i;
                let i1 = i + 1;

                let sum_recip = (a + b).recip();
                let cd = c - d;

                let t0 = find(i0, sum_recip, cd, a, b, c, d).max(0.0);
                let t1 = find(i1, sum_recip, cd, a, b, c, d).min(1.0);

                let x0f = t0.mul_add(lines.dx[li as usize], lines.x0[li as usize]);
                let y0f = t0.mul_add(lines.dy[li as usize], lines.y0[li as usize]);
                let x1f = t1.mul_add(lines.dx[li as usize], lines.x0[li as usize]);
                let y1f = t1.mul_add(lines.dy[li as usize], lines.y0[li as usize]);

                let x0_sub = round(x0f);
                let x1_sub = round(x1f);
                let y0_sub = round(y0f);
                let y1_sub = round(y1f);

                let border_x = x0_sub.min(x1_sub) >> PIXEL_SHIFT;
                let border_y = y0_sub.min(y1_sub) >> PIXEL_SHIFT;

                let tile_x = (border_x >> TW.trailing_zeros() as i32) as i16;
                let tile_y = (border_y >> TH.trailing_zeros() as i32) as i16;
                let local_x = (border_x & (TW - 1) as i32) as u8;
                let local_y = (border_y & (TH - 1) as i32) as u8;

                let border = (border_x << PIXEL_SHIFT) + PIXEL_WIDTH as i32;
                let height = y1_sub - y0_sub;

                let double_area_multiplier =
                    ((x1_sub - x0_sub).abs() + 2 * (border - x0_sub.max(x1_sub))) as u8;
                let cover = height as i8;

                PixelSegment::new(
                    lines.orders[li as usize],
                    tile_x,
                    tile_y,
                    local_x,
                    local_y,
                    double_area_multiplier,
                    cover,
                )
            })
            .collect_into_vec(&mut self.segments);
    }

    const BIT_FIELD_LENGTH: [usize; 7] = bit_field_lens::<TW, TH>();

    #[inline]
    pub fn sort(&mut self) {
        // Sort by (tile_y, tile_x, layer_id).
        let offset = Self::BIT_FIELD_LENGTH[3]
            + Self::BIT_FIELD_LENGTH[4]
            + Self::BIT_FIELD_LENGTH[5]
            + Self::BIT_FIELD_LENGTH[6];
        self.segments.par_sort_unstable_by_key(|segment| {
            let segment: u64 = segment.into();
            segment >> offset
        });
    }
}

#[cfg(test)]
mod tests {
    use super::*;

    use crate::{GeomId, Layer, LinesBuilder, Order, Point, TILE_HEIGHT, TILE_WIDTH};

    fn segments(p0: Point, p1: Point) -> Vec<PixelSegment<TILE_WIDTH, TILE_HEIGHT>> {
        let mut builder = LinesBuilder::new();
        builder.push(GeomId::default(), [p0, p1]);
        let lines = builder
            .build(|_| Some(Layer { order: Some(Order::new(0).unwrap()), ..Default::default() }));

        let mut rasterizer = Rasterizer::default();
        rasterizer.rasterize(&lines);

        rasterizer.segments().to_vec()
    }

    fn areas_and_covers(segments: &[PixelSegment<TILE_WIDTH, TILE_HEIGHT>]) -> Vec<(i16, i8)> {
        segments
            .iter()
            .map(|&segment| {
                let segment: PixelSegmentUnpacked = segment.into();
                (segment.double_area, segment.cover)
            })
            .collect()
    }

    #[test]
    fn area_cover_octant_1() {
        assert_eq!(
            areas_and_covers(&segments(Point::new(0.0, 0.0), Point::new(3.0, 2.0))),
            [(11 * 16, 11), (5 * 8 + 2 * (5 * 8), 5), (5 * 8, 5), (11 * 16, 11)],
        );
    }

    #[test]
    fn area_cover_octant_2() {
        assert_eq!(
            areas_and_covers(&segments(Point::new(0.0, 0.0), Point::new(2.0, 3.0))),
            [(16 * 11 + 2 * (16 * 5), 16), (8 * 5, 8), (8 * 5 + 2 * (8 * 11), 8), (16 * 11, 16)],
        );
    }

    #[test]
    fn area_cover_octant_3() {
        assert_eq!(
            areas_and_covers(&segments(Point::new(0.0, 0.0), Point::new(-2.0, 3.0))),
            [(16 * 11, 16), (8 * 5 + 2 * (8 * 11), 8), (8 * 5, 8), (16 * 11 + 2 * (16 * 5), 16)],
        );
    }

    #[test]
    fn area_cover_octant_4() {
        assert_eq!(
            areas_and_covers(&segments(Point::new(0.0, 0.0), Point::new(-3.0, 2.0))),
            [(11 * 16, 11), (5 * 8, 5), (5 * 8 + 2 * (5 * 8), 5), (11 * 16, 11)],
        );
    }

    #[test]
    fn area_cover_octant_5() {
        assert_eq!(
            areas_and_covers(&segments(Point::new(0.0, 0.0), Point::new(-3.0, -2.0))),
            [(-(11 * 16), -11), (-(5 * 8), -5), (-(5 * 8 + 2 * (5 * 8)), -5), (-(11 * 16), -11)],
        );
    }

    #[test]
    fn area_cover_octant_6() {
        assert_eq!(
            areas_and_covers(&segments(Point::new(0.0, 0.0), Point::new(-2.0, -3.0))),
            [
                (-(16 * 11), -16),
                (-(8 * 5 + 2 * (8 * 11)), -8),
                (-(8 * 5), -8),
                (-(16 * 11 + 2 * (16 * 5)), -16),
            ],
        );
    }

    #[test]
    fn area_cover_octant_7() {
        assert_eq!(
            areas_and_covers(&segments(Point::new(0.0, 0.0), Point::new(2.0, -3.0))),
            [
                (-(16 * 11 + 2 * (16 * 5)), -16),
                (-(8 * 5), -8),
                (-(8 * 5 + 2 * (8 * 11)), -8),
                (-(16 * 11), -16),
            ],
        );
    }

    #[test]
    fn area_cover_octant_8() {
        assert_eq!(
            areas_and_covers(&segments(Point::new(0.0, 0.0), Point::new(3.0, -2.0))),
            [(-(11 * 16), -11), (-(5 * 8 + 2 * (5 * 8)), -5), (-(5 * 8), -5), (-(11 * 16), -11)],
        );
    }

    #[test]
    fn area_cover_axis_0() {
        assert_eq!(areas_and_covers(&segments(Point::new(0.0, 0.0), Point::new(1.0, 0.0))), []);
    }

    #[test]
    fn area_cover_axis_45() {
        assert_eq!(
            areas_and_covers(&segments(Point::new(0.0, 0.0), Point::new(1.0, 1.0))),
            [(16 * 16, 16)],
        );
    }

    #[test]
    fn area_cover_axis_90() {
        assert_eq!(
            areas_and_covers(&segments(Point::new(0.0, 0.0), Point::new(0.0, 1.0))),
            [(2 * 16 * 16, 16)],
        );
    }

    #[test]
    fn area_cover_axis_135() {
        assert_eq!(
            areas_and_covers(&segments(Point::new(0.0, 0.0), Point::new(-1.0, 1.0))),
            [(16 * 16, 16)],
        );
    }

    #[test]
    fn area_cover_axis_180() {
        assert_eq!(areas_and_covers(&segments(Point::new(0.0, 0.0), Point::new(-1.0, 0.0))), []);
    }

    #[test]
    fn area_cover_axis_225() {
        assert_eq!(
            areas_and_covers(&segments(Point::new(0.0, 0.0), Point::new(-1.0, -1.0))),
            [(-(16 * 16), -16)],
        );
    }

    #[test]
    fn area_cover_axis_270() {
        assert_eq!(
            areas_and_covers(&segments(Point::new(0.0, 0.0), Point::new(0.0, -1.0))),
            [(2 * -(16 * 16), -16)],
        );
    }

    #[test]
    fn area_cover_axis_315() {
        assert_eq!(
            areas_and_covers(&segments(Point::new(0.0, 0.0), Point::new(-1.0, -1.0))),
            [(-(16 * 16), -16)],
        );
    }

    fn tiles(segments: &[PixelSegment<TILE_WIDTH, TILE_HEIGHT>]) -> Vec<(i16, i16, u8, u8)> {
        segments
            .iter()
            .map(|&segment| {
                let segment: PixelSegmentUnpacked = segment.into();
                (segment.tile_x, segment.tile_y, segment.local_x, segment.local_y)
            })
            .collect()
    }

    #[test]
    fn tile_octant_1() {
        assert_eq!(
            tiles(&segments(
                Point::new(TILE_WIDTH as f32, TILE_HEIGHT as f32),
                Point::new(TILE_WIDTH as f32 + 3.0, TILE_HEIGHT as f32 + 2.0),
            )),
            [(1, 1, 0, 0), (1, 1, 1, 0), (1, 1, 1, 1), (1, 1, 2, 1)],
        );
    }

    #[test]
    fn tile_octant_2() {
        assert_eq!(
            tiles(&segments(
                Point::new(TILE_WIDTH as f32, TILE_HEIGHT as f32),
                Point::new(TILE_WIDTH as f32 + 2.0, TILE_HEIGHT as f32 + 3.0),
            )),
            [(1, 1, 0, 0), (1, 1, 0, 1), (1, 1, 1, 1), (1, 1, 1, 2)],
        );
    }

    #[test]
    fn tile_octant_3() {
        assert_eq!(
            tiles(&segments(
                Point::new(-(TILE_WIDTH as f32), TILE_HEIGHT as f32),
                Point::new(-(TILE_WIDTH as f32) - 2.0, TILE_HEIGHT as f32 + 3.0),
            )),
            [
                (-1, 1, TILE_WIDTH as u8 - 1, 0),
                (-1, 1, TILE_WIDTH as u8 - 1, 1),
                (-1, 1, TILE_WIDTH as u8 - 2, 1),
                (-1, 1, TILE_WIDTH as u8 - 2, 2),
            ],
        );
    }

    #[test]
    fn tile_octant_4() {
        assert_eq!(
            tiles(&segments(
                Point::new(-(TILE_WIDTH as f32), TILE_HEIGHT as f32),
                Point::new(-(TILE_WIDTH as f32) - 3.0, TILE_HEIGHT as f32 + 2.0),
            )),
            [
                (-1, 1, TILE_WIDTH as u8 - 1, 0),
                (-1, 1, TILE_WIDTH as u8 - 2, 0),
                (-1, 1, TILE_WIDTH as u8 - 2, 1),
                (-1, 1, TILE_WIDTH as u8 - 3, 1),
            ],
        );
    }

    #[test]
    fn tile_octant_5() {
        assert_eq!(
            tiles(&segments(
                Point::new(-(TILE_WIDTH as f32), -(TILE_HEIGHT as f32)),
                Point::new(-(TILE_WIDTH as f32) - 3.0, -(TILE_HEIGHT as f32) - 2.0),
            )),
            [
                (-1, -1, TILE_WIDTH as u8 - 1, TILE_HEIGHT as u8 - 1),
                (-1, -1, TILE_WIDTH as u8 - 2, TILE_HEIGHT as u8 - 1),
                (-1, -1, TILE_WIDTH as u8 - 2, TILE_HEIGHT as u8 - 2),
                (-1, -1, TILE_WIDTH as u8 - 3, TILE_HEIGHT as u8 - 2),
            ],
        );
    }

    #[test]
    fn tile_octant_6() {
        assert_eq!(
            tiles(&segments(
                Point::new(-(TILE_WIDTH as f32), -(TILE_HEIGHT as f32)),
                Point::new(-(TILE_WIDTH as f32) - 2.0, -(TILE_HEIGHT as f32) - 3.0),
            )),
            [
                (-1, -1, TILE_WIDTH as u8 - 1, TILE_HEIGHT as u8 - 1),
                (-1, -1, TILE_WIDTH as u8 - 1, TILE_HEIGHT as u8 - 2),
                (-1, -1, TILE_WIDTH as u8 - 2, TILE_HEIGHT as u8 - 2),
                (-1, -1, TILE_WIDTH as u8 - 2, TILE_HEIGHT as u8 - 3),
            ],
        );
    }

    #[test]
    fn tile_octant_7() {
        assert_eq!(
            tiles(&segments(
                Point::new(TILE_WIDTH as f32, -(TILE_HEIGHT as f32)),
                Point::new(TILE_WIDTH as f32 + 2.0, -(TILE_HEIGHT as f32) - 3.0),
            )),
            [
                (1, -1, 0, TILE_HEIGHT as u8 - 1),
                (1, -1, 0, TILE_HEIGHT as u8 - 2),
                (1, -1, 1, TILE_HEIGHT as u8 - 2),
                (1, -1, 1, TILE_HEIGHT as u8 - 3),
            ],
        );
    }

    #[test]
    fn tile_octant_8() {
        assert_eq!(
            tiles(&segments(
                Point::new(TILE_WIDTH as f32, -(TILE_HEIGHT as f32)),
                Point::new(TILE_WIDTH as f32 + 3.0, -(TILE_HEIGHT as f32) - 2.0),
            )),
            [
                (1, -1, 0, TILE_HEIGHT as u8 - 1),
                (1, -1, 1, TILE_HEIGHT as u8 - 1),
                (1, -1, 1, TILE_HEIGHT as u8 - 2),
                (1, -1, 2, TILE_HEIGHT as u8 - 2),
            ],
        );
    }

    #[test]
    fn start_and_end_not_on_pixel_border() {
        assert_eq!(
            areas_and_covers(&segments(Point::new(0.5, 0.25), Point::new(4.0, 2.0)))[0],
            (4 * 8, 4),
        );

        assert_eq!(
            areas_and_covers(&segments(Point::new(0.0, 0.0), Point::new(3.5, 1.75)))[4],
            (4 * 8 + 2 * (4 * 8), 4),
        );
    }
}