diff options
Diffstat (limited to 'third_party/rust/plane-split/src/clip.rs')
-rw-r--r-- | third_party/rust/plane-split/src/clip.rs | 142 |
1 files changed, 142 insertions, 0 deletions
diff --git a/third_party/rust/plane-split/src/clip.rs b/third_party/rust/plane-split/src/clip.rs new file mode 100644 index 0000000000..4425692085 --- /dev/null +++ b/third_party/rust/plane-split/src/clip.rs @@ -0,0 +1,142 @@ +use crate::{Intersection, NegativeHemisphereError, Plane, Polygon}; + +use euclid::default::{Rect, Scale, Transform3D, Vector3D}; + +use std::{fmt, iter, mem}; + +/// A helper object to clip polygons by a number of planes. +#[derive(Debug)] +pub struct Clipper<A> { + clips: Vec<Plane>, + results: Vec<Polygon<A>>, + temp: Vec<Polygon<A>>, +} + +impl<A: Copy + fmt::Debug> Clipper<A> { + /// Create a new clipper object. + pub fn new() -> Self { + Clipper { + clips: Vec::new(), + results: Vec::new(), + temp: Vec::new(), + } + } + + /// Reset the clipper internals, but preserve the allocation. + pub fn reset(&mut self) { + self.clips.clear(); + } + + /// Extract the clipping planes that define the frustum for a given transformation. + pub fn frustum_planes( + t: &Transform3D<f64>, + bounds: Option<Rect<f64>>, + ) -> Result<impl Iterator<Item = Plane>, NegativeHemisphereError> { + let mw = Vector3D::new(t.m14, t.m24, t.m34); + let plane_positive = Plane::from_unnormalized(mw, t.m44)?; + + let bounds_iter_maybe = match bounds { + Some(bounds) => { + let mx = Vector3D::new(t.m11, t.m21, t.m31); + let left = bounds.origin.x; + let plane_left = + Plane::from_unnormalized(mx - mw * Scale::new(left), t.m41 - t.m44 * left)?; + let right = bounds.origin.x + bounds.size.width; + let plane_right = + Plane::from_unnormalized(mw * Scale::new(right) - mx, t.m44 * right - t.m41)?; + + let my = Vector3D::new(t.m12, t.m22, t.m32); + let top = bounds.origin.y; + let plane_top = + Plane::from_unnormalized(my - mw * Scale::new(top), t.m42 - t.m44 * top)?; + let bottom = bounds.origin.y + bounds.size.height; + let plane_bottom = + Plane::from_unnormalized(mw * Scale::new(bottom) - my, t.m44 * bottom - t.m42)?; + + Some( + plane_left + .into_iter() + .chain(plane_right) + .chain(plane_top) + .chain(plane_bottom), + ) + } + None => None, + }; + + Ok(bounds_iter_maybe + .into_iter() + .flat_map(|pi| pi) + .chain(plane_positive)) + } + + /// Add a clipping plane to the list. The plane will clip everything behind it, + /// where the direction is set by the plane normal. + pub fn add(&mut self, plane: Plane) { + self.clips.push(plane); + } + + /// Clip specified polygon by the contained planes, return the fragmented polygons. + pub fn clip(&mut self, polygon: Polygon<A>) -> &[Polygon<A>] { + log::debug!("\tClipping {:?}", polygon); + self.results.clear(); + self.results.push(polygon); + + for clip in &self.clips { + self.temp.clear(); + mem::swap(&mut self.results, &mut self.temp); + + for mut poly in self.temp.drain(..) { + let dist = match poly.intersect_plane(clip) { + Intersection::Inside(line) => { + let (res1, res2) = poly.split_with_normal(&line, &clip.normal); + self.results.extend( + iter::once(poly) + .chain(res1) + .chain(res2) + .filter(|p| clip.signed_distance_sum_to(p) > 0.0), + ); + continue; + } + Intersection::Coplanar => { + let ndot = poly.plane.normal.dot(clip.normal); + clip.offset - ndot * poly.plane.offset + } + Intersection::Outside => clip.signed_distance_sum_to(&poly), + }; + + if dist > 0.0 { + self.results.push(poly); + } + } + } + + &self.results + } + + /// Clip the primitive with the frustum of the specified transformation, + /// returning a sequence of polygons in the transformed space. + /// Returns None if the transformation can't be frustum clipped. + pub fn clip_transformed<'a>( + &'a mut self, + polygon: Polygon<A>, + transform: &'a Transform3D<f64>, + bounds: Option<Rect<f64>>, + ) -> Result<impl 'a + Iterator<Item = Polygon<A>>, NegativeHemisphereError> { + let planes = Self::frustum_planes(transform, bounds)?; + + let old_count = self.clips.len(); + self.clips.extend(planes); + self.clip(polygon); + // remove the frustum planes + while self.clips.len() > old_count { + self.clips.pop(); + } + + let polys = self + .results + .drain(..) + .flat_map(move |poly| poly.transform(transform)); + Ok(polys) + } +} |