From 36d22d82aa202bb199967e9512281e9a53db42c9 Mon Sep 17 00:00:00 2001 From: Daniel Baumann Date: Sun, 7 Apr 2024 21:33:14 +0200 Subject: Adding upstream version 115.7.0esr. Signed-off-by: Daniel Baumann --- third_party/rust/plane-split/tests/clip.rs | 147 ++++++++++++ third_party/rust/plane-split/tests/main.rs | 341 ++++++++++++++++++++++++++++ third_party/rust/plane-split/tests/split.rs | 138 +++++++++++ 3 files changed, 626 insertions(+) create mode 100644 third_party/rust/plane-split/tests/clip.rs create mode 100644 third_party/rust/plane-split/tests/main.rs create mode 100644 third_party/rust/plane-split/tests/split.rs (limited to 'third_party/rust/plane-split/tests') 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 = Transform3D::rotation(0.0, 1.0, 0.0, Angle::radians(-FRAC_PI_4)); + let t_div: Transform3D = 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 = 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::::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::::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 = 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 = 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 = 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, transform: Transform3D) { + 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 = 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 = 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 = 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 = 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 = 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, 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 = 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, _> = 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) { + 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) { + let transform0: Transform3D = + Transform3D::rotation(0.0, 1.0, 0.0, Angle::radians(-FRAC_PI_4)); + let transform1: Transform3D = Transform3D::rotation(0.0, 1.0, 0.0, Angle::radians(0.0)); + let transform2: Transform3D = + Transform3D::rotation(0.0, 1.0, 0.0, Angle::radians(FRAC_PI_4)); + + let rect: Rect = 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) { + let anchors: Vec<_> = (0usize..10).collect(); + let rect: Rect = rect(-10.0, -10.0, 20.0, 20.0); + let polys: Vec<_> = anchors + .iter() + .map(|&anchor| { + let transform: Transform3D = 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) { + let rect0: Rect = rect(-10.0, -10.0, 20.0, 20.0); + let poly0 = Polygon::from_rect(rect0, 0); + let poly1 = { + let transform0: Transform3D = + Transform3D::rotation(1.0, 0.0, 0.0, Angle::radians(2.0 * FRAC_PI_4)); + let transform1: Transform3D = 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 = 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; 2]> = SmallVec::new(); + let mut back: SmallVec<[Polygon; 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()); +} -- cgit v1.2.3