1 files changed, 152 insertions, 0 deletions
diff --git a/third_party/rust/plane-split/src/bsp.rs b/third_party/rust/plane-split/src/bsp.rs
new file mode 100755
index 0000000000..b9bb3109d1
--- /dev/null
+++ b/third_party/rust/plane-split/src/bsp.rs
@@ -0,0 +1,152 @@
+use crate::{is_zero, Intersection, Plane, Polygon, Splitter};
+
+use binary_space_partition::{BspNode, Plane as BspPlane, PlaneCut};
+use euclid::{approxeq::ApproxEq, Point3D, Vector3D};
+use num_traits::{Float, One, Zero};
+
+use std::{fmt, iter, ops};
+
+impl<T, U, A> BspPlane for Polygon<T, U, A>
+where
+    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
+        + Float,
+    U: fmt::Debug,
+    A: Copy + fmt::Debug,
+{
+    fn cut(&self, mut poly: Self) -> PlaneCut<Self> {
+        log::debug!("\tCutting anchor {:?} by {:?}", poly.anchor, self.anchor);
+        log::trace!("\t\tbase {:?}", self.plane);
+
+        //Note: we treat `self` as a plane, and `poly` as a concrete polygon here
+        let (intersection, dist) = match self.plane.intersect(&poly.plane) {
+            None => {
+                let ndot = self.plane.normal.dot(poly.plane.normal);
+                log::debug!("\t\tNormals are aligned with {:?}", ndot);
+                let dist = self.plane.offset - ndot * poly.plane.offset;
+                (Intersection::Coplanar, dist)
+            }
+            Some(_) if self.plane.are_outside(&poly.points) => {
+                //Note: we can't start with `are_outside` because it's subject to FP precision
+                let dist = self.plane.signed_distance_sum_to(&poly);
+                (Intersection::Outside, dist)
+            }
+            Some(line) => {
+                //Note: distance isn't relevant here
+                (Intersection::Inside(line), T::zero())
+            }
+        };
+
+        match intersection {
+            //Note: we deliberately make the comparison wider than just with T::epsilon().
+            // This is done to avoid mistakenly ordering items that should be on the same
+            // plane but end up slightly different due to the floating point precision.
+            Intersection::Coplanar if is_zero(dist) => {
+                log::debug!("\t\tCoplanar at {:?}", dist);
+                PlaneCut::Sibling(poly)
+            }
+            Intersection::Coplanar | Intersection::Outside => {
+                log::debug!("\t\tOutside at {:?}", dist);
+                if dist > T::zero() {
+                    PlaneCut::Cut {
+                        front: vec![poly],
+                        back: vec![],
+                    }
+                } else {
+                    PlaneCut::Cut {
+                        front: vec![],
+                        back: vec![poly],
+                    }
+                }
+            }
+            Intersection::Inside(line) => {
+                log::debug!("\t\tCut across {:?}", line);
+                let (res_add1, res_add2) = poly.split_with_normal(&line, &self.plane.normal);
+                let mut front = Vec::new();
+                let mut back = Vec::new();
+
+                for sub in iter::once(poly)
+                    .chain(res_add1)
+                    .chain(res_add2)
+                    .filter(|p| !p.is_empty())
+                {
+                    let dist = self.plane.signed_distance_sum_to(&sub);
+                    if dist > T::zero() {
+                        log::trace!("\t\t\tdist {:?} -> front: {:?}", dist, sub);
+                        front.push(sub)
+                    } else {
+                        log::trace!("\t\t\tdist {:?} -> back: {:?}", dist, sub);
+                        back.push(sub)
+                    }
+                }
+
+                PlaneCut::Cut { front, back }
+            }
+        }
+    }
+
+    fn is_aligned(&self, other: &Self) -> bool {
+        self.plane.normal.dot(other.plane.normal) > T::zero()
+    }
+}
+
+/// Binary Space Partitioning splitter, uses a BSP tree.
+pub struct BspSplitter<T, U, A> {
+    tree: BspNode<Polygon<T, U, A>>,
+    result: Vec<Polygon<T, U, A>>,
+}
+
+impl<T, U, A> BspSplitter<T, U, A> {
+    /// Create a new BSP splitter.
+    pub fn new() -> Self {
+        BspSplitter {
+            tree: BspNode::new(),
+            result: Vec::new(),
+        }
+    }
+}
+
+impl<T, U, A> Splitter<T, U, A> for BspSplitter<T, U, A>
+where
+    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 + Default,
+{
+    fn reset(&mut self) {
+        self.tree = BspNode::new();
+    }
+
+    fn add(&mut self, poly: Polygon<T, U, A>) {
+        self.tree.insert(poly);
+    }
+
+    fn sort(&mut self, view: Vector3D<T, U>) -> &[Polygon<T, U, A>] {
+        //debug!("\t\ttree before sorting {:?}", self.tree);
+        let poly = Polygon {
+            points: [Point3D::origin(); 4],
+            plane: Plane {
+                normal: -view, //Note: BSP `order()` is back to front
+                offset: T::zero(),
+            },
+            anchor: A::default(),
+        };
+        self.result.clear();
+        self.tree.order(&poly, &mut self.result);
+        &self.result
+    }
+}