tiny_skia/

line_clipper.rs

// Copyright 2011 Google Inc.
// Copyright 2020 Yevhenii Reizner
//
// Use of this source code is governed by a BSD-style license that can be
// found in the LICENSE file.

use crate::{Point, Rect};

use tiny_skia_path::Scalar;

pub const MAX_POINTS: usize = 4;

/// Clip the line pts[0]...pts[1] against clip, ignoring segments that
/// lie completely above or below the clip. For portions to the left or
/// right, turn those into vertical line segments that are aligned to the
/// edge of the clip.
///
/// Return the number of line segments that result, and store the end-points
/// of those segments sequentially in lines as follows:
///
/// 1st segment: lines[0]..lines[1]
/// 2nd segment: lines[1]..lines[2]
/// 3rd segment: lines[2]..lines[3]
pub fn clip<'a>(
    src: &[Point; 2],
    clip: &Rect,
    can_cull_to_the_right: bool,
    points: &'a mut [Point; MAX_POINTS],
) -> &'a [Point] {
    let (mut index0, mut index1) = if src[0].y < src[1].y { (0, 1) } else { (1, 0) };

    // Check if we're completely clipped out in Y (above or below)

    if src[index1].y <= clip.top() {
        // we're above the clip
        return &[];
    }

    if src[index0].y >= clip.bottom() {
        // we're below the clip
        return &[];
    }

    // Chop in Y to produce a single segment, stored in tmp[0..1]

    let mut tmp = *src;

    // now compute intersections
    if src[index0].y < clip.top() {
        tmp[index0] = Point::from_xy(sect_with_horizontal(src, clip.top()), clip.top());
        debug_assert!(is_between_unsorted(tmp[index0].x, src[0].x, src[1].x));
    }

    if tmp[index1].y > clip.bottom() {
        tmp[index1] = Point::from_xy(sect_with_horizontal(src, clip.bottom()), clip.bottom());
        debug_assert!(is_between_unsorted(tmp[index1].x, src[0].x, src[1].x));
    }

    // Chop it into 1..3 segments that are wholly within the clip in X.

    // temp storage for up to 3 segments
    let mut result_storage = [Point::zero(); MAX_POINTS];
    let mut line_count = 1;
    let mut reverse;

    if src[0].x < src[1].x {
        index0 = 0;
        index1 = 1;
        reverse = false;
    } else {
        index0 = 1;
        index1 = 0;
        reverse = true;
    }

    let result: &[Point] = if tmp[index1].x <= clip.left() {
        // wholly to the left
        tmp[0].x = clip.left();
        tmp[1].x = clip.left();
        reverse = false;
        &tmp
    } else if tmp[index0].x >= clip.right() {
        // wholly to the right
        if can_cull_to_the_right {
            return &[];
        }

        tmp[0].x = clip.right();
        tmp[1].x = clip.right();
        reverse = false;
        &tmp
    } else {
        let mut offset = 0;

        if tmp[index0].x < clip.left() {
            result_storage[offset] = Point::from_xy(clip.left(), tmp[index0].y);
            offset += 1;
            result_storage[offset] =
                Point::from_xy(clip.left(), sect_clamp_with_vertical(&tmp, clip.left()));
            debug_assert!(is_between_unsorted(
                result_storage[offset].y,
                tmp[0].y,
                tmp[1].y
            ));
        } else {
            result_storage[offset] = tmp[index0];
        }
        offset += 1;

        if tmp[index1].x > clip.right() {
            result_storage[offset] =
                Point::from_xy(clip.right(), sect_clamp_with_vertical(&tmp, clip.right()));
            debug_assert!(is_between_unsorted(
                result_storage[offset].y,
                tmp[0].y,
                tmp[1].y
            ));
            offset += 1;
            result_storage[offset] = Point::from_xy(clip.right(), tmp[index1].y);
        } else {
            result_storage[offset] = tmp[index1];
        }

        line_count = offset;
        &result_storage
    };

    // Now copy the results into the caller's lines[] parameter
    if reverse {
        // copy the pts in reverse order to maintain winding order
        for i in 0..=line_count {
            points[line_count - i] = result[i];
        }
    } else {
        let len = line_count + 1;
        points[0..len].copy_from_slice(&result[0..len]);
    }

    &points[0..line_count + 1]
}

/// Returns X coordinate of intersection with horizontal line at Y.
fn sect_with_horizontal(src: &[Point; 2], y: f32) -> f32 {
    let dy = src[1].y - src[0].y;
    if dy.is_nearly_zero() {
        src[0].x.ave(src[1].x)
    } else {
        // need the extra precision so we don't compute a value that exceeds
        // our original limits
        let x0 = f64::from(src[0].x);
        let y0 = f64::from(src[0].y);
        let x1 = f64::from(src[1].x);
        let y1 = f64::from(src[1].y);
        let result = x0 + (f64::from(y) - y0) * (x1 - x0) / (y1 - y0);

        // The computed X value might still exceed [X0..X1] due to quantum flux
        // when the doubles were added and subtracted, so we have to pin the
        // answer :(
        pin_unsorted_f64(result, x0, x1) as f32
    }
}

/// Returns value between the two limits, where the limits are either ascending or descending.
fn is_between_unsorted(value: f32, limit0: f32, limit1: f32) -> bool {
    if limit0 < limit1 {
        limit0 <= value && value <= limit1
    } else {
        limit1 <= value && value <= limit0
    }
}

fn sect_clamp_with_vertical(src: &[Point; 2], x: f32) -> f32 {
    let y = sect_with_vertical(src, x);
    // Our caller expects y to be between src[0].y and src[1].y (unsorted), but due to the
    // numerics of floats/doubles, we might have computed a value slightly outside of that,
    // so we have to manually clamp afterwards.
    // See skbug.com/7491
    pin_unsorted_f32(y, src[0].y, src[1].y)
}

/// Returns Y coordinate of intersection with vertical line at X.
fn sect_with_vertical(src: &[Point; 2], x: f32) -> f32 {
    let dx = src[1].x - src[0].x;
    if dx.is_nearly_zero() {
        src[0].y.ave(src[1].y)
    } else {
        // need the extra precision so we don't compute a value that exceeds
        // our original limits
        let x0 = f64::from(src[0].x);
        let y0 = f64::from(src[0].y);
        let x1 = f64::from(src[1].x);
        let y1 = f64::from(src[1].y);
        let result = y0 + (f64::from(x) - x0) * (y1 - y0) / (x1 - x0);
        result as f32
    }
}

fn pin_unsorted_f32(value: f32, mut limit0: f32, mut limit1: f32) -> f32 {
    if limit1 < limit0 {
        core::mem::swap(&mut limit0, &mut limit1);
    }
    // now the limits are sorted
    debug_assert!(limit0 <= limit1);

    if value < limit0 {
        limit0
    } else if value > limit1 {
        limit1
    } else {
        value
    }
}

fn pin_unsorted_f64(value: f64, mut limit0: f64, mut limit1: f64) -> f64 {
    if limit1 < limit0 {
        core::mem::swap(&mut limit0, &mut limit1);
    }
    // now the limits are sorted
    debug_assert!(limit0 <= limit1);

    if value < limit0 {
        limit0
    } else if value > limit1 {
        limit1
    } else {
        value
    }
}

/// Intersect the line segment against the rect. If there is a non-empty
/// resulting segment, return true and set dst[] to that segment. If not,
/// return false and ignore dst[].
///
/// `clip` is specialized for scan-conversion, as it adds vertical
/// segments on the sides to show where the line extended beyond the
/// left or right sides. `intersect` does not.
pub fn intersect(src: &[Point; 2], clip: &Rect, dst: &mut [Point; 2]) -> bool {
    let bounds = Rect::from_ltrb(
        src[0].x.min(src[1].x),
        src[0].y.min(src[1].y),
        src[0].x.max(src[1].x),
        src[0].y.max(src[1].y),
    );

    if let Some(bounds) = bounds {
        if contains_no_empty_check(clip, &bounds) {
            dst.copy_from_slice(src);
            return true;
        }

        // check for no overlap, and only permit coincident edges if the line
        // and the edge are colinear
        if nested_lt(bounds.right(), clip.left(), bounds.width())
            || nested_lt(clip.right(), bounds.left(), bounds.width())
            || nested_lt(bounds.bottom(), clip.top(), bounds.height())
            || nested_lt(clip.bottom(), bounds.top(), bounds.height())
        {
            return false;
        }
    }

    let (index0, index1) = if src[0].y < src[1].y { (0, 1) } else { (1, 0) };

    let mut tmp = src.clone();

    // now compute Y intersections
    if tmp[index0].y < clip.top() {
        tmp[index0] = Point::from_xy(sect_with_horizontal(src, clip.top()), clip.top());
    }

    if tmp[index1].y > clip.bottom() {
        tmp[index1] = Point::from_xy(sect_with_horizontal(src, clip.bottom()), clip.bottom());
    }

    let (index0, index1) = if tmp[0].x < tmp[1].x { (0, 1) } else { (1, 0) };

    // check for quick-reject in X again, now that we may have been chopped
    if tmp[index1].x <= clip.left() || tmp[index0].x >= clip.right() {
        // usually we will return false, but we don't if the line is vertical and coincident
        // with the clip.
        if tmp[0].x != tmp[1].x || tmp[0].x < clip.left() || tmp[0].x > clip.right() {
            return false;
        }
    }

    if tmp[index0].x < clip.left() {
        tmp[index0] = Point::from_xy(clip.left(), sect_with_vertical(src, clip.left()));
    }

    if tmp[index1].x > clip.right() {
        tmp[index1] = Point::from_xy(clip.right(), sect_with_vertical(src, clip.right()));
    }

    dst.copy_from_slice(&tmp);
    true
}

fn nested_lt(a: f32, b: f32, dim: f32) -> bool {
    a <= b && (a < b || dim > 0.0)
}

// returns true if outer contains inner, even if inner is empty.
fn contains_no_empty_check(outer: &Rect, inner: &Rect) -> bool {
    outer.left() <= inner.left()
        && outer.top() <= inner.top()
        && outer.right() >= inner.right()
        && outer.bottom() >= inner.bottom()
}