1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
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)
    }
}