plane_split/
clip.rs

1use crate::{Intersection, NegativeHemisphereError, Plane, Polygon};
2
3use euclid::default::{Rect, Scale, Transform3D, Vector3D};
4
5use std::{fmt, iter, mem};
6
7/// A helper object to clip polygons by a number of planes.
8#[derive(Debug)]
9pub struct Clipper<A> {
10    clips: Vec<Plane>,
11    results: Vec<Polygon<A>>,
12    temp: Vec<Polygon<A>>,
13}
14
15impl<A: Copy + fmt::Debug> Clipper<A> {
16    /// Create a new clipper object.
17    pub fn new() -> Self {
18        Clipper {
19            clips: Vec::new(),
20            results: Vec::new(),
21            temp: Vec::new(),
22        }
23    }
24
25    /// Reset the clipper internals, but preserve the allocation.
26    pub fn reset(&mut self) {
27        self.clips.clear();
28    }
29
30    /// Extract the clipping planes that define the frustum for a given transformation.
31    pub fn frustum_planes(
32        t: &Transform3D<f64>,
33        bounds: Option<Rect<f64>>,
34    ) -> Result<impl Iterator<Item = Plane>, NegativeHemisphereError> {
35        let mw = Vector3D::new(t.m14, t.m24, t.m34);
36        let plane_positive = Plane::from_unnormalized(mw, t.m44)?;
37
38        let bounds_iter_maybe = match bounds {
39            Some(bounds) => {
40                let mx = Vector3D::new(t.m11, t.m21, t.m31);
41                let left = bounds.origin.x;
42                let plane_left =
43                    Plane::from_unnormalized(mx - mw * Scale::new(left), t.m41 - t.m44 * left)?;
44                let right = bounds.origin.x + bounds.size.width;
45                let plane_right =
46                    Plane::from_unnormalized(mw * Scale::new(right) - mx, t.m44 * right - t.m41)?;
47
48                let my = Vector3D::new(t.m12, t.m22, t.m32);
49                let top = bounds.origin.y;
50                let plane_top =
51                    Plane::from_unnormalized(my - mw * Scale::new(top), t.m42 - t.m44 * top)?;
52                let bottom = bounds.origin.y + bounds.size.height;
53                let plane_bottom =
54                    Plane::from_unnormalized(mw * Scale::new(bottom) - my, t.m44 * bottom - t.m42)?;
55
56                Some(
57                    plane_left
58                        .into_iter()
59                        .chain(plane_right)
60                        .chain(plane_top)
61                        .chain(plane_bottom),
62                )
63            }
64            None => None,
65        };
66
67        Ok(bounds_iter_maybe
68            .into_iter()
69            .flat_map(|pi| pi)
70            .chain(plane_positive))
71    }
72
73    /// Add a clipping plane to the list. The plane will clip everything behind it,
74    /// where the direction is set by the plane normal.
75    pub fn add(&mut self, plane: Plane) {
76        self.clips.push(plane);
77    }
78
79    /// Clip specified polygon by the contained planes, return the fragmented polygons.
80    pub fn clip(&mut self, polygon: Polygon<A>) -> &[Polygon<A>] {
81        log::debug!("\tClipping {:?}", polygon);
82        self.results.clear();
83        self.results.push(polygon);
84
85        for clip in &self.clips {
86            self.temp.clear();
87            mem::swap(&mut self.results, &mut self.temp);
88
89            for mut poly in self.temp.drain(..) {
90                let dist = match poly.intersect_plane(clip) {
91                    Intersection::Inside(line) => {
92                        let (res1, res2) = poly.split_with_normal(&line, &clip.normal);
93                        self.results.extend(
94                            iter::once(poly)
95                                .chain(res1)
96                                .chain(res2)
97                                .filter(|p| clip.signed_distance_sum_to(p) > 0.0),
98                        );
99                        continue;
100                    }
101                    Intersection::Coplanar => {
102                        let ndot = poly.plane.normal.dot(clip.normal);
103                        clip.offset - ndot * poly.plane.offset
104                    }
105                    Intersection::Outside => clip.signed_distance_sum_to(&poly),
106                };
107
108                if dist > 0.0 {
109                    self.results.push(poly);
110                }
111            }
112        }
113
114        &self.results
115    }
116
117    /// Clip the primitive with the frustum of the specified transformation,
118    /// returning a sequence of polygons in the transformed space.
119    /// Returns None if the transformation can't be frustum clipped.
120    pub fn clip_transformed<'a>(
121        &'a mut self,
122        polygon: Polygon<A>,
123        transform: &'a Transform3D<f64>,
124        bounds: Option<Rect<f64>>,
125    ) -> Result<impl 'a + Iterator<Item = Polygon<A>>, NegativeHemisphereError> {
126        let planes = Self::frustum_planes(transform, bounds)?;
127
128        let old_count = self.clips.len();
129        self.clips.extend(planes);
130        self.clip(polygon);
131        // remove the frustum planes
132        while self.clips.len() > old_count {
133            self.clips.pop();
134        }
135
136        let polys = self
137            .results
138            .drain(..)
139            .flat_map(move |poly| poly.transform(transform));
140        Ok(polys)
141    }
142}
plane_split/clip.rs

plane_split/
clip.rs
