Adding upstream version 124.0.1.upstream/124.0.1

Signed-off-by: Daniel Baumann <daniel.baumann@progress-linux.org>

3 files changed, 626 insertions, 0 deletions

diff --git a/third_party/rust/plane-split/tests/clip.rs b/third_party/rust/plane-split/tests/clip.rs
new file mode 100644
index 0000000000..f243c3e843
--- /dev/null
+++ b/third_party/rust/plane-split/tests/clip.rs
@@ -0,0 +1,147 @@
+use euclid::{
+    default::{Rect, Transform3D},
+    point3, rect, vec3, Angle,
+};
+use plane_split::{Clipper, Plane, Polygon};
+
+use std::f64::consts::FRAC_PI_4;
+
+#[test]
+fn clip_in() {
+    let plane = Plane::from_unnormalized(vec3(1.0, 0.0, 1.0), 20.0)
+        .unwrap()
+        .unwrap();
+    let mut clipper = Clipper::new();
+    clipper.add(plane);
+
+    let poly = Polygon::from_points(
+        [
+            point3(-10.0, -10.0, 0.0),
+            point3(10.0, -10.0, 0.0),
+            point3(10.0, 10.0, 0.0),
+            point3(-10.0, 10.0, 0.0),
+        ],
+        0,
+    )
+    .unwrap();
+
+    let results = clipper.clip(poly.clone());
+    assert_eq!(results[0], poly);
+    assert_eq!(results.len(), 1);
+}
+
+#[test]
+fn clip_out() {
+    let plane = Plane::from_unnormalized(vec3(1.0, 0.0, 1.0), -20.0)
+        .unwrap()
+        .unwrap();
+    let mut clipper = Clipper::new();
+    clipper.add(plane);
+
+    let poly = Polygon::from_points(
+        [
+            point3(-10.0, -10.0, 0.0),
+            point3(10.0, -10.0, 0.0),
+            point3(10.0, 10.0, 0.0),
+            point3(-10.0, 10.0, 0.0),
+        ],
+        0,
+    )
+    .unwrap();
+
+    let results = clipper.clip(poly);
+    assert!(results.is_empty());
+}
+
+#[test]
+fn clip_parallel() {
+    let plane = Plane {
+        normal: vec3(0.0, 0.0, 1.0),
+        offset: 0.0,
+    };
+    let mut clipper = Clipper::new();
+    clipper.add(plane);
+
+    let poly = Polygon::from_points(
+        [
+            point3(-10.0, -10.0, 0.0),
+            point3(10.0, -10.0, 0.0),
+            point3(10.0, 10.0, 0.0),
+            point3(-10.0, 10.0, 0.0),
+        ],
+        0,
+    )
+    .unwrap();
+
+    let results = clipper.clip(poly);
+    assert!(results.is_empty());
+}
+
+#[test]
+fn clip_repeat() {
+    let plane = Plane::from_unnormalized(vec3(1.0, 0.0, 1.0), 0.0)
+        .unwrap()
+        .unwrap();
+    let mut clipper = Clipper::new();
+    clipper.add(plane.clone());
+    clipper.add(plane.clone());
+
+    let poly = Polygon::from_points(
+        [
+            point3(-10.0, -10.0, 0.0),
+            point3(10.0, -10.0, 0.0),
+            point3(10.0, 10.0, 0.0),
+            point3(-10.0, 10.0, 0.0),
+        ],
+        0,
+    )
+    .unwrap();
+
+    let results = clipper.clip(poly);
+    assert_eq!(results.len(), 1);
+    assert!(plane.signed_distance_sum_to(&results[0]) > 0.0);
+}
+
+#[test]
+fn clip_transformed() {
+    let t_rot: Transform3D<f64> = Transform3D::rotation(0.0, 1.0, 0.0, Angle::radians(-FRAC_PI_4));
+    let t_div: Transform3D<f64> = Transform3D::perspective(5.0);
+    let transform = t_rot.then(&t_div);
+
+    let polygon = Polygon::from_rect(rect(-10.0, -10.0, 20.0, 20.0), 0);
+    let bounds: Rect<f64> = rect(-1.0, -1.0, 2.0, 2.0);
+
+    let mut clipper = Clipper::new();
+    let results = clipper.clip_transformed(polygon, &transform, Some(bounds));
+    // iterating enforces the transformation checks/unwraps
+    assert_ne!(0, results.unwrap().count());
+}
+
+#[test]
+fn clip_badly_transformed() {
+    let mut tx = Transform3D::<f64>::identity();
+    tx.m14 = -0.0000001;
+    tx.m44 = 0.0;
+
+    let mut clipper = Clipper::new();
+    let polygon = Polygon::from_rect(rect(-10.0, -10.0, 20.0, 20.0), 0);
+    let results = clipper.clip_transformed(polygon, &tx, None);
+    assert!(results.is_err());
+}
+
+#[test]
+fn clip_near_coplanar() {
+    let tx = Transform3D::<f64>::new(
+        1.0, 0.0, 0.0, 0.0, 0.0, 1.0, 0.0, 0.0, -960.0, -625.0, 1.0, -1.0, 100.0, -2852.0, 0.0, 1.0,
+    );
+    let mut clipper = Clipper::new();
+    let polygon = Polygon::from_rect(rect(0.0, 0.0, 1703.0, 4020.0), 0);
+
+    let bounds1 = rect(0.0, -430.0, 2048.0, 2048.0);
+    let results1 = clipper.clip_transformed(polygon.clone(), &tx, Some(bounds1));
+    assert_ne!(0, results1.unwrap().count());
+
+    let bounds2 = rect(0.0, 0.0, 816.0, 1039.0);
+    let results2 = clipper.clip_transformed(polygon, &tx, Some(bounds2));
+    assert_ne!(0, results2.unwrap().count());
+}
diff --git a/third_party/rust/plane-split/tests/main.rs b/third_party/rust/plane-split/tests/main.rs
new file mode 100644
index 0000000000..0bcac5a179
--- /dev/null
+++ b/third_party/rust/plane-split/tests/main.rs
@@ -0,0 +1,341 @@
+use euclid::{
+    approxeq::ApproxEq,
+    default::{Rect, Size2D, Transform3D},
+    point2, point3, vec3, Angle,
+};
+use plane_split::{Intersection, Line, LineProjection, NegativeHemisphereError, Plane, Polygon};
+
+#[test]
+fn line_proj_bounds() {
+    assert_eq!(
+        (-5.0f64, 4.0),
+        LineProjection {
+            markers: [-5.0f64, 1.0, 4.0, 2.0]
+        }
+        .get_bounds()
+    );
+    assert_eq!(
+        (1f64, 4.0),
+        LineProjection {
+            markers: [4f64, 3.0, 2.0, 1.0]
+        }
+        .get_bounds()
+    );
+}
+
+#[test]
+fn valid() {
+    let poly_a: Polygon<usize> = Polygon {
+        points: [
+            point3(0.0, 0.0, 0.0),
+            point3(1.0, 1.0, 1.0),
+            point3(1.0, 1.0, 0.0),
+            point3(0.0, 1.0, 1.0),
+        ],
+        plane: Plane {
+            normal: vec3(0.0, 1.0, 0.0),
+            offset: -1.0,
+        },
+        anchor: 0,
+    };
+    assert!(!poly_a.is_valid()); // points[0] is outside
+    let poly_b: Polygon<usize> = Polygon {
+        points: [
+            point3(0.0, 1.0, 0.0),
+            point3(1.0, 1.0, 1.0),
+            point3(1.0, 1.0, 0.0),
+            point3(0.0, 1.0, 1.0),
+        ],
+        plane: Plane {
+            normal: vec3(0.0, 1.0, 0.0),
+            offset: -1.0,
+        },
+        anchor: 0,
+    };
+    assert!(!poly_b.is_valid()); // winding is incorrect
+    let poly_c: Polygon<usize> = Polygon {
+        points: [
+            point3(0.0, 0.0, 1.0),
+            point3(1.0, 0.0, 1.0),
+            point3(1.0, 1.0, 1.0),
+            point3(0.0, 1.0, 1.0),
+        ],
+        plane: Plane {
+            normal: vec3(0.0, 0.0, 1.0),
+            offset: -1.0,
+        },
+        anchor: 0,
+    };
+    assert!(poly_c.is_valid());
+}
+
+#[test]
+fn empty() {
+    let poly = Polygon::from_points(
+        [
+            point3(0.0, 0.0, 1.0),
+            point3(0.0, 0.0, 1.0),
+            point3(0.0, 0.00000001, 1.0),
+            point3(1.0, 0.0, 0.0),
+        ],
+        1usize,
+    );
+    assert_eq!(None, poly);
+}
+
+fn test_transformed(rect: Rect<f64>, transform: Transform3D<f64>) {
+    let poly = Polygon::from_transformed_rect(rect, transform, 0).unwrap();
+    assert!(poly.is_valid());
+
+    let inv_transform = transform.inverse().unwrap();
+    let poly2 =
+        Polygon::from_transformed_rect_with_inverse(rect, &transform, &inv_transform, 0).unwrap();
+    assert_eq!(poly.points, poly2.points);
+    assert!(poly.plane.offset.approx_eq(&poly2.plane.offset));
+    assert!(poly.plane.normal.dot(poly2.plane.normal).approx_eq(&1.0));
+}
+
+#[test]
+fn from_transformed_rect() {
+    let rect = Rect::new(point2(10.0, 10.0), Size2D::new(20.0, 30.0));
+    let transform = Transform3D::rotation(0.5f64.sqrt(), 0.0, 0.5f64.sqrt(), Angle::radians(5.0))
+        .pre_translate(vec3(0.0, 0.0, 10.0));
+    test_transformed(rect, transform);
+}
+
+#[test]
+fn from_transformed_rect_perspective() {
+    let rect = Rect::new(point2(-10.0, -5.0), Size2D::new(20.0, 30.0));
+    let mut transform = Transform3D::perspective(400.0).pre_translate(vec3(0.0, 0.0, 100.0));
+    transform.m44 = 0.7; //for fun
+    test_transformed(rect, transform);
+}
+
+#[test]
+fn untransform_point() {
+    let poly: Polygon<usize> = Polygon {
+        points: [
+            point3(0.0, 0.0, 0.0),
+            point3(0.5, 1.0, 0.0),
+            point3(1.5, 1.0, 0.0),
+            point3(1.0, 0.0, 0.0),
+        ],
+        plane: Plane {
+            normal: vec3(0.0, 1.0, 0.0),
+            offset: 0.0,
+        },
+        anchor: 0,
+    };
+    assert_eq!(poly.untransform_point(poly.points[0]), point2(0.0, 0.0));
+    assert_eq!(poly.untransform_point(poly.points[1]), point2(1.0, 0.0));
+    assert_eq!(poly.untransform_point(poly.points[2]), point2(1.0, 1.0));
+    assert_eq!(poly.untransform_point(poly.points[3]), point2(0.0, 1.0));
+}
+
+#[test]
+fn are_outside() {
+    let plane = Plane {
+        normal: vec3(0.0, 0.0, 1.0),
+        offset: -1.0,
+    };
+    assert!(plane.are_outside(&[point3(0.0, 0.0, 1.1), point3(1.0, 1.0, 2.0),]));
+    assert!(plane.are_outside(&[point3(0.5, 0.5, 1.0),]));
+    assert!(!plane.are_outside(&[point3(0.0, 0.0, 1.0), point3(0.0, 0.0, -1.0),]));
+}
+
+#[test]
+fn intersect() {
+    let poly_a: Polygon<usize> = Polygon {
+        points: [
+            point3(0.0, 0.0, 1.0),
+            point3(1.0, 0.0, 1.0),
+            point3(1.0, 1.0, 1.0),
+            point3(0.0, 1.0, 1.0),
+        ],
+        plane: Plane {
+            normal: vec3(0.0, 0.0, 1.0),
+            offset: -1.0,
+        },
+        anchor: 0,
+    };
+    assert!(poly_a.is_valid());
+    let poly_b: Polygon<usize> = Polygon {
+        points: [
+            point3(0.5, 0.0, 2.0),
+            point3(0.5, 1.0, 2.0),
+            point3(0.5, 1.0, 0.0),
+            point3(0.5, 0.0, 0.0),
+        ],
+        plane: Plane {
+            normal: vec3(1.0, 0.0, 0.0),
+            offset: -0.5,
+        },
+        anchor: 0,
+    };
+    assert!(poly_b.is_valid());
+
+    let intersection = match poly_a.intersect(&poly_b) {
+        Intersection::Inside(result) => result,
+        _ => panic!("Bad intersection"),
+    };
+    assert!(intersection.is_valid());
+    // confirm the origin is on both planes
+    assert!(poly_a
+        .plane
+        .signed_distance_to(&intersection.origin)
+        .approx_eq(&0.0));
+    assert!(poly_b
+        .plane
+        .signed_distance_to(&intersection.origin)
+        .approx_eq(&0.0));
+    // confirm the direction is coplanar to both planes
+    assert!(poly_a.plane.normal.dot(intersection.dir).approx_eq(&0.0));
+    assert!(poly_b.plane.normal.dot(intersection.dir).approx_eq(&0.0));
+
+    let poly_c: Polygon<usize> = Polygon {
+        points: [
+            point3(0.0, -1.0, 2.0),
+            point3(0.0, -1.0, 0.0),
+            point3(0.0, 0.0, 0.0),
+            point3(0.0, 0.0, 2.0),
+        ],
+        plane: Plane {
+            normal: vec3(1.0, 0.0, 0.0),
+            offset: 0.0,
+        },
+        anchor: 0,
+    };
+    assert!(poly_c.is_valid());
+    let poly_d: Polygon<usize> = Polygon {
+        points: [
+            point3(0.0, 0.0, 0.5),
+            point3(1.0, 0.0, 0.5),
+            point3(1.0, 1.0, 0.5),
+            point3(0.0, 1.0, 0.5),
+        ],
+        plane: Plane {
+            normal: vec3(0.0, 0.0, 1.0),
+            offset: -0.5,
+        },
+        anchor: 0,
+    };
+    assert!(poly_d.is_valid());
+
+    assert!(poly_a.intersect(&poly_c).is_outside());
+    assert!(poly_a.intersect(&poly_d).is_outside());
+}
+
+fn test_cut(poly_base: &Polygon<usize>, extra_count: u8, line: Line) {
+    assert!(line.is_valid());
+
+    let normal = poly_base.plane.normal.cross(line.dir).normalize();
+    let mut poly = poly_base.clone();
+    let (extra1, extra2) = poly.split_with_normal(&line, &normal);
+    assert!(poly.is_valid() && poly_base.contains(&poly));
+    assert_eq!(extra_count > 0, extra1.is_some());
+    assert_eq!(extra_count > 1, extra2.is_some());
+    if let Some(extra) = extra1 {
+        assert!(extra.is_valid() && poly_base.contains(&extra));
+    }
+    if let Some(extra) = extra2 {
+        assert!(extra.is_valid() && poly_base.contains(&extra));
+    }
+}
+
+#[test]
+fn split() {
+    let poly: Polygon<usize> = Polygon {
+        points: [
+            point3(0.0, 1.0, 0.0),
+            point3(1.0, 1.0, 0.0),
+            point3(1.0, 1.0, 1.0),
+            point3(0.0, 1.0, 1.0),
+        ],
+        plane: Plane {
+            normal: vec3(0.0, 1.0, 0.0),
+            offset: -1.0,
+        },
+        anchor: 0,
+    };
+
+    // non-intersecting line
+    test_cut(
+        &poly,
+        0,
+        Line {
+            origin: point3(0.0, 1.0, 0.5),
+            dir: vec3(0.0, 1.0, 0.0),
+        },
+    );
+
+    // simple cut (diff=2)
+    test_cut(
+        &poly,
+        1,
+        Line {
+            origin: point3(0.0, 1.0, 0.5),
+            dir: vec3(1.0, 0.0, 0.0),
+        },
+    );
+
+    // complex cut (diff=1, wrapped)
+    test_cut(
+        &poly,
+        2,
+        Line {
+            origin: point3(0.0, 1.0, 0.5),
+            dir: vec3(0.5f64.sqrt(), 0.0, -0.5f64.sqrt()),
+        },
+    );
+
+    // complex cut (diff=1, non-wrapped)
+    test_cut(
+        &poly,
+        2,
+        Line {
+            origin: point3(0.5, 1.0, 0.0),
+            dir: vec3(0.5f64.sqrt(), 0.0, 0.5f64.sqrt()),
+        },
+    );
+
+    // complex cut (diff=3)
+    test_cut(
+        &poly,
+        2,
+        Line {
+            origin: point3(0.5, 1.0, 0.0),
+            dir: vec3(-0.5f64.sqrt(), 0.0, 0.5f64.sqrt()),
+        },
+    );
+
+    // perfect diagonal
+    test_cut(
+        &poly,
+        1,
+        Line {
+            origin: point3(0.0, 1.0, 0.0),
+            dir: vec3(0.5f64.sqrt(), 0.0, 0.5f64.sqrt()),
+        },
+    );
+}
+
+#[test]
+fn plane_unnormalized() {
+    let zero_vec = vec3(0.0000001, 0.0, 0.0);
+    let mut plane: Result<Option<Plane>, _> = Plane::from_unnormalized(zero_vec, 1.0);
+    assert_eq!(plane, Ok(None));
+    plane = Plane::from_unnormalized(zero_vec, 0.0);
+    assert_eq!(plane, Err(NegativeHemisphereError));
+    plane = Plane::from_unnormalized(zero_vec, -0.5);
+    assert_eq!(plane, Err(NegativeHemisphereError));
+
+    let plane = Plane::from_unnormalized(vec3(-3.0, 4.0, 0.0), 2.0)
+        .unwrap()
+        .unwrap();
+    let expected = Plane {
+        normal: vec3(-3.0 / 5.0, 4.0 / 5.0, 0.0),
+        offset: 2.0 / 5.0,
+    };
+    assert!(plane.normal.approx_eq(&expected.normal));
+    assert!(plane.offset.approx_eq(&expected.offset));
+}
diff --git a/third_party/rust/plane-split/tests/split.rs b/third_party/rust/plane-split/tests/split.rs
new file mode 100644
index 0000000000..60d1d8035f
--- /dev/null
+++ b/third_party/rust/plane-split/tests/split.rs
@@ -0,0 +1,138 @@
+use euclid::{
+    default::{Rect, Transform3D},
+    rect, vec3, Angle,
+};
+use plane_split::PlaneCut;
+use plane_split::{make_grid, BspSplitter, Polygon};
+use std::f64::consts::FRAC_PI_4;
+
+fn grid_impl(count: usize, splitter: &mut BspSplitter<usize>) {
+    let polys = make_grid(count);
+    let result = splitter.solve(&polys, vec3(0.0, 0.0, 1.0));
+    assert_eq!(result.len(), count + count * count + count * count * count);
+}
+
+#[test]
+fn grid_bsp() {
+    grid_impl(2, &mut BspSplitter::new());
+}
+
+fn sort_rotation(splitter: &mut BspSplitter<usize>) {
+    let transform0: Transform3D<f64> =
+        Transform3D::rotation(0.0, 1.0, 0.0, Angle::radians(-FRAC_PI_4));
+    let transform1: Transform3D<f64> = Transform3D::rotation(0.0, 1.0, 0.0, Angle::radians(0.0));
+    let transform2: Transform3D<f64> =
+        Transform3D::rotation(0.0, 1.0, 0.0, Angle::radians(FRAC_PI_4));
+
+    let rect: Rect<f64> = rect(-10.0, -10.0, 20.0, 20.0);
+    let p1 = Polygon::from_transformed_rect(rect, transform0, 0);
+    let p2 = Polygon::from_transformed_rect(rect, transform1, 1);
+    let p3 = Polygon::from_transformed_rect(rect, transform2, 2);
+    assert!(
+        p1.is_some() && p2.is_some() && p3.is_some(),
+        "Cannot construct transformed polygons"
+    );
+
+    let polys = [p1.unwrap(), p2.unwrap(), p3.unwrap()];
+    let result = splitter.solve(&polys, vec3(0.0, 0.0, -1.0));
+    let ids: Vec<_> = result.iter().map(|poly| poly.anchor).collect();
+    assert_eq!(&ids, &[2, 1, 0, 1, 2]);
+}
+
+#[test]
+fn rotation_bsp() {
+    sort_rotation(&mut BspSplitter::new());
+}
+
+fn sort_trivial(splitter: &mut BspSplitter<usize>) {
+    let anchors: Vec<_> = (0usize..10).collect();
+    let rect: Rect<f64> = rect(-10.0, -10.0, 20.0, 20.0);
+    let polys: Vec<_> = anchors
+        .iter()
+        .map(|&anchor| {
+            let transform: Transform3D<f64> = Transform3D::translation(0.0, 0.0, anchor as f64);
+            let poly = Polygon::from_transformed_rect(rect, transform, anchor);
+            assert!(poly.is_some(), "Cannot construct transformed polygons");
+            poly.unwrap()
+        })
+        .collect();
+
+    let result = splitter.solve(&polys, vec3(0.0, 0.0, -1.0));
+    let anchors1: Vec<_> = result.iter().map(|p| p.anchor).collect();
+    let mut anchors2 = anchors1.clone();
+    anchors2.sort_by_key(|&a| -(a as i32));
+    //make sure Z is sorted backwards
+    assert_eq!(anchors1, anchors2);
+}
+
+fn sort_external(splitter: &mut BspSplitter<usize>) {
+    let rect0: Rect<f64> = rect(-10.0, -10.0, 20.0, 20.0);
+    let poly0 = Polygon::from_rect(rect0, 0);
+    let poly1 = {
+        let transform0: Transform3D<f64> =
+            Transform3D::rotation(1.0, 0.0, 0.0, Angle::radians(2.0 * FRAC_PI_4));
+        let transform1: Transform3D<f64> = Transform3D::translation(0.0, 100.0, 0.0);
+        Polygon::from_transformed_rect(rect0, transform0.then(&transform1), 1).unwrap()
+    };
+
+    let result = splitter.solve(&[poly0, poly1], vec3(1.0, 1.0, 0.0).normalize());
+    let anchors: Vec<_> = result.iter().map(|p| p.anchor).collect();
+    // make sure the second polygon is split in half around the plane of the first one,
+    // even if geometrically their polygons don't intersect.
+    assert_eq!(anchors, vec![1, 0, 1]);
+}
+
+#[test]
+fn trivial_bsp() {
+    sort_trivial(&mut BspSplitter::new());
+}
+
+#[test]
+fn external_bsp() {
+    sort_external(&mut BspSplitter::new());
+}
+
+#[test]
+fn test_cut() {
+    use smallvec::SmallVec;
+    let rect: Rect<f64> = rect(-10.0, -10.0, 20.0, 20.0);
+    let poly = Polygon::from_rect(rect, 0);
+    let mut poly2 = Polygon::from_rect(rect, 0);
+    // test robustness for positions
+    for p in &mut poly2.points {
+        p.z += 0.00000001;
+    }
+
+    let mut front: SmallVec<[Polygon<i32>; 2]> = SmallVec::new();
+    let mut back: SmallVec<[Polygon<i32>; 2]> = SmallVec::new();
+
+    assert_eq!(poly.cut(&poly2, &mut front, &mut back), PlaneCut::Sibling);
+    assert!(front.is_empty());
+    assert!(back.is_empty());
+
+    // test robustness for normal
+    poly2.plane.normal.z += 0.00000001;
+    assert_eq!(poly.cut(&poly2, &mut front, &mut back), PlaneCut::Sibling);
+    assert!(front.is_empty());
+    assert!(back.is_empty());
+
+    // test opposite normal handling
+    poly2.plane.normal *= -1.0;
+    assert_eq!(poly.cut(&poly2, &mut front, &mut back), PlaneCut::Sibling);
+    assert!(front.is_empty());
+    assert!(back.is_empty());
+
+    // test grouping front
+    poly2.plane.offset += 0.1;
+    assert_eq!(poly.cut(&poly2, &mut front, &mut back), PlaneCut::Cut);
+    assert_eq!(front.len(), 1);
+    assert!(back.is_empty());
+
+    front.clear();
+
+    // test grouping back
+    poly2.plane.normal *= -1.0;
+    assert_eq!(poly.cut(&poly2, &mut front, &mut back), PlaneCut::Cut);
+    assert_eq!(back.len(), 1);
+    assert!(front.is_empty());
+}