Bug 1525087 - Plane split dependency update to 0.13.5 r=kats
authorDzmitry Malyshau <dmalyshau@mozilla.com>
Tue, 05 Feb 2019 15:28:52 +0000
changeset 456792 2cbf16256f4ef5c0e234229ba5fb8840cdf04f4d
parent 456791 80040669106ba13b73cfaac4605d3a611b27ba47
child 456793 954ae98c066e4f06b1f4de68dbe53034efb37aee
push id35504
push usercsabou@mozilla.com
push dateTue, 05 Feb 2019 21:57:12 +0000
treeherdermozilla-central@1e374e23c02f [default view] [failures only]
perfherder[talos] [build metrics] [platform microbench] (compared to previous push)
reviewerskats
bugs1525087
milestone67.0a1
first release with
nightly linux32
nightly linux64
nightly mac
nightly win32
nightly win64
last release without
nightly linux32
nightly linux64
nightly mac
nightly win32
nightly win64
Bug 1525087 - Plane split dependency update to 0.13.5 r=kats Update to have https://github.com/servo/plane-split/pull/27 included Differential Revision: https://phabricator.services.mozilla.com/D18593
Cargo.lock
gfx/wr/Cargo.lock
third_party/rust/plane-split/.cargo-checksum.json
third_party/rust/plane-split/Cargo.toml
third_party/rust/plane-split/src/bsp.rs
third_party/rust/plane-split/src/clip.rs
third_party/rust/plane-split/src/lib.rs
third_party/rust/plane-split/src/polygon.rs
third_party/rust/plane-split/tests/main.rs
third_party/rust/plane-split/tests/split.rs
--- a/Cargo.lock
+++ b/Cargo.lock
@@ -1941,17 +1941,17 @@ source = "registry+https://github.com/ru
 
 [[package]]
 name = "plain"
 version = "0.2.3"
 source = "registry+https://github.com/rust-lang/crates.io-index"
 
 [[package]]
 name = "plane-split"
-version = "0.13.4"
+version = "0.13.6"
 source = "registry+https://github.com/rust-lang/crates.io-index"
 dependencies = [
  "binary-space-partition 0.1.2 (registry+https://github.com/rust-lang/crates.io-index)",
  "euclid 0.19.5 (registry+https://github.com/rust-lang/crates.io-index)",
  "log 0.4.6 (registry+https://github.com/rust-lang/crates.io-index)",
  "num-traits 0.2.6 (registry+https://github.com/rust-lang/crates.io-index)",
 ]
 
@@ -3027,17 +3027,17 @@ dependencies = [
  "freetype 0.4.0 (registry+https://github.com/rust-lang/crates.io-index)",
  "fxhash 0.2.1 (registry+https://github.com/rust-lang/crates.io-index)",
  "gleam 0.6.8 (registry+https://github.com/rust-lang/crates.io-index)",
  "lazy_static 1.0.1 (registry+https://github.com/rust-lang/crates.io-index)",
  "libc 0.2.43 (registry+https://github.com/rust-lang/crates.io-index)",
  "log 0.4.6 (registry+https://github.com/rust-lang/crates.io-index)",
  "malloc_size_of_derive 0.1.0 (registry+https://github.com/rust-lang/crates.io-index)",
  "num-traits 0.2.6 (registry+https://github.com/rust-lang/crates.io-index)",
- "plane-split 0.13.4 (registry+https://github.com/rust-lang/crates.io-index)",
+ "plane-split 0.13.6 (registry+https://github.com/rust-lang/crates.io-index)",
  "rayon 1.0.0 (registry+https://github.com/rust-lang/crates.io-index)",
  "ron 0.1.7 (registry+https://github.com/rust-lang/crates.io-index)",
  "serde 1.0.80 (registry+https://github.com/rust-lang/crates.io-index)",
  "sha2 0.8.0 (registry+https://github.com/rust-lang/crates.io-index)",
  "smallvec 0.6.6 (registry+https://github.com/rust-lang/crates.io-index)",
  "thread_profiler 0.1.1 (registry+https://github.com/rust-lang/crates.io-index)",
  "time 0.1.40 (registry+https://github.com/rust-lang/crates.io-index)",
  "webrender_api 0.58.0",
@@ -3396,17 +3396,17 @@ dependencies = [
 "checksum percent-encoding 1.0.0 (registry+https://github.com/rust-lang/crates.io-index)" = "de154f638187706bde41d9b4738748933d64e6b37bdbffc0b47a97d16a6ae356"
 "checksum petgraph 0.4.13 (registry+https://github.com/rust-lang/crates.io-index)" = "9c3659d1ee90221741f65dd128d9998311b0e40c5d3c23a62445938214abce4f"
 "checksum phf 0.7.21 (registry+https://github.com/rust-lang/crates.io-index)" = "cb325642290f28ee14d8c6201159949a872f220c62af6e110a56ea914fbe42fc"
 "checksum phf_codegen 0.7.21 (registry+https://github.com/rust-lang/crates.io-index)" = "d62594c0bb54c464f633175d502038177e90309daf2e0158be42ed5f023ce88f"
 "checksum phf_generator 0.7.21 (registry+https://github.com/rust-lang/crates.io-index)" = "6b07ffcc532ccc85e3afc45865469bf5d9e4ef5bfcf9622e3cfe80c2d275ec03"
 "checksum phf_shared 0.7.21 (registry+https://github.com/rust-lang/crates.io-index)" = "07e24b0ca9643bdecd0632f2b3da6b1b89bbb0030e0b992afc1113b23a7bc2f2"
 "checksum pkg-config 0.3.9 (registry+https://github.com/rust-lang/crates.io-index)" = "3a8b4c6b8165cd1a1cd4b9b120978131389f64bdaf456435caa41e630edba903"
 "checksum plain 0.2.3 (registry+https://github.com/rust-lang/crates.io-index)" = "b4596b6d070b27117e987119b4dac604f3c58cfb0b191112e24771b2faeac1a6"
-"checksum plane-split 0.13.4 (registry+https://github.com/rust-lang/crates.io-index)" = "69f5ea52d7bf50ff02342f5af8527c81030bac5545e92eeeb4a2dfd7bfd2ef69"
+"checksum plane-split 0.13.6 (registry+https://github.com/rust-lang/crates.io-index)" = "b84b8cf2daa6a829b3e756fb75e0eab8e0d963754de9bfc83a4373a47121323a"
 "checksum podio 0.1.5 (registry+https://github.com/rust-lang/crates.io-index)" = "e5422a1ee1bc57cc47ae717b0137314258138f38fd5f3cea083f43a9725383a0"
 "checksum precomputed-hash 0.1.1 (registry+https://github.com/rust-lang/crates.io-index)" = "925383efa346730478fb4838dbe9137d2a47675ad789c546d150a6e1dd4ab31c"
 "checksum proc-macro2 0.3.5 (registry+https://github.com/rust-lang/crates.io-index)" = "77997c53ae6edd6d187fec07ec41b207063b5ee6f33680e9fa86d405cdd313d4"
 "checksum proc-macro2 0.4.24 (registry+https://github.com/rust-lang/crates.io-index)" = "77619697826f31a02ae974457af0b29b723e5619e113e9397b8b82c6bd253f09"
 "checksum procedural-masquerade 0.1.1 (registry+https://github.com/rust-lang/crates.io-index)" = "9f566249236c6ca4340f7ca78968271f0ed2b0f234007a61b66f9ecd0af09260"
 "checksum quick-error 1.2.1 (registry+https://github.com/rust-lang/crates.io-index)" = "eda5fe9b71976e62bc81b781206aaa076401769b2143379d3eb2118388babac4"
 "checksum quote 0.5.2 (registry+https://github.com/rust-lang/crates.io-index)" = "9949cfe66888ffe1d53e6ec9d9f3b70714083854be20fd5e271b232a017401e8"
 "checksum quote 0.6.10 (registry+https://github.com/rust-lang/crates.io-index)" = "53fa22a1994bd0f9372d7a816207d8a2677ad0325b073f5c5332760f0fb62b5c"
--- a/gfx/wr/Cargo.lock
+++ b/gfx/wr/Cargo.lock
@@ -1042,17 +1042,17 @@ source = "registry+https://github.com/ru
 
 [[package]]
 name = "pkg-config"
 version = "0.3.11"
 source = "registry+https://github.com/rust-lang/crates.io-index"
 
 [[package]]
 name = "plane-split"
-version = "0.13.4"
+version = "0.13.6"
 source = "registry+https://github.com/rust-lang/crates.io-index"
 dependencies = [
  "binary-space-partition 0.1.2 (registry+https://github.com/rust-lang/crates.io-index)",
  "euclid 0.19.4 (registry+https://github.com/rust-lang/crates.io-index)",
  "log 0.4.1 (registry+https://github.com/rust-lang/crates.io-index)",
  "num-traits 0.2.4 (registry+https://github.com/rust-lang/crates.io-index)",
 ]
 
@@ -1616,17 +1616,17 @@ dependencies = [
  "log 0.4.1 (registry+https://github.com/rust-lang/crates.io-index)",
  "malloc_size_of_derive 0.1.0 (registry+https://github.com/rust-lang/crates.io-index)",
  "mozangle 0.1.6 (registry+https://github.com/rust-lang/crates.io-index)",
  "num-traits 0.2.4 (registry+https://github.com/rust-lang/crates.io-index)",
  "pathfinder_font_renderer 0.5.0 (git+https://github.com/pcwalton/pathfinder?branch=webrender)",
  "pathfinder_gfx_utils 0.2.0 (git+https://github.com/pcwalton/pathfinder?branch=webrender)",
  "pathfinder_partitioner 0.2.0 (git+https://github.com/pcwalton/pathfinder?branch=webrender)",
  "pathfinder_path_utils 0.2.0 (git+https://github.com/pcwalton/pathfinder?branch=webrender)",
- "plane-split 0.13.4 (registry+https://github.com/rust-lang/crates.io-index)",
+ "plane-split 0.13.6 (registry+https://github.com/rust-lang/crates.io-index)",
  "png 0.14.0 (registry+https://github.com/rust-lang/crates.io-index)",
  "rand 0.4.2 (registry+https://github.com/rust-lang/crates.io-index)",
  "rayon 1.0.1 (registry+https://github.com/rust-lang/crates.io-index)",
  "ron 0.1.7 (registry+https://github.com/rust-lang/crates.io-index)",
  "serde 1.0.80 (registry+https://github.com/rust-lang/crates.io-index)",
  "serde_json 1.0.17 (registry+https://github.com/rust-lang/crates.io-index)",
  "sha2 0.8.0 (registry+https://github.com/rust-lang/crates.io-index)",
  "smallvec 0.6.3 (registry+https://github.com/rust-lang/crates.io-index)",
@@ -1960,17 +1960,17 @@ dependencies = [
 "checksum parking_lot 0.6.3 (registry+https://github.com/rust-lang/crates.io-index)" = "69376b761943787ebd5cc85a5bc95958651a22609c5c1c2b65de21786baec72b"
 "checksum parking_lot_core 0.2.14 (registry+https://github.com/rust-lang/crates.io-index)" = "4db1a8ccf734a7bce794cc19b3df06ed87ab2f3907036b693c68f56b4d4537fa"
 "checksum pathfinder_font_renderer 0.5.0 (git+https://github.com/pcwalton/pathfinder?branch=webrender)" = "<none>"
 "checksum pathfinder_gfx_utils 0.2.0 (git+https://github.com/pcwalton/pathfinder?branch=webrender)" = "<none>"
 "checksum pathfinder_partitioner 0.2.0 (git+https://github.com/pcwalton/pathfinder?branch=webrender)" = "<none>"
 "checksum pathfinder_path_utils 0.2.0 (git+https://github.com/pcwalton/pathfinder?branch=webrender)" = "<none>"
 "checksum percent-encoding 1.0.1 (registry+https://github.com/rust-lang/crates.io-index)" = "31010dd2e1ac33d5b46a5b413495239882813e0369f8ed8a5e266f173602f831"
 "checksum pkg-config 0.3.11 (registry+https://github.com/rust-lang/crates.io-index)" = "110d5ee3593dbb73f56294327fe5668bcc997897097cbc76b51e7aed3f52452f"
-"checksum plane-split 0.13.4 (registry+https://github.com/rust-lang/crates.io-index)" = "69f5ea52d7bf50ff02342f5af8527c81030bac5545e92eeeb4a2dfd7bfd2ef69"
+"checksum plane-split 0.13.6 (registry+https://github.com/rust-lang/crates.io-index)" = "b84b8cf2daa6a829b3e756fb75e0eab8e0d963754de9bfc83a4373a47121323a"
 "checksum png 0.14.0 (registry+https://github.com/rust-lang/crates.io-index)" = "9adebf7fb91ccf5eac9da1a8e00e83cb8ae882c3e8d8e4ad59da73cb8c82a2c9"
 "checksum proc-macro2 0.4.25 (registry+https://github.com/rust-lang/crates.io-index)" = "d3797b7142c9aa74954e351fc089bbee7958cebbff6bf2815e7ffff0b19f547d"
 "checksum quick-error 1.2.1 (registry+https://github.com/rust-lang/crates.io-index)" = "eda5fe9b71976e62bc81b781206aaa076401769b2143379d3eb2118388babac4"
 "checksum quote 0.6.3 (registry+https://github.com/rust-lang/crates.io-index)" = "e44651a0dc4cdd99f71c83b561e221f714912d11af1a4dff0631f923d53af035"
 "checksum rand 0.3.22 (registry+https://github.com/rust-lang/crates.io-index)" = "15a732abf9d20f0ad8eeb6f909bf6868722d9a06e1e50802b6a70351f40b4eb1"
 "checksum rand 0.4.2 (registry+https://github.com/rust-lang/crates.io-index)" = "eba5f8cb59cc50ed56be8880a5c7b496bfd9bd26394e176bc67884094145c2c5"
 "checksum rand 0.5.5 (registry+https://github.com/rust-lang/crates.io-index)" = "e464cd887e869cddcae8792a4ee31d23c7edd516700695608f5b98c67ee0131c"
 "checksum rand_core 0.2.1 (registry+https://github.com/rust-lang/crates.io-index)" = "edecf0f94da5551fc9b492093e30b041a891657db7940ee221f9d2f66e82eef2"
--- a/third_party/rust/plane-split/.cargo-checksum.json
+++ b/third_party/rust/plane-split/.cargo-checksum.json
@@ -1,1 +1,1 @@
-{"files":{"Cargo.toml":"b91e34b32c5ace1a51d7d4fd1cc1c18982e85017caaf943aadbf50b1d9230286","LICENSE":"b946744aeda89b467929585fe8eeb5461847695220c1b168fb375d8abd4ea3d0","README.md":"a65ed5c817c867fe23bc2029f34baea4a645a07dd5d101a0027e796d2923be58","benches/split.rs":"632a011dfc6d8235dea853785061b7bbfe0362eb85b91b3b01fbf77a7f1c7f26","src/bsp.rs":"451d2fffdb558e85c595cfeb0ab721a99a20386551620b46261c80b7d262b7b1","src/clip.rs":"a635bda3de37a133d78183953e0eec6571ef97782582bd6abf339c8b4ff19ae4","src/lib.rs":"89dfb8415217863a303c40346395ad327fcc044f8c6cb5236a3359a44a15281c","src/polygon.rs":"31ba899f7e10082644b95fff7527b43b2786720d16fc2d4c225bc7b63ada75ee","tests/clip.rs":"3335364fd6849697d3919084be5dce6c49acb31d8c53adc93a4cd05ee2ea93a9","tests/main.rs":"86dd9b91db2a5c28451164b14ca5179f2c08598562d04ee52f578a17640b134f","tests/split.rs":"87b539bf4bb699d428108f583ebd420fcd2d40ae0266a0b358a5f8b8d88003b9"},"package":"69f5ea52d7bf50ff02342f5af8527c81030bac5545e92eeeb4a2dfd7bfd2ef69"}
\ No newline at end of file
+{"files":{"Cargo.toml":"b9eb30cfd45bebc30ac709d34e029f2a1efee60f3c88cb4fc59354cd63ef7420","LICENSE":"b946744aeda89b467929585fe8eeb5461847695220c1b168fb375d8abd4ea3d0","README.md":"a65ed5c817c867fe23bc2029f34baea4a645a07dd5d101a0027e796d2923be58","benches/split.rs":"632a011dfc6d8235dea853785061b7bbfe0362eb85b91b3b01fbf77a7f1c7f26","src/bsp.rs":"2ccdca9bfc7d9a52621fcf91c441e924eb2068291b48daa8235ec000932a7790","src/clip.rs":"b58bb753b85b822eee2a0a88ea4eb5dff6a69276168ca61202486a6fb95eb95e","src/lib.rs":"57a6c885819b18ead087968937017b6330378bdcc10f285052c9d76e7a1b2226","src/polygon.rs":"133922c90751a8c08e4b5b0529ab3000b65e4a25d4e18cfe119b5e3104411269","tests/clip.rs":"3335364fd6849697d3919084be5dce6c49acb31d8c53adc93a4cd05ee2ea93a9","tests/main.rs":"7c50a23d32eb8b0742bd533e98ba95c96110c4773b27ae0c40121c347feb9325","tests/split.rs":"88fe8192f8e0d03ac2b4b526c377ceeccbee4e3c35f4fa00be160d1402af09a2"},"package":"b84b8cf2daa6a829b3e756fb75e0eab8e0d963754de9bfc83a4373a47121323a"}
\ No newline at end of file
--- a/third_party/rust/plane-split/Cargo.toml
+++ b/third_party/rust/plane-split/Cargo.toml
@@ -7,17 +7,17 @@
 #
 # If you believe there's an error in this file please file an
 # issue against the rust-lang/cargo repository. If you're
 # editing this file be aware that the upstream Cargo.toml
 # will likely look very different (and much more reasonable)
 
 [package]
 name = "plane-split"
-version = "0.13.4"
+version = "0.13.6"
 authors = ["Dzmitry Malyshau <kvark@mozilla.com>"]
 description = "Plane splitting"
 documentation = "https://docs.rs/plane-split"
 keywords = ["geometry", "math"]
 license = "MPL-2.0"
 repository = "https://github.com/servo/plane-split"
 [dependencies.binary-space-partition]
 version = "0.1.2"
--- a/third_party/rust/plane-split/src/bsp.rs
+++ b/third_party/rust/plane-split/src/bsp.rs
@@ -17,25 +17,24 @@ impl<T, U> BspPlane for Polygon<T, U> wh
     U: fmt::Debug,
 {
     fn cut(&self, mut poly: Self) -> PlaneCut<Self> {
         debug!("\tCutting anchor {} by {}", poly.anchor, self.anchor);
         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 if self.plane.normal.dot(poly.plane.normal) > T::zero() => {
-                debug!("\t\tNormals roughly point to the same direction");
-                (Intersection::Coplanar, self.plane.offset - poly.plane.offset)
-            }
             None => {
-                debug!("\t\tNormals roughly point to opposite directions");
-                (Intersection::Coplanar, self.plane.offset + poly.plane.offset)
+                let ndot = self.plane.normal.dot(poly.plane.normal);
+                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())
             }
         };
@@ -59,17 +58,17 @@ impl<T, U> BspPlane for Polygon<T, U> wh
                     PlaneCut::Cut {
                         front: vec![],
                         back: vec![poly],
                     }
                 }
             }
             Intersection::Inside(line) => {
                 debug!("\t\tCut across {:?}", line);
-                let (res_add1, res_add2) = poly.split(&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())
                 {
--- a/third_party/rust/plane-split/src/clip.rs
+++ b/third_party/rust/plane-split/src/clip.rs
@@ -100,17 +100,17 @@ impl<
         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(..) {
                 if let Intersection::Inside(line) = poly.intersect_plane(clip) {
-                    let (res1, res2) = poly.split(&line);
+                    let (res1, res2) = poly.split_with_normal(&line, &clip.normal);
                     self.results.extend(
                         res1
                             .into_iter()
                             .chain(res2)
                             .filter(|p| clip.signed_distance_sum_to(p) > T::zero())
                     );
                 }
                 // Note: if the intersection has happened, the `poly` will now
--- a/third_party/rust/plane-split/src/lib.rs
+++ b/third_party/rust/plane-split/src/lib.rs
@@ -62,16 +62,40 @@ impl<T, U> Line<T, U> where
         is_zero(self.dir.dot(self.dir) - T::one())
     }
     /// Check if two lines match each other.
     pub fn matches(&self, other: &Self) -> bool {
         let diff = self.origin - other.origin;
         is_zero_vec(self.dir.cross(other.dir)) &&
         is_zero_vec(self.dir.cross(diff))
     }
+
+    /// Intersect an edge given by the end points.
+    /// Returns the fraction of the edge where the intersection occurs.
+    fn intersect_edge(
+        &self,
+        edge: ops::Range<TypedPoint3D<T, U>>,
+    ) -> Option<T>
+    where T: ops::Div<T, Output=T>
+    {
+        let edge_vec = edge.end - edge.start;
+        let origin_vec = self.origin - edge.start;
+        // edge.start + edge_vec * t = r + k * d
+        // (edge.start, d) + t * (edge_vec, d) - (r, d) = k
+        // edge.start + t * edge_vec = r + t * (edge_vec, d) * d + (start-r, d) * d
+        // t * (edge_vec - (edge_vec, d)*d) = origin_vec - (origin_vec, d) * d
+        let pr = origin_vec - self.dir * self.dir.dot(origin_vec);
+        let pb = edge_vec - self.dir * self.dir.dot(edge_vec);
+        let denom = pb.dot(pb);
+        if denom.approx_eq(&T::zero()) {
+            None
+        } else {
+            Some(pr.dot(pb) / denom)
+        }
+    }
 }
 
 
 /// An infinite plane in 3D space, defined by equation:
 /// dot(v, normal) + offset = 0
 /// When used for plane splitting, it's defining a hemisphere
 /// with equation "dot(v, normal) + offset > 0".
 #[derive(Debug, PartialEq)]
--- a/third_party/rust/plane-split/src/polygon.rs
+++ b/third_party/rust/plane-split/src/polygon.rs
@@ -1,16 +1,16 @@
 use {Line, Plane, is_zero};
 
 use euclid::{Point2D, TypedTransform3D, TypedPoint3D, TypedVector3D, TypedRect};
 use euclid::approxeq::ApproxEq;
 use euclid::Trig;
 use num_traits::{Float, One, Zero};
 
-use std::{fmt, mem, ops};
+use std::{fmt, iter, mem, ops};
 
 
 /// The projection of a `Polygon` on a line.
 pub struct LineProjection<T> {
     /// Projected value of each point in the polygon.
     pub markers: [T; 4],
 }
 
@@ -356,18 +356,114 @@ impl<T, U> Polygon<T, U> where
             }
             None => {
                 debug!("\t\tCoplanar");
                 Intersection::Coplanar
             }
         }
     }
 
-    /// Split the polygon along the specified `Line`. Will do nothing if the line
-    /// doesn't belong to the polygon plane.
+    fn split_impl(
+        &mut self,
+        first: (usize, TypedPoint3D<T, U>),
+        second: (usize, TypedPoint3D<T, U>),
+    ) -> (Option<Self>, Option<Self>) {
+        //TODO: can be optimized for when the polygon has a redundant 4th vertex
+        //TODO: can be simplified greatly if only working with triangles
+        debug!("\t\tReached complex case [{}, {}]", first.0, second.0);
+        let base = first.0;
+        assert!(base < self.points.len());
+        match second.0 - first.0 {
+            1 => {
+                // rect between the cut at the diagonal
+                let other1 = Polygon {
+                    points: [
+                        first.1,
+                        second.1,
+                        self.points[(base + 2) & 3],
+                        self.points[base],
+                    ],
+                    .. self.clone()
+                };
+                // triangle on the near side of the diagonal
+                let other2 = Polygon {
+                    points: [
+                        self.points[(base + 2) & 3],
+                        self.points[(base + 3) & 3],
+                        self.points[base],
+                        self.points[base],
+                    ],
+                    .. self.clone()
+                };
+                // triangle being cut out
+                self.points = [
+                    first.1,
+                    self.points[(base + 1) & 3],
+                    second.1,
+                    second.1,
+                ];
+                (Some(other1), Some(other2))
+            }
+            2 => {
+                // rect on the far side
+                let other = Polygon {
+                    points: [
+                        first.1,
+                        self.points[(base + 1) & 3],
+                        self.points[(base + 2) & 3],
+                        second.1,
+                    ],
+                    .. self.clone()
+                };
+                // rect on the near side
+                self.points = [
+                    first.1,
+                    second.1,
+                    self.points[(base + 3) & 3],
+                    self.points[base],
+                ];
+                (Some(other), None)
+            }
+            3 => {
+                // rect between the cut at the diagonal
+                let other1 = Polygon {
+                    points: [
+                        first.1,
+                        self.points[(base + 1) & 3],
+                        self.points[(base + 3) & 3],
+                        second.1,
+                    ],
+                    .. self.clone()
+                };
+                // triangle on the far side of the diagonal
+                let other2 = Polygon {
+                    points: [
+                        self.points[(base + 1) & 3],
+                        self.points[(base + 2) & 3],
+                        self.points[(base + 3) & 3],
+                        self.points[(base + 3) & 3],
+                    ],
+                    .. self.clone()
+                };
+                // triangle being cut out
+                self.points = [
+                    first.1,
+                    second.1,
+                    self.points[base],
+                    self.points[base],
+                ];
+                (Some(other1), Some(other2))
+            }
+            _ => panic!("Unexpected indices {} {}", first.0, second.0),
+        }
+    }
+
+    /// Split the polygon along the specified `Line`.
+    /// Will do nothing if the line doesn't belong to the polygon plane.
+    #[deprecated(note = "Use split_with_normal instead")]
     pub fn split(&mut self, line: &Line<T, U>) -> (Option<Self>, Option<Self>) {
         debug!("\tSplitting");
         // check if the cut is within the polygon plane first
         if !is_zero(self.plane.normal.dot(line.dir)) ||
            !is_zero(self.plane.signed_distance_to(&line.origin)) {
             debug!("\t\tDoes not belong to the plane, normal dot={:?}, origin distance={:?}",
                 self.plane.normal.dot(line.dir), self.plane.signed_distance_to(&line.origin));
             return (None, None)
@@ -376,90 +472,80 @@ impl<T, U> Polygon<T, U> where
         let mut cuts = [None; 4];
         for ((&b, &a), cut) in self.points
             .iter()
             .cycle()
             .skip(1)
             .zip(self.points.iter())
             .zip(cuts.iter_mut())
         {
-            // intersecting line segment [a, b] with `line`
-            // a + (b-a) * t = r + k * d
-            // (a, d) + t * (b-a, d) - (r, d) = k
-            // a + t * (b-a) = r + t * (b-a, d) * d + (a-r, d) * d
-            // t * ((b-a) - (b-a, d)*d) = (r-a) - (r-a, d) * d
-            let pr = line.origin - a - line.dir * line.dir.dot(line.origin - a);
-            let pb = b - a - line.dir * line.dir.dot(b - a);
-            let denom = pb.dot(pb);
-            if !denom.approx_eq(&T::zero()) {
-                let t = pr.dot(pb) / denom;
-                if t > T::approx_epsilon() && t < T::one() - T::approx_epsilon() {
+            if let Some(t) = line.intersect_edge(a .. b) {
+                if t >= T::zero() && t < T::one() {
                     *cut = Some(a + (b - a) * t);
                 }
             }
         }
 
         let first = match cuts.iter().position(|c| c.is_some()) {
             Some(pos) => pos,
             None => return (None, None),
         };
         let second = match cuts[first+1 ..].iter().position(|c| c.is_some()) {
             Some(pos) => first + 1 + pos,
             None => return (None, None),
         };
-        debug!("\t\tReached complex case [{}, {}]", first, second);
-        //TODO: can be optimized for when the polygon has a redundant 4th vertex
-        //TODO: can be simplified greatly if only working with triangles
-        let (a, b) = (cuts[first].unwrap(), cuts[second].unwrap());
-        match second-first {
-            2 => {
-                let mut other_points = self.points;
-                other_points[first] = a;
-                other_points[(first+3) % 4] = b;
-                self.points[first+1] = a;
-                self.points[first+2] = b;
-                let poly = Polygon {
-                    points: other_points,
-                    .. self.clone()
-                };
-                (Some(poly), None)
+        self.split_impl(
+            (first, cuts[first].unwrap()),
+            (second, cuts[second].unwrap()),
+        )
+    }
+
+    /// Split the polygon along the specified `Line`, with a normal to the split line provided.
+    /// This is useful when called by the plane splitter, since the other plane's normal
+    /// forms the side direction here, and figuring out the actual line of split isn't needed.
+    /// Will do nothing if the line doesn't belong to the polygon plane.
+    pub fn split_with_normal(
+        &mut self, line: &Line<T, U>, normal: &TypedVector3D<T, U>,
+    ) -> (Option<Self>, Option<Self>) {
+        debug!("\tSplitting with normal");
+        // figure out which side of the split does each point belong to
+        let mut sides = [T::zero(); 4];
+        let (mut cut_positive, mut cut_negative) = (None, None);
+        for (side, point) in sides.iter_mut().zip(&self.points) {
+            *side = normal.dot(*point - line.origin);
+        }
+        // compute the edge intersection points
+        for (i, ((&side1, point1), (&side0, point0))) in sides[1..]
+            .iter()
+            .chain(iter::once(&sides[0]))
+            .zip(self.points[1..].iter().chain(iter::once(&self.points[0])))
+            .zip(sides.iter().zip(&self.points))
+            .enumerate()
+        {
+            // figure out if an edge between 0 and 1 needs to be cut
+            let cut = if side0 < T::zero() && side1 >= T::zero() {
+                &mut cut_positive
+            } else if side0 > T::zero() && side1 <= T::zero() {
+                &mut cut_negative
+            } else {
+                continue;
+            };
+            // compute the cut point
+            if let Some(t) = line.intersect_edge(*point0 .. *point1) {
+                //Note: it is expected that T is in [0, 1] range, but it can go outside of it
+                // by an epsilon due to computation inefficiencies, and it's fine.
+                debug_assert!(t >= -T::epsilon() && t <= T::one() + T::epsilon());
+                debug_assert_eq!(*cut, None);
+                let point = *point0 + (*point1 - *point0) * t;
+                *cut = Some((i, point));
             }
-            3 => {
-                let xpoints = [
-                    self.points[first+1],
-                    self.points[first+2],
-                    self.points[first+3],
-                    b];
-                let ypoints = [a, self.points[first+1], b, b];
-                self.points = [self.points[first], a, b, b];
-                let poly1 = Polygon {
-                    points: xpoints,
-                    .. self.clone()
-                };
-                let poly2 = Polygon {
-                    points: ypoints,
-                    .. self.clone()
-                };
-                (Some(poly1), Some(poly2))
+        }
+        // form new polygons
+        if let (Some(first), Some(mut second)) = (cut_positive, cut_negative) {
+            if second.0 < first.0 {
+                second.0 += 4;
             }
-            1 => {
-                let xpoints = [
-                    b,
-                    self.points[(first+2) % 4],
-                    self.points[(first+3) % 4],
-                    self.points[first]
-                    ];
-                let ypoints = [self.points[first], a, b, b];
-                self.points = [a, self.points[first+1], b, b];
-                let poly1 = Polygon {
-                    points: xpoints,
-                    .. self.clone()
-                };
-                let poly2 = Polygon {
-                    points: ypoints,
-                    .. self.clone()
-                };
-                (Some(poly1), Some(poly2))
-            }
-            _ => panic!("Unexpected indices {} {}", first, second),
+            self.split_impl(first, second)
+        } else {
+            (None, None)
         }
     }
 }
--- a/third_party/rust/plane-split/tests/main.rs
+++ b/third_party/rust/plane-split/tests/main.rs
@@ -213,20 +213,26 @@ fn intersect() {
         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<f32, ()>, extra_count: u8, line: Line<f32, ()>) {
+fn test_cut(
+    poly_base: &Polygon<f32, ()>,
+    extra_count: u8,
+    line: Line<f32, ()>,
+) {
     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(&line);
+    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));
@@ -273,16 +279,22 @@ fn split() {
         dir: vec3(0.5f32.sqrt(), 0.0, 0.5f32.sqrt()),
     });
 
     // complex cut (diff=3)
     test_cut(&poly, 2, Line {
         origin: point3(0.5, 1.0, 0.0),
         dir: vec3(-0.5f32.sqrt(), 0.0, 0.5f32.sqrt()),
     });
+
+    // perfect diagonal
+    test_cut(&poly, 1, Line {
+        origin: point3(0.0, 1.0, 0.0),
+        dir: vec3(0.5f32.sqrt(), 0.0, 0.5f32.sqrt()),
+    });
 }
 
 #[test]
 fn plane_unnormalized() {
     let zero_vec = vec3(0.0000001, 0.0, 0.0);
     let mut plane: Result<Option<Plane<f32, ()>>, _> = Plane::from_unnormalized(zero_vec, 1.0);
     assert_eq!(plane, Ok(None));
     plane = Plane::from_unnormalized(zero_vec, 0.0);
--- a/third_party/rust/plane-split/tests/split.rs
+++ b/third_party/rust/plane-split/tests/split.rs
@@ -90,30 +90,42 @@ fn external_bsp() {
     sort_external(&mut BspSplitter::new());
 }
 
 #[test]
 fn test_cut() {
     let rect: TypedRect<f32, ()> = 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;
+    }
+    match poly.cut(poly2.clone()) {
+        PlaneCut::Sibling(p) => assert_eq!(p, poly2),
+        PlaneCut::Cut { .. } => panic!("wrong cut!"),
+    }
+    // test robustness for normal
     poly2.plane.normal.z += 0.00000001;
     match poly.cut(poly2.clone()) {
         PlaneCut::Sibling(p) => assert_eq!(p, poly2),
         PlaneCut::Cut { .. } => panic!("wrong cut!"),
     }
+    // test opposite normal handling
     poly2.plane.normal *= -1.0;
     match poly.cut(poly2.clone()) {
         PlaneCut::Sibling(p) => assert_eq!(p, poly2),
         PlaneCut::Cut { .. } => panic!("wrong cut!"),
     }
 
+    // test grouping front
     poly2.plane.offset += 0.1;
     match poly.cut(poly2.clone()) {
         PlaneCut::Cut { ref front, ref back } => assert_eq!((front.len(), back.len()), (1, 0)),
         PlaneCut::Sibling(_) => panic!("wrong sibling!"),
     }
+    // test grouping back
     poly2.plane.normal *= -1.0;
     match poly.cut(poly2.clone()) {
         PlaneCut::Cut { ref front, ref back } => assert_eq!((front.len(), back.len()), (0, 1)),
         PlaneCut::Sibling(_) => panic!("wrong sibling!"),
     }
 }