Bug 1523347 - Plane-split update to 0.13.4 r=kats
authorDzmitry Malyshau <dmalyshau@mozilla.com>
Sat, 02 Feb 2019 04:11:25 +0000
changeset 456536 cb5ed33ae30da0deceb984932ec69a1a02b0e88b
parent 456535 5473faa3c4b031839c7a91507665f98a68880188
child 456537 d8cebb3b46cfd216ab60e58588e585f28750a5f3
child 456538 de93460e55c469f93834a87d5820d9d94c3d386e
push id111656
push userdvarga@mozilla.com
push dateSat, 02 Feb 2019 09:51:54 +0000
treeherdermozilla-inbound@d8cebb3b46cf [default view] [failures only]
perfherder[talos] [build metrics] [platform microbench] (compared to previous push)
reviewerskats
bugs1523347
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 1523347 - Plane-split update to 0.13.4 r=kats new version includes necessary quality fixes for plane-splitting Differential Revision: https://phabricator.services.mozilla.com/D18480
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/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.4"
 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)",
 ]
 
@@ -2067,17 +2067,17 @@ dependencies = [
 name = "rayon-core"
 version = "1.4.0"
 source = "registry+https://github.com/rust-lang/crates.io-index"
 dependencies = [
  "crossbeam-deque 0.2.0 (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)",
  "num_cpus 1.7.0 (registry+https://github.com/rust-lang/crates.io-index)",
- "rand 0.3.22 (registry+https://github.com/rust-lang/crates.io-index)",
+ "rand 0.4.3 (registry+https://github.com/rust-lang/crates.io-index)",
 ]
 
 [[package]]
 name = "redox_syscall"
 version = "0.1.32"
 source = "registry+https://github.com/rust-lang/crates.io-index"
 
 [[package]]
@@ -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.4 (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.4 (registry+https://github.com/rust-lang/crates.io-index)" = "69f5ea52d7bf50ff02342f5af8527c81030bac5545e92eeeb4a2dfd7bfd2ef69"
 "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.4"
 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.4 (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.4 (registry+https://github.com/rust-lang/crates.io-index)" = "69f5ea52d7bf50ff02342f5af8527c81030bac5545e92eeeb4a2dfd7bfd2ef69"
 "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":"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
--- 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.4"
 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,41 @@ 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 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)
+            }
+            Some(_) if self.plane.are_outside(&poly.points) => {
+                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);
@@ -61,21 +68,22 @@ impl<T, U> BspPlane for Polygon<T, U> wh
                 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,16 +90,17 @@ 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(..) {
--- a/third_party/rust/plane-split/src/lib.rs
+++ b/third_party/rust/plane-split/src/lib.rs
@@ -157,38 +157,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/tests/split.rs
+++ b/third_party/rust/plane-split/tests/split.rs
@@ -55,25 +55,47 @@ 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);
     poly2.plane.normal.z += 0.00000001;
     match poly.cut(poly2.clone()) {
         PlaneCut::Sibling(p) => assert_eq!(p, poly2),
         PlaneCut::Cut { .. } => panic!("wrong cut!"),