Adding upstream version 115.7.0esr.upstream/115.7.0esr

Signed-off-by: Daniel Baumann <daniel.baumann@progress-linux.org>

13 files changed, 2283 insertions, 0 deletions

diff --git a/third_party/rust/plane-split/.cargo-checksum.json b/third_party/rust/plane-split/.cargo-checksum.json
new file mode 100644
index 0000000000..bb9ba0d4c9
--- /dev/null
+++ b/third_party/rust/plane-split/.cargo-checksum.json
@@ -0,0 +1 @@
+{"files":{"Cargo.toml":"bf346898b621baab8a7667819a93ec9a31055012518bb8903da85abb1577d1b6","LICENSE":"b946744aeda89b467929585fe8eeb5461847695220c1b168fb375d8abd4ea3d0","README.md":"7d7930c1163595388512c4ca0b674f6755096a05ca226b1033256b46374b88c3","benches/split.rs":"686d3729a939e94cdf4c38fbc4bd52bd92e6487adbaa9cd4a7c57eb649b6f7d8","rustfmt.toml":"e3b0c44298fc1c149afbf4c8996fb92427ae41e4649b934ca495991b7852b855","src/bsp.rs":"7a533feb7e60f376d64a53f9993eafeddce6fe6cfa22182ae0c342675cc576ae","src/clip.rs":"c1d20c0ee8fb324ca540722ca216dd8cb964d326fd1d77455ee1403c6dbb4148","src/lib.rs":"b2b28ebd7ff8157f6b0309da8cb95fa30b5d01f19c675b99ecbe481fc420e328","src/polygon.rs":"f790599d89625813d65d29d632e8871a8dcdd505e25a557f05d07ba0f6c26cd3","tests/clip.rs":"afb2a79edee4d5d986004a46e6e74bf5bd44b914739d7a92cfe57b7112dc9ca3","tests/main.rs":"b10ec5a7e2453095fbd932804e7a69909e1b06a26399932264d40758352ad2d9","tests/split.rs":"5e675c0aefa631d883f972e031bed19793acba9a649a9cd2126220dec400b71c"},"package":"8c1f7d82649829ecdef8e258790b0587acf0a8403f0ce963473d8e918acc1643"}
\ No newline at end of file
diff --git a/third_party/rust/plane-split/Cargo.toml b/third_party/rust/plane-split/Cargo.toml
new file mode 100644
index 0000000000..59b1e2ebe8
--- /dev/null
+++ b/third_party/rust/plane-split/Cargo.toml
@@ -0,0 +1,34 @@
+# THIS FILE IS AUTOMATICALLY GENERATED BY CARGO
+#
+# When uploading crates to the registry Cargo will automatically
+# "normalize" Cargo.toml files for maximal compatibility
+# with all versions of Cargo and also rewrite `path` dependencies
+# to registry (e.g., crates.io) dependencies.
+#
+# If you are reading this file be aware that the original Cargo.toml
+# will likely look very different (and much more reasonable).
+# See Cargo.toml.orig for the original contents.
+
+[package]
+edition = "2018"
+name = "plane-split"
+version = "0.18.0"
+authors = ["Dzmitry Malyshau <kvark@mozilla.com>"]
+description = "Plane splitting"
+documentation = "https://docs.rs/plane-split"
+readme = "README.md"
+keywords = [
+    "geometry",
+    "math",
+]
+license = "MPL-2.0"
+repository = "https://github.com/servo/plane-split"
+
+[dependencies.euclid]
+version = "0.22"
+
+[dependencies.log]
+version = "0.4"
+
+[dependencies.smallvec]
+version = "1.9"
diff --git a/third_party/rust/plane-split/LICENSE b/third_party/rust/plane-split/LICENSE
new file mode 100644
index 0000000000..398385c9fb
--- /dev/null
+++ b/third_party/rust/plane-split/LICENSE
@@ -0,0 +1,374 @@
+ Mozilla Public License Version 2.0
+==================================
+
+1. Definitions
+--------------
+
+1.1. "Contributor"
+means each individual or legal entity that creates, contributes to
+the creation of, or owns Covered Software.
+
+1.2. "Contributor Version"
+means the combination of the Contributions of others (if any) used
+by a Contributor and that particular Contributor's Contribution.
+
+1.3. "Contribution"
+means Covered Software of a particular Contributor.
+
+1.4. "Covered Software"
+means Source Code Form to which the initial Contributor has attached
+the notice in Exhibit A, the Executable Form of such Source Code
+Form, and Modifications of such Source Code Form, in each case
+including portions thereof.
+
+1.5. "Incompatible With Secondary Licenses"
+means
+
+(a) that the initial Contributor has attached the notice described
+in Exhibit B to the Covered Software; or
+
+(b) that the Covered Software was made available under the terms of
+version 1.1 or earlier of the License, but not also under the
+terms of a Secondary License.
+
+1.6. "Executable Form"
+means any form of the work other than Source Code Form.
+
+1.7. "Larger Work"
+means a work that combines Covered Software with other material, in
+a separate file or files, that is not Covered Software.
+
+1.8. "License"
+means this document.
+
+1.9. "Licensable"
+means having the right to grant, to the maximum extent possible,
+whether at the time of the initial grant or subsequently, any and
+all of the rights conveyed by this License.
+
+1.10. "Modifications"
+means any of the following:
+
+(a) any file in Source Code Form that results from an addition to,
+deletion from, or modification of the contents of Covered
+Software; or
+
+(b) any new file in Source Code Form that contains any Covered
+Software.
+
+1.11. "Patent Claims" of a Contributor
+means any patent claim(s), including without limitation, method,
+process, and apparatus claims, in any patent Licensable by such
+Contributor that would be infringed, but for the grant of the
+License, by the making, using, selling, offering for sale, having
+made, import, or transfer of either its Contributions or its
+Contributor Version.
+
+1.12. "Secondary License"
+means either the GNU General Public License, Version 2.0, the GNU
+Lesser General Public License, Version 2.1, the GNU Affero General
+Public License, Version 3.0, or any later versions of those
+licenses.
+
+1.13. "Source Code Form"
+means the form of the work preferred for making modifications.
+
+1.14. "You" (or "Your")
+means an individual or a legal entity exercising rights under this
+License. For legal entities, "You" includes any entity that
+controls, is controlled by, or is under common control with You. For
+purposes of this definition, "control" means (a) the power, direct
+or indirect, to cause the direction or management of such entity,
+whether by contract or otherwise, or (b) ownership of more than
+fifty percent (50%) of the outstanding shares or beneficial
+ownership of such entity.
+
+2. License Grants and Conditions
+--------------------------------
+
+2.1. Grants
+
+Each Contributor hereby grants You a world-wide, royalty-free,
+non-exclusive license:
+
+(a) under intellectual property rights (other than patent or trademark)
+Licensable by such Contributor to use, reproduce, make available,
+modify, display, perform, distribute, and otherwise exploit its
+Contributions, either on an unmodified basis, with Modifications, or
+as part of a Larger Work; and
+
+(b) under Patent Claims of such Contributor to make, use, sell, offer
+for sale, have made, import, and otherwise transfer either its
+Contributions or its Contributor Version.
+
+2.2. Effective Date
+
+The licenses granted in Section 2.1 with respect to any Contribution
+become effective for each Contribution on the date the Contributor first
+distributes such Contribution.
+
+2.3. Limitations on Grant Scope
+
+The licenses granted in this Section 2 are the only rights granted under
+this License. No additional rights or licenses will be implied from the
+distribution or licensing of Covered Software under this License.
+Notwithstanding Section 2.1(b) above, no patent license is granted by a
+Contributor:
+
+(a) for any code that a Contributor has removed from Covered Software;
+or
+
+(b) for infringements caused by: (i) Your and any other third party's
+modifications of Covered Software, or (ii) the combination of its
+Contributions with other software (except as part of its Contributor
+Version); or
+
+(c) under Patent Claims infringed by Covered Software in the absence of
+its Contributions.
+
+This License does not grant any rights in the trademarks, service marks,
+or logos of any Contributor (except as may be necessary to comply with
+the notice requirements in Section 3.4).
+
+2.4. Subsequent Licenses
+
+No Contributor makes additional grants as a result of Your choice to
+distribute the Covered Software under a subsequent version of this
+License (see Section 10.2) or under the terms of a Secondary License (if
+permitted under the terms of Section 3.3).
+
+2.5. Representation
+
+Each Contributor represents that the Contributor believes its
+Contributions are its original creation(s) or it has sufficient rights
+to grant the rights to its Contributions conveyed by this License.
+
+2.6. Fair Use
+
+This License is not intended to limit any rights You have under
+applicable copyright doctrines of fair use, fair dealing, or other
+equivalents.
+
+2.7. Conditions
+
+Sections 3.1, 3.2, 3.3, and 3.4 are conditions of the licenses granted
+in Section 2.1.
+
+3. Responsibilities
+-------------------
+
+3.1. Distribution of Source Form
+
+All distribution of Covered Software in Source Code Form, including any
+Modifications that You create or to which You contribute, must be under
+the terms of this License. You must inform recipients that the Source
+Code Form of the Covered Software is governed by the terms of this
+License, and how they can obtain a copy of this License. You may not
+attempt to alter or restrict the recipients' rights in the Source Code
+Form.
+
+3.2. Distribution of Executable Form
+
+If You distribute Covered Software in Executable Form then:
+
+(a) such Covered Software must also be made available in Source Code
+Form, as described in Section 3.1, and You must inform recipients of
+the Executable Form how they can obtain a copy of such Source Code
+Form by reasonable means in a timely manner, at a charge no more
+than the cost of distribution to the recipient; and
+
+(b) You may distribute such Executable Form under the terms of this
+License, or sublicense it under different terms, provided that the
+license for the Executable Form does not attempt to limit or alter
+the recipients' rights in the Source Code Form under this License.
+
+3.3. Distribution of a Larger Work
+
+You may create and distribute a Larger Work under terms of Your choice,
+provided that You also comply with the requirements of this License for
+the Covered Software. If the Larger Work is a combination of Covered
+Software with a work governed by one or more Secondary Licenses, and the
+Covered Software is not Incompatible With Secondary Licenses, this
+License permits You to additionally distribute such Covered Software
+under the terms of such Secondary License(s), so that the recipient of
+the Larger Work may, at their option, further distribute the Covered
+Software under the terms of either this License or such Secondary
+License(s).
+
+3.4. Notices
+
+You may not remove or alter the substance of any license notices
+(including copyright notices, patent notices, disclaimers of warranty,
+or limitations of liability) contained within the Source Code Form of
+the Covered Software, except that You may alter any license notices to
+the extent required to remedy known factual inaccuracies.
+
+3.5. Application of Additional Terms
+
+You may choose to offer, and to charge a fee for, warranty, support,
+indemnity or liability obligations to one or more recipients of Covered
+Software. However, You may do so only on Your own behalf, and not on
+behalf of any Contributor. You must make it absolutely clear that any
+such warranty, support, indemnity, or liability obligation is offered by
+You alone, and You hereby agree to indemnify every Contributor for any
+liability incurred by such Contributor as a result of warranty, support,
+indemnity or liability terms You offer. You may include additional
+disclaimers of warranty and limitations of liability specific to any
+jurisdiction.
+
+4. Inability to Comply Due to Statute or Regulation
+---------------------------------------------------
+
+If it is impossible for You to comply with any of the terms of this
+License with respect to some or all of the Covered Software due to
+statute, judicial order, or regulation then You must: (a) comply with
+the terms of this License to the maximum extent possible; and (b)
+describe the limitations and the code they affect. Such description must
+be placed in a text file included with all distributions of the Covered
+Software under this License. Except to the extent prohibited by statute
+or regulation, such description must be sufficiently detailed for a
+recipient of ordinary skill to be able to understand it.
+
+5. Termination
+--------------
+
+5.1. The rights granted under this License will terminate automatically
+if You fail to comply with any of its terms. However, if You become
+compliant, then the rights granted under this License from a particular
+Contributor are reinstated (a) provisionally, unless and until such
+Contributor explicitly and finally terminates Your grants, and (b) on an
+ongoing basis, if such Contributor fails to notify You of the
+non-compliance by some reasonable means prior to 60 days after You have
+come back into compliance. Moreover, Your grants from a particular
+Contributor are reinstated on an ongoing basis if such Contributor
+notifies You of the non-compliance by some reasonable means, this is the
+first time You have received notice of non-compliance with this License
+from such Contributor, and You become compliant prior to 30 days after
+Your receipt of the notice.
+
+5.2. If You initiate litigation against any entity by asserting a patent
+infringement claim (excluding declaratory judgment actions,
+counter-claims, and cross-claims) alleging that a Contributor Version
+directly or indirectly infringes any patent, then the rights granted to
+You by any and all Contributors for the Covered Software under Section
+2.1 of this License shall terminate.
+
+5.3. In the event of termination under Sections 5.1 or 5.2 above, all
+end user license agreements (excluding distributors and resellers) which
+have been validly granted by You or Your distributors under this License
+prior to termination shall survive termination.
+
+************************************************************************
+* *
+* 6. Disclaimer of Warranty *
+* ------------------------- *
+* *
+* Covered Software is provided under this License on an "as is" *
+* basis, without warranty of any kind, either expressed, implied, or *
+* statutory, including, without limitation, warranties that the *
+* Covered Software is free of defects, merchantable, fit for a *
+* particular purpose or non-infringing. The entire risk as to the *
+* quality and performance of the Covered Software is with You. *
+* Should any Covered Software prove defective in any respect, You *
+* (not any Contributor) assume the cost of any necessary servicing, *
+* repair, or correction. This disclaimer of warranty constitutes an *
+* essential part of this License. No use of any Covered Software is *
+* authorized under this License except under this disclaimer. *
+* *
+************************************************************************
+
+************************************************************************
+* *
+* 7. Limitation of Liability *
+* -------------------------- *
+* *
+* Under no circumstances and under no legal theory, whether tort *
+* (including negligence), contract, or otherwise, shall any *
+* Contributor, or anyone who distributes Covered Software as *
+* permitted above, be liable to You for any direct, indirect, *
+* special, incidental, or consequential damages of any character *
+* including, without limitation, damages for lost profits, loss of *
+* goodwill, work stoppage, computer failure or malfunction, or any *
+* and all other commercial damages or losses, even if such party *
+* shall have been informed of the possibility of such damages. This *
+* limitation of liability shall not apply to liability for death or *
+* personal injury resulting from such party's negligence to the *
+* extent applicable law prohibits such limitation. Some *
+* jurisdictions do not allow the exclusion or limitation of *
+* incidental or consequential damages, so this exclusion and *
+* limitation may not apply to You. *
+* *
+************************************************************************
+
+8. Litigation
+-------------
+
+Any litigation relating to this License may be brought only in the
+courts of a jurisdiction where the defendant maintains its principal
+place of business and such litigation shall be governed by laws of that
+jurisdiction, without reference to its conflict-of-law provisions.
+Nothing in this Section shall prevent a party's ability to bring
+cross-claims or counter-claims.
+
+9. Miscellaneous
+----------------
+
+This License represents the complete agreement concerning the subject
+matter hereof. If any provision of this License is held to be
+unenforceable, such provision shall be reformed only to the extent
+necessary to make it enforceable. Any law or regulation which provides
+that the language of a contract shall be construed against the drafter
+shall not be used to construe this License against a Contributor.
+
+10. Versions of the License
+---------------------------
+
+10.1. New Versions
+
+Mozilla Foundation is the license steward. Except as provided in Section
+10.3, no one other than the license steward has the right to modify or
+publish new versions of this License. Each version will be given a
+distinguishing version number.
+
+10.2. Effect of New Versions
+
+You may distribute the Covered Software under the terms of the version
+of the License under which You originally received the Covered Software,
+or under the terms of any subsequent version published by the license
+steward.
+
+10.3. Modified Versions
+
+If you create software not governed by this License, and you want to
+create a new license for such software, you may create and use a
+modified version of this License if you rename the license and remove
+any references to the name of the license steward (except to note that
+such modified license differs from this License).
+
+10.4. Distributing Source Code Form that is Incompatible With Secondary
+Licenses
+
+If You choose to distribute Source Code Form that is Incompatible With
+Secondary Licenses under the terms of this version of the License, the
+notice described in Exhibit B of this License must be attached.
+
+Exhibit A - Source Code Form License Notice
+-------------------------------------------
+
+This Source Code Form is subject to the terms of the Mozilla Public
+License, v. 2.0. If a copy of the MPL was not distributed with this
+file, You can obtain one at http://mozilla.org/MPL/2.0/.
+
+If it is not possible or desirable to put the notice in a particular
+file, then You may include the notice in a location (such as a LICENSE
+file in a relevant directory) where a recipient would be likely to look
+for such a notice.
+
+You may add additional accurate notices of copyright ownership.
+
+Exhibit B - "Incompatible With Secondary Licenses" Notice
+---------------------------------------------------------
+
+This Source Code Form is "Incompatible With Secondary Licenses", as
+defined by the Mozilla Public License, v. 2.0.
+
diff --git a/third_party/rust/plane-split/README.md b/third_party/rust/plane-split/README.md
new file mode 100644
index 0000000000..cd59852920
--- /dev/null
+++ b/third_party/rust/plane-split/README.md
@@ -0,0 +1,6 @@
+# plane-split
+[![Build Status](https://github.com/servo/plane-split/actions/workflows/main.yml/badge.svg)](https://github.com/servo/plane-split/actions)
+[![](https://img.shields.io/crates/v/plane-split.svg)](https://crates.io/crates/plane-split)
+[![Documentation](https://docs.rs/plane-split/badge.svg)](https://docs.rs/plane-split)
+
+Plane splitting with [euclid](https://crates.io/crates/euclid), made for [WebRender](https://github.com/servo/webrender).
diff --git a/third_party/rust/plane-split/benches/split.rs b/third_party/rust/plane-split/benches/split.rs
new file mode 100644
index 0000000000..c224bd7de7
--- /dev/null
+++ b/third_party/rust/plane-split/benches/split.rs
@@ -0,0 +1,20 @@
+#![feature(test)]
+
+extern crate euclid;
+extern crate plane_split;
+extern crate test;
+
+use euclid::vec3;
+use plane_split::{make_grid, BspSplitter};
+use std::sync::Arc;
+
+#[bench]
+fn bench_bsp(b: &mut test::Bencher) {
+    let polys = Arc::new(make_grid(5));
+    let mut splitter = BspSplitter::new();
+    let view = vec3(0.0, 0.0, 1.0);
+    b.iter(|| {
+        let p = polys.clone();
+        splitter.solve(&p, view);
+    });
+}
diff --git a/third_party/rust/plane-split/rustfmt.toml b/third_party/rust/plane-split/rustfmt.toml
new file mode 100644
index 0000000000..e69de29bb2
--- /dev/null
+++ b/third_party/rust/plane-split/rustfmt.toml
diff --git a/third_party/rust/plane-split/src/bsp.rs b/third_party/rust/plane-split/src/bsp.rs
new file mode 100644
index 0000000000..0b72d759f8
--- /dev/null
+++ b/third_party/rust/plane-split/src/bsp.rs
@@ -0,0 +1,187 @@
+use crate::{Plane, PlaneCut, Polygon};
+
+use euclid::default::{Point3D, Vector3D};
+use smallvec::SmallVec;
+
+use std::fmt;
+
+#[derive(Copy, Clone, Debug, PartialEq, Eq)]
+pub struct PolygonIdx(usize);
+
+#[derive(Copy, Clone, Debug, PartialEq, Eq)]
+pub struct NodeIdx(usize);
+
+/// Binary Space Partitioning splitter, uses a BSP tree.
+pub struct BspSplitter<A: Copy> {
+    result: Vec<Polygon<A>>,
+    nodes: Vec<BspNode>,
+    polygons: Vec<Polygon<A>>,
+}
+
+impl<A: Copy> BspSplitter<A> {
+    /// Create a new BSP splitter.
+    pub fn new() -> Self {
+        BspSplitter {
+            result: Vec::new(),
+            nodes: vec![BspNode::new()],
+            polygons: Vec::new(),
+        }
+    }
+}
+
+impl<A> BspSplitter<A>
+where
+    A: Copy + fmt::Debug + Default,
+{
+    /// Put the splitter back in it initial state.
+    ///
+    /// Call this at the beginning of every frame when reusing the splitter.
+    pub fn reset(&mut self) {
+        self.polygons.clear();
+        self.nodes.clear();
+        self.nodes.push(BspNode::new());
+    }
+
+    /// Add a polygon to the plane splitter.
+    ///
+    /// This is where most of the expensive computation happens.
+    pub fn add(&mut self, poly: Polygon<A>) {
+        let root = NodeIdx(0);
+        self.insert(root, &poly);
+    }
+
+    /// Sort the added and split polygons against the view vector.
+    ///
+    /// Call this towards the end of the frame after having added all polygons.
+    pub fn sort(&mut self, view: Vector3D<f64>) -> &[Polygon<A>] {
+        //debug!("\t\ttree before sorting {:?}", self.tree);
+        let poly = Polygon {
+            points: [Point3D::origin(); 4],
+            plane: Plane {
+                normal: -view, //Note: BSP `order()` is back to front
+                offset: 0.0,
+            },
+            anchor: A::default(),
+        };
+
+        let root = NodeIdx(0);
+        let mut result = std::mem::take(&mut self.result);
+        result.clear();
+        self.order(root, &poly, &mut result);
+        self.result = result;
+
+        &self.result
+    }
+
+    /// Process a set of polygons at once.
+    pub fn solve(&mut self, input: &[Polygon<A>], view: Vector3D<f64>) -> &[Polygon<A>]
+    where
+        A: Copy,
+    {
+        self.reset();
+        for p in input {
+            self.add(p.clone());
+        }
+        self.sort(view)
+    }
+
+    /// Insert a value into the sub-tree starting with this node.
+    /// This operation may spawn additional leafs/branches of the tree.
+    fn insert(&mut self, node_idx: NodeIdx, value: &Polygon<A>) {
+        let node = &mut self.nodes[node_idx.0];
+        if node.values.is_empty() {
+            node.values.push(add_polygon(&mut self.polygons, value));
+            return;
+        }
+
+        let mut front: SmallVec<[Polygon<A>; 2]> = SmallVec::new();
+        let mut back: SmallVec<[Polygon<A>; 2]> = SmallVec::new();
+        let first = node.values[0].0;
+        match self.polygons[first].cut(value, &mut front, &mut back) {
+            PlaneCut::Sibling => {
+                node.values.push(add_polygon(&mut self.polygons, value));
+            }
+            PlaneCut::Cut => {
+                if front.len() != 0 {
+                    if self.nodes[node_idx.0].front.is_none() {
+                        self.nodes[node_idx.0].front = Some(add_node(&mut self.nodes));
+                    }
+                    let node_front = self.nodes[node_idx.0].front.unwrap();
+                    for p in &front {
+                        self.insert(node_front, p)
+                    }
+                }
+                if back.len() != 0 {
+                    if self.nodes[node_idx.0].back.is_none() {
+                        self.nodes[node_idx.0].back = Some(add_node(&mut self.nodes));
+                    }
+                    let node_back = self.nodes[node_idx.0].back.unwrap();
+                    for p in &back {
+                        self.insert(node_back, p)
+                    }
+                }
+            }
+        }
+    }
+
+    /// Build the draw order of this sub-tree into an `out` vector,
+    /// so that the contained planes are sorted back to front according
+    /// to the view vector defined as the `base` plane front direction.
+    pub fn order(&self, node: NodeIdx, base: &Polygon<A>, out: &mut Vec<Polygon<A>>) {
+        let node = &self.nodes[node.0];
+        let (former, latter) = match node.values.first() {
+            None => return,
+            Some(first) => {
+                if base.is_aligned(&self.polygons[first.0]) {
+                    (node.front, node.back)
+                } else {
+                    (node.back, node.front)
+                }
+            }
+        };
+
+        if let Some(node) = former {
+            self.order(node, base, out);
+        }
+
+        out.reserve(node.values.len());
+        for poly_idx in &node.values {
+            out.push(self.polygons[poly_idx.0].clone());
+        }
+
+        if let Some(node) = latter {
+            self.order(node, base, out);
+        }
+    }
+}
+
+pub fn add_polygon<A: Copy>(polygons: &mut Vec<Polygon<A>>, poly: &Polygon<A>) -> PolygonIdx {
+    let index = PolygonIdx(polygons.len());
+    polygons.push(poly.clone());
+    index
+}
+
+pub fn add_node(nodes: &mut Vec<BspNode>) -> NodeIdx {
+    let index = NodeIdx(nodes.len());
+    nodes.push(BspNode::new());
+    index
+}
+
+/// A node in the `BspTree`, which can be considered a tree itself.
+#[derive(Clone, Debug)]
+pub struct BspNode {
+    values: SmallVec<[PolygonIdx; 4]>,
+    front: Option<NodeIdx>,
+    back: Option<NodeIdx>,
+}
+
+impl BspNode {
+    /// Create a new node.
+    pub fn new() -> Self {
+        BspNode {
+            values: SmallVec::new(),
+            front: None,
+            back: None,
+        }
+    }
+}
diff --git a/third_party/rust/plane-split/src/clip.rs b/third_party/rust/plane-split/src/clip.rs
new file mode 100644
index 0000000000..4425692085
--- /dev/null
+++ b/third_party/rust/plane-split/src/clip.rs
@@ -0,0 +1,142 @@
+use crate::{Intersection, NegativeHemisphereError, Plane, Polygon};
+
+use euclid::default::{Rect, Scale, Transform3D, Vector3D};
+
+use std::{fmt, iter, mem};
+
+/// A helper object to clip polygons by a number of planes.
+#[derive(Debug)]
+pub struct Clipper<A> {
+    clips: Vec<Plane>,
+    results: Vec<Polygon<A>>,
+    temp: Vec<Polygon<A>>,
+}
+
+impl<A: Copy + fmt::Debug> Clipper<A> {
+    /// Create a new clipper object.
+    pub fn new() -> Self {
+        Clipper {
+            clips: Vec::new(),
+            results: Vec::new(),
+            temp: Vec::new(),
+        }
+    }
+
+    /// Reset the clipper internals, but preserve the allocation.
+    pub fn reset(&mut self) {
+        self.clips.clear();
+    }
+
+    /// Extract the clipping planes that define the frustum for a given transformation.
+    pub fn frustum_planes(
+        t: &Transform3D<f64>,
+        bounds: Option<Rect<f64>>,
+    ) -> Result<impl Iterator<Item = Plane>, NegativeHemisphereError> {
+        let mw = Vector3D::new(t.m14, t.m24, t.m34);
+        let plane_positive = Plane::from_unnormalized(mw, t.m44)?;
+
+        let bounds_iter_maybe = match bounds {
+            Some(bounds) => {
+                let mx = Vector3D::new(t.m11, t.m21, t.m31);
+                let left = bounds.origin.x;
+                let plane_left =
+                    Plane::from_unnormalized(mx - mw * Scale::new(left), t.m41 - t.m44 * left)?;
+                let right = bounds.origin.x + bounds.size.width;
+                let plane_right =
+                    Plane::from_unnormalized(mw * Scale::new(right) - mx, t.m44 * right - t.m41)?;
+
+                let my = Vector3D::new(t.m12, t.m22, t.m32);
+                let top = bounds.origin.y;
+                let plane_top =
+                    Plane::from_unnormalized(my - mw * Scale::new(top), t.m42 - t.m44 * top)?;
+                let bottom = bounds.origin.y + bounds.size.height;
+                let plane_bottom =
+                    Plane::from_unnormalized(mw * Scale::new(bottom) - my, t.m44 * bottom - t.m42)?;
+
+                Some(
+                    plane_left
+                        .into_iter()
+                        .chain(plane_right)
+                        .chain(plane_top)
+                        .chain(plane_bottom),
+                )
+            }
+            None => None,
+        };
+
+        Ok(bounds_iter_maybe
+            .into_iter()
+            .flat_map(|pi| pi)
+            .chain(plane_positive))
+    }
+
+    /// Add a clipping plane to the list. The plane will clip everything behind it,
+    /// where the direction is set by the plane normal.
+    pub fn add(&mut self, plane: Plane) {
+        self.clips.push(plane);
+    }
+
+    /// Clip specified polygon by the contained planes, return the fragmented polygons.
+    pub fn clip(&mut self, polygon: Polygon<A>) -> &[Polygon<A>] {
+        log::debug!("\tClipping {:?}", polygon);
+        self.results.clear();
+        self.results.push(polygon);
+
+        for clip in &self.clips {
+            self.temp.clear();
+            mem::swap(&mut self.results, &mut self.temp);
+
+            for mut poly in self.temp.drain(..) {
+                let dist = match poly.intersect_plane(clip) {
+                    Intersection::Inside(line) => {
+                        let (res1, res2) = poly.split_with_normal(&line, &clip.normal);
+                        self.results.extend(
+                            iter::once(poly)
+                                .chain(res1)
+                                .chain(res2)
+                                .filter(|p| clip.signed_distance_sum_to(p) > 0.0),
+                        );
+                        continue;
+                    }
+                    Intersection::Coplanar => {
+                        let ndot = poly.plane.normal.dot(clip.normal);
+                        clip.offset - ndot * poly.plane.offset
+                    }
+                    Intersection::Outside => clip.signed_distance_sum_to(&poly),
+                };
+
+                if dist > 0.0 {
+                    self.results.push(poly);
+                }
+            }
+        }
+
+        &self.results
+    }
+
+    /// Clip the primitive with the frustum of the specified transformation,
+    /// returning a sequence of polygons in the transformed space.
+    /// Returns None if the transformation can't be frustum clipped.
+    pub fn clip_transformed<'a>(
+        &'a mut self,
+        polygon: Polygon<A>,
+        transform: &'a Transform3D<f64>,
+        bounds: Option<Rect<f64>>,
+    ) -> Result<impl 'a + Iterator<Item = Polygon<A>>, NegativeHemisphereError> {
+        let planes = Self::frustum_planes(transform, bounds)?;
+
+        let old_count = self.clips.len();
+        self.clips.extend(planes);
+        self.clip(polygon);
+        // remove the frustum planes
+        while self.clips.len() > old_count {
+            self.clips.pop();
+        }
+
+        let polys = self
+            .results
+            .drain(..)
+            .flat_map(move |poly| poly.transform(transform));
+        Ok(polys)
+    }
+}
diff --git a/third_party/rust/plane-split/src/lib.rs b/third_party/rust/plane-split/src/lib.rs
new file mode 100644
index 0000000000..4d3936b137
--- /dev/null
+++ b/third_party/rust/plane-split/src/lib.rs
@@ -0,0 +1,239 @@
+/*!
+Plane splitting.
+
+Uses [euclid](https://crates.io/crates/euclid) for the math basis.
+Introduces new geometrical primitives and associated logic.
+
+Automatically splits a given set of 4-point polygons into sub-polygons
+that don't intersect each other. This is useful for WebRender, to sort
+the resulting sub-polygons by depth and avoid transparency blending issues.
+*/
+#![warn(missing_docs)]
+
+mod bsp;
+mod clip;
+mod polygon;
+
+pub use polygon::PlaneCut;
+
+use euclid::{
+    approxeq::ApproxEq,
+    default::{Point3D, Scale, Vector3D},
+};
+
+use std::ops;
+
+pub use self::bsp::BspSplitter;
+pub use self::clip::Clipper;
+pub use self::polygon::{Intersection, LineProjection, Polygon};
+
+fn is_zero(value: f64) -> bool {
+    //HACK: this is rough, but the original Epsilon is too strict
+    (value * value).approx_eq(&0.0)
+}
+
+fn is_zero_vec(vec: Vector3D<f64>) -> bool {
+    vec.dot(vec).approx_eq(&0.0)
+}
+
+/// A generic line.
+#[derive(Debug)]
+pub struct Line {
+    /// Arbitrary point on the line.
+    pub origin: Point3D<f64>,
+    /// Normalized direction of the line.
+    pub dir: Vector3D<f64>,
+}
+
+impl Line {
+    /// Check if the line has consistent parameters.
+    pub fn is_valid(&self) -> bool {
+        is_zero(self.dir.dot(self.dir) - 1.0)
+    }
+    /// 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<Point3D<f64>>) -> Option<f64> {
+        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(&0.0) {
+            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)]
+pub struct Plane {
+    /// Normalized vector perpendicular to the plane.
+    pub normal: Vector3D<f64>,
+    /// Constant offset from the normal plane, specified in the
+    /// direction opposite to the normal.
+    pub offset: f64,
+}
+
+impl Clone for Plane {
+    fn clone(&self) -> Self {
+        Plane {
+            normal: self.normal.clone(),
+            offset: self.offset.clone(),
+        }
+    }
+}
+
+/// An error returned when everything would end up projected
+/// to the negative hemisphere (W <= 0.0);
+#[derive(Clone, Debug, Hash, PartialEq, PartialOrd)]
+pub struct NegativeHemisphereError;
+
+impl Plane {
+    /// Construct a new plane from unnormalized equation.
+    pub fn from_unnormalized(
+        normal: Vector3D<f64>,
+        offset: f64,
+    ) -> Result<Option<Self>, NegativeHemisphereError> {
+        let square_len = normal.square_length();
+        if square_len < f64::approx_epsilon() * f64::approx_epsilon() {
+            if offset > 0.0 {
+                Ok(None)
+            } else {
+                Err(NegativeHemisphereError)
+            }
+        } else {
+            let kf = 1.0 / square_len.sqrt();
+            Ok(Some(Plane {
+                normal: normal * Scale::new(kf),
+                offset: offset * kf,
+            }))
+        }
+    }
+
+    /// Check if this plane contains another one.
+    pub fn contains(&self, other: &Self) -> bool {
+        //TODO: actually check for inside/outside
+        self.normal == other.normal && self.offset == other.offset
+    }
+
+    /// Return the signed distance from this plane to a point.
+    /// The distance is negative if the point is on the other side of the plane
+    /// from the direction of the normal.
+    pub fn signed_distance_to(&self, point: &Point3D<f64>) -> f64 {
+        point.to_vector().dot(self.normal) + self.offset
+    }
+
+    /// Compute the distance across the line to the plane plane,
+    /// starting from the line origin.
+    pub fn distance_to_line(&self, line: &Line) -> f64 {
+        self.signed_distance_to(&line.origin) / -self.normal.dot(line.dir)
+    }
+
+    /// Compute the sum of signed distances to each of the points
+    /// of another plane. Useful to know the relation of a plane that
+    /// is a product of a split, and we know it doesn't intersect `self`.
+    pub fn signed_distance_sum_to<A>(&self, poly: &Polygon<A>) -> f64 {
+        poly.points
+            .iter()
+            .fold(0.0, |u, p| u + self.signed_distance_to(p))
+    }
+
+    /// Check if a convex shape defined by a set of points is completely
+    /// outside of this plane. Merely touching the surface is not
+    /// considered an intersection.
+    pub fn are_outside(&self, points: &[Point3D<f64>]) -> bool {
+        let d0 = self.signed_distance_to(&points[0]);
+        points[1..]
+            .iter()
+            .all(|p| self.signed_distance_to(p) * d0 > 0.0)
+    }
+
+    //TODO(breaking): turn this into Result<Line, DotProduct>
+    /// Compute the line of intersection with another plane.
+    pub fn intersect(&self, other: &Self) -> Option<Line> {
+        // 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 = 1.0 - w * w;
+        if divisor < f64::approx_epsilon() * f64::approx_epsilon() {
+            return None;
+        }
+        let origin = Point3D::origin() + self.normal * ((other.offset * w - self.offset) / divisor)
+            - other.normal * ((other.offset - self.offset * w) / divisor);
+
+        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(),
+        })
+    }
+}
+
+/// Helper method used for benchmarks and tests.
+/// Constructs a 3D grid of polygons.
+#[doc(hidden)]
+pub fn make_grid(count: usize) -> Vec<Polygon<usize>> {
+    let mut polys: Vec<Polygon<usize>> = Vec::with_capacity(count * 3);
+    let len = count as f64;
+    polys.extend((0..count).map(|i| Polygon {
+        points: [
+            Point3D::new(0.0, i as f64, 0.0),
+            Point3D::new(len, i as f64, 0.0),
+            Point3D::new(len, i as f64, len),
+            Point3D::new(0.0, i as f64, len),
+        ],
+        plane: Plane {
+            normal: Vector3D::new(0.0, 1.0, 0.0),
+            offset: -(i as f64),
+        },
+        anchor: 0,
+    }));
+    polys.extend((0..count).map(|i| Polygon {
+        points: [
+            Point3D::new(i as f64, 0.0, 0.0),
+            Point3D::new(i as f64, len, 0.0),
+            Point3D::new(i as f64, len, len),
+            Point3D::new(i as f64, 0.0, len),
+        ],
+        plane: Plane {
+            normal: Vector3D::new(1.0, 0.0, 0.0),
+            offset: -(i as f64),
+        },
+        anchor: 0,
+    }));
+    polys.extend((0..count).map(|i| Polygon {
+        points: [
+            Point3D::new(0.0, 0.0, i as f64),
+            Point3D::new(len, 0.0, i as f64),
+            Point3D::new(len, len, i as f64),
+            Point3D::new(0.0, len, i as f64),
+        ],
+        plane: Plane {
+            normal: Vector3D::new(0.0, 0.0, 1.0),
+            offset: -(i as f64),
+        },
+        anchor: 0,
+    }));
+    polys
+}
diff --git a/third_party/rust/plane-split/src/polygon.rs b/third_party/rust/plane-split/src/polygon.rs
new file mode 100644
index 0000000000..5929263346
--- /dev/null
+++ b/third_party/rust/plane-split/src/polygon.rs
@@ -0,0 +1,654 @@
+use crate::{is_zero, Line, Plane};
+
+use euclid::{
+    approxeq::ApproxEq,
+    default::{Point2D, Point3D, Rect, Transform3D, Vector3D},
+};
+use smallvec::SmallVec;
+
+use std::{iter, mem};
+
+/// The projection of a `Polygon` on a line.
+pub struct LineProjection {
+    /// Projected value of each point in the polygon.
+    pub markers: [f64; 4],
+}
+
+impl LineProjection {
+    /// Get the min/max of the line projection markers.
+    pub fn get_bounds(&self) -> (f64, f64) {
+        let (mut a, mut b, mut c, mut d) = (
+            self.markers[0],
+            self.markers[1],
+            self.markers[2],
+            self.markers[3],
+        );
+        // bitonic sort of 4 elements
+        // we could not just use `min/max` since they require `Ord` bound
+        //TODO: make it nicer
+        if a > c {
+            mem::swap(&mut a, &mut c);
+        }
+        if b > d {
+            mem::swap(&mut b, &mut d);
+        }
+        if a > b {
+            mem::swap(&mut a, &mut b);
+        }
+        if c > d {
+            mem::swap(&mut c, &mut d);
+        }
+        if b > c {
+            mem::swap(&mut b, &mut c);
+        }
+        debug_assert!(a <= b && b <= c && c <= d);
+        (a, d)
+    }
+
+    /// Check intersection with another line projection.
+    pub fn intersect(&self, other: &Self) -> bool {
+        // compute the bounds of both line projections
+        let span = self.get_bounds();
+        let other_span = other.get_bounds();
+        // compute the total footprint
+        let left = if span.0 < other_span.0 {
+            span.0
+        } else {
+            other_span.0
+        };
+        let right = if span.1 > other_span.1 {
+            span.1
+        } else {
+            other_span.1
+        };
+        // they intersect if the footprint is smaller than the sum
+        right - left < span.1 - span.0 + other_span.1 - other_span.0
+    }
+}
+
+/// Polygon intersection results.
+pub enum Intersection<T> {
+    /// Polygons are coplanar, including the case of being on the same plane.
+    Coplanar,
+    /// Polygon planes are intersecting, but polygons are not.
+    Outside,
+    /// Polygons are actually intersecting.
+    Inside(T),
+}
+
+impl<T> Intersection<T> {
+    /// Return true if the intersection is completely outside.
+    pub fn is_outside(&self) -> bool {
+        match *self {
+            Intersection::Outside => true,
+            _ => false,
+        }
+    }
+    /// Return true if the intersection cuts the source polygon.
+    pub fn is_inside(&self) -> bool {
+        match *self {
+            Intersection::Inside(_) => true,
+            _ => false,
+        }
+    }
+}
+
+/// A convex polygon with 4 points lying on a plane.
+#[derive(Debug, PartialEq)]
+pub struct Polygon<A> {
+    /// Points making the polygon.
+    pub points: [Point3D<f64>; 4],
+    /// A plane describing polygon orientation.
+    pub plane: Plane,
+    /// A simple anchoring index to allow association of the
+    /// produced split polygons with the original one.
+    pub anchor: A,
+}
+
+impl<A: Copy> Clone for Polygon<A> {
+    fn clone(&self) -> Self {
+        Polygon {
+            points: [
+                self.points[0].clone(),
+                self.points[1].clone(),
+                self.points[2].clone(),
+                self.points[3].clone(),
+            ],
+            plane: self.plane.clone(),
+            anchor: self.anchor,
+        }
+    }
+}
+
+impl<A> Polygon<A>
+where
+    A: Copy,
+{
+    /// Construct a polygon from points that are already transformed.
+    /// Return None if the polygon doesn't contain any space.
+    pub fn from_points(points: [Point3D<f64>; 4], anchor: A) -> Option<Self> {
+        let edge1 = points[1] - points[0];
+        let edge2 = points[2] - points[0];
+        let edge3 = points[3] - points[0];
+        let edge4 = points[3] - points[1];
+
+        if edge2.square_length() < f64::EPSILON || edge4.square_length() < f64::EPSILON {
+            return None;
+        }
+
+        // one of them can be zero for redundant polygons produced by plane splitting
+        //Note: this would be nicer if we used triangles instead of quads in the first place...
+        // see https://github.com/servo/plane-split/issues/17
+        let normal_rough1 = edge1.cross(edge2);
+        let normal_rough2 = edge2.cross(edge3);
+        let square_length1 = normal_rough1.square_length();
+        let square_length2 = normal_rough2.square_length();
+        let normal = if square_length1 > square_length2 {
+            normal_rough1 / square_length1.sqrt()
+        } else {
+            normal_rough2 / square_length2.sqrt()
+        };
+
+        let offset = -points[0].to_vector().dot(normal);
+
+        Some(Polygon {
+            points,
+            plane: Plane { normal, offset },
+            anchor,
+        })
+    }
+
+    /// Construct a polygon from a non-transformed rectangle.
+    pub fn from_rect(rect: Rect<f64>, anchor: A) -> Self {
+        let min = rect.min();
+        let max = rect.max();
+        Polygon {
+            points: [
+                min.to_3d(),
+                Point3D::new(max.x, min.y, 0.0),
+                max.to_3d(),
+                Point3D::new(min.x, max.y, 0.0),
+            ],
+            plane: Plane {
+                normal: Vector3D::new(0.0, 0.0, 1.0),
+                offset: 0.0,
+            },
+            anchor,
+        }
+    }
+
+    /// Construct a polygon from a rectangle with 3D transform.
+    pub fn from_transformed_rect(
+        rect: Rect<f64>,
+        transform: Transform3D<f64>,
+        anchor: A,
+    ) -> Option<Self> {
+        let min = rect.min();
+        let max = rect.max();
+        let points = [
+            transform.transform_point3d(min.to_3d())?,
+            transform.transform_point3d(Point3D::new(max.x, min.y, 0.0))?,
+            transform.transform_point3d(max.to_3d())?,
+            transform.transform_point3d(Point3D::new(min.x, max.y, 0.0))?,
+        ];
+        Self::from_points(points, anchor)
+    }
+
+    /// Construct a polygon from a rectangle with an invertible 3D transform.
+    pub fn from_transformed_rect_with_inverse(
+        rect: Rect<f64>,
+        transform: &Transform3D<f64>,
+        inv_transform: &Transform3D<f64>,
+        anchor: A,
+    ) -> Option<Self> {
+        let min = rect.min();
+        let max = rect.max();
+        let points = [
+            transform.transform_point3d(min.to_3d())?,
+            transform.transform_point3d(Point3D::new(max.x, min.y, 0.0))?,
+            transform.transform_point3d(max.to_3d())?,
+            transform.transform_point3d(Point3D::new(min.x, max.y, 0.0))?,
+        ];
+
+        // Compute the normal directly from the transformation. This guarantees consistent polygons
+        // generated from various local rectanges on the same geometry plane.
+        let normal_raw = Vector3D::new(inv_transform.m13, inv_transform.m23, inv_transform.m33);
+        let normal_sql = normal_raw.square_length();
+        if normal_sql.approx_eq(&0.0) || transform.m44.approx_eq(&0.0) {
+            None
+        } else {
+            let normal = normal_raw / normal_sql.sqrt();
+            let offset = -Vector3D::new(transform.m41, transform.m42, transform.m43).dot(normal)
+                / transform.m44;
+
+            Some(Polygon {
+                points,
+                plane: Plane { normal, offset },
+                anchor,
+            })
+        }
+    }
+
+    /// Bring a point into the local coordinate space, returning
+    /// the 2D normalized coordinates.
+    pub fn untransform_point(&self, point: Point3D<f64>) -> Point2D<f64> {
+        //debug_assert!(self.contains(point));
+        // get axises and target vector
+        let a = self.points[1] - self.points[0];
+        let b = self.points[3] - self.points[0];
+        let c = point - self.points[0];
+        // get pair-wise dot products
+        let a2 = a.dot(a);
+        let ab = a.dot(b);
+        let b2 = b.dot(b);
+        let ca = c.dot(a);
+        let cb = c.dot(b);
+        // compute the final coordinates
+        let denom = ab * ab - a2 * b2;
+        let x = ab * cb - b2 * ca;
+        let y = ab * ca - a2 * cb;
+        Point2D::new(x, y) / denom
+    }
+
+    /// Transform a polygon by an affine transform (preserving straight lines).
+    pub fn transform(&self, transform: &Transform3D<f64>) -> Option<Polygon<A>> {
+        let mut points = [Point3D::origin(); 4];
+        for (out, point) in points.iter_mut().zip(self.points.iter()) {
+            let mut homo = transform.transform_point3d_homogeneous(*point);
+            homo.w = homo.w.max(f64::approx_epsilon());
+            *out = homo.to_point3d()?;
+        }
+
+        //Note: this code path could be more efficient if we had inverse-transpose
+        //let n4 = transform.transform_point4d(&Point4D::new(0.0, 0.0, T::one(), 0.0));
+        //let normal = Point3D::new(n4.x, n4.y, n4.z);
+        Polygon::from_points(points, self.anchor)
+    }
+
+    /// Check if all the points are indeed placed on the plane defined by
+    /// the normal and offset, and the winding order is consistent.
+    pub fn is_valid(&self) -> bool {
+        let is_planar = self
+            .points
+            .iter()
+            .all(|p| is_zero(self.plane.signed_distance_to(p)));
+        let edges = [
+            self.points[1] - self.points[0],
+            self.points[2] - self.points[1],
+            self.points[3] - self.points[2],
+            self.points[0] - self.points[3],
+        ];
+        let anchor = edges[3].cross(edges[0]);
+        let is_winding = edges
+            .iter()
+            .zip(edges[1..].iter())
+            .all(|(a, &b)| a.cross(b).dot(anchor) >= 0.0);
+        is_planar && is_winding
+    }
+
+    /// Check if the polygon doesn't contain any space. This may happen
+    /// after a sequence of splits, and such polygons should be discarded.
+    pub fn is_empty(&self) -> bool {
+        (self.points[0] - self.points[2]).square_length() < f64::EPSILON
+            || (self.points[1] - self.points[3]).square_length() < f64::EPSILON
+    }
+
+    /// Check if this polygon contains another one.
+    pub fn contains(&self, other: &Self) -> bool {
+        //TODO: actually check for inside/outside
+        self.plane.contains(&other.plane)
+    }
+
+    /// Project this polygon onto a 3D vector, returning a line projection.
+    /// Note: we can think of it as a projection to a ray placed at the origin.
+    pub fn project_on(&self, vector: &Vector3D<f64>) -> LineProjection {
+        LineProjection {
+            markers: [
+                vector.dot(self.points[0].to_vector()),
+                vector.dot(self.points[1].to_vector()),
+                vector.dot(self.points[2].to_vector()),
+                vector.dot(self.points[3].to_vector()),
+            ],
+        }
+    }
+
+    /// Compute the line of intersection with an infinite plane.
+    pub fn intersect_plane(&self, other: &Plane) -> Intersection<Line> {
+        if other.are_outside(&self.points) {
+            log::debug!("\t\tOutside of the plane");
+            return Intersection::Outside;
+        }
+        match self.plane.intersect(&other) {
+            Some(line) => Intersection::Inside(line),
+            None => {
+                log::debug!("\t\tCoplanar");
+                Intersection::Coplanar
+            }
+        }
+    }
+
+    /// Compute the line of intersection with another polygon.
+    pub fn intersect(&self, other: &Self) -> Intersection<Line> {
+        if self.plane.are_outside(&other.points) || other.plane.are_outside(&self.points) {
+            log::debug!("\t\tOne is completely outside of the other");
+            return Intersection::Outside;
+        }
+        match self.plane.intersect(&other.plane) {
+            Some(line) => {
+                let self_proj = self.project_on(&line.dir);
+                let other_proj = other.project_on(&line.dir);
+                if self_proj.intersect(&other_proj) {
+                    Intersection::Inside(line)
+                } else {
+                    // projections on the line don't intersect
+                    log::debug!("\t\tProjection is outside");
+                    Intersection::Outside
+                }
+            }
+            None => {
+                log::debug!("\t\tCoplanar");
+                Intersection::Coplanar
+            }
+        }
+    }
+
+    fn split_impl(
+        &mut self,
+        first: (usize, Point3D<f64>),
+        second: (usize, Point3D<f64>),
+    ) -> (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
+        log::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) -> (Option<Self>, Option<Self>) {
+        log::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))
+        {
+            log::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);
+        }
+        // compute the intersection points for each edge
+        let mut cuts = [None; 4];
+        for ((&b, &a), cut) in self
+            .points
+            .iter()
+            .cycle()
+            .skip(1)
+            .zip(self.points.iter())
+            .zip(cuts.iter_mut())
+        {
+            if let Some(t) = line.intersect_edge(a..b) {
+                if t >= 0.0 && t < 1.0 {
+                    *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),
+        };
+        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,
+        normal: &Vector3D<f64>,
+    ) -> (Option<Self>, Option<Self>) {
+        log::debug!("\tSplitting with normal");
+        // figure out which side of the split does each point belong to
+        let mut sides = [0.0; 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 < 0.0 && side1 >= 0.0 {
+                &mut cut_positive
+            } else if side0 > 0.0 && side1 <= 0.0 {
+                &mut cut_negative
+            } else {
+                continue;
+            };
+            // compute the cut point by weighting the opposite distances
+            //
+            // Note: this algorithm is designed to not favor one end of the edge over the other.
+            // The previous approach of calling `intersect_edge` sometimes ended up with "t" ever
+            // slightly outside of [0, 1] range, since it was computing it relative to the first point only.
+            //
+            // Given that we are intersecting two straight lines, the triangles on both
+            // sides of intersection are alike, so distances along the [point0, point1] line
+            // are proportional to the side vector lengths we just computed: (side0, side1).
+            let point =
+                (*point0 * side1.abs() + point1.to_vector() * side0.abs()) / (side0 - side1).abs();
+            if cut.is_some() {
+                // We don't expect that the direction changes more than once, unless
+                // the polygon is close to redundant, and we hit precision issues when
+                // computing the sides.
+                log::warn!("Splitting failed due to precision issues: {:?}", sides);
+                break;
+            }
+            *cut = Some((i, point));
+        }
+        // form new polygons
+        if let (Some(first), Some(mut second)) = (cut_positive, cut_negative) {
+            if second.0 < first.0 {
+                second.0 += 4;
+            }
+            self.split_impl(first, second)
+        } else {
+            (None, None)
+        }
+    }
+
+    /// Cut a polygon with another one.
+    ///
+    /// Write the resulting polygons in `front` and `back` if the polygon needs to be split.
+    pub fn cut(
+        &self,
+        poly: &Self,
+        front: &mut SmallVec<[Polygon<A>; 2]>,
+        back: &mut SmallVec<[Polygon<A>; 2]>,
+    ) -> PlaneCut {
+        //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);
+                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), 0.0)
+            }
+        };
+
+        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) => PlaneCut::Sibling,
+            Intersection::Coplanar | Intersection::Outside => {
+                if dist > 0.0 {
+                    front.push(poly.clone());
+                } else {
+                    back.push(poly.clone());
+                }
+
+                PlaneCut::Cut
+            }
+            Intersection::Inside(line) => {
+                let mut poly = poly.clone();
+                let (res_add1, res_add2) = poly.split_with_normal(&line, &self.plane.normal);
+
+                for sub in iter::once(poly)
+                    .chain(res_add1)
+                    .chain(res_add2)
+                    .filter(|p| !p.is_empty())
+                {
+                    let dist = self.plane.signed_distance_sum_to(&sub);
+                    if dist > 0.0 {
+                        front.push(sub)
+                    } else {
+                        back.push(sub)
+                    }
+                }
+
+                PlaneCut::Cut
+            }
+        }
+    }
+
+    /// Returns whether both polygon's planes are parallel.
+    pub fn is_aligned(&self, other: &Self) -> bool {
+        self.plane.normal.dot(other.plane.normal) > 0.0
+    }
+}
+
+/// The result of a polygon being cut by a plane.
+/// The "cut" here is an attempt to classify a plane as being
+/// in front or in the back of another one.
+#[derive(Debug, PartialEq)]
+pub enum PlaneCut {
+    /// The planes are one the same geometrical plane.
+    Sibling,
+    /// Planes are different, thus we can either determine that
+    /// our plane is completely in front/back of another one,
+    /// or split it into these sub-groups.
+    Cut,
+}
+
+#[test]
+fn test_split_precision() {
+    // regression test for https://bugzilla.mozilla.org/show_bug.cgi?id=1678454
+    let mut polygon = Polygon::<()> {
+        points: [
+            Point3D::new(300.0102, 150.00958, 0.0),
+            Point3D::new(606.0, 306.0, 0.0),
+            Point3D::new(300.21954, 150.11946, 0.0),
+            Point3D::new(300.08844, 150.05064, 0.0),
+        ],
+        plane: Plane {
+            normal: Vector3D::zero(),
+            offset: 0.0,
+        },
+        anchor: (),
+    };
+    let line = Line {
+        origin: Point3D::new(3.0690663, -5.8472385, 0.0),
+        dir: Vector3D::new(0.8854436, 0.46474677, -0.0),
+    };
+    let normal = Vector3D::new(0.46474662, -0.8854434, -0.0006389789);
+    polygon.split_with_normal(&line, &normal);
+}
diff --git a/third_party/rust/plane-split/tests/clip.rs b/third_party/rust/plane-split/tests/clip.rs
new file mode 100644
index 0000000000..f243c3e843
--- /dev/null
+++ b/third_party/rust/plane-split/tests/clip.rs
@@ -0,0 +1,147 @@
+use euclid::{
+    default::{Rect, Transform3D},
+    point3, rect, vec3, Angle,
+};
+use plane_split::{Clipper, Plane, Polygon};
+
+use std::f64::consts::FRAC_PI_4;
+
+#[test]
+fn clip_in() {
+    let plane = Plane::from_unnormalized(vec3(1.0, 0.0, 1.0), 20.0)
+        .unwrap()
+        .unwrap();
+    let mut clipper = Clipper::new();
+    clipper.add(plane);
+
+    let poly = Polygon::from_points(
+        [
+            point3(-10.0, -10.0, 0.0),
+            point3(10.0, -10.0, 0.0),
+            point3(10.0, 10.0, 0.0),
+            point3(-10.0, 10.0, 0.0),
+        ],
+        0,
+    )
+    .unwrap();
+
+    let results = clipper.clip(poly.clone());
+    assert_eq!(results[0], poly);
+    assert_eq!(results.len(), 1);
+}
+
+#[test]
+fn clip_out() {
+    let plane = Plane::from_unnormalized(vec3(1.0, 0.0, 1.0), -20.0)
+        .unwrap()
+        .unwrap();
+    let mut clipper = Clipper::new();
+    clipper.add(plane);
+
+    let poly = Polygon::from_points(
+        [
+            point3(-10.0, -10.0, 0.0),
+            point3(10.0, -10.0, 0.0),
+            point3(10.0, 10.0, 0.0),
+            point3(-10.0, 10.0, 0.0),
+        ],
+        0,
+    )
+    .unwrap();
+
+    let results = clipper.clip(poly);
+    assert!(results.is_empty());
+}
+
+#[test]
+fn clip_parallel() {
+    let plane = Plane {
+        normal: vec3(0.0, 0.0, 1.0),
+        offset: 0.0,
+    };
+    let mut clipper = Clipper::new();
+    clipper.add(plane);
+
+    let poly = Polygon::from_points(
+        [
+            point3(-10.0, -10.0, 0.0),
+            point3(10.0, -10.0, 0.0),
+            point3(10.0, 10.0, 0.0),
+            point3(-10.0, 10.0, 0.0),
+        ],
+        0,
+    )
+    .unwrap();
+
+    let results = clipper.clip(poly);
+    assert!(results.is_empty());
+}
+
+#[test]
+fn clip_repeat() {
+    let plane = Plane::from_unnormalized(vec3(1.0, 0.0, 1.0), 0.0)
+        .unwrap()
+        .unwrap();
+    let mut clipper = Clipper::new();
+    clipper.add(plane.clone());
+    clipper.add(plane.clone());
+
+    let poly = Polygon::from_points(
+        [
+            point3(-10.0, -10.0, 0.0),
+            point3(10.0, -10.0, 0.0),
+            point3(10.0, 10.0, 0.0),
+            point3(-10.0, 10.0, 0.0),
+        ],
+        0,
+    )
+    .unwrap();
+
+    let results = clipper.clip(poly);
+    assert_eq!(results.len(), 1);
+    assert!(plane.signed_distance_sum_to(&results[0]) > 0.0);
+}
+
+#[test]
+fn clip_transformed() {
+    let t_rot: Transform3D<f64> = Transform3D::rotation(0.0, 1.0, 0.0, Angle::radians(-FRAC_PI_4));
+    let t_div: Transform3D<f64> = Transform3D::perspective(5.0);
+    let transform = t_rot.then(&t_div);
+
+    let polygon = Polygon::from_rect(rect(-10.0, -10.0, 20.0, 20.0), 0);
+    let bounds: Rect<f64> = rect(-1.0, -1.0, 2.0, 2.0);
+
+    let mut clipper = Clipper::new();
+    let results = clipper.clip_transformed(polygon, &transform, Some(bounds));
+    // iterating enforces the transformation checks/unwraps
+    assert_ne!(0, results.unwrap().count());
+}
+
+#[test]
+fn clip_badly_transformed() {
+    let mut tx = Transform3D::<f64>::identity();
+    tx.m14 = -0.0000001;
+    tx.m44 = 0.0;
+
+    let mut clipper = Clipper::new();
+    let polygon = Polygon::from_rect(rect(-10.0, -10.0, 20.0, 20.0), 0);
+    let results = clipper.clip_transformed(polygon, &tx, None);
+    assert!(results.is_err());
+}
+
+#[test]
+fn clip_near_coplanar() {
+    let tx = Transform3D::<f64>::new(
+        1.0, 0.0, 0.0, 0.0, 0.0, 1.0, 0.0, 0.0, -960.0, -625.0, 1.0, -1.0, 100.0, -2852.0, 0.0, 1.0,
+    );
+    let mut clipper = Clipper::new();
+    let polygon = Polygon::from_rect(rect(0.0, 0.0, 1703.0, 4020.0), 0);
+
+    let bounds1 = rect(0.0, -430.0, 2048.0, 2048.0);
+    let results1 = clipper.clip_transformed(polygon.clone(), &tx, Some(bounds1));
+    assert_ne!(0, results1.unwrap().count());
+
+    let bounds2 = rect(0.0, 0.0, 816.0, 1039.0);
+    let results2 = clipper.clip_transformed(polygon, &tx, Some(bounds2));
+    assert_ne!(0, results2.unwrap().count());
+}
diff --git a/third_party/rust/plane-split/tests/main.rs b/third_party/rust/plane-split/tests/main.rs
new file mode 100644
index 0000000000..0bcac5a179
--- /dev/null
+++ b/third_party/rust/plane-split/tests/main.rs
@@ -0,0 +1,341 @@
+use euclid::{
+    approxeq::ApproxEq,
+    default::{Rect, Size2D, Transform3D},
+    point2, point3, vec3, Angle,
+};
+use plane_split::{Intersection, Line, LineProjection, NegativeHemisphereError, Plane, Polygon};
+
+#[test]
+fn line_proj_bounds() {
+    assert_eq!(
+        (-5.0f64, 4.0),
+        LineProjection {
+            markers: [-5.0f64, 1.0, 4.0, 2.0]
+        }
+        .get_bounds()
+    );
+    assert_eq!(
+        (1f64, 4.0),
+        LineProjection {
+            markers: [4f64, 3.0, 2.0, 1.0]
+        }
+        .get_bounds()
+    );
+}
+
+#[test]
+fn valid() {
+    let poly_a: Polygon<usize> = Polygon {
+        points: [
+            point3(0.0, 0.0, 0.0),
+            point3(1.0, 1.0, 1.0),
+            point3(1.0, 1.0, 0.0),
+            point3(0.0, 1.0, 1.0),
+        ],
+        plane: Plane {
+            normal: vec3(0.0, 1.0, 0.0),
+            offset: -1.0,
+        },
+        anchor: 0,
+    };
+    assert!(!poly_a.is_valid()); // points[0] is outside
+    let poly_b: Polygon<usize> = Polygon {
+        points: [
+            point3(0.0, 1.0, 0.0),
+            point3(1.0, 1.0, 1.0),
+            point3(1.0, 1.0, 0.0),
+            point3(0.0, 1.0, 1.0),
+        ],
+        plane: Plane {
+            normal: vec3(0.0, 1.0, 0.0),
+            offset: -1.0,
+        },
+        anchor: 0,
+    };
+    assert!(!poly_b.is_valid()); // winding is incorrect
+    let poly_c: Polygon<usize> = Polygon {
+        points: [
+            point3(0.0, 0.0, 1.0),
+            point3(1.0, 0.0, 1.0),
+            point3(1.0, 1.0, 1.0),
+            point3(0.0, 1.0, 1.0),
+        ],
+        plane: Plane {
+            normal: vec3(0.0, 0.0, 1.0),
+            offset: -1.0,
+        },
+        anchor: 0,
+    };
+    assert!(poly_c.is_valid());
+}
+
+#[test]
+fn empty() {
+    let poly = Polygon::from_points(
+        [
+            point3(0.0, 0.0, 1.0),
+            point3(0.0, 0.0, 1.0),
+            point3(0.0, 0.00000001, 1.0),
+            point3(1.0, 0.0, 0.0),
+        ],
+        1usize,
+    );
+    assert_eq!(None, poly);
+}
+
+fn test_transformed(rect: Rect<f64>, transform: Transform3D<f64>) {
+    let poly = Polygon::from_transformed_rect(rect, transform, 0).unwrap();
+    assert!(poly.is_valid());
+
+    let inv_transform = transform.inverse().unwrap();
+    let poly2 =
+        Polygon::from_transformed_rect_with_inverse(rect, &transform, &inv_transform, 0).unwrap();
+    assert_eq!(poly.points, poly2.points);
+    assert!(poly.plane.offset.approx_eq(&poly2.plane.offset));
+    assert!(poly.plane.normal.dot(poly2.plane.normal).approx_eq(&1.0));
+}
+
+#[test]
+fn from_transformed_rect() {
+    let rect = Rect::new(point2(10.0, 10.0), Size2D::new(20.0, 30.0));
+    let transform = Transform3D::rotation(0.5f64.sqrt(), 0.0, 0.5f64.sqrt(), Angle::radians(5.0))
+        .pre_translate(vec3(0.0, 0.0, 10.0));
+    test_transformed(rect, transform);
+}
+
+#[test]
+fn from_transformed_rect_perspective() {
+    let rect = Rect::new(point2(-10.0, -5.0), Size2D::new(20.0, 30.0));
+    let mut transform = Transform3D::perspective(400.0).pre_translate(vec3(0.0, 0.0, 100.0));
+    transform.m44 = 0.7; //for fun
+    test_transformed(rect, transform);
+}
+
+#[test]
+fn untransform_point() {
+    let poly: Polygon<usize> = Polygon {
+        points: [
+            point3(0.0, 0.0, 0.0),
+            point3(0.5, 1.0, 0.0),
+            point3(1.5, 1.0, 0.0),
+            point3(1.0, 0.0, 0.0),
+        ],
+        plane: Plane {
+            normal: vec3(0.0, 1.0, 0.0),
+            offset: 0.0,
+        },
+        anchor: 0,
+    };
+    assert_eq!(poly.untransform_point(poly.points[0]), point2(0.0, 0.0));
+    assert_eq!(poly.untransform_point(poly.points[1]), point2(1.0, 0.0));
+    assert_eq!(poly.untransform_point(poly.points[2]), point2(1.0, 1.0));
+    assert_eq!(poly.untransform_point(poly.points[3]), point2(0.0, 1.0));
+}
+
+#[test]
+fn are_outside() {
+    let plane = Plane {
+        normal: vec3(0.0, 0.0, 1.0),
+        offset: -1.0,
+    };
+    assert!(plane.are_outside(&[point3(0.0, 0.0, 1.1), point3(1.0, 1.0, 2.0),]));
+    assert!(plane.are_outside(&[point3(0.5, 0.5, 1.0),]));
+    assert!(!plane.are_outside(&[point3(0.0, 0.0, 1.0), point3(0.0, 0.0, -1.0),]));
+}
+
+#[test]
+fn intersect() {
+    let poly_a: Polygon<usize> = Polygon {
+        points: [
+            point3(0.0, 0.0, 1.0),
+            point3(1.0, 0.0, 1.0),
+            point3(1.0, 1.0, 1.0),
+            point3(0.0, 1.0, 1.0),
+        ],
+        plane: Plane {
+            normal: vec3(0.0, 0.0, 1.0),
+            offset: -1.0,
+        },
+        anchor: 0,
+    };
+    assert!(poly_a.is_valid());
+    let poly_b: Polygon<usize> = Polygon {
+        points: [
+            point3(0.5, 0.0, 2.0),
+            point3(0.5, 1.0, 2.0),
+            point3(0.5, 1.0, 0.0),
+            point3(0.5, 0.0, 0.0),
+        ],
+        plane: Plane {
+            normal: vec3(1.0, 0.0, 0.0),
+            offset: -0.5,
+        },
+        anchor: 0,
+    };
+    assert!(poly_b.is_valid());
+
+    let intersection = match poly_a.intersect(&poly_b) {
+        Intersection::Inside(result) => result,
+        _ => panic!("Bad intersection"),
+    };
+    assert!(intersection.is_valid());
+    // confirm the origin is on both planes
+    assert!(poly_a
+        .plane
+        .signed_distance_to(&intersection.origin)
+        .approx_eq(&0.0));
+    assert!(poly_b
+        .plane
+        .signed_distance_to(&intersection.origin)
+        .approx_eq(&0.0));
+    // confirm the direction is coplanar to both planes
+    assert!(poly_a.plane.normal.dot(intersection.dir).approx_eq(&0.0));
+    assert!(poly_b.plane.normal.dot(intersection.dir).approx_eq(&0.0));
+
+    let poly_c: Polygon<usize> = Polygon {
+        points: [
+            point3(0.0, -1.0, 2.0),
+            point3(0.0, -1.0, 0.0),
+            point3(0.0, 0.0, 0.0),
+            point3(0.0, 0.0, 2.0),
+        ],
+        plane: Plane {
+            normal: vec3(1.0, 0.0, 0.0),
+            offset: 0.0,
+        },
+        anchor: 0,
+    };
+    assert!(poly_c.is_valid());
+    let poly_d: Polygon<usize> = Polygon {
+        points: [
+            point3(0.0, 0.0, 0.5),
+            point3(1.0, 0.0, 0.5),
+            point3(1.0, 1.0, 0.5),
+            point3(0.0, 1.0, 0.5),
+        ],
+        plane: Plane {
+            normal: vec3(0.0, 0.0, 1.0),
+            offset: -0.5,
+        },
+        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<usize>, extra_count: u8, line: Line) {
+    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_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));
+    }
+}
+
+#[test]
+fn split() {
+    let poly: Polygon<usize> = Polygon {
+        points: [
+            point3(0.0, 1.0, 0.0),
+            point3(1.0, 1.0, 0.0),
+            point3(1.0, 1.0, 1.0),
+            point3(0.0, 1.0, 1.0),
+        ],
+        plane: Plane {
+            normal: vec3(0.0, 1.0, 0.0),
+            offset: -1.0,
+        },
+        anchor: 0,
+    };
+
+    // non-intersecting line
+    test_cut(
+        &poly,
+        0,
+        Line {
+            origin: point3(0.0, 1.0, 0.5),
+            dir: vec3(0.0, 1.0, 0.0),
+        },
+    );
+
+    // simple cut (diff=2)
+    test_cut(
+        &poly,
+        1,
+        Line {
+            origin: point3(0.0, 1.0, 0.5),
+            dir: vec3(1.0, 0.0, 0.0),
+        },
+    );
+
+    // complex cut (diff=1, wrapped)
+    test_cut(
+        &poly,
+        2,
+        Line {
+            origin: point3(0.0, 1.0, 0.5),
+            dir: vec3(0.5f64.sqrt(), 0.0, -0.5f64.sqrt()),
+        },
+    );
+
+    // complex cut (diff=1, non-wrapped)
+    test_cut(
+        &poly,
+        2,
+        Line {
+            origin: point3(0.5, 1.0, 0.0),
+            dir: vec3(0.5f64.sqrt(), 0.0, 0.5f64.sqrt()),
+        },
+    );
+
+    // complex cut (diff=3)
+    test_cut(
+        &poly,
+        2,
+        Line {
+            origin: point3(0.5, 1.0, 0.0),
+            dir: vec3(-0.5f64.sqrt(), 0.0, 0.5f64.sqrt()),
+        },
+    );
+
+    // perfect diagonal
+    test_cut(
+        &poly,
+        1,
+        Line {
+            origin: point3(0.0, 1.0, 0.0),
+            dir: vec3(0.5f64.sqrt(), 0.0, 0.5f64.sqrt()),
+        },
+    );
+}
+
+#[test]
+fn plane_unnormalized() {
+    let zero_vec = vec3(0.0000001, 0.0, 0.0);
+    let mut plane: Result<Option<Plane>, _> = Plane::from_unnormalized(zero_vec, 1.0);
+    assert_eq!(plane, Ok(None));
+    plane = Plane::from_unnormalized(zero_vec, 0.0);
+    assert_eq!(plane, Err(NegativeHemisphereError));
+    plane = Plane::from_unnormalized(zero_vec, -0.5);
+    assert_eq!(plane, Err(NegativeHemisphereError));
+
+    let plane = Plane::from_unnormalized(vec3(-3.0, 4.0, 0.0), 2.0)
+        .unwrap()
+        .unwrap();
+    let expected = Plane {
+        normal: vec3(-3.0 / 5.0, 4.0 / 5.0, 0.0),
+        offset: 2.0 / 5.0,
+    };
+    assert!(plane.normal.approx_eq(&expected.normal));
+    assert!(plane.offset.approx_eq(&expected.offset));
+}
diff --git a/third_party/rust/plane-split/tests/split.rs b/third_party/rust/plane-split/tests/split.rs
new file mode 100644
index 0000000000..60d1d8035f
--- /dev/null
+++ b/third_party/rust/plane-split/tests/split.rs
@@ -0,0 +1,138 @@
+use euclid::{
+    default::{Rect, Transform3D},
+    rect, vec3, Angle,
+};
+use plane_split::PlaneCut;
+use plane_split::{make_grid, BspSplitter, Polygon};
+use std::f64::consts::FRAC_PI_4;
+
+fn grid_impl(count: usize, splitter: &mut BspSplitter<usize>) {
+    let polys = make_grid(count);
+    let result = splitter.solve(&polys, vec3(0.0, 0.0, 1.0));
+    assert_eq!(result.len(), count + count * count + count * count * count);
+}
+
+#[test]
+fn grid_bsp() {
+    grid_impl(2, &mut BspSplitter::new());
+}
+
+fn sort_rotation(splitter: &mut BspSplitter<usize>) {
+    let transform0: Transform3D<f64> =
+        Transform3D::rotation(0.0, 1.0, 0.0, Angle::radians(-FRAC_PI_4));
+    let transform1: Transform3D<f64> = Transform3D::rotation(0.0, 1.0, 0.0, Angle::radians(0.0));
+    let transform2: Transform3D<f64> =
+        Transform3D::rotation(0.0, 1.0, 0.0, Angle::radians(FRAC_PI_4));
+
+    let rect: Rect<f64> = rect(-10.0, -10.0, 20.0, 20.0);
+    let p1 = Polygon::from_transformed_rect(rect, transform0, 0);
+    let p2 = Polygon::from_transformed_rect(rect, transform1, 1);
+    let p3 = Polygon::from_transformed_rect(rect, transform2, 2);
+    assert!(
+        p1.is_some() && p2.is_some() && p3.is_some(),
+        "Cannot construct transformed polygons"
+    );
+
+    let polys = [p1.unwrap(), p2.unwrap(), p3.unwrap()];
+    let result = splitter.solve(&polys, vec3(0.0, 0.0, -1.0));
+    let ids: Vec<_> = result.iter().map(|poly| poly.anchor).collect();
+    assert_eq!(&ids, &[2, 1, 0, 1, 2]);
+}
+
+#[test]
+fn rotation_bsp() {
+    sort_rotation(&mut BspSplitter::new());
+}
+
+fn sort_trivial(splitter: &mut BspSplitter<usize>) {
+    let anchors: Vec<_> = (0usize..10).collect();
+    let rect: Rect<f64> = rect(-10.0, -10.0, 20.0, 20.0);
+    let polys: Vec<_> = anchors
+        .iter()
+        .map(|&anchor| {
+            let transform: Transform3D<f64> = Transform3D::translation(0.0, 0.0, anchor as f64);
+            let poly = Polygon::from_transformed_rect(rect, transform, anchor);
+            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));
+    //make sure Z is sorted backwards
+    assert_eq!(anchors1, anchors2);
+}
+
+fn sort_external(splitter: &mut BspSplitter<usize>) {
+    let rect0: Rect<f64> = rect(-10.0, -10.0, 20.0, 20.0);
+    let poly0 = Polygon::from_rect(rect0, 0);
+    let poly1 = {
+        let transform0: Transform3D<f64> =
+            Transform3D::rotation(1.0, 0.0, 0.0, Angle::radians(2.0 * FRAC_PI_4));
+        let transform1: Transform3D<f64> = Transform3D::translation(0.0, 100.0, 0.0);
+        Polygon::from_transformed_rect(rect0, transform0.then(&transform1), 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() {
+    use smallvec::SmallVec;
+    let rect: Rect<f64> = 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;
+    }
+
+    let mut front: SmallVec<[Polygon<i32>; 2]> = SmallVec::new();
+    let mut back: SmallVec<[Polygon<i32>; 2]> = SmallVec::new();
+
+    assert_eq!(poly.cut(&poly2, &mut front, &mut back), PlaneCut::Sibling);
+    assert!(front.is_empty());
+    assert!(back.is_empty());
+
+    // test robustness for normal
+    poly2.plane.normal.z += 0.00000001;
+    assert_eq!(poly.cut(&poly2, &mut front, &mut back), PlaneCut::Sibling);
+    assert!(front.is_empty());
+    assert!(back.is_empty());
+
+    // test opposite normal handling
+    poly2.plane.normal *= -1.0;
+    assert_eq!(poly.cut(&poly2, &mut front, &mut back), PlaneCut::Sibling);
+    assert!(front.is_empty());
+    assert!(back.is_empty());
+
+    // test grouping front
+    poly2.plane.offset += 0.1;
+    assert_eq!(poly.cut(&poly2, &mut front, &mut back), PlaneCut::Cut);
+    assert_eq!(front.len(), 1);
+    assert!(back.is_empty());
+
+    front.clear();
+
+    // test grouping back
+    poly2.plane.normal *= -1.0;
+    assert_eq!(poly.cut(&poly2, &mut front, &mut back), PlaneCut::Cut);
+    assert_eq!(back.len(), 1);
+    assert!(front.is_empty());
+}