new file mode 100644
--- /dev/null
+++ b/third_party/rust/binary-space-partition/.cargo-checksum.json
@@ -0,0 +1,1 @@
+{"files":{".cargo-ok":"e3b0c44298fc1c149afbf4c8996fb92427ae41e4649b934ca495991b7852b855",".gitignore":"f9b1ca6ae27d1c18215265024629a8960c31379f206d9ed20f64e0b2dcf79805",".travis.yml":"0310eaafa77ed58afbc5f93b1a26e938e96533b352865bc75ff4a5993aa4a8e0","Cargo.toml":"6b56e1576b18b05d665fc048ac8995efbfc8f15f9952472c382b11957114a906","LICENSE":"b946744aeda89b467929585fe8eeb5461847695220c1b168fb375d8abd4ea3d0","README.md":"ed45cabc231f18f0972348f0e230d45c92495c31e4a06eb105e8259ed9b582b3","src/lib.rs":"566b415ed879434aef230a5b5a993d789f61e98b2e38a8c87fb7f1f6102f5e6d"},"package":"df65281d9b2b5c332f5bfbd9bb5e5f2e62f627c259cf9dc9cd10fecb758be33d"}
\ No newline at end of file
new file mode 100644
--- /dev/null
+++ b/third_party/rust/binary-space-partition/.gitignore
@@ -0,0 +1,2 @@
+target
+Cargo.lock
new file mode 100644
--- /dev/null
+++ b/third_party/rust/binary-space-partition/.travis.yml
@@ -0,0 +1,10 @@
+sudo: false
+language: rust
+cache: cargo
+rust:
+ - nightly
+ - stable
+script:
+ - cargo build
+ - cargo doc
+ - cargo test
new file mode 100644
--- /dev/null
+++ b/third_party/rust/binary-space-partition/Cargo.toml
@@ -0,0 +1,14 @@
+[package]
+name = "binary-space-partition"
+version = "0.1.1"
+authors = ["Dzmitry Malyshau <kvark@mozilla.com>"]
+description = "Abstract BSP tree"
+license = "MPL-2.0"
+repository = "https://github.com/kvark/binary-space-partition"
+keywords = ["geometry", "math"]
+documentation = "https://docs.rs/binary-space-partition"
+
+[dependencies]
+
+[dev-dependencies]
+rand = "0.3"
new file mode 100644
--- /dev/null
+++ b/third_party/rust/binary-space-partition/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.
+
new file mode 100644
--- /dev/null
+++ b/third_party/rust/binary-space-partition/README.md
@@ -0,0 +1,5 @@
+# binary-space-partition
+[](https://travis-ci.org/kvark/binary-space-partition) [](https://crates.io/crates/binary-space-partition) [](https://docs.rs/binary-space-partition)
+
+Binary Space Partitioning (BSP) tree.
+Designed to be used with [plane-split](https://github.com/kvark/plane-split) crate.
new file mode 100644
--- /dev/null
+++ b/third_party/rust/binary-space-partition/src/lib.rs
@@ -0,0 +1,218 @@
+/*!
+Binary Space Partitioning (BSP)
+
+Provides an abstract `BspNode` structure, which can be seen as a tree.
+Useful for quickly ordering polygons along a particular view vector.
+Is not tied to a particular math library.
+*/
+#![warn(missing_docs)]
+
+use std::cmp;
+
+
+/// The result of one plane being cut by another one.
+/// The "cut" here is an attempt to classify a plane as being
+/// in front or in the back of another one.
+pub enum PlaneCut<T> {
+ /// The planes are one the same geometrical plane.
+ Sibling(T),
+ /// 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 {
+ /// Sub-planes in front of the base plane.
+ front: Vec<T>,
+ /// Sub-planes in the back of the base plane.
+ back: Vec<T>,
+ },
+}
+
+/// A plane abstracted to the matter of partitioning.
+pub trait Plane: Sized + Clone {
+ /// Try to cut a different plane by this one.
+ fn cut(&self, Self) -> PlaneCut<Self>;
+ /// Check if a different plane is aligned in the same direction
+ /// as this one.
+ fn is_aligned(&self, &Self) -> bool;
+}
+
+/// Add a list of planes to a particular front/end branch of some root node.
+fn add_side<T: Plane>(side: &mut Option<Box<BspNode<T>>>, mut planes: Vec<T>) {
+ if planes.len() != 0 {
+ if side.is_none() {
+ *side = Some(Box::new(BspNode::new()));
+ }
+ let mut node = side.as_mut().unwrap();
+ for p in planes.drain(..) {
+ node.insert(p)
+ }
+ }
+}
+
+
+/// A node in the `BspTree`, which can be considered a tree itself.
+pub struct BspNode<T> {
+ values: Vec<T>,
+ front: Option<Box<BspNode<T>>>,
+ back: Option<Box<BspNode<T>>>,
+}
+
+impl<T> BspNode<T> {
+ /// Create a new node.
+ pub fn new() -> Self {
+ BspNode {
+ values: Vec::new(),
+ front: None,
+ back: None,
+ }
+ }
+
+ /// Check if this node is a leaf of the tree.
+ pub fn is_leaf(&self) -> bool {
+ self.front.is_none() && self.back.is_none()
+ }
+
+ /// Get the tree depth starting with this node.
+ pub fn get_depth(&self) -> usize {
+ if self.values.is_empty() {
+ return 0
+ }
+ let df = match self.front {
+ Some(ref node) => node.get_depth(),
+ None => 0,
+ };
+ let db = match self.back {
+ Some(ref node) => node.get_depth(),
+ None => 0,
+ };
+ 1 + cmp::max(df, db)
+ }
+}
+
+impl<T: Plane> BspNode<T> {
+ /// Insert a value into the sub-tree starting with this node.
+ /// This operation may spawn additional leafs/branches of the tree.
+ pub fn insert(&mut self, value: T) {
+ if self.values.is_empty() {
+ self.values.push(value);
+ return
+ }
+ match self.values[0].cut(value) {
+ PlaneCut::Sibling(value) => self.values.push(value),
+ PlaneCut::Cut { front, back } => {
+ add_side(&mut self.front, front);
+ add_side(&mut self.back, back);
+ }
+ }
+ }
+
+ /// 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 given as the `base` plane normal.
+ pub fn order(&self, base: &T, out: &mut Vec<T>) {
+ let (former, latter) = match self.values.first() {
+ None => return,
+ Some(ref first) if base.is_aligned(first) => (&self.back, &self.front),
+ Some(_) => (&self.front, &self.back),
+ };
+
+ if let Some(ref node) = *former {
+ node.order(base, out);
+ }
+
+ out.extend_from_slice(&self.values);
+
+ if let Some(ref node) = *latter {
+ node.order(base, out);
+ }
+ }
+}
+
+
+#[cfg(test)]
+mod tests {
+ extern crate rand;
+ use super::*;
+ use self::rand::Rng;
+
+ #[derive(Clone, Debug, PartialEq)]
+ struct Plane1D(i32, bool);
+
+ impl Plane for Plane1D {
+ fn cut(&self, plane: Self) -> PlaneCut<Self> {
+ if self.0 == plane.0 {
+ PlaneCut::Sibling(plane)
+ } else if (plane.0 > self.0) == self.1 {
+ PlaneCut::Cut {
+ front: vec![plane],
+ back: vec![],
+ }
+ } else {
+ PlaneCut::Cut {
+ front: vec![],
+ back: vec![plane],
+ }
+ }
+ }
+
+ fn is_aligned(&self, plane: &Self) -> bool {
+ self.1 == plane.1
+ }
+ }
+
+
+ #[test]
+ fn test_add_side() {
+ let mut node_opt = None;
+ let p0: Vec<Plane1D> = Vec::new();
+ add_side(&mut node_opt, p0);
+ assert!(node_opt.is_none());
+
+ let p1 = Plane1D(1, true);
+ add_side(&mut node_opt, vec![p1.clone()]);
+ assert_eq!(node_opt.as_ref().unwrap().values, vec![p1.clone()]);
+ assert!(node_opt.as_ref().unwrap().is_leaf());
+
+ let p23 = vec![Plane1D(0, false), Plane1D(2, false)];
+ add_side(&mut node_opt, p23);
+ let node = node_opt.unwrap();
+ assert_eq!(node.values, vec![p1.clone()]);
+ assert!(node.front.is_some() && node.back.is_some());
+ }
+
+ #[test]
+ fn test_insert_depth() {
+ let mut node = BspNode::new();
+ assert_eq!(node.get_depth(), 0);
+ node.insert(Plane1D(0, true));
+ assert_eq!(node.get_depth(), 1);
+ node.insert(Plane1D(6, true));
+ assert_eq!(node.get_depth(), 2);
+ node.insert(Plane1D(8, true));
+ assert_eq!(node.get_depth(), 3);
+ node.insert(Plane1D(6, true));
+ assert_eq!(node.get_depth(), 3);
+ node.insert(Plane1D(-5, false));
+ assert_eq!(node.get_depth(), 3);
+ }
+
+ #[test]
+ fn test_order() {
+ let mut rng = rand::thread_rng();
+ let mut node = BspNode::new();
+ let mut out = Vec::new();
+
+ node.order(&Plane1D(0, true), &mut out);
+ assert!(out.is_empty());
+
+ for _ in 0 .. 100 {
+ let plane = Plane1D(rng.gen(), rng.gen());
+ node.insert(plane);
+ }
+
+ node.order(&Plane1D(0, true), &mut out);
+ let mut out2 = out.clone();
+ out2.sort_by_key(|p| p.0);
+ assert_eq!(out, out2);
+ }
+}
--- a/third_party/rust/euclid/.cargo-checksum.json
+++ b/third_party/rust/euclid/.cargo-checksum.json
@@ -1,1 +1,1 @@
-{"files":{".cargo-ok":"e3b0c44298fc1c149afbf4c8996fb92427ae41e4649b934ca495991b7852b855",".gitignore":"118514fd9c4958df0d25584cda4917186c46011569f55ef350530c1ad3fbdb48",".travis.yml":"13d3e5a7bf83b04c8e8cfa14f0297bd8366d68391d977dd547f64707dffc275a","COPYRIGHT":"ec82b96487e9e778ee610c7ab245162464782cfa1f555c2299333f8dbe5c036a","Cargo.toml":"67de38f0cff93c8020ec3b04b222ea319be655700c58ea9e82951766c1d01b27","LICENSE-APACHE":"a60eea817514531668d7e00765731449fe14d059d3249e0bc93b36de45f759f2","LICENSE-MIT":"62065228e42caebca7e7d7db1204cbb867033de5982ca4009928915e4095f3a3","README.md":"7a5648f52b09d3213348177860171d4f19b0fdda55e8fed7c04dafcb0ed9c215","src/approxeq.rs":"2987e046c90d948b6c7d7ddba52d10c8b7520d71dc0a50dbe7665de128d7410e","src/length.rs":"0976cac2d792383389b58f8ea7eea022c618accc0d38f89858999082b4d8fe30","src/lib.rs":"a404dd1472f579b8e542a60ec0fb319e856c5424421ef6db8de8b0b792ccc2d9","src/macros.rs":"b63dabdb52df84ea170dc1dab5fe8d7a78c054562d1566bab416124708d2d7af","src/matrix2d.rs":"2612824b050823a88c96213fb5478558931e9d403cffb617cba02ac5190b964a","src/matrix4d.rs":"a5a917842105441f093da8a1a5d17f8f77a4ad3a2544cf937f6573b9713acbcc","src/num.rs":"62286aa642ce3afa7ebd950f50bf2197d8722907f2e23a2e2ea6690484d8b250","src/point.rs":"a585ad405a69505792efb624f0c0e6345b92b27a2c77e9a4366d6192ac914ef0","src/rect.rs":"7f79b1bc12a292ea413bd8a99637291bc131ee40374ebfd6a229c61298009246","src/scale_factor.rs":"df6dbd1f0f9f63210b92809f84a383dad982a74f09789cf22c7d8f9b62199d39","src/side_offsets.rs":"f85526a421ffda63ff01a3478d4162c8717eef68e942acfa2fd9a1adee02ebb2","src/size.rs":"ef95a114f389a357ef940f42789e2cdbdbbdf4ae6993a80a74cc2c9d10c891c9","src/trig.rs":"6b207980052d13c625272f2a70a22f7741b59513c2a4882385926f497c763a63"},"package":"34559b159306de36203986eff799f83ef2bfb301a29fad333883f1a74a4cc6b0"}
\ No newline at end of file
+{"files":{".cargo-ok":"e3b0c44298fc1c149afbf4c8996fb92427ae41e4649b934ca495991b7852b855",".gitignore":"118514fd9c4958df0d25584cda4917186c46011569f55ef350530c1ad3fbdb48",".travis.yml":"13d3e5a7bf83b04c8e8cfa14f0297bd8366d68391d977dd547f64707dffc275a","COPYRIGHT":"ec82b96487e9e778ee610c7ab245162464782cfa1f555c2299333f8dbe5c036a","Cargo.toml":"10cfe5580ee83ae883a60d96f504dda8ae7885ae5fd3a3faf95c2a2b8b38fad0","LICENSE-APACHE":"a60eea817514531668d7e00765731449fe14d059d3249e0bc93b36de45f759f2","LICENSE-MIT":"62065228e42caebca7e7d7db1204cbb867033de5982ca4009928915e4095f3a3","README.md":"52f974f01c1e15182413e4321c8817d5e66fe4d92c5ec223c857dd0440f5c229","src/approxeq.rs":"2987e046c90d948b6c7d7ddba52d10c8b7520d71dc0a50dbe7665de128d7410e","src/length.rs":"d7c6369f2fe2a17c845b57749bd48c471159f0571a7314d3bf90737d53f697d3","src/lib.rs":"e2e621f05304278d020429d0349acf7a4e7c7a9a72bd23fc0e55680267472ee9","src/macros.rs":"b63dabdb52df84ea170dc1dab5fe8d7a78c054562d1566bab416124708d2d7af","src/matrix2d.rs":"2361338f59813adf4eebaab76e4dd82be0fbfb9ff2461da8dd9ac9d43583b322","src/matrix4d.rs":"b8547bed6108b037192021c97169c00ad456120b849e9b7ac7bec40363edaec1","src/num.rs":"62286aa642ce3afa7ebd950f50bf2197d8722907f2e23a2e2ea6690484d8b250","src/point.rs":"53f3c9018c822e0a6dc5018005e153775479f41fe55c082d0be10f331fda773f","src/rect.rs":"db62b3af8939529509ae21b3bf6ae498d73a95b4ff3a6eba4db614be08e95f8b","src/scale_factor.rs":"df6dbd1f0f9f63210b92809f84a383dad982a74f09789cf22c7d8f9b62199d39","src/side_offsets.rs":"f85526a421ffda63ff01a3478d4162c8717eef68e942acfa2fd9a1adee02ebb2","src/size.rs":"19d1c08f678d793c6eff49a44f69e5b7179e574aa9b81fb4e73210733af38718","src/trig.rs":"6b207980052d13c625272f2a70a22f7741b59513c2a4882385926f497c763a63"},"package":"f5517462c626a893f3b027615e88d7102cc6dd3f7f1bcb90c7220fb1da4970b5"}
\ No newline at end of file
--- a/third_party/rust/euclid/Cargo.toml
+++ b/third_party/rust/euclid/Cargo.toml
@@ -1,14 +1,14 @@
[package]
name = "euclid"
-version = "0.11.0"
+version = "0.11.3"
authors = ["The Servo Project Developers"]
description = "Geometry primitives"
-documentation = "http://doc.servo.org/euclid/"
+documentation = "https://docs.rs/euclid/"
repository = "https://github.com/servo/euclid"
license = "MIT / Apache-2.0"
[features]
unstable = []
[dependencies]
heapsize = "0.3"
--- a/third_party/rust/euclid/README.md
+++ b/third_party/rust/euclid/README.md
@@ -1,5 +1,5 @@
# euclid
This is a small library for geometric types.
-[Documentation](http://doc.servo.org/euclid/)
+[Documentation](https://docs.rs/euclid/)
--- a/third_party/rust/euclid/src/length.rs
+++ b/third_party/rust/euclid/src/length.rs
@@ -17,24 +17,24 @@ use serde::{Deserialize, Deserializer, S
use std::cmp::Ordering;
use std::ops::{Add, Sub, Mul, Div, Neg};
use std::ops::{AddAssign, SubAssign};
use std::marker::PhantomData;
use std::fmt;
/// A one-dimensional distance, with value represented by `T` and unit of measurement `Unit`.
///
-/// `T` can be any numeric type, for example a primitive type like u64 or f32.
+/// `T` can be any numeric type, for example a primitive type like `u64` or `f32`.
///
-/// `Unit` is not used in the representation of a Length value. It is used only at compile time
-/// to ensure that a Length stored with one unit is converted explicitly before being used in an
+/// `Unit` is not used in the representation of a `Length` value. It is used only at compile time
+/// to ensure that a `Length` stored with one unit is converted explicitly before being used in an
/// expression that requires a different unit. It may be a type without values, such as an empty
/// enum.
///
-/// You can multiply a Length by a `scale_factor::ScaleFactor` to convert it from one unit to
+/// You can multiply a `Length` by a `scale_factor::ScaleFactor` to convert it from one unit to
/// another. See the `ScaleFactor` docs for an example.
// Uncomment the derive, and remove the macro call, once heapsize gets
// PhantomData<T> support.
#[repr(C)]
#[derive(RustcDecodable, RustcEncodable)]
pub struct Length<T, Unit>(pub T, PhantomData<Unit>);
impl<T: Clone, Unit> Clone for Length<T, Unit> {
--- a/third_party/rust/euclid/src/lib.rs
+++ b/third_party/rust/euclid/src/lib.rs
@@ -7,30 +7,30 @@
// option. This file may not be copied, modified, or distributed
// except according to those terms.
#![cfg_attr(feature = "unstable", feature(asm, repr_simd, test))]
//! A collection of strongly typed math tools for computer graphics with an inclination
//! towards 2d graphics and layout.
//!
-//! All types are generic over the the scalar type of their component (f32, i32, etc.),
+//! All types are generic over the scalar type of their component (`f32`, `i32`, etc.),
//! and tagged with a generic Unit parameter which is useful to prevent mixing
//! values from different spaces. For example it should not be legal to translate
//! a screen-space position by a world-space vector and this can be expressed using
//! the generic Unit parameter.
//!
//! This unit system is not mandatory and all Typed* structures have an alias
//! with the default unit: `UnknownUnit`.
//! for example ```Point2D<T>``` is equivalent to ```TypedPoint2D<T, UnknownUnit>```.
//! Client code typically creates a set of aliases for each type and doesn't need
//! to deal with the specifics of typed units further. For example:
//!
-//! All euclid types are marked #[repr(C)] in order to facilitate exposing them to
-//! foreign function interfaces (provided the underlying scalar type is also repr(C)).
+//! All euclid types are marked `#[repr(C)]` in order to facilitate exposing them to
+//! foreign function interfaces (provided the underlying scalar type is also `repr(C)`).
//!
//! ```rust
//! use euclid::*;
//! pub struct ScreenSpace;
//! pub type ScreenPoint = TypedPoint2D<f32, ScreenSpace>;
//! pub type ScreenSize = TypedSize2D<f32, ScreenSpace>;
//! pub struct WorldSpace;
//! pub type WorldPoint = TypedPoint3D<f32, WorldSpace>;
@@ -89,17 +89,17 @@ mod macros;
pub mod matrix2d;
pub mod matrix4d;
pub mod num;
pub mod point;
pub mod rect;
pub mod scale_factor;
pub mod side_offsets;
pub mod size;
-mod trig;
+pub mod trig;
/// The default unit.
#[derive(Clone, Copy, RustcDecodable, RustcEncodable)]
pub struct UnknownUnit;
/// Unit for angles in radians.
pub struct Rad;
--- a/third_party/rust/euclid/src/matrix2d.rs
+++ b/third_party/rust/euclid/src/matrix2d.rs
@@ -18,23 +18,23 @@ use trig::Trig;
use std::fmt;
define_matrix! {
/// A 2d transform stored as a 2 by 3 matrix in row-major order in memory,
/// useful to represent 2d transformations.
///
/// Matrices can be parametrized over the source and destination units, to describe a
/// transformation from a space to another.
- /// For example, TypedMatrix2D<f32, WordSpace, ScreenSpace>::transform_point4d
- /// takes a TypedPoint2D<f32, WordSpace> and returns a TypedPoint2D<f32, ScreenSpace>.
+ /// For example, `TypedMatrix2D<f32, WordSpace, ScreenSpace>::transform_point4d`
+ /// takes a `TypedPoint2D<f32, WordSpace>` and returns a `TypedPoint2D<f32, ScreenSpace>`.
///
/// Matrices expose a set of convenience methods for pre- and post-transformations.
/// A pre-transformation corresponds to adding an operation that is applied before
/// the rest of the transformation, while a post-transformation adds an operation
- /// that is appled after.
+ /// that is applied after.
pub struct TypedMatrix2D<T, Src, Dst> {
pub m11: T, pub m12: T,
pub m21: T, pub m22: T,
pub m31: T, pub m32: T,
}
}
/// The default 2d matrix type with no units.
--- a/third_party/rust/euclid/src/matrix4d.rs
+++ b/third_party/rust/euclid/src/matrix4d.rs
@@ -20,23 +20,23 @@ use std::marker::PhantomData;
use std::fmt;
define_matrix! {
/// A 4 by 4 matrix stored in row-major order in memory, useful to represent
/// 3d transformations.
///
/// Matrices can be parametrized over the source and destination units, to describe a
/// transformation from a space to another.
- /// For example, TypedMatrix4D<f32, WordSpace, ScreenSpace>::transform_point4d
- /// takes a TypedPoint4D<f32, WordSpace> and returns a TypedPoint4D<f32, ScreenSpace>.
+ /// For example, `TypedMatrix4D<f32, WordSpace, ScreenSpace>::transform_point4d`
+ /// takes a `TypedPoint4D<f32, WordSpace>` and returns a `TypedPoint4D<f32, ScreenSpace>`.
///
/// Matrices expose a set of convenience methods for pre- and post-transformations.
/// A pre-transformation corresponds to adding an operation that is applied before
/// the rest of the transformation, while a post-transformation adds an operation
- /// that is appled after.
+ /// that is applied after.
pub struct TypedMatrix4D<T, Src, Dst> {
pub m11: T, pub m12: T, pub m13: T, pub m14: T,
pub m21: T, pub m22: T, pub m23: T, pub m24: T,
pub m31: T, pub m32: T, pub m33: T, pub m34: T,
pub m41: T, pub m42: T, pub m43: T, pub m44: T,
}
}
--- a/third_party/rust/euclid/src/point.rs
+++ b/third_party/rust/euclid/src/point.rs
@@ -105,16 +105,26 @@ where T: Copy + Mul<T, Output=T> + Add<T
self.x * other.x + self.y * other.y
}
/// Returns the norm of the cross product [self.x, self.y, 0] x [other.x, other.y, 0]..
#[inline]
pub fn cross(self, other: TypedPoint2D<T, U>) -> T {
self.x * other.y - self.y * other.x
}
+
+ #[inline]
+ pub fn normalize(self) -> Self where T: Float + ApproxEq<T> {
+ let dot = self.dot(self);
+ if dot.approx_eq(&T::zero()) {
+ self
+ } else {
+ self / dot.sqrt()
+ }
+ }
}
impl<T: Copy + Add<T, Output=T>, U> Add for TypedPoint2D<T, U> {
type Output = TypedPoint2D<T, U>;
fn add(self, other: TypedPoint2D<T, U>) -> TypedPoint2D<T, U> {
TypedPoint2D::new(self.x + other.x, self.y + other.y)
}
}
@@ -188,85 +198,85 @@ impl<T: Copy + Div<T, Output=T>, U1, U2>
TypedPoint2D::new(self.x / scale.get(), self.y / scale.get())
}
}
impl<T: Round, U> TypedPoint2D<T, U> {
/// Rounds each component to the nearest integer value.
///
/// This behavior is preserved for negative values (unlike the basic cast).
- /// For example { -0.1, -0.8 }.round() == { 0.0, -1.0 }
+ /// For example `{ -0.1, -0.8 }.round() == { 0.0, -1.0 }`.
pub fn round(&self) -> Self {
TypedPoint2D::new(self.x.round(), self.y.round())
}
}
impl<T: Ceil, U> TypedPoint2D<T, U> {
- /// Rounds each component to the smallest integer equal or greater than the orginal value.
+ /// Rounds each component to the smallest integer equal or greater than the original value.
///
/// This behavior is preserved for negative values (unlike the basic cast).
- /// For example { -0.1, -0.8 }.ceil() == { 0.0, 0.0 }.
+ /// For example `{ -0.1, -0.8 }.ceil() == { 0.0, 0.0 }`.
pub fn ceil(&self) -> Self {
TypedPoint2D::new(self.x.ceil(), self.y.ceil())
}
}
impl<T: Floor, U> TypedPoint2D<T, U> {
- /// Rounds each component to the biggest integer equal or lower than the orginal value.
+ /// Rounds each component to the biggest integer equal or lower than the original value.
///
/// This behavior is preserved for negative values (unlike the basic cast).
- /// For example { -0.1, -0.8 }.floor() == { -1.0, -1.0 }.
+ /// For example `{ -0.1, -0.8 }.floor() == { -1.0, -1.0 }`.
pub fn floor(&self) -> Self {
TypedPoint2D::new(self.x.floor(), self.y.floor())
}
}
impl<T: NumCast + Copy, U> TypedPoint2D<T, U> {
/// Cast from one numeric representation to another, preserving the units.
///
/// When casting from floating point to integer coordinates, the decimals are truncated
/// as one would expect from a simple cast, but this behavior does not always make sense
- /// geometrically. Consider using round(), ceil or floor() before casting.
+ /// geometrically. Consider using `round()`, `ceil()` or `floor()` before casting.
pub fn cast<NewT: NumCast + Copy>(&self) -> Option<TypedPoint2D<NewT, U>> {
match (NumCast::from(self.x), NumCast::from(self.y)) {
(Some(x), Some(y)) => Some(TypedPoint2D::new(x, y)),
_ => None
}
}
// Convenience functions for common casts
- /// Cast into an f32 vector.
+ /// Cast into an `f32` point.
pub fn to_f32(&self) -> TypedPoint2D<f32, U> {
self.cast().unwrap()
}
- /// Cast into an usize point, truncating decimals if any.
+ /// Cast into an `usize` point, truncating decimals if any.
///
- /// When casting from floating point vectors, it is worth considering whether
- /// to round(), ceil() or floor() before the cast in order to obtain the desired
- /// conversion behavior.
+ /// When casting from floating point points, it is worth considering whether
+ /// to `round()`, `ceil()` or `floor()` before the cast in order to obtain
+ /// the desired conversion behavior.
pub fn to_uint(&self) -> TypedPoint2D<usize, U> {
self.cast().unwrap()
}
/// Cast into an i32 point, truncating decimals if any.
///
- /// When casting from floating point vectors, it is worth considering whether
- /// to round(), ceil() or floor() before the cast in order to obtain the desired
- /// conversion behavior.
+ /// When casting from floating point points, it is worth considering whether
+ /// to `round()`, `ceil()` or `floor()` before the cast in order to obtain
+ /// the desired conversion behavior.
pub fn to_i32(&self) -> TypedPoint2D<i32, U> {
self.cast().unwrap()
}
/// Cast into an i64 point, truncating decimals if any.
///
- /// When casting from floating point vectors, it is worth considering whether
- /// to round(), ceil() or floor() before the cast in order to obtain the desired
- /// conversion behavior.
+ /// When casting from floating point points, it is worth considering whether
+ /// to `round()`, `ceil()` or `floor()` before the cast in order to obtain
+ /// the desired conversion behavior.
pub fn to_i64(&self) -> TypedPoint2D<i64, U> {
self.cast().unwrap()
}
}
impl<T: Copy+ApproxEq<T>, U> ApproxEq<TypedPoint2D<T, U>> for TypedPoint2D<T, U> {
#[inline]
fn approx_epsilon() -> Self {
@@ -381,16 +391,26 @@ impl<T: Mul<T, Output=T> +
// Cross product.
#[inline]
pub fn cross(self, other: TypedPoint3D<T, U>) -> TypedPoint3D<T, U> {
TypedPoint3D::new(self.y * other.z - self.z * other.y,
self.z * other.x - self.x * other.z,
self.x * other.y - self.y * other.x)
}
+
+ #[inline]
+ pub fn normalize(self) -> Self where T: Float + ApproxEq<T> {
+ let dot = self.dot(self);
+ if dot.approx_eq(&T::zero()) {
+ self
+ } else {
+ self / dot.sqrt()
+ }
+ }
}
impl<T: Copy + Add<T, Output=T>, U> Add for TypedPoint3D<T, U> {
type Output = TypedPoint3D<T, U>;
fn add(self, other: TypedPoint3D<T, U>) -> TypedPoint3D<T, U> {
TypedPoint3D::new(self.x + other.x,
self.y + other.y,
self.z + other.z)
@@ -409,16 +429,32 @@ impl<T: Copy + Sub<T, Output=T>, U> Sub
impl <T: Copy + Neg<Output=T>, U> Neg for TypedPoint3D<T, U> {
type Output = TypedPoint3D<T, U>;
#[inline]
fn neg(self) -> TypedPoint3D<T, U> {
TypedPoint3D::new(-self.x, -self.y, -self.z)
}
}
+impl<T: Copy + Mul<T, Output=T>, U> Mul<T> for TypedPoint3D<T, U> {
+ type Output = Self;
+ #[inline]
+ fn mul(self, scale: T) -> Self {
+ Self::new(self.x * scale, self.y * scale, self.z * scale)
+ }
+}
+
+impl<T: Copy + Div<T, Output=T>, U> Div<T> for TypedPoint3D<T, U> {
+ type Output = Self;
+ #[inline]
+ fn div(self, scale: T) -> Self {
+ Self::new(self.x / scale, self.y / scale, self.z / scale)
+ }
+}
+
impl<T: Float, U> TypedPoint3D<T, U> {
pub fn min(self, other: TypedPoint3D<T, U>) -> TypedPoint3D<T, U> {
TypedPoint3D::new(self.x.min(other.x),
self.y.min(other.y),
self.z.min(other.z))
}
pub fn max(self, other: TypedPoint3D<T, U>) -> TypedPoint3D<T, U> {
@@ -432,26 +468,26 @@ impl<T: Round, U> TypedPoint3D<T, U> {
///
/// This behavior is preserved for negative values (unlike the basic cast).
pub fn round(&self) -> Self {
TypedPoint3D::new(self.x.round(), self.y.round(), self.z.round())
}
}
impl<T: Ceil, U> TypedPoint3D<T, U> {
- /// Rounds each component to the smallest integer equal or greater than the orginal value.
+ /// Rounds each component to the smallest integer equal or greater than the original value.
///
/// This behavior is preserved for negative values (unlike the basic cast).
pub fn ceil(&self) -> Self {
TypedPoint3D::new(self.x.ceil(), self.y.ceil(), self.z.ceil())
}
}
impl<T: Floor, U> TypedPoint3D<T, U> {
- /// Rounds each component to the biggest integer equal or lower than the orginal value.
+ /// Rounds each component to the biggest integer equal or lower than the original value.
///
/// This behavior is preserved for negative values (unlike the basic cast).
pub fn floor(&self) -> Self {
TypedPoint3D::new(self.x.floor(), self.y.floor(), self.z.floor())
}
}
impl<T: NumCast + Copy, U> TypedPoint3D<T, U> {
@@ -466,44 +502,44 @@ impl<T: NumCast + Copy, U> TypedPoint3D<
NumCast::from(self.z)) {
(Some(x), Some(y), Some(z)) => Some(TypedPoint3D::new(x, y, z)),
_ => None
}
}
// Convenience functions for common casts
- /// Cast into an f32 vector.
+ /// Cast into an `f32` point.
pub fn to_f32(&self) -> TypedPoint3D<f32, U> {
self.cast().unwrap()
}
- /// Cast into an usize point, truncating decimals if any.
+ /// Cast into an `usize` point, truncating decimals if any.
///
- /// When casting from floating point vectors, it is worth considering whether
- /// to round(), ceil() or floor() before the cast in order to obtain the desired
- /// conversion behavior.
+ /// When casting from floating point points, it is worth considering whether
+ /// to `round()`, `ceil()` or `floor()` before the cast in order to obtain
+ /// the desired conversion behavior.
pub fn to_uint(&self) -> TypedPoint3D<usize, U> {
self.cast().unwrap()
}
- /// Cast into an i32 point, truncating decimals if any.
+ /// Cast into an `i32` point, truncating decimals if any.
///
- /// When casting from floating point vectors, it is worth considering whether
- /// to round(), ceil() or floor() before the cast in order to obtain the desired
- /// conversion behavior.
+ /// When casting from floating point points, it is worth considering whether
+ /// to `round()`, `ceil()` or `floor()` before the cast in order to obtain
+ /// the desired conversion behavior.
pub fn to_i32(&self) -> TypedPoint3D<i32, U> {
self.cast().unwrap()
}
- /// Cast into an i64 point, truncating decimals if any.
+ /// Cast into an `i64` point, truncating decimals if any.
///
- /// When casting from floating point vectors, it is worth considering whether
- /// to round(), ceil() or floor() before the cast in order to obtain the desired
- /// conversion behavior.
+ /// When casting from floating point points, it is worth considering whether
+ /// to `round()`, `ceil()` or `floor()` before the cast in order to obtain
+ /// the desired conversion behavior.
pub fn to_i64(&self) -> TypedPoint3D<i64, U> {
self.cast().unwrap()
}
}
impl<T: Copy+ApproxEq<T>, U> ApproxEq<TypedPoint3D<T, U>> for TypedPoint3D<T, U> {
#[inline]
fn approx_epsilon() -> Self {
@@ -670,79 +706,79 @@ impl<T: Round, U> TypedPoint4D<T, U> {
///
/// This behavior is preserved for negative values (unlike the basic cast).
pub fn round(&self) -> Self {
TypedPoint4D::new(self.x.round(), self.y.round(), self.z.round(), self.w.round())
}
}
impl<T: Ceil, U> TypedPoint4D<T, U> {
- /// Rounds each component to the smallest integer equal or greater than the orginal value.
+ /// Rounds each component to the smallest integer equal or greater than the original value.
///
/// This behavior is preserved for negative values (unlike the basic cast).
pub fn ceil(&self) -> Self {
TypedPoint4D::new(self.x.ceil(), self.y.ceil(), self.z.ceil(), self.w.ceil())
}
}
impl<T: Floor, U> TypedPoint4D<T, U> {
- /// Rounds each component to the biggest integer equal or lower than the orginal value.
+ /// Rounds each component to the biggest integer equal or lower than the original value.
///
/// This behavior is preserved for negative values (unlike the basic cast).
pub fn floor(&self) -> Self {
TypedPoint4D::new(self.x.floor(), self.y.floor(), self.z.floor(), self.w.floor())
}
}
impl<T: NumCast + Copy, U> TypedPoint4D<T, U> {
/// Cast from one numeric representation to another, preserving the units.
///
/// When casting from floating point to integer coordinates, the decimals are truncated
/// as one would expect from a simple cast, but this behavior does not always make sense
- /// geometrically. Consider using round(), ceil or floor() before casting.
+ /// geometrically. Consider using `round()`, `ceil()` or `floor()` before casting.
pub fn cast<NewT: NumCast + Copy>(&self) -> Option<TypedPoint4D<NewT, U>> {
match (NumCast::from(self.x),
NumCast::from(self.y),
NumCast::from(self.z),
NumCast::from(self.w)) {
(Some(x), Some(y), Some(z), Some(w)) => Some(TypedPoint4D::new(x, y, z, w)),
_ => None
}
}
// Convenience functions for common casts
- /// Cast into an f32 vector.
+ /// Cast into an `f32` point.
pub fn to_f32(&self) -> TypedPoint4D<f32, U> {
self.cast().unwrap()
}
- /// Cast into an usize point, truncating decimals if any.
+ /// Cast into an `usize` point, truncating decimals if any.
///
- /// When casting from floating point vectors, it is worth considering whether
- /// to round(), ceil() or floor() before the cast in order to obtain the desired
- /// conversion behavior.
+ /// When casting from floating point points, it is worth considering whether
+ /// to `round()`, `ceil()` or `floor()` before the cast in order to obtain
+ /// the desired conversion behavior.
pub fn to_uint(&self) -> TypedPoint4D<usize, U> {
self.cast().unwrap()
}
- /// Cast into an i32 point, truncating decimals if any.
+ /// Cast into an `i32` point, truncating decimals if any.
///
- /// When casting from floating point vectors, it is worth considering whether
- /// to round(), ceil() or floor() before the cast in order to obtain the desired
- /// conversion behavior.
+ /// When casting from floating point points, it is worth considering whether
+ /// to `round()`, `ceil()` or `floor()` before the cast in order to obtain
+ /// the desired conversion behavior.
pub fn to_i32(&self) -> TypedPoint4D<i32, U> {
self.cast().unwrap()
}
- /// Cast into an i64 point, truncating decimals if any.
+ /// Cast into an `i64` point, truncating decimals if any.
///
- /// When casting from floating point vectors, it is worth considering whether
- /// to round(), ceil() or floor() before the cast in order to obtain the desired
- /// conversion behavior.
+ /// When casting from floating point points, it is worth considering whether
+ /// to `round()`, `ceil()` or `floor()` before the cast in order to obtain
+ /// the desired conversion behavior.
pub fn to_i64(&self) -> TypedPoint4D<i64, U> {
self.cast().unwrap()
}
}
impl<T: ApproxEq<T>, U> ApproxEq<T> for TypedPoint4D<T, U> {
fn approx_epsilon() -> T {
T::approx_epsilon()
@@ -796,16 +832,26 @@ mod point2d {
pub fn test_cross() {
let p1: Point2D<f32> = Point2D::new(4.0, 7.0);
let p2: Point2D<f32> = Point2D::new(13.0, 8.0);
let r = p1.cross(p2);
assert_eq!(r, -59.0);
}
#[test]
+ pub fn test_normalize() {
+ let p0: Point2D<f32> = Point2D::zero();
+ let p1: Point2D<f32> = Point2D::new(4.0, 0.0);
+ let p2: Point2D<f32> = Point2D::new(3.0, -4.0);
+ assert_eq!(p0.normalize(), p0);
+ assert_eq!(p1.normalize(), Point2D::new(1.0, 0.0));
+ assert_eq!(p2.normalize(), Point2D::new(0.6, -0.8));
+ }
+
+ #[test]
pub fn test_min() {
let p1 = Point2D::new(1.0, 3.0);
let p2 = Point2D::new(2.0, 2.0);
let result = p1.min(p2);
assert_eq!(result, Point2D::new(1.0, 2.0));
}
@@ -868,16 +914,26 @@ mod point3d {
pub fn test_cross() {
let p1 = Point3D::new(4.0, 7.0, 9.0);
let p2 = Point3D::new(13.0, 8.0, 3.0);
let p3 = p1.cross(p2);
assert_eq!(p3, Point3D::new(-51.0, 105.0, -59.0));
}
#[test]
+ pub fn test_normalize() {
+ let p0: Point3D<f32> = Point3D::zero();
+ let p1: Point3D<f32> = Point3D::new(0.0, -6.0, 0.0);
+ let p2: Point3D<f32> = Point3D::new(1.0, 2.0, -2.0);
+ assert_eq!(p0.normalize(), p0);
+ assert_eq!(p1.normalize(), Point3D::new(0.0, -1.0, 0.0));
+ assert_eq!(p2.normalize(), Point3D::new(1.0/3.0, 2.0/3.0, -2.0/3.0));
+ }
+
+ #[test]
pub fn test_min() {
let p1 = Point3D::new(1.0, 3.0, 5.0);
let p2 = Point3D::new(2.0, 2.0, -1.0);
let result = p1.min(p2);
assert_eq!(result, Point3D::new(1.0, 2.0, -1.0));
}
--- a/third_party/rust/euclid/src/rect.rs
+++ b/third_party/rust/euclid/src/rect.rs
@@ -389,50 +389,50 @@ impl<T: Floor + Ceil + Round + Add<T, Ou
let origin = self.origin.floor();
let size = self.origin.add_size(&self.size).ceil() - origin;
TypedRect::new(origin, TypedSize2D::new(size.x, size.y))
}
}
// Convenience functions for common casts
impl<T: NumCast + Copy, Unit> TypedRect<T, Unit> {
- /// Cast into an f32 vector.
+ /// Cast into an `f32` rectangle.
pub fn to_f32(&self) -> TypedRect<f32, Unit> {
self.cast().unwrap()
}
- /// Cast into an usize vector, truncating decimals if any.
+ /// Cast into an `usize` rectangle, truncating decimals if any.
///
- /// When casting from floating point vectors, it is worth considering whether
- /// to round(), round_in() or round_out() before the cast in order to obtain the desired
- /// conversion behavior.
+ /// When casting from floating point rectangles, it is worth considering whether
+ /// to `round()`, `round_in()` or `round_out()` before the cast in order to
+ /// obtain the desired conversion behavior.
pub fn to_uint(&self) -> TypedRect<usize, Unit> {
self.cast().unwrap()
}
- /// Cast into an i32 vector, truncating decimals if any.
+ /// Cast into an `i32` rectangle, truncating decimals if any.
///
- /// When casting from floating point vectors, it is worth considering whether
- /// to round(), round_in() or round_out() before the cast in order to obtain the desired
- /// conversion behavior.
+ /// When casting from floating point rectangles, it is worth considering whether
+ /// to `round()`, `round_in()` or `round_out()` before the cast in order to
+ /// obtain the desired conversion behavior.
pub fn to_i32(&self) -> TypedRect<i32, Unit> {
self.cast().unwrap()
}
- /// Cast into an i64 vector, truncating decimals if any.
+ /// Cast into an `i64` rectangle, truncating decimals if any.
///
- /// When casting from floating point vectors, it is worth considering whether
- /// to round(), round_in() or round_out() before the cast in order to obtain the desired
- /// conversion behavior.
+ /// When casting from floating point rectangles, it is worth considering whether
+ /// to `round()`, `round_in()` or `round_out()` before the cast in order to
+ /// obtain the desired conversion behavior.
pub fn to_i64(&self) -> TypedRect<i64, Unit> {
self.cast().unwrap()
}
}
-/// Shorthand for TypedRect::new(TypedPoint2D::new(x, y), TypedSize2D::new(w, h)).
+/// Shorthand for `TypedRect::new(TypedPoint2D::new(x, y), TypedSize2D::new(w, h))`.
pub fn rect<T: Copy, U>(x: T, y: T, w: T, h: T) -> TypedRect<T, U> {
TypedRect::new(TypedPoint2D::new(x, y), TypedSize2D::new(w, h))
}
#[cfg(test)]
mod tests {
use point::Point2D;
use size::Size2D;
--- a/third_party/rust/euclid/src/size.rs
+++ b/third_party/rust/euclid/src/size.rs
@@ -50,42 +50,42 @@ impl<T, U> TypedSize2D<T, U> {
width: width,
height: height,
_unit: PhantomData,
}
}
}
impl<T: Clone, U> TypedSize2D<T, U> {
- /// Constructor taking scalar stronlgy typed lengths.
+ /// Constructor taking scalar strongly typed lengths.
pub fn from_lengths(width: Length<T, U>, height: Length<T, U>) -> TypedSize2D<T, U> {
TypedSize2D::new(width.get(), height.get())
}
}
impl<T: Round, U> TypedSize2D<T, U> {
/// Rounds each component to the nearest integer value.
///
/// This behavior is preserved for negative values (unlike the basic cast).
pub fn round(&self) -> Self {
TypedSize2D::new(self.width.round(), self.height.round())
}
}
impl<T: Ceil, U> TypedSize2D<T, U> {
- /// Rounds each component to the smallest integer equal or greater than the orginal value.
+ /// Rounds each component to the smallest integer equal or greater than the original value.
///
/// This behavior is preserved for negative values (unlike the basic cast).
pub fn ceil(&self) -> Self {
TypedSize2D::new(self.width.ceil(), self.height.ceil())
}
}
impl<T: Floor, U> TypedSize2D<T, U> {
- /// Rounds each component to the biggest integer equal or lower than the orginal value.
+ /// Rounds each component to the biggest integer equal or lower than the original value.
///
/// This behavior is preserved for negative values (unlike the basic cast).
pub fn floor(&self) -> Self {
TypedSize2D::new(self.width.floor(), self.height.floor())
}
}
impl<T: Copy + Add<T, Output=T>, U> Add for TypedSize2D<T, U> {
@@ -178,61 +178,61 @@ impl<T: Copy, U> TypedSize2D<T, U> {
TypedSize2D::new(p.width, p.height)
}
}
impl<T: NumCast + Copy, Unit> TypedSize2D<T, Unit> {
/// Cast from one numeric representation to another, preserving the units.
///
/// When casting from floating point to integer coordinates, the decimals are truncated
- /// as one would expect from a simple cast, but this behavior does not always marke sense
- /// geometrically. Consider using round(), ceil or floor() before casting.
+ /// as one would expect from a simple cast, but this behavior does not always make sense
+ /// geometrically. Consider using `round()`, `ceil()` or `floor()` before casting.
pub fn cast<NewT: NumCast + Copy>(&self) -> Option<TypedSize2D<NewT, Unit>> {
match (NumCast::from(self.width), NumCast::from(self.height)) {
(Some(w), Some(h)) => Some(TypedSize2D::new(w, h)),
_ => None
}
}
// Convenience functions for common casts
- /// Cast into an f32 size.
+ /// Cast into an `f32` size.
pub fn to_f32(&self) -> TypedSize2D<f32, Unit> {
self.cast().unwrap()
}
- /// Cast into an usize size, truncating decimals if any.
+ /// Cast into an `uint` size, truncating decimals if any.
///
/// When casting from floating point sizes, it is worth considering whether
- /// to round(), ceil() or floor() before the cast in order to obtain the desired
- /// conversion behavior.
+ /// to `round()`, `ceil()` or `floor()` before the cast in order to obtain
+ /// the desired conversion behavior.
pub fn to_uint(&self) -> TypedSize2D<usize, Unit> {
self.cast().unwrap()
}
- /// Cast into an i32 size, truncating decimals if any.
+ /// Cast into an `i32` size, truncating decimals if any.
///
/// When casting from floating point sizes, it is worth considering whether
- /// to round(), ceil() or floor() before the cast in order to obtain the desired
- /// conversion behavior.
+ /// to `round()`, `ceil()` or `floor()` before the cast in order to obtain
+ /// the desired conversion behavior.
pub fn to_i32(&self) -> TypedSize2D<i32, Unit> {
self.cast().unwrap()
}
- /// Cast into an i64 size, truncating decimals if any.
+ /// Cast into an `i64` size, truncating decimals if any.
///
/// When casting from floating point sizes, it is worth considering whether
- /// to round(), ceil() or floor() before the cast in order to obtain the desired
- /// conversion behavior.
+ /// to `round()`, `ceil()` or `floor()` before the cast in order to obtain
+ /// the desired conversion behavior.
pub fn to_i64(&self) -> TypedSize2D<i64, Unit> {
self.cast().unwrap()
}
}
-/// Shorthand for TypedSize2D::new(w, h).
+/// Shorthand for `TypedSize2D::new(w, h)`.
pub fn size2<T, U>(w: T, h: T) -> TypedSize2D<T, U> {
TypedSize2D::new(w, h)
}
#[cfg(test)]
mod size2d {
use super::Size2D;
new file mode 100644
--- /dev/null
+++ b/third_party/rust/plane-split/.cargo-checksum.json
@@ -0,0 +1,1 @@
+{"files":{".cargo-ok":"e3b0c44298fc1c149afbf4c8996fb92427ae41e4649b934ca495991b7852b855",".gitignore":"f9b1ca6ae27d1c18215265024629a8960c31379f206d9ed20f64e0b2dcf79805",".travis.yml":"b76d49f66f842c652d40825c67791352364a6b6bbb7d8d1009f2ac79eb413e66","Cargo.toml":"b7991659a5ad212104ef390baee63066645a20af5b7d0891bd9166b38cab1f7d","LICENSE":"b946744aeda89b467929585fe8eeb5461847695220c1b168fb375d8abd4ea3d0","README.md":"62f99334c17b451342fcea70eb1cc27b26612616b7c1a58fab50dd493f766f32","benches/split.rs":"49befe22321f34280106fdea53d93644b7757873407376247f86f9d55d09b4ab","src/bsp.rs":"6ec056292b3499f16ad520af7b0480471e34c136bb29429c3c4e1d68efd42a57","src/lib.rs":"368c320c9d4f4bb788b3fb5c0b0e0a6b9756d0da02035539e845639ab9bff80e","src/naive.rs":"8c0e93fcdc30e90fa9da4a032a55fe58619e8e8928000583575eb2f3e001e331","tests/main.rs":"7177353c68b31a78cda67da0485b45d8551961b36e23121d549aa535e68dd287","tests/split.rs":"a4681a788f9a9a515d4084d97ba33406a54bc0725711ade9fc955348d1703368"},"package":"a05e1e40e37630095627acfd2c7c6cf259e8b4f4ef4f01b2adf2a35331e45975"}
\ No newline at end of file
new file mode 100644
--- /dev/null
+++ b/third_party/rust/plane-split/.gitignore
@@ -0,0 +1,2 @@
+target
+Cargo.lock
new file mode 100644
--- /dev/null
+++ b/third_party/rust/plane-split/.travis.yml
@@ -0,0 +1,11 @@
+sudo: false
+language: rust
+cache: cargo
+rust:
+ - nightly
+ - stable
+script:
+ - cargo build
+ - cargo doc
+ - cargo test
+ - if [ "$TRAVIS_RUST_VERSION" == "nightly" ]; then (cargo bench); fi
new file mode 100644
--- /dev/null
+++ b/third_party/rust/plane-split/Cargo.toml
@@ -0,0 +1,15 @@
+[package]
+name = "plane-split"
+version = "0.2.1"
+description = "Plane splitting"
+authors = ["Dzmitry Malyshau <kvark@mozilla.com>"]
+license = "MPL-2.0"
+repository = "https://github.com/kvark/plane-split"
+keywords = ["geometry", "math"]
+documentation = "https://docs.rs/plane-split"
+
+[dependencies]
+binary-space-partition = "0.1.1"
+euclid = "0.11.2"
+log = "0.3"
+num-traits = {version = "0.1.37", default-features = false}
new file mode 100644
--- /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.
+
new file mode 100644
--- /dev/null
+++ b/third_party/rust/plane-split/README.md
@@ -0,0 +1,4 @@
+# plane-split
+[](https://travis-ci.org/kvark/plane-split) [](https://crates.io/crates/plane-split) [](https://docs.rs/plane-split)
+
+Plane splitting with [euclid](https://crates.io/crates/euclid).
new file mode 100644
--- /dev/null
+++ b/third_party/rust/plane-split/benches/split.rs
@@ -0,0 +1,31 @@
+#![feature(test)]
+
+extern crate euclid;
+extern crate plane_split;
+extern crate test;
+
+use std::sync::Arc;
+use euclid::TypedPoint3D;
+use plane_split::{BspSplitter, NaiveSplitter, Splitter, _make_grid};
+
+#[bench]
+fn bench_naive(b: &mut test::Bencher) {
+ let polys = Arc::new(_make_grid(5));
+ let mut splitter = NaiveSplitter::new();
+ let view = TypedPoint3D::new(0.0, 0.0, 1.0);
+ b.iter(|| {
+ let p = polys.clone();
+ splitter.solve(&p, view);
+ });
+}
+
+#[bench]
+fn bench_bsp(b: &mut test::Bencher) {
+ let polys = Arc::new(_make_grid(5));
+ let mut splitter = BspSplitter::new();
+ let view = TypedPoint3D::new(0.0, 0.0, 1.0);
+ b.iter(|| {
+ let p = polys.clone();
+ splitter.solve(&p, view);
+ });
+}
new file mode 100644
--- /dev/null
+++ b/third_party/rust/plane-split/src/bsp.rs
@@ -0,0 +1,101 @@
+use binary_space_partition::{BspNode, Plane, PlaneCut};
+use euclid::TypedPoint3D;
+use euclid::approxeq::ApproxEq;
+use num_traits::{Float, One, Zero};
+use std::{fmt, ops};
+use {Intersection, Polygon, Splitter};
+
+
+impl<T: Copy + fmt::Debug + PartialOrd + ApproxEq<T> +
+ ops::Sub<T, Output=T> + ops::Add<T, Output=T> +
+ ops::Mul<T, Output=T> + ops::Div<T, Output=T> +
+ Zero + One + Float,
+ U> Plane for Polygon<T, U> {
+
+ fn cut(&self, mut plane: Self) -> PlaneCut<Self> {
+ let dist = self.signed_distance_sum_to(&plane);
+ match self.intersect(&plane) {
+ Intersection::Coplanar if dist.approx_eq(&T::zero()) => {
+ PlaneCut::Sibling(plane)
+ }
+ Intersection::Coplanar | Intersection::Outside => {
+ if dist > T::zero() {
+ PlaneCut::Cut {
+ front: vec![plane],
+ back: vec![],
+ }
+ } else {
+ PlaneCut::Cut {
+ front: vec![],
+ back: vec![plane],
+ }
+ }
+ }
+ Intersection::Inside(line) => {
+ let (res_add1, res_add2) = plane.split(&line);
+ let mut front = Vec::new();
+ let mut back = Vec::new();
+
+ for sub in Some(plane).into_iter().chain(res_add1).chain(res_add2) {
+ if self.signed_distance_sum_to(&sub) > T::zero() {
+ front.push(sub)
+ } else {
+ back.push(sub)
+ }
+ }
+
+ PlaneCut::Cut {
+ front: front,
+ back: back,
+ }
+ },
+ }
+ }
+
+ fn is_aligned(&self, plane: &Self) -> bool {
+ self.normal.dot(plane.normal) > T::zero()
+ }
+}
+
+
+/// Binary Space Partitioning splitter, uses a BSP tree.
+pub struct BspSplitter<T, U> {
+ tree: BspNode<Polygon<T, U>>,
+ result: Vec<Polygon<T, U>>,
+}
+
+impl<T, U> BspSplitter<T, U> {
+ /// Create a new BSP splitter.
+ pub fn new() -> Self {
+ BspSplitter {
+ tree: BspNode::new(),
+ result: Vec::new(),
+ }
+ }
+}
+
+impl<T: Copy + fmt::Debug + PartialOrd + ApproxEq<T> +
+ ops::Sub<T, Output=T> + ops::Add<T, Output=T> +
+ ops::Mul<T, Output=T> + ops::Div<T, Output=T> +
+ Zero + One + Float,
+ U> Splitter<T, U> for BspSplitter<T, U> {
+
+ fn reset(&mut self) {
+ self.tree = BspNode::new();
+ }
+
+ fn add(&mut self, poly: Polygon<T, U>) {
+ self.tree.insert(poly);
+ }
+
+ fn sort(&mut self, view: TypedPoint3D<T, U>) -> &[Polygon<T, U>] {
+ let poly = Polygon {
+ points: [TypedPoint3D::zero(); 4],
+ normal: view,
+ offset: T::zero(),
+ anchor: 0,
+ };
+ self.tree.order(&poly, &mut self.result);
+ &self.result
+ }
+}
new file mode 100644
--- /dev/null
+++ b/third_party/rust/plane-split/src/lib.rs
@@ -0,0 +1,483 @@
+/*!
+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)]
+
+extern crate binary_space_partition;
+extern crate euclid;
+#[macro_use]
+extern crate log;
+extern crate num_traits;
+
+mod bsp;
+mod naive;
+
+use std::{fmt, mem, ops};
+use euclid::{Point2D, TypedMatrix4D, TypedPoint3D, TypedRect};
+use euclid::approxeq::ApproxEq;
+use euclid::trig::Trig;
+use num_traits::{Float, One, Zero};
+
+pub use self::bsp::BspSplitter;
+pub use self::naive::NaiveSplitter;
+
+/// A generic line.
+#[derive(Debug)]
+pub struct Line<T, U> {
+ /// Arbitrary point on the line.
+ pub origin: TypedPoint3D<T, U>,
+ /// Normalized direction of the line.
+ pub dir: TypedPoint3D<T, U>,
+}
+
+impl<
+ T: Copy + One + Zero + PartialEq + ApproxEq<T> +
+ ops::Add<T, Output=T> + ops::Sub<T, Output=T> + ops::Mul<T, Output=T>,
+ U,
+> Line<T, U> {
+ /// Check if the line has consistent parameters.
+ pub fn is_valid(&self) -> bool {
+ self.dir.dot(self.dir).approx_eq(&T::one())
+ }
+ /// Check if two lines match each other.
+ pub fn matches(&self, other: &Self) -> bool {
+ let diff = self.origin - other.origin;
+ let zero = TypedPoint3D::zero();
+ self.dir.cross(other.dir).approx_eq(&zero) &&
+ self.dir.cross(diff).approx_eq(&zero)
+ }
+}
+
+/// A convex flat polygon with 4 points, defined by equation:
+/// dot(v, normal) + offset = 0
+#[derive(Debug, PartialEq)]
+pub struct Polygon<T, U> {
+ /// Points making the polygon.
+ pub points: [TypedPoint3D<T, U>; 4],
+ /// Normalized vector perpendicular to the polygon plane.
+ pub normal: TypedPoint3D<T, U>,
+ /// Constant offset from the normal plane, specified in the
+ /// direction opposite to the normal.
+ pub offset: T,
+ /// A simple anchoring index to allow association of the
+ /// produced split polygons with the original one.
+ pub anchor: usize,
+}
+
+impl<T: Clone, U> Clone for Polygon<T, U> {
+ fn clone(&self) -> Self {
+ Polygon {
+ points: [self.points[0].clone(),
+ self.points[1].clone(),
+ self.points[2].clone(),
+ self.points[3].clone()],
+ normal: self.normal.clone(),
+ offset: self.offset.clone(),
+ anchor: self.anchor,
+ }
+ }
+}
+
+/// The projection of a `Polygon` on a line.
+pub struct LineProjection<T> {
+ /// Projected value of each point in the polygon.
+ pub markers: [T; 4],
+}
+
+impl<T: Copy + PartialOrd + ops::Sub<T, Output=T> + ops::Add<T, Output=T>> LineProjection<T> {
+ /// Get the min/max of the line projection markers.
+ pub fn get_bounds(&self) -> (T, T) {
+ 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
+ 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,
+ }
+ }
+}
+
+impl<T: Copy + fmt::Debug + PartialOrd + ApproxEq<T> +
+ ops::Sub<T, Output=T> + ops::Add<T, Output=T> +
+ ops::Mul<T, Output=T> + ops::Div<T, Output=T> +
+ Zero + One + Float,
+ U> Polygon<T, U> {
+
+ /// Construct a polygon from a transformed rectangle.
+ pub fn from_transformed_rect<V>(rect: TypedRect<T, V>,
+ transform: TypedMatrix4D<T, V, U>,
+ anchor: usize)
+ -> Polygon<T, U>
+ where T: Trig + ops::Neg<Output=T> {
+ let points = [
+ transform.transform_point3d(&rect.origin.to_3d()),
+ transform.transform_point3d(&rect.top_right().to_3d()),
+ transform.transform_point3d(&rect.bottom_right().to_3d()),
+ transform.transform_point3d(&rect.bottom_left().to_3d()),
+ ];
+
+ //Note: this code path could be more efficient if we had inverse-transpose
+ //let n4 = transform.transform_point4d(&TypedPoint4D::new(T::zero(), T::zero(), T::one(), T::zero()));
+ //let normal = TypedPoint3D::new(n4.x, n4.y, n4.z);
+
+ let normal = (points[1] - points[0]).cross(points[2] - points[0])
+ .normalize();
+ let offset = -TypedPoint3D::new(transform.m41, transform.m42, transform.m43).dot(normal);
+
+ Polygon {
+ points: points,
+ normal: normal,
+ offset: offset,
+ anchor: anchor,
+ }
+ }
+
+ /// Bring a point into the local coordinate space, returning
+ /// the 2D normalized coordinates.
+ pub fn untransform_point(&self, point: TypedPoint3D<T, U>) -> Point2D<T> {
+ //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
+ }
+
+ /// Return the signed distance from this polygon to a point.
+ /// The distance is negative if the point is on the other side of the polygon
+ /// from the direction of the normal.
+ pub fn signed_distance_to(&self, point: &TypedPoint3D<T, U>) -> T {
+ point.dot(self.normal) + self.offset
+ }
+
+ /// Compute the distance across the line to the polygon plane,
+ /// starting from the line origin.
+ pub fn distance_to_line(&self, line: &Line<T, U>) -> T
+ where T: ops::Neg<Output=T> {
+ self.signed_distance_to(&line.origin) / -self.normal.dot(line.dir)
+ }
+
+ /// Compute the sum of signed distances to each of the points
+ /// of another polygon. Useful to know the relation of a polygon that
+ /// is a product of a split, and we know it doesn't intersect `self`.
+ pub fn signed_distance_sum_to(&self, other: &Self) -> T {
+ other.points.iter().fold(T::zero(), |sum, p| {
+ sum + self.signed_distance_to(p)
+ })
+ }
+
+ /// Check if all the points are indeed placed on the plane defined by
+ /// the normal and offset, and the winding order is consistent.
+ /// The epsion is specified for the plane distance calculations.
+ pub fn is_valid_eps(&self, eps: T) -> bool {
+ let is_planar = self.points.iter()
+ .all(|p| self.signed_distance_to(p).approx_eq_eps(&T::zero(), &eps));
+ 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) >= T::zero());
+ is_planar && is_winding
+ }
+
+ /// Check validity. Similar to `is_valid_eps` but with default epsilon.
+ pub fn is_valid(&self) -> bool {
+ self.is_valid_eps(T::approx_epsilon())
+ }
+
+ /// Check if a convex shape defined by a set of points is completely
+ /// outside of this polygon. Merely touching the surface is not
+ /// considered an intersection.
+ pub fn are_outside(&self, points: &[TypedPoint3D<T, U>]) -> bool {
+ let d0 = self.signed_distance_to(&points[0]);
+ points[1..].iter()
+ .all(|p| self.signed_distance_to(p) * d0 > T::zero())
+ }
+
+ /// Check if this polygon contains another one.
+ pub fn contains(&self, other: &Self) -> bool {
+ //TODO: actually check for inside/outside
+ self.normal == other.normal && self.offset == other.offset
+ }
+
+ /// 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: &TypedPoint3D<T, U>) -> LineProjection<T> {
+ LineProjection {
+ markers: [
+ vector.dot(self.points[0]),
+ vector.dot(self.points[1]),
+ vector.dot(self.points[2]),
+ vector.dot(self.points[3]),
+ ],
+ }
+ }
+
+ /// Compute the line of intersection with another polygon.
+ pub fn intersect(&self, other: &Self) -> Intersection<Line<T, U>> {
+ if self.are_outside(&other.points) || other.are_outside(&self.points) {
+ // one is completely outside the other
+ return Intersection::Outside
+ }
+ let cross_dir = self.normal.cross(other.normal);
+ if cross_dir.dot(cross_dir) < T::approx_epsilon() {
+ // polygons are co-planar
+ return Intersection::Coplanar
+ }
+ let self_proj = self.project_on(&cross_dir);
+ let other_proj = other.project_on(&cross_dir);
+ if !self_proj.intersect(&other_proj) {
+ // projections on the line don't intersect
+ return Intersection::Outside
+ }
+ // 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 factor = T::one() / (T::one() - w * w);
+ let center = self.normal * ((other.offset * w - self.offset) * factor) -
+ other.normal* ((other.offset - self.offset * w) * factor);
+ Intersection::Inside(Line {
+ origin: center,
+ dir: cross_dir.normalize(),
+ })
+ }
+
+ /// Split the polygon along the specified `Line`. Will do nothing if the line
+ /// doesn't belong to the polygon plane.
+ pub fn split(&mut self, line: &Line<T, U>)
+ -> (Option<Polygon<T, U>>, Option<Polygon<T, U>>) {
+ // check if the cut is within the polygon plane first
+ if !self.normal.dot(line.dir).approx_eq(&T::zero()) ||
+ !self.signed_distance_to(&line.origin).approx_eq(&T::zero()) {
+ 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()) {
+ // intersecting line segment [a, b] with `line`
+ //a + (b-a) * t = r + k * d
+ //(a, d) + t * (b-a, d) - (r, d) = k
+ // a + t * (b-a) = r + t * (b-a, d) * d + (a-r, d) * d
+ // t * ((b-a) - (b-a, d)*d) = (r-a) - (r-a, d) * d
+ let pr = line.origin - a - line.dir * line.dir.dot(line.origin - a);
+ let pb = b - a - line.dir * line.dir.dot(b - a);
+ let denom = pb.dot(pb);
+ if !denom.approx_eq(&T::zero()) {
+ let t = pr.dot(pb) / denom;
+ if t > T::zero() && t < T::one() {
+ *cut = Some(a + (b - a) * t);
+ }
+ }
+ }
+
+ let first = match cuts.iter().position(|c| c.is_some()) {
+ Some(pos) => pos,
+ None => return (None, None),
+ };
+ let second = match cuts[first+1 ..].iter().position(|c| c.is_some()) {
+ Some(pos) => first + 1 + pos,
+ None => return (None, None),
+ };
+ //TODO: can be optimized for when the polygon has a redundant 4th vertex
+ let (a, b) = (cuts[first].unwrap(), cuts[second].unwrap());
+ match second-first {
+ 2 => {
+ let mut other_points = self.points;
+ other_points[first] = a;
+ other_points[(first+3) % 4] = b;
+ self.points[first+1] = a;
+ self.points[first+2] = b;
+ let poly = Polygon {
+ points: other_points,
+ .. self.clone()
+ };
+ (Some(poly), None)
+ }
+ 3 => {
+ let xpoints = [
+ self.points[first+1],
+ self.points[first+2],
+ self.points[first+3],
+ b];
+ let ypoints = [a, self.points[first+1], b, b];
+ self.points = [self.points[first], a, b, b];
+ let poly1 = Polygon {
+ points: xpoints,
+ .. self.clone()
+ };
+ let poly2 = Polygon {
+ points: ypoints,
+ .. self.clone()
+ };
+ (Some(poly1), Some(poly2))
+ }
+ 1 => {
+ let xpoints = [
+ b,
+ self.points[(first+2) % 4],
+ self.points[(first+3) % 4],
+ self.points[first]
+ ];
+ let ypoints = [self.points[first], a, b, b];
+ self.points = [a, self.points[first+1], b, b];
+ let poly1 = Polygon {
+ points: xpoints,
+ .. self.clone()
+ };
+ let poly2 = Polygon {
+ points: ypoints,
+ .. self.clone()
+ };
+ (Some(poly1), Some(poly2))
+ }
+ _ => panic!("Unexpected indices {} {}", first, second),
+ }
+ }
+}
+
+
+/// Generic plane splitter interface.
+pub trait Splitter<T, U> {
+ /// Reset the splitter results.
+ fn reset(&mut self);
+
+ /// Add a new polygon and return a slice of the subdivisions
+ /// that avoid collision with any of the previously added polygons.
+ fn add(&mut self, Polygon<T, U>);
+
+ /// Sort the produced polygon set by the ascending distance across
+ /// the specified view vector. Return the sorted slice.
+ fn sort(&mut self, TypedPoint3D<T, U>) -> &[Polygon<T, U>];
+
+ /// Process a set of polygons at once.
+ fn solve(&mut self, input: &[Polygon<T, U>], view: TypedPoint3D<T, U>)
+ -> &[Polygon<T, U>]
+ where T: Clone, U: Clone {
+ self.reset();
+ for p in input.iter() {
+ self.add(p.clone());
+ }
+ self.sort(view)
+ }
+}
+
+
+/// Helper method used for benchmarks and tests.
+/// Constructs a 3D grid of polygons.
+pub fn _make_grid(count: usize) -> Vec<Polygon<f32, ()>> {
+ let mut polys: Vec<Polygon<f32, ()>> = Vec::with_capacity(count*3);
+ let len = count as f32;
+ polys.extend((0 .. count).map(|i| Polygon {
+ points: [
+ TypedPoint3D::new(0.0, i as f32, 0.0),
+ TypedPoint3D::new(len, i as f32, 0.0),
+ TypedPoint3D::new(len, i as f32, len),
+ TypedPoint3D::new(0.0, i as f32, len),
+ ],
+ normal: TypedPoint3D::new(0.0, 1.0, 0.0),
+ offset: -(i as f32),
+ anchor: 0,
+ }));
+ polys.extend((0 .. count).map(|i| Polygon {
+ points: [
+ TypedPoint3D::new(i as f32, 0.0, 0.0),
+ TypedPoint3D::new(i as f32, len, 0.0),
+ TypedPoint3D::new(i as f32, len, len),
+ TypedPoint3D::new(i as f32, 0.0, len),
+ ],
+ normal: TypedPoint3D::new(1.0, 0.0, 0.0),
+ offset: -(i as f32),
+ anchor: 0,
+ }));
+ polys.extend((0 .. count).map(|i| Polygon {
+ points: [
+ TypedPoint3D::new(0.0, 0.0, i as f32),
+ TypedPoint3D::new(len, 0.0, i as f32),
+ TypedPoint3D::new(len, len, i as f32),
+ TypedPoint3D::new(0.0, len, i as f32),
+ ],
+ normal: TypedPoint3D::new(0.0, 0.0, 1.0),
+ offset: -(i as f32),
+ anchor: 0,
+ }));
+ polys
+}
new file mode 100644
--- /dev/null
+++ b/third_party/rust/plane-split/src/naive.rs
@@ -0,0 +1,177 @@
+use std::{fmt, ops};
+use std::cmp::Ordering;
+use {Intersection, Line, Polygon, Splitter};
+use euclid::TypedPoint3D;
+use euclid::approxeq::ApproxEq;
+use num_traits::{Float, One, Zero};
+
+
+/// Naive plane splitter, has at least O(n^2) complexity.
+pub struct NaiveSplitter<T, U> {
+ result: Vec<Polygon<T, U>>,
+ current: Vec<Polygon<T, U>>,
+ temp: Vec<Polygon<T, U>>,
+}
+
+impl<T, U> NaiveSplitter<T, U> {
+ /// Create a new `NaiveSplitter`.
+ pub fn new() -> Self {
+ NaiveSplitter {
+ result: Vec::new(),
+ current: Vec::new(),
+ temp: Vec::new(),
+ }
+ }
+}
+
+/// Find a closest intersection point between two polygons,
+/// across the specified direction.
+fn intersect_across<T, U>(a: &Polygon<T, U>, b: &Polygon<T, U>,
+ dir: TypedPoint3D<T, U>)
+ -> TypedPoint3D<T, U>
+where
+ T: Copy + fmt::Debug + PartialOrd + ApproxEq<T> +
+ ops::Sub<T, Output=T> + ops::Add<T, Output=T> +
+ ops::Mul<T, Output=T> + ops::Div<T, Output=T> +
+ Zero + One + Float,
+{
+ let pa = a.project_on(&dir).get_bounds();
+ let pb = b.project_on(&dir).get_bounds();
+ let pmin = pa.0.max(pb.0);
+ let pmax = pa.1.min(pb.1);
+ let k = (pmin + pmax) / (T::one() + T::one());
+ debug!("\t\tIntersection pa {:?} pb {:?} k {:?}", pa, pb, k);
+ dir * k
+}
+
+fn partial_sort_by<T, F>(array: &mut [T], fun: F) where
+ F: Fn(&T, &T) -> Ordering,
+ T: fmt::Debug,
+{
+ debug!("\nSorting");
+ if array.is_empty() {
+ return
+ }
+ for i in 0 .. array.len() - 1 {
+ let mut up_start = array.len();
+ // placement is: [i, ... equals ..., up_start, ... greater ..., j]
+ // if this condition fails, everything to the right is greater
+ 'find_smallest: while i + 1 != up_start {
+ let mut j = i + 1;
+ 'partition: loop {
+ debug!("\tComparing {} to {}, up_start = {}", i, j, up_start);
+ let order = fun(&array[i], &array[j]);
+ debug!("\t\t{:?}", order);
+ match order {
+ Ordering::Less => {
+ // push back to "greater" area
+ up_start -= 1;
+ if j == up_start {
+ break 'partition
+ }
+ array.swap(j, up_start);
+ },
+ Ordering::Equal => {
+ // continue
+ j += 1;
+ if j == up_start {
+ // we reached the end of the "equal" area
+ // so our "i" can be placed anywhere
+ break 'find_smallest;
+ }
+ }
+ Ordering::Greater => {
+ array.swap(i, j);
+ up_start -= 1;
+ array.swap(j, up_start);
+ // found a smaller one, push "i" to the "greater" area
+ // and restart the search from the current element
+ break 'partition;
+ },
+ }
+ }
+ }
+ debug!("\tEnding {} with up_start={}, poly {:?}", i, up_start, array[i]);
+ }
+}
+
+
+impl<
+ T: Copy + fmt::Debug + PartialOrd + ApproxEq<T> +
+ ops::Sub<T, Output=T> + ops::Add<T, Output=T> +
+ ops::Mul<T, Output=T> + ops::Div<T, Output=T> +
+ Zero + One + Float,
+ U: fmt::Debug,
+> Splitter<T, U> for NaiveSplitter<T, U> {
+ fn reset(&mut self) {
+ self.result.clear();
+ self.current.clear();
+ self.temp.clear();
+ }
+
+ fn add(&mut self, poly: Polygon<T, U>) {
+ // "current" accumulates all the subdivisions of the originally
+ // added polygon
+ self.current.push(poly);
+ for old in self.result.iter() {
+ for new in self.current.iter_mut() {
+ // temp accumulates all the new subdivisions to be added
+ // to the current, since we can't modify it in place
+ if let Intersection::Inside(line) = old.intersect(new) {
+ let (res_add1, res_add2) = new.split(&line);
+ if let Some(res) = res_add1 {
+ self.temp.push(res);
+ }
+ if let Some(res) = res_add2 {
+ self.temp.push(res);
+ }
+ }
+ }
+ self.current.extend(self.temp.drain(..));
+ }
+ let index = self.result.len();
+ self.result.extend(self.current.drain(..));
+ debug!("Split result: {:?}", &self.result[index..]);
+ }
+
+ //TODO: verify/prove that the sorting approach is consistent
+ fn sort(&mut self, view: TypedPoint3D<T, U>) -> &[Polygon<T, U>] {
+ // choose the most perpendicular axis among these two
+ let axis_pre = {
+ let axis_pre0 = TypedPoint3D::new(T::one(), T::zero(), T::zero());
+ let axis_pre1 = TypedPoint3D::new(T::zero(), T::one(), T::zero());
+ if view.dot(axis_pre0).abs() < view.dot(axis_pre1).abs() {
+ axis_pre0
+ } else {
+ axis_pre1
+ }
+ };
+ // do the orthogonalization
+ let axis_x = view.cross(axis_pre);
+ let axis_y = view.cross(axis_x);
+ debug!("Chosen axis {:?} {:?}", axis_x, axis_y);
+ // sort everything
+ partial_sort_by(&mut self.result, |a, b| {
+ debug!("\t\t{:?}", a);
+ debug!("\t\t{:?}", b);
+ //TODO: proper intersection
+ // compute the origin
+ let comp_x = intersect_across(a, b, axis_x);
+ let comp_y = intersect_across(a, b, axis_y);
+ // line that tries to intersect both
+ let line = Line {
+ origin: comp_x + comp_y,
+ dir: view,
+ };
+ debug!("\t\tGot {:?}", line);
+ // distances across the line
+ let da = a.distance_to_line(&line);
+ let db = b.distance_to_line(&line);
+ debug!("\t\tDistances {:?} {:?}", da, db);
+ // final compare
+ da.partial_cmp(&db).unwrap_or(Ordering::Equal)
+ });
+ // done
+ &self.result
+ }
+}
new file mode 100644
--- /dev/null
+++ b/third_party/rust/plane-split/tests/main.rs
@@ -0,0 +1,237 @@
+extern crate euclid;
+extern crate plane_split;
+
+use euclid::{Point2D, Radians, TypedPoint2D, TypedPoint3D, TypedRect, TypedSize2D, TypedMatrix4D};
+use euclid::approxeq::ApproxEq;
+use plane_split::{Intersection, Line, LineProjection, Polygon};
+
+
+#[test]
+fn line_proj_bounds() {
+ assert_eq!((-5i8, 4), LineProjection { markers: [-5i8, 1, 4, 2] }.get_bounds());
+ assert_eq!((1f32, 4.0), LineProjection { markers: [4f32, 3.0, 2.0, 1.0] }.get_bounds());
+}
+
+#[test]
+fn valid() {
+ let poly_a: Polygon<f32, ()> = Polygon {
+ points: [
+ TypedPoint3D::new(0.0, 0.0, 0.0),
+ TypedPoint3D::new(1.0, 1.0, 1.0),
+ TypedPoint3D::new(1.0, 1.0, 0.0),
+ TypedPoint3D::new(0.0, 1.0, 1.0),
+ ],
+ normal: TypedPoint3D::new(0.0, 1.0, 0.0),
+ offset: -1.0,
+ anchor: 0,
+ };
+ assert!(!poly_a.is_valid()); // points[0] is outside
+ let poly_b: Polygon<f32, ()> = Polygon {
+ points: [
+ TypedPoint3D::new(0.0, 1.0, 0.0),
+ TypedPoint3D::new(1.0, 1.0, 1.0),
+ TypedPoint3D::new(1.0, 1.0, 0.0),
+ TypedPoint3D::new(0.0, 1.0, 1.0),
+ ],
+ normal: TypedPoint3D::new(0.0, 1.0, 0.0),
+ offset: -1.0,
+ anchor: 0,
+ };
+ assert!(!poly_b.is_valid()); // winding is incorrect
+ let poly_c: Polygon<f32, ()> = Polygon {
+ points: [
+ TypedPoint3D::new(0.0, 0.0, 1.0),
+ TypedPoint3D::new(1.0, 0.0, 1.0),
+ TypedPoint3D::new(1.0, 1.0, 1.0),
+ TypedPoint3D::new(0.0, 1.0, 1.0),
+ ],
+ normal: TypedPoint3D::new(0.0, 0.0, 1.0),
+ offset: -1.0,
+ anchor: 0,
+ };
+ assert!(poly_c.is_valid());
+}
+
+#[test]
+fn from_transformed_rect() {
+ let rect: TypedRect<f32, ()> = TypedRect::new(TypedPoint2D::new(10.0, 10.0), TypedSize2D::new(20.0, 30.0));
+ let transform: TypedMatrix4D<f32, (), ()> =
+ TypedMatrix4D::create_rotation(0.5f32.sqrt(), 0.0, 0.5f32.sqrt(), Radians::new(5.0))
+ .pre_translated(0.0, 0.0, 10.0);
+ let poly = Polygon::from_transformed_rect(rect, transform, 0);
+ assert!(poly.is_valid_eps(1e-5));
+}
+
+#[test]
+fn untransform_point() {
+ let poly: Polygon<f32, ()> = Polygon {
+ points: [
+ TypedPoint3D::new(0.0, 0.0, 0.0),
+ TypedPoint3D::new(0.5, 1.0, 0.0),
+ TypedPoint3D::new(1.5, 1.0, 0.0),
+ TypedPoint3D::new(1.0, 0.0, 0.0),
+ ],
+ normal: TypedPoint3D::new(0.0, 1.0, 0.0),
+ offset: 0.0,
+ anchor: 0,
+ };
+ assert_eq!(poly.untransform_point(poly.points[0]), Point2D::new(0.0, 0.0));
+ assert_eq!(poly.untransform_point(poly.points[1]), Point2D::new(1.0, 0.0));
+ assert_eq!(poly.untransform_point(poly.points[2]), Point2D::new(1.0, 1.0));
+ assert_eq!(poly.untransform_point(poly.points[3]), Point2D::new(0.0, 1.0));
+}
+
+#[test]
+fn are_outside() {
+ let poly: Polygon<f32, ()> = Polygon {
+ points: [
+ TypedPoint3D::new(0.0, 0.0, 1.0),
+ TypedPoint3D::new(1.0, 0.0, 1.0),
+ TypedPoint3D::new(1.0, 1.0, 1.0),
+ TypedPoint3D::new(0.0, 1.0, 1.0),
+ ],
+ normal: TypedPoint3D::new(0.0, 0.0, 1.0),
+ offset: -1.0,
+ anchor: 0,
+ };
+ assert!(poly.is_valid());
+ assert!(poly.are_outside(&[
+ TypedPoint3D::new(0.0, 0.0, 1.1),
+ TypedPoint3D::new(1.0, 1.0, 2.0),
+ ]));
+ assert!(poly.are_outside(&[
+ TypedPoint3D::new(0.5, 0.5, 1.0),
+ ]));
+ assert!(!poly.are_outside(&[
+ TypedPoint3D::new(0.0, 0.0, 1.0),
+ TypedPoint3D::new(0.0, 0.0, -1.0),
+ ]));
+}
+
+#[test]
+fn intersect() {
+ let poly_a: Polygon<f32, ()> = Polygon {
+ points: [
+ TypedPoint3D::new(0.0, 0.0, 1.0),
+ TypedPoint3D::new(1.0, 0.0, 1.0),
+ TypedPoint3D::new(1.0, 1.0, 1.0),
+ TypedPoint3D::new(0.0, 1.0, 1.0),
+ ],
+ normal: TypedPoint3D::new(0.0, 0.0, 1.0),
+ offset: -1.0,
+ anchor: 0,
+ };
+ assert!(poly_a.is_valid());
+ let poly_b: Polygon<f32, ()> = Polygon {
+ points: [
+ TypedPoint3D::new(0.5, 0.0, 2.0),
+ TypedPoint3D::new(0.5, 1.0, 2.0),
+ TypedPoint3D::new(0.5, 1.0, 0.0),
+ TypedPoint3D::new(0.5, 0.0, 0.0),
+ ],
+ normal: TypedPoint3D::new(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.signed_distance_to(&intersection.origin).approx_eq(&0.0));
+ assert!(poly_b.signed_distance_to(&intersection.origin).approx_eq(&0.0));
+ // confirm the direction is coplanar to both planes
+ assert!(poly_a.normal.dot(intersection.dir).approx_eq(&0.0));
+ assert!(poly_b.normal.dot(intersection.dir).approx_eq(&0.0));
+
+ let poly_c: Polygon<f32, ()> = Polygon {
+ points: [
+ TypedPoint3D::new(0.0, -1.0, 2.0),
+ TypedPoint3D::new(0.0, -1.0, 0.0),
+ TypedPoint3D::new(0.0, 0.0, 0.0),
+ TypedPoint3D::new(0.0, 0.0, 2.0),
+ ],
+ normal: TypedPoint3D::new(1.0, 0.0, 0.0),
+ offset: 0.0,
+ anchor: 0,
+ };
+ assert!(poly_c.is_valid());
+ let poly_d: Polygon<f32, ()> = Polygon {
+ points: [
+ TypedPoint3D::new(0.0, 0.0, 0.5),
+ TypedPoint3D::new(1.0, 0.0, 0.5),
+ TypedPoint3D::new(1.0, 1.0, 0.5),
+ TypedPoint3D::new(0.0, 1.0, 0.5),
+ ],
+ normal: TypedPoint3D::new(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<f32, ()>, extra_count: u8, line: Line<f32, ()>) {
+ assert!(line.is_valid());
+ let mut poly = poly_base.clone();
+ let (extra1, extra2) = poly.split(&line);
+ 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<f32, ()> = Polygon {
+ points: [
+ TypedPoint3D::new(0.0, 1.0, 0.0),
+ TypedPoint3D::new(1.0, 1.0, 0.0),
+ TypedPoint3D::new(1.0, 1.0, 1.0),
+ TypedPoint3D::new(0.0, 1.0, 1.0),
+ ],
+ normal: TypedPoint3D::new(0.0, 1.0, 0.0),
+ offset: -1.0,
+ anchor: 0,
+ };
+
+ // non-intersecting line
+ test_cut(&poly, 0, Line {
+ origin: TypedPoint3D::new(0.0, 1.0, 0.5),
+ dir: TypedPoint3D::new(0.0, 1.0, 0.0),
+ });
+
+ // simple cut (diff=2)
+ test_cut(&poly, 1, Line {
+ origin: TypedPoint3D::new(0.0, 1.0, 0.5),
+ dir: TypedPoint3D::new(1.0, 0.0, 0.0),
+ });
+
+ // complex cut (diff=1, wrapped)
+ test_cut(&poly, 2, Line {
+ origin: TypedPoint3D::new(0.0, 1.0, 0.5),
+ dir: TypedPoint3D::new(0.5f32.sqrt(), 0.0, -0.5f32.sqrt()),
+ });
+
+ // complex cut (diff=1, non-wrapped)
+ test_cut(&poly, 2, Line {
+ origin: TypedPoint3D::new(0.5, 1.0, 0.0),
+ dir: TypedPoint3D::new(0.5f32.sqrt(), 0.0, 0.5f32.sqrt()),
+ });
+
+ // complex cut (diff=3)
+ test_cut(&poly, 2, Line {
+ origin: TypedPoint3D::new(0.5, 1.0, 0.0),
+ dir: TypedPoint3D::new(-0.5f32.sqrt(), 0.0, 0.5f32.sqrt()),
+ });
+}
new file mode 100644
--- /dev/null
+++ b/third_party/rust/plane-split/tests/split.rs
@@ -0,0 +1,80 @@
+extern crate euclid;
+extern crate plane_split;
+
+use std::f32::consts::FRAC_PI_4;
+use euclid::{Radians, TypedMatrix4D, TypedPoint2D, TypedPoint3D, TypedSize2D, TypedRect};
+use plane_split::{BspSplitter, NaiveSplitter, Polygon, Splitter, _make_grid};
+
+
+fn grid_impl(count: usize, splitter: &mut Splitter<f32, ()>) {
+ let polys = _make_grid(count);
+ let result = splitter.solve(&polys, TypedPoint3D::new(0.0, 0.0, 1.0));
+ assert_eq!(result.len(), count + count*count + count*count*count);
+}
+
+#[test]
+fn grid_naive() {
+ grid_impl(2, &mut NaiveSplitter::new());
+}
+
+#[test]
+fn grid_bsp() {
+ grid_impl(2, &mut BspSplitter::new());
+}
+
+
+fn sort_rotation(splitter: &mut Splitter<f32, ()>) {
+ let transform0: TypedMatrix4D<f32, (), ()> =
+ TypedMatrix4D::create_rotation(0.0, 1.0, 0.0, Radians::new(-FRAC_PI_4));
+ let transform1: TypedMatrix4D<f32, (), ()> =
+ TypedMatrix4D::create_rotation(0.0, 1.0, 0.0, Radians::new(0.0));
+ let transform2: TypedMatrix4D<f32, (), ()> =
+ TypedMatrix4D::create_rotation(0.0, 1.0, 0.0, Radians::new(FRAC_PI_4));
+
+ let rect: TypedRect<f32, ()> = TypedRect::new(TypedPoint2D::new(-10.0, -10.0), TypedSize2D::new(20.0, 20.0));
+ let polys = [
+ Polygon::from_transformed_rect(rect, transform0, 0),
+ Polygon::from_transformed_rect(rect, transform1, 1),
+ Polygon::from_transformed_rect(rect, transform2, 2),
+ ];
+
+ let result = splitter.solve(&polys, TypedPoint3D::new(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_naive() {
+ sort_rotation(&mut NaiveSplitter::new());
+}
+
+#[test]
+fn rotation_bsp() {
+ sort_rotation(&mut BspSplitter::new());
+}
+
+
+fn sort_trivial(splitter: &mut Splitter<f32, ()>) {
+ let anchors: Vec<_> = (0usize .. 10).collect();
+ let rect: TypedRect<f32, ()> = TypedRect::new(TypedPoint2D::new(-10.0, -10.0), TypedSize2D::new(20.0, 20.0));
+ let polys: Vec<_> = anchors.iter().map(|&anchor| {
+ let transform: TypedMatrix4D<f32, (), ()> = TypedMatrix4D::create_translation(0.0, 0.0, anchor as f32);
+ Polygon::from_transformed_rect(rect, transform, anchor)
+ }).collect();
+
+ let result = splitter.solve(&polys, TypedPoint3D::new(0.0, 0.0, -1.0));
+ let anchors1: Vec<_> = result.iter().map(|p| p.anchor).collect();
+ let mut anchors2 = anchors1.clone();
+ anchors2.sort_by_key(|&a| -(a as i32));
+ assert_eq!(anchors1, anchors2); //make sure Z is sorted backwards
+}
+
+#[test]
+fn trivial_naive() {
+ sort_trivial(&mut NaiveSplitter::new());
+}
+
+#[test]
+fn trivial_bsp() {
+ sort_trivial(&mut BspSplitter::new());
+}