1 files changed, 161 insertions, 0 deletions
diff --git a/third_party/rust/plane-split/src/clip.rs b/third_party/rust/plane-split/src/clip.rs
new file mode 100755
index 0000000000..ee240b2f2f
--- /dev/null
+++ b/third_party/rust/plane-split/src/clip.rs
@@ -0,0 +1,161 @@
+use crate::{Intersection, NegativeHemisphereError, Plane, Polygon};
+
+use euclid::{approxeq::ApproxEq, Rect, Scale, Transform3D, Trig, Vector3D};
+use num_traits::{Float, One, Zero};
+
+use std::{fmt, iter, mem, ops};
+
+/// A helper object to clip polygons by a number of planes.
+#[derive(Debug)]
+pub struct Clipper<T, U, A> {
+    clips: Vec<Plane<T, U>>,
+    results: Vec<Polygon<T, U, A>>,
+    temp: Vec<Polygon<T, U, A>>,
+}
+
+impl<
+        T: Copy
+            + fmt::Debug
+            + ApproxEq<T>
+            + ops::Sub<T, Output = T>
+            + ops::Add<T, Output = T>
+            + ops::Mul<T, Output = T>
+            + ops::Div<T, Output = T>
+            + Zero
+            + One
+            + Float,
+        U: fmt::Debug,
+        A: Copy + fmt::Debug,
+    > Clipper<T, U, A>
+{
+    /// Create a new clipper object.
+    pub fn new() -> Self {
+        Clipper {
+            clips: Vec::new(),
+            results: Vec::new(),
+            temp: Vec::new(),
+        }
+    }
+
+    /// Reset the clipper internals, but preserve the allocation.
+    pub fn reset(&mut self) {
+        self.clips.clear();
+    }
+
+    /// Extract the clipping planes that define the frustum for a given transformation.
+    pub fn frustum_planes<V>(
+        t: &Transform3D<T, U, V>,
+        bounds: Option<Rect<T, V>>,
+    ) -> Result<impl Iterator<Item = Plane<T, U>>, NegativeHemisphereError> {
+        let mw = Vector3D::new(t.m14, t.m24, t.m34);
+        let plane_positive = Plane::from_unnormalized(mw, t.m44)?;
+
+        let bounds_iter_maybe = match bounds {
+            Some(bounds) => {
+                let mx = Vector3D::new(t.m11, t.m21, t.m31);
+                let left = bounds.origin.x;
+                let plane_left =
+                    Plane::from_unnormalized(mx - mw * Scale::new(left), t.m41 - t.m44 * left)?;
+                let right = bounds.origin.x + bounds.size.width;
+                let plane_right =
+                    Plane::from_unnormalized(mw * Scale::new(right) - mx, t.m44 * right - t.m41)?;
+
+                let my = Vector3D::new(t.m12, t.m22, t.m32);
+                let top = bounds.origin.y;
+                let plane_top =
+                    Plane::from_unnormalized(my - mw * Scale::new(top), t.m42 - t.m44 * top)?;
+                let bottom = bounds.origin.y + bounds.size.height;
+                let plane_bottom =
+                    Plane::from_unnormalized(mw * Scale::new(bottom) - my, t.m44 * bottom - t.m42)?;
+
+                Some(
+                    plane_left
+                        .into_iter()
+                        .chain(plane_right)
+                        .chain(plane_top)
+                        .chain(plane_bottom),
+                )
+            }
+            None => None,
+        };
+
+        Ok(bounds_iter_maybe
+            .into_iter()
+            .flat_map(|pi| pi)
+            .chain(plane_positive))
+    }
+
+    /// Add a clipping plane to the list. The plane will clip everything behind it,
+    /// where the direction is set by the plane normal.
+    pub fn add(&mut self, plane: Plane<T, U>) {
+        self.clips.push(plane);
+    }
+
+    /// Clip specified polygon by the contained planes, return the fragmented polygons.
+    pub fn clip(&mut self, polygon: Polygon<T, U, A>) -> &[Polygon<T, U, A>] {
+        log::debug!("\tClipping {:?}", polygon);
+        self.results.clear();
+        self.results.push(polygon);
+
+        for clip in &self.clips {
+            self.temp.clear();
+            mem::swap(&mut self.results, &mut self.temp);
+
+            for mut poly in self.temp.drain(..) {
+                let dist = match poly.intersect_plane(clip) {
+                    Intersection::Inside(line) => {
+                        let (res1, res2) = poly.split_with_normal(&line, &clip.normal);
+                        self.results.extend(
+                            iter::once(poly)
+                                .chain(res1)
+                                .chain(res2)
+                                .filter(|p| clip.signed_distance_sum_to(p) > T::zero()),
+                        );
+                        continue;
+                    }
+                    Intersection::Coplanar => {
+                        let ndot = poly.plane.normal.dot(clip.normal);
+                        clip.offset - ndot * poly.plane.offset
+                    }
+                    Intersection::Outside => clip.signed_distance_sum_to(&poly),
+                };
+
+                if dist > T::zero() {
+                    self.results.push(poly);
+                }
+            }
+        }
+
+        &self.results
+    }
+
+    /// Clip the primitive with the frustum of the specified transformation,
+    /// returning a sequence of polygons in the transformed space.
+    /// Returns None if the transformation can't be frustum clipped.
+    pub fn clip_transformed<'a, V>(
+        &'a mut self,
+        polygon: Polygon<T, U, A>,
+        transform: &'a Transform3D<T, U, V>,
+        bounds: Option<Rect<T, V>>,
+    ) -> Result<impl 'a + Iterator<Item = Polygon<T, V, A>>, NegativeHemisphereError>
+    where
+        T: Trig,
+        V: 'a + fmt::Debug,
+    {
+        let planes = Self::frustum_planes(transform, bounds)?;
+
+        let old_count = self.clips.len();
+        self.clips.extend(planes);
+        self.clip(polygon);
+        // remove the frustum planes
+        while self.clips.len() > old_count {
+            self.clips.pop();
+        }
+
+        let polys = self
+            .results
+            .drain(..)
+            .flat_map(move |poly| poly.transform(transform));
+        Ok(polys)
+    }
+}