summaryrefslogtreecommitdiffstats
path: root/third_party/rust/plane-split
diff options
context:
space:
mode:
Diffstat (limited to '')
-rw-r--r--third_party/rust/plane-split/.cargo-checksum.json1
-rw-r--r--third_party/rust/plane-split/Cargo.toml34
-rw-r--r--third_party/rust/plane-split/LICENSE374
-rw-r--r--third_party/rust/plane-split/README.md6
-rw-r--r--third_party/rust/plane-split/benches/split.rs20
-rw-r--r--third_party/rust/plane-split/rustfmt.toml0
-rw-r--r--third_party/rust/plane-split/src/bsp.rs187
-rw-r--r--third_party/rust/plane-split/src/clip.rs142
-rw-r--r--third_party/rust/plane-split/src/lib.rs239
-rw-r--r--third_party/rust/plane-split/src/polygon.rs654
-rw-r--r--third_party/rust/plane-split/tests/clip.rs147
-rw-r--r--third_party/rust/plane-split/tests/main.rs341
-rw-r--r--third_party/rust/plane-split/tests/split.rs138
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());
+}
generated by cgit v1.2.3 (git 2.39.1) at 2024-12-28 10:54:05 +0000