Bug 1525087 - Plane split dependency update to 0.13.5 r=kats a=lizzard
authorDzmitry Malyshau <dmalyshau@mozilla.com>
Thu, 14 Feb 2019 14:05:55 +0100
changeset 515944 99fa26897e4189c491946dfb2d667c8bda522b89
parent 515943 d6e47c340828f443a824ec136d52d6d21d6e1d99
child 515945 720c87f798e304851f72f5ac6fc90d21d1239a38
push id1953
push userffxbld-merge
push dateMon, 11 Mar 2019 12:10:20 +0000
treeherdermozilla-release@9c35dcbaa899 [default view] [failures only]
perfherder[talos] [build metrics] [platform microbench] (compared to previous push)
reviewerskats, lizzard
bugs1525087
milestone66.0
Bug 1525087 - Plane split dependency update to 0.13.5 r=kats a=lizzard
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
@@ -1939,17 +1939,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.3"
+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)",
 ]
 
@@ -3025,17 +3025,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.3 (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",
@@ -3394,17 +3394,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.3 (registry+https://github.com/rust-lang/crates.io-index)" = "9b1d9a84aa3bbc2dafd06856bdb1dc333eb1d442ad8987b9d596c7344b3ed969"
+"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
@@ -1040,17 +1040,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.3"
+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)",
 ]
 
@@ -1614,17 +1614,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.3 (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)",
@@ -1958,17 +1958,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.3 (registry+https://github.com/rust-lang/crates.io-index)" = "9b1d9a84aa3bbc2dafd06856bdb1dc333eb1d442ad8987b9d596c7344b3ed969"
+"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":"7b16d31dbd148b3dae6e90b30d4ea17798e13f5256647da48e96f4e678dbd4fe","LICENSE":"b946744aeda89b467929585fe8eeb5461847695220c1b168fb375d8abd4ea3d0","README.md":"a65ed5c817c867fe23bc2029f34baea4a645a07dd5d101a0027e796d2923be58","benches/split.rs":"632a011dfc6d8235dea853785061b7bbfe0362eb85b91b3b01fbf77a7f1c7f26","src/bsp.rs":"5ee2a20ce632d6c5283787f908fa3eac856ec55e4f1ed6e615cecb6fe041ed21","src/clip.rs":"838cee6106d240581d1cfcba5d47b67f99a1360748ce7c56531dc4582121fc34","src/lib.rs":"a9ce93011a0b0702a1df2a342aeeb9982a3c8a819b20fefa284686ee0fa04d08","src/polygon.rs":"31ba899f7e10082644b95fff7527b43b2786720d16fc2d4c225bc7b63ada75ee","tests/clip.rs":"3335364fd6849697d3919084be5dce6c49acb31d8c53adc93a4cd05ee2ea93a9","tests/main.rs":"86dd9b91db2a5c28451164b14ca5179f2c08598562d04ee52f578a17640b134f","tests/split.rs":"7da8d6f7cce4643ae9c5ce4917aa11aef503c4267dfaeae7b2a4b9bc813cb095"},"package":"9b1d9a84aa3bbc2dafd06856bdb1dc333eb1d442ad8987b9d596c7344b3ed969"}
\ 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.3"
+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
@@ -8,34 +8,40 @@ use num_traits::{Float, One, Zero};
 
 use std::{fmt, iter, ops};
 
 
 impl<T, U> BspPlane for Polygon<T, U> 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,
+        Zero + Float,
     U: fmt::Debug,
 {
     fn cut(&self, mut poly: Self) -> PlaneCut<Self> {
         debug!("\tCutting anchor {} by {}", poly.anchor, self.anchor);
         trace!("\t\tbase {:?}", self.plane);
 
-        let ndot = self.plane.normal.dot(poly.plane.normal);
-        let (intersection, dist) = if ndot.approx_eq(&T::one()) {
-            debug!("\t\tNormals roughly point to the same direction");
-            (Intersection::Coplanar, self.plane.offset - poly.plane.offset)
-        } else if ndot.approx_eq(&-T::one()) {
-            debug!("\t\tNormals roughly point to opposite directions");
-            (Intersection::Coplanar, self.plane.offset + poly.plane.offset)
-        } else {
-            let is = self.intersect(&poly);
-            let dist = self.plane.signed_distance_sum_to(&poly);
-            (is, dist)
+        //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);
+                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) => {
                 debug!("\t\tCoplanar at {:?}", dist);
@@ -52,30 +58,31 @@ 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())
                 {
-                    if self.plane.signed_distance_sum_to(&sub) > T::zero() {
-                        trace!("\t\t\tfront: {:?}", sub);
+                    let dist = self.plane.signed_distance_sum_to(&sub);
+                    if dist > T::zero() {
+                        trace!("\t\t\tdist {:?} -> front: {:?}", dist, sub);
                         front.push(sub)
                     } else {
-                        trace!("\t\t\tback: {:?}", sub);
+                        trace!("\t\t\tdist {:?} -> back: {:?}", dist, sub);
                         back.push(sub)
                     }
                 }
 
                 PlaneCut::Cut {
                     front,
                     back,
                 }
--- a/third_party/rust/plane-split/src/clip.rs
+++ b/third_party/rust/plane-split/src/clip.rs
@@ -90,26 +90,27 @@ impl<
     /// 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>) -> &[Polygon<T, U>] {
+        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(..) {
                 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)]
@@ -157,38 +181,38 @@ impl<
     /// considered an intersection.
     pub fn are_outside(&self, points: &[TypedPoint3D<T, U>]) -> bool {
         let d0 = self.signed_distance_to(&points[0]);
         points[1..]
             .iter()
             .all(|p| self.signed_distance_to(p) * d0 > T::zero())
     }
 
+    //TODO(breaking): turn this into Result<Line, DotProduct>
     /// Compute the line of intersection with another plane.
     pub fn intersect(&self, other: &Self) -> Option<Line<T, U>> {
-        let cross_dir = self.normal.cross(other.normal);
-        if cross_dir.dot(cross_dir) < T::approx_epsilon() {
-            return None
-        }
-
         // compute any point on the intersection between planes
         // (n1, v) + d1 = 0
         // (n2, v) + d2 = 0
         // v = a*n1/w + b*n2/w; w = (n1, n2)
         // v = (d2*w - d1) / (1 - w*w) * n1 - (d2 - d1*w) / (1 - w*w) * n2
         let w = self.normal.dot(other.normal);
         let divisor = T::one() - w * w;
         if divisor < T::approx_epsilon() {
             return None
         }
         let factor = T::one() / divisor;
         let origin = TypedPoint3D::origin() +
             self.normal * ((other.offset * w - self.offset) * factor) -
             other.normal* ((other.offset - self.offset * w) * factor);
 
+        let cross_dir = self.normal.cross(other.normal);
+        // note: the cross product isn't too close to zero
+        // due to the previous check
+
         Some(Line {
             origin,
             dir: cross_dir.normalize(),
         })
     }
 }
 
 
--- 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
@@ -55,43 +55,77 @@ fn sort_trivial(splitter: &mut Splitter<
         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));
-    assert_eq!(anchors1, anchors2); //make sure Z is sorted backwards
+    //make sure Z is sorted backwards
+    assert_eq!(anchors1, anchors2);
+}
+
+fn sort_external(splitter: &mut Splitter<f32, ()>) {
+    let rect0: TypedRect<f32, ()> = rect(-10.0, -10.0, 20.0, 20.0);
+    let poly0 = Polygon::from_rect(rect0, 0);
+    let poly1 = {
+        let transform0: TypedTransform3D<f32, (), ()> = TypedTransform3D::create_rotation(1.0, 0.0, 0.0, Angle::radians(2.0 * FRAC_PI_4));
+        let transform1: TypedTransform3D<f32, (), ()> = TypedTransform3D::create_translation(0.0, 100.0, 0.0);
+        Polygon::from_transformed_rect(rect0, transform1.pre_mul(&transform0), 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() {
     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!"),
     }
 }