plane_split/
lib.rs

1/*!
2Plane splitting.
3
4Uses [euclid](https://crates.io/crates/euclid) for the math basis.
5Introduces new geometrical primitives and associated logic.
6
7Automatically splits a given set of 4-point polygons into sub-polygons
8that don't intersect each other. This is useful for WebRender, to sort
9the resulting sub-polygons by depth and avoid transparency blending issues.
10*/
11#![warn(missing_docs)]
12
13mod bsp;
14mod clip;
15mod polygon;
16
17pub use polygon::PlaneCut;
18
19use euclid::{
20    approxeq::ApproxEq,
21    default::{Point3D, Scale, Vector3D},
22};
23
24use std::ops;
25
26pub use self::bsp::BspSplitter;
27pub use self::clip::Clipper;
28pub use self::polygon::{Intersection, LineProjection, Polygon};
29
30fn is_zero(value: f64) -> bool {
31    //HACK: this is rough, but the original Epsilon is too strict
32    (value * value).approx_eq(&0.0)
33}
34
35fn is_zero_vec(vec: Vector3D<f64>) -> bool {
36    vec.dot(vec).approx_eq(&0.0)
37}
38
39/// A generic line.
40#[derive(Debug)]
41pub struct Line {
42    /// Arbitrary point on the line.
43    pub origin: Point3D<f64>,
44    /// Normalized direction of the line.
45    pub dir: Vector3D<f64>,
46}
47
48impl Line {
49    /// Check if the line has consistent parameters.
50    pub fn is_valid(&self) -> bool {
51        is_zero(self.dir.dot(self.dir) - 1.0)
52    }
53    /// Check if two lines match each other.
54    pub fn matches(&self, other: &Self) -> bool {
55        let diff = self.origin - other.origin;
56        is_zero_vec(self.dir.cross(other.dir)) && is_zero_vec(self.dir.cross(diff))
57    }
58
59    /// Intersect an edge given by the end points.
60    /// Returns the fraction of the edge where the intersection occurs.
61    fn intersect_edge(&self, edge: ops::Range<Point3D<f64>>) -> Option<f64> {
62        let edge_vec = edge.end - edge.start;
63        let origin_vec = self.origin - edge.start;
64        // edge.start + edge_vec * t = r + k * d
65        // (edge.start, d) + t * (edge_vec, d) - (r, d) = k
66        // edge.start + t * edge_vec = r + t * (edge_vec, d) * d + (start-r, d) * d
67        // t * (edge_vec - (edge_vec, d)*d) = origin_vec - (origin_vec, d) * d
68        let pr = origin_vec - self.dir * self.dir.dot(origin_vec);
69        let pb = edge_vec - self.dir * self.dir.dot(edge_vec);
70        let denom = pb.dot(pb);
71        if denom.approx_eq(&0.0) {
72            None
73        } else {
74            Some(pr.dot(pb) / denom)
75        }
76    }
77}
78
79/// An infinite plane in 3D space, defined by equation:
80/// dot(v, normal) + offset = 0
81/// When used for plane splitting, it's defining a hemisphere
82/// with equation "dot(v, normal) + offset > 0".
83#[derive(Debug, PartialEq)]
84pub struct Plane {
85    /// Normalized vector perpendicular to the plane.
86    pub normal: Vector3D<f64>,
87    /// Constant offset from the normal plane, specified in the
88    /// direction opposite to the normal.
89    pub offset: f64,
90}
91
92impl Clone for Plane {
93    fn clone(&self) -> Self {
94        Plane {
95            normal: self.normal.clone(),
96            offset: self.offset.clone(),
97        }
98    }
99}
100
101/// An error returned when everything would end up projected
102/// to the negative hemisphere (W <= 0.0);
103#[derive(Clone, Debug, Hash, PartialEq, PartialOrd)]
104pub struct NegativeHemisphereError;
105
106impl Plane {
107    /// Construct a new plane from unnormalized equation.
108    pub fn from_unnormalized(
109        normal: Vector3D<f64>,
110        offset: f64,
111    ) -> Result<Option<Self>, NegativeHemisphereError> {
112        let square_len = normal.square_length();
113        if square_len < f64::approx_epsilon() * f64::approx_epsilon() {
114            if offset > 0.0 {
115                Ok(None)
116            } else {
117                Err(NegativeHemisphereError)
118            }
119        } else {
120            let kf = 1.0 / square_len.sqrt();
121            Ok(Some(Plane {
122                normal: normal * Scale::new(kf),
123                offset: offset * kf,
124            }))
125        }
126    }
127
128    /// Check if this plane contains another one.
129    pub fn contains(&self, other: &Self) -> bool {
130        //TODO: actually check for inside/outside
131        self.normal == other.normal && self.offset == other.offset
132    }
133
134    /// Return the signed distance from this plane to a point.
135    /// The distance is negative if the point is on the other side of the plane
136    /// from the direction of the normal.
137    pub fn signed_distance_to(&self, point: &Point3D<f64>) -> f64 {
138        point.to_vector().dot(self.normal) + self.offset
139    }
140
141    /// Compute the distance across the line to the plane plane,
142    /// starting from the line origin.
143    pub fn distance_to_line(&self, line: &Line) -> f64 {
144        self.signed_distance_to(&line.origin) / -self.normal.dot(line.dir)
145    }
146
147    /// Compute the sum of signed distances to each of the points
148    /// of another plane. Useful to know the relation of a plane that
149    /// is a product of a split, and we know it doesn't intersect `self`.
150    pub fn signed_distance_sum_to<A>(&self, poly: &Polygon<A>) -> f64 {
151        poly.points
152            .iter()
153            .fold(0.0, |u, p| u + self.signed_distance_to(p))
154    }
155
156    /// Check if a convex shape defined by a set of points is completely
157    /// outside of this plane. Merely touching the surface is not
158    /// considered an intersection.
159    pub fn are_outside(&self, points: &[Point3D<f64>]) -> bool {
160        let d0 = self.signed_distance_to(&points[0]);
161        points[1..]
162            .iter()
163            .all(|p| self.signed_distance_to(p) * d0 > 0.0)
164    }
165
166    //TODO(breaking): turn this into Result<Line, DotProduct>
167    /// Compute the line of intersection with another plane.
168    pub fn intersect(&self, other: &Self) -> Option<Line> {
169        // compute any point on the intersection between planes
170        // (n1, v) + d1 = 0
171        // (n2, v) + d2 = 0
172        // v = a*n1/w + b*n2/w; w = (n1, n2)
173        // v = (d2*w - d1) / (1 - w*w) * n1 - (d2 - d1*w) / (1 - w*w) * n2
174        let w = self.normal.dot(other.normal);
175        let divisor = 1.0 - w * w;
176        if divisor < f64::approx_epsilon() * f64::approx_epsilon() {
177            return None;
178        }
179        let origin = Point3D::origin() + self.normal * ((other.offset * w - self.offset) / divisor)
180            - other.normal * ((other.offset - self.offset * w) / divisor);
181
182        let cross_dir = self.normal.cross(other.normal);
183        // note: the cross product isn't too close to zero
184        // due to the previous check
185
186        Some(Line {
187            origin,
188            dir: cross_dir.normalize(),
189        })
190    }
191}
192
193/// Helper method used for benchmarks and tests.
194/// Constructs a 3D grid of polygons.
195#[doc(hidden)]
196pub fn make_grid(count: usize) -> Vec<Polygon<usize>> {
197    let mut polys: Vec<Polygon<usize>> = Vec::with_capacity(count * 3);
198    let len = count as f64;
199    polys.extend((0..count).map(|i| Polygon {
200        points: [
201            Point3D::new(0.0, i as f64, 0.0),
202            Point3D::new(len, i as f64, 0.0),
203            Point3D::new(len, i as f64, len),
204            Point3D::new(0.0, i as f64, len),
205        ],
206        plane: Plane {
207            normal: Vector3D::new(0.0, 1.0, 0.0),
208            offset: -(i as f64),
209        },
210        anchor: 0,
211    }));
212    polys.extend((0..count).map(|i| Polygon {
213        points: [
214            Point3D::new(i as f64, 0.0, 0.0),
215            Point3D::new(i as f64, len, 0.0),
216            Point3D::new(i as f64, len, len),
217            Point3D::new(i as f64, 0.0, len),
218        ],
219        plane: Plane {
220            normal: Vector3D::new(1.0, 0.0, 0.0),
221            offset: -(i as f64),
222        },
223        anchor: 0,
224    }));
225    polys.extend((0..count).map(|i| Polygon {
226        points: [
227            Point3D::new(0.0, 0.0, i as f64),
228            Point3D::new(len, 0.0, i as f64),
229            Point3D::new(len, len, i as f64),
230            Point3D::new(0.0, len, i as f64),
231        ],
232        plane: Plane {
233            normal: Vector3D::new(0.0, 0.0, 1.0),
234            offset: -(i as f64),
235        },
236        anchor: 0,
237    }));
238    polys
239}
plane_split/lib.rs

plane_split/
lib.rs
